Time in the Analysis of Algorithms
Time in the Analysis of Algorithms
复制标题
DOI：
10.1007/978-3-642-32332-4_6
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Carlo A. Furia;D. Mandrioli;A. Morzenti;M. Rossi
中科院分区：
文献类型：
--
作者：
Carlo A. Furia;D. Mandrioli;A. Morzenti;M. Rossi
在这一章中，我们给出了计算和算法的经典理论的基本模型和结果的简要概述。根据本书的总主题，概述突出了软件和计算过程的传统描述中的时间特征。本章从经典的图灵机模型和用于度量图灵机计算复杂性的非常抽象的时间概念开始，复杂性类的定义依赖于此。它继续介绍随机存取机（RAM），一个计算模型仍然抽象，但更接近真实的计算机的体系结构比简单的图灵机。最后，它讨论了具有随机行为的计算模型，如马尔可夫链和概率图灵机。
In this chapter, we give a concise overview of the fundamental models and results of the classic theory of computation and algorithms. In accordance with the general theme of the book, the overview highlights the characteristics of time in the traditional descriptions of software and computational processes. The chapter starts with the classic Turing machine model and with the very abstract notion of time used to measure the computational complexity of Turing machines, on which the definition of complexity classes rests. It continues with the presentation of Random Access Machines (RAM), a computational model still abstract but much closer to the architecture of real computers than the simple Turing machine. Finally, it discusses models of computation with randomized behavior, such as Markov chains and probabilistic Turing machines.