بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
مراجع درس
- مرجع اصلی:
- Sipser, ”Introduction to the Theory of Computation,” 2nd Ed., Thompson Learning Inc., 2006.
- مراجع کمکی:
- Linz, “An Introduction to Formal Languages and Automata,” 3rd Ed., Jones and Barlett Publishers, Inc., 2001.
J.E. Hopcroft, R. Motwani and J.D. Ullman, “Introduction to Automata Theory, Languages, and Computation,” 2nd Ed., Addison-Wesley, 2001.
P.J. Denning, J.B. Dennnis, and J.E. Qualitz, “Machines, Languages, and Computation,” Prentice-Hall, Inc., 1978.
اسلاید 2 :
سیاست نمره دهی درس
- تمرینات %10
- کوییزهای کوتاه مربوط به تمرینات %15
- کوییز های عمومی درس 45%
- آزمون پایان نیمسال %30
اسلاید 3 :
نظریه پیچیدگی
- دانش رده بندی مسائل بر اساس سختی محاسباتی
- برای غلبه بر پیچیدگی چه می توان کرد؟
–تغییر مسئله پس از کشف که عامل دشواری آن
–تقریب زدن راه حل مسئله
–ارائه روش هایی که در حالت متوسط عملکرد خوبی دارند؛
–استفاده از روش های تصادفی
- کاربردها
–به عنوان مثال در رمزنگاری، هدف این است که رمزگشایی با توان محاسباتی مهاجم غیرممکن باشد.
اسلاید 4 :
عناوین مورد بحث
- نظریه پیچیدگی
- نظریه محاسبه پذیری
- نظریه ماشین ها
- مبانی ریاضی
- الفبا
- رشته ها
- زبان ها
اسلاید 5 :
نظریه محاسبه پذیری
- ماشین ها چه مسائلی را می توانند حل کنند؟
- رده بندی مسائل در دو گروه قابل محاسبه و غیرقابل محاسبه
- مدل های نظری برای ماشین ها
–به علت قدرتمندی مدل هایی مانند RAM یا ماشین تورینگ اثبات این که چه مسائلی را می توانند حل کنند دشوار است.
اسلاید 6 :
نظریه ماشین ها
- تعریف و ویژگی های مدل های ریاضی محاسبه
–مدل ماشین حالت متناهی
- در پردازش متن، کامپایلرها و طراحی سخت افزار کاربرد دارد.
–مدل ماشین پشته ای
- در زبان های برنامه سازی و هوش مصنوعی کاربرد دارد.
اسلاید 7 :
انواع منطق
- Propositional logic منطق کامل
- Predicate logic منطق مُسندی
اسلاید 8 :
تعريف منطق
Syntax
مجموعه اي از متغيرها و انواع عملگرها
{p, q, r, …} متغيرها
و
} , ν, →, ↔^{┐, عملگرها
Semantic
معنايي که توسط جدول درستي براي دنباله اي از نمادها به تعداد محدود بار، به
همراه يک Syntax خاص، تعريف مي شود.
اسلاید 9 :
تعاريف
- فرمول : دنباله اي محدود از نمادها به تعداد محدود بار به همراه يک Syntax خاص
- Logical System: مجموعه اي از اصول و قواعد استنتاج
- اصول (axioms): گزاره هايي از منطق مورد نظر که هميشه درست است، تعداد آنها مي تواند محدود يا نامحدود باشد.
- قواعد استنتاج: قواعدي که از طريق آنها مي توان از دو گزارۀ درست به يک گزارۀ درست ديگر رسيد.
اسلاید 10 :
ادامه
- اثبات : دنباله اي است از گزاره هاي p1,p2,…,pk به گونه اي که p1 بايد يکي از اصول و p2 بايد يکي از اصول باشد يا با استفاده از p1 و يکي از قواعد استنتاج اثبات مي شود و p3 هم ... که به اين مراحل يک اثبات براي pk گفته مي شود.
- قضيه (theorem) : گزاره اي است که در منطق، براي آن اثباتي وجود داشته باشد.
- منطق غير کامل : فرمول هايي وجود دارد که نمي توان آنها را اثبات کرد.
