Table of Contents

Informatica 3

News

English version

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

  1. I linguaggi di programmazione: concetti generali e classificazioni fondamentali; cenni storici
  2. Sintassi e semantica
  3. La struttura dei dati
  4. La struttura di controllo
  5. Modularizzazione
  6. Linguaggi orientati agli oggetti
  7. Cenni ai linguaggi Interpretati

Programma del corso: Algoritmi e Strutture Dati

  1. Introduzione alla 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
  13. 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:

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:

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.

Temi d'esame