وصف المقرر : يقدم هذا المقرر مقدمة في نظرية التعقيد الحسابي. تشمل الموضوعات: المسائل السهلة والصعبة، آلات تورينغ، مسألة التوقف واللغات غير القابلة للتقرير (آلة تورينغ الشاملة)، فئات التعقيد الحتمية، P و NP، واكتمال-NP (آلات تورينغ غير الحتمية، مسار هاملتون، الوقت شبه كثير الحدود، صعوبة-NP)، تعقيد المساحة ونظريات التدرج الهرمي (Hierarchy theorems). بالإضافة إلى ذلك، يغطي المقرر موضوعات تتعلق بالتحسين والتقريب، مع تقديم مفاهيم متقدمة للطلاب مثل التعقيد العشوائي (Randomized complexity).
الساعات المعتمدة : 3
أهداف المقرر :
• تصنيف مسائل القرار إلى فئات التعقيد المناسبة.
• التعبير بدقة عما يعنيه اختزال مسألة إلى أخرى، وبناء عمليات اختزال لأمثلة بسيطة.
• تصنيف مسائل التحسين إلى فئات تعقيد التقريب المناسبة واستخدام هذه المعلومات بفعالية.
مخرجات المقرر :
1. المعرفة والفهم:
1.1. تصنيف مسائل القرار إلى فئات التعقيد المناسبة.
1.2. التعبير بدقة عما يعنيه اختزال مسألة إلى مسألة أخرى، وبناء عمليات اختزال لأمثلة بسيطة.
2. المهارات:
2.1. تصميم حلول لمسائل تحسين محددة.
2.2. استخدام مفهوم البراهين التفاعلية في تحليل مسائل التحسين.
3. القيم:
3.1. القدرة على تطبيق البراهين التفاعلية في تحليل مسائل التحسين.
هذا الموقع يستخدم ملفات تعريف الارتباط الخاصة لضمان سهولة الاستخدام، وتحسين تجربتك أثناء التصفح، كما يوضح الأحكام والسياسات المتعلقة بخصوصية المستخدم. من خلال الاستمرار في تصفح هذا الموقع، فإنك تقر بقبول استخدام ملفات تعريف الارتباط، وما جاء في سياسة الخصوصية