Теоретический семинар (осень 2014)

Доклад является выдержкой из статей Jakob Nordström и описывает базовые свойства black-only и black-white pebble games,
устанавливая связь некоторых параметров pebble игр с параметрами резолюционных доказательств: размером и variable space.

Интерпретация теории типов в множествах. Тип равенства. Интерпретация теории типов в топологических пространствах, пространство путей. Основные свойства равенства.

Теория множеств, логика и теория типов. Утверждения и суждения. Теория типов как основания математики. Классическая теория типов Мартин-Лёфа, связь с интуиционистской логикой и лямбда-исчислением.

В задаче MAX-ATSP требуется найти гамильтонов цикл максимального веса
в полном взвешенном ориентированном графе. Мы получим $\frac{2}{3}$
приближение при помощи округления решения линейной программы. Из
получающегося таким образом d-регулярного мультиграфа можно будет
извлечь пару покрытий циклами большого веса, в которых можно найти
гамильтонов тур, вес которого не меньше чем $\frac{2}{3}$ от
оптимального.
Мы рассмотрим задачу Seclude Path и Secluded Steiner Tree и параметризованные алгоритмы для их решения.
  • Алгоритм, параметризованный максимальной степенью вершины, для Secluded Path.
  • Алгоритмы, параметризованные размером ответа, $3^{\frac{k}{3}}$ для пути и $2^{k}$ для дерева.
  • Алгоритм, параметризованный Tree Width, с временем работы $4^{tw}$.
  • Рассмотрим shared-memory модель организации буфера. Вспомним соревновательный подход к анализу алгоритмов. Дадим общую для всех онлайн алгоритмов нижнюю оценку $\frac{4}{3}$ в данной модели. Рассмотрим алгоритм LQD (Largest Queue Drop) для случая, когда пакеты имеют равную стоимость. Дадим для LQD константную верхнюю оценку $2$.
    We construct a constant degree bipartite graph $G_n$ such that the resolution
    complexity of the perfect matching principle for $G_n$ is $2^{\Omega(n)}$,
    where $n$ is the number of vertices in $G_n$. We also prove the following corollary.
    For every natural number $d$,for every $n$ large enough, for every function
    $h:\{1,2,\dots, n\}\to \{1,2,\dots, d\}$, we construct a graph with $n$ vertices
    that has the following properties:
    • There exists a constant $D$ such that the