Студенческая олимпиада «Я — профессионал»: направление «Программирование и информационные технологии»

Сегодня последний день регистрации на студенческую олимпиаду «Я — профессионал». И мы рассказываем о направлении «Программирование и информационные технологии».

Генеральный партнер олимпиады по направлениям Университета ИТМО — «Программирование и ИТ», «Информационная и кибербезопасность», «Большие данные» — Сбербанк.


^{Christina Morillo / Pexels / PD}

Пара слов об олимпиаде «Я — профессионал»

Студенческая олимпиада «Я — профессионал» — это конкурс для бакалавров и магистров гуманитарных и технических специальностей. Те студенты, которые хорошо покажут себя на олимпиаде, смогут поступить в российские вузы без экзаменов. При этом они будут проходить стажировку в ведущих российских ИТ-компаниях: Яндексе, Сбербанке, IBS и Мэйл.Ру.

Олимпиада начнется 24 ноября (сегодня последний день регистрации) — это дата старта отборочных этапов. Они будут проходить в онлайн-формате. Те участники, которые выйдут в следующий тур, попадут на очный этап соревнования. Он пройдет в различных университетах страны в феврале 2019 года.

Какие направления олимпиады мы курируем

Университет ИТМО занимается подготовкой заданий по следующим направлениям: «Программирование и ИТ», «Информационная и кибербезопасность» и «Фотоника».

Еще в этом году мы представили два новых направления:

• «Робототехника»: Темами направления являются механика, электроника и управление. Участвовать стоит тем студентам, кто планирует продолжать обучение по специальностям прикладная механика, программная инженерия и др. Партнерами этого направления выступили компания «Моторика», НПО «Андроидная техника», DNS.
• «Большие данные»: тематика этого направления включает анализ данных, статистику и машинное обучение. Подойдет студентам, обучающимся на факультетах прикладной информатики, ИВТ, информационных технологий в гуманитарной сфере и др. Среди партнеров числятся такие компании, как Газпром, Сименс, МТС и Деловые линии.

Далее, мы подробнее расскажем о направлении «Программирование и информационные технологии».

О направлении «Программирование и ИТ»

Университет ИТМО — один из крупнейших организаторов мероприятий, близких по уровню к олимпиаде «Я — профессионал».

Мы проводим большое количество творческих соревнований и конкурсов по информатике и программированию. Это школьные олимпиады, например Всероссийская командная олимпиада школьников, олимпиада «Информационные технологии» и ИОИП. Также мы организуем студенческие олимпиады, в частности, полуфинал чемпионата мира по программированию ICPC.

При работе над направлением «Программирование и информационные технологии» мы учли богатый опыт проведения других тематических соревновательных мероприятий в ИТ-сфере и экспертизу коллег. Например, с этого года в Университете ИТМО работает автор и разработчик портала Codeforces Михаил Мирзаянов.

Подготовкой направления «Программирование и информационные технологии» со стороны Университета ИТМО занимаются сотрудники соответствующего факультета. Это декан Парфенов Владимир Глебович, а также доцент и тренер студенческой команды ИТМО по спортивному программированию Станкевич Андрей Сергеевич.

В проектировании и разработке заданий олимпиады участвуют сотрудники ИТ-компаний, преподающие на факультете профильные дисциплины, и сотрудники вузов-соорганизаторов. Этими вузами являются Уральский федеральный университет, Северо-Восточный федеральный университет им. Аммосова, Саратовский государственный университет и Самарский университет.

Как подготовиться к олимпиаде

Направление «Программирование и информационные технологии» основано на знании математики, информатики и умении разрабатывать надежное и безопасное программное обеспечение. Во время подготовки студентам желательно повторить теорию вычислительной сложности, теорию формальных языков и грамматик, принципы построения вычислительных архитектур, ООП и параллельного программирования, теорию реляционных баз данных.

Мы рекомендуем посмотреть тематические вебинары, подготовленные нашими преподавателями. Например, в этом видео рассматриваются вопросы хранения данных и принципы работы операционных систем.

Во втором вебинаре направления речь идет об алгоритмах и структурах данных:

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

Пример задачи: Дан код на абстрактном языке программирования имитирующий работу очереди запросов.

Код для задачи

queue tasks;
task worker_task;

void do_task(task) { sleep(random()) : }

void request() {
  while (true) {
    new_task = new task();
    if (worker_task == null)
      worker_task = new_task;
    else if (queue.size() < 5)
      queue.push(new_task) sleep(random())
  }
}

void worker() {
  while (true) {
    if (worker_task == null) {
      sleep(1000);
    } else {
      do_task(worker_task);
      if (queue.notEmpty()) worker_task = queue.pop();
    }
  }
}

main() {
  thread worker_thread(worker);
  for (int i = 0; i < N; ++i) {
    threadr tr(request)
  }
}

В отдельном потоке запускается процесс worker, который обрабатывает задачи, поступающие из N (N > 1) потоков request. Метод do_task имитирует выполнение задач.

Какие из следующих утверждений верны?

1. Race condition по переменной worker_task
2. Очередь queue может содержать 6 элементов
3. Система может перестать выполнять задания, даже если очередь не пуста.
4. Система всегда будет выполнять задания, если они будут поступать,
5. Система гарантированно выполнит все поступившие задания.

Ответ: 1, 2, 3

Далее, в качестве примера приведем задание из заключительного этапа. Вот задача, связанная с операционными системами и планированием выполнения процессов.

Пример задачи: Рассмотрим вычислительную систему с одним центральным процессором, который в каждый момент времени может осуществлять вычисления только одного процесса. Системное время дискретно и измеряется в условных тактах.

Продолжение текста задачи

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



Для управления порядком выполнения заданий используется многоуровневая очередь. Для каждого источника формируется своя FIFO очередь из заданий этого источника. Очередям присвоены приоритеты. Процесс выполнения конкретного задания может быть запущен только, если ни в одной очереди с большим приоритетом нет ни одного задания.

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

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

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

• Будем считать, что момент появления задания, это начальный момент указанного такта. Соответственно, когда мы говорим, что такт появления первого задания от источника равен 1, а количество тактов до появления следующего задания равно 5, то второе задание от этого источника появиться в начале такта 6.
• Время, требуемое на переключение для выполнения следующего задания, будем считать несущественным и не учитывать при решении задания.
• У каждого источника независимая нумерация заданий, начинающаяся с 1.

Ответ: 24

Большие информации по теме можно подчерпнуть в тематических курсах по программированию из утвержденного списка на сайте олимпиады.

Дополнительные ссылки по теме:

• Олимпиада «Я — профессионал» — официальный сайт
• О направлении «Программирование и информационные технологии»
• Нормативные документы и правила участия