信息技术学科基础与前沿.doc

52信息技术学科基础与前沿 Foundation and Frontier of Information Technology 【课程性质】专业必修课程【课程学分】本课程共计3学分【教学目标】以深化教学改革、更新教育理念为先导，以培养专业基础扎实、适应性强的教师人才的培养要求为目标，以建设优秀教材为核心，以提高师资队伍素质和教学 方法为关键，努力把学科基础与发展前沿这门课程建设成为集科学性、先进性、教育性、整体性、有效性和示范性于一身的精品课程。【教学方式】网络教学【考核方式】本课程要进行期中和期末两次阶段测试，测试方式为实时在线测试。考核测试题包括思考讨论题、在线测试题和小组合作任务题等。思考讨论题将以专题为单 位，每个专题提供2-3个思考与讨论题。思考与讨论题有助于加深教育硕士研究生对课程内容的理解，有助于引导研究生运用所学理论思考和分析教育实践问题。 在线测试题将提供不少于4套测试题(期中和期末各2套)。阶段性在线测试旨在监控研究生的学习过程，促进研究生注重平时学习，同时检查研究生对课程基本内 容的掌握情况。小组合作研究题要提供3-5个的小组合作研究题供研究生选择。合作研究题应有助于引导研究生运用所学知识，通过相互合作，解决教育实际问 题。课程内容简介：在学科基础与发展前沿这门课程中，我们将从“可计算性”、“计算复杂性分析”、“物联网”、“云计算”、“神经网络”、“模式识别”、“数字图像处理”、“视频跟踪”、“智能算法”、“信息搜索”这十个专题来进行授课。【学习建议】一、结合自己的工作实际学习本课程 理论联系实际是我们学习任何知识的一条基本原则。所谓理论联系实际原则，就是在学习过程中，既要能够联系实际以掌握理论基础知识，又要能够运用 理论去分析和说明实际，达到观点和材料、理论和实际、学与用、知与行的辩证统一。理论联系实际原则的基本要求是：一要掌握理论，二要联系实际。单纯强调理 论固然不对，如果抛弃理论，单纯强调经验和实际也是不对的，关键是在两者的结合上下工夫。 二、在弄懂各专题逻辑结构的基础上掌握本课程的知识点 学习本课程，首先应该在各专题网络资源的指导下认真通读必读文献，弄懂知识的逻辑结构，然后再着重学习各个部分的内容，既突出重点，又覆盖全面，以收“事半功倍”之效。 三、掌握开放学习的策略和方法 开放学习是学习化社会中人们学习的主要形式。它与开放教育是一致的，它强调教育工作的出发点应以学习者为转移，无论是教学信息、资料、教学过 程、教学方法、教学媒体、教学管理等都应以学习者为中心。开放学习是相对于封闭学习而言的，远程开放学习则是开放学习系统的一个部分。 所谓开放学习的策略和方法，是指一个人在开放学习的新环境中，用以促进其获得知识或技能的内部的和外部的策略、方法、技巧的总和。在现代远程开 放学习的情境中，学习者最关键的是要学会怎样学习。学会学习是指：学习者要能把更多的时间(包括闲暇时间)用于积极学习，并能从学习中得到乐趣，喜欢学习 并希望能多学些；要发展向自己提供反馈的技能；知道在哪些方面已学好，哪些方面学得不太好，并懂得需要做些什么，以便改进学习；在遇到学科中特定而具体的 学习困难时，能熟练地从书本、电子邮件、朋友和教师那儿寻找答案与寻求帮助。开放学习的策略和方法主要包括以下5个方面： 1激发动机，确定学习目标 日新月异的现代信息社会带来了新的环境，不断地激励着人们要继续学习。人们为了适应社会的发展和自身的发展需求，也从内部自发地产生要不断学习 的需求，这样的需求产生学习的动机，学习动机是使个人趋向一定目标的内在动力，是隐藏在学习行为背后的内驱力。内驱力的大小与开放学习的成效密切相关。对 每个学习者来说其学习的动机都各不相同，不同的动机会产生不同的目标；同时，目标又对激发、维持学习动机起支配和调节作用。因此，一个人在学习之前，就应 该磨砺自己的学习动机，同时制定远大而具体的学习目标。 2分析自我，制定学习计划 确定了自己的学习目标以后，应拟定实现目标的计划，即如何充分利用新环境的一切资源，包括人、财、物、时空和教学信息等为开放学习服务。要拟定 自我计划，首先要进行自我分析，包括与自我相关的新环境的分析。如分析自己已有的认知水平，找出自己的长处、短处；分析与开放学习相关的物质环境和人际环 境；科学地运筹学习的时间与空间等。 3运用反馈，进行自我调节 在开放学习中，由于与教师接触少，在学习过程中要想取得成效，自我调节控制显得十分重要。开放学习的自我调节不仅与个人有关，而且还受所处的环 境和行为事件的影响。人、行为和环境三者之间相互影响又要靠反馈的信息产生作用。作为开放学习的学员，应善于寻找、运用学习过程中的反馈信息。开放学习中 的反馈信息有教师的辅导、教师批改的作业、平时练习、终结性考试和实践性操作等。由于是开放学习，这些反馈信息往往是难以获取而且时间较长，善于自我调节 者就要善于及时捕捉反馈信息，并运用它。 4寻求合作，协同学习 开放学习系统创造了个别化学习的环境，有利于民主化、个性化学习，但不能把个体学习封闭化。21世纪，要求懂知识，能操作，善合作，会生存的人 才，因此，要在开放学习中提倡合作学习精神。合作学习要求学习者在一定区域范围内根据不同合作的条件组成学习小组，在各自独立学习，获取教学信息之后，交 换学习心得、体会，互相提问，相互评价，以寻找协作之间的非线性的学习增长效益。事实证明，在开放学习中，有组织小组学习的学习者比没有组织学习小组的学 习者的平均学习成绩更高，学习效果更好。 5讲求实效，自我评价 开放学习不是敷衍、搪塞他人的被动学习。它是个体内在的自我的学习需求，因此，要求学习应有自我负责精神，要能增长知识，有改变个体行为的实际 作用。自我评价就是开放学习中自我发起的自我负责学习的主要手段之一。开放学习中的自我评价具有自我诊断、自我激励、自我调控和自我改进学习的功能。只有 在学习者对自己决定评价准则、学习目的，以及达到目的的程度等都认真地负起责任的时候，开放学习才会真正取得实效。 专题一 计算机科学基础【主要内容】1基础知识2可计算性3计算复杂性4求解NP问题的基本思路5进一步理解NP问题一、简介 本讲主要介绍可计算性与计算复杂性理论涉及到的最基本知识以及相关概念，集中在计算理论的可计算性与计算复杂性。计算机的基本能力和限制是什么？这个问题要回溯到20世纪30年代，那时数理逻辑学家们首先开始探究计算的含义。自那时起以来，技术进步极大地增强了我们的计算能力，并且把这个问题从理 论王国带进现实世界。在可计算性与计算复杂性中的每一个领域内，对这个问题作了不同的解释，并且答案随着解释的不同而各不相同。我们将分别介绍可计算性和 计算复杂性的相关知识。1. 可计算性理论对于计算机这门学科，他的最基本问题是要考虑研究对象是什么的问题，换言之，什么是可以计算的，什么是不可以计算的。这就引出了计算机科学领域的一个非常重要的概念：可计算性。 在21世纪前半叶，数学家们，如歌德尔(Kurt Gdel)、图灵(Alan Turing)及丘奇(Alonzo Church)，发现一些基本问题是不能用计算机解决的。确定一个数学命题是真是假就是一个例子。这项工作是数学家的生计。用计算机来解决似乎是天经地义 的，因为这是数学王国里的事。但是，没有计算机算法能够完成这项工作。关于计算机理论模型思想的发展是这一意义深远的结论的成果之一，它最终促使建造出实 际的计算机。可计算理论与复杂性理论是密切相关的。在复杂性理论中，目标是把问题分成容易的和困难的；而在可计算理论中，是把问题分成可解的和不可解的。2. 计算复杂性理论计算的问题是各种各样的，有的容易，有的困难。例如，排序是一个容易的问题，比如说需要按升序排列一张数表，即使一台小型计算机都相当快地处理100万个 数。与时间表问题比较一下，比如说要制定一所大学的课程表，课程表必须满足某些合理的限制，如不能有两个班在同一时间使用同一教室。时间表问题看来比排序 问题困难得多。如果有1000个班，即使是使用一台超级计算机，制定一份最好的课程表也可能需要若干世纪。是什么使某些问题很难计算，又使另一些问题容易 计算？这是复杂性理论的核心问题。值得注意的是，虽然在过去的二十多年里对它进行了深入细致的研究，但是我们仍然不知道它的答案。以后我们将探究这个迷人 的问题和它的一些分支。迄今为止，复杂性理论的一个重要成果是，发现了一个按照计算难度给问题分类的完美体系。它类似按照化学性质给元素分类的周期表。运 用这个体系，我们能够提出一种方法给出某些问题是难计算的证据，尽管还不能证明它们是难计算的。当你面对一个看来很难计算的问题时，有几种选择。首先，搞 清楚问题困难的原因，你可能会做某些变动，使问题变的容易解决。其次，你可能会求出问题的不那么完美的的解。在某些情况下，寻找问题的近似解相对容易一 些。第三，有些问题仅仅在最坏的情况下是困难的，而在绝大多数的时候是容易的。就应用而言，一个偶尔运行得很慢、而通常运行得很快的过程是能够令人满意 的。最后，你可以考虑其他类型的计算，如随机计算，它能够加速某些工作。受到复杂性理论直接影响的一个应用领域是密码技术，这是一个古老的研究领域。在绝 大多数的情况下，容易计算的问题比难计算的问题更可取，因为求解容易的问题的代价要小。密码技术与众不同，它特别需要难计算的问题，而不是容易计算的问 题。在不知道密钥或口令时，密码应该是很难破译的。复杂性理论给密码研究人员指出了寻找计算问题的方向，围绕这些问题已经设计出新的革命性的编码。二、可计算性与图灵机 1. 可计算函数 在这一节将引进整个讲义的最基本概念可计算函数。设P为一n元程序，则对每组输入值x1a1,x2=a2,xn=an都计算出一个值y，因此可使每一个程序P对应一个函数。不同的程序可对应于同一函数。设P是以x1,x2,xn为输入变量的n元程序，则将用jp(x1, x2, ,xn)表示程序P所对应的函数。具体如下：因此jp2(x1，x2)是无定义函数。上面两个程序是处处无定义的一元和二元函数。定义1 函数f (x1，x2，xn)被称为部分可计算的，若有一程序P使得jp (x1，x2，xn)= f (x1，x2，xn)这里等号“=”表示：或者两边都无定义，或者两边都有定义并且其值相同。定义2 函数f (x1，x2，xn)被称为全函数，若它对一切x1，x2，xn的值都有定义。定义3 函数f (x1，x2，xn)被称为可计算函数，若它是部分可计算的而且是全函数。可计算函数不只要求有计算它的程序，且要求永远有定义。可计算函数是部分可计算函数的特殊情形 图 2.12. 图灵机 现在开始研究一种新的计算装置Turing(图灵机)。Turing机和Post-Turing机类似，它有一个带和指针Turing和Post-Turing机一样有三个基本动作：1. 往带上输出符号2. 把指针右移一格；3. 把指针左移一格。每个Turing机都有自己的字母表和状态集：字母表S=S0，S1，S2，SK状态集Q=q1，q2，q3，qN在状态集中有一个特殊的状态叫做初始状态。我们假定q1为初始状态。Turing机的每步动作由所谓的四元组来确定。每个四元组完成一个基本动作并转入下一个状态。四元组有三类，具体如下：四元组中L和R是特殊符，它们区别于字母表中符号Si。四元组中前两个符号表示条件，第三个符号表示动作内容，第四个符号表示要转入的下一个状态。图灵用形式化方法成上述这种功地表述了计算这一过程的本质：所谓计算就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。 图灵机具有如下性质： 定义3 函数f(x1，x2，xn)是Turing部分可计算的。若有Turing机计算它。(而不是程序)定义4 函数f(x1，x2，xn)是Turing可计算的，若函数f(x1，x2，xn)是Turing部分可计算并且是全函数。由图灵机存在一个重要的论题： Church-Turing论题：凡是可计算的过程都可用图灵机实现； 换言之，图灵机的计算能力要强于目前任何一台计算机，计算机科学所处理的研究对象是：可以被图灵机实现的计算问题 三、计算复杂性与图灵机 1. P问题与NP问题 考虑计算复杂类中最常见的两类问题：P类和Np类问题，我们可以利用图灵机对P和NP问题进行划分： P类 确定性图灵机在多项式时间内可以判定的问题 NP问题： 在非确定型图灵机上多项式时间可解的问题 由上可知，P类包含于NP类中。 P与NP的另一种定义： 多项式时间算法，设某算法C的时间复杂度是，其中是问题规模，有，是多项式函数，则称C算法是多项式时间算法。即：时间复杂度函数是的算法 指数时间算法：时间复杂性函数不能表示成的算法（包括：非多项式函数，不是指数函数） P类问题有多项式时间算法解决的判定问题。 NP类问题对问题的一个猜想存在多项式时间算法来验证它的判定问题上一页 1 2 下一页 2. NP完全问题和NP难问题 NP完全问题：我们称一个问题q是NP完全的，那么q满足如下性质： o q是NP的 o 对于任意的一个NP问题q0，都可以在多项式的时间转换为等价的q问题 换言之，要证明一个问题是NP完全的，首先需要证明它至少是一个NP问题，再证明其中一个已知的NP完 全问题能约化到它。根据NP完全问题的定义可以看出，如果我们可以证明一个NP完全问题可以在多项式时间求解，那么P等于NP。因为既然所有的NP问题都 能约化成NP完全问题，那么只要任意一个NP完全问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P 了。 NP难问题和NP完全问题的区别在于，不需要满足上述性质中的第一个性质，从这我们可以看出NP难问题要比NP完全问题更为困难。 3. NP完全问题实例 问题1 图着色问题 判定问题：是否存在不超过k种颜色的着色方案?优化问题：求图的最小着色数和着色方案 问题2 子集和数问题s1,s2,sn,C判定问题：是否存在和数等于C的子集?优化问题：求C的最大子集和数.可归约为背包问题: pi=wi.问题3 TSP(旅行商)问题 判定问题：任意给定一整数k，是否存在一长度不超过k的Hamiltonian回路？ 优化问题 问题4:顶点覆盖:无向图中的每一条边都被某些节点关联 判定问题：给定无向图G和正整数k,是否存在一k节点覆盖.优化问题：最小节点覆盖 问题5: 给定一无向图G, k-独立集;最大独立集.问题6: 给定一无向图G , k-集团;最大集团.四、NP 完全问题的求解方法 1. 完全算法 假设P、NP不相等，理论上只存在求解NP完全问题的指数时间算法；因此对最坏情况下算法时间上界的一个微小改进，例如从 O(ck)改进为O(c-e)k)都会提高甚至大幅度的提高算法的求解效率和难解问题的可解范围。对算法时间上界的改进通常采用两种方法，其一是引入新 的化简规则，其二是选择合适的时间测度。 以3-SAT问题为例， Dantsin等人提出了短语覆盖方法，证明了O(1.5n)的算法时间上界。Schiermeyer利用纯文字预测的方法，提出了在O(1.497n) 时间内求解3-SAT问题的算法。Dantsin等人采用覆盖码技术将算法上界改进为O(1.481n)。目前精确算法的3-SAT问题的最好的算法在最 坏情况下时间上界是Kutzkov等人给出的O(1.439n)。Schoning从随机算法的角度通过在随机行走算法中引入了多次启动的概念证明了其在 求解3-SAT问题时的上界是O(1.334n)。在随机算法方面目前最好的上界为Rolf等人给出的(O(1.323n)。但是从无论采用何种改进， 目前尚无求解NP完全问题的高效的完全算法。 2. 近似求解算法 由于完全算法无法快速高效的求解NP完全问题，近似求解算法就是很好的补充，利用近似求解算法我们虽然无法保证求解的完备性和最优性，但是可以以较大概率求得解或者求得次优解。在这些近似求解算法中，局部搜索算法是其中的重要组成部分之一，主要包括： 1） 爬山算法 从当前的节点开始，和周围的邻居节点的值进行比较。 如果当前节点是最大的，那么返回当前节点，作为最大值(既山峰最高点)；反之就用最高的邻居节点来，替换当前节点，从而实现向山峰的高处攀爬的目的。如此循环直到达到最高点。 2）模拟退火算法 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而 徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为 e-E/(kT），其中E为温度T时的内能，E为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f， 温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃” 的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解。 3）遗传算法 遗传算法是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索算法, 从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。生物种群的生存过程普遍遵循达尔文进化准则，群体中的个体根据对环境的适应能力而被大自然所 选择或淘汰。进化过程的结果反映在个体的结构上，其染色体包含若干基因，相应的表现型和基因型的联系体现了个体的外部特性与内部机理间逻辑关系。通过个体 之间的交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来体现就是一串数码，仍叫染色体，有时也叫个体；适应能力是对应着一个染色体的一个 数值来衡量；染色体的选择或淘汰则按所面对的问题是求最大还是最小来进行。 4）粒子群算法 属于进化算法的一种，和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传 算法规则更为简单，它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越 性。 5) 禁忌搜索 禁忌搜索（Tabu Search简称TS）的思想最早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模 拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实 现全局优化。相对于模拟退火和遗传算法，TS是又一种搜索特点不同的 meta-heuristic算法。 6) 蚁群算法 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具 有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模 拟进化优化方法的有效性和应用价值。 3. 未来进展 P是否等于NP迄今无人证明，研究人员从其他途径试图寻找比图灵机更为强大的计算工具来求解NP问题，比较著名的有DNA计算和量子计算方法 1） DNA计算 DNA计算是计算机科学和分子生物学相结合而发展起来的新型研究领域。它以DNA为计算工具，利用DNA反应的强大并行计算能力，成功地解决了诸如哈密尔顿路径、最大Clique等NP难题。 DNA可能是完成计算的最完美材料。DNA计算的创始人是美国南加州大学的莱昂那多阿德莱曼教授，他于1994年利用DNA 计算方法解决了一个著名的数学难题“七顶点哈密尔顿路径”。最近，科学家们开始利用DNA计算来创造生物计算机，放在人体或生物体工作，其计算结果可通过 荧光蛋白的活动来读取。 DNA计算是利用DNA双螺旋结构和碱基互补配对规律进行信息编码，将要运算的对象映射成DNA分子链，通过生物酶的作用，生 成各种数据池，再按照一定的规则将原始问题的数据运算高度并行地映射成DNA 分子链的可控的生化反应过程。最后，利用分子生物技术（如聚合链反应PCR、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等），检测所需 要的运算结果。 从数学上讲，单链DNA可看作由符号A、C、G、T组成的串，同电子计算机中编码0和1一样，可表示成4 字母的集合来译码信息。特定的酶可充当“软件”来完成所需的各种信息处理工作。不同的酶用于不同的算子，如限制内核酸酶可作为分离算子，DNA结合酶可作 为绑结算子，DNA聚合酶可作为复 制算子，外核酸酶可作为删除算子等。这样，通过对DNA双螺旋进行丰富的、精确可控的化学反应以完成各种不同的运算过程，就可研制成一种以DNA为芯片的新型计算机。已被证明DNA计算至少在理论上是通用的，可以解决图灵机所能解决的所有问题。 本质上，DNA计算可以分为3类：分子内、分子间和超分子DNA计算。Takahashi致力于分子内DNA计算，借助于分子 内的形态转移操作，用单DNA分子构建可编程的状态机。分子间DNA计算集中在不同DNA分子间的杂交反应，使其作为计算中的一个基本步骤，像 Adleman的实验。而超分子DNA计算是利用不同序列的原始DNA分子的自装配过程进行的计算。目前，超分子DNA计算的创新及应用进入了一个新的台 阶。 DNA计算机的研制无疑要经历3个阶段：首先是试管阶段，验证DNA计算原理的可行性；其次是表面阶段，这也是一个过渡性阶 段，要克服试管中DNA分子的易丢失和操作难的缺点；最后是芯片阶段，只有芯片化后，DNA计算机才能走向实用。这3个阶段也就是DNA计算的3种实现方 式。 经过10多年的发展已有多种DNA计算模型被提出，如剪接模型、粘贴模型、等同检测模型、插入/删除系统、最小计算模型等，这些模型都被证明和图灵机是等价的，也就是具有计算完备性。 目前，DNA计算的大量研究还停留在纸面上，很多设想和方案都是理想化的，还没有条件付诸实验，如何实现DNA计算并制造 DNA计算机，还存在许多技术障碍。对于DNA计算构造的现实性及计算潜力、DNA计算中错误的减少、有效的通用算法以及人机交互等问题都需要进行进一步 的研究。尤其是DNA计算中存在的误码，这种误码是依概率随机产生的，并能被逐级放大。误码率直接影响DNA的计算精度，目前还不能有效克服这一问题。也 许DNA计算机仅起一个运算器的作用，即便如此，这种DNA计算与传统计算机互补所获得的计算机也将产生不可估量的影响。 2） 量子计算 量子计算 (quantum computation) 的概念最早由IBM的科学家R. Landauer及C. Bennett于70年代提出。他们主要探讨的是计算过程中诸如自由能(free energy)、信息(informations)与可逆性(reversibility)之间的关系。80年代初期，阿岗国家实验室的P. Benioff首先提出二能阶的量子系统可以用来仿真数字计算；稍后费因曼也对这个问题产生兴趣而着手研究，并在1981年于麻省理工学院举行的 First Conference on Physics of Computation中给了一场演讲，勾勒出以量子现象实现计算的愿景。1985年，牛津大学的D. Deutsch提出量子图灵机(quantum Turing machine)的概念，量子计算才开始具备了数学的基本型式。量子计算将有可能使计算机的计算能力大大超过今天的计算机，但仍然存在很多障碍。大规模量 子计算所存在的一个问题是，提高所需量子装置的准确性有困难。 五、进一步理解NP完全问题 为了更好的理解NP完全问题，我们可以从NP完全问题的一些性质入手，例如NP完全问题的相变现象，NP完全问题的结构特征；1. 相变现象人工智能领域中的很多问题是难于计算的。例如SAT问题的计算复杂性即为NP完全的1.这意味着如果PNP成立，即无法 在多项式时间内解决SAT问题。另一方面，目前的SAT问题求解器已经可以在十秒以内处理包含十万个变量百万个子句以上规模的SAT问题实例。理论上的求 解困难和实际中的求解高效形成了巨大反差，引起了研究人员的广泛关注。 1994年Kirkpatrick和Selman在Science杂志上撰文指出对于k-SAT问题存在从可满足到不可满足的突变现象，即所谓的“相变现象”，当 时( 与均为子句个数与变量个数的比值)，k-SAT问题实例的可满足概率趋近于1；当 时，k-SAT问题实例的可满足概率趋近于0。该文同时指出在相变区域两侧较远的地方，大部分的SAT实例一般容易求解，而在相变点附近(称为相变点)大部分实例的求解通常是困难的。在此基础上，1996年Mitchell等人给出了SAT问题中子句的个数与命题变量的个数的比值和命题可满足性的关系以及该比值和问题难度的关系。1999年Selman等人在Nature上指出求解k-SAT问题在计算复杂性上的分布呈现出一种特殊的“easy-hard-easy”模式，即当子句个数和变量个数的比值到达一定值时，问题从可满足跃迁为不可满足，从易于求解突变到难于求解又转向易于求解。近年来，对相变现象的研究已经成为人工智能乃至计算机科学领域的研究热点。在SAT问题相变的基础上，研究人员对其他困难问题的相变现象做了深入研 究。研究发现，在旅行商问题（Traveling Salesman Problem，TSP）、约束可满足问题（Constraint Satisfaction Problem，CSP）、量词布尔范式问题（Quantified Boolean formula，QBF）、智能规划问题（Intelligent Planning）等问题中，都存在着相变现象。 对相变现象的研究不仅有助于研究人员理解导致求解问题困难的本质，而且激发研究人员针对相变区域问题设计更好的求解算法。以SAT问题为 例，2002年Mzard等人在杂志上提出调查传播(Survey Propagation，SP)算法，该算法源于统计物理学，可以在稍高于线性时间内判断具有1,000,000变量规模的处于相变区域的SAT问题。 在3-SAT问题中，Crawford等人通过实验证明了4.27，如图1所示。当子句个数与变量个数比值小于4.27时，问题实例的可满足概率几乎为100%；当子句个数与变量个数比值大于4.27时，问题实例可满足的概率几乎为0。问题的求解难度也从易于求解跃迁为难于求解最后回到易于求解。 2. 问题结构隐蔽集（Backbone）和骨架集（Backdoor）是NP完全问题中的重要结构，和问题求解难度以及问题的相变现象有着 密切关系。隐蔽集最初由Willianms等人在2003年为了分析NP完全问题的回溯算法中的重尾现象提出的。隐蔽集的大小和问题的难度有着密切的关 系。目前有三种隐蔽集的定义：强隐蔽集、删除隐蔽集和弱隐蔽集。当基本类是封闭的时候，删除隐蔽集和强隐蔽集等价。 定义4(强隐蔽集，Strong Backdoor) 给定一个命题逻辑公式，如果对于中变量的任意赋值都使得在多项式时间内可解，那么变量集合就是强隐蔽集。 定义5（弱隐蔽集，Weak Backdoor），如果中变量存在一个真值指派使得在多项式时间内可解，那么变量集合就是弱隐蔽集。 定义6（删除隐蔽集，Delete Backdoor）是一个非空变量子集，如果简化公式可在多项式时间内求解，那么变量集合是删除隐蔽集。 与隐蔽集密切相关的另一个重要的结构是骨架集。 定义7(骨架集，Backbone Set) 给定一个命题逻辑公式，骨架集是一个变量的集合，在所有的可满足赋值中，中变量的赋值都相同。 Kilby用实验的方法获知隐蔽集和骨架之间存在一定的关系，即一般情况下骨架变量不在隐蔽集中，它们之间存在很小的交集。NP完全问题的求解难度和上述这些变量存在着很多关联。上一页 1 2 下一页 专题二 人工智能综述【主要内容】1从不同科学或学科出发对人工智能进行的定义； 2介绍人工智能的起源与发展过程； 3讨论人工智能与人类智能的关系； 4简介目前人工智能的主要学派； 5简介人工智能所研究的范围与应用领域。 一、人工智能的定义 人工智能（Artificial Intelligence，AI）又称为机器智能或计算机智能，它不仅试图理解智能体，还想建造智能体。人工智能是最新兴的学科之一，至今尚无统一的定 义，这是因为人工智能的严格定义依赖于对智能的定义，但是智能本身还没有严格的定义。图1列出了8种教科书给人工智能下的定义。这些定义在两个主要方面存 在差异。粗略地说，图的上部给出的定义关心的是思维过程和推理，而图的下部的定义则强调行为。左侧的定义从模拟人类功能的逼真度的角度来度量成功与否，而 右半部的定义从理想的智能概念来度量，也就是我们所谓的“理性”。一个系统如果能够在它所知的范围内“正确行事”，它就是理性的。在这里我们可以简单解释 人工智能是用人工的方法在机器（计算机）上实现的智能。 图1. 人工智能的定义二、人工智能的起源与发展 （一）孕育时期（1956年前）人工智能的发展是以硬件与软件的发展为基础的，它的发展经历了漫长的发展历程。人类很早就开始研究自身的思维形式。早在公元前384-322年，在亚里士 多德研究他称为三段论的演绎推理时就迈出了向人工智能发展的早期步伐，可以把它看作原始的知识表达规范。三段论是以真言判断为其前提的一种演绎推理，它借 助于一个共同项，把两个直言判断联系起来，从而得出结论。 对于人工智能的发展来说，20世纪30年代和40年代的智能界，出现了两件最重要的事情：数理逻辑和关于计算的新思想。 1913年，年仅19岁的维纳在他的论文中把数理关系理论简化为类理论，为发展数理逻辑做出了贡献。数理逻辑仍然是人工智能研究的一个活跃领域，其部分原 因是由于一些逻辑演绎系统已经在计算机上实现过。丘奇、图灵和其他一些人关于计算本质的思想，提供了形式推理概念与即将发明的计算机之间的联系。在这 方面的重要工作是关于计算和符号处理的理论概念。英国数学家图灵，1936年创立了图灵机理论，1950年在其著作计算机器与智能中首次提出“机器也 能思维”，被誉为“人工智能之父”。美国数学家、电子数字计算机的先驱莫克，1946年研制成功了世界上第一台通用电子数字计算机。美国神经生理学家麦克 洛奇和皮茨，1943年建成第一个神经网络模型（MP模型）。美国著名数学家、控制论创始人维纳1948年创立了控制论。控制论对人工智能的影响，形成了 行为主义学派。 由此可见，人工智能开拓者们在数理逻辑、计算本质、控制论、神经网络模型等方面做出了的创造性贡献，奠定了人工智能发展的理论基础，孕育了人工智能的胎儿。 （二）形成时期（1956年-1970年）1956年，由年轻的美国数学家和计算机专家麦卡锡、数学家和神经学家明斯基、IBM公司信息中心主任朗彻斯特和贝尔实验室信 息部数学家和信息学家香农共同发起，在美国的达特茅斯大学举办了一次长达两个月的研讨会，认真地讨论用机器模拟人类智能的问题。会上，由麦卡锡提议正式使 用人工智能这一术语。这是人类历史上第一次人工智能研讨会，标志着人工智能学科的诞生，具有十分重要的意义。在这期间人工智能也得到了迅速的发 展，1956年，塞缪尔在IBM计算机上研制成功了具有自学习、自组织和自适应能力的西洋跳棋程序。1957年，纽厄尔等研制了一个称为逻辑理论机的数学 定理证明程序。1958年，麦卡锡建立了行动规划咨询系统。1960年，纽厄尔等研制了通用问题求解（GPS）程序。麦卡锡研制了人工智能语言LISP。 1961年，明斯基发表了“走向人工智能的步骤”的论文，推动了人工智能的发展。1965年，鲁滨逊提出了消解原理。在这一时期，人工智能已成为一门独立 的学科，为进一步发展打下重要的基础。 （三）暗淡时期（1966年-1974年）在取得发展的同时，人工智能也遇到一些困难和问题。一方面，由于一些人工智能研究者被胜利冲昏了头脑，盲目乐观，对人工智能的 未来发展和成果做出了过高的预言，而这些预言的失败给人工智能的声誉造成重大伤害。另一方面，许多人工智能理论和方法未能得到通用化和应用推广，专家系统 也未获得广泛开发，看不出人工智能的重要价值。1971年英国剑桥大学数学家詹姆士按照英国政府的旨意，发表一份关于人工智能的综合报告，声称人工智能即 使不是骗局也是庸人自扰。在这个报告的影响下，英国政府削减了人工智能研究经费，解散了人工智能研究机构。在人工智能的发源地美国，连在人工智能研究方面 颇有影响的IBM公司，也被迫取消了该公司的所有人工智能研究。人工智能研究在世界范围内陷入困境，处于低潮。 困难和挫折是难免的。通过总结经验教训，开展更广泛、深入和有针对性的研究，人工智能必将走出谷底，迎来新的发展时期。 （四）知识应用时期（1970年-1988年） 整个20世纪80年代，专家系统和知识工程在全世界得到迅速发展。专家系统实现了人工智能从理论研究走向专门知识应用，是AI发展史上的一次重要突破与转 折。1976年，斯坦福大学的杜达等人研制地质勘探专家系统PROSPECTOR。1972-1976年，费根鲍姆研制MYCIN专家系统，用于协助内科 医生诊断细菌感染疾病，并提供最佳处方。同时，在这一时期，计算机视觉、机器人、自然语言理解、机器翻译等AI应用研究获得发展。 （五）集成发展时期（1986年-至今） 到20世纪80年代后期，各国争相进行的智能计算机研究计划先后遇到严峻挑战和困难，无法实现其预期目标，这促使人工智能研究者们对已有的人工智能和专家 系统思想和方法进行反思。已有的专家系统应用领域狭窄、缺乏常识性知识、知识获取困难、推理方法单一、没有分布式功能、不能访问现存数据库等，促进专家系 统的改进与发展。20世纪80年代后期以来机器学习、人工神经网络、智能机器人和行为主义研究趋向热烈和深入。 三、人类智能与人工智能 （一）智能处理信息系统的假设1符号处理系统的六种基本功能 信息处理系统又叫符号操作系统(Symbol Operation System)或物理符号系统(Physical Symbol System)。所谓符号就是模式(pattern)。 一个完善的符号系统应具有下列6种基本功能： (1)输入符号(input)； (2)输出符号(output);(3)存储符号(store);(4)复制符号(copy);(5)建立符号结构：通过找出各符号间的关系，在符号系统中形成符号结构； (6)条件性迁移(conditional transfer):根据已有符号，继续完成活动过程。 2. 可以把人看成一个智能信息处理系统 如果一个物理符号系统具有上述全部6种功能，能够完成这个全过程，那么它就是一个完整的物理符号系统。人具有上述6种功能；现代计算机也具备物理符号系统的这6种功能。 3. 物理符号系统的假设 任何一个系统，如果它能表现出智能，那么它就必定能够执行上述6种功能。反之，任何系统如果具有这6种功能，那么它就能够表现出智能；这种智能指的是人类所具有的那种智能。把这个假设称为物理符号系统的假设。 4. 物理符号系统3个推论 推论一 既然人具有智能，那么他(她)就一定是个物理符号系统。人之所以能够表现出智能，就是基于他的信息处理过程。 推论二 既然计算机是一个物理符号系统，它就一定能够表现出智能。这是人工智能的基本条件。 推论三 既然人是一个物理符号系统，计算机也是一个物理符号系统，那么就能够用计算机来模拟人的活动。 5. 人类的认知行为具有不同的层次 认知生理学 研究认知行为的生理过程，主要研究人的神经系统（神经元、中枢神经系统和大脑）的活动，是认知科学研究的底层。 认知心理学 研究认知行为的心理活动，主要研究人的思维策略，是认知科学研究的顶层。 认知信息学 研究人的认知行为在人体内的初级信息处理，主要研究人的认知行为如何通过初级信息自然处理，由生理活动变为心理活动及其逆过程，即由心理活动变为生理行为。这是认知活动的中间层，承上启下。 认知工程学 研究认知行为的信息加工处理，主要研究如何通过以计算机为中心的人工信息处理系统，对人的各种认知行为（如知觉、思维、记忆、语言、学习、理解、推理、识 别等）进行信息处理。这是研究认知科学和认知行为的工具，应成为现代认知心理学和现代认知生理学的重要研究手段。 （二）人类智能的计算机模拟1. 机器智能可以模拟人类智能物理符号系统假设的推论一告诉人们，人有智能，所以他是一个物理符号系统；推论三指出，可以编写出计算机程序去模拟人类的思维活动。这就是说，人和计算机这两个物理符号系统所使用的物理符号是相同的，因而计算机可以模拟人类的智能活动过程。2. 智能计算机的功能 如下棋、证明定理、翻译语言文字和解决难题等。神经计算机(neural computer)能够以类似人类的方式进行“思考”，它力图重建人脑的形象。一些国家对量子计算机的研究也已起步，希望通过对量子计算(quantum computing)的研究，产生量子计算机。四、人工智能的学派及争论 （一）人工智能三大学派 1. 符号主义(Symbolicism)，又称为逻辑主义(Logicism)、心理学派(Psychlogism)或计算机学派(Computerism)，其原理主要为物理符号系统(即符号操作系统)假设和有限合理性原理。2. 连接主义(Connectionism)，又称为仿生学派(Bionicsism)或生理学派(Physiologism)，其原理主要为神经网络及神经网络间的连接机制与学习算法。3. 行为主义(Actionism)，又称进化主义(Evolutionism)或控制论学派(Cyberneticsism)，其原理为控制论及感知动作模式控制系统。（二）对人工智能的争论1对人工智能理论的争论 （1）符号主义 符号主义认为人的认知基元是符号，而且认知过程即符号操作过程。它认为人是一个物理符号系统，计算机也是一个物理符号系统，因此， 我们就能够用计算机来模拟人的智能行为，即用计算机的符号操作来模拟人的认知过程。也就是说，人的思维是可操作的。它还认为，知识是信息的一种形式，是构 成智能的基础。人工智能的核心问题是知识表示、知识推理和知识运用。知识可用符号表示，也可用符号进行推理，因而有可能建立起基于知识的人类智能和机器智 能的统一理论体系。 （2）连接主义 连接主义认为人的思维基元是神经元，而不是符号处理过程。它对物理符号系统假设持反对意见，认为人脑不同于电脑，并提出连接主义的大脑工作模式，用于取代符号操作的电脑工作模式。 （3）行为主义 行为主义认为智能取决于感知和行动(所以被称为行为主义)，提出智能行为的“感知动作”模式。行为主义者认为智能不需要知识、不 需要表示、不需要推理；人工智能可以像人类智能一样逐步进化(所以称为进化主义)；智能行为只能在现实世界中与周围环境交互作用而表现出来。行为主义还认 为：符号主义(还包括连接主义)对真实世界客观事物的描述及其智能行为工作模式是过于简化的抽象，因而是不能真实地反映客观存在的。 2对人工智能方法的争论 （1）符号主义 符号主义认为人工智能的研究方法应为功能模拟方法。通过分析人类认知系统所具备的功能和机能，然后用计算机模拟这些功能，实现人工智能。符号主义力图用数学逻辑方法来建立人工智能的统一理论体系，但遇到不少暂时无法解决的困难，并受到其它学派的否定。 （2）连接主义 连接主义主张人工智能应着重于结构模拟，即模拟人的生理神经网络结构，并认为功能、结构和智能行为是密切相关的。不同的结构表现出不同的功能和行为。已经提出多种人工神经网络结构和众多的学习算法。 （3）行为主义 行为主义认为人工智能的研究方法应采用行为模拟方法，也认为功能、结构和智能行为是不可分开的。不同的行为表现出不同的功能和不同的控制结构。行为主义的研究方法也受到其它学派的怀疑与批判，认为行为主义最多只能创造出智能昆虫行为，而无法创造出人的智能行为。 3对人工智能技术路线的争论 （1）专用路线 专用路线强调研制与开发专用的智能计算机、人工智能软件、专用开发工具、人工智能语言和其它专用设备，如LISP机、PROLOG 机、PROLOG、LISP语言、M.I语言、OPSS83语言、专家系统开发工具EMYCIN、EXPERT、INSIGHT2和GURU等。 （2）通用路线通用路线认为通用的计算机硬件和软件能够对人工智能开发提供有效的支持，并能够解决广泛的和一般的人工智能问题。这方面的例子有以 VLSI技术为基础的RISC技术、UNIX分时操作系统、C语言及其改进型、SUN工作站和SPARC工作站等。通用路线强调人工智能应用系统和人工智 能产品的开发，应与计算机立体技术和主流技术相结合，并把知识工程视为软件工程的一个分支。 （3）硬件路线 硬件路线认为人工智能的发展主要依靠硬件技术，如VLSI、人工神经网络、脑模型、智能机和智能机器人等。该路线还认为智能机器的开发主要有赖于各种智能硬件、智能工具及固