در این بخش، به دنیای برنامهنویسی، الگوریتمها، شبکه و زیرساختهای فناوری میپردازیم
مقایسه منصفانه یک CPU و یک GPU نیازمند مدلی است که هم توان عملیاتی محاسباتی و هم محدودیتهای پهنای باند حافظه را با هم در نظر بگیرد. این مقاله مدل roofline مورد استفاده برای مقایسه سختافزار واقعی مانند Intel Core i7 و NVIDIA Tesla GPU را معرفی میکند، سپس نشان میدهد ضرب ماتریس چگونه در سراسر چند پردازنده تسریع میشود، بهعنوان کاربرد عملی نهایی مفاهیم موازی این فصل.
پس از پوشش هر چیزی از موازیسازی سطح رشته تا محاسبات در مقیاس انبار، ارزش دارد تصورات غلط پایداری درباره سیستمهای موازی که حتی مهندسان باتجربه هم گاهی به آنها دارند را اصلاح کنیم. این مقاله به مغالطات رایج درباره مقیاسپذیری و سختافزار موازی میپردازد، سپس فصل پردازش موازی را با پیوند دادن مسیر کامل از یک دستور منفرد تا یک ساختمان پر از ماشینهای همکار به پایان میرساند.
پیش از پرداختن به الگوریتمهای خاص، ضروری است درک کنیم یک الگوریتم واقعاً چیست، چرا مطالعه الگوریتمها حتی با سختافزار سریع امروزی اهمیت دارد، و چگونه کارایی یک الگوریتم را بهطور دقیق تحلیل کنیم. این راهنمای جامع تعریف رسمی الگوریتم را پوشش میدهد، insertion sort را بهعنوان اولین مثال کامل مرور میکند، و تکنیکهای اصلی برای سنجش و مقایسه زمان اجرا را معرفی میکند.
مقایسه منصفانه الگوریتمها نیازمند یک زبان ریاضی است که فاکتورهای ثابت را نادیده بگیرد و روی نرخ رشد با بزرگشدن اندازه ورودی تمرکز کند. این راهنمای جامع تعاریف رسمی نمادگذاری Big-O، Big-Omega، و Big-Theta را پوشش میدهد، توضیح میدهد چگونه کرانهای مجانبی را مستقیماً از تعاریفشان اثبات کنیم، و توابع و نرخهای رشد استانداردی که هر تحلیل الگوریتمی به آنها متکی است را مرور میکند.
ضرب دو ماتریس یک عملیات بنیادین در علوم کامپیوتر است، و رویکرد ساده بسیار دور از بهینه است. این راهنمای جامع الگوریتم استاندارد ضرب ماتریس با زمان مکعبی را توضیح میدهد، نشان میدهد چگونه یک رویکرد تقسیموغلبه ساده در بهبود آن شکست میخورد، و الگوریتم قابلتوجه اشتراسن که به یک زمان اجرای مجانبی واقعاً سریعتر میرسد را مرور میکند.
زمان اجرای هر الگوریتم تقسیموغلبه توسط یک رابطه بازگشتی توصیف میشود، و حل آن رابطه برای درک کارایی الگوریتم ضروری است. این راهنمای جامع سه تکنیک استاندارد برای حل رابطههای بازگشتی را پوشش میدهد: روش substitution برای اثبات یک کران حدسزدهشده، روش recursion-tree برای تولید یک حدس، و روش استاد بهعنوان یک میانبر سریع برای یک دسته رایج از رابطههای بازگشتی.
برخی الگوریتمها در حین اجرا انتخابهای تصادفی میکنند، و تحلیل رفتار مورد انتظارشان نیازمند جعبهابزاری متفاوت از تحلیل بدترینحالت بهتنهایی است. این راهنمای جامع تحلیل احتمالاتی را از طریق مسئله کلاسیک استخدام معرفی میکند، متغیرهای تصادفی نشانگر را بهعنوان یک ابزار تحلیلی قدرتمند توضیح میدهد، و نشان میدهد تصادفیسازی چگونه میتواند کارایی مورد انتظار یک الگوریتم را بهبود بخشد.
هیپ دودویی یکی از ظریفترین ساختارهای داده در علوم کامپیوتر است، که هم یک الگوریتم مرتبسازی کارآمد درجا و هم انتزاع صف اولویت مورد استفاده در سراسر طراحی الگوریتم را ممکن میسازد. این راهنمای جامع ویژگیهای هیپ و نمایش آرایهای، عملیات اصلی heapify، ساخت یک هیپ از یک آرایه مرتبنشده، الگوریتم کامل heapsort، و عملیاتهای صف اولویت ساختهشده روی هیپها را پوشش میدهد.
Quicksort یکی از پراستفادهترین الگوریتمهای مرتبسازی در عمل است، که بهخاطر کارایی عالی حالتمیانگین و عملیات درجا ارزشمند است، با وجود داشتن بدترینحالت نظری ضعیف. این راهنمای جامع الگوریتم مبتنی بر partition را با جزئیات پوشش میدهد، هم زمان اجرای بدترینحالت و هم مورد انتظار آن را تحلیل میکند، و توضیح میدهد تصادفیسازی چگونه آن را به یک الگوریتم بهطور قابلاعتماد کارآمد صرفنظر از ترتیب ورودی تبدیل میکند.
هر الگوریتم مرتبسازی مبتنی بر مقایسه در بدترینحالت حداقل به زمان Ω(n log n) نیاز دارد، اما الگوریتمهایی که کاملاً از مقایسه اجتناب میکنند میتوانند تحت شرایط درست در زمان خطی مرتب کنند. این راهنمای جامع کران پایین مرتبسازی مبتنیبرمقایسه را با استدلال درخت تصمیم اثبات میکند، سپس سه الگوریتم زمان-خطی — counting sort، radix sort، و bucket sort — را همراه با فرضیات ورودی خاصی که هرکدام نیاز دارند توضیح میدهد.
یافتن k-امین کوچکترین عنصر در یک آرایه مرتبنشده نیازمند هزینه کامل Θ(n log n) مرتبسازی نیست؛ میتواند در زمان خطی انجام شود. این راهنمای جامع مورد بدیهی یافتن حداقل یا حداکثر، یک الگوریتم انتخاب تصادفی ظریف با زمان مورد انتظار خطی، و یک الگوریتم قطعی پیچیدهتر که زمان خطی را حتی در بدترینحالت تضمین میکند را پوشش میدهد.
پیش از پرداختن به ساختارهای داده پیشرفته، تسلط بر بلوکهای سازنده ابتدایی ضروری است، چون تقریباً هر ساختار پیچیدهای از این پایهها ساخته میشود. این راهنمای جامع پشتهها و صفهای مبتنی بر آرایه، لیستهای پیوندی تکی و دوگانه، و تکنیکهای استاندارد نمایش درختهای ریشهدار را پوشش میدهد، شامل نمایش ظریف فرزند-چپ راهبر-راست برای درختهایی با شاخهبندی نامحدود.
