مبانی کامپیوتر و الگوریتم؛ از حل مسئله تا پروژهٔ عملی

چاپ پاسخ درستِ مثال کتاب فقط موفقیت همان اجرا را نشان می‌دهد. برای دفاع از راه‌حل باید مسئله، ورودی مجاز، دلیل رسیدن به پاسخ و هزینهٔ رشد داده را توضیح دهیم. آزمون، استدلال درستی و اندازه‌گیری هرکدام سؤال متفاوتی را پاسخ می‌دهند؛ گزارش قابل اعتماد، محدودیت این شواهد را نیز روشن می‌کند.

پیش‌شرط و پس‌شرط را پیش از آزمون بنویسید

پیش‌شرط توصیف دادهٔ قابل قبول است؛ مثلاً فهرست فشرده‌ای از عددهای متناهی. پس‌شرط می‌گوید خروجی چه رابطه‌ای با ورودی دارد؛ کمینه باید عضو فهرست باشد و از هیچ عضو دیگری بزرگ‌تر نباشد. برای فهرست خالی، خروجی null را قرارداد می‌کنیم تا نبود داده با کمینهٔ واقعیِ صفر اشتباه نشود. اگر ورودی متن باشد، تبدیل آن به عدد وظیفهٔ همین تابع نیست. این مرزبندی اجازه می‌دهد شکست ورودی را از شکست خود الگوریتم جدا تشخیص دهیم.

درستی کامل، دو بخش دارد: اگر محاسبه تمام شد، پاسخ باید قرارداد را برآورده کند؛ افزون بر آن، برای هر ورودی مجاز باید پایان یابد. برای حلقهٔ اندیسی، معمولاً نزدیک‌شدن اندیس به طول ثابت فهرست، دلیل خاتمه است. اگر داخل حلقه طول فهرست را بی‌قاعده زیاد کنیم، این دلیل دیگر خودکار معتبر نیست. بنابراین «در همهٔ مثال‌ها متوقف شد» به‌تنهایی جای دلیل خاتمه برای خانوادهٔ ورودی‌ها را نمی‌گیرد. در پروژهٔ آخر، فهرست ورودی را تغییر نمی‌دهیم تا این تعهد هم روشن‌تر بماند.

مثال اول؛ ناوردای حلقه برای کمینه

ناوردا گزاره‌ای است که در نقطهٔ مشخصی از تکرار درست می‌ماند. در الگوریتم کمینه، درست پیش از بررسی خانهٔ i، متغیر best کمینهٔ خانه‌های دیده‌شده از صفر تا i−1 است. ابتدا i برابر یک است و best از خانهٔ صفر می‌آید؛ پس گزاره برقرار است. پس از مقایسه با عضو تازه، best کمینهٔ همان پیشوندِ یک‌خانه بزرگ‌تر می‌شود. هنگام خروج، i به طول رسیده و دیگر عضو بررسی‌نشده‌ای نداریم. این سه مرحله را آغاز، حفظ و نتیجهٔ پایان می‌نامیم.

Input: [5, 2, 7]
Before i=1: inspected [5],       best=5
Before i=2: inspected [5, 2],    best=2
At exit:    inspected [5, 2, 7], best=2
Invariant: best = minimum of inspected prefix

کد زیر را در 11-minimum-proof.mjs اجرا کنید. نگهبان ورودی با پیمایش for...of عدد نامتناهی، NaN و خانهٔ خالی را رد می‌کند. سپس هستهٔ کمینه دادهٔ معتبر را بررسی می‌کند. آزمون سه حلقهٔ تو در تو، همهٔ ۲۷ فهرستِ سه‌عضوی ساخته‌شده از مجموعهٔ کوچکِ منفی دو، صفر و سه را می‌سازد؛ تصادفی نیست و هر بار همان موارد را بررسی می‌کند. مرجعِ این آزمایش Math.min برای سه عدد محدود است، نه تابعی که قرار است با spread فهرست عظیم را بپذیرد.

import assert from 'node:assert/strict';

