- People
- Obligatory exercise
- Course description
- Lecture slides and notes
- Tutorial Exercises
- Assignments
- General Information & Other Resources
| Lecturer: | Dave
Robertson | dr@inf.ed.ac.uk |
| Teaching Assistant: | Tom French | T.R.French@sms.ed.ac.uk |
You will be required to do an exercise (to appear here by 13th
November) and submit it (on
paper) to the Informatics Teaching Organisation office on Level 4 of
Appleton Tower by noon on Friday 21st of November. The aim of this
exercise is to give you practice at tackling exam-style questions.
3a. Aims and Objectives
The goal of this course is to introduce the notions of computation and
specification using finite-state systems and propositional logic.
Finite state machines provide a simple model of computation
that is widely used, has an interesting meta-theory and has immediate
application in a range of situations. They are
used as basic computational models across the whole of Informatics and
at the same time are used successfully in many widely used
applications and components. Propositional logic, similarly is the
first step in understanding logic which is an essential element of the
specification of Informatics systems and their properties.
3b. Syllabus
This course provides students with experience of theory
in practical applications. An unordered list of topics is as follows:
- A brief introduction of computation as a process and a method of
modelling behaviour. Discussion of the advantages of moving to simple
models that are appropriate for restricted classes of tasks.
Discussion of the importance of correctness of computational
procedures, and how logic can be used to reason about correctness.
- Reasoning: Propositional logic, its connectives and the meaning
of those connectives in terms of truth tables. The concepts of
satisfiability, validity and proof. The relationship between a
proof and the validity of an implication in terms of truth tables.
- Computation: the definition as acceptor and transducer,
deterministic/non deterministic machines, regular
expressions, operations on FSMs,
discussion of formal limits, how good are FSMs as a model of
interactions.
- Applications/Modelling: simple examples drawn from a number of
domains, design issues, using operations on FSMs to structure
solutions, more complex examples: dialogue systems, controllers,
digital watch, regular expressions and pattern matching. Application
areas such as robotic controllers.
- Engineering: how do we specify, test and debug FSM's, design by
decomposition, concurrency, size of machines.
- Logic in use: Basic introduction to propositional modal logic,
satisfaction, validity, proof, model checking. Examples of how such
logics have wide applicability in expressing properties of
computational systems.
- Tools: examples of logic/FSM based tools in system building.
3c. Context
This course supplies foundational knowledge for Informatics courses
taken in subsequent years of study. It runs alongside the Informatics
1 Functional Programming course, which provides complementary
experience in programming.
4a. Logic
4b. Finite State Machines
- FSM notes:
Section 1,
Section 2,
Section 3,
Section 4,
Section 5,
Section 6,
Section 7.
- Lecture slides:
Lecture 1,
Lecture 2,
Lecture 3,
Lecture 4,
Lecture 5,
Lecture 6,
Lecture 7.
Lecture 8.
4c. Concluding Lectures
There is a single assignment for Computation and Logic. See the
Informatics 1A timetable for the timing of release and deadlines
for submission. It does not count toward your final mark for the
course but it is a course requirement that you complete it, and it
will be assessed to provide feedback for your benefit.
- Wikipedia is a good
source for many topics (it has pages on topics such as
- Click here
for Matt Chapman's Finite State Machine animator.
This is a Java Applet that allows you to draw FSMs in a window and
experiment with them.
- Another first-year course which has some material on
Finite State Machines is
here.
