Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Специалист
Длительность:
7:12:00
Студентов:
2486
Выпускников:
115
Качество курса:
4.77 | 3.92
В курсе рассказывается о базовых и "продвинутых" (advanced) алгоритмах для школьников. Этот курс читался на летней компьютерной школе для участников олимпиад по информатике.
Рассматривается широкий список алгоритмов: двоичный поиск, методы сортировки, поиска кратчайшего пути в графе и обход графа в глубину. Изучаются остовные деревья, динамическое программирование, динамика на деревьях, вопросы вычислительной геометрии и алгоритмы работы со строками.
Специальности: Программист
 

План занятий

Занятие
Заголовок <<
Дата изучения
Двоичный поиск
В лекции подробно рассматриваются быстрая сортировка и сортировка слиянием, относящиеся к группе сортировок сравнения. Подробно разбираются сортировка подсчетом, цифровая и корзинная сортировки. Для каждого метода сортировки приводятся оценки времени выполнения. Рассматривается задача Райта для графов, приводится пример двоичного поиска по ответам
Оглавление
-
Алгоритмы и методы сортировки. Алгоритмы нахождения кратчайшего пути в графе
В первой половине лекции подробно рассматриваются метод сортировки подсчетом и метод цифровой (поразрядной) сортировки. Приводятся оценки времени их выполнения. Дается определение понятия списка, программно реализуются основные операции работы со списком. Во второй половине лекции рассматриваются алгоритм поиска вершины в графе в ширину и алгоритм Дейкстры нахождения кратчайшего пути во взвешенном графе. Для каждого алгоритма приводятся варианты программной реализации, оценки времени выполнения, примеры практического использования
Оглавление
-
Алгоритмы и методы поиска кратчайшего пути в графе
В данной лекции приводится метод хранения графа в виде списка. Подробно рассматриваются алгоритмы обхода графа в ширину и в глубину, алгоритмы Форда-Беллмана и Флойда поиска кратчайшего пути во взвешенном графе. Для каждого алгоритма приводятся варианты программной реализации, оценки времени выполнения, примеры практического использования
Оглавление
-
Алгоритм обхода графа в глубину
В лекции рассматривается применение алгоритма обхода графа в глубину к решению практических задач. В начале лекции подробно рассматривается алгоритм метода и его программная реализация. Далее рассматривается применение метода к решению задач поиска циклов в графе, топологической сортировки вершин, поиска компонент связности и сильной связности в графе
Оглавление
-
Алгоритм DFS
В первой половине лекции рассматривается применение алгоритма DFS к задаче о мостах и задаче поиска точек сочленения графа. Подробно разбираются алгоритмы решения и варианты их программной реализации. Формулируются и доказываются критерии существования эйлеровых цикла и пути в графе. Во второй половине лекции вводятся понятия новых типов данных - кучи и очереди с приоритетами. Определяются основные операции над элементами данных типов, приводятся варианты их программной реализации
Оглавление
-
Системы непересекающихся множеств. Остовные деревья
-
Динамическое программирование
В первой части лекции повторяются основные моменты алгоритмов Прима и Краскала построения остовных деревьев. Во второй части вводится понятие динамического программирования, рассматриваются алгоритмы вычисления числа сочетаний из n по k. В заключительной части лекции подробно разбираются несколько примеров задач динамического программирования
Оглавление
-
Динамическое программирование. Деревья разбора
Начало лекции посвящено повторению пройденного в предыдущей лекции материала. Подробно разбираются решения задач на разбиение числа и поиск наборов чисел с суммой меньше заданного методом динамического программирования. Дается понятие динамики на подотрезках. Подробно рассматриваются алгоритмы работы с деревьями разбора
Оглавление
-
Динамика на деревьях
В данной лекции на примерах решения задач подробно разбираются основные моменты работы с использованием динамики на деревьях. Дается определение понятия триангуляции. Решаются задачи на повторение пройденного материала
-
Вычислительная геометрия
Лекция посвящена вопросам программирования операций над геометрическими объектами. Даются определения основным геометрическим примитивам, приводятся возможные варианты их хранения в памяти ПК. Подробно рассматриваются векторы, операции над ними. Дается понятие полярной системы координат, обсуждаются ее достоинства и недостатки. Разбираются несколько задач на способы задания прямой. Обращается внимание на особенности сравнения вещественных чисел в ПК
Оглавление
-
Вычислительная геометрия
Лекция посвящена работе с многоугольниками. Рассматриваются алгоритмы Джарвиса и Грэхема построения выпуклых оболочек. Вводится понятие двоичного дерева поиска.
-
Строки
Лекция посвящена работе со строками. Рассматриваются алгоритмы Кнута-Морриса и Z-алгоритм поиска подстроки в строке. Вводится понятие Z-функции, приводится алгоритм ее вычисления
Оглавление
-
1 час 40 минут
-
Олег Марков
Олег Марков

Уточните, пожалуйста, какая нужна предварительная подготовка для прохождения курса Базовые и "продвинутые" алгоритмы для школьников.

Примерно на какой класс рассчитан.