بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus

کتاب طراحی الگوریتم با رویکردی خلاقانه

[برو به فهرست نوشته‌ها]
        معرفی کتاب Introduction to Algorithms: A Creative Approach

کتاب Introduction to Algorithms: A Creative Approach را می‌توان مکملی بر استفاده از کتاب Introduction to Algorithms (مشهور به کتاب CLRS) دانست. در این کتاب علاوه بر معرفی تکنیک‌های مختلف طراحی الگوریتم‌ها و روش‌های حل برخی مسائل الگوریتمی، روش‌های تحلیل و حل آنها با جزئیات بیشتر و به صورت گام به گام بررسی شده است. به همین دلیل نیز از جمله منابع اصلی پیشنهادی به متقاضیان شرکت در المپیادهای کامپیوتر و مسابقات برنامه‌نویسی برای یادگیری طراحی و تحلیل الگوریتم‌ها است.

ادامه ...

کتاب مقدمه‌ای بر الگوریتم‌ها

[برو به فهرست نوشته‌ها]
        معرفی کتاب Introduction to Algorithms (ویراست سوم) به عنوان مرجع مباحث طراحی الگوریتم‌ها و ساختمان داده‌ها

کتاب Introduction to Algorithms (مشهور به کتاب CLRS) از انتشارات MIT اثر Thomas H. Cormen، Charles E. Leiserson، Ronald L. Rivest و Clifford Stein کتاب جامع مباحث الگوریتم‌ها و ساختمان داده‌ها است که منبع درسی بسیاری از دانشگاه‌های معتبر بوده و تا کنون بیش از سی هزار مقاله و کتاب با ارجاع به آن نگارش یافته است. مطالب این کتاب از مباحث اولیه مانند مفهوم تحلیل و طراحی الگوریتم آغاز شده و مباحث پیشرفته‌ی طراحی الگوریتم‌ها و ساختمان داده‌ها را نیز پوشش می‌دهد. به همین دلیل مطالعه و استفاده از آن به عنوان مرجع برای کلیه‌ی علاقمندان مباحث طراحی الگوریتم‌ها، ساختمان داده‌ها و همینطور شرکت‌کنندگان المپیادهای کامپیوتری و مسابقات برنامه‌نویسی توصیه می‌شود.

ادامه ...

کتاب چالش‌های برنامه‌نویسی

[برو به فهرست نوشته‌ها]
        معرفی کتاب Programming Challenges برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی یا معرفی پیوند دانلود فایل‌های صوتی، تصویری و اسلایدهای کلاس درس نویسنده

کتاب Programming Challenges: The Programming Contest Training Manual از انتشارات معتبر Springer کتاب مفیدی برای آمادگی شرکت در مسابقات برنامه‌نویسی است که نویسندگان آن به صورت گام به گام، خلاصه و مفید، به مفاهیم و نکات مهم برنامه‌نویسی، ساختمان داده‌ها، محاسبات ریاضی و طراحی الگوریتم‌ها اشاره داشته و با طرح مسائل متفاوت از هر موضوع، خواننده را به چالش حل مسأله کشیده‌اند.

    در این کتاب برای هر موضوع مورد بحث تعدادی سوال از وب‌سایت UVA انتخاب و مطرح شده است. به این ترتیب خواننده علاوه بر آشنایی با مفاهیم مختلف، با نحوه‌ی طراحی سوال از آن موضوع نیز مواجه می‌شود. نویسندگان کتاب در مقدمه به این نکته اشاره داشته‌اند که در انتخاب سوال‌ها علاوه بر مرتبط بودن موضوع، جنبه‌ی سرگرمی و جذابیت نیز تا حد ممکن رعایت شده است: «گاهی موضوعات جذاب علم کامپیوتر و ریاضیات در قالب داستان‌های سرگرم کننده بیان شده است. این مسأله مطالعه‌ی موارد جذاب دیگری را پیش می‌آورد.»

ادامه ...

روش حریصانه

[برو به فهرست نوشته‌ها]
        آشنایی با روش حریصانه و کاربردهای آن مانند مسأله‌ی خرد کردن پول

