1 Востаннє редагувалося Patlatus (26.09.2018 16:57:55)

Тема: Як краще перекласти фразу Maintain candidate subsequences by linking t

Привіт всім. Перекладаю книжку вступ до алгоритмів Кормена і компанії.
Застряг на перекладі фрази "Maintain candidate subsequences by linking them through the input sequence."
Вчора декілька годин думав як це перекласти.
Не думаю, що варто це перекладати як "Підтримайте підпослідовності кандидати поєднуючи їх через вхідну послідовність".
Головний редактор каже, що москалі в своєму перекладі пропустили цю фразу і пропонує також її видалити.
Хотів ще з кимось порадитись.

Подякували: leofun01, Yola2

2

Re: Як краще перекласти фразу Maintain candidate subsequences by linking t

А можна трохи контексту?

3

Re: Як краще перекласти фразу Maintain candidate subsequences by linking t

\exer{1} Give an $O(n \lg n)$-time алгоритм to find the longest
monotonically increasing subsequence of a sequence of $n$ numbers.
(\hint Observe that the last element of a candidate subsequence of
length $i$ is at least as large as the last element of a candidate
subsequence of length $i-1$.  Maintain candidate subsequences by
linking them through the input sequence.)


\exer{1} Напишіть алгоритм з часом виконання $O(n \lg n)$ для знаходження найдовшої
монотонно зростаючої підпослідовності послідовності з $n$ чисел.
(\hint Зауважте, що останній елемент підпослідовності-кандидата
довжини $i$ принаймні такий же, як і останній елемент
підпослідовності-кандидата довжини $i-1$.  ???не можу це перекласти??? (Maintain candidate subsequences by) Підтримайте підпослідовності кандидати
поєднуючи їх через вхідну послідовність (linking them through the input sequence).)

4

Re: Як краще перекласти фразу Maintain candidate subsequences by linking t

Усе ж таки коректніше  не "час виконання", а "складність".
І не розумію, звідки там n log(n) - там же просто перебираємо елементи, якщо знайшли монотонний фрагмент - запам'ятовуємо початок, знайшли кінець - порівнюємо довжину із поточним рекордсменом і, якщо більший, замінюємо. Все за один прохід, чистий O(n). І про останній елемент - до чого це?
(10,11,12,13),(4,5,6,7,8) - перша підпослідовність довжиною 4, друга довжиною 5, але останній елемент другої менший.
Я не розумію, про який алгоритм мова, тому мені важко зрозуміти, що мається на увазі.

5

Re: Як краще перекласти фразу Maintain candidate subsequences by linking t

задача трохи не про те

6

Re: Як краще перекласти фразу Maintain candidate subsequences by linking t

Так і я про те - я не розумію контексту, а без цього мені важко перекласти.

7

Re: Як краще перекласти фразу Maintain candidate subsequences by linking t

Patlatus написав:

Привіт всім. Перекладаю книжку вступ до алгоритмів Кормена і компанії.
Застряг на перекладі фрази "Maintain candidate subsequences by linking them through the input sequence."
Вчора декілька годин думав як це перекласти.
Не думаю, що варто це перекладати як "Підтримайте підпослідовності кандидати поєднуючи їх через вхідну послідовність".

Я б у цьому контексті переклав maintain як «зберігайте». Щодо іншого, то треба подумати.

Patlatus написав:

Головний редактор каже, що москалі в своєму перекладі пропустили цю фразу

Там де пропущено, де спотворено (причому так, що я не вірю, що той перекладач-наукред міг так помилитися, швидше за все перекладали за копійки не згадані у вихідних книжки «раби»-студенти кібфакультету КНУ, а він просто недовичитав).

Patlatus написав:

і пропонує також її видалити. Хотів ще з кимось порадитись.

Та ні, треба подумати. Це все ж таки підказка до розв'язку.

printf("Nested comments is %s\n", */*/**/"*/"/*"/**/ == '*' ? "OFF" : "ON");
Подякували: Patlatus, leofun012

8

Re: Як краще перекласти фразу Maintain candidate subsequences by linking t

Зберігайте знайдені кандидати в підпослідовності привязуючи їх через вхідну послідовність.

Подякували: Patlatus1

9

Re: Як краще перекласти фразу Maintain candidate subsequences by linking t

Знайшов оригінал, сторінка 397, Exercise 15.4-6 *.

"Maintain candidate subsequences by linking them through the input sequence."
"Тримайте підпослідовності кандидатів прив'язуючи їх до вхідної послідовності."
Я б перефразував як
"Підпослідовності кандидатів можна зберігати як посилання на елементи вхідної послідовності."

Подякували: ReAl, Patlatus, koala3

10

Re: Як краще перекласти фразу Maintain candidate subsequences by linking t

Дякую всім. Обрав варіант

Зберігайте знайдені кандидати в підпослідовності
як посилання на елементи вхідної послідовності

Поки що закомічу такий варіант, потім якщо що науковий редактор і коректор відкоректує, якщо буде потреба.

11 Востаннє редагувалося Yola (03.10.2018 18:16:36)

Re: Як краще перекласти фразу Maintain candidate subsequences by linking t

Тут, мабуть, мається на увазі, що треба мати ще один масив, в якому на місці кожного елемента стоїть посилання на попередній елемент в його послідовності. Напр.:

1 4 9 2 3 5 -- дані
- 0 1 0 3 4 -- індекси
1 2 3 2 3 4 -- довжини

Не певен, що це оптимальний варіант, бо треба 2n пам'яті.

"Підпослідовності кандидатів можна зберігати як посилання на елементи вхідної послідовності."
"Підпослідовності кандидатів можна зв'язувати за допомогою посилань на елементи вхідної послідовності."

Бо linking them.

ukrainian.stackexchange.com - це питання-відповіді з української мови
Подякували: leofun011