План занятий параллели A' ЛКШ 2011.Август

День 1 (03.08.11)
Практика. Разминочные задачи
Лекция. Общие рекомендации
Лекция. Продвинутые применения поиска в глубину
День 2 (04.08.11)
Практика. Задачи на поиск в глубину и 2-SAT
Лекция. Паросочетания. Элементарные потоки
День 3 (05.08.11)
Практика. Задачи на паросочетания и потоки. Тестирование
Лекция. Потоки (mincost-maxflow). Least common ancestor. Disjoint set union
День 4 (06.08.11)
Практика. Задачи на maxflow-mincost и LCA
Лекция. Поиск подстрок
День 5 (07.08.11)
Практика. Задачи на поиск подстрок
Лекция. Суффиксный автомат
День 6 (08.08.11)
Практика. Задачи на суффиксный автомат
Лекция. Продвинутое динамическое программирование
День 7 (10.08.11)
Практика. Задачи на ДП
Лекция. Приемы решения задач на P- и Z-функции и на ДП
День 8 (11.08.11)
Практика. Задачи на P/Z-функцию и на ДП
Лекция. Игры на графах
День 9 (12.08.11)
Практика. Задачи на игры
Лекция. Матрицы
День 10 (13.08.11)
Практика. Задачи на матрицы
Лекция. Задачи на отрезках
День 11 (16.08.11)
Практика. Задачи на задачи на отрезках
Лекция. Декартовы деревья
День 12 (17.08.11)
Практика. Продолжение задач на задачи на отрезках
Лекция. Последняя лекция

День 1 (03.08.11)
Практика: Разминочные задачи pdf
topsort1.Топологическая сортировка — 1pdf
topsort2.Топологическая сортировка — 2pdf
console1.Поиск набора образцовpdf
mincoin1.Сдачи нет! — 1pdf
mincoin2.Сдачи нет! — 2pdf
msquare.Магический квадратpdf
Лекция: Общие рекомендации
  1. Как тестировать задачи
    1. Какие тесты подсовывать
      • Минимальные и другие крайние случаи
      • Простые случаи
      • Подлые случаи с небольшими примерами
      • Генераторы для больших тестов
      • Максимальные тесты вообще
      • Максимальные тесты для вашего решения
      • Все случаи для вашего решения
    2. Подсовывать тест, на который вы заранее (вручную) не нашли ответ, наполовину бессмысленно (это и про большие тесты тоже)
    3. Тестирование со знанием решения и без него
    4. Стресс-тестирование
    5. Отладка на минимальном примере
    6. Сохранение тестов
    7. Использование команды assert
    8. Примеры (обсуждение на примере задачи топологической сортировки)
  2. Читать все условия сначала
Лекция: Продвинутые применения поиска в глубину
  1. Топологическая сортировка
  2. Сильная связность
    1. Компоненты сильной связности. Алгоритм поиска
    2. Конденсация графа. Алгоритм поиска
    3. База и антибаза. Алгоритм поиска
    4. 2-SAT
  3. Мосты и точки сочленения
  4. Эйлеровы циклы и пути
    1. Определение. Критерий существования цикла и пути
    2. Нахождение эйлеровых циклов и путей в ориентированных и неориентированных графах

День 2 (04.08.11)
Практика: Задачи на поиск в глубину и 2-SAT pdf
firesafe.Пожарная безопасностьpdf
domino.Марсианское доминоpdf
points.Точки сочлененияpdf
bridges.Мостыpdf
contest.Контест!pdf
Лекция: Паросочетания. Элементарные потоки
  1. Паросочетания в двудольном графе и связанные темы
    1. Определения
      • Паросочетание
      • Вершинное покрытие
      • Независимое множество
      • Связь понятий для произвольного графа
    2. Поиск паросочетания в двудольном графе: простой алгоритм
    3. Алгоритм Куна
    4. Максимальное независимое множество в двудольном графе
    5. Минимальное вершинное покрытие в двудольном графе
  2. Элементарные потоки
    1. Определения
    2. Элементарный алгоритм поиска
      • Минимальный разрез
      • Остаточная сеть
      • Дополняющий путь
      • Поиск дополняющих путей поиском в глубину, оценка O(Ef*)
      • Поиск дополняющих путей поиском в ширину (алгоритм Эдмонса-Карпа)
    3. Минимальный разрез: связь с задачей о потоке и доказательство корректности алгоритма поиска потока
    4. Масштабирование потока

