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
90th Street
New Cairo
Egypt

Course List

Theory of Computations

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

Instructor information :

Area of Study :

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, Recent correlated software packages should be used through labs.

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, Recent correlated software packages should be used through labs

For further information :

Theory of Computations

Course outcomes:

a. Knowledge and Understanding:

1- Know the theoretical foundations of computing.
2- Understand advanced techniques for formal languages.
3- Understand Grammars those machines recognize,
4- Read, write, and manipulate an abstract specification describing the requirements of a computer system,
5- Apply various proof methods of computing and corresponding classes of languages.
6- Understand the abstract models of the process of computation such as Turing Machines, its variations, and Post Machines, and including abstract models of computing machines

b. Intellectual Skills:

1- Describe and compare the main models of computing
2- Analyze the complexity of simple computing programs
3- Explain and illustrate by means of examples the terms finite, non finite, and pushdown automata, and context free grammars, un-decidability, equivalence and decision procedures
4- Explain the use of formal systems in computers
5- Good students will be able to formally analyze simple properties of on topics of formal specifications through proof.

c. Professional and Practical Skills:

1- Approach the advanced formal languages with confidence
2- Understand new advanced formal languages

d. General and Transferable Skills:

1- Deploy communication skills
2- Deploy research skills
3- To work to tight deadlines
4- Justify students design decisions in a written document
5- Work more easily within a team to achieve an objective

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
Equivalence of Computing Paradigms 4 2 2
Turing Machines 4 2 2
Midterm Exam II 4 2 2
Post Machines 4 2 2
Computers 4 2 2
Revision 4 2 2
Final Exam 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
Midterm Exam I 4 2 2
Transition Graphs 4 2 2
Context-Free Grammars 4 2 2
Pushdown Automata 4 2 2

For further information :

Theory of Computations

Teaching And Learning Methodologies:

Teaching and learning methods
Lectures
Exercises
Projects

For further information :

Theory of Computations

Course Assessment :

Methods of assessment Relative weight % Week No. Assess What

For further information :

Theory of Computations

Books:

Book Author Publisher
Automata, Computability and Complexity: Theory and Applications Elaine Rich Pearson
Introduction to Computer Theory Daniel I. A. Cohen Wiley

For further information :

Follow us on

Visit the Faculty

ADS