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

Teoretyczne Podstawy Informatyki - Egzamin - Termin III

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
Znajdowanie najkrótszej drogi w grafie o n wierzchołkach, którego połączenia są obciążone nieujemnymi wagami.
Kolorowanie grafu, zawierającego n wierzchołków, możliwie najmniejszą liczbą kolorów.
Sprawdzenie, czy dana liczba n jest liczbą pierwszą.

2. Scharakteryzuj krótko problemy należące do klas P i NP. Opisz podstawowe różnice między problemami należącymi do tych klas pod względem ich złożoności obliczeniowej. Podaj dwa przykłady problemów, które należą do klasy P i dwa przykłady problemów, które należą do klasy NP, a nie należą do klasy P.

3. Poniższy diagram przedstawia automat, działający nad alfabetem {a, b}. Wypisz najpierw kilka 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. Dana jest liczba naturalna n. 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 TAK? Podaj pełną specyfikację problemu, rozwiązywanego przez ten algorytm. Jaki to jest typ algorytmu?

begin

read(n);

k := random(n);

{Procedura random(n) generuje losową liczbę naturalną z przedziału 1 i n}

if k > 1 then begin

l := n div k;

if k*l = n then print(`TAK')

end

end.

1

2

WISZ Gorzów Wlkp., Teoretyczne podstawy informatyki, Egzamin III, MMS

+/-

b

b

a

a

---