Детерминиран алгоритъм

Детерминиран алгоритъм в информатиката е алгоритъм, който винаги при един и същ подаден вход връща един и същ резултат, като преминава през една и съща поредица от състояния. Неформално казано, поведението на такъв алгоритъм е предсказуемо. Детерминираните алгоритми са несравнимо по-добре изучени и използвани в практиката, тъй като могат ефективно да работят в реални условия.

Прост модел на детерминиран алгоритъм е математическата функция, тъй като тя също винаги връща един и същ резултат при подадени еднакви входни данни. Разликата между детерминиран алгоритъм и функция е в това, че алгоритъмът изрично описва как от входните данни се получават изходните, докато абстрактните функции могат да се дефинират имплицитно.

Формално определение

Формално, детерминираните алгоритми могат да се дефинират в термините на машина на състоянията: всяко от състоянията описва какво извършва машината във всеки конкретен момент от време. Машината на състоянията преминава последователно от едно дискретно състояние към друго, като навлиза в начално състояние тогава, когато ѝ се подаде вход. Ако машината е детерминирана, оттогава нататък, всяко нейно текущо състояние ще определя еднозначно какво ще бъде следващото състояние, и съответно множеството от състоянията е предварително известно. Следва да се отбележи, че дори никога да не спре работа, машината пак може да е детерминирана, стига да можем със сигурност да предскажем през какви точно състояния тя ще премине.

Примери за такива конкретни детерминирани абстрактни машини включват детерминираната машина на Тюринг и детерминираният краен автомат.

Фактори на недетерминираност

Разнообразни фактори могат да бъдат причината даден алгоритъм да се държи по непредсказуем, недетерминиран начин:

• Ако използва външно състояние, различно от входните данни, например потребителски вход, глобална променлива, стойност от хардуерен таймер, случайна стойност или съхранени на твърдия диск данни.
• Ако за функционирането на алгоритъма е от критично значение добрата синхронизация, например ако множество микропроцесори споделят един и същ ресурс от данни по едно и също време. В такъв случай, последователността, в която всеки процесор ще има достъп до данните, ще се отрази на крайния резултат.
• Ако хардуерна грешка доведе до непредвидена промяна на състоянието.

Въпреки че в действителност софтуерните програми рядко са напълно детерминирани, за хората, както и за останалите програми е по-лесно да ги разглеждат като такива. По тази причина, повечето езици за програмиране и по-специално езиците за функционално програмиране се опитват да предотвратят събития като гореизброените освен в контролирани условия. Поради начина по който подобни ограничения налагат детерминизма, детерминираните алгормитми понякога се наричат „чисто функционални“.

Проблеми при детерминираните алгоритми

За жалост, за решаването на някои проблеми е много трудно да се намерят детерминирани алгоритми. Например, съществуват прости и ефективни вероятностни алгоритми, които определят това дали дадено число е просто, но за които съществува много малка вероятност за грешка. Такива алгоритми са известни още от 1970-те години, например алгоритъма на Ферма за простите числа. Съответните им добре известни детерминирани алгоритми на практика функционират значително по-бавно.

Друг пример са задачите за NP-пълнота, включващи много от най-важните практически задачи, които бързо се решават, използвайки недетерминирана машина на Тюринг, но за които никога не са били изнамирани ефикасни практически алгоритми.

Друг голям проблем с детерминираните алгоритми е, че понякога ние не искаме резултатите да са предсказуеми. Например, ако разгледаме алгоритъма на онлайн игра на Блекджек, който разбърква тестето, използвайки генератор на псевдослучайни числа, съобразителният играч може с точност да отгатне кои числа ще избере генераторът и предварително да определи точната последователност на картите в тестето, което да му позволи да мами другите играчи. Подобни проблеми възникват и в криптографията, където частните ключове често се генерират използвайки такъв генератор. Проблеми като тези обикновено се избягват с употребата на криптографски сигурен генератор на псевдослучайни числа.

Източници

Тази страница частично или изцяло представлява превод на страницата Deterministic algorithm в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​