Комбинаторные методы дискретной математики

Название спецкурса на английском языке
Combinatorial methods of discrete mathematics
Авторы курса
Носов Валентин Александрович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Модели вычислений, используемые для оценки сложности алгоритмов и вычислений
Меры сложности алгоритмов
Труднорешаемость задач
Классы P и NP и их свойства
NP-полные задачи
Теорема Кука о NP-полноте проблемы выполнимости формул алгебры высказываний
Полиномиальная сводимость задач
Рекурсивные алгоритмы для задач сортировки массивов чисел, умножения чисел, умножения матриц, преобразования формул алгебры логики
Доказательства не существования приближенных алгоритмов с некоторыми мерами уклонения
Оптимизация алгоритмов перебора
Политика жадности
Приближенные алгоритмы для задач об упаковке, о коммивояжере, о вершинном покрытии
Матроиды
Характеризация случаев оптимальности жадных алгоритмов
Теорема Радо- Эдмонса.
Список источников
Носов В.А. Основы теории алгоритмов и анализа их сложности. Курс лекций. Москва, 1992. 140 стр.
Дополнительная информация

Для 5го курса МаТИС

Изучение классического раздела дискретной математики, разработанной в целях приложений к компьютерным наукам, касающимся вопросов обработки дискретной информации (Теории дискретных систем, Существования и перечисления комбинаторных конфигураций, Методов оптимизации комбинаторных алгоритмов). Изучение основных комбинаторных чисел и конфигураций, используемых при анализе дискретных систем и касающихся вопросов обработки и передачи информации.

День недели
среда
Время
15:00-16:35
Аудитория
Ещё не назначена
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.