1. (5 pkt.) Sposród podanych problemów wybierz 5 i opisz krótko:

problem n-hetmanów

Na szachownicy nxn nalezy ustawić n hetmanów tak, aby sie wzajemnie nie szachowały.

puzzle n2-1

Mamy daną planszę nxn, w której jedno pole jest puste. Pozostałe są wypełnione elementami oznaczonymi cyframi od 1 do n^2-1. Należy przesuwając elementy na puste miejsce doprowadzic do stanu, w którym elementy będą ułożone po kolei - w pierwszym wierszu kolejno od 1 do n, w drugim - od n+1 do 2n itd. Przykład:
problem plecakowy (złodziejski)

Mamy dany zbiór przedmiotów, z których każdy posiada pewną objętość Vi oraz wartość ci, oraz plecak o pojemności C. Należy wybrać zbiór przedmiotów, których łączna objętość będzie <=C, a łączna wartość będzie maksymalna.

problem komiwojażera

Mamy dany zbiór n miast na mapie. Nalezy wybrac najkrótszą ścieżkę przechodzącą przez wszystkie miasta i wracającą do miasta początkowego. Każde miasto jest odwiedzane jednokrotnie.

problem jeepa

Jeep na pustyni ma danych n kontenerów po 1 jednostkę paliwa. Pozwala ona na przejechanie 1 jednostki odległości. Celem jest zmaksymalizowanie pokonanej przez jeep odległości. Jeep może wyruszyc z bazy z max. 1 jednostką paliwa, pozostawic część paliwa po drodze i wrócić korzystając z pozostałej reszty. Tankować może tylko w bazie i w miejscach, w których napotkał pozostawione paliwo.

iterowany dylemat więźnia

Rozgrywamy n gier takich, jak w dylemacie więźnia. Jaką strategię powinni stosować gracze, aby zminimalizować sumaryczną karę?
sterowanie odwróconym wahadłem

Mamy wózek poruszający się w poziomie, na którym jest umieszczone odwrócone wahadło. Należy tak sterować wózkiem, aby wahadło nie przewróciło się.

Był jeszcze problem minimalnego sudoku

Znaleźć dla danej wielkości planszy sudoku minimalną ilośc początkowo wypełnionych elementów, dla których ma ono jednoznaczne rozwiązanie
2. (2 pkt.) Na czym polega Gra w życie Conwaya?

Jest to automat komórkowy. Mamy tablicę, której każdy element może przyjąć stan pełny lub pusty. W każdej iteracji korzystamy z następujących reguł:

-jeżeli komórka ma mniej niż 2 sąsiadów, umiera

-jeżeli komórka ma więcej niż 3 sąsiadów, umiera

-jeżeli komórka ma 2 lub 3 sąsiadów, trwa

-jeżeli pusta komórka ma dokładnie 3 sąsiadów, staje się pełna
3. (3 pkt.) Na czym polega Gra w naśladownictwo Turinga (test Turinga)?

Test Turinga, czy jak sam autor go zwał, gra w naśladownictwo, wyrósł z zabawy towarzyskiej w stylu „retro”. W skrócie: pytający znajduje się w jednym pokoju, człowiek i maszyna w drugim. Zadaniem pytającego jest, za pomocą tylko odpowiedzi uzyskiwanych od rozmówców, określić, który z nich jest człowiekiem, a który maszyną.

Było też polecenie opisania dwóch szachowych testów Turinga

W I wersji tego testu gracz na podstawie samych ruchów swojego przeciwnika musi określić, czy gra z człowiekiem, czy z maszyną.

W II wersji człowiek obserwuje grę w szachy i musi określić na podstawie ruchów obu graczy, który z nich jest człowiekiem, a który maszyną.
4. (5 pkt.) Na przykładzie poniższego grafu prześledź działanie algorytmu Breadth-First-Search znajdując ścieżkę z węzła v6 (startowy) do węzła v4 (docelowy).

W algorytmie Breadth-First-Search zbiory open i closed są implementowane jako kolejki FIFO. Dlatego też pobieranie elementów ze zbioru open jest uwarunkowane kolejnością elementów do niego dodanych.
Jedna z możliwości rozwiązania:

