1 пєнініњ ОЌу программасы syllabus

• 
  Тұйық емес маршрут, бірақ шынжыр емес;
  
• 
  Қарапайым емес шынжар;
  
• 
  Қарапайым шынжыр;
  
• 
  Тұйық маршрут, бірақ цикл емес;
  
• 
  Қарапайым емес цикл;
  
• 
  Қарапайым цикл;
  

Бірінші төбеден шығатын ұзындығы 2-ге тең барлық маршруттарды және ұзындығы 2-ге тең маршрут

тың матрицасын табыңыз.

2.7. Өзің өзі тексеруге арналған тест тапсырмалары. 1. Берілген жиынтықтан эквивалентті формулаларды көрсетіңіз:

1)

2)

3)

4)

А) 1, 3 В) 3, 2 С) 2, 4 D) 1, 4 Е) 1, 2

2. Берілген тізбектерден тең жиындарды табыңыз.

1)

2) A

3) B

4) A-B

5)

А) 2, 4 В) 1, 2 С) 5, 2 D) 3, 4 Е) 1, 3, 5
3. Берілген Буль формуласын Жегалкин полиномы түрінде өрнектеңіз.

А) XY+YZ+XZ+Y

В) X+Y+Z+XYZ

С) X+Y+XZ+YZ

D) XY+XYZ+1(

Е) X+Y+XY+YZ+XZ+XYZ

4. Х={0,1,2,3,4,5} төбелер жиыны және осы G жиынындағы 2=<|x-y| <=4 қатынасымен берілген графтың цикломатикалық санын табыңыз:

1. 
   3 B) 4 C) 1 D) 2 E) 5
   

5. Төмендегі тұжырымдардың қайсылары ақиқат, қайсысы жалған ( айнымалылар мәні R нақты сандар жиынынан).

1)  x ( |x| 0)

2)  y (y²+y+1=0)

3)  x ( x³ < x² )

А) 1) ақиқат В) 1) жалған С) 1) ақиқат Д) 1) ақиқат Е) 1) жалған

2) ақиқат 2) ақиқат 2) жалған 2) жалған 2)жалған

3) жалған 3) жалған 3) жалған 3) ақиқат 3)ақиқат
6. Аталған жиындардың қайсылары саналымды?

А) Барлық иррационал сандар жиыны

В) Барлық бүтін сандар жиыны

С) [0;1] кесіндісінің нақты сандар жиыны

Д) [-10;10] кесіндісінің нақты сандар жиыны

Е) Жазықтықтың I ширегіндегі барлық нүктелер жиыны

7. Берілген Буль Функциялары жиынтығындағы өзіне-өзі түйіндестерін белгілеңіз:

1) X

2)

3)

4)

5)

А) 1, 2, 5 В) 2 С) 1 D) 1, 4 Е) 4, 5

8. Бос жиындарды көрсетіңіз:

1)

2)

3)

4)

5)

А) 2, 4 В) 1, 2, 4, 5 С) 3, 5 D) 2, 4 Е) 1

9. Берілген формулалардан мүлтіксіз дизъюнктивті қалыпты формадағыларын белгілеңіз (ДҚФ):

1)

2)

3)

4)

5)

6)

А) 1, 6 В) 1, 3, 6 С) 2, 4, 5 D) 5 Е) ондайлар жоқ
10. Берілген формулалардан мүлтіксіз конъюнктивті қалыпты формадағыларын белгілеңіз (КҚФ):

1)

2)

3)

4)

5)

6)

А) 1, 6 В) 1, 3, 6 С) 2, 4, 5 D) 5 Е) ондайлар жоқ
11. Көрсетілген логикалық функциялар жүйесінің қайсысын функцияналды толық деуге болады?

A) { x + y +z ,x &y, 0, 1 }; B) {x + y, x &y}; C) {x + y, 0, 1}; D) {x &y, 0, 1}; E) {x V y, 0 };

12. Айталық, Х-жиыны, ׀Х׀= 9 болсын, неше тәсілмен бұл жиынды біріншісі 3 элементтен, екіншісі 2 элементтен, үшіншісі 4 элементтен тұратын 3 ішкі жиындарға бөлуге болады?
A) 27 B) 729 C) 1260 D) 81 E) 252

