فلش‌کارت‌های آموزشی مبانی و کاربردهای نظریه محاسبه پذیری (بر اساس کتاب Sommerhalder)

🎓 دوره آموزشی جامع

📚 اطلاعات دوره

عنوان دوره: دوره مبانی و کاربردهای نظریه محاسبه پذیری (بر اساس کتاب Sommerhalder)

موضوع کلی: علوم کامپیوتر نظری

موضوع میانی: نظریه محاسبه پذیری

📋 سرفصل‌های دوره

• 1. مقدمه‌ای بر علوم کامپیوتر نظری
• 2. تاریخچه نظریه محاسبه‌پذیری
• 3. مفاهیم بنیادی مجموعه، رابطه و تابع
• 4. رابطه‌ها و توابع روی مجموعه‌های طبیعی
• 5. اعداد طبیعی و اصل استقرای ریاضی
• 6. تعاریف بازگشتی و القایی
• 7. الفباها، رشته‌ها و زبان‌ها
• 8. مقدمه‌ای بر منطق گزاره‌ای
• 9. مقدمه‌ای بر منطق محمولات مرتبه اول
• 10. فرمول‌های خوش‌ساخت و ساختار نحوی
• 11. استنتاج و برهان در منطق
• 12. مفهوم الگوریتم و محاسبات
• 13. تابع‌های پایه برای بازگشتی اولیه
• 14. عملگر ترکیب (Composition) توابع
• 15. تعریف بازگشت اولیه (Primitive Recursion)
• 16. مجموعه توابع بازگشتی اولیه (Primitive Recursive Functions)
• 17. خواص بسته بودن توابع بازگشتی اولیه
• 18. توابع جمع و ضرب به عنوان توابع بازگشتی اولیه
• 19. توابع توان و تفریق معین به عنوان توابع بازگشتی اولیه
• 20. توابع پیش‌بینی (Projection Functions)
• 21. توابع منطقی و شرطی بازگشتی اولیه
• 22. عملگر حداقل‌سازی کراندار (Bounded Minimization)
• 23. روابط بازگشتی اولیه (Primitive Recursive Relations)
• 24. کدگذاری زوج‌های مرتب کانتور
• 25. کدگذاری دنباله‌های متناهی (Gödel Numbering)
• 26. دیکدینگ توابع و دنباله‌ها
• 27. محدودیت‌های توابع بازگشتی اولیه
• 28. توابع بدون توقف و توابع جزئی
• 29. عملگر حداقل‌سازی نامحدود (Unbounded Minimization یا μ-operator)
• 30. تعریف توابع بازگشتی عمومی (General Recursive Functions)
• 31. رابطه توابع بازگشتی اولیه و عمومی
• 32. قضیه فرم نرمال کلین (Kleene's Normal Form Theorem)
• 33. مدل‌های معادل محاسبه‌پذیری (مقدمه)
• 34. تز چرچ-تورینگ (Church-Turing Thesis)
• 35. شهود پشت تز چرچ-تورینگ
• 36. اهمیت تز چرچ-تورینگ در علوم کامپیوتر
• 37. تعریف رسمی ماشین تورینگ (Turing Machine)
• 38. پیکربندی ماشین تورینگ و گام‌های محاسبه
• 39. طراحی ماشین‌های تورینگ ساده
• 40. ماشین‌های تورینگ چند نواره (Multi-Tape Turing Machines)
• 41. ماشین‌های تورینگ چند سر (Multi-Head Turing Machines)
• 42. ماشین‌های تورینگ غیرقطعی (Non-Deterministic Turing Machines)
• 43. معادل بودن قدرت مدل‌های مختلف ماشین تورینگ
• 44. ماشین تورینگ جهانی (Universal Turing Machine)
• 45. عملکرد و طراحی ماشین تورینگ جهانی
• 46. کدگذاری ماشین‌های تورینگ (Gödel Numbering for TMs)
• 47. زبان‌های بازگشتی (Recursive Languages)
• 48. زبان‌های بازگشتی شمارش‌پذیر (Recursively Enumerable Languages)
• 49. تفاوت زبان‌های بازگشتی و بازگشتی شمارش‌پذیر
• 50. ماشین‌های رجیستر (Register Machines/RAMs)
• 51. معادل بودن ماشین‌های رجیستر و ماشین‌های تورینگ
• 52. مقدمه‌ای بر Lambda Calculus (محاسبات لامبدا)
• 53. معادل بودن لامبدا کالکولوس و ماشین تورینگ
• 54. سیستم‌های پست (Post Systems)
• 55. قضیه فرم نرمال برای توابع جزئی محاسبه‌پذیر
• 56. مسائل تصمیم‌ناپذیر و شمارش‌ناپذیر
• 57. روش قطردهی کانتور (Cantor's Diagonalization)
• 58. مسئله توقف (Halting Problem)
• 59. اثبات توقف‌ناپذیری مسئله توقف
• 60. مفهوم توابع غیرقابل محاسبه
• 61. مجموعه K و خواص آن
• 62. مکمل مجموعه‌های بازگشتی شمارش‌پذیر
• 63. تقلیل‌پذیری (Reducibility)
• 64. تقلیل‌پذیری Many-One (m-reducibility)
• 65. تقلیل‌پذیری One-One (1-reducibility)
• 66. قضیه رایس (Rice's Theorem)
• 67. اثبات قضیه رایس
• 68. کاربردهای قضیه رایس: مسائل تصمیم‌ناپذیر دیگر
• 69. مسئله تطابق پست (Post Correspondence Problem - PCP)
• 70. اثبات تصمیم‌ناپذیری PCP
• 71. مسائل تصمیم‌ناپذیر در منطق (Entscheidungsproblem)
• 72. مسائل تصمیم‌ناپذیر در نظریه زبان‌های رسمی
• 73. مسائل تصمیم‌ناپذیر در نظریه گراف
• 74. مسائل تصمیم‌ناپذیر در ریاضیات (مثلاً هیلبرت دهم)
• 75. قضیه بازگشت کلین (Kleene's Recursion Theorem)
• 76. کاربردهای قضیه بازگشت
• 77. تابع‌های نقطه ثابت و بازگشت
• 78. مجموعه‌های بازگشتی شمارش‌پذیر (r.e. Sets)
• 79. خواص بستار مجموعه‌های r.e.
• 80. مجموعه‌های خلاق (Creative Sets)
• 81. مجموعه‌های مولد (Productive Sets)
• 82. قضیه مای‌هیل (Myhill's Isomorphism Theorem)
• 83. خواص مجموعه‌های خلاق و مولد
• 84. مجموعه‌های ساده (Simple Sets)
• 85. مجموعه‌های ایمن (Immune Sets)
• 86. محاسبات نسبی (Relative Computability)
• 87. ماشین‌های تورینگ با اوراکل (Oracle Turing Machines)
• 88. تقلیل‌پذیری تورینگ (Turing Reducibility)
• 89. درجه‌های تورینگ (Turing Degrees)
• 90. ساختار نیم-شبکه درجه‌های تورینگ
• 91. وجود درجه‌های تورینگ غیرقابل مقایسه
• 92. سلسله مراتب حسابی (Arithmetical Hierarchy)
• 93. کلاس‌های سیگما (Σ_n) سلسله مراتب حسابی
• 94. کلاس‌های پی (Π_n) سلسله مراتب حسابی
• 95. کلاس‌های دلتا (Δ_n) سلسله مراتب حسابی
• 96. ارتباط سلسله مراتب حسابی با مجموعه‌های r.e. و Co-r.e.
• 97. ارتباط با قضایای ناتمامیت گودل
• 98. محدودیت‌های ذاتی سیستم‌های صوری
• 99. مقدمه‌ای بر پیچیدگی محاسباتی و نظریه P و NP
• 100. جنبه‌های فلسفی نظریه محاسبه‌پذیری و آینده آن