function minimum(values) {
  if (!Array.isArray(values)) throw new TypeError('Expected an array');
  for (const value of values) {
    if (!Number.isFinite(value)) throw new TypeError('Expected finite numeric values');
  }
  if (values.length === 0) return null;
  let best = values[0];
  for (let i = 1; i < values.length; i += 1) {
    if (values[i] < best) best = values[i];
  }
  return best;
}
assert.equal(minimum([]), null);
assert.equal(minimum([5]), 5);
assert.equal(minimum([5, 2, 7]), 2);
assert.equal(minimum([-5, -2, -7]), -7);
assert.equal(minimum([0, 0]), 0);
assert.throws(() => minimum([2, NaN]), TypeError);
assert.throws(() => minimum(new Array(1)), TypeError);
for (const a of [-2, 0, 3]) {
  for (const b of [-2, 0, 3]) {
    for (const c of [-2, 0, 3]) {
      assert.equal(minimum([a, b, c]), Math.min(a, b, c));
    }
  }
}
console.log('Minimum: boundary cases and 27 generated cases passed');

خروجی موفق پیام مشخصِ گذر آزمون‌های مرزی و ۲۷ حالت تولیدشده است. assert خطای اختلاف را به شکست اجرا تبدیل می‌کند؛ صرفاً چاپ‌کردن دو مقدار کنار هم، کنترل خودکار نمی‌سازد. ورودی‌های خالی، تک‌عضوی، همه‌منفی و تکراری هرکدام فرض متفاوتی را می‌سنجند. آزمون ورودی نامعتبر هم بررسی می‌کند که خطا به‌جای تولید خروجی ظاهراً معتبر آشکار شود. برای تمرین، مقدار آغاز best را موقتاً صفر بگذارید و ببینید کدام نمونهٔ مثبت، خطای شما را پیدا می‌کند.

مثال نقض، پوشش مرزی و آزمون ویژگی

مثال نقض ورودی مجازی است که ادعا را رد می‌کند؛ پاسخ غلط روی [۵،۲،۷] برای رد درستی عمومیِ کمینه کافی است، ولی هزار پاسخ درست اثبات عمومی نیست. نمونه‌ها را هدفمند انتخاب کنید: طول صفر و یک، پاسخ در ابتدا و انتها، تکرار، مرز و ورودی نامجاز. با تغییر قرارداد، انتظار آزمون را هم بازبینی کنید.

آزمون ویژگی رابطه‌ای عمومی را روی چند داده می‌سنجد؛ نتیجهٔ مرتب‌سازی باید هم صعودی باشد و هم شمار مقدارها را حفظ کند. آرایهٔ خالی همیشه صعودی است، پس ویژگی اول کافی نیست. دامنه و تعداد دادهٔ تولیدشده را روشن نگه دارید تا شکست بازتولید شود؛ مولد آزمون نیز می‌تواند بعضی حالت‌ها را هرگز نسازد.

مثال دوم؛ شمارش بازدید، نه ادعای سرعت عمومی

در کد بعد، واحد هزینه «دیدن یک خانهٔ آرایه در هستهٔ جست‌وجو» است. دادهٔ نمونه از قبل مرتب، فشرده و عددی است؛ دو تابع داخلی نگهبان عمومی ندارند و نباید مستقیم به ورودی بیرونی وصل شوند. برای هدف ۳۱ در فهرست عددهای زوج صفر تا سی، خطی شانزده خانه و دودویی پنج خانه می‌بیند. این آزمایش زمان‌سنجی نیست، پس وابسته به شلوغی رایانه عدد میلی‌ثانیه نمی‌سازد. از آن برای بررسی روند کاهش بازه استفاده می‌کنیم.

import assert from 'node:assert/strict';

