OberonCore
https://forum.oberoncore.ru/

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

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

Евгений Темиргалеев писал(а):
руками не пощупаешь и торжественно не вручишь...
Примат чувственного восприятия. H. sapiens, как же.

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

igor писал(а):
vvp писал(а):
Вообще-то книги принадлежат издателю. Издатель вполне может обидиться вплоть до судебного возмещения убытков.
Юридически издателю принадлежат не книги, а определённые права. Право собственности на книгу является отчуждаемым. После купли-продажи право собственности переходит к покупателю.

Не совсем понял, на что может обидеться издатель.


Как на что? Вы же делая электронную копию уменьшаете продажи и лишаете его прибыли. Вот на это и обидится. Право собственности конечно является отчуждаемым, но не автоматически по чьему либо желанию, а по решению суда. А до оного право собственности за издателем. Покупателю переходит право использования его личного экземпляра, в личных целях. Потом это же элементарный здравый смысл. если Издатель не будет получать прибыли существенно превышающей его издержки он просто разорится. А первая же хорошая копия его прибыль может свести к нулю.

Да кстати надо вспомнить еще о авторах.

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

Info21 писал(а):
Евгений Темиргалеев писал(а):
руками не пощупаешь и торжественно не вручишь...
Примат чувственного восприятия. H. sapiens, как же.

Это надо ОБЯЗАТЕЛЬНО учитывать, если имеется желание "повернуть стадо" (участников мэйнстрима :) ) в нужную сторону.

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

vvp писал(а):
igor писал(а):
Не совсем понял, на что может обидеться издатель.
Как на что? Вы же делая электронную копию уменьшаете продажи и лишаете его прибыли.
А, Вы об этом! Щекотливый вопрос. Может я не делал электронную копию, а нашёл её в сети, в свободном доступе. А кто её делал - ищи свищи.

Автор:  Сергей Губанов [ Среда, 27 Январь, 2010 17:02 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

igor писал(а):
Может я не делал электронную копию, а нашёл её в сети, в свободном доступе. А кто её делал - ищи свищи.
А как докажете, что нашли её в интернете в свободном доступе? По действующему в РФ закону ответственность доказывать утверждения возлагается на того кто их выдвигает.

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

igor писал(а):
В таблице 1.1 на стр. 24 столбцы истинности для конъюнкции и дизъюнкции перепутаны местами.

Что интересно, сравнил с изданием для Модулы-2 - там та же самая ошибка.

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

Ну что ж, Вы тест прошли... :lol:

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

На странице 132 приводится примерчик рекурсивного определения натуральных чисел.
Казус, однако, состоит в том, что число 0 не входит в множество натуральных чисел.

С первоисточником не сверял.

Автор:  Geniepro [ Пятница, 23 Апрель, 2010 11:43 ]
Заголовок сообщения:  Re: "Алгоритмы и структуры данных. Новая версия для Оберона"

igor писал(а):
Казус, однако, состоит в том, что число 0 не входит в множество натуральных чисел.
Есть две школы математики, одна из которых (французкая/немецкая, например) включает ноль в множество натуральных чисел, а другая (в частности, русская) -- не включает.
Вопрос терминологии.

http://ru.wikipedia.org/wiki/Натуральное_число
Цитата:
Существуют два подхода к определению натуральных чисел — числа, используемые при:

* перечислении (нумеровании) предметов (первый, второй, третий…) — подход, общепринятый в большинстве стран мира (в том числе и в России);

* обозначении количества предметов (нет предметов, один предмет, два предмета…). Принят в трудах Бурбаки, где натуральные числа определяются как мощности конечных множеств.

Отрицательные и нецелые числа натуральными числами не являются.

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

Валерий Лаптев писал(а):
Наш второй курс седни признался, что книжка сильно помогла делать лабы по структурам данных и алгоритмам. Хотя сдавали их на С++
viewtopic.php?p=46444#p46444

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

(дублирую сюда)
Валерий Лаптев писал(а):
но тоже без примечания переводчика.
Все изменения авторизованы. Поэтому без примечаний переводчика. Тем более их там довольно много, хотя большинство мелкие.

Автор:  Владислав Жаринов [ Четверг, 02 Декабрь, 2010 05:07 ]
Заголовок сообщения:  Доки на Блэкбокс для АиСД-Оберон

В документе Введение в Блэкбокс на с. 14 имеется ссылка на описание возможности включения асмкода в КП-программы - в п. Процедуры в кодах док. Особенности, зависящие от платформы. В указанном документе (в т.ч. в английской версии) такого пункта не нашёл. Это сейчас не поддерживается или просто пункт выпущен? Интересно, в частности в отношении вызова функций DOS-Int - возможен ли аналогично Турбо-Паскалю?

Автор:  Info21 [ Четверг, 02 Декабрь, 2010 05:31 ]
Заголовок сообщения:  Re: Доки на Блэкбокс для АиСД-Оберон

Драконограф писал(а):
В документе Введение в Блэкбокс на с. 14 имеется ссылка на описание возможности включения асмкода в КП-программы - в п. Процедуры в кодах док. Особенности, зависящие от платформы. В указанном документе (в т.ч. в английской версии) такого пункта не нашёл.
Проверил, есть. В первом разделе, Модуль SYSTEM, в конце перед Примеры -- Процедуры в машинных кодах.

Автор:  Евгений Темиргалеев [ Четверг, 02 Декабрь, 2010 09:50 ]
Заголовок сообщения:  Re: Доки на Блэкбокс для АиСД-Оберон

Драконограф писал(а):
Интересно, в частности в отношении вызова функций DOS-Int - возможен ли аналогично Турбо-Паскалю?
Получить такой код Вы можете. Но ББ не собирает ДОС-приложений. И вопрос переходит в "возможен ли вызов функций DOS-Int из Windows приложения" :)

