CSEDays. Theory 2011

Екатеринбург, 14-17 апреля

News subscription
Share:

Reviews

Очень понравилась организация, все продумано, есть время пообщаться. Вкусные кофе-брейки!
Алексей / CSEDays. Theory 2011
Home / CSEDays Theory 2011 /

Участие в CSEDays.Theory 2011

В школе могут принять участие* студенты, аспиранты, молодые ученые, а также специалисты IT-компаний.

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

Кандидатам на участие в школе нужно пройти конкурсный отбор. Решение о приглашении участника на школу принимается по итогам рассмотрения поступивших заявок (выполнение домашнего задания – необязательное условие). Ограниченному числу претендентов по результатам конкурсного отбора будут предоставлены гранты на покрытие затрат на проживание и питание во время школы. В этом случае вам надо будет оплатить только дорогу до Екатеринбурга.

* Под участием понимается посещение всех мероприятий в рамках CSEDays.Theory 2011 (доклады, круглые столы, развлекательные мероприятия).

Важные даты

Заявки на участие в школе и выполненные домашние задания принимались до 24 марта 2011 года.

Участники получили уведомления о результатах набора 1 апреля 2011 года.

Домашнее задание

Предлагаем вам подумать над следующими задачами (нумерация идет от простого к сложному). Решение (или его часть) можно вписать в заявку или отправить нам позже в ответ на уведомление о поступлении заявки. Присылать решение необязательно, но это повышает ваши шансы на участие в школе и получение гранта от спонсоров. Удачи!

Задача 1. 

Что находит следующий фрагмент кода?

int f(int x); //  функция f определена в другом месте программы

typedef pair <int, int> Pair;
stack<Pair> s;
int n = 0;
int x = 0;
s.push(Pair(x, n));
for(;;)
{
  x = f(x); n++;
  while(!s.empty() && s.top().first < x)
    s.pop();
  if(!s.empty() && s.top().first == x)
    return n - s.top().second;
  s.push(Pair(x, n));
}

Задача 2. 

Предположим, что функция f есть случайная функция, отображающая интервал [0..N-1] в себя. 

Оцените среднее время работы кода из предыдущего пункта и его требование к памяти.

Задача 3. 

Покажите, что если задача нахождения коллизий в функции f(x) = g^x mod N, 

где g - генератор группы квадратичных вычетов по модулю N, а N - произведение двух простых чисел, 

решается за полиномиальное время от длины N, то задача разложения числа N на простые сомножители также решается за полиномиальное время. 

Указание: для решения (и понимания условия) можно пользоваться любыми источниками.

Илья Миронов:

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

Загрузить файл с заданием.