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