13. 13. Матрицада 6 төбелі бағытталмаған байланысты граф қабырғаларының салмақтары берілген. Салмағы ең аз болатын барлық қаңқалы ағаштарды табыңыз. A) 9 B) 7 C) 11 D) 8 E) 13

 3 5 9 1 8 3  2 1 3 4 5 2  1 5 7 9 1 1  9 3 1 3 5 9  1 8 4 7 3 1 

14. f(x,y,z)=x&y V y&z функциясының барлық маңызды айнымалыларын көрсетіңіз.

A)  B) {x,y} C) {y,z} D) {x,y,z} E) {x}

15. Формулалардың қайсысы тепе- тең ақиқат (тавтология)?
A) х  х B) х  y C) x  D) x  y E) x  x
16. Егер X = x | 1  x <3, Y = y | 2  y  4 болса, Х және Y жиындарының қиылысуын

(X  Y) табыңыз

A) x | 1  x  4 B) x | 2  x  3 C) 2, 3 D) 1, 2, 3, 4 E) y | 2  y  4
17. f(x,y,z)=xy V(x y + z) Логикалық функцияның мүлтіксіз дизъюнктивті қалыпты формасы (МДҚФ) қайсы?

A)

B)
C)

D)

E)
18. Айталық, |X|=4 Х-жиыны берілсін.Осы жиынның неше өзіне -өзін биективті бейнелеуі бар?

A) 16 B) 256 C) 64 D) 24 E) 512

19. 30 қызметкерден тұратын бөлімнен 19-ы ағылшын тілін 17-і неміс тілін біледі, ал 5-і не ағылшын тілін, не неміс тілін білмейді. Қанша адам тек неміс тілін біледі?
A) 10 B) 6 C) 8 D) 2 E) 12
20. А={2,3,4} және B={4,5,6} жиындарының симметриялы айырымын (AΔB) табыңыз:
A) 2, 3, 4, 5, 6 B) 5, 6 C) 4 D) 2, 3 E) 2, 3, 5, 6
Өзін өзі тексеру сұрақтарының жауабы:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
с	е	d	b	d	b	c	e	b	c	a	e	b	d	c	b

17	18	19	20
b	d	b	e

8. 
   Пән бойынша емтихан сұрақтары:
   

1. Жиындар үшін де Морган заңын тұжырымдаңыз?

2. Универсум деген не?

3. Қиылысу операциясын кескіндейтін Эйлер-Венн диаграммасын сызыңыз?

4. Кортеж деген не?Екі жиынның Декарт көбейтіндісі деп нені айтамыз?

5. Ақырлы жиынның қуаты деген не? Қандай жиынды саналымды дейміз?

6. Екі саналымды екі жиынның бірігуінің қуаты қандай?

7. Жазықтықтың барлық нүктелерінің жиынының қуаты қандай?

8. Қуаты үшке тең жиын элементтерінен қанша бинарлы қатынас құруға болады?

9. Араларында өзара бір мәнді сәйкестік болуы үшін екі жиынның қуаттары қандай болуы керек?

10.Берілген жиында рефлексивті ,симметриялы емес, транзитивті қатынастар құрыңыз?

11.Квадрат пен кесінді нүктелерінің жиыны эквивалентті екенін дәлелдеңіз?

12. Бір жиынды екінші жиынға түрлендіретін функциялар саны қанша?

13.Жиынды екінші жиынға түрлендіретін инъективті бейнелеулері қанша?

14. Кантор теоремасын дәлелдеңіз?

15. Иррационал сандар жиынының қуаты қандай?

16. Жиында қандай қатынас рефлексивті деп аталады? Транзитивті қатынасқа мысал келтіріңіз?

17. Антирефлексивті, антисимметриялы және транзитивті қатынастар қалай аталады?

18. Екі түзудің перпендикуляр болу қатынасы эквивалентті деуге бола ма?

19. Жиындар арасындағы қандай сәйкестік бейнелеу деп аталады?

20. Қандай бейнелеу функционалды деп аталады?

21. Реті қатаң емес қатынас қандай қасиетке ие?

22. Жиынды бөліктеу деген не?

23. Қандай функция логикалық деп аталады?

24. Екі айнымалыда тәуелді қанша логикалық функция бар?

25. Эквиваленттіліктің терістеуі қандай функция?

26. Логикалық функцияда қандай айнымалы жалған деп аталады?

27. Үшіншіні шығару және қарама қарсылық заңдарын атаңыз?

28. Логикалық функцияның қандай түрі ДҚФ деп аталады?

