Diario delle lezioni

Ogni lezione è da 2 ore.

Totale: 36 lezioni (72 ore) per 9 CFU.

 

18 settembre 2017 (Lezione n° 1)

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

19 settembre 2017 (Lezione n° 2)

• Problema / Algoritmo / Programma
• Pseudo-codice per la descrizione di algoritmi
• Correttezza ed efficienza
• Modelli di calcolo: macchina di Turing e RAM
• Notazioni asintotiche
• Complessità di problemi e di algoritmi

20 settembre 2017 (Lezione n° 3)

• Stima di complessità nel caso migliore, peggiore, medio
• Analisi di complessità dell’Insertion Sort
• Le invarianti come strumento per dimostrare la correttezza di algoritmi
• Dimostrazione di correttezza dell’Insertion Sort (tecnica dell’invariante di ciclo)

25 settembre 2017 (Lezione n° 4)

• Tecnica del Divide et impera
• Merge sort: analisi di correttezza e di complessità
• Risoluzione di ricorrenze tramite albero delle chiamate ricorsive

2 ottobre 2017 (Lezione n° 5)

• Tecnica dell’invariante di ciclo per la correttezza di Selection-Sort
• Risoluzione di ricorrenze tramite sostituzione
• Dimostrazione per induzione applicata alla soluzione di ricorrenze
• Risoluzione di ricorrenze tramite il metodo dell’esperto

3 ottobre 2017 (Lezione n° 6)

• Metodo dell’esperto: esercizi
• Quick-sort: analisi di complessità nel caso migliore, peggiore e medio
• Lower bound al problema dell’ordinamento risolto tramite algoritmi basati su confronti

4 ottobre 2017 (Lezione n° 7)

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

9 ottobre 2017 (Lezione n° 8)

• Counting sort
• Radix sort
• Introduzione alle strutture dati per i dizionari

11 ottobre 2017 (Lezione n° 9)

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

16 ottobre 2017 (Lezione n° 10)

• Pile
• Code
• Liste

17 ottobre 2017 (Lezione n° 11)

• Liste (cancellazione di elementi)
• Alberi
• Alberi binari di ricerca: introduzione

18 ottobre 2017 (Lezione n° 12)

• Implementazione in Java di alberi binari di ricerca (prima parte)
• Inserimento di nodi in alberi binari di ricerca
• Alberi binari di ricerca costruiti in modo casuale: valutazione altezza media

23 ottobre 2017 (Lezione n° 13)

• Cancellazione di nodi in alberi binari di ricerca
• Introduzioni all’Heap
• Rappresentazione di un albero binario quasi completo tramite array
• Procedura Heapify

24 ottobre 2017 (Lezione n° 14)

• Code con priorità implementate tramite heap
• Inserimento ed estrazione di chiavi
• Heap-sort

25 ottobre 2017 (Lezione n° 15)

• Analisi della complessità della procedura build-Heap
• Implementazione in Java di alberi binari di ricerca (seconda parte)

26 ottobre 2017 (Lezione n° 16)

• Implementazione in Java di Heap (code con priorità)
• Implementazione in Java dell’algoritmo heap-sort
• Ricerca lineare
• Ricerca binaria (iterativa e ricorsiva)
• Esercizi

30 ottobre 2017 (Lezione n° 17)

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

31 ottobre 2017 (Lezione n° 18)

• Esercizi su notazioni asintotiche
• Esercizi su progettazione di algoritmi
• Esercizi su algoritmi di ordinamento e ricerca
• Ricerca binaria ricorsiva: stima della complessità con sostituzione e induzione

6 novembre 2017 (Lezione n° 19)

• Esercizi su Notazioni asintotiche e stime di ricorrenze
• Esercizi su algoritmi di ordinamento
• Esercizi su strutture dati dinamiche

7 novembre 2017 (Lezione n° 20)

• Esercizi su Notazioni asintotiche e stime di ricorrenze
• Esercizi su algoritmi di ordinamento
• Esercizi su strutture dati dinamiche

8 novembre 2017 (Lezione n° 21)

• Implementazione in Java di Liste
• Implementazione in Java di Tabelle Hash con liste di trabocco
• Implementazione in Java di Tabelle Hash con indirizzamento aperto (prima parte)

13 novembre 2017 (Lezione n° 22)

• Programmazione dinamica: progettazione algoritmi

14 novembre 2017 (Lezione n° 23)

• Algoritmi greedy: progettazione
• Esercizi su programmazione dinamica

20 novembre 2017 (Lezione n° 24)

• Grafi: definizioni
• Rappresentazione di grafi mediante liste di adiacenza
• Rappresentazione di grafi mediante matrice di adiacenza
• Visita in ampiezza di grafi: analisi e proprietà

21 novembre 2017 (Lezione n° 25)

• Visita in profondità di grafi: analisi e proprietà.
• Ordinamento topologico di un DAG.
• Esercizi su grafi.

22 novembre 2017 (Lezione n° 26)

• Implementazione in Java di Tabelle Hash con indirizzamento aperto (seconda parte)

23 novembre 2017 (Lezione n° 27)

• Implementazione in Java di Grafi con liste di adicenza
• Implementazione in Java dell’algoritmo di visita in ampiezza

27 novembre 2017 (Lezione n° 28)

• Problema del minimo albero ricoprente (MST).
• Schema di algoritmi per MST e sua dimostrazione di ottimalità.
• Algoritmo di Kruskal (parte prima)

28 novembre 2017 (Lezione n° 29)

• 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 (prima parte): introduzione

29 novembre 2017 (Lezione n° 30)

• Implementazione in Java di Grafi pesati con liste di adicenza
• Implementazione in Java dell’algoritmo di Kruskal

4 dicembre 2017 (Lezione n° 31)

• Algoritmo di Dijkstra (seconda parte): correttezza e complessità
• Implementazione dell’algoritmo di Dijkstra tramite liste e heap di minimo.
• Algoritmo di Bellman-Ford

5 dicembre 2017 (Lezione n° 32)

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

6 dicembre 2017 (Lezione n° 33)

• Java generics
• Presentazione preliminare del progetto

11 dicembre 2017 (Lezione n° 34)

• Esercizi

12 dicembre 2017 (Lezione n° 35)

• Esercizi

13 dicembre 2017 (Lezione n° 36)

• Input e output su file in Java
• Esercizi