电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

算法1_算法求解基础_大校

52页
  • 卖家[上传人]:壹****1
  • 文档编号:26280880
  • 上传时间:2017-12-24
  • 文档格式:PPT
  • 文档大小:530.50KB
  • / 52 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、算法设计与分析,张怡婷Email:Phone:13951927531,课前简介,课程学时:48学时(40+8)平时成绩考核办法:点名作业实验报告考试时间、方式19周(之前),闭卷答疑时间、地点周五上午第2小节,教2-316,学习要求:预习动手实现上课认真听讲,在书上作适当的标记和注释课后复习,随堂提问课堂练习学习报告,算法与数据结构的关系,算法是数据结构的灵魂:不了解施加于数据上的算法就无法决定如何构造数据。反之,数据结构又是算法的基础:算法的结构和选择又常常在很大程度上依赖于数据结构。,算法+数据结构=程序,学习算法不外乎两个目的:一是了解各种算法,在遇到问题时能灵活的应用所掌握的方法技巧;二是研究算法设计技术,当没有现成可用的算法时,能够创造出问题的求解方法。,算法怎么学?,前者很实际,后者很重要。,课程学习目标,Learning to solve real problems that arise frequently in computer application学习计算机应用中求解实际问题的有效算法Learning the basic principles and techni

      2、ques used for answering the question: “How good, or, how bad is the algorithm”学习评价算法好/坏的基本原理和技巧Getting to know a group of “very difficult problems” categorized as “NP-Complete”学习NP-Complete问题的相关理论和算法,课程主要章节内容:Ch1 算法问题求解基础Ch2 算法分析基础(算法复杂度概念)算法设计策略、算法分析和证明Ch5 分治法Ch6 贪心法Ch7 动态规划法Ch8 回溯法Ch9 分枝限界法Ch10 NP完全问题Ch13 密码算法,课程内容,课程参考书,ClassicsDonald E.Knuth. The Art of Computer ProgrammingVol.1 Fundamental Algorithms基本算法Vol.2 Seminumerical Algorithms半数字化算法Vol.3 Sorting and Searching排序与搜索Popular textbooksTho

      3、mas H.Cormen, etc. Introduction to AlgorithmsAlfred V.Aho,John E.Hopcroft,Jeffrey D.Ullman. The Design and Analysis of Computer AlgorithmsUdi Manber. Introduction to Algorithms-A Creative ApproachRobert Sedgewick. Algorithms in C/C+/Java(with different versions using different programming languages)Advanced mathematical techniquesGraham, Knuth, etc. Concrete Mathematics: A Foundation for Computer Science具体数学(连续数学+离散数学),其他参考书1 王晓东.计算机算法设计与分析.电子工业出版社,2001.2 Jon Bentley著,黄倩,钱丽艳译,编程珠玑(第2版).人民邮电出版社,2

      4、008. 3 卢开澄,计算机算法导引设计与分析.清华大学出版社,1996.4 Jon Kleinberg, Eva Tardos著,张立昂,屈婉玲 译,算法设计.清华大学出版社,2007.网上学习资料MIT OpenCourseWare | Electrical Engineering and Computer Science(MIT开放式课件 | 电气工程与计算机科学)http:/ http:/,上机安排,上机时间和地点分治策略第7周周五(4月 4日) 第1大节( 8:00- 9:35)动态规划法第11周周五(5 月 2 日) 第1大节( 8:00- 9:35)回溯法第13周周五(5月 16日) 第1大节( 8:00- 9:35)密码算法第14周周五(5月 23 日) 第1大节( 8:00- 9:35)地点:教2-316(软件与信息安全实验室)先修课程: 高级语言程序设计、面向对象程序设计、数据结构,第1章 算法问题求解基础,学习要点:理解算法的概念。理解什么是程序,程序与算法的区别和内在联系。章节内容:1.1 算法概述1.3 算法设计与分析,An Arabian mathemati

      5、cian AbAbud Allh Muhammad ibn Ms al-Khwrizm (c.780-c.850?) wrote the famous “Persian text-book” titled Kitb al-jabr wal-muqbala”,Algebra,Algorism,Algorithm,Algorithm的由来,Arithmetic,1.1 算法概述,An algorithm is a precise description of the process of solving a problem, consisting of finite number of instructions which can be executed mechanically and produce a deterministic result.算法是对某个问题求解方案的完整而明确的描述,是指令的有限序列。Five important features(五个重要特征):Finiteness有穷性(算法必须总能在执行有限步之后终止)Definiteness确定性(组成算法的每一条指令都是

      6、清晰,无歧义的)Input输入(算法有零个或多个外部提供的输入量)Output输出(算法至少产生一个输出量)Effectiveness可行性(算法的每一条指令必须足够基本,能够通过已经实现的基本运算执行有限次来实现),算法与程序,程序(Program)是算法用某种程序设计语言的具体实现。算法必须可终止,程序却没有这一限制。即:程序可以不满足算法的性质(5)“有穷性”。例如:操作系统是一个在无限循环中执行的程序,却不是算法。因此操作系统是使用计算机语言描述的一个计算过程,而不是一个算法。,算法描述,描述一个算法可以用自然语言、流程图、伪代码和程序设计语言。,经典算法举例,欧几里德算法(辗转相除法):求两整数m和n的最大公约数(0mn) Swap(m,n);return RGcd(m,n);,程序1-1 欧几里德算法(递归)void Swap(int ,程序1-2 欧几里德算法(迭代)void Swap(int ,程序设计语言描述(迭代):,可见:一个问题可以设计不同的算法来求解。同一个算法可采用不同的形式来表示。,程序1-3 连续整数检测int Gcd(int m,int n)if (m

      7、=0) return n;if (n=0) return m;int t=mn?n:m;while (m%t|n%t) t-;return t;,程序设计语言描述(连续整数检测):,小思考,若不事先比较m和n的大小,如何实现欧几里德算法?,int Gcd(int m,int n) while (m!=0 ,程序是否一定会在有限步之内终止?,小思考,m*n /Gcd(m,n),如何求最小公倍数?,算法的重要性( Algorithm Everywhere ),ApplicationsHuman Genome Project: identifying 100000 genes in human DNA, determining the sequences of the 3 billion chemical base pairs that make up human DNA, storing this information in databases, and developing tools for data analysis. (卡普Karp -华盛顿)Internet service:

      8、e.g. routing the dataElectronic commerce: public-key cryptography and digital signaturesSystemsHardwareOperating systemsCompilers(克努特Knuth-LR(k)文法),假设某一负责人交给你一个很难的任务,几天后询问你问题解决了没有。可能会发生如下图这样的情况:,问:“交给你的问题,解决方案设计出来了吗?”答:“我找不到一个有效的算法来解决它,没能完成任务。”,问:“交给你的问题,解决方案设计出来了吗?”答: “我找不到一个有效的算法来解决它,因为这样的算法是不存在的。”,不过,要证明一个问题不存在有效算法,往往跟寻找有效算法一样难。,问:“交给你的问题,解决方案设计出来了吗?”答: “我找不到一个有效的算法来解决它,但不是我不行,因为所有这些名人也都找不到解决它的有效算法。”,Philosophy of Problem Solving,To distinguish between the two classes, we use our wit.,算法与图灵奖超过1/3的Turing奖获奖者其成果与算法有关,1974 - Donald Knuth(Stanford): “The Art of Computer Programming”1976 - Michael Rabin(Hebrew) & Dana Scott(Oxford): Nondeterministic Finite State Automata (NDFSA)1982 - Stephen Cook(Toronto): Satisfiability of Proposition Calculus is NP-complete1985 - Richard Karp(UC Berkley): Branch-and-Bound Method1986 - John Hopcroft(Cornell) & Robert Tarjan (Princeton): Graph algorithms,

      《算法1_算法求解基础_大校》由会员壹****1分享,可在线阅读,更多相关《算法1_算法求解基础_大校》请在金锄头文库上搜索。

      点击阅读更多内容
    最新标签
    发车时刻表 长途客运 入党志愿书填写模板精品 庆祝建党101周年多体裁诗歌朗诵素材汇编10篇唯一微庆祝 智能家居系统本科论文 心得感悟 雁楠中学 20230513224122 2022 公安主题党日 部编版四年级第三单元综合性学习课件 机关事务中心2022年全面依法治区工作总结及来年工作安排 入党积极分子自我推荐 世界水日ppt 关于构建更高水平的全民健身公共服务体系的意见 空气单元分析 哈里德课件 2022年乡村振兴驻村工作计划 空气教材分析 五年级下册科学教材分析 退役军人事务局季度工作总结 集装箱房合同 2021年财务报表 2022年继续教育公需课 2022年公需课 2022年日历每月一张 名词性从句在写作中的应用 局域网技术与局域网组建 施工网格 薪资体系 运维实施方案 硫酸安全技术 柔韧训练 既有居住建筑节能改造技术规程 建筑工地疫情防控 大型工程技术风险 磷酸二氢钾 2022年小学三年级语文下册教学总结例文 少儿美术-小花 2022年环保倡议书模板六篇 2022年监理辞职报告精选 2022年畅想未来记叙文精品 企业信息化建设与管理课程实验指导书范本 草房子读后感-第1篇 小数乘整数教学PPT课件人教版五年级数学上册 2022年教师个人工作计划范本-工作计划 国学小名士经典诵读电视大赛观后感诵读经典传承美德 医疗质量管理制度 2 2022年小学体育教师学期工作总结 2022年家长会心得体会集合15篇
     
    收藏店铺
    关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
    手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
    ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.