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
Giorgio Ausiello , Fabrizio D'Amore , Giorgio Gambosi, Luigi Laura. Linguaggi, modelli, complessità. 2a edizione, Franco Angeli, 2014, pp. 1-454
Lezione frontale
Esame scritto con domande aperte ed esercizi sugli argomenti trattati nel corso.
Informazioni sul corso e materiale integrativo all'indirizzo:
http://dinamico2.unibg.it/dondi/didattica.html
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
Giorgio Ausiello , Fabrizio D'Amore , Giorgio Gambosi, Luigi Laura. Linguaggi, modelli, complessità. 2a edizione, Franco Angeli, 2014, pp. 1-454
Lectures
Written test with open questions and exercises on the topics of the course.
Information on the course and links to additional teaching material at
http://dinamico2.unibg.it/dondi/didattica.html