Diario delle lezioni

Ogni lezione è da 2 ore.

Totale: 24 lezioni (2*24 = 48 ore) per 6 CFU.

25 settembre 2018 (Lezione n° 1)

• Presentazione del corso
• Problema / Algoritmo / Programma
• Concetto di algoritmo
• Corrispondenza tra algoritmi e numeri naturali
• Enumerazione
• Convergenza/Divergenza
• Esistenza di funzioni matematiche non calcolabili
• Halting problem

26 settembre 2018 (Lezione n° 2)

• Pseudo-codice per la descrizione di algoritmi
• Correttezza ed efficienza
• Modelli di calcolo: macchina di Turing e RAM
• Tesi di Church
• Teorema di Böhm-Jacopini
• Esempio di analisi di complressità e introduzione a caso migliore e peggiore: Insertion Sort

2 ottobre 2018 (Lezione n° 3)

• Notazioni asintotiche
• Complessità di problemi e di algoritmi
• Stima di complessità nel caso migliore, peggiore, medio
• Analisi di complessità dell’Insertion Sort

3 ottobre 2018 (Lezione n° 4)

• Le invarianti come strumento per dimostrare la correttezza di algoritmi
• Dimostrazione di correttezza dell’Insertion-Sort (tecnica dell’invariante di ciclo)
• Tecnica del Divide et impera
• Merge-Sort: descrizione dell’algoritmo

4 ottobre 2018 (Lezione n° 5)

• Implementazione in Java di algoritmi di ordinamento (Insertion-Sort, Merge-Sort)
• Analisi euristica delle loro prestazioni (parte prima)

9 ottobre 2018 (Lezione n° 6)

• Merge sort: analisi di correttezza e di complessità
• Risoluzione di ricorrenze tramite albero delle chiamate ricorsive
• Risoluzione di ricorrenze tramite sostituzione
• Dimostrazione per induzione applicata alla soluzione di ricorrenze

11 ottobre 2018 (Lezione n° 7)

• Analisi euristica delle prestazioni di Insertion-Sort e Merge-Sort (parte seconda)
• Risoluzione di ricorrenze tramite il metodo dell’esperto
• Lower bound al problema dell’ordinamento risolto tramite algoritmi basati su confronti

16 ottobre 2018 (Lezione n° 8)

• Quick-sort: analisi di complessità nel caso migliore, peggiore e medio
• Counting sort

17 ottobre 2018 (Lezione n° 9)

• Counting sort (analisi di complessità)
• Radix sort
• Introduzione alle strutture dati per i dizionari
• Pile (prima parte)

18 ottobre 2018 (Lezione n° 10)

• Implementazione in Java di algoritmi di ordinamento (Counting-Sort e Radix-Sort)
• Analisi euristica delle loro prestazioni

23 ottobre 2018 (Lezione n° 11)

• Pile (seconda parte)
• Code
• Liste (prima parte)

24 ottobre 2018 (Lezione n° 12)

• Liste (seconda parte)
• Alberi
• Alberi binari di ricerca (prima parte)

25 ottobre 2018 (Lezione n° 13)

• Alberi binari di ricerca (seconda parte)
• Heap (prima parte)

30 ottobre 2018 (Lezione n° 14)

• Heap (seconda parte)
• Heap Sort

31 ottobre 2018 (Lezione n° 15)

• Tabelle a indirizzamento diretto
• Tabelle Hash: liste di trabocco
• Tabelle Hash: indirizzamento aperto con ispezione lineare
• Fattore di carico e ridimensionamento della tabella Hash
• Complessità temporale delle operazioni di inserimento, ricerca e cancellazione

6 novembre 2018 (Lezione n° 16)

• Tabelle Hash: Hashing doppio
• Esercizi su strutture dati

7 novembre 2018 (Lezione n° 17)

• Ricerca binaria ricorsiva e sua analisi di complessità con il teorema generale e con il metodo di sostituzione e induzione
• Esercizi su tecnica divide et impera
• Esercizi su algoritmi di ordinamento e di ricerca

8 novembre 2018 (Lezione n° 18)

• Implementazione in Java di Heap
• Implementazione in Java di Heap-Sort e confronto delle sue prestazioni con Merge-Sort
• Implementazione in Java di tabelle Hash (prima parte)

13 novembre 2018 (Lezione n° 19)

• Programmazione dinamica: progettazione di algoritmi
• Algoritmi greedy (prima parte)

14 novembre 2018 (Lezione n° 20)

• Algoritmi greedy (seconda parte)
• Esercizi su programmazione dinamica
• Grafi: introduzione
• Rappresentazione di grafi con liste di adiacenza e matrice di adiacenza

15 novembre 2018 (Lezione n° 21)

• Implementazione in Java di tabelle Hash (seconda parte)

20 novembre 2018 (Lezione n° 22)

• Visita in ampiezza di grafi: analisi e proprietà
• Visita in profondità di grafi: analisi e proprietà
• Ordinamento topologico di un DAG.
• Problema del minimo albero ricoprente (MST).
• Algoritmo di Kruskal (parte prima)

21 novembre 2018 (Lezione n° 23)

• Algoritmo di Kruskal (parte seconda)
• Analisi di complessità dell’algoritmo di Kruskal secondo diverse implementazioni
• Algoritmo di Prim
• Analisi di complessità dell’algoritmo di Prim secondo diverse implementazioni
• Problema dei cammini minimi da singola sorgente
• Algoritmo di Dijkstra
• Implementazione dell’algoritmo di Dijkstra tramite liste e heap di minimo.

29 novembre 2018 (Lezione n° 24)

• Algoritmo di Bellman-Ford
• Cammini minimi tra tutte le coppie
• Algoritmo di Floyd-Warshall