Verjetnostna metodaStibilj, Timotej (Avtor) Perman, Mihael (Mentor) verjetnostna metodaverjetnostni algoritemmetoda izbrisapričakovana vrednostneenakost Markovaneenakost Čebiševaslučajni grafVerjetnostno metodo uporabljamo za nekostrukcijsko dokazovanje obstaja kombinatoričnih objektov z določenimi lastnostmi. Spoznamo osnove verjetnostnih algoritmov in povezavo z verjetnostno metodo; dokaz z verjetnostno metodo lahko pogosto prevedemo na verjetnostni algoritem. Spoznamo več načinov uporabe verjetnostne metode: osnovno metodo, metodo izbrisa, uporabo linearnosti pričakovane vrednosti in metodo drugega momenta. Pri vsaki metodi je predstavljen najmanj en primer. Predstavljena so Ramseyeva števila, barvanje hipergrafov in turnirji. Na primeru maksimalnega prereza grafa prikažemo prevedbo dokaza na verjetnostni algoritem in njegovo derandomizacijo. Dokažemo Erdősev izrek, ki pravi, da obstaja graf s poljubno veliko ožino in poljubno velikim kromatičnim številom. Spoznamo pojem slučajnega grafa in pragovne funkcije ter poiščemo pragovno funkcijo za vsebovanost danega podgrafa.20242024-07-14 08:15:03Delo diplomskega seminarja/zaključno seminarsko delo/naloga159615UDK: 519.17VisID: 139918COBISS_ID: 201843971sl