مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

این صفحه فقط خواندنی است. شما می‌توانید متن صفحه را مشاهده کنید، اما نمی‌توانید آن را تغییر دهید. اگر فکر می‌کنید که مشکلی رخ داده است، مدیر ویکی را در جریان بگذارید.
====== مسایل نظری ======
اکثر مسایل قبل از اینکه قابل حل با یک یا ترکیبی از چند روش الگوریتمی باشند، نیاز به حل نظری دارند. البته اینکه چه راه‌حل‌هایی را می‌توان برای یک مسأله به کار برد و چه راه‌حل‌هایی را به دلیل زمان زیاد، نقض کردن یکی از شرایط مسأله و ... نمی‌توان به کار برد؛ پس از شناخت مسأله مهم‌ترین قسمت حل است.
===== روش‌های حل مسأله =====
روش‌های زیر می‌توانند در حل قسمت نظری مسأله مفید باشند.
  * پیدا کردن الگوی تکرار شونده. رابطه‌ای که همیشه برقرار است و با کمک آن می‌توان مثلاً حالت‌های مجاز و غیرمجاز مسأله را تشخیص داد.
  * رسم شکل. برای حل مسایل ریاضی معمولاً مفید است اما برای حالت‌های ساده‌ی مسایل دیگر هم می‌تواند به درک مسأله کمک کند.
  * پیدا کردن مسأله‌ی معادل. مثلاً دنباله‌ای که مورد نظر سوال بوده است دنباله‌ی مشهوری مانند فیبوناچی یا اعداد کاتالان است؛ اما در صورت سوال این موضوع گفته نشده است.
  * حل مسایل کمکی که با دانستن آنها مسأله‌ی ما ساده‌تر می‌شود. مثلاً اگر کوتاهترین مسیر بین زوج رأسها را بدانیم، مسأله‌ی دیگری را می‌توانیم حل کنیم.
  * تشخیص وضعیت‌های مسأله و حل مسأله بر اساس آنها.
  * حل مسأله از آخر به اول می‌تواند کمک کند. یعنی فرض کنیم به جواب رسیده‌ایم و با کمک آن مسأله را حل کنیم. مثلاً وضعیت‌های مجاز را شناسایی کنیم و بررسی کنیم که آیا در یکی از این وضعیت‌ها هستیم یا خیر.
  * برهان خلف. با این کار می‌توانیم مطمئن شویم مسأله را درست مدل کرده‌ایم.
  * حالت‌های مرزی و خاص.
  * حل مسأله‌ی کلی‌تر. مثلاً اگر کوتاهترین مسیر بین چندین زوج مبدأ و مقصد خواسته شده است، بهتر است همه‌ی مسیرها را پیدا کنیم.
  * تقارن و زوجیت. مثلاً اگر کوتاهترین مسیرها در یک گراف بدون جهت را حساب کرده‌ایم، ترتیب رأس مبدأ و مقصد مهم نیست. مثالی از زوجیت هم می‌تواند این باشد که دو نفر یکی در میان پفک‌های درون یک بسته را می‌خورند، اگر تعداد اولیه پفک‌ها زوج باشد دو نفر مقدار مساوی پفک می‌خورند، در غیر این صورت نفر اول یک پفک بیشتر می‌خورد.

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

[[http://fa.wikipedia.org/wiki/%D8%B1%D8%A7%D8%A8%D8%B7%D9%87_%D8%A8%D8%A7%D8%B2%DA%AF%D8%B4%D8%AA%DB%8C#.D8.B1.D9.88.D8.B4_.D8.AD.D9.84|حل روابط بازگشتی همگن با ضرایب ثابت]]

برای حل روابط بازگشتی می‌توان از [[الگوریتم:برنامه‌ریزی_پویا|برنامه‌ریزی پویا]] هم استفاده کرد.
===== هندسه =====
فاصله‌ی اقلیدسی: بین دو نقطه‌ی $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]
\]

[[http://fa.wikipedia.org/wiki/%D8%A7%D9%85%DB%8C%D8%AF_%D8%B1%DB%8C%D8%A7%D8%B6%DB%8C|امید ریاضی]]
===== توری =====
یک توری منظم مربعی مانند یک جدول با خانه‌های برابر است. یک توری نامنظم می‌تواند از امتداد دادن اضلاع اشکال درون یک صفحه ساخته شود. ساخت چنین توری می‌تواند به حل مسأله کمک کند و به همراه روش‌های دیگر مانند [[الگوریتم:برنامه‌ریزی_پویا|برنامه‌ریزی پویا]] برای حل مسأله استفاده شود.

[[http://en.wikipedia.org/wiki/Lattice_graph|توری]]
===== توابع صعودی/نزولی و محدب/مقعر =====
اگر مقادیر تابعی همواره در حال افزایش یا ثابت باشند، به آن صعودی می‌گویند و اگر مقادیر تابع همواره در حال کاهش یا ثابت باشند به آن نزولی می‌گویند.

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

ابزار کاربر

ابزار سایت

ابزار صفحه
