FIT2014
Theory of computation
基本信息
| 学分 | 6 credit points |
|---|---|
| 开课学期 | First semester / Second semester |
| 校区 | Malaysia |
| 考核构成 | Scheduled final assessment (3 hours and 10 minutes) — 50% Practical Preparation — 5% Mid-semester Test — 15% Assignment 1: Regular Expressions and Finite Automata — 10% Assignment 2: Lexical Analysis, Parsing, Computability — 20% |
开课安排2 条
| 教学期 | 授课方式 | 状态 |
|---|---|---|
| Second semester | Teaching activities are on-campus (ON-CAMPUS) | 开课 |
| First semester | Teaching activities are on-campus (ON-CAMPUS) | 开课 |
以上为该校区在官方资料中登记的全部开课安排，不是汇总。同一门课可能在多个 教学期开课，也可能不同教学期的授课方式不同。
课程简介
This unit introduces formal languages, models of computation, and computational complexity. It looks at what computers can and cannot compute. Topics include finite state automata, regular expressions, grammars, pushdown automata, computable functions, Turing machines, polynomial-time reductions, complexity classes P and NP, and NP-completeness. Skills at writing formal proofs will be developed.
以上为 Monash Handbook 的官方原文，版权属 Monash University，此处按本站要求转载并标注出处： 官方页面 ↗
学习成果10 条
官方原文（Learning outcomes），版权属 Monash University。
- ULO1 Use propositional logic, predicates and quantifiers to represent and analyse problems in the theory of computation;
- ULO10 Write rigorous formal proofs, including proofs by construction, cases, contradiction and induction.
- ULO2 Construct Finite Automata, Nondeterministic Finite Automata and Context-Free Grammars to describe languages;
- ULO3 Convert Regular Expressions into Finite Automata and vice versa;
- ULO4 Find a Regular Grammar for a Regular Language;
- ULO5 Find a parse tree, leftmost derivation and rightmost derivation for a word in a Context Free Language;
- ULO6 Use Turing Machines to describe languages and represent computable functions;
- ULO7 Demonstrate the limitations of the models of computation considered;
- ULO8 Show a language is not regular, or not context-free, or not decidable;
- ULO9 Show that a language is in P, or in NP, or NP-complete;
教学方式与预期工作量
教学方式
Enquiry-based learning
Active learning
Peer assisted learning
Problem-based learning
预期工作量
Minimum total expected workload to achieve the learning outcomes for this unit is 144 hours per semester typically comprising a mixture of scheduled online and face to face learning activities and independent study. Independent study may include associated reading and preparation for scheduled teaching activities.
官方原文，版权属 Monash University。
先修 / 同修要求
以下先修关系按官方来源的结构化先修字段解析，原始记号：(FIT1008 OR FIT1054 OR FIT2085 OR MTH2021 OR MTH2025 OR MTH2140 OR MTH3140 OR MTH2141 OR MTH3141) AND (FIT1058 OR MAT1830 OR MTH1035 OR ATS2866)
先修链路
按官方先修字段的原始分组展开，AND / OR 的区别保留着—— 「A 或 B」和「A 与 B」在选课时是两回事。每门课点进去可以继续往下看。
属于这些学位1 个
这门课出现在下列学位的官方结构里。反过来说：如果你读的是这些学位之一，它大概率是要修的 （必修还是选修取决于它在 Part 里的位置，点进去看结构）。
数据来源
- 数据来源
- 官方网页
handbook.monash.edu ↗ - 抓取时间
- 2026-09-13
- 可信度
- 程序抓取，未人工核实
查看官方完整描述 ↗ — 事实性字段（代码、学分、教学期、授课方式、考核权重、先修/同修/互斥关系）与 课程简介、学习成果、教学方式、预期工作量均取自官方 Handbook； 正文版权属 Monash University，此处转载并逐处标注出处。
发现信息有误？告诉我们。请用自己的话描述问题，不要上传成绩单、截图或校内系统文件。