Appunti completi corso Algoritmi

ALGORITMO DI KRUSKAL

Molto semplicemente si prendono gli archi di peso minimo e si continua a prendere gli

archi di peso minimo che connettono nuovi vertici finché avremo connesso tutti i vertici.

Questo algoritmo lo studiamo per come funziona ma non vediamo l'implementazione,

perché appartiene ad una categoria di algoritmi che non vedremo.

DUE NOTE FONDAMENTALI PER L'ESAME:

La visita in ampiezza di un grafo non pesato e non orientato genera un free tree.

– Quindi se ti chiede di trovare un free tree su un grafo che non ha pesi ti basta una

banale visita in ampiezza :)

I free tree sono degli spanning tree, quindi il numero di archi è uguale al numero di

– vertici – 1

Questa lezione la vediamo in cinque minuti giusto per un'idea generale perché è stata

praticamente tagliata.

Tutti gli algoritmi hanno delle finalità che si possono collocar ein una di queste categorie:

PROBLEMA DECISIONALE: dire se qualcosa è vero oppure no

– PROBLEMA DI RICERCA: trovare una soluzione che rispetti certi criteri

– PROBLEMA DI OTTIMIZZAZIONE: cercare la soluzione migliore tra le tante

– ammissibili

Ogni algoritmo poi può essere implementato seguendo una di queste tecniche:

DIVIDE ET IMPERA

– PROGRAMMAZIONE DINAMICA

– BACKTRACKING

– GREEDY

–

Il DIVIDE ET IMPERA consiste nel risolvere problemi grossi spezzettandoli in

sottoproblemi più piccoli facili da risolvere e poi combinare i risultati. Un esempio sono il

Quicksort e il Mergesort, dove ricorsivamente si risolve l'ordinamento passando prima su

array di dimensioni dimezzate. Il divide et impera non funziona allo stesso modo in tutti gli

algoritmi: per esempio nel quicksort la parte di suddivisione è più complessa, mentre la

ricombinazione praticamente non c'è perché il pivot alla fine si trova nella posizione

definitiva. Nel mergesort invece la divisione è banale ed è più complessa la

ricombinazione dei risultati.

Il divide et impera è utile quando i sottoproblemi sono indipendenti, ma quando ci sono

sottoproblemi che si ripetono, questa tecnica fa schifo. Per esempio il calcolo della

sequenza di Fibonacci con la ricorsione ha una complessità esponenziale, perché ogni

valore viene ricalcolato più volte. In queste situazioni entra in gioco la

PROGRAMMAZIONE DINAMICA, che invece al contrario parte da problemi semplici e da

questi ottiene dei valori intermedi con cui risolvere i problemi più grandi. Per poter

memorizzare i valori intermedi normalmente si fa uso di array o matrici. Esempio che

abbiamo visto è l'algoritmo di Floyd per i grafi.

Il BACKTRACKING è il metodo più sfigato: prova tutto. È alla base di tutti gli algoritmi di

attraversamento e visita dei grafi, ma anche per risolvere problemi per cui non esistono

soluzioni migliori, come la risoluzione di un labirinto, del Sudoku o la colorazione dei grafi.

Nell'esempio del Sudoku, risolverlo ha complessità esponenziale (con base 9 tra l'altro),

ma verificare se una soluzione proposta è effettivamente una soluzione, ha al contrario

una complessità polinomiale. Ciò non è per forza vero in tutti i casi, come vedremo nella

prossima, fighissima lezione.

Gli algoritmi GREEDY sono quelli che effettuano scelte ottimali partendo da informazioni

solo locali. Quindi non valutano tutte le soluzioni possibili, ma solo quelle localmente

disponibili. Sono quindi efficienti per problemi di ottimizzazione, anche più della

programmazione dinamica. Un esempio è l'algoritmo di Dijkstra. Anche i codici di

Huffman si formano con questa classe di algoritmi.

Questa lezione rappresenta un ponte tra il corso di algoritmi e quello di informatica teorica.

Quello che vogliamo capire è: se un problema possiamo risolverlo con una macchina di

Turing in tempi ragionevoli, allora possiamo risolverlo in tempi ragionevoli anche su

calcolatore? In pratica è un analogo della tesi di Chruch applicata alla complessità. Noi

sappiamo già che, se un problema si può risolvere con una macchina di Turing, allora si

può risolvere anche con un calcolatore. Ma questo è vero anche per la complessità?

Prima di tutto dobbiamo capire come calcolare la complessità di una macchina di Turing.

Ma spoilero subito: NON C'È CORRISPONDENZA!

Nelle macchine di Turing deterministiche a k nastri, definiamo il costo temporale

unitario per ogni “passo” o meglio transizione. Cioè ogni volta che leggiamo un carattere,

scriviamo su nastro o spostiamo le testine. Specifichiamo che si parla di DETERMINISMO,

perché con il non determinismo accadono cose interessanti. Sappiamo che una macchina

di Turing può non arrestarsi mai, e in quel caso il costo temporale diventa infinito. Per

quanto riguarda la complessità spaziale, la calcoliamo come il numero massimo di celle

occupate su ogni nastro di memoria. NON consideriamo i nastri di input e output, in quanto

non sono memorie. Siccome anche qua non ci interessa l'espressione esatta ma la

crescita asintotica, useremo alla fine un parametro n dove normalmente n indica la

lunghezza della stringa in ingresso. R

Facendo un esempio sul linguaggio wcw , usando l'implementazione che tutti noi

