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

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

Nozioni di base

  • 25 settembre. Obiettivi formativi e organizzazione del corso. Concetti fondamentali: problema computazionale, algoritmo, modello RAM, pseudocodice, taglia dell'istanza.
  • 27 settembre. Concetti fondamentali: struttura dati. Analisi di Algoritmi: complessità e correttezza; definizione della funzione complessità ordini di grandezza (O, Omega, Theta).
  • 28 settembre. Concetti fondamentali: Ordini di grandezza (o); funzioni parte bassa e alta; funzioni notevoli; esercizio R-4.21 del testo; procedimenti per provare limiti superiori e inferiori alla complessità ; esempi (PrefixAverages quadratico e lineare); confronto di algoritmi; complessità polinomiale vs complessità esponenziale;
  • 2 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). Esercizio C-4.43 del testo. Analisi di correttezza: approccio generale.
  • 4 ottobre. Analisi di correttezza: metodo degli invarianti; applicazione del metodo degli invarianti ad arrayMax e arrayFind. Esercizi: determinazione del più lungo segmento di 1 consecutivi in una sequenza binaria; determinazione di una colonna di 0 in una matrice di interi. Calcolo di F(n) iterativo.
  • 5 ottobre: Algoritmi ricorsivi: specifica; complessità tramite relazioni di ricorrenza; uso dell'induzione per provare limiti superiori/inferiori basati su una relazione di ricorrenza; analisi di correttezza tramite induzione. Esempi: LinearSum, ReverseArray e Power.
  • 9 ottobre: Algoritmi ricorsivi: Power (pseudocodice, relazione di ricorrenza e prova per induzione di un upper bound); BinaryFib (pseudocodice, relazione di ricorrenza e prova per induzione di upper e lower bound). Algoritmo PowerFib. Esempi di domande teoriche d'esame. Esercizi: esercizio C-5.10 del testo (element uniqueness); conteggio di 1 in una matrice binaria con gli 1 prima degli 0 in ogni riga, e il numero di 1 non decrescente con l'indice di riga.
Materiale di riferimento:
  1. Lucidi (con errata): Nozioni di Base
  2. Esercizi svolti sulle nozioni di base
  3. Testo [GTG14]: Paragrafi 1.8.2, 2.1.2, 13.1, 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

  • 11 ottobre: Definizione del Pattern Matching come problema computazionale. Notazioni. Algoritmo findBrute: pseudocodice, esempi e analisi. Esercizi: C-12.14 del testo; modifica di findBrute quando il primo carattere del pattern è diverso dagli altri. Algoritmo findKMP: idee principali; definizione di failure function.
  • 12 ottobre: Algoritmo findKMP: pseudocodice, esempi e analisi. Algoritmo computeFailKMP: idee principali; pseudocodice.
  • 18 ottobre: Algoritmo computeFailKMP: esempio e analisi. Esempi di domande teoriche. Esercizi: C-12.19 del testo; ricerca di un pattern come sottostringa circolare di un testo.
  • 19 ottobre: Esercizi: ricerca di tutte le occorrenze di un pattern in un testo; analisi di findBrute assumendo il pattern fatto di caratteri tutti distinti.
Materiale di riferimento:
  1. Lucidi (con errata): Text Processing
  2. Esercizi svolti sul text processing

Ripasso di Java

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

Alberi

  • 25 ottobre: Alberi: applicazioni; definizioni; terminologia;
  • 26 ottobre: Alberi: dimostrazione Proposizione 8.3 del testo (esercizio R-8.2); metodi dell'interfaccia Tree; calcolo della profondità di un nodo (algoritmi ricorsivo e iterativo); calcolo dell'altezza di un nodo e di un albero; esercizio C-8.27 del testo; visite in preorder e postorder.
  • 30 ottobre: Alberi: analisi di complessità delle visite; esercizi sul calcolo delle profondità e delle altezze di tutti i nodi di un albero; esercizio C-8.50 del testo. Alberi binari: definizione; interfaccia. Alberi binari propri: definizione; proprietà (Esercizio R-8.7 e R-8.8 del testo).
  • 30 ottobre (bis): Alberi binari: visita inorder; Parse Tree di un'espressione fully parenthesized in notazione infissa; algoritmo evaluateExpression; algoritmo di ricostruzione della espressione a partire dal Parse Tree; espressione in notazione postfissa e sua relazione con la visita postorder del Parse Tree. Esercizi sugli alberi binari: calcolo della heightsum; metodo preorderNext (da esercizio C-8.41 del testo); calcolo dell'imbalance dell'albero (inizio).
  • 2 novembre: Esercizi sugli alberi binari: calcolo dell'imbalance dell'albero (inizio); dimostrazione che in un albero binario proprio m >= h+1. Cenni sull'implementazione Java di alberi binari.
