Teoretyczne Podstawy Informatyki Test # 2 a)

Imię i nazwisko . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.2007

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

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

a) decyzyjnym trudnym

b) optymalizacyjnym łatwym

c) decyzyjnym łatwym

3. MY 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ę

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

a) O(n!)

b) O(n)

c) O(aⁿ)

5. Liczba 1101 z zadania 4-ego jest:

a) daną wejściową

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

6. Dana jest całkowita liczba dodatnia. Sprawdzenie czy jest ona liczba pierwszą jest problemem:

a) decyzyjnym trudnym

b) decyzyjnym łatwym

c) optymalizacyjnym trudnym

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) zbiorem danych wejściowych

b) zbiorem danych wyjściowych

c) programem maszyny Turinga

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

a) na dwa sposoby

b) tylko na jeden sposób

c) na nieskończenie wiele sposobów

---