PRESENTAZIONE

Nel modulo teorico, il corso presenta i modelli formali di soluzione di problemi mediante calcolatore intesa come trattamento di linguaggi e le relative problematiche di computabilità e complessità. Il corso considera le principali tecniche per la costruzione di algoritmi e strutture dati corrette ed efficienti. Nel modulo di laboratorio vengono esposti strumenti di progettazione e programmazione in un linguaggio orientato agli oggetti finalizzato allo sviluppo di un interprete.

OBIETTIVI E CONTENUTI

PREREQUISITI

Per la comprensione degli argomenti del corso è necessaria la conoscenza dei concetti di programmazione procedurale (principali tipi di dato scalari e vettoriali, dichiarazione e utilizzo di variabili, scelte condizionali, iterazioni, definizione di funzioni), della programmazione orientata agli oggetti (definizione di classi e classi generiche) e del linguaggio C++ come forniti dai corsi di Fondamenti di Informatica. E' inoltre consigliabile un'esposizione ai concetti di base di insiemistica, matematica discreta e probabilità.

DOCENTI E COMMISSIONI

ESAMI

MODALITA' D'ESAME

L'esame prevede due prove obbligatorie:

- Prova scritta su teoria della computazione, algoritmi e strutture dati
- Realizzazione di un progetto assegnato dal docente

Al termine del primo semestre è prevista una prova scritta intermedia sulla sola teoria della computazione. Tutte le prove scritte prevedono una o più domande aperte. Il progetto viene assegnato al termine del primo semestre e viene svolto individualmente dagli studenti. Il progetto ha validità annuale, ossia l'esame scritto deve essere svolto entro un anno dalla data di consegna del progetto. Il progetto concorre al voto finale per un quarto (25%) del punteggio complessivo, mentre lo scritto concorre ai tre quarti (75%) del punteggio complessivo (25% la parte di teoria della computazione, 50% algoritmi e strutture dati). 

MODALITA' DI ACCERTAMENTO

Il progetto valuterà la capacità dello studente di mettere in pratica i concetti di teoria della computazione nel contesto di un'applicazione semplice ma realistica (ad esempio, un interprete per un linguaggio di programmazione) progettata e realizzata con il linguaggiop C++.

Lo scritto valuterà la comprensione dello studente dei concetti esposti a lezione mediante lo svolgimento di esercizi che prevedono sia la soluzione di problemi sia la dimostrazione di proprietà relativamente alle soluzioni proposte.