منبع رایانشی

در نظریه پیچیدگی محاسباتی، منبع رایانشی، منبعی است که توسط مدل‌های محاسباتی برای حل مسئله محاسباتی استفاده می‌شود.

ساده‌ترین منابع رایانشی عبارتند از زمان اجرای الگوریتم، تعداد گام‌های لازم برای حل مسئله، و فضای حافظه، فضای حافظه‌ای لازم برای حل مسئله.

با استفاده از مفهوم منابع رایانشی می‌توان گفت کدام مسئله با مقدار معینی از هر کدام از منابع رایانشی حل می‌شود. در اینصورت می‌توان گفت کدام الگوریتم برای حل مسئله بهینه است و چقدر کاراست. مجموعه از مسئله محاسباتی ای که با استفاده از مقدار معینی از منابع رایانشی قابل حل اند، رده پیچیدگی نامیده می‌شوند و رابطه بین کلاس‌های پیچیدگی یکی از مهمترین موضوع‌های نظریه پیچیدگی است.[1][2]

منابع

Gregory J., Chaitin (1966). "On the Length of Programs for Computing Finite Binary Sequences" (PDF). Journal of the ACM (JACM). 13 (4): 547–569. doi:10.1145/321356.321363. Archived from the original (PDF) on 5 February 2007. Retrieved 2007-09-25.
Sow, Daby; Eleftheriadis, Alexandros (1998). "Representing Information with Computational Resource Bounds" (PDF). Signals, Systems & Computers. Conference Record of the Thirty-Second Asilomar. Volume 1. pp. 452–456. ISBN 0-7803-5148-7. 10.1109/ACSSC.1998.750904. Retrieved 2007-09-25.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Gregory J., Chaitin (1966). "On the Length of Programs for Computing Finite Binary Sequences" (PDF). Journal of the ACM (JACM). 13 (4): 547–569. doi:10.1145/321356.321363. Archived from the original (PDF) on 5 February 2007. Retrieved 2007-09-25.

[2] Sow, Daby; Eleftheriadis, Alexandros (1998). "Representing Information with Computational Resource Bounds" (PDF). Signals, Systems & Computers. Conference Record of the Thirty-Second Asilomar. Volume 1. pp. 452–456. ISBN 0-7803-5148-7. 10.1109/ACSSC.1998.750904. Retrieved 2007-09-25.