Дискретная математика (1-й поток) — различия между версиями

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

Версия 14:06, 10 февраля 2022

Дополнительная страница по курсу Дискретная математика (1й курс).

Основной курс для студентов 1-го курса, читается во 2-м семестре. Лекции - 3 ч в неделю, семинары - 2 ч в неделю, отчетность - экзамен.

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

Экзамен

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

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

Записи лекций можно найти по ссылке [1] в разделе СелезневаСН.

Лекции

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

Лекция 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. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.

Коды

Лекция 12. Кодирование. Алфавитные коды. Теорема об однозначности равномерного кода. Теорема об однозначности префиксного кода. Алгоритм распознавания однозначности алфавитного кода. Теорема Маркова.

Лекция 13. Алфавитные коды. Неравенство Макмиллана. Теорема о существовании префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.

Лекция 14. Алфавитные коды. Оптимальные коды (коды с минимальной избыточностью). Свойства оптимальных кодов. Теорема редукции. Метод Хаффмана построения оптимального кода.

Лекция 15. Коды, обнаруживающие и исправляющие ошибки, их свойства. Мощность кода, исправляющего ошибки. Линейные коды и их свойства.

Лекция 16. Коды, исправляющие одну ошибку. Коды Хэмминга и их свойства. Мощность кода, исправляющего одну ошибку.

Автоматы

Лекция 17. Конечные автоматы. Способы их представления. Схемы из функциональных элементов с задержками (СФЭЗ) и представление конечных автоматов ими.

Лекция 18. Конечные автоматы. Отличимость состояний конечного автомата. Оценка длины слова, отличающего два отличимых состояния конечного автомата. Упрощение автоматов.

СФЭ

Лекция 19. Схемы из функциональных элементов (СФЭ). Схемы для сложения и вычитания, их сложность.

Лекция 20. Схема для умножения. Сложность схемы для умножения по методу Карацубы.

Многозначные логики

Лекция 21. Функции k-значной логики. Таблицы значений. Представление функций k-значной логики в 1-й и 2-й формах. Представление функций k-значной логики полиномами по модулю k.

Семинары

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

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

Занятие 1. Функции алгебры логики. Формулы. Тождества. Существенность переменных.

Занятие 2. Дизъюнктивные и конъюнктивные нормальные формы. Полиномы Жегалкина.

Занятие 7. Деревья и их свойства. Корневые деревья. Остовные деревья. Поиск кратчайшего остовного дерева в графе.

Занятие 8. Планарность графов. Критерий планарности. Раскраски графов.

Занятие 9. Алфавитные коды. Однозначность алфавитного кода. Оптимальные коды. Метод Хаффмана построения оптимального кода.

Занятие 10. Коды, исправляющие ошибки. Линейные коды. Коды Хэмминга.

Занятие 11. Конечные автоматы и автоматные функции. Способы их представления: канонические уравнения и диаграммы Мура.

Занятие 12. Конечные автоматы и автоматные функции. Способы их представления: схемы из функциональных элементов с задержками (СФЭЗ). Упрощение конечных автоматов.