روش حریصانه (Greedy) یکی از روش‌های مشهور و پرکاربرد طراحی الگوریتم‌ها است که با ساختاری ساده در حل بسیاری از مسائل استفاده می‌شود. این روش اغلب در حل مسائل بهینه‌سازی استفاده شده و در پاره‌ای مواقع جایگزین مناسبی برای روش‌هایی مانند برنامه‌ریزی پویا است. در حالت کلی این روش سرعت و مرتبه‌ی اجرایی بهتری نسبت به روش‌های مشابه خود دارد؛ اما متناسب با مسأله ممکن است به یک جواب بهینه‌ی سراسری ختم نشود.

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

ادامه ...

کتاب هنر مسابقات برنامه‌نویسی

[برو به فهرست نوشته‌ها]
        معرفی کتاب Art of Programming Contest برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی با قابلیت دانلود نسخه‌ی الکترونیکی

وب‌سایت UVa یکی از وب‌سایت‌هایی است که امکانات مفیدی را برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی (بالاخص ACM) مهیا کرده است. در این وب‌سایت مجموعه سوالاتی در سطوح مختلف و مشابه سوالات مسابقات برنامه‌نویسی بین‌المللی در دسترس عموم قرار گرفته است که علاقه‌مندان می‌توانند پس از عضویت در سایت، پاسخ هر سوالی را که حل کرده‌اند، ارسال کنند. این جواب‌ها بررسی شده و درست یا نادرست بودن آن به کاربر ابلاغ می‌شود. می‌توان گفت نوعی شبیه‌سازی مسابقات برنامه‌نویسی رسمی انجام می‌گیرد.

    یکی از شرکت‌کنندگان مسابقات ACM به نام احمد شمس العارفین (Ahmed Shamsul Arefin) از کشور بنگلادش - که فعالیت‌های گسترده‌ی دیگری مانند وب‌سایت www.acmsolver.org نیز دارد - اقدام به انتشار کتاب رایگانی در مورد آمادگی مسابقات برنامه‌نویسی از طریق همین وب‌سایت نموده است.

ادامه ...

روش برنامه‌نویسی پویا

[برو به فهرست نوشته‌ها]
        آشنایی با روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا، برنامه‌سازی پویا - Dynamic Programming) به عنوان یکی از روش‌های پر کاربرد طراحی الگوریتم برای حل بهینه‌ی مسائل با مثالی از محاسبه‌ی دنباله‌ی فیبوناچی

یکی از روش‌های پرکاربرد و مشهور طراحی الگوریتم روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا، برنامه‌سازی پویا - Dynamic Programming) است. این روش همچون روش تقسیم و حل (Divide and Conquer) بر پایه‌ی تقسیم مسأله بر زیرمسأله‌ها کار می‌کند. اما تفاوت‌های چشم‌گیری با آن دارد.

    زمانی که یک مسأله به دو یا چند زیرمسأله تقسیم می‌شود، دو حالت ممکن است پیش بیاید:

    1- داده‌های زیرمسأله‌ها هیچ اشتراکی با هم نداشته و کاملا مستقل از هم هستند. نمونه‌ی چنین مواردی مرتب‌سازی آرایه‌ها با روش ادغام یا روش سریع است که داده‌ها به دو قسمت تقسیم شده و به صورت مجزا مرتب می‌شوند. در این حالت داده‌های یکی از بخش‌ها هیچ ارتباطی با داده‌های بخش دیگر نداشته و در نتیجه حاصل از آن بخش اثری ندارند. معمولا روش تقسیم و حل برای چنین مسائلی کارآیی خوبی دارد.

ادامه ...

روش تقسیم و غلبه

[برو به فهرست نوشته‌ها]
        آشنایی با روش Divide and Conquer (تقسیم و حل / تقسیم و غلبه) و کاربردهای آن در مرتب‌سازی، جستجو و حل مسائل الگوریتمی دیگر

یکی از روش‌های پرکاربرد و محبوب برای طراحی الگوریتم‌ها روش Divide and Conquer است که در زبان فارسی به صورت تقسیم و حل یا تقسیم و غلبه ترجمه شده است.

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

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

      

مرتب‌سازی سریع (Quick Sort)

ادامه ...