Belépés címtáras azonosítással
magyar nyelvű adatlap
angol nyelvű adatlap
Foundation of Computer Science
A tantárgy neve magyarul / Name of the subject in Hungarian: A számítástudomány alapjai
Last updated: 2015. november 23.
Electrical Engineering
BSc
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ó.
The objective is to provide the students with the required theoretical background in combinatorics, algorithmics, elementary cryptography, and graph theory for further studies in electrical engineering.
Week 1: Basic concepts of combinatorics: permutations, variations, combinations, binomial coefficient, nimonial theorem
Week 2: Basic concepts of graph theory (vertex, edge, degree, isomorphism). Path, circuit, connectivity, trees.
Week 3: Shortest path, BFS, Dijkstra, Ford, Floyd algorithms, widest paths in directed and undirected graphs
Week 4: DFS, directed cycles, fundamental system of cycles and cuts, PERT
Week 5: Euler- and Hamiltonian circuits, sufficient and necessary conditions for the existence. Dirac, Ore theorems,
Week 6: Graph coloring problems (vertex, edge and map coloring). Bipartite graphs. Flows, Ford-Fulkerson theorem, algorithm to find a maximal flow. Integral maximum flow lemma.
Week 7: Multiple source flows, vertex capacities, undirected flows.
Week 8: Bipartite graphs, matchings, Hall's theorem, algorithm to find a maximal matching. Independent and covering vertex and edge sets, König's and Gallai's theorems.
Week 9: Planar graphs, duality. Euler's Theorem, Kuratowski's theorem, four color theorem.
Week 10: Basic concepts of algorithms and complexity. Polynomially solvable and NP-complete problems, coNP.
Week 11: Karp-reduction, Cook-Levin theorem, famous NP-complete problems: SAT, HAM, 3-COLOR, k-COLOR, MAXSTABLE, MAXCLIQUE, HAMPATH.
Week 12: Basic concepts in number theory: divisibility, primes, fundamental theorem of number theory, number of divisors, distribution of primes
Week 13: Congruences, diophantine equations, Euler-Fermat theorem,
Week 14: Algorithms in number theory: prime tests, public key cryptography, RSA.
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.
Dr. Tamás Fleiner, associate professor
Department of Computer Science and Information Theory
Dr. Gyula Katona, associate professor
Dr. András Recski, professor
