Information
Базовые и "продвинутые" алгоритмы для школьников
: Information
Created: 04.04.2011 | Level: for all | Cost: 490.00 руб. | Duration: 14 дней
В курсе рассказывается о базовых и "продвинутых" (advanced) алгоритмах для школьников. Этот курс читался на летней компьютерной школе для участников олимпиад по информатике.
Рассматривается широкий список алгоритмов: двоичный поиск, методы сортировки, поиска кратчайшего пути в графе и обход графа в глубину. Изучаются остовные деревья, динамическое программирование, динамика на деревьях, вопросы вычислительной геометрии и алгоритмы работы со строками.
План занятий
| Lesson | Title << | Date |
|---|---|---|
| - | ||
Lecture 1 | Двоичный поиск
В лекции подробно рассматриваются быстрая сортировка и сортировка слиянием, относящиеся к группе сортировок сравнения. Подробно разбираются сортировка подсчетом, цифровая и корзинная сортировки. Для каждого метода сортировки приводятся оценки времени выполнения. Рассматривается задача Райта для графов, приводится пример двоичного поиска по ответам
| - |
Тест 136 minutes | - | |
Lecture 2 | Алгоритмы и методы сортировки. Алгоритмы нахождения кратчайшего пути в графе
В первой половине лекции подробно рассматриваются метод сортировки подсчетом и метод цифровой (поразрядной) сортировки. Приводятся оценки времени их выполнения. Дается определение понятия списка, программно реализуются основные операции работы со списком. Во второй половине лекции рассматриваются алгоритм поиска вершины в графе в ширину и алгоритм Дейкстры нахождения кратчайшего пути во взвешенном графе. Для каждого алгоритма приводятся варианты программной реализации, оценки времени выполнения, примеры практического использования
| - |
Тест 236 minutes | - | |
Lecture 3 | Алгоритмы и методы поиска кратчайшего пути в графе
В данной лекции приводится метод хранения графа в виде списка. Подробно рассматриваются алгоритмы обхода графа в ширину и в глубину, алгоритмы Форда-Беллмана и Флойда поиска кратчайшего пути во взвешенном графе. Для каждого алгоритма приводятся варианты программной реализации, оценки времени выполнения, примеры практического использования
| - |
Тест 336 minutes | - | |
Lecture 4 | Алгоритм обхода графа в глубину
В лекции рассматривается применение алгоритма обхода графа в глубину к решению практических задач. В начале лекции подробно рассматривается алгоритм метода и его программная реализация. Далее рассматривается применение метода к решению задач поиска циклов в графе, топологической сортировки вершин, поиска компонент связности и сильной связности в графе
Contents
| - |
Тест 436 minutes | - | |
Lecture 5 | Алгоритм DFS
В первой половине лекции рассматривается применение алгоритма DFS к задаче о мостах и задаче поиска точек сочленения графа. Подробно разбираются алгоритмы решения и варианты их программной реализации. Формулируются и доказываются критерии существования эйлеровых цикла и пути в графе. Во второй половине лекции вводятся понятия новых типов данных - кучи и очереди с приоритетами. Определяются основные операции над элементами данных типов, приводятся варианты их программной реализации
| - |
Тест 536 minutes | - | |
Lecture 6 | Системы непересекающихся множеств. Остовные деревья
В лекции вводится понятие системы непересекающихся множеств (СНМ). Рассматриваются примеры СНМ, возможные варианты реализации, основные операции над элементами СНМ. Во второй половине лекции рассматриваются остовные деревья (ОД), объясняются основные алгоритмы построения ОД
| - |
Тест 636 minutes | - | |
Lecture 7 | Динамическое программирование
В первой части лекции повторяются основные моменты алгоритмов Прима и Краскала построения остовных деревьев. Во второй части вводится понятие динамического программирования, рассматриваются алгоритмы вычисления числа сочетаний из n по k. В заключительной части лекции подробно разбираются несколько примеров задач динамического программирования
| - |
Тест 736 minutes | - | |
Lecture 8 | Динамическое программирование. Деревья разбора
Начало лекции посвящено повторению пройденного в предыдущей лекции материала. Подробно разбираются решения задач на разбиение числа и поиск наборов чисел с суммой меньше заданного методом динамического программирования. Дается понятие динамики на подотрезках. Подробно рассматриваются алгоритмы работы с деревьями разбора
| - |
Тест 836 minutes | - | |
Lecture 9 | Динамика на деревьях
В данной лекции на примерах решения задач подробно разбираются основные моменты работы с использованием динамики на деревьях. Дается определение понятия триангуляции. Решаются задачи на повторение пройденного материала
| - |
Тест 936 minutes | - | |
Lecture 10 | Вычислительная геометрия
Лекция посвящена вопросам программирования операций над геометрическими объектами. Даются определения основным геометрическим примитивам, приводятся возможные варианты их хранения в памяти ПК. Подробно рассматриваются векторы, операции над ними. Дается понятие полярной системы координат, обсуждаются ее достоинства и недостатки. Разбираются несколько задач на способы задания прямой. Обращается внимание на особенности сравнения вещественных чисел в ПК
Contents
| - |
Тест 1036 minutes | - | |
Lecture 11 | Вычислительная геометрия
Лекция посвящена работе с многоугольниками. Рассматриваются алгоритмы Джарвиса и Грэхема построения выпуклых оболочек. Вводится понятие двоичного дерева поиска.
| - |
Тест 1136 minutes | - | |
Lecture 12 | Строки
Лекция посвящена работе со строками. Рассматриваются алгоритмы Кнута-Морриса и Z-алгоритм поиска подстроки в строке. Вводится понятие Z-функции, приводится алгоритм ее вычисления
| - |
Тест 1236 minutes | - | |
5 hours | - |