INFORMATICA TEORICA | Università degli studi di Bergamo

INFORMATICA TEORICA

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

Scheda dell'insegnamento

Per studenti immatricolati al 1° anno a.a.: 
2020/2021
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: 
2020/2021
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
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

Metodi didattici

Lezione frontale

Modalità verifica profitto e valutazione

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)

Altre informazioni

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

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

Teaching methods

Lectures

Assessment and Evaluation

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)

Further information

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.