Algoritmi e Programmazione - Appunti

Gli algoritmi

Definizione di algoritmo

Un algoritmo è una sequenza finita di istruzioni che risolvono un problema e soddisfano i seguenti criteri:

• Ricevono valori in ingresso;
• Producono valori in uscita;
• Sono chiare, non ambigue ed eseguibili;
• Terminano dopo un numero finito di passi (altrimenti procedura);
• Operano su strutture dati.

Il modello computazionale

Chi o che cosa esegue un algoritmo? Uomo o macchina? Alcune domande fondamentali includono:

• Ci sono limiti sulla potenza delle macchine che possiamo costruire?
• Esiste un modello universale? La macchina di Turing.

Tesi di Church-Turing (1936) → La macchina di Turing può calcolare qualsiasi funzione che possa essere calcolata da una macchina fisicamente realizzabile.

Tipologie di problemi

• Problemi di decisione, che ammettono una risposta sì/no.
• Problemi di ricerca: esiste una soluzione valida?
• Problemi di verifica: la soluzione trovata è davvero una soluzione?
• Problemi di ottimizzazione: qual è la soluzione migliore?

Problemi di decisione

Possono essere:

• Decidibili (esiste un algoritmo che li risolve);
• Indecidibili (non esiste alcun algoritmo che li risolve).

La classe P

I problemi decidibili possono essere:

• Trattabili, cioè risolvibili in tempi "ragionevoli";
• Intrattabili, cioè non risolvibili in tempi "ragionevoli".

La ragionevolezza del tempo di soluzione comporta l'esistenza di un algoritmo polinomiale che li risolve. Si dice polinomiale un algoritmo che, operando su n dati, data una costante c > 0, termini in un numero di passi limitato superiormente da n^c. Perché si parli di ragionevolezza, c non deve eccedere 2.

La classe NP

Esistono problemi decidibili per cui conosciamo algoritmi esponenziali, ma non conosciamo algoritmi polinomiali. Non possiamo però escludere che esistano. Conosciamo algoritmi polinomiali per verificare che una soluzione è davvero tale.

È probabile che P sia un sottoinsieme proprio di NP.

La classe NP-completa

È formata da problemi NP tali che, se si trova un algoritmo polinomiale per un problema di questa classe, allora attraverso opportune trasformazioni polinomiali si possono trovare algoritmi polinomiali per tutti i problemi NP.

Algoritmi di ricerca su vettori

Ricerca sequenziale

Scansione del vettore da primo a potenzialmente fino all'ultimo elemento, operando un confronto con la chiave k. Per vettori non ordinati.

Ricerca binaria o dicotomica

Ad ogni passo confronto k con l'elemento centrale del vettore:

• Uguale: terminazione con successo;
• Minore: la ricerca prosegue nel sottovettore di sinistra;
• Maggiore: la ricerca prosegue nel sottovettore di destra.

L'analisi di complessità degli algoritmi

Analisi di complessità

Previsione delle risorse (memoria, tempo) richieste dall'algoritmo per la sua esecuzione. Caratteristiche:

• Indipendente dalla macchina;
• Indipendente dai dati di ingresso di una particolare istanza del problema;
• Dipendente dalla dimensione n del problema.

Output → S(n), occupazione di memoria, e T(n), tempo di esecuzione.

Classificazione degli algoritmi

• 1 → Costante.
• logn → Logaritmico.
• n → Lineare.
• nlogn → Linearitmico.
• 2n → Quadratico.
• 3n → Cubico.
• n² → Esponenziale.

Analisi asintotica di caso peggiore

Scopo → Stima di un limite superiore a T(n) di un algoritmo su n dati nel caso peggiore, stima asintotica perché si fa tendere n ad infinito. Perché caso peggiore:

• Conservatività della stima;
• Casistica del caso peggiore molto frequente;
• Il caso medio:
• O coincide con il caso peggiore;
• O non è definibile a meno di ipotesi complesse sui dati.

Complessità inferiore → Compensa l'inefficienza dell'hardware.

Analisi della ricerca lineare, della ricerca dicotomica e dell'insertion sort.

Notazione asintotica O, Ω e Θ

• T(n) = O(g(n)), g(n) si dice limite superiore lasco di T(n). T(n) non si comporterà mai peggio della classe di complessità a cui appartiene.
• T(n)=Ω(g(n)), g(n) si dice limite inferiore lasco di T(n). La quantità di tempo sufficiente per eseguire l'algoritmo con qualsiasi dati è g(n).
• T(n)=Θ(g(n)), g(n) si dice limite asintotico stretto di T(n).

