Тематический план
Учебно-тренировочные сборы
Учебно-тренировочные сборы, 25.11.2024 - 20.12.2024
ТЕОРИЯ ЧИСЕЛ
Теория чисел — раздел математики, занимающийся изучением чисел непосредственно как таковых, их свойств и поведения в различных ситуациях.
⇓ ТРЕНИРОВКА №1 (введение в теорию чисел).
Арифметика остатков. Деление с округлением вверх. gcd(a, b). lcm(a, b). Алгоритм Евклида . Основная теорема арифметики. Быстрое возведение в степень.Пишем функцию проверки числа на простоту с временной эффективностью O(sqrt(n)). Основная теорема арифметики
Рассматриваем алгоритм факторизации натуральных чисел с временной сложностью O(sqrt(n)). Пишем функцию канонического разложения на языках программирования Python и C++.
⇓ ТРЕНИРОВКА №2 (базовые алгоритмы теории чисел).
Простые числа. Функции делителей. Проверка числа на простоту. Решето Эратосфена. Факторизация числа
ЛИНЕЙНЫЕ АЛГОРИТМЫ
Линейные алгоритмы представляют собой класс алгоритмов, позволяющих решать задачи за линейную сложность , где — размерность задачи.
- Линейные алгоритмы (теоретический материал) Файл документ PDF, 815.2Кбайт
ГОАОУ «Центр поддержки одаренных детей «Стратегия» Липецкой области, к.т.н., доцент Шуйкова И.А. – директор, ООО «Яндекс. Технологии», Полднев А.В. – руководитель службы, МАОУ СамЛИТ г.о. Самара, Панькова М.Г. – учитель информатики, Первеев М.В. – студент Университета ИТМО
⇓ ТРЕНИРОВКА №3 (линейные алгоритмы).
БИНАРНЫЙ ПОИСК
Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины.
- Бинарный поиск (М.Густокашин) Файл документ PDF, 111.3Кбайт
- Бинарный поиск (М. Первеев, с++) Файл документ PDF, 353.3Кбайт
- Бинарный поиск (П. Калинин) Файл документ PDF, 119.4Кбайт
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Динамическое программирование — это когда у нас есть задача,
которую непонятно как решать, и мы разбиваем ее на меньшие задачи,
которые тоже непонятно как решать. (с) А. Кумок.Метод динамического программирования, который иногда называют методом динамической оптимизации - это подход к решению сложных задач путем разбиения их на более мелкие части и запоминания результатов решения этих частей.
Давайте разберем пример:
5 + 5 = ?
5 + 5 + 5 = ?
5 + 5 + 5 + 5 = ?
5 + 5 + 5 + 5 + 5 = ?Динамическое программирование позволяет нам избежать повторений, путем запоминания промежуточных результатов. То есть путем запоминания результатов проблем, которые мы уже решили.
Динамическое программирования является комбинацией двух подходов: алгоритма разделяй и властвуй (divide and conquer algorithm) и жадного алгоритма (greedy algorithm).
На алгоритм разделяй и властвуй похоже тем, что мы разбиваем задачу на более мелкие части. Хотя в динамическом программировании мелкие задачи пересекаются, дополняют друг друга.
На жадный алгоритм похоже тем, что мы также сразу ищем оптимальное решение. Правда не всей задачи целиком, а отдельных подзадач. Другими словами, мы не пересчитываем решения подзадач.
- Динамическое программирование с одним параметром Файл документ PDF, 252.3Кбайт
⇓ Тренировка №4 (задачи о кузнечике).
Одномерное динамическое программирование.
Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга.
⇓ Тренировка №5 (одномерное динамическое программирование).Always remember! “Those who can’t remember the past are condemned to repeat it”
⇓ Тренировка №6 (двумерное динамическое программирование).
⇓ Тренировка №7 (динамика с восстановлением ответа).
