Пристрелочная лекция

  1. Алгоритм A* (модификация Дейкстры)
    1. Собственно алгоритм и доказательство корректности
    2. Почему быстрей работает?
  2. Задача "самый длинный путь в графе"
    1. Решение динамикой за O(2nn2)
    2. Перебор с запоминанием за O(2nn2) (ленивая динамика)
    3. Отсечение по ответу
    4. Применяем A* (улучшаем с помощью этого отсечение по ответу)
  3. Перебор подмножеств всех множеств за 3n
    1. Кодирование множеств n-битовыми числами
    2. Собственно перебор подмножеств и надмножеств
    3. Раскраска вершин графа в минимальное число цветов за O(3n)
      1. Предподсчет за O(2nn2) − является подмножество антикликой
      2. Предподсчет за O(2n) (научились делать все операции с множествами за O(1))
      3. Решение исходной задачи динамикой f[set] = min_colors
  4. Разбиения на слагаемые
    1. Количество разбиений числа N на упорядоченные возрастающие различные слагаемые
    2. За O(N2)
    3. За O(N2) с O(N) памяти
    4. Различные/с повторениями
    5. k-слагаемых/максимальное не больше k
    6. За O(N√ N ) с O(N) памяти