下载文档原格式
大学计算机-计算思维导论 1 第9讲怎样研究算法—遗传算法研究示例1、快速浏览---本讲视频都讲了什么?【视频9.1可求解与难求解问题】计算学科中计算的根本目的是设计算法让计算机替代人进行计算求解。
有些问题容易求解-计算量可接受，有些问题难以求解-计算量大，还有些问题是不能求解-根本没有算法来求解；什么是可求解问题、难求解问题和不能求解问题？难求解问题的关键又在哪里？计算学科中经常提及的P类问题和NP类问题又是什么呢，其关系是怎样的？--请看视频……。
【视频9.2遗传算法的缘起--生物学中的遗传与进化】遗传算法源自于生物学中的遗传与进化(优胜劣汰)思想，但怎样将其转换为计算学科的算法呢？你是否真的理解了遗传与进化呢？若你真的理解了，则你便能将这种思想以一种过程的形式展现出来，明确这种过程的每一步骤及其要做的事情，能够将生物/自然规律转换为一种过程，是类比该思想形成算法的重要方面，看视频是怎样通过过程示意来理解遗传与进化的… …。
【视频9.3计算学科的遗传算法】遗传算法应该是一把牛刀，是否理解了遗传算法，杀只鸡看看。
通过小规模问题的示例，能够将求解复杂问题的算法的计算过程展现出来，易于理解。
本段视频以一个“求解多项式函数的最小值”问题，从其解的表示，到可能解的产生，到最终解的获得，类比生物遗传与进化过程，展现了遗传算法的计算过程，展现了相关概念的含义，你看明白了吗……。
【视频9.4遗传算法为什么可以求解NPC问题】在理解了遗传算法基本计算过程的基础上，需要思考遗传算法为什么可以求解NPC问题，只有真正理解了为什么可以求解，才能在具体问题的求解算法设计中进行有针对性的设计。
遗传算法为什么可以求解NPC问题，一种思维脉络是：NPC类问题计算量大→降低计算量求近似解→随机产生可能解进行判断→同时随机产生多组解进行判断，… …。
请看视频是如何讲解的。
【视频9.5怎样用遗传算法求解具体的应用问题(I)—问题及其建模】遗传算法是一种算法框架，针对具体问题可设计具体的遗传算法。
计算机程序设计基础教师：文迪Email: wendi@清华大学电子工程系智能图文信息处理实验室回顾上节课内容1.指针的概念，声明和取值；2.使用指针操作基本数据（整型、浮点）；3.使用指针操作数组元素（一维、多维）；3使用指针操作数组元素（维多维）4.指针作为数组元素：指针的数组。
我们已经知道：指针可以作为其指向变量的代表。
这节课我们就继续学习这个特性所带来的好处。
第九章指针（二）1.指针作为函数参数和返回值2⏹指针作为函数参数和返回2.使用指针操作字符串3.使用指针操作指针：指向指值有什么用？⏹如何使用指针操作字符串？⏹什么是指向指针的指针？针的指针4.使用指针操作函数：指向函的针什么是指向指针的指针它有什么用？⏹什么是指向函数的指针？数的指针指针变量作为函数参数•指针变量可以作为函数参数，也可以作为函数返回值，实现函数与外部的数据传递。
d bl l i t double calc (int op,double * pOp1,calc (op, &a, b);函数调用double op2){&a...*O 1135pOp10x0031ae400x0031ae40*pOp1 = 1.35;3a1.35}1.void swap(int * pa, int *pb)示例：指针作为函数参数当我们希望某个函数2.{3.int tmp = *pa;4.*pa = *pb;参数的值可以在函数内被改写，可以：1) 5.*pb = tmp;6.})将该参数定义为指针类型；2) 在实际调用中将变量的地址传入；7.void main()8.{9int a =10b =2;3) 在函数中用取内容操作符“*”改写地址指向的内存值。
9. a = 10, b = 2;10.swap(&a, &b);11.cout << “a=” << a << “, b=” << b << endl;1212.}1.void swap(int & a, int & b)示例：引用作为函数参数2.{3.int tmp = a;4. a = b;用变量的引用作为函数参数可以达到同样的目的，但是，原理5. b = tmp;6.}和指针作为函数参数并不相同。
9.1 证明TIME(2n)=TIME(2n+1).证明：2n=O(2n+1)TIME(2n)TIME(2n+1).2n+1=O(2n)TIME(2n+1)TIME(2n).所以TIME(2n)=TIME(2n+1).9.2证明TIME(2n)TIME(22n)。
注：这里“”是严格包含。
证明：令f(n)=22n,则f(n)/logf(n)=22n/2n, 由时间层次定理有TIME(o(22n/2n))TIME(22n).又由于2n=o(22n/2n)，TIME(2n)TIME(o(22n/2n))，所以TIME(2n)TIME(22n).9.3 证明NTIME(n)PSPACE.证明：NTIME(n)NSPACE(n)SPACE(n2)SPACE(n3)PSPACE.9.6 证明若A P，则P A＝P。
证明：首先P P A。
这是因为不带谕示即可。
下面证明P A P。
任取A P，则存在多项式图灵机T判定A。
设B P A，则存在带语言A的谕示的多项式时间图灵机M A判定B。
如下构造不带谕示的图灵机D：D=“对于输入串w:1)在w上运行M A。
2)每当M A要在谕示带上写下某个字符串x，则在x上运行T，若T接受，则代替谕示回答x属于A，否则代替谕示回答x不属于A。
3)若M A接受，则接受；否则，拒绝。
”设M A的运行时间是n a，T的运行时间是n b。
谕示带上写下的字符串的长度不会超过n a，询问谕示带的次数也不会超过n a。
D的运行时间是n a (n a)b=n a+ab，所以A P。
9.7 给出带指数的正则表达式，产生如下在字母表{0,1}上的语言：a.所有长为500的字符串. (01)500。
b.所有长度不超过500的字符串.(01)500.c.所有不少于500的字符串. (01)500(01)*.d.所有长度不等于500的字符串. (01)499(01)501(01)*.e.所有恰好包含500个1的字符串. 0*(10*)500.f.所有包含至少500个1的字符串. (01)*(1(01)*)500.g.包含至多500个1的字符串. 0*((1)0*)500.h.所有长度不少于500并且在第500个位置上是0的字符串. (01)4990(01)*.i.所有包含两个0并且其间至少相隔500个符号的字符串。
