Lecturer: | Michael Fourman | mfourman @ed.ac.uk |

The goal of this course is to introduce you to computational thinking — using computational models to describe and reason about systems, including systems that change through time.

We begin by introducing some mathematical tools that help us to talk clearly and unambiguously. We then use these tools to study finite-state systems and propositional logic. These provide examples of the logical ideas of syntax and semantics and the computational ideas of structure and behaviour.

We will use sets, properties, relations, and functions to think and talk about computational systems.

Talking is all well-and-good, but talking in English, or any other natural language, is notoriously ambiguous, and we are often imprecise. We introduce a logical notation to make precise and unambiguous statements about computational systems.

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.

In future courses you will study more-general models of computation.

Various logics are used for specifying and reasoning about informatic systems. Statements about finite systems can be expressed in propositional logic. We introduce two procedures for reasoning in propositional logic, and show that these can be used to solve many combinatorial problems. This provides a basis for later study of more general logics used to specify and reason about Informatic systems.

- Sets, properties, relations and functions, used to model situations.
- Making clear and unambigous statements about situations, using logic.
- Describing the computational behaviour of physical systems, using states.
- Finite-state systems: a basic model of computation; deterministic and non-deterministic automata; regular expressions; acceptors; structured design of finite state machines.
- Propositional logic: truth tables, satisfiability; natural deduction, resolution; soundness, completeness.

Normally Thursdays 11:10-12:00 and Fridays 14:10-15:00.

Sometimes we will swop slots with INF1-FP. These swops are shewn in
**bold**.

Week | Monday 14:10-15:00 George Square LT | Tuesday 11:10-12:00 LTA DHT | Thursday 11.10-12:00 LTA DHT | Friday 14:10-15:00 LTA DHT |
---|---|---|---|---|

1 | INF1-FP | INF1-FP | INF1-CL | INF1-CL |

2 | INF1-CL |
INF1-CL |
INF1-CL | INF1-CL |

3 | INF1-FP | INF1-FP | INF1-CL | INF1-FP |

4 | INF1-FP | INF1-FP | INF1-FP |
INF1-FP |

5 | INF1-FP | INF1-FP | INF1-CL | INF1-CL |

6 | INF1-FP | INF1-FP | INF1-CL | INF1-CL |

7 | INF1-FP | INF1-FP | INF1-CL | INF1-CL |

8 | INF1-FP | INF1-FP | INF1-CL | INF1-CL |

9 | INF1-FP | INF1-FP | INF1-CL | INF1-CL |

10 | INF1-CL |
INF1-CL |
INF1-CL | INF1-CL |

11 | INF1-FP | INF1-FP | INF1-CL | INF1-CL |

**Tutorials:** These start in week 2 and
take place each week until the end of semester, including week 11.
If you are ill or otherwise unable to attend one week then if possible
you attend another tutorial in the same week.

*Link:* Tutorial group times, places and membership.

If you wish to move to a different tutorial group, please * ask the ITO*
through their online
contact form and explain your constraints.
Or visit them in Forrest Hill.

Students are expected to prepare for each tutorial, which includes completing the tutorial exercises and the reading.

*You must attempt the work before the tutorial and bring with you
a copy of the work you have done. Tutorials are mandatory, and the
only way to learn is to do the work before the tutorial, not at the tutorial.
Students who have not done the work in advance will be sent away.*

- (Week 2) Forty Questions

Week 1: MML Sections 1.1-1.7.

Week 1: MML Chapter 2.

Informatics looks at the world in terms of information.

Nature is, perhaps, infinitely complicated, but we often use abstract models of natural systems based on a finite amount of information. The first part of this course deals with such models. We model states of such systems using sets, functions, and relations.

For example, a marine weather report describes the state of the weather by reporting a finite number of attributes. Visibility is Good, Moderate, Poor, or Very Poor; Sea State has eight values, ranging from Smooth to Phenomenal.

A mariner may decide never to go out is the visibility is too poor or the wind is too strong, or the sea is too rough. Propositional logic can be used to express such conditions.

In the second part of the course we model change. Many systems in nature change continuously. Our second abstraction is to consider a discrete series of time steps, and to focus on how the state of our system changes from one step to another, without worrying about the details of what happens in between. For example, in describing a game of chess we focus on the state of the board before and after each move, but pay no attention to the way the players move their pieces.

A common theme is the analysis of complex systems using compositional descriptions. Complex truth tables are built using a few boolean operations. Complex machines are composed using primitives for sequential composition, alternation, and repetition.

- A brief introduction of computation as a process, and computational models as 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, inference and truth. The relationship between a proof and the validity of an implication in terms of truth tables. Searching for satisfaction: algorithms for finding models for systems of propositional constraints.
- 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.
- Using Logic to describe change. The Stanford Research Institute Problem Solver (STRIPS) and elementary planning.
- Tools: examples of logic/FSM based tools in the design, analysis and construction of complex systems.

Much of the material we will cover will only be presented in lectures. Copies of the slides, annotated with brief notes, will be available. The slides may be modified and expanded to clarify questions raised during the lecture, so they will normally be re-published a few days after each lecture.

Chapters 1-3 of Mathematical Methods in Linguistics, by Robert Wall, Alice Ter Meulen, and Barbara Hall Partee (which you can download freely) provide a good reference for the basic mathematical tools we will use.

The brief notes I provide should be supplemented with notes taken by you during the lecture. If you are unable to attend a lecture, you should try to go through the slides with someone who did. Don't be shy about asking someone to do this — explaining things to you will probably help them at least as much as it helps you.

- inf1.hgs.club
- 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. - 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.

Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk Please contact our webadmin with any comments or corrections. Logging and Cookies Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh |