Вычислительный ресурс

В теории сложности вычислений — вычислительный ресурс это ресурс, используемый некоторыми вычислительными моделями при решении вычислительных задач .

Простейшими вычислительными ресурсами являются время вычислений (количество шагов, необходимых для решения задачи) и объем памяти ( объем памяти, необходимый для решения задачи), но были определены и многие более сложные ресурсы. ^{[ нужна ссылка ]}

Вычислительная задача, как правило, ^{[ нужна ссылка ]} определяется с точки зрения его действия на любой допустимый входной сигнал. Примерами задач могут быть «данное целое число n , определить, является ли n простым» или «данные два числа x и y , вычислить произведение x * y ». По мере увеличения входных данных количество вычислительных ресурсов, необходимых для решения проблемы, будет увеличиваться. Таким образом, ресурсы, необходимые для решения проблемы, описываются с точки зрения асимптотического анализа путем определения ресурсов как функции длины или размера входных данных. Использование ресурсов часто частично определяется количественно с использованием нотации Big O.

Вычислительные ресурсы полезны, потому что мы можем изучить, какие задачи можно решить с использованием определенного количества каждого вычислительного ресурса. Таким образом, мы можем определить, являются ли алгоритмы решения задачи оптимальными, и сделать выводы об эффективности алгоритма . Набор всех вычислительных задач, которые можно решить с использованием определенного количества определенного вычислительного ресурса, представляет собой класс сложности , а отношения между различными классами сложности являются одной из наиболее важных тем теории сложности.

Описание общедоступного компьютерного оборудования [ править ]

Термин «вычислительный ресурс» обычно используется для описания доступного компьютерного оборудования и программного обеспечения. См. «Коммунальные вычисления» .

вычислительных возможностей количественная оценка Формальная

Были предприняты некоторые усилия по формальной количественной оценке вычислительных возможностей. Ограниченная машина Тьюринга использовалась для моделирования конкретных вычислений с использованием количества переходов состояний и размера алфавита для количественной оценки вычислительных усилий, необходимых для решения конкретной проблемы. ^[1]^[2]

Ссылки [ править ]

^ Грегори Дж., Чайтин (1966). «О длине программ для вычисления конечных двоичных последовательностей» (PDF) . Журнал АКМ . 13 (4): 547–569. дои : 10.1145/321356.321363 . S2CID 207698337 . Архивировано из оригинала (PDF) 5 февраля 2007 г. Проверено 25 сентября 2007 г.
^ Соу, Дэби; Элефтериадис, Александрос (1998). «Представление информации с границами вычислительных ресурсов» (PDF) . Сигналы, системы и компьютеры. Протокол конференции тридцать второй конференции Asilomar дальше . Том. 1. С. 452–456. ISBN 0-7803-5148-7 . 10.1109/ACSSC.1998.750904 . Проверено 25 сентября 2007 г.

[1] Грегори Дж., Чайтин (1966). «О длине программ для вычисления конечных двоичных последовательностей» (PDF) . Журнал АКМ . 13 (4): 547–569. дои : 10.1145/321356.321363 . S2CID 207698337 . Архивировано из оригинала (PDF) 5 февраля 2007 г. Проверено 25 сентября 2007 г.

[2] Соу, Дэби; Элефтериадис, Александрос (1998). «Представление информации с границами вычислительных ресурсов» (PDF) . Сигналы, системы и компьютеры. Протокол конференции тридцать второй конференции Asilomar дальше . Том. 1. С. 452–456. ISBN 0-7803-5148-7 . 10.1109/ACSSC.1998.750904 . Проверено 25 сентября 2007 г.

[1]

[2]