Problema Computazionale PDF

 Problema Computazionale Un problema computazionale è costituito da un insieme I di ISTANZE (i possibili input) un insieme S di SOLUZIONI (i possibili output) una relazione Π che a ogni istanza i ∈ I associa una o più soluzioni s ∈ S. Oss. Π è un sottoinsieme...

 Problema Computazionale Un problema computazionale è costituito da un insieme I di ISTANZE (i possibili input) un insieme S di SOLUZIONI (i possibili output) una relazione Π che a ogni istanza i ∈ I associa una o più soluzioni s ∈ S. Oss. Π è un sottoinsieme del prodotto cartesiano I × S 3  Algoritmo e modello di calcolo Definizione Algoritmo: procedura computazionale ben definita che transforma un dato input in un output eseguendo una sequenza finita di passi elementari. L’algoritmo fa riferimento a un modello di calcolo, ovvero un’astrazione di computer che definisce l’insieme di passi elementari. 1 Modello di calcolo RAM (Random Access Machine) input, output, dati intermedi (e programma): in memoria passi elementari: operazioni primitive quali assegnamento, operazioni logiche, operazioni aritmetiche, indicizzazione di array, return di un valore da parte di un metodo, ecc. 1 Diverso da Random Access Memory! 6 Un algoritmo A risolve un problema computazionale Π ⊆ I × S se: 1 A riceve come input istanze i ∈ I 2 A produce come output soluzioni s ∈ S 3 Dato un input i ∈ I, A produce come output s ∈ S tale che (i, s) ∈ Π 7  Pseudocodice Per semplicità e facilità di analisi, descriviamo un algoritmo utilizzando uno pseudocodice strutturato come segue: Algoritmo nome (parametri) Input: breve descrizione dell’istanza di input Output: breve descrizione della soluzione restituita in output descrizione chiara dell’algoritmo tramite costrutti di linguaggi di programmazione e, se utile ai fini della chiarezza, anche tramite linguaggio naturale, dalla quale sia facilmente determinabile la sequenza di passi elementari eseguita per ogni dato input. USARE SEMPRE QUESTA STRUTTURA PER LO PSEUDOCODICE!! Per maggiori dettagli fare riferimento alla dispesa sulla Specifica di Algoritmi in Pseudocodine, disponibile sul Moodle del corso. 8  Taglia di una istanza L’analisi di un algoritmo (ad es., la determinazione della sua complessità) viene solitamente fatta partizionando le istanze in gruppi in base alla loro taglia (size), in modo che le istanze di un gruppo siano tra loro confrontabili. La taglia di un’istanza è espressa da uno o più valori che ne caratterizzano la grandezza. 12  Strutture dati Le strutture dati sono usate dagli algoritmi per organizzare e accedere in modo sistematico ai dati di input e ai dati generati durante l’esecuzione. Definizione Una struttura dati è una collezione di oggetti corredata di metodi di accesso e/o modifica. Due livelli di astrazione: 1 Livello logico: specifica l’organizzazione logica degli oggetti della collezione, e la relazione input-output di ciascun metodo (a questo livello si parla di Abstract Data Type o ADT) 2 Livello fisico: specifica il layout fisico dei dati e la realizzazione dei metodi tramite algoritmi. Ad esempio in Java: Livello logico: (gerarchia di) interfacce Livello fisico: (gerarchia di) classi. 14  Analisi degli algoritmi L’analisi di un algoritmo A mira a studiarne l’efficienza e l’efficacia. In particolare, essa può valutare i seguenti aspetti: Complessità tempo spazio Correttezza terminazione soluzione del problema computazionale Noi ci concentreremo su: 1 complessità: tempo 2 correttezza: soluzione del problema computazionale 16  Complessità in Tempo Obiettivo: stimare il tempo di esecuzione (running time) di un algoritmo per valutarne l’efficienza e poterlo confrontare con altri algoritmi per lo stesso problema computazionale. Osservazioni Il tempo di esecuzione (di un programma) dipende da istanza di input: di solito cresce con la taglia, ma a parità di taglia, input diversi possono avere tempi anche molto diversi (e.g., InsertionSort) ambiente HW (e.g., processore, sistema di memoria, ecc.) ambiente SW (e.g., linguaggio di programmazione, OS, compilatore, etc.) Come possiamo studiare la complessità in tempo? 17 Studio Sperimentale In Java: uso System.currentTimeMillis() ritorna il numero (long) di millisecondi trascorsi da un evento di riferimento (la mezzanotte del 1/1/1970) invocazione: prima e dopo esecuzione algoritmo ⇒ differenza Buona idea? OK ma con dei limiti non può considerare tutti gli input richiede l’implementazione di un algoritmo con un programma molto lavoro! confronto tra algoritmi: difficile (implementazione ha un ruolo) HW/SW dependent 18 Requisiti per l’analisi della complessità in tempo 1 deve considerare tutti gli input 2 deve permettere di confrontare algoritmi (senza necessariamente determinare il tempo di esecuzione esatto) 3 deve essere eseguibile a partire da una specifica high level dell’algoritmo (⇒ pseudocodice) Approccio analisi al caso pessimo (worst-case) in funzione della taglia dell’istanza (req. 1,2) Altri tipi di analisi sono possibili: analisi al caso medio (average case), analisi probabilistica conteggio passi elementari nel modello RAM (req. 2,3) analisi asintotica (per semplificare il conteggio) 19 Sia A un algoritmo che risolve Π ⊆ I × S. Definizione La complessità (in tempo) al caso pessimo di A è una funzione tA (n) definita come il massimo numero di operazioni che A esegue per risolvere una istanza di taglia n. Terminologia: operazioni ≡ passi elementari del modello RAM. In altre parole, se chiamiamo tA,i il numero di operazioni eseguite da A per l’istanza i, abbiamo che tA (n) = max{tA,i : istanza i ∈ I di taglia n}. 20  Difficoltà nel calcolo di tA (n) Determinare tA (n) per ogni n è arduo, se non impossibile, perché: È difficile identificare l’istanza peggiore di taglia n. È difficile contare il max numero di operazioni richieste per risolvere tale istanza peggiore (il conteggio richiederebbe anche una specifica dettagliata dei possibili passi elementari del modello RAM). È necessario determinare esattamente tA (n)? No, per le seguenti ragioni: La scelta del set di passi elementari del modello RAM e, in pratica, gli instruction set delle architetture non sono tutti uguali. Il tempo di esecuzione, che la complessità vuole stimare, dipende da tanti fattori che è impossibile quantificare in modo preciso. ⇒ ci accontentiamo di limiti superiori e limiti inferiori a tA (n). 21  Esempio: arrayMax Algoritmo arrayMax(A) Input: array A[0 ÷ n − 1] di n ≥ 1 interi Output: max intero in A currMax ← A; for i ← 1 to n − 1 do if (currMax < A[i]) then currMax ← A[i]; return currMax Taglia dell’istanza: n (ragionevole) 22  Stima di tarrayMax (n) È facile vedere che per una qualsiasi istanza di taglia n: al di fuori del ciclo for arrayMax esegue un numero costante (rispetto a n) di operazioni. in ciascuna delle n − 1 iterazioni del ciclo for si esegue un numero costante di operazioni. ⇒ esistono costanti c1 , c2 , c3 , c4 > 0 tali che per ogni n tarrayMax (n) ≤ c1 n + c2 (limite superiore) tarrayMax (n) ≥ c3 n + c4 (limite inferiore) Dobbiamo stimare le costanti c1 , c2 , c3 , c4 ? No, per le stesse ragioni per cui non è necessario stimare esattamente la complessità 23  Analisi Asintotica Si ricorre quindi alla Analisi asintotica Si ignorano fattori moltiplicativi costanti (= non dipendenti dalla taglia dell’istanza) Si ignorano termini additivi non dominanti Nel caso di arrayMax possiamo affermare che tarrayMax (n) è al più proporzionale a n (limite superiore) tarrayMax (n) è almeno proporzionale a n (limite inferiore) Dalle due affermazioni consegue che: tarrayMax (n) è proporzionale a n (limite stretto) Per esprimere efficacemente affermazioni come quelle fatte sopra si usano gli ordini di grandezza: O (·), Ω (·), Θ (·), o(·). 24 Definizione f (n) ∈ Θ (g (n)) se f (n) ∈ O (g (n)) e f (n) ∈ Ω (g (n)), ovvero ∃c 0 , c 00 > 0 e n0 ≥ 1, costanti non dipendenti da n, tali che: c 0 g (n) ≤ f (n) ≤ c 00 g (n), ∀n ≥ n0 Applicando la definizione agli esempi dei lucidi precedenti otteniamo: f (n) = 3n + 4 ∈ Θ (n) f (n) = n + 2n2 ∈ Θ n2
