ورود / ثبت‌نامورود
خودآموز بنیاد: ساختمانی که فقط طرحِ خطی است و پیِ زیرِ آن با جک‌های آزمایشِ بار و ساعت‌های اندازه‌گیری، به‌تفصیل کشیده شده

خودآموز تعاملی

بنیاد — الگوریتم، ساختار داده و پیچیدگی، با معیار

۶ ترم۴۹ فصل ۱۵ فصل رایگان

هنوز کسی امتیاز نداده

کدت درست کار می‌کند و روی دادهٔ واقعی غیرقابلِ استفاده است. این دوره می‌گوید چرا — و مهم‌تر، چطور قبل از اجرا پیش‌بینی‌اش کنی: اندازه‌گیریِ صادقانهٔ زمان، Big-O به‌عنوان یک پیش‌بینی که آزمون می‌دهد، list و hash و درخت و گراف، مرتب‌سازی و جست‌وجو، و یک قاعدهٔ سخت — هیچ ادعای پیچیدگی بدونِ جدولِ اندازه‌گیری. همه در Google Colab، فقط روی CPU و فقط با کتابخانهٔ استاندارد.

  • کدنویسی متنی
  • آزمایشگاه زنده در مرورگر
جلسه اول را رایگان بخوان

فهرست کتاب

۶ ترم، ۴۹ فصل — به ترتیب.

۱«سریع» یعنی چه: اول اندازه بگیر، بعد پیش‌بینی کنترم ۱ · ۱۰ فصلترم ۱ بنیاد — اول اندازه بگیر: چهار نمونهٔ بزرگ‌شونده، کرنومتر، و منحنی‌ای که تا حلقهٔ هدف در شبکهٔ خالی ادامه یافته
  1. یک ماشینِ مقایسه‌گرِ دستی کنارِ قیفی صد برابر بزرگ‌تر از خودشفصل ۰۱ — کدی که درست کار می‌کند و غیرقابلِ استفاده استرایگان
  2. یک کرنومترِ مکانیکی که پنج عقربهٔ ثبت‌شده روی صفحه‌اش در نقاطِ متفاوتی ایستاده‌اندفصل ۰۲ — ساعتِ صادق: تکرار، کمینه، گرم‌کردنرایگان
  3. ترازویی با دو کفهٔ دقیقاً هم‌وزن که عقربه‌اش زیرِ لرزشِ میز تکان می‌خوردفصل ۰۳ — نویز: چرا همان کد دو بارِ پشتِ‌هم دو عدد می‌دهدرایگان
  4. دو ابزارِ اندازه‌گیری کنارِ هم: کرنومتری با عقربهٔ لرزان و شمارنده‌ای مکانیکی با ارقامِ قفل‌شدهفصل ۰۴ — عمل بشمار، نه ثانیهرایگان
  5. نردبانی که فاصلهٔ هر پله تا پلهٔ بعد دقیقاً دو برابرِ فاصلهٔ قبلی استفصل ۰۵ — جدولِ دوبرابری: `n` را دو برابر کن و نگاه کنرایگان
  6. شش لولهٔ شیشه‌ای هم‌قد که مایع در هرکدام تا ارتفاعِ کاملاً متفاوتی بالا آمدهفصل ۰۶ — شش منحنی که تقریباً همه‌چیز را توضیح می‌دهندرایگان
  7. یک ذره‌بین بزرگ روی یک عبارتِ سه‌جمله‌ای که فقط جملهٔ اول را پررنگ نگه داشتهفصل ۰۷ — `Big-O`: یک پیش‌بینی، نه یک برچسبرایگان
  8. دو خط‌کشِ فنری روی یک منحنی، که یکی از روی بازهٔ کوتاه تنظیم شده و یکی از روی بازهٔ بلندفصل ۰۸ — برازش کن، پیش‌بینی کن، اجرا کن، خطا را گزارش کنرایگان
  9. دو مسیرِ ریلی که یکی از پلی بلند بالا می‌رود و دیگری کوتاه‌تر شروع می‌شود ولی تندتر اوج می‌گیردفصل ۰۹ — الگوریتمِ بدتری که در اندازهٔ واقعیِ تو برنده استرایگان
  10. چهار جعبهٔ دربستهٔ هم‌شکل روی میزِ آزمایش، که فقط از راهِ ترازو و کرنومتر می‌شود درباره‌شان حرف زدفصل ۱۰ — پروژه: مرتبهٔ یک کدِ ناشناس را اعلام کنرایگان
