سایت آموزشی ادکس برگزار می‌کند:آموزش رایگان مسائل NP-complete در طراحی الگوریتم

شما در این دوره آموزشی رایگان می‎‌توانید در‌مورد مسائل NP-complete یاد بگیرید، که به‌عنوان مسائل سختی شناخته می‌شوند که نمی‌توان آنها را به‌صورت کارآمد حل کرد. به‌علاوه از طریق این دوره می‌توانید، حل این مسائل را با استفاده از تکنیک‌های الگوریتمی تمرین نمایید.

دوره «مسائل NP-complete» که بخشی از برنامه MicroMasters الگوریتم‌ها و ساختارهای داده است، مسائل ذاتا سختی را که در دنیای واقعی با آنها مواجه خواهید شد و الگوریتم کارآمد شناخته‌شده‌ای ندارند و به‌عنوان مسائل NP-Complete شناخته می‌شوند، مورد بحث قرار می‌دهد.

آنچه در این دوره خواهید آموخت

آنچه در این دوره به شما ارائه می‌گردد عبارت است از: «NP-کامل بودن و نحوه برخورد با آن»، «نحوه تقریب الگوریتم‌ها» و «نحوه استفاده از الگوریتم‌های اکتشافی برای حل سریع‌تر یک مسئله، زمانی که روش‌های کلاسیک خیلی در این زمینه کند عمل می‌کنند.»

در‌حقیقت شما با استفاده از نرم‌افزارهای تخصصی بسیار کارآمد و تکنیک‌های الگوریتمی از‌جمله «حل‌کننده‌های مسائل خانواده SAT»، «الگوریتم‌های تقریبی»، «موارد خاص مسائل NP-hard» و «الگوریتم‌های اکتشافی»، به شناخت مسائل NP-complete در طراحی الگوریتم خواهید پرداخت.

نگاهی به سرفصل دروس این دوره

مفاهیم ارائه‌شده در هفته اول تحت‌عنوان مسائل NP-complete است، اگرچه بسیاری از الگوریتم‌هایی که تاکنون آموخته‌اید، در عمل بسیار استفاده می‌شوند، اما به نظر می‌رسد که جهان تحت سلطه مشکلات دنیای واقعی است، بدون اینکه توسط یک الگوریتم کارآمد شناخته‌شده قابل اثبات باشد. بسیاری از این مسائل را می‌توان به یکی از مسائل کلاسیک به نام مسائل NP-complete تقلیل داد، که با یک الگوریتم چندجمله‌ای قابل‌حل نیستند و حل هر‌یک از ‌آنها برای شما یک میلیون دلار به ارمغان می‌آورد (مسائل جایزه هزاره را ببینید)، ضمن ‌آنکه شهرت ابدی در سراسر جهان برای شما رقم خواهد زد.

یکی دیگر از مفاهیم این فصل، حل مشکل اصلی علوم کامپیوتر به نام P در مقابل NP است. یادگیری این مفهوم برای شما خوب است، پیش از آنکه تلاش کنید برای حل یک مشکل و پیش از آنکه فردا برسد، بهتر است با این موضوعات آشنایی داشته باشید. اگرچه بعید است که این مشکلات در‌آینده نزدیک به‌طور موثر قابل‌ حل باشند، اما مردم همیشه راه‌حل‌های مختلفی را ارائه می‌دهند. در این ماژول شما مسائل کلاسیک NP-complete و کاهش بین آنها را مطالعه خواهید کرد. شما همچنین حل نمونه‌های بزرگ برخی از این مشکلات را با وجود سختی آنها، با استفاده از نرم‌افزارهای تخصصی بسیار کارآمد، بر‌اساس تحقیقات فراوان در ‌زمینه مسائل NP-complete، تمرین خواهید کرد.

در هفته دوم این آموزش شما به مبحث مقابله با کامل بودن NP در موارد خاص خواهید رسید. ممکن است پس از اتمام فصل قبلی، احساس ناامیدی و یاس به شما دست داده باشد. شما 5 دوره در الگوریتم‌ها را گذرانده‌اید تا متوجه شوید که آنها برای اکثر مشکلات دنیای واقعی مناسب نیستند! با‌این‌حال، پیشنهاد می‌کنیم هنوز تسلیم نشوید! زیرا افراد خلاقی هستند و می‌دانند که به‌هر‌حال باید این مشکلات را حل کنند، بنابراین در‌عمل راه‌هایی برای کنار‌آمدن با یک مشکل NP-complete وجود دارد. در این فصل شما در‌می‌یابید که برخی از این موارد خاص در مسائل NP-complete، در‌واقع می‌توانند در‌ مرتبه زمانی چند‌جمله‌ای حل شوند.

عنوان مباحث هفته سوم مقابله با کامل بودن NP بوده و شامل موضوعاتی همچون الگوریتم‌های دقیق، تقریبی و الگوریتم‌های دقیقی می‌شود که سریع‌تر از الگوریتم brute force راه‌حل را پیدا می‌کنند. در این دوره شما با کمک الگوریتم‌های تقریبی که در زمان چند‌جمله‌ای کار می‌کنند، نتیجه‌گیری کرده و راه‌حلی را پیدا می‌کنید که نزدیک به بهینه باشد.

آشنایی با استادان دوره

این دوره توسط Alexander S. Kulikov استاد مدعو دانشگاه کالیفرنیا San Diego و Daniel Kane استادیار، علوم کامپیوتر و مهندسی و گروه ریاضیات از دانشگاه کالیفرنیا San Diego ارائه می‌گردد. Kulikov همچنین یک محقق در موسسه ریاضی Steklov در سنت‌پترزبورگ روسیه بوده و بیش از هشت سال است که در کلاس‌های الگوریتم تدریس می‌کند. Kane استادیار دانشگاه UCSD، با انتصاب مشترک بین دپارتمان علوم و مهندسی کامپیوتر و دپارتمان ریاضیات است. او دارای مدرک کارشناسی از MIT و Ph.D از هاروارد است.

چه کسانی می‌توانند در این دوره شرکت کنند؟

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

برای ارزیابی پایداری، امنیت و نگهداری این زیرساخت، راهنمای پشتیبانی شبکه را نیز مطالعه کنید.