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 d'esame.
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 da prima parte.
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.
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.
Materiale di riferimento:
  1. Lucidi: Priority Queue (I Parte)
  2. 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.

Ultimo aggiornamento: 12 novembre 2018 Vai alla pagina iniziale