zaliczenie WDSI
12

(1 pkt.) Podaj główną różnicę pomiędzy algorytmami A"¹, Bmt-First-Searcli i algorytmem Dijkstry.

(2 pkt.) .Jakich struktur danych dobrze jest użyć do implementacji zbiorów Open i Ciosał w algorytmie .4* i dlaczego?

(2 pkt.) W pewnym trójwymiarowym labiryncie gracz może poruszać się tylko po liniach prostych (lewo prawo, przód / tył. góra / dół). Punktem docelowym jest. punkt o współrzędnych (10, -3,1). Zapis/, heurystykę za pomocą metryki Manhattan w ogólności dla dowolnego punktu (x, y,w którym może znaleźć się gracz.

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

(1 pkt.) Jaką złożoność obliczeniową ma algorytm MIN-MAX? Przyjmij: D liczba poziomów drzewa, b — średnia liczba ruchów z każdego węzła.

(3 pkt.) Podaj algorytm przycinanie a-fi w formie dwóch procedur rekureiieyjnych (wyjaśnij oznaczenia), Z czego wynika przewaga tego algorytmu nad algorytmem MIN-MAX.

(3 pkt.) Na poniższym drzewie gry skreśl gałęzie, których nie odwiedzi algorytm przycinanie o-o (zakładamy porządek odwiedzania dzieci „od lewej do prawej”).

MAX

( 1 pkt.) Dana jest następująca gra dwuosobowa, w której gracze wykonują ruchy naprzemiennie. Na, stole leży pięć zapałek. Każdy gracz w ramach swojego ruchu może zabrać: ze stołu jedną lub dwie zapałki. Przegrywa ten gracz, który weźmie -ostatnią zapałkę (lub zapałki). Udowodnij, który z graczy zawsze wygrywa w tej grze.

(2 pkt.) W perceptronie Rosenblatfa do poprawki aktualnych wag w.{k) ~ (2.0.1,.....3) wybrano punkt

X] , — (2. —3. —2,1) o yis = 1. Przyjmując fj = 0.5 oblicz wagi w kroku następnym: ‘tr(k + i). Sprawdź, czy po poprawce ten punkt jest już dobrze klasyfikowany.

(2 pkt.) Na podstawie dowodu Novikoffa podaj górne ograniczenie' na maksymalną liczbę kroków w algorytmie uczenia perceptronu Rosenblatfa. Wyjaśnij wielkości występujące w tym ograniczeniu.

(2 pkt.) Podaj wzór obliczający współrzędne punktu danych w przestrzeni o większej wymiarowośei wg imekształcenia Gaussa. Wyjaśnij oznaczenia.

(2 pkt.) Narysuj schemat sieci MLP z jedną warstwą ukrytą (nieliniowe neurony sigmoidahu:) i z, jednym liniowym neuronem w warstwie wyjściowej.

(2 pkt,.) Dla sigmoidalnej funkcji aktywacji 4>(s) w sieci MLP pokaż że: cf>'(s) - (/)($) (l ^— 0(s)

(3 pkt..) Podaj ogólny algorytm back-propagation w formie rckurencyjnej.