Вычислительная задача
- Вычислительная задача — это задача, решаемая с помощью алгоритма.
- Примеры вычислительных задач: факторинг, разложение на множители, проверка на примитивность, факторинг, подсчет голосов, оптимизация, функциональная проблема, проблема с обещаниями.
- Вычислительные задачи являются основным объектом изучения в теоретической информатике.
- Теория сложности вычислений определяет объем ресурсов, необходимых для решения задачи, и объясняет неразрешимость некоторых проблем.
- Вычислительные задачи относятся к классам сложности, определяющим ресурсы, необходимые для их вычисления с помощью различных абстрактных машин.
- Примеры классов сложности: P, BPP, BQP.
- Сложность задачи определяется длиной входного представления.
- Типы вычислительных задач: принятие решения, поиск, подсчет голосов, оптимизация, функциональная проблема, проблема с обещаниями.
Полный текст статьи: