Course Catalog 2009-2010 |
|||||
| Basic | Pori | International | Postgraduate | Open University | |
|
|
|
|||||||||||||||||
OHJ-2306 Introduction to Theoretical Computer Science, 6 cr |
Tapio Elomaa, Antti Valmari
| Lecture times and places | Target group recommended to | |
| Implementation 1 |
|
3.-n. vuosikurssi
DI-Opiskelijat Jatko-opiskelijat Tieto- ja sähkötekniikan tiedekunta Tietotekniikan koulutusohjelma |
Weekly exercises and exam
Completion parts must belong to the same implementation
The course offers an introduction to the fundamental possibilities of programming and computation - which problems can be solved in principle by computing and, additionally, which problems can be solved efficiently. What can be done if the problem needing solution cannot be solved efficiently using computers.
| Content | Core content | Complementary knowledge | Specialist knowledge |
| 1. | Universal models of computation | Turing machines | Variants of Turing machines |
| 2. | Computability theory | Decidability | Reducibility |
| 3. | Complexity theory | Intractability | Time and space complexity |
| 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 |
| Course | Mandatory/Advisable | Description |
| OHJ-2156 Analysis of Algorithms | Mandatory | A course on the analysis of algorithms. |
| MAT-20600 Diskreetti matematiikka | Mandatory | A course on discrete mathematics, or the old requirement 8100500 Ohjelmistotekniikan matemaattiset menetelmät. |
| Course | Corresponds course | Description |
|
|
|
| Description | Methods of instruction | Implementation | |
| Implementation 1 | Lectures Excercises |
Contact teaching: 50 % Distance learning: 0 % Self-directed learning: 50 % |