В інформатиці детермінований алгоритм — це алгоритм, який, з урахуванням конкретних вхідних даних, завжди буде видавати ті ж самі вихідні дані, а основна машина завжди проходить через однакову послідовність станів. Детерміновані алгоритми є на сьогоднішній день найвивченішим і найзвичнішим видом алгоритмів, а також одним із найпрактичніших, оскільки вони можуть бути запущені на реальних машинах ефективно.
Формально детермінований алгоритм обчислює математичну функцію; функція має унікальне значення для будь-яких вхідних даних в своїй області, і алгоритм являє собою процес, який дає на виході певне значення.
Формальне визначення
Детерміновані алгоритми можуть бути визначені в терміні кінцевого автомата: стан описує те, що машина робить в конкретний момент часу. Автомати проходять дискретним способом з одного стану в інший. Тільки після того, як ми вносимо вхідні дані, машина знаходиться в первинному або початковому стані. Якщо машина є детермінованою, це означає, що з цього моменту його поточний стан визначає яким буде наступний стан; його курс через безліч станів визначено. Зауважте, що машина може бути детермінованою і може ніколи не зупинитися чи закінчити якусь дію і, відповідно, не спромогтися надати результат обчислень.
Щодо прикладів конкретних абстрактних машин, які є детермінованими, можна віднести детерміновані машини Тьюринга і детермінований скінченний автомат.
Що робить алгоритми недетермінованими?
Різні фактори можуть змінювати поведінку алгоритму, роблячи її недермінованою:
- Якщо він використовує зовнішні стани, окрім вхідних даних, таких як введення даних користувачем, глобальна змінна, апаратний таймер значення, випадкове значення, або дані, збережені на жорсткому диску.
- Якщо він діє таким чином, що, наприклад, якщо він має кілька процесорів, які записують одні й ті ж самі дані у один і той самий час. В даному випадку, точний порядок, в якому кожен процесор записує дані будуть впливати на результат.
- Якщо апаратна помилка приводить до зміни стану.
Хоча реальні програми рідко є повністю детермінованими, тому що це простіше для людей. З цієї причини, більшість мов програмування і особливо мови функціонального програмування доклали зусиль, щоб запобігти вище описаним подіям, за винятком подій, на контрольованих умовах.
Поширеність багатоядерних процесорів привела до сплеску інтересу до детермінізму в паралельному програмуванні та виклики недетермінованости були добре задокументовані. Цілий ряд інструментів, щоб допомогти впоратися з проблемами, були запропоновані для боротьби з тупиками і умовами гонки.
Недоліки детермінізму
Недетермінована поведінка програми є вигідна в деяких випадках. Поведінка програми карти перетасовки, використовуваної в грі в блекджек, наприклад, не повинні бути передбачуваними гравцями — навіть якщо вихідний код програми видно. Використання генератора псевдовипадкових чисел часто буває недостатньо для того, щоб гравці не в змозі передбачити результат перетасовки. Розумний гравець може вгадати точно число, генератор буде вибирати і таким чином визначити весь вміст колоди завчасно, дозволяючи йому обдурити; наприклад, групи безпеки програмного забезпечення в надійних Software Technologies був в змозі зробити це для реалізації Texas Hold 'Em Poker, який поширюється ASF Software, Inc, що дозволяє їм послідовно передбачити результат руки завчасно. Ці проблеми можна уникнути, зокрема, за рахунок використання криптографічного безпечного генератора псевдовипадкових чисел, але він як і раніше необхідний для непередбачування випадкового числа, використованого для ініціалізації генератора. Для цієї цілі необхідне джерело недетермінізма, таке, яке є згенероване за допомогою апаратного генератора випадкових чисел.
Зверніть увагу, що негативна відповідь на проблеми P = NP не означатиме, що програми з недетермініроваим виходом теоретично більш потужні, ніж з детермінованим . Складність класу NP може бути визначена без посилання на недетермінізма, використовуючи визначення верифікатор основі.
Детермінізм категорій у мовах
Mercury
Ця логіко-функціональна мова програмування, створює різні категорії для режими детермінізму, які є пояснені в реф.
Haskell забезпечує кілька механізмів:
- недетермінованість або поняття fail
- типи Maybe і Either включають в себе поняття успіху в результаті.
- Метод fail класу монади, може бути використаний для сигналу fail як виняток.
- Монада Maybe і монада MaybeT перетворює безуспішні обчислення (зупиняє послідовность обчислень і нічого не повертає)
- детермінізм з кількома рішеннями
- ви можете отримати всі можливі результати множинного результату обчислення, обернувши його результат у монади типу MonadPlus. (метод mzero обробляє безуспішні результати і mplus збирає успішні результати).
Сім'я ML та похідні від неї мови
Як зазначено в стандартному ML, OCaml i Scala
- Даний тип option включає в себе поняття успішності.
- Значення NULL може представляти невдалий (який не входить в домен) результат.
Примітки
- . Архів оригіналу за 3 липня 2012. Процитовано 31 травня 2016.
- . Архів оригіналу за 3 липня 2012. Процитовано 31 травня 2016.
- . Архів оригіналу за 3 січня 2015. Процитовано 31 травня 2016.
- . Архів оригіналу за 13 липня 2014. Процитовано 31 травня 2016.
![]() | Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V informatici determinovanij algoritm ce algoritm yakij z urahuvannyam konkretnih vhidnih danih zavzhdi bude vidavati ti zh sami vihidni dani a osnovna mashina zavzhdi prohodit cherez odnakovu poslidovnist staniv Determinovani algoritmi ye na sogodnishnij den najvivchenishim i najzvichnishim vidom algoritmiv a takozh odnim iz najpraktichnishih oskilki voni mozhut buti zapusheni na realnih mashinah efektivno Formalno determinovanij algoritm obchislyuye matematichnu funkciyu funkciya maye unikalne znachennya dlya bud yakih vhidnih danih v svoyij oblasti i algoritm yavlyaye soboyu proces yakij daye na vihodi pevne znachennya Formalne viznachennyaDeterminovani algoritmi mozhut buti viznacheni v termini kincevogo avtomata stan opisuye te sho mashina robit v konkretnij moment chasu Avtomati prohodyat diskretnim sposobom z odnogo stanu v inshij Tilki pislya togo yak mi vnosimo vhidni dani mashina znahoditsya v pervinnomu abo pochatkovomu stani Yaksho mashina ye determinovanoyu ce oznachaye sho z cogo momentu jogo potochnij stan viznachaye yakim bude nastupnij stan jogo kurs cherez bezlich staniv viznacheno Zauvazhte sho mashina mozhe buti determinovanoyu i mozhe nikoli ne zupinitisya chi zakinchiti yakus diyu i vidpovidno ne spromogtisya nadati rezultat obchislen Shodo prikladiv konkretnih abstraktnih mashin yaki ye determinovanimi mozhna vidnesti determinovani mashini Tyuringa i determinovanij skinchennij avtomat Sho robit algoritmi nedeterminovanimi Rizni faktori mozhut zminyuvati povedinku algoritmu roblyachi yiyi nederminovanoyu Yaksho vin vikoristovuye zovnishni stani okrim vhidnih danih takih yak vvedennya danih koristuvachem globalna zminna aparatnij tajmer znachennya vipadkove znachennya abo dani zberezheni na zhorstkomu disku Yaksho vin diye takim chinom sho napriklad yaksho vin maye kilka procesoriv yaki zapisuyut odni j ti zh sami dani u odin i toj samij chas V danomu vipadku tochnij poryadok v yakomu kozhen procesor zapisuye dani budut vplivati na rezultat Yaksho aparatna pomilka privodit do zmini stanu Hocha realni programi ridko ye povnistyu determinovanimi tomu sho ce prostishe dlya lyudej Z ciyeyi prichini bilshist mov programuvannya i osoblivo movi funkcionalnogo programuvannya doklali zusil shob zapobigti vishe opisanim podiyam za vinyatkom podij na kontrolovanih umovah Poshirenist bagatoyadernih procesoriv privela do splesku interesu do determinizmu v paralelnomu programuvanni ta vikliki nedeterminovanosti buli dobre zadokumentovani Cilij ryad instrumentiv shob dopomogti vporatisya z problemami buli zaproponovani dlya borotbi z tupikami i umovami gonki Nedoliki determinizmuNedeterminovana povedinka programi ye vigidna v deyakih vipadkah Povedinka programi karti peretasovki vikoristovuvanoyi v gri v blekdzhek napriklad ne povinni buti peredbachuvanimi gravcyami navit yaksho vihidnij kod programi vidno Vikoristannya generatora psevdovipadkovih chisel chasto buvaye nedostatno dlya togo shob gravci ne v zmozi peredbachiti rezultat peretasovki Rozumnij gravec mozhe vgadati tochno chislo generator bude vibirati i takim chinom viznachiti ves vmist kolodi zavchasno dozvolyayuchi jomu obduriti napriklad grupi bezpeki programnogo zabezpechennya v nadijnih Software Technologies buv v zmozi zrobiti ce dlya realizaciyi Texas Hold Em Poker yakij poshiryuyetsya ASF Software Inc sho dozvolyaye yim poslidovno peredbachiti rezultat ruki zavchasno Ci problemi mozhna uniknuti zokrema za rahunok vikoristannya kriptografichnogo bezpechnogo generatora psevdovipadkovih chisel ale vin yak i ranishe neobhidnij dlya neperedbachuvannya vipadkovogo chisla vikoristovanogo dlya inicializaciyi generatora Dlya ciyeyi cili neobhidne dzherelo nedeterminizma take yake ye zgenerovane za dopomogoyu aparatnogo generatora vipadkovih chisel Zvernit uvagu sho negativna vidpovid na problemi P NP ne oznachatime sho programi z nedeterminirovaim vihodom teoretichno bilsh potuzhni nizh z determinovanim Skladnist klasu NP mozhe buti viznachena bez posilannya na nedeterminizma vikoristovuyuchi viznachennya verifikator osnovi Determinizm kategorij u movahMercury Cya logiko funkcionalna mova programuvannya stvoryuye rizni kategoriyi dlya rezhimi determinizmu yaki ye poyasneni v ref Haskell Haskell zabezpechuye kilka mehanizmiv nedeterminovanist abo ponyattya fail tipi Maybe i Either vklyuchayut v sebe ponyattya uspihu v rezultati Metod fail klasu monadi mozhe buti vikoristanij dlya signalu fail yak vinyatok Monada Maybe i monada MaybeT peretvoryuye bezuspishni obchislennya zupinyaye poslidovnost obchislen i nichogo ne povertaye determinizm z kilkoma rishennyami vi mozhete otrimati vsi mozhlivi rezultati mnozhinnogo rezultatu obchislennya obernuvshi jogo rezultat u monadi tipu MonadPlus metod mzero obroblyaye bezuspishni rezultati i mplus zbiraye uspishni rezultati Sim ya ML ta pohidni vid neyi movi Yak zaznacheno v standartnomu ML OCaml i Scala Danij tip option vklyuchaye v sebe ponyattya uspishnosti Java Znachennya NULL mozhe predstavlyati nevdalij yakij ne vhodit v domen rezultat Primitki Arhiv originalu za 3 lipnya 2012 Procitovano 31 travnya 2016 Arhiv originalu za 3 lipnya 2012 Procitovano 31 travnya 2016 Arhiv originalu za 3 sichnya 2015 Procitovano 31 travnya 2016 Arhiv originalu za 13 lipnya 2014 Procitovano 31 travnya 2016 Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi