Компьютерные науки

Базовые и продвинутые алгоритмы для школьников

Расширенная программа по алгоритмике для участников олимпиад. Охватывает как базовые концепции, так и продвинутые темы: двоичный поиск, обход графов, деревья и работу со строками.
Студентов 2682 Выпускников 169 Для специалистов
690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Темы:
Алгоритмы и сложность, Программирование
Объем
36 час.
Длительность
30 дней
Нагрузка в неделю
9 час.
Формат обучения
Дистанционно (самостоятельно)
Описание Учебная программа посвящена глубокому погружению в олимпиадное программирование. В учебной программе изучаются системы непересекающихся множеств, динамика на деревьях разбора, алгоритмы поиска кратчайшего пути и вычислительная геометрия. Разбор сложных структур данных и алгоритмических методов поможет школьникам и начинающим программистам повысить свой уровень. Материал выстроен вокруг разбора продвинутых концепций от обхода графов до динамического программирования и работы со строками. Изучение подкрепляется проверочными тестами по каждой теме.
Цели
  • Сформировать навыки применения продвинутых олимпиадных алгоритмов.
  • Познакомить с методами работы на графах и остовных деревьях.
  • Раскрыть сложные аспекты динамического программирования.
Чему я научусь?
  • Реализовывать обход графов в глубину (DFS) и поиск кратчайшего пути.
  • Применять динамическое программирование на деревьях разбора.
  • Разрабатывать эффективные алгоритмы для работы со строками.

Авторы

