Diario delle lezioni

Dettaglio degli argomenti svolti durante le lezioni.

  • Lezione del 30-09-2015
    Informazioni generali sul corso: obiettivi e motivazioni. Analisi delle risorse di calcolo richieste da un programma (es: tempo e spazio di memoria). Approcci alla stima dei tempi richiesti da un programma (metodo empirico vs. metodo teorico). Calcolo dei numeri di Fibonacci. Algoritmo numerico per calcolo dei numeri di Fibonacci (il suo costo ed i suoi problemi); Algoritmo ricorsivo per calcolo dei numeri di Fibonacci. Albero della ricorsione. Relazione di ricorrenza. Algoritmo ricorsivo per calcolo dei numeri di Fibonacci. Occupazione di memoria. Notazione Asintotica O (o grande). Algoritmo con complessità logaritmica basato sulle matrici per il calcolo dei numeri di Fibonacci e sua relazione di ricorrenza.
    - CAP. 1 (fino a 1.7 (incluso), escluse le dimostrazioni). Slide del corso (pdf).
  • Lezione del 01-10-2015
    Notazione asintotica O, Ω e Θ per delimitare l'andamento delle funzioni di costo. Metodi di analisi di un algoritmo: caso migliore, caso medio e caso peggiore. Analisi del caso medio e probabilità. Algoritmo per la ricerca sequenziale e sua analisi. Analisi algoritmi ricorsivi. Ricerca binaria (versione ricorsiva e non). Risoluzione con il metodo iterativo e della sostituzione. Tecnica del divide et impera e relazione di ricorrenza di algoritmi che adottano tale tecnica. Master Theorem e sua applicabilità (esempi).
    - CAP. 2 (da 2.1 fino a 2.5.2 compreso). Slide del corso (pdf).
  • Lezione del 07-10-2015
    I tipo di dato dizionario, pila e coda e definizione delle loro funzioni astratte. Rappresentazioni indicizzate (array) e collegate (liste semplici, circolari, doppiamente collegate): pro e contro. Alberi e loro rappresentazione tramite strutture collegate. Rappresentazione di tipo puntatore ai figli, rappresentazione di tipo lista di figli e rappresentazione di tipo primo figlio-fratello successivo. Implementazione del tipo di dato Pila utilizzando un array ed implementazione delle sue operazioni. Implementazione del tipo di dato Pila utilizzando una lista semplice ed implementazione delle sue operazioni. Implementazione del tipo di dato Coda utilizzando una lista semplice ed implementazione delle sue operazioni. Esercizio lasciato agli studenti: implementazione del tipo di dato Coda utilizzando un array ed implementazione delle sue operazioni. Algoritmo per verificare se le parentesi in una stringa sono bilanciate.
    - CAP. 3 (da 3.1 fino a 3.2 compreso). Slide del corso (pdf e pdf).
  • Lezione del 08-10-2015
    Implementazione del tipo di dato Coda utilizzando un array ed implementazione delle sue operazioni. Visite di alberi. Algoritmo generico di vista di un albero. Algoritmo iterativo di visita in profondità. Algoritmo ricorsivo di visita in profondità. Algoritmo di visita in ampiezza. Algoritmo per il calcolo della profondità di un albero binario. Algoritmo per contare le foglie di un albero binario.
    - CAP. 3 (esclusi: "tecnica del raddoppiamento-dimezzamento" e dimostrazione del teorema 3.2). Slide del corso (pdf e pdf).
  • Lezione del 14-10-2015
    Il problema dell'ordinamento. L'approccio incrementale. Algoritmo SelectionSort (descrizione, codice e analisi). Algoritmo InsertionSort (descrizione, codice e analisi). Algoritmo BubbleSort (descrizione, codice e analisi). Alberi Heap: caratteristiche e rappresentazione. Le procedure fixHeap e getMax. Algoritmo HeapSort (descrizione, codice e analisi). Algoritmo MergeSort (descrizione, codice e analisi). Algoritmo QuickSort (descrizione, codice e analisi nel caso medio e peggiore). Lower bound per il problema dell'ordinamento nel modello basato sui confronti e sua dimostrazione. Alberi di decisione.
    - CAP 4. (4.1, 4.2, 4.3, 4.4, 4.5). Slide del corso (pdf).
  • Lezione del 15-10-2015
    Ordinamenti lineari: IntegerSort (descrizione, codice e analisi), BucketSort, Proprietà di stabilità, RadixSort (descrizione ed analisi).
    - CAP 4. (4.6, 4.7). Slide del corso (pdf).
  • Lezione del 21-10-2015
    Esercitazione: visita generica di un albero, visita in ampiezza di un albero, visita in profondità di un albero (visita in preordine, simmetrica e in postordine). Esercizio sugli Heap. Il problema della "moneta più leggera".
    - Slide del corso (pdf).
  • Lezione del 22-10-2015
    Il tipo di dato Dizionario. Introduzione agli alberi di ricerca (Binary Search Tree -- BST) e le operazioni di ricerca, inserimento e cancellazione in un BST (descrizione, pseudocodice ed analisi). La funzione max(nodo n) e pred(nodo n) (predecessore di un nodo).
    - Appunti presi a lezione.
  • Lezione del 28-10-2015
    Il tipo di dato Dizionario. Alberi di ricerca (Binary Search Tree -- BST). Operazioni di ricerca, inserimento e cancellazione in un albero BST (descrizione, pseudocodice ed analisi). La funzione max(nodo n) (nodo contenente valore massimo) e pred(nodo n) (predecessore di un nodo). Alberi AVL - definizione, fattore di bilanciamento di un nodo, albero bilanciato in altezza. Ricerca in un AVL (descrizione, codice ed analisi). Rotazioni di base. Ribilanciamento tramite rotazioni. Inserimento di un nuovo nodo. Cancellazione di un nodo. Costo delle operazioni su alberi AVL.
    - CAP 6. (6.1, 6.2). Slide del corso (pdf).
  • Lezione del 29-10-2014
    Esercitazione: ordinamento di stringhe utilizzando il RadixSort; verificare se tutte le foglie di un albero contengono valori pari.
    - SLIDE DEL CORSO - (pdf).
  • Lezione del 04-11-2014
    Tabelle di hash - Tabelle ad accesso diretto. Implementazione del tipo di dato Dizionario con tabelle ad accesso diretto. Costo delle operazioni di insert, delete e search. Fattore di carico. Pregi e difetti delle tabelle ad accesso diretto. Tabelle di hash. Funzione di hash. Problema delle collisioni. Funzioni di hash perfette. Implementazione del tipo di dato Dizionario con tabelle di hash che usa una funzione di hash perfetta. Costo delle operazioni di insert, delete e search. Uniformità semplice. Risoluzione delle collisioni: Lista di collisione e Indirizzamento Aperto Implementazione del tipo di dato Dizionario con tabelle di hash basate sulle liste di collisione e sull'indirizzamento aperto. Metodi di scansione: scansione lineare e hasing doppio. La cancellazione di elementi nell'indirizzamento aperto.
    - CAP 7. (7.1, 7.2, 7.3). Slide del corso (pdf).
  • Lezione del 05-11-2014
    Esercitazione: ripasso delle proprietà degli alberi di ricerca ed AVL. Costruzione di un albero AVL. Cancellazionedi un nodo da un albero AVL. Algoritmo di vistia simmetrica di un albero (algoritmo stampa-DFS-Sim), ordinamento utilizzando BST ed AVL.
    - SLIDE DEL CORSO - Esercitazione 5 (pdf).
  • Lezione del 18-11-2014
    Esercitazione: Alberi binari; Numero di nodi ad una porfondità K; MAX-HEAP e MIN-HEAP; Funzione per verificare se un array rappresenta un MIN-HEAP.
    - SLIDE DEL CORSO - Esercitazione 6 (pdf).
  • Lezione del 19-11-2014
    Esercitazione: Ripasso delle proprietà degli heap e le operazioni su questi definite. Esercitazione: cancellazione del massimo. Ordinamento in loco. Ordinare in loco mediante heap. La funzione insert per aggiungere un nuovo elemento ad un heap.
    - SLIDE DEL CORSO - Esercitazione 7 (pdf).
  • Lezione del 26-11-2014
    Definizione di grafo. Grafi orientati e non orientati. Adiacenza ed incidenza. Grado di un vertice. Cammini e cicli in un grafo. Connettività e connettività forte. Sottografi e sottografi indotti. Strutture dati per rappresentare grafi (orientati e non): liste di archi, liste di adiacenza, liste di incidenza, matrici di adiacenza, matrici di incidenza. Visite di grafi.
    - CAP 12. (12.1, 12.2). Slide del corso (pdf).
  • Lezione del 26-11-2014
    Algoritmo di visita generico (analisi e costo). Algoritmo per la visita in ampiezza (analisi e costo). Algoritmo per la visita in profondità (analisi e costo). Versione ricorsiva dell'algoritmo di visita in profondità Componenti connesse e fortemente connesse e loro calcolo.
    - CAP 12. (12.3, 12.4, 12.5). Slide del corso (pdf).
  • Lezione del 03-12-2014
    Esercitazione: visita in ampiezza di un grafo e visita in profondità di un grafo. Rappresentazione del grafo basata sulla matrice di adiacenza. L'algoritmo nodoMaxGrado.
    - SLIDE DEL CORSO - Esercitazione 8 (pdf).
  • Lezione del 09-12-2014
    Tecnica algoritmica golosa. Minimo albero ricoprente e problema del calcolo del minimo albero ricoprente. Approccio goloso alla risoluzione del problema. Definizione di tagio. Regola del taglio e regola del ciclo. Algoritmo di Kruskal. Algoritmo di Prim. Algoritmo di Boruvka.
    - CAP. 10 (10.3). CAP. 13 (13.1, 13.2 (escluso 13.2.1), 13.3 (escluso 13.3.1), 13.4). - Slide del corso (pdf).
  • Lezione del 10-12-2014
    Definizione di cammino minimo. Proprietà dei cammini minimi. Distanza tra vertici. Disuguaglianza triangolare e condizione di Bellman. Algoritmo per calcolare i cammini minimi date le distanze. Albero dei cammini minimi. Varianti del problema dei cammini minimi. Tecnica del rilassamento. Algoritmo generico per il calcolo delle distanze. Algoritmo di Bellman e Ford (descrizione, codice ed analisi). Ordinamento topologico. Algoritmo per calcolare i cammini minimi a sorgente singola per grafi aciclici (descrizione, codice ed analisi). Algoritmo di Dijkstra (descrizione, codice ed analisi).
    - CAP. 14 (14.1, 14.2, 14.3, 14.4, 14.5 (fino a 14.5.1 escluso)). Slide del corso (pdf).
  • Lezione del 16-12-2014
    Esercitazione: algoritmo di Kruskal; algoritmo di Prim; ordinamento topologico; distanze in un grafo aciclico; algoritmo di Dijkstra; esercizio: "il castello dei mostri".
    SLIDE DEL CORSO - Esercitazione 9 (pdf).