Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 3000.00 руб. | Длительность: 14 дней
В курсе рассказывается о базовых и "продвинутых" (advanced) алгоритмах для школьников. Этот курс читался на летней компьютерной школе для участников олимпиад по информатике.
Рассматривается широкий список алгоритмов: двоичный поиск, методы сортировки, поиска кратчайшего пути в графе и обход графа в глубину. Изучаются остовные деревья, динамическое программирование, динамика на деревьях, вопросы вычислительной геометрии и алгоритмы работы со строками.

План занятий

ЗанятиеЗаголовок <<Дата изучения
-
Лекция 1
1 час 49 минут
Двоичный поиск
В лекции подробно рассматриваются быстрая сортировка и сортировка слиянием, относящиеся к группе сортировок сравнения. Подробно разбираются сортировка подсчетом, цифровая и корзинная сортировки. Для каждого метода сортировки приводятся оценки времени выполнения. Рассматривается задача Райта для графов, приводится пример двоичного поиска по ответам
Оглавление
-
Тест 1
36 минут
-
Лекция 2
1 час 55 минут
Алгоритмы и методы сортировки. Алгоритмы нахождения кратчайшего пути в графе
В первой половине лекции подробно рассматриваются метод сортировки подсчетом и метод цифровой (поразрядной) сортировки. Приводятся оценки времени их выполнения. Дается определение понятия списка, программно реализуются основные операции работы со списком. Во второй половине лекции рассматриваются алгоритм поиска вершины в графе в ширину и алгоритм Дейкстры нахождения кратчайшего пути во взвешенном графе. Для каждого алгоритма приводятся варианты программной реализации, оценки времени выполнения, примеры практического использования
Оглавление
-
Тест 2
36 минут
-
Лекция 3
2 часа 10 минут
Алгоритмы и методы поиска кратчайшего пути в графе
В данной лекции приводится метод хранения графа в виде списка. Подробно рассматриваются алгоритмы обхода графа в ширину и в глубину, алгоритмы Форда-Беллмана и Флойда поиска кратчайшего пути во взвешенном графе. Для каждого алгоритма приводятся варианты программной реализации, оценки времени выполнения, примеры практического использования
Оглавление
-
Тест 3
36 минут
-
Лекция 4
1 час 55 минут
Алгоритм обхода графа в глубину
В лекции рассматривается применение алгоритма обхода графа в глубину к решению практических задач. В начале лекции подробно рассматривается алгоритм метода и его программная реализация. Далее рассматривается применение метода к решению задач поиска циклов в графе, топологической сортировки вершин, поиска компонент связности и сильной связности в графе
Оглавление
-
Тест 4
36 минут
-
Лекция 5
1 час 51 минута
Алгоритм DFS
В первой половине лекции рассматривается применение алгоритма DFS к задаче о мостах и задаче поиска точек сочленения графа. Подробно разбираются алгоритмы решения и варианты их программной реализации. Формулируются и доказываются критерии существования эйлеровых цикла и пути в графе. Во второй половине лекции вводятся понятия новых типов данных - кучи и очереди с приоритетами. Определяются основные операции над элементами данных типов, приводятся варианты их программной реализации
Оглавление
-
Тест 5
36 минут
-
Лекция 6
1 час 26 минут
Системы непересекающихся множеств. Остовные деревья
-
Тест 6
36 минут
-
Лекция 7
1 час 39 минут
Динамическое программирование
В первой части лекции повторяются основные моменты алгоритмов Прима и Краскала построения остовных деревьев. Во второй части вводится понятие динамического программирования, рассматриваются алгоритмы вычисления числа сочетаний из n по k. В заключительной части лекции подробно разбираются несколько примеров задач динамического программирования
Оглавление
-
Тест 7
36 минут
-
Лекция 8
1 час 22 минуты
Динамическое программирование. Деревья разбора
Начало лекции посвящено повторению пройденного в предыдущей лекции материала. Подробно разбираются решения задач на разбиение числа и поиск наборов чисел с суммой меньше заданного методом динамического программирования. Дается понятие динамики на подотрезках. Подробно рассматриваются алгоритмы работы с деревьями разбора
Оглавление
-
Тест 8
36 минут
-
Лекция 9
1 час 50 минут
Динамика на деревьях
В данной лекции на примерах решения задач подробно разбираются основные моменты работы с использованием динамики на деревьях. Дается определение понятия триангуляции. Решаются задачи на повторение пройденного материала
-
Тест 9
36 минут
-
Лекция 10
1 час 37 минут
Вычислительная геометрия
Лекция посвящена вопросам программирования операций над геометрическими объектами. Даются определения основным геометрическим примитивам, приводятся возможные варианты их хранения в памяти ПК. Подробно рассматриваются векторы, операции над ними. Дается понятие полярной системы координат, обсуждаются ее достоинства и недостатки. Разбираются несколько задач на способы задания прямой. Обращается внимание на особенности сравнения вещественных чисел в ПК
Оглавление
-
Тест 10
36 минут
-
Лекция 11
1 час 27 минут
Вычислительная геометрия
Лекция посвящена работе с многоугольниками. Рассматриваются алгоритмы Джарвиса и Грэхема построения выпуклых оболочек. Вводится понятие двоичного дерева поиска.
-
Тест 11
36 минут
-
Лекция 12
1 час 34 минуты
Строки
Лекция посвящена работе со строками. Рассматриваются алгоритмы Кнута-Морриса и Z-алгоритм поиска подстроки в строке. Вводится понятие Z-функции, приводится алгоритм ее вычисления
Оглавление
-
Тест 12
36 минут
-
5 часов
-