Studying at the University of Verona

Here you can find information on the organisational aspects of the Programme, lecture timetables, learning activities and useful contact details for your time at the University, from enrolment to graduation.

The Study Plan includes all modules, teaching and learning activities that each student will need to undertake during their time at the University.
Please select your Study Plan based on your enrollment year.

2° Year  activated in the A.Y. 2012/2013

ModulesCreditsTAFSSD
12
B
INF/01
6
C
FIS/01
6
B
ING-INF/05
12
B
ING-INF/05
Un insegnamento a scelta tra i seguenti:

3° Year  activated in the A.Y. 2013/2014

ModulesCreditsTAFSSD
12
B
INF/01
Un insegnamento a scelta tra i seguenti:
Prova finale
6
E
-
activated in the A.Y. 2012/2013
ModulesCreditsTAFSSD
12
B
INF/01
6
C
FIS/01
6
B
ING-INF/05
12
B
ING-INF/05
Un insegnamento a scelta tra i seguenti:
activated in the A.Y. 2013/2014
ModulesCreditsTAFSSD
12
B
INF/01
Un insegnamento a scelta tra i seguenti:
Prova finale
6
E
-

Legend | Type of training activity (TTA)

TAF (Type of Educational Activity) All courses and activities are classified into different types of educational activities, indicated by a letter.




S Placements in companies, public or private institutions and professional associations

Teaching code

4S00005

Credits

6

Language

Italian

Scientific Disciplinary Sector (SSD)

INF/01 - INFORMATICS

Period

I semestre dal Oct 1, 2013 al Jan 31, 2014.

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.

Program

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.

Reference texts
Author Title Publishing house Year ISBN Notes
N. Jones Computability and Complexity MIT Press 1997
Christos H. Papadimitriou Computational complexity Addison Wesley 1994 0201530821
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman Introduction to Automata Theory, Languages and Computation (Edizione 2) Addison-Wesley 2000 0201441241
Michael Sipser Introduction to the Theory of Computation PWS 1997 053494728X
H. Rogers Theory of recursive functions and effective computability MIT Press 1988

Examination Methods

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.

Students with disabilities or specific learning disorders (SLD), who intend to request the adaptation of the exam, must follow the instructions given HERE