Граматичні особливості перекладу науково-технічної літератури з англійської на українську мову

Рис 1.11Початкова та кінцева форми зміни обертання: приклад показаний в 3 позиції обертання в межах М8(праворуч). Пара загальних напрямків, які дозволяють досягти сталого обертання : а) напрямок, за яким слідує вектор Ф в той час, як зустрічається з початком площини Mn перед його правою стороною; б) напрямок, за яким слідує вектор F в той час, як він зустрічається з правою стороною площини Mn перед його початковою стороною; всі діагональні шляхи мають той самий нахил.

Алгоритми засновані на «обійманні» «стін» Mn

Задачі перегрупування, що обговорюються в розд. 1.3.1, в деякому сенсі є зручними для вирішення, тому що деякі встановлені "кодові слова", такі як "зміна" або попередньо-встановлений параметр, як наприклад, раціональний ?, який визначаючи обертання, встановлює спочатку зразок траєкторії, який можна використовувати для вирішення будь-якого примірника завдання. Зараз ми обговорюємо алгоритмічну стратегію перебудови, яка часто може бути використана для вирішення менш наочно проілюстрованих задач перебудови, зокрема тих, що вимагають комплексу пристосувань робочого циклу до зразків траєкторії. (Слово "комплекс" тут призначене для того, щоб відрізнити пристосування простого двійкового перемикача адаптації, який ми використовували для задачі зміни обертання в розд. 1.3.1.3.Б).

Стратегія «плавання» Mn, у той час як вона "обіймає свої стіни", дає гнучкий механізм для вирішення широкого спектру "визначеного робочого циклу" задачі зміни обертання. Кругосвітній зразок траєкторії, показаний в його загальній формі на рис. 1.13. КА F робить серію подорожі відрізку Mn, транспортуючи один об'єкт з рядка 0 до рядка N ? 1 під час кожного циклу зворотів. Сила цієї алгоритмічної стратегії проявляється в:

* його широкій застосовуваністі; насправді, він може бути використаний, щоб вирішити обидві проблеми зміни обертання в Розд. 1.3.1.3;

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

Слабкість цієї стратегії виникає від негнучкості щодо усіх доступних "коротких шляхів": кожна подорож займає однакову кількість часу - приблизно 4n кроків. На відміну від цього, іноді використовують визначену для задачі стратегію, щоб прискорити зміну з коефіцієнтом 2. Анулювання КА Розд. 1.3.1.3. Досягнення такого прискорення і обертання КА іноді досягається в залежності від раціонального ? і спектру руху одноступеневої КА (пор. Рис. 1.2).

Ми викладаємо в деталях попереднє абстрактне обговорення, зосередивши увагу на двох істотних "визначених робочих циклів" проблеми зміни обертання. Класифікація проблеми зміни Розд. 1.3.2.1 передбачає необхідність КА F, яка переміщує об'єкти, що перебувають у рядках 0 Mn в рядок n ? 1, де F вносить об'єкти у відсортованому порядку за їх типами. (Ми, звичайно, припускаємо, що об'єкти-типи проходять упорядкований набор.)

Очевидно, що F може визначити остаточне розміщення об'єкта у вздовж рядка N?1, тільки коли він визначить, скільки об'єктів з рядка 0 мають типи, менше, ніж типи у (за класифікацією типів). В Розд. 1.3.2.1 ми покажемо, як стратегія «плавання» надає ефективне рішення для класифікації проблеми зміни. Ми завершуємо цей розділ в Розд. 1.3.2.2, обговорюючи варіант стратегії «плавання», таким чином, визначаючи спосіб перевірки зразку задачі Розд. 1.3.1.2.

Рис. 1.13 Загальна траєкторія «плавання», що дозволяє F виконувати цілий ряд операцій перегрупування. F перетинає складний шлях, оскільки він переміщує наступний об'єкт із своєї початкової плитки вздовж рядка від 0 до відведеної йому плитки вздовж рядка n? 1. F перетинає пунктирну лінія, оскільки він повертається в верхнього рядку площини Mn для того, щоб знайти наступний об'єкт.

Класифікація зміни

Проілюстрований процес досить простий. F декілька разів проходить через рядок 0. В той час, коли проходить перша група, кожне «плавання» транспортує один об'єкт, що має найменше значення за класифікацією, назвемо його o, ліворуч в блок плиток вздовж рядка n ? 1, які призначені для об'єктів цього типу. F визначає цей блок, йдучи уздовж рядка n ? 1, поки він не зустріне об'єкт типу o або лівий край площини Mn (який подає сигнали, що жодні об'єкти типу o ще не були встановлені вздовж рядка n ? 1). Переправивши всі об'єкти типу о, F починає проходити через рядок 0 вдруге, протягом чого він транспортує всі об'єкти, що мають друге найменше значення в ліву плитку вздовж рядка n - 1, які знаходяться праворуч від плиток що тримають об'єкти типу o. Процес транспортування триває, нова партія проходить обробку кожного наступного більшого за значенням об'єкту. Відбувається остаточний прохід, який підтверджує відсутність залишку об'єктів ряду 0 і завершує процес. Зверніть увагу, що за це останнє порожнє «плавання» в межах площини Mn, F виконує один повний кругообіг за об'єкт. Таким чином, весь процес займає приблизно 4n2 кроків.

