Algorithms and Complexity
A tantárgy neve magyarul / Name of the subject in Hungarian: Algoritmusok és bonyolultságuk
Last updated: 2016. július 29.
Engineering Information Technology, MsC
Theory of Computation, minor specialization
Dr Csima Judit associate professor Department of Computer Science and Information Theory
Dr Friedl Katalin associate professor Department of Computer Science and Information Theory
Dr Katona Gyula 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 rend az adott szak honlapján és képzési programjában található.
Introduction of selected topics.
Interactive proofs -- a possible generalization of NP. Strong and weak players, the AM and IP classes. Probabilistically checkable proofs.
Communication complexity : computation with minimal information exchange. Connection to the matrix of the function. Nondeterministic complexity and its relation to deterministic complexity. Randomized protcols and their efficiency.
Geometrical algorithms: computations without division, closest pair of points, efficient convex hull computation .
Advanced search techniques: k-th element in linear time, computation of rank. How to store intervals
Pattern matching: KMP and Boyer-Moore algorithms. Pattern matching by finite automaton. Matching with errors, approximate solutions, and the efficient computation of edit distanc.
Parallel algorithms: variants of the PRAM model. Comparisons for simple cases. Computations organized in binary trees. The effect of changing the numer of processors (Brent's theorem)
Parallel algorithms for sorting (Batcher). Prefix sum computation and its applications. Computation of ranks.
Distributed algorithms: theoretical model. Leader selection algorithms on rings and on general graphs.
Distributed algorithms whith failers: fails in lines, when processors stop, and byzantine errors.
Network topologies from graph theoretical point of view: grid, cube, cube connected cycel, butterfly, Benes(shortest paths, diameter, cuts). Embeddings,algorithmical aspects.
Random graphs: different models, their basic properties (degrees, paths, connectedness). Random graphs as models of networks.
Parametric complexity: NP-hard problems with efficient solution for small values of a parameter. Bounding the depth of a search tree.Grpah minor theorem and consequences. The kernel method. W[1] complexity.
On-line algorithms: measure of effifiency. Examples. Scheduling algorithms.
Quantum computation: tools from linear algebra, simple algorithms (teleporting, Deusch-Jozsa). Qunatum Fourier transformation, the idea of prime factorization. Quantum cryptography.
T. Corman, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms
H. Attiya: Distributed Computing lecture notes
J. Flum, M. Grohe: Parameterized Complexity Theory, Springer 2006.
A. Gibbons, W. Rytter: Efficient Parallel Algorithms, Cambridge University Press, 1988.