Materiale di riferimento:
  1. Lucidi (con errata): Alberi Generali
  2. Lucidi (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

  • 2 novembre: Priority Queue: definizione; Interfacce Entry(K,V) e PriorityQueue(K,V); applicazioni reali; implementazione tramite liste (ordinate e non). Albero binario completo: definizione e relazione tra altezza e numero di nodi.
  • 6 novembre: Caso di studio (relativo agli alberi): alberi di decisione. Priority Queue: heap (definizione, realizzazione tramite vettore, level numbering e sue proprietà); esercizi R-9.9, R-9.10. R-9.15 del testo.
  • 8 novembre: Implementazione dei metodi della Priority Queue tramite heap su array: pseudocodice e analisi. Esercizio sulla rimozione di una entry generica da uno heap, ed esercizio C-9.34 del testo.
  • 9 novembre: Esercizi di ripasso per il compitino: C-5.18 del testo; II.2 dell'Esempio Compitino (2); II.1 dell'Esempio Compitino (2); II.1 dell'Esempio Compitino; Problema 1 della dispensa di esercizi svolti sugli alberi. Domande teoriche di ripasso per il compitino: I.2(b) dell'Esempio Compitino (2); I.1 dell'Esempio Compitino.
  • 13 novembre: I Compitino
  • 20 novembre: Esercizo C-9.36 del testo. 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.
  • 22 novembre: 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.
  • 23 novembre: Problemi 6 e 7 della dispensa di esercizi svolti.
Materiale di riferimento:
  1. Lucidi (con errata): Priority Queue (I Parte)
  2. Lucidi (con errata): Priority Queue (II Parte)
  3. Esercizi svolti su priority queue e heap
  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.

Mappe e Dizionari

  • 23 novembre: Mappa e Dizionario: definizione e applicazioni. Mappa: interfaccia Map; implementazione tramite lista (doubly-linked) e complessità dei metodi get, put e remove. Tabelle Hash: ingredienti principali; nozione di hashing uniforme.
  • 27 novembre: Tabelle Hash: risoluzione collisioni tramite separate chaining; implementazione dei metodi della mappa (get(k), put(k,x) e remove(k)) e loro complessità dei metodi della mappa (get(k), put(k,x) e remove(k)) al caso medio in funzione del load factor; rehashing; scelta dell'hash code; scelta della compression function; esercizi R-10.5 e R-10.9 del testo. Alberi Binari di Ricerca (ABR): definizione; proprietà della vista in-order;
  • 29 novembre: Alberi Binari di Ricerca (ABR): metodo TreeSearch(k,v); implementazione dei metodi della mappa (get(k), put(k,x) e remove(k)) e loro analisi. Esercizi: esercizio R-11.1 del testo; versione iterativa di TreeSearch; conteggio del numero di entry con chiave <=k, con e senza variabile size.
  • 30 dicembre: 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.
  • 4 dicembre: Osservazioni sui questionari. (2,4)-Tree: metodi put(k,x) con Split(u), remove(k) con Delete(e,u,alfa).
  • 7 dicembre: Dizionario: differenze tra Dizionario e Mappa; specifica dei metodi get(k), put(k,x) e remove(k,v); implementazione tramite la Mappa. Esercizi: calcolo dell'altezza di un (2,4)-Tree; esercizio C-11.44 del testo (altezze uguali e non); calcolo del numero di entry con chiave <=k in un (2,4)-Tree con la variabile size in ogni nodo. Esempi di domande da I parte del compito.
Materiale di riferimento:
  1. Lucidi (con errata): Mappa/Dizionario I Parte
  2. Lucidi (con errata): Mappa/Dizionario 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

  • 11 dicembre: Definizione di grafo; terminologia; esempi applicativi; 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).
  • 12 dicembre: Rappresentazione di grafi (liste di adiacenza, matrice di adiacenza); nozione di visita; algoritmo DFS (pseudocodice e analisi); Proposizioni 14.12 e 14.14 del testo.
  • 13 dicembre: Completamento prova della Proposizione 14.14 del testo. Esercizi: C-14.37; aggiunta di archi per rendere connesso un grafo; discussione sul labirinto. Algoritmo BFS (pseudocodice e analisi); Proposizione 14.16 del testo.
  • 14 dicembre: Determinazione di un ciclo tramite BFS. Esercizi: numerosità dei livelli della BFS di un grafo a grado costante; riconoscimento di grafi bipartiti; ricerca di un vertice che raggiunge almeno altri n/2 vertici.
Materiale di riferimento:
  1. Lucidi (con errata): Grafi I Parte
  2. Lucidi (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

  • 18 dicembre: Introduzione al problema dell'ordinamento. Algoritmi basati su confronti: definizione, MergeSort (algoritmo, relazione di ricorrenza, analisi di Merge, analisi di MergeSort tramite l'albero della ricorsione per n potenza di 2 ed n generale); Esecizio sulla fusione di k sequenze ordinate
  • 19 dicembre: QuickSort: strategia generale; pseudocodice in-place (QuickSortInPlace); analisi di correttezza e complessità. Randomized QuickSort: algoritmo; analisi di complessità probabilistica (senza prova). Distinzione tra algoritmi probabilistici e deterministici.
  • 20 dicembre: Esercizio C-13.48 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.
  • 21 dicembre: Radix Sort: algoritmo; analisi di complessità. e analisi di correttezza. Esercizi C-13.39 e C-13.42 del testo.
Materiale di riferimento:
  1. Lucidi (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;

Ripasso

  • 8 gennaio: Ripasso di: ordini di grandezza; alberi binari ed espressioni aritmetiche; rehashing; MWTreeSearch; analisi della BFS. Esercizi: esercizio 3 dell'esempio di Scritto Completo 3 (simile al Problema 11 della dispensa di esercizi sull'ordinamento)
  • 10 gennaio: Esercizi: Problemi 5c e 7 della dispensa di esercizi sull'ordinamento; esercizio 2 dell'esempio di Scritto Completo 3; esercizio 2 dell'esempio di Scritto Completo 2 (anche Problema 5 della dispensa di esercizi su Alberi Binari di Ricerca e (2,4)-Tree); Problema 8 della dispensa di esercizi sui grafi. Domande teoriche.

Ultimo aggiornamento: 11 gennaio 2018 Vai alla pagina iniziale