Teoretyczne Podstawy Informatyki Test # 2 (a)

Imię i nazwisko . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30.5.2008

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. Algorytm opisany MT z poprzedniego zadania ma złożoność obliczeniową:

a) n!

b) n^a

c) aⁿ

3. Liczba 1101 z zadania 4-ego jest:

a) daną wejściową

b) daną wyjściową

c) programem maszyny Turinga

4. Sprawdzenie czy dana całkowita liczba dodatnia jest liczbą pierwszą jest problemem:

a) decyzyjnym trudnym

b) decyzyjnym łatwym

c) optymalizacyjnym trudnym

5. Algorytm dla który dla różnych wartości danych wymaga wykonania n², 2ⁿ, 2n operacji ma złożoność obliczeniową:

1. wielomianową

2. wykładniczą

3. liniową

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

7. Dany algorytm: begin i:=1; while i≠u do i:=i+1 end przykładowe warunki są poprawne:

a) „u liczba całkowita”

b) „u = i”

c) „u>0”

8. Algorytm opisany schematem blokowym jest:

a) niedokonczony

b) niepoprawny

c) skończony

9. Wydrukowane zostanie:

a) 1 , 2, 3, 4, 5, 6, …

b) same spacje

c) 1 , 2, 3, 4, 5

10. Złożoność algorytmu opisuje funkcja:

a) wielomianowa

b) wykładnicza

c) typu MOD

Teoretyczne Podstawy Informatyki Test # 2 (b)

Imię i nazwisko . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30.5.2008

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_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. Algorytm opisany MT z poprzedniego zadania ma złożoność obliczeniową:

a) n!

b) n^a

c) aⁿ

3. Liczba 1101 z zadania 4-ego jest:

a) daną wyjściową

b) daną wejściową

c) programem maszyny Turinga

4. Sprawdzenie czy NWD(M,N) jest liczbą pierwszą jest problemem:

a) decyzyjnym trudnym

b) decyzyjnym łatwym

c) optymalizacyjnym trudnym

5. Algorytm dla który dla różnych wartości danych wymaga wykonania n², n⁸, 2n operacji ma złożoność obliczeniową:

a) wielomianową

2. wykładniczą

3. liniową

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

a) na dwa sposoby

b) na nieskończenie wiele sposobów

c) tylko na jeden sposób

7. Dany algorytm: begin i:=1; while i≠u do i:=i+1 end przykładowe warunki są poprawne:

a) „u liczba naturalna”

b) „u ≠ i”

c) „u>0”

8. Algorytm opisany schematem blokowym jest:

a) niedokonczony

b) niepoprawny

c) skończony

9. Wydrukowane zostanie:

a) 1 , 2, 3, 4, 5, 6, …

b) same spacje

c) 1 , 2, 3, 4, 5

10. Złożoność algorytmu opisuje funkcja:

a) wielomianowa

b) wykładnicza

c) typu MOD

i = n

T

i=i+1

Print i

T

MOD(i,6)>7

n=6; i=1

n=6; i=1

MOD(i,6)<7

T

Print i

i=i+1

T

i = n

---