WISZ, Gorzów Wlkp., Rok akademicki 2002/2003. Prowadzący: M.M. Sysło

Teoretyczne Podstawy informatyki - Egzamin - Termin II

Czas na rozwiązanie: 90 min

Nazwisko i imię, numer indeksu: .........................................................

1. Uzupełnij następującą tabelę:

Problem	Dla 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 problemu
Badanie, czy dany element a należy do zbioru A (zbiór A ma n elementów).
Problem plecakowy
Kolorowanie grafu, zawierającego n wierzchołków

2. 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?

begin

read(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 do

for każdego j ∈ W do

if {i, j} ∉ E then b:=false;

if b then write(1) else write(0)

end.

1

2

WISZ Gorzów Wlkp., Teoretyczne podstawy informatyki, Egzamin II - dzienne, MMS

-

+

0

0

1

1

0, 1

0

1

---