Course Title:
Theory of Computing
Instructor:
Gyula Y. Katona
Duration:
Weeks 1-14, 2x2 hours/week, 4 credits
Short Description of the Course:
In the first part of this coursewe introduce different theoretical models for computing. There are those that are easy to describe but have limited power, and there are more complicated models with more power. We begin with finite automatons. On the one hand they can be used directly, since it is easy to build them to perform simple tasks. Many electronic devices contain basically one chip, which is really a finite automaton. On the other hand, this model can be used as a programming technique, as well, to help with code optimization and verification. Unfortunately, not every problem can be solved in this way, and we will also examine their limits.
The next model is the pushdown automaton. It has more power but is still relatively easy to build. It is used widely in compilers, for example.
The last important model is the Turing machine. It is considered to be the model of an everyday computer. It is very powerful, and can be used to solve most real life problems, especially when there is no time limit. We will define many variants, and examine how such variations change its scope and ability.
In the second part of this course we answer an important question: Can every problem be expressed in algorithms? And if there is an algorithm for a particular problem, can we implement it with a given computational model? It turns out that some interesting problems seem to be much more difficult than others even when implemented on extremely fast computers.
Another question concerns what happens if we have limited resources, if time and/or space for computation is limited, which is often the case in real life.
Scientists have tried to solve some of the most difficult algorithmic problems over centuries, but have failed in some cases. Is it the case that they are not clever enough? Is there no algorithm at all? Or is there something in between these two possibilities?
Aim of the Course:
The main aim of the course is to establish a mathematical background for computational problems. With this background we are able to derive results that have important consequences in many areas of mathematics, engineering, programming and other practical areas of life. The theoretical foundation also gives new tools that can be useful in other disciplines.
Prerequisites:
Some experience with basic proof methods (e.g. proof by construction, contradiction, and induction) is recommended.
Very basic knowledge of combinatorics, number theory, sets, logic (e.g. definitions and basic properties of graphs, binomial coefficients, primes, union, set complement, AND, OR) is helpful, but not absolutely necessary.
Although course content directly relates to programming no prior knowledge of programming is required.
Detailed Program and Class Schedule:
Method of instruction:
Lectures, recitations
Textbook:
Michael Sipser: Introduction to the Theory of Computation, Thomson Course Technology, 2006
Instructor’s Bio:
Gyula Y. Katona (born 1965) is an associate professor at the Department of Computer Science and Information Theory, Faculty of Electrical Engineering and Informatics, Budapest University of Technology and Economics (BME). He graduated from Eötvös Loránd University as a mathematician in 1991. Receiving his Ph.D. in mathematics in 1997 from the Hungarian Academy of Sciences, Katona spent two years at Ibaraki University, Japan. He also had a visiting appointment for a year at Arizona State University. He is the author of more than 25 papers and co-author of a university textbook on discrete mathematics. He has been teaching Theory of Computing at the Budapest Semesters of Mathematics for several years. His Erdős number is 2.
Download in PDF
