1.1. Sztuczna Inteligencja: Dział Informatyki, Którego Przedmiotem

Transcript

1.1. Sztuczna inteligencja: Dział informatyki, którego przedmiotem jest badanie reguł rządzących inteligentnymi zachowaniami człowieka, tworzenie modeli formalnych tych zachowań i – w rezultacie – programów komputerowych symulujących te zachowania. 1.2.Podaj 3 różne typy inteligencji? Inteligencja Kognitywna –sprawność umysłowa (analiza i synteza danych) Inteligencja Werbalna – zdolność formułowania wypowiedzi Inteligencja Twórcza – zdolność do generowania nowych pojęć 1.3.Test Turinga. to sposób określania zdolności maszyny do posługiwania się językiem naturalnym i pośrednio mającym dowodzić opanowania przez nią umiejętności myślenia w sposób podobny do ludzkiego. Sędzia (człowiek) prowadzi rozmowę z pozostałymi uczestnikami w języku naturalnym. Sędzia ma określić czy jego rozmówca to człowiek, czy maszyna. Maszyna zachowuje się jak człowiek . 1.4. Na czym polega argument „chińskiego pokoju”? Co ma pokazać? John Searle (1932-) - Człowiek zamknięty w pokoju. Przez szparę pod drzwiami otrzymuje wiadomości napisane po chińsku. Człowiek nie zna chińskiego, ale dysponuje „książką reguł” - która określa jakie znaki są odpowiedzią na określone znaki wejściowe. Człowiek kopiuje znaki odpowiedzi i wysuwa swoją odpowiedź na zewnątrz. Człowiek w pokoju może uczestniczyć w konwersacji, a nawet przejść test Turinga – nie zna on jednak języka. 1.5. Podać przykłady współczesnego wykorzystania systemów opartych na sztucznej inteligencji. *Algorytmy genetyczne i programowanie ewolucyjne *Rozpoznawanie mowy i pisma – zastosowanie tzw. „ukrytych modeli Markowa” *Wnioskowanie probabilistyczne *Rozwój robotyki *PEGASUS –rozpoznawanie i analiza mowy *MARVEL – obróbka danych przychodzących ze stacji kosmicznych *Systemy wspierające kierowanie pojazdów, diagnostykę medyczną, sterowanie ruchem w miastach, wspomagające decyzje biznesowe 2.1. zasady „gry w życie” Conway’a. * 2-wymiarowa siatka prostokątnych komórek. * Każda komórka może być żywa lub martwa (dwa stany) * Każda komórka ma potencjalnie 8 sąsiadów * Komórka umiera jeżeli liczba sąsiadów jest mniejsza niż 2 lub większa niż 3. * Martwa komórka „ożywa” jeżeli ma dokładnie 3 sąsiadów 2.2. zasady gry „wojny rdzeniowe” Gracze umieszczają programy napisane w psudoassemblerze (Redcode) na serwerze * Pojedynki każdy-z-każdym, np. 100 walk w ramach pojedynku * Wyliczana punktacja (liczba zwycięstw, porażek, remisów) * Zwycięzcy turnieju biorą udział w kolejnym turnieju. 2.3. Do jakiego typu eksperymentów może służyć program Tierra? *Komputerowy model ewolucji *„Organizmy” walczą o zasoby (CPU i pamięć wirtualnej maszyny) *Modelowanie selekcji naturalnej, ewolucji typu pasożyt-nosiciel i innych. 2.4. Co to jest sztuka ewolucyjna? * Dzieła sztuki wykorzystujące proces ewolucji do ciągłej modyfikacji * System ulega ciągłej ewolucji * Artysta ocenia poszczególne „osobniki” i określa ich funkcję przystosowania. * Osobniki o najlepszej funkcji przystosowania kierowane są do dalszej ewolucji * Łączy grafikę komputerową i metody sztucznej inteligencji (sieci neuronowe, algorytmy genetyczne 3.1. Czym się różni optymalizacja lokalna od globalnej? Op. lokalna — punkt, w którym funkcja celu ma wartosc najmniejsza (najwieksza) niz w jakichkolwiek innych dopuszczalnych punktach w swoim otoczeniu. Op. globalna — najlepsze z rozwiazan lokalnych. Róznią się metodami szukania minimum. Lokalne: Przeszukiwanie liniowe *Metoda simplex * Metoda największego spadku *Metody gradientow sprzężonych W globalnej :Brak ogólnego algorytmu rozwiązywania GOP 3.2.Wymień 3 różne metody szukania minimum lokalnego. Opisz krótko jedna z nich. *Metoda największego spadku *Metody gradientow sprzężonych * Metoda simplex w n-wymiarowej przestrzeni na bazie n+1 punktów (wierzchołków) buduje się figure nazywana simplexem. Optymalizacja polega na budowaniu kolejnych przyblizen, gdzie punkt o najwiekszej wartosci jest symetrycznie „odbijany” od naprzeciwległej sciany. Jednoczesnie moze nastapic rozszerzenie lub zawezenie simplexu. Warunkiem zakonczenia jest jego zmniejszenie ponizej wartosci progowej. 3.3. Czym różnią się deterministyczne i stochastyczne metody szukania minimum globalnego? Metody deterministyczne gwarantują znalezienie minimum globalnego w przeciwieństwie do metod stochastycznych. Te pierwsze stosuje się do specyficznych i względnie prostych problemów natomiast te drugie używane są do złożonych problemów. Do metod deterministycznych często wymagana jest specjalna postać lub szczególne własności badanej funkcji natomiast do metody stochastycznej są potrzebne mniejsze wymagania 3.4. Proszę podać przykłady dwóch metod szukania minimum globalnego. Proszę krótko opisać działanie jednej z nich. - Metoda bisekcji ( „ Złoty Podział „) - Metoda Simplex 3.5. Na czym polegają metody Monte Carlo? Proszę podać przykłady wykorzystania. W optymalizacji nazwę Monte Carlo zwykle stosuje się do metody wykorzystującej tzw. kryterium Metropolisa. Oparte o zmodyfikowane błądzenie losowe: – Jeżeli nowy stan jest lepszy od starego, jest akceptowany – Jeżeli nowy stan jest gorszy od starego, jest akceptowany z prawdopodobieństwem zależnym od różnicy stanów. Stosowane do modelowania matematycznego bardzo złożonych procesów (np. w fizyce, chemii, biologii). 3.6. Proszę krótko opisać zasadę działania algorytmu „Symulowanego wyżarzania”. Adresuje problem parametrów M-C – Zbyt duże prawd. akceptacji – błądzenie losowe – Zbyt małe prawd. akceptacji – algorytm wspinaczkowy ● Metoda SA wprowadza dodatkowy parametr – temperaturę (T). ● Stopniowe obniżanie T „zamraża” układ. 3.7. Proszę krótko opisać zasadę działania algorytmu „Ant colony”. Algorytm oparty na obserwacji kolonii mrówek. Mrówki losowo poszukują pożywienia. Mrówka, która pierwsza znalazła pożywienie, wraca do mrowiska pozostawiając po sobie ślad w postaci feromonów. Inne mrówki podążają pozostawionym śladem do znalezionego wcześniej pożywienia. Każda kolejna mrówka podążająca tym śladem wzmacnia go ponieważ pozostawione ślady bez wzmocnienia zanikają. 3.8. Proszę krótko opisać zasadę działania algorytmu „Particle swarm”. Ogólna rodzina algorytmów oparta o tzw. Swarm intelligence”. System złożony z osobników i interakcji zachodzących między nimi. Osobniki poszukują przestrzeni rozwiązań w celu znalezienia rozwiązań optymalnych. Koncepcja inspirowana zachowaniem stada ptaków lub ławicy ryb. Metoda dobrze radzi sobie z optymalizacją kosztowych funkcji w obecności wielu minimów lokalnych. 3.9 Proszę krótko opisać problem „podróżującego sprzedawcy” (TSP). *Klasyczny problem optymalizacji kombinatorycznej. *Sprzedawca ma odwiedzić N map rozrzuconych na mapie tak, aby każde miasto odwiedzić tylko raz i odbyć jak najkrótsza drogę. *Jak znaleźć najlepsze rozwiązanie? 4.1. Proszę krótko opisać zasadę działania algorytmu genetycznego. *Inicjujemy pewną początkową populację osobników *Podajemy każdego z nich ocenie *Wybieramy z populacji osobniki najlepiej do tego przystosowane *Za pomocą operacji genetycznych ( krzyżowanie oraz mutacja ) tworzymy nowe pokolenie. 4.2.Na czym polega dobór według „reguły ruletki”? Na kole ruletki przydzielono sektory proporcjonalne do wartości przystosowania. Większa wartość przystosowanie równa się częstszemu wyborowi do populacji rodzicielskiej. Lepiej przystosowana populacja może być wybierana wielokrotnie. Skutkiem będzie zajmowanie miejsc słabszej populacji przez populacji mocniejszej. 4.3. Co to jest krzyżowanie? Proszę podać przykłady. Krzyżowanie proste – cross-over – Osobniki z puli rodzicielskiej dobierane są w pary – Dla każdej pary wybierana jest pozycja przecięcia – Fragmenty ciągów kodowych osobników są zamieniane – tworzą się dwa nowe osobniki. Np. 1010 | 1101  1010 | 0101 1100 | 0101  1100 | 1101 4.4. Proszę podać i krótko scharakteryzować dwie różne metody selekcji. *Wybór deterministyczny Każdy osobnik otrzymuje tyle kopii ile wynika z jego prawdopodobieństwa reprodukcji *Wybór losowy wg resztJ.w. ale w przypadku części ułamkowej prawdopodobieństw używana jest metoda ruletki *Turnieje losowe Po obliczeniu prawdopodobieństwa reprodukcji następuje losowanie par. Zwycięzca zostaje wybrany 4.5. Proszę krótko wyjaśnić mechanizm dominacji genów. Mechanizm dominacji genów to mechanizm służący do wyboru między dwoma allelami tzn. Że jeden za alleli ( zwany dominującym ) zajmujący ten sam locus ( pozycję ) ma pierwszeństwo przed odmianą alternatywną ( allelem recesywnym ). 4.6. Podać przykłady trzech różnych operatorów genetycznych. Opisać ich działanie. Krzyżowanie - Jest łączenie osobników w pary. Dla każdej pary wybierana jest pozycja przecięcia. Fragmenty ciągów kodowych osobników są zamieniane w ten sposób tworzą się dwa nowe osobniki. Mutacja – Losowa zamiana pojedynczego bitu w ciągu kodowanym. Mutacja ma znaczenie drugorzędne – częstość rzędu 0.01%. Odpowiada błądzeniu przypadkowemu. Może pomóc w uniknięciu pułapki lokalnego minimum i wprowadzić nowe schematy do populacji. Inwersja – polega na odwróceniu fragmentu ciągu kodowego ma zastosowanie w przypadku gdy funkcja alleli nie zależy od ich położenia. Zmienia sposób kodowania informacji wpływając na poprawienie jakości schematów. 4.7. Co oznacza pojęcie specjacji gatunku? Proces gatunkotwórczy, zasadniczy, powszechny proces w ewolucji organizmów, prowadzący do powstania nowych gatunków z gatunków wcześniej ukształtowanych. 4.8. Proszę wyjaśnić efektywność działania algorytmu genetycznego za pomocą pojęcia schematu i hipotezy cegiełek. Brak odp. 5.1. Co to jest system informacyjny? Jak się go opisuje? System informacyjny SI zdefiniowany jest jako dwójka: SI = (U,A) gdzie U jest niepustym, skończonym zbiorem obiektów, A jest niepustym, skończonym zbiorem atrybutów. 5.2. Co to jest górna i dolna aproksymacja zbioru przybliżonego? *dolna a. zbioru X – zbiór elementów, o których można z całą pewnością powiedzieć, że są elementami zbioru X.Obiekt x jest elementem dolnej aproksymacji X jeżeli cała klasa abstrakcji, do której należy, jest podzbiorem X. *górna a. zbioru X – zbiór elementów, o których nie można z całą pewnością powiedzieć, że nie są elementami zbioru X.Obiekt x jest elementem górnej aproksymacji X jeżeli cała klasa abstrakcji, do której należy, ma niepustą część wspólną ze zbiorem X. 5.3. Co to jest pozytywny, negatywny i brzegowy obszar zbioru rozmytego? Pozytywny obszar zbioru X jest tożsamy z jego dolną aproksymacją. Brzegowy obszar zbioru X to różnica zbiorów będących górną i dolną aproksymacją zbioru X.Negatywny obszar zbioru X to zbiór obiektów x należących do U które z całą pewnością nie należą do zbioru X. 5.4. Co to jest zbiór niedefiniowalny? Proszę wymienić rodzaje. Zbiór niedefiniowalny jest to zbiór którego nie można scharakteryzować przez własności jego elementów. Taki zbiór nazywany jest jako zbiór przybliżony. Dlatego w teorii zbiorów przybliżone zostały wprowadzone pojęcia dolnego i górnego przybliżenia zbioru, które pozwalają zbiór niedefiniowalny scharakteryzować za pomocą dwóch zbiorów definiowalnych – jego dolnego i górnego przybliżenia. Rodzaje zbiorów niedefiniowalnych : *zbiór w przybliżeniu definiowalny *zbiór wewnętrznie niedefiniowalny *zbiór zewnętrznie niedefiniowalny *zbiór całkowicie niedefiniowalny 5.5. Co to jest dokładność aproksymacji zbioru przybliżonego? Dokładność aproksymacji = liczba elementów należących do dolnej aproksymacji przez liczbę elementów należy do górnej aproksymacji. 5.6. Czym różnią się deterministyczne i niedeterministyczne reguły tablicy decyzyjnej? Reguła w tablicy decyzyjnej TD jest deterministyczna, gdy równość atrybutów warunkowych implikuje równość atrybutów decyzyjnych. W przeciwnym wypadku reguły określa się jako reguły niedeterministyczne. Reguła w tablicy decyzyjnej TD jest niedeterministyczna, gdy równość atrybutów warunkowych nie implikuje równości atrybutów decyzyjnych 5.7. Co oznacza określenie, że tablica decyzyjna jest źle określona? Oznacza to, że tablica zawiera reguły niedeterministyczne. 5.8. Proszę podać dwa sposoby poprawienia źle określonej tablicy decyzyjnej. Źle określoną tablicę decyzyjną można naprawić poprzez: – Usunięcie reguł niedeterministycznych – Rozszerzenie zbiorów atrybutów warunkowych. 5.9. Co to jest redukt zbioru przybliżonego? Redukty to minimalne podzbiory atrybutów zachowujących charakterystykę całego zbioru atrybutów. W teorii zbiorów przybliżonych, istnieją co najmniej 2 pojęcia reduktów: informacyjne i decyzyjne. 5.10. Co to jest rdzeń zbioru przybliżonego? Zbiór wszystkich atrybutów nieusuwalnych ze zbioru P nazywa się rdzeniem P 6.1.krótko opisać różnicę między zbiorem klasycznym a rozmytym. Zbiór rozmyty to obiekt matematyczny ze zdefiniowaną funkcją przynależności, która przybiera wartości z ciągłego przedziału <0, 1>. Natomiast przeciwdziedzina funkcji przynależności klasycznego zbioru ma jedynie dwie wartości {0,1}. 6.2. Co to jest funkcja przynależności zbioru rozmytego? Proszę podać 3 przykłady. zwana też funkcją charakterystyczną zbioru rozmytego), która przybiera wartości z przedziału [0, 1]. Wartość funkcji przynależności – określa stopień przynależności elementu x do zbioru rozmytego A. Typy funkcji przynależności: *Singleton *Funkcja Gaussa *Funkcja typu dzwonowego *Funkcja klasy s 6.3. Proszę wyjaśnić pojęcia bazy i jądra zbioru rozmytego. Baza – zbiór elementów przestrzeni X dla których mA(x)>0 supp A = { xÎX;mA(x)>0} Jądro zbioru rozmytego – zbiór elementów przestrzeni X dla których mA(x)=1 core A = { xÎX;mA(x)=1} 6.4. Co to jest alfa przekrój zbioru rozmytego? Jako przekrój alfa zbioru rozmytego rozumiemy przedział wartości zbioru rozmytego A który zawiera w sobie wszystkie wartości tego zbioru dla których funkcja przynależności m ma wartość większą bądź równą alfa. 6.5. Co to jest liczba rozmyta? Jakie warunki musi spełniać? Są to zbiory rozmyte zdefiniowane na osi liczb rzeczywistych. Dodatkowo są normalne, wypukłe, funkcja przynależności jest przedziałami ciągła. 6.6.Co to jest liczba rozmyta typu LP? Podać definicję. Liczba rozmyta AÍR jest liczbą rozmytą typu L-P wtedy i tylko wtedy , gdy jej funkcja przynależności ma postać L(m-x/alfa) jeżeli x £ m mA(x) = klamra P(x-m/beta) jeżeli x ³ m Gdzie: m – liczba rzeczywista zwana wartością liczby rozmytej A(mA(m)=1) a – liczba rzeczywista dodatnia zwana rozrzutem lewostronnym b – liczba rzeczywista dodatnia zwana rozrzutem prawostronnym natomiast L i P są funkcjami odwzorowującymi (¥,¥)®[0,1] oraz spełniającymi warunki : L(-x)=L(x),P(-x)=P(x), L(0)=I,P(0)=i, L i P są funkcjami nierosnącymi w przedziale [0,+¥] 6.7. Proszę podać definicję płaskiej liczby rozmytej typu LP. Płaska liczba rozmyta definiuje przedział rozmyty, jej definicja jest następująca: 𝑚1 − 𝑥 ) , 𝑗𝑒ż𝑒𝑙𝑖 𝑥 ≤ 𝑚1 , 𝐿(  A (x) = { 1, 𝑗𝑒ż𝑒𝑙𝑖 𝑚1 ≤ 𝑥 ≤ 𝑚2 𝐿( 𝑥 − 𝑚2  ) , 𝑗𝑒ż𝑒𝑙𝑖 𝑥 ≥ 𝑚2 , Płaską liczbą rozmytą typu L-P nazywamy liczbę rozmytą o funkcji przynależności L(m-x/alfa) jeżeli x £ m1 mA(x) = klamra 1 jeżeli m1 £ x £ m2 P(x-m/beta) jeżeli x ³ m2 6.8. Co to jest trójkątna liczba rozmyta? Liczba rozmyta dla której funkcja przynależności opisywana jest funkcją klasy t. A=(a1, AM, a2) Trójkątna liczba rozmyta to liczba dla której funkcja przynależności opisywana jest funkcją klasy t.A=(a1, am, a2). 6.9. Proszę podać przykład wnioskowania modus ponens i modus tollens. Modus ponens Modus tolens Przesłanka: A Implikacja: jeśli A to B Wniosek: B Przesłanka: nie (B) Implikacja: jeśli A to B Wniosek: nie (A) 6.10. Co to jest zmienna lingwistyczna? Zmienna, której wartościami są słowa lub zdania języka naturalnego: np. „mały”, „średni”, „umiarkowanie wysoki” itd. ● Wartościom zmiennych lingwistycznych można przyporządkować odpowiadające zbiory rozmyte ● Zmienna lingwistyczna może również przyjmować wartości liczbowe. 6.11. Proszę krótko opisać elementy sterownika rozmytego. Baza reguł – nazywana czasami modelem lingwistycznym, stanowi zbiór rozmytych reguł Blok rozmywania – konkretna wartość Blok wnioskowania – zakładamy, że na wejściu bloku mamy zbiór rozmyty Blok wyostrzania – wielkością bloku wnioskowania jest bądź N zbiorów rozmytych, bądź jeden zbiór rozmyty. 7.1. Proszę krótko opisać budowę naturalnego neuronu. Neuron podstawowy element układu nerwowego *Ciało komórki (soma) zawierające jądro komórkowe – element „obliczeniowy” neuronu *Dendryty - „drzewiaste” wypustki odbierające sygnały od innych komórek. *Akson – przekazuje informację z ciała komórki do innych neuronów lub komórek efektorowych (mięśniowe, gruczołowe). *Synapsa – miejsce komunikacji między aksonem neuronu a błoną komórkową drugiej komórki. 7.2. Proszę krótko scharakteryzować podstawowe założenia modelu neuronu MCP. Model neuronu MCP – prosty model umożliwiający realizację układów logicznych Założenia: – Aktywność neuronu jest oparta na zasadzie „wszystko albo nic” (tzn. binarna) – Do wzbudzenia neuronu potrzebna jest pewna liczba wzbudzeń na synapsach (>1) – Neuron nie wprowadza opóźnień (poza naturalnym propagacja sygnału) – Aktywność synapsy hamującej blokuje aktywność neuronu – Struktura połączeń neuronów jest stała 7.3. Proszę krótko opisać zasadę działania sztucznego neuronu. Na wejściu neuronu podawane są sygnały wejściowe, zostają one przemnożone przez odpowiadające im wagi a następnie zsumowane, uzyskana wartość nosi nazwę potencjału membranowego. Potencjał membranowy podawany jest na funkcje atywacji ( jest jej argumentem ) i w ten sposób wyliczane jest wyjcie neuronu. 7.4. Proszę podać 3 przykładowe funkcje aktywacji. Proszę naszkicować wykresy funkcje aktywacji: ● bipolarna f(x)=-1, dla x<0 f(x)=1, dla x>=0 ● niesymetryczna liniowa z nasyceniem f(x)=0, dla x<0 f(x)=x, dla 0<=x<=1 f(x)=1, dla x>1 ● symetryczna liniowa z nasyceniem f(x)=-1, dla x<0 f(x)=x, dla 0<=x<=1 f(x)=1, dla x>1 ● logarytmiczno-sigmoidalna f(x)=1/(1+e-x) ● tangens hiperboliczny f(x)=(ex-e-x)/(ex+e-x) 7.5. Na czym polega uczenie neuronu w wersji nadzorowanej? Metoda uczenia nadzorowanego – Na wejściu podaje się sygnał, dla którego znamy prawidłową odpowiedź – Modyfikujemy wagi tak, aby zminimalizować błąd między wyjściem a sygnałem wzorcowym – Czynność powtarzamy dla kolejnych sygnałów wzorcowych (ciąg uczący) 7.6. Czym różni się model neuronu ADALINE od modelu Perceptronu? Model ADALINE od modelu Perceptronu różni się sposobem uczenia. Do uczenia wykorzystuje się nie sygnał wyjściowy ale sygnał z sumatora. Dzięki temu funkcja jest różniczkowalna i można zastosować jeden z wielu algorytmów optymalizacji. 7.7. Co to jest neuron sigmoidalny? Jakie ma zalety w stosunku do Perceptronu? Neuron sigmoidalny jako funkcję aktywacji stosuje funkcję sigmoidalną unipolarną lub bipolarną Zalety stosowania sigmoidalnej funkcji aktywacji *Funkcja jest ciągła. W procesie uczenia można wykorzystać sygnał wyjściowy a nie sygnał z sumatora (net) *Pochodne są łatwe do wyznaczenia. Można stosować efektywne algorytmy uczenia sieci. 7.8. czym polega reguła Hebba? Jak można ją wykorzystać do procesu uczenia neuronu? Badania nad działaniem komórek nerwowych ● Hebb zauważył, że połączenie między komórkami jest wzmacniane, jeżeli obie są w tym samym czasie aktywne. ● Zgodnie z tą obserwacją można wprowadzić model uczenia, w którym wzmocnienie wag jest proporcjonalne do wejść i wyjścia neuronu. ● Specyfika tego modelu polega na metodzie uczenia opartej o regułę Hebba ● W przypadku jednego neuronu polega ona na wzmacnianiu wagi wi proporcjonalnie do sygnału wyjściowego i sygnału wejściowego xi ● Uczenie może być realizowane bez nadzoru i z nadzorem. 8.1. Co to jest jednokierunkowa wielowarstwowa sieć neuronowa? Sieć składająca się z przynajmniej dwóch warstw neuronów- wejściowej i wyjściowej, oraz pewnej liczby warstw ukrytych. Połączenia tworzone są tylko między neuronami kolejnych warstw. Sygnały przekazywane są tylko w jednym kierunku tzn, do kolejnej warstwy 8.2. Co oznacza „efekt szczytu” w przypadku projektowania sieci neuronowej? Dodawanie neuronów do warstw ukrytych początkowo zmniejsza błąd dla zbioru testowego, później go zwiększa 8.3. Co to jest sieć MADALINE? Do czego się ją wykorzystuje? Sieć MADALINE jest to warstwa ukryta neuronów typu ADELINE. Sieć ta chętnie jest stosowana w filtrach adaptacyjnych(np. eliminacja efektu echa w liniach telefonicznych ). 8.4. Co to jest rekurencyjna sieć neuronowa? Proszę podać przykłady. W sieci rekurencyjnej sygnał z wyjścia trafia ponownie na wejście – występuje sprzężenie zwrotne. W sieciach takich może występować wiele zjawisk – tłumienia, oscylacje, chaos deterministyczny itp. Sieci rekurencyjne mogą być stosowane jako pamięci asocjacyjne. Przykłady sieci rekurencyjnych: – Sieć Hopfielda – Sieć Hamminga – RTRN – Sieć Elmana – Sieć BAM 8.5. Proszę krótko scharakteryzować budowę sieci Hopfielda. Jest to sieć jednowarstwowa, neurony połączone są każdy z każdym. Symetryczne wagi, brak sprzężenia w ramach jednego neuronu. Sygnał wielokrotnie przechodzi przez sieć aż do ustabilizowania odpowiedzi. Można wykazać, że sieć zawsze osiągnie jakieś minimum. 8.6. Do czego można zastosować sieć BAM? Sieć BAM umożliwia zakodowanie zbiorów 2 wektorów wzajemnie stowarzyszonych. Można ją zastosować w : *systemach obrony przeciw lotniczej *w zapytaniach do baz danych 8.7. Co oznacza pojęcie samoorganizującej się sieci neuronowej? Sieci samoorganizujące się wykorzystują algorytmy uczenia bez nauczyciela (bez nadzoru). W uczeniu bez nadzoru ciąg uczący to jedynie wartości wejściowe – bez sygnału wyjściowego 8.8.Czym różni się proces uczenia sieci typu WTA od sieci WTM? Różnica polega na korekcie wag, w sieci typu WTA polega na modyfikacji wag zwycięzcy natomiast w sieci WTM korekta wag dotyczy nie tylko zwycięzcy, ale również i sąsiednich neurownów 8.9.Do czego stosuje się sieci Kohonena? Proszę krótko opisać zasadę. Stosowana jest do kompresji obrazów. Obraz dzieli się na ramki – każda z nich stanowi wektor wejściowy. Każdej ramce odpowiada neuron „zwycięzca” a jego wagi określają parametry ramki (jasność punktów). Numery kolejnych neuronów „zwycięzców” stanowią zakodowany obraz. Sieć uczy się tak, aby zminimalizować błąd kwantowania. Górne obrazy to obraz oryginalny i obraz odtworzony, zastosowane do uczenia sieci. Obrazy dolne wykorzystują nauczoną wcześniej sieć. 8.10. Do czego można zastosować sieć ART? Czym się ona charakteryzuje? Sieci oparte o Adaptacyjną Teorię Rezonansu. Stosowana do rozpoznawania obrazów binarnych. Klasyfikuje obrazy zgodnie z zapamiętanymi wzorcami (zależnie od ustawionej czułości). Potrafi również zapamiętać obraz jako nowy wzorzec jeżeli stopień podobieństwa do zapamiętanych wzorców jest zbyt mały. 8.11.Co to są sieci radialne? Proszę podać przykład funkcji radialnej. Sieć radialna jest odmianą iteracyjnej sztucznej sieci neuronowej. W radialnych sztucznych sieciach neuronowych odwzorowanie zbioru wejściowego w wyjściowy jest realizowane przez dopasowanie wielu pojedynczych funkcji aproksymujących do wartości zadanych, ważne jedynie w wąskim obszarze przestrzeni wielowymiarowej. Przykłady :*liniowa r(r)=r *sześcienna r(r)=r3 8.12.Proszę podać i krótko scharakteryzować trzy różne obszary zastosowań sieci neuronowych. Obszary zastosowań: ● Klasyfikacja – sieć uczy się rozpoznawać wzorce i na ich podstawie klasyfikować wektory wejściowe do różnych klas. Faza uczenia – sieć otrzymuje wektory wzorcowe i informacje o ich zaklasyfikowaniu. Faza odtwarzania – sieć otrzymuje wektory danych i klasyfikuje je do określonej klasy ● Predykcja – ocena zachowania systemu na podstawie jego historii. Faza uczenia – sieć otrzymuje zbiór danych określających zachowanie systemu w przeszłości. Faza odtwarzania – sieć przewiduje przyszłe zachowanie systemu. ● Sterowanie procesami dynamicznymi -Zwykle połączenie kilku funkcji. Sieć stanowi nieliniowy model procesu. Pozwala identyfikować podstawowe parametry procesu, śledzić zachowanie procesu. Sieć może również służyć jako neuroregulator. Przykład: sterowanie robotów. 9.1. Proszę wymienić charakterystyczne cechy paradygmatu programowania agentowego. Paradygmat programowania o dużym poziomie abstrakcji. Polega na tworzeniu systemów składających się z dużej liczby tzw. „agentów”. ● Programowanie agentowe – rozwinięcie podejścia obiektowego (agent jako obiekt, działania jako metody – komunikaty) ● Nacisk na wielozadaniowość i architektury rozproszone. ● Według prognoz programowanie agentowe zastąpi programowanie i projektowanie zorientowane obiektowo. 9.2. Proszę podać podstawowe podobieństwa i różnice między programowaniem obiektowym i agentowym. OOP – kolekcja obiektów przekazujących komunikaty. Mogą być one uruchomione w środowisku rozproszonym. OOP – System złożony z dopasowanych „klocków”. Poszczególne elementy wykonują określone zadania. Awaria „klocka” może prowadzić do uszkodzenia całego systemu. OOP – Zakłada określoną „strukturę” informacji. Praca z informacją niepewną wymaga dodatkowych działań ● AOP – kolekcja agentów mogących się ze sobą komunikować. W sposób naturalny działają one w środowisku rozproszonym. Reagują na zmiany środowiska. ● AOP – System złożony z grupy współpracujących elementów. Poszczególne czynności mogą być dublowane (weryfikacja, redundancja). Awaria elementu nie prowadzi do uszkodzenia całego systemu. ● AOP – Może korzystać z niestrukturalizowanych źródeł informacji (np. język naturalny). Dopuszcza niekompletność informacji lub jej przekłamania. 9.3. Co to jest agent racjonalny i agent wszechwiedzący? Agent racjonalny – decyzja podejmowana na bazie dostępnych (niekompletnych, niekoniecznie poprawnych) informacji Agent wszechwiedzący – dostęp do wszystkich danych określających które działanie jest najbardziej efektywne. – W realnych systemach założenie wszechwiedzy jest niemożliwe do spełnienia. 9.4. Jakie elementy składają się na charakterystykę agenta? Co oznacza skrót PAGE? Charakterystyka agenta – P – Percepts – Receptory, sygnały z otoczenia – A – Actions – Czynności dostępne dla agenta – G – Goals – Ocena efektywności agenta – E – Environment – Otoczenie agenta. 9.5. Proszę wymienić i krótko opisać dwa rodzaje agentów. Agent reaktywny z pamięcią Agent przechowuje wewnętrzny model otoczenia. Wewnętrzny stan agenta odzwierciedla historię sygnałów z otoczenia. Przykład – Obraz z przedniej kamery pojazdu. – Kolejne ramki wskazują na zbliżanie się pojazdu z przodu. – Konieczność zahamowania. Niektóre decyzje agenta nie mogą być podjęte tylko na podstawie wiedzy o aktualnym otoczeniu (np. którą drogę ma wybrać kierowca). Dodatkową informacją dostępną dla jest cel działania (może być odległy). Połączenie reaktywności z dążeniem do celu może wymagać skomplikowanego procesu decyzyjnego (szukanie rozwiązań, planowanie działań) Agent z funkcją użyteczności - Często dany cel może być osiągnięty na wiele sposobów (np. dojazd na określone miejsce) Funkcja użyteczności (utility) pozwala określić która z sekwencji działań jest najlepsza (najbardziej użyteczna) Wartość funkcji użyteczności dla danego stanu = stopień „zadowolenia” agenta 9.6. Co to jest agent reaktywny? Agent reaktywny (simple reflex agent) Prosty rodzaj agenta. Działanie agenta warunkowane aktualnym sygnałem z receptorów. Procedura decyzyjna oparta o zbiór reguł typu akcja-reakcja (if-then) Przykład: * Sygnał: Obraz z przedniej kamery samochodu *Reguła: Jeżeli pojazd z przodu hamuje to hamuj. Program agenta – czynności: *Interpretuj sygnał wejściowy jako stan * Dopasuj regułę do stanu *Wykonaj działanie wynikające z reguły Agent reaktywny jest prosty w implementacji ale ma ograniczone zastosowanie. 9.7. Podać i krótko opisać cztery różne własności środowiska agenta. ● Gra w szachy – dostępne, deterministyczne, nieepizodyczne, statyczne, dyskretne. ● Gra w szachy z zegarem – dostępne, deterministyczne, nieepizodyczne, semidynamiczne (upływ czasu), dyskretne. ● Gra w pokera – niedostępne, niedeterministyczne, nieepizodyczne, statyczne, dyskretne. ● Kierowca taksówki – niedostępne, niedeterministyczne, nieepizodyczne, dynamiczne, ciągłe. ● System diagnostyki medycznej – niedostępne, niedeterministyczne, nieepizodyczne, dynamiczne, ciągłe. ● Robot sortujący – niedostępne, niedeterministyczne, epizodyczne, dynamiczne, ciągłe 9.8. Podać przynajmniej trzy różne cechy środowiska agenta grającego w szachy. Dostępne, deterministyczne, nieepizodyczne, statyczne, dyskretne 9.9. Podać przynajmniej trzy różne cechy środowiska agenta grającego w pokera. Niedostępne, niedeterministyczne, nieepizodyczne, statyczne, dyskretne 10.1. Proszę krótko opisać różnicę między typem problemu jedno – i wielostanowego. Jednostanowy – Agent ma pełną informację o otoczeniu i rezultacie swoich działań. Wielostanowy – Agent nie ma pełnej informacji o stanie otoczenia. 10.2. Jakie są kryteria oceny rozwiązania znalezionego przez agenta? *Czy rozwiązanie zostało znalezione? *Jak dobre jest rozwiązanie? * Jaki był koszt jego znalezienia? 10.3. Proszę podać trzy przykłady praktycznych problemów, w których występuje problem przeszukiwania. Problemy o znaczeniu praktycznym: *Problem wyznaczania trasy (routing) * Problemy logistyczne (problemy typu TSP) * Programowanie układów scalonych *Sterowanie robotami 10.4. Proszę podać i krótko scharakteryzować 3 różne strategie poszukiwania rozwiązań. ● Poszukiwanie wszerz Algorytm: Odwiedzamy wszystkie węzły połączone z początkowym. Później odwiedzamy wszystkie węzły połączone z tymi węzłami itd. Duża złożoność pamięciowa – konieczność przechowywania wszystkich odwiedzonych węzłów. Złożoność czasowa – proporcjonalna do liczby węzłów i gałęzi. Gwarantuje znalezienie rozwiązania. ● Strategia iteracyjnego pogłębiania Algorytm: Rozwinięcie algorytmu poszukiwania w głąb z ograniczeniem. Jako ograniczenie wybierane są kolejno wartości 0, 1, 2, itd... Łączy zalety poszukiwania wszerz i w głąb. Dodatkowy narzut w wyniku wielokrotnego przeglądania węzłów nie jest duży ze względu na specyfikę drzewa (większość węzłów jest na jego dole). ● Szukanie dwukierunkowe Szukanie dwukierunkowe polega na jednoczesnym rozpoczęciu poszukiwania z punktu początkowego i końcowego (celu). Wymaga określenia węzłów poprzedzających dany węzeł, odwracalności działań, oraz sprawdzania czy znaleziony został punkt „spotkania”. 10.5. Proszę porównać wady i zalety strategii poszukiwania w głąb i wszerz. ● Poszukiwanie wszerz Algorytm: Odwiedzamy wszystkie węzły połączone z początkowym. Później odwiedzamy wszystkie węzły połączone z tymi węzłami itd. Duża złożoność pamięciowa – konieczność przechowywania wszystkich odwiedzonych węzłów. Złożoność czasowa – proporcjonalna do liczby węzłów i gałęzi. Gwarantuje znalezienie rozwiązania. ● Poszukiwanie w głąb Algorytm: Z węzła początkowego wybieramy jedną gałąź i odwiedzamy położony na niej węzeł. W ten sposób dochodzimy do samego dołu drzewa. Cofamy się do poprzedniego poziomu i wybieramy kolejną gałąź. Złożoność pamięciowa – mała gdyż przechowujemy tylko aktualną ścieżkę. Złożoność czasowa – proporcjonalna do liczby węzłów i gałęzi. Gwarantuje znalezienie rozwiązania tylko dla drzew skończonych. 10.6. Na czym polega strategia poszukiwania poprzez iteracyjne pogłębianie? Algorytm: Rozwinięcie algorytmu poszukiwania w głąb z ograniczeniem. Jako ograniczenie wybierane są kolejno wartości 0, 1, 2, itd... Łączy zalety poszukiwania wszerz i w głąb. Dodatkowy narzut w wyniku wielokrotnego przeglądania węzłów nie jest duży ze względu na specyfikę drzewa (większość węzłów jest na jego dole). 10.7. Co to są heurystyczne metody poszukiwania? Poszukiwanie oparte na wiedzy Metody stosowane, gdy dostępne są dodatkowe informacje pozwalające ocenić stany. Przykład: Podróżując z miasta A do B wybieramy miasta zgodnie z określonym kierunkiem geograficznym. Metody wykorzystują tzw. funkcje heurystyczne. 10.8.Proszę krótko opisać strategię minimaksu stosowaną w teorii gier. Każdy węzeł drzewa gry ma przypisaną ocenę szansy wygranej gry.Poszukiwanie: *Ruch gracza – wybór maksymalizujący szansę wygrania gry *Ruch przeciwnika – wybór minimalizujący szansę wygrania gry 10.9.Proszę podać trzy różne zastosowania systemów wieloagentowych. – W wielu sytuacjach efektywność agentów można zwiększyć łącząc je w grupy. – Grupa współdziałających agentów – system wieloagentowy (multi-agent system – MAS) – Efekt współdziałania agentów opiera się na ich wzajemnej komunikacji 11.1. Co oznacza w teorii gier pojęcie „gracza racjonalnego”? Modele teorii gier zakładają że gracz zachowuje się racjonalnie, tzn. – Gracz zna zasady gry i reguły wypłat (w granicach określonych przez grę) – Gracz jest w stanie określić który z wyników jest lepszy – Gracz zdaje sobie sprawę że inni gracze też są racjonalni i potrafi określić strategie jakie mogą wybrać Przykład „nieracjonalnego gracza” – przypadki losowe. 11.2.Proszę podać i krótko opisać trzy przykładowe kryteria klasyfikacji gier. ● Liczba graczy --Gry dwuosobowe – Gry wieloosobowe (N-osobowe) – Przypadek szczególny – gry jednoosobowe ● Suma wypłat – Gra o stałej sumie wypłat – wypadek szczególny, gra o sumie zerowej –Gra o zmiennej sumie wypłat (ekonomia) *Moment podejmowania decyzji – Gra symultaniczna – gracze podejmują decyzję jednocześnie. – Gracze podejmują decyzję kolejno. 11.3. Co to jest gra strategiczna? ● W grze uczestniczy N graczy. ● Każdy z graczy może podjąć określoną decyzję ● Decyzje podejmowane są jednorazowo ● Decyzje graczy są jednoczesne ● Każda decyzja związana jest z określonym wynikiem. 11.4. Proszę podać przykład prostej gry i narysować macierz wypłat. Analiza gry – macierz wypłat Wiersze i kolumny – strategie każdego z graczy Komórki macierzy – wypłaty gracza zależnie od strategii wybranej przez niego oraz oponenta. Dla przykładu: – Gracze: Jaś,Małgosia – Strategie: Pokój, Kuchnia Macierz wypłat – Jaś J Pokój a Kuchnia ś Macierz wypłat – Małgosia Jaś Pokój Kuchnia Pokój C – Małgosia Kuchnia – C Pokój – C Małgosia Kuchnia C – 11.5. Co to jest strategia dominująca i strategia zdominowana w teorii gier? Strategia dominująca – strategia przynosząca graczowi najwyższą wypłatę niezależnie od zachowania drugiego gracza Strategia zdominowana – strategia dla której istnieje lepsza strategia niezależnie od strategii drugiego gracza 11.6. Co to jest równowaga Nasha w teorii gier? Strategie graczy tworzą równowagę graczy jeżeli maksymalizują wypłatę gracza przy danym wyborze drugiego gracza. Każdy z graczy dokonał wyboru maksymalizującego jego wypłatę. Żadnemu nie opłaca się odstępstwo. Gra może posiadać wiele równowag Nasha, lub nie mieć żadnej. 12.1 Na czym polega znany z teorii gier „dylemat więźnia”? Najbardziej znany przykład z teorii gier. Dwóch podejrzanych umieszczono w osobnych celach i przesłuchano. Jeżeli obaj się przyznają – otrzymają obniżoną karę, jeżeli jeden się przyzna to będzie wolny a drugi odbędzie karę, jeżeli żaden się nie przyzna to obaj otrzymają niewielką karę. 12.2. Co to jest „iterowany dylemat więźnia”? ● Wersja gry w której jest ona powtarzana wielokrotnie przez tych samych graczy ● Gracze ustalają strategię na bazie poprzednich wyników gry ● Przy skończonej liczbie tur optymalną dla gracza strategią jest zdrada ● W przypadku nieznanej liczby tur zaczyna się pojawiać współpraca ● W 1984 roku – turniej programów grających w iterowany dylemat więźnia ● Różne strategie – egoistyczne, altruistyczne 12.3. Co w teorii gier oznacza pojęcie „strategia mieszana”? ● Strategia mieszana domyślnie zakłada że gra będzie powtarzana (lub jest wiele „kopii” gry) – gdyż wprowadza do wyboru strategii prawdopodobieństwo. ● Strategia mieszana określa prawdopodobieństwa z jakimi gracz wybierze swoje strategie ● Można wykazać że dla każdej gry o sumie stałej istnieje optymalna strategia mieszana ● Wypłata w przypadku strategii mieszanej będzie sumą elementów określających prawdopodobieństwa wyborów określonych strategii graczy mnożonych przez odpowiedni element macierzy wypłat ● Strategia czysta – przypadek szczególny – jedna ze strategii ma prawdopodobieństwo 1, pozostałe – 0. 12.4. Proszę podać charakterystyczne cechy gry ekstensywnej o pełnej informacji. Charakterystyka gry – Zbiór sekwencji decyzji graczy – Gracze decydują po kolei – Gracze znają całą historię poprzednich decyzji Terminologia ● Historia – element zbioru sekwencji ● Akcja – pojedynczy element historii ● Gra skończona – skończony zbiór historii ● Skończona najdłuższa historia – gra ma skończony horyzont Pusta historia jest początkowym elementem gry Reprezentacja gry ● Wygodną reprezentacją gry ekstensywnej (pozycyjnej) jest drzewo. ● Wierzchołek drzewa reprezentuje początek gry ● Gałęzie reprezentują możliwe decyzje poszczególnych graczy ● Przy każdej pozycji końcowej umieszczone są wartości wypłaty 12.5. Proszę krótko opisać znaną z teorii gier „grę na wejście”. Gra na Wejście (Entry Game) – często stosowana w teorii gier. ● Założenia: – „rezydent” zajmuje pewną pozycję – „konkurent” chciałby ją zająć. ● Przykłady praktyczne – wejście firmy na rynek monopolisty – wybory na stanowiska (np. kierownicze) – walka o partnera/partnerkę ● Możliwości konkurenta: wejść do gry (I) lub z niej zrezygnować (R). ● Możliwości rezydenta jeżeli konkurent wszedł do gry: zrezygnować (R) lub walczyć (F). ● Możliwe historie: (R), (I,R), (I,F) ● Przykładowe wypłaty: – Rezydent: (R) - 2, (I,R) – 1, (I,F) – 0 – Konkurent: (R) – 1, (I,R) – 2, (I,F) – 0 12.6. Co w teorii gier oznacza pojęcie „strategii ewolucyjnej”? Jaka jest jej biologiczna analogia? ● Ekosystem jako zbiór osobników ● Osobniki wchodzą w interakcje między sobą ● Interakcje można rozpatrywać jako „gry” między osobnikami. ● Osobniki stosują w trakcie tych gier różne strategie. Pytanie: Które ze strategii są korzystne dla całej populacji? Przykład: zbiór osobników dwóch gatunków rywalizujących o zasoby. W sytuacji spotkania osobnik może zdecydować się na walkę lub ucieczkę (zachowanie Jastrzębia/Gołębia). Zachowanie osobnika będzie warunkowane macierzą wypłat – zyski i straty osobnika dla każdego zachowania. Z punktu widzenia ewolucji wypłata = liczba potomstwa. Potomstwo dziedziczy strategie wybrane przez rodziców. Różne strategie będą różnie ewoluowały w populacji. 12.7. Co oznacza pojęcie „strategia ewolucyjnie stabilna”? ● Załóżmy populację osobników stosujących określoną strategię. ● W populacji pojawia się grupa „mutantów” stosujących inną strategię. ● Strategia ewolucyjnie stabilna – „mutanci” nie uzyskają przewagi i nie zmieni się strategia większości. Zastosowania ● Badania zachowań zwierząt i ludzi. ● Badania zachowań „trudnych” do wyjaśnienia innymi teoriami – np. altruizm. ● Ekonomia, polityka – analiza decyzji ekonomicznych i politycznych. ● Badania nad ewolucją zachowań, wierzeń i informacji kulturowej (R. Dawkins, „Samolubny gen”)