INF210 - Datamaskinteori
## Spring 2016

## Contents on this web page

The course covers models of computation that form the basis of modern computers, with an emphasis on applications. Logical circuits for e.g. addition and a simple CPU are designed on a mathematical basis. An overview is given of methods for generating and recognising formal languages (grammars, automata, Turing machines) and their relation to computation is explained.
### Reading Material

The curriculum consists of
all lectures, notes, handouts, exercises, and related course material and the book:

### Additional Reading Material

For those especially interested in reading up on the background material,
the following (classical) book is recommended.

- Harry R. Lewis and Christos H. Papadimitriou: Elements of the theory of Computation. Prentice-Hall, 1981. ISBN 0-13-273426-5. (This is the first edition, later editions are very different).

Lecturer and course responsible: Magne Haveraaen

Teaching assistant: Eivind Jahren
The participants are adviced to organise study groups for discussing
the topics of the course and assist each other in solving the exercises.

- Monday 1415 - 1600 in seminar room 4138 Høyteknologisenteret, exercise class, starting week 15
- Tuesdays 1415 - 1600 in seminar room 4138 Høyteknologisenteret
- Wednesdays 1415 - 1600 in seminar room 4138 Høyteknologisenteret
- Thursdays 1615 - 1800 in seminar room 4138 Høyteknologisenteret, exercise class, last time week 14

Teaching starts Tuesday 19 January 2016 (week 3), with exercise classes starting Thusday 28 January (week 4).
Teaching will be in the form of lectures, exercises and
time off for self studies.
The following teaching plan sums up the semester.
- T: Introduction

W: Languages & Graphs - Ch 1.

Th: No exercise class
- TuW: Boolean functions, Straight-line programs, Circuits - Ch 2-2.3

Th: Exercise set 1
- TuW: Ch 2.4-2.7

Th: Exercise set 2
- TuW: Ch 2.9, 3-3.1, 3.3

Th: Exercise set 3
- TuW: Ch 3.3-3.6

Th: Exercise set 4
- TuW: Ch 3.7-3.8, 4-4.3, 4.6

Th: Exercise set 5 - compulsory 1
- TuW: No lectures

Th: Exercise set 5 - compulsory 1
- TuW: Ch 4.4-4.5, 4.8-4.9

Th: Exercise set 5 - compulsory 1
- TuWTh: Ch 4.10-4.13

Th: Exercise set 5 - compulsory 1 feedback
- Easter break
- TuWTh: Exercise set 6
- TuW: Ch 5-5.6

Th: Exercise set 6
- M: Exercise set 7 - compulsory 2

TuW: No lectures
- M: Exercise set 8, set 7 - compulsory 2

TuW: Ch 5.6-5.8
- M: Exercise set 8, set 7 - compulsory 2 feedback, set 9 - compulsory 3

TuW: No lectures
- M: Exercise set 8

M: Exercise set 9 - compulsory 3

TuW: No lectures
- M: Exercise set 9 - compulsory 3 feedback

Tu: No lecture

W: Q & A
- W: Exam

The exam is 18 May 2016.
The exercises will be provided as the course evolves,
check INF210 Filer.
The course is evaluated by an oral exam.

Last updated 2016-05-13 by
Magne Haveraaen