| 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.
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.
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 |
InfBase is in room 7.03 of Appleton tower, and is staffed from 11am-3pm on Monday through Friday during the normal semester (Weeks 3-11) and during Revision weeks. See the detailed schedule for when tutors with specific expertise will be present.
The course TA, Dave Cochran will be available in InfBase 1400-1500 on Wednesdays.
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 Appleton Tower (level 6).
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.
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.
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.
Mathematical Methods in Linguistics, by Robert Wall, Alice Ter Meulen, and Barbara Hall Partee, ISBN-10: 9027722455 ISBN-13: 978-9027722454 (Part 1 of which you can download freely) provide a good reference for the basic mathematical tools we will use. It also covers a lot of material that goes beyond this course, much of which will be useful to you in future.
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.
The first 5 chapters of Genesereth, Computational Logic, 2012, provide a good summary of much of the basic technical material on propositional logic covered in this course.
Another reference is Foundations of Computer Science by Aho and Ullman. This book has been taken out of print by W. H. Freeman. You may be lucky and find a used copy, e.g. on Amazon, but it is freely available for download on the web :-)
|
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 |
