Inf1: Computation and Logic 2017

if-then-else

Contents

  1. People
  2. Learning Materials
  3. Tutorials and Assignments
  4. Course description
  5. General Information & Other Resources

People

Lecturer: Michael Fourmanmfourman @ed.ac.uk

Aims and Objectives

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.

Computation

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.

Logic

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.

Syllabus

This course provides students with experience of theory in a practical context. It also introduces a variety of 'professional issues' including software IP, verification, correctness, best practice and liability.

Learning Materials

There is no textbook corresponding to this course. 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.

Lectures

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

Lecture slides and videos

Exceptions

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

Week 2: Inf1-CL Tue 26 Sep (11:10–12:00, DHT LTA)
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 and Assignments

Tutorials, assignments, and readings are essential components of this course.

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.

Tutorials

2017

Reading

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.

References

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.

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.

General Information & Other Resources

  1. inf1.hgs.club
  2. Past papers for all Informatics courses and modules, organised by year. Search through each year to find available Inf1 Computation and Logic past papers.
  3. Wikipedia is a good source for many topics, such as,
  4. 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.
  5. 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


Home : Teaching : Courses : Inf1