《算法设计技巧与分析》 第10章 NP完全问题 朱友文 zhuyw@nuaa.edu.cn.

Slides:



Advertisements
Similar presentations
第三节 纵膈常见疾病的 CT 表现 一、平片表现为纵膈普遍增宽的非肿瘤病变 纵膈炎 --- 纵膈肿胀,脂肪密度增高,气泡; 原因:炎症来自颈部、食管、术后; 纵膈血肿 --- 肿胀相对局限,出血密度; 原因:外伤、血管破裂; 纵膈气肿 --- 大量含气; 原因:气胸、食管; 纵膈脂肪沉着 ---
Advertisements

天然 養生 樂活 年貨集錦 田森館 - 艾草之家. ‧環保健康生活小常識 : 日常使用的家中日用品,包含各種各樣的化學物質,這些化學物質,有些頗具 毒性,有些雖然沒有急毒性,但暴露日久卻會造成慢性中毒,導致健康受損, 甚至致命。 環境荷爾蒙會影響人類或其他生物的生殖能力與發育,其中一類的「壬基酚 (
义务教育课程标准实验教科书人教版七年级上册第 24 课 《散文诗两首》之 —— 荷叶 母亲 宁夏彭阳县王洼中学 庞鸿渊 冰 心冰 心.
F 15.1 股票指数的功能 F 15.2 股票指数的分类 F 15.3 股票指数的编制 F 15.4 如何编制不同功能的股票指数 F 15.4 中外主要股票指数.
问题 1 :如图,某人由入口 A 进入,顺着道路走到出口 B ,共有几种不同的行走路线 A 桥 B 分析:要从入口 A 走到出口 B ,需要两个步骤 第一步 ; 从入口 A 走到桥上,有两条路线 。 第二步 ; 从桥上走到出口 B 有三条路线 。 结论:从入口 A 走到出口 B 共有 2×3 种不同的行走路线.
落 枕. 疼痛 颈部 活动 不利 概述 以单纯性颈项强痛, 活动受限为主症的病证。 特点: 1 、常为急性起病。 2 、一年四季均可发生。 3 、多见于成年人, 儿童罹患极少。
第六章 血液系统疾病病人的护理. 第一节 血液系统疾病 常见症状和体征的护理 一、贫血 贫血是血液系统最常见的症状 【护理评估】 (一)病史 贫血发生的速度、贫血的程度 (二)身体评估 评估主要体征,包括皮肤 甲床、粘膜是否苍白、血压的改变、肝 脾淋巴结是否肿大等。 (三)心理 - 社会资料 (四)辅助检查.
深圳市快易典电子技术有限公司市场部培训组 2009 年 6 月 —— 随心随意,玩 “ 转 ” 学习.
港股通业务方案. 交易货币 VsVs 沪市交易货币以人民币为主,港市交易货币以港币为主。 交易时段 9:00 9:15 9:30 12:00 13:00 9:15-9:25 开盘集合竞价 15:00 16:00 9:30-11:30 连续竞价 13 : 00-15:00 连续竞价 9:00-9:30.
常見傳染病 ( 結核病 ). 何謂結核病 ? 與 常見的結核病有哪些 ? 結核病是感染結核菌所引起的一種傳染病。 當結核菌侵入人體可在任何器官引起病變,故 可分為肺結核與肺外結核。 肺外結核 : 如結合性腦膜炎、脊椎結核、腎結 核 、骨結核、腸結核 … 等。 因結核菌在繁殖時需要氧氣,大多在肺內,尤.
1  超静定次数的确定及力法基本概念 超静定次数的确定及力法基本概念  超静定梁、刚架和排架 超静定梁、刚架和排架  超静定桁架、组合结构和拱 超静定桁架、组合结构拱  对称结构的计算 对称结构的计算  支座移动和温度改变时的力法计算 支座移动和温度改变时的力法计算  超静定结构的位移计算和计算校核.
第二章 中药药性理论的现代研究 掌握中药四性的现代研究 掌握中药五味的现代研究 掌握中药毒性的现代研究 了解中药归经的现代研究.
第四节 细胞中的糖类和脂质 沫若中学 刘建英.
第一节 概述 第二节 高速公路收费方式及种类 第三节 收费标准的分析 第四节 高速公路收费日常管理 第五节 高速公路收费管理现代化
第三部分 木薯淀粉 木薯是世界七大作物之一,与马铃薯、红薯并列为世界三大薯类作物。木薯的主要用途是食用、饲用和在工业上开发利用,世界上木薯全部产量的65%用于人类食物,工业上木薯主要用于提取淀粉,可制浆料、酒精、果糖、葡萄糖、味精、塑料纤维、塑料薄膜、涂料和胶粘剂等。世界木薯制品的主要贸易国集中在亚洲和西欧地区,排名前五位的国家和地区分别是中国、韩国、荷兰、西班牙和比利时。
參與除權(息)是否能獲利— 以台灣125家上市公司為例
總務處報告.
輻射警示標誌 圖底為黃色,三葉形為紫紅色.
2007金坛房地产市场调研报告.
知识点一 第五章 理解·教材新知 知识点二 知识点三 把握·命题热点 命题点一 命题点二 课堂回扣练习 应用·落实体验 课下综合检测.
微生物饲料添加剂 河南省恒隆态生物技术研究所 主讲:陈红坤.
单纯性肥胖 概 述 肥胖是一种身体内脂肪过度蓄积 以致威胁健康的慢性疾病。世界卫生 组织已于1999年正式宣布肥胖是一种 疾病。肥胖现已成为全球性的流行病。 危害 易患冠心病、高血压、中风、糖尿病、胆囊炎、阑尾炎、骨关节炎、高血脂、便秘、痛风、下肢静脉曲张,甚至还会影响性功能,导致阳痿、月经不调、闭经或不孕症等,严重影响人们的身体健康。
精品课程 国际贸易实务.
认识常见的寄生虫和病原微生物 浙江省疾病预防控制中心 传防所.
离散随机变量及分布律 定义 个或可列个, 则称 X 为离散型随机变量 描述X 的概率特性常用概率分布或分布律 即 X 或 P §2.2
第四节 1.了解现代汉语各类短语的特点及作用 2.掌握层次分析法的三个原则
第一篇 总 论 第二篇 普外科 外科护理学 吉林大学远程教育学院.
七堵調車場與台鐵平溪線.
分泌性中耳炎 Secretory otitis media (SOM)
维格尔美容套餐 2000年推广执行提案 成都金鹰/APEX.IMC
专题3 植物组织培养技术.
台中市信義國小 六年10班 指導老師:自然科陳慧如老師 製作日期:100年10月1日~10月30日
常见内科疾病的眼底表现 北 京 友 谊 医 院 眼 科 高 立 新.
麻 风 病健 康 教 育 余庆县天湖小学刘秀峰.
第十三讲 法律方法专题.
病历 本硕042班 黎斐文
主 讲 教 师:付冬梅 北京科技大学信息工程学院自动化系
汽车起重机 安全规程 三一汽车起重机械有限公司.
学好考纲,提升能力 年考纲解读 林镜仁.
第一章 百度不能出现问题.
把握趋向 科学备考 漳州三中 沈丹燕.
麻风病 福建省疾病预防控制中心 武文斌 电话:
透视鱼粉贸易 如何把控农产品交易风险 海富特(中国)集团有限公司 ——陈红红 C.E.O.
贵宾专享 金融服务方案 邓慧景.
傅里叶变换的性质 对偶性 则: 若 f (t) 是偶函数, f (t) R(),则 R (t) 2 f (),
政府採購契約範本 主講人:柯慶昆.
瘿 病 中医内科教研室 洪军.
新人教版七年级数学上册第二章第一节 2.1整式(第一课时) ——用含字母的式子表示数量关系.
第七章 单总体假设检验.
灾情巡视问题 陆荻 韩向前 吕慧洁 素材天下 sucaitianxia.com-ppt193.
家政報告 ~泰式摩摩喳喳&越式春捲~ 九年十班第三小組.
闪电定位仪原理介绍和日常维护 安徽省气象技术装备中心 技术保障科.
鞍结节脑膜瘤 2013级影像 吴志斌.
制冷与低温技术原理 (四) 多媒体教学课件 李文科 制作.
變壓器和高壓輸電 危險!高壓電力! 互感現象 變壓器的原理 進度評估 4 電壓比 變壓器的電流
SAT问题.
导热系数的测量 兰州理工大学物理实验中心.
國產建材實業股份有限公司 簡報資料 2018年11月21日.
启辰国庆嘉年华暨T90媒体品鉴会 活动方案 启辰重庆东风南方渝达专营店 2016年9月28日.
1.為什麼要辦? 2.開辦好處 3.每月該繳多少錢? 4.國民年金計算公式 5.結論 6.資料來源
國民年金 np97006.
第4章 密码学的计算复杂性理论基础.
第九章 正規形式與邏輯設計.
孔融《与曹操论盛孝章书》.
第四章 随机变量的数字特征 关键词: 数学期望 方差 协方差、相关系数 其它数字特征.
第二章 遺傳 2‧2 基因與遺傳.
初二物理 1.4测量平均速度.
控制系统设计举例 戴连奎 浙江大学控制学院 2017/04/20.
近似算法 东南大学计算机学院 方效林.
第十二章 机械波 4、波的反射和折射.
Presentation transcript:

《算法设计技巧与分析》 第10章 NP完全问题 朱友文 zhuyw@nuaa.edu.cn

10.1 引言 判定问题与最优化问题 判定问题 最优化问题 2019/5/29 南京航空航天大学 计算机学院

10.2 P类问题 P类问题:对于判定问题Π,如果存在确定性算法A,且A可以在多项式时间内对问题Π进行判定或者求解。 2019/5/29 南京航空航天大学 计算机学院

10.3 NP类问题 NP类问题:对于判定问题Π,如果存在确定性算法A,且A可以在多项式时间内指出某个答案是否是问题Π的解。 2019/5/29 南京航空航天大学 计算机学院

10.4 NP完全问题 归约: TT T x T(x) 解 2019/5/29 南京航空航天大学 计算机学院

10.4 NP完全问题 NP完全问题 如果问题Π是NP问题 如果能够在多项式时间内求解问题Π ,那么就可以在多项式时间内求解任何一个NP问题 2019/5/29 南京航空航天大学 计算机学院

10.4 NP完全问题 NP完全问题 如果可以找到一个多项式时间的算法A求解某个NP完全问题Π,那么所有的NP问题就可以在多项式时间内求解,也就是说 NP=P 这是个机会? 2019/5/29 南京航空航天大学 计算机学院

10.4 NP完全问题 NP完全问题:举例 合取范式(CNF)可满足问题 哈密顿回路问题 顶点覆盖问题 2019/5/29 南京航空航天大学 计算机学院

10.4 NP完全问题 如何证明一个问题X是NP完全问题? 证明X是NP问题 证明存在一个已知的NP完全问题Y可以归约到X 2019/5/29 南京航空航天大学 计算机学院