G TPI Egz III 2003, 15


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: .........................................................

0x08 graphic
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.

0x08 graphic

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



Wyszukiwarka

Podobne podstrony:
G TPI Egz II 2003 - II rok, 15
G TPI Egz I 2003 - II rok, 15
egz+popr 2003 i 2004, III rok, Patofizjologia
harmonogram msu ea iii 2014 15 cus
III CZP 15 91 id 210268 Nieznany
Mela - egz. III, SGSP, SGSP, cz.1, fizykochemia splania, Fizykochemia spalania
egz sem2 2003 (2)
diagnostyka laboratoryjna- test egz, III rok, Diagnostyka laboratoryjna, Giełdy, diagno
Egz.Farma 2003, Giełdy z farmy
egz pop 2003 (2)
Ściąga na EGZ. 97-2003 do wysłania, studia rolnictwo, semestr 5
Mózgowie2002 2003 15 05
III Wykład 15 03 Oęwietlenie pojazdów
Mózgowie2002 2003 15 05

więcej podobnych podstron