Дискреттік математика

Сипаттама: Пән студенттерге ғылыми және кәсіби қызметте компьютерлік модельдерді қолдануға бағытталған математикалық дайындықты ұсынады. Пән дискретті модельдер мен конфигурациялардың сандық параметрлерін бағалаудың тетігін құрайды және негізгі бөлімдерден тұрады: жиынтық теориялар, формальды логикалық теориялар және бульдік функциялар, Тюринг машиналары негізінде алгоритм тұжырымдамасын қалыптастыру, графика теориясына кіріспе.

Кредиттер саны: 3

Пәннің еңбек сыйымдылығы:

Жұмыс түрлері	сағат
Дәрістер	30
Практикалық жұмыстар	30
Зертханалық жұмыстар
СӨЖО	15
СӨЖ	15
Қорытынды бақылау нысаны	емтихан
Қорытынды бақылауды жүргізу нысаны

Компонент: ЖОО компоненті

Цикл: Базалық пәндер

Мақсат

• Аппаратты-бағдарламалы комплекстерді және басқа да жобалы-құрамалы және жобалы –технологиялық қызметке ақпараттық және бағдарламалық кешенді жобалау үшін маман дайындау.

Міндет

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

Оқыту нәтижесі: білу және түсіну

• Ой өрісі кең және ойлау мәдениетіне ие жоғарғы білімді тұлға қалыптастыруға мүмкіндік туғызатын дискретті математика аумағында базалық ілімді меңгеру
• Заманауи математиканың және оның құрылымының негізін түсіну

Оқыту нәтижесі: білім мен ұғымды қолдану

• Есептеу жүйесі мен желісінің санімділігі мен қауіпсіздігін бағалай білу; ғылыми зерттеулерде және қызметтің басқа да түрлерінде математикалық үлгілеу әдістерін, ақпараттық технологияларды қолдану әдістерін білу
• Ғылыми зерттеулерде және қызметтің барлық түрлерінде математикалық үлгісін, әдісін, ақпараттық технологияны қолдану және білу

Оқыту нәтижесі: талқылай білуді қалыптастыру

• Математика облысында жаңа ғылыми есептерді қою; ғылым мен техниканың әртүрлі есептерін шешу кезінде заманауи математикалық әдістерді қолдану

Оқыту нәтижесі: коммуникативтік қабілеттіліктер

• Математика саласындағы теориялық және қолданбалы ғылыми зерттеу жүргізу керек; математика саласы мен оның қолдануында халықаралық бірлестікте, жеке және ұжыммен жұмыс істеуге қабілетті

Оқыту нәтижесі: Оқу дағдылары немесе сабаққа қабілеттілігі

• Қазіргі математиканың фундаменталды негізі мен оның логикалық құрылымын түсіну және білу

Оқыту әдістері

лекции и онлайн-лекции, практические занятия с применением слайдов и других средств мультимедиа, в частности, использование платформы Open edX. Интерактивные методики обеспечиваются решением индивидуальных задач студентами и коллективным обсуждением результатов и методов решения.

Дәріс сабақтарының тақырыптары

• Основные понятия теории множеств (в основном повторение): множества, способы задания, операции над множествами и их свойства, декартово (прямое) произведение
• Элементы комбинаторики
• Булевы функции
• Двойственные функции, принцип двойственности
• Монотонные функции
• Необходимость формализации логики
• Теория алгоритмов и сложность вычислений
• Разновидности машин Тьюринга: многоленточные, двухсторонние, с разными алфавитами
• Частично рекурсивные функции, совпадение с классом функций, вычислимых на машинах Тьюринга
• Другие формализации – алгорифмы Маркова, машины Шёнфилда, РАМ-машины и др
• Алгоритмически неразрешимые проблемы: проблема остановки, примеры из логики
• Сложность вычислений
• Теория графов
• Изоморфизм графов
• Простые экстремальные алгоритмы на графах: Дейкстры, Прима и Краскала

Негізгі әдебиет

• С.В. Яблонский Введение в дискретную математику.– М., Наука, 2019.
• С.В. Судоплатов, Е.В. Овчинникова Дискретная математика, Новосибирск, 2017.
• И.В. Латкин Дискретная математика с элементами математической логики. Усть-Каменогорск, ВКГТУ, 2016.
• Ф.А. Новиков Дискретная математика для программистов.–СПб: Питер, 2011.
• В.А. Емеличев и др. Лекции по теории графов.– М.: Наука. 2010.
• Г.П. Гаврилов, А.А. Сапоженко Задачи и упражнения по курсу дискретной математики.– М.: Наука, 2012.
• А.И. Мальцев Алгоритмы и рекурсивные функции.– М.: Наука, 2012.
• А.А. Зыков Основы теории графов.– М.: Наука. 2013.
• А.Е. Андреев и др. Дискретная математика: прикладные задачи и сложность алгоритмов. М.: Юрайт, 2019. – 317 с.
• В.Н. Крупский, В.Е. Плиско. Математическая логика и теория алгоритмов: Учебное пособие для студентов учреждений высшего проф. образования. М.: ИЦ Академия, 2013. – 416 с.

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

• М.О. Асанов, В.А. Баранский, В.В. Расин Дискретная математика: графы, матроиды, алгоритмы. – Москва, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2011.
• И.А. Лавров, Л.Л. Максимова. Задачи по теории множеств, математической логике и теории множеств. М.: Наука, 2015.
• А.С. Морозов, Н.Г. Хисамиев. Теория алгоритмов. ВКГТУ, 2014.
• И.В. Латкин Дискретная математика. – Методические указания и задания по выполнению контрольных работ заочной формы обучения. Усть-Каменогорск, ВКТУ, 2003.