Детерминированный алгоритм
Детерминированный алгоритм — алгоритмический процесс, который выдаёт уникальный и предопределённый результат для заданных входных данных.
Недетерминированный алгоритм
В информатике, «недетерминированный алгоритм» — это алгоритм, указывающий несколько путей обработки одних и тех же входных данных, — без какого-либо уточнения, какой именно вариант будет выбран.
Использование
Теория алгоритмов
В теории алгоритмов — под термином «алгоритм» обычно понимается «детерминированный» алгоритм. «Недетерминированный» — отличается от своего более известного «двойника» возможностью получения результата разными путями («детерминированный» — следует единственным путём: от данных — к результату, — тогда как некоторые пути выполнения «недетерминированного» могут привести к одинаковому результату, а некоторые — к другим результатам). Эти свойства — описаны математически: в «недетерминированной» модели вычислений, известной как «».
Разработка алгоритмов
В разработке алгоритмов — «недетерминированные» алгоритмы часто используются, когда задача, решаемая алгоритмом, — по своей сути, — позволяет найти много выходов (или — когда существует один выход со многими путями, через которые он может быть найден, и все «одинаково хороши»). Важно, что каждый выход «недетерминированного» алгоритма — верный; — независимо от путей, «выбранных» алгоритмом во время выполнения.
Примеры
«Список покупок»
Представим «список покупок»: список товаров для покупки — что можно осмыслить двумя способами: как указание купить все эти товары...
- ...в любом порядке («недетерминированный» алгоритм);
- ...в данном порядке («детерминированный» алгоритм).
«Сортировка слиянием»
Допустим, — имеется набор «сущностей» (скажем, — 300 студентов), который необходимо «упорядочить» (скажем, — по «номерам» студентов). Один из алгоритмов для этого — «сортировка слиянием»:
- Разделить набор на две приблизительно равные группы;
- Отсортировать обе группы данной сортировкой (т.е. «рекурсивно»);
- Объединить результаты («слить воедино»; см. название метода).
Элементы могут быть «уникально» отсортированы, если критерий сортировки всегда определяет «полный» порядок (т.е. «номера» студентов «уникальны»: не повторяются между собой). Но иначе (например, — если сортировать экзамены по фамилиям студентов без учёта однофамильцев) — результат сортировки не определён: неизвестно, какое именно упорядочение считать верным; — т.е. алгоритм «недетерминированный».
«Тест простоты»
Задача: дано натуральное число больше единицы; определить, является ли оно простым.
Решение: «недетерминированный» алгоритм — следующий:
- Взять любое целое «k» — такое, что 2 ≤ k ≤ √(n);
- Если «k» является делителем «n» — остановиться с ответом «нет»; иначе — остановиться с ответом «неизвестно».
Видно, что алгоритм не всегда даёт «полезный» ответ, но никогда не даёт неправильного ответа.
Этот алгоритм — «недетерминированный»: он не всегда выдаёт «полезное» решение — но может, при определённой комбинации выборов. Это — пример «поискового» типа «недетерминированного» алгоритма.
См. также
- Конечный автомат
- Недетерминированная машина Тьюринга
- Алгоритмы класса NP
- Побочный эффект (программирование)
- Неоднозначная грамматика
- Вероятностный алгоритм
Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры, мобильный, телефон, Android, iOS, apple, мобильный телефон, Samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Сеть, компьютер, Информация о Детерминированный алгоритм, Что такое Детерминированный алгоритм? Что означает Детерминированный алгоритм?
Determinirovannyj algoritm algoritmicheskij process kotoryj vydayot unikalnyj i predopredelyonnyj rezultat dlya zadannyh vhodnyh dannyh Nedeterminirovannyj algoritmOsnovnaya statya Nedeterminirovannaya mashina Tyuringa V informatike nedeterminirovannyj algoritm eto algoritm ukazyvayushij neskolko putej obrabotki odnih i teh zhe vhodnyh dannyh bez kakogo libo utochneniya kakoj imenno variant budet vybran IspolzovanieTeoriya algoritmov V teorii algoritmov pod terminom algoritm obychno ponimaetsya determinirovannyj algoritm Nedeterminirovannyj otlichaetsya ot svoego bolee izvestnogo dvojnika vozmozhnostyu polucheniya rezultata raznymi putyami determinirovannyj sleduet edinstvennym putyom ot dannyh k rezultatu togda kak nekotorye puti vypolneniya nedeterminirovannogo mogut privesti k odinakovomu rezultatu a nekotorye k drugim rezultatam Eti svojstva opisany matematicheski v nedeterminirovannoj modeli vychislenij izvestnoj kak Razrabotka algoritmov V razrabotke algoritmov nedeterminirovannye algoritmy chasto ispolzuyutsya kogda zadacha reshaemaya algoritmom po svoej suti pozvolyaet najti mnogo vyhodov ili kogda sushestvuet odin vyhod so mnogimi putyami cherez kotorye on mozhet byt najden i vse odinakovo horoshi Vazhno chto kazhdyj vyhod nedeterminirovannogo algoritma vernyj nezavisimo ot putej vybrannyh algoritmom vo vremya vypolneniya Primery Spisok pokupok Predstavim spisok pokupok spisok tovarov dlya pokupki chto mozhno osmyslit dvumya sposobami kak ukazanie kupit vse eti tovary v lyubom poryadke nedeterminirovannyj algoritm v dannom poryadke determinirovannyj algoritm Sortirovka sliyaniem Osnovnaya statya Sortirovka sliyaniem Dopustim imeetsya nabor sushnostej skazhem 300 studentov kotoryj neobhodimo uporyadochit skazhem po nomeram studentov Odin iz algoritmov dlya etogo sortirovka sliyaniem Razdelit nabor na dve priblizitelno ravnye gruppy Otsortirovat obe gruppy dannoj sortirovkoj t e rekursivno Obedinit rezultaty slit voedino sm nazvanie metoda Elementy mogut byt unikalno otsortirovany esli kriterij sortirovki vsegda opredelyaet polnyj poryadok t e nomera studentov unikalny ne povtoryayutsya mezhdu soboj No inache naprimer esli sortirovat ekzameny po familiyam studentov bez uchyota odnofamilcev rezultat sortirovki ne opredelyon neizvestno kakoe imenno uporyadochenie schitat vernym t e algoritm nedeterminirovannyj Test prostoty Osnovnaya statya Perebor delitelej Zadacha dano naturalnoe chislo bolshe edinicy opredelit yavlyaetsya li ono prostym Reshenie nedeterminirovannyj algoritm sleduyushij Vzyat lyuboe celoe k takoe chto 2 k n Esli k yavlyaetsya delitelem n ostanovitsya s otvetom net inache ostanovitsya s otvetom neizvestno Vidno chto algoritm ne vsegda dayot poleznyj otvet no nikogda ne dayot nepravilnogo otveta Etot algoritm nedeterminirovannyj on ne vsegda vydayot poleznoe reshenie no mozhet pri opredelyonnoj kombinacii vyborov Eto primer poiskovogo tipa nedeterminirovannogo algoritma Sm takzheKonechnyj avtomat Nedeterminirovannaya mashina Tyuringa Algoritmy klassa NP Pobochnyj effekt programmirovanie Neodnoznachnaya grammatika Veroyatnostnyj algoritm
