هذا الكتاب مخصص لخمسة مبادئ رئيسية لتصميم الخوارزمية: فرق تسد ، خوارزميات الجشع ، التخفيف ، البرمجة الديناميكية ، والبحث الشامل. يتم تقديم هذه المبادئ باستخدام Haskell ، وهي لغة وظيفية بحتة ، تؤدي إلى تفسيرات أبسط وبرامج أقصر مما يمكن الحصول عليه باللغات الضرورية. تكشف الأمثلة المختارة بعناية ، الجديدة والمعيارية ، القواسم المشتركة وتسلط الضوء على الاختلافات بين الخوارزميات. تستخدم تطورات الخوارزمية الاستدلال المعادل عند الاقتضاء ، مع توضيح شروط التطبيق وحجج الصواب. يختتم كل فصل بتمارين (ما يقرب من 300 في المجموع) ، لكل منها إجابات كاملة ، مما يسمح للقارئ بتعزيز فهمه وتطبيق التقنيات على مجموعة من المشاكل.
يخدم الكتاب الطلاب (الجامعيين وطلاب الدراسات العليا) والباحثين والمعلمين والمهنيين الذين يرغبون في معرفة المزيد حول ما يدخل في خوارزمية جيدة وكيف يمكن التعبير عن هذه الخوارزميات بمصطلحات وظيفية بحتة.
محتويات
الصفحة التمهيدية xiii
أساسيات الجزء الأول 1
1 البرمجة الوظيفية 5
1.1 الأنواع والوظائف الأساسية 5
1.2 قوائم المعالجة 7
1.3 التعريفات الاستقرائية والعودية 9
1.4 فيوجن 11
1.5 تراكم وتبويب 14
1.6 ملاحظات الفصل 16
المراجع 16
تمارين 16
الإجابات 19
2 التوقيت 25
2.1 تدوين مقارب 25
2.2 تقدير أوقات التشغيل 27
2.3 أوقات التشغيل في السياق 32
2.4 أوقات التشغيل المطفأة 34
2.5 ملاحظات الفصل 38
المراجع 38
تمارين 38
الإجابات 40
3 هياكل البيانات المفيدة 43
3.1 القوائم المتماثلة
المحتويات viii
3.2 قوائم الوصول العشوائي 47
3.3 المصفوفات 51
3.4 ملاحظات الفصل 53
المراجع 54
تمارين 54
الإجابات 56
الجزء الثاني الفرقة والغزو 59
4 Binarysearch 63
4.1 مشكلة بحث أحادية البعد 63
4.2 مشكلة بحث ثنائية الأبعاد 67
4.3 أشجار البحث الثنائية 73
4.4 المجموعات الديناميكية 81
4.5 ملاحظات الفصل 84
المراجع 84
تمارين 85
الإجابات 87
5 الفرز 93
5.1 الترتيب السريع 94
5.2 ترتيب الدمج 96
5.3 Heapsort 101
5.4 Bucketsort و Radixsort 102
5.5 فرز المجاميع 106
5.6 ملاحظات الفصل 110
110ـ المراجع
تمارين 111
الإجابات 114
6 الاختيار 121
6.1 الحد الأدنى والحد الأقصى 121
6.2 الاختيار من مجموعة واحدة 124
6.3 الاختيار من مجموعتين 128
6.4 التحديد من تكملة مجموعة 132
6.5 ملاحظات الفصل 135
المراجع 135
تمارين 135
الإجابات 137
المحتويات التاسع
الجزء الثالث الخوارزميات الخضراء 141
7 الخوارزميات الجشعة في القوائم 145
7.1 خوارزمية الجشع العامة 145
7.2 خوارزميات الفرز الجشعة 147
7.3 تغيير العملات 151
7.4 الكسور العشرية في TEX 156
7.5 وظائف غير حتمية وصقل 161
7.6 ملخص 165
7.7 ملاحظات الفصل 165
المراجع 166
تمارين 166
الإجابات 170
8 الخوارزميات الجشعة على الأشجار 177
8.1 الأشجار ذات الارتفاع الأدنى 177
8.2 أشجار ترميز هوفمان 187
8.3 طوابير الأولوية 196
8.4 ملاحظات الفصل 199
المراجع 199
تمارين 199
الإجابات 201
9 الخوارزميات الجشعة على الرسوم البيانية 205
9.1 الرسوم البيانية والأشجار الممتدة 205
9.2 خوارزمية Kruskal 208
9.3 المجموعات المنفصلة وخوارزمية البحث عن الاتحاد 211
9.4 خوارزمية Prim 215
9.5 أقصر المسارات أحادية المصدر 219
9.6 خوارزمية ديكسترا 220
9.7 مشكلة العداء ببطء 224
9.8 ملاحظات الفصل 228
المراجع 228
تمارين 229
الإجابات 231
الجزء الرابع الخوارزميات الرقيقة 237
10 مقدمة للتخفيف 241
10.1 نظرية 241
10.2 المسارات في شبكة ذات طبقات 244
10.3 إعادة النظر في تغيير العملة 248
x المحتويات
10.4 مشكلة الحقيبة 252
10.5 خوارزمية التخفيف العامة 255
10.6 ملاحظات الفصل 257
المراجع 257
تمارين 257
الإجابات 261
11 المقاطع وما يليها 267
11.1 أطول نتيجة 267
11.2 أطول نتيجة شائعة تالية 270
11.3 مقطع قصير بحد أقصى 274
11.4 ملاحظات الفصل 280
المراجع 281
تمارين 281
الإجابات 283
12 أقسام 289
12.1 طرق إنشاء الأقسام 289
12.2 إدارة حسابين بنكيين 291
12.3 مشكلة الفقرة 294
12.4 ملاحظات الفصل 299
المراجع 300
تمارين 300
الإجابات 303
الجزء الخامس البرمجة الديناميكية 309
13 العودية الفعالة 313
13.1 مثالان رقميان 313
13.2 إعادة النظر في الحقيبة 316
13.3 تسلسلات التحرير ذات التكلفة الدنيا 319
13.4 الأطول الشائعة اللاحقة تمت إعادة النظر فيها 322
13.5 مشكلة الباص 323
13.6 ملاحظات الفصل 326
المراجع 326
تمارين 327
الإجابات 330
14 الأقواس الأمثل 335
14.1 خوارزمية الوقت المكعب 336
14.2 خوارزمية تربيعية الوقت 339
14.3 أمثلة 341
المحتويات xi
14.4 إثبات الرتابة 345
14.5 أشجار البحث الثنائية المثلى 347
14.6 خوارزمية Garsia-Wachs 349
14.7 ملاحظات الفصل 358
المراجع 358
تمارين 359
الإجابات 362
365 مشروع صناعة الحديد والصلب 365
15 طرق البحث 369
15.1 البحث الضمني ومسألة n-queens 369
15.2 التعبيرات ذات المجموع المحدد 376
15.3 بحث العمق الأول والعرض الأول 378
15.4 الهبوط على سطح القمر 383
15.5 التخطيط المستقبلي 386
15.6 ساعة الذروة 389
15.7 ملاحظات الفصل 393
المراجع 394
تمارين 395
الإجابات 398
16 البحث الارشادي 405
16.1 البحث بإرشادية متفائلة 406
16.2 البحث بإرشادية رتيبة 411
16.3 الإبحار في مستودع 415
16.4 لغز 8 419
16.5 ملاحظات الفصل 425
المراجع 425
تمارين 426
الإجابات 428
الفهرس 432
