Fondamenti dell'informatica 1
A.A. 2020/2021
Obiettivi formativi
Scopo principale dell'insegnamento è quello di presentare la nozione di calcolabilità usando semplici linguaggi di programmazione. In particolare vogliamo illustrare e motivare la tesi di Church, lo studio dei problemi indecidibili, i risultati fondamentali della teoria della ricorsività. Una seconda parte è invece dedicata alla complessità computazionale e in particolare ai problemi NP-completi.
Risultati apprendimento attesi
Comprensione dei principali concetti di calcolabilità e decidibilità. Capacità di riconoscere l'indecidibilità e la difficoltà dei problemi nei casi principali. Capacità di formalizzare modelli di calcolo.
Periodo: Primo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Primo semestre
1) Lezioni
Nell'anno accademico 2020/21 il corso, previsto nel primo semestre, verrà tenuto mediante lezioni a distanza erogate in modalità asincrona. Le lezioni saranno videoregistrate in formato MP4 e messe a disposizione degli studenti nella pagina Ariel del corso due volte alla settimana, in linea di massima il lunedì e il mercoledì, seguendo il calendario ufficiale delle lezioni. Durante tutto il periodo di erogazione delle lezioni, sullo stesso sito Ariel del corso sarà attivo un forum di discussione aperto a tutti gli studenti, dedicato alle domande e alla discussione sugli argomenti presentati nelle lezioni.
2) Programma e materiale
Il programma e il materiale di riferimento rimangono invariati rispetto ai periodi di didattica tradizionali.
3) Esami
L'esame consisterà in una prova orale, riguardante gli argomenti del programma, che si dovrà svolgere per via telematica usando l'applicazione Zoom. I candidati, una volta iscritti all'appello prescelto, sono tenuti a contattare per post elettronica il docente del corso e concordare con lui la data e l'ora di svolgimento effettive della prova orale, che non potranno essere precedenti alla data ufficiale dell'appello. Per svolgere l'orale ogni studente dovrà disporre di computer con telecamera e microfono, avere con se l'occorrente per scrivere e trovarsi da solo nella stanza da dove effettuerà il collegamento; pochi minuti prima della prova il candidato riceverà per posta elettronica le specifiche necessarie per partecipare alla riunione telematica, alla quale potranno partecipare altri docenti come membri della commissione. Le specifiche consistono di un semplice indirizzo web al quale collegarsi. La prova orale si svolgerà come al solito, il candidato potrà risponderà a voce alle domande poste scrivendo i dettagli formali su fogli di carta, saltuariamente sarà tenuto a mostrare a video la parte scritta.
Nell'anno accademico 2020/21 il corso, previsto nel primo semestre, verrà tenuto mediante lezioni a distanza erogate in modalità asincrona. Le lezioni saranno videoregistrate in formato MP4 e messe a disposizione degli studenti nella pagina Ariel del corso due volte alla settimana, in linea di massima il lunedì e il mercoledì, seguendo il calendario ufficiale delle lezioni. Durante tutto il periodo di erogazione delle lezioni, sullo stesso sito Ariel del corso sarà attivo un forum di discussione aperto a tutti gli studenti, dedicato alle domande e alla discussione sugli argomenti presentati nelle lezioni.
2) Programma e materiale
Il programma e il materiale di riferimento rimangono invariati rispetto ai periodi di didattica tradizionali.
3) Esami
L'esame consisterà in una prova orale, riguardante gli argomenti del programma, che si dovrà svolgere per via telematica usando l'applicazione Zoom. I candidati, una volta iscritti all'appello prescelto, sono tenuti a contattare per post elettronica il docente del corso e concordare con lui la data e l'ora di svolgimento effettive della prova orale, che non potranno essere precedenti alla data ufficiale dell'appello. Per svolgere l'orale ogni studente dovrà disporre di computer con telecamera e microfono, avere con se l'occorrente per scrivere e trovarsi da solo nella stanza da dove effettuerà il collegamento; pochi minuti prima della prova il candidato riceverà per posta elettronica le specifiche necessarie per partecipare alla riunione telematica, alla quale potranno partecipare altri docenti come membri della commissione. Le specifiche consistono di un semplice indirizzo web al quale collegarsi. La prova orale si svolgerà come al solito, il candidato potrà risponderà a voce alle domande poste scrivendo i dettagli formali su fogli di carta, saltuariamente sarà tenuto a mostrare a video la parte scritta.
Programma
Introduzione alla calcolabilità: le funzioni intuitivamente calcolabili, esistenza di funzioni non calcolabili, la funzione coppia e le sue estensioni. Sintassi e semantica del linguaggio RAM ridotto. Sintassi e semantica del linguaggio While. Esempio di funzione compilatore e di funzione interprete. Equivalenza computazionale tra linguaggio RAM e linguaggio While. Aritmetizzazione dei programmi RAM. Funzioni ricorsive parziali. Tesi di Church.
Sistemi di programmazione accettabili. Il teorema di ricorsione e il teorema di isomorfismo. I problemi indecidibili. Problemi particolari: arresto, totalità, equivalenza. Insiemi ricorsivi e ricorsivamente numerabili. Caratterizzazioni principali degli insiemi ricorsivamente numerabili. Riducibilità tra insiemi e insiemi completi. Insiemi che rispettano le funzioni. Il teorema di Rice.
Linguaggi e grammatiche formali. Gerarchia di Chomsky: linguaggi regolari, liberi da contesto, dipendenti da contesto, di tipo 0. Automi a stati finiti deterministici, non deterministici e loro proprietà di simulazione. Linguaggi regolari: lemma di iterazione e proprietà di chiusura rispetto alle operazioni booleane.
Macchine di Turing. Macchine deterministiche e non deterministiche. Proprietà di simulazione tra modelli. Classi di complessità in tempo. Classi P e NP. Riducibilità in tempo polinomiale e suoi esempi notevoli. I problemi NP-completi. Il teorema di Cook. Introduzione alla complessità in spazio: le classi L, NL, Pspace e il teorema di Savitch.
Sistemi di programmazione accettabili. Il teorema di ricorsione e il teorema di isomorfismo. I problemi indecidibili. Problemi particolari: arresto, totalità, equivalenza. Insiemi ricorsivi e ricorsivamente numerabili. Caratterizzazioni principali degli insiemi ricorsivamente numerabili. Riducibilità tra insiemi e insiemi completi. Insiemi che rispettano le funzioni. Il teorema di Rice.
Linguaggi e grammatiche formali. Gerarchia di Chomsky: linguaggi regolari, liberi da contesto, dipendenti da contesto, di tipo 0. Automi a stati finiti deterministici, non deterministici e loro proprietà di simulazione. Linguaggi regolari: lemma di iterazione e proprietà di chiusura rispetto alle operazioni booleane.
Macchine di Turing. Macchine deterministiche e non deterministiche. Proprietà di simulazione tra modelli. Classi di complessità in tempo. Classi P e NP. Riducibilità in tempo polinomiale e suoi esempi notevoli. I problemi NP-completi. Il teorema di Cook. Introduzione alla complessità in spazio: le classi L, NL, Pspace e il teorema di Savitch.
Prerequisiti
Conoscenza generale degli algoritmi di base, delle strutture dati principali e di almeno un linguaggio di programmazione di tipo imperativo, avendo svolto una corrispondente attività di programmazione elementare.
E' fortemente consigliato aver superato l'esame di un insegnamento di Programmazione e di uno di Algoritmi, svolti nell'ambito di un corso di laurea triennale.
E' fortemente consigliato aver superato l'esame di un insegnamento di Programmazione e di uno di Algoritmi, svolti nell'ambito di un corso di laurea triennale.
Metodi didattici
L'insegnamento è basato su lezioni tradizionali.
Materiale di riferimento
- Sito web dell'insegnamento:
http://users.mat.unimi.it/users/goldwurm/Fondamenti_Informatica/
- Presso il portale Ariel dell'Ateneo, all'indirizzo https://ariel.unimi.it/
si trova una pagina web dedicata all'insegnamento di Fondamenti dell'Informatica 1.
- Dispense del Corso:
M. Goldwurm, Computabilità e complessità computazionale, Università degli Studi di Milano, Gennaio 2019,
scaricabili al sito web riportato sopra.
- Testi di riferimento:
A. Bertoni, Introduzione alla calcolabilità, Dispense del corso di Informatica Teorica, parte 1, Univ. degli Studi di
Milano, 1990. Scaricabile al sito Ariel di Fondamenti dell'Informatica 1, menzionato nel seguito.
A. Kfoury, R. Moll, M. Arbib, A Programming Approach to Computability, Springer-Verlag, 1982.
Versione italiana (stessi autori): Programmazione e computabilità, Etas Libri, 1986.
J. Hopcroft, J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1997.
C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
J. Hopcroft, R. Motwani, J. Ullman, Introduction to Automata Theory, Languages, and Computation, 2001.
http://users.mat.unimi.it/users/goldwurm/Fondamenti_Informatica/
- Presso il portale Ariel dell'Ateneo, all'indirizzo https://ariel.unimi.it/
si trova una pagina web dedicata all'insegnamento di Fondamenti dell'Informatica 1.
- Dispense del Corso:
M. Goldwurm, Computabilità e complessità computazionale, Università degli Studi di Milano, Gennaio 2019,
scaricabili al sito web riportato sopra.
- Testi di riferimento:
A. Bertoni, Introduzione alla calcolabilità, Dispense del corso di Informatica Teorica, parte 1, Univ. degli Studi di
Milano, 1990. Scaricabile al sito Ariel di Fondamenti dell'Informatica 1, menzionato nel seguito.
A. Kfoury, R. Moll, M. Arbib, A Programming Approach to Computability, Springer-Verlag, 1982.
Versione italiana (stessi autori): Programmazione e computabilità, Etas Libri, 1986.
J. Hopcroft, J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1997.
C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
J. Hopcroft, R. Motwani, J. Ullman, Introduction to Automata Theory, Languages, and Computation, 2001.
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste di una prova orale riguardante gli argomenti inclusi nel programma. Ai candidati è richiesta la conoscenza precisa delle definizioni delle nozioni fondamentali elencate nel programma, la capacità di fornire esempi significativi delle loro proprietà e di presentare la dimostrazione di alcuni teoremi rilevanti illustrati a lezione.
Il voto è espresso in trentesimi e verrà comunicato immediatamente al termine della prova orale.
Il voto è espresso in trentesimi e verrà comunicato immediatamente al termine della prova orale.
Siti didattici
Docente/i
Ricevimento:
su appuntamento (accordi per e-mail).
dip. Matematica, via Saldini 50 (ufficio al secondo piano).