// Both cores assume a dense, ascending array of finite numbers.
function linearCore(values, target) {
  let visits = 0;
  for (let i = 0; i < values.length; i += 1) {
    visits += 1;
    if (values[i] === target) return { found: true, visits };
  }
  return { found: false, visits };
}
function binaryCore(values, target) {
  let lo = 0;
  let hi = values.length - 1;
  let visits = 0;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    visits += 1;
    if (values[mid] === target) return { found: true, visits };
    if (values[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return { found: false, visits };
}
const values = Array.from({ length: 16 }, (_, index) => index * 2);
assert.deepEqual(linearCore(values, 31), { found: false, visits: 16 });
assert.deepEqual(binaryCore(values, 31), { found: false, visits: 5 });
assert.deepEqual(linearCore(values, 0), { found: true, visits: 1 });
assert.deepEqual(binaryCore([], 0), { found: false, visits: 0 });
for (let target = -1; target <= 32; target += 1) {
  assert.equal(linearCore(values, target).found, binaryCore(values, target).found);
}
console.log(JSON.stringify(linearCore(values, 31)));
console.log(JSON.stringify(binaryCore(values, 31)));

دو خط خروجی به‌ترتیب {"found":false,"visits":16} و {"found":false,"visits":5} هستند. برای هدف صفر، خطی فقط یک بازدید دارد؛ پس گزارهٔ «دودویی در همهٔ اجراها کمتر کار می‌کند» از همین نمونه هم درنمی‌آید. انتخاب روش به تعداد درخواست‌ها و هزینهٔ آماده‌سازی نیز وابسته است. اگر داده فقط یک بار و بی‌ترتیب دریافت شده، مرتب‌سازی برای یک جست‌وجوی منفرد ممکن است مناسب نباشد. در درخواست‌های پرتعداد روی مجموعهٔ ثابت، هزینهٔ آماده‌سازی می‌تواند میان درخواست‌ها تقسیم شود.

O و Θ را از بهترین و بدترین حالت جدا کنید

ابتدا تابع هزینه را مشخص کنید؛ مثلاً بیشترین بازدید برای ورودی‌های طول n. سپس O یک کران بالای رشد را با نادیده‌گرفتن ضریب ثابت و ورودی‌های کوچک بیان می‌کند. Θ کران دوطرفهٔ همان تابع هزینه را می‌گوید. بنابراین O نام دیگر «بدترین حالت» نیست؛ می‌توان تابعِ بهترین حالت را هم با نماد کران توصیف کرد. جست‌وجوی خطی روی ورودی غیرخالی، در بهترین حالت یک خانه می‌بیند و در بدترین حالت n خانه؛ باید بگوییم کدام تابع را توصیف می‌کنیم.

برای جست‌وجوی دودویی، تعداد بازدیدِ بدترین حالت در مدل دسترسی مستقیم به آرایه، لگاریتمی است. اگر در هر فراخوانی، مرتب‌بودن همهٔ داده را با پیمایش بررسی کنید، تابع عمومیِ شامل اعتبارسنجی دیگر فقط هزینهٔ هسته را ندارد. همچنین طول رشتهٔ کلید یا هزینهٔ مقایسهٔ رکورد بزرگ را نباید همیشه ثابت فرض کرد. مدل سادهٔ این دوره برای فهم انتخاب روش است؛ برای نتیجهٔ اجرایی، مدل و محدودهٔ داده را کنار ادعای هزینه بنویسید.

فضای کمکی، خروجی و زمان واقعی

فضای کمکی به حافظهٔ موقت افزوده بر ورودی و خروجی گفته می‌شود، البته باید قرارداد گزارش را روشن کنید. تابعی که نسخهٔ مرتب‌شدهٔ تازه می‌سازد، برای خروجی هم فضای متناسب با n لازم دارد؛ ثابت‌بودن چند شمارنده این هزینه را حذف نمی‌کند. بازگشت هم قاب‌های فعال دارد. از سوی دیگر، تعداد خانه‌های منطقی دقیقاً مقدار بایت یا اوج مصرف حافظهٔ موتور نیست. در JavaScript، تخصیص، جمع‌آوری حافظه و نمایش داخلی داده می‌توانند بر اندازهٔ واقعی اثر بگذارند.

زمان واقعی را با نسخهٔ Node.js، سخت‌افزار، شکل داده، چند تکرار و تعیین هزینهٔ آماده‌سازی گزارش کنید. شمار بازدید به‌تنهایی بنچمارک نیست و نتیجهٔ هسته به کل برنامه تعمیم ندارد. مطالعهٔ تکمیلیِ مدل هزینه: https://www.darsavand.com/resources/javascript-runtime-cost-complexity و آزمایش آرایه‌ها: https://www.darsavand.com/resources/javascript-nodejs-arrays-performance

سه نمونه‌سؤال با پاسخ تشریحی

سؤال 1: الگوریتم کمینه با best=0 روی فهرست [۵،۲،۷] چرا غلط است، حتی اگر روی ورودی‌های منفی درست به نظر برسد؟

پاسخ: صفر جزو داده نیست، ولی از همهٔ این مقدارها کوچک‌تر است و هیچ مقایسه‌ای best را تغییر نمی‌دهد؛ خروجی صفر قرارداد کمینهٔ اعضا را نقض می‌کند. یک مثال نقض برای رد ادعای عمومی کافی است. مقدار آغاز باید از عضو واقعی، مانند خانهٔ اول، گرفته شود و فهرست خالی سیاست جدا داشته باشد. موفقیت روی دادهٔ منفی، ایراد مقداردهی اولیه را پنهان می‌کند و نمی‌تواند جای استدلال مقدار آغاز را بگیرد.

سؤال 2: در شمارندهٔ بازدید، جست‌وجوی دودویی برای فهرست ۱۶عضوی و هدف ۳۱ پنج خانه می‌بیند. آیا می‌توان گفت برنامهٔ کامل فقط پنج عملیات دارد؟

پاسخ: خیر؛ شمارنده فقط بازدید خانهٔ میانی در هسته را مدل کرده است. مقایسه، محاسبهٔ میانه، شرط حلقه و تغییر مرز نیز اجرا می‌شوند؛ ساخت داده و بررسی مرتب‌بودن اصلاً در شمارنده نیستند. پنج، عدد دقیق همین معیار و همین ورودی است. برای برنامهٔ عمومی باید هزینهٔ دریافت، اعتبارسنجی و آماده‌سازی را نیز حساب کرد. به همین دلیل، اجرای بررسی مرتب‌بودن خطی در هر جست‌وجو می‌تواند هزینهٔ کل هر درخواست را خطی کند.

سؤال 3: آیا گذراندن ۲۷ ترکیب سه‌عضویِ آزمون کمینه اثبات می‌کند تابع برای همهٔ ورودی‌های مجاز درست است؟ چه استدلالی کم است؟

پاسخ: این آزمون تنها همان مجموعهٔ محدود را پوشش می‌دهد. برای ادعای عمومی، ناوردای حلقه را بیان می‌کنیم: پیش از دور i، best کمینهٔ اعضای اندیس صفر تا i−1 است. مقداردهی از خانهٔ اول این گزاره را آغاز می‌کند، مقایسهٔ عضو تازه آن را حفظ می‌کند و پایان حلقه یعنی همهٔ اعضا دیده شده‌اند. این استدلال همراه با خاتمه و قرارداد ورودی، درستی الگوریتم را توضیح می‌دهد؛ آزمون‌ها برای یافتن خطای پیاده‌سازی و کنترل موارد مرزی همچنان ارزش دارند.

معیار تحویل: پیش‌شرط، پس‌شرط، دلیل خاتمه، سه آزمون مرزی و شمارندهٔ عملیاتِ یکی از الگوریتم‌ها را بنویسید. یک تغییر غلط و مثال نقضش را پیدا کنید. هزینه‌های شمرده‌شده و حذف‌شده را مشخص کنید. کمک‌مرجع: #validation-contracts و #array .

منابع بررسی و مطالعهٔ بیشتر

Princeton — Analysis of Algorithms: https://algs4.cs.princeton.edu/14analysis/
MIT 6.0001 — جلسات Testing/Debugging و Efficiency: https://ocw.mit.edu/courses/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/pages/lecture-slides-code/
Node.js 24 — Test runner: https://nodejs.org/docs/latest-v24.x/api/test.html
تألیف مستقل، نمونه‌ها و پاسخ‌ها: تحریریه درس‌آوند. هیچ زمان‌سنجی عمومی یا ادعای برتری همیشگی از این مثال‌ها نتیجه نشده است.

فایل مثال‌ها، راهنمای فارسی اجرا و عیب‌یابی، پروژهٔ گزارش نمره‌ها و آزمون جمع‌بندی تألیفی با پاسخ تشریحی، رایگان در صفحهٔ بستهٔ تمرین همین دوره ارائه می‌شود:
https://www.darsavand.com/resources/computer-algorithms-practice-kit
تألیف و مثال‌های اختصاصی: تحریریه درس‌آوند.