|
В конце каждого занятия, очевидно, есть практическая часть, которая не попадает в видео. Можно где-то посмотреть эти задачи? |
Базовые алгоритмы для школьников: Информация
Авторы: Константин Абакумов, Марина Мухачева, Андрей Станкевич | Санкт-Петербургский государственный университет
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 85 студентам
Уровень:
Для всех
Длительность:
3:00:00
Студентов:
5694
Выпускников:
344
Качество курса:
4.63 | 3.84
В курсе излагаются базовые алгоритмы для школьников.
Этот курс читался на летней компьютерной школе для участников олимпиад по информатике.
Рассматривается понятие сложности алгоритма, изучаются алгоритмы сортировки и поиска. Даются базовые представления о динамическом программировании, теории графов и деревьев. Дается основы работы с длинными числами и комбинаторные алгоритмы.
Специальности: Программист
Дополнительные курсы
- Элементы линейной алгебры для школьников
- Введение в проективную геометрию для школьников
- Введение в базы данных для школьников
- "Продвинутые" алгоритмы для школьников
- Базовые и "продвинутые" алгоритмы для школьников
- C# для школьников
- Комбинаторные алгоритмы для программистов
- Графы и алгоритмы
- Введение в схемы, автоматы и алгоритмы
- Вычислительная математика и структура алгоритмов
- Программирование и знакомство с алгоритмами
- Введение в алгоритмы
- Алгоритмы и модели вычислений
- Алгоритмы и теория вычислений
План занятий
Занятие
Заголовок <<
Дата изучения
Сложность алгоритмов
Оценка сложности алгоритмов. Необходимость оценки сложности программ. Полиномиальные и экспоненциальные оценки. Структуры данных: стек, очередь. Списки и операции со списками.
Оглавление
-
Сортировка и поиск
Поиск в упорядоченном и неупорядоченном массиве. Целочисленный двоичный поиск. Вещественный двоичный поиск. Приоритетная очередь. Куча. Деревья. Двоичные деревья.
Оглавление
-
Динамическое программирование
Числа Фибоначчи. Задача о кузнечике, прыгающем по столбикам. Задача о кузнечике и лягушках. Задача о кузнечике и монетах. Задача о черепашке. Задача о черепашке и монетках. Задача о клетках с животными. Задача о рюкзаке. Оптимальность использования динамического программирования.
Оглавление
- Введение
- Числа Фибоначчи
- Задача о кузнечике, прыгающем по столбикам
- Этапы решения задачи с помощью динамического программирования
- Задача о кузнечике и лягушках
- Задача о кузнечике и монетах
- Задача о черепашке
- Задача о черепашке и монетках
- Оптимальность использования динамического программирования
- Задача о клетках с животными
- Задача о рюкзаке
-
Теория графов
Графы. Вершины и ребра графа. Путь в графе. Длина пути. Простой путь. Циклический путь. Неориентированный граф. Ориентированный граф. Лемма о рукопожатиях. Связность в неориентированном графе. Компоненты связности в неориентированном графе. Полный граф. Ациклические графы. Представление графов в программе.
-
Поиск в графах и обход. Алгоритм Дейкстры
Поиск в глубину. Топологическая сортировка. Алгоритм поиска циклов в графе. Кратчайшие пути в графах. Обход графа в ширину. Обход графа в глубину. Пути во взвешенных графах. Алгоритм Дейкстры.
-
Остовные деревья
Остовные деревья. Алгоритм Краскала. Алгоритм Прима. Остовный лес.
-
Геометрия
Базовые геометрические примитивы и работа с ними. Тригонометрические функции. Обратные тригонометрические функции. Операции над векторами. Скалярное произведение векторов. Векторное произведение векторов.
-
Точность вычислений
Точность вычислений. Геометрические объекты. Окружность. Многоугольники. Выпуклые и невыпуклые многоугольники. Площадь многоугольника. Определение выпуклости многоугольника. Самопересекающиеся многоугольники.
-
Длинная арифметика
Представление чисел. Реализация процедуры считывания длинного числа. Реализация процедуры вывода длинного числа. Сложение длинных чисел. Умножение длинного числа на короткое. Вычитание длинных чисел. Деление длинного числа на короткое. Сравнение длинных чисел.
-
Комбинаторика
Лексикографический порядок. Сложение двоичных чисел. Перевод чисел из десятичной системы счисления в двоичную. Перевод чисел из двоичной системы счисления в десятичную. Перестановки. Сочетания.
Оглавление
- Введение
- Поиск количества последовательностей из 0 и 1 длины n
- Лексикографический порядок
- Перевод чисел из десятичной системы счисления в двоичную
- Сложение двоичных чисел. Реализация алгоритма сложения.
- Определение номера по слову
- Перевод чисел из двоичной системы счисления в десятичную
- Определение слова по номеру
- Перестановки
- Определение номера по перестановке
- Сочетания
-
