关于复杂性理论的一点探讨 孙广中 sungz@mail.ustc.edu.cn.

Slides:



Advertisements
Similar presentations
义务教育课程标准实验教科书人教版七年级上册第 24 课 《散文诗两首》之 —— 荷叶 母亲 宁夏彭阳县王洼中学 庞鸿渊 冰 心冰 心.
Advertisements

F 15.1 股票指数的功能 F 15.2 股票指数的分类 F 15.3 股票指数的编制 F 15.4 如何编制不同功能的股票指数 F 15.4 中外主要股票指数.
行政院原住民族委員會 法規暨訴願審議委員會 102 年度原住民身分法實例演練講習: 原住民身分認定及救濟程序.
问题 1 :如图,某人由入口 A 进入,顺着道路走到出口 B ,共有几种不同的行走路线 A 桥 B 分析:要从入口 A 走到出口 B ,需要两个步骤 第一步 ; 从入口 A 走到桥上,有两条路线 。 第二步 ; 从桥上走到出口 B 有三条路线 。 结论:从入口 A 走到出口 B 共有 2×3 种不同的行走路线.
本校自民國 78 年於顏前校長世錫任內創設本系 設立鑑識科學學系大學部,專責鑑識人才之培養, 為目前國內唯一專門培育鑑識科學人才、研究鑑識 科學學術之大學學系,設系剛滿 20 年。自 85 年於姚 前校長高橋任內,設立鑑識科學研究所招收碩士生 ,民國 88 年於謝前校長瑞智任內先後獲內政部、教.
第二节 基因在亲子代间的传递. 1. 什么叫做遗传? 2. 什么叫做性状? 3. 性状是由什么决定的?
第二章:生物科學與食品 第三節:基因改造食品.
無性生殖是由親代直接產生新的個體,並不涉及配子的生成與結合。
第四节 细胞中的糖类和脂质 沫若中学 刘建英.
當我已老 謹以此文獻給像我一樣流浪在外的子女們.
大學入學考試中心 九十六學度學科能力測驗試題 國文科 -哈利波特番外篇-
第三章 现代教育与人的发展.
強制認領私生子首例 第十組組員:4970T012 劉柏宇 4970T013 黃偵泰 4970T035 陳建儒 4970T100 蔡維哲
2015年12月14日-2015年12月20日 缩略版.
指導老師:羅夏美 組別:第四組 組員: 車輛二甲 蔡中銘 車輛三甲 莊鵬彥 國企二甲 陳于甄 國企二甲 詹雯晴 資傳二乙 林怡芳
基因工程及转基因生物.
自然的食物就是你最好的醫生 上課之前先聽一首歌~稻香 歌詞、音樂還不錯和大家分享一下
第21课时 生物圈中的微生物 考 点 聚 焦 专 项 突 破 1.
國民中學 自然與生活科技 第二冊 第3章 生殖 3-1 細胞分裂 3-2 無性生殖 3-3 有性生殖.
怎樣吃才健康? 賴亭竹.
南通市卫生监督所副主任医师 南京医科大学副教授 施 飞
培养好的心智与理想 拥有丰富的专业理论知识与实践能力 锻炼强健的身体
第2章 基因和染色体的关系 第1节 减数分裂和受精作用.
胫腓骨骨折.
愛的書庫 智慧循環 愛與分享 謝志誠 財團法人九二一震災重建基金會
学校核心发展力 上海市建平中学 程红兵.
3.2 体外受精和早期胚胎培养.
第二单元(6-9课) 近代化的探索.
必修二 生物 (人教版).
想一想 议一议 P74 我们常吃的蘑菇有根、茎、叶吗? 它们的生长是否需要光? 为什么说它们是真菌而不是植物呢?
三次科技革命 学习目标: 1.知道三次科技革命的时间、标志、发源地、理论基础、主要成就、主要特点及影响。 2.培养归纳历史知识的能力
量子计算机 林晓菲
301——隆重登场.
課程:諮商概論 指導老師:李秀玉老師 閱讀書籍:傷癒—低估自我的醫治(一) (P.60~69)
新帝國主義開港 (一)臺灣成為侵略者目標 1.背景: A.買賣利豐=鴉片進口+米、糖、樟腦、煤炭出口 B.地理位置優越=航行安全+商貿中心 2.新帝國主義: A.19C中:英、法、美、日為主 B.臺被迫開港通商,割地賠款,簽訂不平等條約.
“网络问政”给九江新闻网 带来新的发展机遇 -- 九江新闻网 高立东 --.
佳力科技 防爆叉车的应用、发展 浙江佳力科技股份有限公司.
王永慶遺產分配 第三組民法報告 4970T011 劉昭妤 4970T037 吳品怡 4970T090 袁如意
台南在地美食文化介紹 台南市鳳凰城文史協會 理事長 歐財榮.
一、作者概說:    王壽來,民國三十八年生,山西省 五臺縣人,中興大學 法律系畢業,美國 喬治城大學碩士、臺灣師範大學 美術研究所碩博士。長期從事文化與外交工作,現任文建會 文化資產總管理處籌備處主任。   王壽來靈感多取自生活經驗,善用中外名言,描繪人生百態。著有《公務員快意人生》、《藝術‧收藏‧我》、《公務員DNA》、《和世界偉人面對面》等書。
导入新课 波能绕过障碍物产生衍射。既然光也是一种波,为什么在日常生活中难以观察到光的衍射现象呢?.
高中生物学必修Ⅰ 分子与细胞 前 言.
烟花爆竹企业开复工 安 全 培 训参考课件 浏 阳 市 安 监 局.
常规免疫接种率 监测 免疫规划科 章梦然.
入托、入学儿童预防接种证查验 武平县疾病预防控制中心 林传贵
社会工作概论 个案工作 课程培训 深圳电大 赖小乐.
关注生物技术的 伦理问题.
复习专题 现代文阅读 (总论) 汕头市潮阳第四中学:陈钦发.
2015年高考历史质量分析报告 兰州市外国语高级中学 杨彩玲.
大 纲 一、备案系统数据迁移方案 二、备案系统过程数据处理方案 三、备案系统内存量数据核验方案 四、新备案系统信息真实性核验方案※
肝功能正常的小三阳注意事项.
突變 突變是指遺傳物質發生改變, 而影響到性狀的表現 例:白化症.
前言.
词类活用.
第七章 单总体假设检验.
本法所稱區域計畫,係指基於地理、人口、資源、經濟活動等相 互依賴及共同利益關係,而制定之區域發展計畫。
司法机关.
新 竹 縣 未 來 發 展 構 想 相.關.計.畫 休 閒 農 業 [ 執 行活動 ] 法 令 案 例 分 析.
生物五界的分類方式.
透视 从众消费 现象 冯敏 国贸132.
Interactive Proofs 姚鹏晖
人是由什么发育而来的? 一个受精卵.
Boolean circuits 姚鹏晖 助教: 刘明谋 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502
目次检索 打印 下载 文字摘录 更换背景 多窗口阅读.
1.為什麼要辦? 2.開辦好處 3.每月該繳多少錢? 4.國民年金計算公式 5.結論 6.資料來源
國民年金 np97006.
孔融《与曹操论盛孝章书》.
信用部財務專業人員初級研習班 台灣債券市場簡介
非同源染色体:不是同源染色体的两条染色体
证据运用 第八章 证据的运用 第一节 证据体系的结构及运用规则.
Presentation transcript:

