Computability

Code:

CC333

Acronym:

CC333

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2015/2016 - 2S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~rvr/aulas/AC1516/CC15-16/
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Bachelor in Geology

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L:AST	0	Plano de Estudos a partir de 2008	3	-	7,5	-
L:B	0	Plano de estudos a partir de 2008	3	-	7,5	-
L:F	0	Plano de estudos a partir de 2008	3	-	7,5	-
L:G	0	P.E - estudantes com 1ª matricula anterior a 09/10	3	-	7,5	-
		P.E - estudantes com 1ª matricula em 09/10	3	-	7,5	-
L:M	0	Plano de estudos a partir de 2009	3	-	7,5	-
L:Q	0	Plano de estudos Oficial	3	-	7,5	-

Teaching language

Portuguese

Objectives

Study and comparison of different (Turing-complete) models of computation, their computational power and limitations.

After completing this course students are expected to

- know the classical models of computation;
- be able to prove the equivalence of several Turing-complete models;
- know the fundamental results and methods used in the study of computability and complexity;
- be able to classify concrete examples of problems and prove their (un)decidability within several classes of computability.

Learning outcomes and competences

Students are exposed to different standard Turing-complete models of

computation, such as register machines, Turing machines e recursive

functions. Besides proving the equivalence of those models, they also

are used to identify different undecidable problems. For this,

different techniques, such as the diagonalization method and the

reduction between languages are used. In order to gain experience

identifying the computational complexity of concrete problems,

students are introduced to the classes P and NP, the notion of

NP-completeness and Cook’s theorem, revisiting again the reduction

technique.

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

Knowledge of some models of computation such as Finite Automata, Regular Expressions and Context-free Grammars. Basic notions of Logic.

Program

Notion of (semi-)decidable language/problem. Revision of some models of computation (DFA, NFA, CFG and PDA) and their power of computation. Register machines. Church-Turing thesis. Chomsky hierarchy. Study of other Turing-complete models of computation and their equivalence (Turing machines, recursive functions). Effective enumerability of the instances of a model of computation. The diagonalization method and the indecidability of the halting-problem. Reduction “many to one” between languages. Introduction to complexity theory: P and NP classes, NP-completeness, Cook’s theorem and other NP-complete problems.

Mandatory literature

Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani and Ullmann.
Recursion theory, Phillips, in Handbook of logic in computer science (vol. 1), Oxford University Press.
Computabilidade e Decidibilidade, Sabine Broda.

Complementary Bibliography

Introduction to the Theory of Computation, Michael Sipser.
Models of Computation - An Introduction to Computability Theory, Maribel Fernández.
Oded Goldreich; P, NP, and NP-Completeness - The Basics of Computational Complexity, Cambridge University Press, 2010

Teaching methods and learning activities

Lectures: exposition of the elements in the syllabus.
Lab classes: resolution of exercises proposed each week.

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	100,00
Total:	100,00

Eligibility for exams

N/a

Calculation formula of final grade

The final mark corresponds to the classification obtained
- as average grade of two tests to be realized during the semester (each with a classification of at least 7 out of 20 points);
- or the grade of the final exam.

 

Students with approval on behalf of the grades of their tests, might nevertheless go to the final exam and their final mark in the course will be the better of both classifications.

Examinations or Special Assignments

There will be two non-obligatory tests to be realized during the semester