العودة إلى الدورات
متقدم
تطوير البرمجيات
en
موضوعات في علوم الحاسوب النظرية: البراهين القابلة للتحقق احتماليًا
معهد ماساتشوستس - المساقات المفتوحة
منصة
· Cambridge, USA
عن هذه الدورة
في هذه الدورة على مستوى الدراسات العليا، يتعرّف الطلاب على نظرية البراهين القابلة للتحقق احتماليًا (PCPs) وعواقبها الرئيسية في علوم الحاسوب النظرية وخوارزميات التقريب. يركّز النصف الأول من الدورة على البرهان الجبري لنظرية الـ PCP الأساسية وعلاقتها الجوهرية بمسائل التقريب. أما النصف الثاني فيتناول موضوعات أكثر تقدّمًا، بما في ذلك تضخيم الصعوبة الحسابية، وإطار الشيفرة الطويلة (long code)، وحدسية الألعاب الفريدة (Unique Games Conjecture) وتبعاتها، ونظرية ألعاب 2-إلى-2.
المهارات المطلوبة مسبقاً
المهارات التي يُفضّل امتلاكها قبل الالتحاق بهذه الدورة
الرياضيات المتقطعة
الجبر المجرد
الخوارزميات وهياكل البيانات
نظرية الاحتمالات
مقدمة في علوم الحاسوب النظرية
الرياضيات المتقطعة المتقدمة
التمكن الرياضي
المهارات المكتسبة
المهارات التي ستكتسبها عند إتمام هذه الدورة
علوم الحاسوب النظرية
نظرية التعقيد الحسابي
البراهين القابلة للتحقق احتماليًا (PCP)
خوارزميات التقريب
صعوبة مسائل التقريب
حدسية الألعاب الفريدة
تقنيات الشيفرة الطويلة
البراهين الرياضية
الرياضيات المتقطعة
التعقيد الحسابي