INFORMATICA TEORICA

Attività formativa monodisciplinare
Codice dell'attività formativa: 
38045

Scheda dell'insegnamento

Per studenti immatricolati al 1° anno a.a.: 
2019/2020
Insegnamento (nome in italiano): 
INFORMATICA TEORICA
Insegnamento (nome in inglese): 
THEORETICAL COMPUTER SCIENCE
Tipo di attività formativa: 
Attività formativa Caratterizzante
Tipo di insegnamento: 
Opzionale
Settore disciplinare: 
SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI (ING-INF/05)
Anno di corso: 
1
Anno accademico di offerta: 
2019/2020
Crediti: 
6
Responsabile della didattica: 
Altri docenti: 
Mutuazioni

Altre informazioni sull'insegnamento

Modalità di erogazione: 
Didattica Convenzionale
Lingua: 
Italiano
Ciclo: 
Secondo Semestre
Obbligo di frequenza: 
No
Ore di attività frontale: 
48
Ambito: 
Ingegneria informatica
Materiali didattici: 
Prerequisiti

Conoscenze di base di matematica e logica.

Obiettivi formativi

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.

Contenuti dell'insegnamento

- Concetti matematici di base
- Linguaggi formali e grammatiche
- Macchine di Turing
- Modelli di calcolo e teoria generale della calcolabilità
- Complessità computazionale
- Algoritmi di approssimazione

Testi di riferimento

Giorgio Ausiello , Fabrizio D'Amore , Giorgio Gambosi, Luigi Laura. Linguaggi, modelli, complessità. 2a edizione, Franco Angeli, 2014, pp. 1-454

Metodi didattici

Lezione frontale

Modalità verifica profitto e valutazione

Esame scritto con domande aperte ed esercizi sugli argomenti trattati nel corso.

Altre informazioni

Informazioni sul corso e materiale integrativo all'indirizzo:
http://dinamico2.unibg.it/dondi/didattica.html

Prerequisites

Basic knowledge of mathematics and logic.

Educational goals

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.

Course content

- Basic Mathematical Concepts
- Formal languages and grammars
- Turing machines
- Models of computation and general theory of calculability
- Computational Complexity
- Approximation algorithm

Textbooks and reading lists

Giorgio Ausiello , Fabrizio D'Amore , Giorgio Gambosi, Luigi Laura. Linguaggi, modelli, complessità. 2a edizione, Franco Angeli, 2014, pp. 1-454

Teaching methods

Lectures

Assessment and Evaluation

Written test with open questions and exercises on the topics of the course.

Further information

Information on the course and links to additional teaching material at
http://dinamico2.unibg.it/dondi/didattica.html