مبحث تحلیل الگوریتم‌ها به تعیین میزان منابعی که برای اجرای هر الگوریتم نیاز است اشاره دارد. در این زمینه منابع ارزشمندی مثل زمان، حافظه، پهنای باند ارتباطی یا سخت‌افزار مورد بحث قرار می‌گیرند…

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

نظریه پیچیدگی محاسباتی چیست؟

نظریه پیچیدگی محاسباتی (Computational complexity theory) شاخه‌ای از نظریه محاسبات، علوم نظری رایانه و ریاضی است که به بررسی دشواری حل مسائل توسط الگوریتم می‌پردازد. هنگامی که یک الگوریتم خاص را تحلیل می‌کنیم، پیچیدگی زمانی (یا حافظه‌ای) یا مرتبه پیچیدگی زمانی آن را تعیین می‌کنیم. عبارت است از مطالعه تمام الگوریتم‌های امکان‌پذیر برای حل یک مسئله مفروض است. در تحلیل پیچیدگی محاسباتی کوشش می‌کنیم تا حد پایینی کارایی همه الگوریتم‌ها را برای یک مسئله مفروض به دست آوریم. تحلیل پیچیدگی محاسباتی را با مطالعه مسئله مرتب‌سازی معرفی می‌کنیم. دو دلیل برای انتخاب مسئله وجود دارد. نخست چند الگوریتم ابداع شده‌اند که مسئله را حل می‌کنند. با مطالعه و مقایسه این الگوریتم‌ها، دیدی از چگونگی انتخاب از میان چند الگوریتم برای یک مسئله و بهبود بخشیدن به یک الگوریتم مفروض به دست می‌آوریم. این نظریه بخشی از نظریه محاسباتی است که با منابع مورد نیاز برای حل یک مسئله سروکار دارد. در نظریه پیچیدگی محاسباتی، برای سادگی کار مسئله‌ها به کلاس‌هایی تقسیم می‌شوند، طوری که مسئله‌های یک کلاس از حیث زمان یا فضای مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اصطلاح کلاس‌های پیچیدگی خوانده می‌شوند.

پیچیدگی زمانی

پیچیدگی زمانی یک مسئله تعداد گام‌های مورد نیاز برای حل یک نمونه از یک مسئله به عنوان تابعی از اندازه ورودی (معمولاً به وسیله تعداد بیت‌ها بیان می‌شود) به وسیله کارآمدترین الگوریتم می‌باشد. برای درک بهتر این مسئله، فرض کنید که یک مسئله با ورودی n بیت در n به توان 2 گام حل شود. در این مثال می‌گوییم که مسئله از درجه پیچیدگی n به توان 2 است. البته تعداد دقیق گام‌ها بستگی به ماشین و زبان مورد استفاده دارد. اما برای صرف‌نظر کردن از این مشکل، نماد O بزرگ (Big O notation) معمولاً بکار می‌رود. اگر یک مسئله پیچیدگی زمانی از مرتبه O ضرب در n به توان 2 روی یک کامپیوتر نمونه داشته باشد، معمولاً روی اکثر کامپیوترهای دیگر نیز پیچیدگی زمانی از مرتبه O ضرب در n به توان 2 خواهد داشت. پس این نشانه به ما کمک می‌کند که صرف نظر از یک کامپیوتر خاص، یک حالت کلی برای پیچیدگی زمانی یک الگوریتم ارائه دهیم.

چرا تجزیه و تحلیل نظری الگوریتمی مهم است؟

در تجزیه و تحلیل نظری الگوریتم آنچه مشترک است، برآورد پیچیدگی در معنای تقریبی آن است. به‌عنوان مثال، برآورد تابع پیچیدگی برای ورودی خودسرانه بزرگ. نمادهایی همچون تتا، امگا و لاندا برای این منظور استفاده می‌شوند. به طور مثال گفته می‌شود، جست‌وجوی دودویی برای اجرا به Theta (log n) نیاز دارد. به طور معمول تخمین‌های تقریبی استفاده می‌شوند، زیرا پیاده‌سازی‌های مختلف از همان الگوریتم، ممکن است در کارایی متفاوت باشد. با این حال بازده هر دو، با منطق پیاده‌سازی یک الگوریتم داده شده، ضرب در یک ضریب ثابت به نام ثابت مخفی مرتبط است. در مورد تحلیل الگوریتم باید در مورد موضوعاتی مانند تابع رشد، روش تحلیل الگوریتم‌های ترتیبی و بازگشتی، حل رابطه‌های بازگشتی ساده، همگن و نا همگن و همچنین تحلیل سرشکنی صحبت کرد.

