آموزش الگوریتم‌های بهینه از نظر I/O - آخرین آپدیت

مقدمه Introduction

• چرا الگوریتم‌های بهینه I/O Why I/O-efficient Algorithms

• مدل پایه I/O The basic I/O-model

• تحلیل الگوریتم‌ها در مدل I/O Analyzing algorithms in the I/O-model

• تحلیل الگوریتم‌ها در مدل I/O، بخش دوم Analyzing algorithms in the I/O-model, II

• الگوریتم‌های آگاه از کش در مقابل بی‌اطلاع از کش Cache-aware versus cache-oblivious algorithms

طراحی الگوریتم‌های آگاه از کش و بی‌اطلاع از کش Designing cache-aware and cache-oblivious algorithms

• مسئله ترانهاده ماتریس The matrix-transposition problem

• یک الگوریتم آگاه از کش برای ترانهاده ماتریس A cache-aware algorithm for matrix transposition

• یک الگوریتم بی‌اطلاع از کش برای ترانهاده ماتریس A cache-oblivious algorithm for matrix transposition

سیاست‌های جایگزینی Replacement Policies

• سیاست‌های جایگزینی Replacement Policies

مرتب‌سازی بهینه از نظر I/O I/O-efficient sorting

• مرتب‌سازی بهینه I/O، بخش اول I/O-Efficient sorting, I

• مرتب‌سازی بهینه I/O، بخش دوم I/O-Efficient sorting, II

ساختارهای داده بهینه از نظر I/O I/O-efficient data structures

• جستجوی بهینه اول: درخت‌های B Efficient searching I: B-Trees

• جستجوی بهینه دوم: درخت‌های بافری Efficient searching II: Buffer Trees

• صف‌های اولویت بهینه از نظر I/O I/O-Efficient Priority queues

پردازش پیشرو در زمان Time-Forward Processing

• ارزیابی توابع محلی روی یک DAG Evaluating local functions on a DAG

• ارزیابی توابع محلی روی یک DAG: تحلیل I/O Evaluating local function on a DAG: I/O-analysis

• پردازش پیشرو در زمان Time-forward processing

• محاسبه مجموعه‌های مستقل حداکثری Computing maximal independent sets