Informatica 3
Il corso di Informatica 3 viene svolto, quest'anno, in tre sezioni (Proff. Agosta, Campi e Matera). I contenuti del corso sono gli stessi per le tre sezioni, e la parte scritta dell'esame viene svolta su testi comuni.
Il corso si divide in due parti, all'incirca di dimensioni uguali: la prima tratta i linguaggi di programmazione e i relativi criteri di progetto, mentre la seconda affronta il tema della progettazione di algoritmi e strutture dati efficienti.
Il corso è composto da 30 ore di lezione e 20 di esercitazione. Il responsabile delle esercitazioni per questa sezione è l'ing. Gerardo Pelosi.
Programma del corso: Linguaggi di Programmazione
- I linguaggi di programmazione: concetti generali e classificazioni fondamentali; cenni storici
- Sintassi e semantica
- La struttura dei dati
- La struttura di controllo
- Modularizzazione
- Linguaggi orientati agli oggetti
- Cenni ai linguaggi Interpretati
Programma del corso: Algoritmi e Strutture Dati
- Introduzione alla complessità del calcolo
- La notazione “Theta-grande”
- La realizzazione di tipi astratti di dati in Java
- Strutture dati e algoritmi fondamentali
- Algoritmi di ricerca e ordinamento
- Alberi e loro gestione
- Realizzazione mediante puntatori
- Alberi binari
- Algoritmi di visita e gestione
- B-trees
- Grafi, loro rappresentazione e gestione
- Pile, code e tabelle hash
- Applicazioni di elaborazioni numeriche e simboliche: a scelta e a rotazione alcuni tra: string matching, compressione dei dati, crittografia (cenni), moltiplicazione tra matrici, trasformata veloce di Fourier (FFT)
Materiale didattico
Per il corso di Informatica 3, si adottano formalmente due libri di testo:
- Per la prima parte: Ghezzi C., Jazayeri M.: Programming language concepts, 4th edition, John Wiley & Sons, 2002.
- Per la seconda parte: C.A.Shaffer: A practical Introduction to data structures and algorithm analysis.
Lo Shaffer è sostituibile con T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduzione agli algoritmi e strutture dati 2/ed. Questo secondo testo rimane utile anche al di fuori del corso come testo di riferimento, ed ha un'impostazione più vicina a quella seguita da me a lezione. L'altra faccia della medaglia è che si tratta di un testo più complesso, con un'impostazione matematica più formale.
Potete inoltre fare riferimento alle slide usate nelle altre sezioni del corso, e, per la seconda parte, al materiale associato al libro di testo.
Per finire, il classico libro di David Harel, “Algorithmics: The Spirit of Computing”, fornisce una introduzione meno traumatica ai concetti visti nel corso.
Python
A lezione, gli algoritmi vengono presentati, invece che in pseudo-codice o in C++/Java, in Python (al contrario, Java viene usato nelle esercitazioni). Potete (e dovete, dato che la programmazione Python è argomento d'esame) scaricare l'interprete Python dal link qui sopra, sia per Linux che per Windows. Se usate Linux, quasi certamente l'interprete è già presente nel sistema.
Per avvicinarsi a Python, è possibile avvalersi di vari testi liberamente disponibili in formato pdf o html, fra cui:
- Mark Pilgrim, Dive Into Python: molto completo;
- Allen B. Downey, Jeffrey Elkner and Chris Meyers How to Think Like a Computer Scientist - Learning with Python: testo introduttivo alla programmazione, va bene se avete bisogno di un ripasso dei concetti fondamentali di programmazione;
- Bruce Eckel, Thinking in Python: questo non è un testo introduttivo; si tratta della version Python del classico Thinking in Java.
Il programma in dettaglio
Qui trovate il programma dettagliato del corso. Le note allegate alle lezioni future fanno riferimento al programma 2008/2009, e potranno subire (lievi) cambiamenti.
| Argomento | Data | Tipo |
|---|---|---|
| Sintassi e semantica | 30/9 | L |
| Chiamate a funzione | 5/10 | L |
| Python | 7/10 | L |
| Semantica operazionale | 12/10 | E |
| Concorrenza e Threading | 14/10 | L |
| Threading & Mutua Esclusione | 19/10 | L |
| Parallelismo e Threading | 21/10 | E |
| Liste, pile e code | 26/10 | L |
| Iteratori, generatori e coroutine | 28/10 | L |
| Complessità | 2/11 | L |
| Notazioni O, Ω e Θ | 4/11 | L |
| Induzione e ricorrenze | 9/11 | L |
| Algoritmi di ordinamento | 11/11 | L |
| Algoritmi di ordinamento | 23/11 | E |
| Alberi Binari, parte 1 | 25/11 | L |
| Alberi Binari, Binary Search Tree | 30/11 | L |
| Alberi | 2/12 | E |
| Seminario: algoritmi paralleli su schede video NVIDIA | 9/12 | S |
| Heap | 14/12 | L |
| B-Tree | 16/12 | L |
| B-Tree | 21/12 | E |
| Grafi | 11/01 | L |
| Grafi | 13/01 | E |
| Hash & Huffman code | 18/01 | L |
| Seminario: Crittografia | 18/01 | S |
| Hash e complessità | 20/01 | E |
| Esercitazione riassuntiva 1 | 25/01 | E |
| Esercitazione riassuntiva 2 | 27/01 | E |
Inoltre sono disponibile i calendari degli anni precedenti.