۲آرایه، `list`، `stack`، `queue`: هزینهٔ هر عملیاتترم ۲ · ۹ فصلترم ۲ بنیاد — آرایه و list: سینی‌ای که درجِ ابتدا همهٔ خانه‌ها را جابه‌جا می‌کند، و سینی‌ای که از دو سر باز است
  1. برشی از یک ردیفِ طولانی خانه‌های هم‌اندازه که همه در یک نوار پیوسته کنارِ هم چیده شده‌اندفصل ۰۱ — آرایه: چرا رفتن به خانهٔ هزارم گران‌تر از خانهٔ دوم نیسترایگان
  2. کشویی با یک ردیف خانهٔ هم‌اندازه که نیمی پر است و نیمی از پیش ساخته و خالی ماندهفصل ۰۲ — `list` پایتون یک آرایهٔ پویاست
  3. سه میزِ کار با پهنای فزاینده، که بارِ میزِ میانی یکجا به میزِ پهن‌تر منتقل می‌شودفصل ۰۳ — هزینهٔ `amortised`: عملی که گاهی گران است و همیشه ارزان
  4. قفسه‌ای پر که با گذاشتنِ یک چیز در ابتدایش، تک‌تکِ اجزایش یک خانه جابه‌جا می‌شوندفصل ۰۴ — `list.insert(0, x)` یک تله است
  5. چرخ‌دنده‌ای پنهان که برای هر دندانهٔ دستهٔ بیرونی یک دورِ کامل می‌زندفصل ۰۵ — `O(n²)`ی که در یک حلقهٔ بی‌گناه پنهان است
  6. زنجیری از مهره‌های پراکنده روی میز در برابرِ یک ریلِ فشردهٔ پیوستهفصل ۰۶ — پیوند به‌جای پیوستگی: `linked list`
  7. دیسپنسرِ فنری که فقط بشقابِ رویی را می‌دهد، کنارِ ریلی که بشقابِ اولی رافصل ۰۷ — `stack` و `queue`: دو انضباط روی یک داده
  8. سه ظرفِ هم‌طول با ساختِ متفاوت، کنارِ سه ابزارِ اندازه‌گیریفصل ۰۸ — کدام ظرفِ ترتیبی، برای کدام الگوی دسترسی
  9. نوارِ بلندِ کاغذی که از دو ماشینِ متفاوت رد می‌شود و دو خروجیِ یکسان می‌دهدفصل ۰۹ — پروژه: یک سیاههٔ بزرگ، دو بار
