Teoretyczne Podstawy Informatyki Test # 2 a)

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. Liczba 1101 z zadania 2-ego jest:

a) daną wejściową

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

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

a) O(n!)

b) O(n)

c) O(aⁿ)

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

a) decyzyjnym trudnym

b) decyzyjnym łatwym

c) optymalizacyjnym trudnym

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

10. 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ą

---