臺大課程網
最新消息幫助中心預選課表

計算理論

112-2 開課

  • 流水號

    54099

  • 課號

    IM3006

  • 課程識別碼

    705 30400

  • 無分班

  • 3 學分

  • 選修

    資訊管理學系

      選修

    • 資訊管理學系

  • 蔡益坤
  • 二 7, 8, 9

  • 管二203

  • 2 類加選

  • 修課總人數 40 人

    本校 36 人 + 外校 4 人

  • 無領域專長

  • 中文授課
  • NTU COOL
  • 核心能力與課程規劃關聯圖
  • 備註
    本課程中文授課,使用英文教科書。部份週次之週二6有實習課，地點同上課教室。

  • 本校選課狀況

    已選上
    0/36
    外系已選上
    0/8
    剩餘名額
    0
    已登記
    0
  • 課程概述
    This is an introductory course to the theory of computing, a study of formal/mathematical foundations of computer science and technology. It covers various mathematical models, including automata and Turing machines, for physical computing machineries along with their computational capabilities/limitations. In terms of specific topics and the order of their exposition, the course will follow closely the book by Sipser.
  • 課程目標
    The goal of this course is to acquaint the students with the basic concepts in computation theory and to cultivate the students' ability in analyzing the complexity of computational problems.
  • 課程要求
    The students are assumed to have taken a course on Algorithms. There will be two exams and ten homework assignments. Class participation will also be taken into account in grading.
  • 預期每週課後學習時數
    About 4.5 hours.
  • Office Hour
    星期二13:30 - 14:00
    星期三13:30 - 14:00

    Or by appointment using email.

  • 指定閱讀
    Introduction to the Theory of Computation, 3rd Edition, Michael Sipser, Cengage Learning, 2012.
  • 參考書目
    See the course wiki site: http://im.ntu.edu.tw/~tsay/dokuwiki/doku.php?id=courses:theory2024:main
  • 評量方式
    35%

    Final Exam

    35%

    Midterm Exam

    10%

    Participation

    20%

    Homework

    There are ten homework assignments.

  • 針對學生困難提供學生調整方式
    調整方式說明
    上課形式

    以錄音輔助

    作業繳交方式

    延長作業繳交期限

    考試形式

    延後期末考試日期(時間)

    其他

    由師生雙方議定

  • 課程進度
    2/20第 1 週Introduction and Mathematical Preliminaries
    2/27第 2 週Introduction and Mathematical Preliminaries; Finite Automata and Regular Languages
    3/5第 3 週Finite Automata and Regular Languages
    3/12第 4 週Finite Automata and Regular Languages
    3/19第 5 週Context-Free Languages and Pushdown Automata
    3/26第 6 週Context-Free Languages and Pushdown Automata
    4/2第 7 週Context-Free Languages and Pushdown Automata
    4/9第 8 週Midterm
    4/16第 9 週Turing Machines
    4/23第 10 週Turing Machines; Decidability (and Undecidability)
    4/30第 11 週Decidability (and Undecidability)
    5/7第 12 週Decidability (and Undecidability); Reducibility
    5/14第 13 週Reducibility
    5/21第 14 週Time Complexity and NP-Completenes
    5/28第 15 週Time Complexity and NP-Completenes
    6/4第 16 週Final