جزوه مقدمه‌ای بر تحلیل و طراحی الگوریتم

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

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

فهرست مطالب جزوه مقدمه‌ای بر تحلیل و طراحی الگوریتم :

یادآوری

• مروری بر روش‌های مرتب‌سازی و پیچیدگی آنها
• درخت پوشای مینیمم
• پیمایش و جستجوی گراف‌ها

تحلیل الگوریتم‌ها

• نمادهای مجانبی
• تحلیل حالت متوسط الگوریتم
• روابط بازگشتی
• قضیه اصلی (Master Theorem)

روش حریصانه (Greedy)

• مسئله کوله پشتی ساده یا کسری (Knapsack)
• مسئله ادغام دودویی و بهینه فایل‌ها (یا آرایه‌های مرتب)
• کدینگ Huffman
• درخت پوشای مینیمم
• کوتاه‌ترین مسیرهای هم مبدا
• انتخاب بهینه فعالیت‌ها (Activity Selection)

روش تقسیم و حل (Divide and Conquer)

• محاسبه عناصر کمینه و بیشینه یک آرایه
• ضرب دو ماتریس به روش استراسن (Strassen)
• تعیین نزدیک‌ترین زوج نقاط
• تعاریف و الگوریتم‌های پایه در هندسه محاسباتی
• تولید پوش محدب (Convex Hill)

روش برنامه‌سازی پویا (Dynamic Pragramming)

• مسئله کوله پشتی 0/1
• مسئله همه کوتاه‌ترین مسیرها (APSP)
• عدد کاتلان (Catalan Number) و مسائل وابسته
• ضرب زنجیره‌ای و بهینه ماتریس‌ها
• مثلث‌بندی بهینه چندضعلی محدب
• طولانی‌ترین زیردنباله مشترک (LCS)
• فروشنده دوره‌گرد

روش عقب‌گرد (Backtracking)

• مولد ترکیبات
• مسئله n وزیر
• تعیین نقاط روی محور x ها از روی فواصل آنها

روش انشعاب و تحدید (Branch and Bound)

• فروشنده دوره‌گرد
• جمع زیرمجموعه‌های یک مجموعه

پیچیدگی محاسبات

• مسئله تا کردن خط‌کش
• مسئله افراز (Partition)