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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Лекции)
(Лекции)
Строка 17: Строка 17:
 
[[Media: dm1-l2-selezn.pdf | Лекция 2]]. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества. Двойственность.
 
[[Media: dm1-l2-selezn.pdf | Лекция 2]]. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества. Двойственность.
  
Лекция 3. Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полные системы. Полнота некоторых систем.
+
[[Media: dm1-l3-selezn.pdf | Лекция 3]]. Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полные системы. Полнота некоторых систем.
  
Лекция 4. Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина. Полные системы. Полнота некоторых систем.  
+
[[Media: dm1-l4-selezn.pdf | Лекция 4]]. Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина. Полные системы. Полнота некоторых систем.  
  
Лекция 5. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. Леммы о несамодвойственной, немонотонной и нелинейной функциях.
+
[[Media: dm1-l5-selezn.pdf | Лекция 5]]. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. Леммы о несамодвойственной, немонотонной и нелинейной функциях.
  
Лекция 6. Полные системы. Теорема Поста о полноте. Базис в P_2. Теореме о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.
+
[[Media: dm1-l6-selezn.pdf | Лекция 6]]. Полные системы. Теорема Поста о полноте. Базис в P_2. Теореме о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.
  
 
'''Графы'''
 
'''Графы'''
  
Лекция 7. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе. Орграфы.
+
[[Media: dm1-l7-selezn.pdf | Лекция 7]]. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе. Орграфы.
  
Лекция 8. Деревья. Теорема о равносильных определениях дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.
+
[[Media: dm1-l8-selezn.pdf | Лекция 8]]. Деревья. Теорема о равносильных определениях дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.
  
Лекция 9. Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.
+
[[Media: dm1-l9-selezn.pdf | Лекция 9]]. Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.
  
Лекция 10. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.  
+
[[Media: dm1-l10-selezn.pdf | Лекция 10]]. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.  
  
Лекция 11. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.
+
[[Media: dm1-l11-selezn.pdf | Лекция 11]]. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.
  
 
'''Коды'''
 
'''Коды'''
  
Лекция 12. Кодирование. Алфавитные коды. Теорема об однозначности равномерного кода. Теорема об однозначности префиксного кода. Алгоритм распознавания однозначности алфавитного кода. Теорема Маркова.
+
<!---Лекция 12. Кодирование. Алфавитные коды. Теорема об однозначности равномерного кода. Теорема об однозначности префиксного кода. Алгоритм распознавания однозначности алфавитного кода. Теорема Маркова.
  
 
Лекция 13. Алфавитные коды. Неравенство Макмиллана. Теорема о существовании префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.
 
Лекция 13. Алфавитные коды. Неравенство Макмиллана. Теорема о существовании префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.
Строка 47: Строка 47:
 
Лекция 15. Коды, обнаруживающие и исправляющие ошибки, их свойства. Мощность кода, исправляющего ошибки. Линейные коды и их свойства.
 
Лекция 15. Коды, обнаруживающие и исправляющие ошибки, их свойства. Мощность кода, исправляющего ошибки. Линейные коды и их свойства.
  
Лекция 16. Коды, исправляющие одну ошибку. Коды Хэмминга и их свойства. Мощность кода, исправляющего одну ошибку.
+
Лекция 16. Коды, исправляющие одну ошибку. Коды Хэмминга и их свойства. Мощность кода, исправляющего одну ошибку.--->
  
 
'''Автоматы'''
 
'''Автоматы'''
  
Лекция 17. Конечные автоматы. Способы их представления. Схемы из функциональных элементов с задержками (СФЭЗ) и представление конечных автоматов ими.
+
<!---Лекция 17. Конечные автоматы. Способы их представления. Схемы из функциональных элементов с задержками (СФЭЗ) и представление конечных автоматов ими.
  
Лекция 18. Конечные автоматы. Отличимость состояний конечного автомата. Оценка длины слова, отличающего два отличимых состояния конечного автомата. Упрощение автоматов.
+
Лекция 18. Конечные автоматы. Отличимость состояний конечного автомата. Оценка длины слова, отличающего два отличимых состояния конечного автомата. Упрощение автоматов.--->
  
 
===Литература===
 
===Литература===

Версия 11:41, 15 марта 2022


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

Лектор - Селезнева Светлана Николаевна

Удаленное обучение

Вопросы по содержанию курса (и другие вопросы, относящиеся к курсу) можно задавать лектору Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru

Лекции

Алгебра логики

Лекция 1. Двоичный куб. Наборы, вес набора. Слой n-мерного куба. Частичный порядок на n-мерном кубе. Соседние и противоположные наборы, расстояние между наборами. Лексико-графический порядок на n-мерном кубе.

Лекция 2. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества. Двойственность.

Лекция 3. Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полные системы. Полнота некоторых систем.

Лекция 4. Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина. Полные системы. Полнота некоторых систем.

Лекция 5. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. Леммы о несамодвойственной, немонотонной и нелинейной функциях.

Лекция 6. Полные системы. Теорема Поста о полноте. Базис в P_2. Теореме о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.

Графы

Лекция 7. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе. Орграфы.

Лекция 8. Деревья. Теорема о равносильных определениях дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.

Лекция 9. Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.

Лекция 10. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.

Лекция 11. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.

Коды


Автоматы


Литература

  1. Слайды к лекциям.
  2. Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
  3. Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс.
  4. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
  5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
  6. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.

Семинары

План семинарских занятий

Дополнительные задачи к семинарским занятиям