A tárgy célja, hogy a hallgatóink képesek legyenek randomizált algoritmusok tervezésére, és elemzésére. Alapelv: minden egyes témához sok konkrét alkalmazást mutatunk be, hangsúlyt helyezünk a szemléletre.
Tematika: Létezés és véletlen (4 óra). Véletlent használó egzisztanciabizonyítások (az ún. Erdős-módszer) nevezetes példákon keresztül (hipergráf 2-színezése, Ramsey-gráfok, stb.), ezek algoritmikus vonatkozásai. A Turán-tétel véletlent használó bizonyítása. Derandomizálás. Néhány nevezetes randomizált algoritmus elemzése (8 óra). A gyorsrendezés várható lépésszáma. A Rabin–Miller-prímteszt elemzése. A Schwartz–Zippel-lemma és közvetlen alkalmazásai (Tutte-determináns, mátrixszorzás ellenőrzése). Randomizált mintaillesztés. Minimális feszítőfa számítása lineáris várható időben. Bolyongások és algoritmusok. Lovász lokális lemmája (2 óra). A módszer ismertetése, néhány egyszerű alkalmazása, a módszer algoritmikus változata. Véletlen és bonyolultsági osztályok (8 óra ea). Az RP és a Las Vegas nyelvosztályok, példákkal. Az IP nyelvosztály: nem izomorrf gráfok, IP=PSPACE lényeges részének a bizonyítása. Nulla ismeretű bizonyítás fogalma, példák. A BPP nyelvosztály, a BPP és a P viszonyával foglalkozó néhány eredmény vázlatos ismertetése. Az RL nyelvosztály. Véletlen grá fok (4 óra) Erdős–Rényi-gráfok, néhány gráftulajdonság (pl. összefüggőség) evolúciója. Barabási-Albert-gráfok, alkalmazásuk (számítógépes-, szociális-, biológiai-) hálózatok modellezésére.

The objective of the  course is to enable students to design and analyse randomised algorithm, and have a first understanding of randomness in the context of computation.
Major topics: Existence and randomness. Existence proofs using probailistic arguments (the Erdős method) through notable examples (2-coloring of hypergraphs, diagonal Ramsey numbers, good assignments for a 2-CNF, etc. ), with algorithmic aspects. Probabilistic proof for Turán's theorem. Derandomization. – Analysis of some important randomized algorithms: the expected running time of quicksort, Rabin-Miller primality test, the Schwartz-Zippel lemma and some applications (Tutte determinant, equality testing). Randomized pattern matching. Minimum weight spanning tree in expected linear time. Random walks and algorithms. Lovász local lemma, applications and algorithmic aspects. – Randomness and complexity classes. RP and Las Vegas classes with examples. The IP language class: non isomorphic graphs, interactive proof for #3-SAT. The BPP and RL complexity classes. –  Random graph models. Erdős–Rényi graphs, threshold functions. Watts-Strogatz and Albert-Barabási graph models. Kleinberg's algorithmic small world.