Ш.Уәлиханов атындағы Көкшетау мемлекеттік университеті

050504-Есептеу техникасы және ПҚ мамандығы

Дискреттік математика пәні бойынша

Емтихан сұрақтарының

ТІЗІМІ

Көкшетау-2007 ж.

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. Желідегі ең үлкен ағынды анықтайтын Форд-Фалкерсон алгоритмін сипаттаңыз?

Глоссарий

№	Жаңа ұғымдар	Мазмұны
	Жиын	Табиғаты кез келген болатын элементтер жиынтығы.
	А жиыны В жиынының ішкі жиыны деп аталады.	Егер А жиынының барлық элементтері В-ға жатса: .
	А мен В жиындары тең	Егер және болса, болып белгіледі.
	А мен В жиындарының қиылысуы	А мен В жиындарының екеуінде де бар элементтерден тұратын жиын яғни және
	А мен В жиындарының бірігуі	А мен В жиындарының не ға, не В немесе екеуіне де тиісті элементтерден тұратын жиын яғни немесе
	Универсум (фундаментальды жиын)	Алғашқы берілген жиын.
	Толықтауыш жиын	А жиынын универсумға дейін толықтыратын жиын.
	A мен B жиындарының айырымы	А жиынының B -ға енбейтін элементтерден тұратын жиын , болып белгіленеді.
	жиындарының Декарт көбейтіндісі	реттелген тізбектер жиыны,мұндағы . Декарт көбейтіндісі деп аталады және немесе болып белгіленеді.
	A және B иындарының арасындағы бинарлы қатыас	´ Декарт көбейтіндісінің ішкі жиынын айтады.
	Рефлексивті қатынас деп	Барлық xR x шарты орындалатын A жиынындағы R бинарлы қатынысын айтады.
	Симметриялы қатынас деп	Барлық x, y R үшін xRy болғандығынан yRx орындалатын A жиынындағы R бинарлы қатыны-сын айтады.
	Транзитивті қатынас деп	Барлық x, y,z R. үшін x R y және y R z болғандығынан xRz орындалатын A жиынындағы R бинарлы қатынысын айтады.
	Функция	А-дан алынған әрбір элементке В жиынынан бір ғана элементті сәйкестендіретін А мен В жиын-дарының арасындағы қатынысты айтады.
	Инъективті функция	f(a₁)=f(a₂) болғандықтан a₁=a₂ болатын функцияны айтады.
	Сюръективті функция	Мәндер жиыны мен анықталу облысы бірдей болатын функция
	Биективті функция	Бір мезетте инъективті де, сюръективті де болатын функция
	Логикалық функция	0 немесе 1 мәндерінің бірін ғана қабылдайтын функция.
	Буль алгебрасы	(конъюнкция), (дизъюнкция), (терістеу) операцияларының алгебрасы
	Дизъюнктивті қалыпты форма	Логикалық функцияларды минтермдердің дизъюнкциясы түрінде өрнектеу.
	Жегалкин алгебрасы	(конъюнкция), (сложение по модулю 2), 1(единица) операцияларының алгебрасы
	Логикалық функциялардың толық жүйесі	Кез-келген басқа логикалық функцияны өрнектеуге болатын функциялар жиыны.