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

DIARIO delle LEZIONI

Nozioni di base

  • 26 settembre: Obiettivi formativi e organizzazione del corso. Concetti fondamentali: problema computazionale, algoritmo, modello RAM, pseudocodice.
  • 28 settembre: Concetti fondamentali: taglia dell'istanza, struttura dati. Analisi di Algoritmi: complessità e correttezza; definizione della funzione complessità ordini di grandezza (O, Omega, Theta, o); funzioni parte bassa e alta.
  • 29 settembre: Concetti fondamentali: 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; cenni all'algoritmo RSA; caveat.
  • 4 ottobre: Esercizio: analisi di InsertionSort. 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; metodo degli invarianti; applicazione del metodo degli invarianti ad arrayMax.
  • 5 ottobre: Invarianti: esercizio (max segmento di 1 consecutivi); calcolo di F(n) iterativo. Algoritmi ricorsivi: algoritmi LinearSum, ReverseArray e Power; relazioni di ricorrenza; uso dell'induzione per provare limiti superiori/inferiori alla complessità definita tramite relazione di ricorrenza.
  • 6 ottobre: Calcolo di F(n): algoritmi ricorsivo e basato su Power(x,n), e loro analisi. Esempi di domande teoriche d'esame. Esercizio: determinazione di una colonna di 0 in una matrice di interi (algoritmo, analisi complesità e correttezza).
Materiale di riferimento:
  1. Lucidi (finali): Nozioni di Base
  2. Homework 1
  3. Soluzioni Homework 1 e altri esercizi svolti sulle nozioni di base
  4. 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

  • 10 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.
  • 13 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.
  • 17 ottobre: Esercizi: ricerca di tutte le occorrenze di un pattern in un testo.
Materiale di riferimento:
  1. Lucidi (finali): Text Processing
  2. Homework 2
  3. Soluzioni Homework 2 e altri esercizi svolti sul text processing
  4. 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

Ripasso di Java

  • 17 ottobre: Programma stand-alone; esempio (calcolo dell'n-esimo numero di Fibonacci); caratteristiche di Java e della programmazione Object-Oriented (portabilità, modularità)
  • 19 ottobre: Caratteristiche di Java e della programmazione Object-Oriented (incapsulamento, interfacce, classi astratte, ereditarietà); programmazione generica. Esempio completo (definizione, interfaccia ed implementazione di una Doubly-Linked list; implementazione di InsertionSort); Java Collection Framework e nozione di Application Programming Interface (API) Iteratori (interfacce Iterator e Iterable; implementazione di un interatore per PositionList).
Materiale di riferimento:
  1. Testo [GTG14]: Ch. 1, 2, 7
  2. Lucidi (finali): Ripasso Java
  3. Codice: Insertion Sort con PositionList e ArrayList (cartella zippata)
  4. Voce Wikipedia su Application Programming Interface

Alberi

  • 20 ottobre: Alberi: applicazioni; definizioni; terminologia; dimostrazione Proposizione 8.3 del testo; metodi dell'interfaccia Tree; algoritmo ricorsivo per il calcolo della profondità di un nodo; algoritmo iterativo calcolo per il calcolo della profondità di un nodo.
  • 24 ottobre: Algoritmo height per il calcolo dell'altezza di un nodo (e di un albero); algoritmo heightBad per il calcolo dell'altezza di un albero; visite in preorder e postorder; esercizi sulle visite, sul calcolo di tutte le altezze e sul calcolo di tutte le profondità.
  • 26 ottobre: 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); parse tree di un'espressione fully parenthesized (notazione infissa); algoritmo evaluateExpression; espressione in notazione postfissa; relazione tra visita postorder del parse tree e la notazione postfissa di una espressione; vista inorder
  • 27 ottobre: Esercizi sugli alberi binari (dai lucidi).
  • 2 novembre: Implementazione di alberi binari in Java.
