删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

上海交通大学软件学院博士课程内容介绍《软件理论概要》

上海交通大学 免费考研网/2012-12-28

《软件理论概要》

课程代码C037001学分/学时3.0/48开课时间春
课程名称软件理论概要
开课学院软件学院
任课教师傅育熙
面向专业软件工程
预修课程可计算理论、自动机理论
课程讨论时数0 (小时)课程实验数0 (小时)
课程内容简介

本课程以"问题描述、问题求解、问题归类"为主线，以重大理论思想的历史形成背景和核心定理的证明为主要内容，从数理逻辑、计算模型、递归论、不完备定理、计算复杂性理论五个方面，向学员阐述本学科的理论研究方法，为培养学员的计算思维能力奠定理论基础。主要内容包括：（1）数理逻辑。讲授计算机科学的逻辑基础，包括一阶逻辑及其证明论、完备性定理、算术公理、公理集合论，培养学员严密的逻辑思维能力。（2）计算模型。讲授计算的三类模型（数学模型、程序模型、机器模型），重点考察递归函数、Lambda演算和图灵机，以及它们之间的等价性证明，再次强化学员对Church-Turing Thesis的认同。（3）递归论。讲授问题的可解性与不可解度，内容覆盖了从哥德尔编码到图林度结构的基本递归论，为学员打下扎实的可计算理论基础。（4）不完备定理。讲授第一二不完备定理、第二不完备定理、一阶逻辑的不可判定性、Presburger算术的可判定性，使学员对定理自动证明、人工智能、验证等领域有定性认识。（5）计算复杂性。讲授经典复杂性理论，为学员进一步学习现代复杂性理论、密码学理论奠定基础。

课程内容简介（英文）

(无)

教学大纲

Part I. Mathematical Logic1. First order logic2. Completeness theorem3. First order theory (arithmetic, set theory)Part II. Model1. Recursive function2. Lambda calculus3. Turing machine4. URMPart III. Recursion Theory1. G?del encoding2. Problem classificationPart IV. Incompleteness Theorem1. Undecidability of first order logic2. Decidability of Presburger Arithmetic3. First Incompleteness Theorem4. Second Incompleteness Theorem

课程进度计划

(无)

课程考核要求

最终成绩由论文研讨、论文报告、期末报告组合而成。各部分所占比例如下：1.论文研讨：30%。主要考评学生在学习经典和前沿研究工作过程中的自主参与度。2.论文报告：40%。主要通过具体论文研读和报告演讲，评定学生对ru安静基础理论的学习情况和实际应用能力。3.期末报告：30%。主要考核对学生通过一学期的系统学习，对软件基础理论掌握程度和自身的理解情况。

参 考 文 献
相关话题/课程

Free考研考试FreeKaoYan.Com
欢迎来到Free考研考试，"为实现人生的Free而奋斗"

© 2020 FreeKaoYan! . All rights reserved.