Corso di Didactics of Computer Science a.a. 2011/2012

Valeria Mattuzzi

Definizione di algoritmo

Un algoritmo è un insieme finito ed ordinato di passi non ambigui, che specificano le operazioni eseguendo le quali si risolve una classe di problemi

Il termine algoritmo, che significa “procedimento di calcolo”, è una versione moderna del termine latino medievale algorismus. Algorismus deriva dal matematico persiano Al-Khwarizmi, del IX secolo d.C.

In altre parole, un algoritmo è la descrizione precisa di un procedimento valido per la risoluzione di un problema attraverso un numero finito di passi. Un problema risolvibile mediante un algoritmo si dice computabile

Il primo algoritmoIl primo algoritmo di cui si abbia documentazione si trova nel papiro egiziano di Ahmes, risalente circa al 1650 a.C. e conservato al British Museum di Londra

Il papiro contiene un algoritmo per la moltiplicazione. Tale algoritmo viene usato tuttora nei circuiti delle unità aritmetico/logiche dei calcolatori elettronici

Proprietà degli algoritmiLe proprietà principali di un algoritmo sono:

Finitezza. L'algoritmo deve essere composto da un numero finito di passi

Non ambiguità. I passi costituenti l'algoritmo devono essere interpretabili in modo univoco dall'esecutore sia esso umano o artificiale

Terminazione. L'esecuzione deve terminare dopo un tempo finito

Eseguibilità. Gli informatici utilizzano il termine efficace per indicare il concetto di essere eseguibile.

Natura astratta degli algoritmiDistinzione tra algoritmo e la sua rappresentazione

E' analoga a quella tra una storia e un libro. Una storia è astratta o concettuale; mentre, un libro è una “rappresentazione fisica” della storia.

Allo stesso modo, un algoritmo è astratto e distinto dalla sua rappresentazione

Distinzione tra programma e processo

Un programma è la rappresentazione di un algoritmo; mentre, un processo è l'attività di esecuzione di un algoritmo.

Programmi, algoritmi e processi sono entità distinte, ma correlate.

Rappresentazione degli algoritmiPrimitive

Esempio. Rappresentazione di un algoritmo usando delle figure

Lo stesso algoritmo può essere rappresentato in vari modi:

formula, sequenza di istruzioni, disegno, a parole

a diversi livelli di astrazione

Rappresentazione degli algoritmiPrimitive

Molti canali di comunicazione presentano spesso una terminologia che ha più di un significato

nascono così problemi di comunicazione

Ogni rappresentazione si basa su un insieme di primitive ben definite, comprensibili dall'esecutore

Se l'esecutore è un computer, una collezione di primitive per descrivere un algoritmo, insieme alle regole per comporle, costituisce un linguaggio di programmazione

Ogni primitiva ha una propria sintassi (rappresentazione simbolica) e semantica (significato)

PseudocodicePermette una rappresentazione informale degli algoritmi

È un linguaggio meno formale, non direttamente comprensibile da un programma

L'introduzione di questo tipo di formalismo è volta alla comprensibilità e alla leggibilità del codice

Primitive dello pseudocodiceAssegnamento

Sintassi:

Effetto: “associa” a nome il valore ottenuto valutando espressione. Successivamente nome può essere usato per richiamare quel valore

Possiamo pensare a nome come ad una scatola (cella di memoria) in cui mettiamo il valore

nome espressione

Primitive dello pseudocodiceSelezione condizionale

Sintassi:

Significato: Si valuta la condizione

Se il risultato è true si esegue l'azione dopo then

Se il risultato è false si esegue l'azione dopo else

Esempio:

