Математика в кафе. S2E2.

Математика Оставить комментарий

Задача о Васе в интернете.

Задача навеяна условием задачи "на соображение" из журнала Компьютерра. Программист Вася играет в интернете в такую игру: начиная с какой-то страницы он начинает ходить по страницам, переходя всегда по первой ссылке со страницы. Известно, что с каждой страницы есть хотя бы одна ссылка.

Как ему понять, что он уже "зациклился", если его браузер умеет сохранять только конечное число "закладок"? (в оригинальном условии — 2 закладки).

Участвовали: Володя, Лёша, Катя, Саша, Лена, Алёша, Настя, я.

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

Текст получился путаным, но, боюсь, что ничего более толкового я в ближайшее время не напишу, а потом — и подавно 🙁

Конфигурация той части сети, по которой будет ходить Вася, всегда состоит из начальной "предпериодической" последовательности из k страниц и цикла длины l, где k и l Васе неизвестны.

Алгоритм, позволяющий достоверно определить, что мы уже "зациклились", в общем виде выглядит следующим образом:

закладка обновляется в p-ый раз перед f(p)-ым шагом, где f(p) — функция, такая что f(p+1) - f(p) > f(p) - f(p-1), т.е. число переходов между двумя "заложенными" страницами возрастает. При этом до установки очередной закладки мы переходим между страницами, сравнивая каждую текущую с "заложенной".

Далее анализировался алгоритм, в котором число шагов между соседними закладками равно степени двойки, т.е. первая закладка ставится в самой первой вершине, вторая — через 1 вершину, третья — ещё через 2, потом через 4, через 8, и т.д. Таким образом в качестве функции f(p) была выбрана функция 2p-1.

Возникает вопрос о том, сколько шагов потребуется такому алгоритму на сети с "хвостом" длины k и циклом длины l.

Легко заметить, что номер P первой закладки, попавшей в цикл, удовлетворяет неравенству
2P-1 ≥ k. Наименьшее такое целое P = ]log2(k+1)[.

Если 2P ≥ l, то пройдя от закладки l шагов (ещё до установки следующей закладки) мы узнаем, что мы в цикле.

Если же 2P < l, то сначала придётся довести номер закладки до Q, такого что 2Q ≥ l. Наименьшее такое целое Q = ]log2l[.

Обозначая число шагов на сети с хвостом из k страниц и циклом из l через S(k,l) получаем, что


S(k,l) = 2]log2(k+1)[-1+l при 2]log2(k+1)[ ≥ l
S(k,l) = 2]log2l[-1+l при 2]log2(k+1)[ < l

Пусть теперь k+l = n. Зафиксируем значение n и рассмотрим среднее число шагов по сетям с различными k и l, 0 ≤ k ≤ n-1.



где под S*(k,n-k) понимается 2]log2(k+1)[ или 2]log2(n-k)[ в зависимости от соотношения между 2]log2(k+1)[ и n-k.

Остаётся получить значение суммы S*(k,n-k).

Заметим, что k+1 ≤ 2]log2(k+1)[ ≤ 2(k+1).

Если k+1 ≥ n-k, то 2]log2(k+1)[ тем более превышает n-k, а значит при k≥(n-1)/2 выполнено S*(k,n-k) = 2]log2(k+1)[.

Если 2(k+1) < n-k, то 2]log2(k+1)[ тем более не превышает n-k, а значит при k < (n-2)/3 выполнено S*(k,n-k) = 2]log2(n-k)[.

"Сомнительным" для функции S*(k,n-k) является только промежуток от (n-2)/3 до (n-1)/2, но на нём легко проверить выполнение оценки


2]log2(k+1)[ ≤ S*(k,n-k) ≤ 2]log2(n-k)[.

Таким образом,


В действительности, это суммы отличаются не больше, чем в одном слагаемом. Для того, чтобы их вычислить, получим формулу для

Обозначим ]log2m[ через ψ. Тогда 2ψ-1 < m ≤ 2ψ, откуда следует, что в нашей сумме не более 2ψ-1 слагаемых со значением 2ψ (а на самом деле, за исключением последней группы слагаемых, их ровно 2ψ-1).

Поэтому искомую сумму можно представить в виде

Обозначив ]log2n[ через φ и выполнив кучу преобразований с полученной формулой, можно получить, что


Разделив сумму на n и с учётом уже полученного ранее добавка, получаем, что среднее время не превышает величины



Асимтотически эта оченка, по-видимому, колеблется от 7n/4 (для "хороших" n=2s) до 2n (для "плохих" n=2s+1).

Параллельно с приведённой выше кучей вычислений анализировался алгоритм, в котором функция f(p) основывалась на арифметической, а не на геометрической прогрессии, а найти требовалось не просто "вершину в цикле", но и значения параметров k и l. Для построенного там алгоритма среднее время (как утверждает Володя) получилось квадратичным по n.

По итогам всего написанного можно сформулировать некоторые открытые вопросы:

  • Насколько точна полученная верхняя оценка для среднего времени? (Требуется куча аккуратных вычислений...?)
  • Насколько лучше можно сделать результат, если использовать более одной закладки?
  • Как можно ли оптимизировать время нахождения цикла, подбирая подходящую функцию для точек установки закладок? ("Арифметический" шаг, по-видимому, ухудшает дело. Возможно надо использовать "прогрессию" с основанием e? — такая идея озвучивалась...)
  • Сколько шагов требуется для точного нахождения k и l? (И как на это влияет количество доступных закладок?)

4 комментария к “Математика в кафе. S2E2.”

Оставить комментарий

Тема WordPress и иконки разработаны N.Design Studio
© 2018 Страница Алексея Яшунского RSS записей RSS комментариев Войти