Archive for Январь 2010

Универсальные семейства хэш-функций

Январь 19, 2010

Пусть мы хотим разработать структуру данных, которая хранит множество S \subseteq \{0, 1, \ldots, m - 1\} и поддерживает следующие операции:

  • Insert(x) добавляет x в S,
  • Delete(x) удаляет x из S,
  • Find(x) проверяет принадлежность x \in S.

(more…)

Реклама

Тестирование свойства

Январь 2, 2010

Пусть у нас есть ненаправленный граф G = (V, E) (|V| = n). Мы хотим проверить, можно ли раскрасить его вершины в k цветов так, чтобы каждое ребро было разноцветным. Если k \geq 3, то эта задача \mathrm{NP}-полная. Но пусть мы знаем, что либо G k-раскрашиваемый, либо он \varepsilon-далек от k-раскрашиваемых графов, то есть нужно удалить по крайней мере \varepsilon n^2 ребер, чтобы такая раскраска нашлась.

(more…)

PCP теорема и тестирование линейности

Январь 1, 2010

Хотели бы вы записать доказательство теоремы Ферма так, чтобы можно было проверить его с высокой вероятностью, лишь посмотрев какой-то локальный фрагмент? TCS делает мечты реальностью.

(more…)