FOUNDATIONS OF COMPUTER SCIENCE

iten
Code
80303
ACADEMIC YEAR
2017/2018
CREDITS
6 credits during the 3nd year of 8759 Computer Science (L-31) GENOVA
SCIENTIFIC DISCIPLINARY SECTOR
INF/01
LANGUAGE
Italian
TEACHING LOCATION
GENOVA (Computer Science)
semester
1° Semester
Teaching materials

OVERVIEW

We introduce notions and results from Automata Theory and Computability Theory which are of paramount importance for a computer scientist.

 

AIMS AND CONTENT

LEARNING OUTCOMES

To understand key concepts of Theory of Automata and Theory of Computability, such as expressive power of automata, and decidability and semi-decidability of problems. 

 

TEACHING METHODS

Traditional.

SYLLABUS/CONTENT

Automata and Languages
Alphabets, strings, languages
Deterministic (DFA) and non deterministic (NFA) finite state automata
DFA minimization, regular expressions

Closure properties of regular languages, pumping lemma
Context-free grammars, derivation trees, ambiguity
Deterministic and non deterministic push down automata (PDA)
Closure properties of context-free languages, pumping lemma

Computability
Turing machines, accepted languages
Indecidability, recursive and recursively enumerable languages, universal language and machine, indecidability of the universal language
Halting problem
Indecidable problems on Turing machines, Rice theorem, Church thesis

RECOMMENDED READING/BIBLIOGRAPHY

Course notes.

TEACHERS AND EXAM BOARD

Office hours: On request. In addition, on aulaweb there will be a discussion forum for questions and answer of general interest for all students.

Exam Board

ELENA ZUCCA (President)

DAVIDE ANCONA

FRANCESCO DAGNINO

GIORGIO DELZANNO

EUGENIO MOGGI

LESSONS

TEACHING METHODS

Traditional.

EXAMS

Exam schedule

Date Time Location Type Notes
11/01/2018 14:30 GENOVA Scritto 11/01/18 Aula 710 13/02/18 Aula 710 07/06/18 Aula 505 09/07/18 Aula 506 12/09/18 Aula 710 ATTENZIONE: questo appello è posticipato alle ore 14:30
13/02/2018 14:30 GENOVA Scritto 11/01/18 Aula 710 13/02/18 Aula 710 07/06/18 Aula 505 09/07/18 Aula 506 12/09/18 Aula 710 ATTENZIONE: questo appello è posticipato alle ore 14:30
07/06/2018 14:30 GENOVA Scritto 11/01/18 Aula 710 13/02/18 Aula 710 07/06/18 Aula 505 09/07/18 Aula 506 12/09/18 Aula 710 ATTENZIONE: questo appello è posticipato alle ore 14:30
09/07/2018 14:30 GENOVA Scritto 11/01/18 Aula 710 13/02/18 Aula 710 07/06/18 Aula 505 09/07/18 Aula 506 12/09/18 Aula 710 ATTENZIONE: questo appello è posticipato alle ore 14:30
12/09/2018 14:30 GENOVA Scritto 11/01/18 Aula 710 13/02/18 Aula 710 07/06/18 Aula 505 09/07/18 Aula 506 12/09/18 Aula 710 ATTENZIONE: questo appello è posticipato alle ore 14:30