OberonCore
https://forum.oberoncore.ru/

"Алгоритмы и структуры данных. Новая версия для Оберона"
https://forum.oberoncore.ru/viewtopic.php?f=80&t=1970
Страница 5 из 8

Автор:  Galkov [ Воскресенье, 05 Декабрь, 2010 01:40 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Поддеревья дают вклад в общую среднюю длину пути на 1 больше, чем их собственная средняя длина, когда они "голые".

Автор:  Galkov [ Воскресенье, 05 Декабрь, 2010 02:00 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Info21 писал(а):
При чем тут ЦЕРН??

Нашли ошибку -- сообщите, лучше в исправленном варианте.

А философствование только мешает.
Тем более очевидно, что Вы книг не делали ни разу. Иначе знали бы, что буквы не только съезжают, но и вообще как тараканы бегают по всей странице.
Ну так и явите понимание того, что исправление ошибки отличается от исправления авторского текста тем, что первое как раз восстанавливает авторский текст.
А второе явлется нарушением авторских прав по большому счету-то.

Повторю вопрос: приведенное мной есть исправление ошибки, или исправление авторского текста :?:

Автор:  Galkov [ Воскресенье, 05 Декабрь, 2010 02:33 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Info21 писал(а):
При чем тут ЦЕРН??
При том, что что ни у одного издателя, редактора, корректора, переводчика, и т.п. не хватит фантазии внести таковые искажения в авторский математический вывод. А кто тогда? Сами догадаетесь, или тоже разжевывать надо?

Info21 писал(а):
Иначе знали бы, что буквы не только съезжают, но и вообще как тараканы бегают по всей странице.
Знаю, даже знаю в каком количестве, и возможно, что уже лучше Вас.
В таком количестве, что говорить о них по одиночке - совершенно бесперспективное занятие. Надо брать электронный варинт и просто править. Ну это уже - если Вас интересует результат
Просто такое не называется Учебником. Примите пожалуйста это к сведению без обсуждений (философий - по Вашему)

Автор:  Peter Almazov [ Воскресенье, 05 Декабрь, 2010 09:44 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Galkov писал(а):
Поддеревья дают вклад в общую среднюю длину пути на 1 больше, чем их собственная средняя длина, когда они "голые".
Просьба все-таки пояснить на примере. Пусть деревья строятся из ключей 1..2, т.е. из последовательностей {1,2},{2,1}. Какова будет средняя длина дерева?

Galkov писал(а):
Повторю вопрос: приведенное мной есть исправление ошибки, или исправление авторского текста :?:
Второй раз не понял. Что мешает посмотреть здесь http://www.oberoncore.ru/library/start на первой строчке?

Автор:  Info21 [ Воскресенье, 05 Декабрь, 2010 14:19 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Боже мой, как утомляют эти истерики по любому поводу...

Автор:  Galkov [ Понедельник, 06 Декабрь, 2010 00:19 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

А в чем проблема, собственоо :wink:
Вам привели ошибку, и в полном соответствии с Вашими же пожеланиями - в исправленном виде(ах)
Но Вам этого показалось мало: Вас заинтересовали причины "паники", и Вы даже высказали смелое предположение о ее причинах.
Обращаю внимание: ВАС заинтересовали, и ВЫ высказали

И Вам ответили, что (если уж вообще отбросить всякую дипломатию) причиной "паники" является принципиаальное отличие между просто опечатками, и научной графоманией.

И ВСЕ.
Вас это утомляет ??? Попробуйте относиться с уважением к коллегам, может получиться менее утомительно...
Исключите из свего лексикона "паники", "истерики", "клеветы" - и Вас перестанут держать за сноба.
И, боже мой - могла БЫ получиться конструктивная работа.

DIXI

Автор:  Galkov [ Понедельник, 06 Декабрь, 2010 00:21 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Peter Almazov писал(а):
Второй раз не понял. Что мешает посмотреть здесь
Не мешает ничего. Просто не помогает ни на копейку
Ну посмотрел, и чего ???
Точно с таким же успехом посмотрел таблицу значений истинности логических операторов - ну не могу я поверить, что студентам-швейцарцам на лекциях давали именно эту таблицу.
Не укладывается у меня в голове, чтобы мэтр Вирт подошел к доске и своими руками написал мелом на доске такой бред. Правду писал, скорее всего...

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


Peter Almazov писал(а):
Просьба все-таки пояснить на примере. Пусть деревья строятся из ключей 1..2, т.е. из последовательностей {1,2},{2,1}. Какова будет средняя длина дерева?
Хм..
На дереве из двух элементов объяснять крайне сложно :)
Давайте из трех... А для себя в памяти зафиксируем, что средняя глубина дерева из одного элемента =0, а из двух - =1/2. Потому-что для двух - равновероятны случаи попадания в корень (глубина=0), и в боковой уэел (глубина=1), что и дает 1/2-ю в среднем.

Ну смотрим... Дерёвы бывают разные: корневым узлом может быть узел 1, 2, или 3.
Рассмотрим для примера случай для корня =2. У этого корня могут быть левое поддерево их одного элемента (в общем случае из (i-1)-го элемента), и правое поддерево тоже из одного элемента (в общем случае из (n-i) элементов). А у нас в памяти зафиксировано, что средняя глубина деревьев из одного элемента =0. Но если мы кидаем на поиск цифрьки, уходящие в эти поддеревья, то длина пути будет вовсе не ноль (что соответствует формуле из AD), а единице - у нас же есть реальное ребро от узла 2 к узлу 1 (ну или 3)
В результате: кидаем 1 - глубина 1+0, кидаем 2 - глубина 0, кидаем 3 - глубина 1+0, средняя, соответственно A2[3]= 2/3
Далее рассмотрим случай для корня =1. У нас только одно правое поддерево из 2-х элементов (помним, что для этого поддерева - средняя глубина =1/2)
В этом случае: кидаем 1 - глубина 0, кидаем 1 - глубина 1+1/2, кидаем 3 - глубина 1+1/2, средняя, соответственно A1[3]=(0+3/2+3/2)/3=1
Для случая корня =3 - все симметрично предыдущему случаю с теми же цифрами A3[3]=A1[3]=1
Если усредним по этим трем дерёвам, то получим A[3]=(1 + 2/3 + 1)/3=8/9

Ну вот, как-то так... В общем же случае будет: Ai[n] = ((i-1)*(A[i-1]+1) + (n-i)*(A[n-i])+1)/n, где "плюс одыны" соответствуют ребрам, выходящим из корня на рис.4.29

Ну и наконец, возводя аккуратность в религию, сверяем конечную формулу с нашими цифирьками: A[2]=2*(H(2)*(2+1)/2-2) = 1/2, и A[3]=2*(H(3)*(3+1)/3-2) = 8/9.
И испытываем от этого чувство глубокого удовлетворения.

Автор:  Peter Almazov [ Понедельник, 06 Декабрь, 2010 09:42 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Спасибо за подробное объяснение.
Для большей убедительности его можно было бы начать с предложения посчитать среднюю длину дерева при n=2 по формуле, приведенной в книге (Ai[n] = ((i-1)*A[i-1] + (n-i)*A[n-i])/n), и убедиться, что получается неправильный ответ 0.

Но тут есть одна вещь, которая меня смущает. Во всех вариантах рассуждения начинаются с того, что средняя длина дерева из одного элемента равна 0. А потом в формулах используется средняя длина дерева из 0 элементов! И предполагается, что она = 0.
Неаккуратно это.

Автор:  Info21 [ Понедельник, 06 Декабрь, 2010 10:22 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Galkov писал(а):
Сами догадаетесь, или тоже разжевывать надо?
Спасибо, я уже догадался, когда сказал про "истерики".

Автор:  Galkov [ Понедельник, 06 Декабрь, 2010 12:01 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Peter Almazov писал(а):
... и убедиться, что получается неправильный ответ 0
А она для любого 0 получится, если с нуля начинать :lol:
Рекурентные соотношения-то - однородные, т.е., с нулевым свободным членом!!!
Собственно с этого-то все и начинается (с чего - я специально попытался отметить в комментарии), именно за это глаз цепляется прежде всего, а вовсе не за "плюс одыны". Эти детали уже потом возникают, когда понимешь, что надо именно в консерватории что-то подправить...
Тесты на дуракоустойчивость проходятся легко в уме, но да - секунд 20 необходимо для реагирования. Возраст уже не тот... хотя в той стае, где я был вскормлен, в физиков это вбивали до уровня рефлексов: ну там размерность, асимптотики, краевые случаи, и т.п..

Peter Almazov писал(а):
Во всех вариантах рассуждения начинаются с того, что средняя длина дерева из одного элемента равна 0. А потом в формулах используется средняя длина дерева из 0 элементов!
Есть такое. НО таковая длина обязательно идет с НУЛЕВЫМ коэффициентом. Типа - пофиг чему равна высота дерева для 0 элементов.
Возможно, что "академичней" было бы просто не писать эти члены в суммах... Но так зато вид формулок регулярнее.

Психологически (без разницы в мате.строгости), тогда вывод для начальных условий A[1]=1 смотрелся бы приятней, наверное:
Ai[n] = ((i-1)*(A[i-1]+1) +1 + (n-i)*(A[n-i])+1)/n
Типа можно считать, что A[0]=0, и испытывать моральное спокойствие. Хотя это конкретное значение - никак не влияет на результат. Да и в окончательную формулу подставить n=0 - дулю с маком. Что и понятно - ну никак не вырисовывается рекурентный переход от n=0, к n=1, с центральным узлом и двумя ребрами :D

В общем, что лучше и правильнее - пусть решают психологи и педагоги :)

Автор:  Info21 [ Понедельник, 13 Декабрь, 2010 13:50 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

АиСД, как и Потопахин, в Библио-Глобусе, похоже, проданы (этот один магазин дает четверть продаж всей Москвы).

Поздравляю.

Автор:  Сергей Прохоренко [ Понедельник, 13 Декабрь, 2010 23:52 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Info21 писал(а):
АиСД, как и Потопахин, в Библио-Глобусе, похоже, проданы (этот один магазин дает четверть продаж всей Москвы).

Поздравляю.


В Доме книги на Ладожской АиСД еще есть, как и "Компиляторы..." Вирта. Рядом с Кауфманом - если кто-то еще не купил. Правда, Кауфман очень дорогой.

Автор:  Info21 [ Четверг, 16 Декабрь, 2010 00:03 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Только что увидел отзыв Валерия Викторовича на Озоне. Спасибо!

Автор:  Info21 [ Суббота, 18 Декабрь, 2010 07:19 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

В Библио-Глобусе 1 экз. таки выставили.

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

В общем, тираж распродан, гнутца шведы.

Автор:  Валерий Лаптев [ Суббота, 18 Декабрь, 2010 10:19 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Надо допечатать. У нас очередной 2 курс :)

Автор:  Alexey Veselovsky [ Суббота, 18 Декабрь, 2010 11:45 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

А вот "Построение компиляторов" ещё есть.

Автор:  Info21 [ Суббота, 18 Декабрь, 2010 13:45 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Alexey Veselovsky писал(а):
А вот "Построение компиляторов" ещё есть.
Это все-таки узкоспециальная тема.

----
А в Библио-Глобусе последний экземпляр до вечера не дожил :)

Автор:  vvp [ Суббота, 25 Декабрь, 2010 05:21 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Info21 писал(а):
Alexey Veselovsky писал(а):
А вот "Построение компиляторов" ещё есть.
Это все-таки узкоспециальная тема.

----
А в Библио-Глобусе последний экземпляр до вечера не дожил :)


А вообще, как будет допечатка? Виртовская книжка красная, да и синяя в моем курсе имеет место

Автор:  Info21 [ Суббота, 25 Декабрь, 2010 10:59 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

vvp писал(а):
как будет допечатка?
Ждем ответа издателя.

Автор:  Info21 [ Среда, 16 Февраль, 2011 14:53 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

Если у кого-то есть замечания/поправки, следует явно и точно указать, какое нужно сделать исправление, без истерик и переходов на личности.

Страница 5 из 8 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/