فهرست مندرجات

مسایل نظری

اکثر مسایل قبل از اینکه قابل حل با یک یا ترکیبی از چند روش الگوریتمی باشند، نیاز به حل نظری دارند. البته اینکه چه راه‌حل‌هایی را می‌توان برای یک مسأله به کار برد و چه راه‌حل‌هایی را به دلیل زمان زیاد، نقض کردن یکی از شرایط مسأله و … نمی‌توان به کار برد؛ پس از شناخت مسأله مهم‌ترین قسمت حل است.

روش‌های حل مسأله

روش‌های زیر می‌توانند در حل قسمت نظری مسأله مفید باشند.

روش‌های حل مسأله‌ی نظری را بر حسب مبحث آنها مرور می‌کنیم.

روابط بازگشتی

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

حل روابط بازگشتی همگن با ضرایب ثابت

برای حل روابط بازگشتی می‌توان از برنامه‌ریزی پویا هم استفاده کرد.

هندسه

فاصله‌ی اقلیدسی: بین دو نقطه‌ی $p=(x_1,y_1)$ و $q=(x_2,y_2)$ فاصله‌ی اقلیدسی به صورت $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ تعریف می‌شود. طول هر مسیر دیگری بین دو نقطه از فاصله‌ی اقلیدسی آنها بیشتر است.

امید ریاضی

امیدریاضی مقداری است که با توجه به احتمال رخ دادن هر مقدار، برای یک متغیر تصادفی محاسبه می‌شود. در حالتی که احتمالها برابر باشند، امید ریاضی تبدیل به میانگین خواهد شد. \[ E[X] = \sum_{i=1}^{n} v_i\times p_i \] اعداد ثابت از امید ریاضی خارج می‌شوند: \[ E[a.X+b] = a.E[X]+b \] امید ریاضی خاصیت خطی دارد: \[ E[X+Y] = E[X]+E[Y] \]

امید ریاضی

توری

یک توری منظم مربعی مانند یک جدول با خانه‌های برابر است. یک توری نامنظم می‌تواند از امتداد دادن اضلاع اشکال درون یک صفحه ساخته شود. ساخت چنین توری می‌تواند به حل مسأله کمک کند و به همراه روش‌های دیگر مانند برنامه‌ریزی پویا برای حل مسأله استفاده شود.

توری

توابع صعودی/نزولی و محدب/مقعر

اگر مقادیر تابعی همواره در حال افزایش یا ثابت باشند، به آن صعودی می‌گویند و اگر مقادیر تابع همواره در حال کاهش یا ثابت باشند به آن نزولی می‌گویند.

توابع محدب توابعی هستند که به ازای هر دو نقطه، میانگین مقدار تابع در آن دو نقطه بیشتر از مقدار میانگین آن نقاط است. \[ f(\frac{x+y}{2}) \leq \frac{f(x)+f(y)}{2} \] برعکس آن را تابع مقعر می‌نامیم: \[ f(\frac{x+y}{2}) \geq \frac{f(x)+f(y)}{2} \]