CZĘŚĆ TESTOWA

1. Suma I zmiennych w postaci prostej lub zanegowanej, spełniający następującą zależność: I=1 ⇒ F()=1 nazywamy
a	implikacją	c	implikantem
b	implicentem	d	pokryciem funkcji

2. A ∨ (A ∧x) = A ∨ (A ∧~x) = A oraz A ∧ (A ∨ x) = A ∧ (A ∨ ~x) = A opisują:
a	reguły pochłaniania	c	aksjomaty algebry Boole'a
b	operacje sklejania	d	prawa d'Morgana

3. W kodzie Grey'a dwa sąsiednie słowa kodowe:
a	są sąsiednie logicznie	c	różnią się o wartość 1
b	zawierają tą samą liczbę jedynek	d	różnią się o wartość 3

4. Wartość 1 1111111 w zapisie uzupełnienia do jeden oznacza:
a	- 1	c	-127
b	0	d	1

5. Wartość -19 w zapisie uzupełnienia do dwóch ma postać:
a	1 101101	c	1 101111
b	1 101100	d	1 010011

6. Metoda restytucyjna dotyczy metody:
a	Mnożenia	c	dodawania
b	Dzielenia	d	mnożenia w zapisie znak moduł

7. W kodzie dwójkowo-dziesiętnym liczba przedstawiana jest
a	za pomocą cyfr binarnych i dziesiętnych	c	częściowo binarnie i częściowo dziesiętnie
b	w postaci binarnej w grupach po 10 cyfr zapisanych binarnie	d	w grupach po 4 bity reprezentujących pozycje dziesiętne

8. Problemy decyzyjne są to problemy:
a	w których następuje ekstremalizacja funkcji celu.	c	na które można dać odpowiedź tak lub nie
b	w których podejmowana jest decyzja	d	które wiążą się z optymalizacją decyzji

9. Funkcja f(k) jest rzędu g(k), co zapisuje się O(g(k)), jeśli istnieje taka stała c, że
a	| f(k) | < c + | g(k) |, dla wszystkich wartości k	c	| f(k) | <= c + | g(k) |, dla wszystkich wartości k>0
b	| f(k) | <= c * | g(k) |, dla wszystkich wartości k>1	d	| f(k) | <= c * | g(k) |, dla wszystkich wartości k

10. Klasę P tworzą wszystkie problemy decyzyjne, które rozwiązuje deterministyczna maszyna Turinga
a	w co najmniej wielomianowym czasie	c	w co najmniej wykładniczym czasie
b	w co najwyżej wykładniczym czasie	d	w co najwyżej w wielomianowym czasie

11. Zbiór reguł umożliwiających generowanie słów danego języka, jak też rozróżnienie słów poprawnie zbudowanych od niepoprawnie zbudowanych to
a	syntaktyka	c	Gramatyka
b	semantyka	d	lingwistyka

12. Gramatyki prawostronnie regularne są gramatykami, w których wszystkie produkcje mają postać:
a	uXw ubw gdzie: u, w ∈ A* , X ∈ Σ b ∈ A* - {ε}	c	X bY gdzie: X ∈ Σ , Y ∈ Σ ∪ {ε} b ∈ A* - {ε}
b	X b, gdzie: X ∈ Σ , b ∈ A* - {ε}	d	X Yb gdzie: X ∈ Σ , Y ∈ Σ ∪ {ε} b ∈ A* - {ε}

13. Notacja umożliwiająca zapisanie dowolnego wyrażenia arytmetycznego bez użycia nawiasów zmieniających kolejność wykonywania działań, to:
a	notacja wyrażeń algebry Boole'a	c	notacja BNF
b	odwrotna notacja polska (ONP)	d	zmodyfikowana notacja BNF

14. Przekład tekstów zredagowanych w jednym języku źródłowym na równoważny semantycznie tekst w innym języku - wynikowym, to
a	kompilacja	c	konwersja
b	translacja	d	interpretacja

15. Jeżeli oznaczymy przez : Q - skończony zbiór stanów, - skończony alfabet symboli wejściowych, q0 należące do Q jest stanem początkowym od którego automat rozpoczyna działanie, F zbiór stanów końcowych, ð - funkcję przejścia , L zbiór słów języka, to automat skończony opisywany jest przez
a	< L, Q, , ð , F>	c	< Q, , ð , qo, F, L>
b	< Q, , ð , F>	d	< Q, , ð , qo, F>

16. Zaistnienie kilku przejść z określonego stanu przy tym samym symbolu wejściowym realizuje:
a	Deterministyczna maszyna Turinga	c	Niedeterministyczny automat skończony
b	Deterministyczny automat skończony	d	Niedeterministyczna maszyna Turinga

17. Słowo 010100110010101010 należy do zbioru reprezentowanego przez wyrażenie:
a	(0+01)^*(0+10)^*	c	(0+001)^*(0+010)^*
b	(0+01)^*001(0+01)^*	d	(0+1)^*0101(0)^*

18. Właściwością binarnego zapisu zmienno-przecinkowego liczby x wyrażonej dziesiętnie jest:
a	x = znak liczby * mantysa * 2 ^cecha(U2)	c	x = znak liczby * mantysa * 2 ^cecha(U1)
b	x = znak liczby * mantysa * 10 ^cecha(U2)	d	x = znak liczby * mantysa * 10 ^cecha(U1)

19. Suma J zmiennych w postaci prostej lub zanegowanej, spełniająca następującą zależność: J=0  F()=0 nazywamy
a	implikacją	c	implikantem
b	implicentem	d	pokryciem funkcji

