Conoscenze di base di matematica e logica.
Il corso ha l'obiettivo di fornire le conoscenze dei fondamenti teorici dell'informatica:
dai concetti logico-matematici alla teoria della computabilità e alla complessità computazionale. Al termine del percorso didattico lo studente sarà in grado di comprendere gli aspetti fondamentali della teoria della computabilità e conoscerà le principali classi di complessità computazionale.
- Concetti matematici di base
- Linguaggi formali e grammatiche
- Macchine di Turing
- Modelli di calcolo e teoria generale della calcolabilità
- Complessità computazionale
- Algoritmi di approssimazione
Lezione frontale
Esame scritto con domande aperte ed esercizi sugli argomenti trattati nel corso.
L'esame scritto prevede cinque domande a risposta aperta:
1) Due esercizi sulla progettazione di macchine di Turing (5 punti per esercizio)
2) Una domanda a risposta aperta sulle proprietà di decidibilità e semi-decidibilità dei linguaggi (8 punti)
3) Due domande aperte sulle classi di complessità e le loro proprietà (7 punti per domanda)
Informazioni sul corso e materiale integrativo all'indirizzo sulla piattaforma e-leanring del corso
Qualora la situazione pandemica renda necessarie prove d'esame a distanza potranno essere introdotte modifiche rispetto a quanto dichiarato nel syllabus
Basic knowledge of mathematics and logic.
The course aims at providing the theoretical foundations of computer science: from logical-mathematical concepts to computability and computational complexity. At the end of the course the student will be able to understand the fundamental aspects of computability theory and will know the main classes of computational complexity.
- Basic Mathematical Concepts
- Formal languages and grammars
- Turing machines
- Models of computation and general theory of calculability
- Computational Complexity
- Approximation algorithm
Lectures
Written test with open questions and exercises on the topics of the course.
The written exam includes five open questions:
1) Two exercises on the design of Turing machines (5 points for each exercise)
2) An open question on the decidability and semi-decidability properties of languages (8 points)
3) Two open questions on complexity classes and their properties (7 points for each question)
Information on the course and links to additional teaching material on the e-learning platform
In case of exclusively online teaching, changes can be introduced compared to what is stated in the syllabus.