Хеширование, хеш-таблицы, приближённые алгоритмы
Алгоритмы и структуры данных, часть 1


Что: Лекция
Когда: Пятница, 09 декабря 2016, 18:30–20:00
Где: Таймс, 4 этаж

Описание

  • Универсальное семейство хеш-функций
  • Совершенное хеширование (двухуровневая схема)
  • Хеш-таблица на списках
  • Хеш-таблица с открытой адресацией
  • Куку-хеширование (без доказательства)
  • Приближённое решение задачи о set cover. \(\ln n\)-прибилижение.
  • Приближённое решение задачи о коммивояжёре через MST. \(2\)-прибилижение и \(1.5\)-прибилижение.