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ó    

    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: 2015. november 29.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZAA01 2 2/2/0/v 4  
    3. Course coordinator and department dr. Szeszlér Dávid,
    Web page of the course cs.bme.hu/bsz2
    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
    Kötelező:
    (TárgyEredmény( "BMEVISZAA00" , "aláírás" , _ ) = -1
    VAGY
    TárgyEredmény( "BMEVISZA103" , "aláírás" , _ ) = -1 )

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

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

    A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

    Ajánlott:
    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 graph theory) necessary for software engineering studies.
    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 lecture, 2 hours problem solving
    10. Assessment

    Signature:

    2 midterms during the semester. Both must be at least 30% and at least 40% in average. 2 occasions for retake, each time either one of the test can be retaken.

    Final:

    Oral exam.

    Final grade: 40% midterms, 60% oral exam.

    14. Required learning hours and assignment
    In class56
    Preparation for classes 8
    Preparation for midterms 6
    Homework 8
    Reading assignment 0
    Preparation for final 42
    Total 120
    15. Syllabus prepared by Dr. Dávid Szeszlér, associate professor, Department of Computer Science and Information Theory