FOUNDATIONS OF COMPUTER SCIENCE

Obiettivi formativi

Obiettivi generali: Acquisire i fondamenti della scienza dai dati e dell'apprendimento automatico. Obiettivi specifici: Rendere gli studenti consapevoli degli strumenti teorici e pratici della scienza dei dati e dell'apprendimento automatico, nonché dei loro limiti intrinseci; rendere gli studenti in grado di affrontare problemi reali attraverso gli strumenti più appropriati. Conoscenza e comprensione: Il corso fornisce le nozioni, tecniche e metodologie di base utilizzate nell'ambito della scienza dei dati e dell'apprendimento automatico. Fornisce inoltre i rudimenti di programmazione necessari ad applicare la teoria a casi reali Applicare conoscenza e comprensione: Alla fine del corso, gli studenti sapranno affrontare problemi concreti di scienza dei dati, dalla loro formalizzazione sino alla manipolazione dei dati attraverso appropriati strumenti software. Capacità  critiche e di giudizio: Gli studenti saranno in grado di scegliere le tecniche da applicare al caso specifico e di valutarne le prestazioni. Capacità  comunicative: Gli studenti saranno in grado di rappresentare e comunicare l'informazione estratta dai dati, attraverso l'uso razionale di grafici e indicatori. Capacità  di apprendimento: Gli studenti saranno messi in grado di apprendere autonomamente nozioni sia teoriche che pratiche del campo.

Canale 1
DANIELE GORLA Scheda docente

Programmi - Frequenza - Esami

Programma
Automi e Linguaggi: Linguaggi regolari, automi a stati finiti e grammatiche regolari. Linguaggi context-free, grammatiche context-free e automi a pila; gerarchia di Chomsky. Teoria della Calcolabità: Macchine di Turing. Tesi di Church-Turing. Problemi indecidibili: il problema della fermata. La riduzione tra problemi: uno strumento per dimostrarne l'indecibilità o la decidibilità. Esempi di problemi decidibili e indecidibili. Teoria della Complessità: Complessità di tempo e spazio per le macchine di Turing.Classi di complessità. Problemi trattabili e problemi non provatamente intrattabili: le classi P e NP. Riduzioni polinomiali e NP-completezza. Teorema di Cook-Levin e altri problemi NP-completi.
Prerequisiti
Conoscenze basilari di algoritmo, complessità computazionale (notazione O), alberi, grafi, logica del prim'ordine
Testi di riferimento
M. Sipser, Introduction to the Theory of Computation, III edition. Engage Learning, 2012. E' disponibile la traduzione in italiano: Introduzione alla teoria della computazione. Apogeo Edizioni. Alcuni argomenti saranno tratti dal capitolo 9 di: J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison Wesley, 1979.
Frequenza
La frequenza è fortemente consigliata, vista la difficoltà degli argomenti trattati
Modalità di esame
Una prova scritta sulla parte di automi e un orale su tutta la teoria presentata (definizioni e dimostrazioni)
Modalità di erogazione
Lezioni in aula
  • Codice insegnamento10595530
  • Anno accademico2024/2025
  • CorsoApplied Computer Science and Artificial Intelligence – Informatica Applicata e Intelligenza Artificiale
  • CurriculumCurriculum unico
  • Anno3º anno
  • Semestre1º semestre
  • SSDINF/01
  • CFU6
  • Ambito disciplinareDiscipline Informatiche