WSKiZ Teoretyczne Podstawy Informatyki „0” a)

Imię i nazwisko . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . data. . . . . . . .

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

a) optymalizacyjnym łatwym

b) decyzyjnym trudnym

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₁,-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ę

	a b
0 1 2	0 1 0 2 2 2

3. Dany jest automat M zadany przez stan S₀ = 0 zbiór stanów końcowych: F = {2} i funkcję przejścia zadaną tabelą. Automat ten rozpoznaje słowo:

a) aⁿ

b) aⁿ b aⁿ

c) aⁿ bⁿ

4. Liczba 1101 z zadania 2-ego jest:

a) daną wejściową

b) daną wyjściową

c) programem maszyny Turinga

5. Dziedzina algorytmiczna to:

a) rodzina zbiorów obiektów, funkcji, relacji

b) rodzina zbiorów funkcji, operatorów i funktorów

c) dziedzina zmiennych decyzyjnych oraz stałych

6. Algorytm dla różnych wartości danej wymaga wykonania n², 2n, 2ⁿ ma złożoność

obliczeniową:

1. wielomianową

2. wykładniczą

3. typu silnia

7. System informacyjny selektywny to taki, w którym:

a) każda informacja jest nie pusta

b) każdej informacji odpowiada co najwyżej jeden obiekt

c) każdemu obiektowi odpowiada co najwyżej klika informacji

8. Dany jest system informacyjny zadany tabelą. Term (a,v₁)*(bu₃)*(c,w₁)
wyznacza zbiór elementarny:

x₁ x₂ x₃ x₄ x₅ x₆ x₇ a) {x₂}

a v₁ v₁ v₁ v₃ v₁ v₁ v₂ b) ∅

b u₂ u₃ u₃ u₂ u₃ u₁ u₁ c) {x₂,x₃}

c w₃ w₁ w₁ w₃ w₃ w₂ w₃

8. W systemie informacyjnym z poprzedniego przykładu wartością termu ¬
(b,u₁) → (b,u₁) jest :

a) 1 b) (x₆,x₇) c) 0

9. Algorytm opisany schematem blokowym jest:

a) niedokonczony

b) niepoprawny

c) skończony

10. Wydrukowane zostanie:

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

b) same spacje

c) 1 , 2, 3, 4, 5

T

T

i = n

MOD(i,6)>7

n=6; i=1

i=i+1

Print i

---