文档介绍：姓名:萨力
教育经历:1993-,本科毕业;-,获博士学位;主要研究方向为专家系统、人工生命。
1
科研情况: 读博期间参加中科院知识创新工程“基于人工生命技术的知识发现及其农业应用研究”、“基于涌现计算的生态系统建模及应用”等项目的研究及多项国家重点科研项目的申请、答辩工作,2005年7月进入上海大学控制科学与工程博士后流动站,研究方向为P2P计算、基于主体的复杂系统建模。
2
业余爱好:篮球,围棋,古典吉他。
E-mail: ******@
电话:**********
3
主要内容介绍
第1章 算法引论
第2章 递归与分治策略
第3章 动态规划
第4章 贪心算法
第5章 回溯法
第6章 分支限界法
4
主要内容介绍(续)
第7章 概率算法
第8章 NP完全性理论
第9章 近似算法
第10章 算法优化策略
5
第1章算法引论
算法与程序
表达算法的抽象机制
描述算法
算法复杂性分析
本章主要知识点:
6
算法与程序
输入:有零个或多个外部量作为算法的输入。
输出:算法产生至少一个量作为输出。
确定性:组成算法的每条指令清晰、无歧义。
有限性:算法中每条指令的执行次数有限,执行每条指令的时间也有限。
是算法用某种程序设计语言的具体实现。
程序可以不满足算法的性质(4)即有限性。
是满足下述性质的指令序列。
算法:
程序:
7
表达算法的抽象机制
高级程序设计语言的主要好处是:
(4)把繁杂琐碎的事务交给编译程序,所以自动化程度高,开发周期短,程序员可以集中时间和精力从事更重要的创造性劳动,提高程序质量。
(1)高级语言更接近算法语言,易学、易掌握,一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作;
(2)高级语言为程序员提供了结构化程序设计的环境和工具,使得设计出来的程序可读性好,可维护性强,可靠性高;
(3)高级语言不依赖于机器语言,与具体的计算机硬件关系不大,因而所写出来的程序可植性好、重用率高;
8
表达算法的抽象机制
抽象数据类型是算法的一个数据模型连同定义在该模型上
并作为算法构件的一组运算。
抽象数据类型带给算法设计的好处有:
(1)算法顶层设计与底层实现分离;
(2)算法设计与数据结构设计隔开,允许数据结构自由选择;
(3)数据模型和该模型上的运算统一在ADT中,便于空间和时间耗费的折衷;
(4)用抽象数据类型表述的算法具有很好的可维护性;
(5)算法自然呈现模块化;
(6)为自顶向下逐步求精和模块化提供有效途径和工具;
(7)算法结构清晰,层次分明,便于算法正确性的证明和复杂性的分析。
9
在本书中,采用Java语言描述算法。
描述算法
以下,对Java语言的若干重要特性作简要概述。
(1)Java程序的两种类型:应用程序和applet
区别:应用程序的主方法为main,其可在命令行中用命令
语句 java 应用程序名来执行;
applet的主方法为init,其必须嵌入HTML文件,由
Web浏览器或applet阅读器来执行。
(2)包:java程序和类可以包(packages)的形式组织管理。
(3)import语句:在java程序中可用import语句加载所需的包。
例如,import .*;。
10