conosciamo, viene fuori che sia il tempo di esecuzione che lo spazio richiesto sono O(n).

Per il tempo non possiamo fare di meglio, perché comunque ci tocca almeno leggere tutta

la stringa. Per lo spazio invece, agendo sulla codifica dei dati, possiamo ridurci a O(logn),

2

ma in quel caso la complessità temporale esplode a O(n logn)! Anche in questo mondo

abbiamo sempre un trade off tra spazio e tempo, in quanto la riduzione dello spazio

richiede una codifica dei dati e la testina deve andare di qua e di là... Infatti se proviamo

ad implementare un algoritmo di ricerca con le macchine di Turing, scopriamo che la

ricerca sequenziale è la migliore! Sempre con complessità O(n). La ricerca binaria invece

peggiora le prestazioni, diventando O(nlogn), contro il O(logn) dei calcolatori. Questo

proprio perché le macchine di Turing sono prive di accesso sequenziale, per cui in una

ricerca binaria dovremmo continuamente saltare da una parte all'altra! Ecco qui la

dimostrazione che non c'è equivalenza tra complessità delle macchine di Turing e quella

dei calcolatori. Ma vogliamo chiederci adesso: la differenza è davvero radicale, o è solo

marginale?

Siccome sappiamo ora che la complessità è dipendente dal modello di calcolo, studiamola

anche sugli altri automi.

FSA La complessità spaziale è sempre O(1), in quanto non hanno memoria.

La complessità temporale è sempre O(n), dato che dobbiamo leggere

sempre l'intera stringa. Negli automi a stati finiti la complessità è fissa e

determinata per qualsiasi problema risolvibile tramite essi.

(D)PDA Anche in questo caso la complessità temporale è sempre O(n) visto che ci

tocca leggere l'intera stringa. La complessità spaziale può variare da O(1)

(non scrivo niente) a O(n), visto che si può scrivere un numero limitato di

simboli alla volta.

Un caso particolare è dato dalle macchine di Turing a nastro singolo: dato che hanno

un solo nastro per tutto (input, dati, output), la complessità spaziale non potrà mai essere

inferiore a O(n)! E il tempo invece esplode eheh

Chiediamoci un'altra domanda: possiamo migliorare la complessità? Di quanto? Qui

entrano in gioco i TEOREMI DI ACCELERAZIONE LINEARE:

Data una certa macchina di Turing con una determinata complessità spaziale,

– possiamo costruirne una equivalente con una complessità spaziale ridotta di un

fattore costante, agendo sulla codifica dei dati (per esempio arricchendo l'alfabeto)

Data una certa macchina di Turing a k nastri, possiamo realizzarne una equivalente

– ad un nastro di memoria lasciando inalterata la complessità spaziale (anche qui può

essere necessario agire sull'alfabeto)

Un terzo teorema ci dice che possiamo fare entrambe le cose, cioè ridurre sia i nastri che

lo spazio, ma i miglioramenti sono solo di tipo lineare, cioè si agisce sulle costanti

moltiplicative, non sull'ordine di grandezza! Lo stesso principio vale per la complessità

2 2 2

temporale: possiamo passare da 10n a 5n , ma la complessità è pur sempre O(n ). Per

scendere di ordini di grandezza bisogna proprio cambiare algoritmo! Non puoi passare da

4

n a n come pensavi tu cambiando una virgola...

Approfondiamo ora l'aspetto della differenza di complessità della ricerca binaria tra MT e

RAM. Già a prima vista sembra che la RAM svernici la MT in tutto: è ad accesso casuale

(mentre Turing è sequenziale) e alcune operazioni come l'addizione sono elementari

(mentre su una MT pure la somma ha complessità lineare). È per questi motivi che con

una MT non puoi andare sotto O(n). Ci serve quindi un'analisi di complessità anche sulle

macchine RAM. Assumiamo per ora che ogni istruzione abbia lo stesso costo (temporale

ed eventualmente spaziale), ovvero applichiamo il CRITERIO DI COSTO UNIFORME.

Questo criterio non è sempre opportuno, specialmente nel caso in cui operiamo su cifre

molto grandi, per cui sono necessarie più celle per memorizzare i risultati. In quel caso è

meglio applicare il CRITERIO DI COSTO LOGARITMICO, in cui ogni istruzione costa logi

con i il numero di bit occupati dall'operando (1 se l'operando non c'è). La complessità

quindi dipende dalla lunghezza dei dati. Tuttavia è stupido usare questo criterio quando

invece i dati restano di dimensioni inalterate rispetto ai valori di partenza, perché la

complessità aumenta inutilmente: in pratica l'uso di uno o dell'altro criterio dipende

dall'applicazione particolare! Se i dati non cambiano ordine di grandezza va bene il costo

uniforme, altrimenti è più ragionevole il costo logaritmico (fattoriali, moltiplicazioni assurde,

ricorsioni spinte...). Per non stare lì a fare i conti su ogni singola istruzione, puoi fare che il

costo con criterio logaritmico è quello uniforme per il logaritmo del costo uniforme stesso:

Siamo quindi arrivati a dire che la complessità di un algoritmo dipende dal modello di

calcolo usato per implementarlo. Ma non possiamo dire che tutti gli algoritmi sono sempre

migliori su uno stesso modello: se una macchina fosse superiore in ogni situazione,

studieremmo solo quella. Esattamente come succede per altri algoritmi e strutture dati:

ognuno è più efficiente in una determinata situazione e meno in altre. Non abbiamo ancora

risposto però alla d