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à.
Materiale di riferimento:
  1. Testo [GTG14]: Ch. 1, 2, 7
  2. Lucidi: Ripasso Java

Ultimo aggiornamento: 20 ottobre 2017 Vai alla pagina iniziale