Предисловие

• МОЖНО ЛИ ДОВЕРЯТЬ МАТЕМАТИКЕ? | IQ (0мин.)

Тема 1. Множества и отношения

• 1.1. Множества и булеаны (65мин.)
• 1.2. Отношения (98мин.)
• • 1.2.1. Соответствия (49мин.)
  • 1.2.2. Гомоморфизм и изоморфизм (16мин.)
  • 1.2.3. Однородные бинарные отношения (16мин.)
• Задачи (33мин.)
• Тест:  Множества и отношения (60мин.)

Тема 2. Функции алгебры логики

• 2.1. Основные определения (114мин.)
• 2.2. Разложение булевых функций по переменным (98мин.)
• 2.3. Теорема о полноте (81мин.)
• 2.4. Минимизация булевых функций (98мин.)
• 2.5. Геометрическая интерпретация дизъюнктивной нормальной формы (98мин.)
• 2.6. Минимизация систем функций алгебры логики (65мин.)
• Задачи (33мин.)
• Тест:  Функции алгебры логики (34мин.)

Тема 3. Алгебры высказываний, предикатов и множеств

• 3.1. Алгебра высказываний (65мин.)
• 3.2. Алгебра предикатов (49мин.)
• 3.3. Алгебра множеств (16мин.)
• Задачи (16мин.)
• Тест:  Алгебры высказываний, предикатов и множеств (26мин.)

Тема 4. Отношения эквивалентности и частичного порядка

• 4.1. Отношения эквивалентности (33мин.)
• 4.2. Ядерная эквивалентность и каноническое разложение (33мин.)
• 4.3. Отношения частичного порядка (49мин.)
• 4.4. Многокритериальная оптимизация (16мин.)
• 4.5. Решетки (49мин.)
• 4.6. Булевы решетки (49мин.)
• Задачи (16мин.)
• Тест:  Отношения эквивалентности и частичного порядка (32мин.)

Тема 5. Комбинаторика

• 5.1. Основные принципы комбинаторики (98мин.)
• • Основы дискретной математики | Алексей Пастор | Лекция 2 (89мин.)
• 5.2. Упорядоченные разбиения и сочетания с повторениями (16мин.)
• 5.3. Формула включения-исключения и числа Стирлинга (179мин.)
• • Основы дискретной математики | Алексей Пастор | Лекция 3 (89мин.)
• 5.4. Числа Фибоначчи (33мин.)
• 5.5. Рекуррентные последовательности (179мин.)
• 5.6. Производящие функции (81мин.)
• 5.7. Числа Стирлинга и взаимно-обратные преобразования (49мин.)
• 5.8. Задача Эйлера о размене монет и разбиение чисел на слагаемые (114мин.)
• 5.9. Числа Каталана (81мин.)
• 5.10. Линейные рекуррентные последовательности и производящие функции (146мин.)
• 5.11. Шары в ящиках: 12 вариантов задачи (33мин.)
• 5.12. Статистики перестановок (98мин.)
• 5.13. Производящие функции множеств и языков (49мин.)
• 5.14. Формула обращения Мёбиуса (49мин.)
• 5.15. Теория перечисления Пойа (81мин.)
• Задачи (114мин.)
• Тест:  Комбинаторика (34мин.)

Тема 6. Графы

• 6.1. Основные понятия (114мин.)
• 6.2. Операции над графами. Подграфы (49мин.)
• 6.3. Фундаментальные циклы и разрезы графа (81мин.)
• 6.4. Обходы графа и орграфа (130мин.)
• 6.5. Связность графов и орграфов (81мин.)
• • Основы дискретной математики | Алексей Пастор | Лекция 12 (95мин.)
• 6.6. Множества внешней и внутренней устойчивости (65мин.)
• 6.7. Раскраска графов (98мин.)
• 6.8. Паросочетания в двудольных графах (130мин.)
• 6.9. Плоские графы. Критерии планарности графа (81мин.)
• 6.10. Потоки в сетях (81мин.)
• 6.11. Задача о минимальном остовном дереве (49мин.)
• Задачи (49мин.)
• Тест:  Графы (62мин.)

Тема 7. Логика предикатов

• 7.1. Формулы логики предикатов (81мин.)
• 7.2. Преобразование предикатов (33мин.)
• 7.3. Эквивалентные преобразования формул (81мин.)
• 7.4. Общезначимые и противоречивые формулы (81мин.)
• 7.5. Логические следствия (16мин.)
• Задачи (49мин.)
• Тест:  Логика предикатов (18мин.)

Тема 8. Логические схемы

• 8.1. Схемы из функциональных элементов и логические схемы (98мин.)
• 8.2. Сложность схемы. Минимальные схемы (65мин.)
• 8.3. Некоторые элементарные методы синтеза (49мин.)
• 8.4. Функция Шеннона. Оценки Шеннона — Лупанова (65мин.)
• 8.5. Синтез схем методом каскадов (49мин.)
• 8.6. Декомпозиционные методы синтеза (195мин.)
• • 8.6.1. Понятие декомпозиции (65мин.)
  • 8.6.2. Использование нетривиальной декомпозиции (65мин.)
  • 8.6.3. Использование программируемых логических матриц (65мин.)
• 8.7. Контактные схемы (98мин.)
• 8.8. Тестирование логических схем (65мин.)
• Задачи (16мин.)
• Тест:  Логические схемы (34мин.)

Тема 9. Конечные автоматы

