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