Ми знаємо, але все ж повинні довести, що попередній алгоритм сортування-зміни алгоритму не може прискорити якісь конкретні задачі стратегії, через раніше згаданий факт, що кінцевий пункт призначення уздовж рядка N ? 1 будь-якого об'єкта у з рядка 0 залежить від кількості об'єктів, які почалися уздовж рядка 0 і які мають значення менше за у.

Перегляд ідентифікації/перевірки зразка задачі

Кожна проблема класу, що обговорюються в розд. 1.3.1.3, вимагає одинарного КА, що може транспортувати об'єкти з верхнього рядка до нижнього рядка площини Mn та зберігати їх там за певним зразком. Тепер ми переходимо до задачі спорідненого типу, яка починається з об'єктів розташованих як у верхньому, так і в нижньому рядку площини Mn. Зараз стоїть завдання розробити КА (або команду для нього), який би міг за допомогою масштабу перевірити, чи зразок класу об'єкта, що розташований уздовж рядка N-1 належить системі перегрупувань зразка класу об'єктів, розташованих уздовж рядка 0. Звичайно, якщо цільова система перегрупувань включає в себе лише один клас перегрупування -- так званий, зразок зі зворотнім ходом або зразок, що обертається -- то рішення щойно описаної задачі перевірки не є складнішим, ніж вирішити задачу перегрупування. А саме, розробити перестановчий КА, який потім буде перевіряти результати свого перегрупування за введеним зразком вздовж рядку n?1. Проте, якщо цільова система охоплює велику кількість можливих перегрупувань, то вирішення задачі перевірки може вимагати досить різних алгоритмічних засобів, ніж просто зробити для кожного окреме перегрупування. Цей розділ представляє задачу перевірки за допомогою лише однієї щільно заповненої цільової системи перегрупувань, зокрема, систему всіх можливих обертових зразків.

Докладно, задача, що нас цікавить має наступну форму. Площина Mn містить об'єкти розташовані вздовж її верхніх та нижніх рядків. Потрібно розробити КА, який зможе, в достатньо великих площинах відповісти на наступне запитання: чи є зразок класу об'єктів вздовж нижнього ряду площини Mn обертанням зразку вздовж верхнього ряду? Рис. 1.16.

Не важко розробити КА F, який би вирішував цю обертально-визначальну задачу, особливо якщо припустити, що всі плитки Mn, крім тих, що у верхньому і нижньому рядках залишаються порожніми. Ми допускаємо це тут; конторські модифікації можуть обійти його. Алгоритм, який наш КА F втілює, не є досконалим: він безпосередньо перевіряє всі можливості по порядку. Єдина тонкість у процедурі - як F відслідковує місця всіх обертів. На Рис. 1.17 F виконує свої підрахунки, вибірково переміщаючи об'єкти з їхніх вихідних рядків (які знаходяться в рядку 0 або врядку N ? 1) до сусідніх рядків. (Для "чистоти" F ми відновлювати об'єкти в їх вихідні плитки для того, щоб зробити висновок алгоритму.) Алгоритм розвивається в етапах N, кожен з яких має підетапи n.