if (l'anno è bisestile) then (totaleGiornaliero ← totale/366)

else (totaleGiornaliero ← totale/365)

If condizione then azione else azione

Primitive dello pseudocodiceIterazione

Sintassi:

Significato: Si valuta la condizione

Se il risultato è true si esegue l'attività, quindi si riesegue tutto il while

Se il risultato è false si termina l'esecuzione

Esempio:

while (ci sono biglietti da vendere) do (vendi un biglietto)

while condizione do attività

Primitive dello pseudocodiceProcedure

Una procedura associa delle azioni da eseguire richiamandone il nome.

Equivale a definire una nuova primitiva.

Esempio:

Risultato: stampa tre volte la stringa “Saluti”

procedure Saluticontatore ← 3while (contatore > 0) do

(stampa il messaggio “Saluti”;contatore ← contatore - 1)

Primitive dello pseudocodiceProcedure

L'importanza e la praticità di una procedura sta nel fatto che può essere “chiamata” in diversi punti del programma

Esempio:

Per renderle più flessibili, le procedure possono avere parametri (o nomi generici). Un parametro viene usato come se fosse un valore nella procedura. Quando si esegue la procedura va fornito un valore per il parametro.

Esempio:

if (l'ospite è simpatico)then (esegui la procedura Saluti)else (...)

procedure Salutibis (contatore)while (contatore > 0) do

(stampa il messaggio “Saluti”;contatore ← contatore - 1)

Algoritmi e risoluzione di problemi1. Comprendere il problema

2. Progettare una soluzione (algoritmo)

3. Realizzare l'algoritmo (scrittura del codice)

4. Valutare l'efficienza e l'accuratezza dell'algoritmo trovato

Osservazioni:Le fasi riportate sopra non sono necessariamente in sequenza

Si potrebbe anche sostenere che non si ha una vera comprensione del problema fintanto che non si arriva a una soluzione del problema stesso.

Risolvere problemi (Problem Solving)

"Una grande scoperta risolve un grande problema, ma nella soluzione di qualsiasi problema c'è un pizzico di scoperta. Il tuo problema può essere modesto, ma se stimola la tua curiosità, tira in ballo la tua inventiva e lo risolvi con i tuoi mezzi, puoi sperimentare la tensione e gioire del trionfo della scoperta"

G.Polya, matematico ungherese (1887 - 1985)

Come si risolvono problemi?

La capacità di risolvere problemi è un'abilità da sviluppare piuttosto che una scienza esatta da imparare

Getting a foot in the doorCi sono numerosi approcci per risolvere problemi. Esiste un filo conduttore che li accomuna ed è detto getting a foot in the door.

Esempio:

Problema: Prima di iniziare una corsa, A,B,C,D fanno le seguenti previsioni:

A prevede che B vincerà; B prevede che D sarà l'ultimo; C prevede che A arriverà terzo; D prevede che la predizione di A sarà corretta.

Solo una di queste previsioni è vera e quella è la previsione fatta dal vincitore. Chi vincerà la gara?

Soluzione: Poichè le previsioni di A e D sono equivalenti, sono entrambe false (il vincitore è uno solo). A questo punto abbiamo a foot in the door. Se la previsione di A è falsa, allora B non ha vinto. Dunque il vincitore è C.

Alcune tecniche per risolvere problemi

Provare a risolvere un problema analogo più semplice

Usare la tecnica di raffinamento, che consiste nel suddividere il problema in sottoproblemi più semplici da risolvere

Seguire una metodologia top-down, andando dal generale allo specifico

Usare la metodologia bottom-up, che consiste nel cominciare a risolvere sottoproblemi del problema dato ed estendere poi le soluzioni

In generale, risolvere un problema richiede una forma di creatività

Strutture iterativeAlgoritmo di ricerca sequenziale

Problema: trovare un algoritmo che verifichi che un particolare valore (target value) è presente in una lista data. Se il valore è nella lista, la ricerca è stata un successo; altrimenti, un fallimento

Soluzione: si scorre la lista dall'inizio, confrontando ogni voce (test entry) con target value. Se si raggiunge la fine dell'elenco senza trovare target value, la ricerca è stata un fallimento

Un algoritmo di questo tipo è detto algoritmo di ricerca sequenziale. A causa della sua semplicità, è spesso utilizzato per liste brevi; infatti, nel caso di lunghi elenchi, ricerche sequenziali non sono così efficienti come altre tecniche

Strutture iterativeAlgoritmo di ricerca sequenziale

procedure ricerca (Lista, TargetValue)if (Lista vuota)

then (Dichiarare la ricerca un fallimento)

else (Selezionare la prima voce nella lista come TestEntry;while ( TargetValue > TestEntry

e rimangono voci da considerare)do (seleziona la voce successiva nella lista come TestEntry)

if (TargetValue = TestEntry)then (Dichiarare la ricerca un successo)else (Dichiarare la ricerca un fallimento)

) end if

Strutture iterativeStrutture di controllo iterative

Un metodo per implementare un uso ripetitivo di un'istruzione o una sequenza di istruzioni è una struttura iterativa detta loop (ciclo), nella quale un insieme di istruzioni, chiamate corpo del ciclo, vengono eseguite in modo ripetitivo sotto la direzione di alcuni control process

Vi sono due importanti strutture ad anello:

while (condizione) do (corpo del ciclo)

repeat (corpo del ciclo) until (condizione)

Osservazione:

Il corpo del repeat viene sempre eseguito almeno una volta

Il repeat termina quando la condizione è vera

I diagrammi di flusso

Struttura del while: diagramma di flusso

Struttura del repeat: diagramma di flusso

I diagrammi di flusso sono un'alternativa allo pseudocodice per rappresentare algoritmi in modo informale ma preciso

Strutture iterativeAlgoritmo di ordinamento per inserimento

Problema: trovare un algoritmo che riordini in ordine alfabetico la seguente lista: Fred, Alex, Diana, Byron, Carol

Soluzione:

La sottolista costituita dai primi due nomi non è ordinata. Si prende la scheda contenente Alex, si fa scorrere il nome Fred verso il basso nello spazio dove c'era Alex e si posiziona poi il nome Alex nello spazio

Ora i primi due nomi formano una sottolista ordinata, ma i primi tre no. Così si può prendere il terzo nome, Diana, si fa scorrere il nome di Fred nello spazio dove c'era Diana e si inserisce Diana nel buco lasciato da Fred. Le prime tre voci dell'elenco sono così ordinate

Si prosegue in maniera analoga e si ottiene un elenco in ordine alfabetico

Strutture iterativeAlgoritmo di ordinamento per inserimento

Ciascuna riga rappresenta lo stesso procedimento che viene ripetuto più volte.

Il programma ordina l'elenco più volte rimuovendo una voce e inserendola nella sua posizione corretta.

Per questo che si parla di ordinamento per inserimento

Strutture ricorsiveAlgoritmo di ricerca binaria

Un algoritmo di ricerca binaria individua un valore desiderato all'interno di un insieme ordinato di dati

Problema: trovare un algoritmo che individui una particolare voce in una lista ordinata

Soluzione:

Si seleziona la “middle entry” nella lista, cioè la prima voce della seconda metà dell'elenco

Se la “middle entry” è il valore cercato, la ricerca è stata un successo. Altrimenti, possiamo limitare la nostra ricerca alla prima o ultima metà della lista.

Si prosegue in maniera analoga per la parte rimanente di lista

Strutture ricorsiveAlgoritmo di ricerca binaria

Esempio: Nella lista data cercare la parola John

Strutture ricorsiveAlgoritmo di ricerca binaria

In pseudocodiceprocedure Search (lista, targetvalue)if (lista vuota)

then (Affermare che la ricerca e stata un fallimento)else

(selezionare middle-entry come Testentry;Eseguire il caso seguente appropriato.

Caso 1: TargetValue = Testentry(Affermare che la ricerca e stato un successo)

Caso 2: TargetValue < Testentry(Applicare la procedura Search per vedere se il TargetValue e nellaporzione della lista precedente a Testentry e riportare il risultato dellaricerca)

Caso 3: TargetValue > Testentry(Applicare la procedura Search per vedere se il TargetValue e nellaporzione della lista successiva a Testentry e riportare il risultato dellaricerca)

) end if

Strutture ricorsiveStrutture di controllo ricorsive

L'algoritmo di ricerca binaria è simile a quello di ricerca sequenziale, poiché entrambi gli algoritmi richiedono l'esecuzione di un processo ripetitivo

Tuttavia, l'attuazione di questa ripetizione è molto diversa. La ricerca sequenziale comporta una forma circolare di ripetizione, mentre la ricerca binaria esegue ogni fase della ripetizione come una sottoattività della fase precedente. Questa tecnica è nota come ricorsione.

I sistemi ricorsivi dipendono da una condizione di terminazione detta base case o degenerative case

Efficienza degli algoritmiAnche se le macchine di oggi sono in grado di eseguire milioni di istruzioni al secondo, l'efficienza rimane una delle principali criticità nella progettazione di algoritmi. Spesso la scelta tra algoritmi efficienti e non efficienti può fare la differenza tra una soluzione effettiva al problema e una impraticabile.

Ci sono diverse misure per valutare la “bontà” di un algoritmo

Normalmente siamo interessati al costo dell'esecuzione dell'algoritmo o in termini del tempo impiegato dall'esecuzione o dello spazio di memoria occupato dalle varie strutture dati necessarie per l'esecuzione

Analisi dell'algoritmo di ordinamento per inserimento

Esempio: Consideriamo una lista di n termini e l'algoritmo di ordinamento per inserimento analizzato sopra

Poichè l'attività di confronto tra due voci domina l'algoritmo, si conta il numero dei confronti eseguiti durante l'ordinamento della lista

Nel miglior caso possibile, si devono eseguire n – 1 confronti

Nel caso peggiore, cioè quando l'elenco originale è in ordine inverso, si devo effettuare

1 + 2 + 3 + … + (n – 1) = ½ (n² – n) confronti

Il numero di confronti effettuati durante l'esecuzione dell'algoritmo fornisce un identificatore della quantità di tempo necessaria per eseguire l'algoritmo

Analisi dell'algoritmo di ordinamento per inserimento

Nel caso peggiore, il tempo impiegato per eseguire l'algoritmo aumenta in maniera esponenziale se cresce la lunghezza della lista

L'algoritmo diventa meno efficiente più la dimensione della lista aumenta

Analisi dell'algoritmo di ricerca binaria

L'analisi dell'algoritmo di ricerca binaria nel caso peggiore.

Si osserva che l'algoritmo di ricerca binaria diventa più efficiente man mano che la lunghezza della lista aumenta.

La notazione big OPoichè la forma del grafico ottenuto riflette l'efficienza dell'algoritmo, è comune classificare gli algoritmi secondo le forme di questi grafici, basati sull'analisi del caso peggiore. La notazione utilizzata per identificare queste classi è talvolta chiamata “big-theta notation”

Tutti gli algoritmi i cui grafici hanno la forma di una parabola, come l' algoritmo di ordinamento per inserimento, vengono posti nella classe rappresentata da O(n²)

Tutti gli algoritmi i cui grafici hanno la forma di una espressione logaritmica, come la ricerca binaria, rientrano nella classe rappresentata da O(ln(n))

Conoscere la classe in cui un particolare algoritmo cade ci permette di prevedere le sue prestazioni e di confrontarle con altri algoritmi che risolvono lo stesso problema

Correttezza degli algoritmiImportante è la distinzione tra programma che si crede essere corretto e un programma che è corretto

Si è cercato di applicare le tecniche di logica formale per dimostrare la correttezza di un programma, cioè il fatto che l'algoritmo rappresentato da un programma faccia quello che è destinato a fare

Una prima prova di correttezza inizia con l'assunzione che certe condizioni, chiamate precondizioni, siano soddisfatte all'inizio dell'esecuzione del programma

Secondo passo in una prova di correttezza è quello di considerare in che modo le conseguenze di queste precondizioni si propagano nel programma

Correttezza degli algoritmiUna dimostrazione di correttezza procede poi identificando asserzioni che possono essere stabilite in vari punti del programma. Ognuna di esse è conseguenza delle precondizioni del programma e dell'insieme di istruzioni che portano al punto in cui è stabilita l'asserzione.

Se l'asserzione stabilita alla fine del programma corrisponde alle postcondizioni desiderate, possiamo concludere che il programma è corretto.

I progressi nello sviluppo di tecniche per verificare la correttezza di un programma continuano ad essere una sfida. Uno dei progressi più significativi si ha nel linguaggio di programmazione SPARK. Un programma in SPARK non presenta solo l'algoritmo da applicare, ma anche le informazioni necessarie per l'applicazione della dimostrazione formale di correttezza.

BibliografiaBrookshear, J. Glenn, 2012, Computer Science: An Overview, 11/E, Addison-Wesley