«Алгоритмдер теориясы» ПӘннің ОҚУ-Әдістемелік кешені

2. «АЛГОРИТМДЕР ТЕОРИЯСЫ» КУРСЫНЫҢ БАҒДАРЛАМАСЫ

2009-20010 оқу жылының 2-семестрі 2 кредит

2.1. Оқытушы туралы мәлімет:

Аты-жөні: Атушева М.К., оқытушы

Офис: Достық данғ 162

Мекен-жайы: № 1, 307-кабинет.
2.2. Пән туралы мәлімет:
Семестр 15 апта оқу үрдісі мен 2 апта сессиядан тұрады. Бір аптаға 2 кредит сағаты жоспарланады, оның 1 сағаты дәріс, 1 сағаты практикалық сабақ. Сонымен бірге 2 сағаттан СОБӨЖ жүргізіледі.

сабақ	ұзақтығы	сабақ	ұзақтығы
Байланыс сағаты 1 (дәріс )	50 мин.	СОӨЖ,СӨЖ (практикалық сабақ)	50 мин.+50
Байланыс сағаты 2 (практика )	50 мин	СОӨЖ,СӨЖ (практикалық сабақ)	50+50 мин

Кредит саны-2

Өту орны: № 8 оқу ғимараты, 306-311 ауд., сабақ кестесі бойынша
Оқу жоспарынан көшірме:

Курс	Семестр	Кредит саны	Дәрістер	Зертханалық жұмыс	СӨБӨЖ	СӨЖ	Барлығы	Бақылау түрі
3	6	2	15	15	30	30	90	емтихан

2.3. Курстың мақсаты мен міндеттері

Курс сипаттамасы:

Алгоритмдер теориясы курсы студенттердің абстрактылы, алгоритмдік ойлау мәдениетін қалыптастыру үшін өте қажет. Курста төмендегідей бөлімдер: алгоритмдердің мазмұнды ұғымы, алгоритм ұғымдарын әртүрлі формальдау тәсілдері және олардың эквиваленттері, формальды әдістерді бағдарлау, универсальды номерлеу, рекурсивті саналатын және рекурсивті жиындар, алгоритмдік шешілетін және шешілмейтін проблемалар, жиындардың келтірімділігі, жай және продуктивті жиындар, жиындар баспалдығы қарастырылады.

Аталған курс «бағдарлау тілдері», «логикалық бағдарлау», «информатиканың теориялық негіздері» курстарын оқытуға дайындық болады. Курсты меңгеру үшін мектеп математикасын, алгебра және сандар теориясы, математикалық логика, дискрет математиканың кейбір ұғымдарын білу қажет.
Курс мақсаты:

Студенттерді алгоритм ұғымын формальдау әдісімен, есептелетін функциялар ұғымымен және т.б. материалдармен таныстыру. Курсты оқыту барысында студенттер алгоритмдердің блок-сұлбаларын, алгоритмдердің күрделілігін, алгоритмдік шешілмейтін проблемалардың бар болатындығын оқып біледі.

Пәнді оқытудың міндеттері:

Алгоритмдердің формальды теориясының әдістерін меңгеру, есептелетін функциялардың кластарымен, алгориитмдік шешілмейтін проблемаларымен, алгоритмдердің күрделілігімен танысу.

Пререквизит:

Берілген курсты игеру үшін студенттер келесі пәндер бойынша білімдері болуы қажет:

• 
  Алгоритмдеу және бағдарламалау тілдері
  
• 
  Бағдарламалау технологиясы
  
• 
  Программалау негіздері
  

Постреквизит:

Пәнді оқып үйрену негізінде студенттер төмендегілерді білулері керек:

• 
  мәлеміттердәң логикалық және машиналық сипаттауларын басқа программалау тілдерінде қолдану
  
• 
  алгоритмдердің күрделілігн анықтауды білу
  
• 
  -іздестіру, реттеу алгоритмдерін қолдана білу
  
• 
  алгоритмдерді құру, структуралау эдістерін игеру
  
• 
  динамикалық айнымалылармен жұмыс жасау негіздері
  

Оқыту әдістемесі:

Оқыту үрдесінің негізгі кезеңдері: Оқыту іс-әрекет үш кезеңнен тұрады:

1. Материалды еңгізу барысында мотивациялау.

2. Операциялық-танымалылық.

3. Бақылау-бағалау.

Бірінші кезеңде тақырыптың пән жүйсінде алатан орнын, мағынасын, ролін анықтау мақсатымен проблемалық жағдай құрылады. Оқыту мақсаттары және білімнің минимальды деңгейіне деген, оқушылардың біліктері мен дағдылар деңгейіне қойлытын талаптар тұжырымдалады(оқыту алдындағы, оқытудан кейінгі). Тақырыпты игеру жоспары тұсіндіріледі.

