WSKiZ Teoretyczne Podstawy Informatyki #1 b)
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 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,S1,-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. Dowolny algorytm może być przedstawiony jako maszyna Turinga:
a) tylko na jeden sposób
b) na dwa sposoby
c) na nieskończenie wiele sposobów
4. Liczba 1101 z zadania 2-ego jest:
a) daną wejściową
b) daną wyjściową
c) programem maszyny Turinga
5. 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
7. Algorytm dla różnych wartości danej wymaga wykonania n2, 2n, 2n ma złożoność
obliczeniową:
wielomianową
wykładniczą
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,v1)*(bu3)*(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. Algorytm opisany schematem blokowym jest:
a) poprawny
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