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.
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
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.
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,
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.
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 grade: 40% midterms, 60% oral exam.