 | Эта статья требует дополнительных ссылок для проверки . ( сентябрь 2007 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) |
В теории сложности вычислений , вычислительный ресурс представляет собой ресурс , используемый некоторые вычислительные модели в решении вычислительных задач .
Простейшие вычислительные ресурсы - это время вычислений , количество шагов, необходимых для решения проблемы, и объем памяти , объем памяти, необходимый для решения проблемы, но были определены гораздо более сложные ресурсы. [ необходима цитата ]
Вычислительная проблема , как правило , [ править ] определяется в терминах его действия на любой действительный вход. Примеры проблем могут быть такими: «дать целое число n , определить, является ли n простым», или «учитывая два числа x и y , вычислить произведение x * y ». По мере увеличения входных данных увеличивается количество вычислительных ресурсов, необходимых для решения проблемы. Таким образом, ресурсы, необходимые для решения проблемы, описываются в терминах асимптотического анализа путем определения ресурсов как функции длины или размера входных данных. Использование ресурсов часто частично количественно определяется с использованием нотации Big O.
Вычислительные ресурсы полезны, потому что мы можем изучить, какие проблемы могут быть вычислены в определенном количестве каждого вычислительного ресурса. Таким образом, мы можем определить, являются ли алгоритмы для решения проблемы оптимальными, и мы можем сделать выводы об эффективности алгоритма . Набор всех вычислительных задач, которые могут быть решены с использованием определенного количества определенных вычислительных ресурсов, представляет собой класс сложности , а отношения между различными классами сложности являются одной из наиболее важных тем в теории сложности.
Описание общедоступного вычислительного оборудования [ править ]
Термин «вычислительный ресурс» обычно используется для описания доступного вычислительного оборудования и программного обеспечения. См. Коммунальные вычисления .
Формальная количественная оценка вычислительной мощности [ править ]
Были предприняты некоторые усилия для формальной количественной оценки вычислительных возможностей. Ограниченная машина Тьюринга использовалась для моделирования конкретных вычислений с использованием количества переходов между состояниями и размера алфавита для количественной оценки вычислительных усилий, необходимых для решения конкретной проблемы. [1] [2]
Ссылки [ править ]
- ↑ Грегори Дж., Чайтин (1966). «О длине программ для вычисления конечных двоичных последовательностей» (PDF) . Журнал ACM . 13 (4): 547–569. DOI : 10.1145 / 321356.321363 . Архивировано из оригинального (PDF) 05 февраля 2007 года . Проверено 25 сентября 2007 .
- ^ Соу, Даби; Элефтериадис, Александрос (1998). «Представление информации с ограничениями вычислительных ресурсов» (PDF) . Сигналы, системы и компьютеры. Отчет о Тридцать второй конференции Асиломар на . Том 1. С. 452–456. ISBN 0-7803-5148-7. 10.1109 / ACSSC.1998.750904 . Проверено 25 сентября 2007 .
|volume=есть дополнительный текст ( справка )
