Доказ того, що 40-річний алгоритм є оптимальним, буде полегшенням для фахівців з обчислювальних систем


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

Пише Ларри Хардести | Новинне бюро MIT

Порівняння геномів різних видів або різних представників одного виду – основа більшої частини сучасної біології. Послідовності ДНК, що зустрічаються у різних видів, можуть виявитися функціонально важливими, тоді як відмінності в генах представників одного виду можуть вказувати на сприйнятливість до різних хвороб.

Основному алгоритму для визначення того, скільки у двох послідовностей символів загального, тобто так званої редакційної відстані між ними, вже більше 40 років. І упродовж 40 років нікому так і не вдалося поліпшити його.

На симпозіумі ACM по Теорії Обчислень (STOC) наступного тижня вчені MIT повідомлять, що це, швидше за все, тому, що ніщо краще за цей алгоритм з’явитися вже не може. Якщо широко поширене припущення про обчислювальну складність вірно, то ефективнішого способу виміру різниці двох геномів, текстів, мовних зразків або чогось ще, що може бути представлено у вигляді ряду символів, не існує.

З одного боку, це погана новина, оскільки у цього алгоритму піде 1000 років на вичерпне порівняння двох людських геномів. Але це також означає, що фахівці з обчислювальних систем можуть перестати мучитися, намагаючись поліпшити його.

“Я намагався поліпшити алгоритми для обчислення редакційної відстані відколи був аспірантом в середині 90-х”, – говорить Петро Индык, професор комп’ютерних наук і інженерії в Массачусетському технологічному інституті і співавтор доповіді для STOC. “Я витратив на цього багато безсонних ночей і так і не досяг ніякого прогресу. Принаймні, тепер можна спати спокійно”.

Крім того, за словами Индыка, попри те, що доповідь ще не була офіційно представлена, вже написані дві статті, що застосовують підхід доповіді до схожих завдань. “У цієї доповіді є і технічна сторона, що розповідає про конструкцію деякого гаджета, який виявився корисним для інших цілей”, – говорить Индык.

Редакційна відстань – ця мінімальна кількість правок, тобто видалень, вставок і замін, необхідних для перетворення одного ряду символів на інший. Стандартний алгоритм для визначення редакційної відстані, відомий як алгоритм Вагнера – Фишера, привласнює кожен символ однієї послідовності до стовпця у велетенській сітці, а кожен символ інший – до рядка в цій сітці. Потім, починаючи з верхнього лівого кута і рухаючись по діагоналі, він заповнює кожен осередок кількістю редакцій, необхідних для перетворення ряду символів, що закінчується відповідним стовпцем, в ряд, що закінчується відповідним рядком

Фахівці з обчислювальних систем ефективністю алгоритму вважають відношення часу обчислення до кількості числа елементів, з якими працює цей алгоритм. Оскільки алгоритм Вагнера – Фишера повинен заповнити кожен осередок сітки, час його роботи прямо пропорціонально довжині двох послідовностей, які він порівнює. Якщо подвоїти довжини цих послідовностей, час виконання збільшується в чотири рази. Говорячи мовою комп’ютерників, алгоритм виконується в квадратичний час.

Це навряд чи здасться вам дуже ефективним, але квадратична складність набагато краща за експоненціальну складність, коли час виконання пропорційний 2N, де N – кількість елементів, з якими працює алгоритм. Якщо на певному апараті у алгоритму, працюючого в квадратичному часі, пішла сота секунди на обробку ста елементів, у алгоритму з експоненціальною складністю це займе близько 100 квінтилліонів років.

Теоретична інформатика зокрема заклопотана класом проблем, відомих як NP- повні. Більшість учених вважають, що для вирішення NP- повних завдань треба експоненціальний час, але ніхто доки не зміг цього довести. У своїй доповіді Индык і його студент Артур Бачкурс доводять, що якщо можливо розв’язати проблему редакційної відстані швидше квадратичного часу, то можливо і вирішити NP- повне завдання за час менше експоненціального. Більшість учених, працюючих у сфері обчислювальної складності, вважають це переконливим доказом того, що існують субквадратичні рішення завдань редакційних відстаней.

Основна NP- повне завдання відоме як “завдання здійснимості”: враховуючи безліч логічних обмежень, чи можна виконати їх все? Уявимо, що ви хочете організувати звану вечерю і намагаєтеся вирішити, кого запросити. Ви можете зіткнутися з рядом обмежень: або Алісі, або Бобу доведеться залишитися удома з дітьми, тому обоє вони прийти не зможуть; якщо ви запросите Синди або Дейва, вам доведеться також запросити усіх інших учасників книжкового клубу, щоб ніхто не відчув себе обділеним; Елен прийде або з чоловіком Фредом, або з коханцем Джорджем, але не з обома; і так далі. Чи існує список гостей, який врахує усі ці обмеження?

Индык і Бачкурс у своєму доказі припускають, що зіткнувшись з проблемою здійснимості, ви повинні розділити змінні на дві групи приблизно однакового розміру: Алісу, Боба і Синди потрібно помістити в одну, а Уолта, Ивонн і Зака – в іншу. Потім для обох груп ви повинні вирішити це завдання, враховуючи усі відповідні обмеження. Таке обчислення може виявитися неймовірно трудомістким, та зате набагато менш складним, чим обчислення для усієї групи в цілому. Те, що, наприклад, Заку не можна наближатися до Аліси із-за заборонного судового наказу, не має ніякого значення, оскільки вони знаходяться в різних підгрупах. Це обмеження не треба враховувати.

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

“Це відмінна робота”, – говорить Барна Саха, доцент комп’ютерних наук в Університеті штату Массачусетс в Амхерсте. “Багато людей працювало над цим завданням, тому що у неї є значиме практичне застосування. Але вони вже не намагатимуться розробити субквадратичний алгоритм, тому що позитивний результат маловірогідний, якщо вірити виведенням цієї роботи”.

Що стосується припущення, на якому грунтований доказ учених MIT, що NP- повні завдання не можуть бути вирішені в субекспоненціальний час, Саха пояснює: “Багато учених вірять в цю гіпотезу. Існує багато інших робіт в області складнощі низького полиноминального часу, які покладаються на цю гіпотезу”.

Переклад “Longstanding problem put to rest. Proof that a 40 – year old algorithm is the best possible will come as relief to computer scientists”

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *