Diario delle lezioni

Ogni lezione è da 2 ore.

Totale:

• 24 lezioni (48 ore) per un totale di 6 CFU

24 settembre 2018 (Lezione di teoria n° 1)

• Presentazione del corso e delle modalità d’esame
• Problema / algoritmo / programma
• Concetto di correttezza e di efficienza di un algoritmo
• Linguaggi di alto livello
• Compilatore ed Interprete
• Linguaggio macchina

25 settembre 2018 (Lezione di teoria n° 2)

• Paradigmi di programmazione
• Commenti in Java
• Variabili, tipi, identificatori
• Tipi primitivi del Java

1° ottobre 2018 (Lezione di teoria n° 3)

• Dichiarazione, Inizializzazione ed assegnazione di variabili
• Lo stack di memoria
• Sintassi e semantica dei linguaggi di programmazione
• Espressioni ed effetti collaterali
• Operatori per tipi numerici

2 ottobre 2018 (Lezione di teoria n° 4)

• Espressioni booleane
• Operatori relazionali
• Operatori booleani
• Leggi di De Morgan
• Programmazione strutturata
• Comando if e If…else
• Comando vuoto
• Comando blocco

8 ottobre 2018 (Lezione di teoria n° 5)

• I diagrammi di flusso
• Esercizi su diagrammi di flusso
• Comando while e suo diagramma di flusso strutturato
• Programmazione strutturata versus programmazione con salti
• Comando do…while e suo diagramma di flusso strutturato

9 ottobre 2018 (Lezione di teoria n° 6)

• Equivalenza comandi while e do…while
• Introduzione agli array
• Tipi primitivi vs tipi riferimento
• Stack e Heap
• Array monodimensionali: dichiarazione, creazione, accesso

15 ottobre 2018 (Lezione di teoria n° 7)

• Array multidimensionali
• Comando for (introduzione)

16 ottobre 2018 (Lezione di teoria n° 8)

• Equivalenza tra comandi while, do…while e for
• Comando for each
• Comando switch e comando break
• Comandi etichettati
• Comando break
• Comando continue
• Espressione condizionale
• Modificatore final per le costanti

22 ottobre 2018 (Lezione di teoria n° 9)

• Metodi
• Parametri formali e Parametri attuali
• Parametri di tipo primitivo e di tipo riferimento
• Stack e Heap nella chiamata dei metodi
• Simulazione programmi con Stack e Heap

23 ottobre 2018 (Lezione di teoria n° 10)

• Overloading di metodi
• Firma dei metodi
• Ricorsione
• Esercizio: fattoriale (versione ricorsiva ed iterativa)

29 ottobre 2018 (Lezione di teoria n° 11)

• Albero delle chiamate ricorsive
• Esercizi sulla ricorsione
• Array e ricorsione

30 ottobre 2018 (Lezione di teoria n° 12)

• Esercizi su programmi iterativi

5 novembre 2018 (Lezione di teoria n° 13)

• Esercizi su cicli, array e metodi

6 novembre 2018 (Lezione di teoria n° 14)

• Esercizi su cicli, array e metodi

12 novembre 2018 (Lezione di teoria n° 15)

• Correttezza ed efficienza
• Modelli di calcolo: macchina di Turing e RAM
• Tesi di Church
• Teorema di Böhm-Jacopini
• Notazioni asintotiche

13 novembre 2018 (Lezione di teoria n° 16)

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

20 novembre 2018 (Lezione di teoria n° 17)

• Tecnica del divide et impera
• Risoluzione di ricorrenze tramite sostituzione
• Dimostrazione per induzione applicata alla soluzione di ricorrenze
• Merge-Sort
• Analisi di complessità del Merge-Sort

26 novembre 2018 (Lezione di teoria n° 18)

• Teorema generale per la soluzione esplicita di ricorrenze
• Lower bound alla complessità del problema dell’ordinamento risolto con algoritmi basati su confronti

27 novembre 2018 (Lezione di teoria n° 19)

• Quick-Sort
• Counting-Sort
• Radix-Sort

3 dicembre 2018 (Lezione di teoria n° 20)

• Alberi
• Alberi binari di ricerca (prima parte)

10 dicembre 2018 (Lezione di teoria n° 21)

• Heap
• Code con priorità

11 dicembre 2018 (Lezione di teoria n° 22)

• Heap-Sort
• Ricerca lineare e ricerca binaria
• Esercizi

17 dicembre 2018 (Lezione di teoria n° 23)

• Esercizi

18 dicembre 2018 (Lezione di teoria n° 24)

• Esercizi