Materiale di riferimento:
  1. Lucidi (finali): Alberi generali
  2. Lucidi (finali): Alberi binari
  3. Lucidi (finali): Alberi binari in Java
  4. Homework 3
  5. Soluzioni Homework 3 e altri esercizi svolti sugli alberi
  6. 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.
  • 3 novembre: Priority Queue: Heap (definizione, realizzazione tramite vettore, level numbering e sue proprietà); implementazione dei metodi della Priority Queue; esercizi R-9.9, R-9.10. R-9.15 del testo e altri esercizi simili sulle relazioni tra profondità di un nodo e rank della chiave.
  • 7 novembre: Analisi del metodo removeMin(); Esercizi (rimozione di una entry generica; esercizi C-9.34 e C-9.36 del testo; proprietà di un albero ternario completo).
  • 9 novembre: Ripasso per compitino
  • 10 novembre: Costruzione di uno Heap top-down e bottom-up iterativa. Esercizio C-9.35 del testo ed esercizio sul calcolo della entry con la k-esima chiave più piccola.
  • 14 novembre: I Compitino
  • 21 novembre: PriorityQueueSort: SelectionSort, InsertionSort, HeapSort come casi particolari. Implementazione di HeapSort in place. Esercizi: problema 5 della dispensa; esercizio C-9.39 del testo (assumendo l'input come stream di entry e memoria limitata)
Materiale di riferimento:
  1. Lucidi (finali): Priority Queue I Parte
  2. Lucidi (finali): 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: Mappe 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; 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)); esercizio R-10.5 del testo.
  • 24 novembre: Tabelle Hash: complessità dei metodi della mappa (get(k), put(k,x) e remove(k)) al caso medio in funzione del load factor; algoritmo WordCount; rehashing; esercizio R-10.9 del testo. 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.
  • 30 novembre: Esercizio R-11.1 del testo. Esercizi sugli ABR: versione iterativa di TreeSearch; ricerca di una entry con chiave in un intervallo [A,B]; conteggio del numero di entry con chiave <=k, con e senza variabile size. Multi-Way Search Tree: definizione ed esempi; Proposizione 11.2 (ed esercizio C-11.46) del testo.
  • 1 dicembre: Multi-Way Search Tree: metodo MWTreeSearch(k,v) e implementazione di get(k). (2,4)-Tree: definizione; altezza (Proposizione 11.3 del testo); metodi put(k,x) con Split(u), remove(k) con Delete(e,u,alfa). Questionario di valutazione.
  • 5 dicembre: Osservazioni sui questionari. Dizionario: differenze tra Dizionario e Mappa; specifica dei metodi get(k), put(k,x) e remove(k,v); implementazione tramite la Mappa. Esercizi: R-11.17 del testo, problemi 7 e 8 della dispensa di esercizi svolti
  • 7 dicembre: Problemi 6 e 9 della dispensa di esercizi svolti. Esempi di domande da I parte del compito. Riepilogo.
Materiale di riferimento:
  1. Lucidi (finali): Mappa/Dizionario I Parte
  2. Lucidi (finali): Mappa/Dizionario II parte
  3. Homework 4
  4. Esercizi svolti su Alberi Binari di Ricerca e (2,4)-Tree
  5. Testo [GTG14]: Ch. 10 (Par. 1, 2, 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.17; R-11.20a; R-11.20d; C-11.31; C-11.44; C-11.46.
Grafi
  • 7 dicembre: Definizione di grafo (diretto e non diretto); terminologia (nodi/vertici/archi). Esempi applicativi.
  • 12 dicembre: Grafi: terminologia (vertici adiacenti, archi incidenti, cammino, ciclo, grafo connesso, subgraph, spanning subgraph, free tree, rooted tree); equivalenza tra le definizioni di free tree e rooted tree; nozioni di spanning tree/forest; proprietà dei grafi; Proposizione 14.11 e esercizio C-14.34 del testo.
  • 14 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.
  • 15 dicembre: Algoritmo BFS (pseudocodice e analisi); Proposizioni 14.16 e esercizi C-14.46 e C-14.47 del testo.
  • 19 dicembre: Esercizi:C-14.37 e C-14.49 del testo; riconoscimento di grafi bipartiti; aggiunta di archi per rendere connesso un grafo; numerosità dei livelli della BFS di un grafo a grado costante. Esempi di domande teoriche e riepilogo sui grafi.
Materiale di riferimento:
  1. Lucidi (finali): Grafi I Parte
  2. Lucidi (finali): Grafi II Parte
  3. Homework 5
  4. Esercizi svolti sui Grafi
  5. 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

  • 19 dicembre (bis): Design Pattern: Divide-and-Conquer. Definizione del problema computazionale dell'ordinamento. MergeSort: algoritmo e analisi tramite l'albero della ricorsione; relazione di ricorrenza. InsertionSort: algoritmo in place.
  • 21 dicembre: InsertionSort: analisi in funzione della taglia dell'input e del numero di inversioni. 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.
  • 22 dicembre: Esercizi: merge di k sequenze ordinate; esercizi C-13.42, C-14.48 del testo. Definizione di algoritmo di ordinamento basato su confronti e lower bound sulla complessità di un tale algoritmo (senza prova).
  • 9 gennaio: Analisi di Randomized QuickSort. BucketSort: algortimo e analisi di complessità. Nozione di ordinamento stabile. Radix Sort: algoritmo e analisi di complessità.
  • 11 gennaio: Radix Sort: analisi di correttezza. Esercizi C-13.39, C-13.40 e C-13.35 del testo.
  • 12 gennaio: Esercizi e domande teoriche dai due esempi di scritto completo.
Materiale di riferimento:
  1. Lucidi (finali): Ordinamento
  2. Homework 6
  3. Esercizi svolti sull'Ordinamento
  4. 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.30; 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 2017 Vai alla pagina iniziale