Мы используем файлы cookies. Посещая страницы сайта, вы соглашаетесь с условиями использования файлов cookie.
Стоимость программы
по средам
с 18:00 до 19:30
с 18:00 до 19:30
по четвергам
с 18:00 до 19:30
с 18:00 до 19:30
Студенты, школьники, выпускники
Бесплатно
Аудитория
4 корпус ННГУ им. Лобачевского
1 корпус НГТУ им. Р.Е. Алексеева
Площадки и расписание
Программа рассчитана на людей, стремящихся участвовать в соревнованиях по программированию (прежде всего — студенческий чемпионат мира ICPC), но не имеющих опыта решения олимпиадных задач.
Глубоких знаний языков программирования и опыта участия в олимпиадах не требуется (но, конечно, приветствуется!) — достаточно желания учиться и любить соревноваться!
Программа не ориентирована на промышленную разработку, но многие приемы и практики из олимпиад будут выделены, как подходящие и для реальных проектов.
Кому будет интересно
Занятия ориентированы на студентов младших курсов, кто еще может участвовать в ICPC и сможет показать высокие результаты через 1−2 года. Однако, на занятия приглашаются все желающие — студенты, школьники и даже выпускники!
Программа обучения
- Лекция 0 - Как сдавать задачи, платформа CodeForces
- Лекция 1 – Вычислительная сложность и линейные алгоритмы
- Лекция 2 – Сортировки
- Лекция 3 – Жадные алгоритмы
- Лекция 4 – Бинарный поиск
- Лекция 5 – Префикс-суммы
- Лекция 6 – Алгоритмы STL
- Лекция 7 – Контейнеры set и map
- Закрепляющий контест – основы
- Лекция 8 – Простые числа
- Лекция 9 – Делители
- Лекция 10 – Арифметика остатков
- Лекция 11 – Комбинаторика
- Лекция 12 – Динамическое программирование - 1
- Закрепляющий контест – теория чисел
- Лекция 13 – Основы теории графов
- Лекция 14 – Алгоритм Флойда и BFS
- Лекция 15 – Алгоритм Дейкстры
- Лекция 16 – DFS
- Лекция 17 – Деревья
- Лекция 18 – Решение задач на графы
- Закрепляющий контест – графы
- Лекция 19 – Рекурсивный перебор
- Лекция 20 – Нерекурсивный перебор
- Лекция 21 – Динамическое программирование - 2
- Лекция 22 – Решение задач ДП
- Лекция 23 – Решение задач на разложение в сумму
- Лекция 24 – Игры
- Закрепляющий контест – ДП и перебор
- Лекция 25 – Геометрия
- Лекция 26 – Алгоритмы на строках
- Лекция 27 – Дерево отрезков
- Закрепляющий контест – первый год
Блок 1 – Основы
Лекция 1 – Вычислительная сложность и линейные алгоритмы
Важность времени работы алгоритма. Пример решения задачи разными способами. Вычисление времени работы алгоритма. Понятие асимптотической сложности, O-нотация. Простейшие линейные алгоритмы. Разбиение на группы за O(n). Сортировка подсчетом. Решение задачи «Количество различных» через сортировку подсчетом.
Лекция 2 – Сортировки
Понятие порядка возрастания/убывания. Пример простейшей сортировки. Примеры эффективных сортировок. Сортировки, основанные на сравнении, доказательство оптимальности. Стандартный алгоритм sort. Решение задачи «Количество различных» с использованием sort. Сортировка с функцией сравнения. Задача «Урок физкультуры». Создание структур. Стандартная структура pair.
Лекция 3 – Жадные алгоритмы
Примеры «жадных» алгоритмов в реальной жизни. Понятие жадного алгоритма. Глобальный и локальный критерии в задаче. Примеры правильных и неправильных жадных алгоритмов – задача о рюкзаке, задача о назначениях, алгоритм Краскала, алгоритм Прима. Сложность при решении задач. Использование сортировки для эффективной реализации. Задача «Отрезки». Контейнер vector.
Лекция 4 – Бинарный поиск
Поиск числа в массиве. Задачи с несколькими запросами. Понятие бинарного поиска, доказательство асимптотики. Реализация с функцией проверки. Обобщение на поиск в интервале, бинарный поиск по ответу. Необходимость монотонности функции, примеры неправильных решений. Задача «Уравнение». Вещественный бинарный поиск. Проблемы точности и эффективная реализация. Обобщение через понятие двойственной задачи. Задача «Лифт».
Лекция 5 – Префикс-суммы
Понятие префикс-сумм и эффективная реализация. Нахождение суммы на отрезке. Нахождение отрезка с максимальной суммой, разные реализации. Двумерные префикс-суммы. Нахождение суммы на прямоугольнике. Обобщение на d-мерный случай, количество слагаемых в сумме.
Лекция 6 – Алгоритмы STL
Память компьютера. Указатель, массив, адресная арифметика. Понятие итератора, итераторы произвольного доступа. Знакомство с STL, библиотека <algorithm>. Алгоритмы линейного поиска. Алгоритмы бинарного поиска. Сортировки. Другие алгоритмы, модифицирующие диапазон. Библиотека <numeric>. Алгоритмы с перестановками.
Лекция 7 – Контейнеры set и map
Бинарные деревья. Сильная и слабая балансировка. Оценка минимальной и максимальной высоты дерева. Деревья поиска. Контейнер set, итератор контейнера. Простейшие операции, асимптотическая сложность. Решение задачи «Количество различных» с использованием set. Поиск ближайшего элемента. Контейнер multiset. Использование функции сравнения, отношение порядка. Контейнер map, решение задачи «Урок физкультуры» с использованием map.
Закрепляющий контест – основы
Важность времени работы алгоритма. Пример решения задачи разными способами. Вычисление времени работы алгоритма. Понятие асимптотической сложности, O-нотация. Простейшие линейные алгоритмы. Разбиение на группы за O(n). Сортировка подсчетом. Решение задачи «Количество различных» через сортировку подсчетом.
Лекция 2 – Сортировки
Понятие порядка возрастания/убывания. Пример простейшей сортировки. Примеры эффективных сортировок. Сортировки, основанные на сравнении, доказательство оптимальности. Стандартный алгоритм sort. Решение задачи «Количество различных» с использованием sort. Сортировка с функцией сравнения. Задача «Урок физкультуры». Создание структур. Стандартная структура pair.
Лекция 3 – Жадные алгоритмы
Примеры «жадных» алгоритмов в реальной жизни. Понятие жадного алгоритма. Глобальный и локальный критерии в задаче. Примеры правильных и неправильных жадных алгоритмов – задача о рюкзаке, задача о назначениях, алгоритм Краскала, алгоритм Прима. Сложность при решении задач. Использование сортировки для эффективной реализации. Задача «Отрезки». Контейнер vector.
Лекция 4 – Бинарный поиск
Поиск числа в массиве. Задачи с несколькими запросами. Понятие бинарного поиска, доказательство асимптотики. Реализация с функцией проверки. Обобщение на поиск в интервале, бинарный поиск по ответу. Необходимость монотонности функции, примеры неправильных решений. Задача «Уравнение». Вещественный бинарный поиск. Проблемы точности и эффективная реализация. Обобщение через понятие двойственной задачи. Задача «Лифт».
Лекция 5 – Префикс-суммы
Понятие префикс-сумм и эффективная реализация. Нахождение суммы на отрезке. Нахождение отрезка с максимальной суммой, разные реализации. Двумерные префикс-суммы. Нахождение суммы на прямоугольнике. Обобщение на d-мерный случай, количество слагаемых в сумме.
Лекция 6 – Алгоритмы STL
Память компьютера. Указатель, массив, адресная арифметика. Понятие итератора, итераторы произвольного доступа. Знакомство с STL, библиотека <algorithm>. Алгоритмы линейного поиска. Алгоритмы бинарного поиска. Сортировки. Другие алгоритмы, модифицирующие диапазон. Библиотека <numeric>. Алгоритмы с перестановками.
Лекция 7 – Контейнеры set и map
Бинарные деревья. Сильная и слабая балансировка. Оценка минимальной и максимальной высоты дерева. Деревья поиска. Контейнер set, итератор контейнера. Простейшие операции, асимптотическая сложность. Решение задачи «Количество различных» с использованием set. Поиск ближайшего элемента. Контейнер multiset. Использование функции сравнения, отношение порядка. Контейнер map, решение задачи «Урок физкультуры» с использованием map.
Закрепляющий контест – основы
Блок 2 – Теория чисел
Лекция 8 – Простые числа
Определение простого числа. Алгоритмы проверки на простоту. Погрешность функции sqrt. Оценка количества простых чисел. Поиск следующего простого. Ускорение проверки на простоту. Решето Эратосфена, реализация. Неасимптотические оптимизации. Упрощенная реализация, оценка времени работы. Сумма гармонического ряда. Более сильная оценка времени работы.
Лекция 9 – Делители
Алгоритмы поиска делителей числа. Чётность количества делителей. Оценка количества делителей, поиск минимального циклического сдвига строки. Факторизация, простейшая реализация. Оценка количества простых делителей. КПД алгоритма факторизации. Расширение алгоритма решета Эратосфена. Эффективная факторизация маленький чисел. Оценка среднего количества делителей. Формула количества делителей по заданной факторизации. Задача «Количество делителей произведения». Наибольший общий делитель, алгоритм Евклида, рекурсия.
Лекция 10 – Арифметика остатков
Взаимно-простые числа. Сравнение по модулю, операции. Группа остатков по простому модулю. Деление по модулю, обратный элемент, примеры. Малая теорема Ферма. Бинарное возведение в степень – рекурсивная и нерекурсивная реализация. Обобщение на составной модуль. Функция Эйлера и её свойства. Алгоритм нахождения функции Эйлера. Полный алгоритм деления по модулю. Расширенный алгоритм Евклида. Нахождение обратного элемента через алгоритм Евклида. Что нужно проверять каждое утро?
Лекция 11 – Комбинаторика
Количество путей в гору. Сложение и умножение при подсчете способов. Способы корректировки при учёте лишних случаев. Деление, число сочетаний. Свойства числа сочетаний, треугольник Паскаля. Доказательство свойств через формулы и через логику. Число путей на прямоугольной доске. Обобщение на случай вырезанных клеток. Подход «шары и перегородки». Вычитание лишних случаев. Формула включений/исключений. Использование на примере алгоритма префикс-сумм. Пример с перебором делителей.
Лекция 12 – Динамическое программирование – 1
Числа Фибоначчи, рекурсивная реализация, оценка времени работы. Эффективная реализация. Понятие динамического программирования. Использование ДП на примере уже пройденных алгоритмов. Задача «Лесенка». Задача «Зайчик». Понятие состояния в ДП. Двумерное ДП, примеры задач.
Закрепляющий контест – теория чисел
Определение простого числа. Алгоритмы проверки на простоту. Погрешность функции sqrt. Оценка количества простых чисел. Поиск следующего простого. Ускорение проверки на простоту. Решето Эратосфена, реализация. Неасимптотические оптимизации. Упрощенная реализация, оценка времени работы. Сумма гармонического ряда. Более сильная оценка времени работы.
Лекция 9 – Делители
Алгоритмы поиска делителей числа. Чётность количества делителей. Оценка количества делителей, поиск минимального циклического сдвига строки. Факторизация, простейшая реализация. Оценка количества простых делителей. КПД алгоритма факторизации. Расширение алгоритма решета Эратосфена. Эффективная факторизация маленький чисел. Оценка среднего количества делителей. Формула количества делителей по заданной факторизации. Задача «Количество делителей произведения». Наибольший общий делитель, алгоритм Евклида, рекурсия.
Лекция 10 – Арифметика остатков
Взаимно-простые числа. Сравнение по модулю, операции. Группа остатков по простому модулю. Деление по модулю, обратный элемент, примеры. Малая теорема Ферма. Бинарное возведение в степень – рекурсивная и нерекурсивная реализация. Обобщение на составной модуль. Функция Эйлера и её свойства. Алгоритм нахождения функции Эйлера. Полный алгоритм деления по модулю. Расширенный алгоритм Евклида. Нахождение обратного элемента через алгоритм Евклида. Что нужно проверять каждое утро?
Лекция 11 – Комбинаторика
Количество путей в гору. Сложение и умножение при подсчете способов. Способы корректировки при учёте лишних случаев. Деление, число сочетаний. Свойства числа сочетаний, треугольник Паскаля. Доказательство свойств через формулы и через логику. Число путей на прямоугольной доске. Обобщение на случай вырезанных клеток. Подход «шары и перегородки». Вычитание лишних случаев. Формула включений/исключений. Использование на примере алгоритма префикс-сумм. Пример с перебором делителей.
Лекция 12 – Динамическое программирование – 1
Числа Фибоначчи, рекурсивная реализация, оценка времени работы. Эффективная реализация. Понятие динамического программирования. Использование ДП на примере уже пройденных алгоритмов. Задача «Лесенка». Задача «Зайчик». Понятие состояния в ДП. Двумерное ДП, примеры задач.
Закрепляющий контест – теория чисел
Блок 3 – Теория графов
Лекция 13 – Основы теории графов
Основные определения – вершина, ребро, граф. Примеры представления через графы – дороги, отношения дружбы. Пути, циклы, компоненты связности, деревья. Ориентированные графы, взвешенные графы. Примеры описания соц.сетей через графы. Представление графов – список ребер, матрица смежности, списки смежности. Задача «Друзья друзей».
Лекция 14 – Алгоритм Флойда и BFS
Задача о нахождении кратчайшего пути. Алгоритм Флойда-Уоршелла, доказательство, оценка сложности и особенности реализации. Рёбра отрицательного веса. Поиск пути на невзвешенном графе, алгоритм поиска в ширину (BFS). Контейнер queue, применение в реализации BFS. Поиск пути в лабиринте. «Теория» 6 рукопожатий, число Эрдеша.
Лекция 15 – Алгоритм Дейкстры
Проблемы обобщения алгоритма BFS на взвешенные графы. Алгоритм Дейкстры, реализация за O(n^2). Сведение алгоритма к поиску минимального элемента. Эффективная реализация с контейнером set. Примеры плотных и разреженных графов. Сравнение алгоритмов поиска путей по параметрам: эффективность, простота реализации, универсальность.
Лекция 16 – DFS
Примеры алгоритмов поиска в «обычной» жизни – поиск файла, поиск аудитории, обход локации в игре. Формулировка алгоритмов в терминах графов, поиск в глубину (DFS). Понятие рекурсии. Реализация DFS при помощи рекурсии, неявный переход при завершении функции. Принципиальное отличие BFS от DFS в построении пути. Особенности дерева обхода DFS. Задача разбиения графа на компоненты связности.
Лекция 17 – Деревья
Основные свойства деревьев. Диаметр дерева, простой алгоритм нахождения диаметра. Понятие подвешенного дерева, корня, поддерева. Примеры иерархических структур. Обход подвешенного дерева при помощи DFS. Вычисление характеристик поддеревьев за O(n), простейшее ДП по поддеревьям. Сведение задачи к подвешенному дереву. Нахождение диаметра дерева через поддеревья.
Лекция 18 – Решение задач на графы
Задача «Красим дерево», задача «Строим дорогу», задача «Вклад», задача «Пути и деревья», задача «Кефа и парк», задача «Праздник»
Закрепляющий контест – графы
Основные определения – вершина, ребро, граф. Примеры представления через графы – дороги, отношения дружбы. Пути, циклы, компоненты связности, деревья. Ориентированные графы, взвешенные графы. Примеры описания соц.сетей через графы. Представление графов – список ребер, матрица смежности, списки смежности. Задача «Друзья друзей».
Лекция 14 – Алгоритм Флойда и BFS
Задача о нахождении кратчайшего пути. Алгоритм Флойда-Уоршелла, доказательство, оценка сложности и особенности реализации. Рёбра отрицательного веса. Поиск пути на невзвешенном графе, алгоритм поиска в ширину (BFS). Контейнер queue, применение в реализации BFS. Поиск пути в лабиринте. «Теория» 6 рукопожатий, число Эрдеша.
Лекция 15 – Алгоритм Дейкстры
Проблемы обобщения алгоритма BFS на взвешенные графы. Алгоритм Дейкстры, реализация за O(n^2). Сведение алгоритма к поиску минимального элемента. Эффективная реализация с контейнером set. Примеры плотных и разреженных графов. Сравнение алгоритмов поиска путей по параметрам: эффективность, простота реализации, универсальность.
Лекция 16 – DFS
Примеры алгоритмов поиска в «обычной» жизни – поиск файла, поиск аудитории, обход локации в игре. Формулировка алгоритмов в терминах графов, поиск в глубину (DFS). Понятие рекурсии. Реализация DFS при помощи рекурсии, неявный переход при завершении функции. Принципиальное отличие BFS от DFS в построении пути. Особенности дерева обхода DFS. Задача разбиения графа на компоненты связности.
Лекция 17 – Деревья
Основные свойства деревьев. Диаметр дерева, простой алгоритм нахождения диаметра. Понятие подвешенного дерева, корня, поддерева. Примеры иерархических структур. Обход подвешенного дерева при помощи DFS. Вычисление характеристик поддеревьев за O(n), простейшее ДП по поддеревьям. Сведение задачи к подвешенному дереву. Нахождение диаметра дерева через поддеревья.
Лекция 18 – Решение задач на графы
Задача «Красим дерево», задача «Строим дорогу», задача «Вклад», задача «Пути и деревья», задача «Кефа и парк», задача «Праздник»
Закрепляющий контест – графы
Блок 4 – Динамическое программирование и перебор
Лекция 19 – Рекурсивный перебор
Основная идея полного перебора решений. Сложности перебора при помощи циклов, рекурсивный подход. Решение задачи о рюкзаке при помощи рекурсивного перебора, оценка сложности. Поэлементное построение решения. Оптимизация через подсчет промежуточных значений, разделение на глобальные переменные и аргументы функции. Вывод ответа, функция exit. Разные варианты решения задачи коммивояжера. Отсечения в рекурсивном переборе, решение задачи «Самое сложное число». Особенность вычислительной сложности решений полным перебором.
Лекция 20 – Нерекурсивный перебор
Двоичная система счисления, битовые операции. Представление подмножества через биты числа, проверка наличия элемента в подмножестве. Перебор всех подмножеств, решение задачи о рюкзаке, решение задачи «Куча камней». k-ичная система счисления, кодирование массива. Перебор всех вариантов разбиения на группы. Перебор всех перестановок, сложность алгоритма next_permutation. Решение задачи коммивояжера. Перебор перестановок с одинаковыми элементами. Отличия нерекурсивного перебора от рекурсивного.
Лекция 21 – Динамическое программирование – 2
Нахождение чисел Фибоначчи при помощи рекурсивной реализации. Оптимизация через сохранение подсчитанных состояний, понятие «ленивой» динамики. Определение минимального необходимого набора параметров состояния. Свойства графа переходов между состояниями, начальные состояния. Общий подход к решению задач при помощи ДП. Преимущества и недостатки «ленивой» реализации. Задача «Амёбы», задача «Самый длинный путь».
Лекция 22 – Решение задач ДП
Улучшенная реализация «ленивой» динамики. Восстановление оптимального ответа. Задача «k-ичные числа», задача «Крышки», задача «Folding», задача «Чернобыльский орёл на крыше».
Лекция 23 – Решение задач на разложение в сумму
Количество способов разложения числа в сумму. Ограничение на количество слагаемых. Ограничение на значение слагаемых, подсчет количества счастливых билетов. Задача «Лестницы»
Лекция 24 – Игры
Понятие игры, хода, выигрышной стратегии. Игры-шутки, задача «Шоколадка». Игры с симметричной стратегией, задача «Два ферзя». Игры с ответными ходами, задача «Один ферзь». Произвольные стратегии, задача «Палочки». Обобщение – выигрышные/проигрышные позиции, задача «Время забирать камни». Расстановка позиций при помощи ДП. Сведение произвольной конечной игры к игре на графе. Обобщение на несимметричные игры. Обобщение на случай ничейного исхода. Игры на графах с циклами.
Закрепляющий контест – ДП и перебор
Основная идея полного перебора решений. Сложности перебора при помощи циклов, рекурсивный подход. Решение задачи о рюкзаке при помощи рекурсивного перебора, оценка сложности. Поэлементное построение решения. Оптимизация через подсчет промежуточных значений, разделение на глобальные переменные и аргументы функции. Вывод ответа, функция exit. Разные варианты решения задачи коммивояжера. Отсечения в рекурсивном переборе, решение задачи «Самое сложное число». Особенность вычислительной сложности решений полным перебором.
Лекция 20 – Нерекурсивный перебор
Двоичная система счисления, битовые операции. Представление подмножества через биты числа, проверка наличия элемента в подмножестве. Перебор всех подмножеств, решение задачи о рюкзаке, решение задачи «Куча камней». k-ичная система счисления, кодирование массива. Перебор всех вариантов разбиения на группы. Перебор всех перестановок, сложность алгоритма next_permutation. Решение задачи коммивояжера. Перебор перестановок с одинаковыми элементами. Отличия нерекурсивного перебора от рекурсивного.
Лекция 21 – Динамическое программирование – 2
Нахождение чисел Фибоначчи при помощи рекурсивной реализации. Оптимизация через сохранение подсчитанных состояний, понятие «ленивой» динамики. Определение минимального необходимого набора параметров состояния. Свойства графа переходов между состояниями, начальные состояния. Общий подход к решению задач при помощи ДП. Преимущества и недостатки «ленивой» реализации. Задача «Амёбы», задача «Самый длинный путь».
Лекция 22 – Решение задач ДП
Улучшенная реализация «ленивой» динамики. Восстановление оптимального ответа. Задача «k-ичные числа», задача «Крышки», задача «Folding», задача «Чернобыльский орёл на крыше».
Лекция 23 – Решение задач на разложение в сумму
Количество способов разложения числа в сумму. Ограничение на количество слагаемых. Ограничение на значение слагаемых, подсчет количества счастливых билетов. Задача «Лестницы»
Лекция 24 – Игры
Понятие игры, хода, выигрышной стратегии. Игры-шутки, задача «Шоколадка». Игры с симметричной стратегией, задача «Два ферзя». Игры с ответными ходами, задача «Один ферзь». Произвольные стратегии, задача «Палочки». Обобщение – выигрышные/проигрышные позиции, задача «Время забирать камни». Расстановка позиций при помощи ДП. Сведение произвольной конечной игры к игре на графе. Обобщение на несимметричные игры. Обобщение на случай ничейного исхода. Игры на графах с циклами.
Закрепляющий контест – ДП и перебор
Блок 5 – Дополнительные темы
Лекция 25 – Геометрия
Способы нахождения площади – формула Герона, метод трапеций, формула Пика. Ориентированная площадь, векторное произведение, определитель матрицы. Нахождение площади многоугольника через триангуляцию. Проверка нахождения точки внутри многоугольника. Проверка пересечения отрезков через ориентированную площадь. Нахождение точки пересечения через систему уравнений. Формулы Крамера. Обобщение проверки пересечения на случай луча и прямой, общее решение в целых числах. Окружность, угол. Связь длины дуги, длины хорды, величины угла. Пересечение окружностей.
Лекция 26 – Алгоритмы на строках
Наивная реализация поиска подстроки в строке. Простейшие эффективные алгоритмы – префикс-функция, z-функция. Эффективный поиск подстроки. Алгоритм Кнута-Морриса-Пратта. Нахождение количества различных подстрок. Преобразование строки в число. Понятия хэширования, хэш-функции, коллизии. Полиномиальный хэш. Вероятность коллизии, «парадокс» дней рождений. Два вида задач на хэширование. Хэши по модулю 2^64. Использование 128-битного типа данных, другие способы перемножения больших чисел. Нахождение хэша подстроки, быстрое сравнение подстрок. Нахождение количества подстрок через хэши.
Лекция 27 – Дерево отрезков
Общий вид задачи с множеством запросов к массиву. Пример – нахождение суммы на отрезке. Подходы к эффективному решению подобных задач. Идея дерева отрезков, запрос изменения, запрос нахождения значения, доказательство вычислительной сложности. Требования к целевой функции на отрезке. Создание структуры, описывающей отрезок, рекурсивная реализация запросов. Более эффективная работа с памятью. Проверка корректности индексов, метод assert. Нахождение количества инверсий в массиве.
Закрепляющий контест – первый год
Способы нахождения площади – формула Герона, метод трапеций, формула Пика. Ориентированная площадь, векторное произведение, определитель матрицы. Нахождение площади многоугольника через триангуляцию. Проверка нахождения точки внутри многоугольника. Проверка пересечения отрезков через ориентированную площадь. Нахождение точки пересечения через систему уравнений. Формулы Крамера. Обобщение проверки пересечения на случай луча и прямой, общее решение в целых числах. Окружность, угол. Связь длины дуги, длины хорды, величины угла. Пересечение окружностей.
Лекция 26 – Алгоритмы на строках
Наивная реализация поиска подстроки в строке. Простейшие эффективные алгоритмы – префикс-функция, z-функция. Эффективный поиск подстроки. Алгоритм Кнута-Морриса-Пратта. Нахождение количества различных подстрок. Преобразование строки в число. Понятия хэширования, хэш-функции, коллизии. Полиномиальный хэш. Вероятность коллизии, «парадокс» дней рождений. Два вида задач на хэширование. Хэши по модулю 2^64. Использование 128-битного типа данных, другие способы перемножения больших чисел. Нахождение хэша подстроки, быстрое сравнение подстрок. Нахождение количества подстрок через хэши.
Лекция 27 – Дерево отрезков
Общий вид задачи с множеством запросов к массиву. Пример – нахождение суммы на отрезке. Подходы к эффективному решению подобных задач. Идея дерева отрезков, запрос изменения, запрос нахождения значения, доказательство вычислительной сложности. Требования к целевой функции на отрезке. Создание структуры, описывающей отрезок, рекурсивная реализация запросов. Более эффективная работа с памятью. Проверка корректности индексов, метод assert. Нахождение количества инверсий в массиве.
Закрепляющий контест – первый год
Преподаватели
Шмелев Алексей Сергеевич
- Руководитель лаборатории олимпиадного программирования в Университете НЕЙМАРК
- Тренер команд ННГУ, ВШЭ-НН, НГТУ, ННГАСУ
- Серебряный медалист финала ICPC
- Участник финалов международных соревнований — Google Code Jam, Google Hash Code, CodeChef SnackDown, Russian Code Cup, Russian AI Cup
- Победитель программы для преподавателей олимпиадного программирования VK Fellowship
Каримова Анастасия Михайловна
- Инженер Техкомпании "Хуавей"
- Участник полуфиналов ICPC
- Призер Четвертьфиналов ICPC
- Призер TechArena Volga Challenge
- Призер чемпионата Volgograd STU Open
Алясева Диана Александровна
- Специалист по методической работе лаборатории олимпиадного программирования Университета НЕЙМАРК.
- Полуфиналист ICPC. Финалист международного чемпионата по спортивному программированию BSUIR Open XIII.
- С 2024 года является членом Региональной предметно-методической комиссии по информатике в Нижегородской области. Тренер школьных команд.
- Преподаватель алгоритмов и структур данных в Т-Поколении Параллель С с 2024 года.
- Руководитель лаборатории олимпиадного программирования в Университете НЕЙМАРК
- Тренер команд ННГУ, ВШЭ-НН, НГТУ, ННГАСУ
- Серебряный медалист финала ІСРС
- Участник финалов международных соревнований - Google Code Jam, Google Hash Code,
- CodeChef SnackDown, Russian Code Cup, Russian AI Cup
- Победитель программы для преподавателей олимпиадного программирования VK
- Fellowship
Шмелев
Алексей Сергеевич
Алексей Сергеевич
- Инженер Техномпании "Хуавей"
- Участник полуфиналов ICPC
- Призер Четвертьфиналов ICPC
- Призер TechArena Volga Challenge
- Призер чемпионата Volgograd STU
Каримова
Анастасия Михайловна
Анастасия Михайловна
- Специалист по методической работе лаборатории олимпиадного программирования
- Университета НЕЙМАРК.
- Полуфиналист ІСРС. Финалист международного чемпионата по спортивному
- программированию BSUIR Open XIII.
- С 2024 года является членом Региональной предметно-методической комиссии по информатике в Нижегородской области. Тренер школьных команд.
- Преподаватель алгоритмов и структур данных в Т-Поколении Параллель С с 2024 года.
Алясева
Диана Александровна
Диана Александровна
Формат участия
Занятия проходят очно в течение учебного года, раз в неделю:
▪ по средам с 18:00 до 19:30, 4й корпус ННГУ им. Лобачевского
▪ по четвергам с 18:00 до 19:30, 1й корпус НГТУ им. Р.Е. Алексеева
Примеры реализации алгоритмов приводятся на языке C++.
По каждой теме подготовлен список задач на платформе CodeForces. Наиболее важные и красивые задачи будут также разобраны на лекциях.
После каждого блока тем будет проходить «закрепляющий» контест, обычно такие соревнования проводим в офисах нижегородских IT-компаний.
▪ по средам с 18:00 до 19:30, 4й корпус ННГУ им. Лобачевского
▪ по четвергам с 18:00 до 19:30, 1й корпус НГТУ им. Р.Е. Алексеева
Примеры реализации алгоритмов приводятся на языке C++.
По каждой теме подготовлен список задач на платформе CodeForces. Наиболее важные и красивые задачи будут также разобраны на лекциях.
После каждого блока тем будет проходить «закрепляющий» контест, обычно такие соревнования проводим в офисах нижегородских IT-компаний.
Да
Сертификат, подписанный Университетом НЕЙМАРК и ННГУ, будет выдан тем, кто успешно пройдет курс – решит достаточно много задач на финальном контесте. Первокурсники ИТММ могут также получить официальный зачёт
Нет, но будут конспекты лекций, включая разборы задач «закрепляющих» контестов
Да. Посещение занятий поможет выработать привычку регулярно заниматься олимпиадами. Кроме того, на очных лекциях будет разбираться больше задач, а также можно задать вопросы по теории
Да. Конечно, наша цель – результаты на олимпиадах. Однако, если решили только получить знания на лекциях, тоже приходите
Нет, приглашаются все желающие, в том числе студенты других вузов, выпускники и уверенные в своих силах школьники!
Занятия проводятся в большой аудитории, вмещающей до 200 человек
Да, задачи всегда есть в специальной группе на CodeForces, их можно решать в любое время. Но «долги», конечно, лучше не накапливать
Для людей ниже уровня участника заключительного этапа ВСОШ рекомендуется посещать занятия – есть и достаточно сложные задачи, и нетривиальная теория, которую обычно не рассказывают школьникам. Если на каких-то темах будет слишком легко, можно просто порешать задачи из архивов
Для начала занятий не требуется глубоких знаний C++, достаточно самых основ. Если есть цель добиться успеха в олимпиадах, то рекомендуется использовать именно C++, ресурсы для быстрого старта порекомендуем. Если же хочется только узнать алгоритмы, то подойдет любой язык программирования, в том числе и для решения задач.
Не обязательно. На лекциях не требуется написание кода, конспекты вести тоже не обязательно – материал будет предоставлен, где можно будет «подсмотреть» детали. Рекомендуется сфокусироваться на понимании теории и не терять нить повествования