Доказать, что нельзя пройти дерево за константную память (решена)
Есть бинарное деревопопробую подкорректировать задачу, ибо она не верная:
доказать отсутствие конечного автомата, обходящего любое бинарное дерево (с указателями только вниз, бла-бла)
так правильно?
зы: "что-то делать с деревом" меня смущает это дополнение
какие ограничения на что-то сделать? можно сложить все узлы в линейный списокнепонятно, что нужно сделать. под "посетить вершину" подразумевается скажем напечатать ее ключ? или подразумевается вообще обращение к вершине?
если нужно по одному разу напечатать все ключи в дереве, то исходное утверждение неверно, ведь можно реализовать поиск предка за O(число вершин). итого будет квадрат.
а за одно обращение к каждой вершине и за константную память это вроде нельзя сделать даже имея указателей на предка.
верно ли что общее время работы ограничено O(число вершин) ?
если нужно по одному разу напечатать все ключи в дереве, то исходное утверждение неверно, ведь можно реализовать поиск предка за O(число вершин). итого будет квадрат.
а за одно обращение к каждой вершине и за константную память это вроде нельзя сделать даже имея указателей на предка.
верно ли что общее время работы ограничено O(число вершин) ?
если нужно по одному разу напечатать все ключи в дереве, то исходное утверждение неверно, ведь можно реализовать поиск предка за O(число вершин). итого будет квадрат.Почему за O(N если можно и за O(logN)?
интересно, как вы найдете предка за константную память? это та же самая задача обхода дерева 
ну да, надо алгоритм, работающий с произвольным деревом
зы: "что-то делать с деревом" меня смущает это дополнениеможно, но надо потом обратно вернуть будет, чтобы после работы снова было старое дерево.
пускай даже снимем ограничение "по одному разу": пускай надо только найти некоторый ключ в дереве, все.
Пусть у нас есть ограниченное константой количество памяти, а именно X (двоичных) бит. Тогда у данного алгоритма не может быть больше 2^X состояний. Берем дерево с количеством вершин 1+2^X - алгоритм не может его обойти, так как он зациклится или закончится не более чем через 2^X шагов, а вершин на одну больше.
При углублении в непоследнюю ветвь нам нужно обязательно помнить оставшихся соседей, чтобы продолжить обход. Т.к. если мы их не запоминаем, то продолжить обход никак не можем после того как обработаем эту вершину.
фишка в том, что тут опущено (вроде бы очевидное) слово дополнительная память. Т.е. само дерево уже есть в памяти и ее можно изменять (только потом надо вернуть все на места следовательно состояний может быть больше. Это надо как-то обойти.
это понятно, но я хочу именно математически точное доказательство чтобы вот прямо сразу все ясно и никаких вопросов.
чтобы вот прямо сразу все ясно и никаких вопросов.Берем дерево с количеством вершин 1+2^X - алгоритм не может его обойти, так как он зациклится или закончится не более чем через 2^X шагов, а вершин на одну больше.неверный вывод
кол-во вершин которые надо обойти и кол-во состояний алгоритма - абсолютно несвязанные вещи
возьмем однонаправленный список: для него есть простой алгоритм (2 состояния где-то) обхода и он не зависит от кол-ва элементов в списке
это понятно, но я хочу именно математически точное доказательствоНу это вроде можно формализовать. Что для работы алгоритма нужно запоминать кое-что. По типу как с функциями, которые нельзя представить в виде хвостовой рекурсии.
еще проще: у него написано "берем дерево". Ну я вот буду всегда брать дерево, где только влево есть поддерево, оно-то всяко обходится.
ну да, запоминание чего-то — это количество состояний. Надо куда-то сюда, наверное, да.
Т.е. само дерево уже есть в памяти и ее можно изменять (только потом надо вернуть все на места следовательно состояний может быть больше.если можно в процессе обхода менять дерево, то у нас как бы есть доп память, пропорционально кол-ву узлов и тут я уже не уверен, что алгоритма не существует (пусть даже ему придется восстановить все дерево после обхода)
в общем, дополнение плохо сформулировано, поэтому на строгое мат. док-во я бы не рассчитывал на твоем месте)
если можно в процессе обхода менять дерево, то у нас как бы есть доп память, пропорционально кол-ву узлов и тут я уже не уверен, что алгоритма не существует (пусть даже ему придется восстановить все дерево после обхода)да, в этом и смысл, но она не "доп", это inplace же. Главное вернуть все обратно. В чем проблема с математикой — не знаю, анализируеют же quicksort, например.
я уже не уверен, что алгоритма не существуетну вот первое, что нашлось в яндексе: http://amazing-new-gate.blogspot.com/2010/06/blog-post_30.ht...
погугли еще
немного обсуждения такой задачи:
http://www.codeforces.com/blog/entry/4308?locale=ru
http://www.codeforces.com/blog/entry/4308?locale=ru
блин, точняк, теперь нашел. А ведь искал перед этим.
вот тут норм из кнута
http://stackoverflow.com/questions/791052/iterating-over-a-b...
http://stackoverflow.com/questions/791052/iterating-over-a-b...
Эта задача, имхо, страдает от недостатка формализма.
С одной стороны, если считать размер указателя произвольным (а это необходимо для включения произвольного числа узлов в дерево то для хранения произвольного указателя уже не хватит О(1) памяти.
Если он фиксирован и равен N бит, то можно обойти дерево за константную память: N бит на текущий указатель curr. N бит на счётчик глубины (очевидно, она ограничена сверху N) deep. N бит на счётчик развилок branch. Бит этого счётчика указывает, должны ли мы на очередной развилке взять левого сына или правого. log N бит на положение в счётчике развилок branchPos, N бит на счётчик текущей глубины currDeep. Опционально - несколько булевых флагов для сокращения времени обхода.
Обходим по ярусам (одинаковая глубина).
С одной стороны, если считать размер указателя произвольным (а это необходимо для включения произвольного числа узлов в дерево то для хранения произвольного указателя уже не хватит О(1) памяти.
Если он фиксирован и равен N бит, то можно обойти дерево за константную память: N бит на текущий указатель curr. N бит на счётчик глубины (очевидно, она ограничена сверху N) deep. N бит на счётчик развилок branch. Бит этого счётчика указывает, должны ли мы на очередной развилке взять левого сына или правого. log N бит на положение в счётчике развилок branchPos, N бит на счётчик текущей глубины currDeep. Опционально - несколько булевых флагов для сокращения времени обхода.
Обходим по ярусам (одинаковая глубина).
deep = 0
Пока deep не равна N:
branch = 0
Пока branch не равны N:
currDeep = branchPos = 0
curr = корень
пока есть хоть одно поддерево и currDeep < deep:
curr = если деревьев два - выбираем поддерево в зависимости от branch[branchPos++]
иначе - выбираем единственное
currDeep ++
если глубина наша - печатаем
branch++
deep++
неверный выводТы забыл про одно упрощение, которое обычно принимается: что размер числа есть константа памяти.
кол-во вершин которые надо обойти и кол-во состояний алгоритма - абсолютно несвязанные вещи
возьмем однонаправленный список: для него есть простой алгоритм (2 состояний где-то) обхода и он не зависит от кол-ва элементов в списке
Для обхода списка нужно O(logN) дополнительной памяти формально, что дает те самые N = 2^{log N} состояний.
Можно еще на примере массива посмотреть:
for(i = 0; i < n; i++) do_something(a[i]);
"Константа" дополнительной памяти на хранение i, но алгоритм не работает для размера массива больше чем 2^{sizeof(i) * 8}.
Этого нельзя доказать, потому что это можно сделать.
// немного опоздал, но энивей, этого решения еще никто не приводил
// немного опоздал, но энивей, этого решения еще никто не приводил
да, кстати, тоже об этом думал, но я просто собирался в одном числе бинарном кодировать путь к вершине в дереве. Не додумался до этой идеи, что указатели сами по себе ограничены. Да, это дыра в условии.
Ты забыл про одно упрощение, которое обычно принимается: что размер числа есть константа памяти.какие еще числа при обходе списка? мне нужно объяснять, что такое односвязный список и что значит его обойти, используя указатель Next в каждом узле?
А указатель current тебе не нужен при обходе списка, да?
N бит на счётчик развилок branch. Бит этого счётчика указывает, должны ли мы на очередной развилке взять левого сына или правого.Вот вы меня плюсуете, и совершенно зря, ибо в это время я посыпаю голову пеплом.
Очевидно, число развилок в худшем случае равно 2^(N-1 соответственно для хранения такого числа надо 2^(N-1)бит памяти, а не N, что уже не выглядит константой в неформальном понимании этого термина.
я не читал алгоритм, я плюсанул за правильное замечание к формализации. Все равно привели уже несколько устраивающих меня решений. Теперь надо думать над исходной задачей
> N бит на счётчик развилок branch
2^N же. Про структуру же ничего не сказано.
2^N же. Про структуру же ничего не сказано.
хранить нужно current, а под next память выделять не нужно.
более того, в его посте не было указаний на то, что нужно хранить указатель на next.
а ты похоже хочешь сказать, что размер указателя на current может изменяться в процессе алгоритма?
более того, в его посте не было указаний на то, что нужно хранить указатель на next.
а ты похоже хочешь сказать, что размер указателя на current может изменяться в процессе алгоритма?
Надо взять константную память , равную сумме всех винчестеров вселенной.
Я хочу сказать, что размер указателя связан с максимальным возможным размером списка. Ну не может у тебя быть списка из 100000 элементов при 16 битных указателях.
Т.е. его контрпример о списком контрпримером не является.
Т.е. его контрпример о списком контрпримером не является.
тогда приведи пример алгоритма, работающего с константной памятью. боюсь что при твоем способе мышления их в принципе не существует.
Это просто, достаточно ограничить размер списка константой. Только тогда и сложность в константу выродится. Причем любого алгоритма. А чтобы этого не происходило как раз и вводят это допущение, что числаи указатели имеют размер О(1 но волшебным образом могут хранить любые нужные нам значения. Таким образом приводят к общему знаменателю теорию (машина Тьюринга, бесконечная лента, переменный размер чисел) и практику (процессор, фиксированные размеры чисел и памяти).
Я согласен, что в моем доказательстве есть проблема, так как оно использует константность памяти в строгом смысле, которая не следует из условия. Но поскольку оно все равно не подходит, не вижу смысла его дальше обсуждать.
Я согласен, что в моем доказательстве есть проблема, так как оно использует константность памяти в строгом смысле, которая не следует из условия. Но поскольку оно все равно не подходит, не вижу смысла его дальше обсуждать.
ну а смысл тогда писать то, что и так всегда подразумевается?
Потому что в первом своем посте я отошел от этого допущения и это привело к непониманию.
Оставить комментарий
Serab
Что-то туплю, как это формально доказать?Есть бинарное дерево, в нем только указатели вниз (это важно). Как доказать, что нельзя посетить все вершины по одному разу с использованием только ограниченного константой количества памяти? Теоретически с деревом можно делать что-то, но в итоге надо вернуть на место.