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.
Materiale di riferimento:
  1. Lucidi: Grafi I Parte
  2. Lucidi: Grafi II Parte

Ultimo aggiornamento: 13 dicembre 2017 Vai alla pagina iniziale