Table of Contents

Algoritmi e Principi dell'Informatica: Informatica 3

News

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

  1. Lla complessità del calcolo
  2. La notazione “Theta-grande”
  3. La realizzazione di tipi astratti di dati in Java
  4. Strutture dati e algoritmi fondamentali
  5. Algoritmi di ricerca e ordinamento
  6. Alberi e loro gestione
  7. Realizzazione mediante puntatori
  8. Alberi binari
  9. Algoritmi di visita e gestione
  10. B-trees
  11. Grafi, loro rappresentazione e gestione
  12. Pile, code e tabelle hash

Materiale didattico

Per il corso di Informatica 3, si adottano formalmente due libri di testo (alternativi):

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:

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.

Esercizi