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 - там та же самая ошибка. Об этой ашипке я тут несколько лет назад упоминал. Тогда тут ответили, что, возможно, это было сделано намеренно, для проверки бдительности читателя. Ну что ж, Вы тест прошли... |
Автор: | 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/ |