Москва. Физматшкола 2007. Аминев Б.Д.

Тематический план

• 

  Тема 1

  Повторение. Входной контроль
• 

  Тема 2

  Рекурсия
• 

  Тема 3

  Расширенный алгоритм Евклида. Задачи, сводящиеся к вычислению НОД

  • Задачи Условия задач
• 

  Тема 4

  Алгоритм Евклида, Решето Эратосфена
• 

  Тема 5

  Расширенный алгоритм Евклида. Задачи, сводящиеся к вычислению НОД
• 

  Тема 6

  Функция Эйлера. Малая теорема Ферма

  • Задачи Условия задач
• 

  Тема 7

  Быстрое возведение в степень за O(logN)

  • Задачи Условия задач
• 

  Тема 8

  Алгоритм шифрования RSA
• 

  Тема 9

  Системы счисления
• 

  Тема 10

  Битовые операции, битовые сдвиги
• 

  Тема 11

  Комбинаторные алгоритмы (перестановки, сочетания)

  • Комбинаторный перебор и рекурсия, алгоритмы STL для организации перебора Гиперссылка
• 

  Тема 12

  Скобочные последовательности

  • Задачи Условия задач
  • Foxford: Правильные скобочные последовательности. Проверка на правильность. Гиперссылка
  • MAXimal: Правильные скобочные последовательности Гиперссылка
• 

  Тема 13

  Графы. Алгоритм поиска в глубину.

  • Задачи Условия задач
  • hecs.info Поиск в глубину Гиперссылка
  • Графы. Способы хранения Файл
  • Графы. Алгоритм поиска в глубину (depth-first search) Файл
• 

  Тема 14

  Графы. Алгоритм поиска в ширину.

  • Задачи Условия задач
  • Foxford: Алгоритм поиска в ширину Гиперссылка
• 

  Тема 15

  Алгоритм Дейкстры

  • Задачи Условия задач
  • Foxford: Алгоритм Дейкстры Гиперссылка
• 

  Тема 16

  Алгоритмы Флойда-Уоршелла и Форда-Беллмана

  • Задачи Условия задач
  • Foxford: Алгоритм Флойда Гиперссылка
  • Foxford: Алгоритм Форда-Беллмана Гиперссылка
  • MAXimal: Алгоритм Флойда-Уоршелла нахождения кратчайших путей между всеми парами вершин Гиперссылка
  • MAXimal: Алгоритм Форда-Беллмана Гиперссылка
• 

  Тема 17

  Одномерное динамическое программирование

  • Задачи Условия задач
  • Foxford: Одномерное динамическое программирование: количество способов Гиперссылка
  • Foxford: Одномерное динамическое программирование: наилучший способ Гиперссылка
  • Видеозаписи лекций ЛКШ: Числа Фибоначчи. Рекурсия с запоминанием. Гиперссылка
  • Видеозаписи лекций ЛКШ: Задачи о кузнечике: количество путей и самый выгодный путь. Гиперссылка
  • Видеозаписи лекций ЛКШ: Восстановление ответа в задаче о кузнечике: обратный ход или запоминание лучшего. Гиперссылка
  • Видеозаписи лекций ЛКШ: Общая схема решение задачи динамическим программированием. Гиперссылка
  • Habr: Всё, что вы хотели знать о динамическом программировании, но боялись спросить Гиперссылка
• 

  Тема 18

  Динамическое программирование по профилю

  • Задачи Условия задач
  • Василевский Б. Динамическое программирование по профилю Гиперссылка
  • Habr: Всё, что вы хотели знать о динамическом программировании, но боялись спросить Гиперссылка
  • MAXimal: Динамика по профилю. Задача "паркет" Гиперссылка
• 

  Тема 19

  Динамическое программирование по отрезкам и множествам

  • Задачи Условия задач
  • Habr: Всё, что вы хотели знать о динамическом программировании, но боялись спросить Гиперссылка
  • Habr: Динамика по подотрезкам: базовые вещи и «одна хорошо, а две лучше» Гиперссылка
• 

  Тема 20

  Префикс-функция. Z-функция. Алгоритм Кнута - Морриса - Пратта

  • Задачи Условия задач
  • MAXimal: Префикс-функция. Алгоритм Кнута-Морриса-Пратта Гиперссылка
  • MAXimal: Z-функция строки и её вычисление Гиперссылка
• 

  Тема 21
• 

  Тема 22
• 

  Тема 23
• 

  Тема 24
• 

  Тема 25
• 

  Тема 26
• 

  Тема 27
• 

  Тема 28
• 

  Тема 29
• 

  Тема 30
• 

  Тема 31
• 

  Тема 32
• 

  Тема 33
• 

  Тема 34