Mathematics methods for computer science (2010/2011)

Course code
Name of lecturer
Roberto Giacobazzi
Roberto Giacobazzi
Number of ECTS credits allocated
Academic sector
Language of instruction
I semestre dal Oct 4, 2010 al Jan 31, 2011.
Web page

Lesson timetable

I semestre
Day Time Type Place Note
Monday 9:30 AM - 11:30 AM lesson Lecture Hall M from Oct 11, 2010  to Jan 31, 2011
Friday 1:30 PM - 3:30 PM lesson Lecture Hall M  

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, security and issues in the mathematical or recursion

The course requires the standard courses on Discrete mathematics and logic.


Automata and formal languages (20h): Formal languages and grammars, finite state automata, regular languages, context-free languages, normal forms, Push-down automata, Chomsky classification of formal languages. Computability (25h): 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. Computational virology.

Assessment methods and criteria

Discussion of a cooperative project.

Statistics about transparency requirements (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

Outcomes Exams Outcomes Percentages Average Standard Deviation
Positive 85.71% 29 0
Rejected --
Absent 14.28%
Ritirati --
Canceled --
Distribuzione degli esiti positivi
18 19 20 21 22 23 24 25 26 27 28 29 30 30 e Lode
0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 0.0% 33.3% 0.0% 33.3% 33.3%

Data from AA 2010/2011 based on 7 students. I valori in percentuale sono arrotondati al numero intero più vicino.