Dati e Algorithmi 1 (9 CFU - 72 ore)
Canale 2 INF (5-9)
A.A. 2018/2019

DIARIO delle LEZIONI
Diario delle lezioni A.A. 17/18

Nozioni di base

  • 1 ottobre. Obiettivi formativi e organizzazione del corso. Concetti fondamentali: problema computazionale, algoritmo, modello RAM, pseudocodice, taglia dell'istanza.
  • 3 ottobre. Concetti fondamentali: struttura dati. Analisi di Algoritmi: complessità e correttezza; definizione della funzione complessità ordini di grandezza (O, Omega, Theta).
  • 8 ottobre. Concetti fondamentali: Ordino di grandezza o-piccolo; proprietà degli ordini di grandezza; math tools (parte bassa e alta, sommatorie notevoli); esempi (PrefixAverages quadratico e lineare); procedimento per provare limiti superiori e inferiori alla complessità ; esercizio simile a R-4.29 del testo; esercizio su InsertionSort.
  • 10 ottobre. Caso di studio: algoritmo RSA. Caveat relativi all'analisi asintotica al caso pessimo. Tecniche di dimostrazione: esempio, controesempio, per assurdo, induzione. Dimostrazione della formula chiusa per F(n) (n-esimo numero di Fibonacci). Esempio di induzione fallace per provare che F(n)=0
  • 11 ottobre. Analisi di correttezza: approccio generale; definizione di invariante; utilizzo di un invariante per provare la correttezza di un ciclo; esempi (arrayMax e arrayFind). Esercizi: determinazione del più lungo segmento di 1 consecutivi in una sequenza binaria; conteggio del numero di 1 in una matrice binaria con gli 1 prima degli 0 in ciascuna riga e numero di 1 non crescente con l'indice di riga.
  • 15 ottobre. Esercizio: determinazione di una colonna di 0 in una matrice di interi. Algoritmi ricorsivi: definizione; esempi (LinearSum e ReverseArray); albero della ricorsione; analisi di complessità tramite lalbero della ricorsione; analisi di correttezza; relazioni di ricorrenza; esempi.
  • 17 ottobre. Algoritmi ricorsivi: BinaryFib (pseudocodice, relazione di ricorrenza e prova per induzione del lower bound). Algoritmo PowerFib. Esercizi: esercizio C-5.10 del testo (element uniqueness); Esempi di domande teoriche.
Materiale di riferimento:
  1. Lucidi (finali con errata): Nozioni di Base (I Parte)
  2. Lucidi (finali con errata): Nozioni di Base (II Parte)
  3. Esercizi svolti sulle nozioni di base
  4. Testo [GTG14]: Paragrafi 1.8.2, 2.1.2, e Capitoli 4 e 5.
    Esercizi consigliati dal libro di testo: R-4.2; R-4.7; R-4.10; R-4.12; R-4.14; R-4.16; R-4.21; R-4.31; R-5.6; C-4.35; C-4.43; C-4.44; C-4.45; C-4.46; C-5.10; C-5.18; C-5.20.

Text Processing

  • 17 ottobre. Definizione del Pattern Matching come problema computazionale. Notazioni. Algoritmo findBrute: pseudocodice, esempi e analisi. Esercizi: C-12.14 del testo.
  • 18 ottobre. Esercizio: modifica di findBrute quando il primo carattere del pattern è diverso dagli altri. Algoritmo findKMP: idee principali; definizione di failure function; pseudocodice, esempi e analisi di correttezza.
  • 22 ottobre. Algoritmo computeFailKMP: idee principali; pseudocodice; esempio; analisi di complessità e correttezza. Esercizi: ricerca di un pattern come sottostringa circolare di un testo; ricerca di tutte le occorrenze di un pattern in un testo.
  • 24 ottobre: Esercizi: ricerca di tutte le occorrenze di un pattern in un testo; ricerca del più lungo prefisso di un pattern in un testo. Esempi di domande teoriche.
Materiale di riferimento:
  1. Lucidi (finali con errata): Text Processing
  2. Esercizi svolti sul text processing
  3. Testo [GTG14]: Ch. 12 (Par. 12.1, 12.2.1, 12.2.3).
    Esercizi consigliati dal libro di testo: R-12.1; C-12.14; C-12.15; C-12.17; C-12.19; C-12.22; C-12.30