День 3 (05.08.11)
Практика: Задачи на паросочетания и потоки. Тестирование pdf
pairs.Паросочетаниеpdf
flow.Максимальный потокpdf
king.Корольpdf
topsort2t.Топологическая сортировка 2: тестыpdf
Лекция: Потоки (mincost-maxflow). Least common ancestor. Disjoint set union
  1. Связь задачи о потоке с задачей о паросочетании
  2. Mincost-maxflow
    1. Определения
    2. Теорема об отрицательных циклах в остаточной сети
    3. Алгоритмы поиска
      • Алгоритм с Фордом-Беллманом
      • Алгоритм с потенциалами и Дейкстрой. Доказательство корректности
    4. Задача о назачениях
  3. СНМ
    1. Сжатие путей и ранговая эвристика
    2. Доказательство log(n) для сжатия путей
    3. RMQ-offline без сведения к LCA(*)
  4. Least common ancestor
    1. LCA online(двоичный подъем)
    2. LCA offline(алгоритм Тарьяна для поиска ближайшего общего предка)
    3. Сведение к задаче RMQ +- 1

День 4 (06.08.11)
Практика: Задачи на maxflow-mincost и LCA pdf
molecule.Химияpdf
brides.В поисках невестpdf
lca.Least Common Ancestorpdf
rmq.Range Minimum Querypdf
Лекция: Поиск подстрок
  1. Алгоритм Кнута-Морисса-Пратта
  2. Z-функция
  3. КМП и Z-функция за $O(|S|)$ памяти
  4. Бор
  5. Алгоритм Ахо-Корасик
  6. Хэши

День 5 (07.08.11)
Практика: Задачи на поиск подстрок pdf
yandex.Яндексpdf
palindr.Палиндромыpdf
console2.Поиск набора образцов 2pdf
birthday.Египетские дни рожденияpdf
Лекция: Суффиксный автомат
  1. Автомат. Определение, простейшие примеры.
  2. Несжатое суффиксное дерево
  3. Алгоритм построения суффиксного автомата за O(N)
    1. Правые контексты.
    2. Разбиение подстрок на классы эквивалентности
    3. Суффиксные ссылки

День 6 (08.08.11)
Практика: Задачи на суффиксный автомат pdf
nenokku.Неноккуpdf
supersub.Головоломка "Суперподстрока"pdf
Лекция: Продвинутое динамическое программирование
  1. Элементарные примеры ДП
  2. Восстановление ответа в задачах на ДП
    1. Примеры рекурсивного восстановления решения
    2. Общая концепция
    3. Возможность нерекурсивной реализации
    4. Вывод лексикографически первого решения
    5. Нетривиальная процедура вывода решения (алг. Флойда с сохранением промежуточной вершины)
    6. Вывод k-ого решения (опреление объекта по номеру)
    7. Определение номера по объекту
  3. Способы написания ДП (на примере задачи о наборе заданной суммы заданным набором монет)
    1. ДП с просмотром назад
    2. ДП с просмотром вперед
    3. Рекурсия с запоминанием результата (ленивое ДП)
  4. Виды задач на ДП
    1. Линейное ДП (последовательности нулей и единиц без двух единиц подряд)
    2. Многомерное ДП (наибольшая общая подпоследовательность)
    3. ДП на подотрезках (максимальный подпалиндром)
    4. ДП по полной сумме (задача о рюкзаке или о наборе суммы заданным набором монет)
    5. ДП на ациклических графах (наидлиннейший путь)
    6. ДП на деревьях (наидлиннейший путь или макс. паросочетание)
    7. ДП на подмножествах (паросочетание в произвольном графе за $2^N\cdot P(N)$)
    8. ДП по профилю (симпатичные узоры)
    9. ДП по изломанному профилю