عملکرد الگوریتم چیست؟

در نظریه پیچیدگی محاسباتی، الگوریتم‌ها از حیث کارایی در استفاده از منابعی مانند زمان و فضا (حافظه) مورد بررسی قرار می‌گیرند. در این بررسی آنچه اهمیت دارد میزان زمان و فضای مورد نیاز برای حل یک مسئله خاص نیست بلکه چگونگی افزایش میزان زمان و فضای مورد نیاز با بزرگ شدن ورودی الگوریتم مورد توجه است. به طور مثال، فرض کنید دو الگوریتم A و B برای حل مسئله زیر پیشنهاد شده‌اند.

در این مسئله نقشه یک منطقه شامل شهرهای قرار گرفته در آن منطقه، جاده‌های بین آن‌ها و طول هر جاده و نیز نام دو شهر مبدأ و مقصد داده شده است. هدف پیدا کردن کوتاه‌ترین مسیر از مبدأ به مقصد است. فرض کنید به صورت تجربی مشاهده کرده‌ایم که اگر تنها یک شهر به تعداد شهرهای نقشه اضافه شود الگوریتم A به دو برابر زمان برای حل مسئله نیاز دارد در حالی که زمان مورد نیاز برای الگوریتم B وقتی دو برابر می‌شود که تعداد شهرهای نقشه دو برابر شده باشد. بدیهی است که در چنین شرایطی الگوریتم B را بهتر از الگوریتم A می‌دانیم.

در نظریه پیچیدگی محاسباتی نیز همین روش را پی می‌گیریم، اما به جای روش‌های تجربی از روش‌های ریاضی استفاده می‌کنیم. به این منظور ابتدا برای ورودی مسئله یک اندازه تعریف می‌کنیم. این اندازه می‌تواند میزان حافظه مورد نیاز برای ذخیره کردن ورودی مسئله باشد. سپس زمان (یا فضای) مورد نیاز برای حل مسئله توسط یک الگوریتم به صورت تابعی از اندازه مسئله محاسبه می‌شود. به محاسبه یا تقریب زدن این چنین تابعی تحلیل الگوریتم گفته می‌شود.

در تحلیل الگوریتم‌ها بهترین، بدترین و متوسط زمان اجرا بررسی می‌شود. هرچند معمولاً بهترین زمان اجرای آن اهمیت ندارد؛ زیرا اساساً به‌ازای ورودی‌های غیر محتمل این حالت رخ می‌دهد. لیکن لازم است الگوریتم‌ها را در بدترین حالت و در صورت امکان در حالت میانگین تحلیل و بررسی کنیم. ممکن است پیچیدگی الگوریتم در یک حالت میانگین بهتر از پیچیدگی‌اش در بدترین حالت باشد و این اطلاعات مفیدی در مورد آن الگوریتم است.

الگوریتم‌ها به دو دسته تقسیم می‌شوند، بازگشتی و ترتیبی. الگوریتم‌های ترتیبی را معمولاً با شمارش دفعات اجرای دستوری که بر اساس اندازه داده ورودی، بیشترین بار اجرا می‌شود، (در صورتی که زمان اجرای دستور از یک مقدار ثابت تبعیت کند) تحلیل می‌کنیم. اما زمان اجرا و الگوریتم بازگشتی با رابطه‌های بازگشتی بیان می‌شوند. روش‌های مختلفی برای حل این نوع رابطه‌ها داریم. یک روش خوب برای حل رابطه‌های بازگشتی، استفاده از درخت بازگشتی است. این روش نحوه جای‌گذاری یک عبارت بازگشتی و نیز مقدار ثابتی را که در هر سطح از آن عبارت به دست می‌آید، نشان می‌دهد. حاصل جمع مقادیر ثابت تمام سطرها جواب حل بازگشتی است. برای بررسی خوب بودن یک الگوریتم، باید به آهنگ رشد منحنی زمان اجرا – اندازه ورودی یا میزان حافظه مصرفی – اندازه ورودی توجه کنیم. برای بررسی دقیق‌تر به بررسی شاخص‌های تحلیل الگوریتم و تعریف توابع رشد می‌پردازیم.

روش اعتبارسنجی متقابل

