Исследовательские задачи

Уважаемые друзья!

На этой странице публикуются исследовательские задачи Unsolved, которые не обязательно имеют четкую постановку или даже окончательное решение. Каждая Unsolved – это скорее не задача, а направление исследований. Идею Unsolved предложил наш читатель axiomatikos.

Формулировка очередной Unsolved сопровождается комментариями автора, соображениями и, надеемся, решениями читателей.

Присылайте интересные Unsolved по адресу agievich at bsu by.

Unsolved № 2. Парковка

Улица Л имеет длину l. На улице организовано одностороннее автомобильное движение и вся правая сторона Л предназначена для парковки. Боб в автомобиле находится в начале улицы и хочет добраться в самый ее конец, к месту работы. Боб может ехать на автомобиле со скоростью v₁, запарковать автомобиль на свободном месте, а затем идти пешком со скоростью v₂ < v₁. Боб может попытаться подъехать как можно ближе к концу улицы, чтобы сократить время ходьбы пешком. Однако свободных для парковки мест может не оказаться, разворачиваться нельзя и Бобу придется сделать круг по кварталу, чтобы  вернуться в начало Л. Для этого Бобу потребуется время t. Боб может оценивать плотность запаркованных машин на начальном отрезке улицы и, руководствуясь этой оценкой, принимать решение о парковке на очередном свободном месте. Проблема в том, что другие водители действуют примерно так же, поэтому плотность свободных мест на протяжении улицы меняется, что затрудняет принятие решения.
Предложите стратегию, которая позволит Бобу попасть на работу как можно раньше.

Автор: agievich.

Дата публикации: 25.07.2012.

Комментарии автора:

[25.07.2012] Менять скорость движения на автомобиле запрещено. Можно только остановиться для парковки на свободном месте.

Соображения:

[CryptoOfficer, 16.10.2012] pdf.

Unsolved № 1. Определить ключ

Пусть X = {0,1}^_n – множество двоичных слов длины n. На X заданы две бинарные операции: операция ⊕ сложения слов-как-двоичных-векторов и операция + сложения слов-как-чисел (по модулю 2ⁿ ): 110 ⊕ 011 = 101,  110 + 011 = 001. Задана случайная биекция g: X→X. Предполагается, что значения g эффективно вычисляются, например, g задана таблично. Зашифрование открытого текста a в шифртекст b на ключе (x, y) выполняется по правилу:
    b = g(a + x) ⊕ y,      a, b, x, y ∈ X.
Предложите алгоритм определения неизвестного ключа (x, y) по T парам (открытый текст a_t, шифртекст b_t). Алгоритм должен быть существенно проще полного перебора ключей.
Число пар T может быть большим. Более того, при решении можно выбирать открытый текст a_t и получать соответствующий шифртекст b_t.

Автор: axiomatikos.

Дата публикации: 06.05.2012.

Комментарии автора:

[17.04.2012] pdf.

Соображения: