    Close Help Print  Course module: 201300042  201300042Limits to Computing Course info Schedule   Course module 201300042
Credits (ECTS) 5
Course type Course
Language of instruction English
Contact person dr. B. Manthey
E-mail b.manthey@utwente.nl
Lecturer(s)  Lecturer dr. B. Manthey   Contactperson for the course dr. B. Manthey   Examiner dr. B. Manthey   Lecturer dr. A. Skopalik  Starting block
 1A Application procedureYou apply via OSIRIS Student
Registration using OSIRISYes Aims
 body { font-size: 9pt; font-family: Arial } table { font-size: 9pt; font-family: Arial } Knowing different models of computation, and being able to explain how they are equivalent Knowledge of standard undecidable problems, and methods for proving undecidability (e.g Rice's Theorem) A solid understanding of the basic notions in complexity theory (time and space complexity, hardness and completeness, different types of reductions) Being able to give simple reductions, to prove hardness of problems for various complexity classes Knowledge of the most important complexity classes (P, NP, coNP, PSPACE, L, NL), typical complete problems for them, and relations between them A feeling for the implications of complexity on practical problems Content
 body { font-size: 9pt; font-family: Arial } table { font-size: 9pt; font-family: Arial } A central topic in computer science and mathematics is the study of computational problems, such as •         computing a shortest path in a network; •         given a logical formula, deciding whether the variables can be set so that the formula is true; •         given a number of locations, finding a shortest round-trip that visits all locations; •         deciding whether two programs perform the same computational task. Such problems come in varying degrees of hardness; some seem to be more easily solvable than others. Some problems are even not solvable at all by algorithmic means. The central question of this course is: how can we formally quantify the hardness of computational problems and prove that certain problems are harder than others?   This leads to the following questions: •         How can we define computation? •         Are there any limits to what is computable at all? •         What are suitable measures for the performance of algorithms? •         What are the most important complexity classes, how are they related, and what are the typical hardest problems in each class? To answer these questions, we introduce mathematical models of computation such Turing Machines as a central model of computation. This is motivated by relating it to other (more familiar) computation models, and showing that essentially they all have the same computing power. First, we will study problems that cannot be computed at all on any computer.   Secondly, we will introduce performance measures based on running-time and memory usage. Throughout the course, the notion of reductions between computational problems is a key concept to compare the difficulty of computational problems.  Assumed previous knowledge a basic knowledge of algorithms, discrete mathematics (graph theory) and logic is required, such as included in any computer science or mathematics bachelor study. Participating study Master Applied Mathematics     Participating study Master Computer Science  Required materials
- Recommended materials
Handouts
 -  Instructional modes Lecture   Tutorial    Tests Homework, Written exam      Close Help Print   