ПӘн бойынша оқыту бағдарламасы (Syllabus)

Бағдарлама «___»_________20__ж. бекітілген жұмыс оқу бағдарламасының негізінде әзірленген.

20__ж. «___»____________кафедра отырысында ұсынылған №_____ Хаттама

Кафедра меңгерушісі__________М.Е.Исин 20__ж. «___»____________
Физика,математика және ақпараттық технологиялар факультетінің оқу-әдістемелік кеңесімен мақұлданған 20__ж. «___»_____________Хаттама №___
ОӘК төрағасы ________________ Ж.Ғ.Мұқанова 20__ж. «___»_______________

КЕЛІСІЛГЕН

Құдайберген Маржан Құдайбергенқызы

Аға оқытушы

Математика кафедрасы А1 корпусында, А1-211 аудиторияда орналасқан. Байланыс телефоны: 67-36-46 , ішкі тел: 1-120.

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

Студенттерді қолданбалы есептерді шығаруға бағытталған, математикалық әдістермен модельдердің, тілдердің өзара тығыз байланысқан жиынтығы ретінде қарауға болатын математикалық аппаратпен қаруландыру.

- дискретті математиканың мынадай объектілерін: логикалық функциялар, алгоритмдер, графтар, кодтау теориясының негізгі ұғымдарын меңгерту;

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

5 Білімге, икемділікке және машықтарға қойылатын талаптар

Курсты оқыту нәтижесінде студенттер міндетті:

- дискретті математиканың мынадай объектілерін: логикалық функциялар, алгоритмдер, графтар, кодтау теориясының негізгі ұғымдарын меңгеру;

- программалау процесінде жасанды интеллект есептерін шығаруда, программалардың дұрыстығын дәлелдеуде модельдеуді пайдалануға дағдылану.
6 Пререквизиттер

- Математикалық анализ

- Алгебра және геометрия

- Жиындар теориясы

Осы пәндер бойынша толық білімдері қажет.

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

Курстың оқу нәтижесінде алған білім, икем, дағдылары келесі салалардың негізі болып табылады:

-программалау тілдері;

-автоматтандырылған басқару және жобалау жүйелері.

Компьютерлік ғылымның теориялық фундаменті болып саналатын дискретті математика арқылы сипаттағы құрылымдар қасиеттерін зерттейтін математиканың бір саласы болып саналады. Оның жедел қарқынмен дамуы есептеу техникасын автоматты өңдеу және тарату жабдықтарын жасау және табиғатында арқылы құрылымды модельдерді компьютерде бейнелеу қажеттігімен байланысты.

Жиын, ішкі жиын және элементтер. Жиындар алгебрасының тепе-теңдігі. Декарттық көбейтінді және қатынастар. Қатынастардағы амалдар. Функциялар. Эквиваленттік қатынас және реттік қатынас. Дирихле принципі. Эрдели-Шекерели теоремасы. Ретсіздіктер саны. Кіріс-шығыс формуласы. Бином коэффициенттері. Ақырлы жиындардағы функциялар. Инъекциялар, сюръекциялар, биекциялар және олардың мөлшері. Математикалық индукция. Фибоначчи сандары және олардың қасиеттері. Рекурентті қатынастар. Ақырсыз сандық тізбектердің алгебрасы. Шығарушы функциялар және олардың қасиеттері. Юнг теоремасы. Белл сандары. Мерсенн сандары. Жетілген сандар.

Салыстыру. Мультипликативті функциялар. Эйлер және Ферма теоремалары. Сызықты диофантты теңдеулер. Жақшаларды ассоциативті емес түрде орналастыру. Каталан сандары. Жақшаларды коммутативті түрде орналастыру. Кармайкл сандары. Жай сандарға компьютерлік тест. Ашық кілтті криптожүйе.

Пікірлерге логикалық амалдар. Формулалар. Формулалардың ақиқат мәндері. Ақиқат таблицалары бойынша формулаларды қайта тұрғызу. Формулаларды тепе-тең түрлендіру. Де-Морган заңдары, қарсыпозиция, екі рет терістеу. Дизъюнктивті және конъюнктивті қалыпты формалар. Логикалық байланыстардың толық жүйесі. Формальді жүйелер. Пікірлерді есептеудің аксиомалары мен шығару ережелері. Формулалардың дәлелденуі. Жорамалдан формулаларды шығару. Дедукция теоремасы. Шығарым туралы лемма. Кальмар леммасы. Пікірлерді есептеудің толықтығы. Пікірлерді есептеудің қайшылықсыздығы.

