Дискретная математика (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]]. Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полиномы Жегалкина. Теорема | + | [[Media: dm1-l3-selezn.pdf | Лекция 3]]. Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полиномы Жегалкина. Теорема Жегалкина. |
| − | [[Media: dm1-l4-selezn.pdf | Лекция 4]]. Полные системы. Полнота некоторых систем | + | [[Media: dm1-l4-selezn.pdf | Лекция 4]]. Построение полиномов Жегалкина. Полные системы. Полнота некоторых систем. |
| − | [[Media: dm1-l5-selezn.pdf | Лекция 5]]. | + | [[Media: dm1-l5-selezn.pdf | Лекция 5]]. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. Леммы о несамодвойственной, немонотонной и нелинейной функциях. |
| − | [[Media: dm1-l6-selezn.pdf | Лекция 6]]. Функции k-значной логики. Таблицы значений. Представление функций k-значной логики в 1-й и 2-й формах. Представление функций k-значной логики полиномами по модулю k. | + | [[Media: dm1-l6-selezn.pdf | Лекция 6]]. Полные системы. Теорема Поста о полноте. Базис в P_2. Теореме о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2. |
| + | |||
| + | <!---[[Media: dm1-l6-selezn.pdf | Лекция 6]]. Функции k-значной логики. Таблицы значений. Представление функций k-значной логики в 1-й и 2-й формах. Представление функций k-значной логики полиномами по модулю k. | ||
'''Графы''' | '''Графы''' | ||
Версия 23:48, 5 февраля 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.
Семинары
Дополнительные задачи к семинарским занятиям
Занятие 1. Функции алгебры логики. Формулы. Тождества. Существенность переменных.
Занятие 2. Дизъюнктивные и конъюнктивные нормальные формы. Полиномы Жегалкина.
Занятие 7. Деревья и их свойства. Корневые деревья. Остовные деревья. Поиск кратчайшего остовного дерева в графе.
Занятие 8. Планарность графов. Критерий планарности. Раскраски графов.
Занятие 9. Алфавитные коды. Однозначность алфавитного кода. Оптимальные коды. Метод Хаффмана построения оптимального кода.
Занятие 10. Коды, исправляющие ошибки. Линейные коды. Коды Хэмминга.
Занятие 11. Конечные автоматы и автоматные функции. Способы их представления: канонические уравнения и диаграммы Мура.
Занятие 12. Конечные автоматы и автоматные функции. Способы их представления: схемы из функциональных элементов с задержками (СФЭЗ). Упрощение конечных автоматов.