Ripasso di Java

  • 24 ottobre: Programma stand-alone; esempio (calcolo dell'n-esimo numero di Fibonacci);
  • 25 ottobre: Caratteristiche di Java e della programmazione Object-Oriented: portabilità, modularità, incapsulamento, interfacce, classi astratte, ereditarietà. Programmazione generica. Lista position-based: definizione; interfaccia; implementazione doubly-linked con accesso tramite position; Pila, e Coda.
  • 31 ottobre: InsertionSort: implementazione con List e ArrayList di Java. Java Collection Framework. Iteratori (interfacce Iterator e Iterable).
Materiale di riferimento:
  1. Lucidi: Ripasso Java
  2. Testo [GTG14]: Ch. 1, 2, 7
  3. Codice: Esempi di codice Java (cartella zippata)

Alberi

  • 31 ottobre: Alberi: applicazioni; definizioni; terminologia; dimostrazione Proposizione 8.3 del testo (esercizio R-8.2); metodi dell'interfaccia Tree;
  • 5 novembre: Calcolo della profondità di un nodo (algoritmi ricorsivo e iterativo); calcolo dell'altezza di un nodo e di un albero; esercizio simile a R-8.19 del testo; visite in preorder e postorder (pseudocodici, analisi ed esempi). Esercizio sul calcolo delle profondità e delle altezze di tutti i nodi di un albero;
  • 7 novembre: Esercizi C-8.27 e C-8.50 del testo. Alberi binari: definizione; interfaccia. Alberi binari propri: definizione; proprietà (dal testo: Proposition 8.7 del testo, limitata alla parte sugli alberi binari propri, Proposition 8.8, Esercizi R-8.7 e R-8.8).
  • 8 novembre: Alberi binari: visita inorder; Parse Tree di un'espressione in notazione infissa; algoritmo evaluateExpression; algoritmo di ricostruzione della espressione a partire dal Parse Tree. Esercizi sugli alberi binari: calcolo della heightsum; metodo preorderNext e inorderNext (da esercizio C-8.41 del testo).
  • 8 novembre (bis): Esercizi sugli alberi binari: conteggio dei nodi strong (lucido 26 sugli alberi binari); dimostrazione che in un albero binario proprio m >= h+1. Esempi di domande teoriche.
Materiale di riferimento:
  1. Lucidi (finali con errata): Alberi Generali
  2. Lucidi (finali con errata): Alberi Binari
  3. Implementazione Java: Codice e lucidi di presentazione
  4. Esercizi svolti sugli alberi
  5. Testo [GTG14]: Ch. 8 (Par. 8.1, 8.2, 8.3.1, 8.4.1, 8.4.3-8.4.5).
    Esercizi consigliati dal libro di testo: R-8.3; R-8.4: R-8.6; R-8.7; R-8.8; R-8.19; C-8.24; C-8.25; C-8.26; C-8.27; C-8.39; C-8.41; C-8.50; C-8.52.

Priority Queue

  • 8 novembre (bis): Priority Queue: definizione; Interfacce Entry(K,V) e PriorityQueue(K,V); applicazioni reali; algoritmo per top-K pattern discovery; implementazione tramite liste (ordinate e non). Albero binario completo: definizione e relazione tra altezza e numero di nodi.
  • 12 novembre: Priority Queue: heap (definizione, realizzazione tramite vettore, level numbering e sue proprietà); esercizi R-9.9, R-9.10, (variante di) R-9.13 del testo. Implementazione dei metodi della Priority Queue tramite heap su array: pseudocodice e analisi.
  • 14 novembre: Ripasso per il compitino: esempio di I compitino (3); esempio di I compitino (1) (domande 1 e 3 della prima parte e esercizio 1 della seconda parte); nozione di complessità di un algoritmo.
  • 15 novembre: Esercizio sulla rimozione di una entry generica da uno heap, e esercizi C-9.34 e C-9.36 del testo. Esercizio 2 da Esempio di Scritto Completo (4). Cenni sull'implementazione di alberi.
  • 26 novembre: Cenni sull'implementazione Java di alberi. Caso di studio: simulazione per eventi di un ufficio postale. Costruzione di uno Heap a partire da un array con n entry: approcci top-down e bottom-up. Analisi dell'approccio top-down.
  • 28 novembre: Analisi dell'approccio bottom-up. Esercizio C-9.35 del testo PriorityQueueSort: SelectionSort, InsertionSort, HeapSort come casi particolari. Implementazione di HeapSort in place. Esercizio sul calcolo della entry con la k-esima chiave più piccola.
  • 29 novembre: Esercizio sulla determinazione della sequenza ordinata delle m entry con chiavi più piccole di uno Heap con n>m entry. Esempi di domande teoriche.
Materiale di riferimento:
  1. Lucidi (finali con errata): Priority Queue (I Parte)
  2. Lucidi (finali con errata): Priority Queue (II Parte)
  3. Esercizi svolti sulle Priority Queue
  4. Testo [GTG14]: Ch. 9 (Par. 9.1-9.4).
    Esercizi consigliati dal libro di testo: R-9.1; R-9.9: R-9.10; R-9.12; R-9.13; R-9.15; R-9.16; R-9.17; R-9.18; R-9.19; R-9.23; C-9.30; C-9.32; C-9.34; C-9.36; C-9.37; C-9.38; C-9.39.

Mappa

  • 29 novembre: Mappa: definizione e applicazioni; interfaccia Map; implementazione tramite lista doubly-linked con la complessità dei metodi get, put e remove. Tabelle Hash: ingredienti principali.
  • 3 dicembre: Tabelle Hash: esempio (word count); nozione di uniform hashing; scelta dell'hash code; scelta della compression function; risoluzione collisioni tramite separate chaining; implementazione dei metodi della mappa (get(k), put(k,x) e remove(k)) e loro complessità al caso pessimo e al caso medio in funzione del load factor; rehashing; esercizi R-10.5 e R-10.9 del testo.
  • 5 dicembre (prof. Vandin): Alberi Binari di Ricerca (ABR): definizione; proprietà della vista in-order; metodo TreeSearch(k,v); implementazione dei metodi della mappa (get(k), put(k,x) e remove(k)) e loro analisi.
  • 10 dicembre: Esercizi: esercizio R-11.1 del testo; versione iterativa di TreeSearch; conteggio del numero di entry con chiave <=k, con e senza variabile size.
  • 12 dicembre: Esercizio: algoritmo non ricorsivo per trovare la più piccola chiave positiva in un albero binario di ricerca. Multi-Way Search Tree: definizione ed esempi; Proposizione 11.2 (ed esercizio C-11.46) del testo; metodo MWTreeSearch(k,v) e implementazione di get(k). (2,4)-Tree: definizione; altezza (Proposizione 11.3 del testo). Questionario di valutazione.
  • 13 dicembre: Osservazioni sui questionari. (2,4)-Tree: metodi put(k,x) con Split(u), remove(k) con Delete(e,u,alfa). Esempi.
  • 17 dicembre: MultiMappa: differenze tra MultiMappa e Mappa; specifica dei metodi get(k), put(k,x) e remove(k,v); implementazione tramite Mappa+Liste. Esercizi: calcolo dell'altezza di un (2,4)-Tree; fusione di due (2,4)-Tree T e U con la massima chiave in T minore della minima chiave in U (con stessa altezza e altezze differenti). Esempi di domande teoriche.
Materiale di riferimento:
  1. Lucidi (finali con errata): Mappa I Parte
  2. Lucidi (finali con errata): Mappa II Parte
  3. Esercizi svolti su Alberi Binari di Ricerca e (2,4)-Tree
  4. Testo [GTG14]: Ch. 10 (Par. 1, 2 (tranne open addressing), 5.3), Ch 11 (Par. 11.1, 11.4)
    Esercizi consigliati dal libro di testo: R-10.4; R-10.5; C-10.42, R-11.1; R-11.2; R-11.5; R-11.13; R-11.15; R-11.17; R-11.18a; R-11.20a; R-11.20d; C-11.31; C-11.44; C-11.46.

Grafi

  • 17 dicembre: Definizione di grafo; terminologia; esempi applicativi.
  • 19 dicembre: Concetti fondamentali (cammino, ciclo, grafo connesso, subgraph, spanning subgraph, alberi (radicati, liberi e loro equivalenza), spanning tree/forest); proprietà dei grafi (Proposizioni 14.8, 14.10, 14.11 ed esercizio C-14.34 del testo); rappresentazione di grafi (strutture di base L_E e L_V, liste di adiacenza, matrice di adiacenza); nozione di visita; algoritmo DFS (pseudocodice).
  • 20 dicembre: Algoritmo DFS: analisi; visita di tutto il grafo; applicazioni (connettività, spanning tree, s-t reachability, ciclicità).
  • 7 gennaio: Esercizi: soluzione del problema del labirinto tramite DFS; aggiunta di K-1 archi per rendere connesso un grafo con K componenti connesse. Algoritmo BFS (pseudocodice e analisi); Proposizione 14.16 del testo; complessità di BFS; applicazioni (cammino minimo e ciclicità). Esercizio: massima separazione tra due vertici (ad es. profili nel grafo di Facebook).
  • 9 gennaio: Esercizi: calcolo del numero di coppie di vertici raggiungibili; upper bound sulla taglia dei livelli della BFS di un grafo regolare di grado c; Esercizio C-14.49 di [GTG14]. Esempi di domande teoriche.
Materiale di riferimento:
  1. Lucidi (finali con errata): Grafi I Parte
  2. Lucidi (finali con errata): Grafi II Parte
  3. Esercizi svolti sui Grafi
  4. Testo [GTG14]: Ch. 14 (Par. 1, 2, 3) Esercizi consigliati dal libro di testo: R-14.1; R-14.2; R-14.14; C-14.34; C-14.37; C-14.46; C-14.47; C-14.49; C-14.52; C-14.56

Ordinamento

  • 9 gennaio: Introduzione al problema dell'ordinamento. Definizione di algoritmo basato su confronti. MergeSort (algoritmo, analisi di Merge, analisi di MergeSort tramite l'albero della ricorsione).
  • 10 gennaio: Analisi di MergeSort tramite l'albero della ricorsione per n potenza di 2 ed n generale). Esecizio sulla fusione di k sequenze ordinate. QuickSort: strategia generale; pseudocodice in-place (QuickSortInPlace); complessità di partition; esempi.
  • 14 gennaio: QuickSortInPlace: analisi di complessità tramite albero della ricorsione. Distinzione tra algoritmi probabilistici e deterministici e definizione dell'analisi di complessità in alta probabilità e in media per un algoritmo probabilistico. Randomized QuickSort: algoritmo; complessità probabilistica (senza prova). Esercizi: modifica di QuickSortInPlace per renderlo fedele alla strategia L-E-G nel caso di chiavi non distinte (Esercizio C-13.33 in [GTG14]); modifica di Merge per determinare la taglia dell'intersezione di due sequenze ordinate con chiavi distinte.
  • 16 gennaio: Esercizio C-13.42 del testo. InsertionSort: algoritmo in place; analisi in funzione della taglia dell'input e del numero di inversioni. Lower bound sulla complessità di un algoritmo quasliasi algoritmo di ordinamento basato su confronti (senza prova). BucketSort: algortimo e analisi di complessità. Nozione di ordinamento stabile.
  • 17 gennaio: Radix Sort: algoritmo; analisi di complessità. e analisi di correttezza. Esercizi: C-13.39; C-13.40; lconteggio delle chiavi frequenti (Esempio di II Compitino (3)). Esempi di domande teoriche
Materiale di riferimento:
  1. Lucidi (finali con errata): Ordinamento
  2. Esercizi svolti sull'Ordinamento
  3. Testo [GTG14]: Par. 9.4.1 e Ch. 13 (Par. 1, 2, 3) Esercizi consigliati dal libro di testo: R-13.1; R-13.2; R-13.3; R-13.6; R-13.8; R-13.9; C-13.29; C-13.32; C-13.33; C-13.34; C-13.35; C-13.36; C-13.37; C-13.38; C-13.39; C-13.40; C-13.42; C-13.43; C-13.45; C-13.46; C-13.48;

Ultimo aggiornamento: 20 gennaio 2019 Vai alla pagina iniziale