Детермінований алгоритм - це
недетермінований алгоритм
В інформатиці. недетермінований алгоритм - це алгоритм. який вказує кілька шляхів обробки одних і тих же вхідних даних, без будь-якого уточнення, який саме варіант буде обраний.
Використання
У теорії алгоритмів під терміном «алгоритм» зазвичай розуміється детермінованості алгоритм. Недетермінований алгоритм відрізняється від свого більш відомого двійника можливістю отримання результату кількома різними шляхами. Детермінований алгоритм слід єдиним шляхом від вхідних даних до вихідних, тоді як деякі шляхи виконання недетермінірованного алгоритму можуть привести до однакового результату, а деякі до інших результатів. Ці властивості описані математично в «недетермінованої» моделі обчислень відомої як недетермінований автомат.
У розробці алгоритмів, недетерміновані алгоритми часто використовуються, коли завдання, яке вирішується алгоритмом, за своєю суттю дозволяє багато виходів (або коли існує один вихід з багатьма шляхами через які він може бути знайдений, і все однаково хороші). Важливо, що кожен вихід недетермінірованного алгоритму вірний, незалежно від шляхів обраних алгоритмом під час виконання.
Список покупок
Уявімо список покупок: список товарів для покупки.
Це можна осмислити двома способами:
- Як вказівку купити всі ці товари в будь-якому порядку. Це недетермінований алгоритм.
- Як вказівку купити всі ці товари в даному порядку. Це детермінований алгоритм.
Сортування злиттям
Припустимо ми маємо набір сутностей (скажімо, 300 студентських іспитів), які необхідно відсортувати (скажімо, за номерами студентів).
Один з алгоритмів для цього (називається Сортування злиттям):
- розбити набір на дві приблизно рівні частини
- впорядкувати обидві половини сортуванням злиттям (тобто рекурсивно)
- злити результати
Елементи можуть бути унікально відсортовані, якщо критерій сортування завжди визначає повний порядок; тобто номера студентів унікальні, але якщо сортувати іспити за прізвищами студентів та два студента мають однакові прізвища, результат сортування залишається невизначеним. У таких випадках, сортування злиттям завжди буде видавати один з можливих упорядкування, але яке саме залишається невідомо, тобто алгоритм недетермінований.
тест простоти
Завдання: дано натуральне число більше одиниці, визначити чи є це число простим.
Недетермінований алгоритм наступний:
- Взяти будь-яке ціле k таке, що 2 ≤ k ≤ √ (n).
- Якщо k є дільником n. зупиниться з відповіддю немає; інакше зупиниться з відповіддю не відомо.
Видно, що алгоритм не завжди дає корисний відповідь, але ніколи не дає неправильної відповіді.
Цей алгоритм недетермінований, він не завжди видає вірне рішення, але тільки при певній комбінації виборів. Це приклад пошукового типу недетермінірованного алгоритму.
Дивитися що таке "Детермінований алгоритм" в інших словниках:
Алгоритм Шенкса - (англ. Baby step giant step; також званий алгоритм великих і малих кроків) в теорії груп, детермінований алгоритм дискретного логарифмування в кільці відрахувань по модулю простого числа. Для модулів спеціального виду даний ... ... Вікіпедія
Алгоритм поліг - Хеллмана - алгоритм поліґа-геллмана (також званий алгоритм Силвера поліг Хеллмана) детермінований алгоритм дискретного логіріфмірованія в кільці відрахувань по модулю простого числа. Для модулів спеціального виду даний алгоритм ... ... Вікіпедія
Алгоритм поліг - алгоритм поліґа-геллмана (також званий алгоритм Сільвера поліг Хеллмана) детермінований алгоритм дискретного логарифмування в кільці відрахувань по модулю простого числа. Однією з особливостей алгоритму є те, ... ... Вікіпедія
алгоритм - а, м. algorithme m. 1230 algorisme. Лексіс.1. В математиці общепонятном припис, що визначає детермінований обчислювальний процес, що веде від вихідних даних до шуканого результату. БАС 2. Алгебра логіка математики; алгоритм її ... ... Історичний словник галліцізмов української мови
Алгоритм - Цей термін має також інші значення див. Алгоритм (значення). Для поліпшення цієї статті бажано. Переробити оформлення відповідно до правил ... Вікіпедія
деревовидний алгоритм - 05.02.59 деревовидний алгоритм [tree algorithm]: Детермінований алгоритм, який використовується пристроєм зчитування / опитування, при якому після виявлення колізії сигналів радіочастотних міток здійснюється пошук по доступному простору ... ... Словник-довідник термінів нормативно-технічної документації
Імовірнісний алгоритм - В теорії алгоритмів класом складності BPP (від англ. Bounded error, probabilistic, polynomial) називається клас предикатів, швидко (за поліноміальний час) обчислюваних і дають відповідь з високою ймовірністю (причому, жертвуючи часом, можна домогтися ... Вікіпедія
Програмовані алгоритми - Службовий список статей, створений для координації робіт з розвитку теми. Дане попередження не встановлюють нові ... Вікіпедія