第三节其他应用 1.主要内容 单源最短路径，布线问题，批处理作业调度问题。 2.基本概今和知识占 各类问题的定义、算法应用 问题与应用 用多种方法求解 (三)实践环节 01背包问题的分支限界法算法实现。 (四)教学方法与手段 课堂讲授为 结合课堂分组讨论 第七章NP完全性理论与近似算法 (一)目的与要求 1.了解NPC理论中的假设条件，并能够从“真理的相对性”角度，来阐述 NP完全之所以能够成立的前提假设： 2· 掌握P类与N 题的划分 利用近似算法解决问题的基本思想，能对其可靠性进行分。 (二)教学内容 第一节问题分类 1. 主要内容 计算模型：确定性图灵机DTM、非确定性图灵机NDTM 问题的分类：P类与NP类问题、不可解问题 2.基本概今和知识点 DTM与NDTM P类与NP类问题 此内容的教学过程中，要介绍一下计算机之父A.MTui血g,及等价于计算机 界的NOBEL奖地位的“图灵奖”得主中，于2000年获得图灵奖的华人姚期 智教授，计算理论包括伪随机数生成、密码学与通信复杂度的突出贡献，美 国计算机协会(ACM)把2000年度的图灵奖授予他。姚期智是图灵奖创立 以来首位获奖的亚裔学者，也是迄今为止获此殊荣的唯一华裔计算机科学家。 姚期智教授放弃了自己在美国优厚的工作待遇，甚至是不惜变卖自己在美国 的房产回国，充分展现了中华学子的爱国情怀！同时强调：姚期智教授在计 算理论中所做出的突出贡献，充实和完普了NP完全理论的知识体系。 3.问题与知识要点 问题及其分类，问题的难度与时间复杂性关系、NP类问题的证明 第二节NP完全问题与NP-hard问题 1.主要内容 77 第三节 其他应用 1．主要内容 单源最短路径，布线问题，批处理作业调度问题。 2． 基本概念和知识点 各类问题的定义、算法应用 3． 问题与应用 用多种方法求解 （三）实践环节 0-1 背包问题的分支限界法算法实现。 （四）教学方法与手段 课堂讲授为主，结合课堂分组讨论。 第七章 NP 完全性理论与近似算法 （一）目的与要求 1．了解 NPC 理论中的假设条件，并能够从“真理的相对性”角度，来阐述 NP 完全之所以能够成立的前提假设； 2．掌握 P 类与 NP 类问题的划分； 3．掌握利用近似算法解决问题的基本思想，能对其可靠性进行分。 （二）教学内容 第一节 问题分类 1. 主要内容 计算模型：确定性图灵机 DTM、非确定性图灵机 NDTM 问题的分类：P 类与 NP 类问题、不可解问题 2. 基本概念和知识点 DTM 与 NDTM P 类与 NP 类问题 此内容的教学过程中，要介绍一下计算机之父 A.M.Turing，及等价于计算机 界的 NOBEL 奖地位的“图灵奖”得主中，于 2000 年获得图灵奖的华人姚期 智教授，计算理论包括伪随机数生成、密码学与通信复杂度的突出贡献，美 国计算机协会（ACM）把 2000 年度的图灵奖授予他。姚期智是图灵奖创立 以来首位获奖的亚裔学者，也是迄今为止获此殊荣的唯一华裔计算机科学家。 姚期智教授放弃了自己在美国优厚的工作待遇，甚至是不惜变卖自己在美国 的房产回国，充分展现了中华学子的爱国情怀！同时强调：姚期智教授在计 算理论中所做出的突出贡献，充实和完善了 NP 完全理论的知识体系。 3. 问题与知识要点 问题及其分类，问题的难度与时间复杂性关系、NP 类问题的证明 第二节 NP 完全问题与 NP-hard 问题 1．主要内容