la definizione di algoritmo, nelle sue diverse varianti, esige
l'eseguibilità dei passi, o
l'effettiva computabilità delle
operazioni, da parte dell'esecutore o agente di calcolo
nella descrizione di un algoritmo
si fa dunque riferimento, spesso implicito, alle effettive capacità
dell'esecutore, o al suo livello cognitivo
ad esempio, una descrizione più concisa dell'algoritmo di cottura dell'uovo alla coque già visto può presupporre
che l'esecutore sappia riconoscere un uovo fresco, e abbia qualche
familiarità con l'uso dei fornelli:
accendi una fiamma vivace sotto un pentolino con un uovo fresco immerso
in acqua fredda
all'ebollizione, modera la fiamma e spegni dopo 100 secondi circa
blocca la cottura temperando con acqua fredda
questa descrizione è a un più alto livello di astrazione rispetto alla precedente perché, appunto,
astrae da alcuni dettagli, inutili al presupposto livello cognitivo
dell'esecutore
per converso, la descrizione più dettagliata è un raffinamento di quella ora vista perché ne precisa alcuni passi,
sì da renderli eseguibili da un agente meno esperto
astrazione e raffinamento sono concetti fondamentali, inerenti
qualsiasi genere di descrizione, non solo quella di algoritmi
si costituisce naturalmente una gerarchia di livelli di astrazione in base alla presenza di dettagli,
a un livello inferiore, dai quali si astrae al livello superiore
la struttura di un libro in: indice, capitoli, sezioni, sottosezioni,
paragrafi, è un esempio familiare di organizzazione dell'informazione
per successivi livelli di astrazione (decrescente)
nell'evoluzione storica dei linguaggi di programmazione è facilmente
riconoscibile una tendenza verso livelli di astrazione sempre più alti,
cioè meno vincolati a caratteristiche degli agenti di calcolo
astrazione e raffinamento danno anche luogo a importanti
principi metodologici, utili al progetto
di algoritmi, esposti nella prossima lezione
al momento, questi concetti ci tornano utili per dotarci di una notazione
agevole per la rappresentazione di algoritmi
i calcolatori non sono gli esclusivi destinatari di descrizioni di algoritmi
spesso accade di voler descrivere una soluzione algoritmica di un problema
per comunicarla ad altre persone
il linguaggio naturale sembra conveniente a tal fine, ma si presta ad
ambiguità, e inoltre non fornisce supporto immediato ai costrutti più
tipici degli algoritmi;
d'altra parte, i linguaggi di programmazione
pongono vincoli formali spesso eccessivi a fini di comunicazione
le primitive di una rappresentazione
ne sono i costituenti di base, cioè sono:
le sue componenti elementari, al livello di astrazione della rappresentazione
costituite da termini che designano azioni interpretabili ed eseguibili dall'esecutore (reale o presupposto)
dell'algoritmo
tipici esempi di primitive in descrizioni di algoritmi sono:
oltre alle primitive, la rappresentazione di un algoritmo necessita di
regole di composizione
queste si applicano alle primitive, come pure a espressioni composte risultanti dall'applicazione delle regole
lo pseudocodice è una tecnica informale di
rappresentazione di algoritmi nella quale:
le primitive sono espressioni il cui
significato si assume noto
le regole di composizione sono espresse da costrutti, in linguaggio naturale, simili alle strutture di controllo
più frequenti nei linguaggi di programmazione, che esaminiamo fra breve:
sequenza, alternativa, iterazione, etc.
in buona sostanza, la rappresentazione di un algoritmo in pseudocodice
ha le stesse caratteristiche strutturali delle sue rappresentazioni in
linguaggi di programmazione (di alto livello), ma non è soggetta ai
rigidi vincoli sintattici di tali linguaggi
facciamoci una prima idea della rappresentazione in pseudocodice
attraverso un semplice esempio: la ricerca del massimo in un insieme
finito di numeri
ipotizziamo che l'insieme sia rappresentato da una sequenza di numeri
naturali fornita in ingresso, dove l'immissione di un numero negativo
segnala la fine della sequenza in input
conveniamo che v ← E
designi l'assegnamento del valore dell'espressione E alla variabile v
funzione massimo
candidato ← -1
leggi nuovo
finché nuovo ≥ 0
ripeti:
se nuovo > candidato
allora candidato ← nuovo
leggi nuovo
fine ciclo
se candidato ≥ 0
allora scrivi candidato
altrimenti scrivi "insieme vuoto?!"
operatori di confronto (relativi all'ordinamento dei numeri):
"≥",
">"
dichiarazione di funzione ingresso/uscita:
funzionenome
lettura dal canale d'ingresso: leggivariabile
scrittura sul canale di uscita: scriviespressione
gli operatori di confronto sono di tipo
booleano,
cioè formano, con i loro argomenti, espressioni la cui valutazione dà un
valore di verità:
vero o
falso;
nell'esempio visto si hanno tre espressioni di tal tipo,
costituenti la condizione in altrettante
strutture di controllo
il costrutto finchécondizione ...
fine ciclo
è una struttura di controllo iterativa :
lo esaminiamo appresso, assieme ad altre strutture di questo tipo
una struttura di controllo implicita nelle descrizioni di algoritmi è la
sequenza: in assenza di costrutti che alterino
l'ordine di esecuzione, si intende che i passi dell'algoritmo vadano eseguiti
nell'ordine in cui sono descritti
come vedremo fra poco, sequenza e iterazione giocano un ruolo fondamentale
nella costruzione di algoritmi
stato: la mappa dei valori assegnati alle
variabili, in un dato momento dell'esecuzione
ingredienti essenziali di una struttura
iterativa (o ciclo, ingl.
loop ) :
inizializzazione :
stabilisce uno stato iniziale per l'iterazione;
lo stato è modificabile nell'esecuzione iterativa del corpo del ciclo
condizione di continuazione :
da valutare ad ogni iterazione; quando è falsa, l'esecuzione iterativa termina
corpo del ciclo :
costrutto eseguibile iterativamente; di solito modifica lo stato, fino a rendere falsa la condizione di continuazione
N.B. talvolta l'inizializzazione è
realizzata esternamente alla struttura iterativa propriamente detta,
che è composta in sequenza con essa
pseudocodice:
finchécondizioneripeti:corpo del ciclofine ciclo
in questa struttura l'inizializzazione è esterna, e precede in sequenza
il primo controllo della condizione di continuazione
pseudocodice:
ripeti:corpo del ciclofinchécondizionefine ciclo
anche in questa struttura l'inizializzazione è esterna, e precede
in sequenza la prima esecuzione del corpo del ciclo
almeno una esecuzione del corpo del ciclo avviene sempre, cioè indipendentemente dal valore della condizione
di continuazione, poiché quest'ultima viene valutata solo alla fine di
ciascuna iterazione
N.B. attenzione alla traduzione nell'inglese
repeat ... until condition end loop :
"until" significa finché non, dunque condition è una
condizione di terminazione, ovvero l'opposta
della condizione di continuazione la traduzione che, invece, corrisponde allo pseudocodice in questione è: repeat ... while condition end loop
ipotizziamo che il nome da cercare, e il nome di un file contenente
l'elenco, siano i due argomenti della funzione desiderata, che produrrà
in uscita un numero naturale ; questo indicherà
la posizione, a partire da 1, (della prima occorrenza) del nome nell'elenco,
se il nome è nell'elenco, altrimenti sarà 0
estendiamo le primitive dello pseudocodice con
dafileleggivariabile :
per la lettura sequenziale di un elemento (nome) da un file
eoffile :
condizione vera sse si è tentato di leggere oltre l'ultimo elemento di
file
operatori booleani di significato immediato
funzione trova (nome, file)
posizione ← 0
ripeti:
da file
leggi elemento
se non eof file
allora posizione ← posizione + 1
finché non ( elemento = nome
oppure eof file )
fine ciclo
se eof file
allora scrivi 0
altrimenti scrivi posizione
il ciclo a condizione anticipata è
la
struttura iterativa fondamentale:
tutte le altre strutture iterative possono essere realizzate mediante
(uso opportuno di) sequenza e ciclo a condizione anticipata
non vale il converso
versione ridotta del Teorema di Böhm-Jacopini:
sequenza e ciclo a condizione anticipata bastano per costruire qualsiasi algoritmo
infatti, ad esempio, si possono realizzare le strutture condizionali viste
prima come segue:
secondizioneallorapseudocodice
con un ciclo a condizione anticipata che venga eseguito al più una volta
secondizioneallorapseudocodicealtrimentipseudocodice
con due cicli a condizione anticipata, ciascuno dei quali venga eseguito
al più una volta, e aventi opposte condizioni di continuazione (purché
l'esecuzione del corpo del primo ciclo non influisca sulla condizione di
continuazione del secondo ciclo)
problema:
ricerca di tutte le occorrenze di una sequenza (contigua) di simboli
S =
S1...Sk
in una data sequenza M =
M1...Mn
di simboli dello stesso alfabeto {A,T,C,G}, con n > k
si vuole una funzione che, date le due sequenze come argomenti, produca
in uscita la sequenza (eventualmente vuota) delle posizioni iniziali delle
occorrenze di S in M
assumiamo di disporre delle seguenti operazioni primitive su sequenze:
lunghezza (X) :
dà il numero di occorrenze di simboli nella sequenza
X
estrai (X, p, k)
: produce la sottosequenza contigua, di lunghezza
k, della sequenza
X a partire dalla posizione
p (sia p≥ 1,
e la sequenza X sia di lunghezza almeno p+k-1)
X=Y : eguaglianza, vera sse
X e Y
hanno la stessa lunghezza e
Xi=Yi
per ogni posizione i
funzione trova_gene (S, M)
posizione ← 1
k ← lunghezza(S)
n ← lunghezza(M)
finché posizione + k - 1 ≤ n
ripeti:
se S =estrai(M, posizione, k)
allora scrivi posizione
dove (parte del)l'inizializzazione e la condizione
di continuazione sono determinati dai tre valori specificati per la variabile
contatore : inizializzazione:
le si assegna il valore iniziale continuazione:
si incrementa contatore del valore
passo alla fine di ogni iterazione,
e la condizione di continuazione, all'inizio di ogni iterazione, è vera
sse il valore di contatore
non supera il valore finale
l'esercizio consiste nell'indicare come ottenere un descrizione equivalente
a quella di un ciclo a contatore adoperando solo le strutture fondamentali
del Teorema di Böhm-Jacopini
l'algoritmo di ricerca di un gene in una molecola di DNA proposto ad
esempio opera ad un livello
piuttosto alto di astrazione, se si considerano le operazioni primitive
assunte nell'esempio; raffinarlo ad un livello più basso, assumendo
disponibile l'operazione di confronto di eguaglianza di simboli dell'alfabeto
dato, mediante algoritmi che definiscano funzioni per le tre operazioni
suddette
N.B. per definire tali funzioni si suggerisce di adoperare la notazione
in pseudocodice usata finora, eccetto che in luogo della primitiva
"scriviE
",
che produce il valore dell'espressione E
in uscita, conviene adoperare la primitiva
"restituisciE
",
per fornire il valore di E, quale risultato
del calcolo della funzione che si descrive, all'algoritmo più astratto che
ne fa uso