Екінші кезең мазмұны: дәріс, оқулықтар, материалды демонстациялау көрнекі құралдары, эксперимент жүргізілуі мүмкін, студенттердің оқу-танымалық іс-әрекеттерә ұйымдастырылады, бақылау, студенттердің аралық жұмысын бағалау, ескеру, коррекциялау.

Үшінші кезеңде оқушылардың білімдері жалпыланылып, корытындылық бақылау , қателер диагностикасы, оқушылардың білімдерін коррекциялау ұйымдастырылады, жүргізіледі.

Курс мазмұны

• 
  Алгоритм ұғымы
  
• 
  Алгоритмге қойылатын негізгі талаптар
  
• 
  Блок-сұлба және алгоритмнің сипаттамасы
  
• 
  Алгоритм ұғымын сипаттаудың негізгі бағыттары
  
• 
  Тьюринг машиналары
  
• 
  Сыртқы және ішкі алфавиттер, командалар, бағдарламалар
  
• 
  Тьюринг машинасы жұмысының сипаттамасы
  
• 
  Қосу, тұрақты шамалар, көшіру бағдарламалары
  
• 
  Тьюринг машиналарының композициясы
  
• 
  Циклдарды біріктіру
  
• 
  Қарапайым функциялардың есептелінетіндігі
  
• 
  Клинидің формальдау жолы
  
• 
  Жай функциялар
  
• 
  Суперпозиция және примитивті рекурсия рператорлары
  
• 
  Примитивті рекурсивті функциялар класы
  
• 
  Негізгі арифметикалық функциялардың примитивті рекурсивтілігі
  
• 
  Минимизация операторы
  
• 
  Толымсыз рекурсивті, жалпы рекурсивті және рекурсивті функциялар кластарыМарковтың нормальды алгорифмдеріАлфавит, сөздер, қарапайым әрекеттер
  
• 
  Марковтың нормальды алгорифмдерінің жұмысының сипаттамасы
  
• 
  Марковтың цифрлы алгорифмдер
  
• 
  Марков алгорифмдерінің таралуы және бірігуі
  
• 
  Басқарушы алгорифм
  
• 
  Марковтың тармақталатын алгорифмы
  
• 
  Алгоритам ұғымын формальдаудың әртүрлі тәсілдерінің өзара эквиваленттілігі
  
• 
  Черчтың тезисі
  
• 
  Универсаль функциялар
  
• 
  Клини номерлеуі
  
• 
  Рекурсивті функциялардың номерлер жиынының қасиеттері
  
• 
  Диагональды құрастырулар
  
• 
  Рекурсия туралы теорема
  
• 
  Райс теоремасы
  
• 
  Рекурсивті және рекурсивті саналатын жиында
  
• 
  Рекурсивті алмастырулар
  
• 
  Рекурсивті жиындар және олардың қасиеттері
  
• 
  Келтірілетідік
  
• 
  Эквиваленттілік
  
• 
  Толық жиындар және дәрежелер
  
• 
  Жай жиындар
  
• 
  Максимальды жиындар
  
• 
  Райс-Шапиро теоремасы
  

2.4. Сабақ мазмұны мен кестесі.

