UiB : MatNat : Informatikk : Undervisning


INF210 - Datamaskinteori (Models of Computation)

Studiehåndbok (description in study guide): INF210
Studentportalen

Link to Olav Hjortås' English-Norwegian dictionary of terms used in the course.

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æreboken 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

10.00 Ove Vik-Mo
10.30 Tore Nedretvedt
11.00 Jonas Helgi Palsson
11.30 Oyvind Jakobsson
13.00 Olav Hjortas
13.30 Thomas Edvindsen
14.00 Tor Kristian Larsen

November, 27, 2143

10.00 Kjetil Watnedal
10.30 Helge Holm
11.00 Arianna Kyriacon
11.30 Haakon Vik Nilsen
13.00 Aina Johansen
13.30 Thomas Watnedal

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