|
Как включить звук на второй половине лекций |
Опубликован: 02.02.2009 | Уровень: для всех | Доступ: свободно
В курсе рассказывается о "продвинутых" алгоритмах для школьников. Этот курс читался на летней компьютерной школе для участников олимпиад по информатике.
Рассматриваются вопросы сортировки, поиски в ширину и глубину, алгоритмы на графах, динамическое программирование. Демонстрируются алгоритмы работы с графическими объектами, отрезками, строками и другими объектами.
План занятий
| Занятие | Заголовок << | Дата изучения |
|---|---|---|
| - | ||
Лекция 1 | Сортировки
Рассматриваются вопросы сортировки: быстрая, сортировка слиянием, устойчивость сортировки, цифровая сортировка. Списки, операции с элементами массива
| - |
Тест 136 минут | - | |
Лекция 2 | Поиск в ширину
В лекции даются алгоритмы поиска в ширину. Рассматриваются подвешенные и двоичные деревья. Дается пример решения задачи нахождения самого длинного пути
| - |
Тест 236 минут | - | |
Лекция 3 | Графы. Задача максимальных или минимальных остовных деревьев
Дается алгоритм поиска минимального остовного дерева. Алгоритм Прима. Рассматриваются другие алгоритмы нахождения минимального остовного дерева
| - |
Тест 336 минут | - | |
Лекция 4 | Матрицы. Поиск кратчайших путей в графах
Матрицы и операции с ними. Числа Фибоначчи. Дается алгоритм поиска кратчайших путей в графах. Алгоритм Форда-Беллмана. Алгоритм Флойда.
| - |
Тест 436 минут | - | |
Лекция 5 | Поиск в глубину и его применение
В лекции рассматриваются Эйлеровы циклы и Эйлеровы пути. Поиск в глубину. Неориентированные графы.
| - |
Тест 536 минут | - | |
Лекция 6 | Паросочетания в двудольном графе
В данной лекции рассматриваются независимые множества, паросочетания, вершинные покрытия. Даются определения, приводятся способы решения различных задач, рассматривается алгоритм Куна
| - |
Тест 636 минут | - | |
Лекция 7 | Динамическое программирование
В данной лекции дается сравнение динамического программирования с перебором. Даются примеры решения различных задач с применением динамического программирования
| - |
Тест 736 минут | - | |
Лекция 8 | Простейшие геометрические объекты
В лекции даются определения простейших геометрических объектов, операции с ними. Рассматриваются примеры пересечения прямых. Окружности.
| - |
Тест 836 минут | - | |
Лекция 9 | Строки
Даются определения, рассматривается алгоритм Кнута-Морриса-Пратта. Бор: Базовые операции. Хэш
| - |
Тест 936 минут | - | |
Лекция 10 | Отрезки
Рассматриваются задачи на отрезках, операции при наличии обновлений на отрезке, построение дерева отрезков, подсчет суммы чисел на отрезке
| - |
Тест 1036 минут | - | |
Лекция 11 | Задачи на отрезках
Рассматриваются задачи на отрезках, построение дерева отрезков, подсчет сумм чисел на отрезке. Решение задач.
| - |
Тест 1136 минут | - | |
5 часов | - |