randomly built binary search tree

Переклад книжки Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein "Introduction to Algorithms". Обговорення, термінологія.
Відповісти
ReAl
Повідомлень: 55
З нами з: П'ят жовтня 27, 2017 11:58 pm
Контактна інформація:

randomly built binary search tree

Повідомлення ReAl » Суб березня 17, 2018 3:21 pm

Гарно лягає в текст у різних варіантах використання «увипадковлене двійкове дерево пошуку», але, на відміну від «увипадковленого алгоритму» саме дерево не несе жодної «випадковості», це при побудові дерева бралися випадкові послідовності ключів (при аналізі розглядалися як рівноймовірні всі n! перестановок множини із n ключів).

«випадкове дерево пошуку» зовсім не підходить
• по-перше, несе забагато відтіноку «випадково вибраного з усіх можливих дерев», а є навіть вправа «Покажiть, що поняття випадково вибраного двiйкового дерева пошуку з n ключiв, де кожне таке дерево має однакову iмовiрнiсть бути вибраним, вiдрiзняється вiд …» оцього «randomly built»
• по друге, «random binary search tree» також є в тексті

«двійкове дерево пошуку, побудоване випадковим чином» погано лягає в текст. Можна паралельно використовувати «випадково побудоване двійкове дерево пошуку», хоча в ньому є трохи від «будувати не збиралися, але якось випадково вийшло»

Що порадите?

Yola
Повідомлень: 134
З нами з: Чет квітня 28, 2011 9:25 am

Re: randomly built binary search tree

Повідомлення Yola » Нед березня 18, 2018 10:33 am

«довільно побудоване двійкове дерево пошуку»?

Andriy
Адміністратор сайту
Повідомлень: 3038
З нами з: Сер травня 27, 2009 8:23 pm

Re: randomly built binary search tree

Повідомлення Andriy » Вів березня 20, 2018 3:52 am

"довільно побудоване" мені подобається

ReAl
Повідомлень: 55
З нами з: П'ят жовтня 27, 2017 11:58 pm
Контактна інформація:

Re: randomly built binary search tree

Повідомлення ReAl » Сер березня 21, 2018 8:30 am

Все ж таки «довільний» то не «випадковий» :-(
Хоч іноді зі сторони так і видаватиметься

Yola
Повідомлень: 134
З нами з: Чет квітня 28, 2011 9:25 am

Re: randomly built binary search tree

Повідомлення Yola » Сер березня 21, 2018 9:20 am

Ось тут random слово довільний зустрічається 7 разів.

Хіба треба, щоб довільний повністю збігався в значенні з випадковий? Тут достатньо, щоб він саме в цьому контексті підходив. Можна вважати, що Хтось як захотів так і побудував. І для нас таке дерево випадкове, якщо звісно ми не знаємо чогось про звички Хтося.

З іншого боку, random access можна перекласти як довільний доступ, бо користувач має волю вибирати як йому заманеться, а тут інше.

ReAl
Повідомлень: 55
З нами з: П'ят жовтня 27, 2017 11:58 pm
Контактна інформація:

Re: randomly built binary search tree

Повідомлення ReAl » Сер березня 21, 2018 9:40 pm

Там по тексту описано, що саме мають на увазі — проводиться імовірнісний аналіз характеристик дерев, які будувалися випадковим вибором послідовності ключів з усіх можливих перестановок заданої множини ключів.

Відповісти

Повернутись до “Переклад "Introduction to Algorithms"”