سرفصل های درس طراحی الگوریتم

نام بسته درسی : طراحی الگوریتم

——————————

فهرست:

فصل اول:روش های تحلیل الگوریتم                                                                                                               
زمان اجرای الگوریتم ها                                                                                                                               
الگوریتم مرتب سازی                                                                                                                                    
مرتبه اجرای الگوریتم                                                                                                                                  
روشهای تحلیل الگوریتم ها                                                                                                                            
الگوریتم برج هانوی                                                                                                                                   
فصل دوم:روشهای تحلیل الگوریتمهای بازگشتی                                                                                              
الگوریتمهای بازگشتی                                                                                                                                 
محاسبه مقادیر الگوریتم بازگشتی                                                                                                                  
حل تعدادی مثال برای محاسبه الگوریتم‌های بازگشتی                                                                                         
فصل سوم:حل روابط بازگشتی                                                                                                                    
روش حدس و استقرا                                                                                                                                  
روش تکرار با جای گذاری                                                                                                                           
روش اصلی                                                                                                                                              
روش کلی حل رابطه های بازگشتی                                                                                                                
فصل چهارم:روش تقسیم و حل                                                                                                                  
الگوریتم کلی تقسیم و حل                                                                                                                           
جستجوی دودویی                                                                                                                                    
مرتب سازی ادغامی                                                                                                                                   
مرتب سازی سریع                                                                                                                              
الگوریت تقسیم بندی لیست                                                                                                                   
ضرب ماتریس‌ها به روش استراسن                                                                                                           
پیدا کردن ماکزیمم و مینیمم                                                                                                                 
ضرب اعداد صحیح بزرگ                                                                                                                       
فصل پنجم:روش حریصانه                                                                                                                    
الگوریتم کلی حریصانه                                                                                                                          
مسئله خرد کردن پول                                                                                                                         
درخت‌های پوشای مینیمم                                                                                                                     
کوتاه‌ترین مسیرهای تک منبعی                                                                                                              
مسئله کوله‌پشتی                                                                                                                                 
مسئله زمان‌بندی                                                                                                                                
فشرده سازی کدها – الگوریتم ضمن                                                                                                        
الگوریتم الگوریتم تولید کد هافمن                                                                                                            
فصل ششم:برنامه نویسی پویا                                                                                                                
برنامه‌نویسی پویا و مسائل بهینه‌سازی                                                                                                        
زنجیره ضرب ماتریس‌ها                                                                                                                        
محاسبه ترکیب K مؤلفه‌ از n مولفه (محاسبه ضریب چند جمله‌ا‌ی)                                                                    
الگوریتم فلوید (Floyd) برای کوتاه‌ترین مسیر                                                                                            
درخت‌های جستجوی دودویی بهینه                                                                                                          
مسأله کوله‌پشتی صفر و یک                                                                                                                  
فصل هفتم:تکنیک عقب گرد                                                                                                                 
معرفی تکنیک عقبگرد با استفاده از مثال ساده 4 وزیر                                                                                   
مسأله n وزیر                                                                                                                                     
مسأله حاصل جمع زیرمجموعه‌ها                                                                                                            
رنگ‌آمیزی گراف                                                                                                                                 
مساله مدارهای هامیلتونی                                                                                                                            

فصل هشتم:انشعاب و تحدید                                                                                                                   
روش پیمایش درخت (یا گراف)                                                                                                               
حل مسأله فروشنده دوره‌گرد با استفاده از روش انشعاب و تحدید                                                                      
فصل نهم:مسایل رام نشدنی                                                                                                                   
مسائل رام‌نشدنی                                                                                                                                
نظریه‌NP                                                                                                                                          
کلاس (Polynomia)
کلاسNP                                                                                                                                        

بخش هایی از بسته درسی طراحی الگوریتم

مقدمه

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

1-1 زمان اجرای الگوریتم ها

حال مسئله را به طور دقیق بررسی می‌کنیم. می‌خواهیم بدانیم که نقش الگوریتم در زمان اجرا چه تأثیری دارد.