Копелиович Сергей Владимирович
Копелиович Сергей Владимирович
Студент СПбГУ, факультет мат-мех, призер (золотая медаль) Международной олимпиады по информатике и финала студенческого чемпионата мира по программированию
Мельников Сергей Вячеславович
Мельников Сергей Вячеславович
Студент СПбГУ ИТМО, неоднократный призёр всероссийских олимпиад по информатике, финалист TopCoder High School Tournament 2008
Пестов Олег Александрович
Пестов Олег Александрович
Инженер-программист, Crystal Reality LLC
Чему я научусь?
  • Реализовывать обход графов в глубину (DFS) и поиск кратчайшего пути.
  • Применять динамическое программирование на деревьях разбора.
  • Разрабатывать эффективные алгоритмы для работы со строками.

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Двоичный поиск В лекции подробно рассматриваются быстрая сортировка и сортировка слиянием, относящиеся к группе сортировок сравнения. Подробно разбираются... В лекции подробно рассматриваются быстрая сортировка и сортировка слиянием, относящиеся к группе сортировок сравнения. Подробно разбираются сортировка подсчетом, цифровая и корзинная сортировки. Для каждого метода сортировки приводятся оценки времени выполнения. Рассматривается задача Райта для графов, приводится пример двоичного поиска по ответам ещё
Двоичный поиск тест для курса Базовые и продвинутые алгоритмы для школьников 60 мин
2 Алгоритмы и методы сортировки. Алгоритмы нахождения кратчайшего пути в графе В первой половине лекции подробно рассматриваются метод сортировки подсчетом и метод цифровой (поразрядной) сортировки. Приводятся оценки... В первой половине лекции подробно рассматриваются метод сортировки подсчетом и метод цифровой (поразрядной) сортировки. Приводятся оценки времени их выполнения. Дается определение понятия списка, программно реализуются основные операции работы со списком. Во второй половине лекции рассматриваются алгоритм поиска вершины в графе в ширину и алгоритм Дейкстры нахождения кратчайшего пути во взвешенном графе. Для каждого алгоритма приводятся варианты программной реализации, оценки времени выполнения, примеры практического использования ещё
Алгоритмы и методы сортировки. Алгоритмы нахождения кратчайшего пути в графе тест для курса Базовые и продвинутые алгоритмы для школьников 60 мин
3 Алгоритмы и методы поиска кратчайшего пути в графе В данной лекции приводится метод хранения графа в виде списка. Подробно рассматриваются алгоритмы обхода графа в... В данной лекции приводится метод хранения графа в виде списка. Подробно рассматриваются алгоритмы обхода графа в ширину и в глубину, алгоритмы Форда-Беллмана и Флойда поиска кратчайшего пути во взвешенном графе. Для каждого алгоритма приводятся варианты программной реализации, оценки времени выполнения, примеры практического использования ещё
Алгоритмы и методы поиска кратчайшего пути в графе тест для курса Базовые и продвинутые алгоритмы для школьников 60 мин
4 Алгоритм обхода графа в глубину В лекции рассматривается применение алгоритма обхода графа в глубину к решению практических задач. В начале лекции... В лекции рассматривается применение алгоритма обхода графа в глубину к решению практических задач. В начале лекции подробно рассматривается алгоритм метода и его программная реализация. Далее рассматривается применение метода к решению задач поиска циклов в графе, топологической сортировки вершин, поиска компонент связности и сильной связности в графе ещё
Алгоритм обхода графа в глубину тест для курса Базовые и продвинутые алгоритмы для школьников 60 мин
5 Алгоритм DFS В первой половине лекции рассматривается применение алгоритма DFS к задаче о мостах и задаче поиска точек... В первой половине лекции рассматривается применение алгоритма DFS к задаче о мостах и задаче поиска точек сочленения графа. Подробно разбираются алгоритмы решения и варианты их программной реализации. Формулируются и доказываются критерии существования эйлеровых цикла и пути в графе. Во второй половине лекции вводятся понятия новых типов данных - кучи и очереди с приоритетами. Определяются основные операции над элементами данных типов, приводятся варианты их программной реализации ещё
Алгоритм DFS тест для курса Базовые и продвинутые алгоритмы для школьников 60 мин
6 Системы непересекающихся множеств. Остовные деревья В лекции вводится понятие системы непересекающихся множеств (СНМ). Рассматриваются примеры СНМ, возможные варианты реализации, основные операции... В лекции вводится понятие системы непересекающихся множеств (СНМ). Рассматриваются примеры СНМ, возможные варианты реализации, основные операции над элементами СНМ. Во второй половине лекции рассматриваются остовные деревья (ОД), объясняются основные алгоритмы построения ОД ещё
Системы непересекающихся множеств. Остовные деревья тест для курса Базовые и продвинутые алгоритмы для школьников 60 мин
7 Динамическое программирование В первой части лекции повторяются основные моменты алгоритмов Прима и Краскала построения остовных деревьев. Во второй... В первой части лекции повторяются основные моменты алгоритмов Прима и Краскала построения остовных деревьев. Во второй части вводится понятие динамического программирования, рассматриваются алгоритмы вычисления числа сочетаний из n по k. В заключительной части лекции подробно разбираются несколько примеров задач динамического программирования ещё
Динамическое программирование тест для курса Базовые и продвинутые алгоритмы для школьников 60 мин
8 Динамическое программирование. Деревья разбора Начало лекции посвящено повторению пройденного в предыдущей лекции материала. Подробно разбираются решения задач на разбиение числа... Начало лекции посвящено повторению пройденного в предыдущей лекции материала. Подробно разбираются решения задач на разбиение числа и поиск наборов чисел с суммой меньше заданного методом динамического программирования. Дается понятие динамики на подотрезках. Подробно рассматриваются алгоритмы работы с деревьями разбора ещё
Динамическое программирование. Деревья разбора тест для курса Базовые и продвинутые алгоритмы для школьников 60 мин
9 Динамика на деревьях В данной лекции на примерах решения задач подробно разбираются основные моменты работы с использованием динамики на... В данной лекции на примерах решения задач подробно разбираются основные моменты работы с использованием динамики на деревьях. Дается определение понятия триангуляции. Решаются задачи на повторение пройденного материала ещё
Динамика на деревьях тест для курса Базовые и продвинутые алгоритмы для школьников 60 мин
10 Вычислительная геометрия Лекция посвящена работе с многоугольниками. Рассматриваются алгоритмы Джарвиса и Грэхема построения выпуклых оболочек. Вводится понятие двоичного... Лекция посвящена работе с многоугольниками. Рассматриваются алгоритмы Джарвиса и Грэхема построения выпуклых оболочек. Вводится понятие двоичного дерева поиска. ещё
Вычислительная геометрия тест для курса Базовые и продвинутые алгоритмы для школьников 60 мин
11 Строки Лекция посвящена работе со строками. Рассматриваются алгоритмы Кнута-Морриса и Z-алгоритм поиска подстроки в строке. Вводится понятие... Лекция посвящена работе со строками. Рассматриваются алгоритмы Кнута-Морриса и Z-алгоритм поиска подстроки в строке. Вводится понятие Z-функции, приводится алгоритм ее вычисления ещё
Строки тест для курса Базовые и продвинутые алгоритмы для школьников 60 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

Какой документ я получу?

Сертификат

Выдаётся автоматически после успешного завершения программы.

Удостоверение о повышении квалификации

Выдается при наличии среднего специального или высшего образования (необходимые документы).

Стоимость программы

690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^