INF210 - Datamaskinteori (Models of Computation)

Course Description: The course covers models of computation that form the basis of modern computers. The course overviews methods for generating and recognizing formal languages (grammars, automata, Turing machines) and explains their relation to computation. With an emphasis on applications, logical circuits and a simple CPU are designed on a mathematical basis.

Objectives: The student should acquire a good understanding of formal models of computation and their relevance to computer science.

Lærebok (Textbook): John Martin, Introduction to Languages and the Theory of Computation, McGraw Hill, Third Edition. In addition some parts from John Savage, Models of Computation, Addison-Wesley, will be used. Booklets with selected parts from Savage's book will be available at Studia for approximately 80 NOK.

The course covers Chapters 1-8 of Martin's book (plus-minus some minor parts to be specified later) and selected parts from Savage's book.

Foreleser (Lecturer): Fedor V. Fomin

Gruppeleder (Assistent): Olav Hjortås

Forelesninger på engelsk (lectures in English):
Mandag (Monday) 10.15-12.00, Onsdag (Wednesday) 14.15-16.00
Sted (place): Grupperom 2143, HIB.

Gruppeøvinger (plenary workshops):
Tirsdag (Tuesday) 14:15-16.00
Sted (place): Grupperom 2143, HIB

Første forelesning (starting lecture): 18/8 Siste forelesning (last lecture): by the end of November

Office Hours: 12:30-13:00 Monday, or by appointment (fomin_AT_ii.uib.no)

Exam:: Written or oral, depending on number of students. There will be two compulsory exercisers (obligatoriske oppgaver). They will be counted equally (15% each), and will count 30% of the final grade.

Tentative Schedule (changes are possible):

Off stands for no meeting at all, Ch. for lecturing material and Ex. for workshop exercises to be found at the end of each chapter. For example, Ch.1.1-5;2.1,3 would denote a slot with lectures on the first 5 sections of chapter 1 and sections 1 and 3 of chapter 2.

W	Monday 10.15-12.00	Tuesday 14:15-16.00	Wednesday 14.15-16.00
34	Ch. 1	Off	Ch. 2,3
35	Ch. 3	Ex. 1.38--1.41, 1.44, 1.47, 2.42, 2.44, 3.1--3.4, 3.9, 3.10, 3.19	Ch. 3
36	Ch. 3, Ch. 4.1	3.15, 3.33, 4.1-4.4	Ch. 4
37	Ch. 4	4.10, 4.13-4.15, 4.17, 4.18, 4.24, 4.36	Ch. 4,5
38	Ch. 5	4.27, 4.28, 4.29, 4.35, 4.38	Ch. 5
39	Compulsory Exercise 1	Off	Off
40	Ch. 6	Discussions of compulsory exercises	Ch. 6
41	Ch. 6	6.1.a-c, h, 6.4.a,b, 6.6, 6.10	Ch. 6
42	Ch. 7	6.18.a,b, 6.19.a,b, 6.26.a,c,d, 6.34, 6.39.a,b,d	Ch. 7
43	Ch. 7	6.36, 6.40, 7.1,7.2, 7.5 a,b	Ch. 7
44	Savage book	7.9, 7.13a, 7.17a,b, 7.22	Savage book
45	Compulsory Exercise 2	Off	Off
46	Ch. 8	Discussions of compulsory exercises	Off
47	Q & A	Off	Off
48	Q & A	Off	Off

Oral exam: November, 26 and 27, 2143 Questions

November, 26, 2143

November, 27, 2143

Slides

Lecture 1

Lecture 2

Lecture 3

Lecture 4

Lecture 5

Lecture 6

Lecture 7

Lecture 8

Lecture 9

Lecture 10

Lecture 11

Lecture 12

Lecture 13

Lecture 14

Lecture 15

Lecture 16

Lecture 17

Lecture 18

Lecture 21

Siden vedlikeholdes av Fedor V. Fomin