Exam 05-04-2017 - Halls are shared by last names first letter(s):
Hall Aalto: A ‒ L
Hall B: M ‒ Y
Compulsory course of the Computer Science and Engineering major.
Credits: 5 cr
Teaching Period: III - IV (Spring). The Course starts on Tuesday 03.01.2017, 10:15 - 12:00, T1 / C202 Tietotekniikka
- Lectures: Tuesdays 10:15 - 12:00, starting 03.01.2017 in T1 T1 / C202 Tietotekniikka
- Mondays 14:15 - 16:00 TU3 / 1194 TUAS Maarintie 8, starting 9.01.2017
- Tuesdays 16:15 - 18:00 T6 / A136 Tietotekniikka, starting 10.01.2017
- Wednesdays 10:15 - 12:00 T6 / A136 Tietotekniikka, starting 11.01.2017
- Thursdays 12:15 - 14:00 T6 / A136 Tietotekniikka, starting 12.01.2017
- Fridays 10:15 - 12:00 T5 / A133 Tietotekniikka, starting 13.01.2017
- Lectures: 24h (2)
- Exercises in small groups: 24h (2)
- Independent work: 82h
- Exam: 3h
- Total: 133h
Learning Outcomes: After the course you know the most important models of computation and you can examine them with mathematical precision. You can model computation using finite automata, and characterize simple languages with regular expressions and context-free grammars. You understand how the Turing machine models everything that can be computed using a real computer, and that there are well-defined problems that cannot be solved with any algorithm. You know the relationship between the expressiveness of the models of computation studied during the course. You have been exposed to some basic concepts of computational complexity theory such as reductions between problems.
Content: Finite automata and regular languages. Context-free grammars and pushdown automata. Turing machines and computability. Basics of computational complexity.
Assessment Methods and Criteria: Exam and home assignments
Study Material: Michael Sipser, Introduction to the Theory of Computation; lecture notes and slides; and other separately announced study material
Substitutes for Courses: ICS-C2000 Theoretical Computer Science, T-79.1001 Introduction to Theoretical Computer Science T (4 cr), T-79.1002 Introduction to Theoretical Computer Science Y (2 cr)
Prerequisites: CS-A1110 / CSE-A1110 Programming 1 and CS-A1120 / ICS-A1120 Programming 2 or CS-A1111 / CSE-A1111 Basic Course in Programming Y1 and CS-A1121 / CSE-A1121 Basic Course in Programming Y2, MS-A0401/A0402/A0409 Foundations of discrete mathematics.
Grading Scale: 0-5
Lecturer: Ph.D. Viorel Preoteasa