《算法设计与分析》- 第 1 章 概述

算法设计与分析授课教师：刘伟电话件：bme_liuwei@163.comQQ：1071271580办公室：长安校区东区FZ145室授课教师简介工学博士，副教授，硕士生导师。长期从事智能图像处理和医学影像计算机辅助诊断方面的算法研究、设计和应用软件开发工作。主持和参与了多项国家、省部级及企业科研项目，发表了多篇学术论文，授权了多项发明专利和软件著作权。欢迎对我的研究方向感兴趣的同学参与我的科研工作，报考我的硕士研究生。课程简介I.为什么要学习《算法设计与分析》？II.怎样学好《算法设计与分析》？课程简介为什么要学习《算法设计与分析》？◆写程序的基础◆分析和解决问题的方法◆大数据时代下软件的效率要求◆找工作的需要课程简介写程序的基础程序=算法

+数据结构●编写计算从吴家坟到西邮长安校区最短公交路线程序●编写分析校园一卡通数据得到同学消费习惯的程序●编写“贪吃蛇”游戏程序●编写“美颜相机”程序●……课程简介分析和解决问题的方法算法分析与设计课程讲授了一些分析和解决问题的策略和方法。这些策略和方法可以解决一些表面上看起来难以下手的问题。课程简介“编辑距离”问题编辑距离，又称Levenshtein距离，由俄罗斯科学家VladimirLevenshtein在1965年提出。是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。设A和B是2个字符串，允许的字符操作包括：（1）添加一个字符；（2）删除一个字符；（3）修改一个字符。要用最少的字符操作将字符串A转换为字符串B。课程简介例如将kitten转换成sitting，可以采用如下3个步骤完成：sitten（k→s）sittin（e→i）sitting（→g）//添加字符将字符串A和B的之间的编辑距离记为d(A,B)。试设计一个有效算法，对任意给定的2个字符串A和B，计算它们之间的编辑距离。在一些有关文字处理的应用中会遇到编辑距离问题。课程简介如何求解“编辑距离”问题？有同学可能想到采用“穷举法”这种直观的方法求解问题。字符串内容千变万化，将字符串A变为字符串B可能有很多种途径，穷举法会导致算法运行时间长，不是一个好方法。可以采用“动态规划”算法高效地解决该问题（在后续课程中将详细讲解该方法）。课程简介深入的算法：智能图像处理问题–文字识别香积寺：中国“佛教八宗”之一“净土宗”祖庭，全国重点文物保护单位，位于陕西省西安市长安区郭杜镇香积寺村（摘自百度百科）。课程简介智能图像处理问题–文字识别课程简介智能图像处理问题–文字识别智能图像处理算法可以解决该问题。课程简介大数据时代下软件的效率要求●

大数据时代●Netflix公司采用大数据技术拍摄的流行美剧“纸牌屋”●

在“大数据时代”如果没有高效的算法则无法实时处理海量数据课程简介Facebookstatistics:60+billionphotostotal(about1.5PB),220,000,000newphotoseachweek(about25TB),550,000photosprocessedpersecondduringthepeakhours.大数据课程简介不同的算法带来不同的效率：一个简单实验在同样的硬件环境下采用“快速排序法”和“选择排序法”排序不同数量实数所需时间的比较实验结果（分别排序1000,2000,5000,10000,20000,30000,40000,50000,60000,100000个数据）。课程简介大数据时代对的算法（运行正确的算法）是不够的，更需要好的算法（高效算法）！课程简介国内外的互联网公司（谷歌、百度、阿里、腾讯、京东等）每时每刻都会产生海量数据，涵盖了人们日常生活的方方面面。分析这些数据特别需要高效率的算法。课程简介举例：“位”技术的应用（大数据时代下的海量数据处理）给

