НОУ ИНТУИТ | Повышение квалификации | Базовые и "продвинутые" алгоритмы для школьников

Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность: 14 дней

Темы: Теория вычислений, Программирование, Алгоритмы и дискретные структуры, Дискретные структуры, Алгоритмы

В курсе рассказывается о базовых и "продвинутых" (advanced) алгоритмах для школьников. Этот курс читался на летней компьютерной школе для участников олимпиад по информатике.

Рассматривается широкий список алгоритмов: двоичный поиск, методы сортировки, поиска кратчайшего пути в графе и обход графа в глубину. Изучаются остовные деревья, динамическое программирование, динамика на деревьях, вопросы вычислительной геометрии и алгоритмы работы со строками.

Вам нравится? Нравится 1 студенту

| Поделиться |

Поддержать

Занятие	Заголовок <<	Дата изучения
	Экзамен экстерном	-
Лекция 1	Двоичный поиск В лекции подробно рассматриваются быстрая сортировка и сортировка слиянием, относящиеся к группе сортировок сравнения. Подробно разбираются сортировка подсчетом, цифровая и корзинная сортировки. Для каждого метода сортировки приводятся оценки времени выполнения. Рассматривается задача Райта для графов, приводится пример двоичного поиска по ответам Оглавление Введение Задача Райта Постановка задачи Алгоритм решения Практический пример Пример двоичного поиска по ответам Быстрая сортировка (Quick-Sort) Назначение Алгоритм реализации Программирование части Partition Особенности практической реализации сортировки Оценка времени выполнения алгоритма сортировки Пример использования сортировки Псевдослучайные числа k-я порядковая статистика. Нахождение k-той порядковой статистики Сортировка слиянием Алгоритм реализации Процедура слияния Оценка времени выполнения алгоритма сортировки Пример использования сортировки Обобщение материала по разделу "Сортировки сравнения" Сортировка подсчетом (Count Sort) Постановка задачи Алгоритм реализации. Оценка времени выполнения Цифровая сортировка (Radix Sort) Постановка задачи Алгоритм реализации Оценка времени выполнения Программирование алгоритма Корзинная сортировка (Basket Sort) Пример: сортировка людей по росту Оценка времени выполнения	-
Тест 1 36 минут	12 заданий	-
Лекция 2	Алгоритмы и методы сортировки. Алгоритмы нахождения кратчайшего пути в графе В первой половине лекции подробно рассматриваются метод сортировки подсчетом и метод цифровой (поразрядной) сортировки. Приводятся оценки времени их выполнения. Дается определение понятия списка, программно реализуются основные операции работы со списком. Во второй половине лекции рассматриваются алгоритм поиска вершины в графе в ширину и алгоритм Дейкстры нахождения кратчайшего пути во взвешенном графе. Для каждого алгоритма приводятся варианты программной реализации, оценки времени выполнения, примеры практического использования Оглавление Введение Сортировка подсчетом Сортировка подсчетом. Оценка времени выполнения Блочная сортировка подсчетом. Оценка времени выполнения Сортировка больших объемов данных Устойчивость сортировки Цифровая (поразрядная) сортировка Сортировка строк из двух символов. Оценка времени выполнения Сортировка строк из k символов. Оценка времени выполнения Сортировка целых чисел Список. Массив списков Определение списка Программная реализация списка Операция добавления элемента в список Организация хранения графа с помощью списка Алгоритм выбора свободного индекса Операция удаления элемента из списка Массив свободных ячеек Алгоритм поиска вершины в графе в ширину (Breath First Search) Задача нахождения минимального пути в невзвешенном графе Алгоритм решения Программная реализация. Оценка времени выполнения Задача нахождения минимального пути в гриде Циклическая очередь Задача нахождения минимального пути во взвешенном графе Алгоритм решения. Программная реализация. Оценка времени выполнения Оптимизация программного кода Простой пример работы алгоритма Memory Manager. Необходимость создания Memory Manager Пример поиска вершины в графе в глубину Программирование поиска вершины в невзвешенном графе в ширину на двух очередях. Оценка времени выполнения Задача нахождения кратчайшего пути в графе с ребрами длины 0 и 1 Алгоритм Дейкстры нахождения кратчайшего пути во взвешенном графе Постановка задачи Алгоритм решения Программная реализация. Оценка времени выполнения Восстановление кратчайшего пути	-
Тест 2 36 минут	12 заданий	-
Лекция 3	Алгоритмы и методы поиска кратчайшего пути в графе В данной лекции приводится метод хранения графа в виде списка. Подробно рассматриваются алгоритмы обхода графа в ширину и в глубину, алгоритмы Форда-Беллмана и Флойда поиска кратчайшего пути во взвешенном графе. Для каждого алгоритма приводятся варианты программной реализации, оценки времени выполнения, примеры практического использования Оглавление Введение Списки. Хранение графа в виде списка Организация храненния графа в виде списка Пример Подробное объяснение примера Организация перебора ребер графа, хранимого в виде списка Удаление элемента списка Алгоритм поиска вершины в графе в ширину Принцип работы алгоритма Программирование алгоритма на основе очереди. Оценка времени выполнения Случай "1-k" графа Программирование алгоритма на основе k очередей. Оценка времени выполнения Оптимизация работы алгоритма BFS "0-1" Оптимизация работы алгоритма Алгоритм Форда-Беллмана Принцип работы алгоритма Условия применения Схема реализации алгоритма. Необходимый и достаточный критерий существования цикла в графе Поиск отрицательного цикла в графе Оценка времени выполнения алгоритма Алгоритм Флойда Основная идея. Принцип работы Схема реализации алгоритма Оценка времени выполнения алгоритма Поиск отрицательных циклов в графе Поиск отрицательных циклов в неориентированном графе Обход графа в глубину Основная идея метода. Принцип работы Схема реализации алгоритма Оценка времени выполнения алгоритма Сравнение методов обхода графа в глубину и ширину Обратное ребро. Поиск отрицательного цикла в графе	-
Тест 3 36 минут	12 заданий	-
Лекция 4	Алгоритм обхода графа в глубину В лекции рассматривается применение алгоритма обхода графа в глубину к решению практических задач. В начале лекции подробно рассматривается алгоритм метода и его программная реализация. Далее рассматривается применение метода к решению задач поиска циклов в графе, топологической сортировки вершин, поиска компонент связности и сильной связности в графе Оглавление Введение Обход графа в глубину Основная идея метода Алгоритм реализации Классификация ребер графа относительно обхода в глубину Обход неориентированного графа в глубину Счетчик времени обработки вершин Применение счетчика времени обработки вершин Классификация вершин графа относительно обхода в глубину Применение метода обхода графа в глубину к задаче поиска цикла в графе Основная идея метода Восстановление пути Применение метода обхода графа в глубину к задаче топологической сортировки вершин Постановка задачи Алгоритм реализации метода Применение метода обхода графа в глубину к задаче поиска компоненты сильной связности в ориентированном графе Компонента сильной связности ориентированного графа Алгоритм поиска компонент сильной связности графа Свойства алгоритма поиска компонент сильной связности графа Поиск компонент связности в неориентированном графе Основные определения и понятия Алгоритм реализации	-
Тест 4 36 минут	12 заданий	-
Лекция 5	Алгоритм DFS В первой половине лекции рассматривается применение алгоритма DFS к задаче о мостах и задаче поиска точек сочленения графа. Подробно разбираются алгоритмы решения и варианты их программной реализации. Формулируются и доказываются критерии существования эйлеровых цикла и пути в графе. Во второй половине лекции вводятся понятия новых типов данных - кучи и очереди с приоритетами. Определяются основные операции над элементами данных типов, приводятся варианты их программной реализации Оглавление Введение Применение алгоритма DFS к задаче поиска точек сочленения графа Определение точки сочленения графа Переход к новой вершине графа Переход к просмотренной ранее вершине графа Обобщение алгоритма DFS для задачи поиска точек сочленения графа Применение алгоритма DFS к задаче о мостах Определение понятия мост в графе Определение понятий эйлерова пути и эйлерова цикла в графе Задача о мостах Критерий наличия эйлерова цикла в графе Критерий наличия эйлерова пути в графе Программирование алгоритма нахождения эйлерова пути в графе Куча Основные операции над элементами кучи Оценка времени выполнения основных операций над элементами кучи Определение понятия кучи. Организация хранения кучи в памяти ПК Реализация добавления элемента в кучу Написание процедуры всплытия элемента кучи Оценка времени выполнения операции добавления элемента в кучу Извлечение минимального элемента из кучи Сортировка массива с помощью кучи Очередь с приоритетами Определение. Основные операции над элементами очереди Пример очереди с приоритетом Внешние указатели	-
Тест 5 36 минут	12 заданий	-
Лекция 6	Системы непересекающихся множеств. Остовные деревья В лекции вводится понятие системы непересекающихся множеств (СНМ). Рассматриваются примеры СНМ, возможные варианты реализации, основные операции над элементами СНМ. Во второй половине лекции рассматриваются остовные деревья (ОД), объясняются основные алгоритмы построения ОД Оглавление Введение Системы непересекающихся множеств (СНМ) Определение. Основные функции Пример простой СНМ Наивная реализация СНМ Реализация СНМ списком Улучшение наивной реализации СНМ (весовая эвристика) Реализация СНМ в виде дерева Ранговая эвристика Эвристика сжатия путей Программирование функции, возвращающей индекс дерева по его элементу Остовные деревья Определение остовного дерева Разрез графа Лемма о разрезе и минимальном ребре Алгоритм Прима построения остовного дерева Алгоритм Краскала построения остовного дерева	-
Тест 6 36 минут	12 заданий	-
Лекция 7	Динамическое программирование В первой части лекции повторяются основные моменты алгоритмов Прима и Краскала построения остовных деревьев. Во второй части вводится понятие динамического программирования, рассматриваются алгоритмы вычисления числа сочетаний из n по k. В заключительной части лекции подробно разбираются несколько примеров задач динамического программирования Оглавление Введение Алгоритм Краскала построения остовного дерева Идея метода Программирование алгоритма Алгоритм Прима построения остовного дерева Идея метода Программирование алгоритма Введение в динамическое программирование Задача выбора k объектов из совокупности n объектов Число сочетаний из n по k Программирование алгоритма вычисления числа сочетаний из n по k Дерево вызовов Оптимизация алгоритма вычисления числа сочетаний из n по k Примеры задач на динамическое программирование Задача о камнях Динамическое программирование вперед Правильные скобочные последовательности Проверка правильности последовательности Точки разбиения последовательности Задача о черепашке Задача о нахождении максимальной возрастающей последовательности (пс) Задача о нахождении наибольшей общей подпоследовательности двух пс	-
Тест 7 36 минут	12 заданий	-
Лекция 8	Динамическое программирование. Деревья разбора Начало лекции посвящено повторению пройденного в предыдущей лекции материала. Подробно разбираются решения задач на разбиение числа и поиск наборов чисел с суммой меньше заданного методом динамического программирования. Дается понятие динамики на подотрезках. Подробно рассматриваются алгоритмы работы с деревьями разбора Оглавление Введение Повторение предыдущей лекции Задача о нахождении наибольшей общей подпоследовательности (ППС) для трех последовательностей (ПС) Программная реализация алгоритма решения задачи о нахождении наибольшей общей ППС для трех ПС Задача о разбиении числа n на k слагаемых Формулировка задачи: порядок слагаемых в разложении важен Решение задачи методом динамического программирования Формулировка задачи: порядок слагаемых в разложении не имеет значения Решение задачи методом динамического программирования Задача о подсчете количества наборов из k чисел, сумма которых меньше n Формулировка задачи: порядок слагаемых важен Задача о частичных суммах массива Динамика на подотрезках Задача о полиндроме. Вычисляемая функция. Рекуррентное соотношение Другие варианты решения задачи Дерево разбора Формы записи арифметических выражений Вычисление выражения, записанного в обратной польской записи Дерево разбора Задача об оптимальной растановке скобок в арифметическом выражении Программная реализация алгоритма решения Задача об условном добавлении скобок в арифметическое выражение	-
Тест 8 36 минут	12 заданий	-
Лекция 9	Динамика на деревьях В данной лекции на примерах решения задач подробно разбираются основные моменты работы с использованием динамики на деревьях. Дается определение понятия триангуляции. Решаются задачи на повторение пройденного материала Оглавление Введение Динамика на дереве Задача о нахождении максимального подмножества некоторого множества элементов Парасочетания на дереве Задача о нахождении максимального по числу ребер парасочетания в графе Оценка времени выполнения алгоритма решения Программная реализация алгоритма решения задачи о нахождении максимального парасочетания в графе Задача "Кузнечик" Задача о спуске игроков вниз по дереву Задача о нахождении суммы длин всех путей графа Задачи на повторение пройденного материала Задача о минимизации максимальной площади треугольника Задача о двух рюкзаках Задача о разбиении произвольного множества на подмножества Задача о подсчете числа связных графов для n вершин Треангуляция	-
Тест 9 36 минут	12 заданий	-
Лекция 10	Вычислительная геометрия Лекция посвящена вопросам программирования операций над геометрическими объектами. Даются определения основным геометрическим примитивам, приводятся возможные варианты их хранения в памяти ПК. Подробно рассматриваются векторы, операции над ними. Дается понятие полярной системы координат, обсуждаются ее достоинства и недостатки. Разбираются несколько задач на способы задания прямой. Обращается внимание на особенности сравнения вещественных чисел в ПК Оглавление Введение Геометрические примитивы Точка. Способы задания точки. Программная реализация Вектор. Способы задания вектора. Программная реализация Векторы. Операции над векторами Скалярное произведение векторов. Свойства Векторное произведение векторов. Свойства Псевдовекторное произведение векторов Выражение векторного произведения векторов через координаты Пример использования свойств скалярного произведения векторов Полярная система координат Полярная система координат Преобразование полярных координат точки в декартовы координаты Применение полярных координат на практике Поворот вектора на некоторый угол Прямая. Способы задания прямой Нормальный и направляющий векторы к прямой Построение прямой по двум точкам Нахождение расстояния от точки до прямой Метод Крамера решения систем линейных алгебраических уравнений Задача нахождения полярного угла Параметрическое задание прямой отрезка, луча Особенности сравнения вещественных чисел	-
Тест 10 36 минут	12 заданий	-
Лекция 11	Вычислительная геометрия Лекция посвящена работе с многоугольниками. Рассматриваются алгоритмы Джарвиса и Грэхема построения выпуклых оболочек. Вводится понятие двоичного дерева поиска. Оглавление Введение Многоугольники Определение многоугольника Программирование многоугольника Выпуклость многоугольников Сложные многоугольники Обход многоугольника Площадь многоугольника. Теорема о площади многоугольника Выпуклая оболочка Метод Джарвиса построения выпуклой оболочки Алгоритм построения Оценка времени выполнения алгоритма Метод Грэхема построения выпуклой оболочки Алгоритм построения Стек. Использование стека для построения выпуклой оболочки Проведение касательной от точки к окружности Двоичное дерево поиска Определение дерева. Свойства Программирование дерева поиска Программирование обхода всех вершин дерева AVL-деревья	-
Тест 11 36 минут	12 заданий	-
Лекция 12	Строки Лекция посвящена работе со строками. Рассматриваются алгоритмы Кнута-Морриса и Z-алгоритм поиска подстроки в строке. Вводится понятие Z-функции, приводится алгоритм ее вычисления Оглавление Введение Задача поиска подстроки в строке Формулровка задачи. Обозначения Программирование алгоритма решения. Оценка времени выполнения алгоритма Задача о нахождении длины наибольшего префикса строки, являющегося суффиксом Префикс строки Суффикс строки Постановка задачи. Алгоритм решения Программная реализация алгоритма решения Пример Оценка времени выполнения алгоритма Алгоритм Кнута-Морриса. Пример поиска подстроки в строке Алгоритм Кнута-Морриса поиска подстроки в строке Оценка времени выполнения алгоритма Пример использования префикс-функции в задаче о циклическом сдвиге строки Пример вычисления префикс-функции Задача поиска подстроки в строке с помощью Z-алгоритма Понятие Z-функции Пример нахождения Z-функции Алгоритм вычисления Z-функции Понятие Z-блока. Задание Z-блока Программирование алгоритма вычисления Z-функции Пример использования Z-функции	-
Тест 12 36 минут	12 заданий	-
5 часов	Экзамен	-

Авторизоваться

Базовые и "продвинутые" алгоритмы для школьников

План занятий