Future University In Egypt (FUE)
Future University is one of most promising private universities in Egypt. Through excellence in teaching, research and service, Future University strives to provide a comprehensive, high-quality education that prepares our graduates to be future leaders.
mainLogo
Altagamoa Al Khames, Main centre of town, end of 90th Street
New Cairo
Egypt

List of Courses

Theory of Computations

  • Course Code :
    CS416
  • Level :
    Undergraduate
  • Course Hours :
    3.00 Hours
  • Department :
    Department of Computer Science

Instructor information :

Area of Study :

Apply the basic concepts theoretical foundations of computing. Combine and evaluate the principles of abstract models of computing machines, the grammars those machines recognize, and the corresponding classes of languages. Use basic mathematics to learn the principles of recursion and grammars induction. Analyze the analytical requirements of some applications for decidability. Compare, evaluate and select methodologies from range of complexity hierarchy, the prepositional calculus.

For further information :

Theory of Computations

This course deals with the theoretical foundations of computing, including abstract models of computing machines, the grammars those machines recognize, and the corresponding classes of languages. Topics include church's thesis; grammars, the m-recursive functions, and tuning computability of the m-recursive functions, the incompatibility: the halting problem, tuning innumerability, tuning acceptability, and tuning decidability, unsolvable problems about tuning machines and m-recursive functions, computational complexly: time – bounded tuning machines, rate of growth of functions, up – completeness, the complexity hierarchy, the prepositional calculus: syntax, truth – assignment, validity and satisfy, and equivalence and normal forms compactness.

For further information :

Theory of Computations


Course outcomes:

a. Knowledge and Understanding:

1- Define the fundamental concepts and theories related to foundations of computing
2- Describe methodologies and practices of abstract models of computing machines.
3- Select analytical requirements in abstract models of the process of computation such as Turing Machines, its variations, and Post Machines

b. Intellectual Skills:

1- Analyze operations, types of foundations of computing.
2- Illustrate the concepts of tuning decidability and unsolvable problems about tuning machines.
3- Evaluate the solution of prepositional calculus

c. Professional and Practical Skills:

1- Apply the relation concepts to create simple languages
2- Combine the properties of theoretical foundations to generate languages
3- Organize some concepts and theorems to perform computational complexly

d. General and Transferable Skills:

1- Exploit a range of learning resources computations theory.
2- Work in a team effectively and efficiently considering time and stress management.
3- Apply communication skills and techniques in solving reports.


For further information :

Theory of Computations

Course topics and contents:

Topic No. of hours Lecture Tutorial/Practical
Background to Theory of Formal Languages 4 2 2
Introduction to Formal Languages 4 2 2
Regular Expressions 4 2 2
Finite Automata 4 2 2
Non Deterministic Finite Automata 4 2 2
Transition Graphs 4 2 2
Context-Free Grammars 4 2 2
Pushdown Automata 4 2 2
Mid-Term Exam 2
Equivalence of Computing Paradigms 4 2 2
Turing Machines 4 2 2
Post Machines 4 2 2
Computers 4 2 2
Final Exam 2

For further information :

Theory of Computations

Teaching And Learning Methodologies:

Teaching and learning methods
Interactive Lectures including Discussions
Tutorials
Practical Lab Sessions
Self-Study (Project / Reading Materials / Online Material / Presentations)
Problem Solving

For further information :

Theory of Computations

Course Assessment :

Methods of assessment Relative weight % Week No. Assess What
Assignments 10.00 4
Final Exam 40.00 14
Midterm Exam (s) 20.00 9
Others (Participations) 10.00
Quizzes 20.00 5

For further information :

Theory of Computations

Books:

Book Author Publisher

Course notes :

An Electronic form of the Course Notes and all the slides of the Lectures is available on the Students Learning Management System (Moodle)

Recommended books :

John E. Hopcroft, Rajeev Motwani, and Jeffrey Ullman, Introduction to Automata Theory Languages and Computation, 2nd Ed., Addison Wesely, 2001

For further information :

Follow us on

Visit the Faculty

ADS