Teoretyczne Podstawy Informatyki „0”
Imię i nazwisko . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . data. . . . . . . .
1. Problem sprawdzania czy dana liczba naturalna jest liczba parzystą jest problemem:
a) decyzyjnym trudnym
b) optymalizacyjnym łatwym
c) decyzyjnym łatwym
2. MT opisana tabelą znajduje się w stanie S0. Jej głowica czyta najbardziej znaczącą cyfrę liczby 1101. 0 1 b
S0 0,S0,+1 1,S0,+1 b,SS,-1
Maszyna ta: S1 b,S1,-1 1,SS,-1 b,S0,+1
a) zatrzyma się na znaku „0”
b) zatrzyma się na najmniej znaczącej cyfrze liczby 1101
c) nigdy nie zatrzyma się
3. Liczba 1101 z zadania 2-ego jest:
a) daną wyjściową
b) daną wejściową c) programem maszyny Turinga
4. 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
5. 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
6. Pytanie dotyczące liczby obiektów należy do klasy pytań:
a) relacyjnych
b) liczbowych
c) numerycznych
7. Dany jest system informacyjny zadany tabelą. Term (a,v1)*(bu2)*(c,w1)
wyznacza zbiór elementarny:
x1 x2 x3 x4 x5 x6 x7 a) {x2}
a v1 v1 v1 v3 v1 v1 v2 b) ∅
b u2 u3 u3 u2 u3 u1 u1 c) {x2,x4}
c w3 w1 w1 w3 w3 w2 w3
8. W systemie informacyjnym z poprzedniego przykładu wartością termu
(b,u1) → (b,u1) jest :
a) 1 b) (x6,x7) c) 0
9. Który z poniższych algorytmów jest szybszy:
y = x2 x2 - ax2 + b x2
y = x2 (x2 - a + b)
y = x2x2 - x2 (a - b)
10. 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