Português English
Contato

Lista de Disciplinas | CMP601

Algorithms and Theory of Computation

Professor: Luciana Buriol, Álvaro Freitas Moreira
Prerequisites: –
Hours: 60 hs
Credits: 4
Semesters: First and second semesters
Undergraduate Enrollment: The enrollment must be made as Special Student
Page Link: –

SUMMARY

Theory of Computation: Models of computation. Limits of formal systems. Complexity theory. Algorithms: Analysis of algorithms. Main techniques for designing algorithms.

OBJECTIVES

This course will introduce the students to the main models of computation, justifying each model and comparing them. We will also study classes of problems that can or can not be solved by computers (limits of computation) as well as how to classify the computable problems according to how efficiently they can be solved (complexity theory). Focusing on the algorithms area, we will study the main techniques for designing and analyzing algorithms. After successful completion of the course, the students are expected to: (i) understand what a model of computation is and understand the main models (ii) be able to analyze whether a problem may have an algorithmic solution or not (iii) be able to analyze algorithms using standard techniques; (iv) be able to apply the main techniques in designing algorithms; (v) know the main complexity classes.

PROGRAM

In the Theory of Computation area:
1. Turing Machines and the Church -Turing Thesis (chapter 3 of [1])
2. Decidability and Undecidability (chapters 4 and 5 of [1])

  1. Reducibility (chapter 5 of [1])
  2. Time Complexity and Space Complexity (chapters 7 and 8 of [1])
  3. Intractability (chapter 9 of [1])

In the Algorithms area:
1. Introduction: Some representative Problems (chapter 1 of [2])
2. Basics of Algorithms Analysis (chapter 2 of [2])
3. Graphs (chapter 3 of [2])
4. Greedy Algorithms (chapter 4 of [2])
5. Divide and Conquer (chapter 5 of [2])
6. Dynamic Programming (chapter 6 of [2])

EVALUATION

Students will be evaluated in both areas separately, and the final score will be obtained by the arithmetic mean of the scores of each area. At the end of the semester, there will be an exam that can substitute the final score obtained. The possible grades are A (score >= 9.0), B (score >= 7.5 and < 9.0), C (score >= 6.0 and < 7.5), D (failed, score< 6.0) or FF (failed, the student attended less than 75% of the classes).

BIBLIOGRAPHY

  1. Michael Sipser. Introduction to the Theory of Computation, Cengage Learning, 2013
    2. J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley,2005.