Registry
Module Specifications
Archived Version 2020 - 2021
| |||||||||||||||||||||||||||||||||||||||||
Description The goal of this module is to provide an insight into the fundamental capabilities and limitations of computers. This module will expose students to three central areas of the theory of computation: automata, computability and complexity. With respect to automata, a number of languages of increasing descriptive power will be studied as well as corresponding automata which can be used to recognise these languages. With respect to computability, it will be shown which problems can or cannot be solved by computer. A number of different models of computation will be studied, and it will be shown that these are all of equivalent computational power. With respect to complexity, it will be shown for those problems which can be solved by computer whether they can be solved within a reasonable amount of time and space. | |||||||||||||||||||||||||||||||||||||||||
Learning Outcomes 1. Determine which languages are descriptive enough to describe particular problems. 2. Determine which automata are powerful enough to solve particular problems. 3. Design languages to describe particular problems. 4. Design automata to solve particular problems. 5. Solve problems using a number of different models of computation. 6. Determine whether a given problem can be solved by computer. 7. Determine whether a given problem can be solved within a reasonable amount of time. 8. Determine whether a given problem can be solved within a reasonable amount of space. | |||||||||||||||||||||||||||||||||||||||||
All module information is indicative and subject to change. For further information,students are advised to refer to the University's Marks and Standards and Programme Specific Regulations at: http://www.dcu.ie/registry/examinations/index.shtml |
|||||||||||||||||||||||||||||||||||||||||
Indicative Content and
Learning Activities IntroductionSets, Functions, Languages and AlgorithmsRegular languages and finite automataRegular grammars, Regular expressions and Finite state automataContext-free languages and pushdown automataContext-free grammars, Derivations and ambiguity and Pushdown automataContext-sensitive grammars and linear bounded automataContext-sensitive grammars, Context-sensitive languages and Linear bounded automataModels of computationTuring machines, Unrestricted grammars, Partial recursive functions, Lambda calculus, Haskell, Cellular automata and Church-Turing thesis.ComputabilityHalting problem , Reducibility and Other uncomputable problemsComplexityAsymptotic notation, The class P, The class NP, NP-completeness, Space complexity, The class PSPACE, PSPACE-completeness and The class EXP | |||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||
Indicative Reading List
| |||||||||||||||||||||||||||||||||||||||||
Other Resources None | |||||||||||||||||||||||||||||||||||||||||
Programme or List of Programmes |
CASE | BSc in Computer Applications (Sft.Eng.) |
CPSSD | BSc in ComputationalProblem Solv&SW Dev. |
ECSA | Study Abroad (Engineering & Computing) |
ECSAO | Study Abroad (Engineering & Computing) |
- See the module specification for CA320 in 2003 - 2004
- See the module specification for CA320 in 2004 - 2005
- See the module specification for CA320 in 2005 - 2006
- See the module specification for CA320 in 2006 - 2007
- See the module specification for CA320 in 2007 - 2008
- See the module specification for CA320 in 2008 - 2009
- See the module specification for CA320 in 2009 - 2010
- See the module specification for CA320 in 2010 - 2011
- See the module specification for CA320 in 2011 - 2012
- See the module specification for CA320 in 2012 - 2013
- See the module specification for CA320 in 2013 - 2014
- See the module specification for CA320 in 2014 - 2015
- See the module specification for CA320 in 2015 - 2016
- See the module specification for CA320 in 2016 - 2017
- See the module specification for CA320 in 2017 - 2018
- See the module specification for CA320 in 2018 - 2019
- See the module specification for CA320 in 2019 - 2020
- See the module specification for CA320 in 2020 - 2021
- See the module specification for CA320 in 2021 - 2022
- See the module specification for CA320 in 2022 - 2023
- See the module specification for CA320 in 2023 - 2024
- See the module specification for the current year