Дополнительные главы теоретической информатики

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