ALGORITMI E COMPLESSITÀ
G1DisCs: Albertani, Driussi, Tomasoni
Pastasciutta all’olio
1.
2.
3.
4.
5.
6.
7.
8.
9.
Mettere 2 litri di acqua in una pentola
Mettere la pentola sopra al gas
Portare l’acqua in ebollizione
Buttare in acqua 20 g di sale
Aggiungere 80 g di pasta
Spegnere il fuoco dopo il tempo indicato sulla
confezione della pasta
Scolare l’acqua in un apposito scolapasta
Servire in un piatto aggiungendo 10 ml di olio
Cospargere il tutto con 10 g di parmigiano
Cos’è un algoritmo?


È una procedura automatica, cioè
eseguibile da un essere non pensante (ad
esempio un computer), per risolvere in un
numero finito di passi un certo problema
Un algoritmo è un insieme ordinato di passi
eseguibili e non ambigui
Algoritmo
Input
ELABORATORE
Output
Pastasciutta all’olio 2
1.
2.
3.
4.
5.
6.
7.
8.
9.
Mettere un po’ d’acqua in una pentola
Mettere la pentola sopra al gas
Portare l’acqua in ebollizione
Buttare in acqua sale q.b.
Aggiungere una porzione di pasta
Spegnere il fuoco quando la pasta è cotta
Scolare l’acqua in un apposito scolapasta
Servire in un piatto aggiungendo un filo d’olio
Cospargere il tutto con una spolverata di
parmigiano
Finitezza



Un algoritmo per essere tale, deve
produrre un output in un numero
finito di passi
Questo significa che finirà in un tempo
finito qualora venga eseguito da un
computer
La finitezza è una condizione
necessaria per un algoritmo
Questo è un algoritmo?
Calcolare il numero di
Nepero come somma
di una serie
Correttezza


Ovvero per ogni input valido,
l'output dell'algoritmo è una
soluzione per il problema
La correttezza non è una
condizione necessaria per
un algoritmo (un algoritmo
non corretto è comunque un
algoritmo)
Efficienza



Si indica col termine efficienza la
velocità di un algoritmo nel risolvere
un problema
L’efficienza dipende da molte
variabili esterne: tipo di calcalatore,
input differenti, ecc.
Come trovare una misura univoca
dell’efficienza dell’algoritmo?
Complessità computazionale


La misura univoca dell’efficienza di
un algoritmo si basa sul numero di
istruzioni da eseguire nel caso
peggiore possibile
Il numero di istruzioni dipende dalle
dimensioni dell’input
Classi di complessità


I problemi vengono classificati in
differenti classi di complessità
La complessità è sempre funzione
della dimensione dell’input (dice
come aumentano le istruzioni al
crescere delle dimensioni dell’input)
Tempo/Memoria


Per diminuire la complessità di un
algoritmo è utile memorizzare le
soluzioni di sottoproblemi in
modo da non doverle ricalcolare più
volte
Si rischiano però problemi
insuperabili di spazio per la
memoria
Esempi

Calcolo dei numeri di Fibonacci


con uso della memoria
senza memoria
Programma ≠ Algoritmo


Un algoritmo non è un programma!
Un programma è
l’implementazione di uno o più
algoritmi
Strutture dati


Organizzazione dell’input:
vengono usate in ogni programma
per raggruppare in modo logico i
dati e accedervi in modo veloce.
Sono utilizzate dall'algoritmo e ne
influenzano l'efficienza
Calcolabilità



Per ogni problema esiste un
algoritmo che lo risolve?
Può essere utile sapere se esiste o
no un algoritmo per un determinato
problema
È stato dimostrato che per certi
problemi non esiste un algoritmo
risolutivo
Ruolo nel pensiero razionale



Matematica…. Latino… perché
non l’informatica?
È universalmente riconosciuto il
valore di alcune discipline per
esercitare e stimolare il
ragionamento: l’informatica si
presta molto bene
Computational thinking!
Relazione con altre Scienze


Al giorno d’oggi l’informatica
assume un ruolo centrale tra le
scienze
Algoritmi di ogni genere sono usati
da fisici, matematici, biologi, ecc.
Importanza in informatica




Gli algoritmi sono come il
prezzemolo
Gli algoritmi sono tra i fondamenti
dell’informatica
Hanno dato vita a molti studi teorici
(teorie della complessità e della
calcolabilità)
Sono presenti in ogni settore, dalla teoria
all’ingegneria
Per saperne di più




The Art of Computer Programming
Donald Knuth
Introduction to Algorithms
Thomas H. Cormen
Algoritmi, divinità e gente comune
F. Luccio, L. Pagli
http://g1discs.wikispaces.com/