{"id":6782,"date":"2024-09-03T10:21:55","date_gmt":"2024-09-03T13:21:55","guid":{"rendered":"https:\/\/www.inf.ufrgs.br\/profcomp\/?page_id=6782"},"modified":"2024-09-03T10:21:55","modified_gmt":"2024-09-03T13:21:55","slug":"cmp626","status":"publish","type":"page","link":"https:\/\/www.inf.ufrgs.br\/profcomp\/lista-de-disciplinas\/cmp626\/","title":{"rendered":"CMP626"},"content":{"rendered":"

CMP626 – Theory of Computation<\/strong><\/h3>\n

Professor<\/b>: \u00c1lvaro e Henrique
\nPrerequisites<\/b>: \u2013
\nHours<\/b>: 60 hs
\nCredits<\/b>: 4
\nSemesters<\/b>: First and second semesters
\nUndergraduate Enrollment<\/b>: \u2013
\nPage Link<\/b>: \u2013<\/p>\n

SUMMARY<\/strong><\/p>\n

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<\/p>\n

OBJECTIVES<\/strong><\/p>\n

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
\ntheory). 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.<\/p>\n

PROGRAM<\/strong><\/p>\n

    \n
  1. Turing Machines and the Church-Turing Thesis<\/li>\n
  2. Decidability and Undecidability<\/li>\n
  3. Reducibility<\/li>\n
  4. Time Complexity Classes<\/li>\n
  5. Space Complexity Classes<\/li>\n
  6. Intractability<\/li>\n<\/ol>\n

    EVALUATION<\/strong><\/p>\n

    Students will be submitted to two partial evaluations during the semester, each evaluation\u00a0 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).<\/p>\n

    BIBLIOGRAPHY<\/strong><\/p>\n

    Sipser, Michael. Introduction to the Theory of Computation<\/em>, Cengage Learning, 2013.
    \nHarel, David. Algorithmics: The Spirit of Computing<\/em>. MIT Press. 2004
    \nFerreira Filho, Wladston. Computer science distilled: learn the art of solving computational problems<\/em>. Code Energy, 2017.<\/p>\n

     <\/p>\n","protected":false},"excerpt":{"rendered":"

    CMP626 – Theory of Computation Professor: \u00c1lvaro e Henrique Prerequisites: \u2013 Hours: 60 hs Credits: 4 Semesters: First and second semesters Undergraduate Enrollment: \u2013 Page Link: \u2013 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. […]<\/p>\n","protected":false},"author":11,"featured_media":0,"parent":462,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/6782"}],"collection":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/users\/11"}],"replies":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/comments?post=6782"}],"version-history":[{"count":1,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/6782\/revisions"}],"predecessor-version":[{"id":6783,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/6782\/revisions\/6783"}],"up":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/462"}],"wp:attachment":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/media?parent=6782"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}