Algoritmi e Principi dell'Informatica: Informatica 3
Pagine di Informatica 3, prima della fusione
Il modulo 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 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: Algoritmi e Strutture Dati
- Lla 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
Materiale didattico
Per il corso di Informatica 3, si adottano formalmente due libri di testo (alternativi):
- A. Bertossi e A Montresor: Algoritmi e strutture dati.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduzione agli algoritmi e strutture dati 3/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.
Per finire, il classico libro di David Harel, “Algorithmics: The Spirit of Computing”, fornisce una introduzione meno traumatica ai concetti visti nel corso.
Linguaggi di Programmazione
Formalmente, nel corso non vengono presentati o adottati linguaggi di programmazione – tutti i concetti sono proposti, anche nelle esercitazioni, usando lo pseudo-codice adottato nel Cormen. Lo stesso avverra' nei temi d'esame.
Ciononostante, e' fortemente consigliato (da me, almeno) provare ad implementare gli algoritmi proposti in un linguaggio di programmazione a scelta.
Personalmente, consiglio Python, che e' stato usato negli anni scorsi come linguaggio di riferimento per la versione del corso presente nell'ordinamento 509. Potete 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 troverete, man mano che svolgeremo le lezioni, il programma dettagliato del corso, con una sintesi degli argomenti presentati a lezione.
Al momento, ho inserito un programma di massima, basato sul Cormen (terza edizione, ma la seconda va bene per tutto, tranne l'ultima lezione). Questo programma sara' soggetto a (sperabilmente lievi) variazioni. Inoltre, verranno svolti in parallelo alcuni argomenti di raccordo con la prima parte del corso, trattati nel capitolo 3 del Ghezzi/Mandrioli oltre che nei capitoli 1-4 e 34 del Cormen.
| Data | Argomenti | Tipo |
|---|---|---|
| 22/11/10 | Intro + Cap. 1 | L |
| 24/11/10 | App. A, Cap. 2-3 | L |
| 25/11/10 | Cap. 1-3 | E |
| 29/11/10 | Cap. 4 | L |
| 30/11/10 | Cap. 6-7 | L |
| 01/12/10 | Cap. 4 | E |
| 02/12/10 | Cap. 8, Cap. 10 | L |
| 13/12/10 | Cap. 6-8 | E |
| 14/12/10 | Cap. 11 | L |
| 15/12/10 | Cap. 12 + 10.4 | L |
| 16/12/10 | Cap. 10, Cap. 11 | E |
| 21/12/10 | Cap. 18 | L |
| 10/01/11 | Cap. 12 + 10.4 | E |
| 11/01/11 | Cap. 15 | L |
| 12/01/11 | Cap. 18 | E |
| 13/01/11 | Cap. 16 | L |
| 17/01/11 | Cap. 15-16 | E |
| 18/01/11 | Cap. 13 | L |
| 19/01/11 | Complessita' | L |
| 20/01/11 | Cap. 13 | E |
| 24/01/11 | Complessita' + Tema d'esame | E |
| 25/01/11 | Cap. 22 | L |
| 26/10/11 | Argomenti avanzati (Cap. 27) + Tema d'esame | S |
| 27/01/11 | Cap. 34 | L |
Temi d'esame
Qui trovate i temi d'esame degli appelli precedenti.
Dato che questo e' il primo anno in cui si tiene il corso, non vi sono temi d'esame precedenti. Potete pero' fare riferimento agli esercizi proposti nel Cormen, e, per le sole parti relative al programma del corso attuale, ai temi d'esame dell'ordinamento 509, riportati qui sotto.
