Teoretyczne Podstawy Informatyki „0”

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

1. Termem jest wyrażenie:

a) (DIV(a,b), C)

b)  (MOD(a,b), C)

c) ((DIV(a,b), C))

2. Dany jest n elementowy zbiór nie ocechowanych odważników. Czy

uda się je rozmieścić 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

3. Który z poniższych algorytmów jest szybszy:

1. 
   y = x^2­ x² - ax² + b x² 

2. 
   y = x^2­ (x² - a + b)

3. 
   y = x⁴ - x² (a - b)

4. Problem wyboru „najlepszego” podzbioru zbioru n elementowego ma

złożoność:

a) (n-1)!

b) 2ⁿ

c) n²/2 - n/2

5. Dany jest system informacyjny S 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₃

6. Wartością termu (a,v₁)*(c,w₃) w S jest: a) {x₁,x­₂,x₃,x₅,x₆}

b) {x₁,x­₄,x₅,x₇} c) {x₁,x­}

7. MT opisana tabelą znajduje się w stanie S₀. Jej głowica czyta najbardziej znaczącą cyfrę liczby 1011. 0 1 b

S₀ 0,S₀,+1 1,S₀,+1 b,S₁,-1

S₁ 0,S₁,-1 1,S₁,-1 b,S₀,+1

Maszyna ta:

a) zatrzyma się na znaku „0”

b) zatrzyma się na najmniej znaczącej cyfrze liczby 1011 c) c) nigdy nie zatrzyma się

8. Dane są informacje z dwóch punktów a I b. Sygnalizowana ma być sytuacja

gdy na wejściach a i c pojawi się 1. Funkcja przełączająca ma postać:

1. 
   y₁ = a b

2. 
   y₁ = a b

3. 
   y₁ = a b

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

10 Funkcja przełączająca y₁ = (x₂  x₁)  (x₂  x₁ )  (x₂  x₁)  (x₂  x₁) jest postaci:

a) normalnej zupełnej sumy

b) normalnej prostej regularnej

c) normalnej zupełnej iloczynu

	a b
0 1 2	0 1 0 2 2 2

---