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