• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Факультатив «Подготовка к студенческим олимпиадам по программированию»

Лекционные занятия факультатива «Подготовка к студенческим олимпиадам по программированию» проходит по адресу: Кочновский проезд, д. 3, ауд.501 по четвергам с 16:40 до 18:00 (6 пара). Консультации проходят в с 13:40 до 16:30 (4 и 5 пара) там же. На факультативе опытные участники олимпиад пишут командные тренировки, а начинающие слушают лекции по применению различных алгоритмов в олимпиадных задачах и решают тренировочные индивидуальные туры. Раз в две недели также проводятся открытые лекции для всех желающих, информация о них публикуется в новостях сайта. Для поступления на факультатив необходимо заполнить анкету.

Первое занятие факультатива состоится 14 сентября 2016 года. Перед посещением факультатива всем, кроме первокурсников ПМИ и участников факультатива прошлого года, необходимо написать виртуальный турнир, в котором нужно постараться полностью решить как можно больше задач.

Турнир можно начать в любое время до 17 сентября, его продолжительность 5 часов.
вход в турнир

Кроме занятий в НИУ ВШЭ, слушатели факультатива участвуют в командных тренировках по субботам с 14:30 до 20:00 в компании Яндекс. Новости и рабочие вопросы факультатива публикуются в группе Вконтакте. Там же можно задать любые вопросы по участию в олимпиадах в ВШЭ и по работе факультатива.

Принять участие в олимпиадах по программированию могут все желающие студенты ВШЭ, Центр студенческих олимпиад может оказать вам помощь в поиске и подборе команды.

Ключевые даты соревнований

16 октября — московский четвертьфинал ACM ICPC.

Начало – середина декабря — полуфинал ACM ICPC (Санкт-Петербург).

Май-июнь 2017 года — финал ACM ICPC.

Кроме этого, предполагается участие в турах Открытого кубка, Всесибирской олимпиаде по программированию, чемпионате Урала и других соревнованиях, а также в сборах в Петрозаводске и Ижевске.

Среди личных соревнований можно отметить следующие:

Яндекс.Алгоритм — июнь–август

Google Code Jam — апрель–август

Russian Code Cup — апрель–октябрь

Facebook Hacker Cup — январь–март

Примерное содержание программы:

Ниже приведен список основных олимпиадных алгоритмов, которые будут отрабатываться на тренировках. Подразумевается, что студенты знакомы со значительной частью этих алгоритмов (или познакомятся на других курсах в процессе обучения), и основное время будет уделяться их применению и реализации.

Алгоритмы сортировки в олимпиадных задачах

Сортировки подсчетом, поразрядная, слиянием, быстрая, пирамидальная, trim-sort. Сравнение эффективности и методы оптимизации сортировки.

Алгоритмы поиска в олимпиадных задачах

Линейный, бинарный и тернарный поиск. Бинарный поиск по ответу. Стандартные функции поиска.

Задачи на обработку текстов

Разбиение на токены, конечные автоматы, грамматики.

Использование структур данных из стандартной библиотеки языка программирования

Хеш-таблицы, сбалансированные бинарные деревья поиска, стеки, очереди, деки, словари, динамически расширяемые массивы.

Применение хеш-функций

Быстрое вычисление хеш-функций и условия его применения, хеш-функции от подстрок, сочетание хешей и бинарного поиска, суффиксный массив.

Применение нестандартных структур данных и их эффективная реализация

Деревья отрезков, RMQ, RSQ, дерево Фенвика, Декартово дерево, бор.

Динамическое программирование

Динамическое программирование с одним и несколькими параметрами, по подстрокам, с введением дополнительного параметра, по профилю.

Применение алгоритмов на графах

Обход в глубину и решаемые с его помощью задачи, кратчайшие пути в графе, остовные деревья, потоки.

Полный перебор, методы его оптимизации и рандомизированные алгоритмы

Метод ветвей и границ, жадные алгоритмы, генетическое программирование, метод отжига.

Использование математических алгоритмов

Простые числа и факторизация, системы счисления, быстрое преобразование Фурье.

Геометрические алгоритмы

Скалярные и векторные произведения, пересечения фигур, выпуклые оболочки, стереометрические задачи, использование бинарного поиска в вычислительной геометрии.

Методы тестирования олимпиадных задач

Автоматизация тестирования, правила написания решений, генерация стресс-тестов, практикум по подготовке исчерпывающего набора тестов.

Обзор задач по обработке больших данных

Применение математической статистики и основ машинного обучения к решению реальных задач, олимпиады по аналитике, Kaggle.

Обзор соревнований по компьютерной безопасности

Практическое применение знаний об архитектуре компьютера, устройстве ОС и сетевых протоколов. Декомпиляция и реверс-инжениринг. Участие в соревнованиях “Capture the flag”.