Pogojev za vključitev v delo ni.
Verjetnostne metode v računalništvu
2021/2022
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:
Izvajalec (kontaktna oseba):
Ure na teden – 1. ali 2. semester:
Predavanja
2
Seminar
1
Vaje
2
Laboratorij
0
Vsebina
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.
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
Izpit iz vaj (2 kolokvija ali pisni izpit) ali domače naloge
ustni izpit
Ocene: 6-10 pozitivno, 5 negativno (v skladu s Statutom 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]
