ITA | ENG
B006821 - THEORETICAL COMPUTER SCIENCE
Main information
Course Content
Suggested readings
Learning Objectives
Prerequisites
Teaching Methods
Further information
Type of Assessment
Course program
Academic Year 2013-14
Course year
Third year - First Semester
Belonging Department
Statistics, IT and its applications "G. Parenti" (DISIA)
Course Type
Single education field course
Scientific Area
INF/01 - INFORMATICS
Credits
9
Teaching Hours
72
Teaching Term
23/09/2013 ⇒ 20/12/2013
Attendance required
No
Type of Evaluation
Final Grade
Course Content
show
Course program
show
Lectureship
Course Content
Computability theory: the Church-Turing thesis, decidability, reducibility. Machines and languages: regular, context-free, context-sensitive, and type 0 languages. Complexity theory: time and space complexity, classes P and NP, classes EXP and PSPACE.
Suggested readings (Search our library's catalogue)
P. Crescenzi, Theoretical computer science (lecture notes available on the web).
Learning Objectives
Knowledge:
The main goal of the course is to determine what can and what cannot be computed, with which computation model and how fast.
Skills acquired:
The course will introduce the students to the theoretical principles which are also relevant in practice, in order to design, develop and manage information systems. In particular, it will present the basic ideas of theoretical computer science, concerning formal languages, and the computability and complexity theory.
Skill acquired (at the end of the corse):
By learning these arguments, the students will be able to deal with important computational problems.
The main goal of the course is to determine what can and what cannot be computed, with which computation model and how fast.
Skills acquired:
The course will introduce the students to the theoretical principles which are also relevant in practice, in order to design, develop and manage information systems. In particular, it will present the basic ideas of theoretical computer science, concerning formal languages, and the computability and complexity theory.
Skill acquired (at the end of the corse):
By learning these arguments, the students will be able to deal with important computational problems.
Prerequisites
Courses to requirements (required and / or recommended)
Courses required: Algoritmi e Strutture Dati, Architetture degli Elaboratori, Matematica Discreta e Logica, Programmazione.
Courses recommended: Algoritmi e Strutture Dati, Architetture degli Elaboratori, Matematica Discreta e Logica, Programmazione.
Courses required: Algoritmi e Strutture Dati, Architetture degli Elaboratori, Matematica Discreta e Logica, Programmazione.
Courses recommended: Algoritmi e Strutture Dati, Architetture degli Elaboratori, Matematica Discreta e Logica, Programmazione.
Teaching Methods
Total number of hours of the course: 225
Number of hours for personal study and other individual learning: 153
Number of hours for classroom activities: 72
Number of hours for personal study and other individual learning: 153
Number of hours for classroom activities: 72
Further information
Frequency of lessons and exercises: Recommended
Tools to support teaching UniFi E-Learning: http://el.unifi.it
Office hours:
Tuesday and Wednesday, 14:30 to 16:30 or by appointment.
Viale Morgagni, 65 - 50134 Florence
Tel 055 4237452
Fax 055 4796363 - 4237436
E-mail pierluigi.crescenzi @ unifi.it
Tools to support teaching UniFi E-Learning: http://el.unifi.it
Office hours:
Tuesday and Wednesday, 14:30 to 16:30 or by appointment.
Viale Morgagni, 65 - 50134 Florence
Tel 055 4237452
Fax 055 4796363 - 4237436
E-mail pierluigi.crescenzi @ unifi.it
Type of Assessment
Written and oral examination
Course program
Computability theory: the Church-Turing thesis (Turing machines and their variants, notion of algorithm), decidability (decidable languages, halting problem), reducibility (examples of undecidable languages), recursion and Rice theorems, models of computation.
Machines and languages: regular languages (finite state automata, non determinism, regular expressions, non regular languages), context-free languages (context-free grammars, pushdown automata, non context-free languages), context-sensitive automata (linear Turing machines), type 0 languages.
Complexity theory: time complexity (class P, class NP, NP-completeness), space complexity (Savitch theorem, class PSPACE), class EXP.
Machines and languages: regular languages (finite state automata, non determinism, regular expressions, non regular languages), context-free languages (context-free grammars, pushdown automata, non context-free languages), context-sensitive automata (linear Turing machines), type 0 languages.
Complexity theory: time complexity (class P, class NP, NP-completeness), space complexity (Savitch theorem, class PSPACE), class EXP.