Правильно ли мое доказательство?

[GrishinUS]

Цитата:

Я, возможно, придираюсь на самом деле и Вам все нужно более просто, но дело в том, что как раз в таких базовых вещах часто находятся хитрые заковыки :)

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

Цитата:

(про быстрое умножение слышали?).

Теперь слышал. А разве он работает на неполных исходных данных?

[Xaositect]

GrishinUS в сообщении #322723 писал(а):

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

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

GrishinUS в сообщении #322723 писал(а):

Теперь слышал. А разве он работает на неполных исходных данных?

Да нет, это я к тому, что оно неочевидно. Колмогоров вначале думал, что перемножать быстрее чем за $n^2$ нельзя.

-- Сб май 22, 2010 14:34:16 --

Я бы написал что-то такое:

Пусть мы считали начальный отрезок $x_1,\dots,x_n$. Докажем, что для любого номера $i$ найдется такое продолжение последовательности $x_{n+1},\dots,x_{n+m_i}$, что $\mathrm{median}(x_1,\dots,x_n,x_{n+1},\dots,x_{n+m_i}) = x_i$. (Далее описание конструкции)
Это значит, что не зная заранее $x_{n+1},\dots,x_{n+m}$, мы не можем отбросить ни одно из значений $x_1,\dots,x_n$, так как каждое из них при определенных условиях может стать ответом.

[TOTAL]

Xaositect в сообщении #322724 писал(а):

так как каждое из них при определенных условиях может стать ответом.

Пусть отброшенное число стало ответом. Чему это помешало?

[Xaositect]

TOTAL в сообщении #323323 писал(а):

Пусть отброшенное число стало ответом. Чему это помешало?

Мы не можем этот ответ выдать на выход - его у нас нет в памяти.

Я могу это с большей строгостью написать (как минимум, нужно формально описать модель вычислений и сформулировать утверждение в этой модели), но для программистского курса, думаю, достаточно того, что я уже написал.

[TOTAL]

Xaositect в сообщении #323324 писал(а):

TOTAL в сообщении #323323 писал(а):

Пусть отброшенное число стало ответом. Чему это помешало?

Мы не можем этот ответ выдать на выход - его у нас нет в памяти.

Мы отбросили число и всё равно правильно нашли медиану. Поэтому мы не доказали, что требуется.

[Xaositect]

TOTAL в сообщении #323327 писал(а):

Мы отбросили число и всё равно правильно нашли медиану. Поэтому мы не доказали, что требуется.

Где мы нашли медиану?

P.S. раз уж топикстартер пропал, мне писать решение? :)

[GrishinUS]

Почему пропал?
Я здесь, благодарю за потраченное на меня время (и параллельно слежу за топиком).
В планах распечатать его и читать на досуге пока не наступит Прозрение.
Как только спорящие придут к общему знаменателю.

[TOTAL]

Xaositect в сообщении #323329 писал(а):

P.S. раз уж топикстартер пропал, мне писать решение? :)

Сначала напишите, как понимаете условие.

[Xaositect]

TOTAL в сообщении #323362 писал(а):

Сначала напишите, как понимаете условие.

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

Более формально: введем некоторый оператор $\mathrm{discard}(x)$, после которого обращение к переменной $x$ считается нелегальным. Тогда: в любом алгоритме, вычисляющем медиану, оператор $\mathrm{discard}$ применяется к элементу коллекции либо после того, как было обращение ко всем элементам коллекции, либо после того как значение этого элемента было присвоено другой переменной, либо после того, как значение этого элемента проверено на равенство с другой переменной и оказалось ей равно (напр. $\mathrm{if} (x[i]=x[j]) \mathrm{then} \{\mathrm{discard}(x[j]);\; q[i]\leftarrow q[i]+q[j];\; q[j] \leftarrow -1;\}$ - после этого мы будем значть, что значение $x[i]$ в коллекции встречается более одного раза ($q[i]$ - счетчик количества вхождений), а к переменной $x[j]$ обращаться нельзя ($q[j] = -1$))

[TOTAL]

Xaositect в сообщении #323384 писал(а):

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

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

Автор топика дал примерно такое же доказательство.

Вас чем не устраивает такое доказательство?

[Xaositect]

TOTAL в сообщении #323385 писал(а):

Вас чем не устраивает такое доказательство?

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

[TOTAL]

Xaositect в сообщении #323390 писал(а):

Если бы мы заранее знали, что реализуется этот случай, то могли бы все элементы выкинуть. Но это не доказывает, что нельзя выкинуть эти элементы в общем случае.

Заранее не знаем, поэтому выкинуть не можем. Это и требовалось доказать.

[Xaositect]

ИМХО, надо написать, что минимальный элемент выкинуть не можем, т.к. если все послеующие меньше и их $n-1$, то он будет медианой и его потребуется подать на выход алгоритма. Второй по величине выкинуть не можем, т.к. ...
Или одним предложением так, как я написал: для любого $i$ существует набор последующих, при котором $x_i$ будет медианой, поэтому выкинуть его не можем.

Я еще раз говорю, что я, возможно, требую здесь излишней строгости, но, по-моему

TOTAL в сообщении #323392 писал(а):

Заранее не знаем, поэтому выкинуть не можем. Это и требовалось доказать.

- это не доказательство. Это условие задачи, переформулироваенное своими словами. По сути Вы вместо доказательства говорите "Очевидно".

-- Пн май 24, 2010 13:39:01 --

TOTAL в сообщении #323385 писал(а):

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

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

[TOTAL]

Xaositect в сообщении #323395 писал(а):

Или одним предложением так, как я написал: для любого $i$ существует набор последующих, при котором $x_i$ будет медианой, поэтому выкинуть его не можем.

Почему не можем?

Xaositect в сообщении #323395 писал(а):

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

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

[Xaositect]

TOTAL в сообщении #323396 писал(а):

Почему не можем?

Потому что он должен идти на выход алгоритма.