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

Teoretyczne Podstawy informatyki - Egzamin - Termin I

Czas na rozwiązanie: 90 min

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

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

Technika algorytmiczna	Przykład użycie techniki algorytmicznej podanej obok - wpisz algorytm (i problem), w którym została zrealizowana ta technika	Podaj złożoność algorytmu wymienionego w kratce po lewej stronie obok, jako zależność od rozmiaru problemu
Dziel i zwyciężaj
Podejście zachłanne
Programowanie dynamiczne
Przeszukiwanie z nawrotami

2. Scharakteryzuj krótko problemy należące do klas P i NP. W swojej charakterystyce uwypuklij różnice między tymi klasami. Podaj po 3 przykłady problemów, które należą do każdej z tych klas.

3. Poniższy automat działa nad alfabetem {0, 1}. 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. Dany jest graf G 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

{a jest tablicą a[1..n]}

a:=permutaja-losowa(n); {n jest liczbą wierzchołków w grafie G}

{powyższa instrukcja umieszcza w tablicy a losową permutację liczb 1, 2, ..., n}

b:=true; i:=1;

while (i < n) and b do begin

if {a[i],a[i+1]} nie jest krawędzią w grafie G then b:=false;

i:=i+1

end;

b:=b and ({a[n],a[1]} jest krawędzią w grafie G);

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

end.

1

2

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

-

+

+

0

0

1

1

0, 1

0, 1

0, 1