• ustawiamy poprzednika węzła v na null

• wkładamy v do zbioru open

• dopóki zbiór open != pusty:

• pobieramy ze zbioru open (w/g kolejności FIFO!) węzeł v

• jeśli węzeł v jest rozwiązaniem, to kończymy algorytm

• dodajemy do zbioru open wszystkich potomków v, którzy nie są jeszcze w zbiorze open i w miejscu ich poprzednika ustawiamy v

Etapy poszukiwania rozwiązania dla powyższego zadania:

(jeśli traktować zbiory jak tort, to elementy na lewo - warstwy niższe, elementy na prawo - warstwy wyższe (w/g FIFO pobieramy warstwę najniżej położoną); w nawiasie przy węźle podany jest jego poprzednik)

1. open := {v6(null)} ; closed := {null}

2. open := {v1(v6), v7(v6)} ; closed := {v6(null)}

3. open := {v7(v6), v2(v1), v3(v1)} ; closed := {v6(null), v1(v6)}

4. open := {v2(v1), v3(v1)} ; closed := {v6(null), v1(v6), v7(v6)}

5. open := {v3(v1)} ; closed := {v6(null), v1(v6), v7(v6), v2(v1)}

6. open := {v4(v3)} ; closed := {v6(null), v1(v6), v7(v6), v2(v6), v3(v1)}

7. algorytm stop: v4 - rozwiązanie

5. (3 pkt.) Podaj algorytm A*.

Algorytm A* próbuje wybierać najlepszą spośród ścieżek prowadzących do rozwiązania. Dla każdego węzła (v) w liczy:

-h(v), czyli jego przybliżoną odległość od rozwiązania - heurystykę

-g(v), czyli odległość od punktu początkowego - zwykle ilość kroków, jakie przeszliśmy, aby dotrzeć do tego stanu.

-f(v)=g(v)+h(v)

Żeby obliczyć g(w), który jest potomkiem v, należy skorzystać z wzoru g(w) = g(v) + d(v,w). d(v,w) jest kosztem przejścia z stanu v do w - w tych algorytmach z laborek dodawaliśmy po prostu 1.

1. Dla stanu początkowego oblicz h, g ustaw na 0, f=h+g i pustego poprzednika.

2. Dodaj stan początkowy do Open

3. Dopóki zbiór Open jest niepusty:

Pobierz i usuń element v ze zbioru Open - o najmniejszej wartości f

1. Jeżeli v jest stanem docelowym, zakończ algorytm

2. W przeciwnym wypadku wyznacz stany potomne w i dla każdego z nich:

Jeżeli w należy do Closed, pomiń w innym wypadku:

1. Oblicz h(w), g(w)=g(v)+d(v,w), oraz f(w)=g(w)+h(w)

2. Jeżeli stan nie występuje w Open dodaj go ustawiając v jako poprzednika

3. Jeżeli stan występuje w Open, podmień wartości g i f oraz poprzednika, o ile są korzystniejsze.

6. (3 pkt.) Do czego stosuje się algorytm MIN-MAX? Na czym polega? Co to jest efekt horyzontu?

    Algorytm MIN-MAX stosuje się do gier dwuosobowych (szachy, warcaby, GO itp.). Jest to metoda w teorii decyzji do minimalizowania maksymalnych możliwych strat - opcjonalnie do maksymalizacji minimalnego zysku. Buduje się drzewo do zadanej głębokości i przechodzi się je od dołu do góry nadając oceny liczbowe poszczególnym stanom gry. (Drzewo ma na przemian poziomy MIN i MAX, łopatologicznie gdy jest poziom min wybieramy mniejszą wartość, gdy max - większą ). Funkcje optymalizujące: min dąży do minus nieskończoności, max do plus nieskończoności. Ruch jednego z graczy nazywamy półruchem (ang. ply).

    Efekt horyzontu jest zauważalny, gdy przez ograniczoną głębokość przeszukiwania pominąć można różne zagrożenia, które by zauważono zwiększając głębokość przeszukiwania. Inaczej mówiąc: może się zdarzyć, że w ramach pewnej maksymalnej głębokości przeszukiwania gracz wybiera najlepsze dla siebie posunięcie, jednak gdyby rozważyć większą głębokość okaże się, że posunięcie jest złe.
