|
Уточните, пожалуйста, какая нужна предварительная подготовка для прохождения курса Базовые и "продвинутые" алгоритмы для школьников. Примерно на какой класс рассчитан. |
Базовые и "продвинутые" алгоритмы для школьников: Информация
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 39 студентам
Уровень:
Специалист
Длительность:
7:12:00
Студентов:
2495
Выпускников:
117
Качество курса:
4.77 | 3.92
В курсе рассказывается о базовых и "продвинутых" (advanced) алгоритмах для школьников. Этот курс читался на летней компьютерной школе для участников олимпиад по информатике.
Рассматривается широкий список алгоритмов: двоичный поиск, методы сортировки, поиска кратчайшего пути в графе и обход графа в глубину. Изучаются остовные деревья, динамическое программирование, динамика на деревьях, вопросы вычислительной геометрии и алгоритмы работы со строками.
Специальности: Программист
Теги: алгоритм Дейкстры, алгоритмы, взвешенный граф, кратчайший путь, поиск, программная реализация, сортировка
План занятий
Занятие
Заголовок <<
Дата изучения
Двоичный поиск
В лекции подробно рассматриваются быстрая сортировка и сортировка слиянием, относящиеся к группе сортировок сравнения. Подробно разбираются сортировка подсчетом, цифровая и корзинная сортировки. Для каждого метода сортировки приводятся оценки времени выполнения. Рассматривается задача Райта для графов, приводится пример двоичного поиска по ответам
-
Алгоритмы и методы сортировки. Алгоритмы нахождения кратчайшего пути в графе
В первой половине лекции подробно рассматриваются метод сортировки подсчетом и метод цифровой (поразрядной) сортировки. Приводятся оценки времени их выполнения. Дается определение понятия списка, программно реализуются основные операции работы со списком. Во второй половине лекции рассматриваются алгоритм поиска вершины в графе в ширину и алгоритм Дейкстры нахождения кратчайшего пути во взвешенном графе. Для каждого алгоритма приводятся варианты программной реализации, оценки времени выполнения, примеры практического использования
-
Алгоритмы и методы поиска кратчайшего пути в графе
В данной лекции приводится метод хранения графа в виде списка. Подробно рассматриваются алгоритмы обхода графа в ширину и в глубину, алгоритмы Форда-Беллмана и Флойда поиска кратчайшего пути во взвешенном графе. Для каждого алгоритма приводятся варианты программной реализации, оценки времени выполнения, примеры практического использования
-
Алгоритм обхода графа в глубину
В лекции рассматривается применение алгоритма обхода графа в глубину к решению практических задач. В начале лекции подробно рассматривается алгоритм метода и его программная реализация. Далее рассматривается применение метода к решению задач поиска циклов в графе, топологической сортировки вершин, поиска компонент связности и сильной связности в графе
Оглавление
- Введение
- Обход графа в глубину
- Применение метода обхода графа в глубину к задаче поиска цикла в графе
- Применение метода обхода графа в глубину к задаче топологической сортировки вершин
- Применение метода обхода графа в глубину к задаче поиска компоненты сильной связности в ориентированном графе
- Поиск компонент связности в неориентированном графе
-
Алгоритм DFS
В первой половине лекции рассматривается применение алгоритма DFS к задаче о мостах и задаче поиска точек сочленения графа. Подробно разбираются алгоритмы решения и варианты их программной реализации. Формулируются и доказываются критерии существования эйлеровых цикла и пути в графе. Во второй половине лекции вводятся понятия новых типов данных - кучи и очереди с приоритетами. Определяются основные операции над элементами данных типов, приводятся варианты их программной реализации
-
Системы непересекающихся множеств. Остовные деревья
В лекции вводится понятие системы непересекающихся множеств (СНМ). Рассматриваются примеры СНМ, возможные варианты реализации, основные операции над элементами СНМ. Во второй половине лекции рассматриваются остовные деревья (ОД), объясняются основные алгоритмы построения ОД
-
Динамическое программирование
В первой части лекции повторяются основные моменты алгоритмов Прима и Краскала построения остовных деревьев. Во второй части вводится понятие динамического программирования, рассматриваются алгоритмы вычисления числа сочетаний из n по k. В заключительной части лекции подробно разбираются несколько примеров задач динамического программирования
-
Динамическое программирование. Деревья разбора
Начало лекции посвящено повторению пройденного в предыдущей лекции материала. Подробно разбираются решения задач на разбиение числа и поиск наборов чисел с суммой меньше заданного методом динамического программирования. Дается понятие динамики на подотрезках. Подробно рассматриваются алгоритмы работы с деревьями разбора
-
Динамика на деревьях
В данной лекции на примерах решения задач подробно разбираются основные моменты работы с использованием динамики на деревьях. Дается определение понятия триангуляции. Решаются задачи на повторение пройденного материала
-
Вычислительная геометрия
Лекция посвящена вопросам программирования операций над геометрическими объектами. Даются определения основным геометрическим примитивам, приводятся возможные варианты их хранения в памяти ПК. Подробно рассматриваются векторы, операции над ними. Дается понятие полярной системы координат, обсуждаются ее достоинства и недостатки. Разбираются несколько задач на способы задания прямой. Обращается внимание на особенности сравнения вещественных чисел в ПК
Оглавление
- Введение
- Геометрические примитивы
- Векторы. Операции над векторами
- Полярная система координат
- Прямая. Способы задания прямой
- Метод Крамера решения систем линейных алгебраических уравнений
- Задача нахождения полярного угла
- Параметрическое задание прямой отрезка, луча
- Особенности сравнения вещественных чисел
-
Вычислительная геометрия
Лекция посвящена работе с многоугольниками. Рассматриваются алгоритмы Джарвиса и Грэхема построения выпуклых оболочек. Вводится понятие двоичного дерева поиска.
-
Строки
Лекция посвящена работе со строками. Рассматриваются алгоритмы Кнута-Морриса и Z-алгоритм поиска подстроки в строке. Вводится понятие Z-функции, приводится алгоритм ее вычисления
-
Олег Марков