Teoretyczne Podstawy Informatyki Test # 2 b)

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

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

a) decyzyjnym trudnym

b) optymalizacyjnym łatwym

c) decyzyjnym łatwym

2. 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_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ę

3. Liczba 1101 z zadania 2-ego jest:

a) daną wyjściową

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

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

a) O(n)

b) O(n!)

c) O(aⁿ)

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

a) 2ⁿ

b) n!

c) n²/2 - n/2

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

---