Diario delle lezioni

Ogni lezione è da 2 ore.

Totale:

• 24 lezioni (48 ore) per il modulo di teoria da 6 CFU.
• 2*12=24 lezioni (2*24 = 48 ore) per il modulo di Laboratorio da 3 CFU, sdoppiato in due canali (A[A-L] e B[M-Z])

26 settembre 2023 (Lezione di teoria n° 1)

• Presentazione del corso e delle modalità d’esame
• Richiami di programmazione strutturata
• Modelli di calcolo: Macchina di Turing e Random Access Machine

27 settembre 2023 (Lezione di teoria n° 2)

• Complessità di programmi
• Tipi riferimento definiti dall’utente
• Variabili e Oggetti in memoria
• Stack e Heap nei tipi riferimento

28 settembre 2023 (Lezioni di laboratorio n° A.1 e B.1)

• Tipi riferimento definiti dall’utente
• Array di tipi riferimento
• Array multidimensionali
• Esercizi

3 ottobre 2023 (Lezione di teoria n° 3)

• Tipi riferimento definiti ricorsivamente
• Garbage collector della JVM
• Strutture dati: introduzione alle liste
• Strutture dati: dizionari
• Strutture dati elementari: Pile con loro implementazione in Java

4 ottobre 2023 (Lezione di teoria n° 4)

• Strutture dati elementari: Code con loro implementazione in Java
• Alberi e loro rappresentazione in memoria
• Alberi binari di ricerca (parte prima)

5 ottobre 2023 (Lezioni di laboratorio n° A.2 e B.2)

• Implementazione di liste ordinate in Java (prima parte)

11 ottobre 2023 (Lezione di teoria n° 5)

• Alberi binari di ricerca (parte seconda)
• Heap per implementare code con priorità (prima parte)

12 ottobre 2023 (Lezioni di laboratorio n° A.3 e B.3)

• Esercizi su pile e code
• Implementazione di liste ordinate in Java (seconda parte)

17 ottobre 2023 (Lezione di teoria n° 6)

• Heap per implementare code con priorità (seconda parte)
• Heapsort (prima parte)

18 ottobre 2023 (Lezione di teoria n° 7)

• Heapsort (seconda parte)
• Introduzione alla programmazione orientata ad oggetti
• Incapsulamento
• Campi di istanza e campi di classe
• Metodi di istanza e campi di classe

19 ottobre 2023 (Lezioni di laboratorio n° A.4 e B.4)

• Implementazione di alberi binari di ricerca in Java (prima parte)

24 ottobre 2023 (Lezione di teoria n° 8)

• Costruttori e costruttore di default
• Parola chiave this
• Modificatori di accesso e Information hiding
• Metodi di accesso e di modifica
• Inizializzazione dei campi di istanza
• Modificator final e oggetti immutabili
• Classe String

25 ottobre 2023 (Lezione di teoria n° 9)

• Package e import
• Import di classi e metodi statici
• Introduzione ai Generics
• ArrayList
• Classi involucro

26 ottobre 2023 (Lezioni di laboratorio n° A.5 e B.5)

• Implementazione di alberi binari di ricerca in Java (seconda parte)
• Verifica sperimentale altezza media alberi binari di ricerca

31 ottobre 2023 (Lezione di teoria n° 10)

• Ereditarietà
• Costruttori di classi figlie e parola chiave super
• Modificatore di accesso “protected”
• Il polimorfismo: l’overriding
• Ereditarietà singola
• Modificatore final per metodi di istanza e per classi
• Gerarchia delle classi in Java: la classe Object
• Metodo toString
• Metodo equals: significato ed implementazione

2 novembre 2023 (Lezioni di laboratorio n° A.6 e B.6)

• Implementazione di Pile e Code in stile object oriented
• Java Generics: implementazione di Pile e Code di elementi
• Calcolo dell’altezza di un albero binario di ricerca in modo iterativo (sfruttando una coda di nodi)

7 novembre 2023 (Lezione di teoria n° 11)

• Possibili relazioni tra classi nella programmazione a oggetti
• Tipo statico e tipo dinamico di variabili di tipo riferimento
• Parola chiave var
• Selezione della firma con overriding e overloading

8 novembre 2023 (Lezione di teoria n° 12)

