PK_WE_Z Teoretyczne Podstawy Informatyki Egzamin

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

1. Dziedzina algorytmiczna to:

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

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

3. 
   dziedzina zmiennych decyzyjnych oraz stałych

2. Termem jest wyrażenie:

a) ∧(∨a,(¬b∨c)) Ÿ

b) ∧(∨ (a,(¬b∨c)),d)

3. 
   ∨((a,¬b), ∨a)

3. Wartością termu MAX{3,9,0} + MOD(11,13) jest:

a) 11 b) 9 c) 20

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

1. 
   y = 3(x + b) - 3c Ÿ

2. 
   y = 3(x + b - c)

3. 
   y = 3x + 3b - 3c

5. Algorytm sortowania zbioru n liczb naturalnych ma złożoność:

a) n-1

b) n²/2 + n/2 Ÿ

4. 
   n²/2 - n/2

6. 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₁ b,S₁,-1 b,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ę

7. Pytanie dotyczące liczby obiektów należy do klasy pytań:

a) relacyjnych

b) liczbowych

3. 
   numerycznych

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₃

9. W systemie informacyjnym z poprzedniego przykładu wartością termu

(b,u₁) → (b,u₁) jest :

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

10. W systemie informacyjnym z przykładu # 3 termem prostym jest:

a) (a,v₁)*(b,u₁)

b) (a,v₁)*(b,u₁)*(c,w₁)

c) (a,v₁)*(b,u₁)*(c,w₁) + (a,v₁)*(b,u₁)*(c,w₂)+... +(a,v₃)*(b,u₃)*(c,w₃)

---