День 7 (10.08.11)
Практика: Задачи на ДП pdf
nice.Симпатичные узоры — 1pdf
nice2.Симпатичные узоры — 2pdf
buratino.Буратиноpdf
numbers.Числаpdf
network.Сетьpdf
seq.Последовательностьpdf
Лекция: Приемы решения задач на P- и Z-функции и на ДП
  1. Приемы решения задач на P- и Z-функции
    1. Разбор задачи basis: решение с помощью P- и с помощью Z-функции
    2. Разбор задачи cubes: решение с помощью P- и с помощью Z-функции
    3. Разбор задачи prof: решение с помощью Z-функции, сложности с решением с помощью P-функции
    4. Разбор задачи invonly: решение с помощью Z-функции, сложности с решением с помощью P-функции
  2. Приемы решения задач на ДП
    1. Разбор задачи censored
    2. Идея решения задачи casino
    3. Разбор задачи html
    4. Идея решения задачи holidays

День 8 (11.08.11)
Практика: Задачи на P/Z-функцию и на ДП pdf
prof.Жужжащий профессорpdf
cubes.Кубикиpdf
html.Восстановление HTML файлаpdf
censored.Цензураpdf
Лекция: Игры на графах
  1. Определения
  2. Решение динамикой
    1. Метод проигрышных и выигрышных позиций
    2. Игры со стоимостью на ациклических графах
    3. Ретроанализ, в том числе на циклических графах
  3. Функция Гранди
    1. Сумма игр. Сумма игр, как игра на ациклическом графе
    2. Функция Гранди. Определение
    3. Простейшие примеры: простой ним; ним, в котором можно брать не более $k$ камней
    4. Функция Гранди от суммы игр, как xor функций Гранди. Поиск хода в даную функцию Гранди в общем случае.
    5. Примеры задач на функцию Гранди
      • Ним с делением кучки на две части
      • Ним с делением кучки на произвольное количество частей
      • Штирлиц и очередь
      • Задача choko
      • Hackenbush. Поиск выигрышного хода

День 9 (12.08.11)
Практика: Задачи на игры pdf
choco.Шоколадкаpdf
stones.Камниpdf
chocorev.Шоколадка — революцияpdf
woodcut.Дровосекpdf
Лекция: Матрицы
  1. Определения и действия над матрицами
  2. Решение линейных рекуррентных соотношений
    1. Сведение ЛРС к матричному уравнению
    2. Быстрое умножение и возведение в степень чисел
      • Связь с двоичной системой счисления
    3. Быстрое решение ЛРС с операциями по модулю
    4. Применение к ДП
    5. Если требуется длинная арифметика
  3. Метод Гаусса решения систем линейных уравнений

День 10 (13.08.11)
Практика: Задачи на матрицы pdf
nice3.Симпатичные узоры — 3pdf
rng.Генератор случайных чиселpdf
gauss.Система линейных уравненийpdf
Лекция: Задачи на отрезках

День 11 (16.08.11)
Практика: Задачи на задачи на отрезках pdf
stars.Звездыpdf
rvq.Range Variation Querypdf
windows.Окнаpdf
sum2.И снова суммаpdf
movetofront.Вперед!pdf
step.Шагиpdf
elephants.Слоникиpdf
rect2.Прямоугольники - 2pdf
upit.Вопросpdf
matrix.Матрицаpdf
Лекция: Декартовы деревья

День 12 (17.08.11)
Практика: Продолжение задач на задачи на отрезках pdf
Лекция: Последняя лекция
  1. Венгерский алгоритм
  2. Определитель матрицы
  3. Решение систем линейных уравнений с нулевым определителем