همانطور که می‌دانیم الگوریتم عبارت است از:

مجموعه‌ای از دستورات و دستورالعمل‌ها برای حل مسئله، که شرایط زیر را باید دارا باشد:

• دقیق باشد.
• مراحل آن به ترتیب انجام پذیرد
• پایان پذیر باشد.

الگوریتم‌ها، توسط زبان‌های برنامه‌نویسی پیاده‌سازی می‌شوند. و هر الگوریتم توسط یک برنامه (Program) ارائه می‌شود (یا هر زبان برنامه نویسی).

هر برنامه نیز مثل الگوریتم زمان اجرای خاص خود را دارد. بحث را از عوامل دخیل در زمان اجرای برنامه شروع می‌کنیم.

عوامل دخیل در زمان اجرای برنامه عبارتند از:

• سرعت سخت افزار
• نوع کامپایلر
• اندازه داده ورودی
• پیچیدگی زمانی الگوریتم
• پارامترهای دیگر که تأثیر ثابت در زمان اجرا دارند.

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

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

برای بررسی یک الگوریتم تابعی به نام T (n) که تابع زمانی الگوریتم نامیده می شود، در نظر می گیریم.  که در آن n اندازۀ ورودی مسئله است. مسئله ممکن است شامل چند دادۀ ورودی باشد. به عنوان مثال اگر ورودی یک گراف باشد علاوه بر تعداد راس‌ها (n) تعداد یال‌ها (m) هم یکی از مشخصه‌های دادۀ ورودی می‌باشد. در این صورت زمان اجرای الگوریتم را با T (n,m) نمایش می‌دهیم، در صورتی که تعداد پارامترها بیشتر باشند، آن‌هایی که در اهمیت بیشتری در زمان اجرا دارند، را در محاسبات وارد می‌کنیم و از بقیه صرف نظر می‌کنیم.

برای محاسبه تابع T (n) برای یک الگوریتم موارد زیر را باید در محاسبات در نظر بگیریم:

• زمان مربوط به اعمال جایگزینی که مقدار ثابت می‌باشند.
• زمان مربوط به انجام اعمال محاسبات که مقدار ثابتی دارند.
• زمان مربوط به تکرار تعدادی دستور یا دستورالعمل (حلقه ها)
• زمان مربوط به توابع بازگشتی

از موارد ذکر شده در محاسبه زمان T (n) یک الگوریتم محاسبه تعداد تکرار عملیات و توابع بازگشتی، اهمیت ویژه‌ای دارند. و در حقیقت در کل پیچیدگی زمانی مربوط به این دو می‌باشد. بحث را با یک الگوریتم مرتب‌سازی شروع می‌کنیم.

1-1 الگوریتم مرتب سازی Insertion  

مسأله: تابع زیر مربوط به الگوریتم مرتب‌سازی Insertion  را در نظر بگیرید:

ورودی: A یک آرایه

n طول آرایه یا تعداد عناصر آرایه

خروجی: لیست مرتب از داده‌ها (A, n)

همانطور که می‌دانید الگوریتم فوق یک لیست مرتب از داده‌ها، تولید می‌کند. برای محاسبه زمان اجرای تابع Instertion – Sort  نخست به هر یک از دستورات الگوریتم هزینه اجرای آن و نیز تعداد دفعاتی را که آن دستور یا دستورات اجرا می‌شوند، نسبت می‌دهیم.

جدول زیر هزینه‌های مربوط به الگوریتم بالا می‌باشد:

توجه: مقدار  به تعداد ورودی‌ها بستگی دارد.

هزینه کل الگوریتم بالا به صورت زیر می‌باشد:

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

که در آن A ، B و C مقادیر ثابت هستند. حال مقدار ها را برای کامل شدن بحث، بررسی می‌کنیم. می‌دانیم که حداکثر مقدار ، برابر  می‌باشد. بنابراین:

ملاحظه می‌کنید که T (n) با یک چند جمله‌ای درجه دو معادل است. در حالت کلی به بیشترین درجه چند جمله‌ای برای محاسبه پیچیدگی زمانی نیاز خواهیم داشت.

