First cycle
degree courses
Second cycle
degree courses
Single cycle
degree courses
School of Engineering
INFORMATION ENGINEERING
Course unit
THEORY OF COMPUTATION (Ult. numero di matricola da 0 a 4)
IN01103926, A.A. 2016/17

Information concerning the students who enrolled in A.Y. 2014/15

Information on the course unit
Degree course First cycle degree in
INFORMATION ENGINEERING
IN0513, Degree course structure A.Y. 2011/12, A.Y. 2016/17
Ult1001
bring this page
with you
Number of ECTS credits allocated 6.0
Type of assessment Mark
Course unit English denomination THEORY OF COMPUTATION
Department of reference Department of Information Engineering
E-Learning website https://elearning.dei.unipd.it/course/view.php?idnumber=2016-IN0513-000ZZ-2014-IN01103926-ULT1001
Mandatory attendance No
Language of instruction Italian
Branch PADOVA
Single Course unit The Course unit can be attended under the option Single Course unit attendance
Optional Course unit The Course unit can be chosen as Optional Course unit

Lecturers
Teacher in charge CINZIA PIZZI ING-INF/05

Mutuated
Course unit code Course unit name Teacher in charge Degree course code
IN01103926 THEORY OF COMPUTATION (Ult. numero di matricola da 0 a 4) CINZIA PIZZI IN0521

ECTS: details
Type Scientific-Disciplinary Sector Credits allocated
Core courses ING-INF/05 Data Processing Systems 6.0

Course unit organization
Period Second semester
Year 3rd Year
Teaching method frontal

Type of hours Credits Teaching
hours
Hours of
Individual study
Shifts
Lecture 6.0 48 102.0 No turn

Calendar
Start of activities 27/02/2017
End of activities 09/06/2017
Show course schedule 2019/20 Reg.2011 course timetable

Examination board
Board From To Members of the board
11 A.A. 2016/2017 01/10/2016 31/12/2019 PIZZI CINZIA (Presidente)
RODA' ANTONIO (Membro Effettivo)
COMIN MATTEO (Supplente)
PIETRACAPRINA ANDREA ALBERTO (Supplente)
PINI MARIA SILVIA (Supplente)
SATTA GIORGIO (Supplente)
SILVESTRI FRANCESCO (Supplente)
VANDIN FABIO (Supplente)
10 A.A. 2016/2017 01/10/2016 15/03/2018 PINI MARIA SILVIA (Presidente)
PIZZI CINZIA (Membro Effettivo)
COMIN MATTEO (Supplente)
FERRARI CARLO (Supplente)
SATTA GIORGIO (Supplente)
VANDIN FABIO (Supplente)
9 A.A. 2015/2016 01/10/2015 15/03/2017 PIZZI CINZIA (Presidente)
PINI MARIA SILVIA (Membro Effettivo)
COMIN MATTEO (Supplente)
FERRARI CARLO (Supplente)
SATTA GIORGIO (Supplente)

Syllabus
Prerequisites: In order to follow this course with success it is necessary to have a solid mathematical background.
Target skills and knowledge: Acquisition of basic concepts of computational models, notions of computability and decidability, and of the related hierarchies of automata, languages ​​and grammars.
Development of the capacity of abstraction, analysis, and problem solving.
Examination methods: A written examination.
Assessment criteria: The evaluation of the student will be based on the assessment of the understanding of basic concepts introduced during the course, and their application to the resolution of problems in terms of analysis of formal languages ​​and their properties.
Course unit contents: Characterization of problems in terms of formal languages.
Study of formal languages ​​and of the limits of computability by hierarchies of computational models (automata) and generative models (grammars). In particular, we will study regular​​, context-free, recursive and recursively enumerable languages.

Regular Languages ​​(REG).
Finite state automata: deterministic, non-deterministic, non-deterministic with epsilon-transitions. Regular expression: definitions, properties, and their relationship with automata. Properties of regular languages​​.

Context-free languages ​​(CFL).
Context-free grammars: definitions, parse-trees, simplification of context-free grammars, Chomsky Normal Form. Push-down automata: definitions and their relation to the context-free grammars. Properties of context-free languages​​.

Turing machines.
Definitions of recursively-enumerable (computable) and recursive (decidable) languages ​​(problems). Church-Turing thesis. Basic definitions of Turing machines and techniques to construct them. Evidence of the existance of languages/functions that are not decidable or computable.
Textbooks (and optional supplementary readings)
  • J.E. Hopcrpft, R.Motwani, J.D.Ullman, Automi, Linguaggi e Calcolabilità. --: Pearson, Addison Wesley, --. Cerca nel catalogo