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

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

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

Компонент: Таңдау бойынша компонент

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

Мақсат
  • Аппаратты-бағдарламалы комплекстерді және басқа да жобалы-құрамалы және жобалы –технологиялық қызметке ақпараттық және бағдарламалық кешенді жобалау үшін маман дайындау.
Міндет
  • Студенттер графтар теориясынан, бульдік функциялар теориясынан, жиындар теориясынан, формальды есептеулерден негізгі білімді игеру керек.
  • Негізгі ұғымдар мен анықтамаларды қолданып, болашақ мамандыққа сәйкес есептердің математикалық моделін құру және талдауды қалыптастыру
Оқыту нәтижесі: білу және түсіну
  • Ой өрісі кең және ойлау мәдениетіне ие жоғарғы білімді тұлға қалыптастыруға мүмкіндік туғызатын дискретті математика аумағында базалық ілімді меңгеру
  • Заманауи математиканың және оның құрылымының негізін түсіну
Оқыту нәтижесі: білім мен ұғымды қолдану
  • Есептеу жүйесі мен желісінің санімділігі мен қауіпсіздігін бағалай білу; ғылыми зерттеулерде және қызметтің басқа да түрлерінде математикалық үлгілеу әдістерін, ақпараттық технологияларды қолдану әдістерін білу
  • Ғылыми зерттеулерде және қызметтің барлық түрлерінде математикалық үлгісін, әдісін, ақпараттық технологияны қолдану және білу
Оқыту нәтижесі: талқылай білуді қалыптастыру
  • Математика облысында жаңа ғылыми есептерді қою; ғылым мен техниканың әртүрлі есептерін шешу кезінде заманауи математикалық әдістерді қолдану
Оқыту нәтижесі: коммуникативтік қабілеттіліктер
  • Математика саласындағы теориялық және қолданбалы ғылыми зерттеу жүргізу керек; математика саласы мен оның қолдануында халықаралық бірлестікте, жеке және ұжыммен жұмыс істеуге қабілетті
Оқыту нәтижесі: Оқу дағдылары немесе сабаққа қабілеттілігі
  • Қазіргі математиканың фундаменталды негізі мен оның логикалық құрылымын түсіну және білу
Дәріс сабақтарының тақырыптары
  • Комбинаторика – 7 ч. Основные понятия теории множеств (в основном повторение): множества, способы задания, операции над множествами и их свойства, декартово (прямое) произведение. Комбинаторика: принцип умножения, принципы сложения и дополнения в форме правила включений и исключений, перестановки, размещения и сочетания.
  • Матлогика – 8 ч. Булевы функции и их свойства. Необходимость формализации. Исчисление высказываний как пример формальной логической системы. Предикаты и кванторы. Формальные логические теории. Применения в математике и информатике.
  • Теория алгоритмов и сложность вычислений – 9 ч. Интуитивное понимание алгоритма, его недостаточность. Формализация понятия вычислимой функции на основе машин Тьюринга. Другие формализации – частично рекурсивные функции (кратко < 1ч), алгорифмы Маркова, машины Шёнфилда, РАМ-машины и др. – упоминание; их равносильность для натуральных функций. Тезис Чёрча. Алгоритмически неразрешимые проблемы: проблема остановки, примеры из логики. Сложность вычислений. Полиномиальные и переборные алгоритмы. Проблема P = ? NP.
  • Теория графов – 6 ч.. Графы и их изображения (диаграммы). Обыкновенные (простые), ориентированные графы, мультиграфы. Степени (валентность) вершин, основные ограничения на степени. Изоморфизм графов. Эйлеровы и гамильтоновы обходы. Планарность. Деревья и их свойства. Способы задания графов в ЭВМ.
Негізгі әдебиет
  • С.В. Яблонский Введение в дискретную математику.– М., Наука, 2019.
  • С.В. Судоплатов, Е.В. Овчинникова Дискретная математика, Новосибирск, 2017.
  • И.В. Латкин Дискретная математика с элементами математической логики. Усть-Каменогорск, ВКГТУ, 2016.
  • Ф.А. Новиков Дискретная математика для программистов.–СПб: Питер, 2011.
  • В.А. Емеличев и др. Лекции по теории графов.– М.: Наука. 2010.
  • Г.П. Гаврилов, А.А. Сапоженко Задачи и упражнения по курсу дискретной математи-ки.– М.: Наука, 2012.
  • А.И. Мальцев Алгоритмы и рекурсивные функции.– М.: Наука, 2012.
Қосымша әдебиеттер
  • М.О. Асанов, В.А. Баранский, В.В. Расин Дискретная математика: графы, матроиды, алгоритмы. – Москва, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2011.
  • И.А. Лавров, Л.Л. Максимова. Задачи по теории множеств, математической логике и теории множеств. М.: Наука, 2015.
  • А.С. Морозов, Н.Г. Хисамиев. Теория алгоритмов. ВКГТУ, 2014.