• 9.1. Основные понятия (114мин.)
• 9.2. Эквивалентность автоматов (49мин.)
• 9.3. Изоморфизм автоматов (33мин.)
• 9.4. Минимизация автоматов (65мин.)
• 9.5. Регулярные события и регулярные выражения (33мин.)
• 9.6. Регулярность событий, представимых автоматами (33мин.)
• 9.7. Представление регулярного события автоматом (81мин.)
• 9.8. Схемы с обратной связью (65мин.)
• Задачи (49мин.)
• Тест:  Конечные автоматы (32мин.)

Тема 10. Теория алгоритмов и вычислимых функций

• 10.1. Машины Тьюринга (98мин.)
• 10.2. Тьюрингово программирование и тьюринговы диаграммы (49мин.)
• 10.3. Алгоритмически неразрешимые проблемы (49мин.)
• 10.4. Вычисления на абаке (33мин.)
• 10.5. Рекурсивные функции (81мин.)
• 10.6. Универсальные функции (33мин.)
• 10.7. Разрешимые и перечислимые множества и предикаты (49мин.)
• 10.8. Формальные системы и алгорифмы Маркова (130мин.)
• • 10.8.1. Формальные системы (114мин.)
  • 10.8.2. Нормальные алгорифмы Маркова (16мин.)
• Задачи (49мин.)
• Тест:  Теория алгоритмов и вычислимых функций (18мин.)

Тема 11. NP-полные задачи

• 11.1. Схемы, предикаты и конъюнктивные нормальные формы (81мин.)
• 11.2. Моделирование машин Тьюринга булевыми схемами (65мин.)
• 11.3. Классы P и NP. Теорема Кука (49мин.)
• • Приближенное решение задач комбинаторной оптимизации: алгоритмы и трудность | Михаил Вялый | Лекция 1 (94мин.)
  • Алгоритмы и структуры данных | Александр Куликов | Лекция 12 (87мин.)
• 11.4. NP-полные задачи (244мин.)
• 11.5. Частные случаи NP-полных задач (146мин.)
• 11.6. Алгоритмы для точного решения некоторых NP-полных задач (244мин.)
• • 11.6.1. Динамическое программирование (81мин.)
  • 11.6.2. Псевдополиномиальные алгоритмы (16мин.)
  • 11.6.3. Метод ветвей и границ (146мин.)
• 11.7. Приближенные алгоритмы решения NP-полных задач (195мин.)
• • 11.7.1. Жадные алгоритмы (81мин.)
  • 11.7.2. Полиномиальные алгоритмы с ограниченной погрешностью (65мин.)
  • 11.7.3. Алгоритмы локальной минимизации (49мин.)
• Задачи (81мин.)
• Тест:  NP-полные задачи (28мин.)

Тема 12. Конечные поля и эллиптические кривые

• 12.1. Группы, кольца, поля и многочлены (244мин.)
• 12.2. Конечные поля (179мин.)
• • 12.2.1. Мультипликативная группа поля (33мин.)
  • 12.2.2. Подполя и их расширения (65мин.)
  • 12.2.3. Неприводимые и примитивные многочлены (49мин.)
• 12.3. Эллиптические кривые (179мин.)
• Задачи (16мин.)
• Тест:  Конечные поля и эллиптические кривые (50мин.)

Тема 13. Теория кодов, исправляющих ошибки

• 13.1. Основные понятия (163мин.)
• • 13.1.1. Двоичные коды (65мин.)
  • 13.1.2. q-Ичные коды и границы сферической упаковки (49мин.)
  • 13.1.3. Линейные коды. Порождающие и проверочные матрицы (49мин.)
• 13.2. Коды Хемминга (163мин.)
• • 13.2.1. Коды Хемминга как циклические коды (81мин.)
  • 13.2.2. q-Ичные коды Хемминга (33мин.)
• 13.3. Коды Рида — Соломона (49мин.)
• 13.4. Коды Боуза — Чоудхури — Хоквингема (33мин.)
• 13.5. Матричное определение кодов Боуза — Чоудхури — Хоквингема и Рида — Соломона (49мин.)
• 13.6. Исправление двух ошибок (16мин.)
• 13.7. Определение позиций ошибок в общем случае методом Питерсона (65мин.)
• Задачи (49мин.)
• Тест:  Теория кодов, исправляющих ошибки (36мин.)

Тема 14. Криптографические приложения

• 14.1. Линейная рекуррентная последовательность и ее характеристический многочлен (130мин.)
• • 14.1.1. Основные понятия (16мин.)
  • 14.1.2. Автоматная интерпретация линейной рекуррентной последовательности (33мин.)
  • 14.1.3. Статистические свойства линейной рекуррентной последовательности (16мин.)
  • 14.1.4. След элемента конечного поля (16мин.)
  • 14.1.5. Формула общего члена линейной рекуррентной последовательности (49мин.)
• 14.2. Электронная цифровая подпись (65мин.)
• • 14.2.1. Понятие, назначение и свойства цифровой подписи (33мин.)
  • 14.2.2. О российском стандарте цифровой подписи 2012 года (33мин.)
• 14.3. Предварительное распределение ключей в компьютерной сети (130мин.)
• • 14.3.1 Схемы предварительного распределения ключей. (k, m)‑Схема Блома (16мин.)
  • 14.3.2. Безусловная безопасность схемы Блома относительно компрометации ключей m пользователей (16мин.)
  • 14.3.3. Многочлены в (k, m)-схеме Блома и условие ее вскрытия (98мин.)
• Задачи (33мин.)
• Тест:  Криптографические приложения (12мин.)

Литература

Новые издания по дисциплине «Дискретная математика» и смежным дисциплинам

Завершение курса

• Тест:  Итоговое тестирование (46мин.)