دليل المراجعة · GKU 1

دليل مراجعة الخوارزميات والحوسبة والتعقيد (علوم الحاسب)

تطرح هذه الوحدة نوعين من الأسئلة. الأول عملي: إذا أُعطيت مسألة، فأي طريقة تحلها، وبأي سرعة، وبكم من الذاكرة — ويُجاب عنه بعدّ العمليات وحل العلاقات التكرارية وتوقيت التشغيل الفعلي، والاختيار بين فرّق تسد والقواعد الجشعة والبرمجة الديناميكية والتراجع والطرق الاستدلالية. والثاني نظري: ماذا تستطيع الآلة أن تحسب أصلاً، وماذا تستطيع أن تحسب بكفاءة — ويُجاب عنه بالآلات المنتهية والقواعد النحوية وآلات تورنغ ومسألة التوقف والفئتين P وNP. ويلتقي النصفان في القسم الأخير، حيث تغيّر معرفةُ أن المسألة NP-complete الخوارزميةَ التي ينبغي أن تكتبها. يبدأ كل قسم ببطاقة مراجعة سريعة، وتتدرج الأمثلة المحلولة من السهل إلى مستوى الاختبار، وقد تُحقق من كل تتبع وكل رقم فيها بتشغيله.