Algoritmi
Paolo Bison
Fondamenti di Informatica 1 A.A. 2004/05
Universit`a di Padova
Algoritmo
descrizione di come si deve eseguire un lavoro o risolvere un problema
sequenza di passi/istruzioni
Muh.ammad ibn M¯us¯a al- Khuw¯arizm¯ı
matematico arabo autore di
Al-jabr w’al muq¯abala
procedimento di calcolo
esistono anche in altri contesti:
processo algoritmo passo tipico
montare un istruzioni incolla
Esecuzione
esecutore
uomo/calcolatore
funzionalità dell’esecutore:
capire il significato di ogni passo
eseguire l’operazione corrispondente
descrizione
uomo linguaggio naturale calcolatore programma in un
linguaggio di programmazione
indipendenti dal linguaggio in cui sono espressi
potenza espressiva del linguaggio
Programmazione
problema
⇓
algoritmo
⇓
programma
fasi
progettare un algoritmo
esprimerlo in un linguaggio di programmazione (programma)
far eseguire il programma
Progettazione
Dato un problema come si progetta un algoritmo che lo risolva ?
NON ESISTE un algoritmo per progettare algoritmi
attività intellettuale
metodologie e linguaggi
prevedere tutti i possibili eventi che potrebbero verificarsi durante l’esecuzione
•
distruzione del vettore Arianne
Computabilità
Ci sono problemi per i quali non esistono algoritmi?
halting problem
Dato un problema, come possiamo sapere se esiste
un algoritmo che lo risolve?
Correttezza
Dato un algoritmo, come possiamo essere sicuri che è corretto?
metodi formali
metodi empirici
inaffidabilità dei programmi
Complessità
dato un algoritmo
quali sono le risorse necessarie per eseguirlo ? in quanto tempo ?
se ci sono più algoritmi per un dato problema, qual’è il
“migliore”?
esistono problemi per i quali il miglior algoritmo richiede tante risorse da rendere impossibile l’elaborazione?
crittografia
Algoritmo
un insieme di passi/istruzioni che definiscono una
sequenza di operazioni mediante le quali si risolve un problema (o una classe di problemi)
proprietà
finitezza
numero dei passi finito ed eseguito un numero finito di volte
determinatezza
istruzioni definite senza ambiguità in modo tale da garantire sempre gli stessi risultati a parità di
condizioni
realizzabilit`a
istruzioni devono essere conosciute all’esecutore
che sa come eseguirle
Top Down
approccio metodologico alla progettazione di algoritmi per affinamenti successivi
divide et impera
fasi
dato un problema
lo si scompone in sottoproblemi
ogni sottoproblema è scomposto in ulteriori sottoproblemi
così via finché ogni sotto-
P
P1 P2 P3
P P
Algoritmo del tè - I
algoritmo principale:
fai bollire dell’acqua
metti il tè nella tazza
versa l’acqua
si noti:
azioni(istruzioni) e oggetti (dati)
ambiguità
Algoritmo del tè - II
affinamento primo sottoproblema
fai bollire l’acqua:
riempi il bollitore
accendi il fuoco
attendi che bolla
spegni il fuoco
Bottom Up
approccio opposto al top down
dato un certo insieme di algoritmi/istruzioni elementari si cerca di aggregarli in maniera da costruire
l’algoritmo per la soluzione del problema o di suoi sottoproblemi
combinazione delle due metodologie
Algoritmo del tè - III
Se esecutore capace di strofinare si può accendere il fuoco con il seguente algoritmo:
strofina due legnetti
continua finché il fuoco appare
Rappresentazione
linguaggi per rappresentare algoritmi:
naturale
pseudocodice
flow chart
linguaggio di programmazione
Elementi di un linguaggio
sintassi
l’insieme della regole relative ai procedimenti tramite i quali le unità sintattiche si combinano in espressioni linguistiche
semantica
relazione fra le espressioni linguistiche e il mondo cui
si riferiscono
Do it yourself
