This page is designed to provide easy access to the course materials in convenient form. The definitive source is on Learn, but if that fails, this may still be here. Comments and suggestions for improvement are welcome.
In Week 11 we introduce a key idea which is optional in this course; it will be important for later courses. This is the idea of inductive definitions, which are pervasive in Informatics.
We then turn to revision.
We show that the regular languages, correspond to the languages
We introduce finite state machines (FSM), and implement them in Haskell.
A language is a subset of the set of strings on some alphabet of symbols. We define the operations of concatenation (RS), alternation (R|S), and iteration (R*), on languages.
The regular languages are the languauges generated using these operations, from the empty language amd the simple languages {s}, for s a symbol of the alphabet.
Each FSM accepts some language of strings. We show that these are the regular languages.
We introduce the language of Boolean algebra, and translate any Boolean expression to our language of forms (CNF).
The Tseytin procedure is an algorithm that takes a Boolean expresssion and produces an equisatisfiable CNF whose size is linear in the size of the expression.
Binary constraints are simple -- we can count the soutions to a set of binary constraints using the arrow rule.
We introduce the idea of quantifiers, and the notion of a formal language.
We also introduce Sudoku as a non-trivial example aof aproblem we can express in our simple language of forms.
We introduce the DPLL algorithm, and use if to solve Sudoku puzzles.
In Week 6 we introduced Karnaugh Maps. These give another way of producing CNF (for small problems, with only 4 predicates), and make it easy to optimise the CNF you obtain. This material is covered in Ch.12 of the Book. We'll also introduce a Haskell type for expressions in CNF, and use Haskell to test satisfiablility.
In Week 5 we will introduce more Boolean connectives, and the idea of conjunctive normal form (CNF), but no new methods. We will only introduce new examples of things you have already met. This will give you an opportunity to consolidate the logic topics we have introduced so far.
Week
4
Reading:
This
week's material is mainly covered in Chapter 10 of The Book.
This week's material is covered in Chapter 8 of The Book.
Test 1, to be taken on Wednesday in week 4, will focus on syllogisms and relevant material taught in weeks 1—3.
In this week's tutorial assignment you will use Haskell to
This week and next you will be studying Syllogisms. These are patterns of reasoning introduced by Aristotle in the third century BC. For a very long time, the study of logic was the study of Aristotle's syllogisms.
Unlike the Wikipedia article, we will use modern notation, to cover in a couple of weeks, ideas that occupied some of the worlds great thinkers for many centuries.
In week 4 we will find that Aristotle's affirmative propositions are just special cases of more general assertions that we study in modern logic.
This week's material is covered in Chapter 7 of The Book.
Tasks for each week (n) will include lectures (videos), readings (normally from The Book), quizzes (provided so you can assess your understanding), and a tutorial assignment for the following week's tutorial (week n+1). More details of these are given below.
These are essential components of this course.
CL tutorials will be held on Tuesdays.
| [09:00 - 10:30] | Lab/01, Lab/02, Lab/03 |
|---|---|
| [11:10 - 12:40] | Lab/04, Lab/05, Lab/06 |
| [13:10 - 14:40] | Lab/07, Lab/08, Lab/09 |
| [16:40 - 18:10] | Lab/10 |
You will work within a group of six students. We call these groups tables. Each tutor will be responsible for a couple of tables and will move between the tables. During the tutorial, you will be responsible for working together with others at your table, to compare your tutorial submissions and structure your interactions with your tutor. More details of these interactions will be provided in the tutorial sheets.
Each week (2-11) includes a tutorial assignment that you must attempt and submit by 16h00 on the Saturday before the tutorial. You should then be prepared to share and discuss your work during the tutorial. Tutorials are mandatory, and only effective if you do the assigned work before the tutorial. This work is also assessed; it contributes to your final grade for the course, and no credit will be given for late submissions.
You must submit your assigned work for the following week's tutorial before the deadline of 16h00 on Saturday. This deadline is chosen to allow you maximum flexibility, to cater for different timezones, and to allow time for our tutors to mark your submissions.
Before this deadline you are encouraged to discuss the subject with each other. However, you must work independently on your tutorial submissions. This is assessed work. So you will have to find or invent similar problems to discuss with each other.
We suggest you plan to submit before the deadline. Set yourself an earlier personal deadline sometime on Friday, so you can take a break over the weekend, and use the extra time only as a backstop in case of unanticipated delays. Also, if you make a mistake and discover it before the deadline you can resubmit to correct it. But always remember and respect the golden rule: you must not discuss your answers with other students until after the official deadline.
On Wednesday in weeks 4, 6, 7, 9, 11, there will be a single-topic test. In addition to a final one hour summative test taken on Thursday of week 12, after the teaching period.
The syllabus is roughly divided in five topics. Your knowledge of each topic will be assessed by a 30 minute online test, designed to assess your understanding of the topic, and your mastery of related skills, covered in the quizzes and tutorials. These topic tests will be open from 00h00 on Monday of the relevant week, to be completed before 20h00 on that day. You can choose your own 30 minute slot in which to complete the test.
The final online test will be taken on Thursday in week 12. This will be a one hour test covering all aspects of the course. Again the test will be available from 00h00, and you will be free to choose your 1 hour slot within a 20h window, as summarised in the following table.
| Topic | Date | Duration |
|---|---|---|
| Syllogisms | Week 4: Wednesday, 14 October | 30 minutes |
| Inference and reduction | Week 6: Wednesday, 28 October | 30 minutes |
| CNF and Karnaugh maps | Week 7: Wednesday, 4 November | 30 minutes |
| Satisfiability | Week 9: Wednesday, 18 November | 30 minutes |
| NFA, DFA, and regex | Week 11: Wednesday, 2 December | 30 minutes |
| Final Test | Week 12: Thursday, 10 December | 1 hour |
More detail of the scope of each test, and examples of the kinds of question you may expect, will be given in due course.
Credit is given for tutorial assignment submissions (2 x 10), the topic tests (12 * 5), and the final test (20). These marks are summed to give a final percentage mark for the computation and logic component of the course.
To pass the course you have to pass both components, CL and FP, independently. The avaerage of your percentage scores for the two strands then gives your final mark.
Marking will be in accordance with the School's Common Marking Scheme. For example, we mark each topic test on a scale of 0-12. A score of 9 requires an exceptional submission, corresponding to a score of more than 75% on the common marking scheme, which signifies: Very good or excellent in most respects, the work is what might be expected of a very competent student.. A score of 10 would be exceptional, Outstanding in some respects, the work is often beyond what is expected of a competent student at their level of study.
A live online Question and Answer session will be held weekly at 10h00 on Thursdays. You should therefor aim to study your weekly tutorial assignment by Wednesday, or earlier, so you can post any questions you may have on Piazza and have them answered in the Q&A.
In addition to these scheduled events you should use the quizzes to check your understanding, and Piazza to ask questions asynchronously, and contribute to answering them.
Online quizzes are provided alongside the videos to let you check your understanding. You should find ways of discussing problems with each other, use the quizzes, which you can take and retake as often as you choose, to check your understanding, and revise and ask questions as necessary. The quizzes are purely formative. That means that they are not assessed and make no contribution to your final grade. They provide you with the opportunity to identify gaps in your understanding, or things we have simply failed to communicate effectively. You can then revise the material, or ask questions to address the issue.
Piazza is a great resource but it works best if you take some care before you post. You can find many internet posts on Piazza Etiquette, there, I've just linked to one. Here are a few to bear in mind: Search before posting. Link to any external resources you refer to. Avoid open-ended or vague questions. Don't discuss homework problems before the hand-in deadline. Use the @nnn syntax to link to other relevant posts in Piazza.
Informatics is the study of systems that store, process, and communicate information. The logic and computation strand of INF1A introduces ideas you will use, in many future courses, to describe and reason about such systems.
We begin by introducing some mathematical tools that help us to talk clearly and unambiguously. 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 in 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.
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.
In the programming strand of INF1A you will learn to program in Haskell. Haskell is designed to make it easy to represent sets, properties, relations and, above all, functions. It will allow us to implement many of the constructions we discuss.
We often describe things in terms of their properties: big red balloon; small green triangle. We also use properties to make statements about the world: all men are mortal; some swans are black.
We can reason about such staments: All men are mortal; Socrates is a man; therefore, Socrates is mortal. We begin our study of logic by developing the theory of such syllogistic reasoning.
Many different logical systems are used for specifying and reasoning about informatic systems. We focus on the simplest example, propositional logic, and explore some fundamental ideas that will provides a basis for your later study of more expressive logics.
Many statements about finite systems can be expressed in propositional logic. We introduce computational procedures for reasoning in propositional logic, and show that these can be used to solve many combinatorial problems.
One 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 will focus on one deceptively simple example.
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. This fundamental computational model is routinely used in the design and implementation of software and hardware systems, across the whole of Informatics.
In future courses you will study more-general models of computation.
Feedback and assessment: Each week we will highlight the skills you should have learnt, and provide online quizzes you can use to check that you have mastered them. You make take and retake the quizzes as often as you choose.
For example, by the end of week 2 you should have mastered the following skills:
This course supplies foundational knowledge for Informatics courses taken in subsequent years of study. It provides students with experience of theory in a practical context, develops their abilities to reason and communicate, and also introduces a variety of 'professional issues' including software IP, verification, correctness, best practice and liability.
| Lecturer: | Michael Fourman | mfourman @ed.ac.uk |
| Teaching Fellow: | Claudia Chirita | cchirita_@ed.ac.uk |
| Teaching Assistant: | Gavin Peng | hpeng2_@exseed.ed.ac.uk |
| Course Secretary: | Laura Ambrose | lambrose_@exseed.ed.ac.uk |