Дискретная математика (КФ) — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Экзамен)
 
(не показаны 19 промежуточные версии 2 участников)
Строка 1: Строка 1:
 +
__NOTOC__
 +
<div style="max-width:940px">
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]
  
Курс для студентов 1-го курса Казахстанского филиала МГУ, читается во 2-м семестре. Лекции - 32 ч, семинары - 32 ч, отчетность - экзамен.  
+
Курс для студентов 2-го курса Казахстанского филиала МГУ, читается в 1-м семестре, 2 ч лекций и 2 ч семинаров в неделю, отчетность экзамен.  
 +
 
 +
==2025-2026 учебный год==
 +
 
 +
Лектор - [[Савицкий Игорь Владимирович]]
 +
 
 +
===Экзамен===
 +
 
 +
[[Media:Дискретная математика_(2_часа)_-_программа.pdf|'''Программа курса''']]
 +
 
 +
===Основные материалы===
 +
 
 +
[[Media:ДМ_2h_Презентация.pdf|'''Презентации к лекциям''']] (в файле присутствует электронное оглавление)
 +
 
 +
===Литература===
 +
 
 +
#[https://www.youtube.com/playlist?list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT Видео-лекции], прочитанные профессором [[Алексеев Валерий Борисович | В.Б. Алексеевым]] в 2020 г. (расширенный вариант курса на 3 ч в неделю).
 +
#[[Media:ДМ_2h_Презентация.pdf|Савицкий И.В. Презентации к лекциям по дискретной математике для 2 часов в неделю. 2023.]]
 +
#[[Media:Алексеев_-_2004_-_Лекции_по_дискретной_математике.pdf|Алексеев В.Б. Лекции по дискретной математике. М.: ВМК МГУ, 2004.]]
 +
#Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. 384 с.
 +
#Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. 416 с.
 +
 
 +
 
 +
<!---
 +
==2021-2022 учебный год==
  
 
Лектор - [[Селезнева Светлана Николаевна]]
 
Лектор - [[Селезнева Светлана Николаевна]]
  
==Экзамен==
+
===Экзамен===
  
 
'''Экзамен состоится 14 июня очно'''.
 
'''Экзамен состоится 14 июня очно'''.
Строка 16: Строка 42:
  
 
Экзамен проводится очно в аудитории. Работу следует написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются принимающему экзамен.  
 
Экзамен проводится очно в аудитории. Работу следует написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются принимающему экзамен.  
 
Итоги экзамена появятся 17 июня в 10 ч (по московскому времени). Затем до 11 ч (по московскому времени) 17 июня на почту dm1@cs.msu.ru можно прислать вопросы по оцениванию заданий в работах. После всех обсуждений оценки выставляются в ведомость.
 
  
 
'''Вопросы к экзамену'''
 
'''Вопросы к экзамену'''
Строка 79: Строка 103:
 
*Найти диаграмму Мура, каноническую таблицу или канонические уравнения автоматной функции, заданной одним из перечисленных способов.
 
*Найти диаграмму Мура, каноническую таблицу или канонические уравнения автоматной функции, заданной одним из перечисленных способов.
 
*Построить диаграмму Мура, не содержащую недостижимых и неотличимых состояний, для заданной автоматной функции.
 
*Построить диаграмму Мура, не содержащую недостижимых и неотличимых состояний, для заданной автоматной функции.
 
+
--->
==Удаленное обучение==
+
 
+
Вопросы по содержанию курса (и другие вопросы, относящиеся к курсу) можно задавать лектору Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru
+
 
+
==Лекции==
+
 
+
'''Алгебра логики'''
+
 
+
[[Media: dm1-l1-selezn.pdf | Лекция 1]]. Двоичный куб. Наборы, вес набора. Слой n-мерного куба. Частичный порядок на n-мерном кубе. Соседние и противоположные наборы, расстояние между наборами. Лексико-графический порядок на n-мерном кубе.
+
 
+
[[Media: dm1-l2-selezn.pdf | Лекция 2]]. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества. Двойственность.
+
 
+
[[Media: dm1-l3-selezn.pdf | Лекция 3]]. Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полные системы. Полнота некоторых систем.
+
 
+
[[Media: dm1-l4-selezn.pdf | Лекция 4]]. Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина. Полные системы. Полнота некоторых систем.
+
 
+
[[Media: dm1-l5-selezn.pdf | Лекция 5]]. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. Леммы о несамодвойственной, немонотонной и нелинейной функциях.
+
 
+
[[Media: dm1-l6-selezn.pdf | Лекция 6]]. Полные системы. Теорема Поста о полноте. Базис в P_2. Теореме о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.
+
 
+
'''Графы'''
+
 
+
[[Media: dm1-l7-selezn.pdf | Лекция 7]]. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе. Орграфы.
+
 
+
[[Media: dm1-l8-selezn.pdf | Лекция 8]]. Деревья. Теорема о равносильных определениях дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.
+
 
+
[[Media: dm1-l9-selezn.pdf | Лекция 9]]. Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.
+
 
+
[[Media: dm1-l10-selezn.pdf | Лекция 10]]. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.
+
 
+
[[Media: dm1-l11-selezn.pdf | Лекция 11]]. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.
+
 
+
'''Коды'''
+
 
+
[[Media: dm1-kf-l12-selezn.pdf | Лекция 12]]. Кодирование. Алфавитные коды. Проверка однозначности алфавитного кода. Теорема Маркова. Неравенство Макмиллана. Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.
+
 
+
[[Media: dm1-kf-l13-selezn.pdf | Лекция 13]]. Алфавитные коды. Оптимальные коды (коды с минимальной избыточностью). Свойства оптимальных кодов. Теорема редукции. Метод Хаффмана построения оптимального кода.
+
 
+
[[Media: dm1-kf-l14-selezn.pdf | Лекция 14]]. Устойчивость кодов к ошибкам. Коды, обнаруживающие и исправляющие ошибки, их свойства. Коды Хэмминга.
+
 
+
'''Автоматы'''
+
 
+
[[Media: dm1-kf-l15-selezn.pdf | Лекция 15]]. Конечные автоматы. Способы их представления. Отличимость состояний конечного автомата. Теорема Мура. Упрощение автоматов.
+
 
+
===Литература===
+
<ol>
+
<li> Слайды к лекциям.
+
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
+
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс.
+
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
+
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
+
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.
+
</ol>
+
 
+
==Семинары==
+
 
+
[[Media: dm1-kf-s.pdf | План семинарских занятий]]
+
 
+
[[Media: dm1-1-s-d.pdf | Дополнительные задачи к семинарским занятиям]]
+

Текущая версия на 10:19, 27 ноября 2025

Курс для студентов 2-го курса Казахстанского филиала МГУ, читается в 1-м семестре, 2 ч лекций и 2 ч семинаров в неделю, отчетность — экзамен.

2025-2026 учебный год

Лектор - Савицкий Игорь Владимирович

Экзамен

Программа курса

Основные материалы

Презентации к лекциям (в файле присутствует электронное оглавление)

Литература

  1. Видео-лекции, прочитанные профессором В.Б. Алексеевым в 2020 г. (расширенный вариант курса на 3 ч в неделю).
  2. Савицкий И.В. Презентации к лекциям по дискретной математике для 2 часов в неделю. 2023.
  3. Алексеев В.Б. Лекции по дискретной математике. М.: ВМК МГУ, 2004.
  4. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. 384 с.
  5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. 416 с.