f (n) = 2100 ∈ Θ (1) tarrayMax (n) ∈ Θ (n) 29 Definizione f (n) ∈ o (g (n)) se ∀c > 0 ∃n0 ≥ 1, con c e n0 costanti non dipendenti da n, tale che f (n) ≤ cg (n), ∀n ≥ n0 , ovvero limn→+∞ f (n)/g (n) = 0. N.B. n0 è in genere una funzione di c. Esempi f (n) = 100n per n ≥ 1 ⇒ f (n) ∈ o n2
(dato che f (n)/n2 → 0 per n → +∞) f (n) = 3n/(log2 n) per n ≥ 1 ⇒ f (n) ∈ o (n) (dato che f (n)/n → 0 per n → +∞) 30  Proprietà degli ordini di grandezza max{f (n), g (n)} ∈ Θ (f (n) + g (n)), per ogni coppia f (n), g (n) → N ∪ {0} → R+ ∪ {0}. Pk i k
i=0 ai n ∈ Θ n , se ak > 0, k, ai costanti, e k ≥ 0.
Ad es.: (n + 1)5 ∈ Θ n5 logb n ∈ Θ (loga n), se a, b > 1 sono costanti. Oss.: grazie a questa proprietà, la base dei logaritmi, se costante, si omette negli ordini di grandezza (a meno che il logaritmo non sia all’esponente). nk ∈ o (an ), se k > 0, a > 1 sono costanti. (logb n)k ∈ o nh se b, k, h sono costanti, con b > 1 e h, k > 0.
La verifica delle proprietà è lasciata come esercizio 31  Strumenti matematici (Parte bassa) ∀x ∈ 0 costante esponenziale: Ω (an ), a > 1 costante polilogaritmica: Θ ((log n)c ), c > 0 costante 36 Esempio: Prefix Averages ([GTG14 ] pp. 164-165) Si consideri il seguente problema computazionale: dato un array di n interi X [0... n − 1] calcolare un array A[0... n − 1] dove   i X 1 A[i] =  X [j] , per 0 ≤ i < n. i +1 j=0 Vedremo adesso 2 algoritmi: 1 banale e inefficiente, e 1 più furbo ed efficiente. Per entrambi gli algoritmi vale la seguente specifica di input-output: Input: X [0... n − 1] array di n interi Pi Output: A[0... n − 1]: A[i] = ( j=0 X [j])/(i + 1) per 0 ≤ i < n 37 Algoritmo prefixAverages1 for i ← 0 to n − 1 do a ← 0; for j ← 0 to i do a ← a + X [j]; a A[i] ← i+1 ; return A Complessità: 38 Algoritmo prefixAverages2 s ← 0; for i ← 0 to n − 1 do s ← s + X [i]; s A[i] ← i+1 ; return A Complessità: 39  Regola di buon senso Complessità polinomiale (o migliore) ⇒ algoritmo efficiente Complessità esponenziale ⇒ algoritmo inefficiente Giustificazione ≈[GTG14,4.3.2] Supponiamo che la complessità tA (n) sia espressa in ns, e definiamonτ come la max taglia eseguibile in tempo τ. Per ottenere nτ , risolviamo tA (nτ ) = τ rispetto a nτ. Ecco alcuni esempi: tA (nτ ) = log2 nτ tA (nτ ) = nτ tA (nτ ) = nτ2 tA (nτ ) = 2nτ 44  Esempio: sicurezza in internet Crittografia a chiave pubblica message&m Alice& Bob& Bob: chiave privata k1 , chiave pubblica k2 Alice invia a Bob un messaggio m cifrato con k2 Bob decifra il messaggio ricevuto da Alice con k1 47  Algoritmo RSA (Rivest, Shamir, Adleman, 1977) √  N = p · q, dove p, q numeri primi grandi: p, q ∈ Θ N Chiave pubblica: N, e (e < N funzione di p, q) Chiave privata: N, d (d < N funzione di e, p, q) messaggio m: cifratura: m → (me ) mod N = m̄ decifratura: m̄ → m̄d mod N = m
N.B.: pur conoscendo N ed e, per conoscere d, necessario per la decifratura, mi serve conoscere p e q Ottenere p e q da N è difficile!. Taglia dell’istanza = numero di bit di N = blog2 Nc + 1 = n 48  Algoritmo banale √ for p ← 2 to b Nc do if (N mod p = 0) then return {p, N/p}; √  √  n
Se p, q ∈ Θ N ⇒ la complessità è Θ N = Θ 22. Esempio numerico n n = 1024 ⇒ 2 2 = 2512 ≥ 10154 Sul computer più potente al mondo (≈ 1018 flop/sec) l’algoritmo banale richiederebbe circa 10154 /1018 = 10136 sec 1 anno ha ≤ 108 sec ⇒ > 10128 anni di calcolo... Osservazione Esistono algoritmi più efficienti ma sempre con complessità esponenziale. 2009: risolto problema con n = 768 (2 anni di calcolo, centinaia di macchine). Non si può escludere l’esistenza di un algoritmo efficiente. 49  Efficienza asintotica degli algoritmi A,B che risolvono Π tA (n), tB (n) complessità di A, B (rispettivamente) al caso pessimo tA (n) ∈ o (tB (n)) ⇒ A è “asintoticamente più efficiente” di B. N.B.: n0 potrebbe essere molto grande!! 51  Caveat sull’analisi asintotica al caso pessimo Caveat 1: il caso pessimo potrebbe essere costituito solo da istanze patologiche mentre per tutte le istanze di interesse la complessità potrebbe essere asintoticamente migliore Soluzioni restringere con opportune assunzioni il dominio delle istanze per mantenere quelle di interesse ed escludere quelle patologiche analisi del caso medio o aggirare il caso pessimo probabilisticamente. 52  Caveat sull’analisi asintotica al caso pessimo Caveat 2: Le costanti trascurate potrebbero avere un impatto cruciale in pratica. Esempio tA (n) = 10100 n = Θ (n) (10100 =“costante”) tB (n) = n2 ⇒ tA (n) = o (tB (n)) ⇒ A è più efficiente di B in realtà: tA (n) < tB (n) solo se n > 10100 N.B.: 10100 >> numero di atomi dell’universo... Esempio tA (n) = 400 log2 n tB (n) = log22 n tA (n) < tB (n) ⇒ log2 n > 400 ⇒ n > 2400 ≥ 10100... Soluzioni: dare una stima delle costanti nel caso siano molto elevate. 53  Tecniche di dimostrazione Esempio/Controesempio/Assurdo Illustriamo con degli esempi tre tecniche di dimostrazione, che sono utili nell’analisi di algoritmi. Proprietà: L’algoritmo A ha complessità tA (n) ∈ Ω n2.
Dimostrazione (tramite esempio): è sufficiente far vedere che, per ogni n abbastanza grande, esiste un’istanza che richiede ≥ cn2 operazioni con c costante. Proprietà: l’affermazione “2i − 1 è primo ∀i ≥ 1” è falsa. Dimostrazione (tramite controesempio): 24 − 1 = 15, non primo. Proprietà: dati due interi a, b ≥ 1, se ab dispari, allora sia a che b sono dispari. Dimostrazione (per assurdo): se almeno uno tra a o b fosse pari (negazione della tesi), ad es. a, allora a = 2c per un qualche intero c ≥ 1, e quindi ab = 2cb sarebbe pari, contraddicendo l’ipotesi. 54 Induzione Per provare che una proprietà Q(n) è vera ∀n ≥ n0 (n0 = 1 in [GTG14]) Si procede cosı̀: scegli opportunamente un intero k ≥ 0 base: dimostra Q(n0 ), Q(n0 + 1),... , Q(n0 + k) passo induttivo: si fissa n ≥ n0 + k arbitrario e si dimostra che Q(m) vera ∀m : n0 ≤ m ≤ n ⇒ Q(n + 1) vera. Osservazioni: “Q(m) vera ∀m : n0 ≤ m ≤ n” è chiamata ipotesi induttiva la dimostrazione deve valere per ogni n ≥ n0 + k di solito (ma non sempre) k = 0 55  Correttezza Terminazione Per provare la terminazione è necessari assicurarsi che i cicli (inclusi i GOTO) e l’eventuale ricorsione abbiano termine. Soluzione del problema computazionale Approccio generale: Identificare lo stato iniziale dell’algoritmo e quello finale che esso deve raggiungere. Decomporre A in segmenti e definire per ogni segmento lo stato in cui l’algoritmo si deve trovare al termine del segmento (checkpoint). Dimostrare che a partire dallo stato iniziale si raggiungono in successione gli stati specificati per la fine di ogni segmento. In particolare, lo stato che deve valere alla fine dell’ultimo segmento deve coincidere (o implicare) lo stato finale desiderato. Segmenti notevoli: cicli (for, while, repeat-until) 62  Analisi di cicli Osservazione: i cicli sono i segmenti più difficili da analizzare (perché definiscono implicitamente molto operazioni) ma, insieme alla ricorsione, costituiscono gli strumenti essenziali per la scrittura di algoritmi/programmi interessanti. Correttezza di un ciclo (for, while, repeat-until...): provare la correttezza di un ciclo consiste nel dimostrare che al termine della sua esecuzione vale una certa proprietà L, che rappresenta uno stato. A tale fine, si fa uso di un INVARIANTE Definizione Un invariante per un ciclo è una proprietà espressa in funzione delle variabili usate nel ciclo, che descrive lo stato in cui si trova l’esecuzione alla fine di una generica iterazione del ciclo. 64  Correttezza di un ciclo tramite invariante Per dimostrare che alla fine del ciclo vale una certa proprietà L, si individua un opportuno invariante e si dimostra che: 1 Esso vale all’inizio del ciclo (subito prima che il ciclo inizi). 2 Esso vale alla fine di ciascuna iterazione. Si dimostra in modo induttivo provando che se vale alla fine di una generica iterazione, vale alla fine della successiva. 3 Valendo alla fine dell’ultima iterazione implica la proprietà L. Terminologia: l’esecuzione di un ciclo consiste di ≥ 0 iterazioni delle istruzioni in esso contenute (corpo del ciclo). Ad esempio: for i ← 1 to n do {corpo del ciclo} è un ciclo che esegue sempre n iterazioni. 65  Ricorsione Algoritmo Ricorsivo: algoritmo che invoca se stesso (su istanze sempre più piccole) sfruttando la nozione di induzione. La soluzione di una istanza di taglia n è ottenuta: direttamente: se n = n0 , n0 + 1,... , n0 + k (casi base) ricorrendo a soluzione di ≥ 1 istanze di taglia < n: se n > n0 + k Ad esempio, si consideri l’algoritmo MergeSort per ordinare una sequenza S di n elementi. Se n = 1 l’algoritmo ordina S direttamente restituendola non modificata (n0 = 1, k = 0), altrimenti invoca ricorsivamente se stesso per ordinare le due metà (di taglia ≤ dn/2e < n), poi fondendole una volta ordinate. 74  Esempi Algoritmo linearSum(A,n) Input: array A, intero n ≥ 1 Pn−1 Output: i=0 A[i] if (n = 1) then return A; else return linearSum(A,n − 1)+A[n − 1]; 75 Algoritmo reverseArray(A,i,j) Input: array A, indici i, j ≥ 0 Output: array A con gli elementi in A[i ÷ j] ribaltati if (i < j) then swap(A[i],A[j]); reverseArray(A,i + 1,j − 1) return 76  Esecuzione di un algoritmo ricorsivo Albero della ricorsione All’esecuzione di un algoritmo ricorsivo su una data istanza è associato un albero della ricorsione tale che: Ogni nodo corrisponde a un’invocazione ricorsiva distinta fatta durante l’esecuzione dell’algoritmo. La radice dell’albero corrisponde alla prima invocazione, e i figli di un nodo x sono associati alle invocazioni ricorsive fatte direttamente dall’invocazione corrispondente a x. Le foglie dell’albero rappresentano casi base. N.B. [GTG14] usa il termine recursion trace per denotare l’albero della ricorsione. 77  Esecuzione di un algoritmo ricorsivo Nell’esecuzione di un programma (in Java) entrano di solito in gioco due spazi di memoria: STACK: spazio destinato a memorizzare variabili locali ai metodi e riferimenti a oggetti. Per ogni invocazione di un metodo viene inserito un record di attivazione (RA) contenente variabili e riferimenti a oggetti relativi a quella invocazione. (In inglese si usa il termine activation record o activation frame.) Un RA viene eliminato quando l’invocazione di metodo corrispondete finisce l’esecuzione. I RA sono inseriti/eliminati con politica LIFO, e in ogni istante possono essere acceduti i dati relativi all’ultimo RA inserito ma non quelli di altri RA. HEAP: spazio destinato a memorizzare gli oggetti. 80  Algoritmi ricorsivi vs algoritmi iterativi Algoritmo ricorsivo: algoritmo che invoca se stesso su istanze più piccole Algoritmo iterativo: algoritmo non-ricorsivo Osservazione: il termine iterativo è usato per evidenziare che (tranne casi banali) un algoritmo non-ricorsivo fa uso di cicli per poter elaborare istanze di qualsiasi taglia. Mentre i cicli sono essenziali in un algoritmo iterativo, un algoritmo ricorsivo può non avere cicli (ad es. linearSum, reverseArray) ma può anche averli (ad es., MergeSort). 83  Complessità di algoritmi ricorsivi La complessità di un algoritmo ricorsivo A può essere stimata tramite l’Albero della Ricorsione. Consideriamo l’albero associato all’esecuzione di A su un’istanza i di taglia n: A ogni nodo è attribuito un costo pari al numero di operazioni eseguite dalla invocazione corrispondente a quel nodo, escluse quelle fatte dalle invocazioni ricorsive al suo interno. Il numero totale di operazioni eseguite da A per risolvere i si ottiene sommando i costi associati a tutti i nodi. Per ottenere un upper bound a tA (n), si ricava una stima per eccesso del numero totale di operazioni che valga per tutte le istanze i di taglia n, mentre per ottenere un lower bound a tA (n) si identifica un’istanza particolare o si fa una stima inferiore che va bene per tutte le istanze. 84  Esempio Algoritmo linearSum(A,n) Input: array A, intero n ≥ 1 Pn−1 Output: i=0 A[i] if (n = 1) then return A; else return linearSum(A,n − 1)+A[n − 1]; Complessità: 85  Calcolo efficiente di potenze Problema: dato x ∈ R e n ≥ 0 intero, calcolare p(x, n) = x n Osservazione chiave  1 
2 n=0 p(x, n) = x · p x, n−1 2 n > 0 dispari  2 p x, n2
n > 0 pari  Algoritmo power(x,n) Input: x ∈ R e n ≥ 0 intero Output: p(x, n) if (n = 0) then return 1; if (n è dispari) then y ←power(x,(n − 1)/2); return x · y · y ; else y ←power(x,n/2); return y · y 87  Complessità di power(x,n) Supponiamo n > 1 (consideriamo n come taglia dell’istanza) Alla i-esima chiamata ricorsiva l’algoritmo viene invocato per un esponente ni ≤ n/2i. Di conseguenza, l’albero della ricorsione avrà O (log n) nodi. Ogni invocazione di power esegue Θ (1) operazioni, esclusa l’eventuale chiamata ricorsiva. Quindi il costo associato a ciascun nodo è Θ (1). ⇒ tpower (n) ∈ O (log n) 88  Applicazione di power al calcolo di F (n) Il seguente √ algoritmo efficiente sfrutta la formula F (n) = (1/ 5)(Φn − Φ̂n ) e l’algoritmo power visto in precedenza: Algoritmo powerFib(n) Input: intero n ≥ 0 Output: F√ (n)
Φ ← (1 + 5)/2 ; √
Φ̂ ← (1 − 5)/2 ; √ return (power(Φ, n) − power(Φ̂, n))/ 5 Da quanto provato per power, otteniamo che la complessità di powerFib è O (log n). 89  Correttezza di algoritmi ricorsivi Per provare la correttezza (o una qualsiasi proprietà) di un algoritmo ricorsivo A si ricorre all’induzione. Sia n la taglia dell’istanza: Si dimostra la correttezza per i casi base n ∈ [n0 , n0 + k] Supponendo che A risolva correttamente tutte le istanze di taglia m ∈ [n0 , n], per un qualche n ≥ n0 + k, si dimostra che esso risolve correttamente tutte le istanze di taglia n + 1 90 Esempio: correttezza di linearSum(A, n) per n ≥ 1 91 Programma stand-alone Compilazione: javac MyProgram.java Crea un bytecode MyProgram.class eseguibile sulla Java Virtual Machine (JVM) Esecuzione: java MyProgram Oss. Richiede che la directory corrente sia nel CLASSPATH. Altrimenti usiamo: java –cp. MyProgram In alternativa si può usare un Integrated Development Environment (IDE), ad es. IntelliJ IDEA, Eclipse, JBuilder Dati e Algoritmi Andrea Pietracaprina 3  Caratteristiche di Java e dell’approccio Object-Oriented 1. Modularità 2. Astrazione e Incapsulamento (Information Hiding) 3. Ereditarietà (Inheritance) Dati e Algoritmi Andrea Pietracaprina 4 Caratteristiche Java e approccio O.O. Modularità: Applicazione  insieme di oggetti interagenti Un oggetto è un’istanza di una classe che definisce  Variabili di istanza (instance variables o fields)  Metodi (methods) La classe rappresenta il “tipo” dell’oggetto Integer i = new Integer(5); Definizione della Creazione di un oggetto variabile i di tipo Integer di tipo Integer Dati e Algoritmi Andrea Pietracaprina 5 Caratteristiche Java e approccio O.O. Astrazione e Incapsulamento (Information Hiding): Si astrae la specifica delle funzionalità, separandola dalla loro implementazione Uso delle funzionalità solo in base alla specifica L’implementazione delle funzionalità è nascosta Gli errori sono più confinati (-> robustezza) Possibilità di cambiare l’implementazione senza cambiare la specifica (-> adattabilità) Nel caso delle strutture dati, questo approccio dà origine alla nozione di Abstract Data Type (ADT), che in Java si realizza tramite l’utilizo di interfacce, classi e classi astratte. Dati e Algoritmi Andrea Pietracaprina 6 Caratteristiche Java e approccio O.O. Interfaccia: dichiarazioni di metodi senza corpo e di costanti. Classe: definzione di costanti/variabili e metodi con corpo Classe astratta: via di mezzo tra interfaccia e classe (alcuni metodi senza corpo) A public interface A { public int a1(); public boolean a2(); } implements public class X implements A { public int a1() {…} public boolean a2() {…} X public void b() {…} Ad es., } java.lang.String A var1 = new A(); NO! implements A var1 = new X(); OK! java.lang.Comparable Dati e Algoritmi Andrea Pietracaprina 7 Caratteristiche Java e approccio O.O. Ereditarietà (Inheritance): Si importano in una classe le caratteristiche di un’altra classe aggiungendone di nuove e/o specializzandone alcune In Java: extends (subclass superclass) public class S { public void a() {…} S Superclass public void b() {…} public int c() {…} extends } public class T extends S { T Subclass float y; // added public void a() {…} // specialized Ogni classe estende public boolean d() {…} // added implicitamente } java.lang.Object Dati e Algoritmi Andrea Pietracaprina 8 Caratteristiche Java e approccio O.O. Ereditarietà multipla per interfacce (non per classi!) public interface A {…} public interface B {…} A B public interface C extends A, B extends extends {…} C N.B. A e B non possono contenere metodi con la stessa signature public class D implements A, B { // deve implementare tutti i metodi di A e B } public class D implements C { // deve implementare tutti i metodi di A e B // e quelli (eventuali) aggiuntivi di C } Dati e Algoritmi Andrea Pietracaprina 9  Programmazione Generica (generics) È un tipo di polimorfismo, introdotto da Java SE 5. Permette l’uso di variabili di tipo nella definizione di classi, interfacce e metodi. Si parla in questo caso di classi/interfacce generiche e metodi generici. Nel creare un’istanza di una classe generica si specifica il tipo (actual type) da sostituire con la variabile di tipo. L’actual type non può essere un tipo primitivo (ad es., int) ma deve essere una classe che estende Object Nell’invocazione di un metodo generico la sostituzione della variabile di tipo con un actual type è fatta automaticamente in base ai parametri passati. L’uso delle classi/interfacce generiche evita il ricorso a parametri di tipo “Object” e l’uso frequente di cast. Dati e Algoritmi Andrea Pietracaprina 10 Programmazione generica Esempi: interfacce e classi generiche public interface MyInterface { public int size(); public boolean method1 (E var1); public E method2 (); } public class MyClass implements MyInterface{ E var; public int size() { …. }; public boolean method1 (E var1) { …. }; public E method2 () { …. }; public E method3 (float var2) { …. }; } MyInterface x = new MyClass(); public class MyClass1 {…} // E può essere sostitutito solo da oggetti di tipo che estende/implementa la classe/interfaccia S Dati e Algoritmi Andrea Pietracaprina 11 Lista LISTA (LIST): collezione di elementi organizzati secondo un ordine lineare tale per cui è identificabile il primo elemento, il secondo, … , e l’ultimo. Lista index-based: un elemento può essere acceduto tramite un indice intero che indica il numero di elementi che lo precedono Lista position-based: ogni elemento è contenuto in un contenitore detto nodo (position) index = 1 X Y Z elemento position Dati e Algoritmi Andrea Pietracaprina 13 Lista index-based Lista index-based public interface List { public int size(); public boolean isEmpty(); public void add(int i, E e); public E get(int i) public E set(int i, E e) public E remove(int i) } Dati e Algoritmi Andrea Pietracaprina 14 Lista position-based Lista position-based public interface Position { public E getElement(); } public interface PositionalList { public int size(); public boolean isEmpty(); public Position first(); public Position last(); …. Dati e Algoritmi Andrea Pietracaprina 15 Lista position-based …. public Position after(Position p); public Position before(Position p); public void addFirst(E e); public void addLast(E e); public void addAfter(Position p, E e); public void addBefore(Position p, E e); public E remove(Position p); public E set(Position p, E e); } Dati e Algoritmi Andrea Pietracaprina 16 Implementazioni della lista IMPLEMENTAZIONI DELLA LISTA Lista index-based: tramite array. I metodi possono essere implementati con complessità O(1) tranne add e remove che richiedono complessità O(n) (n=numero di elementi nella lista) Osservazione: nel caso in cui l’array sia pieno, l’inserimento di un elemento x è implementato creando un nuovo array di capacità maggiore, trasferendo tutte le entry dal vecchio al nuovo array, e inserendo l’elemento x nel nuovo array. Dati e Algoritmi Andrea Pietracaprina 17 Implementazioni della lista Lista position-based: tramite doubly-linked list.  Ogni nodo diventa un oggetto a sé con variabili di istanza che «puntano» a predecessore e successore  Inizio e fine lista delimitati da nodi sentinella  metodi possono essere implementati con complessità O(1) ma la lista può essere scandita solo sequenzialmente Osservazione: è possibile implementare una lista index-based tramite doubly-linked list, o una lista position-based tramite array ma con scarsi vantaggi. Dati e Algoritmi Andrea Pietracaprina 18 Pila PILA (STACK): collezione di elementi inseriti e rimossi in base al principio Last-In First-Out (LIFO) public interface Stack { public int size(); public boolean isEmpty(); public void push(E e); public E top(); public E pop(); } Dati e Algoritmi Andrea Pietracaprina 19 Coda CODA (QUEUE): collezione di elementi inseriti e rimossi in base al principio First-In First-Out (FIFO) public interface Queue { public int size(); public boolean isEmpty(); public void enqueue(E e); public E first(); public E dequeue(); } Dati e Algoritmi Andrea Pietracaprina 20 Implementazioni della lista IMPLEMENTAZIONI DELLA PILA e DELLA CODA Entrambe le strutture dati possono essere implementate tramite doubly-linked list. PILA: inserimento (push) e rimozione (pop) in testa alla lista. CODA: inserimento (enqueue) in coda e rimozione (dequeue) in testa alla lista Tutti i metodi possono essere implementati con complessità O(1) ma, a differenza della lista, non si ha accesso a elementi intermedi a meno di non rimuovere quelli che li precedono nell’ordine di accesso Oss.: è possibile usare anche una singly-linked list. Dati e Algoritmi Andrea Pietracaprina 21 Collection framework di Java Collection Framework di Java Collection: termine generico per indicare una struttura dati. Collection framework di Java: architettura unificata di strutture dati e algoritmi implementato nel package java.util. Contiene:  Interfacce di varie collection  Classi che implementano le interfacce  Algoritmi polimorfi per operare su collection (metodi statici della classe Collections), come ad es. il sorting.  Ampio uso della programmazione generica Dati e Algoritmi Andrea Pietracaprina 22 Collection framework di Java Il package java.util contiene diverse implementazioni di Liste, Pile e Code. Tra esse si segnalano le seguenti. Lista Interfaccia: List Classe ArrayList: implementazione index-based Classe LinkedList: implementazione sia index-based che position-based. Tuttavia l’implementazione position-based non utilizza esplicitamente il concetto di position ma si basa sull’uso di iteratori. Dati e Algoritmi Andrea Pietracaprina 23 Collection framework di Java Pila e Coda Interfaccia unificata: Deque (Double-ended queue) Classe LinkedList: implementazione unificata di Pila e Coda (e Lista) Classe Stack: implementazione della Pila basata su Vector. Si consiglia tuttavia l’uso di classi, come LinkedList, che implemetano l’interfaccia Deque che è più completa. Oss.: I nomi di alcuni metodi differiscono da quelli riportati nei lucidi precedenti che seguono il libro di testo. Dati e Algoritmi Andrea Pietracaprina 24 Nozione (informale) di Albero Collezione di nodi caratterizzata una struttura gerarchica che si dipana da una nodo radice tramite relazioni di tipo padre-figlio. Osservazioni: le relazioni padre-figlio costituiscono un insieme di collegamenti minimali che inducono un legame (connessione) tra tutti i nodi; Una lista è un caso estremo di albero con una struttura gerarchica lineare. 3  Campi Applicativi 1 strutture dati: mappe; priority queue 2 esplorazione risorse: filesystem; siti di e-commerce; 3 sistemi distribuiti e reti di comunicazione: sincronizzazione, broadcast, gathering 4 analisi di algoritmi: albero della ricorsione 5 classificazione: alberi di decisione 6 compressione di dati (codici di Huffman) 7 biologia computazionale: alberi filogenetici 4  Alberi (Tree) Definizione di albero radicato (rooted tree) Un albero radicato T è una collezione di nodi che, se non è vuota, soddisfa le seguenti proprietà: ∃ un nodo speciale r ∈ T (r =. radice) ∀v ∈ T , v = 6 r : ∃!u ∈ T : u è padre di v (v è figlio di u) ∀v ∈ T , v =6 r : risalendo di padre in padre si arriva a r (= ogni nodo è discendente dalla radice.) 5 Nota Nel libro la terza condizione: ∀v ∈ T , v 6= r : risalendo di padre in padre si arriva a r manca. Senza di questa, la seguente collezione r" u" v" con u padre di v e v padre di u sarebbe un albero... che ha poco senso. Questa collezione piuttosto è una foresta di alberi. 6  Alberi: altre definizioni Antenati x è antenato di y se x = y oppure x è antenato del padre di y Discendenti x è discendente di y se y è antenato di x Nodi interni Nodi con ≥ 1 figli 7  Alberi: altre definizioni Nodi esterni (= foglie) Nodi senza figli. Sottoalbero con radice v Tv = albero formato da tutti i discendenti di v Albero ordinato T è un albero ordinato se per ogni nodo interno v ∈ T è definito un ordinamento lineare tra i figli u1 , u2 ,... , uk di v. 9  Definizione Ricorsiva Definizione ricorsiva di albero radicato Un albero radicato T è una collezione di nodi che, se non è vuota, risulta partizionata in questo modo: T = {r } ∪ T1 ∪ T2 ∪ · · · ∪ Tk , per un qualche k ≥ 0, dove: r è radice con figli u1 , u2 ,... , uk ; ∀i, 1 ≤ i ≤ k: Ti è un albero non vuoto con radice ui (⇒ Ti ≡ Tui ). r" u1" u2" …" uk" T1" T2" Tk" Oss.: le 2 definizioni di albero radicato (ricorsiva e non) sono equivalenti. 11  Alberi: ancora definizioni Profondità di un nodo v in un albero T : depthT (v ) Due definizioni alternative: Def.1: depthT (v ) = |antenati(v )| − 1; Def.2: se v = r radice ⇒ depthT (v ) = 0 altrimenti depthT (v ) = 1 + depthT (padre(v )) Livello i Insieme dei nodi a profondità i (∀i ≥ 0) Altezza di un nodo v in un albero T : heightT (v ) se v è foglia ⇒ heightT (v ) = 0 altrimenti heightT (v ) = 1 + maxw :w figlio di v (heightT (w )) 12  Interfacce Iterator e Iterable Prima di definire l’interfaccia Tree definiamo due interfacce: Iterator: un “cursore” che permette di enumerare (scan) gli elementi di una collezione; Iterable: una collezione che rende disponibile un iteratore ai suoi elementi. Si veda [GTG14, Paragrafo 7.4] per maggiori dettagli. public interface Iterator { boolean hasNext(); E next(); } public interface Iterable { Iterator iterator() } 20  Interfaccia Tree public interface Tree extends Iterable { int size(); boolean isEmpty(); Position root(); Position parent(Position p); Iterable children(Position p); int numChildren(Position p); ···· 22  ···· boolean isInternal(Position p); boolean isExternal(Position p); boolean isRoot(Position p); Iterator iterator(); Iterable positions(); } Osservazioni: iterator() deriva dal fatto che Tree estende Iterable Assumiamo complessità Θ (1) per tutti i metodi, tranne children iterator e positions, e che sia possibile enumerare i figli di un nodo (tramite children) in tempo proporzionale al loro numero 23  Calcolo della profondità di un nodo (Algoritmo ricorsivo) Algoritmo: depth(v ) Input: v ∈ T Output: profondità di v in T if (T.isRoot(v )) then return 0; else return 1+depth(T.parent(v )); Osservazione Come in [GTG14], definiamo gli algoritmi di base per gli alberi come metodi di una classe astratta che implementa l’interfaccia Tree, non specificando l’albero T come parametro in quanto esso è associato implicitamente all’istanza (this) da cui si invoca il metodo. 24  Visite di Alberi Visita di un albero T Scansione sistematica tutti i nodi di T che permette di eseguire una qualche operazione (visita) ad ogni nodo. Rappresentano un design pattern algoritmico che può essere istanziato per il calcolo di valori e/o per impostazione opportune variabili associate ai nodi. Per alberi generali studiamo le seguenti visite: Preorder: visita prima il padre e poi (ricorsivamente) i sottoalberi radicati nei figli. In questo modo le operazioni svolte per un nodo possono dipendere da quelle svolte per i suoi antenati. Postorder: visita prima (ricorsivamente) i sottoalberi radicati nei figli, poi il padre. In questo modo le operazioni svolte per un nodo possono dipendere da quelle svolte per i suoi discendenti. 37  Visita in Preorder: pattern algoritmico Algoritmo preorder(v ) Esempio Input: nodo v ∈ T Output: visita di tutti i nodi di Tv A visita v ; foreach w ∈ T.children(v ) do B C D preorder(w ) E F G Assumendo che children() Chiamata iniziale per vistare T A(B(E(F(C(D(G( esamini i figli da sx → dx, preorder(T.root()) l’ordine della visita in preorder è 38  Visita in Postorder: pattern algoritmico Algoritmo postorder(v ) Esempio Input: nodo v ∈ T Output: visita di tutti i nodi di Tv A foreach w ∈ T.children(v ) do postorder(w ) B C D visita v ; E F G Chiamata iniziale per vistare T Assumendo che children() A(B(E(F(C(D(G( postorder(T.root()) esamini i figli da sx → dx, l’ordine della visita in preorder è 39 Definizione Sia T albero ordinato e siano u, v ∈ T due nodi allo stesso livello. Diciamo che u è a sinistra di v (⇒ v è a destra di u) se u viene prima di v nella visita in preorder. Osservazione La definizione è coerente con il modo di disegnare gli alberi. 40 Quale visita è opportuno utilizzare per stampare l’indice di un libro, rappresentato tramite il seguente albero? 41 La visita in preorder! Infatti, la sequenza di visita è Book: Chapter1, Section 1.1., Section 1.2, Section 1.2.1, Section 1.2.2, Chapter 2, Section 2.1, Section 2.2, Section 2.2.1, Section 2.2.2 Esempio analogo: stampa della struttura di un file system come sequenza di cartelle e file. 42  Esempio di algoritmo basato sulla visita in preoder Vogliamo progettare un algoritmo allDepths che: dato un albero T calcoli la profondità di ogni nodo v ∈ T e la memorizzi in un campo v.depth. IDEA: adattare la visita in preorder, definendo la visita di un nodo v in questo modo: se v è radice: si imposta la profondità a 0 se v non è radice: si imposta la profondità a 1+la profondità del padre, che è già impostata, dato che il padre è stato già visitato. 43  Esempi di algoritmi basati sulla visita in postorder Esempio 1: l’algoritmo height è un esempio di visita in postorder dato che l’altezza di un nodo viene calcolata solo dopo aver calcolato quelle dei figli. Esempio 2: Si consideri un file system gerarchico la cui struttura è rappresentata da un albero T dove i nodi interni corrispondono alle cartelle e i nodi foglia ai file. Ogni nodo v ha un campo v.loc-size che memorizza lo spazio occupato dal nodo, escludendo quello dei discendenti. Progettare un algoritmo diskSpace che: dato un tale T calcoli, per ogni nodo v ∈ T , lo spazio aggregato occupato dai suoi discendenti e lo memorizzi in un campo v.aggr-size. 46 Osservazioni per la scrittura di algoritmi ricorsivi Un algoritmo ricorsivo può utilizzare sia variabili globali che sopravvivono a tutta l’esecuzione dell’algoritmo, e sia variabili locali alle singole invocazioni che rimangono in vita solo durante l’esecuzione della invocazione corrispondente. Gli eventuali valori restituiti dalle invocazioni ricorsive (se ce ne sono) devono essere “utilizzati” in qualche modo, altrimenti vanno perduti. 50 Osservazione: Per arietà di un albero si intende il massimo numero di figli di un nodo interno Definizione Un alberto binario T è un albero ordinato in cui ogni nodo interno ha ≤ 2 figli ogni nodo non radice è etichettato come figlio sinistro (sx) o destro (dx) di suo padre se ci sono entrambi i figli, il figlio sx viene prima del figlio dx nell’ordinamento dei figli di un nodo. 2 Esempio e Terminologia 3  Alberi Binari Propri Definizione Albero binario proprio T : albero binario tale che: ogni nodo interno ha esattamente 2 figli Albero'Binario' Albero'Binario'Proprio' Osservazione In letteratura gli alberi propri (proper in inglese) sono anche chiamati pieni (full in inglese). 4  Interfaccia BinaryTree public interface BinaryTree extends Tree { Position left(Position p); Position right(Position p); Position sibling(Position p); } 5 Proprietà di un albero binario proprio T non vuoto n = numero di nodi in T m = numero di foglie in T (nE in [GTG14]) n−m = numero di nodi interni in T (nI in [GTG14]) h = altezza di T Proprietà: 1 m =n−m+1 2 h + 1 ≤ m ≤ 2h 3 h ≤ n − m ≤ 2h − 1 4 2h + 1 ≤ n ≤ 2h+1 − 1 n−1 5 log2 (n + 1) − 1 ≤ h ≤ 2 6  IMPORTANTE In assenza di altre ipotesi, il migliore upper bound che possiamo dare all’altezza di un albero binario è O (n) con n = numero di nodi dell’albero 22  Visite di Alberi Binari Oltre alle visite in preorder e postorder, per gli alberi binari si definisce anche la visita inorder, basata sulla regola: prima (ricorsivamente) il sottoalbero sx, poi il padre, poi (ricorsivamente) il sottoalbero dx. Algoritmo inorder(v ) Input: v ∈ T Output: visita inorder di Tv if (T.left(v ) 6= null) then inorder(T.left(v )); visita v ; if (T.right(v ) 6= null) then inorder(T.right(v )); Chiamata iniziale: inorder(T.root()). 23  Esempio Sequenza inorder: Osservazione: È un esempio di albero binario di ricerca, che studieremo più avanti, dove la visita inorder tocca gli elementi presenti in ordine crescente di valore. 24  Applicazioni delle visite: espressioni aritmetiche Definizione (Parse Tree) Il Parse Tree T associato a una espressione aritmetica E (con operatori solo binari) è un albero binario proprio i cui nodi foglia contengono le costanti/variabili di E e i nodi interni contengono gli operatori di E , in modo tale che: Se E = a, con a costante/variabile, allora T è costituito da un’unica foglia contenente a Se E = (E1 Op E2 ), la radice di T contiene Op e ha come sottoalbero sx (risp., dx) il Parse Tree associato a E1 (risp., E2 ). 27 Osservazioni 1 Se si ammettono operatori unari, l’albero non è più proprio. Ad es.: −15 ∗ (3 + 7) *" !" +" 15" 3" 7" 2 Nei compilatori Nei lucidi successivi vedremo come a partire dal Parse Tree T di una espressione E si possono generare le rappresentazioni di E in notazione postfissa e infissa, usando le visite rispettivamente in postorder e inorder. Sia Ev la espressione associata al sottoalbero Tv , con v nodo di T 29  Generazione della espressione in notazione infissa Idea: si utilizza lo schema della visita inorder Algoritmo infix(T ,v ,L) Input: Parse Tree T for E , v ∈ T , Lista L Output: Aggiunta a L di Ev in notazione infissa if (T.isExternal(v )) then L.addLast(v.getElement()); else L.addlast(’(’); infix(T ,T.left(v ),L); L.addlast(v.getElement()); infix(T ,T.right(v ),L); L.addlast(’)’); Chiamata iniziale: infix(T , T.root(), L) con L = ∅. 30 Generazione della espressione in notazione postfissa Idea: si utilizza lo schema della visita in postorder Algoritmo postfix(T ,v ,L) Input: Parse Tree T for E , v ∈ T , Lista L Output: Aggiunta a L di Ev in notazione postfissa if (T.isExternal(v )) then L.addLast(v.getElement()); else postfix(T ,T.left(v ),L); postfix(T ,T.right(v ),L); L.addlast(v.getElement()); Chiamata iniziale: postfix(T , T.root(), L) con L = ∅. 32