|
Д.СЕРІКБАЕВ атындағы ШЫҒЫС ҚАЗАҚСТАН МЕМЛЕКЕТТІК ТЕХНИКАЛЫҚ УНИВЕРСИТЕТІ
|
Ф1 Н ШҚМТУ 701.01
|
Сапа менеджмент жүйесі
|
Силлабус
(магистрантқа арналған пәннің оқу бағдарламасы)
|
бет 12дан
|
Қазақстан Республикасының Министерство
Білім және ғылым образования и науки
Министрлігі Республики Казахстан
Д. Серікбаев атындағы ВКГТУ им. Д. Серикбаева
ШҚМТУ
БЕКІТЕМІН
АТжЭФ деканы
_________ Ғ. Мұхамедиев
__________________2014 ж.
АЛГОРИТМДЕР ТЕОРИЯСЫ
Силлабус
ТЕОРИЯ АЛГОРИТМОВ
Силлабус
Мамандық: 6М060100 - Математика
Оқу түрі: күндізгі
Курс: 1
Семестр: 1
Кредит саны: 4
Сағат саны: 180
Дәрістер: 30
Тәжірибелік сабақтар: 30
Зертханалық сабақтар: -
СОӨЖ: 15
СӨЖ: 105
Курстық жоба (жұмыс):-
Емтихан: 1-семестр
Өскемен
Усть-Каменогорск
2014
Силлабус «Алгоритмдер теориясы» элективті курсынан 6М060100 - Математика мамандығындағы магистранттарға арналып, «Жоғары математика» кафедрасында жасалынған.
«Жоғары математика» кафедра отырысында талқыланды.
|
Кафедра меңгерушісі
|
Н. Хисамиев
|
№1 хаттама 1-қыркүйек 2014 ж.
|
|
Ақпараттық технологиялар және энергетика факультетінің оқу-әдістемелік кеңесімен мақұлданды.
Төраға Т. Абдрахманова
|
|
|
№____ хаттама _____________________2014ж.
|
|
Дайындаған
|
|
профессор
|
Н. Хисамиев
|
Норма бақылаушы
|
Т. Тютюнькова
|
ОҚЫТУШЫ ТУРАЛЫ МАҒЛҰМАТ ЖӘНЕ СОҒАН БАЙЛАНЫСТЫ АҚПАРАТ
«Жоғары математика» кафедрасы, Ақпараттық технологиялар және энергетика факультеті (Г3-303 дәрісх.)
Пән жүргізетін оқытушы: Хисамиев Назиф Гаррифуллинович – «Жоғарғы математика» кафедрасының меңгерушісі, ф.-м.ғ.д., профессор
Жұмыс телефоны: 540-863
Дәрісханалық сағат және консультацияға арналған уақыт: сабақ кестесі және оқытушының жұмыс кестесі бойынша.
1. ПӘНГЕ СИПАТТАМА, ОНЫҢ ОҚУ ЖҮЙЕСІНДЕГІ ОРНЫ
1.1 Оқылатын пәнге сипаттама
Бұл курс магистрлік дайындықта «Математика» мамандандыруы бойынша негізгі пәндердің бірі болып табылады және келесі бөлімдерден тұрады: есептелімділік теориясының іргелі ұғымдары, есептелімді-тізімдемелі жиындар және Тьюринг машинасы.
1.2 Пәнді меңгеру мақсаты мен міндеттері
Пәнді оқытудың мақсаты: математикалық әдістермен алгоритм ұғымын оқу және нақты алгоритмдерді құру әдісін білу.
1.3. Пәнді меңгеру нәтижелері
«Алгоритмдер теориясы» курсын оқытудағы мамандарды дайындау талаптарына сәйкес, нәтижесінде алынатын қорытынды:
- алгоритм ұғының әртүрлі тұжырымдарын меңгеру;
-
нақты алгоритмді құру әдістерін қарастыру;
-
белгілі функцияларды есептеу үшін Тьюринг машинасы үшін бағдарламаны құру;
-
натурал санның негізгі ішкі жиындарының есептелімді тізімделетінін дәлелдеу.
1.4 Пререквизиттер
«Алгоритмдер теориясы» пәнін оқу үшін студенттерге алгебра, математикалық логика, математикалық және фундаментальдық талдаудың барлық бөлімдерінен білімі болуы керек.
1.5 Постреквизиттер
Бұл пәннен алған білімдерін өрістер теориясы және конструктивті үлгілер теориясын оқу кезінде қолдана алады. Сондай-ак, магистрлік диссертацияны дайындау кезінде қолданылады.
2 ПӘННІҢ МАЗМҰНЫ
2.1 Тақырыптық жоспар
Тақырып атауы, оның мазмұны
|
Еңбек сыйымдылығы, сағаты
|
Ұсынылған әдебиеттер
|
1
|
2
|
3
|
Дәрістік сабақтар
|
Тақырып 1. Жиындар теориясының кейбір ұғымдары. Әліпбилер мен тілдер. Алгоритмдердің интуитивті қасиеттерін талдау
|
2
|
[1-4]
|
Тақырып 2. Детерминделген және детерминделмеген автоматтар
|
2
|
[1-4]
|
Тақырып 3. Регулярлық тілдер
|
2
|
[1-4]
|
Тақырып 4. Шенфильд машинасы
|
2
|
[1-4]
|
Тақырып 5.Жартылай рекурсивті функциялар
|
2
|
[1-4]
|
Тақырып 6. Ақырлы тізбектерді кодтау
|
2
|
[1-4]
|
Тақырып 7. Шенфильд машинасын кодтау
|
2
|
[1-4]
|
Тақырып 8. Тьюринг машинасы
|
2
|
[1-4]
|
Тақырып 9. Марковтың қалыпты алгорифмдері
|
2
|
[1-4]
|
Тақырып 10. Черч тезисі
|
2
|
[1-4]
|
Тақырып 11. Нөмірлеу және алгоритмдік мәселелер
|
2
|
[1-4]
|
Тақырып 12. Қозғалмайтын нүкте туралы Клини теоремасы және Райс теоремасы
|
2
|
[1-4]
|
Тақырып 13. Әмбебап функцияның жалғыздығы туралы
|
2
|
[1-4]
|
Тақырып 14. Тізімдемелі жиындар
|
2
|
[1-4]
|
Тақырып 15. Тьюрингтің детерминирленбеген машиналары және Р мен NP класстары. NP-толық мәселелер туралы ұғым
|
2
|
[1-4]
|
Семинарлық (тәжірибелік) сабақтар
|
Тақырып 1. Жиындар теориясының кейбір ұғымдары. Әліпбилер мен тілдер. Алгоритмдердің интуитивті қасиеттерін талдау
|
2
|
[1-4]
|
Тақырып 2. Детерминделген және детерминделмеген автоматтар
|
2
|
[1-4]
|
Тақырып 3. Регулярлық тілдер
|
2
|
[1-4]
|
Тақырып 4. Шенфильд машинасы
|
2
|
[1-4]
|
Тақырып 5.Жартылай рекурсивті функциялар
|
2
|
[1-4]
|
Тақырып 6. Ақырлы тізбектерді кодтау
|
2
|
[1-4]
|
Тақырып 7. Шенфильд машинасын кодтау
|
2
|
[1-4]
|
Тақырып 8. Тьюринг машинасы
|
2
|
[1-4]
|
Тақырып 9. Марковтың қалыпты алгорифмдері
|
2
|
[1-4]
|
Тақырып 10. Черч тезисі
|
2
|
[1-4]
|
Тақырып 11. Нөмірлеу және алгоритмдік мәселелер
|
2
|
[1-4]
|
1
|
2
|
3
|
Тақырып 12. Қозғалмайтын нүкте туралы Клини теоремасы және Райс теоремасы
|
2
|
[1-4]
|
Тақырып 13. Әмбебап функцияның жалғыздығы туралы
|
2
|
[1-4]
|
Тақырып 14. Тізімдемелі жиындар
|
2
|
[1-4]
|
Тақырып 15. Тьюрингтің детерминирленбеген машиналары және Р мен NP класстары. NP-толық мәселелер туралы ұғым
|
2
|
[1-4]
|
Студенттің оқытушы жетекшілігімен орындайтын өздік жұмысы
|
Тақырып 1. Жиындар теориясының кейбір ұғымдары. Әліпбилер мен тілдер. Алгоритмдердің интуитивті қасиеттерін талдау
|
1
|
[1-4]
|
Тақырып 2. Детерминделген және детерминделмеген автоматтар
|
1
|
[1-4]
|
Тақырып 3. Регулярлық тілдер
|
1
|
[1-4]
|
Тақырып 4. Шенфильд машинасы
|
1
|
[1-4]
|
Тақырып 5.Жартылай рекурсивті функциялар
|
1
|
[1-4]
|
Тақырып 6. Ақырлы тізбектерді кодтау
|
1
|
[1-4]
|
Тақырып 7. Шенфильд машинасын кодтау
|
1
|
[1-4]
|
Тақырып 8. Тьюринг машинасы
|
1
|
[1-4]
|
Тақырып 9. Марковтың қалыпты алгорифмдері
|
1
|
[1-4]
|
Тақырып 10. Черч тезисі
|
1
|
[1-4]
|
Тақырып 11. Нөмірлеу және алгоритмдік мәселелер
|
1
|
[1-4]
|
Тақырып 12. Қозғалмайтын нүкте туралы Клини теоремасы және Райс теоремасы
|
1
|
[1-4]
|
Тақырып 13. Әмбебап функцияның жалғыздығы туралы
|
1
|
[1-4]
|
Тақырып 14. Тізімдемелі жиындар
|
1
|
[1-4]
|
Тақырып 15. Тьюрингтің детерминирленбеген машиналары және Р мен NP класстары. NP-толық мәселелер туралы ұғым
|
1
|
[1-4]
|
2.2 Өздік жұмыс тапсырмалары (СӨЖ)
Тақырып
|
Тапсырманың мазмұны және мақсаты
|
Ұсынылатын әдебиеттер
|
Дайындау мерзімі
|
Бақылау түрі
|
Тапсыру уақыты
|
1
|
2
|
3
|
4
|
5
|
6
|
Алгоритмдер құру. Детерминделген және детерминделмеген автоматтар. Шенфильд машинасы
|
Алгоритмдер құру дағдысын қалыптастыру
|
1
|
1-4 апта
|
Есеп өткізу
|
5-апта
|
1
|
2
|
3
|
4
|
5
|
6
|
Жартылай рекурсивті функциялар Шенфильд машинасын кодтау
|
Шенфильд машинасын кодтай білу
|
3
|
5,6- апта
|
Есеп өткізу, коллоквиум
|
7- апта
|
Тьюринг машинасы
|
Тьюринг машинасын құру дағдысын қалыптастыру
|
9
|
7,8- апта
|
Есеп өткізу
|
9- апта
|
Марковтың қалыпты алгорифмдері. Черч тезисі
|
Марковтың алгорифмдерін құру
|
9
|
9-11- апта
|
Есеп өткізу
|
12- апта
|
Қозғалмайтын нүкте туралы Клини теоремасы және Райс теоремасын қолдану. Әмбебап функцияның жалғыздығы туралы
|
Қозғалмайтын нүкте туралы Клини теоремасы және Райс теоремасын қолдану дағдысын қалыптастыру.
|
9
|
12,13- апта
|
Есеп өткізу және қорғау
|
13- апта
|
Тізімдемелі жиындар
|
Тізімдемелі жиындар есептерді шешу дағдысын қалыптастыру.
|
9
|
14,15- апта
|
Есеп өткізу, коллоквиум
|
15- апта
|
-
Пән тапсырмаларының орындалу және тапсыру кестесі*
Бақылау түрі
|
Оқудың академиялық кезеңі, апта
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
Сабаққа қатысу
|
*
|
*
|
*
|
*
|
*
|
*
|
*
|
*
|
*
|
*
|
*
|
*
|
*
|
*
|
*
|
Дәрістер конспектісі, аудиториядағы студенттің жұмысы
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
*
|
Ауызша сұрау
(Математикалық диктант, коллоквиум).
|
|
|
|
*
|
|
*
|
|
*
|
|
|
*
|
|
|
*
|
|
Ағымдық бақылау
|
|
|
|
*
|
|
*
|
|
*
|
|
|
*
|
|
|
*
|
|
Аралық бақылау
|
|
|
|
|
|
|
|
*
|
|
|
|
|
|
|
*
|
Өз бетімен орындайтын үй жүмысы
|
|
|
*
|
|
|
*
|
|
|
*
|
|
|
|
*
|
|
|
Барлығы
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-
ҰСЫНЫЛҒАН ӘДЕБИЕТТЕР ТІЗІМІ
-
Негізгі әдебиеттер
-
Морозов А.С., Хисамиев Н.Г., Қоңырханова Ә.Ә. Алгоритмдер теориясы. Өскемен, 2012 ж
-
Ершов Ю.Л. Теория нумерации. М., Наука, 2007
-
Ершов Ю.Л. Определимость и вычислимость. Сибирская школа алгебры и логики. Научная книга, Новосибирск, 2006.
-
Мальцев А.И.. Алгоритмы и рекурсивные функции. М., Наука, 2011
-
Қосымша әдебиеттер
1 Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. Мир, Москва, 2012.
2 Соар Р.И. Вычислимо перечислимые множества и степени. Казанское математическое общество, Казань, 2007.
3 Lewis H.R., Papadimitrou C.H. Elements of the Theory of Computation. Pretence-Hall Inc., Upper Saddie Riever, New Jersey, 2008.
4 БІЛІМДІ БАҒАЛАУ
4.1 Оқытушы талаптары
Оқытушы талаптары:
-
Сабақ кестесіндегі дәрістік және тәжірибелік сабақтарға қатысу міндетті;
-
студенттердің қатысуы сабақтың басында тексеріледі. Кешіккен жағдайда студент тыныш дәрісханаға кіріп, жұмысқа кірісуі қажет, ал үзілісте оқытушыға кешігу себебін түсіндіру қажет;
-
сабаққа екі рет кешігу бір рет сабақтан қалғанмен тең;
-
балмен есептелетін жұмыстарды бекітілген мерзімде тапсыру қажет. Жұмыс уақтылы тапсырылмаса қойылатын балл төмендейді. Барлық тапсырманы тапсырмаған студенттер емтиханға кіргізілмейді;
-
қанағаттанарлық деген баға алған студентке аралық бақылауды қайталап өтуге рұқсат берілмейді;
-
орташа рейтингісі Рор = (Р1 + Р2)/2 50% кем, студенттер емтиханға енгізілмейді;
-
сабақ барысында ұялы телефондар сөндірулі болу керек;
-
студент сабаққа іскерлік киімімен келу қажет.
4.2 Баға критериі
Барлық тапсырма түрлері 100-балдық жүйемен бағаланады.
Ағымдағы бақылау әр тарау соңында өткізіледі және оның ішіне дәрістерге қатысуды, тәжірибелік сабақтар мен өздік жұмыстарды орындау кіреді.
Аралық бақылау тест түрінде семестрдің 8 және 15 апталарында өткізіледі. Рейтинг келесі бақылау түрлерінен жиналады:
Аттестациялау кезеңі
|
Қатысу
|
Дәрістер конспектісі аудиториядағы студенттің жұмысы
|
Ауызша сұрау
(Математикалық диктант, коллоквиум).
|
Ағымдық бақылау
|
Аралық бақылау
|
Өз бетімен орындайтын үй жүмысы
|
Барлығы
|
Рейтинг 1
|
5
|
-
|
15
|
15
|
20
|
45
|
100
|
Рейтинг 2
|
5
|
5
|
10
|
15
|
20
|
45
|
100
|
Әр пәннен емтихан емтихандық сессия кезінде тест түрінде өтеді.
Пәннен студент білімінің қорытынды бағасын құрайтындар:
- 40% қорытындысы, емтиханнан алынған баға;
- 60% қорытындысы ағымдағы үлгерім.
Қорытынды баға есебінің формуласы:
 ,
мұндағы Р1, Р2 – бірінші, екінші рейтингтің бағасына сандық эквивалент сәйкесінше;
Еемт – емтихандағы бағаның сандық эквиваленті.
Қорытынды әріптік баға және балл түріндегі сандық эквивалент:
Әріп жүйесіндегі баға
|
Баллдың сандық эквиваленті
|
Пайыздық түрі, %
|
Дәстүрлі жүйедегі баға
|
А
|
4,0
|
95–100
|
өте жақсы
|
А–
|
3,67
|
90–94
|
В+
|
3,33
|
85–89
|
жақсы
|
В
|
3,0
|
80–84
|
В–
|
2,67
|
75–79
|
С+
|
2,33
|
70–74
|
қанағаттанарлық
|
С
|
2,0
|
65–69
|
С–
|
1,67
|
60–64
|
D+
|
1,33
|
55–59
|
D
|
1,0
|
50–54
|
F
|
0
|
0–49
|
қанағаттанғысыз
|
4.3 Қорытынды бақылау жасауға арналған мәліметтер
Қорытынды бақылау ауызша семестр аяғында емтихандар кестесі бойынша жүргізіледі.
Достарыңызбен бөлісу: |
