نظرية الأوتوماتا

تغطي هذه الدورة نظرية الأوتوماتا واللغات الشكلية، وتبدأ بدراسة الأوتوماتا المحدودة (Finite Automata) واللغات التي يمكنها تعريفها، والمعروفة باللغات المنتظمة (Regular Languages). تشمل الموضوعات الأوتوماتا الحتمية وغير الحتمية، والتعبيرات النمطية (Regular Expressions)، وإثبات التكافؤ بين هذه الآليات المختلفة لتعريف اللغات. كما تتناول الدورة خصائص الإغلاق للغات المنتظمة؛ مثل حقيقة أن اتحاد لغتين منتظمتين ينتج لغة منتظمة أيضًا. بعد ذلك ندرس خصائص القرار (Decision Properties) للغات المنتظمة، مثل وجود خوارزمية تستطيع تحديد ما إذا كانت اللغة التي يعرّفها أوتوماتان محدودان هي اللغة نفسها أم لا. وفي نهاية هذا الجزء نتعرّف على «مبرهنة الضخ» (Pumping Lemma) للغات المنتظمة، وهي أداة لإثبات أن بعض اللغات ليست منتظمة. ثم تنتقل الدورة إلى موضوع القواعد الخالية من السياق (Context-Free Grammars) واللغات الناتجة عنها. نتعلم كيفية تمثيل الاشتقاق باستخدام أشجار التحليل (Parse Trees) ومفاهيم التحليل النحوي (Parsing) المرتبطة بها. كما تمتد الدراسة إلى آلات تورنغ ومفهوم قابلية القرار (Decidability)، وصولًا إلى نظرية الاستعصاء الحسابي (Intractability) ومشكلات NP-Complete.

• فهم الأوتوماتا المحدودة والتعبيرات النمطية وكيفية توصيف اللغات المنتظمة
• تعلم القواعد الخالية من السياق واللغات المرتبطة بها وأشجار التحليل
• فهم آلات تورنغ ومفاهيم قابلية القرار وحدود ما يمكن حسمه خوارزميًا
• التعرف إلى نظرية الاستعصاء الحسابي ومشكلات NP-Complete

• مستوى جيد من النضج الرياضي والقدرة على قراءة البراهين وكتابتها
• معرفة مفيدة بالرسوم البيانية والأشجار والمنطق، إضافة إلى هياكل البيانات والخوارزميات الأساسية
• مناسب لطلاب لديهم ما لا يقل عن سنتين من مقررات علوم الحاسوب، بما في ذلك الرياضيات المتقطعة ومقدمة في هياكل البيانات والخوارزميات