تجاوز إلى المحتوى الرئيسي
User Image

عبدالمنعم محمدعلي محمد حسن ارتولي

Professor

أستاذ

علوم الحاسب والمعلومات
Building 31, 2nd floor, Room 2120
مادة دراسية

626 Advanced Theory of Computation and Computability

In-depth study of concepts related to computability - Chomsky hierarchy - Turing machines – Computability - Decidability - Nondeterministic automats, recursive function theory - Theory of complexity and complexity classification. 
Course Plan
PART I : Guided Lectures delivered by Me   (5 weeks): State of the art.
1.     Introduction to Challenges in Theoretical Computer Science
2.     Reviewing basics of TOC: Automata+Computability +Complexity
3.     Chomsky hierarchy
4.     Recognizability Vs Decidability
5.     Complexity
PART II : Students prepare presentations on  a topic   (5 weeks) from selected state of the art problems in  :
1. Complexity, computability and reducibility.
2. Kolmogorov complexity and Solomonoff’s theory of inductive inference applied to Turing Machines. (Soler-Tuscano et al., 2014)
3.Infinite time TMs of Hale.
4. Quantum computers and erasability (Neal Anderson)
 
PART III: student selects a computational challenge  of current interest and contributes to it.
Evaluation:
Midterm  30% (week 7)
Presentation  15%
Assignments 15%
End of semester written exam 40% 
 

ملحقات المادة الدراسية