[ Pobierz całość w formacie PDF ]
.15WISZ, Gorzów Wlkp., Rok akademicki 2002/2003.Prowadzący: M.M.SysłoTeoretyczne Podstawy informatyki - Egzamin - Termin IICzas na rozwiązanie: 90 minNazwisko i imię, numer indeksu:.1.Uzupełnij następującą tabelę:ProblemDla podanego obok problemu, podaj w tej kolumnie znane ci algorytmy rozwiązywania (dokładne i przybliżone, jeśli takie istnieją) oraz określ ich złożoność obliczeniową jako zależność od rozmiaru problemuBadanie, czy dany element a należy do zbioru A (zbiór A ma n elementów).Problem plecakowyKolorowanie grafu, zawierającego n wierzchołków2.Rozważ dwa problemy, definiowane na grafach: (a) Czy dany graf zawiera cykl Eulera?; (b) Czy dany graf zawiera cykl Hamiltona? Porównaj te dwa problemy pod względem efektywności metod ich rozwiązywania.W tym celu m.in.podaj najlepsze algorytmy ich rozwiązywania wraz z ich efektywnością.Określ również klasę złożoności obliczeniowej tych dwóch problemów.3.Poniższy automat działa nad alfabetem {0, 1}.Wypisz najpierw 10 słów, które akceptuje ten automat, a następnie określ, jaki język on akceptuje, czyli jaki jest zbiór wszystkich słów akceptowanych przez ten automat.4.Dany jest graf G = (V, E) o n wierzchołkach Poniżej zapisano algorytm z użyciem symboliki wziętej z języka Pascal.Co jest wynikiem jego działania, czyli kiedy ten algorytm drukuje 0, a kiedy drukuje 1? Podaj pełną specyfikację problemu, rozwiązywanego przez ten algorytm.Jaki to jest typ algorytmu?beginread(k); {k jest parametrem działania tego programu}wylosuj k-elementowy podzbiór W ze zbioru wierzchołków V;b:=true;for każdego i ∈ W dofor każdego j ∈ W doif {i, j} ∉ E then b:=false;if b then write(1) else write(0)end.12WISZ Gorzów Wlkp., Teoretyczne podstawy informatyki, Egzamin II - dzienne, MMS-+110, 11
[ Pobierz całość w formacie PDF ]
