Жоспарының негізінде құрастырған: Байсалова М. Ж., доцент
жүктеу/скачать 348,49 Kb. Pdf көрінісі
|
| Қазақстан Республикасының Білім және Ғылым Министрлігі Коммерциялық емес АҚ «Алматы энергетика және байланыс университеті» Радиотехника және байланыс факультеті Жоғары математика кафедрасы
БЕКІТЕМІН РТжБФ деканы ___________________Ұ.Ы.Медеуов «27» маусым 2016 ж.
Пәннің силлабусы DM 2206 - Дискретті математика 5В060200 –Информатика мамандығы
Курс
2 Семестр
3 Кредиттер саны ECTS–гі барлық кредиттер 2 3 Барлық сағат саны соның ішінде 90 Дәрістер 15 Машықтану сабағы 15 СӨЖ
60 соның ішінде СОӨЖ 15 ЕГЖ
2 Емтихан
Алматы, 2016
2
Силлабусты 5В060200 «Информатика» мамандығының жұмыстық оқу жоспарының негізінде құрастырған: Байсалова М.Ж. , доцент.
Силлабус «Жоғары математика» кафедрасының мәжілісінде қарастырылды және мақұлданды. Хаттама №9 «8» маусым 2016 ж.
Кафедра меңгерушісі________________ Байсалова М.Ж.
Силлабус Радиотехника және байланыс факультетінің оқу-әдістемелік комиссиясымен қаралып мақұлданған ( 27 маусым № 4 хаттама 2016 ж.)
3
№ Мұғалімдердің тізімі Қызметі каб
тел E-mail 1 Байсалова Маншук Жумамуратовна Доцент Б22
8 2 92 99
71
vm@aipe t. kz
2 Абдулланова Жанар Советкалиевна Аға оқыт 3
4
2 Аудиториялық сабақтардың жүргізілу уақыты және орны сабақ кестесінде көрсетілген, СОӨЖ консультация кестесі Аэроғарыш және ақпараттық технологиялар факультеттің деканаты (Д 409) және ЖМ кафедрасының (Б 228) ақпарат тақталарында көрсетілген.
алгоритмдері мен нәтижелерін таныстыру арқылы студенттердің бағдарламалық өнімдерді жасауға және нақты құбылыстарды пішіндеуге дағдыландыру болып табылады. 3.2 Пәннің мәселесі - студенттерге белгілі ұғымдар мен нәтижелерді (анықтамалар, теоремалар, олардың дәлелдеулері, олардын ара қатынастарын, есептерді шешу әдістерін) жеткізу ғана емес, аталған ұғымдарды табысты колдануға үйрету болып табылады. Сонымен бірге оқушылардың логикалық ойлау қабылетін жетілдіру және математиканы игеруге қажетті математикалық мәдениетті қалыптастырып, олардың математикалық түйсігін (сапалық, аналитикалык және геометриялық) жетілдіру болып табылады. 3.3 Пәнді сипаттау «Дискретті математика» курсының бағдарламасы КЕАҚ АЭжБУ 5В060200 «Информатика» мамандығына арналған оқу жоспары негізінде модулдер түрінде (пәннің
тараулары) жасалды. 5В060200 «Информатика» мамандығының барлық студенттері оқу жоспарындағы жалпы кредиттер санына сай 2 модуль оқиды. Әрбір модульдің мазмұны мен көлемі студенттердің жас ерекшелігін және аттестация графигін ескере отырып жасалды.
Пәнді зерделеу нәтижесінде студенттің:
Казақстанда, сондай-ақ шетелдегі дискретті математика аймағындағы ғылыми бағыттар мен мектептердің бар болуы туралы,
даму бағыттары туралы түсінігі болуы тиіс; дискретті математиканың негізгі ұғымдарын: Сандар теориясының алгоритмін және комбинаторикалық сұлбаларды, графтар теориясының негізгі ұғымдары мен нәтижелерін, логикалар алгебрасының негізгі ұғымдары, сонымен қатар дискретті математиканың алгоритмдерін ұсыну әдістерін білуі тиіс; 4 бірінші және екінші ретті салыстырулардың шешімін табу, салыстыру жүйелерін шешу, негізгі комбинаторлық принциптерді қолдана білу, МДҚФ және МКҚФ құру, белгілі буль функцияларына Жегалкин полиномын құру. қабілеті болуы тиіс; -
қолданбалы есептерді классикалық математикалық есептерге келтіріп шешуде
-
машықтану есептерін шешкенде қолайлы әдісті табуда ептілігі болуы тиіс; дискретті математиканың алгоритмдерімен байланысты кәсіби қызмет сұрақтарда
алгебра, Математикалық талдау. 3.5 Пәннің постреквизиттері: Ықшамдаудың әдістері және операцияларды зерттеу, Шешімді қабылдау теориясы, Желілік операциялық жүйелер, Желілерді басқару.
4.1 Теориялық дайындық Тақырып
№ Дәріс тақырыбы әдеб
Ақырлы жиындар комбинаторикасы Жиындар және оларға колданылатын амалдар. Жиындар алгебрасының тепе-теңдіктері. Қосу және көбейту принципі. Ішкі жиынның мінездемелік функциясы. Кіріс- шығыс принципі. Дирихле принципі және оны колдану үлгілері. Бейнелеулер және олардың түрлері. Бинарлық қатынастар және оларға қолданылатын амалдар. Ньютон биномы. Бином коэффициенттерінің қасиеттері. (2 сағат) 7, 12, 16
2 Реккуренттік қатынастар. Туындатушы функциялар Рекуренттік қатынастар. Ақырсыз тізбектер алгебрасы, Фибоначчи және Каталан сандары. Юнг теоремасы. Белл және Мерсенн сандары, Туындатушы функциялар және оларға қолданылатын амалдар, Элементар туындатушы функциялар және олар
анықтайтын қатарлар. Туындатушы функцияларды көбейту. Орам амалы. (1сағат) 7, 12, 16
3 Сандар теориясынын алгоритмдері Бүтін сандар сақинасы. Қалдықпен белу туралы теорема. Евклид алгоритмі. Жай және к¥рама сандар. 7, 12,
16 5 Арифметиканың негізгі теоремасы. Өзара жай сандар және олардың қасиетгері. Ферма және Эйлер теоремалары. Қалдықтар туралы Қытай теоремасы. (2 сағат) 4
Салыстырулар және олардың қасиетгері. Қалындылар сақинасы. Қалындылар сақинасының өріс болу шарты. Ақырлы өрістерді құру. Ақырлы өрістегі примитивті элементтерді табу алгоритмі. (2 сағат) 7, 12, 16
5 Графтар теориясының элементтері Граф
ұғымы. Мысалдар. Графтардың түрлері. Графтардың берілу
жолдары. Эйлерлік және гамильтондық графтар. Ағаштар. Графтың хроматикалық саны. Жазық графтар туралы Эйлер теоремасы. Понтрягин-Куратовский теоремасы. (2 сағат) 7, 12,
16 6
Шкірлер, ақикаттык кесте. Формулаларды тепе-тең түрлендіру. Қалыпты формалар. Предикат және терм ұғымы. Кванторлар жэне формулалар. Модел ұшмы. Моделдегі формулалардың орындалуы. Формулалардың парапарлығы. Универсал және хорн формулалары. Эрбран термдері, сколемизация. Алгоритм ұғымы. Тъюринг машиналары. Математикалык дәлелдеу әдістері. (2 сағат) 7, 12,
16 7
Буль алгебрасы. Буль функциялары. Буль функцияларының саны туралы
лемма. Буль
алгебрасынағы негізгі тепе-теңдіктер. МДНФ және МКНФ.
Жегалкин полиномдары. Жегалкин теоремасы. Буль функцияларының негізгі кластары. Логикалык амалдардың толык жүйелері. (2 сағат) 7, 12,
16 8
Тарихи шифрлар. Алмастыру жэне ауыстыру шифрлары. Ашык кілтгі шифрлар және оларды ашу алгоритмдеріне шолу. (1 сағат) 7, 12,
16 9
Кодтау схемаларына шолу. Макмиллан теңсіздігі. Деректерді сығу. Лемпел-Зив алгоритмі. (11 сағат) 7, 12, 16
4.2 Машықтану дайындық 4.2.1 Машықтану сабақтардың тақырыптары Тақырып
№ тақырып
әдеб
1 Жиындар және оларга қолданылатын амалдар. 7, 12,
6 Қосу және көбейту принциптері. (2 сағат) 16, 13
2 Ішкі жиынның мінездемелік көпмүшелігі. Кіріс-шығыс принципі. (2 сағат) 7, 12,
16, 13
3 Дирихле принципі және оны қолдану үлгілері. Бинарлық қатынастар және оларға қолданылатын амалдар. (2 сағат) 7, 12, 16,
13 4 Ньютон биномы. Бином коэффициенттерінің касиеттері. Рекуренттік қатынастар. Фибоначчи және Каталан сандары. (2 сағат) 7, 12, 16,14
5 Элементар туындатушы функциялар және олар анықгайтын қатарлар. Туындатушы функцияларды көбейту. Орам амалы. (2 сағат) 7, 12,
16,14 6 Графтардың берілу жолдары. Эйлерлік және
гамильтондык графтар. Ағаштар. Графтық хроматикалык саны. Жазық графтар туралы Эйлер теоремасын қолдану. (2 сағат) 7, 12,
16, 15
7 Бүтін
сандар және
қалындылар сақиналары. Салыстырулар. Ферманың кіші теоремасы. Эйлер теоремасы. (2 сағат) 7, 12, 16,
15 8 Қалдыктар туралы қытай теоремасы. Жегалкин полиномдарын құру. (1 сағат) 7, 12,
16, 15
4.3 Есептеу-сызба жұмыстарының тізімі: ЕСЖ № 1. Жиындар, қатынастар. Орындалуы [13, 14] әдістемелік нұсқамаға сәйкес орындалады. Тапсырма семестрдің бірінші аптасында беріледі, бесінші аптада тапсырылады.
орындалады. Тапсырма семестрдің оныншы аптасында беріледі, он бесінші аптада тапсырылады.
1.
Эрдеш-Шекереш теоремасы. 2.
Фибоначчи сандарының туындатушы функциясын табу, 3.
Каталан сандарының туындатушы функциясын табу. 4.
Қалындылар сақинасындағы нөлдік бөлгіштері, нильпотентті және керіленетін элементтер. Идеалдар мен гомоморфизмдер. 5.
6.
Галуа өрістерін құру. Галуа ерістеріндегі есептеулер. 7.
Ашық кілтті криптография есептерінің мысалдары. 8.
Кодтау теориясының есептерінің мысалдары. 7 9. Сызыкты реккурентгі формулалар.
1.
Бөліктеу теоремасын қолдану. 2.
Алмастырулар, орналастырулар және терулер, 3.
Ақырлы топтарға арналған Лагранж теоремасы. 4.
Классикалық алгебралық жүйелер. 5.
Ақырлы топтар. 6.
Ақырлы өрістерді кұру. 7.
Ақырлы өрістерде есептеулер. 8.
Галуа өрістерінің ішкі өрістері. 9.
Ақырлы өрістің примитивті элементтерін табу алгоритмдері,
Әрбір студент өз нұсқасын орындау керек.
1 Тұжырымдардың қайсысы дұрыс? 1. . а)
7 1, 7
, с)
7 1,5, 7 , в)
7 1, 7
, д)
7 1,5, 7
2 Берілген жиынды элементтерін тізу арқылы жазыңыз 2. {x | 8-ден кіші сандар жиыны} 3 Берілген жиынды жалпы қасиеті бойынша жазыңыз 3.
1 1 1 1 1 , , , , 1 4 8 16 32
4 А және В жиындары берілген. Табу керек:4) A B , 5) A B , 6) \ A B , 7)
A B
4-7. , , , , , , A b c d e f g h
, , , , , , , B c d e f k l g h
8-9 Эйлер-Венн диаграммасы арқылы жиынды суреттеңіз. 8.
A B 9.
B C 10
Эйлер-Венн диаграммасы арқылы тепе- теңдікті дәлелдеу керек. 10.
\ \ ( \ )
A B C A C B C
11- 16 А және В жиындары, Р қатынасы берілген. Табу керек:11)
(тура көбейтінді), 12) 2
A A ). 13) В жиыны үшін қандай да бір бүркеуін 14) А және В арасындағы Р қатынасын график түрінде көрсетіңіз, 15) Р қатынасының матрицасын табыңыз 16) 1
(Р кері) бинарлық қатынасты табыңыз 11-16
, , 4,5, 6, 7 , 4 , ,5 ,
, 6 , , 7 ,
, 4 A c d e B P c c d d e
5.2 Екінші аралық бақылау үлгісі (АБ 2) 1-2. y x
1.Логикалық операция қалай аталады және оқылады? 2.Оның ақиқаттық таблицасын құрыңыз. 3.
3. Формуланың ақиқаттық таблицасын құрыңыз. 4. (0110 1100) 4. Функцияның мәндерінің векторы б-ша оның ақиқат. табл. құрыңыз 8 5. y x , Де-Моргана заңы
5. Берілген формулаға көрсетілген заң бойынша эквивалентті формуланы табыңыз. 6.
) ( ) ( z y x z y
6. Формула төмендегі форманың қай түрінде жазылған: а)ДҚФ; б)МДҚФ; в)КҚФ; г)МКҚФ. 7-8.
z y x
7-8. Формуланы ДҚФ келтір. 9-12.
1 ) 1 , 0 , 1 ( ) 1 , 0 , 0 ( ) 0 , 1 , 0 ( ) 1 , 1 , 1 ( f f f f
9-12. Функцияның бірлік жиынтығы берілген. 9. Функцияның МДҚФ құрыңыз.10. Функцияның ақиқаттық табл. құрыңыз.11. Карно картасын құрыңыз.12. Карно картасы бойынша минималды ДҚФ табыңыз.
13-16. Схема берілген.13.Ауыстырмалық функцияны құрыңыз.14-15. Ауыстырмалық функцияны қысқартыңыз.16.Қысқартылған схеманы сызыңыз.
1. Жиындар, берілу тәсілдері. Жиынмен орындалатын операциялар. 2. Жиындарға орындалатын операциялардың қасиеттері. Жиындардың бөліктеуі мен бүркеуі. 3.Жиындардың тікелей көбейтіндісі. Қатынастар (унарлық, бинарлық, n- аралық қатынастар). Бинарлық қатынастың берілу тәсілдері. Кері қатынас, қатынастың толықтауышы, тепе-тең қатынас. Бинарлық қатынастардың композициясы. 4. Дирихле принципі және оның қолданылуы. 5. Эквиваленттік қатынас. Эквиваленттілік класы, фактор-жиын. 6. Реттік қатынастар. Лексикографиктік реттілік. 7. Белл және Мерсенн сандары. 8.Логикалық айтылымдардың негізгі ұғымдары. Айтылымдар, негізгі логикалық. операциялар. 9. Логикалық айнымалылар мен формулалар. Логикалық операциялардың ақиқаттық кестесі. Логикалық операциялардың орындалу реті. 10.
(ақиқаттық кестесі, нөлдік және бірлік жиынтықтар, мәндео векторы, формула). 11.
эквивалентті қарым қытынастар. 12. Логикалық функциялардың толық жүйесі. Логикалық формулаларды ДҚФ және КҚФ келтіру. 13. Мүлтіксіз ДҚФ және КҚФ (МДҚФ, МКҚФ). 14.
15. Коммутациалық сұлбалар. 16 Екі жақтылық. Буль алгебрасы және жиындар теориясы. 9 17. Графтар теориясының негізгі ұғымдары мен анықтамалары. 18. Графтардың берілу тәсілдері. ( ( , )
қос жиыны, сурет, инциденттік матрицасы, қабырғалар (доғалар) тізімі). 19. Графтар изоморфизмі. Ішкі графтар. Графтарға қолданылатын операциялар. 20. Маршрутар, шынжырлар, жолдар, циклдар, контурлар. Байланыстылық, мықты айланыстылық, байланыстылық компоненттері. 21. Байланыстылық және мықты айланыстылық компоненттерін анықтау. Жетерлік матрицасы. 22. Графта маршруттарды іздеу . 23. Орграфтағы мықты компоненталарды табу. 24. Графтағы ара қашықтық. (эксцентриситет, диаметр, радиус, центр). 25. Қысқа жол туралы есеп. 26. Ағаштар, олардың қасиеттері. Діңгекті ағаштар. Орман. 27 Фибоначчи және Каталан сандары. 28 Ферма кіші теоремасы. 29 Эйлер теоремасы. 30 Қалдық туралы Қытай теоремасы. 31 Жегалкин көпмүшелігін құру.
Сіздің
білім деңгейіңіз оқудың кредиттік технологиясында қабылданған курс бағдарламасы бойынша қорытынды бағалар шкаласына сәйкес бағаланады (1 – кесте).
1 – кесте Баға
Балдың сандық эквиваленті Пайыздық мазмұны
Бағаның бұрынғы түрі А 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 Қанағаттанарлықсыз
10
Рұқсат рейтингісінің бағасы семестр
бойына жинақталады. Жұмыстардың әр түрі 100 баллдық шкаламен бағаланады және 2 – кестеге сәйкес коэфиициенттік деңгей рұқсаты ағымдағы бақылаудың орташа бағасына қосылады. 2 – кесте. Әр жұмыс түрінің маңыздылығы (орта арифметикалық мән)
Зертханалық жұмыстары жоқ пәндер үшін коэффициент салмағы Зертханалық жұмыстары бар пәндер үшін коэффициент салмағы Есептік-сызба жұмыстың машықтану бөлімін тексеру және қорғау 0,4 0,3
Есептік-сызба жұмыстың теориялық бөлімін қорғау 0,4 0,3
Аудиториялық сабақтарға қатысуы
0,2 0,1
Зертханалық жұмыстардың орындалуы – 0,3
Ағымдағы бақылаудың орташа бағасы (Ор) 1,0
1,0
Аралық бақылау (АБ) академиялық күнтізбеге сәйкес семестрде екі рет өткізіледі. Әр АБ (А1 және А2) 100-баллдық шкаласымен бағаланады, ақпараттық жүйемен АБ бағасының орташа мәні есептеледі Б ор
1 +Б 2 )/2 және 0,2 салмақ коэффициентпен қабылдау бақылауына қосылады: БР = 0,2Бор+0,8Ор.
Пән бойынша қорытынды баға шығарылады Қ=0,6БР+0,4Е, Е – емтихандық бағасының сандық баламасы. 6.2 Баллдың қойылу саясаты: Максималды бағалар жұмыстың сапасына және орындалуына карап қойылады. Тесттілік тапсырмалардың және дәріске қатысу бағалары тесттің дұрыс жауаптар санына және жіберілген дәрістік сабақтардың санына байланысты қойылады.
Әріптік баға және оның сандық эквиваленті балл бойынша дұрыс жауаптар пайыздық мазмұнымен, төменде көрсетілген кестеге сәйкес анықталады. 3 – кесте
11
бағалар бағалар эквиваленті A A 4,0 100 Өте жақсы B B+
3,33 85
Жақсы C B 3,0 80 D C 2,0 65 қанағаттанарлық E D 1,0 50 FX, F F 0 0 Қанағаттанарлықсыз
15.
– кесте. Балды – рейтингтік әріптік РК баға жүйесіне сәйкес ECTS бойынша бағалар
Әріптік системадағы баға
Балдың сандық
эквиваленті Пайыздық мазмұны Бағаның бұрынғы түрі ECTS
бойынша баға А 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 Қанағаттанарлық D С-
1,67 60-64
D+ 1,33
55-59 D 1,0 50-54 Қанағаттанарлық E F
0-49 Қанағаттанарлықсыз FX, F
Оқып жүргендер пән бойынша Р
50% төмен алғандар, Retake өтулері міндетті (қайталап оқу және тапсыру). Қорытынды бақылау – ауызша емтихан. Емтихан сұрақтары мен тапсырмалары теориялық және практикалық бөліктеріне қатысты дәрістік сабақтардың зерттеу жұмыстарына қатысынсыз анықталады, 1:1тең болады. 7 Курс саясаты: - сабаққа кешікпеу және сабақты жібермеу; - мұғалімнің ұсынған дәрісін мұқият тыңдау; - сабаққа белсенді түрде қатысу; - белгілі себептермен жіберілген зертханалық сабақтарды өтеу ( деканаттан жеке рұқсат қағазы болған жағдайда); 12
- ЕСЖ пән бойынша тапсырмаларды орындау кестесінде көрсетілген мерзімде өткізу; - кітапханада және үйде өз бетімен оқу.
- ұқыптылық; - адалдық; - жауапкершілік; - дәрісте ұялы телефондарды өшіріп жұмыс істеу Түсініспеушілік тудыратын жағдайлар оқу топтарында оқытушымен, эдвайзермен ашық талқылануы керек, ал түсіністікке қол жеткізілмесе бұл мәселе деканат қызметкерлеріне жеткізілуі керек.
1.
Новиков Ф. А., Дискретная математика для программистов., СПб, Питер, 2001.
2.
Судоплатов С.В., Овчинникова Е.В., Элементы дискретной математики, М, Инфра - М, 2002 3.
Гаврилов Г.П., Сапоженко А.А., Задачи и упражнения по курсу дискретной математики. М, Наука, 2002. 4.
математической логике и теории алгоритмов, М, Наука, 2006. 5.
Р.Грэхем, Д.Кнут, О. Паташник, Конкретная математика, М, Мир, 2001 Қосымша қолданатын әдебиеттер: 6.
Яблонский С.В. Введение в дискретную математику, М., Наука, 2008 г. 7.
Досанбай П.Т. Математикалық логика, Алматы, Дәуір, 2011 ж. 8.
Емеличев В.А.и другие, Лекции по теории графов, М, Наука, 2004. 9.
Оре О., Теория графов , М., Наука, 2006 г. 10.
Холл М. Комбинаторика, М., Мир, 2003 г. 11.
Физматлит, 2000 12.
Жетпісов Қ. Математикалық логика және дискретті математика. Алматы, 2011
13. Астраханцева Л.Н., Байсалова М.Ж. Дискрет математика. 050704 – Есептеу техникасы және бағдарламалық қамтамасыз ету мамандығы бойынша оқитын барлық бөлім студенттері үшін есептеу-графикалық жұмыстарды орындауға арналған әдістемелік нұсқаулар мен тапсырмалар. 1 бөлім - Алматы: АЭжБИ, 2008. - 16 б. 14. Астраханцева Л.Н., Байсалова М.Ж. Дискрет математика. 050704 – Есептеу техникасы және бағдарламалық қамтамасыз ету мамандығы бойынша оқитын барлық бөлім студенттері үшін есептеу-графикалық жұмыстарды орындауға арналған әдістемелік нұсқаулар мен тапсырмалар. 2 бөлім - Алматы: АЭжБИ, 2008. - 22 б.
13
15. Астраханцева Л.Н., Байсалова М.Ж. Дискрет математика. 050704 – Есептеу техникасы және бағдарламалық қамтамасыз ету мамандығы бойынша оқитын барлық бөлім студенттері үшін есептеу-графикалық жұмыстарды орындауға арналған әдістемелік нұсқаулар мен тапсырмалар. 3 бөлім - Алматы: АЭжБИ, 2008. - 57 б. 16. Байсалова М.Ж Дискрет математика: оқу құралы – Алматы, АЭжБИ. 2007. - 76 бет. жүктеу/скачать 348,49 Kb. Достарыңызбен бөлісу:
|