Апта	Тақырып	Мазмұны	Практикалық сабақ	СОБӨЖ мазмұны
1-апта
1-кредит сағаты (дәріс)	Кіріспе. Алгоритм ұғымы	Алгоритмге қойылатын негізгі талаптар Блок-сұлба және алгоритмнің сипаттамасы	1.Алгоритмдер және олардың блок-сұлбалары	№ 1 СОБӨЖ. Тақырыбы: Алгоритм құрылымы, алгоритм бөліктері және олардың атқаратын қызметі, қарпайым командалар, сипаттау. № 2 СОБӨЖ. Тақырыбы: Қарапайым типті мәліметтерді өндеу алгоритмдері: блок-схемалар, псевдокод. Арифметикалық өрнектердің жазылуы, базалық конструкциялар.
2-апта
1-кредит сағаты (дәріс)	Алгоритм ұғымын сипаттаудың негізгі бағыттары	Тьюринг машиналары Сыртқы және ішкі алфавиттер, командалар, бағдарламалар	2.Қарапайым функциялар үшін Тьюринг машинасы	Тақырыбы: Программа ұғымы: анықтама, программаға қойылатын талаптар, трансляция. Программанаң негізгі бөліктері. Программалар мысалдары. № 4 СОБӨЖ. Тақырыбы: Енгізу, шығару процедуралары: сипаттау, түрлері, еңгізу, шығару парамаетрлері, енгізу, шығару әдістері. Арифметикалық амалдарды программалау.
3-апта
1-кредит сағаты (дәріс)	Тьюринг машинасы жұмысының сипаттамасы	Қосу, тұрақты шамалар, көшіру бағдарламалары Тьюринг машиналарының композициясы	3.Қарапайым арифметикалық функциялардың примитивті есептелінетіндігі	№ 5 СОБӨЖ. Тақырыбы: Логикалық және машиналық деңгейлерін ескеріп мәліметтерді программалау. № 6 СОБӨЖ. Тақырыбы: Типтерді түрлендіру амалдарын программмалау
4-апта
1-кредит сағаты (дәріс)	Циклдарды біріктіру	Қарапайым функциялардың есептелінетіндігі Клинидің формальдау жолы	4.Рекурсивті функциялар	№ 7 СОБӨЖ. Тақырыбы: Алгоритмдік конструкцияларды программалау, қарастырылған мәліметтерге қолдану № 8 СОБӨЖ. Тақырыбы: Басқаруды беру негізінде циклдарды программалау: счетчиктер, қосындылар, көбейтінділер, Объектілердің кезкелген тізімдерін программалау.
5-апта
1-кредит сағаты (дәріс)	Жай функциялар	Суперпозиция және примитивті рекурсия рператорлары Примитивті рекурсивті функциялар класы	5.Марковтың нормальды алгорифмдері	№ 9 СОБӨЖ. Тақырыбы: Таңдау операторы: сипаттамасы, синтаксикалық диаграмма. № 10 СОБӨЖ Тақырыбы: Сase операторын қолдану мысалдары.
6-апта
1-кредит сағаты (дәріс)	Негізгі арифметикалық функциялардың примитивті рекурсивтілігі	Минимизация операторы Толымсыз рекурсивті, жалпы рекурсивті және рекурсивті функциялар кластары	Бір формальдаудың қарапайым операцияларының басқа формальдаудың қарапайым опреацияларына көшетіндігі	№11 СОБӨЖ. Тақырыбы: Қарастырылған алгоритмдік конструкцияларын программалау, мәліметтердің өткен типтерін өндеуде қолдану. Негізгі алгоритмдік конструкцияларының комбинациялары №12 СОБӨЖ. Тақырыбы: Счетчиктерді, қосындыларды, көбейтітінділерді программалау, объектілердің кез келген тізімдерін өндеу.
7-апта
1-кредит сағаты (дәріс)	Марковтың нормальды алгорифмдері	Алфавит, сөздер, қарапайым әрекеттер Марковтың нормальды алгорифмдерінің жұмысының сипаттамасы	7. Рекурсивті функциялардың номерлерінің қасиеттері	№13 СОБӨЖ. Тақырыбы: Қарастырылған алгоритмдік конструкцияларын программалау, мәліметтердің өткен типтерін өндеуде қолдану. Негізгі алгоритмдік конструкцияларының комбинациялары. №14СОБӨЖ. Тақырыбы: Счетчиктерді, қосындыларды, көбейтітінділерді программалау, объектілердің кез келген тізімдерін өндеу.
8-апта
1-кредит сағаты (дәріс)	Марковтың цифрлы алгорифмдер	Марков алгорифмдерінің таралуы және бірігуі Басқарушы алгорифм	8.Рекурсивті функциялар туралы негізгі теоремалардың қолданылуы	№15 СОБӨЖ. Тақырыбы: Әртүрлі массивтерді сипаттау: массив-тип, массив-айнымалы, элементтерінің типі және өлшемі , өрнектеу диапазоны . Компилятордың мәліметтері. №16 СОБӨЖ. Тақырыбы:Енгізу, шығаруды, счетчиктерді, сумматорларды программалау, массив элементтерін берілген белгілері бойынша таңдау.
9-апта
1-кредит сағаты (дәріс)	Марковтың тармақталатын алгорифмы	Алгоритам ұғымын формальдаудың әртүрлі тәсілдерінің өзара эквиваленттілігі Черчтың тезисі	9.Шешілмейтін алгоритмдік проблемалар	№17 СОБӨЖ. Тақырыбы: Әртүрлі массивтерді сипаттау: массив-тип, массив-айнымалы, массив-константа, элементтердің типімен өлшемдері , өрнектеу диапазоны . Компилятордың мәліметттері. №18 апсырма. Тақырыбы: Енгізу, шығаруды, счетчиктерді, сумматорларды программалау, массив элементтерін берілген белгілері бойынша түрлендіру.
10-апта
1-кредит сағаты (дәріс)	Универсаль функциялар	Клини номерлеуі Рекурсивті функциялардың номерлер жиынының қасиеттері	10.Рекурсивті және рекурсивті саналатын жиындардың қасиеттері	№19 СОБӨЖ. Тақырыбы: Жолдарды түрлендірудің стандартты алгоритмдерін программалау. №20 СОБӨЖ. Тақырыбы: Мәліметтер типтерін түрлендіру, қолдану жағдайлары.
11-апта
1-кредит сағаты (дәріс)	Диагональды құрастырулар	Рекурсия туралы теорема Райс теоремасы	11.Рекурсивті саналатын жиындарға қолданылатын амалдар	№21 СОБӨЖ. Тақырыбы: Жиындар арқылы орындалатын амалдар: біріктіру, қиылысу, эквиваленттігін, кіруін тексеру. №22 СОБӨЖ. Тақырыбы: Жиындар арқылы орындалатын амалдарды программалау.
12-апта
1-кредит сағаты (дәріс)	Рекурсивті және рекурсивті саналатын жиындар	Рекурсивті алмастырулар Рекурсивті жиындар және олардың қасиеттері	12.Жиындардың кетірілетіндігі	№23 СОБӨЖ. Тақырыбы: Жазулар элементтерін еңгізу, шығару , қарапайым өндеулер алгоритмдері. №24 СОБӨЖ. Тақырыбы: Күрделілеу алгоритмдер; массивтерді қолдану
13-апта
1-кредит сағаты (дәріс)	Келтірілетіндік	Эквиваленттілік Толық жиындар және дәрежелер	13. Креативті және продуктивті жиындар	№25 СОБӨЖ. Тақырыбы: Файылға шығаруды программалау. Есептер шығару. Файылды шығару үшін ашу: жазу, қайта жазу, қосу. Негізгі инструкциялар. №26 СОБӨЖ. Тақырыбы: .Мәліметтерді файылға шығаруға және мәліметтерді файылдан оқуға есептер шығару
14-апта
1-кредит сағаты (дәріс)	Жай жиындар	Максимальды жиындар	14. Жай және максимальды жиындар	№27 СОБӨЖ. Тақырыбы: Процедураларды программалау. Есептер шығару. №28 СОБӨЖ. Тақырыбы: Функцияларды программалау . Есептер шығару.
15-апта
1-кредит сағаты (дәріс)	Райс-Шапиро теоремасы	Райс-Шапиро теоремасы	15. Райс-Шапиро теоремасы	№29 СОБӨЖ. Тақырыбы: Коллоквиум. №30 СОБӨЖ. Тақырыбы: Консультация беру.