اعتبارسنجی متقابل، یک روش ارزیابی مدل است که تعیین می‌نماید نتایج یک تحلیل آماری بر روی یک مجموعه‌داده تا چه اندازه قابل تعمیم و مستقل از داده‌های آموزشی است. این روش به طور ویژه در کاربردهای پیش‌بینی مورد استفاده قرار می‌گیرد تا مشخص شود مدل موردنظر تا چه اندازه در عمل مفید خواهد بود. به طور کلی یک دور از اعتبارسنجی ضربدری شامل افراز داده‌ها به دو زیرمجموعه مکمل، انجام تحلیل بر روی یکی از آن زیرمجموعه‌ها (داده‌های آموزشی) و اعتبارسنجی تحلیل با استفاده از داده‌های مجموعه دیگر است (داده‌های اعتبارسنجی یا آزمایش). برای کاهش پراکندگی، عمل اعتبارسنجی چندین بار با افرازهای مختلف انجام و از نتایج اعتبارسنجی‌ها میانگین گرفته می‌شود. در اعتبارسنجی متقابل K لایه، داده‌ها به K زیرمجموعه افراز می‌شوند. از این K زیرمجموعه، هر بار یکی برای اعتبارسنجی و K-1 دیگر برای آموزش بکار می‌روند. این روال K بار تکرار می‌شود و همه داده‌ها دقیقاً یک بار برای آموزش و یک بار برای اعتبارسنجی بکار می‌روند. در نهایت میانگین نتیجه این K بار اعتبارسنجی به‌عنوان یک تخمین نهایی برگزیده می‌شود. به طور معمول از روش اعتبارسنجی پنج لایه یا ده لایه در پژوهش‌های مدل‌سازی و پیش‌بینی استفاده می‌شود.

مسائل محاسباتی

اکثر فرم‌های اعتبارسنجی متقابل، تا زمانی که اجرای روش پیش‌بینی مورد مطالعه موجود باشد، آسان است. به طور خاص، روش پیش‌بینی می‌تواند یک ” جعبه سیاه ” باشد – نیازی به دسترسی داخلی به اجرای آن نیست. اگر روش پیش‌بینی هزینه‌بر باشد، اعتبارسنجی متقابل می‌تواند بسیار کند باشد چون آموزش باید به طور مکرر انجام شود. در برخی موارد از جمله کمترین مربعات و رگرسیون هسته، اعتبارسنجی متقابل می‌تواند به طور قابل‌توجهی با استفاده از مقادیر خاص از قبل محاسبه شود که در آموزش یا با استفاده از قواعد روزآمدسازی سریع مانند فرمول شر من – موریسون نیز مورد نیاز هستند. هدف از اعتبارسنجی، تخمین سطح مورد انتظار تناسب یک مدل به مجموعه‌ داده است که مستقل از داده‌هایی است که برای آموزش مدل به کار رفته ‌است. این روش می‌تواند برای تخمین هر نوع اندازه‌گیری کمی مناسب که برای داده‌ها و مدل مناسب است، استفاده شود. برای مثال، برای مشکلات طبقه‌بندی دوتایی (Binary classification)، هر مورد در مجموعه اعتبارسنجی به‌درستی یا نادرستی پیش‌بینی می‌شود. در این شرایط نرخ خطای طبقه‌بندی را می‌توان برای خلاصه کردن تناسب مورد استفاده قرار داد، اگرچه اقدامات دیگری مانند ارزش پیش‌بینی‌کننده مثبت نیز می‌تواند مورد استفاده قرار گیرد. هنگامی که مقدار پیش‌بینی‌شده به طور پیوسته توزیع می‌شود، خطای میانگین مربعات، خطای جذر میانگین مربعات یا میانه قدر مطلق انحراف می‌تواند برای خلاصه کردن خطاها به کار رود. از آنجا که ترتیب داده‌ها مهم است، اعتبارسنجی متقابل ممکن است برای مدل‌های سری‌های زمانی مشکل‌ساز باشد. یک رویکرد مناسب می‌تواند استفاده از زنجیره‌سازی جلوسو باشد. زنجیره‌سازی جلوسو (Forward chaining) یکی از دو روش استنتاج منطقی در موتور استنتاج است. روش دیگر زنجیره‌سازی عقب سو است. در این روش برای اثبات یک گزاره سعی می‌شود که تمام پیش شرط‌های آن با استفاده از پایگاه دانش اثبات شود.

منبع: مجله شبکه

دوره آموزشی مهندسی شبکه