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