Master's Degree in Mathematics

Mathematics methods for computer science (2010/2011)

Course code 4S02855 Teacher Roberto Giacobazzi Coordinator Roberto Giacobazzi training credits 6 Disciplinary sector INF/01 - Computing Teaching language Italian Period I semestre dal Oct 4, 2010 al Jan 31, 2011. Web page http://profs.sci.univr.it/~giaco/metodi.html

Links Course news Seminars related to the course

Lecture timetable

Educational objectives

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.

Syllabus

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.

Exam methods

Discussion of a cooperative project.