Қазақстан Республикасы Білім және ғылым министрлігі
С.Торайғыров атындағы Павлодар мемлекеттік университеті
«Информатика және ақпараттық жүйелер» кафедрасы
Алгоритмдер және олардың күрделілігі пәнінен
6М011100 – «Информатика», 6М060200 – «Информатика», 6М070300 – «Ақпараттық жүйелер» мамандықтары магистранттарына арналған
жұмыс оқу бағдарламасы
Павлодар
Жұмыс оқу бағдарламасын бекіту парағы
|
|
Нысан
Ф СО ПГУ 7.18.4/17
|
Құрастырушылар: ____________ п.ғ.д, профессор В.А.Криворучко
____________ п.ғ.к, доцент Г.С.Джарасова
«Информатика және ақпараттық жүйелер» кафедрасы
Алгоритмдер және олардың күрделілігі пәнінен
6М011100 – «Информатика», 6М060200 – «Информатика», 6М070300 – «Ақпараттық жүйелер» мамандықтары магистранттарына арналған
жұмыс оқу бағдарламасы
Жұмыс оқу бағдарламасы 6М010900 – «Информатика», 6М060200 – «Информатика», 6М070300 – «Ақпараттық жүйелер» мамандықтарының жұмыс оқу жоспарларына және элективті пәндер каталогтарына сәйкес әзірленген.
Кафедра отырысында ұсынылды 201__ ж. «____»_________
хаттама № ____
Кафедра меңгерушісі _____________ Н.Н.Оспанова 201__ ж. «____»___________
«Физика, математика және ақпараттық технологиялар» факультетінің оқу-әдістемелік кеңесінде ұсынылды
20__ ж. «___» __________ хаттама № ____
ФМжАТФ ОӘК
төрайымы _____________ А.Б. Искакова 201__ ж. «____»___________
КЕЛІСІЛГЕН
ФМжАТФ деканы _____________ Н.А. Испулов 201__ ж. «____»___________
ОӘБ бастығы _____________ Е.Н. Жұманқұлова 201__ ж. «____»___________
Университеттің оқу-әдістемелік кеңесінде 201__ ж. «____»___________ мақұлданды
хаттама № ____
1. Оқу пәнінің төлқұжаты
Пәннің атауы Алгоритмдер және олардың күрделілігі
ЖОО компонент (таңдау) пәні
Кредиттер саны және оқытылу мерзімі
Барлығы – 3 кредит
Курс: 1 және 2
Семестр: бірінші курс – 1 семестрде, екінші курс -3 семестрде
Барлығы аудиториялық сабақтар – 45 сағат
Дәрістер - 22,5 сағат
Практикалық сабақтар – 22,5 сағат
СӨЖ – 90 сағат, оның ішінде СӨЖМ – 22,5 сағат
Жалпы еңбексыйымдылығы – 135 сағат
Бақылау түрі
Емтихан – бірінші курс – 1 семестрде, екінші курс -3 семестрде
2. Пәннің мақсаты мен міндеттері
Алгоритмдер және олардың күрделілігінің пәні – оңтайландырылған алгоритмдер тұрғызу және олардың күрделілігін зерттеу.
Мақсаттары:
- Алгоритмдер және олардың күрделілігі пәні шеңберінде арнайы білімді қалыптастыру;
- магистранттарды деректерді өңдеудің іргелі алгоритмдерімен таныстыру.
Міндеттері:
- алгоритмдерді зерттеудің заманауи әдістеріне шолу және талдау;
- алгоритмдік күрделілікті бағалау.
Пререквизиттер
- математика;
- информатика;
- алгоритмдер, деректер құрылымы және бағдарламалау курстары
Постреквизиттер
Магистрлік диссертация тақырыптары боцынша ғылыми-зерттеу жұмыстары.
3. Білім, білік, дағды мен құзырлылықтарға қойылатын талаптар
Пәнді оқып-үйрену нәтижесінде студенттер келесілерге қол жеткізуі керек
түсінігі болуы керек:
-
комбинаторика, жиындар мен ішкі жиындар туралы;
-
графтар мен желілер туралы;
-
тура және қосарланған алгоритмдер туралы;
-
екіайрықты графтардағы жұптық үйлесімділік туралы;
-
бұтақтар мен шекаралар әдістері туралы;
-
стохастикалық алгоритмдер туралы.
білуі керек:
-
графтар мен желілерді машиналық кескінделуін;
-
графтардағы оңтайландыру есептерін;
-
желілік графикалар, желілердегі ағымдар;
-
Берж теоремасын, Холл теоремасын;
-
бұтақтар мен шекаралар әдістерін.
білігі қажет:
-
орынауыстыруларды, ішкі жиындарды генерациялау;
-
графтарда ұзындығы және тереңдігі бойынша іздестіру жүргізу;
-
минималды остов, желілердегі қысқа жол туралы есептерді шешуді;
-
максималды ағымды тұрғызу, минималды құн ағымы туралы есепті шығару;
-
көліктік есепті шығару;
-
ең үлкен жұптық үйлесімділік алгоритмін тұрғызу;
-
кемелденген жұптық үйлесімділік алгоритмін тұрғызу, жұптық үйлесімділіктердің ең аз санына бөлу есебін шығару;
-
коммивояжер есебін шығару.
қалыптастырылатын практикалық дағдылар:
- оңтайландырылған алгоритмдер құрастыру бойынша;
- алгоритмдер күрделілігі деңгейін таңдау бойынша.
қол жетімді құзырлықтар:
-
алгоритмдерді құрастыру әдістерін таңдау;
-
алгоритмдер күрделілігін бағалау;
-
нақты есепті шығарудың оңтайландырылған алгоритмді құру.
4 Пәнді оқудың тақырыптық жоспары
Академиялық сағаттарды сабақтар түрі бойынша бөлу
№
п/п
|
Тақырыптардың атауы
|
Сабақ түрлеріне қарай аудиториялық сағаттар саны
|
МӨЖ
|
дәрістер
|
практикалық
|
барлығы
|
Оның ішінде ММӨЖ
|
1
|
Тақырып 1. Комбинаторика: орынауыстыруларды генерациялау, ішкі жиындарды генерациялау, жиындарды бөліктеуді генерациялау
|
3
|
3
|
10
|
3
|
2
|
Тақырып 2. Алгоритмдер және олардың күрделіліктері
|
2
|
2
|
10
|
2
|
3
|
Тақырып 3. Графтар мен желілер. графтар мен желілердің машиналық кескінделуі, графтарда ұзындығы және тереңдігі бойынша іздестіру
|
3
|
3
|
10
|
3
|
4
|
Тақырып 4. Графтардағы оңтайландыру есептері: минималды остов, желілердегі қысқа жол туралы есептері
|
2
|
2
|
10
|
2
|
5
|
Тақырып 5. Желілік графикалар, желілердегі ағымдар, максималды ағымды тұрғызу, минималды құн ағымы туралы есеп
|
2
|
2
|
10
|
2
|
6
|
Тақырып 6. Тура және қосарланған алгоритмдер және олардың күрделіліктері, көліктік есеп
|
3
|
3
|
10
|
3
|
7
|
Тақырып 7. Екіайрықты графтардағы жұптық үйлесімділік, Берж теоремасы, ең үлкен жұптық үйлесімділік алгоритмін тұрғызу
|
2
|
2
|
10
|
2
|
8
|
Тақырып 8. Холл теоремасы, кемелденген жұптық үйлесімділік алгоритмі , жұптық үйлесімділіктердің ең аз санына бөлу есебі
|
1
|
1,5
|
5
|
1
|
9
|
Тақырып 9. Бұтақтар мен шекаралар әдісі, коммивояжер есебі, коммивояжер үшін кепілді дәлдік бағалауы бар алгоритм
|
3
|
3
|
10
|
3
|
10
|
Тақырып 10. Стохастикалық алгоритмдер
|
1,5
|
1
|
5
|
1,5
|
|
Барлығы:135 сағат (3 кредит)
|
22,5
|
22,5
|
90
|
22,5
|
5. Әдебиеттер тізімі
Негізгі:
-
Осипова В.А. Основы дискретной математики. Серия высшее образование. - М.: Форум, 2006. – 160 с.
-
Окулов С.М. Программирование в алгоритмах. – М.: БИНОМ. Лаборатория знаний, 2004. – 341 с.: ил.
-
Гаврилов Г.П. Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: Физматлит, 2005. – 416 с.
Қосымша:
-
Новиков Ф.А. Дискретная математика для программистов. - СПБ.: Питер, 2001. – 304 с.
-
Яблонский С.В. Введение в дискретную математику. - М: Высшая школа, 2001. – 384 с.
-
Носов В.А. Основы теории алгоритмов и анализа их сложности. Курс лекций. – Москва, 2001. – 140 с.
-
Материалы сайта http://www.dialektika.com
-
Материалы сайта http://www.williamspublishing.com
Достарыңызбен бөлісу: |