2-1 مرتبه اجرای الگوریتم

در ارزیابی الگوریتم دو فاکتور مهمی که باید مورد توجه قرار گیرد، یکی حافظه مصرفی و دیگری زمان اجرای الگوریتم است. یعنی الگوریتمی بهتر است که حافظه و زمان اجرای کمتری را نیاز داشته باشد. البته غالباً در الگوریتم‌های این کتاب فاکتور مهم‌تر زمان اجرای الگوریتم می‌باشد. برای بررسی محاسبه اجرای الگوریتم‌ها کار را با چند مثال شروع می‌کنیم.

قطعه برنامه زیر را در نظر بگیرید:

در قطعه کد بالا عملیات متفاوتی از جمله جایگزینی، مقایسه و غیره انجام می‌گیرد که هر کدام زمان‌های متفاوتی را برای اجرا شدن نیاز دارند. تابع زمانی قطعه کد بالا را می‌توان به صورت زیر محاسبه کرد:

با توجه به جدول، T (n) برابر است با:

حال C را بیشترین مقدار ، ،  در نظر می گیریم بنابراین:

حال قطعه کد زیر را دو نقطه بگیرید:

تابع زمانی قطعه کد بالا به صورت زیر محاسبه می‌شود:

بنابراین T (n) برابر است با:

C را بیشترین مقدار ، ،  و  در نظر می‌گیریم بنابراین خواهیم داشت:

همانطور که مشاهده می‌کنید  برابر با یک چند جمله‌ای از درجه 2، می‌باشد. اگر دقت کنید ضرایب چند جمله‌ای در تعداد تراکم کم، تأثیرگذار هستند. ولی هدف ما از محاسبه مرتبه یک الگوریتم بدست آوردن زمان، در تعداد تکرارهای بزرگ یا خیلی بزرگ می‌باشد. بنابراین در حالت کلی ضرایب، تأثیر چندانی در زمان اجرا ندارند به همین دلیل غالباً از آن‌ها در محاسبات صرف نظر می‌کنند.

برای بررسی کارایی الگوریتم‌ها، نمادهایی معرفی شده است که در زیر آن‌ها را بررسی می‌کنیم.

1-2- 1 نماد Big- oh

برای بررسی میزان رشد توابع نماد Big-oh را به کار می‌گیرند.

تعریف: گوئیم  اگر و فقط اگر ثابت C و ثابت صحیح  وجود داشته باشند که برای همه مقادیر  ، داشته باشیم  (رابطه  را بخوانید T(n) متعلق به اوی بزرگ g (n)).

تعریف بالا به صورت زیر نیز بیان می‌شود:

 به طوریکه  

در تعریف بالا T (n) زمان اجرای الگوریتم را مشخص می‌کند و تابعی از اندازه داده‌ها می‌باشد.

در حالت کلی F (n) مرتبه زمانی اجرای الگوریتم نامیده می‌شود. (اصطلاحاً پیچیدگی زمانی الگوریتم هم گفته می‌شود) که با O(F(n)) نمایش داده می‌شود.

T(n) مربوط به قطعه کد بالا که برابر بود با:

را در نظر بگیرید C زمان اجرای عملیات، یک مقدار ثابت است با فرض 1=C خواهیم داشت (قبلاً اشاره شد که C به نوع سخت افزار، زبان برنامه نویسی و غیره بستگی دارد):

که در آن  و  می باشد.

2-2-1 نماد Big – Omega

تعریف: گوییم  اگر و فقط اگر ثابت صحیح C و  وجود داشته باشد که به ازای همه مقادیر  داشته باشیم  (رابطه  را بخوانید T(n) امگای بزرگ (g(n)).

تعریف بالا را به صورت زیر نیز ارائه می‌دهند:

اگر دقت کنید ملاحظه می‌کنید که تعریف بالا یک کران پایین زمان اجرا برای T(n) ارائه می‌دهد. در حالت کلی می‌توان گفت که  بهترین حالت اجرا برای یک الگوریتم می‌باشد.

برای مشاوره اینجا بزنید