Module Identifier | CS10310 | ||||||||||||||
Module Title | INTRODUCTION TO THEORETICAL COMPUTER SCIENCE | ||||||||||||||
Academic Year | 2006/2007 | ||||||||||||||
Co-ordinator | Dr Edel M Sherratt | ||||||||||||||
Semester | Semester 1 | ||||||||||||||
Other staff | Dr Edel M Sherratt, Dr Lynda A Thomas | ||||||||||||||
Pre-Requisite | A level or AS level maths. | ||||||||||||||
Mutually Exclusive | CS10410 | ||||||||||||||
Course delivery | Lecture | ||||||||||||||
Seminars / Tutorials | Up to 5 one hour workshops | ||||||||||||||
Practical | Up to 5 two hour practicals that relate the theory to programming languages | ||||||||||||||
Assessment |
|
Motivation - relationship with programs. What are sets and how do we describe them. When to use enumeration and when to use predicates. The set of truth values. Cardinality. Subsets. Using sets to specify pre- and post-conditions for programs. Sets and sequences. Set union, intersection, difference. Universal set. Complement of a set. Venn-Euler diagrams. Cartesian product. Powerset. Examples of proofs.
2. Functions (maps) - 2 Lectures
What are functions and how do we represent them - pictorially, using definitions, injection, bijection, surjection. Functions and the meaning of assignment. Variables. States and operations that cause a change of state. Functions. Relations and logical conditions.
3. Languages and Problems - 10 Lectures
Motivation: computation entails using language to describe and solve problems.
Symbols, alphabets. Strings. String concatenation. Alphabets and strings.
Languages. Language union, intersection, difference and symmetric difference. Language concatenation. Kleene star.
Regular expressions and regular languages. Deterministic finite automata. Nondeterministic Finite Automata. Languages that are not regular. The Pumping Lemma (simple and general forms). Proving that a language is/is not regular. Closure properties of regular language. Using the closure properties to prove that a language is not regular.
Context free languages. Context free grammars. Derivations of context free grammars. Context free grammars and regular grammars. Pushdown automata. Languages that are not context free. Context free languages are not closed under intersection. Context free languages are not closed under complementation. Context free languages are closed under union.
4. Turing Machines - 6 Lectures
What are Turing machines? Beyond context free languages. Example. What does Computable mean? The Halting Problem.
Problem_solving | Inherent to subject. Assessed in assignment and exam. | ||
Research skills | no | ||
Communication | no | ||
Improving own Learning and Performance | Reflection and self-learning will be encouraged during all sessions. In addition the assignment will allow students to reflect on their learning to date. | ||
Team work | no | ||
Information Technology | In practicals students will relate concepts to computing languages | ||
Application of Number | Inherent to subject. Assessed in assignment and exam | ||
Personal Development and Career planning | no | ||
Subject Specific Skills | See contents |
This module is at CQFW Level 4