0

(

ratings

)

1

students

Created by:

Profile Photo

Last updated:

September 25, 2023

Duration:

Unlimited Duration

FREE

This course includes:

Unlimited Duration

Badge on Completion

Certificate of completion

Unlimited Duration

Description

Theory of Computation (ArsDigita University). Instructor: Shai Simonson.

A theoretical treatment of what can be computed and how fast it can be done. Applications to compilers, string searching, and control circuit design will be discussed. The hierarchy of finite state machines, pushdown machines, context free grammars and Turing machines will be analyzed, along with their variations. The notions of decidability, complexity theory and a complete discussion of NP-Complete problems round out the course. (from ADUni.org)

Course Curriculum

  • Lecture 01 – Finite State Machines Unlimited
  • Lecture 02 – Closure and Nondeterminism Unlimited
  • Lecture 03 – The Pumping Lemma Unlimited
  • Lecture 04 – Minimizing FSMs Unlimited
  • Lecture 05 – Recitation 1 Unlimited
  • Lecture 06 – Context Free Languages Unlimited
  • Lecture 07 – CFLs and Compilers Unlimited
  • Lecture 08 – Recitation 2 Unlimited
  • Lecture 09 – Pushdown Machines Unlimited
  • Lecture 10 – Recitation 3 Unlimited
  • Lecture 11 – CFGs and NPDMs Unlimited
  • Lecture 12 – More lemmas, CYK Unlimited
  • Lecture 13 – Undecidability and CFLs Unlimited
  • Lecture 14 – Recitation 4 Unlimited
  • Lecture 15 – The Bullseye Unlimited
  • Lecture 16 – Turing Machines Unlimited
  • Lecture 17 – Recitation 5 Unlimited
  • Lecture 18 – The Halting Problem Unlimited
  • Lecture 19 – Decidability Unlimited
  • Lecture 20 – Complexity Theory, Quantified Boolean Formula Unlimited
  • Lecture 21 – Savitch’s Theorem, Space Hierarchy Unlimited
  • Lecture 22 – Decidability/Complexity Relationship, Recursion Theorem Unlimited

About the instructor

5 5

Instructor Rating

6

Reviews

4637

Courses

24151

Students

Profile Photo
OpenCoursa
We are an educational and skills marketplace to accommodate the needs of skills enhancement and free equal education across the globe to the millions. We are bringing courses and trainings every single day for our users. We welcome everyone woth all ages, all background to learn. There is so much available to learn and deliver to the people.