الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
نوشته‌ها با برچسب محاسبات ریاضی نوشته‌ها با برچسب محاسبات ریاضی - الگوریتمستان الگوریتمستان الگوریتمستان
نوشته‌ها با برچسب «

محاسبات ریاضی

»

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

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

محاسبه‌ی سینوس و کسینوس زاویه‌های مشهور به روش ساده

ادامه ...

بسیاری از فرآیندهای طبیعی از جمله ترکیب ساختار بدن موجودات زنده نظم مشخصی دارند و از دنباله‌ی اعدادی تبعیت می‌کنند که امروزه با نام دنباله‌ی اعداد فیبوناچی (فیبوناتچی - Fibonacci) شناخته می‌شود. مشهورترین خاصیت این اعداد نسبت دو جمله‌ی متوالی آنها به ازای جملات بزرگ دنباله است که به عدد طلایی مشهور است.

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

تعریف: دنباله‌ی اعداد فیبوناچی روی اعداد حسابی به صورت زیر تعریف می‌شود:

ادامه ...

ما معمولا برای توضیح رشد با سرعت زیاد از عبارت «رشد نمایی» استفاده می‌کنیم. رشد نمایی یعنی هر گام که پیش می‌رویم، از گام $n$ به گام $n + 1$، اندازه دو یا هر چند برابری می‌شود که به آن پایه یا مبنای رشد گفته می‌شود. این پایه همیشه ثابت است؛ یعنی چه مرحله‌ی اول باشیم و چه مرحله‌ی هزارم، همیشه مرحله‌ی بعدی ضرب در عدد ثابتی می‌شود. در حالت کلی می‌توان نوشت:

\[ f(n ) = b \times f(n - 1 ),\; f(0) = c \]

که منظور از b همان پایه‌ی رشد است. مثلا اگر $b = 2$ باشد و $f(0 ) = 1$، به تابع $f(n) = 2^n$ می‌رسیم. این تعریف را با تعریف فاکتوریل مقایسه کنید:

ادامه ...

دنباله‌ی اعداد کاتالان (Catalan Numbers) یکی از دنباله‌های عددی مشهور ریاضیات است که برای عدد نامنفی n به صورت $C_n$ نمایش داده می‌شود.

  

$C_n:\qquad 1,\;1,\;2,\;5,\;14,\;42,\;132,\;429,\;1430,\;4862,\;16796,\;\cdots$

  

این دنباله کاربردهای بسیاری در مسائل شمارشی دارد. از جمله:

1- تعداد درخت‌های دودویی با n رأس داخلی برابر $C_n$ است:

ادامه ...

تعریف ترکیب (Combination)

تعداد حالت‌های انتخاب r (عدد صحیح و نامنفی) شیء از n (عدد صحیح و بزرگتر یا مساوی r) شیء را که ترتیب انتخاب اهمیت نداشته باشد، انتخاب r از n یا ترکیب r روی n گویند و به یکی از صورت‌های زیر نمایش می‌دهند:

  

\[C(n,r) = C_r^n= \begin{pmatrix} n \\ r \end{pmatrix} \]

این عدد به ضریب دوجمله‌ای نیز مشهور است که یکی از محل‌های استفاده‌ی آن است.

ادامه ...

دترمینان ماتریس مربعی - که به صورت $ \vert A \vert $ یا $ det( A ) $ نمایش داده می‌شود - یکی از مفاهیم مشهور جبر خطی است که کاربردهای بسیاری در علوم مختلف دارد. امکان محاسبه‌ی سریع دترمینان یک ماتریس با ابعاد بزرگ بحث مهمی است که در ادامه سه روش محاسباتی رایج و پيچيدگي زمانی آنها مرور خواهند شد.

طبق تعریف دترمینان اگر اندازه‌ی ابعاد ماتریس مربعی یک باشد ($n = 1$)، دترمینان همان مقدار تک‌عضو آن است. یعنی:

  

ادامه ...

همه‌ی ما با تعریف ضرب ماتریس‌های مربعی آشنایی داریم. حاصلضرب ماتریس‌های مربعی A و B به صورت زیر تعریف می‌شود:

  

\[ A=(a_{ij})_{n \times n} = \qquad , \qquad B=(b_{ij})_{n \times n} \] \[ C = A \times B = (c_{ij})_{n \times n} \qquad ; \qquad c_{ij}= \sum_{k=1}^{n} a_{ik} \; b{kj} \]

  

به عنوان مثال در حالت $n = 2$ داریم:

  

