اکثر مسایل قبل از اینکه قابل حل با یک یا ترکیبی از چند روش الگوریتمی باشند، نیاز به حل نظری دارند. البته اینکه چه راهحلهایی را میتوان برای یک مسأله به کار برد و چه راهحلهایی را به دلیل زمان زیاد، نقض کردن یکی از شرایط مسأله و … نمیتوان به کار برد؛ پس از شناخت مسأله مهمترین قسمت حل است.
روشهای زیر میتوانند در حل قسمت نظری مسأله مفید باشند.
روشهای حل مسألهی نظری را بر حسب مبحث آنها مرور میکنیم.
به دنبالهای که جملات بعدی آن بر حسب جملات قبلی محاسبه شوند، رابطهی بازگشتی میگویند. مثلاً فاکتوریل و فیبوناچی هر دو رابطهی بازگشتی دارند، اما فقط برای فیبوناچی میتوان رابطهی مستقیم به دست آورد.
حل روابط بازگشتی همگن با ضرایب ثابت
برای حل روابط بازگشتی میتوان از برنامهریزی پویا هم استفاده کرد.
فاصلهی اقلیدسی: بین دو نقطهی $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} \]