Лекция
Теорема Карпа–Липтона. Схемы фиксированного полиномиального размера. P–полнота. NSPACE. Полиномиальные вычисления и логарифмическая память.
Полиномиальная иерархия. Классы, ограниченные по времени и памяти. Иерархия по памяти. Иерархия по времени.
Полиномиальная иерархия. Классы, ограниченные по времени и памяти. Иерархия по памяти. Иерархия по времени.
Задачи поиска. Классы P и NP. Сведения. NP–полные задачи. Не NP–полные задачи в классе NPP.
Задачи поиска. Классы P и NP. Сведения. NP–полные задачи. Не NP–полные задачи в классе NPP.
В своей работе веб–дизайнеры должны принимать решения: (1) какие элементы разместить на странице и (2) какой приоритет дать тому или иному элементу. В...
Новые технологии (социальные сети, семантический веб, мобильный интернет) неизбежно приведут к появлению рекламных систем нового типа. Потребители хотят...
Страница лекции на сайте Computer Science клуба
Страница лекции на сайте Computer Science клуба
Страница лекции на сайте Computer Science клуба
Страница лекции на сайте Computer Science клуба
Страница лекции на сайте Computer Science клуба
SAT-based software model checking.
Introduction to model checking: system modeling and logic specifications.
Abstraction in model checking: Predicate abstraction; CEGAR–based software model checking.
Курс о фундаментальных основах криптографии.
Вероятностное округление для задачи о потоке в сетях с несколькими веществами.
Дополняющие пути, случай двудольных графов, общий случай.
Метод Форда-Фалкерсона, алгоритм проталкивания предпотока, алгоритм «поднять-в-начало».
Курс о фундаментальных основах криптографии.
Курс о фундаментальных основах криптографии.
Метод условных вероятностей, метод малых пространств событий.
Дополняющие пути, случай двудольных графов, общий случай.
Алгоритм и оценки времени его работы в худшем и среднем случае.
Алгоритм Кармаркара
Постановка задачи полуопределённого программирования, приближённый алгоритм для задачи о максимальном разрезе, раскраска 3–раскрашиваемого графа.
Задача о выборе заявок, коды Хаффмена, покрытие множествами, вершинное покрытие, локальный поиск для задачи выполнимости.