Автор:  Владислав Жаринов [ Пятница, 03 Декабрь, 2010 05:38 ]
Заголовок сообщения:  Re: Доки на Блэкбокс для АиСД-Оберон

Info21 писал(а):
Драконограф писал(а):
В указанном документе (в т.ч. в английской версии) такого пункта не нашёл.
Проверил, есть. В первом разделе, Модуль SYSTEM, в конце перед Примеры -- Процедуры в машинных кодах.

Спасибо.

Автор:  Владислав Жаринов [ Пятница, 03 Декабрь, 2010 05:44 ]
Заголовок сообщения:  Re: Доки на Блэкбокс для АиСД-Оберон

Евгений Темиргалеев писал(а):
Драконограф писал(а):
Интересно, в частности в отношении вызова функций DOS-Int - возможен ли аналогично Турбо-Паскалю?
Получить такой код Вы можете. Но ББ не собирает ДОС-приложений. И вопрос переходит в "возможен ли вызов функций DOS-Int из Windows приложения" :)

Да, Ерёмин (вопрос связан с идеей получить КП-исхтекст для этого примера) в своей книге предупреждает, что не на всех виндах это пройдёт :)

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

Перечитывал намедни....
Глаз задержался на расчете средней глубины случайного дерева... дольше 20 секунд.
Парни, там же нет НИ ОДНОЙ правильной формулы :!: даже асимптотика криво написана.
Написано примерно так (стр.208-209):
Код:
Ai[n] = ((i-1)*A[i-1] + (n-i)*A[n-i])/n       (* это уже неправда => дальнейшее, даже      *)
                                              (* сделанное правильно - тоже неправда       *)

 A[n]  = (Si: 1<=i<=n: (i-1)*A[i-1] + (n-i)*A[n-i] )/n^2
      = 2*(Si: 1<=i<=n: (i-1)*A[i-1] )/n^2
      = 2*(Si: 1<=i <n: i*A[i] )/n^2

