آموزش نظریه محاسبه

آموزش نظریه محاسبه

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

با پیشرفت های روز افزون در زمینه توسعه الگوریتم های کامپیوتری همچنان سؤالات زیادی در ارتباط با محدودیت های محاسبات با این الگوریتم ها وجود دارد به طوری که از هفت مسئله باز قرن ۲۱ که توسط انجمن ریاضی کلی در سال ۲۰۰۰ طرح شده اند و دارای جایزه یک میلیون دلاری می باشند یک مسئله مربوط به نظریه محاسبه می باشد.

استفاده از مفاهیم نسبتاً پیچیده ریاضی برای اثبات قضایای چون تز چرچ –تورینگ و یا مسئله کاهش پذیری از یک طرف و واضح نبودن ارتباط این درس با سایر دروس علوم کامپیوتر یادگیری این درس را برای دانشجویانی که برای اولین بار با این مطالب مواجه می شوند سخت و پیچیده می کند.

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

ارائه درس نظریه محاسبه بر اساس سرفصل وزارت علوم به گونه ای که ضمن یادگیری مفاهیم لازم فراگیر دید روشنی نسبت به روند تاریخی این درس و کاربردهای آن در حال حاضر پیدا نماید از اهداف اصلی این دوره خواهد بود.

نظریه محاسبه در کنار نظریه پیچیدگی دو شاخه اصلی در علوم کامپیوتر می باشند. اینکه بدانیم که به طور مشخص برای حل یک مسئله می توانیم یک الگوریتم کامپیوتری یافت یا نه؟ سؤالی است که هر دانشجو یا محقق علوم کامپیوتر در کنار گذراندن دروس یا پِژوهش کردن در زمینه هایی چون رمزنگاری یا هندسه محاسباتی ضروری است دید روشنی نسبت به آن داشته باشد.

 

 

برای مشاهده جزئیات و تهیه آموزش نظریه محاسبه به این لینک (+) مراجعه نمایید.

 

فهرست سرفصل ها و رئوس مطالب مطرح شده در این مجموعه آموزشی، در ادامه آمده است:

  • درس یکم: ماشین تورینگ و انواع آن
    • تعریف ماشین تورینگ
    • برنامه نویسی ماشین های تورینگ
    • مسائل ۲۳ گانه هیلبرت
    • سیر تاریخی مسئله تورینگ
    • قضیه چرچ – تورینگ
    • انواع ماشین تورینگ
    • شبیه سازی چند ماشین تورینگ
    • تشریح معادل بودن عملکرد ماشین تورینگ و عملکرد کامپیوترهای واقعی
  • درس دوم: تصمیم پذیری و تصمیم ناپذیری ناپذیری
    • تصمیم پذیری زبان های منظم
    • تصمیم پذیری زبان های مستقل متن
    • مسئله پست PCP
    • ماشین تورینگ عمومی و مسئله تصمیم پذیری
  • درس سوم: کاهش پذیری
    • مسئله توقف و تصمیم ناپذیری
    • تبین مسئله کاهش پذیری
    • چند مثال در مورد کاهش پذیری
  • درس چهارم: کلاس مسائل P و NP
    • زمان چند جمله ای
    • کارایی در انواع ماشین تورینگ
    • کلاس P
    • مسائل NP
    • مسئله SAT و ۳SAT
    • کلاس P و NP و مسئله کاهش پذیری
    • کاهش پذیری SAT و ۳SAT به یکدیگر 
    • قضیه کوک – لوین

 

مفید برای رشته های

  • علوم کامپیوتر
  • مهندسی کامپیوتر
  • ریاضی

 

پیش نیاز

 

 

برای مشاهده جزئیات و تهیه آموزش نظریه محاسبه به این لینک (+) مراجعه نمایید.

 

0 پاسخ

ارسال یک پاسخ

در گفتگو ها شرکت کنید.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *