هرگاه اشتباهي اثرگذار در كتاب بيابيم، آن را در همين بخش از وبلاگ به اطلاع خوانندگان مي‌رسانيم.
اميدواريم شما هم ما را در اين كار ياري كنيد.
صفحه‌ي 17 شكل 1-1: شماره‌ي سطر بين 3 و 5 كه 2 است، به 4 تبديل شود.
صفحه‌ي 22 سطر 12: (x+1) بايد به (x-1) تغيير كند.
صفحه‌ي 31 سطر 7: بهتر است واژه‌ي "گراف" به "نقشه" تبديل شود.
صفحه‌ي 36 سطر 8: لگاريتم‌گيري روي k است نه n.
صفحه‌ي 36 سطر 11: لگاريتم‌گيري روي k است نه n.
صفحه‌ي 40 سطر 6: در سمت چپ =، آخرين انديس 2n است نه n.
صفحه‌ي 50 تمرين 2-27 سطر 2: "هيچ يك از اين سه خط" به "هيچ سه خطي از اين خط‌ها" تغيير كند.
صفحه‌ي 60 سطر 17: nlogn بايد به n/logn تبديل شود.
صفحه‌ي 63 سطر 16: 1.3، 1.2 و 1.6 بايد به ترتيب به 3/1، 2/1 و 6/1 تبديل شوند.
صفحه‌ي 65 مثال 3-3 سطر 3: درون سيگما توان عدد 2 بايد i باشد.
صفحه‌ي 71 سطر 6: لگاريتمي كه توان a است بايد logn باشد نه loga اما پايه‌ي آن، يعني b، درست است.
صفحه‌ي 71 سطر 17: سمت چپ سومين علامت "=" يك علامت "(" از قلم افتاده است.
صفحه‌ي 73 از پايين سطر 4: 1.3+1.2 بايد به 3/1+2/1 تغيير كند.
صفحه‌ي 74 رابطهي 3-27: m به n تبديل شود.
صفحه‌ي 79 تمرين 3-23 سطر 4: علامت "-" بايد به "=" تغيير كند.
صفحه‌ي 79 تمرين 3-25 سطر 2: سمت چپ دومين "+" از چپ، يك علامت "(" از قلم افتاده است.
صفحه‌ي 115 تمرين 4-27 سطر 4: در سيگما، l به 1 تبديل شود.
صفحه‌ي 128 بخش "پيچيدگي" سطر 2: n+1 بايد به n-1 تغيير كند.
صفحه‌ي 155 سطر 10 و 11: بايد واژه‌ي حد به محدوده تبديل شود.
صفحه‌ي 167 سطرهاي 17، 18 و 20: بايد همه‌ي Xها به x تغيير كنند.
صفحه‌ي 168 سطرهاي 2 و 3: بايد هر دو X به x تغيير كنند.
صفحه‌ي 172 سطر 7: لازم است به جاي واژه‌ي شكل، واژه‌ي بخش قرار گيرد.
صفحه‌ي 175 سطر 6: بايد 23 به 32 تبديل گردد.
صفحه‌ي 180 شكل 6-16 نخستين if: به جاي k>0 بايد k>n بيايد.
صفحه‌ي 184 شكل 6-18 نخستين سطر الگوريتم: عبارت "به يك هرم بيفزا" بايد به عبارت "به هرم H بيفزا" تغيير يابد.
صفحه‌ي 194 سطر 4: روشن است كه كاراكتر mامِ B بايد با b كوچك نشان داده شود؛ نه با B بزرگ.
صفحه‌ي 209 سطر 18: در فرض استقرا k بايد از m-1 كوچك‌تر باشد؛ نه بزرگ‌تر.
صفحه‌ي 212 از پايين سطر 2: 6-12 بايد به 6-10 تغيير كند.
صفحه‌ي 218 سطر 14: 6-42 به اشتباه 6-24 درج شده است.
صفحه‌ي 219 تمرين 6-7 سطر 2: شكل 6-12 درست است؛ نه شكل 6-11.
صفحه‌ي 225 سطرهاي 11 و 13: واژه‌هاي نقص و تناقص بايد به ترتيب به نقض و تناقض تغيير كنند.
صفحه‌ي 229 سطر 1: ترتيب هر دو دنباله برعكس است؛ يعني نخست 0 و سپس 2.
صفحه‌ي 247 لم 7-6: درخت BFS درست است.
صفحه‌ي 248 سطر 3: "است" به اشتباه "راست" درج شده است.
صفحه‌ي 250 سطر 7: v.Indegree بايد به w.Indegree تبديل شود.
صفحه‌ي 253 از پايين سطر 2: انتهايي بايد به ابتدايي تغيير كند.
صفحه‌ي 257 مثال 7-1 سطر 2: V بزرگ بايد به v كوچك تبديل شود.
صفحه‌ي 260 از پايين سطر 7: عبارت "كمتر از" حذف گردد.
صفحه‌ي 272 سطر 3: "طور" به اشتباه "طول" درج شده است.
صفحه‌ي 285 سطر 15 : درون الگوريتم، در شرط v.DFS_Number=0، "=" از قلم افتاده است.
۱۳۸۷ مهر ۸, دوشنبه
۱۳۸۷ مهر ۷, یکشنبه
فهرست مطالب كتاب
فهرست مطالب
پيش‌گفتار مترجمان 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
پيش‌گفتار مترجمان 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
۱۳۸۷ مهر ۶, شنبه
معرفي كتاب
طراحي الگوريتم با رويكردي خلاقانه
نوشته‌ي يودي منبر، ترجمه‌ي احمد صادقي صفت و سيد علي حسيني، جلد نخست
شماره‌ي شابك: 6-2278-04-964-978
Introduction to Algorithms
A Creative Approach
Written by Udi Manber, Translated by Ahmad Sadeghi Sefat & Sayed Ali Hosseini
اگرچه اين كتاب بيش‌ترِ مباحث درس طراحي الگوريتم از دوره‌ي كارشناسي رشته‌ي رايانه را پوشش مي‌دهد، اما مخاطبان اصلي آن كساني هستند كه مي‌خواهند خلاقيت خويش را پرورش دهند. از اين رو، خواندن آن به كساني كه قصد شركت در المپياد دانش‌آموزي يا دانش‌جويي رايانه و يا مسابقات برنامه‌نويسي ACM را دارند، سفارش مي‌شود.
متني كه در ادامه مي‌بينيد گوشه‌هايي از كتاب است كه براي آشنايي خوانندگان آورده شده است:
.
.
.
پيش‌گفتار
اين کتاب را نوشتم تا ناکامي‌هايم در بيان روشن الگوريتم‌ها را جبران كنم. همچون بسياری از استادان دريافته بودم، برای برخی دانش‌جويان نه تنها حل مسائل ساده (ساده در نظر من) دشوار است، بلکه آنان از درک راه‌حل‌های عرضه‌شده نيز عاجزند. معتقدم ايجاد و شرح يک راه‌حل، به هم وابسته‌اند و نبايد از يکديگر جدا گردند؛ يعنی برای درک کامل يک راه‌حل، لازم است مراحل منتهی به آن را دنبال کنيم و تنها دقت در راه‌حل نهايی کافی نيست.
.
.
.
مسيرهايی که در اين کتاب عرضه می‌شوند، چندان ساده نيستند. اگرچه اين کتاب روش حل بسياری از مسائل خاص را نشان مي‌دهد، اما تکيه‌اش بر روی اصول و روش‌های کلی است. در نتيجه، کتابی است چالش‌برانگيز که شما را درگير و وادار به انديشيدن می‌کند. ايمان دارم که می‌ارزد در اين راه بيش‌تر تلاش کنيد.
طراحی الگوريتم‌های کارآمد در زمينه‌های گوناگونی مانند رياضيات، آمار، مهندسی و زيست‌شناسی مولکولی بسيار مهم شده است. اين کتاب به بررسی كلي الگوريتم‌ها می‌پردازد. افراد حرفه‌ایِ بسياري از رشته‌ها و حتا دانشمندانی که عميقاً با رايانه درگير نيستند، برنامه‌نويسی را کاری غيرفکری و خسته‌کننده مي‌دانند. گاهی چنين است، اما اين باور سبب عرضه‌ی راه‌حل‌های دم‌دستی، پيش‌پاافتاده و ناکارآمد می‌شود، درحالی‌که راه‌حل‌های دقيق‌تر و کارآمدتری نيز وجود دارند. يکی از اهداف کتاب اين است که خوانندگان خود را قانع کند تفکر الگوريتمی، ديدگاهی دقيق، ظريف و بااهميت در برخورد با مسائل گوناگون به آنان می‌دهد.
کتاب خودکفاست و شيوه‌ی ارائه‌ي آن بيش‌تر شهودی است. نکات فنی هر بحث يا در کم‌ترين حد ممکن بيان شده، يا از بحث اصلی مجزا گشته است؛ به ويژه، جزئيات پياده سازی تا جای ممکن از طراحی الگوريتم جدا شده است. برای تشريح اصولی که کتاب بر آن‌ها تأکيد دارد، مثال‌های ويژه‌ی زيادی طراحی شده‌اند. مطالب کتاب به گونه‌اي نيست که بتوان بر آن‌ها مسلط شد يا آن‌ها را به خاطر سپرد. اين مطالب به صورت مجموعه‌ای از ايده‌های اوليه، مثال‌ها، مثال‌های نقض، تغيير و بهبود در راه‌حل‌ها و ... ارائه شده‌اند. پس از توصيف اکثر الگوريتم‌ها، شبه‌کدهای متناظر با آن‌ها هم آورده شده است. هر فصل با بخشی برای مطالعه‌ي بيش‌تر به همراه مراجع وابسته به آن و تعدادی تمرين پايان مي‌پذيرد. در بيش‌تر فصل‌ها، تمرين‌ها به دو دسته تقسيم می‌شوند: تمرين‌های آموزشی و تمرين‌های خلاقانه. تمرين‌های آموزشی برای ارزيابی استنباط خواننده از مثال‌ها و الگوريتم‌های آن فصل و تمرين‌های خلاقانه برای ارزيابی توانايي خواننده است. تمرين‌هاي خلاقانه به خواننده نشان مي‌دهند كه آيا با روش‌های آن فصل مي‌تواند مسائل تازه را هم حل کند يا نه. خطوط کلی راه‌حل گزيده‌اي از تمرين‌ها (آن‌هايی که زير شماره‌ی‌شان خط کشيده شده) در پايان کتاب آورده شده و خلاصه‌ای از مطالب هر فصل در پايان همان فصل عرضه گرديده است.
سازمان‌دهی کتاب چنين است: فصل‌های 1 تا 4 موضوعات مقدماتی را ارائه می‌کنند. فصل 2 مقدمه‌ای بر استقراي رياضی است. چنان که خواهيم ديد، استقرای رياضی در طراحی الگوريتم بسيار مهم است. به همين دليل، تجربه‌ی اثبات‌های استقرايي در اين راه مفيدند. بدبختانه شمار اندکی از دانش‌جويان علوم رايانه تجربه‌ی کافی در اين کار دارند. ممکن است فصل 2 برای برخی دانش‌جويان دشوار باشد. پيش‌نهاد می‌کنم که بار نخست از مثال‌های مشکل‌تر بگذريد و آن‌ها را بعداً بخوانيد. فصل 3 برای آشنايی با تحليل الگوريتم‌هاست. اين فصل، فرايند تحليل الگوريتم‌ها را شرح مي‌دهد و ابزارهای اساسی لازم را برای تحليل الگوريتم‌های کتاب فراهم مي‌آورد. فصل 4 نگاهی مختصر به ساختمان‌های داده‌ای است. خوانندگانی که با ساختمان‌های داده‌ای پايه آشناترند و دانش رياضی بيش‌تری دارند، می‌توانند خواندن کتاب را مستقيماً از اين فصل شروع کنند (اگرچه خوب است دست‌كم بخش «آشنايي» تمام فصل‌ها را بخوانيد.) فصل 5 ايده‌ی اصلی طراحی الگوريتم‌ها را به کمک مقايسه‌ی آن‌ها با اثبات‌های استقرايی نشان می‌دهد. اين فصل چندين مثال از الگوريتم‌های ساده ارائه می‌كند و شيوه‌ی ساخت آن‌ها را توضيح مي‌دهد. اگر قصد خواندن تنها يك فصل از كتاب را داريد، همين فصل را بخوانيد.
دو روش کلی برای سازمان‌دهی هر کتاب الگوريتم وجود دارد. يک روش بر پايه‌ی موضوع الگوريتم‌هاست؛ مثلاً فصلی برای الگوريتم‌های گراف يا فصلی برای الگوريتم‌های هندسی. راه ديگر بر پايه‌ی روش‌های طراحي است. درست است که اين کتاب بر روش‌های طراحی تکيه مي‌کند، اما من همان روش نخست را برگزيده‌ام و به نظرم اين روش روشن‌تر و آسان‌تر است. فصل‌های 6 تا 9 به ترتيب الگوريتم‌هايی را در چهار مبحث زير ارائه می‌کنند: الگوريتم‌های دنباله‌ها و مجموعه‌ها (مانند مرتب‌سازی، مقايسه‌ی دنباله‌ها، فشرده‌سازی داده‌ها)، الگوريتم‌های گراف (مانند درخت پوشای کمينه، کوتاه‌ترين مسيرها، تطبيق)، الگوريتم‌های هندسی (مانند پوسته‌ي كوژ، يافتن اشتراک دو چند ضلعی) و الگوريتم‌های عددی و جبری (مانند ضرب ماتريس‌ها، محاسبه‌ی سريع تبديل فوريه).
فصل 10 به reduction يا كاهش اختصاص دارد. اگرچه در فصل‌های پيش از آن نمونه‌هايی از كاهش آورده شده است، اما موضوع به قدری مهم و جالب‌توجه است که می‌ارزد يک فصل جداگانه را به آن اختصاص دهيم. اين فصل مقدمه‌ای بر NP-تمام (موضوع فصل 11) نيز هست. NP-تمام (از مباحث نظريه‌ی پيچيدگی) به بخشی جدانشدنی از نظريه‌ی الگوريتم‌ها تبديل شده است. هرکس که دست به طراحی الگوريتم می‌زند، بايد چيزهايی درباره‌ی روش‌های اثبات NP-تمام بودن مسأله‌ها بداند. فصل 12 برای آشنايی با الگوريتم‌های موازی است و چندين الگوريتم جالب را از مدل‌های گوناگون پردازش موازی به خواننده‌ی خود نشان می‌دهد.
.
.
.
فصل 1
آشنايي
«تركيب اجزاء» فرايندي بسيار مهم است، چنان كه برخي آن را شرط لازم‌وكافي براي پيش‌رفت علم مي‌دانند. بي‌ترديد، شرط لازم هست، اما شرط كافي نيست! براي آن‌كه تركيبي از اجزاء سودمند باشد و تلاش فكري‌مان را به هدر ندهد و براي آن‌كه سكوي پرتابي براي رسيدن به چيزهاي برتر شود؛ پيش از همه بايد از وحدتي برخوردار باشد كه ما آن را تنها چند «عنصرِ كنار يكديگر» نبينيم.
Henri Poincaré
نهمين ويرايش از واژه نامه‌ي Webster (واژه‌نامه‌ي دانشگاهي جديدش) الگوريتم را چنين تعريف مي‌كند: «روالي براي حل يك مسأله‌ي رياضي (مانند يافتن بزرگ‌ترين مقسوم عليه مشترك) در مراحلي متناهي كه غالباً شامل تكرار يك عمل مي‌شود» و يا در تعريفي كلي: «روالي گام‌به‌گام براي حل يك مسأله يا دست‌يابي به اهدافي چند». ما از تعريف كلي الگوريتم استفاده خواهيم كرد. طراحي الگوريتم، موضوعي قديمي و ريشه‌دار است. مردم همواره مي‌خواسته‌اند روشي بهتر براي دست‌يابي به اهدافشان داشته باشند؛ چه آناني كه مي‌خواسته‌اند آتش روشن كنند، چه آناني كه اهرام را مي‌ساخته‌اند و چه آناني كه نامه‌ها را مرتب مي‌كرده‌اند. البته مطالعه روي الگوريتم‌هاي رايانه‌اي موضوعي نوين است. برخي الگوريتم‌هاي رايانه‌اي از روش‌هايي بهره مي‌برند كه پيش از اختراع رايانه هم شناخته شده بودند، اما حل بيش‌تر اين مسأله‌ها با رايانه، به شيوه‌هاي نويني نياز دارد؛ براي مثال، اين‌كه به رايانه بگوييم «به آن سوي كوهستان بنگر و چنان‌چه ديدي ارتشي پيش مي‌آيد، فرياد خطر برآور!» كافي نيست. رايانه بايد دقيقاً بداند معناي «نگريستن» چيست، چگونه «ارتش» را تشخيص دهد و چگونه فرياد خطر برآورد. (البته بنا به دلايلي همواره فرياد خطر برآوردن كاري ساده است!) رايانه تنها مي‌تواند دستورالعمل‌هايي خوش تعريف، محدود به اعمال اوليه دريافت كند. ترجمه‌ي دستورالعمل‌هاي معمولي به زباني كه يك رايانه آن‌ها را بفهمد، دشوار است. برنامه‌نويسي، همين فرايند ضروري و دشواري است كه امروزه ميليون‌ها نفر را در سطوح مختلف به خود مشغول كرده است.
.
.
.
از سوي ديگر، الگوريتم‌هايي كه ما در زندگي روزانه با آن‌ها سر و كار داريم، چندان پيچيده نيستند و خيلي هم تكرار نمي‌شوند. پس نمي‌ارزد براي ايجاد يك الگوريتم خوب تلاش زيادي كنيم؛ چراكه بازدهي‌اش اندك است. مثلاً مسأله‌ي خالي كردن كيسه‌هاي خواربار را در نظر بگيريد. قطعاً براي انجام اين كار با توجه به محتويات كيسه‌ها و چيدمان وسيله‌هاي درون آشپزخانه، راه‌هايي با درجات كارآمدي گوناگون وجود دارد. افراد كمي هستند كه حتا به اين مسأله فكر كنند و از بين آن‌ها هم، كمتر افرادي هستند كه الگوريتمي براي اين كار بسازند. به عبارت ديگر، كساني مجبورند روش‌هاي بهتري ايجاد كنند كه در مقياس وسيع تجاري، كار پر و خالي كردن كيسه‌ها را انجام مي‌دهند. مثال ديگر زدن چمن‌هاست. ما مي‌توانيم با كمتر كردن تعداد تغيير مسير هنگام چمن‌زني يا با كمتر كردن زمان چمن‌زني و يا با كمتر كردن مسافت طي‌شده تا سطل زباله، كار را بهتر انجام دهيم. مگر آن‌كه كسي واقعاً از چمن‌زني متنفر باشد وگرنه كسي نيست كه يك ساعت وقت بگذارد تا بفهمد چطور مي‌شود از زمان چمن‌زني يك دقيقه كم كرد! رايانه‌ها مي‌توانند با كارهاي پيچيده دست و پنجه نرم كنند و آن‌ها را بارها و بارها انجام دهند. اينجاست كه مي‌ارزد براي ايجاد روشي بهتر زمان زيادي را صرف كنيم، حتا اگر با اين كار، الگوريتم‌هاي پيچيده‌تري به دست آيد كه فهمشان دشوارتر باشد. (البته در بهينه‌سازي نبايد افراط كرد و به خاطر بهبود چند ثانيه‌اي در كار رايانه، ساعت‌ها وقت برنامه‌نويسان را به هدر داد.)
نياز به روش‌هاي ناملموس در الگوريتم‌هاي حجيم و پيچيدگي احتمالي اين الگوريتم‌ها، نشانگر دشوار بودن يادگيري آنهاست. نخست، بايد درك كنيم كه شيوه‌هاي شهودي و سرراست، بهترين شيوه‌هاي ممكن نيستند و لازم است به دنبال شيوه‌هاي بهتري هم بگرديم. مسلماً براي انجام اين كار بايد شيوه‌هاي نو و تازه‌اي را ياد بگيريم. كتاب، روش‌هاي فراواني را براي طراحي الگوريتم‌ها بررسي و تشريح مي‌كند؛ اما يادگيري روش‌هاي گوناگون به تنهايي كارساز نيست و مانند اين است كه بخواهيم با حفظ و از بر كردن تعداد زيادي بازي شطرنج، بازيگر خوبي شويم. براي اين كار بايد اصول نهفته در پس شيوه‌هاي گوناگون را درك كرد و دانست كه چگونه و مهم‌تر از آن چه وقت، بايد اين اصول را به كار گرفت.
.
.
.
اين رويكرد، بر مبناي استقراي رياضي است و اساس آن الگوبرداري از فرايند فكري اثبات قضاياي رياضي به كمك استقرا براي طراحي الگوريتم‌هاي تركيبياتي است. ايده‌ي اوليه‌ي اصل استقراي رياضي اين است كه براي اثبات يك گزاره، لازم نيست آن را با دست خالي ثابت كنيم، بلكه اگر نشان دهيم گزاره براي يك نمونه‌ي كوچك مبنا درست است؛ آنگاه كافي است ثابت كنيم درستي‌اش از درستي گزاره براي نمونه‌هاي كوچك‌تر نتيجه مي‌شود. معناي اين اصل در طراحي الگوريتم، حل مسائل بزرگ از روي مسائل كوچك است؛ يعني اگر بدانيم چگونه مي‌توان مسأله را براي ورودي‌هاي كوچك حل كرد، مسأله، به طور كامل حل شده است. ايده‌ي اصلي اين روش، تمركز بر گسترش راه‌حل به جاي ساخت آن است. چنان‌كه در فصل‌هاي آينده نشان خواهيم داد، راه‌هاي زيادي براي انجام اين كار وجود دارد كه طبعاً منجر به روش‌هاي فراواني در طراحي الگوريتم مي‌شود.
.
.
.
قراردادهاي كتاب در توصيف الگوريتم‌ها
در طي فرايند خلاقانه‌ي ايجاد الگوريتم‌ها، براي بسياري از آن‌ها، علاوه بر توصيفشان از شبه‌كدها نيز استفاده كرده‌ايم. هدف از اين شبه‌كدها، توصيف بهتر است؛ يعني به بهينه‌سازي آن‌ها توجه چنداني نداشته‌ايم و توصيه هم نمي‌كنيم كه از آن‌ها عيناً نسخه‌برداري كنيد. در برخي موارد آگاهانه تصميم گرفته‌ايم نسخه‌ي بهينه‌ي برنامه را به كار نبريم، چراكه اگر اين كار را مي‌كرديم، پيچيدگي اضافه‌اي در برنامه به وجود مي‌آمد كه ما را از ايده‌ي اصلي الگوريتم دور مي‌كرد. گاهي روش تبديل الگوريتم به برنامه را به طور دقيق توضيح نداده‌ايم. اين تبديلات، گاه بسيار روشن هستند، اگرچه گاهي هم چنين نيستند. تكيه و تأكيد كتاب – چنان‌كه پيش‌تر نيز گفته شد – بر اصول و مباني طراحي الگوريتم است.
بيش‌تر، زباني شبيه پاسكال (وگاهي خود پاسكال) را به كار برده‌ايم. در موارد زيادي از توصيف سطح بالا (مانند «افزودن به جدول» يا «بررسي تهي بودن مجموعه») درون كد پاسكال استفاده كرده‌ايم تا خوانايي بيش‌تر شود. آنچه برخلاف قوانين پاسكال انجام داده‌ايم، كاربرد begin و end براي محصور ساختن بخشي از كد است. اين دستورها را تنها براي شروع و پايان برنامه به كار برده‌ايم و بخش‌هاي مختلف برنامه را با تورفتگي از يكديگر جدا كرده‌ايم. اين قرارداد بدون آن‌كه سبب ابهام شود، باعث صرفه‌جويي در مصرف كاغذ است. معمولاً در مواردي كه نياز به اعلان نبوده است، اعلان دقيق متغيرها و انواع داده‌اي را انجام نداده‌ايم (براي مثال از G براي گراف و از T براي درخت سود جسته‌ايم).
.
.
.
فصل 2
استقراي رياضي
هيچ كس جز بنيان‌گذار يك فرضيه، آن را باور ندارد، اما جز آزمون‌گر يك تجربه، همه كس آن را باور دارد.
ناشناس
«واضح است» همواره دشمن «اثبات درست» است.
Bertrand Russell
2-1 آشنايي
در فصل‌هاي آينده خواهيم ديد كه استقرا نقشي محوري در طراحي الگوريتم بازي مي‌كند. در اين فصل به كمك چند مثال - از آسان تا بسيار مشكل - و به طور خلاصه استقراي رياضي را معرفي مي‌كنيم. خوانندگاني كه اثبات‌هاي استقرايي زيادي نديده‌اند، ممكن است اين فصل را قدري دشوار بدانند. ما ادعا مي‌كنيم كه فرايند ساخت اثبات‌ها مشابه فرايند ساخت الگوريتم‌هاست. بنابراين تجربه‌ي اثبات‌هاي استقرايي را براي ساخت الگوريتم‌ها بسيار مفيد مي‌دانيم.
استقراي رياضي روش بسيار نيرومندي براي اثبات است و معمولاً به اين صورت انجام مي‌شود: T را قضيه‌اي مي‌گيريم كه مي‌خواهيم اثبات كنيم. فرض كنيد T شامل پارامتر n است و مقدار اين پارامتر مي‌تواند هر عدد طبيعي باشد. (اعداد طبيعي همان اعداد صحيح مثبت هستند.) به جاي آن‌كه به طور مستقيم ثابت كنيم T براي تمام مقادير n برقرار است، اين دو مطلب را ثابت مي‌كنيم:
1- T براي n=1 برقرار است.
2- براي هر n>1، اگر T براي n-1 برقرار باشد، آنگاه T برايn نيز برقرار است.
روشن است اثبات اين دو مطلب براي اثبات قضيه كافي است. از 1 و 2 به طور مستقيم نتيجه مي‌گيريم كه T براي n=2 نيز برقرار است. اگر T براي n=2 برقرار باشد، از شرط 2 نتيجه مي‌شود T براي n=3 نيز برقرار است و ... . اصل استقرا چنان روشن است كه معمولاً ثابت نمي‌شود؛ بلكه به صورت يك اصل موضوع در تعريف اعداد طبيعي بيان مي‌گردد.
معمولاً اثبات 1 ساده است. اثبات 2 در بسياري حالات آسان‌تر از اثبات مستقيم قضيه است، زيرا مي‌توانيم از فرض درستي T براي n-1 استفاده كنيم. اين فرض، فرض استقرا نام دارد. به عبارت ديگر، فرض استقرا بي‌هيچ زحمتي در اختيار ماست. به جاي اثبات با دست خالي، مي‌توانيم درستي قضيه را براي مقادير كوچك‌تر n فرض بگيريم. پس ما بر اثبات قضيه از روي درستي آن براي مقادير كوچك‌تر تمركز مي‌كنيم. بياييد كار را با يك مثال آغاز كنيم:
.
.
.
فصل 3
تحليل الگوريتم‌ها
به بزرگي نيست وگرنه گاو از خرگوش جلو مي‌زد.
ضرب‌المثل آلماني‌‌هاي پنسيلوانيا
آن كس كه به ميوه‌هاي درختان سر به فلك كشيده مي‌نگرد، اما بلنداي آن درختان را اندازه نمي‌گيرد؛ احمقي بيش نيست.
Quintus Curtius Rufus
3-1 آشنايي
هدف از تحليل يك الگوريتم پيش‌بيني رفتار آن، به ويژه زمان اجراي آن است؛ بدون آن كه مجبور شويم آن الگوريتم را روي رايانه‌اي خاص پياده‌سازي كنيم. فايده‌ي چنين كاري روشن است: داشتن معيارهاي ساده‌اي براي كارايي يك الگوريتم بسيار راحت‌تر از آن است كه مجبور باشيم با هر تغييري در پارامترهاي يك رايانه، آن الگوريتم را از نو پياده‌سازي كنيم تا كارايي‌اش آشكار شود. يك برنامه‌ي پيچيده معمولاً الگوريتم‌هاي كوچك فراواني در خود دارد. بنابراين بررسي همه‌ي جاي‌گزين‌ها براي اين الگوريتم‌هاي كوچك، كاري بسيار وقت‌گير و خسته‌كننده است.
متأسفانه پيش‌بيني دقيق رفتار يك الگوريتم معمولاً غيرممكن است، چون عوامل فراواني بر آن تأثير مي‌گذارند. به جاي اين كار مي‌كوشيم تا ويژگي‌هاي اصلي الگوريتم را به دست آوريم؛ يعني پارامترها و معيارهاي مشخصي را تعريف مي‌كنيم كه در تحليل الگوريتم بيش‌ترين اهميت را دارند. پس بيش‌ترِ جزئيات پياده‌سازي را ناديده مي‌گيريم. بنابراين تحليل الگوريتم موضوعي تقريبي است و نبايد آن را ابزار كاملي براي پيش‌بيني رفتار الگوريتم‌ها به شمار آورد؛ به عبارت ديگر، حتا تقريب نادقيق هم مي‌تواند درباره‌ي الگوريتم، اطلاعات ارزشمندي به ما بدهد. مهم‌تر از همه، با اين روش مي‌توانيم الگوريتم‌هاي مختلف را با هم مقايسه كرده، دريابيم كدام يك از آن‌ها با اهدافمان سازگارتر است. اين موضوع را مي‌توان با ادعاي مصرف سوخت در خودروها مقايسه كرد و گفت: «اين معيارها تنها براي مقايسه‌اند و ممكن است زمان واقعي اجراي الگوريتم‌ها، كمتر يا بيش‌تر باشد».
.
.
.
تحليلي كه روي الگوريتم انجام مي‌دهيم بايد نشان دهد كه زمان اجرا براي يك ورودي مشخص چقدر پيش‌بيني مي‌شود؛ اما قادر نخواهيم بود زمان اجراي تمام ورودي‌ها را فهرست كنيم، مگر آن كه الگوريتم موردنظر واقعاً ساده باشد. ورودي، حالت‌هاي گوناگون بسياري دارد و بيش‌تر الگوريتم‌ها در برابر ورودي‌هاي مختلف، رفتارهاي متفاوتي از خود نشان مي‌دهند. به همين دليل، ورودي را با معياري به نام اندازه‌ي ورودي مي‌سنجيم و تحليل را بر پايه‌ي آن انجام مي‌دهيم. يك الگوريتم در برابر ورودي‌هاي هم‌اندازه رفتار دقيقاً يكساني ندارد ولي ما اميدواريم كه نوسانش، معقول و پذيرفتني باشد. معمولاً اندازه‌ي ورودي چنين تعريف مي‌شود: «فضاي لازم براي ذخيره‌ي ورودي». تلاش نمي‌كنيم تا براي همه‌ي الگوريتم‌ها تعريفي كلي از اندازه‌ي ورودي ارائه دهيم، زيرا در اصل علاقه‌منديم الگوريتم‌هاي مختلف يك مسأله را با هم مقايسه كنيم. بيش‌تر اوقات تعريف اندازه‌ي ورودي، كاري سرراست است كه به زودي چند مثال از آن خواهيم ديد. اندازه‌ي ورودي را با n نشان خواهيم داد، مگر آن كه به صراحت چيز ديگري گفته باشيم.
.
.
.
فصل 4
نگاهي کوتاه به ساختمان‌هاي داده‌اي
علم همان بديهيات است؛ پس از دسته‌بندي و آموزش.
T.H. Huxley
از روشن‌فکران بيزارم. آنان از بالا به پايين مي‌رسند؛ من از پايين به بالا.
Frank Lloyd Wright
4-1 آشنايي
ساختمان‌هاي داده‌اي، اجزاي سازنده‌ي الگوريتم‌هاي رايانه‌اي هستند. طراحي يک الگوريتم همانند طراحي يک ساختمان است. اتاق‌هاي يک ساختمان بايد به گونه‌اي در کنار هم قرار گيرند که براي کاربرد مورد نظر بيش‌ترين کارايي را داشته باشند. براي اين کار دانستن عملکرد، بهره‌وري، شکل و زيبايي، به تنهايي کافي نيست، بلکه به دانش کامل روش‌هاي ساختمان‌سازي نيازمنديم. ممکن است کارايي دل‌خواه ما قرار دادن اتاق در هوا، بين زمين و آسمان باشد، اما چنين کاري شدني نيست يا ممکن است برخي ايده‌هاي شدني، بسيار گران تمام شوند. به همين ترتيب، طراحي يک الگوريتم بايد بر مبناي درک کاملي از روش‌هاي ساختمان‌داده و هزينه‌ي هر يك از اين روش‌ها باشد.
در اين فصل تنها ساختمان‌هاي داده‌اي پايه را که در کتاب به کار رفته‌اند، بررسي مي‌کنيم. نمي‌خواهيم درباره‌ي تمام ساختمان‌هاي داده‌اي توضيح جامعي دهيم؛ چرا که براي اين کار (دست‌کم) به يک کتاب کامل نيازمنديم و بدون شک کتاب‌هاي خوبي در اين زمينه وجود دارند. انتظار داريم که بيش‌تر خوانندگان کم و بيش با ساختمان‌هاي داده‌اي آشنا باشند. هدف عمده‌ي اين فصل، نگاهي سريع به موضوع است.
يک روش مناسب در مطالعه‌ي ساختمان‌هاي داده‌اي، بررسي «داده‌گونه‌هاي مجرد» است. عموماً هنگام نوشتن برنامه، بايد نوع داده‌هاي به‌کاررفته (صحيح، اعشاري، کاراکتري و ...) را نيز مشخص کنيم؛ اما گاهي تعيين نوع داده‌ها در طراحي الگوريتم، موضوع مهمي نيست. مثلاً ممکن است بخواهيم يک صف ترتيبي از عناصر را نگه‌داري کنيم. اعمالي که در اينجا مورد نيازند، درج يک عنصر در صف و حذف آن از صف هستند. هنگام برداشتن عنصرها از صف بايد آن‌ها را به همان ترتيبي كه به صف افزوده شده‌اند، حذف كنيم. طراحي الگوريتم‌هاي اين اعمال (يعني درج يا حذف يک عنصر) بدون تعيين نوع داده‌ي عنصر، راحت‌تر و کلي‌تر است. بهتر است تنها، اعمال مورد نياز را مشخص کنيم؛ مثلاً در اين مورد خاص، به داده‌گونه‌ي مجردي که از اعمال گفته‌شده پشتيباني مي‌کند، صف ترتيبي مي‌گوييم. مهم‌ترين بخش هر داده‌گونه‌ي مجرد، فهرست اعمال مورد نياز آن است. مثال ديگري از داده‌گونه‌ي مجرد، صفي است که عناصر آن، اولويت هم دارند؛ يعني حذف آن‌ها بنا به ترتيب درجشان نيست، بلکه برحسب اولويت آنهاست. به عبارت ديگر، نخستين عنصري که در هر گام از عمل حذف، کنار گذاشته مي‌شود، عنصري است که در ميان عناصر صف، بيش‌ترين اولويت را داشته باشد. اين داده‌گونه‌ي مجرد، صف اولويت نام دارد. در اينجا هم، نوع داده‌اي عناصر را مشخص نمي‌کنيم. (حتا نيازي نيست که نوع داده‌اي اولويت‌ها را تعيين کنيم؛ تنها لازم است آن اولويت‌ها ترتيب كلي داشته باشند و ما بتوانيم ترتيب آن‌ها را تعيين کنيم.)
.
.
.
فصل 5
طراحي استقرايي الگوريتم‌ها
ريشه‌يابي اختراعات آن قدر اهميت دارد که به نظر من از خود اختراعات هم جالب‌تر است.
G. W. Leibniz
هر اختراعي موجب اختراعات ديگر مي‌شود.
R. W. Emerson
5-1 آشنايي
در اين فصل با الگوبرداري از استقراي رياضي، شيوه‌ي خودمان در طراحي الگوريتم را نشان مي‌دهيم. به اين منظور از مثال‌هاي نسبتاً ساده سود مي‌جوييم تا اصول و روش‌هاي پايه‌ي اين شيوه را معرفي كنيم. آنچه بايد در مورد استقرا بدانيم، در فصل 2 بيان شده است، اما به هنگام نياز، مطلب را تکرار مي‌کنيم تا اين فصل خودکفا باشد.
استقراي رياضي مانند دومينو است. تعدادي مهره‌ي دومينو را در نظر بگيريد که پشت‌سرهم چيده شده‌اند. مي‌خواهيم تنها با انداختن نخستين مهره، تمام آن‌ها را واژگون سازيم. براي اطمينان از اين رويداد کافي است مطمئن شويم که هر مهره پس از افتادن، مهره‌ي پس از خود را واژگون خواهد کرد. هر بار که مهره‌ي تازه‌اي به جمع مهره‌ها مي‌افزاييم، ديگر لازم نيست تمام آن‌ها را بيندازيم تا از درستي عملکرد مطمئن شويم. مي‌توان از اين اصل در طراحي الگوريتم هم بهره گرفت:
لازم نيست گام‌هاي مورد نياز براي حل مسأله را با دست خالي بپيماييم. کافي است تضمين کنيم که (1) نمونه‌ي کوچکي از مسأله حل‌شدني است (حالت پايه) و (2) مي‌توان راه‌حل نمونه‌هاي بزرگ‌تر مسأله را از روي حل نمونه‌هاي کوچک‌تر يافت (گام استقرا).
هنگامي كه مي‌خواهيم از اين اصل بهره‌برداري كنيم، بايد روي کاهش مسأله به مسأله‌اي کوچک‌تر (يا مجموعه‌اي از مسأله‌هاي کوچک‌تر) تمرکز کنيم؛ اما عموماً يافتن راهي براي کاهش اندازه‌ي مسأله چندان آسان نيست. در اين فصل چندين روش را براي آسان کردن اين فرايند نشان مي‌دهيم. مثال‌هاي اين فصل، نه به دليل زيادي اهميتشان در عمل (چراكه برخي از آن‌ها كاربرد اندكي دارند) بلكه به اين دليل بررسي شده‌اند که ساده هستند و اصول مورد تأكيد را به خوبي تشريح مي‌کنند. در کتاب نمونه‌هاي بسياري از اين رويکرد ارائه خواهيم کرد.
.
.
.
فصل 6
الگوريتم‌هاي دنباله‌ها و مجموعه‌ها
«نظم» را من دوست دارم بس زياد
بال خـود بر روي «بي‌نظـمي» نهاد
«سـادگي» را نغـمه‌خوانـي داد يـاد
Anna Hempstead Branch
6-1 آشنايي
در اين فصل با ورودي‌هايي سر و کار داريم که دنباله‌ها يا مجموعه‌هايي متناهي هستند. دنباله و مجموعه با يكديگر متفاوتند. در دنباله برخلاف مجموعه، ترتيب عناصر اهميت دارد. به علاوه، مي‌دانيم که در يک مجموعه، عنصر تکراري وجود ندارد، در صورتي که يک دنباله ممکن است عنصر تکراري هم داشته باشد. از آنجايي که معمولاً ورودي‌ها ترتيب مشخصي دارند، مي‌توان آن‌ها را «دنباله» در نظر گرفت. با اين حال، هنگامي که ترتيب ورودي براي ما مهم نباشد، مي‌توانيم ورودي را يک مجموعه در نظر بگيريم. در سرتاسر اين فصل، ورودي را با آرايه نمايش مي‌دهيم، مگر آن که به صراحت خلاف آن را گفته باشيم و فرض مي‌کنيم اندازه‌ي آرايه را از پيش مي‌دانيم. فرض بر اين است که عناصر مجموعه يا دنباله، از يك مجموعه با ترتيب کلي (مانند اعداد صحيح يا اعداد حقيقي) گرفته مي‌شوند و مي‌توان آن‌ها را با يكديگر مقايسه کرد. در اين فصل به مسأله‌هايي که عناصر آن‌ها هم‌نوع هستند، پرداخته‌ايم. موضوعاتي مانند بيشينگي، ترتيب، زيردنباله‌هاي ويژه، فشرده‌سازي داده‌ها و تشابه دنباله‌ها را در اين فصل بررسي مي‌کنيم.
در اين فصل، الگوريتم‌هاي بسياري را با کاربردهاي گوناگون مطرح مي‌كنيم. هدف ما اين بوده است که از شيوه‌ي طراحي گفته‌شده در فصل 5، مثال‌هاي بيش‌تري بياوريم و همراه با آن برخي الگوريتم‌هاي مهم را نيز تشريح کنيم. برخي از الگوريتم‌هاي آورده‌شده بسيار مهم و کاربردي هستند (مانند مرتب‌سازي و جستوجوي دودويي)، برخي با آن که اهميت چنداني ندارند، اما روش‌هاي جالبي را تشريح مي‌کنند (مانند يافتن دو عنصر بزرگ‌تر در يک مجموعه و مسأله‌ي زيردنباله‌ي ناپايدار) و برخي نيز با آن که مهم هستند، اما تنها در زمينه‌هاي خاصي به كار مي‌آيند (مانند فشرده‌سازي پرونده‌ها و مقايسه‌ي دنباله‌ها).
نخستين مثال اين فصل، جستوجوي دودويي است - الگوريتمي پايه‌اي و اساسي که گونه‌هاي بسياري دارد و در موارد گوناگوني ظاهر مي‌شود. پس از آن، مرتب‌سازي را مورد بحث و بررسي قرار مي‌دهيم که درباره‌ي آن مطالعات گسترده‌اي انجام شده است. سپس شما را با مرتبه‌ي آماري، فشرده‌سازي داده‌ها، الگوريتم‌هاي مبتني بر احتمال و دو مسأله از دست‌کاري متن آشنا مي‌کنيم. سرانجام، فصل را با چند مثال از الگوريتم‌هايي زيبا و عالي به پايان مي‌رسانيم كه روش‌هاي جالبي از طراحي الگوريتم را تشريح مي‌كنند.
.
.
.
فصل 7
الگوريتم‌هاي گراف
راه ميان‌بر، طولاني‌ترين راه بين دو نقطه است.
ناشناس
7-1 آشنايي
در فصل پيش، الگوريتم‌هايي را براي كار با مجموعه‌ها يا دنباله‌هايي از اشياء بررسي كرديم و به رابطه‌هايي مانند ترتيب، تكرار و هم‌پوشاني برخورديم. در اين فصل، با رابطه‌هاي بيش‌تري بين اشياء آشنا خواهيم شد و گراف‌ها را براي مدل‌سازي اين رابطه‌ها به كار خواهيم گرفت. گراف‌ها مي‌توانند وضعيت‌هاي بسيار گوناگوني را مدل كنند و در زمينه‌هاي بسياري از باستان‌شناسي گرفته تا روان‌شناسي اجتماعي كاربرد دارند. در اين فصل، براي كار با گراف‌ها و محاسبه‌ي ويژگي‌هاي مشخصي از آن‌ها، چندين الگوريتم مهم و پايه‌اي را به شما معرفي خواهيم كرد.
نخست، به نمونه‌هايي از مدل‌سازي با گراف نگاهي مي‌اندازيم:
1- يافتن مسيري خوب از خانه تا رستوراني در شهر؛ خيابان‌ها متناظر با يال‌ها (اگر خيابان‌ها يك‌طرفه باشند، يال‌هاي جهت‌دار) و تقاطع خيابان‌ها متناظر با رأس‌ها هستند. براي هر رأس و هر يال (هر تكه از خيابان كه بين دو تقاطع است) زمان تأخيري مورد انتظار است و مسأله، يافتن «سريع‌ترين» مسير بين دو رأس است.
2- برخي برنامه‌هاي رايانه‌اي را مي‌توان به وضعيت‌هاي گوناگون تقسيم كرد. ممكن است در هر يك از اين وضعيت‌ها، حالت‌هاي مختلفي براي پيش‌روي وجود داشته باشد و برخي از اين وضعيت‌ها نيز ممكن است نامطلوب باشند. يافتن وضعيت‌هايي كه به يك حالت نامطلوب منجر مي‌شوند، مسأله‌ي ديگري از نظريه‌ي گراف است كه در آن هر وضعيت، متناظر با يك رأس و هر يال متناظر با امكان پيش‌روي از يك وضعيت به وضعيت ديگر خواهد بود.
3- به مسأله‌ي برنامه‌ريزي كلاس‌هاي يك دانشگاه مي‌توان به صورت مسأله‌اي از نظريه‌ي گراف نگريست. رأس‌ها بيانگر كلاس‌ها هستند و اگر دانش‌آموزي بخواهد دو كلاس را با هم بگيرد، يا استادي بخواهد در هر دو كلاس تدريس كند، آنگاه آن دو كلاس را به يكديگر متصل مي‌كنيم. مسأله، برنامه‌ريزي كلاس‌هاست، به گونه‌اي كه تعداد تداخل كلاس‌ها كمينه گردد. اين مسأله دشوار است و به راحتي نمي‌توان راه‌حل مناسبي براي آن يافت.
4- يك سامانه‌ي رايانه‌اي با چندين حساب كاربري در نظر بگيريد كه در آن هر كاربر براي دست‌رسي به حساب خود، مجوز يا امتيازي امنيتي دارد. ممكن است كاربران بخواهند با يكديگر همكاري كنند و اجازه‌ي دست‌رسي به حساب خود را در اختيار كاربر ديگري هم بگذارند. از سويي، اگر كاربر A به حساب كاربر B و كاربر B به حساب كاربر C دست‌رسي داشته باشد، آنگاه A نيز به حساب كاربر C دست‌رسي خواهد داشت. مسأله‌ي تعيين دست‌رسي كاربران به حساب‌هاي يكديگر، مسأله‌اي ديگر از نظريه‌ي گراف است. در اينجا، كاربران با رأس‌ها متناظر مي‌شوند و اگر كاربر A اجازه‌ي دست‌رسي به حساب خود را به كاربر B بدهد، يالي جهت‌دار از A به B وجود خواهد داشت.
.
.
.
Written by Udi Manber, Translated by Ahmad Sadeghi Sefat & Sayed Ali Hosseini
اگرچه اين كتاب بيش‌ترِ مباحث درس طراحي الگوريتم از دوره‌ي كارشناسي رشته‌ي رايانه را پوشش مي‌دهد، اما مخاطبان اصلي آن كساني هستند كه مي‌خواهند خلاقيت خويش را پرورش دهند. از اين رو، خواندن آن به كساني كه قصد شركت در المپياد دانش‌آموزي يا دانش‌جويي رايانه و يا مسابقات برنامه‌نويسي ACM را دارند، سفارش مي‌شود.
متني كه در ادامه مي‌بينيد گوشه‌هايي از كتاب است كه براي آشنايي خوانندگان آورده شده است:
.
.
.
پيش‌گفتار
اين کتاب را نوشتم تا ناکامي‌هايم در بيان روشن الگوريتم‌ها را جبران كنم. همچون بسياری از استادان دريافته بودم، برای برخی دانش‌جويان نه تنها حل مسائل ساده (ساده در نظر من) دشوار است، بلکه آنان از درک راه‌حل‌های عرضه‌شده نيز عاجزند. معتقدم ايجاد و شرح يک راه‌حل، به هم وابسته‌اند و نبايد از يکديگر جدا گردند؛ يعنی برای درک کامل يک راه‌حل، لازم است مراحل منتهی به آن را دنبال کنيم و تنها دقت در راه‌حل نهايی کافی نيست.
.
.
.
مسيرهايی که در اين کتاب عرضه می‌شوند، چندان ساده نيستند. اگرچه اين کتاب روش حل بسياری از مسائل خاص را نشان مي‌دهد، اما تکيه‌اش بر روی اصول و روش‌های کلی است. در نتيجه، کتابی است چالش‌برانگيز که شما را درگير و وادار به انديشيدن می‌کند. ايمان دارم که می‌ارزد در اين راه بيش‌تر تلاش کنيد.
طراحی الگوريتم‌های کارآمد در زمينه‌های گوناگونی مانند رياضيات، آمار، مهندسی و زيست‌شناسی مولکولی بسيار مهم شده است. اين کتاب به بررسی كلي الگوريتم‌ها می‌پردازد. افراد حرفه‌ایِ بسياري از رشته‌ها و حتا دانشمندانی که عميقاً با رايانه درگير نيستند، برنامه‌نويسی را کاری غيرفکری و خسته‌کننده مي‌دانند. گاهی چنين است، اما اين باور سبب عرضه‌ی راه‌حل‌های دم‌دستی، پيش‌پاافتاده و ناکارآمد می‌شود، درحالی‌که راه‌حل‌های دقيق‌تر و کارآمدتری نيز وجود دارند. يکی از اهداف کتاب اين است که خوانندگان خود را قانع کند تفکر الگوريتمی، ديدگاهی دقيق، ظريف و بااهميت در برخورد با مسائل گوناگون به آنان می‌دهد.
کتاب خودکفاست و شيوه‌ی ارائه‌ي آن بيش‌تر شهودی است. نکات فنی هر بحث يا در کم‌ترين حد ممکن بيان شده، يا از بحث اصلی مجزا گشته است؛ به ويژه، جزئيات پياده سازی تا جای ممکن از طراحی الگوريتم جدا شده است. برای تشريح اصولی که کتاب بر آن‌ها تأکيد دارد، مثال‌های ويژه‌ی زيادی طراحی شده‌اند. مطالب کتاب به گونه‌اي نيست که بتوان بر آن‌ها مسلط شد يا آن‌ها را به خاطر سپرد. اين مطالب به صورت مجموعه‌ای از ايده‌های اوليه، مثال‌ها، مثال‌های نقض، تغيير و بهبود در راه‌حل‌ها و ... ارائه شده‌اند. پس از توصيف اکثر الگوريتم‌ها، شبه‌کدهای متناظر با آن‌ها هم آورده شده است. هر فصل با بخشی برای مطالعه‌ي بيش‌تر به همراه مراجع وابسته به آن و تعدادی تمرين پايان مي‌پذيرد. در بيش‌تر فصل‌ها، تمرين‌ها به دو دسته تقسيم می‌شوند: تمرين‌های آموزشی و تمرين‌های خلاقانه. تمرين‌های آموزشی برای ارزيابی استنباط خواننده از مثال‌ها و الگوريتم‌های آن فصل و تمرين‌های خلاقانه برای ارزيابی توانايي خواننده است. تمرين‌هاي خلاقانه به خواننده نشان مي‌دهند كه آيا با روش‌های آن فصل مي‌تواند مسائل تازه را هم حل کند يا نه. خطوط کلی راه‌حل گزيده‌اي از تمرين‌ها (آن‌هايی که زير شماره‌ی‌شان خط کشيده شده) در پايان کتاب آورده شده و خلاصه‌ای از مطالب هر فصل در پايان همان فصل عرضه گرديده است.
سازمان‌دهی کتاب چنين است: فصل‌های 1 تا 4 موضوعات مقدماتی را ارائه می‌کنند. فصل 2 مقدمه‌ای بر استقراي رياضی است. چنان که خواهيم ديد، استقرای رياضی در طراحی الگوريتم بسيار مهم است. به همين دليل، تجربه‌ی اثبات‌های استقرايي در اين راه مفيدند. بدبختانه شمار اندکی از دانش‌جويان علوم رايانه تجربه‌ی کافی در اين کار دارند. ممکن است فصل 2 برای برخی دانش‌جويان دشوار باشد. پيش‌نهاد می‌کنم که بار نخست از مثال‌های مشکل‌تر بگذريد و آن‌ها را بعداً بخوانيد. فصل 3 برای آشنايی با تحليل الگوريتم‌هاست. اين فصل، فرايند تحليل الگوريتم‌ها را شرح مي‌دهد و ابزارهای اساسی لازم را برای تحليل الگوريتم‌های کتاب فراهم مي‌آورد. فصل 4 نگاهی مختصر به ساختمان‌های داده‌ای است. خوانندگانی که با ساختمان‌های داده‌ای پايه آشناترند و دانش رياضی بيش‌تری دارند، می‌توانند خواندن کتاب را مستقيماً از اين فصل شروع کنند (اگرچه خوب است دست‌كم بخش «آشنايي» تمام فصل‌ها را بخوانيد.) فصل 5 ايده‌ی اصلی طراحی الگوريتم‌ها را به کمک مقايسه‌ی آن‌ها با اثبات‌های استقرايی نشان می‌دهد. اين فصل چندين مثال از الگوريتم‌های ساده ارائه می‌كند و شيوه‌ی ساخت آن‌ها را توضيح مي‌دهد. اگر قصد خواندن تنها يك فصل از كتاب را داريد، همين فصل را بخوانيد.
دو روش کلی برای سازمان‌دهی هر کتاب الگوريتم وجود دارد. يک روش بر پايه‌ی موضوع الگوريتم‌هاست؛ مثلاً فصلی برای الگوريتم‌های گراف يا فصلی برای الگوريتم‌های هندسی. راه ديگر بر پايه‌ی روش‌های طراحي است. درست است که اين کتاب بر روش‌های طراحی تکيه مي‌کند، اما من همان روش نخست را برگزيده‌ام و به نظرم اين روش روشن‌تر و آسان‌تر است. فصل‌های 6 تا 9 به ترتيب الگوريتم‌هايی را در چهار مبحث زير ارائه می‌کنند: الگوريتم‌های دنباله‌ها و مجموعه‌ها (مانند مرتب‌سازی، مقايسه‌ی دنباله‌ها، فشرده‌سازی داده‌ها)، الگوريتم‌های گراف (مانند درخت پوشای کمينه، کوتاه‌ترين مسيرها، تطبيق)، الگوريتم‌های هندسی (مانند پوسته‌ي كوژ، يافتن اشتراک دو چند ضلعی) و الگوريتم‌های عددی و جبری (مانند ضرب ماتريس‌ها، محاسبه‌ی سريع تبديل فوريه).
فصل 10 به reduction يا كاهش اختصاص دارد. اگرچه در فصل‌های پيش از آن نمونه‌هايی از كاهش آورده شده است، اما موضوع به قدری مهم و جالب‌توجه است که می‌ارزد يک فصل جداگانه را به آن اختصاص دهيم. اين فصل مقدمه‌ای بر NP-تمام (موضوع فصل 11) نيز هست. NP-تمام (از مباحث نظريه‌ی پيچيدگی) به بخشی جدانشدنی از نظريه‌ی الگوريتم‌ها تبديل شده است. هرکس که دست به طراحی الگوريتم می‌زند، بايد چيزهايی درباره‌ی روش‌های اثبات NP-تمام بودن مسأله‌ها بداند. فصل 12 برای آشنايی با الگوريتم‌های موازی است و چندين الگوريتم جالب را از مدل‌های گوناگون پردازش موازی به خواننده‌ی خود نشان می‌دهد.
.
.
.
فصل 1
آشنايي
«تركيب اجزاء» فرايندي بسيار مهم است، چنان كه برخي آن را شرط لازم‌وكافي براي پيش‌رفت علم مي‌دانند. بي‌ترديد، شرط لازم هست، اما شرط كافي نيست! براي آن‌كه تركيبي از اجزاء سودمند باشد و تلاش فكري‌مان را به هدر ندهد و براي آن‌كه سكوي پرتابي براي رسيدن به چيزهاي برتر شود؛ پيش از همه بايد از وحدتي برخوردار باشد كه ما آن را تنها چند «عنصرِ كنار يكديگر» نبينيم.
Henri Poincaré
نهمين ويرايش از واژه نامه‌ي Webster (واژه‌نامه‌ي دانشگاهي جديدش) الگوريتم را چنين تعريف مي‌كند: «روالي براي حل يك مسأله‌ي رياضي (مانند يافتن بزرگ‌ترين مقسوم عليه مشترك) در مراحلي متناهي كه غالباً شامل تكرار يك عمل مي‌شود» و يا در تعريفي كلي: «روالي گام‌به‌گام براي حل يك مسأله يا دست‌يابي به اهدافي چند». ما از تعريف كلي الگوريتم استفاده خواهيم كرد. طراحي الگوريتم، موضوعي قديمي و ريشه‌دار است. مردم همواره مي‌خواسته‌اند روشي بهتر براي دست‌يابي به اهدافشان داشته باشند؛ چه آناني كه مي‌خواسته‌اند آتش روشن كنند، چه آناني كه اهرام را مي‌ساخته‌اند و چه آناني كه نامه‌ها را مرتب مي‌كرده‌اند. البته مطالعه روي الگوريتم‌هاي رايانه‌اي موضوعي نوين است. برخي الگوريتم‌هاي رايانه‌اي از روش‌هايي بهره مي‌برند كه پيش از اختراع رايانه هم شناخته شده بودند، اما حل بيش‌تر اين مسأله‌ها با رايانه، به شيوه‌هاي نويني نياز دارد؛ براي مثال، اين‌كه به رايانه بگوييم «به آن سوي كوهستان بنگر و چنان‌چه ديدي ارتشي پيش مي‌آيد، فرياد خطر برآور!» كافي نيست. رايانه بايد دقيقاً بداند معناي «نگريستن» چيست، چگونه «ارتش» را تشخيص دهد و چگونه فرياد خطر برآورد. (البته بنا به دلايلي همواره فرياد خطر برآوردن كاري ساده است!) رايانه تنها مي‌تواند دستورالعمل‌هايي خوش تعريف، محدود به اعمال اوليه دريافت كند. ترجمه‌ي دستورالعمل‌هاي معمولي به زباني كه يك رايانه آن‌ها را بفهمد، دشوار است. برنامه‌نويسي، همين فرايند ضروري و دشواري است كه امروزه ميليون‌ها نفر را در سطوح مختلف به خود مشغول كرده است.
.
.
.
از سوي ديگر، الگوريتم‌هايي كه ما در زندگي روزانه با آن‌ها سر و كار داريم، چندان پيچيده نيستند و خيلي هم تكرار نمي‌شوند. پس نمي‌ارزد براي ايجاد يك الگوريتم خوب تلاش زيادي كنيم؛ چراكه بازدهي‌اش اندك است. مثلاً مسأله‌ي خالي كردن كيسه‌هاي خواربار را در نظر بگيريد. قطعاً براي انجام اين كار با توجه به محتويات كيسه‌ها و چيدمان وسيله‌هاي درون آشپزخانه، راه‌هايي با درجات كارآمدي گوناگون وجود دارد. افراد كمي هستند كه حتا به اين مسأله فكر كنند و از بين آن‌ها هم، كمتر افرادي هستند كه الگوريتمي براي اين كار بسازند. به عبارت ديگر، كساني مجبورند روش‌هاي بهتري ايجاد كنند كه در مقياس وسيع تجاري، كار پر و خالي كردن كيسه‌ها را انجام مي‌دهند. مثال ديگر زدن چمن‌هاست. ما مي‌توانيم با كمتر كردن تعداد تغيير مسير هنگام چمن‌زني يا با كمتر كردن زمان چمن‌زني و يا با كمتر كردن مسافت طي‌شده تا سطل زباله، كار را بهتر انجام دهيم. مگر آن‌كه كسي واقعاً از چمن‌زني متنفر باشد وگرنه كسي نيست كه يك ساعت وقت بگذارد تا بفهمد چطور مي‌شود از زمان چمن‌زني يك دقيقه كم كرد! رايانه‌ها مي‌توانند با كارهاي پيچيده دست و پنجه نرم كنند و آن‌ها را بارها و بارها انجام دهند. اينجاست كه مي‌ارزد براي ايجاد روشي بهتر زمان زيادي را صرف كنيم، حتا اگر با اين كار، الگوريتم‌هاي پيچيده‌تري به دست آيد كه فهمشان دشوارتر باشد. (البته در بهينه‌سازي نبايد افراط كرد و به خاطر بهبود چند ثانيه‌اي در كار رايانه، ساعت‌ها وقت برنامه‌نويسان را به هدر داد.)
نياز به روش‌هاي ناملموس در الگوريتم‌هاي حجيم و پيچيدگي احتمالي اين الگوريتم‌ها، نشانگر دشوار بودن يادگيري آنهاست. نخست، بايد درك كنيم كه شيوه‌هاي شهودي و سرراست، بهترين شيوه‌هاي ممكن نيستند و لازم است به دنبال شيوه‌هاي بهتري هم بگرديم. مسلماً براي انجام اين كار بايد شيوه‌هاي نو و تازه‌اي را ياد بگيريم. كتاب، روش‌هاي فراواني را براي طراحي الگوريتم‌ها بررسي و تشريح مي‌كند؛ اما يادگيري روش‌هاي گوناگون به تنهايي كارساز نيست و مانند اين است كه بخواهيم با حفظ و از بر كردن تعداد زيادي بازي شطرنج، بازيگر خوبي شويم. براي اين كار بايد اصول نهفته در پس شيوه‌هاي گوناگون را درك كرد و دانست كه چگونه و مهم‌تر از آن چه وقت، بايد اين اصول را به كار گرفت.
.
.
.
اين رويكرد، بر مبناي استقراي رياضي است و اساس آن الگوبرداري از فرايند فكري اثبات قضاياي رياضي به كمك استقرا براي طراحي الگوريتم‌هاي تركيبياتي است. ايده‌ي اوليه‌ي اصل استقراي رياضي اين است كه براي اثبات يك گزاره، لازم نيست آن را با دست خالي ثابت كنيم، بلكه اگر نشان دهيم گزاره براي يك نمونه‌ي كوچك مبنا درست است؛ آنگاه كافي است ثابت كنيم درستي‌اش از درستي گزاره براي نمونه‌هاي كوچك‌تر نتيجه مي‌شود. معناي اين اصل در طراحي الگوريتم، حل مسائل بزرگ از روي مسائل كوچك است؛ يعني اگر بدانيم چگونه مي‌توان مسأله را براي ورودي‌هاي كوچك حل كرد، مسأله، به طور كامل حل شده است. ايده‌ي اصلي اين روش، تمركز بر گسترش راه‌حل به جاي ساخت آن است. چنان‌كه در فصل‌هاي آينده نشان خواهيم داد، راه‌هاي زيادي براي انجام اين كار وجود دارد كه طبعاً منجر به روش‌هاي فراواني در طراحي الگوريتم مي‌شود.
.
.
.
قراردادهاي كتاب در توصيف الگوريتم‌ها
در طي فرايند خلاقانه‌ي ايجاد الگوريتم‌ها، براي بسياري از آن‌ها، علاوه بر توصيفشان از شبه‌كدها نيز استفاده كرده‌ايم. هدف از اين شبه‌كدها، توصيف بهتر است؛ يعني به بهينه‌سازي آن‌ها توجه چنداني نداشته‌ايم و توصيه هم نمي‌كنيم كه از آن‌ها عيناً نسخه‌برداري كنيد. در برخي موارد آگاهانه تصميم گرفته‌ايم نسخه‌ي بهينه‌ي برنامه را به كار نبريم، چراكه اگر اين كار را مي‌كرديم، پيچيدگي اضافه‌اي در برنامه به وجود مي‌آمد كه ما را از ايده‌ي اصلي الگوريتم دور مي‌كرد. گاهي روش تبديل الگوريتم به برنامه را به طور دقيق توضيح نداده‌ايم. اين تبديلات، گاه بسيار روشن هستند، اگرچه گاهي هم چنين نيستند. تكيه و تأكيد كتاب – چنان‌كه پيش‌تر نيز گفته شد – بر اصول و مباني طراحي الگوريتم است.
بيش‌تر، زباني شبيه پاسكال (وگاهي خود پاسكال) را به كار برده‌ايم. در موارد زيادي از توصيف سطح بالا (مانند «افزودن به جدول» يا «بررسي تهي بودن مجموعه») درون كد پاسكال استفاده كرده‌ايم تا خوانايي بيش‌تر شود. آنچه برخلاف قوانين پاسكال انجام داده‌ايم، كاربرد begin و end براي محصور ساختن بخشي از كد است. اين دستورها را تنها براي شروع و پايان برنامه به كار برده‌ايم و بخش‌هاي مختلف برنامه را با تورفتگي از يكديگر جدا كرده‌ايم. اين قرارداد بدون آن‌كه سبب ابهام شود، باعث صرفه‌جويي در مصرف كاغذ است. معمولاً در مواردي كه نياز به اعلان نبوده است، اعلان دقيق متغيرها و انواع داده‌اي را انجام نداده‌ايم (براي مثال از G براي گراف و از T براي درخت سود جسته‌ايم).
.
.
.
فصل 2
استقراي رياضي
هيچ كس جز بنيان‌گذار يك فرضيه، آن را باور ندارد، اما جز آزمون‌گر يك تجربه، همه كس آن را باور دارد.
ناشناس
«واضح است» همواره دشمن «اثبات درست» است.
Bertrand Russell
2-1 آشنايي
در فصل‌هاي آينده خواهيم ديد كه استقرا نقشي محوري در طراحي الگوريتم بازي مي‌كند. در اين فصل به كمك چند مثال - از آسان تا بسيار مشكل - و به طور خلاصه استقراي رياضي را معرفي مي‌كنيم. خوانندگاني كه اثبات‌هاي استقرايي زيادي نديده‌اند، ممكن است اين فصل را قدري دشوار بدانند. ما ادعا مي‌كنيم كه فرايند ساخت اثبات‌ها مشابه فرايند ساخت الگوريتم‌هاست. بنابراين تجربه‌ي اثبات‌هاي استقرايي را براي ساخت الگوريتم‌ها بسيار مفيد مي‌دانيم.
استقراي رياضي روش بسيار نيرومندي براي اثبات است و معمولاً به اين صورت انجام مي‌شود: T را قضيه‌اي مي‌گيريم كه مي‌خواهيم اثبات كنيم. فرض كنيد T شامل پارامتر n است و مقدار اين پارامتر مي‌تواند هر عدد طبيعي باشد. (اعداد طبيعي همان اعداد صحيح مثبت هستند.) به جاي آن‌كه به طور مستقيم ثابت كنيم T براي تمام مقادير n برقرار است، اين دو مطلب را ثابت مي‌كنيم:
1- T براي n=1 برقرار است.
2- براي هر n>1، اگر T براي n-1 برقرار باشد، آنگاه T برايn نيز برقرار است.
روشن است اثبات اين دو مطلب براي اثبات قضيه كافي است. از 1 و 2 به طور مستقيم نتيجه مي‌گيريم كه T براي n=2 نيز برقرار است. اگر T براي n=2 برقرار باشد، از شرط 2 نتيجه مي‌شود T براي n=3 نيز برقرار است و ... . اصل استقرا چنان روشن است كه معمولاً ثابت نمي‌شود؛ بلكه به صورت يك اصل موضوع در تعريف اعداد طبيعي بيان مي‌گردد.
معمولاً اثبات 1 ساده است. اثبات 2 در بسياري حالات آسان‌تر از اثبات مستقيم قضيه است، زيرا مي‌توانيم از فرض درستي T براي n-1 استفاده كنيم. اين فرض، فرض استقرا نام دارد. به عبارت ديگر، فرض استقرا بي‌هيچ زحمتي در اختيار ماست. به جاي اثبات با دست خالي، مي‌توانيم درستي قضيه را براي مقادير كوچك‌تر n فرض بگيريم. پس ما بر اثبات قضيه از روي درستي آن براي مقادير كوچك‌تر تمركز مي‌كنيم. بياييد كار را با يك مثال آغاز كنيم:
.
.
.
فصل 3
تحليل الگوريتم‌ها
به بزرگي نيست وگرنه گاو از خرگوش جلو مي‌زد.
ضرب‌المثل آلماني‌‌هاي پنسيلوانيا
آن كس كه به ميوه‌هاي درختان سر به فلك كشيده مي‌نگرد، اما بلنداي آن درختان را اندازه نمي‌گيرد؛ احمقي بيش نيست.
Quintus Curtius Rufus
3-1 آشنايي
هدف از تحليل يك الگوريتم پيش‌بيني رفتار آن، به ويژه زمان اجراي آن است؛ بدون آن كه مجبور شويم آن الگوريتم را روي رايانه‌اي خاص پياده‌سازي كنيم. فايده‌ي چنين كاري روشن است: داشتن معيارهاي ساده‌اي براي كارايي يك الگوريتم بسيار راحت‌تر از آن است كه مجبور باشيم با هر تغييري در پارامترهاي يك رايانه، آن الگوريتم را از نو پياده‌سازي كنيم تا كارايي‌اش آشكار شود. يك برنامه‌ي پيچيده معمولاً الگوريتم‌هاي كوچك فراواني در خود دارد. بنابراين بررسي همه‌ي جاي‌گزين‌ها براي اين الگوريتم‌هاي كوچك، كاري بسيار وقت‌گير و خسته‌كننده است.
متأسفانه پيش‌بيني دقيق رفتار يك الگوريتم معمولاً غيرممكن است، چون عوامل فراواني بر آن تأثير مي‌گذارند. به جاي اين كار مي‌كوشيم تا ويژگي‌هاي اصلي الگوريتم را به دست آوريم؛ يعني پارامترها و معيارهاي مشخصي را تعريف مي‌كنيم كه در تحليل الگوريتم بيش‌ترين اهميت را دارند. پس بيش‌ترِ جزئيات پياده‌سازي را ناديده مي‌گيريم. بنابراين تحليل الگوريتم موضوعي تقريبي است و نبايد آن را ابزار كاملي براي پيش‌بيني رفتار الگوريتم‌ها به شمار آورد؛ به عبارت ديگر، حتا تقريب نادقيق هم مي‌تواند درباره‌ي الگوريتم، اطلاعات ارزشمندي به ما بدهد. مهم‌تر از همه، با اين روش مي‌توانيم الگوريتم‌هاي مختلف را با هم مقايسه كرده، دريابيم كدام يك از آن‌ها با اهدافمان سازگارتر است. اين موضوع را مي‌توان با ادعاي مصرف سوخت در خودروها مقايسه كرد و گفت: «اين معيارها تنها براي مقايسه‌اند و ممكن است زمان واقعي اجراي الگوريتم‌ها، كمتر يا بيش‌تر باشد».
.
.
.
تحليلي كه روي الگوريتم انجام مي‌دهيم بايد نشان دهد كه زمان اجرا براي يك ورودي مشخص چقدر پيش‌بيني مي‌شود؛ اما قادر نخواهيم بود زمان اجراي تمام ورودي‌ها را فهرست كنيم، مگر آن كه الگوريتم موردنظر واقعاً ساده باشد. ورودي، حالت‌هاي گوناگون بسياري دارد و بيش‌تر الگوريتم‌ها در برابر ورودي‌هاي مختلف، رفتارهاي متفاوتي از خود نشان مي‌دهند. به همين دليل، ورودي را با معياري به نام اندازه‌ي ورودي مي‌سنجيم و تحليل را بر پايه‌ي آن انجام مي‌دهيم. يك الگوريتم در برابر ورودي‌هاي هم‌اندازه رفتار دقيقاً يكساني ندارد ولي ما اميدواريم كه نوسانش، معقول و پذيرفتني باشد. معمولاً اندازه‌ي ورودي چنين تعريف مي‌شود: «فضاي لازم براي ذخيره‌ي ورودي». تلاش نمي‌كنيم تا براي همه‌ي الگوريتم‌ها تعريفي كلي از اندازه‌ي ورودي ارائه دهيم، زيرا در اصل علاقه‌منديم الگوريتم‌هاي مختلف يك مسأله را با هم مقايسه كنيم. بيش‌تر اوقات تعريف اندازه‌ي ورودي، كاري سرراست است كه به زودي چند مثال از آن خواهيم ديد. اندازه‌ي ورودي را با n نشان خواهيم داد، مگر آن كه به صراحت چيز ديگري گفته باشيم.
.
.
.
فصل 4
نگاهي کوتاه به ساختمان‌هاي داده‌اي
علم همان بديهيات است؛ پس از دسته‌بندي و آموزش.
T.H. Huxley
از روشن‌فکران بيزارم. آنان از بالا به پايين مي‌رسند؛ من از پايين به بالا.
Frank Lloyd Wright
4-1 آشنايي
ساختمان‌هاي داده‌اي، اجزاي سازنده‌ي الگوريتم‌هاي رايانه‌اي هستند. طراحي يک الگوريتم همانند طراحي يک ساختمان است. اتاق‌هاي يک ساختمان بايد به گونه‌اي در کنار هم قرار گيرند که براي کاربرد مورد نظر بيش‌ترين کارايي را داشته باشند. براي اين کار دانستن عملکرد، بهره‌وري، شکل و زيبايي، به تنهايي کافي نيست، بلکه به دانش کامل روش‌هاي ساختمان‌سازي نيازمنديم. ممکن است کارايي دل‌خواه ما قرار دادن اتاق در هوا، بين زمين و آسمان باشد، اما چنين کاري شدني نيست يا ممکن است برخي ايده‌هاي شدني، بسيار گران تمام شوند. به همين ترتيب، طراحي يک الگوريتم بايد بر مبناي درک کاملي از روش‌هاي ساختمان‌داده و هزينه‌ي هر يك از اين روش‌ها باشد.
در اين فصل تنها ساختمان‌هاي داده‌اي پايه را که در کتاب به کار رفته‌اند، بررسي مي‌کنيم. نمي‌خواهيم درباره‌ي تمام ساختمان‌هاي داده‌اي توضيح جامعي دهيم؛ چرا که براي اين کار (دست‌کم) به يک کتاب کامل نيازمنديم و بدون شک کتاب‌هاي خوبي در اين زمينه وجود دارند. انتظار داريم که بيش‌تر خوانندگان کم و بيش با ساختمان‌هاي داده‌اي آشنا باشند. هدف عمده‌ي اين فصل، نگاهي سريع به موضوع است.
يک روش مناسب در مطالعه‌ي ساختمان‌هاي داده‌اي، بررسي «داده‌گونه‌هاي مجرد» است. عموماً هنگام نوشتن برنامه، بايد نوع داده‌هاي به‌کاررفته (صحيح، اعشاري، کاراکتري و ...) را نيز مشخص کنيم؛ اما گاهي تعيين نوع داده‌ها در طراحي الگوريتم، موضوع مهمي نيست. مثلاً ممکن است بخواهيم يک صف ترتيبي از عناصر را نگه‌داري کنيم. اعمالي که در اينجا مورد نيازند، درج يک عنصر در صف و حذف آن از صف هستند. هنگام برداشتن عنصرها از صف بايد آن‌ها را به همان ترتيبي كه به صف افزوده شده‌اند، حذف كنيم. طراحي الگوريتم‌هاي اين اعمال (يعني درج يا حذف يک عنصر) بدون تعيين نوع داده‌ي عنصر، راحت‌تر و کلي‌تر است. بهتر است تنها، اعمال مورد نياز را مشخص کنيم؛ مثلاً در اين مورد خاص، به داده‌گونه‌ي مجردي که از اعمال گفته‌شده پشتيباني مي‌کند، صف ترتيبي مي‌گوييم. مهم‌ترين بخش هر داده‌گونه‌ي مجرد، فهرست اعمال مورد نياز آن است. مثال ديگري از داده‌گونه‌ي مجرد، صفي است که عناصر آن، اولويت هم دارند؛ يعني حذف آن‌ها بنا به ترتيب درجشان نيست، بلکه برحسب اولويت آنهاست. به عبارت ديگر، نخستين عنصري که در هر گام از عمل حذف، کنار گذاشته مي‌شود، عنصري است که در ميان عناصر صف، بيش‌ترين اولويت را داشته باشد. اين داده‌گونه‌ي مجرد، صف اولويت نام دارد. در اينجا هم، نوع داده‌اي عناصر را مشخص نمي‌کنيم. (حتا نيازي نيست که نوع داده‌اي اولويت‌ها را تعيين کنيم؛ تنها لازم است آن اولويت‌ها ترتيب كلي داشته باشند و ما بتوانيم ترتيب آن‌ها را تعيين کنيم.)
.
.
.
فصل 5
طراحي استقرايي الگوريتم‌ها
ريشه‌يابي اختراعات آن قدر اهميت دارد که به نظر من از خود اختراعات هم جالب‌تر است.
G. W. Leibniz
هر اختراعي موجب اختراعات ديگر مي‌شود.
R. W. Emerson
5-1 آشنايي
در اين فصل با الگوبرداري از استقراي رياضي، شيوه‌ي خودمان در طراحي الگوريتم را نشان مي‌دهيم. به اين منظور از مثال‌هاي نسبتاً ساده سود مي‌جوييم تا اصول و روش‌هاي پايه‌ي اين شيوه را معرفي كنيم. آنچه بايد در مورد استقرا بدانيم، در فصل 2 بيان شده است، اما به هنگام نياز، مطلب را تکرار مي‌کنيم تا اين فصل خودکفا باشد.
استقراي رياضي مانند دومينو است. تعدادي مهره‌ي دومينو را در نظر بگيريد که پشت‌سرهم چيده شده‌اند. مي‌خواهيم تنها با انداختن نخستين مهره، تمام آن‌ها را واژگون سازيم. براي اطمينان از اين رويداد کافي است مطمئن شويم که هر مهره پس از افتادن، مهره‌ي پس از خود را واژگون خواهد کرد. هر بار که مهره‌ي تازه‌اي به جمع مهره‌ها مي‌افزاييم، ديگر لازم نيست تمام آن‌ها را بيندازيم تا از درستي عملکرد مطمئن شويم. مي‌توان از اين اصل در طراحي الگوريتم هم بهره گرفت:
لازم نيست گام‌هاي مورد نياز براي حل مسأله را با دست خالي بپيماييم. کافي است تضمين کنيم که (1) نمونه‌ي کوچکي از مسأله حل‌شدني است (حالت پايه) و (2) مي‌توان راه‌حل نمونه‌هاي بزرگ‌تر مسأله را از روي حل نمونه‌هاي کوچک‌تر يافت (گام استقرا).
هنگامي كه مي‌خواهيم از اين اصل بهره‌برداري كنيم، بايد روي کاهش مسأله به مسأله‌اي کوچک‌تر (يا مجموعه‌اي از مسأله‌هاي کوچک‌تر) تمرکز کنيم؛ اما عموماً يافتن راهي براي کاهش اندازه‌ي مسأله چندان آسان نيست. در اين فصل چندين روش را براي آسان کردن اين فرايند نشان مي‌دهيم. مثال‌هاي اين فصل، نه به دليل زيادي اهميتشان در عمل (چراكه برخي از آن‌ها كاربرد اندكي دارند) بلكه به اين دليل بررسي شده‌اند که ساده هستند و اصول مورد تأكيد را به خوبي تشريح مي‌کنند. در کتاب نمونه‌هاي بسياري از اين رويکرد ارائه خواهيم کرد.
.
.
.
فصل 6
الگوريتم‌هاي دنباله‌ها و مجموعه‌ها
«نظم» را من دوست دارم بس زياد
بال خـود بر روي «بي‌نظـمي» نهاد
«سـادگي» را نغـمه‌خوانـي داد يـاد
Anna Hempstead Branch
6-1 آشنايي
در اين فصل با ورودي‌هايي سر و کار داريم که دنباله‌ها يا مجموعه‌هايي متناهي هستند. دنباله و مجموعه با يكديگر متفاوتند. در دنباله برخلاف مجموعه، ترتيب عناصر اهميت دارد. به علاوه، مي‌دانيم که در يک مجموعه، عنصر تکراري وجود ندارد، در صورتي که يک دنباله ممکن است عنصر تکراري هم داشته باشد. از آنجايي که معمولاً ورودي‌ها ترتيب مشخصي دارند، مي‌توان آن‌ها را «دنباله» در نظر گرفت. با اين حال، هنگامي که ترتيب ورودي براي ما مهم نباشد، مي‌توانيم ورودي را يک مجموعه در نظر بگيريم. در سرتاسر اين فصل، ورودي را با آرايه نمايش مي‌دهيم، مگر آن که به صراحت خلاف آن را گفته باشيم و فرض مي‌کنيم اندازه‌ي آرايه را از پيش مي‌دانيم. فرض بر اين است که عناصر مجموعه يا دنباله، از يك مجموعه با ترتيب کلي (مانند اعداد صحيح يا اعداد حقيقي) گرفته مي‌شوند و مي‌توان آن‌ها را با يكديگر مقايسه کرد. در اين فصل به مسأله‌هايي که عناصر آن‌ها هم‌نوع هستند، پرداخته‌ايم. موضوعاتي مانند بيشينگي، ترتيب، زيردنباله‌هاي ويژه، فشرده‌سازي داده‌ها و تشابه دنباله‌ها را در اين فصل بررسي مي‌کنيم.
در اين فصل، الگوريتم‌هاي بسياري را با کاربردهاي گوناگون مطرح مي‌كنيم. هدف ما اين بوده است که از شيوه‌ي طراحي گفته‌شده در فصل 5، مثال‌هاي بيش‌تري بياوريم و همراه با آن برخي الگوريتم‌هاي مهم را نيز تشريح کنيم. برخي از الگوريتم‌هاي آورده‌شده بسيار مهم و کاربردي هستند (مانند مرتب‌سازي و جستوجوي دودويي)، برخي با آن که اهميت چنداني ندارند، اما روش‌هاي جالبي را تشريح مي‌کنند (مانند يافتن دو عنصر بزرگ‌تر در يک مجموعه و مسأله‌ي زيردنباله‌ي ناپايدار) و برخي نيز با آن که مهم هستند، اما تنها در زمينه‌هاي خاصي به كار مي‌آيند (مانند فشرده‌سازي پرونده‌ها و مقايسه‌ي دنباله‌ها).
نخستين مثال اين فصل، جستوجوي دودويي است - الگوريتمي پايه‌اي و اساسي که گونه‌هاي بسياري دارد و در موارد گوناگوني ظاهر مي‌شود. پس از آن، مرتب‌سازي را مورد بحث و بررسي قرار مي‌دهيم که درباره‌ي آن مطالعات گسترده‌اي انجام شده است. سپس شما را با مرتبه‌ي آماري، فشرده‌سازي داده‌ها، الگوريتم‌هاي مبتني بر احتمال و دو مسأله از دست‌کاري متن آشنا مي‌کنيم. سرانجام، فصل را با چند مثال از الگوريتم‌هايي زيبا و عالي به پايان مي‌رسانيم كه روش‌هاي جالبي از طراحي الگوريتم را تشريح مي‌كنند.
.
.
.
فصل 7
الگوريتم‌هاي گراف
راه ميان‌بر، طولاني‌ترين راه بين دو نقطه است.
ناشناس
7-1 آشنايي
در فصل پيش، الگوريتم‌هايي را براي كار با مجموعه‌ها يا دنباله‌هايي از اشياء بررسي كرديم و به رابطه‌هايي مانند ترتيب، تكرار و هم‌پوشاني برخورديم. در اين فصل، با رابطه‌هاي بيش‌تري بين اشياء آشنا خواهيم شد و گراف‌ها را براي مدل‌سازي اين رابطه‌ها به كار خواهيم گرفت. گراف‌ها مي‌توانند وضعيت‌هاي بسيار گوناگوني را مدل كنند و در زمينه‌هاي بسياري از باستان‌شناسي گرفته تا روان‌شناسي اجتماعي كاربرد دارند. در اين فصل، براي كار با گراف‌ها و محاسبه‌ي ويژگي‌هاي مشخصي از آن‌ها، چندين الگوريتم مهم و پايه‌اي را به شما معرفي خواهيم كرد.
نخست، به نمونه‌هايي از مدل‌سازي با گراف نگاهي مي‌اندازيم:
1- يافتن مسيري خوب از خانه تا رستوراني در شهر؛ خيابان‌ها متناظر با يال‌ها (اگر خيابان‌ها يك‌طرفه باشند، يال‌هاي جهت‌دار) و تقاطع خيابان‌ها متناظر با رأس‌ها هستند. براي هر رأس و هر يال (هر تكه از خيابان كه بين دو تقاطع است) زمان تأخيري مورد انتظار است و مسأله، يافتن «سريع‌ترين» مسير بين دو رأس است.
2- برخي برنامه‌هاي رايانه‌اي را مي‌توان به وضعيت‌هاي گوناگون تقسيم كرد. ممكن است در هر يك از اين وضعيت‌ها، حالت‌هاي مختلفي براي پيش‌روي وجود داشته باشد و برخي از اين وضعيت‌ها نيز ممكن است نامطلوب باشند. يافتن وضعيت‌هايي كه به يك حالت نامطلوب منجر مي‌شوند، مسأله‌ي ديگري از نظريه‌ي گراف است كه در آن هر وضعيت، متناظر با يك رأس و هر يال متناظر با امكان پيش‌روي از يك وضعيت به وضعيت ديگر خواهد بود.
3- به مسأله‌ي برنامه‌ريزي كلاس‌هاي يك دانشگاه مي‌توان به صورت مسأله‌اي از نظريه‌ي گراف نگريست. رأس‌ها بيانگر كلاس‌ها هستند و اگر دانش‌آموزي بخواهد دو كلاس را با هم بگيرد، يا استادي بخواهد در هر دو كلاس تدريس كند، آنگاه آن دو كلاس را به يكديگر متصل مي‌كنيم. مسأله، برنامه‌ريزي كلاس‌هاست، به گونه‌اي كه تعداد تداخل كلاس‌ها كمينه گردد. اين مسأله دشوار است و به راحتي نمي‌توان راه‌حل مناسبي براي آن يافت.
4- يك سامانه‌ي رايانه‌اي با چندين حساب كاربري در نظر بگيريد كه در آن هر كاربر براي دست‌رسي به حساب خود، مجوز يا امتيازي امنيتي دارد. ممكن است كاربران بخواهند با يكديگر همكاري كنند و اجازه‌ي دست‌رسي به حساب خود را در اختيار كاربر ديگري هم بگذارند. از سويي، اگر كاربر A به حساب كاربر B و كاربر B به حساب كاربر C دست‌رسي داشته باشد، آنگاه A نيز به حساب كاربر C دست‌رسي خواهد داشت. مسأله‌ي تعيين دست‌رسي كاربران به حساب‌هاي يكديگر، مسأله‌اي ديگر از نظريه‌ي گراف است. در اينجا، كاربران با رأس‌ها متناظر مي‌شوند و اگر كاربر A اجازه‌ي دست‌رسي به حساب خود را به كاربر B بدهد، يالي جهت‌دار از A به B وجود خواهد داشت.
.
.
.
اشتراک در:
پست‌ها (Atom)