\[ \begin{pmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{pmatrix} \times \begin{pmatrix} b_{11} & b_{12}\\ b_{21} & b_{22} \end{pmatrix} = \begin{pmatrix} a_{11}b_{11}+a_{12}b_{21} & a_{11}b_{12}+a_{12}b_{22}\\ a_{21}b_{11}+a_{22}b_{21} & a_{21}b_{12}+a_{22}b_{22} \end{pmatrix} \]

ادامه ...

مسئله‌ی ضرب زنجیره‌ای ماتریس‌ها و پرانتزبندی بهینه‌ی آن یکی از مثال‌های مشهور کاربرد برنامه‌نویسی پویا در حل مسائل بهینه‌سازی است.

فرض کنید قصد داریم حاصلضرب عبارت ماتریسی $ A_{3 \times 7} \times B_{7 \times 8 } \times C_{8 \times 4} $ را محاسبه کنیم. می‌دانیم که ضرب ماتریس‌ها خاصیت شرکت‌پذیری داشته، اما خاصیت جابجایی ندارد. بنابراین رعایت ترتیب ضرب آنها مهم است. پرانتزبندی‌های مختلف ضرب ماتریس‌ها حالت‌های مختلف محاسبه آن را به ما می‌دهند:

  

\[1: A \times (B \times C) \]

ادامه ...

الگوریتمستان در تلگرام

   

 

پیوند کوتاه:
»  کتاب Concrete Mathematics
معرفی کتاب Concrete Mathematics برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود
برچسب‌ها
#الگوریتم‌های عقبگرد #نمونه سوال فارسی مسابقات ACM #صف #مسئله‌های الگوریتمی #حل سوالات Timus Online Judge #منبع آموزشی #گراف #آمادگی مسابقه برنامه‌نویسی #معرفی وب‌سایت #درخت پوشا #سوالات برنامه‌نویسی #کتاب مسابقات برنامه‌نویسی #برنامه‌نویسی #حل مسئله‌‌ی الگوریتمی #جستجوی اول عمق #الگوریتم‌های مسیریابی #آموزش برنامه‌نویسی ++C #آموزش طراحی الگوریتم #الگوریتم #الگوریتم‌های کوتاهترین مسیر #مسئله‌های برنامه‌نویسی #الگوریتم‌های حریصانه #نمونه سوال فارسی مسابقه‌ی ACM #درخت‌ها #برنامه‌نویسی ++C #نمونه سوالات مسابقه برنامه‌نویسی #حل سوالات UVa Online Judge #کتاب الگوریتم #حل سوالات ACM-ICPC #ترجمه‌ی فارسی سوالات UVa Online Judge #آموزش ساختمان داده‌ها #الگوریتم‌های تقسیم و غلبه #الگوریتم‌های مرتب‌سازی #الگوریتم دایکسترا #نکات برنامه‌نویسی #دانلود کتاب #محاسبات ریاضی #تمرین المپیاد کامپیوتر #وبلاگ #کتابخانه قالب استاندارد ++C #ترجمه‌ی فارسی سوالات برنامه‌نویسی #نمونه سوال فارسی مسابقات برنامه‌نویسی #تمرین طراحی الگوریتم #الگوریتم‌های بازگشتی #سوالات چالشی برنامه‌نویسی #آموزش الگوریتم #مسابقات برنامه‌نویسی #مسئله‌ی کوله‌پشتی #مسأله‌های برنامه‌نویسی #مسابقات برنامه‌نویسی ACM #مسأله‌های الگوریتمی #سوالات مسابقات ACM-ICPC #سوالات مسابقات برنامه‌نویسی بیان #ترجمه‌ی فارسی سوالات ACM #آمادگی المپیاد کامپیوتر #پیمایش گراف #ماتریس #نمونه سوال مسابقه ACM #تکنیک‌های طراحی الگوریتم #آمادگی مسابقه ACM #تمرین مسابقه برنامه‌نویسی #الگوریتم فلوید-وارشال #ساختمان داده #ترجمه فارسی سوالات کتاب Programming Challenges #حل سوالات مسابقات برنامه‌نویسی #سوالات UVa Online Judge #مسابقه برنامه‌نویسی #الگوریتم‌های برنامه‌نویسی پویا #کتاب الکترونیکی #مسابقه برنامه نویسی #جستجوی اول سطح #Python #الگوریتم‌های گراف #ویدئوی آموزشی #تمرین مسابقه‌ی برنامه‌نویسی ای‌سی‌ام