40亿个不重复的unsignedint的整数，且没有排过序。然后再给一个数，如何快速判断这个数是否在那40亿个数当中？（比如QQ号的判定……）课程简介【分析】显然用内存中储存这40亿个数是不现实的，因为需要40*4=160亿字节（假定是32位机器），大约是14.90GB的内存空间。可以采用“位”技术解决这个问题。因为2^32-1=4294967295，约43亿。所以对于unsignedint类型的数而言，可以表达40亿个不同的数字。课程简介unsignedint的取值范围是0到2^32–1，可以申请连续的2^32/8=512M的内存，然后用每一个bit对应一个unsignedint数字。首先将512M内存都初始化为0，然后每处理一个数字就将其对应的bit设置为1。

当需要查询时，直接找到对应bit，看其值是0还是1即可。这样需要的内存量从14.90GB下降到512MB。而且处理算法也非常便捷。课程简介“位”技术实际应用：PET地址编码PET设备–用于癌症的早期检测某公司致力于PET设备的国产化，开发与PET设备配套的图像重建软件时需要处理硬件设备编码。该设备中二维人体编码的最大地址为795971583，如果要采用整数全部读入内存的方式，则需要申请795971583*4=3183886332字节=3109264KB=3036MB=2.97GB内存！无法实现！（程序一运行就会因为内存不够而崩溃！）课程简介为此采用了上述的“位”技术，因为程序中处理数据分离时只是看给定的某个编码地址是否在特定的表中，是一个查表的过程。所以针对每个连续地址内存中用1个bit（0或1）来表示其是否在符合编码地址体系中。程序中计数时采用了Hash表以加快查找速度。这样一来，上述问题中仅仅需要申请795971583/8=99496448字节=95MB

内存空间即可。圆满地解决了问题！课程简介找工作的需要国内外IT公司无论大小（如百度、腾讯、阿里等）在招聘时的很多面试题目都是算法题。进入公司实习或工作时，从事研发的同学和算法打交道的可能性是相当高的。可以说老师教好，同学学好算法课对帮助同学就业也有一定的积极意义。课程简介实例：美团网数据挖掘面试题：“二维平面上求n个点中距离最近的两个点”。【分析】本题为“最接近点对问题”，这是一个经典问题，具有实用价值。其内容为：给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。满足上述条件的点对可能有多个，为简便起见，假定只找其中的一对。课程简介直接解法：依次计算每一点和其他n–1个点之间的距离，定义距离矩阵为Ad

：课程简介课程简介显然，随着点数n的增加，计算量急剧增加。所以直接解法不是一个好方法。可以采用“递归与分治策略”算法解决该问题（在后续课程中将详细讲解该方法）。课程简介怎样学好《算法设计与分析》？（如何做题目？有些题目的思路是怎么想出来的？）●

先模仿、后创新●

学习经典例子和经典算法，不断积累●

勤学苦练持之以恒！课程简介本课程授课过程中会列举和实际应用紧密相关的算法实例，让同学们了解所学算法知识在实践中的应用。课程简介推荐的参考文献（下面的次序为推荐阅读的次序）（1）计算机程序设计艺术第3版（第一卷、第二卷、第三卷）DonaldE.Knuth的经典著作。《计算机程序设计艺术》三卷中文名为《基本算法》、《半数值算法》及《排序与查找》。（2）编程珠玑（3）编程之美课程简介推荐的参考文献（4）高质量C++/C编程指南，林锐（尽管不是一本专门讲解算法的书，但其中的很多思想有助于编写质量好的程序。虽然针对C/C++，但书中的很多思想对任何语言平台，如Java等，都是适用的）（5）代码之美课程简介程序=数据结构+算法

+开发平台算法：解决问题的一种方法或一个过程。课程简介问题1：编写程序计算S=1+2+…+N的值。算法：（1）输入N

的值；（2）S=0；（3）fork=1toN

