|
|
|||||||||||||||||
Course Catalog 2010-2011
OHJ-2306 Introduction to Theoretical Computer Science, 6 cr |
Person responsible
Tapio Elomaa, Antti Valmari
Lessons
| Study type | P1 | P2 | P3 | P4 | Summer | Implementations | Lecture times and places |
|
|
|
|
|
|
|
|
|
Requirements
Weekly exercises and exam
Completion parts must belong to the same implementation
Learning outcomes
After completing the course the student will have a clear understanding that different computing devices have different computation power and that all formal models of computing have their limitations. The student will learn that different formulations of computation lead to same computing power. In particular, the student can give automaton and grammar implementations for formal languages belonging to classes of regular, context-free, and Turing-recognizable languages. The student is also able to prove basic results concerning computability and decidability. The student can also explain the dependency of time and space complexity of problems on the model of computation.
Content
| Content | Core content | Complementary knowledge | Specialist knowledge |
| 1. | Automata and languages, Regular languages | Nonregular languages, Context-free languages, Push-down automata | Chomsky normal form |
| 2. | Universal models of computation, Turing machines | Variants of Turing machines, Unrestricted grammars | Encoding Turing machines |
| 3. | Computability theory, Decidability | Reducibility | Completeness |
| 4. | Complexity theory, Intractability | Time and space complexity, Classes P and NP | Sunlinear space complexity |
Evaluation criteria for the course
The course grade will be based on the course exam. Active participation to weekly exercises yields extra points. If the student demonstrates thorough understanding of the core content, s/he may pass the course with grade 3. In order to achieve grade 4, the student must also demonstrate competency in complementary knowledge. The student may achieve grade 5, if s/he also demonstrates good command of specialist knowledge. If there are minor shortcomings regarding the core content, the student may receive the grade 1 or 2, depending on the number of flaws. If there are significant shortcomings regarding core content, the student will not pass the course.
Assessment scale:
Numerical evaluation scale (1-5) will be used on the course
Partial passing:
Study material
| Type | Name | Author | ISBN | URL | Edition, availability, ... | Examination material | Language |
| Book | Introduction to the Theory of Computation | Michael Sipser | 0-619-21764-2 | Second, International Edition | English |
Prerequisites
| Course | Mandatory/Advisable | Description |
| OHJ-2156 Analysis of Algorithms | Mandatory |
Prerequisite relations (Requires logging in to POP)
Correspondence of content
| Course | Corresponds course | Description |
|
|
|
Additional information
Suitable for postgraduate studies
More precise information per implementation
| Implementation | Description | Methods of instruction | Implementation |
| Autumn 2010 | Lectures Excercises |
Contact teaching: 50 % Distance learning: 0 % Self-directed learning: 50 % |