Module Title:   Formal Foundations (PG)

Module Credit:   20

Module Code:   CM-1037D

Academic Year:   2015/6

Teaching Period:   Semester 1

Module Occurrence:   A

Module Level:   FHEQ Level 7

Module Type:   Standard module

Provider:   Computer Science

Related Department/Subject Area:   SCIM (Dept of Computer Science)

Principal Co-ordinator:   Prof A Vourdas

Additional Tutor(s):   Dr A Csenki, Dr D R W Holton

Prerequisite(s):   None

Corequisite(s):   None

To provide the foundations for the formal specification and modelling of computer systems.
To equip students for more advanced studies in programming and show them the limitations of what programming can achieve.

Learning Teaching & Assessment Strategy:
The delivery of the module will consist of lectures and tutorials.

Lectures:   36.00          Directed Study:   152.00           
Seminars/Tutorials:   12.00          Other:   0.00           
Laboratory/Practical:   0.00          Formal Exams:   0.00          Total:   200.00

On successful completion of this module you will be able to...

Master the mathematical tools inherent in the construction and analysis of computing systems, and of the fundamental concepts of computer theory.

On successful completion of this module you will be able to...

Appreciate and in your later academic life use the concept of recursion,
Appreciate the importance of strings and string processing in Computer Science,
Be aware of tools (such as egrep) using regular expressions,
Recognize computer programs as implementations of algorithms and appreciate their limitations

Apply mathematical techniques which are necessary for the design and evaluation of computer programs and computer systems.

On successful completion of this module you will be able to...

Conduct a critical analysis in the area of computer systems, its basics and more advanced features.

  Coursework 1.00 15%
  Coursework/Test:Computer Theory
  Examination - closed book 2.00 85%
  Discrete Maths; Computer Theory; Queing Networks
  Examination - closed book 2.00 100%
  Supplementary assessment

Outline Syllabus:
Sets and relations. Logic, propositional logic, first order logic. Functions. Graph theory. Proof by induction. Basic concepts of formal language theory; alphabets, strings, languages. Operations on strings and languages. Recursive definitions. Regular expressions. Finite automata. Deterministic and non-deterministic finite automata. Kleenes theorem. Turing machines. Computability. Decidability. Introduction to Probability and Statistics; simple Queuing Models.


(Computer Theory only)

Daniel Cohen: Introduction to Computer Theory, Wiley, New York, 1999.

(About half of this book will be `covered`, albeit in a conversational, sometimes informal, style appropriate for the material & audience.)

Version No:  5