The Theory of Computation is a scientific discipline concerned with the study of general properties of computation be it natural, man-made, or imaginary. Most importantly, it aims to understand the nature of efficient computation. The [course_title] is designed to introduce various models of computation and study your power and limitations. This course covers the theoretical computer science areas of formal languages and automata, computability and complexity.
Assessment
This course does not involve any written exams. Students need to answer 5 assignment questions to complete the course, the answers will be in the form of written work in pdf or word. Students can write the answers in their own time. Each answer needs to be 200 words (1 Page). Once the answers are submitted, the tutor will check and assess the work.
Certification
Edukite courses are free to study. To successfully complete a course you must submit all the assignment of the course as part of the assessment. Upon successful completion of a course, you can choose to make your achievement formal by obtaining your Certificate at a cost of £49.
Having an Official Edukite Certification is a great way to celebrate and share your success. You can:
- Add the certificate to your CV or resume and brighten up your career
- Show it to prove your success
Course Credit: Open Culture
Course Curriculum
| L1: Introduction to Finite-State Machines and Regular Languages | 01:06:00 | ||
| L2: Regular Languages and Non-Deterministic FSMs | 01:21:00 | ||
| L4: Regular Expressions | 01:19:00 | ||
| L5: Regular Expressions, Regular Languages and Non-Regular Languages | 01:18:00 | ||
| L6: The Pumping Lemma and Introduction to CFLs | 01:17:00 | ||
| L7: Contex-Free Grammars and Push-Down Automata | 01:19:00 | ||
| L8: Introduction to Turing Machines and Computations | 01:15:00 | ||
| L9: More TM Design and Introduction to Non-Determinstic TMs | 01:20:00 | ||
| L10: Equivalence of Non-Deterministic and Deterministic TMs | 01:16:00 | ||
| L11: Church-Turing Thesis and Examples of Decidable Languages | 01:18:00 | ||
| L12: Universal Turing Machines; The Halting Problem is Recognizable but Not Decidable | 01:19:00 | ||
| L13: Diagonalization, Countability and Uncountability | 01:13:00 | ||
| L14: More Diagonalization; Proof that Turing Machines are Countable | 00:11:00 | ||
| L15: Proof by Diagonalization that ATM (Halting Problem) is Not Decidable | 00:25:00 | ||
| L16: Unrecognizable Languages and Reductions | 00:40:00 | ||
| L17: Using Reductions to Prove Language Undecidable | 00:54:00 | ||
| L18: More Complex Reductions | 01:15:00 | ||
| L19: Uncomputable Functions, and Introduction to Complexity | 01:21:00 | ||
| L20: P, NP and Polynomial-Time Reductions | 00:33:00 | ||
| L21: NP-Completeness | 01:12:00 | ||
| L25: Minimizing Finite State Machines | 01:14:00 | ||
| L26: Minimizing the Number of States in a DFA | 01:26:00 | ||
| Assessment | |||
| Submit Your Assignment | 00:00:00 | ||
| Certification | 00:00:00 | ||
Course Reviews
No Reviews found for this course.
Related Courses
