Show/hide contentOpenClose All
Curricular information is subject to change
On completion of this module students should be able to:
- Define and use general concepts like computation, algorithm, and language;
- Work with several models of computing including finite state machines, Turing machines, and automata;
- Use appropriate computation models for real applications;
- Understand and use notions of computability and decidability, and their limits;
- Understand and explain the relationships between mathematical proof and computation.
The topics covered in this module are:
1. Regular Languages (Finite Automata, Regular Expressions)
2. Context-free Languages (Pushdown Automata, Context-free Grammars)
3. Recursively Enumerable Languages (Turing Machines)
4. Undecidability (Does a computer solution/algorithm exist?)
5. Intractability (Can it be solved fast?)
Student Effort Type | Hours |
---|---|
Lectures | 24 |
Tutorial | 22 |
Autonomous Student Learning | 76 |
Total | 122 |
Students should have basic knowledge of mathematics (including set theory, functions and relations, logic, and basic proof techniques) to
attend for this module. Students unfamiliar with these topics must
attend remedial tutorials at the beginning of the semester.
It is strongly recommended that students take and pass all first and
second stage theory modules in CS before taking this module.
Description | Timing | Component Scale | % of Final Grade | ||
---|---|---|---|---|---|
Continuous Assessment: Homework Assignments | Varies over the Trimester | n/a | Alternative linear conversion grade scale 40% | No | 30 |
Class Test: One or more in-class test(s) | Varies over the Trimester | n/a | Alternative linear conversion grade scale 40% | No | 70 |
Resit In | Terminal Exam |
---|---|
Spring | No |
• Feedback individually to students, post-assessment
• Group/class feedback, post-assessment
Not yet recorded.
Name | Role |
---|---|
Mr Jim Quinn | Tutor |