Zadání studentských prací

Zadání bakalářské práce

Základní údaje

Posluchač:
Program / Obor:

Název (CZ):	Náhodné algoritmy: teorie a implementace
Název (EN):	Randomized algorithms: theory and implementation

1.	Náhodné algoritmy řeší zadaný problém za použití menšího či většího počtu náhodných bitů. V současné době nachází řadu uplatnění v diskrétní matematice, teorii grafů, strojovém učení, nebo optimalizaci.
2.	Student se seznámí se základními příklady randomizovaných algoritmů a matematickým aparátem nezbytným pro analýzu jejich vlastností (odhady chyb, délka běhu, apod.)
3.	Student provede analýzu několika vybraných složitějších aplikací randomizovaných algoritmů (např. problém výběrčího kuponů, expanding graphs, teorie diskrepance nebo i jiné), včetně odvození potřebných statistických odhadů.
4.	Student naprogramuje pro různé parametry tyto zvolené algoritmy a demonstruje tak prakticky jejich vlastnosti při řešení zadaných problémů. Tam, kde to bude možné, provede srovnání s dostupnými deterministickými algoritmy.
5.
6.
7.
8.

Vyžadovaný formát referencí

Dodržujte následující formátování seznamu použité literatury. Pokud formát nedodržíte, bude Vám zadání vráceno k přepracování.

článek v časopise: Autor/ři, Název_článku. Název_časopisu ročník, rok, stránky.
příklad: K. G. Hare, Tiles in quasicrystals with quartic irrationality. Mathematics of Computation 75, 2009, 405–420.
kniha: Autor/ři, Název_knihy. Vydavatel, rok.
příklad: N. L. Johnson, S. Kotz, N. Balakrishnan, Continuous univariate distributions. John Wiley & Sons, New York, 1994.
příspěvek ve sborníku: Autor/ři, Název_příspěvku. In ‘Název_sborníku’, Vydavatel, rok, stránky.
příklad P. Mueller, P. Wonka, S. Haegler, et al., Procedural modeling of buildings. In ‘ACM SIGGRAPH 2006 Papers’, ACM New York, 2006, 614–623.

1.	N. Alon, and J. H. Spencer: The probabilistic method, Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1992.
2.	R. Motwani and P. Raghavan: Randomized algorithms, Cambridge University Press, Cambridge, 1995.
3.
4.
5.
6.

Školitel:
	(Celé jméno a příjmení s tituly)
Pracoviště:	Katedra matematiky FJFI ČVUT v Praze Trojanova 13 120 00 Praha
	(Název instituce a adresa)
Email:
Telefon:

Konzultant:
	(Celé jméno a příjmení s tituly)
Pracoviště:
	(Název instituce a adresa)

Datum zadání:
Datum odevzdání:

Stav zadání

Schváleno KM

Historie

2022-10-03 19:37:22

– zahájení procesu zadání

2022-10-03 19:39:05

– zasláno školiteli

2022-10-05 08:09:52

– upraveno školitelem

2022-10-10 19:15:10

– zasláno na KM

2022-10-10 22:20:59

– žádost o autorizaci

2022-10-11 09:35:45

– autorizováno školitelem

2022-11-22 15:24:41

– schváleno KM