طراحی و تحلیل الگوریتم ها:
هر دستوالعملی که مراحل مختلف انجام کاری را به زبان دقیق و با جزئیات کافی بیان نماید به طوریکه ترتیب مراحل و شرط خاتمه عملیات در آن کاملا مشخص باشد الگوریتم نام دارد.
مطالعه الگوریتم ها در برگیرنده موارد زیر است:
- طراحی الگوریتم
- معتبر سازی یا اثبات درستی الگوریتم
- بیان یا پیاده سازی الگوریتم
- تحلیل الگوریتم
که در این کتاب ما موارد اول و چهارم را مورد بررسی قرار میدهیم.
مروری بر روش های مرتب سازی و پیچیدگی آنها ـ مرتب سازی درجی (Insertion Sort):
در مرحله j ام این الگوریتم فرض بر این است که عناصر اول تا ۱- j- ام آرایه مرتب هستند و نصر j ام در عناصر قبل از خود در محل مناسب درج میشود. حال به ازای j از ۲ تا n این عمل انجام می شود.
فهرست مطالب:
- پیش گفتار
- یادآوری
- مروری بر روش های مرتب سازی و پیچیدگی آنها
- مرتب سازی درجی (Insertion Sort)
- الگوریتم مرتب سازی ادغامی (Merge Sort)
- مرتب سازی سریع (Quick Sort)
- مرتب سازی توده ای (Heap Sort)
- درخت پوشای مینیمم
- الگوریتم راشال (Kruskal)
- الگوریتم پریم (Prim)
- پیمایش و جستجوی گراف ها
- جستجو و پیمایش عمقی (DFS)
- جستجو و پیمایش ردیفی (BFS)
- تحلیل الگوریتم ها
- نمادهای مجانبی
- تحلیل حالت متوسط الگوریتم
- روابط بازگشتی
- روابط بازگشتی درجه ۱
- روابط بازگشتی درجه ۲ (همگن)
- قضیه اصلی (Master Theorem)
- روش حریصانه (Greedy)
- مسأله کوله پشتی ساده یا کسری (Knapsack)
- مسئله ادغام دودویی و بهینه فایل ها (یا آرایه های مرتب)
- کدینگ Huffman
- درخت پوشای مینیم
- الگوریتم راشال (kruskal)
- الگوریتم Prim
- مقایسه الگوریتم Kruskal و تعداد درخت های پوشای Kn
- کوتاهترین مسیرهای هم مبدا
- انتخاب بهینه فعالیت ها (Activity Selection)
- روش تقسیم و حل (Divide & Conquer)
- محاسبه عنصر کمینه و بیشینه یک آرایه
- ضرب دو ماتریس به روش استراسن (Strassen)
- تعیین نزدیکترین زوج نقاط
- تعیین نزدیکترین زوج نقاط در فضای یک بعدی
- تعیین نزدیکترین زوج نقاط در فضای دو بعدی
- تعاریف و الگوریتم های پایه در هندسه محاسباتی
- تولید پوش محدب (Convex Hull)
- الگوریتم Graham
- الگوریتم Shamos
- روش برنامه سازی پویا (Dynamic Programming)
- مسئله کوله پشتی ۰/۱
- مسئله همه کوتاهترین مسیرها (APSP)
- عدد کاتلان (Catalan Number) و مسائل وابسته
- ضرب زنجیره ای و بهینه ماتریس ها
- مثلث بندی بهینه چند ضلعی محدب
- طولانی ترین زیر دنباله مشترک (LCS)
- فروشنده دوره گرد
- روش عقبگرد (Backtracking)
- مولد ترکیبات
- مسئله n وزیر
- تعیین نقاط روی محور x ها از روی فواصل آنها
- روش انشعاب و تحدید (Branch & Bound)
- فروشنده دوره گرد
- جمع زیر مجموعه های یک مجموعه
- پیچیدگی محاسبات
- مسئله تا کردن خط کش
- مسئله افراز (PARTITION)
- منابع و مراجع