Дискретная математика (1-й поток) — различия между версиями
(→Лекции) |
|||
| Строка 37: | Строка 37: | ||
'''Коды''' | '''Коды''' | ||
| + | |||
| + | [[Media: dm1-l10-selezn.pdf | Лекция 10]]. Кодирование. Алфавитные коды. Теорема об однозначности равномерного кода. Теорема об однозначности префиксного кода. Алгоритм распознавания однозначности алфавитного кода. Теорема Маркова. | ||
| + | |||
| + | Лекция 11. Алфавитные коды. Неравенство Макмиллана. Теорема о существовании префиксного кода с заданными длинами кодовых слов. Оптимальные коды (коды с минимальной избыточностью). Леммы о свойствах оптимальных кодов. Теорема редукции. Метод Хаффмана построения оптимального кода. | ||
| + | |||
| + | Лекция 12. Коды, обнаруживающие и исправляющие ошибки, их критерии. Код Хэмминга. Линейные коды. Теорема о кодовом расстоянии линейного кода. | ||
'''Алгоритмы''' | '''Алгоритмы''' | ||
Версия 19:31, 24 марта 2020
Дополнительная страница по курсу Дискретная математика (1й курс).
Основной курс для студентов 1-го курса, читается во 2-м семестре. Лекции - 3 ч в неделю, семинары - 2 ч в неделю, отчетность - экзамен.
Лектор - Селезнева Светлана Николаевна
Удаленное обучение
1-я неделя: 17 марта-24 марта
Лекции
Алгебра логики
Лекция 1. Двоичный куб. Наборы, вес набора. Слой n-мерного куба. Частичный порядок на n-мерном кубе. Соседние и противоположные наборы, расстояние между наборами. Лексико-графический порядок на n-мерном кубе.
Лекция 2. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества. Двойственность.
Лекция 3. Разложение функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полиномы Жегалкина. Теорема Жегалкина. Быстрый способ построения полинома Жегалкина.
Лекция 4. Полные системы. Полнота некоторых систем. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. Леммы о несамодвойственной, немонотонной и нелинейной функциях.
Лекция 5. Полные системы. Теорема Поста о полноте. Базис в P_2. Теореме о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.
Лекция 6. Функции k-значной логики. Таблицы значений. Представление функций k-значной логики в 1-й и 2-й формах. Представление функций k-значной логики полиномами по модулю k.
Графы
Лекция 7. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе. Орграфы.
Лекция 8. Деревья. Теорема о равносильных определениях дерева. Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.
Лекция 9. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.
Коды
Лекция 10. Кодирование. Алфавитные коды. Теорема об однозначности равномерного кода. Теорема об однозначности префиксного кода. Алгоритм распознавания однозначности алфавитного кода. Теорема Маркова.
Лекция 11. Алфавитные коды. Неравенство Макмиллана. Теорема о существовании префиксного кода с заданными длинами кодовых слов. Оптимальные коды (коды с минимальной избыточностью). Леммы о свойствах оптимальных кодов. Теорема редукции. Метод Хаффмана построения оптимального кода.
Лекция 12. Коды, обнаруживающие и исправляющие ошибки, их критерии. Код Хэмминга. Линейные коды. Теорема о кодовом расстоянии линейного кода.
Алгоритмы
Автоматы
Семинары
Дополнительные задачи к семинарским занятиям