Модельдер. Бекітілген сигнатуралы термдер. Предикаттар логикасының атомарлы формулалары, еркін және байланысқан айнымалылар, кванторлар. предикаттар логикасының формулалары.

Модельдердегі формулалардың орындалымдылығы. Предикаттар логикасындағы формулалардың тепе-теңдігі және негізгі тепе-тең түрлендірулер. Пренекс қалыпты формасы. Формулалардың жалпымәнділігі мен орындалымдылығы. Бірінші ретті модельдер теориясы. Модельдер автоморфизмі. Арифметика моделінің фрагментінде қатынастардың анықталымдылығы. Кейбір арифметикалық қатынастардың анықталмайтындығын дәлелдеудің Падоа әдісі. Предикаттарды есептеу. Предикаттарды есептеудің формальді жүйесі. Предикаттарды есептеудің аксиомалар жүйесі. Шығару ережесі. Дәлелденетін формулалар және формулаларды жорамалдар жиынынан шығару. Таптаурынның жеке жағдайының дәлелденуі. Предикаттарды есептеудегі дедукция теоремасы. Теорияны аксиомалық түрде құру. Пеано арифметикасын аксиомалық түрде құру. Пеано арифметикасында заңдарды формальді құру мысалдары.

5 тақырып. Алгоритмдер теориясының элементтері

Тьюринг машинасы. Қарапайым сандық функцияларды есептеу программасы. Тьюринг машинасының композициясы.

Жиын, ішкі жиын және элементтер. Жиындар алгебрасының тепе-теңдігі. Декарттық көбейтінді және қатынастар. Қатынастардағы амалдар. Функциялар. Эквиваленттік қатынас және реттік қатынас. Кіріс-шығыс формуласы. Бином коэффициенттері. Инъекциялар, сюръекциялар, биекциялар және олардың мөлшері. Математикалық индукция. Фибоначчи сандары және олардың қасиеттері. Ақырсыз сандық тізбектердің алгебрасы. Шығарушы функциялар және олардың қасиеттері.

Салыстыру. Мультипликативті функциялар. Сызықты диофантты теңдеулер. Жақшаларды ассоциативті емес түрде орналастыру. Каталан сандары. Жақшаларды коммутативті түрде орналастыру. Кармайкл сандары. Жай сандарға компьютерлік тест. Ашық кілтті криптожүйе.

Пікірлерге логикалық амалдар. Формулалар. Формулалардың ақиқат мәндері. Ақиқат таблицалары бойынша формулаларды қайта тұрғызу. Формулаларды тепе-тең түрлендіру. Де-Морган заңдары, қарсыпозиция, екі рет терістеу. Дизъюнктивті және конъюнктивті қалыпты формалар. Логикалық байланыстардың толық жүйесі. Формальді жүйелер. Пікірлерді есептеудің аксиомалары мен шығару ережелері. Формулалардың дәлелденуі. Жорамалдан формулаларды шығару. Дедукция теоремасы. Пікірлерді есептеудің қайшылықсыздығы.

Предикаттар логикасының атомарлы формулалары, еркін және байланысқан айнымалылар, кванторлар. предикаттар логикасының формулалары.

Предикаттар логикасындағы формулалардың тепе-теңдігі және негізгі тепе-тең түрлендірулер. Предикаттарды есептеу. Предикаттарды есептеудің формальді жүйесі. Предикаттарды есептеудің аксиомалар жүйесі. Шығару ережесі. Дәлелденетін формулалар және формулаларды жорамалдар жиынынан шығару. Таптаурынның жеке жағдайының дәлелденуі. Предикаттарды есептеудегі дедукция теоремасы. Теорияны аксиомалық түрде құру. Пеано арифметикасын аксиомалық түрде құру. Пеано арифметикасында заңдарды формальді құру мысалдары.

5 тақырып. Алгоритмдер теориясының элементтері

