فهرست مطالب كتاب

فهرست مطالب
پيش‌گفتار مترجمان 1
پيش‌گفتار 5
تقدير و تشكر 8
فصل 1: آشنايي 11
قراردادهاي كتاب در توصيف الگوريتم‌ها 15
تمرين‌ها 15
فصل 2: استقراي رياضي 21
2-1 آشنايي 21
2-2 سه مثال ساده 23
2-3 شمارش ناحيه‌هاي يك صفحه 25
2-4 يك مسأله‌ي رنگ‌آميزي ساده 27
2-5 مسأله‌اي پيچيده‌تر درباره‌ي حاصل‌جمع 28
2-6 يك نامساوي ساده 29
2-7 رابطه‌ي اويلر 30
2-8 مسأله‌اي از نظريه‌ي گراف 32
2-9 كدهاي Gray ص 33
2-10 يافتن مسيرهايي با يال‌هاي «دو به دو جداازهم» در يك گراف 37
2-11 رابطه‌ي بين ميانگين‌هاي حسابي و هندسي 39
2-12 مثالي از قانون ثابت حلقه در تبديل عددي ده‌دهي به عددي دودويي 41
2-13 لغزش‌هاي رايج در استقرا 43
2-14 خلاصه 45
مراجعي براي مطالعه‌ي بيش‌تر 46
تمرين‌ها 47
فصل 3: تحليل الگوريتم‌ها 55
3-1 آشنايي 55
3-2 نماد O ص 57
نماد OO ص 60
3-3 پيچيدگي فضايي (حافظه‌ي مورد نياز) و پيچيدگي زماني 61
3-4 محاسبه‌ي حاصل‌جمع‌ها 62
3-5 رابطه‌هاي بازگشتي 66
3-5-1 حدس‌هاي هوشمندانه 66
3-5-2 روابط «تقسيم‌وحل» 70
3-5-3 روابط بازگشتي با حافظه‌ي كامل 72
3-6 چند رابطه‌ي سودمند 74
3-7 خلاصه 75
مراجعي براي مطالعه‌ي بيش‌تر 76
تمرين‌هاي آموزشي 76
تمرين‌هاي خلاقانه 78
فصل 4: نگاهي کوتاه به ساختمان‌هاي داده‌اي 81
4-1 آشنايي 81
4-2 ساختمان‌هاي داده‌اي پايه 82
4-2-1 عناصر 82
4-2-2 آرايه‌ها 83
4-2-3 رکوردها 84
4-2-4 ليست‌هاي پيوندي 85
4-3 درخت‌ها 86
4-3-1 شيوه‌ي ذخيره‌ي درخت 88
4-3-2 درخت‌هاي هرمي 89
4-3-3 درخت‌هاي دودويي جست‌وجو 92
درخت جست‌وجو 93
عمل درج 94
عمل حذف 95
4-3-4 درخت‌هاي AVL ص 97
4-4 درهم‌سازي 100
توابع درهم‌ساز 102
چاره‌جويي براي حل مشكل برخورد 102
4-5 مسأله‌ي union-find ص 104
4-6 گراف‌ها 107
4-7 خلاصه 109
مراجعي براي مطالعه‌ي بيش‌تر 110
تمرين‌هاي آموزشي 111
تمرين‌هاي خلاقانه 112
فصل 5: طراحي استقرايي الگوريتم‌ها 117
5-1 آشنايي 117
5-2 محاسبه‌ي مقدار چندجمله‌اي‌ها 118
5-3 بزرگ‌ترين زيرگراف القايي 120
5-4 يافتن نگاشت‌هاي يك‌به‌يك 123
5-5 مسأله‌ي ستاره‌ي مشهور 125
5-6 نمونه‌اي از يك الگوريتم تقسيم‌وحل: مسأله‌ي نماي افقي 129
5-7 محاسبه‌ي عامل‌هاي توازن در درخت‌هاي دودويي 132
5-8 يافتن بزرگ‌ترين زيردنباله‌ي متوالي يا به‌هم‌پيوسته 133
5-9 تقويت فرض استقرا 135
5-10 نمونه‌اي از برنامه‌نويسي پويا: مسأله‌ي کوله‌پشتي 136
5-11 اشتباهات رايج 139
5-12 خلاصه 141
مراجعي براي مطالعه‌ي بيش‌تر 142
تمرين‌هاي آموزشي 143
تمرين‌هاي خلاقانه 144
فصل 6: الگوريتم‌هاي دنباله‌ها و مجموعه‌ها 149
6-1 آشنايي 149
6-2 جست‌وجوي دودويي و گونه‌هايي از آن 150
جست‌وجوي دودويي محض 150
جست‌وجو‌ي دودويي در يک دنباله‌ي چرخشي 151
جست‌وجوي دودويي به دنبال يك انديس ويژه 152
جست‌وجوي دودويي در دنباله‌هايي با اندازه‌هاي نامشخص 153
مسأله‌ي زيردنباله‌ي ناپايدار 154
حل معادله‌ها 155
6-3 جست‌وجو با درون‌يابي 156
6-4 مرتب‌سازي 158
6-4-1 مرتب‌سازي سطلي و مرتب‌سازي بر اساس مرتبه 158
6-4-2 مرتب‌سازي درجي و مرتب‌سازي با انتخاب 162
6-4-3 مرتب‌سازي ادغامي 163
6-4-4 مرتب‌سازي سريع 166
6-4-5 مرتب‌سازي هرمي 171
روش ساخت heap يا هرم 172
6-4-6 حد پايين مرتب‌سازي 175
6-5 مرتبه‌ي آماري 178
6-5-1 بيشينه و کمينه‌ي عناصر 178
6-5-2 يافتن آماري kام يک دنباله 179
6-6 فشرده‌سازي داده‌ها 181
6-7 تطابق رشته‌اي 185
6-8 مقايسه‌ي دنباله‌ها 192
6-9 الگوريتم‌هاي مبتني بر احتمال 196
6-9-1 اعداد تصادفي 198
6-9-2 يک مسأله‌ي رنگ‌آميزي 199
6-9-3 روشي براي تبديل الگوريتم‌هاي مبتني بر احتمال (يا احتمال‌گرا) به الگوريتم‌هاي قطعي 200
6-10 يافتن اکثريت 204
6-11 سه نمونه از روش‌هاي جالب اثبات 207
6-11-1 بلندترين زيردنباله‌ي صعودي (يا افزايشي) 207
6-11-2 يافتن بزرگ‌ترين دو عنصر يک مجموعه 210
6-11-3 پيدا کردن مد در يک مجموعه‌ي چندگانه 212
6-12 خلاصه 215
مراجعي براي مطالعه‌ي بيش‌تر 215
تمرين‌هاي آموزشي 218
تمرين‌هاي خلاقانه 220
فصل 7: الگوريتم‌هاي گراف 231
7-1 آشنايي 231
7-2 گراف‌هاي اويلري 234
7-3 روش‌هاي پيمايش گراف 236
7-3-1 جست‌وجوي نخست-ژرفا 237
گراف‌هاي بدون‌جهت 237
ساخت درخت DFS ص 240
گراف‌هاي جهت‌دار 244
7-3-2 جست‌وجوي نخست-پهنا 246
7-4 ترتيب توپولوژيک 248
7-5 کوتاه‌ترين مسير از يک رأس به رأس‌هاي ديگر 251
حالت بدون‌دور 251
حالت کلي 254
7-6 درخت پوشاي کمينه 259
7-7 کوتاه‌ترين مسيرها بين تمام زوج‌رأس‌هاي گراف 264
7-8 بسط ترايا 267
7-9 شيوه‌هاي تجزيه‌ي گراف 269
7-9-1 مؤلفه‌هاي دوهمبند 270
7-9-2 مؤلفه‌هاي قوياً همبند 280
7-9-3 نمونه‌هايي از کاربرد تجزيه‌ي گراف 287
7-10 تطابق 288
7-10-1 يافتن تطبيق‌هاي کامل در گراف‌هاي بسيار چگال 289
7-10-2 تطابق دوبخشي 290
بهبود الگوريتم 293
7-11 شارهاي شبكه 294
7-12 دورهاي ‌هاميلتوني 300
7-12-1 استقراي معكوس 300
7-12-2 يافتن دورهاي‌ هاميلتوني در گراف‌هاي بسيار چگال 301
7-13 خلاصه 303
مراجعي براي مطالعه‌ي بيش‌تر 304
تمرين‌هاي آموزشي 306
تمرين‌هاي خلاقانه 309
واژه‌نامه‌ي پارسي به انگليسي 329