Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    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 szak

    BSc 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