الگوریتم های کارآمد ورودی/خروجی

الگوریتم‌های کارآمد ورودی/خروجی، که به‌عنوان الگوریتم‌های حافظه خارجی یا الگوریتم‌های حافظه پنهان نیز شناخته می‌شوند، دسته‌ای از الگوریتم‌ها هستند که برای پردازش کارآمد داده‌هایی طراحی شده‌اند که خیلی بزرگ هستند و نمی‌توانند به طور کامل در حافظه اصلی (RAM) رایانه جای بگیرند. این الگوریتم‌ها به‌ویژه هنگام برخورد با مجموعه داده‌های عظیم، مانند مواردی که در پردازش داده‌های مقیاس بزرگ، مدیریت پایگاه داده و سیستم‌های فایل یافت می‌شوند، مفید هستند. زمانی که آیتم داده در سلسله مراتب حافظه بالاتر قرار گیرد، عملیات روی داده گران تر می شود. یک عملیات روی داده در رجیسترهای CPU تقریباً یک میلیون بار سریعتر از عملیات روی یک آیتم داده است که در حافظه خارجی قرار دارد و ابتدا باید واکشی شود. این واکشی داده ها را عملیات ورودی/خروجی نیز می نامند و باید در طول طراحی الگوریتم مورد توجه قرار گیرند. هدف از این دوره آشنایی با مفاهیم و تکنیک های الگوریتمی مهم مورد نیاز برای مقابله موثر با چنین مسائلی است. ما با یک سلسله مراتب حافظه ساده کار خواهیم کرد، اما مفاهیم به طور طبیعی به مدل های واقعی تر گسترش می یابد. پیش نیازها: برای گذراندن موفقیت آمیز این دوره، باید از قبل دانش پایه ای از الگوریتم ها و ریاضیات داشته باشید. در اینجا لیست کوتاهی از آنچه باید بدانید آمده است: - O-notation، Ω-notation، Θ-notation; نحوه تجزیه و تحلیل الگوریتم ها - حساب پایه: دستکاری جمع، حل عود، کار با لگاریتم و غیره. - نظریه احتمال پایه: رویدادها، توزیع های احتمال، متغیرهای تصادفی، مقادیر مورد انتظار و غیره. - ساختارهای داده پایه: لیست های پیوندی، پشته ها، صف ها، پشته ها - درختان جستجوی دودویی (متوازن). - الگوریتم های مرتب سازی اولیه، به عنوان مثال MergeSort، InsertionSort، QuickSort - اصطلاحات نمودار، نمایش گراف ها (لیست مجاورت و ماتریس مجاورت)، الگوریتم های اصلی گراف (BFS، DFS، مرتب سازی توپولوژیکی، کوتاه ترین مسیرها) مطالب این دوره بر اساس یادداشت های دوره است که در زیر برگه منابع یافت می شود. ما همه چیز را از یادداشت های دوره پوشش نمی دهیم. یادداشت های دوره هم برای دانش آموزانی که سخنرانی ها را به طور کامل درک نمی کنند و هم برای دانش آموزانی که مایلند عمیق تر در موضوعات غوطه ور شوند وجود دارد. سخنرانی های ویدیویی حاوی چند اشتباه بسیار جزئی است. فهرستی از این اشتباهات را می توان در زیر منابع یافت. اگر فکر می‌کنید خطایی پیدا کرده‌اید، با کلیک کردن روی علامت مربع در پایین سخنرانی یا امتحانی که در آن خطا را پیدا کردید، مشکل را گزارش کنید.