| Сабақтың коды | Курс аты | Сынып | Академиялық кредит | Cағат | Апталық сабақ сағаттары (лекция) | Апталық сабақ сағаттары (практика) | Апталық сабақ сағаттары (зертханалық) |
|---|---|---|---|---|---|---|---|
| GT 3201 | Графтар Теориясы | Үшінші курс | 5 | 150 | 1 | 2 | 2 |
Студенттерді графтар теориясы мен желілік талдау негіздерімен таныстыруға бағытталған. Пәнді оқу нәтижесінде студенттер әлеуметтік графтарды талдау және визуализациялау үшін Python NetworkX кітапханасымен жұмыс істеудің практикалық дағдыларын алады. Алынған құзыреттерді жарнама және жұртшылықпен байланыс жөніндегі мамандар ақпараттық алаң мониторингі және коммуникациялық науқандарды жоспарлау үшін пайдалана алады.
---
Дискретті математика.
баяндау, пікір алмасу, пікірталасу, проблемалық әдістер.
| 1 | Графтар теориясының негізгі ұғымдарын, графтардың түрлерін және оларды беру тәсілдерін біледі. |
| 2 | Графтардағы ең қысқа жолдарды іздеу және желідегі максималды ағынды табу алгоритмдерін түсінеді. |
| 3 | Ағаш ұғымы мен ағаштардың қасиеттерін біледі. |
| 4 | Эйлерлік және гамильтондық циклдер ұғымдарын және олардың бар болу шарттарын біледі. |
| 5 | Планарлық және жазық графтар ұғымдарын, графтың планарлық болуының қажетті және жеткілікті шарттарын, графтың хроматикалық санын бағалау әдістерін біледі. |
| 6 | Графтарды беру тәсілдерін қолданады. |
| 7 | Графтардағы ең қысқа жолдарды табу мәселелерін шешудің классикалық алгоритмдерін қолданады және олардың модификацияларын жасайды. |
| 8 | Ең аз салмақты қаңқалы ағаш құра біледі. |
| 9 | Графтарда эйлерлік және гамильтондық циклдерді таба біледі. |
| 10 | Жазықтыққа планарлық графты жатқыза біледі, графтың планарлық болып табылатындығын анықтай алады, графтың оңтайлы бояуын табады. |
| Haftalık Konu | Бағалау әдісі | |
|---|---|---|
| 1 | Графтар теориясының тарихы. Сыбайластық. Графтар және оған ұқсас нысандар. Графтар изоморфизмы. Валенттілік. | |
| 2 | Графтарды беру жолдары. Графтарға қолданылатын амалдар. | |
| 3 | Графтар саны. Ішкі графтар. Графтар түрлері. | |
| 4 | Маршруттар, шынжырлар, циклдер. Маршруттардың сандарын анықтау. Маршруттар мен циклдердің бар болуын анықтау. | |
| 5 | Графтың метрикалық сипаттамалары. Графты айналып өту. | |
| 6 | Байланыстық компоненттері. Графтардағы және орграфтардағы байланыстық. Конденсация құру алгоритмы. Базаны және антибазаны анықтау. | |
| 7 | Желідегі ағындар. Форд-Фалкерсон теоремасы. Максималды ағынды табу алгоритмы. | |
| 8 | Салмақталған графтардағы ең қысқа жолдар. Ең қысқа жолдарды табу есебінің қойылуы. Дейкстра алгоритмы. Форд-Беллман алгоритмы. | |
| 9 | Ағаштар және олардың қасиеттері. Ағаштар центроиды. Прюфер коды. | |
| 10 | Ағаштардағы есептер. Қанқалы ағаштарды тізбектеу. Қанқалы ағаштарды санау. | |
| 11 | Минималды қанқалар. Краскал алгоритмы. Прим алгоритмы. Бағытталған, реттелген және бинарлы ағаштар. | |
| 12 | Фундаменталды циклдер және фундаменталды қималар жүйелері. Тәуелсіз циклдер жиыны. Фундаменталды циклдерді құру алгоритмы. Тәуелсіз қималар жиыны. Фундаменталды қималарды құру алгоритмы. | |
| 13 | Эйлерлік циклдер (шынжырлар). Эйлерлік циклдердің бар болуының қажетті және жеткілікті шарттары. Эйлерлік циклдерді табу алгоритмы. Гамильтондық циклдер. Гамильтондық циклдің бар болуының жеткілікті шарттары. Гамильтондық циклдерді табу алгоритмы (алгебралық әдіс). | |
| 14 | Төбелердің тәуелсіз (ішкі орнықтылық) жиыны ұғымы. Максималды тәуелсіз жиындарды іздеу алгоритмы. Төбелердің доминдеуші (сыртқы орнықтылық) жиыны ұғымы. Минималды доминдеуші жиындарды іздеу алгоритмы. | |
| 15 | Жазық графтар. Планарлы графтар. Графты жазықтыққа жатқызу алгоритмы. Графтың хроматикалық саны. Графты бояу алгоритмдері. |
| PÇ1 | PÇ2 | PÇ3 | PÇ4 | PÇ5 | PÇ6 | PÇ7 | PÇ8 | PÇ9 | PÇ10 | PÇ11 | PÇ12 |
|---|
| Оқулық / Материал / Ұсынылатын ресурстар | ||
|---|---|---|
| 1 | Ә.С.Төлеп, Б.И.Ескараева. Графтар теориясы. Оқу құралы. -Түркістан, 2019. -115 б | |
| 2 | Ә.С. Төлеп, Б.И. Ескараева. Дискретті математика. Теория және практикум. -Шымкент, 2020. -132 б. | |
| 3 | Абильдаева Г.Б. Дискретті математика: Электрондық оқулық. - Қарағанды: ҚарМТУ, 2017. | |
| 4 | Шевелев Ю.П. Дискретная математика: Учебное пособие. - 4-е изд., стер. - СПб.: Лань, 2022. |