۳`hash`: چرا جست‌وجو می‌تواند هزینهٔ ثابت داشته باشدترم ۳ · ۷ فصلترم ۳ بنیاد — hash: سرسره‌ای که اشیا را به خانه‌های یکسان می‌فرستد و یک خانه که زنجیرهٔ بلندی از آن آویزان است
  1. کشویی از پرونده‌های ردیف‌شده که برای پیدا کردنِ یک برگه باید از اولین برگه تا آخری یکی‌یکی بالا زده شودفصل ۰۱ — پرسشِ «هست یا نه؟» چقدر خرج داردرایگان
  2. دستگاهی که برگه‌های متفاوت را از یک قیف می‌گیرد و هرکدام را به یکی از خانه‌های شماره‌دار می‌اندازدفصل ۰۲ — `hash`: از کلید تا شمارهٔ خانه
  3. قفسه‌ای از خانه‌های شماره‌دار که از هر خانه یک زنجیرِ کوتاه از برگه‌ها آویزان استفصل ۰۳ — `hash table` را خودت بساز
  4. دو ترازوی کنارِ هم که یکی وزن را روی کفه‌ها پخش کرده و دیگری همه‌اش را روی یک کفه ریختهفصل ۰۴ — بدترین حالت، حالتِ متوسط، و حالتی که واقعاً داری
  5. دو میزِ اطلاعات کنارِ هم، یکی با صفی طولانی و دیگری با تابلوی شماره‌دار و بدون صففصل ۰۵ — `set` و `dict` در عمل
  6. کلیدی که بعد از ساخته شدنِ قفل، دندانه‌هایش تغییر کرده و دیگر در همان قفل نمی‌چرخدفصل ۰۶ — چه چیزی می‌تواند کلید باشد — و چرا
  7. دو دسته سندِ یکسان که یکی برگ‌به‌برگ با همه مقایسه می‌شود و دیگری با یک مهرِ کوتاه دسته‌بندی می‌شودفصل ۰۷ — پروژه: تکراری‌ها در یک پیکرهٔ بزرگ
۴`recursion`، مرتب‌سازی، جست‌وجوترم ۴ · ۹ فصلترم ۴ بنیاد — بازگشت، مرتب‌سازی و جست‌وجو: جعبه‌های تودرتو، ادغامِ دو ردیفِ مرتب، و نشانگری بر وسطِ ردیفِ حاصل
  1. جعبه‌های تودرتو که هرکدام نسخهٔ کوچک‌ترِ خودش را در بر دارد و درونی‌ترینشان توپر استفصل ۰۱ — `recursion`: تابعی که خودش را صدا می‌زندرایگان
  2. درختی که هر شاخه‌اش به دو شاخه تقسیم می‌شود و برگ‌های یکسانِ بسیاری داردفصل ۰۲ — هزینهٔ `recursion`: درختِ فراخوانی و کاری که دوباره انجام می‌شود
  3. دو دستِ مرتب‌کنندهٔ کارت که یکی کوچک‌ترین کارت را بیرون می‌کشد و دیگری کارتِ بعدی را در جای درستش می‌نشاندفصل ۰۳ — دو مرتب‌سازیِ `O(n²)` که باید یک بار با دست انجامشان بدهی
  4. درختی که یک دستهٔ کارت را دو به دو می‌شکند و در راهِ برگشت، هر دو دستهٔ مرتب را به هم می‌بافدفصل ۰۴ — تقسیم و حل: `merge sort`
  5. میله‌ای که یک دستهٔ کارت را حولِ یک کارتِ نشانه‌گذاری‌شده به دو گروهِ کوچک‌تر و بزرگ‌تر می‌راندفصل ۰۵ — `quicksort` و انتخابِ `pivot`
  6. ترازویی که در هر توزین یک دستهٔ ممکن را نصف می‌کند، کنارِ قفسه‌ای از خانه‌های شماره‌دارفصل ۰۶ — چرا هیچ مرتب‌سازیِ مقایسه‌ای بهتر از `n log n` نیست — و کِی این حرف باطل است
  7. خط‌کشی که در هر گام نیمی از بازه را کنار می‌گذارد و دو گیرهٔ متحرک داردفصل ۰۷ — `binary search`، و مرزهایی که همه غلط می‌نویسند
  8. دستگاهی که یک نوارِ درهم را مرتب می‌کند و بخش‌های از قبل مرتبِ نوار را دست‌نخورده رد می‌کندفصل ۰۸ — `sorted` واقعی: `key`، پایداری، و چرا از هر چیزی که بنویسی سریع‌تر است
  9. سه میزِ جست‌وجو کنارِ هم: یکی قفسهٔ بی‌ترتیب، یکی قفسهٔ شماره‌دارِ مرتب، یکی جعبهٔ کلیدفصل ۰۹ — پروژه: از جست‌وجوی خطی تا ساختارِ درست
