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

    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    Introduction to the Theory of Computing 2

    A tantárgy neve magyarul / Name of the subject in Hungarian: Bevezetés a számításelméletbe 2

    Last updated: 2018. december 18.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZAA04   2/2/0/v 5  
    3. Course coordinator and department Dr. Szeszlér Dávid,
    Web page of the course
    4. Instructors

    Dr. Rita Csákány, associate professor, Department of Computer Science and Information Theory

    Dr. Tamás Fleiner, associate professor, Department of Computer Science and Information Theory

    Dr. Péter Pál Pach, associate professor, Department of Computer Science and Information Theory

    Dr. András Recski, professor, Department of Computer Science and Information Theory

    Dr. Gábor Simonyi, professor, Department of Computer Science and Information Theory

    Dr. Dávid Szeszlér, associate professor, Department of Computer Science and Information Theory

    Dr. Gábor Wiener, associate professor, Department of Computer Science and Information Theory
    6. Pre-requisites
    (TárgyEredmény( "BMEVISZAA00" , "aláírás" , _ ) = -1
    TárgyEredmény( "BMEVISZAA03" , "aláírás" , _ ) = -1
    TárgyEredmény( "BMEVISZA103" , "aláírás" , _ ) = -1 )

    ÉS NEM (TargyEredmeny("BMEVISZA110", "jegy", _) >= 2
    TárgyEredmény("BMEVISZA110", "felvétel", AktualisFelev()) > 0
    TargyEredmeny("BMEVISZAA01", "jegy", _) >= 2
    TárgyEredmény("BMEVISZAA01", "felvétel", AktualisFelev()) > 0
    TárgyEredmény( "BMEVISZAA01" , "aláírás" , _ ) = -1)

    ÉS (Training.Code=("5N-A8") VAGY Training.Code=("5NAA8"))

    A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

    A kötelező előtanulmányi rendek grafikus formában itt láthatók.

    Introduction to the Theory of Computing 1
    7. Objectives, learning outcomes and obtained knowledge

    The goal of the subject is to acquire the fundamental mathematical knowledge (in the area of linear algebra and number theory) necessary for software engineering studies. 

    Students successfully completing the course will be able to:

    • (K3) understand and apply the notions and the knowledge covered by the course;
    • (K3) individually solve practical problems related to the material of the course;
    • (K2) apply the algorithms covered by the course;
    • (K3) during their further studies, identify situations where fields of knowledge covered by the course are applicable and apply them successfully.
    8. Synopsis

    1) Basics of combinatorics: permutations, variations and combinations with and without repetition. Relations between binomial coefficients, Pascal's triangle, binomial theorem.

    2) Basic notions of graph theory: graph, simple graph, degree of a vertex, walk, path, cycle, connected graph, connected component, tree, spanning tree. Deciding connectivity, finding a shortest path (with unit edge lengths): Breadth First Search.

    3) Computing a minimum weight spanning tree: Kruskal's algorithm. The notion of a planar graph, equivalence with graphs drawable on a sphere, Euler's polyhedron formula.

    4) Relation between the number of nodes and edges of a simple, planar graph. The non-planarity of the K5 and K3,3 graphs, Kuratowski's theorem. The dual of a planar graph, correspondences between the number of vertices/edges/regions, the image of cycles and cuts.

    5) The notions of Eulerian path and Eulerian cycle, necessary and sufficient conditions on their existence. The notions of Hamiltonian path and Hamiltonian cycle. Necessary conditions on their existence: the maximum number of components after deleting k nodes. Sufficient conditions: theorems of Dirac and Ore.

    6) The notion of a bipartite graph, their characterization with odd cycles. The notion of chromatic number. Greedy coloring, upper bound on the chromatic number in terms of the maximum degree. The notion of maximum clique size, relation to the chromatic number, Mycielski's construction.

    7) Optimal coloring of interval graphs. The notions of matching, vertex cover, independent set and edge cover. Relation between the sizes of the maximum matching and the minimum vertex cover. Gallai's theorems.

    8) Computing a maximum matching in a bipartite graph, the augmenting path algorithm, its optimality. Kőnig's theorem on the equality between the sizes of a maximum matching and a minimum vertex cover. Tutte's theorem.

    9) The notion of edge-chromatic number, its relation to the maximum degree, Vizing's theorem. The maximum flow problem: the norions of network, flow, overall value of a flow, the augmenting path algorithm for computing a maximum flow.

    10) The notions of an st-cut of a network, and its capacity, the Ford-Fulkerson theorem, the Edmonds- Karp theorem. The integer valued maximum flow problem. The problem of edge-disjoint s-t paths, Menger's corresponding theorem.

    11) The problem of edge-disjoint paths in undirected graphs, the problems of vertex-disjoint paths in directed and undirected graphs, Menger's corresponding theorems. The notions of k-connectivity and k-edge-connectivity, Menger's corresponding theorems.

    12) The shortest path problem in undirected and directed graphs with positive edge lengths, and with real edge length in directed graphs, the algorithms of Dijsktra, Ford and Floyd.

    13) Depth First Search in undirected and directed graphs, deciding the existence of directed cycles. Acyclic directed graphs, topological ordering. The shortest and longest path problem in acyclic directed graphs.

    14) Summary and review.

    9. Method of instruction

    2 hours of lecture and 2 hours of problem solving each week.

    The lecture introduces new theory and the role of practice classes is to deepen the acquired knowledge by applying it on problems. Since practice classes closely follow the material of corresponding lectures, a thorough knowledge of the material covered by the lectures is expected from the students. The common work done on practice classes (including homeworks) is an inherent part of the learning process. Lectures in most cases build on the material of previous weeks, it is typically impossible to follow the new material without the preliminary knowledge provided by them.

    10. Assessment


    There will be 1 midterms during the semester. In order to acquire the signature, the result of both the midterm must be at least 40%


    Oral exam. As part of the oral exam, one practice problem will be assigned that will be chosen from the problem sheets covered in the second part of the term the material of which was not part of the midterm. 

    Final grade: 30% midterm, 10% the practice problem assigned during the oral exam, 60% oral exam.
    11. Recaps There will be one midterm during the semester, and two possibilities
    to repeat it (one at the end of the semester, and one in the repeat
    To obtain a signature, you have to reach at least 40% on the midterm.
    The final grade is based 30% on the midterm, 10% on an exercise (from the material not included in the midterm) in the exam and 60% on the oral exam.
    13. References, textbooks and resources

     R. Diestel: Graph Theory

    14. Required learning hours and assignment
    In class 56
    Preparation for lectures8
    Preparation for practice classes21
    Preparation for midterms15
    Preparation for the final50
    15. Syllabus prepared by Dr. Dávid Szeszlér, associate professor, Department of Computer Science and Information Theory