Центр развития одарённости «Перспектива»
Тематический план
Введение в курс
Входное тестирования на определение знания основных алгоритмических конструкций (ветвления, циклы). Максимальная оценка 20 балловPascalABC.NET – это язык программирования Паскаль нового поколения, сочетающий простоту классического языка Паскаль, ряд современных расширений и огромные возможности платформы Microsoft .NET. PascalABC.NET разрабатывается под свободной лицензией LGPLv3 в первую очередь как язык программирования для сферы образования и научных исследований и вбирает в себя лучшее, что предлагают другие современные языки, такие как C#, Kotlin, Python, Haskell и другие.
Целочисленная арифметика
Теория чисел — раздел математики, занимающийся изучением чисел непосредственно как таковых, их свойств и поведения в различных ситуациях. Тема «Целочисленная арифметика» в большей степени уделяет внимание целым числам, их свойствам и алгоритмам работы с ними, которые используются при решении олимпиадных задач.\( \Downarrow \)Арифметические операции с целыми числами.
Пишем функцию проверки числа на простоту с временной эффективностью O(sqrt(n)). Основная теорема арифметики
- \( \Downarrow \)Проверка числа на простоту \({O( \sqrt{n})} \). Факторизация (разложение на простые множители) числа \( {O( \sqrt{n})} \). Каноническое разложение числа на простые множители: поиск всех делителей числа \( {O( \sqrt{n})} \); нахождение количества делителей числа \( {O( \sqrt{n})} \). Алгоритм Евклида \( {O(log(min(a, b)))} \). gcd(a, b). lcm(a, b).
\( \Downarrow \)Решето Эратосфена - это алгоритм, позволяющий найти все простые числа в отрезке \( [1; n] \) за \( O({n}log(log{n})) \) операций. Расширенный алгоритм Евклида
Лекции Константина Широкина (НИУ МИТЭ)
Динамическое программирование
- Динамическое программирование - это когда у нас есть одна большая задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А. Кумок
Динамическое программирование — метод решения задачи путём разбиения её на меньшие подзадачи, которые имеют такую же структуру.
Линейные структуры данных
Структуры данных - это способы хранить и организовывать данные, чтобы эффективней решать различные задачи. Данные можно представить по-разному. В зависимости от того, что это за данные и что вы собираетесь с ними делать, одно представление подойдёт лучше других.Никлаус Вирт, швейцарский ученый-информатик, в 1976 году написал книгу под названием «Алгоритмы + Структуры данных = Программы». Через 40 с лишним лет это тождество остается в силе.
Структура данных классифицируется как линейная структура данных, если её элементы образуют линейную последовательность, то есть её элементы упорядоченно располагаются слева направо (или сверху вниз). Наиболее часто применяемые линейные структуры данных в олимпиадном программировании - это статические и динамические массивы. Динамический массив во многом похож на статический, за исключением того, что динамический массив предназначен и адаптирован для изменения размеров массива во время выполнения программы. К наиболее широко используемым операциям над массивами относятся поиск и сортировка.
Поиск и сортировка
Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании
- Бинарный поиск (М.Густокашин) Файл документ PDF, 111.3Кбайт
- Бинарный поиск (М. Первеев, с++) Файл документ PDF, 353.3Кбайт
- Бинарный поиск (П. Калинин) Файл документ PDF, 119.4Кбайт
Нелинейные структуры данных
Для некоторых задач линейное хранилище - не лучший способ организации данных. С помощью эффективных реализаций нелинейных структур данных, вы можете работать с данными быстрее, тем самым ускоряя алгоритмы, которые основываются на них.
В основе map и set лежит такая нелинейная структура данных, как сбалансированное двоичное дерево поиска. Используя данные структуры данных можно получить производительность ,эквивалентную \( O(logn) \) для операций вставка/поиска/удаления.
Set. Dictionaries
Stack. Queue. Priority queue
Графы
- Поиск в ширину (обход в ширину, breadth-first search) — это один из основных алгоритмов на графах.
В результате поиска в ширину находится путь кратчайшей длины в невзвешенном графе, т.е. путь, содержащий наименьшее число рёбер.
Алгоритм работает за
, где 
— число вершин, 
— число рёбер.
Структуры данных
Система непересекающихся множеств
Система непересекающихся множеств (на английском disjoint-set-union, или просто DSU).
Сканирующая прямая
Метод сканирующей прямой (англ. scanline) заключается в сортировке точек на координатной прямой либо каких-то абстрактных «событий» по какому-то признаку и последующему проходу по ним.
Он часто используется для решения задач на структуры данных, когда все запросы известны заранее, а также в геометрии для нахождения объединений фигур.