۵درخت و گرافترم ۵ · ۸ فصلترم ۵ بنیاد — درخت و گراف: آرایهٔ شاخه‌شاخه با میلهٔ اندازه‌گیریِ ارتفاع، در برابرِ شبکه‌ای از دیسک‌های نخ‌کشی‌شده
  1. درختی با شاخه‌های متوازن در کنارِ زنجیری از همان تعداد گره که فقط رو به پایین رفته استفصل ۰۱ — درخت: وقتی رابطه سلسله‌مراتبی استرایگان
  2. درختی که چهار مسیرِ رنگی متفاوت روی گره‌هایش کشیده شده و هر مسیر ترتیبِ دیگری داردفصل ۰۲ — پیمایشِ درخت، با `recursion` و بدونش
  3. درختی که شاخه‌هایش دو طرف پخش شده در کنارِ درختی که همهٔ گره‌هایش فقط به یک سمت افتاده‌اندفصل ۰۳ — `binary search tree`: `log n`ی که می‌تواند `n` شود
  4. یک ردیف خانهٔ شماره‌دار در کنارِ درختی که هر گره‌اش دقیقاً به یکی از همان خانه‌ها وصل شده استفصل ۰۴ — `heap` و `priority queue`
  5. شبکه‌ای از گره‌ها با یال‌های متقاطع در کنارِ یک جدولِ مربعیِ خانه‌های پر و خالیفصل ۰۵ — گراف: مدلِ رابطه، و دو نمایش
  6. دو موجِ متفاوت که از یک گرهِ واحد در یک شبکه پخش می‌شوند: یکی حلقه‌های هم‌مرکز و دیگری یک رشتهٔ باریکِ عمیقفصل ۰۶ — `BFS` و `DFS`: کدام چه چیزی پیدا می‌کند
  7. شبکه‌ای کوچک که تعدادِ بی‌شماری مسیرِ درهم از میانش رد می‌شود و در لبهٔ تصویر به انبوهی تبدیل شدهفصل ۰۷ — گرافی که منفجر می‌شود
  8. شبکه‌ای با چند گرهِ بسیار پرارتباط که بقیهٔ گره‌ها دورشان حلقه زده‌اندفصل ۰۸ — پروژه: یک شبکهٔ واقعی را پیمایش کن
۶انتخاب کن، و با عدد دفاع کنترم ۶ · ۶ فصلترم ۶ بنیاد — انتخاب کن و دفاع کن: دو سازوکار روی یک میز، ترازویی که به یک طرف چربیده، و برگهٔ گزارشِ خط‌کشی‌شده
  1. برگه‌ای با سه خانهٔ خالی کنارِ دو مسیرِ متفاوت که از همان برگه بیرون می‌آیندفصل ۰۱ — شکلِ مسئله را قبل از انتخابِ ساختار بنویسرایگان
  2. جدولِ شبکه‌ای که چند خانه‌اش با ابزار سنجیده می‌شود و چند خانه‌اش خالی ماندهفصل ۰۲ — جدولِ تصمیم: هزینهٔ هر عملیات در هر ساختار
  3. دو کفهٔ ترازو که یکی ساعت و دیگری انبارِ قفسه‌دار روی آن استفصل ۰۳ — معاملهٔ حافظه و زمان
  4. چراغی که سه کلیدِ توقفِ جداگانه دارد و هر کدام به‌تنهایی خاموشش می‌کندفصل ۰۴ — کِی بس کنی
  5. یک گزارشِ چاپی که کنارش همان آزمایش دوباره برپا شده تا نتیجه‌اش وارسی شودفصل ۰۵ — دفاع از یک انتخاب: گزارشی که دیگری می‌تواند ردش کند
  6. دو ماشینِ پیشنهاددهنده کنارِ هم، یکی با کشوهای از پیش پرشده و یکی با یک ریلِ مرتبفصل ۰۶ — پروژهٔ نهایی: یک مسئلهٔ واقعی، دو ساختار، یک تصمیمِ مستند