- People
- Course description
- Lecture slides and notes
- Tutorial Exercises
- Assignments
- General Information & Other Resources
| Lecturer: | Dave
Robertson | dr@inf.ed.ac.uk |
| Teaching Assistants: | Xi Bai | xi.bai@ed.ac.uk |
2a. 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.
2b. 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.
2c. 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.
3a. Logic
3b. 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.
Revision Lecture
You can find your tutorial group at
Informatics Theon Portal, where
times, locations, tutor and student lists are provided. Tutorial exercise solutions will be released after the appropriate tutorials have been held.
There is a single assignment for Computation and Logic. 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.
-
The following assignment is due for submission to the
Informatics Teaching Organisation (level 4 of Appleton Tower) by
noon 22nd of November. [Assignment]
-
Guide to Standard Answers (and Marking Scheme) [Answers]new!
-
Past papers for all Informatics courses and modules, organised by year. Search through each year to find available Inf1 Computation and Logic past papers.
-
Wikipedia is a good
source for many 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.
- There is no need for a text book for this course, but those who are interested in more reading can see the following books:
Computation: "An introduction to formal languages and automata" by Peter Linz.
Logic: "The essence of Logic", John Kelly, 1997.
if you still want to read more on logic: "Logic for computer science", Steve Reeves, 1990.