Тьюринг машинасы. Қарапайым сандық функцияларды есептеу программасы. Тьюринг машинасының композициясы.

Ұсынылатын әдебиет: [1], [2], [5]

Ұсынылатын әдебиет: [1], [2], [5]

Ұсынылатын әдебиет: [1], [2], [4]

Ұсынылатын әдебиет: [1], [2], [7]

Ұсынылатын әдебиет: [1], [2], [8]

Студенттер міндетті түрде сабақтарға қатысу керек. Себеппен қатыспаған сабақтардың тапсырмаларын кешірек тапсыруға болады.

Кешігіп келген студенттерге сабаққа қатысуға рұксат берілмейді. Сабақта тәртіп бұзғаны үшін 5 балл шегеріледі.

Сабақтың барлық түріне (дәріс, тәжірибе, СОӨЖ) студент міндетті түрде дайындалып келуі керек. Студенттің білімі бақылау жұмысы, тест, межелік бақылау арқылы тексеріледі.

Тәжірибе және өзіндік жұмыстардың тапсырмалары міндетті түрде орындалуы керек.

Өзіндік жұмыс сіздің нұсқаңызға сәйкес орындалуы керек, әйтпесе жұмысыңыз есептелінбейді. Нұсқаңыздың номерін оқытушы анықтайды.

Берілген тапсырмалар уақытында орындалу керек, кеш орындалған тапсырмалар кемітіп есептелінеді. Кез келген бақылау түрінде және емтиханда көшіруге тыйым салынады. Бұл жағдайда алған баллыңыздың 80% шегеріледі.

Бір жағдайлар бойынша бақылау шарасына қатысалмай қалсаңыз, оны келесі жұма ішінде өтуіңізге мүмкіндік беріледі.

АҮ және МБ қорытынды бағалары бойынша студенттің пән бойынша рейтингі (Р1 және Р2) келесі формула бойынша анықталады

Пән бойынша студенттің семестрдегі кіру рұқсатының рейтингі (КРР) келесі формуламен есептелінеді

КРР = (Р1+Р2)/2.

Пән бойынша қорытынды бақылауға (ҚБ) жұмыс бағдарламасының барлық талаптарын орындаған және кіру рұқсатының рейтингі 50 баллдан кем емес студенттер жіберіледі.

Қорытынды бағаны (Б) келесі формула бойынша есептейді

Қ = КРР *0,6 + ҚБ*0,4
Қорытынды баға КРР және ҚБ бағалары қанағаттанарлық болса ғана есептелінеді. Қорытынды бақылауға келмеген жағдайда студентке «қанағаттанарлық емес» деген баға қойылады.

Емтиханның және аралық аттестацияның нәтижелері студентке сол күні, ал түстен кейін өтсе келесі күні жарияланады.

Бақылау түрлері: Т – тәжірибелік жұмыс, СӨЖ – студенттің өзіндік жұмысы, МБ – межелік бақылау.

Құрастырушы: математика кафедрасының аға оқытушысы М.Құдайберген

1. 
   Жетпісов Қ.Ж. Математикалық логика және дискретті математика. Е.Бөкетов ат. Қарағанды мемлекеттік университеті, 2011. – 262 б.
   
2. 
   Нұрсұлтанов Қ. Дискретті математикалық логика. Семей, 2002.-328 б.
   

3. 
   Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М.: Наука, 2004.
   
4. 
   Джумадильдаев А.С.. Элементы дискретной математики Ч1, S. Demirel Univ., Almaty, 2004.
   
5. 
   Судоплатов С.В., Овчинникова Е.В.. Дискретная математика. М.: Наука, 2003
   
6. 
   Дроботун Б.Н., Джарасова Г.С. Вводный курс математики.-Павлодар, 2004.-300 б.
   
7. 
   Яблонский С.В. Дискретті математикаға кіріспе. М.: Ғылым, 2002, 272 б.
   
8. 
   Тарасевич Ю.Ю. Элементы дискретной математики для программистов. Астрахань, 2002, 76с.
   
9. 
   Лавров А., Максимова Л.. Сборник задач по теории множеств, математической логике и теории. –М.: Наука, 2004, 240 с.