Nozione di Algoritmo - Università degli Studi di Milano

Lezione 1 - Nozione di Algoritmo
Corso — Programmazione
Fondamenti di programmazione— Algoritmi
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Università degli Studi di Milano — Dipartimento di informatica
Algoritmo e MdT
• MdT introdotta come modello di calcolo per formalizzare il
concetto di calcolo allo scopo di stabilire l'esistenza di
metodi algoritmici per il riconoscimento dei teoremi
nell'ambito dell'Aritmetica.
• MdT è legata al concetto di automa, come esecutore di
una serie di passi (sempre uguali per ogni automa)
dipendenti dall'input
• L'automa è legato al linguaggio che riconosce o che utilizza
• Il linguaggio è fondamentale per comprendere come
descrivere i passi da far eseguire ad una macchina in
modo che siano comprensibili alla macchina stessa
Architettura di Von Neumann:
conseguenze
• Una macchina è in grado di risolvere più problemi a patto
di elencarne i passi da seguire per farlo.
• Lo sviluppo di strumenti formali per l'elaborazione
dell'informazione
• Nascita di una disciplina che, dato un problema
applicativo, mira ad individuare un procedimento di
calcolo che ne consente la soluzione (algoritmo)
• Si separa l'individuazione degli insiemi di passi (algoritmi)
che risolvono problemi dati (attivita' umana)
dall'esecuzione di tali passi (algoritmi) (attivita' svolta da
un calcolatore)
Algoritmo: definizione storica
Termine dovuto al famoso scrittore al-Khwarizmi: nato nel
780 circa a Baghdad
Originariamente chiamato algorism, un algoritmo è sequenza
finita di istruzioni che specificano come certe
operazioni elementari debbano susseguirsi nel tempo per
risolvere una data classe di problemi.
• Operazioni elementari: operazioni note all'esecutore
• Istruzioni: richieste di azioni rivolte all'esecutore e che
da questo devono essere capite ed eseguite
• Classe di problemi: una formulazione del problema
indipendente dagli specifici dati su cui opera
Algoritmi: Proprietà
• Oltre alle proprietà di eseguibilità e non ambiguità di un
algoritmo, altre proprietà fondamentali degli algoritmi
sono
Definito: ogni passo dell'algoritmo è precisamente definito
(rigoroso e non ambiguo) [dati e risultati definiti]
Correttezza: l'esecuzione dell'algoritmo porta realmente
alla soluzione del problema dato
Efficienza: quanto ``costa'' l'esecuzione di un algoritmo in
termini di risorse consumate
Finitezza: normalmente si richiede che l'algoritmo termini
in un tempo finito, e cioè che la sequenza di istruzioni che
caratterizzano l'algoritmo sia una sequenza finita
Algoritmi: caratteristiche
• Istruzioni insieme ordinato e finito di operazioni da
eseguire
• Ogni istruzione è univoca cioè non lascia dubbi o
ambiguità sul da farsi
• Esiste un esecutore in grado di eseguire le istruzioni
• Le procedure risolvono una classe di problemi
• Non esiste un modo unico per risolvere un problema
• Un algoritmo e' corretto se per ogni istanza di input si
arresta con l'output corretto
Algoritmo esempio
• Ricetta da cucina
• E' una sequenza di passi finiti ed in ordine per giungere
alla preparazione del piatto
• I passi non sono ambigui (per quanto possa non essere
ambiguo il linguaggio naturale)
• Tutte le istruzioni sono eseguibili dall'esecutore della
ricetta
• Risolve una classe di problemi: la ricetta generalizza certe
istruzioni: le quantità, ad esempio, subordinate al numero
di persone rappresentando solo i rapporti fra quantità
(una parte, 1/2 parte etc)
Algoritmo - programma - esecutore
• Un programma è l'espressione di un algoritmo in un
linguaggio che l'esecutore è in grado di comprendere
direttamente.
Un programma è un'espressione concreta dell'algoritmo
che ne è l'astrazione
• A seconda dell'esecutore, lo stesso algoritmo può essere
espresso in linguaggi differenti
• La scrittura del programma è la fase successiva
all'individuazione dell'algoritmo per risolvere un
determinato problema
Calcolatore - programma programmazione
• Calcolatore
Un automa il cui comportamento segue delle regole ben
precise: è in grado di ``comprendere'' un repertorio
ristretto di istruzioni elementari e di eseguirle con una
enorme rapidità ed elevata precisione
• Programma
Sequenza di istruzioni elementari che un calcolatore è in
grado di comprendere ed eseguire
• Programmazione
Attività che consiste nell'organizzare istruzioni elementari,
direttamente comprensibili dall'esecutore, in strutture
complesse (programmi) al fine di svolgere determinati
compiti
Problema - algoritmo - programma
Problema - algoritmo - programma
Problema - algoritmo - programma
Lezione 2 - Problema - Algoritmo –
Esecutore
Corso — Programmazione
Fondamenti di programmazione— Algoritmi
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Università degli Studi di Milano — Dipartimento di informatica
Problema - algoritmo - programma
Formulazione di un problema
• Definizione dei dati e dei risultati che si vogliono ottenere
(a partire dai dati)
• Processo di formulazione di un problema:
1. Individuazione dei dati in ingresso
2. Individuazione dei risultati desiderati
3. Individuazione dell'algoritmo di risoluzione
Analisi dei requisiti
Problema ed istanza(1)
• Specificando quali sono i dati di ingresso si definisce una
istanza di Problema
Problema P: dato un naturale n calcolare la somma dei
primi n naturali
Istanza di P: risolvere P per n = 12 (ovvero calcolare la
somma dei primi 12 naturali)
• Un problema può essere visto come l'insieme di tutte le
sue possibili istanze
Problema ed istanza(2)
[*] Prof. Andrea G. B. Tettamanzi
Problema ed Istanza (3)
[*] Prof. Andrea G. B. Tettamanzi
Problema ed Istanza (4)
[*] Prof. Andrea G. B. Tettamanzi
Problema - algoritmo - esecutore
Figura : Relazione problema, algoritmo ed esecutore
Problema dei secchi
• Sono presenti due secchi con capacità volumetrica
rispettivamente di 3 e 4 litri.
• Determinare le operazioni necessarie per far si che il
primo secchio (da 3 litri) sia riempito con 2 litri.
• Possiamo agire sui due secchi attraverso le seguenti
operazioni:
Riempire completamente un secchio
Svuotarlo completamente
Travasare una certa quantita' di liquido da un secchio
all'altro
Problema dei secchi:soluzione
• Si riempie il secchio da 3 litri
• Si travasa il contenuto nel secchio da 4 litri
• Si riempie nuovamente il secchio da 3
• Si rabbocca il secchio da 4 ottenendo due litri nel secchio
da 3 come richiesto
Problema del Massimo Comune Divisore
• Il problema di calcolare il Massimo Comune Divisore MCD
fra due numeri x e y (x > y)
• Dati: due numeri
• Risultati: il Massimo Comune Divisore
Algoritmo per l'MCD (Euclide)
1. Calcola il resto della divisione di x per y
2. Se il resto è diverso da zero, allora ricomincia dal punto 1
utilizzando come x il valore attuale di y, e come y il valore
del resto
altrimenti
prosegui con il passo successivo
3. Il massimo comune divisore è uguale al valore attuale di y
• L'intelligenza necessaria per trovare la soluzione del
problema è tutta codificata nell'algoritmo
• Chiunque sappia comprendere ed eseguire le operazioni
che costituiscono l'algoritmo di Euclide, può calcolare
l'MCD
Algoritmo: Controesempio
• Non tutto ciò che sembra un una procedura passo passo è
un algoritmo
• Esempio: Dire se un numero è primo
1. N ← {0,1}
2. per ogni coppia di interi i > 1 e j > 1, N ← N ∪ {i · j}
3. n è primo se e solo se n ∈
/N
Ricordiamo che un numero naturale si dice primo se è divisibile solo per 1 e per sè
stesso e che per definizione 0 e 1 non sono primi
Algoritmi: input e output
• Con una terminologia più da programmatori, considerando
un algoritmo di risoluzione del problema, dati e risultati
della formulazione di un problema diventano
Input: un algoritmo può avere zero o più input, i quali sono
quantità che vengono date in pasto all'algoritmo prima che
inizi, oppure dinamicamente mentre è in esecuzione.
Questi input sono presi da uno specifico insieme di oggetti
Output: un algoritmo può avere uno o più output, si tratta
di quantità che hanno una relazione specifica con gli input
Problemi: esempi(1)
• Risoluzione equazione di secondo grado
Input: tre numeri (i coefficienti)
Output: le due radici se reali, stampa di un messaggio
opportuno altrimenti
• Trovare il massimo fra tre numeri
Input: tre numeri
Output: il valore massimo
Problemi: esempi(2)
• Ricerca del numero di un utente in un elenco
telefonico
Input: un insieme ordinato di coppie (nome, num. tel.) e
un nome x
Output: il numero telefonico corrispondente all'utente di
nome x, se presente nell'insieme; nulla altrimenti
• Ricerca del cammino più breve tra due punti su una
rete stradale
Input: una rete stradale (rappresentata come un insieme
di piazze, strade che uniscono due piazze, tempi di
percorrenza di ciascuna strada) e due piazze x e y
Output: la sequenza di strade che portano da x a y con
tempo di percorrenza minimo
Problemi: esempi(3)
• Il problema Knapsack (zaino): ``sia dato uno zaino che
possa sopportare un determinato peso. Siano dati inoltre
N oggetti, ognuno dei quali caratterizzato da un peso p e
un valore v. Scegliere quali di questi oggetti mettere nello
zaino per ottenere il maggiore valore senza eccedere il
peso sostenibile dallo zaino stesso.''
Input:
Valore oggetti: V = v1 , · · · ,vn
Pesi oggetti: P = p1 , · · · ,pn
Capacità massima zaino: c(peso)
• Output: Gli oggetti scelti (≤ n con peso complessivo ≤ c)
Problemi: esempi(4)
• Il problema del commesso viaggiatore: ``Un commesso
viaggiatore deve percorrere il miglior tragitto attraverso le
n citta' nelle quali deve effettuare le consegne''
• ``Esiste un percorso che le collega tutte (passando un
sola volta per ciascuna citta') con una lunghezza minore di
b ?''
Input: la mappa con l'indicazione delle n citta' da
raggiungere e una lunghezza b
Output: SI/NO
Tipologie di problemi(1)
• Problemi di decisione: Output: SI/NO (es. : esiste un
percorso con una lunghezza?)
• Problemi di ricerca: Output: una soluzione (es. : trovare
un percorso di lunghezza minore di k)
• Problemi di enumerazione: Output: un conteggio delle
soluzioni (es. : Quanti sono i percorsi di lunghezza minore
di k)
• Problemi di ottimizzazione: Output: una soluzione ottima
rispetto ad un obiettivo (es. : trovare un percorso di
lunghezza minima)
Tipologie di problemi(2)
• La formulazione dei due problemi ``zaino'' e
``commesso'' differisce per il fatto che:
• Il problema zaino e' formulato come un problema di
ottimizzazione: ``Scegliere tra n valigie quelle ... in
modo da trasportare il maggior peso.''
• Il problema commesso, come un problema di decisione:
``Esiste un percorso che ...''
Problemi: Nota
• Non tutti i problemi sono di natura computazionale cioe'
non per tutti i problemi e' possibile definire una procedura
computazionale (un algoritmo) che consenta, a partire dai
dati di ingresso, di ottenere i risultati
Il problema dell'arresto*
• Non esistono modalita' di descrizione di soluzioni
(algoritmi) alternative che consentano di trasformare un
problema non computazionale in un problema
computazionale
• La scienza degli algoritmi deve limitarsi a considerare
problemi computazionali
* indecidibilità (Turing 1936)
Problema algoritmo
• Relazione tra problema ed istanza e tra algoritmo ed
esecutore
• Analisi del problema
• Individuazione della tipologia di problema
• Valutazione di un algoritmo per la soluzione della tipologia
del problema
• Problemi non computazionali
Lezione 3 - Problema - soluzione
Corso — Programmazione
Fondamenti di programmazione— Algoritmi
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Università degli Studi di Milano — Dipartimento di informatica
Problema - Soluzione
Problema - Soluzione
• Matematica ed informatica si pongono lo stesso obiettivo:
rivolvere dei problemi
• L'informatica è anche definita come l'arte della risoluzione
dei problemi
• Abbiamo visto problemi espressi in vario modo e
classificati come tipologie
• Gli esempi visti si chiamano anche
situazioni problematiche
• Dalla situazione problematica si passa al problema
attraverso la formalizzazione
In matematica significa individuare dati incognite e
condizioni
In informatica non è molto diverso, abbiamo visto come
individuare input e output
Problema del barcarolo
• Rivisitiamo il problema del barcarolo
Scopo: trasportare tutti i personaggi sull'altra sponda
Punto di partenza: tutti i personaggi sono su una sponda
BPCL - (rappresentazione)
Punto di arrivo: tutti i personaggi sull'altra sponda BPCL
Vincoli: Barcarolo presente in alcune combinazioni quindi
esistono delle situazioni non ammesse
PL-- BC BC - PL
PC - BL BL- PC
Obiettivo: trovare le azioni da compiere per arrivare al
punto di partenza rispettando i vincoli
Operazioni: trasformazioni di stato
Soluzione: applico tutte le trasformazioni e elimino quelle
che portano ad uno stato non ammesso e ottengo il
diagramma già visto
Metodo dello spazio degli stati
• Si individua lo spazio degli stati
• Si individuano le transizioni
• Dallo stato iniziale applicate tutte le transizioni si individua
lo stato prossimo
• Si escludono gli stati invalidi o quelli già ottenuti
• Si continua fino ad raggiungere lo stato finale
Problema dei secchi
• Problema già affrontato
• Consideriamo un secchio da 9 e uno da 4
• Raccogliere 6 litri di acqua in secchio
• Quale è lo spazio degli stati: coppie ordinate (a,b) relative
al contenuto d'acqua dei secchi
• Stato iniziale: (0,0), stato finale (6,x)
• Operazioni: riempire i contenitori R(x) svuota il
contenitore S(x), travasa fino al colmo C(x,y) travasa
completamente T(x,y)
• Provate a generare l'albero delle possibilità a partire da
queste operazioni
Problema dei secchi: soluzione
• Soluzione
9,0
5,4 C(x,y)
5,0 S(y)
1,4 C(x,y)
1,0 S(y)
0,1 T(x,y)
9,1 R(x)
6,4 C(x,y)
Problema dei cannibali e dei missionari
• 3 missionari e 3 cannibali fanno un viaggio insieme e
devono attraversare un fiume sfruttando una zattera che
può ospitare al massimo 2 persone alla volta. Prima di
affrontare la traghettata, i missionari prospettano un
pericolo: se su una qualsiasi delle due rive del fiume i
cannibali finiscono per essere più numerosi dei missionari,
questi ultimi potrebbero essere assaliti e mangiati dai
primi.
Come far traghettare tutti e sei gli uomini con i missionari
sani e salvi?
Uno dei due missionario o cannibale governa il traghetto,
non esiste un trasportatore
Problema dei cannibali e dei missionari
• Formalizzo il problema usando dei simboli per gli elementi
in gioco
• M missionario, C cannibale, B barca, - fiume
• Stato iniziale: BMMMCCC- stato finale: - BMMMCC
• Operatori di trasformazione: Tm transita missionario
Tc transita cannibale, Tmm transitano due missionari, tcc
transitano due cannibali ...
• Stati non accettati: non possono esserci sui lati più c di
m
Problema dei cannibali e dei missionari:
Soluzione
• MMMCCCB- Tcc MMMC - CCB Tc
• MMMCCB - C Tcc MMM - CCCB Tc
• MMMCB - CC Tmm MC - CCMMB Tmc
• MMCCB - MC Tmm CC - CMMM Tc
• .....
Algoritmo e flusso
• I passaggi tra le sequenze di stati che vanno dallo stato
iniziale al finale rappresentano il
flusso dell'algoritmo risolutore per l'istanza del problema
da affrontare
• Si tratta di una sequenza di operatori che modificano lo
stato
• Se torno in uno stato già incontrato sto percorrendo una
strada già attraversata (non approssimo la soluzione
meglio che al passo precedente)
Gli stati già incontrati vengono scartati e con loro la strada
che vi ha condotti in quello stato
• Algoritmo descritto come la sequenza di operazioni da
compiere
• L'operazione di generalizzazione dall'istanza all'algoritmo
porta generalmente alla creazione di un
flusso non strettamente sequenziale
Algoritmo e controllo di flusso
• Alcune operazioni sono soggette a particolari condizioni
per essere eseguite (per gestire più istanze)
• Altre essendo ripetitive (stesso operatore ma stati via via
differenti) vanno eseguite più volte
• Nella descrizione dell'algoritmo esistono quindi dei modi
per controllare il flusso delle operazioni da eseguire
• In genere si utilizzano parole del linguaggio che
modificano il flusso generando un salto
• Nell'algoritmo di Euclide si vedono chiaramente la
valutazione della condizione di terminazione (se) e il salto
(salta a) che genera la ripetizione
• Se considero una istanza specifica del problema dell'MCD
tra due numeri posso serializzare la sequenza di istruzioni
avendo un flusso sequenziale
Controllo del flusso
• La sequenza di istruzioni da compiere
E' enumerata in sequenza Ha un flusso governato da delle
istruzioni di controllo di flusso
• Istruzioni che agiscono cambiando lo stato
• Istruzioni che verificano lo stato (se allora altrimenti)
• Istruzioni che rompono la sequenzialità stretta e vanno a
far riprendere l'esecuzione da un determinato punto
(goto).
Esplorazione dell'albero delle soluzioni
• Backtracking trovare soluzioni a problemi in cui devono
essere soddisfatti dei vincoli.
• Enumera tutte le possibili soluzioni e scarta quelle che non
soddisfano i vincoli.
• Una tecnica classica consiste nell'esplorazione di strutture
ad albero e tenere traccia di tutti i nodi e i rami visitati in
precedenza
• Esempio scacchi: enumero tutte le possibili mosse con
una certa profondità e poi scelgo con Backtracking
• Esaminando tutte le alternative è un procedimento molto
lungo (si parla di complessità dell'algoritmo)
Lezione 4 - Decidibilità Trattabilità
Corso — Programmazione
Fondamenti di programmazione— Algoritmi
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Università degli Studi di Milano — Dipartimento di informatica
Problema - algoritmo - programma
Decidibilità(1)
• Consideriamo problemi di decisione
• Analizzare i limiti della risoluzione dei problemi mediante
algoritmi
• Decidibilità: Concetto legato alla decidibilità del
linguaggio che esprime il problema e solitamente alla
Macchina di Turing (MdT) che lo esegue
• Più nello specifico un algoritmo produrrà una
rappresentazione univoca dell'input mediante una stringa
• Diremo che un problema di decisione è:
Decidibile se il linguaggio associato è decidibile
Semidecidibile se il linguaggio associato è
Turing riconoscibile
Indecidibile se il linguaggio associato non è decidibile.
Esprimiamo un problema computazionale come un problema di riconoscimento di
linguaggi
Decidibilità(2)
• MdT M con tre possibili risultati computazione
(accettazione, rifiuto, loop):
Il linguaggio accettato da M è Turing riconoscibile
Problema semidecidibile
• MdT M con due possibili risultati computazione
(accettazione, rifiuto):
Il linguaggio accettato da M è decidibile.
Problema decidibile
Problemi indecidibili: motivazioni
• Sapere che esistono problemi non risolvibili con un
computer
• I problemi indecidibili non sono esoterici
Il problema generale della verifica del software non e'
risolvibile mediante computer
Costruire un perfetto sistema di debugging per determinare
se un programma si arresta.
Equivalenza di programmi: Dati due programmi essi
forniscono lo stesso output?
Individuazione dei virus: Questo programma e' un virus?
Problemi Indecidibili(1)
Problema: appartenenza di una stringa ad un linguaggio
• Il numero di linguaggi diversi su un alfabeto non è
numerabile
• I programmi (stringhe finite su un alfabeto) sono
numerabili
Li posso ordinare per lunghezza
• Quindi esistono infinitamente più linguaggi che programmi
• Come dire che esistono più problemi che algoritmi
• Quindi devono esistere problemi indecidibili (Godel 1931)
Problemi Indecidibili(2)
• Consideriamo un classico quesito di Bertrand Russell:
• In un paese vive un solo barbiere, un uomo ben sbarbato,
che rade tutti e soli gli uomini del villaggio che non si
radono da soli
• Il barbiere si rade da solo?
• Autoreferenza: può determinare indecidibilità
Problema dell'arresto
• Supponiamo per assurdo che sia possibile scrivere un
programma T che accetti in ingresso la coppia < P,x >,
formata da un qualsiasi programma P e dal suo ingresso
x, e restituisca in uscita > , se P(x) termina in un tempo
finito, e ⊥ altrimenti. Consideriamo il programma P ∗ che
realizza il seguente algoritmo, per ogni ingresso x:
1. Esegui T sull'ingresso < P ∗ ,x >;
2. Se T restituisce ⊥, termina;
3. Vai al Passo 1.
Problema dell'arresto: dimostrazione
• Dimostriamo l'assurdo supponendo di eseguire T
sull'ingresso < P ∗ ,x >.
1. T termina con valore di uscita ⊥; ma allora P ∗ termina al
Passo 2 e quindi il risultato restituito da T è scorretto;
2. T termina con valore di uscita >; ma allora P ∗ non
terminerebbe mai al Passo 2 e continuerebbe a ciclare
all'infinito: anche in questo caso il risultato restituito da T è
scorretto;
3. T non termina: anche in questo caso, ciò significherebbe
che T non funziona come abbiamo supposto.
Esempi
• Problemi indecidibili:
Decidere se un generico programma è corretto (calcola la
funzione desiderata)
Decidere se, dato un generico programma ed una
istruzione, l'istruzione sarà eseguita
Ciò non significa che non si possa stabilire se un
determinato programma sia corretto o esegua una
particolare istruzione
Riducibilità
• E' importante riconoscere che un problema P è
indecidibile.
Supponendo che esista una MdT che decide P e provarne la
contraddizione
Dimostrare che un problema indecidibile noto non sia
più difficile del problema P in questione
Dal punto di vista del linguaggio
Un linguaggio A è riducibile a un linguaggio B (A<mB) se
esiste una funzione calcolabile f : Σ∗ → Σ∗ | ∀w,w ∈ A,
f (w) ∈ B La funzione f è chiamata la riduzione di A a B.
Una funzione f : Σ∗ → Σ∗ è calcolabile se esiste una MdT M
tale che su ogni input w, M si arresta con f (w), e solo con
f (w), sul suo nastro.
Trattabilità ed intrattabilità(1)
• Non tutti i problemi sono computazionali
• Considerare la trattabilità di un problema significa
misurare l'efficienza del migliore algoritmo risolutore.
• Un problema è detto trattabile se esiste per la sua
risoluzione un algoritmo efficiente
Problemi facili (trattabili) → algoritmo efficiente
Problemi difficili (intrattabili) → non esiste un algoritmo
efficiente
Trattabilità ed intrattabilità(2)
• Un es. di problema intrattabile: la Torre di Hanoi
Torre di Hanoi
• Tre paletti e un certo numero di dischi di grandezza
decrescente
• Il gioco inizia con tutti i dischi incolonnati su un paletto in
ordine decrescente, in modo da formare un cono.
• Lo scopo del gioco e' portare tutti dischi sull'ultimo
paletto, potendo spostare solo un disco alla volta e
potendo mettere un disco solo su un altro disco piu'
grande, mai su uno piu' piccolo.
• il numero minimo di mosse necessarie per completare il
gioco è 2n − 1, dove n è il numero di dischi.
• Di conseguenza, secondo la leggenda, i monaci di Hanoi
dovrebbero effettuare almeno
18.446.744.073.709.551.615 mosse prima che il mondo
finisca (una mossa al secondo 585 miliardi di anni),
essendo n =64
Lezione 5 - Complessità in tempo e spazio
Corso — Programmazione
Fondamenti di programmazione— Algoritmi
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Università degli Studi di Milano — Dipartimento di informatica
Complessità in tempo e spazio
• Computabilità
• Definizione di un algoritmo corretto per risolvere il
problema
• Valutazioni di massima su trattabilità ed intrattabilità
• Valutazioni dettagliate sull'efficienza
Complessità dell' algoritmo
Tempo
Spazio
Computabilità e complessità (1)
• Calcolabilità: studia la frontiera tra problemi solubili e
problemi insolubili. Si limita ad aspetti qualitativi della
risolubilità dei problemi.
• Complessità: analizza problemi solubili.
Scopo: quantificare le risorse in tempo e/o spazio
necessarie a risolvere un problema dato, in funzione della
sua dimensione
• Teoria della computabilità: utilizza modelli di calcolo come
ad esempio automi a stati, MdT ecc., per dimostrare
l'esistenza o meno di algoritmi per una data classe di
problemi
• Teoria della complessità: ha lo scopo di determinare le
risorse richieste dall'esecuzione di un algoritmo per
risolvere un dato problema.
Un algoritmo formalmente deve essere finito, ma molto spesso deve essere finito in
un numero ragionevole di passi.
Complessità in tempo e spazio
• Risorse necessarie alla sua esecuzione
In termini di tempo di esecuzione e spazio per i dati
• Indicatore della difficoltà del problema
• Analisi degli algoritmi: studio della loro complessità
• Complessità ed efficienza sono ovviamente strettamente
legati
Efficienza di un algoritmo
• L'efficienza di un algoritmo è legata all'utilizzo di risorse di
calcolo
Tempo richiesto per trovare la soluzione (tempo di
esecuzione)
Spazio in termini di quantità di memoria richiesta
• Ci soffermeremo prevalentemente su valutazioni temporali
Tempo di esecuzione
• Considero un dato ingresso
• Valutare quanto tempo richiede ciascuna delle operazioni
elementari
• Valutare quante volte viene eseguita ciascuna delle
operazioni elementari
• Profilazione dell'algoritmo
Misurazione del tempo impiegato da un algoritmo di solito
in una specifica implementazione in un linguaggio, quindi
escludendo tempi di caricamento e di generazione
dell'output
Esempio Euclide: profilazione
Esecuzione di MCD(96,60)
• A seconda della copia n,m in input il tempo varia
• A seconda dei tempi t il tempo totale varia
Efficienza di un algoritmo: modello
• Per valutare l'efficienza di un algoritmo occorre fare
diverse assunzioni
• Prima cosa serve un modello di calcolo astratto
• Nella pratica il tempo utilizzato dipende da molti fattori:
Linguaggio di programmazione utilizzato, bravura del
programmatore, codice generato dal compilatore,
processore, cache, sistema operativo ecc.
• Vogliamo effettuare un'analisi che prescinda da tutti i
fattori citati ovvero vogliamo trovare un modello di calcolo
astratto
Con il quale possiamo definire una computazione
algoritmica
Con il quale possiamo esprimere quantitativamente
l'efficienza
Modelli di computazione
• Per analizzare un algoritmo serve un modello astratto
della tecnologia utilizzata per realizzarlo
Descrive le risorse utilizzate
Descrive il loro costo
• Considerando alcune operazioni elementari a
costo unitario per cui il reale tempo di calcolo possa
essere considerato proporzionale al numero di operazioni
eseguite
• Deve essere sufficientemente realistico
• Deve astrarre da dettagli di processori specifici
Modello di Macchina ad accesso casuale
(RAM)(1)
• Il modello computazionale più comunemente usato
• Modella fedelmente la stragrande maggioranza dei
processori
• Istruzioni eseguite in sequenza
• Ogni istruzione richiede un suo tempo costante per
l'esecuzione
Esistono altri modelli come le macchine basate su rete neurale, macchine quantistiche
o macchine chimiche astratte
Modello di Macchina ad accesso casuale
(RAM)(2)
• Costituita da 4 componenti:
Memoria
Programma
File di input
File di output
• La memoria è costituita da una sequenza di locazioni
0,1, . . . capace di salvare un unico valore intero alla volta
• L'indirizzo è il numero della locazione di memoria
• L'intero riferito da un indirizzo di una locazione di memoria
è il contenuto della locazione stessa
• Il programma è dato da una sequenza di istruzioni
(assegnamenti, input/output, cicli di controllo)
Modello di Macchina ad accesso casuale
(RAM) (3)
• Assegnamento Mem[l] := Mem[j] + Mem[k]. Mette nella
locazione l la somma dei valori nella locazione j e k
• Il file di input è una sequenza di valori consumati uno alla
volta da una istruzione di ``read''
• Il file di output è una sequenza di valori prodotti uno alla
volta da una istruzione di ``write''
• Il flusso di controllo del programma va normalmente da
una istruzione alla successiva ad eccezione di istruzioni di
``goto i'' o goto condizionati tipo if Mem[j] ≥ 0 then goto i
Modello di Macchina ad accesso casuale
(RAM): esempio (4)
1: Mem[0]:=0
2: read(Mem[1])
3: if Mem[1]≥ 0 then goto 5
4: goto 7
5 Mem[3]:=Mem[0]-Mem[1]
6: if Mem[3]≥ 0 then goto 16
7: write(Mem[1])
8: read(Mem[2])
9: Mem[3]:= Mem[2]-Mem[1]
10: if Mem[3]≥ 0 then goto 12
11: goto 14
12: Mem[3]:=Mem[1]-Mem[2]
13: if Mem[3]≥ 0 then goto 8
14: Mem[1]:=Mem[2] +Mem[0]
15: goto 3
16: halt
Profilazione e modello di calcolo
• Concetti utilizzati quando occorre valutare il
costo di esecuzione in maniera precisa
• Spesso usato per valutare il costo di algoritmi la cui
implementazione gira su sistemi embedded
Importante anche lo spazio e la dipendenza spazio - tempo
di esecuzione
• Il modello può cambiare a seconda del sistema reale su
cui l'implementazione dell'algoritmo girerà
• Dal punto di vista teorico senza considerazioni pratiche
implementative si tende ad astrarre dai costi dettagliati
Ordini di grandezza degli algoritmi in relazione all'input
Lezione 6 - Analisi di un algoritmo caso
medio, caso peggiore
Corso — Programmazione
Fondamenti di programmazione— Algoritmi
Marco Anisetti
e-mail: [email protected]
web: http://homes.di.unimi.it/anisetti/
Università degli Studi di Milano — Dipartimento di informatica
Efficienza di un algoritmo: input
• Il tempo di esecuzione di un algoritmo dipende sempre da
quanto è grande l'input (dimensione dell'istanza)
• La dimensione dell'istanza è proporzionale al numero di
elementi che la costituiscono
• Anche con un modello di calcolo semplificato (tempo
uguale al numero di operazioni eseguite) risulta difficile il
calcolo esatto delle operazioni
L'analisi viene generalmente effettuata considerando il
caso peggiore
Misurazione delle risorse
• Tempo
Numero totale di operazioni elementari eseguite
Machine independent
Tempo uguale per tutte le operazioni
• Spazio
Quantità massima di informazione da mantenere
(includendo dati iniziale e risultati)
• Tempo e spazio sono correlati spazio impiegato ≤ k ×
tempo impiegato
Profilazione generalizzata(1)
• Generalizzare l'esempio sulla profilazione di MCD in
relazione alla dimensione dell'input
• Considero il numero di iterazioni che debbo compiere
Nel caso MCD(96,60) ho 4 iterazioni
• Alcuni casi speciali generalizzando il tempo T (n,m) per
MCD(n,m)
T (n,1) = 1
T (n,kn) = 1
T (n,m) = 1 + T (m,n mod m)
T (n,m) = 1 + T (m,n) se m > n
Profilazione generalizzata(2)
• Volendo si può costruire una tabella e valutare i costi al
crescere di n e m
• Equivale a valutare più istanze del problema che
l'algoritmo risolve
• Occorre valutare il risultato al crescere degli input visto
che il tempo di esecuzione dipende dal valore degli input
Profilazione generalizzata(3)
• In particolare dipende principalmente dal valore di m dato
che n mod m viene eseguito da subito
E' evidente la persistenza di alcuni casi particolari dove il
costo è sempre uno anche al crescere di n ed m
• Casi fortunati altri molto sfortunati
• Non tutte le esecuzioni di un determinato algoritmo
richiedono lo stesso tempo
Profilazione generalizzata del caso
peggiore
• Tempo
Potremmo pensare che più il modulo è basso più siamo
vicini alla fine (ma con modulo alto non siamo lontani dalla
fine pensiamo a m mod m-1)
Caso peggiore è quando n mod m ∼
= m
2
Tempo nel caso peggiore: 1 + log2 (m)
• Spazio
Considerando il modello RAM, ho solo 3 celle usate per n,
m, r
Analisi di un algoritmo
• Quantità di risorse è funzione dei dati di ingresso
• Dimensione dei dati di ingresso: n
Caso migliore: il più breve tempo di esecuzione su tutti
gli ingressi di dimensione n
Caso medio: la media dei tempi di esecuzione su tutti gli
ingressi di dimensione n
Caso peggiore: il più lungo tempo di esecuzione su tutti
gli ingressi di dimensione n
Analisi del caso peggiore
• Limite superiore alle risorse che l'esecuzione
dell'algoritmo potrà mai richiedere.
• Il caso peggiore si verifica abbastanza spesso (es., ricerca
di un dato inesistente).
• Spesso il caso medio è analogo al caso peggiore.
Algoritmo e dimensione dell'istanza
• Crescita del tempo di calcolo al crescere della dimensione
dell'istanza
• La bontà di un algoritmo viene valutata rispetto al suo
comportamento asintotico ovvero quando la dimensione
dell'istanza tende all'infinito
• Buon comportamento asintotico: al crescere della
dimensione non cresce troppo il tempo
• Cattivo comportamento asintotico: algoritmo
applicabile nella pratica solo a istanze di dimensione
limitata
Ordine di grandezza
• Ciò che importa veramente non è la quantità precisa di
risorse, ma come questa cresce al crescere della
dimensione dell'ingresso
• O(logn) < O(n) < O(n2 ) < O(n3 ) < · · · < O(2n)