Anno accademico 2023-2024

FONDAMENTI DELL'INFORMATICA

Docenti

Agostino Dovier
Riccardo Romanello
Anno di corso
2
Totale crediti
9
Periodo didattico
Secondo Periodo
Tipologia
Caratterizzante
Prerequisiti. Sono necessarie conoscenze di base di programmazione, di matematica discreta, di analisi matematica e di logica matematica.
Metodi didattici. Il corso è fondazionale e con didattica tradizionale: lezione frontale alla lavagna alternata ad esercizi e discussione di esercizi svolti/assegnati dagli/agli studenti.
Modalità di verifica. Prova scritta nella quale si valutano le capacità di applicare le tecniche e la competenza appresa e  prova orale in cui vengono verificate le conoscenze della materia. Il voto finale sarà una somma pesata dei voti conseguiti nei singoli esercizi della prova scritta e di un eventuale incremento in base all’esito della prova orale. In ogni singolo esercizio e nella prova orale si applicheranno le linee guida approvate dal CCS.
Altre informazioni. Dal sito web del docente è possibile visionare tutti i testi di tutti gli appelli svolti con traccia di soluzione.
Obiettivi formativi
Il corso affronta le basi teoriche della scienza del calcolatore.

Capacità relative alle discipline

1.1  Conoscenza e capacità di comprensione: lo studente acquisisce conoscenze logico-formali fondanti la disciplina “informatica”. In particolare, le nozioni di linguaggio formale e la classificazione degli stessi secondo Chomsky, la nozione di funzione calcolabile e le sue principali caratterizzazioni e limiti, la nozione di complessità di un problema e le principali tecniche per studiarla.

 1.2 Conoscenza e capacità di comprensione applicate: lo studente sarà in grado di comprendere la complessità di un linguaggio formale e dunque quale sia lo strumento software più adatto per generarlo o riconoscerlo, di comprendere se un problema sia o meno risolubile con un calcolatore e, nel primo caso, di comprendere se sia possibile risolverlo efficientemente.

Capacità trasversali/soft skills

2.1 Autonomia di giudizio: lo studente acquisisce una capacità di valutazione critica sulle specifiche di un problema che permettono di comprenderne il suo grado di calcolabilità e, nel caso, sia calcolabile, il suo grado di complessità.

2.2 Abilità comunicative: lo studente impara ad utilizzare la terminologia precisa nell’area dei linguaggi formali (automi, grammatiche), della calcolabilità (problema decidibile, semidecidibile etc) e della complessità (problema polinomiale, classe NP, etc).

2.3 Capacità di apprendimento: lo studente impara a familiarizzare con il metodo scientifico applicato in modo rigoroso alla disciplina informatica. Gran parte dei testi utilizzati sono in lingua inglese e pertanto lo studente migliora la sua capacità di comprendere informazioni ricevute in tale lingua.

Contenuti
Il corso si divide in tre parti: linguaggi formali, calcolabilità, e complessità.

Linguaggi formali.

Linguaggi regolari. Automi a stati finiti deterministici e non-deterministici,

e loro equivalenza.

Espressioni regolari. Pumping Lemma per i linguaggi regolari e sue applicazioni.

Proprietà di chiusura e di decidibilità dei linguaggi regolari.

Linguaggi liberi dal contesto. Grammatiche libere dal contesto e alberi di derivazione.

Grammatiche ambigue. Le forme normali di Chomsky e di Greibach.

Il pumping lemma per i linguaggi liberi e le sue applicazioni.

Proprietà di chiusura e di decidibilità dei linguaggi liberi.

Grammatiche lineari destre e sinistre, grammatiche di tipo 0 e 1 e

gerarchia di Chomsky.

Calcolabilità.

Il concetto di algoritmo. Modelli di calcolo. La macchina di Turing.

Funzioni Turing-calcolabili. Enumerazione. Halting Problem e sua indecidibilita’.

Il teorema SMN. I formalismi delle funzioni primitive ricorsive e

ricorsive parziali. La funzione di Ackermann.

Equivalenza tra le funzioni ricorsive parziali e le funzioni Turing-calcolabili.

Teoremi di Rice, Rice-Shapiro e i Teoremi di ricorsione.

Applicazioni alla programmazione. Riducibilità funzionale.

Studio della relazione. Insiemi ricorsivi e completi. Insiemi creativi e produttivi.

Teorema di Myhill. Insiemi semplici: esistenza di un insieme semplice.

Complessità.

Problemi e linguaggi. Problemi decisionali e funzionali.

Classi di complessità in tempo deterministiche e non deterministiche;

classi in spazio: principali risultati. Riduzioni, completezza, ed esempi.

Teoremi di Cook. NP-completezza di alcuni problemi fondamentali mediante riduzione.

Testi di riferimento
AGOSTINO DOVIER, ROBERTO GIACOBAZZI

Fondamenti dell’Informatica: Linguaggi Formali, Calcolabilità e Complessità.

BOLLATI BORINGHIERI, 320 pagine, MARZO 2020.

ISBN 9788833933795