2.5 Әдебиеттер тізімі.

1. 
   Мальцев А.И. Алгоритмы и рекурсивные функций. М. Наука 1965
   
2. 
   Роджерс Х. «Теория рекурсивных функций и эффективная вычислимость» М., Мир, 1977
   
3. 
   А.Н. Колмогоров, А.Г. Драгалин «Математическая логика» Дополнительные главы: Учеб. Пособие.- М.: Изд-во Моск. Ун-та, 1984-120 ст
   
4. 
   Вирт Н. «Алгоритмы и структура данных» М.: Мир, 1989-360ст
   
5. 
   Фролов Г.Д., Кузнецов Э.И. Элементы информатики: Учеб. Пособие для пед. Инф-ов-М.: Высш. Школа 1989-304
   
6. 
   Игошин В.И. Математическая логикаи теория алгоритмов- Саратов: Изд-во Сарат. Ун-та 1991-256 ст
   
7. 
   Абель П. Язык Ассемблеря для IBM PC и программирования /Пер. с англ. Ю. В. Сальникова- М.: Высш. шк.,1992-447 с
   
8. 
   В.Э. Аладьев, Ю.Я. Хунт, М.Л. Шишаков. «Основы информатики» Учеб. пособие.- М.: Информационно-издательский дом «Филинъ», 1998-496 ст.
   
9. 
   Кудрявцев В.Б., Алешин С.В., Подколзин А.С. «Введение в теорию автоматов»- М.: Наука Гл. Ред. Физ-мат. лит.,-320стр
   

Қосымша әдебиеттер:

1. 
   Непейвода Н.Н. Прикладная логика. Новосибирск из-во НГУ, 2000
   
2. 
   Мендельсон Э «Введение в математическую логику» М., Наука, 1976
   
3. 
   Шенфильд Дж Математическая логика М., Наука, 1975
   
4. 
   Ершов Ю.Л. Теория нумераций. М., Наука, 1972
   
5. 
   Ершов Ю.Л. «Проблемы разрешимости и конструктивные модели» М., Наука 1980
   
6. 
   Ершов Ю.Л. «Определимость и вычислимость»Новосибирск, научная книга, 2003
   

2.8. Тақырыпта және емтихан бойынша студенттердің білімін бақылау үшін сұрақтар.