581330-2 Models for Programming and Computing, Spring 2005
What's New
General Information
The course is a compulsory Cum laude approbatur course for students majoring in computer science, and an alternative course for students studying computer science as a minor subject. The subject matter of the course are the basics of abstract modeling of computational problems.
Previous Knowledge
Satisfactory mathematical background. No specific area is required, but the course is mathematical in its nature. If you would like to refresh your memory about functions and relations, sets, enumerability or proofs by induction, you should attend the first lecture. The courses Discrete Mathematics I and Data Structures support the studies for this course.
Contents of the Course
-
Introduction
- Presentation of the Course
- Repetition of Data Structures and Basic Mathematica Concepts
- Computational Problems and Solvability
-
Regular Languages and Finite Automata
- Deterministic Finite Automata
- Minimization of Finite Automata
- Nondeterministic Finite Automata
- Determinization of Automata
- Regular Expressions and Languages
- Restrictions of Regular Languages: the Pumping Lemma
-
Context-free Languages and Pushdown Automata
- Context-free Grammars and Languages
- The Parsing Problem for Grammars
- Recursive Parsing
- The CYK Parsing Algorithm
- Pushdown Automata
- Restrictions of Context-free Languages
-
Introduction to Theory of Computation
- Unrestricted grammars
- Turing Machines
- Decidability
Lectures
18.01.-24.02. Tuesdays and Thursdays at 10-12 in A111 in Finnish
The lecture material (in Finnish) appears on the Finnish homepage.
A short revision of the most essential stuff (PS, PDF)
The lectures (and thus the exercises) correspond to the Hopcroft-Motwani-Ullman book. A detailed list of the material covered on the lectures will be maintained here.
- Week 1: HMU Chapter 1 (minus Section 1.1) and Halting Problem from p. 380.
- Week 2: HMU 1.1, 2.2, 4.4, 2.3
- Week 3: HMU 3.1, 3.4 (3.4.1--3.4.5), 2.5 (with emphasis on the technique of 2.5.5), 3.2, and at least part of 4.1.1 Note: HMU uses operator symbol "+" instead of "cup" as the union of regular expressions; the latter is used on this course, which doesn't bring any changes to the semantics of REs.
- Week 4: HMU 4.1, 5.1., Exercise 5.1.4. (the definition of right-linear grammar), 5.2., 5.4., LL(1) form grammars and their recursive parsing
- Week 5: HMU 7.1, 7.4.4, 6.1, Introduction of 6.3, 7.2 (not very thoroughly)
- Week 6: HMU 8.2 (briefly), 9.6.
Exercises
There are six sets of exercises, one set for each week during 24.1.- 4.3. English versions will appear here in due time. You can check the times of the exercise groups from the teaching schedule for Spring.
- Exercise 1: ps pdf
- Exercise 2: ps pdf
- Exercise 3: ps pdf
- Exercise 4: ps pdf
- Exercise 5: ps pdf
- Exercise 6: ps pdf
Passing the course
There are two requirements to pass the course: the course exam and the compulsory exercises (at least 1/3 of the exercises or participating in 2/3 of the exercise sessions):
- From the exam you get max. 54 points
- Exercises max. 6 points
The course exam is held on Friday 11.3. at 14-18 in A111 and B123 (Exactum).
You can also read the course material yourself and participate in a separate exam only. In that case, the final grade is determined by the points in the separate exam alone.
Literature
The course is based mainly on the first part of the lectures 'Laskennan teoria' (in Finnish) by Pekka Orponen.
Some books in English:
- John E. Hopcroft, Rajeev Motwani & Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001 (in the course book shelf of the library, textbook for the course Theory of Computation)
- Harry R. Lewis & Christos H. Papadimitriou: Elements of the Theory of Computation, Second Edition, Prentice-Hall, 1998 (in the course book shelf, ask the librarian)
- Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Company, 1997 (in the course book shelf, ask the librarian)
- Efim Kinber & Carl Smith: Theory of Computing. A Gentle Introduction. Prentice Hall, 2001 (in the course book shelf)