Ф досягає цього шляхом тасування об'єктів між двома верхніми рядками і трьома нижніми площини Mn; об'єкти ніколи не залишають свої стовпці. Третій рядок знизу Mn (рядки n-3) використовується для відстеження початкових місць можливих обертів, які вже були випробувані. F використовує рядки площини Mn 1 і n-2 для того щоб стежити за його послідовним зіставленням об'єктів «плавання»: під час кожного «плавання», F визначає, чи відповідає об'єкт праворуч від рядка 1 об'єкту зліва від рядка n?1. F відповідно переносить об'єкти з рядка 0 і n?1 після кожного матч-тесту для того, щоб підготувати їх до наступного «плавання», і він переносить один об'єкт із рядка n?2 для того, щоб підготувати до тесту на наступне потенціальне обертання. Позиції об'єкту повертаються в вихідне положення, щоб підготуватися до кожного нового «плавання».

· Первинний етап алгоритму «i» перевіряє положення плитки вздовж ряду n?1, щоб визначити, чи є зразок класу об'єктів в рядку n?1 обертанням зразку у рядку 0, з плиткою (n?1 i) в якості вісі обертання, це означає, що

у0 . . . у i?1у i . . . у n?1 = уn?i . . . уn?1у0у1 . . . уn?i?1.

- Якщо цей тест пройдено, то F повідомляє про успіх -- зразок вздовж рядка n ? 1 є обертанням зразку вздовж рядка 0.

- Якщо тест не пройдено, то F переміщує уi я до рядка n?3, тобто в плитку (n?3, i) .

Якщо I = n-1, то F зупиняє і звітує про помилки -- зразок вздовж рядка n-1і не є обертанням зразку вздовж рядку 0.

Якщо I n?1, то F відправляється на початковий етап I + 1

* Вторинний етап алгоритму j, виконує n «плавання» яке необхідні для того, щоб визначити, чи є поточно потенціальна вісь плитки (n?1, j), дійсно, віссю поточного обертання. Для кожного i ? [0, n ? 1], F ініціює

послідовність n «плавання».

Перше «плавання» починається в плитці V0 = 0, 0. Впродовж переміщення F перевіряє, чи має об'єкт в плитці V0 той самий тип, що і об'єкт в плитці (n?1, j).

- Якщо відповідь "НІ", то F скасовує цей первинний етап і переходить до наступного.

- Якщо відповідь "ТАК", то F закінчує «плавання» і готується до наступного, протягом якого він буде перевіряти, чи має об'єкт в плитці (0, 1) такий самий тип, як і об'єкт в плитці n?1і j + 1.

Важлива деталь - це як F відстежує верхні та нижні плитки, і чий тип об'єктів перевіряється. F досягає цього шляхом переміщення кожного об'єкта, що перевіряється, в сусідній ряд. Об'єкт з рядка 0 переміщується в рядок 1; об'єкт з рядка n?с (c ? {1, 2}) переноситься в рядок n?с?1. Наприкінці цього вторинного етапу, всі об'єкти будуть повернені в плитки, в яких вони почали цей етап, в рамках підготовки до наступного вторинного етапу. Важливо відзначити, що "арифметика", насправді, виконується для того, щоб визначити послідовні об'єкти вздовж нижнього рядка площини Mn, що виконується по модулю n. Це є поступовим завершенням операції: коли F виявляє праву сторону площини Mn, він починає обробляти плитки з лівої сторони нижніх рядків Mn, а не з його середини.

Деталі з готовністю постачаються, та перетворюють цю схему на довершений алгоритм.

ДОДАТОК Б

Глосарій термінів галузі робототехніки

Терміни-абревіатури

Загальновживані технічні терміни

Размещено на Allbest.ru