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: "Алгоритмы и структуры данных. Новая версия для Оберона" |
А в чем проблема, собственоо Вам привели ошибку, и в полном соответствии с Вашими же пожеланиями - в исправленном виде(ах) Но Вам этого показалось мало: Вас заинтересовали причины "паники", и Вы даже высказали смелое предположение о ее причинах. Обращаю внимание: ВАС заинтересовали, и ВЫ высказали И Вам ответили, что (если уж вообще отбросить всякую дипломатию) причиной "паники" является принципиаальное отличие между просто опечатками, и научной графоманией. И ВСЕ. Вас это утомляет ??? Попробуйте относиться с уважением к коллегам, может получиться менее утомительно... Исключите из свего лексикона "паники", "истерики", "клеветы" - и Вас перестанут держать за сноба. И, боже мой - могла БЫ получиться конструктивная работа. 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 получится, если с нуля начинать Рекурентные соотношения-то - однородные, т.е., с нулевым свободным членом!!! Собственно с этого-то все и начинается (с чего - я специально попытался отметить в комментарии), именно за это глаз цепляется прежде всего, а вовсе не за "плюс одыны". Эти детали уже потом возникают, когда понимешь, что надо именно в консерватории что-то подправить... Тесты на дуракоустойчивость проходятся легко в уме, но да - секунд 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, с центральным узлом и двумя ребрами В общем, что лучше и правильнее - пусть решают психологи и педагоги |
Автор: | 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/ |