====== Algorytmy probabilistyczne - Lista 3. ======

===== 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.

Baza: 
Drzewa w postaci $(liść\;OR\;liść\;OR\;\dots\;OR\;liść)$.
Na zapytania o pierwsze $n-1$ liści tego drzewa odpowiadamy 0. Wtedy A nie wie, czy poddrzewo ma wartość 1, czy 0, bo zależy to od ostatniego liścia.
Jeżeli chcemy wymusić 1, to mówimy 1, jeżeli 0, mówimy 0.

Krok I:
Drzewa w postaci $(drzewo\;AND\;drzewo\;AND\;\dots\;AND\;drzewo)$.
Na zapytania o pierwsze $n-1$ poddrzew tego drzewa wymuszamy 1 w tym poddrzewie. Wtedy A nie wie, czy poddrzewo ma wartość 1, czy 0, bo zależy to od ostatniego poddrzewa.
Jeżeli chcemy wymusić 1, to mówimy 1, jeżeli 0, mówimy 0.

Krok II:
Drzewa w postaci $(drzewo\;OR\;drzewo\;OR\;\dots\;OR\;drzewo)$.
Na zapytania o pierwsze $n-1$ poddrzew tego drzewa wymuszamy 0 w tym poddrzewie. Wtedy A nie wie, czy poddrzewo ma wartość 1, czy 0, bo zależy to od ostatniego poddrzewa.
Jeżeli chcemy wymusić 1, to mówimy 1, jeżeli 0, mówimy 0.

Liści w drzewie d-arnym o wysokości 2k jest $d^{2k}$, algorytm A odwiedza wszystkie.

===== Zadanie 2 =====
====a====
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.

Baza: 
Drzewa w postaci $maj(liść,liść,liść)$.
Na zapytania o pierwsze $2$ liście tego drzewa odpowiadamy 0,1. Wtedy A nie wie, czy poddrzewo ma wartość 1, czy 0, bo zależy to od ostatniego liścia.
Jeżeli chcemy wymusić 1, to mówimy 1, jeżeli 0, mówimy 0.

Krok:
Drzewa w postaci $maj(drzewo,drzewo,drzewo)$.
Na zapytania o pierwsze $2$ poddrzewa tego drzewa wymuszamy 0,1.w tych poddrzewie. Wtedy A nie wie, czy poddrzewo ma wartość 1, czy 0, bo zależy to od ostatniego poddrzewa.
Jeżeli chcemy wymusić 1, to mówimy 1, jeżeli 0, mówimy 0.

Odwiedzamy wszystkie $3^h$ liście.

===== Zadanie 3 =====
===== Zadanie 4 =====
===== Zadanie 5 =====
===== Zadanie 6 =====
===== Zadanie 7 =====