Online Connectivity

Una relazione di equivalenza gode delle seguenti proprietà:

• Riflessiva;
• Simmetrica;
• Transitiva.

Una relazione di connessione è una relazione di equivalenza. Output: lista delle connessioni ignote in precedenza (o non implicate transitivamente dalle precedenti). Nulla se p e q sono già connessi (direttamente o indirettamente), altrimenti ( p, q ).

Approccio

Senza il grafico, lavoriamo coppia per coppia (on-line), mantenendo e aggiornando le informazioni necessarie per determinare la connettività:

• Ogni coppia è formata da 2 interi tra 0 e N – 1;
• Insiemi S delle coppie connesse, inizialmente tanti insiemi quanti i nodi, ogni nodo è connesso solo con se stesso;
• Operazioni astratte: find (trova insieme a cui appartiene un oggetto), union (unisci due insiemi).

Quick find

Algoritmo: per tutte le coppie ( p, q )

• Leggi la coppia ( p, q );
• Esegui find su p, poi su q;
• Se S_p e S_q coincidono, passa alla coppia successiva, altrimenti esegui union di S_p e S_q.

Find → Semplice riferimento a una cella del vettore id[indice], costo unitario.

Union → Scansione del vettore per cambiare gli elementi che valgono p in q, costo lineare nella dimensione del vettore.

Complessivamente il numero di operazioni è legato a numero coppie * dimensione del vettore.

Quick union

Algoritmo: per tutte le coppie ( p, q )

• Leggi la coppia ( p, q );
• Se (id[p])* = (id[q])* non fare nulla (la coppia è già connessa) e passa alla coppia successiva, altrimenti id[(id[p])*] = (id[q])* (connetti la coppia).

Find → Percorrimento di una "catena" di oggetti, costo al massimo lineare nel numero di oggetti, in generale inferiore.

Union → Semplice in quanto basta far sì che un oggetto punti all'altro, costo unitario.

Complessivamente il numero di operazioni è legato a numero coppie * lunghezza della "catena".

Weighted quick union

Ottimizzazione della quick union, per ridurre la lunghezza della catena si mantiene traccia del numero di elementi di ciascun albero e si collega l'albero più piccolo a quello più grande.

Find → Percorrimento di una "catena" di oggetti, costo al massimo logaritmico nel numero di oggetti.

Union → Semplice in quanto basta far sì che un oggetto punti all'altro, costo unitario.

Complessivamente il numero di operazioni è legato a numero coppie * lunghezza della "catena", ma quest'ultima cresce in modo logaritmico!

Logaritmico per i seguenti motivi:

• Conta distanza massima tra un nodo e la radice, la distanza cresce di 1 quando si collega un albero più piccolo a una albero più grande;
• Ad ogni connessione di albero piccolo ad albero grande si genera un albero la cui dimensione T₂ è almeno il doppio di T₁;
• Se ad ogni passo il numero di elementi dell'albero almeno raddoppia e ci sono N elementi, dopo i passi ci saranno almeno 2ⁱ elementi. Deve valere 2ⁱ ≤ N, quindi i ≤ logN.

Gli algoritmi di ordinamento

Classificazione: interni/esterni, in loco/stabili

Ordinamento interno:

• Dati in memoria centrale;
• Accesso diretto agli elementi.

Ordinamento esterno:

• Dati in memoria di massa;
• Accesso sequenziale agli elementi.

Ordinamento in loco → Vettore di n dati + locazioni di memoria ausiliarie in numero fisso.

Ordinamento stabile → Immutato l'ordinamento relativo di dati con ugual valore della chiave.

Classificazione: complessità

• O(n²) → Semplici, iterativi, basati sul confronto (insertion sort, selection sort, exchange/bubble sort).
• O(n^3/2) → Shellsort (con certa scelta di sequenza).
• O(nlogn) → Più complessi, ricorsivi, basati sul confronto (mergesort, quicksort, heapsort).
• O(n) → Applicabili solo con ipotesi restrittive sui dati, basati sul calcolo (counting sort, radix sort, bin/bucket sort).

È possibile un'analisi più raffinata, in cui si distinguono le operazioni di confronto e scambio. Quando infatti il dato da ordinare occupa molta memoria, lo spostamento può essere costoso, comunque la complessità asintotica non cambia.

Generalizzazione

Per n interi distinti, numero di ordinamenti = numero di permutazioni n!.

