No offerings have been identified for this subject in 2015
ITC562 Theory of Computation (8)
Abstract| This subject provides the basis for advanced work in theoretical computer science. Finite automata, pushdown automata and Turing machines and their associated languages (regular, context-free and phrase structure languages) are studied. Some practical applications of these abstract machines are covered in the context of language translation. Tools to support language translation are studied. |
|
|
+ Subject Availability Modes and Location
Continuing students should consult the SAL for current offering details prior to contacting their course coordinator: ITC562
Where differences exist between the handbook and the SAL, the SAL should be taken as containing the correct subject offering details.
|
|
Subject information| Duration | Grading System | School: |
|---|
| One session | HD/FL | School of Computing and Mathematics |
|
|
Enrolment restrictions| Restricted to students in the Bachelor of Information Technology (Honours) and Bachelor of Computer Science (Games Technology)(Honours). |
|
|
Learning OutcomesUpon successful completion of this subject, students should:
* know and be able to understand the mathematical, historical and practical background of the theory of computation;
* be able to understand and prove the capabilities and limitations of the following abstract machines: finite automata, pushdown automata, and Turing machines and their associated languages: regular languages, context-free languages and phrase-structure languages;
* be able to understand the structure of the compilation process of a formal language and understand where the above mentioned abstract machines can be used in this process;
* know how to use tools to assist in the construction of the first stages of a compiler and know the relationship between these tools and the above mentioned abstract machines;
* be able to understand and use recursive function theory and know its relationship to the above mentioned abstract machines;
* know the relationship between symbolic computation and neural networks;
* be able to understand the concept of complexity and analyse the complexity of algorithms;
* know, understand and appreciate some of the philosophical implications of computation theory. |
|
|
SyllabusThe subject will cover the following topics:
. Review of function theory.
. Review of set theory.
. Grammatical basis of language translation.
. Historical background of the theory of computation.
. Finite state machines and regular languages.
. Pushdown automata and context-free languages.
. Turing machines and phase-structure languages.
. Lexical analysis using the LEX utility.
. Parsing using the YACC utility.
. Computability and recursive function theory.
. Complexity.
. Artificial neural networks. |
|
|
Back
The information contained in the 2015 CSU Handbook was accurate at the date of publication: 01 October 2015. The University reserves the right to vary the information at any time without notice.
