Teoretyczne Podstawy Informatyki

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

1. Dany jest automat M zadany przez stan S₀ = 0 zbiór stanów końcowych:

	a b
0 1 2	0 1 0 2 2 2

F = {2} i funkcję przejścia zadaną tabelą. Automat ten rozpoznaje słowo:

a) aⁿ

b) aⁿ b aⁿ

c) aⁿ bⁿ

2. Problem wyboru najwyższego n osobowej druzyny harcerskiej ma
złożoność:

a) (n-1)!

b) 2ⁿ

c) (n-1)

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

złożoność:

a) (n-1)!

b) 2ⁿ

c) (n-1)

4. 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₃

5. Wartością termu (a,v₁)*(b,u₃)*(c,w₁) S z pk-tu 4 jest: a) {x₁,x­₂,x₃,x₅,x₆}

b) {x₂,x­₃} c) {x₂,x­₅}

6. System S z p-ktu 4 jest systemem:

a) selektywnym i niekompletnym

b) nie selektywnym i niekompletnym nie

c) selektywnm i kompletnym

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) 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 b pojawi się odpowiednio 1 i 0. Funkcja przełączająca ma postać:

1. 
   
   y₁ = a ∨ ¬b

2. y₁ = a ∧ b

3. 
   y₁ = a ∧ ¬b

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

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

b) każda informacja jest nie pusta

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

10 Funkcja przełączająca y₁ = (¬x₂ ∨ ¬x₁) ∧ (¬x₂ ∨ x₁ ) ∧ (x₂ ∨ ¬x₁) ∧ (x₂ ∨ x₁) jest postaci:

a) normalnej zupełnej sumy iloczynów

b) normalnej prostej regularnej

c) normalnej zupełnej iloczynu sum

---