|
所在平台: Udemy |
课程主页: https://www.udemy.com/course/principles-in-theory-of-computation/
课程评论：没有评论
**计算理论原理课程总结** 本课程“计算理论原理”深入探讨了理论计算机科学的核心领域，通常被称为计算理论。该领域关注的是如何有效、算法化地解决现实世界的计算问题，并将其映射到各种计算模型上，而这些模型可以通过软件在电子硬件上实现。 课程主要围绕计算理论的三大分支展开： 1. **自动机理论 (Automata Theory):** * 研究抽象机器（而非物理硬件）在解决问题中的作用。 * 介绍了多种类型的抽象机器，包括确定性有限自动机 (DFA)、非确定性有限自动机 (NFA)、下推自动机 (PDA) 和线性有界自动机 (LBA)。 * 强调了图灵机 (Turing Machine) 作为能够执行以上所有类型自动机的通用计算模型的重要性，并指出目前尚无证据表明存在图灵机无法解决但实际计算机可以解决的问题。 2. **可计算性理论 (Computability Theory):** * 探讨哪些问题可以被计算机解决，哪些不能，即可判定性 (decidability) 和不可判定性 (undecidability)。 3. **计算复杂性理论 (Computational Complexity Theory):** * 关注算法解决问题所需的时间和空间资源，即时间复杂性 (Time Complexity) 和空间复杂性 (Space Complexity)。 总而言之，本课程为学习者提供了理解计算本质、问题可解决性的界限以及算法效率评估的基础。
Theoretical Computer Science is a field where all the real world computational problems come under it. Theoretical Computer Science is also called as Theory of Computation. Theory of computation speaks about "How efficiently the real world problems can be solved by using an algorithm in a model of computation. The model of computation denotes any mathematical model which is embedded on any electronic hardware through the software. Theory of computation is divided in to three sub fields. They are automata theory, computability theory and computational complexity theory. Automata theory denotes the study of problem solving in abstract machines. Here the abstract machines are called as mathematical model rather than it's not a hardware. Automata theory has various types of automata such as Deterministic Finite Automata, Non-deterministic finite automata, Pushdown Automata and Linear Bounded Automata. These entire automata can be performed in a single hardware called "Turing Machine". Till now nobody proved that, a problem that cannot be solved by a Turing Machine can be solved by a real world computer. The Computability speaks about "what are all the problems can be solved by a computer and cannot be solved by a computer". This is called as decidability and un-decidability. The computational complexity theory speaks about "how much time and space an algorithm takes to solve a problem. This is called as Time and Space Complexity. These are the topics are discussed in this course "Principles in Theory of Computation".