(1) A[n]   = 2*(n-1)*A[n-1]/n^2 + 2*(Si: 1<=i<n-1: i*A[i] )/n^2
(2) A[n-1] = 2*(Si: 1<=i<n-1: i*A[i] )/(n-1)^2
(3) 2*(Si: 1<=i<n-1: i*A[i] )/n^2 = A[n-1]*(n-1)^2/n^2

 A[n]  = 2*(n-1)*A[n-1]/n^2 + A[n-1]*(n-1)^2/n^2
      = A[n-1]*(n-1)^2/n^2                    (* а это еще и проблемы с арифметикой :(     *)
     (* при этом, не вооруженным глазом видно, что это рекурентное определение для         *)
     (* УБЫВАЮЩЕЙ последовательности !!! даже и без арифметических ошибок: (n^2-1)/n^2 < 1 *)
     (* и что из начального условия A[1]=0 можно вывести только нулевую последовательность *)

 H[n]  = 1 + 1/2 + 1/3 + ... +1/n              (* ПО ОПРЕДЕЛЕНИЮ *)
 A[n]  = 2*(H[n]*(n+1)/n - 1)                  (* A[1]=2 - никого смущать не должно, видимо *)

асимптотика:
 A[n]  = 2*(ln(n)+g-1) + o(1)


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


 A[n]  = (Si: 1<=i<=n: (i-1)*A[i-1] + (n-i)*A[n-i] )/n^2         + (n-1)/n
      = 2*(Si: 1<=i<=n: (i-1)*A[i-1] )/n^2                      + (n-1)/n
      = 2*(Si: 1<=i <n: i*A[i] )/n^2                            + (n-1)/n

(1) A[n]   = 2*(n-1)*A[n-1]/n^2 + 2*(Si: 1<=i<n-1: i*A[i] )/n^2 + (n-1)/n
(2) A[n-1] = 2*(Si: 1<=i<n-1: i*A[i] )/(n-1)^2                  + (n-2)/(n-1)
(3) 2*(Si: 1<=i<n-1: i*A[i] )/n^2 = (A[n-1] - (n-2)/(n-1))*(n-1)^2/n^2

 A[n]  = 2*(n-1)*A[n-1]/n^2 + (A[n-1] - (n-2)/(n-1))*(n-1)^2/n^2 + (n-1)/n
      = A[n-1]*(n^2-1)/n^2 + 2*(n-1)/n^2

 H[n]  = 1 + 1/2 + 1/3 + ... + 1/n             (* ПО ОПРЕДЕЛЕНИЮ *)

(* НАЧАЛО неприведенного вывода конечной формулы для A[n] из предыдущей рекурентной

 A[n]/2    = (A[n-1]/2)  *(n^2-1)/n^2 + (n-1)/n^2
 A[n]/2+1  = (A[n-1]/2+1)*(n^2-1)/n^2 + (n-1)/n^2 + 1 - (n^2-1)/n^2
          = (A[n-1]/2+1)*(n^2-1)/n^2 + 1/n

замена переменной: B[n]=A[n]/2+1
 B[n]          = B[n-1]*(n^2-1)/n^2   + 1/n
 B[n]*n/(n+1)  = B[n-1]*(n-1)/n       + 1/(n+1)

замена переменной: C[n]=B[n]*n/(n+1)
 C[n]  = C[n-1] + 1/(n+1)

из определения H[n] видим, что:
 H[n+1]-H[n] = 1/(n+1) = C[n]-C[n-1] => C[n] = H[n+1] + const
 
добавляем к этому начальные условия A[1]=0 => B[1]=1 => C[1]=1/2, и выводим:
 C[n]  = H[n+1] - 1 = H[n] + 1/(n+1) - 1 = H[n] - n/(n+1)
 B[n]  = C[n]*(n+1)/n = (H[n] - n/(n+1))*(n+1)/n = H[n]*(n+1)/n - 1
 A[n]  = 2*(B[n] - 1) =>

КОНЕЦ вывода конечной формулы для A[n] *)

 A[n]  = 2*(H[n]*(n+1)/n - 2)

асимптотика:
 A[n]  = 2*(ln(n)+g-2) + o(1)


Это все в предположении, что дерево из одного элемента имеет глубину 0. Это существенно использовано в самой первой формуле, а не только при использовании начального значения A[1]=0.
Хотя далее в книге (деревья Фиббоначи) - это уже 1.
Вывод для такого начального условия может даже и проще будет... на несколько буковок.
Вот, если кому интересно:
Код:
Ai[n] = ((i-1)*A[i-1] + (n-i)*A[n-i])/n                         + 1


 A[n]  = (Si: 1<=i<=n: (i-1)*A[i-1] + (n-i)*A[n-i] )/n^2         + 1
      = 2*(Si: 1<=i<=n: (i-1)*A[i-1] )/n^2                      + 1
      = 2*(Si: 1<=i <n: i*A[i] )/n^2                            + 1

(1) A[n]   = 2*(n-1)*A[n-1]/n^2 + 2*(Si: 1<=i<n-1: i*A[i] )/n^2 + 1
(2) A[n-1] = 2*(Si: 1<=i<n-1: i*A[i] )/(n-1)^2                  + 1
(3) 2*(Si: 1<=i<n-1: i*A[i] )/n^2 = (A[n-1] - 1)*(n-1)^2/n^2

 A[n]  = 2*(n-1)*A[n-1]/n^2 + (A[n-1] - 1)*(n-1)^2/n^2           + 1
      = A[n-1]*(n^2-1)/n^2 + (2*n-1)/n^2

 H[n]  = 1 + 1/2 + 1/3 + ... + 1/n             (* ПО ОПРЕДЕЛЕНИЮ *)

(* НАЧАЛО неприведенного вывода конечной формулы для A[n] из предыдущей рекурентной

 A[n]+1     = (A[n-1]+1)  *(n^2-1)/n^2 + (2*n-1)/n^2 + 1 - (n^2-1)/n^2
           = (A[n-1]+1)  *(n^2-1)/n^2 + 2/n
(A[n]+1)/2 = (A[n-1]+1)/2*(n^2-1)/n^2 + 1/n

замена переменной: B[n]=(A[n]+1)/2
 B[n]          = B[n-1]*(n^2-1)/n^2 + 1/n
 B[n]*n/(n+1)  = B[n-1]*(n-1)/n     + 1/(n+1)

замена переменной: C[n]=B[n]*n/(n+1)
 C[n]  = C[n-1] + 1/(n+1)

из определения H[n] видим, что:
 H[n+1]-H[n] = 1/(n+1) = C[n]-C[n-1] => C[n] = H[n+1] + const
 
добавляем к этому начальные условия A[1]=1 => B[1]=1 => C[1]=1/2, и выводим:
 C[n]  = H[n+1] - 1 = H[n] + 1/(n+1) - 1 = H[n] - n/(n+1)
 B[n]  = C[n]*(n+1)/n = (H[n] - n/(n+1))*(n+1)/n = H[n]*(n+1)/n - 1
 A[n]  = 2*B[n] - 1 =>

КОНЕЦ вывода конечной формулы для A[n] *)

 A[n]  = 2*H[n]*(n+1)/n - 3

асимптотика:
 A[n]  = 2*(ln(n)+g)-3 + o(1)

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

Galkov писал(а):
Перечитывал намедни....
Глаз задержался на расчете средней глубины случайного дерева... дольше 20 секунд.
Парни, там же нет НИ ОДНОЙ правильной формулы :!: даже асимптотика криво написана.
Да ладно панику разводить.

"Криво" -- подумаешь, в константе ошибка.

На то он и учебник, чтобы поупражняться.
Вы вот поупражнялись -- и надо порадоваться, что СМОГЛИ.

Впрочем, понимаю: паника -- это способ такой за себя порадоваться.
Хорошо воспитанный человек не скажет, вот, мол, какой я умный :)

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

