Elenco Lezioni, Argomenti e Riferimenti
|
Presentazione del corso.
Introduzione all'informatica e centralità del concetto di algoritmo: alcuni esempi. |
||
| Lezione non tenuta. | ||
|
Ripresa del concetto di algoritmo: alcuni esempi.
Lucidi |
||
|
Cenni allo stato, alle variabili e alla memoria. Concetti di base della programmazione in C: stato, espressioni, assegnamento, input, output, istruzioni di controllo condizionali e ripetitive.
Lucidi |
||
|
Introduzione a UNIX (storia e caratteristiche). Accenni alla struttura del file system. Cosa è la shell. Rassegna sui principali comandi UNIX.
Lucidi Introduzione alla programmazione in C: panoramica del linguaggio e istruzioni per l'uso. Struttura di un programma C. Dal sorgente all'eseguibile: in particolare preprocessing e compilazione. I passi della compilazione (GCC) [Vedi Link utili]. Errori di compilazione e a run time. Lucidi Lucidi |
||
|
Esercitazione in laboratorio sulla shell: esercizi in fondo ai
lucidi visti lunedì.
I primi esercizi di C. |
||
|
Editare, compilare, ed eseguire programmi C sulla Shell. Il primo programma in C: "Ciao mondo!". Tipo di dato primitivi e comandi condizionali in C.
Lucidi |
||
|
Ripresa dei concetti di base della programmazione. Alcuni esempi di algoritmi.
Lucidi |
||
|
Introduzione al C e alla sua sintassi: tipi di dato in C, ovvero int, char, float, double; signed/unsigned/long. Conversioni di tipo. Funzioni di input e di output: printf e scanf.
Lucidi |
||
Esercitazione su variabili, tipi primitivi, e costrutti condizionali.
|
||
|
Esercitazione su istruzioni condizionali e istruzioni iterative.
Lucidi |
||
| Lezione non effettuata a causa della sospensione delle lezioni concessa al fine di permettere agli studenti la partecipazione alle attività collegate all'Internet Festival. | ||
|
Introduzione al C e alla sua sintassi: istruzioni iterative e array.
Lucidi Esercitazione su istruzioni iterative e array. Schemi ricorrenti di programmi. Lucidi |
||
Esercitazione su costrutti iterativi e array.
|
||
|
Breve introduzione alla semantica operazionale.
Lucidi |
||
|
Definizione di Algoritmo. Efficienza di Algoritmi: complessità in tempo, limiti inferiori. Il problema delle dodici monete.
Problema delle 12 monete tratto dal libro di Fabrizio Luccio: La struttura degli algoritmi. Boringhieri, 1984. |
||
|
Introduzione al C e alla sua sintassi: funzioni, regole di visibilità.
Lucidi |
||
Esercitazione su istruzioni iterative, array e funzioni.
|
||
| Insertion sort come esempio di algoritmo di ordinamento: complessità al caso ottimo, al caso pessimo, e al caso medio; dimostrazione di correttezza (Vedi Cap1, e Cap 2 sezioni 2.1 e 2.2 del [Cormen, Leiserson, Rivest, Stein. "Introduzione agli algoritmi e strutture dati"]). | ||
|
Introduzione al C e alla sua sintassi: regole di visibilità e gestione della memoria con i record di attivazione;
puntatori, passaggio dei parametri per indirizzo nelle funzioni, tramite puntatori; passaggio di array e matrici come parametri.
Lucidi |
||
|
Introduzione ai linguaggi regolari e agli automi: Automi a Stati Finiti Deterministici. [Automi, linguaggi e calcolabilità, J. E. Hopcroft, R. Motwani, J. D. Ullman: Cap. 1, Sezione 5, Cap. 2, Sezione 1 e 2]
Lucidi |
||
Esercitazione sui puntatori.
|
||
|
Introduzione ai linguaggi regolari e agli automi: Automi a Stati Finiti Non Deterministici. [Automi, linguaggi e calcolabilità, J. E. Hopcroft, R. Motwani, and J. D. Ullman: Cap. 1, Sezione 5, Cap. 2, Sezione 3 e 4]
Lucidi |
||
| Sospensione della didattica dei corsi di studio in Matematica. | ||
|
Introduzione al C e alla sua sintassi: ricorsione.
Lucidi |
||
|
Esercitazione sulla ricorsione.
esercizi di C non corretti dalla piattaforma di valutazione. |
||
|
Schemi ricorrenti di programmi: ricerca certa e incerta.
Verifica di proprietà con diversi quantificatori in cicli annidati.
Esercitazione su istruzioni iterative e array.
Lucidi Selection Sort. Ordinamento di un vettore booleano. Ricerca binaria. |
||
|
Esercitazione sugli automi.
Alcune proprietà di chiusura dei linguaggi regolari: unione, intersezione e complemento. [Automi, linguaggi e calcolabilità, J. E. Hopcroft, R. Motwani, and J. D. Ullman: 4.2.1] Esempio di dimostrazione sul fatto che un certo automa riconosce un linguaggio dato. [Automi, linguaggi e calcolabilità, J. E. Hopcroft, R. Motwani, and J. D. Ullman: 2.3.4, Esempio 2.9] |
||
|
I prova di verifica intermedia.
|
||
Esercitazione su tipi definiti dall'utente e su struct.
|
||
| Introduzione ai linguaggi regolari e agli automi: Automi a Stati Finiti Non Deterministici con epsilon-transizioni. Espressioni regolari. Equivalenza di automi ed espressioni regolari. [Automi, linguaggi e calcolabilità, J. E. Hopcroft, R. Motwani, and J. D. Ullman: Cap. 2, Sezione 5, Cap. 3, Sezioni 1 e 2 (escluso 3.2.1)] Lucidi | ||
| Notazione asintotica per le funzioni di complessità. Notazioni O, Omega, o, Theta, e omega: definizioni, proprietà algebriche | ||
|
Introduzione al C e alla sua sintassi: allocazione dinamica della memoria e introduzione alle liste collegate
Lucidi |
||
Esercitazione su liste collegate e allocazione dinamica della memoria.
|
||
| Paradigma Divide et Impera. Min-Max e Power iterative e ricorsive. MergeSort: descrizione, esempio. | ||
| Introduzione al C e alla sua sintassi: ripasso struct e liste. | ||
|
Introduzione ai linguaggi regolari e agli automi: dalle espressioni regolari agli automi con epsilon-transizioni.
Applicazioni delle espressioni regolari. Proprietà algebriche delle espressioni regolari.
Pumping Lemma ed esempi di applicazione.
[Automi, linguaggi e calcolabilità, J. E. Hopcroft, R. Motwani, and J. D. Ullman: Cap. 3, Sezioni 2, 3, 4]
Lucidi
|
||
Esercitazione ancora su liste collegate e allocazione dinamica della memoria.
|
||
| Complessità di MergeSort: metodo di sostituzione, e metodo con albero di ricorsione. QuickSort: codice, esempi, complessità. Lower bound nlogn per sorting basato su confronti. | ||
|
Introduzione ai linguaggi regolari e agli automi: proprietà di chiusura dei linguaggi regolari, problemi di decisioni, equivalenza e minimizzazione di automi.
[Automi, linguaggi e calcolabilità, J. E. Hopcroft, R. Motwani, and J. D. Ullman: Cap. 4, Sezioni 2, 3, 4]
Lucidi |
||
|
Introduzione ai linguaggi liberi: linguaggi e grammatiche libere dal contesto (I parte).
[Automi, linguaggi e calcolabilità, J. E. Hopcroft, R. Motwani, and J. D. Ullman: Cap. 5, Sezione 1, Inizio Sezione 2]
Lucidi |
||
Ancora esercitazione su liste collegate.
|
||
|
Introduzione ai linguaggiliberi: linguaggi e grammatiche libere dal contesto (II parte).
[Automi, linguaggi e calcolabilità, J. E. Hopcroft, R. Motwani, and J. D. Ullman: Cap. 5, Sezione 1, Sezioni 2 e 4]
Lucidi |
||
|
Introduzione al C e alla sua sintassi: gli alberi binari e la loro rappresentazione collegata in C. Visite di alberi. Esempi di soluzioni ricorsive a problemi su alberi. Cenni agli alberi binari di ricerca.
Lucidi |
||
|
Introduzione ai linguaggi liberi: proprietà dei linguaggi liberi dal contesto. Forma Normale di Chomsky. Pumping lemma per i linguaggi liberi. Proprietà di chiusura dei linguaggi. Cenni ai problemi di decisione. Accenni alla gerarchia di Chomsky.
[Automi, linguaggi e calcolabilità, J. E. Hopcroft, R. Motwani, and J. D. Ullman: Cap. 7, Sezioni 1, 2 e 3]
Lucidi |
||
Esercitazione sugli alberi.
|
||
| Esercitazione in vista della seconda prova di verifica. | ||
| Esercitazione in vista della seconda prova di verifica. | ||
|
II prova di verifica.
|