Quicksort in minimalni prerez.
Razredi problemov in vrste naključnostnih algoritmov.
Uporaba polinomov.
Černove meje.
Naključnostni prirastni algoritmi in povratna analiza.
Linearno programiranje v nižjih dimenzijah.
Markovske verige.
Približno štetje.
Podlinearni algoritmi.
Verjetnostna metoda.
Verjetnostne metode v računalništvu
2018/2019
Program:
Interdisciplinarni magistrski študijski program 2. stopnje Računalništvo in matematika
Letnik:
1 ali 2 letnik
Semester:
prvi ali drugi
Vrsta:
izbirni
Skupina:
A
ECTS:
6
Jezik:
slovenski, angleški
Nosilec predmeta:
Ure na teden – 1. ali 2. semester:
Predavanja
2
Seminar
1
Vaje
2
Laboratorij
0
Vsebina
Temeljni literatura in viri
M. Mitzenmacher in E. Upfal. Probability and Computing. Cambridge University Press, 2005.
R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, 1995.
M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry: Algorithms and Applications. 3. izdaja, Springer, 2008.
J. Kleinberg in É. Tardos. Algorithm Design. Addison-Wesley, 2005.
Cilji in kompetence
Študent spozna uporabo verjetnosti za algoritmične in sorodne probleme.
Predvideni študijski rezultati
Osnovni naključnostni algoritmi.
Naključnostni algoritmi v računski geometriji.
Uporaba verjetnosti za analiziranje časovne zahtevnosti algoritmov.
Uporaba verjetnosti za dokazovanje obstoja objektov.
Metode poučevanja in učenja
Predavanja, seminar, vaje, domače naloge, konzultacije, in samostojno delo študentov.
Načini ocenjevanja
Sprotno preverjanje (domače naloge, kolokviji in projektno delo).
Končno preverjanje (pisni ali ustni izpit)
(ocene: 5 (negativno), 6-10 (pozitivno), ob upoštevanju Statuta UL)
Reference nosilca
CABELLO, Sergio, ROTE, Günter. Obnoxious centers in graphs. SIAM journal on discrete mathematics, ISSN 0895-4801, 2010, vol. 24, no. 4, str. 1713-1730. [COBISS-SI-ID 15762265]
BERG, Mark de, CABELLO, Sergio, HAR-PELED, Sariel. Covering many or few points with unit disks. Theory of computing systems, ISSN 1432-4350, 2009, vol. 45, no. 3, str. 446-469. [COBISS-SI-ID 14900825]
CABELLO, Sergio, FORT, Marta, SELLARÈS, J. Antoni. Higher-order Voronoi diagrams on triangulated surfaces. Information processing letters, ISSN 0020-0190. [Print ed.], 2009, vol. 109, iss. 9, str. 440-445. [COBISS-SI-ID 15160153]
