Gli algoritmi
Corso di Programmazione A.A. 2008/09
G. Cibinetto
Contenuti della lezione
• Introduzione agli algoritmi
• Rappresentazione degli algoritmi
• Concetti e idee fondamentali
2
Introduzione
Le origini
• Un po’ di storia di come e’ nato il computer e in
generale l’informatica.
• Il computer nasce nel 1948 da due gruppi di persone:
elettronici e matematici.
• Elettronici
• Matematici, logici e filosofi
• Algoritmi
4
Le origini
• Un po’ di storia di come e’ nato il computer e in
generale l’informatica.
• Il computer nasce nel 1948 da due gruppi di persone:
elettronici e matematici.
• Elettronici
• Matematici, logici e filosofi
• Algoritmi
5
David Hilbert
•
Nel 1900 il matematico tedesco D. Hilbert propose la cosiddetta
assiomatizzazione totale della matematica per mezzo di un numero finito
di sistemi formali. Il sogno auspicato da Hilbert era di derivare tutte le
verità matematiche da pochi semplici assiomi e poche semplici regole di
deduzione.
•
La questione era stata posta da Hilbert nei seguenti termini: esiste
sempre, almeno in linea di principio, un metodo meccanico (cioè una
maniera rigorosa) attraverso cui, dato un qualsiasi enunciato matematico,
si possa stabilire se esso sia vero o falso?
•
Una parziale formalizzazione del concetto di algoritmo
inizio’ con il tentativo di risolvere l’entscheidungsproblem
(il problema della decisione) posto da David Hilbert nel
1928: dimostrare cioè, come si era fatto per gli assiomi
della geometria euclidea, che gli assiomi dell'aritmetica dei
numeri reali erano anch'essi coerenti.
6
Gödel
"teorema di incompletezza di Gödel":
“All'interno di ogni sistema formale contenente la teoria dei
numeri esistono proposizioni che il sistema non riesce a
decidere, non riesce, cioe’, a dare una dimostrazione ne’ di
esse ne’ della loro negazione”.
•
•
Questa clamorosa scoperta si manifesto’ subito come un dato fortemente
limitativo circa le possibilità di una completa formalizzazione delle teorie
matematiche. Dal risultato di Gödel vennero tratte, e a ragione, conseguenze filosofiche
di tipo epistemologico sui limiti delle capacita’ cognitive umane, oltre che
sul problema della meccanizzazione del pensiero e dei procedimenti di
calcolo. Crollava cosi’ il sogno di Hilbert che nel 1928 aveva lanciato una
sfida alla comunita’ dei matematici:
“escogitare una macchina logica che potesse dimostrare tutte le verita’
matematiche e, nello stesso tempo, dimostrare che il ragionamento
matematico e’ affidabile” 7
Dopo il teorema di Gödel
• Il teorema di Gödel non ha in ogni caso distrutto lidea
fondamentale del formalismo Hilbertiano, ma ha dimostrato che
ogni sistema potrebbe essere piu’ vasto di quanto Hilbert aveva
previsto. • Inoltre ne derivava che una macchina non poteva essere
programmata per trovare una risposta a tutte le questioni
matematiche.
• Dopo il crollo dell’idea di Hilbert dovuto al lavoro di Gödel
successive formalizzazioni del concetto di algoritmo si
concentrarono sulla calcolabilita’ effettiva (Kleene 1943:274) o sul
metodo effettivo (Rosser 1939:225); queste formalizzazioni
includono le funzioni ricorsive di Gödel-Herbrand-Kleene, il calcolo
lambda di Alonzo Church, la prima formulazione di Emil Post e le
macchine di Turing di Alan Turing.
8
Gödel pero’ non riteneva affatto che il suo teorema
escludesse uno sviluppo dell'Intelligenza Artificiale.
Affermava infatti: “Resta la possibilita` che esista (e
possa persino essere scoperta empiricamente) una
macchina dimostrativa che di fatto e’ equivalente
all'intuizione matematica (alla mente umana)”
In altre parole, secondo Gödel, se mai riusciremo a
costruire un computer intelligente, non lo potremo
capire. Sarebbe troppo complesso per noi
9
Alan Turing
•
•
Nel 1935 un neolaureato di Cambridge, Alan Turing, sfruttando il teorema di incompletezza di Gödel, dimostra l'impossibilita’ di ideare
qualsiasi procedimento meccanico effettivo capace di stabilire in anticipo
se una data proposizione si puo’ dedurre logicamente da un assegnato
sistema di assiomi. Il risultato di Turing fissa limiti invalicabili al calcolo
automatico e al quale non possono sfuggire neppure i piu’ potenti
computer di cui oggi disponiamo. Turing trasporto’ infatti sul computer i risultati di Gödel e dimostro’,
usando argomenti simili a quelli di Gödel, che e’ impossibile costruire un
computer che possa stabilire la verita’ o la falsita’ di tutti i problemi
matematici. Data una congettura non possiamo essere sicuri che esista un
programma in grado di verificarla in un numero finito di passi. Il fatto che il
computer non sia in grado di risolvere un'infinita’ di congetture, vuol forse
dire che la nostra mente e’ superiore al computer? 10
La macchina di Turing
• Le macchine di Turing sono strumenti astratti estremamente
semplici in grado di manipolare simboli. Nonostante la loro
semplicita’ possono essere adatti a simulare la logica di ogni
algoritmo.
• Esse furono descritti da Alan Turing nel 1936. Sebbene
tecnicamente fattibili le macchine di Turing non erano intese come
reale tecnologia di calcolo, ma come un esperimento speculativo
sui limiti della meccanica computazionale. Le macchine di Turing
non furono in realta’ mai costruite, ma lo studio delle loro proprieta’
astratte porta a diversi sviluppi nella scienza dei computer e nella
teoria della complessita’.
11
La macchina di Turing
•
La macchina è formata da una testina di lettura e scrittura con cui è in
grado di leggere e scrivere su un nastro potenzialmente infinito
partizionato, in maniera discreta, in caselle. Ad ogni istante di tempo t1,
la macchina si trova in uno stato interno s1 ben determinato, risultato
dell'elaborazione compiuta sui dati letti.
•
Lo stato interno, o configurazione, di un sistema è la condizione in cui si
trovano le componenti della macchina ad un determinato istante di
tempo t.
•
Le componenti da considerare sono:
– il numero della cella osservata
– il suo contenuto
– l'istruzione da eseguire
12
La macchina di Turing
•
Tra tutti i possibili stati, si distinguono:
– una configurazione iniziale, per t=t0 (prima dell'esecuzione del programma)
– una configurazione finale, per t=tn (al termine dell'esecuzione del programma)
– delle configurazioni intermedie, per t=ti (prima dell'esecuzione dell'istruzione oi)
•
Implementare un algoritmo in questo contesto significa effettuare una delle quattro
operazioni elementari
– spostarsi di una casella a destra
– spostarsi di una casella a sinistra
– scrivere un simbolo preso da un insieme di simboli a sua disposizione su una
casella
– cancellare un simbolo già scritto sulla casella che sta osservando
– oppure fermarsi.
•
Turing poté dimostrare che un tale strumento, dalle caratteristiche così rigidamente
definite, è in grado di svolgere un qualsiasi calcolo e capì che la calcolabilità era
parente stretta della dimostrabilità.
13
La macchina di Turing
14
Universal Turning Machine
• Una macchian di Turing universale (UTM) e` una macchina che
riesce a simulare ogni altra macchina di Turing.
• "It is possible to invent a single machine which can be used to
compute any computable sequence. If this machine U is supplied
with the tape on the beginning of which is written the string of
quintuples separated by semicolons of some computing machine
M, then U will compute the same sequence as M."
• Questa scoperta oggi sembra ovvia, ma nel 1936 fu considerata
sbalorditiva.
15
Boolos & Jeffrey (1974, 1999)
• “No human being can write fast enough, or long enough, or small
enough to list all members of an enumerably infinite set by writing
out their names, one after another, in some notation. But humans
can do something equally useful, in the case of certain enumerably
infinite sets: They can give explicit instructions for determining the
nth member of the set, for arbitrary finite n. Such instructions are to
be given quite explicitly, in a form in which they could be followed
by a computing machine, or by a human who is capable of carrying
out only very elementary operations on symbols” (Boolos & Jeffrey
1974, 1999, p. 19)
• Le parole “enumerably infinite” (infiniti numerabili) significano infiniti
che possono essere contati usando numeri interi estesi all’infinito.
16
Gli algoritmi
Definizione di algoritmo
• Non esiste un unica definizione generalmente
accettata di algoritmo.
• Ne vedremo alcune
18
Etimologia
• Algoritmo deriva dal nome del matematico
e astronomo persiano Muhammad ibn
Msa al-Khwrizm, del IX secolo.
• Il termine fu tradotto in latino nel XII secolo e dal XIII
secolo entro’ a far parte del linguaggio matematico
• Uno dei primi utilizzi del termine fu nel 1240, in un
manuale intitolato “Carmen de Algorismo” scritto da
Alexandre de Villedieu.
19
Wikipedia
• In informatica, con il termine algoritmo si intende un metodo per la
soluzione di un problema adatto a essere implementato sotto
forma di programma.
• Intuitivamente, un algoritmo si può definire come un procedimento
che consente di ottenere un risultato atteso eseguendo, in un
determinato ordine, un insieme di passi semplici corrispondenti ad
azioni scelte solitamente da un insieme finito.
(…)
• Nel senso più ampio della parola, "algoritmo" è anche una ricetta di
cucina, o la sezione del libretto delle istruzioni di una lavatrice che
spiega come programmare un lavaggio. Di norma, comunque, la
parola viene usata in contesti matematici (fin dalle origini) e
soprattutto informatici (più recentemente).
20
Wikipedia (english)
“In mathematics, computing, linguistics and related
disciplines, an algorithm is a sequence of
instructions, often used for calculation and data
processing. It is formally a type of effective method in
which a list of well-defined instructions for completing
a task will, when given an initial state, proceed
through a well-defined series of successive states,
eventually terminating in an end-state. The transition
from one state to the next is not necessarily
deterministic;
some
algorithms,
known
as
probabilistic algorithms, incorporate randomness.”
21
Dizionari: Merriam-Webster
a procedure for solving a mathematical problem (as of
finding the greatest common divisor) in a finite number
of steps that frequently involves repetition of an
operation; broadly : a step-by-step procedure for solving
a problem or accomplishing some end especially by a
computer
22
Garzanti
• 1 (mat.) procedimento sistematico di calcolo: algoritmo
algebrico, euclideo.
• 2 nel Medioevo, il calcolo basato sull'uso delle cifre
arabiche.
• 3 in logica matematica, procedimento meccanico che
permette la risoluzione di problemi mediante un numero
finito di passi | (inform.) serie di operazioni logiche e
algebriche, espresse in linguaggio comprensibile
all'elaboratore, la cui sequenza costituisce un
programma.
23
Esempio
• La sveglia
24
Esempio
25
Altri esempi piu’ o meno
interessanti
• Trovare il M.C.D.
• Ordinare una sequenza di numeri
• Fare una telefonata
• Trovare i primi dieci numeri primi
• Scegliere la strada piu’ corta per arrivare a casa
26
Rappresentazioni
Importante dare e capire diverse rappresentazioni della stessa idea.
Imparare a esprimere la stessa idea in maniera diversa.
1
2
3
27
Descrizione degli algoritmi
•
Gli algoritmi possono essere rappresentati in di molti modi: linguaggio
naturale, pseudocodice, diagrammi, linguaggi di programmazione , …
•
Riprendendo il discorso della macchina di Turing possiamo descrivere gli
algoritmi in tre modi:
1 descrizione di alto livello:
– Descrivere un algoritmo ignorando i dettagli dell’implementazione. Non
dobbiamo preoccuparci di come funzionano le macchine
2 Implementazione:
– Definire come farebbe la macchina ad eseguire l’algoritmo: a leggere i dati e a
calcolare il risultato. A questo livello non occorre specificare ogni transizione
3 Descrizione formale:
– E’ la descrizione piu’ dettagliata e intellegibile alla macchina
28
Vediamo alcuni esempi
29
Codice
30
Codice
Pro:
Contro:
• Funziona su un computer
• Non sono un computer
• Preciso e sintetico
• Occorre un alto livello di
intuizione
• Riuscire a scrivere il codice
e’ l’unico modo per avere un
lavoro o passare l’esame.
(falso)
• Si e’ esposti ai “bachi”
• Si dipende dal linguaggio
scelto
31
Provare su un esempio
• Se devo ordinare una sequenza di numeri, posso
provare ad iniziare con:
7, 14, 2, 5, 10, 18, 9
E vedere cosa devo fare…
32
Prova su un esempio
Pro:
• Concreto
Contro:
• Si basa sull’abilita’ di trovare la
combinazione giusta.
• Dinamico
• Visivo
• Non spiega come funziona
l’algoritmo
• E’ dimostrato solo per una
possibile combinazione
33
Turing machine
34
Turing machine
Pro:
• Buona per teoremi sugli
algoritmi
Contro:
• Non va bene per progettare
algoritmi
35
Alto livello di astrazione
0
i-1
i
i
36
Astrazione
E’ difficile pensare all’amore come a interazioni
fra neuroni
37
Alto livello di astrazione
Pro:
• Intuitivo per gli umani
Contro:
• Non si affrontano problemi
tecnici
• Utile per
– pensare
– disegnare
– descrivere algoritmi
• Troppo astratto
• In genere non piace agli
studenti
• La correttezza di un
algoritmo dovrebbe essere
ovvia
38
Linguaggi, pseudolinguaggi e pseudo
codice
• Per esprimere un algoritmo e` necessario un linguaggio.
• Un linguaggio e` composto da un insieme di parole raggruppate in
un dizionario, da un insieme di operatori per unire tra loro le parole,
da un insieme di regole sintattiche, cioe regole che ci permettono
di unire insieme le parole per ottenere delle frasi corrette e dalle
regole semantiche, cioe regole che ci permettono di dare un senso
alle frasi del linguaggio. • In informatica un algoritmo espresso in un linguaggio
comprensibile ad un calcolatore viene chiamato codice, la stessa
versione dellalgoritmo se espressa in un linguaggio non
comprensibile al calcolatore ma sufficientemente schematico e
detta essere espressa in pseudocodice mentre il linguaggio usato
viene chiamato pseudolinguaggio. 39
Linguaggio comune
•
La procedura per il calcolo del massimo comune
divisore (MCD) tra due numeri puo` essere definita nel
linguaggio comune come segue: 1. Prendi due numeri a e b. 2. Esegui la divisione intera del piu grande per il piu piccolo. 3. Sostituisci il numero piu grande con il resto della divisione. 4. Se il resto non ` e zero ricomincia del passo 2. 5. Hai trovato il MCD 40
Pseudo-linguaggio
• Lo stesso algoritmo puo essere espresso in
psedudolinguaggio come segue: • 1. SIANO a e b, c e mcd quattro variabili. • 2. SE a < b ALLORA – (a) c : = a – (b) a : = b – (c) b : = c •
•
•
•
3. c : = a/b 4. a : = a c b 5. SE a > 0 VAI a a) 6. mcd : = b. 41
Diagrammi di flusso
42
Esercizi
• Algoritmo per trovare il m.c.m.
• Algoritmo per ordinare una sequenza di numeri
• Contare le parole “ciao” in un testo
• Orologio hh:mm:ss
• Distribuzione dei voti del libretto
• Mettere in ordine alfabetico una serie di nomi
43
44
Studio
• E’ stato chiesto a molti programmatori esperti di
scrivere un programma per eseguire una ricerca
binaria:
l’80% ha sbagliato
45
Cosa mancava?
• Astrazione?
Ne abbiamo gia` parlato e ci torneremo in futuro
• Immaginazione?
• Semplicita`?
• Strategia?
Si racconta anche che quando
dissero ad Hilbert che un suo
studente aveva abbandonato
l'università per diventare poeta
egli abbia risposto "Non sono
sorpreso: non aveva
abbastanza immaginazione per
diventare un matematico"
• Un po’ di matematica?
46
Il valore della semplicita`
• Pensare agli algoritmi in maniera semplice
• Non pensate che non ci possano essere idee profonde
nelle cose semplici semplici
=
47
Strategia
• Ci ritorneremo quando studieremo piu’ in dettaglio
alcuni algoritmi e la loro implementazione.
• Per il momento ci limitiamo a vedere come una buona
strategia puo’ influenzare il risultato.
48
Depending on the wind, the striker’s position may vary…
49
Radical, efficient, unstoppable… (ball’s speed may reach 297 km/h)
50
Iron defense, small ideas in midfield, passes to striker..and…Penalty
51
… no comments!
52
They manage to lose the game by themselves, no help needed. 53
In their plan, they try all possible hypotesis.
54
Note: the red dot is not the ball, it’s the referee.
55
56
Mondiali vinti
• Cosa impariamo da questo?
57
Un po’ di matematica
• Algebra …
• Geometria …
58
Tipi di variabili
• Numeri
–
–
–
–
Interi, naturali
Razionali
Reali
Complessi
• Altro
– Caratteri
– Stringhe
– …
59
Funzioni
• Rappresentazione e studio delle funzioni
• Funzioni fondamentali
• Andamenti asintotici
60
Cosa e’ importante di un algoritmo
• Cosa e’ piu’ importante delle prestazioni di un algoritmo?
• Modularita`
• User-friendliness
• Correttezza
• Tempo di programmazione
• Mantenibilita`
• Semplicita`
• Funzionalita’
• Estensibilita`
• Robustezza
• Affidabilita`
• Ma le prestazioni sono la moneta del calcolo
61
Performance asintotiche
• Quando abbiamo a che fare con piccoli numeri spesso
un algoritmo vale l’altro.
• Quando il sistema o il numero di iterazioni inizia a
diventare grande alcuni algoritmi iniziano ad avere
problemi
• E’ importante conoscere le performance asintotiche di
un algoritmo, sapere cioe’ come crescera’ il tempo di
calcolo al crescere delle dimensioni del sistema.
62
Classificazione degli algoritmi
• Classificazione in base all’implementazione
–
–
–
–
Ricorsivi o iterativi
Seriali o paralleli
Deterministici o non deteriministici
Esatti o approssimati
• Classificazione in base al design
– Dividi e conquista
– Programmazione dinamica
– …
• Classificazione in base alla complessita`
• Classificazione in base al campo di applicazione
63
Esercizi
• Trovare algoritmi concettualmente diversi che risolvano
il problema del calcolo delle aree.
64
Riassunto della lezione
65