طراحي الگوريتم با رويكردي خلاقانه
نوشته‌ي يودي منبر، ترجمه‌ي احمد صادقي صفت و سيد علي حسيني، جلد نخست
شماره‌ي شابك: 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 وجود خواهد داشت.
.
.
.
۳ نظر:
خیلی کار خوبی بود
من که هنوز ترجمه شده کتاب رو نخوندم
ولی با این حال کار مفیدی هستش
این کتاب به زبان اصلیش هم کمیابه، امیدوارم ترجمه شدش مشکلی نداشته باشه
و از شما تشکر می کنم
با سلام خدمت نویسندگان عزیز کتاب از شما می خواهم جلد دوم این کتاب را به زودی منتشر کنیدممنونم
khastam bedonam chetor mishe in ketabo tahaye kad ba tashakor az hamaton
ارسال یک نظر