| Сабақтың коды | Курс аты | Сынып | Академиялық кредит | Cағат | Апталық сабақ сағаттары (лекция) | Апталық сабақ сағаттары (практика) | Апталық сабақ сағаттары (зертханалық) |
|---|---|---|---|---|---|---|---|
| GNA 3377 | Графтардағы негізгі алгоритмдер | Үшінші курс | 5 | 150 | 15 | 30 |
Білім алушыларды графтар теориясының негізгі ұғымдарымен таныстыру және оларды қолдана алатын жағдайға жеткізу; графтар теориясында есептердің қойылымы мен оларды шешу әдістерін меңгерту; негізгі теориялық-графтық алгоритмдерді игерту; түрлі салалардағы қолданбалы есептерді графтар теориясы тұрғысынан зерттеу.
сыни ойлау, миға шабуыл, пікір алмасу, пікірталасу, проблемалық әдістер.
| 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 | PÇ13 | PÇ14 | PÇ15 |
|---|