• Introduzione alle tabelle Hash: tabelle a indirizzamento diretto
• Tabelle Hash: Funzioni di hashing
• Hashing esterno con liste di trabocco
• Hashing interno: introduzione

9 novembre 2023 (Lezioni di laboratorio n° A.7 e B.7)

• Esercizi su programmazione a oggetti

14 novembre 2023 (Lezione di teoria n° 13)

• Hashing interno: ispezione lineare e hashing doppio
• Gestione delle cancellazioni nell’hashing interno
• Classi astratte e metodi astratti
• Esercizi su classi astratte

15 novembre 2023 (Lezione di teoria n° 14)

• Le interfacce
• Cenni a interfaccia Comparable e Iterable
• Esercizi su programmazione a oggetti, ereditarietà e classi astratte

21 novembre 2023 (Lezione di teoria n° 15)

• Le eccezioni in Java

22 novembre 2023 (Lezione di teoria n° 16)

• Introduzione alla programmazione dinamica

23 novembre 2023 (Lezioni di laboratorio n° A.8 e B.8)

• Esercizi su programmazione a oggetti, ereditarietà e classi astratte

28 novembre 2023 (Lezione di teoria n° 17)

• Il problema delle attività compatibili
• Algoritmi Greedy

29 novembre 2023 (Lezione di teoria n° 18)

• Grafi: introduzione e definizioni
• Implementazione di grafi tramite liste di adiacenza
• Implementazione di grafi tramite matrici di adiacenza
• Visita in ampiezza di grafi: introduzione e proprietà

29 novembre 2023 (Lezioni di laboratorio n° B.9)

• Esercizi su programmazione a oggetti, ereditarietà e classi astratte

30 novembre 2023 (Lezioni di laboratorio n° A.9)

• Esercizi su programmazione a oggetti, ereditarietà e classi astratte

5 dicembre 2023 (Lezione di teoria n° 19)

• Applicazione della visita in ampiezza: implementazione
• Visita in profondità di grafi: analisi e proprietà
• Applicazione della visita in profondità: Verifica di ciclicità

6 dicembre 2023 (Lezione di teoria n° 20)

• Applicazione della visita in profondità: Ordinamento topologico di un DAG
• Versione ricorsiva ed iterativa della visita in profondità
• Problema del minimo albero ricoprente (MST)
• Algoritmo di Kruskal
• Analisi di complessità dell’algoritmo di Kruskal secondo diverse implementazioni

7 dicembre 2023 (Lezioni di laboratorio n° A.10 e B.10)

Lab Progr Alg 2 - A-L - 7_12_2023-20231207_111338-Registrazione della riunione.mp4

Lab Progr2 - M-Z - 7_12_2023-20231207_142046-Registrazione della riunione.mp4

• Correzione dell’esonero
• Assegnazione del progetto
• Implementazione di liste di Generics con interfacce Iterable e Iterator
• Classe HashMap con esempi di utilizzo

12 dicembre 2023 (Lezione di teoria n° 21)

• Algoritmo di Prim e sua analisi di complessità
• Dimostrazione di correttezza algoritmi di Prim e Kruskal
• Problema dei cammini minimi da singola sorgente

14 dicembre 2023 (Lezioni di laboratorio n° A.11 e B.11)

• Lettura e scrittura di file di testo in Java
• Lettura e scrittura di file di binari in Java: interfaccia Serializable
• Esercizi su programmazione a oggetti
• Java Generics: type erasure
• Invarianza dei Generics e Covarianza degli Array
• Array di Generics: problematicità
• Java Generics: metodi generici
• Java Generics: Wildcards e wildcards bounded

18 dicembre 2023 (Lezione di teoria n° 22)

• Algoritmo di Dijkstra e sua analisi di complessità
• Algoritmo di Bellmann-Ford e sua analisi di complessità

19 dicembre 2023 (Lezione di teoria n° 23)

• Problema dei cammini minimi tra tutte le coppie di nodi
• Algoritmo di Floyd-Warshall e sua analisi di complessità
• Esercizio sull’algoritmo di Floyd-Warshall

20 dicembre 2023 (Lezione di teoria n° 24)

• Esercizi in preparazione all’esame

21 dicembre 2023 (Lezioni di laboratorio n° A.12 e B.12)

• Esercizi in preparazione all’esame