计算理论概述 - 南京大学计算机科学与技术系.pdf

下载文档 降价啦

19
0
约1.79千字
约 13页
2017-09-07 发布于天津
举报
版权申诉
保障服务

计算理论概述 - 南京大学计算机科学与技术系.pdf

1、本文档共13页，其中可免费阅读4页，需付费100金币后方可阅读剩余内容。
2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，可选择认领，认领后既往收益都归您。
3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形，可联系本站下载客服投诉处理。
4、文档侵权举报电话：400-050-0827(电话支持时间：9:00-18:30)。

计算理论概述李李宣宣东东南京大学计算机科学与技术系计算理论计算机的基本能力和限制是什么自动机理论自动机理论可计算性理论复杂性理论自动机理论论述计算的数学模型和它们的定义和性质有限自动机有限自动机下推自动机图灵机可计算理论哪些问题是不能用计算机解决的哪些问题是算法上不可解的哪些问题是不存在解决它的算法的哪些问题是不存在解决它的算法的图灵机的停机问题图灵机停机问题的不可判定性没有一个算法在有限步之内能判断一个没有一个算法在有限步之内能判断一个图灵机在给定的输入串上是否能停机复杂性理论度量复杂性时间复

计算理论概述李李宣宣东东南京大学计算机科学与技术系 http://cs/people/lixuandong/formlcn/people/lixuandong/forml.htmlhtml 计算理论计算机的基本能力和限制是什么？ •• 自动机理论自动机理论 • 可计算性理论 • 复杂性理论自动机理论论述计算的数学模型和它们的