1

OS.

Imię i nazwisko:

Grupa (prowadzący ćwicz.):

Czy poniższe zdania są prawdziwe?

Proszę zaznaczyć właściwą odpowiedź poprzez jej podkreślenie, obrysowanie lub przekreślenie. W razie wątpliwości proszę nic nie zaznaczać, gdyż odpowiedzi błędne będą punktowane ujemnie. W przypadku pomyłki proszę skreślić obie odpowiedzi i obok wyraźnie napisać właściwą.

1.	Problemy klasy P są rozwiązywalne za pomocą niedeterministycznej maszyny Turinga.	TAK	NIE
2.	W algorytmie wychładzania relacja sąsiedztwa rozwiązań nie powinna być spójna.	[TAK	Inie]
3.	Gdyby wielowarstwowa sieć neuronowa była wyposażona w liniową funkcję aktywacji, można by ją zastąpić jedną warstwą neuronów.	TAK	[ŃlEj
4.	Niedeterministyczna maszyna Turinga nie potrafi rozwiązywać problemów NP-zupełnych w czasie wielomianowym.	[tak	NIE
5.	Metody grupowania (clustering) służą do obliczania gradientu w algorytmie wstecznej propagacji.	TAK	[Nlg
6.	Niedeterministyczna maszyna Turinga dopuszcza kilka różnych sposobów działania w tej samej sytuacji.	TAK	[nie]
7.	Nauka z nauczycielem nie polega na bezpośrednim ustalaniu wag przez użytkownika.	TAK	NIE
8.	Wybierając drogi losowo mamy szansę kiedyś znaleźć najkrótszą trasę w problemie komiwojażera.	TAK	NIE

9.    Na płaszczyźnie mamy dane następujące grupy punktów: a) (1,4), (2,5), (4,4), (5,1)

- b) (1,3), (2,2), (2,1)

Wskaż perceptron rozdzielający punkty z grupy a od punktów z grupy b (tzn. taki, który dla każdego punktu z grupy a daje odpowiedź 1, a z grupy b odpowiedź 0 lub odwrotnie), lub uzasadnić, dlaczego taki perceptron nie istnieje.

10.    Dany jest następujący problem:

„Dany jest plan budynku składającego się z licznych prostych korytarzy i prostych odcinków schodów, krzyżujących się pod różnymi kątami i tworzących prawdziwy wielopiętrowy labirynt. W każdym punkcie połączenia korytarzy lub schodów wisi pod sufitem kula z przyciemnionego szkła, w której można zamontować kamery. Szef ochrony budynku chciałby móc monitorować każdy odcinek korytarza i schodów, ale ma ograniczone zasoby pieniężne i nie stać go na umieszczenie kamer we wszystkich kulach. Zakładamy, że wystarczy umieścić jedną obrotową kamerę w kuli, by kontrolować wszystkie odcinki korytarza i schodów wychodzące z danego punktu. Jak szef ochrony powinien rozmieścić kamery, by zakupić ich jak najmniej?”

a)    Zaprojektuj algorytm zachłanny (wielomianowy) rozwiązujący powyższe zadanie.

b)    Podaj przykład konkretnej sytuacji, w której zaproponowany algorytm zachłanny da nieoptymalne rozwiązanie.