关于复杂性理论的一点探讨 孙广中 sungz@mail.ustc.edu.cn

计算理论与计算复杂性理论 关于计算的形式描述 可计算与不可计算 计算复杂性的刻画 计算复杂性理论的应用 新的计算模型

算法的定义 为实现某个任务而构成的简单指令集 有穷的计算良过程 通过有限多次运算可以决定的过程 正确 直观,非形式

算法的定义 希尔伯特第十问题(1900) Alan Turing & Alonzo Church(1936) 算法:图灵机程序 设计一个算法来判断多项式是否有整数根 算法:通过有限多次运算可以决定的过程 Alan Turing & Alonzo Church(1936) 图灵机程序 算法:图灵机程序 形式化的,精确的

可计算与不可计算 停机问题 希尔伯特第十问题 软件验证

计算复杂性的刻画 P类(Polynomial) NP类(Nondeterministic Polynomial ) PSPACE类 IP类, RP类, … NP-完全理论

计算复杂性理论的应用 算法分析 近似算法的下界 随机算法

新的计算模型 DNA计算 量子计算 Richard Feynman 1982 David Deutsch 1985 A.C. Yao 1993 Peter Shor 1994 Grover L. K. 1996

复杂性理论 关于复杂的形式描述 可描述与不可描述 复杂性的刻画 复杂性理论的应用 新的模型

是否需要这方面的研究?

谢谢大家!