20.500.12556/RUL-159615 Verjetnostna metoda delo diplomskega seminarja Probabilistic method Verjetnostno 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. The probabilistic method is used for nonconstructive proofs of existence of combinatorial objects with certain properties. We present the basic ideas of randomized algorithms and show their connection to the probabilistic method. Proofs using the probabilistic method often lead to randomized algorithms for such objects. Several ways of using the probabilistic method are shown, including the basic method, alteration, the use of linearity of expectation and the second-moment method. There is at least one example for each method. We present Ramsey numbers, hypergraph coloring and tournaments. In the example of the maximum cut problem, we present the randomized algorithm and its derandomization. We prove Erdős’ theorem, which states that there exists a graph with arbitrarily large girth and arbitrarily large chromatic number. Lastly, we introduce the idea of random graphs, their threshold functions and find the threshold function for containing a given subgraph. verjetnostna metoda verjetnostni algoritem metoda izbrisa pričakovana vrednost neenakost Markova neenakost Čebiševa slučajni graf probabilistic method randomized algorithm alteration expected value Markov’s inequality Chebyshev’s inequality random graph true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2024-07-14 08:15:03 2024-07-14 08:15:08 2024-07-19 03:30:44 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 139918 201843971 12182.pdf 12182.pdf 1 82E73989B9ACD1B2E724EE4F5452EE43 0d7993ef9f99df46ac0d4b31d382c583ac7a946ef4e9b11e6ca9a62ee907bcaa 6589c484-41a8-11ef-8f74-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=187707 Fakulteta za matematiko in fiziko 0 0 0