|
Module Title |
Languages and Computability
|
|
Module Code |
CA215
|
|
School |
Computing
|
Online Module Resources
|
| Module Co-ordinator | Prof Andy Way | Office Number | L2.01C |
|
Level |
2
|
Credit Rating |
5
|
|
Pre-requisite |
None
|
|
Co-requisite |
None
|
|
|
Module Aims
|
The aims of this module are: 7 To give students a grounding in formal language theory. 7 To give students a grounding in the theory of computation. 7 To study the relationships between languages, computational models and computational problems.
|
|
Learning Outcomes
|
As a result of this module, students will have a good understanding of the following: 7 formal language theory. 7 automata theory. 7 the correspondence between language theory and automata theory. 7 computability and the limits of computation
|
|
Indicative Time Allowances
|
|
|
Hours
|
|
Lectures |
24
|
|
Tutorials |
0
|
|
Laboratories |
24
|
|
Seminars |
0
|
|
Independent Learning Time |
27
|
|
|
|
|
Total |
75
|
|
Placements |
|
|
Assignments |
|
|
|
NOTE
|
Assume that a 5 credit module load represents approximately 75 hours' work, which includes all teaching, in-course assignments, laboratory work or other specialised training and an estimated private learning time associated with the module.
|
|
Indicative Syllabus
|
|
Students will study the following: Mathematical Prerequisites o sets o cardinality and countability o functions o relations o induction and recursion o languages o grammars Regular Languages and Finite Automata o regular languages o regular expressions o finite automata o DFAs and NFAs o converting NFAs to DFAs o Kleene''s theorem o pumping lemma for regular languages Context-Free Languages and Pushdown Automata o context-free grammars o derivations and anbiguity o pushdown automata o deterministic pushdown automata o pumping lemma for context-free languages o parsing Context-Sensitive Languages and Linear Bounded Automata Turing Machines o models of computation o definition of Turing machines o Turing machines as language acceptors o computing with Turing machines o extensions of Turing machines o non-deterministic Turing machines Recursively Enumerable and Recursive Languages o recursively enumerable o recursive o enumerating languages Unsolvable Problems o Church-Turing thesis o universal Turing machines o the halting problem o reducibility o Rice''s theorem Complexity o Big O Notation o The Class P o Problems in P o The Class NP o Problems in NP o Reducibility o NP-Completeness o Cook''s Theorem
|
| Assessment | | Continuous Assessment | 25% | Examination Weight | 75% |
|
|
Indicative Reading List
|
|
Essential Elements of the Theory of Computation , H.R. Lewis and C.H.Papadimitriou, Prentice Hall, 1998 ISBN: 0-13-272741-2 Supplementary Theory of Computing: A Gentle Introduction. Efim Kinber & Carl Smith. Prentice Hall ISBN 0-13-027961-7.The Theory of Computation. B. M. Monet Addison-Wesby ISBN 0-201-25828-5Introduction to Languages and the Theory of Computation , J.C. Martin, McGraw-Hill, 1997 ISBN: 0-07-115468-X Introduction to the Theory of Computation , M. Sipser, PWS Publishing Company, 1996 ISBN: 0-53-494728-X
|
|
|
|
Programme or List of Programmes
|
| BSSA | Study Abroad (DCU Business School) |
| BSSAO | Study Abroad (DCU Business School) |
| CASE | BSc in Computer Applications (Sft.Eng.) |
| ECSA | Study Abroad (Engineering & Computing) |
| ECSAO | Study Abroad (Engineering & Computing) |
| HMSA | Study Abroad (Humanities & Soc Science) |
| HMSAO | Study Abroad (Humanities & Soc Science) |
| SHSA | Study Abroad (Science & Health) |
| SHSAO | Study Abroad (Science & Health) |
| Timetable this semester: Timetable for CA215 |
| Date of Last Revision | 28-NOV-08 |
| Archives: | |
