Відмінності між версіями «* Алгоритмічно нерозв'язні задачі»
Анюта (обговорення • внесок) |
Анюта (обговорення • внесок) |
||
| (не показано одну проміжну версію цього учасника) | |||
| Рядок 1: | Рядок 1: | ||
| − | <center><h2>'''''Проблема розв’язності''''' (зависання)</h2></center> | + | <center><h2>'''''Проблема розв’язності''''' (зависання)</h2></center> [[Файл:Cer.jpeg|right|200px]] |
В теорії обчислювальності існує проблема зависання (обчислювальності): дано опис алгоритму та початкові вхідні дані, необхідно визначити, чи може алгоритм з цими вхідними даними завершитися коли-небудь. Альтернативою зупинки є ситуація, коли робота алгоритму не припиняється (він зависає). | В теорії обчислювальності існує проблема зависання (обчислювальності): дано опис алгоритму та початкові вхідні дані, необхідно визначити, чи може алгоритм з цими вхідними даними завершитися коли-небудь. Альтернативою зупинки є ситуація, коли робота алгоритму не припиняється (він зависає). | ||
| Рядок 38: | Рядок 38: | ||
Математиками доведено, що такого алгоритму не існує, тобто загальний метод визначення цілих коренів рівняння P=0 по цілочисельним коефіцієнтам многочлену відсутній. | Математиками доведено, що такого алгоритму не існує, тобто загальний метод визначення цілих коренів рівняння P=0 по цілочисельним коефіцієнтам многочлену відсутній. | ||
| − | [ | + | [https://docs.google.com/open?id=0B3HPVDhR3f2scnkxX0VpcUxFaWM Алгоритмізація] |
Поточна версія на 18:23, 29 жовтня 2012
Проблема розв’язності (зависання)
В теорії обчислювальності існує проблема зависання (обчислювальності): дано опис алгоритму та початкові вхідні дані, необхідно визначити, чи може алгоритм з цими вхідними даними завершитися коли-небудь. Альтернативою зупинки є ситуація, коли робота алгоритму не припиняється (він зависає). Машина Т‘юринга не може бути використана для вирішення проблеми зависання будь-якого алгоритму. Тому подібна задача відноситься до алгоритмічно нерозв‘язних задач
Алгоритмічно нерозв’язні задачі
Алгоритмічна нерозв‘язність – важлива властивість деяких класів коректно поставлених задач, які допускають використання алгоритмів, яка полягає в тому, що задачі кожного із цих класів в принципі не мають якого-небудь загального універсального алгоритму вирішення, що об‘єднує весь клас.
Незважаючи на повну однотипність умов та вимог для подібних задач не існує єдиного алгоритму вирішення.
Однак це не означає, що подібні задачі не можуть бути вирішені в принципі, просто для їх вирішення необхідно використовувати різні підходи, нерідко творчі і нетрадиційні.
Приклад алгоритмічно нерозв‘язної задачі: виявлення «мертвого коду».
Проблема відсутності загального методу вирішення задачі
Ця проблема визначає певний клас алгоритмічно нерозв‘язних задач, приклади:
1. Розподіл дев‘яток у запису числа π:
Визначимо функцію f(n) = i, де n – кількість цифр ―9‖ підряд у десятковому запису числа π, а i – номер найбільш лівої дев‘ятки із n тих, що йдуть підряд, наприклад: π =3,141592…; f(1) = 5 Задача полягає у визначенні f(n) для довільного n. Оскільки число π є ірраціональним і трансцендентним, то ми не знаємо жодної інформації про розподіл дев'яток (так само як і будь-яких інших цифр) в десятковому записі числа. Обчислення f (n) пов'язане з обчисленням наступних цифр у розкладі π, до тих пір, поки ми не виявимо n дев'яток поспіль, однак у нас немає загального методу обчислення f (n), тому для деяких n обчислення можуть тривати нескінченно - ми навіть не знаємо в принципі (за природою числа π) чи існує рішення для всіх n.
2. Обчислення досконалих чисел
Досконалі числа – це числа, які дорівнюють сумі своїх дільників, наприклад: 28 = 1+2+4+7+14. Визначимо функцію S (n) = n-е за рахунком досконале число і поставимо задачу обчислення S (n) по довільно заданому n. Немає загального методу обрахунку досконалих чисел, невідомо навіть, чи множина досконалих чисел обраховна, чи ні, тому алгоритм має перебирати усі числа підряд, перевіряючи їх досконалість. Відсутність загального методу вирішення не дозволяє відповісти на питання про проблему зупинки: якщо ми перевірили M чисел під час пошуку n-го досконалого числа, чи може це означати, що його взагалі не існує?
3. Десята проблема Гільберта
Нехай задано многочлен n-го ступеня з цілими коефіцієнтами – P, чи існує алгоритм, який визначає, чи існує розв‘язок рівняння P = 0 в цілих числах? Математиками доведено, що такого алгоритму не існує, тобто загальний метод визначення цілих коренів рівняння P=0 по цілочисельним коефіцієнтам многочлену відсутній.
