COMP6363
Theory of Computation
- Credit
- 6 units
- Catalogue year
- 2027
- Recorded offerings
- First Semester
Course information
This course covers the theoretical computer science areas of formal languages and automata, computability and complexity. Topics covered include the following: regular and context-free languages; finite automata and pushdown automata; Turing machines; computability - halting problem, solvable, and unsolvable problems; space and time complexity; classes P, NP and PSPACE; NP-Completeness.
Requisite and Incompatibility
To enrol in this course you must be studying Master of Computing OR Master of Computing (Advanced). Incompatible with COMP3630.
Learning Outcomes
Upon successful completion, students will have the knowledge and skills to:
Demonstrate advanced knowledge of formal computation and its relationship to languages
Distinguish different computing languages and classify their respective types
Recognise and comprehend formal reasoning about languages
Demonstrate a competent understanding of the concepts of complexity theory
Saved ANU Programs & Courses information, 2027. Future offerings are indicative. Checks use the saved requirements and your fictional academic record.
Saved requirements encoded for automatic checks. See your requirement checks for what can be decided.
Course library: sources, offering dates and related entries
Read the full published course information ↗
Who reviews permission requests?
Dr Sam Achterberg is the fictional reviewer assigned to COMP6363 in this prototype. The selected course determines where a request goes.
Make this part of your semester
Sign in to check your fictional academic record, save this offering, and request permission if needed.
Sign in