Info21 писал(а):
"Криво" -- подумаешь, в константе ошибка.

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

Если бы речь шла только о константе - не поставил бы себе в труд поститься на форуме. Там такого несть числа.
Переворачивайте страницу и читайте
Цитата:
Ясно, что оптимум может быть достигнут для идеально сбалансированного дерева с n = 2k - 1
Не, ну подумаешь - буковка вниз съехала....
Вообще-то, мое мнение, что для УЧЕБНИКОВ и это недопустимо. Очень трудно изучать совершенно новый предмет, если "здесь читать, здесь не читать, а здесь рыбу заворачивали".
Поэтому у меня убедительная просьба, оставить при себе высокоумные сентенции из серии "На то он и учебник...". Ибо знать Вам этого объективно не дано - это не есть совершенно новый предмет для Вас. А проявить уважение к учащимся самостоятельно - не прошу ввиду бессмысленности.

Разница в том, что понятно как такие ошибки возникают. Они технические, и техническими же средствами могут быть исправлены. И только после этого книга станет Учебником. Да, эти две книги - очень хорошие кандидаты, чтобы стать Учебниками, каковыми в настоящий момент еще не являются. ИМХО.

И такого характера ошибки никак не характеризуют школу Вирта.
А вот в связи с тем, что книги (из рубрики Классика программирования) написаны на основании курса лекций, читанных в Церне, вопрос у меня возникает: какие на самом деле формулы приводил (в смысле - писал на доске) Вирт на лекциях :?:

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

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

При чем тут ЦЕРН??

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

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

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

Galkov писал(а):
Код:
Ai[n] = ((i-1)*A[i-1] + (n-i)*A[n-i])/n       (* это уже неправда => дальнейшее, даже      *)
А в чём тут неправда?

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