در دنیای برنامهنویسی و علوم کامپیوتر، الگوریتمها و ساختمانهای داده دو ستون اصلی برای حل مسائل پیچیده به صورت کارآمد و بهینه هستند.
درخت جستجوی دودویی ساده که پیشتر در این مجموعه پوشش داده شد، میتواند تحت ترتیبهای درج بدشانس به ارتفاع خطی تنزل یابد. درختهای قرمز-سیاه این را با حفظ پنج ناوردای ساده که از نظر ریاضی ارتفاع لگاریتمی را صرفنظر از ترتیب درج تضمین میکنند حل میکنند. این راهنمای جامع ویژگیهای قرمز-سیاه، عملیات چرخش که ساختار درخت-جستجو را حین بازساختاردهی درخت حفظ میکند، و اینکه درج و حذف چگونه با منطق تعادلمجدد گسترش مییابند تا این تضمینها را حفظ کنند را پوشش میدهد.
برنامهنویسی پویا مسائل پیچیده را با شکستن آنها به زیرمسئلههای همپوشان و ذخیره راهحلها برای اجتناب از محاسبه زائد حل میکند. این راهنمای جامع تکنیک را از طریق مسئله کلاسیک برش میله معرفی میکند، آن را به مسئله جزئیتر ضرب زنجیرهای ماتریس گسترش میدهد، و دو ویژگی ضروری — زیرساختار بهینه و زیرمسئلههای همپوشان — که تعیین میکنند چه زمانی برنامهنویسی پویا اعمال میشود را استخراج میکند.
دو مسئله کلاسیک برنامهنویسی پویای دیگر، تطبیقپذیری این تکنیک را فراتر از بهینهسازی عددی نشان میدهند: یافتن طولانیترین زیردنباله مشترک بین دو رشته، سنگبنای ابزارهای diff و بیوانفورماتیک، و ساخت یک درخت جستجوی دودویی که هزینه جستجوی مورد انتظار را با فرکانسهای دسترسی شناختهشده کمینه میکند. این راهنمای جامع هر دو الگوریتم را با جزئیات کامل، شامل استخراج رابطه بازگشتی، ساخت جدول، و بازسازی راهحل، مرور میکند.
الگوریتمهای حریصانه یک راهحل را قطعهبهقطعه میسازند، و همیشه گزینهای که در لحظه فعلی بهترین بهنظر میرسد را انتخاب میکنند، بدون هرگز بازبینی آن انتخاب بعداً، با این حال برای مسائل خاصی این استراتژی ساده بهطور اثباتپذیر یک نتیجه بهینه سراسری تولید میکند. این راهنمای جامع مسئله انتخاب فعالیت را بهعنوان یک مثال انگیزاننده پوشش میدهد، اصول کلی که تعیین میکنند چه زمانی الگوریتمهای حریصانه کار میکنند را استخراج میکند، و کدگذاری هافمن، یک الگوریتم حریصانه بهطور گسترده استفادهشده برای فشردهسازی بهینه داده، را توضیح میدهد.
برخی عملیاتهای ساختار داده گاهی زمان طولانی میگیرند، اما میانگینگیریشده در سراسر یک توالی کامل از عملیاتها، هزینه بهازای هر عملیات واقعاً بسیار پایین است. تحلیل مستهلک ابزارهای دقیقی برای اثبات این کارایی میانگین بدون تکیه بر احتمال یا فرضیات غیرواقعبینانه ورودی فراهم میکند. این راهنمای جامع سه تکنیک استاندارد تحلیل مستهلک را از طریق مثالهای کلاسیک آرایه پویا و شمارنده باینری پوشش میدهد.
وقتی داده بهاندازهای بزرگ است که در حافظه جا نمیشود و باید روی دیسک ذخیره شود، کمینهکردن تعداد دسترسیهای دیسک بسیار مهمتر از کمینهکردن مقایسهها میشود. این راهنمای جامع درختهای B را توضیح میدهد، یک ساختار درخت جستجوی متوازن که بهطور خاص برای کمینهکردن ورودی/خروجی دیسک با نگهداشتن کلیدهای زیاد بهازای هر گره طراحی شده، و ویژگیهای تعریفکننده، رویه جستجو، و تکنیک درج مبتنی بر تقسیم که توازن را حفظ میکند را پوشش میدهد.
بسیاری الگوریتمها نیاز دارند یک مجموعه پویا از مجموعههای مجزا را ردیابی کنند، و بهطور مکرر مجموعهها را ادغام کرده و پرسوجو کنند کدام مجموعه یک عنصر متعلق به آن است. این راهنمای جامع نمایش جنگل مجموعهمجزا، دو بهینهسازی حیاتی union by rank و path compression، و زمان اجرای مستهلک تقریباً-ثابتی که این بهینهسازیها با هم دست مییابند، نتیجهای مرکزی برای الگوریتمهایی مانند درخت پوشای کمینه کروسکال، را پوشش میدهد.
گرافها روابط بین اشیا را مدلسازی میکنند، و تقریباً هر الگوریتم گراف روی دو استراتژی پیمایش بنیادین ساخته میشود. این راهنمای جامع دو نمایش استاندارد گراف، لیستهای مجاورت و ماتریسهای مجاورت، را پوشش میدهد، سپس جستجوی سطحاول برای یافتن کوتاهترین مسیرها در گرافهای بدونوزن و جستجوی عمقاول برای کاوش ساختار و تشخیص چرخهها را توضیح میدهد، شامل ویژگیهای زمانبندیشان که در الگوریتمهای گراف بعدی استفاده میشوند.
ویژگیهای زمانبندی جستجوی عمقاول دو الگوریتم گراف قدرتمند با کاربرد عملی گسترده را باز میکنند: مرتبکردن وظایفی که وابستگی دارند، و شناسایی خوشههای بهشدت متصل درون یک گراف جهتدار. این راهنمای جامع مرتبسازی توپولوژیک برای زمانبندی وظایف وابسته را توضیح میدهد، سپس الگوریتم DFS دوعبوری ظریف برای یافتن مؤلفههای قویاًمتصل را مرور میکند.
اتصال مجموعهای از مکانها با کمترین هزینه کل اتصالات یک مسئله بهینهسازی کلاسیک با راهحلهای حریصانه ظریف است. این راهنمای جامع مسئله درخت پوشای کمینه را توضیح میدهد، قضیه عمومی مبتنی بر برش که رویکردهای حریصانه برای آن را توجیه میکند اثبات میکند، و هم الگوریتم کروسکال، ساختهشده روی ساختار مجموعهمجزا، و هم الگوریتم پریم، ساختهشده روی یک صف اولویت، را مرور میکند.
یافتن کوتاهترین مسیرها در یک گراف وزندار پیچیدهتر از حالت بدونوزن حلشده توسط جستجوی سطحاول است، بهویژه وقتی وزنهای یال منفی ممکن باشند. این راهنمای جامع تکنیک relaxation زیربنای همه الگوریتمهای کوتاهترینمسیر، الگوریتم بلمن-فورد که وزنهای منفی را مدیریت میکند و چرخههای منفی را تشخیص میدهد، و الگوریتم کارآمدتر دیجکسترا برای گرافهای بدون وزنهای منفی را پوشش میدهد.
گاهی یک اپلیکیشن به کوتاهترین فاصله بین هر جفت رأس ممکن نیاز دارد، نه فقط از یک منبع واحد. این راهنمای جامع مسئله کوتاهترین مسیرهای همهجفت را توضیح میدهد، رابطه بازگشتی برنامهنویسی پویای ظریف پشت الگوریتم فلوید-وارشال را استخراج میکند، و کارایی آن را در برابر اجرای مکرر الگوریتمهای منبع-واحد مقایسه میکند.
