Credits: 5
Schedule: 08.01.2019 - 10.04.2019
Teaching Period (valid 01.08.2018-31.07.2020):
III - IV (Spring)
Learning Outcomes (valid 01.08.2018-31.07.2020):
Theoretical computer science comprises the science of computation, and the science of software. Science is knowledge that helps us make predictions. The stronger the science, the stronger the predictions. The science of computation tells us what is computation, what are the different types of computing machines, and what are their computing powers. Using this science, we can predict (indeed, prove!) that some computational problems are easy, some are hard, and some are impossible to solve! The science of software allows us to make predictions about the programs that we write: will my program always terminate? might it crash? will it always produce the right result? etc. In this course you will learn the basic models of computation (finite automata, regular expressions, context-free grammars, Turing machines). You will solve a set of computerized assignments where you will build such computing machines and answer fun questions about them. You will also learn the foundations behind the science of software, which are formal logic and theorem proving, using the Coq proof assistant.
Content (valid 01.08.2018-31.07.2020):
Finite automata and regular languages. Context-free grammars and pushdown automata. Turing machines and computability. Basics of computational complexity. Logic and theorem proving with Coq.
Assessment Methods and Criteria (valid 01.08.2018-31.07.2020):
Exam, computerized assignments, and home assignments
Workload (valid 01.08.2018-31.07.2020):
Lectures, teaching in small groups, independent work and exam
Study Material (valid 01.08.2018-31.07.2020):
Michael Sipser: Introduction to the Theory of Computation, lecture notes and slides, and other separately announced study material
Substitutes for Courses (valid 01.08.2018-31.07.2020):
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 (valid 01.08.2018-31.07.2020):
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 (valid 01.08.2018-31.07.2020):
0-5
- Teacher: Lipiäinen Valtteri
- Teacher: Orponen Pekka
- Teacher: Saarinen Ville