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

Постановка основных математических задач в теории сложности алгоритмов и их значение для обработки экономической информации.
Роль оптимизации и сложности алгоритмов в разработке программных продуктов искусственного интеллекта.
Машины произвольного доступа к памяти, машины Тьюринга и их модификации.
Взаимное моделирование моделей вычислений.
Функции сложности алгоритмов и их свойства.
Существование сложных задач.
Теорема Блюма об ускорении.
Труднорешаемость задач.
Классы P и NP и их свойства.
Полиномиальная сводимость задач.
NP-полные задачи. Теорема Кука о NP-полноте проблемы выполнимости формул алгебры высказываний.
Основные NP-полные задачи.
Задачи с числовыми параметрами. Задача о рюкзаке. Сильная NP-полнота.
Бесконечная серия NP-полных задач Шиффера.
Методы построения быстрых алгоритмов.
Структуры данных.
Рекурсия. Типы полиномиальных оценок сложности рекурсивных алгоритмов.
Рекурсивные алгоритмы для задач сортировки массивов чисел, умножения чисел, умножения матриц, преобразования формул алгебры логики.
Быстрое преобразование Фурье и его применения. Сложность умножения многочленов.
Быстрые алгоритмы на графах. Поиск в глубину и в ширину. Кратчайшие пути. Минимальные остовные деревья. Алгоритмы для задачи о паросочетании.
Потоки в сетях и алгоритмы нахождения максимального потока.
Методы решения труднорешаемых задач.
Метод ограничения параметров.
Метод приближенных алгоритмов. Существование приближенных алгоритмов с различными мерами уклонений от точных алгоритмов.
Доказательства не существования приближенных алгоритмов с некоторыми мерами уклонения.
Политика жадности. Примеры оптимальности жадных алгоритмов. Приближенные алгоритмы для задач об упаковке, о коммивояжере, о вершинном покрытии. Матроиды. Характеризация случаев оптимальности жадных алгоритмов. Теорема Радо- Эдмонса.
Оптимизация алгоритмов перебора.
Минимизация среднего числа опробований с учетом вероятности истинного варианта и сложности его опробования.
Метод согласования координат при переборе.
Методы получения нижних оценок сложности
Нижние оценки сложности в наследственных алгоритмах, использующих отношение частичной упорядоченности. Теорема Дилуорса. Лемма Анселя для единичного куба..
Сложность оптимального алгоритма выделения монотонной функции.
Нижние оценки вычисления на машине Тьюринга. Проблема симметрии слов. Теорема Барздинь и доказательство оптимальности.
Заключение. Основные направления исследований в области оценок сложности алгоритмов. Приложения к проблемам защиты банковской информации и электронной коммерции.