Complessità: numero h di confronti (altezza dell'albero).

Ogni soluzione = foglia.

Numero di foglie = 2^h.

Approssimazione di Stirling per arrivare al limite inferiore di complessità.

Gli algoritmi iterativi di ordinamento

Insertion sort

Algoritmo di ordinamento, molto importante. Esempio su un vettore:

• Interi in un vettore A con indici compresi tra l e r.
• Vettore diviso in 2 sottovettori:
  • Di sinistra: ordinato;
  • Di destra: disordinato.
• Un vettore di un solo elemento è ordinato.
• Approccio incrementale: ad ogni passo si espande il sottovettore ordinato inserendovi un elemento.
• Terminazione: tutti gli elementi inseriti ordinatamente.
• Al passo i–esimo si scandisce il sottovettore ordinato fino a trovare un A_j > A_i, shiftando a destra di una posizione degli elementi da A_j ad A_i-1.

Caratteristiche:

• In loco;
• Stabile, no scambio tra elementi uguali;
• O(n²) per scambi e confronti nel caso peggiore.

Bubble sort

• Dati: interi in un vettore A con indici compresi tra l e r.
• Vettore diviso in 2 sottovettori:
  • Di destra: ordinato, inizialmente vuoto;
  • Di sinistra: disordinato, inizialmente coincide con A.
• Operazione elementare: confronto tra elementi successivi del vettore A[j] e A[j+1], scambio se A[j] > A[j+1].
• Approccio incrementale: iterazione i, il massimo del sottovettore SX è assegnato a A[r–i+l]; incremento di i. Il sottovettore DX ordinato cresce di 1 posizione verso SX, dualmente quello di SX decresce di 1 posizione.
• Terminazione: tutti gli elementi inseriti ordinatamente.
• Possibili ottimizzazioni: flag che indica se vi sono stati scambi, interrompendo anticipatamente il ciclo se non ci sono stati.

Caratteristiche:

• In loco;
• Stabile: tra più chiavi duplicate quella più a DX prende la posizione più a DX e non viene mai scavalcata a DX da un'altra chiave uguale;
• O(n²) per scambi e confronti nel caso peggiore.

Selection sort

• Dati: interi in un vettore A con indici compresi tra l e r.
• Vettore diviso in 2 sottovettori:
  • Di sinistra: ordinato, inizialmente vuoto;
  • Di destra: disordinato, inizialmente coincide con A.
• Approccio incrementale: iterazione i, il minimo del sottovettore DX è assegnato a A[i], incremento di i.
• Terminazione: tutti gli elementi inseriti ordinatamente.
• La ricerca del minimo nel sottovettore DX comporta la sua scansione.

Caratteristiche:

• In loco;
• Non stabile: scambio tra elementi uguali;
• O(n²) per scambi e confronti nel caso peggiore.

Shellsort

Limite dell'insertion sort: il confronto, quindi lo scambio, avviene solo tra elementi adiacenti. Idea dello shellsort:

• Confrontare, quindi eventualmente scambiare, elementi a distanza h tra di loro;
• Definendo una sequenza decrescente di interi h che termina con 1. La sequenza influenza le prestazioni e ce ne sono diversi tipi (sequenza di Knuth, h = 3h + 1).

Si dice h-ordinato un array formato da h sottosequenze non contigue ordinate composte da elementi che distano tra di loro h. Per ognuna delle sottosequenze si applica l'insertion sort.

Caratteristiche:

• In loco;
• Non stabile: possibile scambio tra elementi uguali;
• Con la sequenza di Knuth esegue meno di O(n^3/2) confronti, con la sequenza originale di Shell (2ⁱ) può degenerare a O(n²).

Counting sort

Ordinamento per calcolo: determinare, per ciascun elemento da ordinare x, quanti elementi sono minori o uguali a x. x direttamente assegnato alla posizione finale.

Si usano 3 vettori:

• Vettore di partenza A di n interi;
• Vettore risultato B di n interi;
• Vettore delle occorrenze C di k interi se i dati sono nell'intervallo [0 .. .k – 1].

Algoritmo:

• Passo 1: occorrenze semplici, in C[i] il numero di elementi di A pari a i.
• Passo 2: occorrenze multiple, in C[i] il numero di elementi di A ≤ i.
• Passo 3: per ogni j, in C[A[j]] il numero di elementi ≤ A[j], quindi posizione finale di A[j] in B (B[C[A[j]]] = A[j]).

Caratteristiche:

• Non in loco;
• Stabile;
• T(n)=O(n).

Richiami di matematica discreta: grafi e alberi

Grafi

Definizione: G = (V, E).

• V: insieme finito e non vuoto di vertici.
• E: insieme finito di archi, che definiscono una relazione binaria su V.

Grafi orientati/non orientati:

• Orientati: arco = coppia ordinata di vertici;
• Non orientati: arco = coppia non ordinata di vertici.

Se il contesto ammette i cappi, ma il grafo ne è privo, esso si dice semplice.

Incidenza e adiacenza

Arco (a, b):

• Incidente da vertice a;
• Incidente in vertice b;
• Incidente (insistente) sui vertici a e b, detti adiacenti.

Grado di un vertice

Grafo non orientato:

• Degree = numero di archi incidenti.

Grafo orientato:

• In_degree = numero di archi entranti;
• Out_degree = numero di archi uscenti;
• Degree = in_degree + out_degree.

Cammini e raggiungibilità

Un cammino è un arco o una serie di archi che porta da un vertice ad un altro. Questo cammino ha una lunghezza e si dice semplice se non tocca uno stesso vertice per più di una volta.

Si parla di ciclo quando il vertice di arrivo coincide con il vertice di partenza. Il ciclo è semplice se il cammino è semplice. Un cappio è un ciclo di lunghezza 1. Un grafo senza cicli è detto aciclico.

Connessione nei grafi non orientati

Un grafo non orientato si dice connesso se tutti i vertici sono tra loro collegati per mezzo di cammini. Si dice componente connessa il sottografo connesso massimale. Un grafo non orientato connesso ha una sola componente connessa.

Un grafo si dice orientato fortemente connesso se tutti i vertici sono tra loro collegati per mezzo di cammini. Si dice componente fortemente connessa il sottografo fortemente connesso massimale. Un grafo orientato fortemente connesso ha una sola componente fortemente connessa.

Grafi densi/sparsi

Un grafo si dice denso se |E| è circa |V|², mentre si dice sparso se |E| << |V|².

Grafo completo

Si dice completo un grafo in cui ogni vertice è legato agli altri per mezzo di un arco. Non orientato → Numero di archi = numero di combinazioni di |V| elementi a 2 a 2. Orientato → Numero di archi = numero di disposizioni di |V| elementi a 2 a 2.

Grafo bipartito e pesato

Un grafo non orientato che può essere partizionato in 2 insiemi tali che i nodi del primo insieme possono essere raggiunti dal secondo e viceversa siccome è non orientato. Un grafo è pesato se gli archi hanno dei pesi.

Alberi non radicati (o liberi)

Albero non radicato (o libero) = grafo non orientato, connesso, aciclico. Foresta = grafo non orientato, aciclico.

Proprietà di un albero

• Ogni coppia di nodi connessa da un unico cammino semplice.
• La rimozione di un arco lo sconnette.
• G connesso e |E| = |V| – 1.
• G aciclico e |E| = |V| – 1.
• G aciclico, l'aggiunta di un arco introduce un ciclo.

Alberi radicati

Esiste un nodo r detto radice, sussiste poi una relazione di parentela con i nodi ad esso legati, i figli. Una radice non ha padre.

• Una foglia non ha figli.
• Esistono antenati, discendenti. Padre e figlio sono nodi adiacenti.

Proprietà di un albero T

• Grado (T) = numero max di figli.
• Profondità (x) = lunghezza del cammino da r a x.
• Altezza (T) = profondità massima.

Gli alberi si ottengono con rappresentazione left-child right-sibling.

Alberi binari

Albero di grado 2 (cioè ogni nodo ha massimo due figli). Ricorsivamente T è un insieme di nodi vuoto oppure una radice, un sottoalbero sinistro, un sottoalbero destro.

Un albero binario è completo se sono soddisfatte le due seguenti condizioni:

• Tutte le foglie hanno stessa profondità;
• Ogni nodo o è una foglia o ha 2 figli.

Allora numero di foglie è 2^h, numero di nodi è 2^{h + 1} – 1. Albero binario bilanciato → Tutti i cammini radice-foglia sono di ugual lunghezza. Se T è completo, allora T è bilanciato, non necessariamente il viceversa. Alberi binari quasi bilanciati → La lunghezza di tutti i cammini radice-foglia differisce al massimo di 1.

Memorizzazione e accesso

• Vettori o array:
  • Dati contigui in memoria;
  • Accesso diretto, O(1).
• Liste:
  • Dati non contigui in memoria;
  • Accesso sequenziale, si scorre la sequenza.