doS=S+k；（4）输出S。课程简介问题2：编写程序实现“用图找图”。“用图找图”就是根据“图像”而非“关键字”从数据库中查找目标图像。这里的数据库可以是特定领域内的图像数据库，如各种数字艺术博物馆、工业产品数据库、天文数据库、军事数据库等；更为普遍的应用则是面向互联网这个海量的、日新月异的图像数据库。在科研和工程领域，有一个专门的方向研究“用图找图”，即“基于内容的图像检索–CBIR，Content-BasedImageRetrieval”。目前国内外大公司和科研机构对这一领域投入了大量资源用于研发。谷歌、微软、百度、阿里（淘宝）、雅虎等公司均有相应的产品上线。课程简介凤仙花课程简介课程简介谷歌搜索引擎中的“用图找图”功能。课程简介百度搜索引擎中的“用图找图”功能。课程简介在移动互联网时代，智能终端由于携带了丰富的传感器，如摄像头、GPS、重力感应器、电子罗盘等，可以随时随地获取周围的影像等视觉以及位置等信息。通过移动终端以及运行其上的强大应用，人们可以在现实世界与信息世界之间建立关联，从而便捷地获取全面的多媒体信息及服务，比如基于位置的多样化服务。课程简介基于移动互联网的“用图找图”技术，即移动视觉搜索技术极有可能会成为支撑未来移动互联网应用的基础技术之一。课程简介移动视觉搜索移动视觉搜索是指利用移动终端获取真实世界中对象的图像或视频并作为查询对象，通过移动互联网检索视觉对象关联信息的检索方式。也即将PC单机和互联网上的基于内容的图像或视频检索技术根据移动互联网的特点“移植”到移动互联网环境下。课程简介谷歌公司：GoogleGlass2012年谷歌推出了名为GoogleGlass的基于视觉搜索的可穿戴设备。课程简介谷歌公司：GoogleGlassGoogleGlass的意义在于提供了一种将真实的物理世界信息映射为互联网信息的方式。摄像头是移动互联网时代的入口，就像PC时代的搜索框一样。课程简介百度公司：百度移动视觉搜索书籍封面检索电影海报检索课程简介百度公司：百度实物翻译课程简介腾讯公司：微信5.0的“扫一扫”功能（封面、街景、翻译）课程简介国内创业公司：机会！北京贞观雨科技有限公司课程简介亮风台(上海)信息科技有限公司课程简介“用图找图”软件是一个复杂的程序，一般性的框架算法如下：框架算法：（1）计算图像库中图像的特征；（2）计算检索图像的特征；（3）特征匹配，用户交互式反馈；（4）输出最终检索结果。上述算法的每一个步骤都有更为细化的复杂步骤，即更为“细化”的算法。课程简介图像特征计算课程简介图像及其颜色特征课程简介程序设计中的“问题求解”过程无论是简单的问题还是复杂的问题，“问题求解”的过程都是一样的。课程简介要求用计算机解决的问题越来越复杂，对这类问题的算法进行设计与（复杂性）分析具有特别重要的意义。课程简介本课程主要介绍计算机算法分析和算法设计中的基本概念、基本算法分析方法和常用的算法设计方法。教材王晓东.计算机算法设计与分析（第4版）.北京：电子工业出版社，2012.参考文献（美）DonaldE.Knuth著，苏运霖译.ArtofComputerProgramming（计算机程序设计艺术）（第三版）.北京：国防工业出版社，2002.《编程之美》小组.编程之美:微软技术面试心得.北京：电子工业出版社，2008.授课计划考试及成绩计算书面闭卷考试平时成绩30%（点名、上机实验）

期末考试70%第1章算法概述教学内容和要求（1）算法的概念与性质（2）程序的概念；程序与算法的区别和内在联系（3）掌握算法的计算复杂性概念（4）掌握算法渐近复杂性的数学表述第1章算法概述算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：（1）输入：有外部提供的量作为算法的输入。（2）输出：算法产生至少一个量作为输出。（3）确定性：组成算法的每条指令是清晰，无歧义的。（4）有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。（5）可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现。第1章算法概述程序是算法用某种程序设计语言的具体实现。如一个Java程序和一个C语言程序可能做的是同一个事情，这两个语言表达的就是同一个算法。二者的不同：（1）算法是给人来读的，直接将算法输入计算机是不能运行的。（2）程序可以不满足算法的性质（4），即“有限性”。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。第1章算法概述算法复杂性

=算法所需要的计算机资源，所需资源多，算法的复杂性高；反之则复杂性低。算法的时