Theory of Computing

A tantárgy neve magyarul / Name of the subject in Hungarian: Számításelmélet

Last updated: 2010. november 11.

 Budapest University of Technology and Economics Faculty of Electrical Engineering and Informatics Mérnök informatikus szakBSc képzés
 Course ID Semester Assessment Credit Tantárgyfélév VISZA081 3/1/0/v 4
3. Course coordinator and department Dr. Katona Gyula,
Web page of the course www.cs.bme.hu/....
4. Instructors
 Name Position Department Gyula Y. KATONA Assoc. professor Department of Computer Science and Information Theory Katalin FRIEDL Assoc. professor Department of Computer Science and Information Theory Gábor WIENER Assoc. professor Department of Computer Science and Information Theory Ildikó SCHLOTTER Assistant lecturer Department of Computer Science and Information Theory Judit CSIMA Assoc. professor Department of Computer Science and Information Theory Tamás FLEINER Assoc. professor Department of Computer Science and Information Theory
7. Objectives, learning outcomes and obtained knowledge

In the first part of this course we introduce different theoretical models for computing. There are ones that are easy to describe but have limited power, and there are more complicated ones with more power. The first one is the finite automaton. On one hand it is 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, it can be used as a programming technique, too. It helps in code optimization and verification. Unfortunately, not every problem can be solved by them, we will show their limits.

The next model is the pushdown automaton. It has more power, but still is not too hard to build one. 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, one can solve most of the real life problems with it, especially if there is no time limit. We will define many variants as well and see how these variations change its power.

In the second half of this course the first important question that we answer: Is there an algorithm for any problem? If there is an algorithm, can we implement it by a given computational model? It turns out that there are some interesting problems that seem to be much more difficult than others even if the computers would be extremely fast.

Another question is that what happens if we have limited resources. Time and/or space is limited for the computation, which is the case in real life.

Scientists over centuries tried to solve some difficult algorithmic problems, but failed to succeed in some cases. Is it the case that they are not clever enough? Or there is no algorithm at all? Is there something in between these two possibilities?

8. Synopsis

First half-semester

1. Finite automata, non-deterministic finite automata

2. Regular and non-regular languages, pumping lemma.

3. Pushdown automata, context-free languages,

4. Turing Machines and variants, universal Turing machines.

5. The existence of universal Turing machines.

6. Recursive functions. Recursive, recursively enumerable languages.

Second half-semester

1. Algorithmic decidability,

2. Halting problem and other undecidable problems.

3. Storage and time, general theorems on space and time complexity

4. Non-deterministic Turing-machines.  NP and co-NP.

5. Cook's theorem: SAT is NP-complete.

6. Other NP-complete problems.

9. Method of instruction Lectures and recitations

10. Assessment A homework set of 4 problems will be given out on weeks 2 – 5 and on weeks 8-11.

Grading will be based on the following criteria:

- Homeworks  60 points

- Final exam     40 points

12. Consultations You can reach the instructor at the following e-mail address for consultation:

Gyula Y, KATONA: kiskat@cs.bme.hu

13. References, textbooks and resources Michael Sipser: Introduction to the Theory of Computation, Thomson Course Technology, 2006

14. Required learning hours and assignment
 Number of contact hours 56 Preparation to the classes 18 Preparation to the tests Homework 26 Assigned reading Preparation to the exam 20 Total 120
15. Syllabus prepared by
 Name Position Department Gyula Y, KATONA Assoc. professor Department of Computer Science and Information Theory