Foundations of Computing (2015/2016)

Course code
4S00005
Name of lecturer
Isabella Mastroeni
Coordinator
Isabella Mastroeni
Number of ECTS credits allocated
6
Academic sector
INF/01 - INFORMATICS
Language of instruction
Italian
Period
I semestre dal Oct 1, 2015 al Jan 29, 2016.

Lesson timetable

I semestre
Day Time Type Place Note
Monday 8:30 AM - 11:30 AM lesson Lecture Hall C  
Thursday 8:30 AM - 10:30 AM lesson Lecture Hall C  

Learning outcomes

The course covers standard principles and methods in theoretical computer science, notably in automata theory and computability. The course is structured in two parts: in the first part we cover automata, regular languages, context-free grammars, normal forms and formal Chomsky's language hierarchy. In the second part we cover the notion of computable function, decidability and issues in the mathematical or recursion.

The course requires the standard courses on Programming, Algorithms, Discrete mathematics and logic. It is introductory for the advanced courses in Complexity, Programming languages and Compilers, as well as for the courses in Security and Cryptography, Static Analysis and Protection, Artificial Intelligence, Automated Deduction, Semantics, Non-standard computational models.

Syllabus

Automata and formal languages (28h): Formal languages and grammars, finite state automata, regular languages, context-free languages, normal forms, Push-down automata, Chomsky classification of formal languages. Computability (34h): intuitive notion of algorithm, Turing analysis of computable functions, Turing machines and WHILE-programs, Church thesis, Goedelization, universality, Theorem s-m-n, unsolvable problems and halting problem, metaprogramming, recursive and recursive enumerable sets, Recursion theorems, Rice Theorem, reducibility, complete, creative and productive sets.

Assessment methods and criteria

Written exam in 4 sessions, with intermediate evaluation. The exams are scheduled as follows: 1 intermediate (written) evaluation during the course, 1 exam in the Extraordinary Session at the end of the course, 1 exam in the Summer Session and 1 exams in the Fall Session. Mandatory oral exam for evaluation greater than 26.

Student opinions - 2015/2016