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

День 1 (29.07.12)
Практика. Разминочные задачи
Лекция. Общие рекомендации
Лекция. Поиск подстрок (основы)
День 2 (30.07.12)
Практика. Поиск подстрок
Лекция. Поиск подстрок (продвинутость)
День 3 (31.07.12)
Практика. Задачи на продвинутый поиск подстрок
Лекция. Суффиксный массив
День 4 (01.08.12)
Практика. Задачи на суффиксные структуры данных
Лекция. Продвинутые применения поиска в глубину и паросочетания
День 5 (02.08.12)
Практика. Задачи на поиск в глубину
Лекция. Элементарные потоки
Лекция. Mincost-maxflow
День 6 (03.08.12)
Практика. Задачи на потоки
Лекция. Продвинутое динамическое программирование
День 7 (05.08.11)
Практика. Задачи на ДП
Лекция. Геометрия
День 8 (06.08.11)
Практика. Задачи на геометрию
Лекция. Игры на графах
День 9 (07.08.11)
Практика. Задачи на игры
Лекция. Матрицы
День 10 (08.08.11)
Практика. Задачи на матрицы
Лекция. Задачи на отрезках
День 11 (11.08.11)
Практика. Задачи на задачи на отрезках
Лекция. Декартовы деревья
Лекция. Задачная лекция на декартовы деревья и на задачи на отрезках
День 12 (12.08.11)
Практика. Продолжение задач на задачи на отрезках
Лекция. Последняя лекция

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

День 2 (30.07.12)
Практика: Поиск подстрок pdf
birthday.Египетские дни рожденияpdf
palindr.Палиндромыpdf
cubes.Кубики (без хэшей!)pdf
console1t.Поиск набора образцов 1: тестыpdf
Лекция: Поиск подстрок (продвинутость)
  1. Про антихэш-тесты
  2. Z-функция
  3. Z-функция за O(|S|) памяти
  4. Бор
  5. Алгоритм Ахо-Корасик

День 3 (31.07.12)
Практика: Задачи на продвинутый поиск подстрок pdf
prof.Жужжащий профессорpdf
yandex.Яндекс (без хэшей!)pdf
palindr2.Палиндромы-2pdf
console2.Поиск набора образцов 2pdf
Лекция: Суффиксный массив

День 4 (01.08.12)
Практика: Задачи на суффиксные структуры данных pdf
inffraction.Бесконечная дробьpdf
lcs.Наибольшая общая подстрокаpdf
refrain.Рефренpdf
Лекция: Продвинутые применения поиска в глубину и паросочетания
  1. Поиск в глубину
    1. Сильная связность
      • Компоненты сильной связности. Алгоритм поиска
      • Конденсация графа. Алгоритм поиска
      • База и антибаза. Алгоритм поиска
      • 2-SAT
    2. Мосты и точки сочленения
    3. Эйлеровы циклы и пути
      • Определение. Критерий существования цикла и пути
      • Нахождение эйлеровых циклов и путей в ориентированных и неориентированных графах
      • (*) Найти минимальное число путей так, чтобы по каждому ребру проходил один и ровно один путь
  2. Паросочетания и связанные с ними понятия
    1. Определения
      • Паросочетание
      • Вершинное покрытие
      • Независимое множество
      • Связь понятий для произвольного графа
    2. Поиск паросочетания в двудольном графе: простой алгоритм
    3. Алгоритм Куна
    4. Максимальное независимое множество в двудольном графе
    5. Минимальное вершинное покрытие в двудольном графе

День 5 (02.08.12)
Практика: Задачи на поиск в глубину pdf
Лекция: Элементарные потоки
Лекция: Mincost-maxflow
  1. Связь задачи о потоке с задачей о паросочетании
  2. Mincost-maxflow
    1. Определения
    2. Теорема об отрицательных циклах в остаточной сети
    3. Алгоритмы поиска
      • Алгоритм с Фордом-Беллманом
      • Алгоритм с потенциалами и Дейкстрой. Доказательство корректности
    4. Задача о назачениях

День 6 (03.08.12)
Практика: Задачи на потоки 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 (05.08.11)
Практика: Задачи на ДП pdf
nice.Симпатичные узоры — 1pdf
nice2.Симпатичные узоры — 2pdf
buratino.Буратиноpdf
numbers.Числаpdf
network.Сетьpdf
seq.Последовательностьpdf
Лекция: Геометрия

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

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

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

День 11 (11.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 (12.08.11)
Практика: Продолжение задач на задачи на отрезках pdf
Лекция: Последняя лекция