Teoretyczne Podstawy Informatyki Test # 2 b)

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

1. MT opisana tabelą znajduje się w stanie S₀. Jej głowica czyta

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

S₀ 0,S₀,+1 1,S₀,+1 b,S₁,-1

Maszyna ta: S₁ b,S₁,-1 1,S_S,-1 b,S₀,+1

a) zatrzyma się na znaku „0”

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

c) nigdy nie zatrzyma się

2. Elementy tabeli MT z zadania 1-ego są: :

a) programem maszyny Turinga

b) zbiorem danych wyjściowych

c) zbiorem danych wejściowych

3. Dany jest n elementowy zbiór ocechowanych 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:

a) decyzyjny trudny

b) optymalizacyjny łatwy

c) decyzyjny łatwy

4. Problem wyznaczania NWW(m,n) jest problemem:

a) decyzyjnym trudnym

b) optymalizacyjnym łatwym

c) decyzyjnym łatwym

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

S₀ 0,S₀,+1 1,S₀,+1 b,S₁,+1

Maszyna ta: S₁ b,S₁,-1 1,S_S,-1 b,S₀,+1

a) zatrzyma się na znaku „0”

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

c) nigdy nie zatrzyma się

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

a) tylko na jeden sposób

b) na dwa sposoby

c) na nieskończenie wiele sposobów

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

1. wielomianową

2. wykładniczą

3. liniową

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

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

S₀ 0,S₀,+1 1,S₀,+1 b,S₁,-1

Maszyna ta: S₁ b,S₁,-1 1,S_S,-1 b,S₀,+1

a) zatrzyma się na znaku „0”

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

c) nigdy nie zatrzyma się

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:

a) decyzyjny trudny

b) optymalizacyjny łatwy

c) decyzyjny łatwy

---