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

Scopri cosa vuol dire essere dell'Ud'A

SEDE DI CHIETI
Via dei Vestini,31
Centralino 0871.3551

SEDE DI PESCARA
Viale Pindaro,42
Centralino 085.45371

email: info@unich.it
PEC: ateneo@pec.unich.it
Partita IVA 01335970693

icona Facebook   icona Twitter

icona Youtube   icona Instagram