Diario delle lezioni

Dettaglio degli argomenti svolti durante le lezioni.

  • Lezione del 29-09-2014
    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).
    CAP. 1 (fino a 1.6 (incluso), escluse le dimostrazioni).
  • Lezione del 30-09-2014
    Algoritmo con complessità logaritmica basato sulle matrici per il calcolo dei numeri di Fibonacci e sua relazione di ricorrenza. Primo esempio di utilizzo del metodo iterativo per il calcolo della complessità. 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.
    CAP. 1 (da 1.7 in poi). CAP. 2 (da 2.1 fino a 2.5.2 compreso).
  • Lezione del 06-10-2014
    Tecnica del divide et impera e relazione di ricorrenza di algoritmi che adottano tale tecnica. Master Theorem e sua applicabilità (esempi). 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. Visite di alberi. Algoritmo iterativo di visita in profondità. Algoritmo ricorsivo di visita in profondità. Algoritmo di visita in ampiezza.
    CAP. 3 (esclusi: "tecnica del raddoppiamento-dimezzamento" e dimostrazione del teorema 3.2).
  • Lezione del 07-10-2014
    Implementazione del tipo di dato Pila utilizzando un array 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 Pila utilizzando una lista semplice ed implementazione delle sue operazioni. Algoritmo per verificare se le parentesi in una stringa sono bilanciate. Algoritmo per il calcolo della profondità di un albero binario. Algoritmo per contare le foglie di un albero binario.
    SLIDE DEL CORSO - Strutture dati elementari - Esercitazione.
  • Lezione del 13-10-2014
    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).
    CAP 4. (4.2, 4.3) SLIDE DEL CORSO - Ordinamento.
  • Lezione del 14-10-2014
    Esercitazione: implementazione del tipo di dato Pila utilizzando una lista semplice ed implementazione delle sue operazioni; esercizio sugli heap, il problema della "moneta più leggera". 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.
    SLIDE DEL CORSO - Esercitazione 2. CAP 4. (4.4, 4.5, 4.1) SLIDE DEL CORSO - Ordinamento.
  • Lezione del 20-10-2014
    Ordinamenti lineari: IntegerSort (descrizione, codice e analisi), BucketSort, Proprietà di stabilità, RadixSort (descrizione ed analisi).
    CAP 4. (4.6, 4.7) SLIDE DEL CORSO - Ordinamento.
  • Lezione del 21-10-2014
    Esercitazione: ordinamento di stringhe utilizzando il RadixSort; verificare se tutte le foglie di un albero contengono valori pari.
    SLIDE DEL CORSO - Esercitazione 3.
  • Lezione del 27-10-2014
    Alberi di ricerca (Binary Search Tree -- BST). Ricerca, inserimento e cancellazione in un BST (descrizione, pseudocodice ed analisi). La funzione max(nodo n) e pred(nodo n) (predecessore di un nodo). Alberi AVL -- nozioni introduttive: definizione, fattore di bilanciamento di un nodo, albero bilanciato in altezza. Ricerca in un AVL (descrizione, codice ed analisi).
    CAP 6. (6.1, 6.2 - fino a 6.2.1 incluso)
  • Lezione del 03-11-2014
    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.2)
  • Lezione del 04-11-2014
    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), costruzione di alberi AVL, ordinamento utilizzando BST ed AVL.
    SLIDE DEL CORSO - Esercitazione 4.
  • Lezione del 10-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, )
  • Lezione del 11-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 5.
  • Lezione del 17-11-2014
    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 6.
  • Lezione del 18-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 - Grafi e visite di grafi.
  • Lezione del 24-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 - Grafi e visite di grafi.
  • Lezione del 25-11-2014
    Esercitazione: visita in ampiezza di un grafo, visita in profondità di un grafo. L'algoritmo nodoMaxGrado, l'esercizio "amici di amici"
    SLIDE DEL CORSO - Esercitazione 7.
  • Lezione del 01-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 - Minimo albero ricoprente.
  • Lezione del 15-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))
  • Lezione del 16-12-2014
    Esercitazione: algoritmo di Kruskal; algoritmo di Prim; ordinamento topologico; distanze in un grafo aciclico; l'algoritmo di Dijkstra; esercizio: "il castello dei mostri".
    SLIDE DEL CORSO - Esercitazione 8.