Методы поиска корней и минимизации численной функции

  1. Бинарный поиск для корней непрерывной функции.
  2. Поиск корней многочлена за O(N2logMax).
  3. Сведение задачи поиска корней к минимизации, а минимизации к максимизации и обратно.
  4. Троичный (тернарный) поиск для нахождения локального минимума.
  5. Усовершенствованный поиск #1 (делим всегда на k частей, сужаем область видимости)
  6. Усовершенствованный поиск #2 (делим на N частей, на каждой запускаем троичный поиск)
  7. Вложенные троичные поиски для минимизации многомерной функции (пример: найти "центр" выпуклого многоугольника)
  8. Градиентный спуск в R1
  9. Градиентный спуск в Rn

Метод отжига

  1. Процесс оптимизации. p = exp-(F1-F0)/T.
  2. Чем это лучше "Усовершенствованных поисков"? Решает многомерную задачу.
  3. Выбор случайной точки: радиус шарика, в котором выбирается точка, тоже сходится к 0.
  4. Собственно алгоритм.
  5. Пример отжига нестандартных пространств: поиск минимального контролирующего множества.

Теория чисел

  1. Решето Эратосфена за O(NloglogN).
  2. Тест Ферма проверки на простоту.
  3. Тест Миллера-Рабина проверки на простоту.
  4. Эвристика Полларда для факторизации числа за O(N1/4).

Строки. Хэши. Хэш-таблицы.

  1. Полиномиальный хэш. Hash(s) - псевдослучайное число в диапозоне от 0 до 264 - 1.
  2. Коллизии, обработка коллизий, вероятность возникновения коллизий.
  3. Сравнение строк на равенство за O(1).
  4. Задача про число различных подстрок строки.
  5. Полиномиальный хэш применим к произвольному объекту. Пример: отсечение в переборе с помощью set <long long>.
  6. Хэш-таблица со списками. Оценка на время работы
  7. Хэш-таблица с открытой адресацией. Оценка на время работы
  8. Удаление элементов из хэш-таблицы.
  9. Примеры задач на хэши и с хэш-таблицей
    1. Наибольшая общая подстрока.
    2. Поиск словарных слов в тексте.

Строки. Суффиксный массив.

  1. Определение. Построение в лоб за O(N2logN). Реальное время работы уже O(NlogN).
  2. Сравнение строк на больше и меньше за O(logN) хэшами.
  3. Построение суффиксного массива за O(Nlog2N) в худшем случае.
  4. Построение LCP для суффиксного массива за O(NlogN).
  5. Решение задачи поиска подстроки в тексте с помощью суф. массива за предподсчет O(|Text|) и запрос за O(|S|*log|Text|).

Строки. Бор. Сжатый Бор.

  1. Бор строк. Суффиксное дерево строк. Определения.
  2. Хранения бора. Массив, список, хэш-таблица.
  3. Решение задачи про подстроки.
  4. Решение задачи про поиск словарных слов в тексте.
  5. Сжатый бор. Сжатое суффиксное дерево. Память = O(NE), где N - число строк, E - размер алфавита.
  6. У сжатого бора необычная малая константа. Решение задачи про подстроки для Len = 20 000.

Доведение старых идей до ума:

  1. Потоки
    1. Диница + масштабирование за O(VElogMax)
    2. Хопкрофт-Карп
  2. MinCost Потоки
    1. Формулировки прикладных задач: Задача о назначениях. Транспортная задача.
    2. Нахождение паросочетания миимального веса в двудольном графе с помощбю mincost потока за O(V3).
  3. Квадро-дерево
    1. Решеаем задачу о площади пересечения/объединения кругов приближенно.
    2. Еще одна задача: найти не покрытую точку.
  4. Покрытие дерева массивами (деревьями отрезков)