7. (3 pkt.) Jaki rodzaj zadania rozwiązuje perceptron Rosenblatta? Narysuj schemat perceptronu Rosenblatt'a i podaj wzór na wyjście.

Perceptron Rosenblatt'a rozwiązuje zadanie klasyfikacji binarnej. Szukamy prostej, która rozdziela punkty dwóch klas. Budowa perceptronu (S- sumator, f(s)-funkcja aktywacji):

Mamy n+1 wejść - pierwsze wejście przed x1 jest stałą jedynką-wszystkie wejścia trafiają na sumator po uprzednim przemnożeniu je przez wagi w0-wn. Sygnał po zsumowaniu podawany jest na funkcję aktywacji, która zwraca wartość 1 jeśli S>0 lub -1 jeśli S<=0.

Wzór na aktualizację wag:a



eta = współczynnik szybkości uczenia perceptronu
yi = klasyfikator punktu (np. -1 lub 1)

8. (4 pkt.) W sieci MLP (Multi-Layer Perceptron) do jednego z neuronów dochodzą następujące
sygnały: x0 = 1, x1 = −0.5, x2 = 2, a odpowiadające im wagi to v0 = 2.5, v1 = 1, v2 = −0.5.
Oblicz wartość funkcji aktywacji (f. sigmoidalnej) tego neuronu.

Funkcja sigmoidalna jest określona wzorem: 

    
  ,gdzie 

Inna wersja 8. :

W perceptronie Rosenblatta w pewnej iteracji waga wynosi w(k) = [-1,2,-4,-6]. Losowe xi jest równe [2,-1,4,-2], yi = -1. Współczynnik eta to 0.5. Wyznacz wagę w następnej iteracji, a także sprawdź czy jest ona poprawna.  

9. (2 pkt.) Jaka jest idea działania metody uczenia back propagation dla sieci MLP?

Po przetworzeniu wektora wejściowego, nauczyciel porównuje wartości otrzymane z wartościami oczekiwanymi i informuje sieć czy odpowiedź jest poprawna, a jeżeli nie, to jaki powstał błąd odpowiedzi. Błąd ten jest następnie propagowany do sieci ale w odwrotnej niż wektor wejściowy kolejności (od warstwy wyjściowej do wejściowej) i na jego podstawie następuje taka korekcja wag w każdym neuronie, aby ponowne przetworzenie tego samego wektora wejściowego spowodowało zmniejszenie błędu odpowiedzi. Procedurę taką powtarza się do momentu wygenerowania przez sieć błędu mniejszego niż założony. Wtedy na wejście sieci podaje się kolejny wektor wejściowy i powtarza te czynności. Po przetworzeniu całego ciągu uczącego (proces ten nazywany jest epoką) oblicza się błąd dla epoki i cały cykl powtarzany jest do momentu, aż błąd ten spadnie poniżej dopuszczalnego.

Algorytm wstecznej propagacji błędów wygląda więc następująco:

1. Pobierz ze zbioru uczącego parę wejście-oczekiwane wyjście.
2. Podaj na wejście neuronu wartości wejściowe.
3. Przepuść sygnał przez sieć obliczając wyjścia poszczególnych neuronów w kolejnych     warstwach.
4. Oblicz sygnał wyjściowy neuronów z warstwy wyjściowej.
5. Oblicz błędy w neuronach warstwy wyjściowej - d=(o-y)*f'(z).
6. Korzystając ze wzoru: 
 przepropaguj (wstecz) błędy przez całą sieć
7. Uaktualnij (w=w+h*d*x) wszystkie wagi w sieci.
8. Powyższe kroki powtarzaj dla wszystkich par uczących.
9. Zakończ naukę gdy całkowity błąd dla wszystkich wzorców uczących będzie mniejszy od pewnej ustalonej na początku nauki wartości.

Symbole we wzorach:

o - obliczone wyjście perceptronu

y - oczekiwane wyjście

f'(z)

---