- CMP625
- CMP626
- CMP628
- CMP630
- CMP629
- CMP631
- CMP102
- CMP117
- CMP119
- CMP121
- CMP124
- CMP134
- CMP135
- CMP143
- CMP147
- CMP148
- CMP150
- CMP157
- CMP158
- CMP165
- CMP166
- CMP167
- CMP169
- CMP176
- CMP177
- CMP182
- CMP187
- CMP189
- CMP191
- CMP192
- CMP193
- CMP194
- CMP195
- CMP196
- CMP197
- CMP198
- CMP199
- CMP223
- CMP230
- CMP231
- CMP234
- CMP235
- CMP236
- CMP237
- CMP238
- CMP241
- CMP242
- CMP244
- CMP246
- CMP248
- CMP249
- CMP258
- CMP259
- CMP262
- CMP263
- CMP264
- CMP265
- CMP266
- CMP267
- CMP268
- CMP269
- CMP270
- CMP271
- CMP273
- CMP30(X)
- CMP410
- CMP411
- CMP527
- CMP537
- CMP545
- CMP552
- CMP567
- CMP568
- CMP570
- CMP571
- CMP574
- CMP581
- CMP585
- CMP586
- CMP587
- CMP588
- CMP592
- CMP594
- CMP595
- CMP596
- CMP597
- CMP598
- CMP599
- CMP602
- CMP603
- CMP604
- CMP605
- CMP606
- CMP607
- CMP608
- CMP609
- CMP610
- CMP611
- CMP612
- CMP613
- CMP614
- CMP615
- CMP617
- CMP618
- CMP619
- CMP620
- CMP621
- CMP622
Lista de Disciplinas | CMP626
CMP626 – Theory of Computation
Professor: Álvaro e Henrique
Prerequisites: –
Hours: 60 hs
Credits: 4
Semesters: First and second semesters
Undergraduate Enrollment: –
Page Link: –
SUMMARY
Computability Theory: Model of Computation – Turing Machines. Church-Turing Thesis. Decidability. Reduction. Complexity theory: Time Complexity, Asymptotic analysis, worst-case analysis. Tractability – Edmond-Cobham Thesis. Time Complexity Classes. NP-Complete Problems. Space Complexity Classes
OBJECTIVES
This course will introduce Turing Machines as a model of computation and will study classes of problems that can or can not be solved by computers (computability theory) and how to classify the computable problems according to how efficiently they can be solved (complexity
theory). After successful completion of the course, the students are expected to: (i) understand what a model of computation is and understand the main model, (ii) be able to analyze whether a problem may have an algorithmic solution and if it is tractable, and (iii) know the main complexity classes.
PROGRAM
- Turing Machines and the Church-Turing Thesis
- Decidability and Undecidability
- Reducibility
- Time Complexity Classes
- Space Complexity Classes
- Intractability
EVALUATION
Students will be submitted to two partial evaluations during the semester, each evaluation with 40% of the final grade. The other 20% will be obtained through class assignments. 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, scoreb< 6.0) or FF (failed, the student attended less than 75% of the classes).
BIBLIOGRAPHY
Sipser, Michael. Introduction to the Theory of Computation, Cengage Learning, 2013.
Harel, David. Algorithmics: The Spirit of Computing. MIT Press. 2004
Ferreira Filho, Wladston. Computer science distilled: learn the art of solving computational problems. Code Energy, 2017.