WSKiZ TPI test+


Teoretyczne Podstawy Informatyki Test # 2 b)

Imię i nazwisko . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.2007

1. Problem sprawdzania czy dana liczba naturalna jest liczba parzystą jest problemem:

0x08 graphic
a) decyzyjnym trudnym

b) optymalizacyjnym łatwym

c) decyzyjnym łatwym

2. MT opisana tabelą znajduje się w stanie S0. Jej głowica czyta najbardziej znaczącą cyfrę liczby 1101. 0 1 b

S0 0,S0,+1 1,S0,+1 b,SS,-1

Maszyna ta: S1 b,S1,-1 1,SS,-1 b,S0,+1

0x08 graphic
a) zatrzyma się na znaku „0”

b) zatrzyma się na najmniej znaczącej cyfrze liczby 1101

c) nigdy nie zatrzyma się

3. Liczba 1101 z zadania 2-ego jest:

0x08 graphic
a) daną wyjściową

b) daną wejściową c) programem maszyny Turinga

0x08 graphic
4. Algorytm opisany MT z poprzedniego zadania ma zlozoność obliczeniową:

a) O(n)

b) O(n!)

c) O(an)

0x08 graphic
5. Problem sortowania ma złożoność:

a) 2n

b) n!

c) n2/2 - n/2

6. Dowolny algorytm może być przedstawiony jako maszyna Turinga:

0x08 graphic
a) tylko na jeden sposób

b) na dwa sposoby

c) na nieskończenie wiele sposobów

0x08 graphic
7. Algorytm dla różnych wartości danej wymaga wykonania n2, 2n, 2n ma złożonośc obliczeniową:

  1. wielomianową

  2. wykładniczą

  3. liniową

8. MT opisana tabelą znajduje się w stanie S0. Jej głowica czyta

najbardziej znaczącą cyfrę liczby 1101. 0 1 b

S0 0,S0,+1 1,S0,+1 b,S1,-1

Maszyna ta: S1 b,S1,-1 1,SS,-1 b,S0,+1

0x08 graphic
a) zatrzyma się na znaku „0”

b) zatrzyma się na najmniej znaczącej cyfrze liczby 1101

c) nigdy nie zatrzyma się

0x08 graphic
9. Elementy tabeli MT z zadania 8-ego są: :

a) programem maszyny Turinga

b) zbiorem danych wyjściowych

c) zbiorem danych wejściowych

10. Dany jest n elementowy zbiór nieocechowanych odwazników. Czy uda się je rozmieścic na tarkach wagi szalkowej, tak aby ta znalazła się w stanie równowagi? Problem ten jest:

0x08 graphic
a) decyzyjny trudny

b) optymalizacyjny łatwy

c) decyzyjny łatwy



Wyszukiwarka

Podobne podstrony:
WSKiZ TPI test*
WSKiZ TPI test 2
WSKiZ TPI test 2 08
WSKiZ TPI test+b
WSKiZ TPI test*a
WSKiZ TPI 0
PK TPI test* (2)
PK TPI test+ (2)
PK TPI test*
PK TPI test 2b
TPI, PK-WE M test 2, WSKiZ
TPI, WSKiZ test 2, WSKiZ
TPI, PK-WE M test, WSKiZ

więcej podobnych podstron