Проблема вибору

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Проблема вибору має тільки два можливих виходи, так чи ні (або 1 чи 0) для будь-якого входу.

У теорії обчислень і теорії складності обчислень, проблема вибору або задача про приймання рішень це запитання в деякій формальній системі з відповіддю так або ні, залежно від значення деяких вхідних параметрів. Наприклад, «дані два числа x і y, чи ділиться x на y без залишку?» — проблема вибору. Відповідь може бути або 'так' або 'ні', і залежить від значень x і y.

Метод розв'язання проблеми вибору даний у формі алгоритму називається алгоритмом вибору, алгоритмом приймання рішень або розв'язувальною процедурою для цієї проблеми. Розв'язувальна процедура для проблеми вибору «дані два числа x і y, чи x ділиться на y без залишку?» має надати покроковий набір дій для визначення чи ділиться x на y без залишку для даних x і y. Одним з таких алгоритмів є ділення в стовпчик. Якщо залишок нуль, тоді відповідь 'так' інакше 'ні'. Проблема вибору, яка може бути розв'язана за допомогою алгоритму, такого як в цьому прикладі, зветься розв'язною.

Теорія складності обчислень розрізняє розв'язні проблеми вибору за складністю їхнього розв'язання. «Складний», у цьому значені, описаний в термінах обчислювальних ресурсів потрібних найефективнішому алгоритму для певної проблеми. Теорія обчислень, тим часом, розрізняє нерозв'язні проблеми вибору за степенем Тюрінга, який є мірою неров'язності властивої будь-якому розв'язку.

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

Література[ред.ред. код]

  • Kozen, D.C. (1997), Automata and Computability, Springer.
  • Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
  • Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
  • Robert I. Soare (1987), Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0-387-15299-7
  • Daniel Kroening & Ofer Strichman, Decision procedures, Springer, ISBN 978-3-540-74104-6
  • Aaron Bradley & Zohar Manna, The calculus of computation, Springer, ISBN 978-3-540-74112-1