Introduzione a Problemi e Algoritmi PDF

Introduzione a problemi e algoritmi February 28, 2019 Obiettivi: introduzione allo sviluppo ed all'analisi degli algoritmi. Argomenti: problemi computazionali, algoritmi, insolubilità ed intrattabilità, il problema Peak nding....

Introduzione a problemi e algoritmi February 28, 2019 Obiettivi: introduzione allo sviluppo ed all'analisi degli algoritmi. Argomenti: problemi computazionali, algoritmi, insolubilità ed intrattabilità, il problema Peak nding. Gli algoritmi cambiano il mondo: I fantastici 9 (un libro) spiega in dettaglio 9 algoritmi che hanno già cambiato il mondo (Indicizzazione nei motori di ricerca, PageRank, Crittograa a chiave pubblica, Codici a correzione d'errore, Riconoscimento di forme, Compressione dei dati, Coerenza nei database, Firme digitali, Vericatore di programmi). Vista l'importanza, a scuola viene introdotto il cosiddetto pensiero computazionale (la quarta abilità di base oltre leggere, scrivere e calcolare) pure per bambini piccoli. Knuth: In realtà una persona non ha davvero capito qualcosa no a che non è in grado di insegnarla a un computer, cioè no a che non è in grado di ricavarne un algoritmo (un programma) che risolve il problema in questione. 1 Problemi computazionali Un problema computazionale è una collezione di domande, le istanze, per cui sia stabilito un criterio (astratto) per riconoscere le risposte corrette. Massimo comune divisore. Ingressi: coppie di interi positivi a, b non entrambi nulli; Uscite: un intero positivo c tale che c divide sia a che b e se un intero positivo d divide a e b allora d ≤ c. Più formalmente: un problema computazionale è una relazione binaria, cioè un insieme di coppie ordinate in cui ogni coppia è composta da un ingresso (la domanda) e l'uscita corrispondente (la risposta). Questa relazione denisce come devono essere gli ingressi, come devono essere le uscite, e, dato un certo ingresso, come deve essere l'uscita per essere la soluzione. Massimo comune divisore. R = {((a, b), c)|a ∈ Z ∧ b ∈ Z ∧ (a > 0 ∨ b > 0) ∧ a mod c = 0 ∧ b mod c = 0 ∧ (∀d > 0.(a mod d = 0 ∧ b mod d = 0) =⇒ d ≤ c)} Il dominio è l'insieme di istanze (domande) che hanno una risposta: dom(R) = {i|∃r.(i, r) ∈ R} Un problema computazionale (cioè una relazione binaria) è univoca se ogni istanza ammette una sola risposta. (Disegno.) Esempio. Moltiplicazione fra interi (univoca). R = {((a, b), c)|a ∈ Z ∧ b ∈ Z ∧ a · b = c} Esempio. Fattorizzazione (non univoca). Qn R = {(a, (c1 ,..., cn ))|a ∈ Z ∧ a > 1 ∧ i=1 ci = a ∧ ∀1 ≤ i ≤ n.ci ∈ P} Esempio. Fattorizzazione (univoca). Qn R = {(a, (c1 ,..., cn ))|a ∈ Z ∧ a > 1 ∧ i=1 ci = a ∧ ∀1 ≤ i ≤ n.ci ∈ P ∧ ∀1 ≤ i ≤ n − 1.ci ≤ ci+1 } 1 2 Algoritmi Un algoritmo è un metodo meccanico per risolvere un problema computazionale. Una procedura è una sequenza nita di operazioni meccanicamente eseguibili, per produrre univocamente un'uscita a partire da certi ingressi. Un algoritmo è una procedura che termina per ogni ingresso ammissibile. Un algoritmo è deterministico se eseguito più volte sullo stesso input, fornisce sempre lo stesso output. Ad ogni algoritmo deterministico è associata una funzione dagli ingressi alle uscite. Un algoritmo risolve un problema computazionale R, ossia è corretto rispetto ad R, se, per qualunque input e l'output corrispondente, la coppia (input, output) è in R. Certi algoritmi si imparano a scuola: somma in colonna. Termine algoritmo viene dalla trascrizione latina del nome del matematico persiano al-Khwarizmi (780-850) che ha scritto Algoritmi de numero Indorum dove descrive operazioni utilizzando il sistema di numerazione indiano. L'algoritmo considerato il primo algoritmo è quello che calcola il massimo comune divisore, chiamato l'algoritmo di Euclide (367-283 a.C.) ma forse era risaputo già prima: 1: Euclid(a, b) 2: r ← a mod b 3: while r 6= 0 do 4: a←b 5: b←r 6: r ← a mod b 7: end while 8: return b Simulazione dell'algoritmo con a = 35, b = 55. Programma vs. algoritmi. Un programma può contenere diversi algoritmi. Un programma è scritto in uno specico linguaggio di programmazione. In un programma occorre specicare ed implementare opportune strutture dati. Programma=Algoritmi+Strutture Dati 3 Problemi impossibili e molto dicili É vero che tutti i problemi computazionali ammettano una soluzione algoritmica? No, esistono problemi indecidibili. Un famoso problema indecidibile è il problema della terminazione che pone la seguente domanda: è possibile sviluppare un algoritmo che, dato un programma e un determinato input nito, stabilisca se il programma in questione termini o continui la sua esecuzione all'innito. La risposta è no. Un problema intrattabile è un problema per il quale non esiste un algoritmo con complessità polinomiale in grado di risolverlo. Torre di hanoi con n dischi richiede 2n − 1 spostamenti. Esistono problemi, detti NP-completi, tali che tutti o nessuno ammettono una soluzione in tempo polino- miale. Esempio: cercare un cammino hamiltoniano (un cammino in un grafo, orientato o non orientato, è detto hamiltoniano se esso tocca tutti i vertici del grafo una e una sola volta). 4 Un esempio per illustrare dei temi che saranno studiati durante il corso Il problema del peak nding. Input: un vettore A[0...n − 1] di n numeri interi; Output: un intero 0 ≤ p ≤ n − 1 tale che A[p − 1] ≤ A[p] ≥ A[p + 1] dove A[−1] = A[n] = −∞. 2 Esempio: se A = |1, 2, 6, 6, 5, 3, 3, 3, 7, 4, 5| allora abbiamo 5 picchi nelle posizioni 2,3,6,8,10. Cerchiamo un picco percorrendo il vettore da sinistra a destra no al picco che si trova più a sinistra. 1: Peak-Find-Left(A[0...n − 1]).n≥1 2: p←0 3: k←1 4: while k < n ∧ A[p] < A[k] do 5: p←k 6: k ←k+1 7: end while 8: return p (Provare ad eliminare la variabile k dall'algoritmo precedente.) Caratteristiche di questo algoritmo: nel caso migliore p = 0 è un picco e si fa un singolo confronto (fra gli elementi del vettore); nel caso peggiore il picco si trova nell'ultima posizione, si percorre tutto il vettore, e si fanno n−1 confronti. Di solito ci interessa caratterizzare il caso peggiore (oppure il caso medio ma qui non ne parliamo). Nel caso peggiore si percorre tutto il vettore. Con lo stesso sforzo si può trovare il picco più alto: 1: Peak-Find-Max(A[0...n − 1]).n≥1 2: p←0 3: for k ← 1 to n − 1 do 4: if A[p] < A[k] then 5: p←k 6: end if 7: end for 8: return p Questo fatto suggerisce che si può fare meglio. Cosa garantisce di avere un picco in un certo segmento del vettore A[i...j] con i ≤ j? Se A[i − 1] ≤ A[i] e A[j] ≥ A[j + 1] allora deve esserci un picco nel segmento A[i...j]. Più formalmente: Teorema: Siano i e j tali che0 ≤ i ≤ j ≤ n − 1 e A[0...n − 1] un vettore di n interi. Se A[i − 1] ≤ A[i] e A[j] ≥ A[j + 1] allora esiste i ≤ p ≤ j tale che A[p − 1] ≤ A[p] ≥ A[p + 1] ossia p è un picco in A[i...j]. Dimostrazione: Se i=j abbiamo A[i − 1] ≤ A[i] ≥ A[i + 1] e quindi p=i è un picco. Se i 6= j allora scegliamo una qualunque posizione q1 tale che i ≤ q1 ≤ j. Abbiamo tre possibilità: A[q1 −1] ≤ A[q1 ] ≥ A[q1 + 1] e quindi la posizione q1 è un picco; A[q1 − 1] > A[q1 ] e quindi la posizione q1 non è un picco; A[q1 ] < A[q1 + 1] e quindi la posizione q1 non è un picco. Se q1 è un picco allora il picco c'è. Se q1 non è un picco siano i1 = i e j1 = q1 − 1 se A[q1 − 1] > A[q1 ] e i1 = q1 + 1 e j1 = j altrimenti. Si nota che abbiamo A[i1 − 1] ≤ A[i1 ] e A[j1 ] ≥ A[j1 + 1], cioè i1 e j1 soddisfano le condizioni richieste dal teorema ma il segmento A[i1...j1 ] contiene meno elementi del segmento A[i...j]. Ora si ripete lo stesso ragionamento ma sul segmento A[i1...j1 ]: se i1 = j1 allora la posizione p = i1 è un picco; se i1 6= j1 q2 tale che i1 ≤ q2 ≤ j1. Se q2 è un picco allora allora si sceglie una qualunque posizione un picco c'è. Se non lo è, allora abbiamo A[q2 − 1] > A[q2 ] oppure A[q2 ] < A[q2 + 1]. Se q2 non è un picco siano i2 = i1 e j2 = q2 − 1 se A[q2 − 1] > A[q2 ] e i2 = q2 + 1 e j2 = j1 altrimenti. Ora si ripete lo stesso ragionamento ma sul segmento A[i2...j2 ]... Procedendo così o si trova un picco nella sequenza q1 , q2 ,... oppure per una certa k si ha i k = jk e quindi ik è un picco. (Una dimostrazione più compatta e meno procedurale si ottiene utilizzando l'induzione completa.) 3 Il teorema, applicato con un vettore A[0...n − 1] e i = 0, j = n − 1 e A[−1] = A[n] = −∞, garantisce la presenza di un picco. In più la dimostrazione del teorema suggerisce un modo di cercare un picco. Nella dimostrazione si sceglie sempre una posizione arbitraria nel segmento considerato. Come conviene scegliere la posizione? Con qk = b ik−1 +j 2 k−1 c (siano i0 =i e j0 = j ) in ogni giro si dimezza il segmento considerato. Ne segue un algoritmo di tipo Divide et Impera: 1: Peak-Find-DI(A[i...j]).i≤j 2: q ← b(i + j)/2c 3: if A[q − 1] ≤ A[q] ≥ A[q + 1] then 4: return p 5: else. A[q − 1] > A[q] ∨ A[q] < A[q + 1] 6: if A[q − 1] > A[q] then 7: return Peak-Find-DI(A[i...q − 1]) 8: else 9: return Peak-Find-DI(A[q + 1...j]) 10: end if 11: end if La chiamata Peak-Find-DI(A[0...n − 1]) trova il picco nel intero vettore. (Cosa succede se la scelta è qk = ik−1 ? Cosa succede se la scelta è qk = jk−1 ? Simulare l'algoritmo col vettore A = |1, 2, 6, 6, 5, 3, 3, 3, 7, 4, 5|.) Quanti confronti fa l'algoritmo precedente? Per semplicità contiamo solo quante volte viene eettuato il confronto A[q − 1] ≤ A[q] ≥ A[q + 1] e lo consideriamo come singolo confronto. Assumiamo di avere n = 2k per qualche intero k e consideriamo il caso peggiore, cioè in ogni giro il vettore si dimezza esattamente e l'algoritmo termina quando viene eettuata la chiamata con i = j. Il numero di confronti in caso di un vettore di n elementi è   1 se n=1 T (n) = n
T +1 se n>1  2 n
T (n) = T 2 +1 n
= T 4 +1+ 1 n
= T 8 +1+ 1+1 n
= T 23 + 3 n
= T 2k +k per 1 ≤ k ≤ log2 n = T (1) + log2 n utilizzando k = log2 n = 1 + log2 n Quindi, nel caso peggiore, il numero di confronti utilizzando Peak-Find-DI è proporzionale a log2 n mentre con Peak-Find-Left è n − 1. Per esempio, con n = 220 = 1048576, log2 n = 20 mentre n − 1 = 1048575. 4