Предисловие

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

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

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

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

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

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

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

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

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

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

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

Тема 6. Графы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

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