Авторы: Константин Абакумов, Марина Мухачева, Андрей Станкевич | Санкт-Петербургский государственный университет
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Стоимость обучения с персональным тьютором:
500 руб. [?]
Доступ:
свободный
Документ об окончании:
 
Уровень:
Для всех
Длительность:
22:14:00
Студентов:
4344
Выпускников:
251
Качество курса:
4.63 | 3.84
В курсе излагаются базовые алгоритмы для школьников. Этот курс читался на летней компьютерной школе для участников олимпиад по информатике.
Рассматривается понятие сложности алгоритма, изучаются алгоритмы сортировки и поиска. Даются базовые представления о динамическом программировании, теории графов и деревьев. Дается основы работы с длинными числами и комбинаторные алгоритмы.
Специальности: Программист
 

План занятий

Занятие
Заголовок <<
Дата изучения
Лекция 1
1 час 56 минут
Сложность алгоритмов
Оценка сложности алгоритмов. Необходимость оценки сложности программ. Полиномиальные и экспоненциальные оценки. Структуры данных: стек, очередь. Списки и операции со списками.
Оглавление
-
Лекция 2
2 часа 5 минут
Сортировка и поиск
Поиск в упорядоченном и неупорядоченном массиве. Целочисленный двоичный поиск. Вещественный двоичный поиск. Приоритетная очередь. Куча. Деревья. Двоичные деревья.
-
Лекция 3
2 часа
Динамическое программирование
Числа Фибоначчи. Задача о кузнечике, прыгающем по столбикам. Задача о кузнечике и лягушках. Задача о кузнечике и монетах. Задача о черепашке. Задача о черепашке и монетках. Задача о клетках с животными. Задача о рюкзаке. Оптимальность использования динамического программирования.
-
Лекция 4
2 часа 3 минуты
Теория графов
Графы. Вершины и ребра графа. Путь в графе. Длина пути. Простой путь. Циклический путь. Неориентированный граф. Ориентированный граф. Лемма о рукопожатиях. Связность в неориентированном графе. Компоненты связности в неориентированном графе. Полный граф. Ациклические графы. Представление графов в программе.
Оглавление
-
Лекция 5
1 час 49 минут
Поиск в графах и обход. Алгоритм Дейкстры
Поиск в глубину. Топологическая сортировка. Алгоритм поиска циклов в графе. Кратчайшие пути в графах. Обход графа в ширину. Обход графа в глубину. Пути во взвешенных графах. Алгоритм Дейкстры.
Оглавление
-
Лекция 6
1 час 48 минут
Остовные деревья
Остовные деревья. Алгоритм Краскала. Алгоритм Прима. Остовный лес.
-
Лекция 7
1 час 57 минут
Геометрия
Базовые геометрические примитивы и работа с ними. Тригонометрические функции. Обратные тригонометрические функции. Операции над векторами. Скалярное произведение векторов. Векторное произведение векторов.
Оглавление
-
Лекция 8
1 час 56 минут
Точность вычислений
Точность вычислений. Геометрические объекты. Окружность. Многоугольники. Выпуклые и невыпуклые многоугольники. Площадь многоугольника. Определение выпуклости многоугольника. Самопересекающиеся многоугольники.
Оглавление
-
Лекция 9
1 час 49 минут
Длинная арифметика
-
Лекция 10
1 час 51 минута
Комбинаторика
Лексикографический порядок. Сложение двоичных чисел. Перевод чисел из десятичной системы счисления в двоичную. Перевод чисел из двоичной системы счисления в десятичную. Перестановки. Сочетания.
-
1 час 40 минут
-
Андрей Мистецкий
Андрей Мистецкий
Посоветуйте плз литературу по данному курсу
Евгений Ледяев
Евгений Ледяев
Россия, Барнаул
Елена Сергеева
Елена Сергеева
Россия, Таганрог, ТРТУ, 2003