COMP10042: Fundamentals of Computation (2008-2009)
The building of real-life computing systems, e.g. mobile phone, tv/video remote control, internet shopping, air-traffic control, internet banking, etc., is always a complex task. Mistakes can be very annoying, costly and sometimes life threatening. Methods and techniques to support the building and understanding of such systems are essential. This course unit provides an introduction to the basic computer science ideas underlying such methods. It is also a part of, and an introduction to, the Modelling and Rigorous Development theme.
This course unit provides a first approach to answering the following questions. What methods are there that can help understanding complicated systems or programs? How can we make sure that a program does what we intend it to do? How do computers go about recognizing pieces of text? If there are two ways of solving the same problem, how can we compare them? How do we measure that one of them gives the solution faster? How can we understand what computers can do in principle, and are there problems that are not solvable by a computer?
On successful completion of this course unit, students should:
-- be able to construct simple graph-based models of computation, e.g., finite state automata;
-- undestand how patterns and grammars can be used to recognise pieces of text;
-- be able to build simple set-theoretic models of systems;
-- be able to use models in order to reason about a system;
-- appreciate that there are unsolvable problems;
-- understand fundamental techniques for measuring performance of systems;
-- gain skills in modelling and abstract thinking.
Assessment of Learning outcomesAll learning outcomes are assessed by examples class assessment and examination (May/June).
There are three groups of topics covered.
The first (8 lectures) treats the fundamental concepts of finite state automata. Alternative equally expressive formalisms, such as regular expressions (most often used in pattern matching), regular languages and regular grammars will be introduced. More expressive languages and their role, e.g. context free languages, will be given.
The second group (8 lectures) is central to the practice of system development. It introduces: set-theoretic models as a set of objects and associated operations; operations specified by pre and post conditions; simple techniques for determining properties of set-theoretic models.
The third group (4 lectures) provides a brief introduction to the two topics of computability and computational complexity. It covers the classical "Halting Problem" and then simple time and space complexity measures.
The course is supported by lecture notes. Additional reading material will be supplied.