Қазақстан республикасының білім және ғылым министірлігі

а) Семестрлік жұмыста құрылған G₁U G₂ жәнеG₁хG₂ графтары үшін:

• 
  Цикломатикалық санды;
  
• 
  Хроматикалық санды;
  
• 
  Диаметр, радиус, центрді табыңыз.
  

б) 7 Семестрлік жұмыстағы графы үшін төмендегілерді көрсетіңіз:

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

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

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

ТІЗІМІ

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

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

Глоссарий

№	Жаңа ұғымдар	Мазмұны
1	Жиын	Табиғаты кез келген болатын элементтер жиынтығы.
2	А жиыны В жиынының ішкі жиыны деп аталады.	Егер А жиынының барлық элементтері В-ға жатса: .
3	А мен В жиындары тең	Егер және болса, болып белгіледі.