20. x  (y  z) = (x  y)  (x  z) opisuje:
a	rozdzielność mnożenia względem dodawania	c	rozdzielność dodawania względem mnożenia
b	regułę sklejania	d	prawa d'Morgana

21. (A  ~ x)  (A  x) = A oraz ( A  ~ x)  (A  x) = A opisują:
a	operacje pochłaniania	c	reguły pochłaniania
b	prawa d'Morgana	d	reguły sklejania

22. Wartość w zapisie dwójkowo dziesiętnym 1001 0101 oznacza:
a	95	c	69
b	149	d	-108

23. Przesunięcie arytmetyczne w lewo liczby w zapisie uzupełnienia do 2 polega na wpisaniu:
a	na najstarszą pozycję bitu znaku	c	na najmłodszą pozycję zera
b	na najmłodszą pozycję bitu znaku	d	na najstarszą pozycję jedynki

24. W zapisie uzupełnienia do jeden dodawanie realizowane jest według reguły:
a	do modułu dodajnej dodać moduł uzupełnienia do jedności dodajnika; jeżeli wystąpi przeniesienie z najstarszej pozycji dodać je do sumy, a wynikowi nadać znak dodajnej;	c	do modułu dodajnej dodać moduł uzupełnienia do jedności dodajnika; jeżeli brak przeniesienia z najstarszej pozycji wyznaczyć uzupełnienie do jedności sumy, a wynikowi nadać znak nadajnika;
b	dodać liczby wraz z bitem znaku przeniesienie z najstarszej pozycji dodać do wyniku	d	dodać liczby wraz z bitem znaku, a ewentualne przeniesienie z najstarszej pozycji pominąć

25. Ustalając wartości wszystkich parametrów problemu Π otrzymamy:
a	instancję problemu	c	instalację problemu
b	realizację problemu	d	konkatencję

26. Gramatyki bezkontekstowe są gramatykami, w których wszystkie produkcje mają postać:
a		c
b		d

27. Maszyna RAM zawiera:
a	taśmy wejściową i wyjściową, licznik rozkazów, program i pamięć danych	c	taśmy wejściową i wyjściową, licznik rozkazów, układ sterowania i pamięć danych
b	licznik rozkazów, pamięć programu i pamięć danych	d	taśmy wejściową i wyjściową i układ sterowania

28. Niedeterministyczny automat skończony różni się od detereministycznego automatu skończonego:
a	nieskończoną liczbą stanów	c	nieskończoną liczbą kroków
b	niesprecyzowanymi warunkami przejścia między stanami	d	Istnieniem kilku przejść ze stanu przy tym samym symbolu wejściowym

29. Na podstawie stanu q i odczytanego znaku a Maszyna Turinga wykonuje:
a	Zmianę stanu i wpis nowego symbolu	c	Zmianę stanu i ruch głowicy w lewo lub w prawo
b	Zmianę stanu, wpis nowego symbolu i ruch głowicy w lewo lub w prawo	d	Wpis nowego symbolu i ruch głowicy w lewo lub w prawo

30. Przy przesuwaniu arytmetycznym liczb w zapisie uzupełnienia do 1:
a	wszystkie dodane cyfry są zerami	c	przy przesunięciu w lewo dodajemy zera, przy przesunięciu w prawo dodajemy cyfry odpowiadające bitowi znaku
b	wszystkie cyfry dodane odpowiadają bitowi znaku	d	wszystkie dodane cyfry są jedynkami

31. Właściwością zapisu zmienno-przecinkowego jest:
a	normalizacja mantysy	c	zgodność znaków mantysy i cechy
b	Oddzielenie znaku cechy od jej wartości bezwzględnej	d	Wartość cechy mniejsza lub równa 1

32. W zapisie ONP o kolejności wykonywanych operacji decyduje:
a	priorytet operatora	c	kolejność zadawanych argumentów
b	kolejność operatorów w zapisie od strony prawej	d	kolejność operatorów w zapisie od strony lewej

33. Wyrażenie jest równoważne
a		c
b		d

34. Iloczyn sum jest równoważny
a		c
b		d

35. Wartość - 23 w zapisie uzupełnienie do dwóch ma postać
a	0010111	c	1101000
b	1010111	d	1101001

36. Jeżeli liczby A i B w zapisie binarnym - uzupełnienie do dwóch A - 1011010 i B - 1001011
a	A>B	c	A i B są liczbami dodatnimi
b	A<B	d	A i B są liczbami o różnych znakach

37. Wartość - 1.75 w zapisie uzupełnienie do dwóch ma postać
a	11.11	c	01.11
b	10.00	d	10.01

38. Wyrażenie (a - b + c) * d zapisane w ONP ma postać
a	ab + c - d *	c	abc + - d *
b	ab - c + d *	d	abc - + d *

39. Słowo >>kaftan<< generowane jest wyrażeniem regularnym :
a	(a + f ) * ft(m + n + a) *	c	(a + f + k)* ft(m + n + a)*
b	( a + f + k) * tf(m + n + a)	d	(a + f + k)* ft(m + v + a)*

40. Słowo 00100100110100101001 należy do zbioru reprezentowanego przez wyrażenie
a	(0 + 01)* (0+010)*	c	(0 + 001)* (0+010)*
b	(0 + 01)*001 (0 + 01)*	d	(0 + 1)*011(0+1)*

41. Wyrażenie regularne (a + k + m)* t(i + o + w)* (c + i + k)*e generuje zbiór, do którego należy
a	matowe	c	kotwice
b	katowic	d	matwik

---