Informatics 1A (U01834)

? Credit Points : 20 ? SCQF Level : 8 ? Acronym : INF-1-INF1A

Informatics 1A consists of two strands, (i) Computation and Logic, and (ii) Functional Programming. (i) Computation and Logic: The goal of this strand 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. (ii) Functional Programming: An introduction to the concepts of programming, using a functional programming language. Students learng to solve small-scale problems succinctly and at an abstract level without being bogged down in details. The course will use examples and exercises that reinforce some of the content of Computation and Logic. Exercises will be drawn from domains across the School of Infomatics.

Entry Requirements

? Pre-requisites : SCE H-grade Mathematics or equivalent is desirable.

Subject Areas

Home subject area

Informatics, (School of Informatics, Schedule O)

Delivery Information

? Normal year taken : 1st year

? Delivery Period : Semester 1 (Blocks 1-2)

? Contact Teaching Time : 6 hour(s) per week for 11 weeks

First Class Information

Date	Start	End	Room	Area	Additional Information
19/09/2006	11:10	12:00	Second Floor Lecture Theatre, Adam House	Central

All of the following classes

Type	Day	Start	End	Area
Lecture	Monday	14:00	14:50	Central
Lecture	Tuesday	11:10	12:00	Central
Lecture	Thursday	11:10	12:00	Central

? Additional Class Information : Labs (2hrs/week) and Tutorials (1hr/week) as arranged.

Summary of Intended Learning Outcomes

(i) Computation and Logic
After completing the course successfully, students should be able to:
- Design a small finite-state system to describe, control or realise some behaviour.
- Evaluate the quality of such designs using standard engineering approaches.
- Apply the algebra of finite automata to design systems and to solve simple problems on creating acceptors for particular languages.
- Describe simple problems using propositional logic.
- For a given formula in propositional logic, draw a truth table for that formula and hence deduce whether that formula is true or not.
- Apply a system of proof rules to prove simple propositional theorems.
- Describe the range of systems to which finite-state systems and propositional logic are applicable and be able to use the meta theory to demonstrate the limitations of these approaches in concrete situations.

(ii) Functional Programming
The goal of this course is to develop basic competence in programming in functional languages. After completing the course successfully, students should be able to use a functional language to:
- Solve simple programming tasks (for example, convert a number into a string for the corresponding roman numeral).
- Define appropriate data types (for example, to represent parse trees for arithmetic expressions).
- Perform case analysis, use recursion (for example, evaluate a parse tree for an arithmetic expression to yield a value).
- Solve simple combinatorial search and deductive inference problems (for example, Missionaries and Cannibals, Cryptarithmetic, Reasoning about Family Trees).
- Perform simple i/o; read and write a file.
Students should also be able to:
- Choose appropriate decompositions of problems to create a program to solve that problem.
- Compose a functional program from suitable function definitions, including their types.
- Document programs effectively.
- Apply basic techniques to test and debug programs, including unit tests.