http://ii.drx.pl/ 2026-05-23T19:57:24+02:00 http://ii.drx.pl/ http://ii.drx.pl/lib/images/favicon.ico text/html 2011-03-11T02:25:24+02:00 http://ii.drx.pl/algorytmy_probabilistyczne:lista1?rev=1299806724&do=diff Zadanie 1 <http://en.wikipedia.org/wiki/Monty_Hall_problem> Zadanie 2 (zmienne są i.i.d. parami) =>=>=> Zadanie 3 alternatywnie: Zadanie 4 Zadanie 5 las_vegas(args): while true: a = monte_carlo(args) if a is correct: return text/html 2011-03-18T02:10:03+02:00 http://ii.drx.pl/algorytmy_probabilistyczne:lista2?rev=1300410603&do=diff Zadanie 1 * Run C for at least double its expected running time. If it gives an answer, give that answer. If it doesn't give any answer before we stop it, give NO. => * Suppose we have a language L recognized by both the RP algorithm A and the (possibly completely different) co-RP algorithm B. Given an input in L, run A on the input. If it returns YES, the answer must be YES. Otherwise, run B on the input. If it returns NO, the answer must be NO. If neither occurs, repeat this step. … text/html 2011-04-01T01:16:56+02:00 http://ii.drx.pl/algorytmy_probabilistyczne:lista3?rev=1301613416&do=diff Zadanie 1 Tworzymy strategie dla adwersarza dla programu, który sprawdza wynik w drzewie. Idukcyjnie po strukturze drzewa, pokażemy, że w każdym poddrzewie potrafimy dla danego algorytmu przeciwnika A, który dfsuje, zmusić go do odwiedzenia wszystkich wierzchołków i w dodatku do uzyskania wyniku jaki chcemy w korzeniu drzewa. text/html 2011-04-15T01:44:27+02:00 http://ii.drx.pl/algorytmy_probabilistyczne:lista4?rev=1302824667&do=diff Zadanie 2 Prawdopodobieństwo tego, że nie będzie kolizji przy B kulach i n pudełkach: Jak 0.5 to prawdopodobieństwo tego, że nie ma kolizji, to 1-0.5 = 0.5 to prawdopodobieństwo, że ta kolizja zajdzie. Zadanie 3 Zadanie 4