29. Қандай екі функция эквивалентті деп аталады?

30. Қандай функция басқа логикалық функцияға түйіндес деп аталады?

31. Қандай логикалық функцияда МКҚФ жоқ?

32. Өзіне өзі түйіндес деп қандай логикалық функцияны айтады?

33. Анықталмаған коэффициенттер әдісімен логикалық функциядан Жегалкин полиномын қалай анықтайды?

34. Қандай логикалық функция сызықты деп аталады?

35. Логикалық функцияның МДҚФ қалай анықтайды?

36. Үш айнымалыдан тәуелді логикалық функцияның анықталу облысының қуаты қандай?

37. Неше элементер логикалық функциялар бірді сақтайды?

38. Нөлді сақтайтын барлық элементар функцияларды атаңыз?

39. Қандай монотонды логикалық функция нөлді сақтамайды?

40. Қандай логикалық функциялар жүйесі толық деп аталады?

41. Бір функциядан тұратын функционалды толық жүйені атаңыз?

42. Функционалдың толықтық туралы Пост функциясын атаңыз?

43. Функциялардың қандай класы тұйық деп аталады?

44.Комбинаторикадағы қосу және көбейту ережесін атаңыз?

45. Қандай таңдамалар орналастыру, теру деп аталады?

46. Түрлі таңдамалар саны қандай формулалармен есептеледі?

47. Қандай бөліктеу саны Стирлинг санын пайдалану арқылы есептеледі?

48. «Тәртіпсіздік»,«Кездесу» есептеріне сипаттаңыз?

49. Жиын элементерінің алмастыру санын қалай есептейді?

50. Бағытталған, бағытталмаған граф анықтамалары қандай?

51. Графтардың берілу тәсілдерін атаңыз?

52. Графтың қандай қабырғалары (доғалары) сыбайлас деп аталады?

53. Графтың қандай қабырғалары (доғалары) бір-біріне инцидентті болады?

54. Төбенің дәрежесі деген не?

55. Қандай граф көп граф деп аталады?

56. Толық графта әр төбенің дәрежесі неге тең?

57. Графтың цикломатикалық санын қалай есептейді?

58. Цикломатикалық сан нені көрсетеді?Цикломатикалық саны нөлге тең граф қалай аталады?

59. Графтармен орындалатын операцияларды атаңыз?

60. Қандай граф толық графтың қосымшасы болады?

61. Граф маршрут, тұйық маршрут дегендер не?

62. Шынжыр, қарапайым шынжыр, цикл, қарапайым цикл дегендерге анықтама бер?

63. Қандай граф байланысты деп аталады?

64. Графтың бөлігі, ішкі граф, суграф деп қандай графтарды айтады?

65. Ағаш деп қандай графты айтады?Ағаштың қаңқасы (каркас) деп нені айтады?

66. Графтарда ара қашықтық деп нені түсінеміз?

67. Графтың диаметрі, радиусы, центрі дегендер не?

68. Қандай граф қаныққан деп аталады?

69. Ең кіші салмақты қаңқалы ағашты анықтаудың Краскал алгоритмі қандай?

70. Графтың цикломатикалық саны деген не?Қандай граф бір хроматикалы?

71. Толық графтың хроматикалық сан неге тең?

72. Бағытталмаған байланысты нагруженный графтың екі төбесінің ең қысқа аралығын анықтайтын 73. Форд алгоритмін сипаттаңыз?

74. Қандай циклдер Эйлер циклы деп аталады?

75. Эйлер графы болу үшін жеткілікті және қажетті шартты атаңыз?

76. Гамильтон шынжыры, Гамильтон циклі деп нені айтады?

77. Коммивояжер туралы есепке сипаттама беріңіз?

78. Графта Гамильтон циклі бар болудың жеткілікті шарты қандай?

79. Қандай граф жазық деп аталады?

80. Қандай граф транспорттық желі деп аталады?

81. Доғаның жіберу мүмкіндігі деп нені айтады?

82. Транспорттық желіде қандай доғалар қаныққан деп аталады?

83. Желіде нені ағын деп атайды?

84. Қандай ағын толық деп аталады?

85. Желінің қандай төбелері бастауы, соңы деп аталады?

86. Желідегі ең үлкен ағынды анықтайтын Форд-Фалкерсон алгоритмін сипаттаңыз?

жүктеу 19,56 Mb.

Достарыңызбен бөлісу: