网络与混沌知识竞赛题目ppt课件

.,0,第六届全国网络科学论坛暨第二届全国混沌应用研讨会知识趣味竞赛2010年7月,.,1,网络论坛与混沌应用知识欢迎参加知识竞赛,.,2,知识游戏与竞赛规则,整个游戏和竞赛过程,既要热烈踊跃参与,又要遵守秩序,服从主持人统一指挥.主持人宣布题目后才能举手抢答,由主持人确定谁最先回答.参与者每人获得抢答的机会最多不超过3次,如果回答不对一次,则扣除一次.每次回答正确者,奖励一个纪念品.,.,3,第1题,考虑一个标准的国际象棋的棋盘，如图(a)所示。定义一个新的棋子，每步只能往对角线方向移动一格，如图(b)所示。问：棋盘上是否存在一个作为起点的黑格，使得新棋子从这个黑格起步后可以走遍所有的黑格，不重复不遗漏，最后回到起点？为什么？,(a),(b),.,4,Answer,不能.该问题等价于：图(c)所示的网络是否为一个欧拉图？即，是否存在一条路径，经过所有的节点，不重复不遗漏，最后回到起点？此问题有解的充分必要条件是图中所有节点的度都为偶数。但显然有两个节点的度是奇数，所以此图不是欧拉图，故此问题无解。,(c),.,5,另一种解法:如图(d)所示，如果该黑点角落是出发点的话，棋子不重复经过对角线上的黑格它就回不了原处；如果从外面进入这个黑点角落的话，它就不能重新走出去。因此，图示的黑点角落是个死角（对称的另一个黑点角落也是个死角）。原问题无解。,(d),Answer,.,6,第2题,考虑对Barabasi-Albert的基本模型作稍微改动如下：第一步：从一个m个节点的星型网络开始。第二步：每次引进一个新的节点。这个新节点带进n(m)条边。每条新的边和老的节点连接的概率为其中ki为节点i的度。问：这样生成的网络是什么类型的网络？为什么？,.,7,生成的网络是一个均匀的随机网络，因为大的节点具有小的概率被新节点连接，而小的节点却有大的概率被新节点连接。这样，慢慢地，小的节点逐渐变大，而原来大的节点逐渐相对地变小，最后所有节点都差不多大小，并且具有差不多相同的概率与新节点连接。,Answer,.,8,人类行为模式的分析是近期国内外的一个研究热点.当前的实证研究表明:人们处理某些事件的时候,事件间隔时间(inter-eventtime,用表示)并不是以往大家认为的泊松分布,而是呈现胖尾的幂律分布,即.如下图所示的三个活动序列对应着三种不同指数的幂律活动模式(已归一化处理).请迅速扫一眼,然后给出其对应的指数之间的大小关系.,第3题,.,9,第3题,.,10,实际上这三个序列分别是用生成的,Answer,.,11,第4题,考虑下面一个复杂网络模型.算法步骤如下:1.(开始)一个很大尺寸的完全连接图.2.(过程)对于每个可能的连接节点对,用概率p(0p1)删除它们之间的边.随时删除可能出现的孤立节点.3.(结束)对每个可能的节点对都如上操作一次,不重复不遗漏,然后停止.问:最后,会得到一个什么类型的网络?,.,12,最终的网络是原来随机网络的补图.因此,它也是一个随机网络.,Answer,.,13,第5题,考虑下面复杂网络模型.步骤如下:1.(开始)一个很大尺寸的完全连接图.2.(过程)随机地捡起一条边:如果删去这条边并不会使整个网络变得不连通,则删除它;如果删除这条边将使网络变得不连通,则什么也不要做.继续从余下的网络中再随机地捡起另外一条边,然后重复上述操作.3.(结束)对每个可能的连接边都运作一次,不重复不遗漏,然后停止.问:最后会得到一个什么类型的网络?,.,14,最终的网络是一个生成树(SpanningTree).,Answer,.,15,第6题,我国召开哪两个系列复杂网络会议?它们的第一届分别在何年何地举行?(A)第一届全国复杂网络论坛(2004,太湖)(B)第一届全国复杂网络会议(2005,武汉)(C)国际复杂性会议(2009,上海)(D)国际复杂性会议(2009,成都),.,16,(A),(B),Answer,.,17,第7题,小世界,无标度网络模型的提出,引起了科学界的广泛关注,并由此形成”复杂网络”这个交叉学科.请问下列选项中,提出小世界模型和无标度模型的分别是哪两篇?并请按照文章发表的先后进行排序.(A)D.J.Watts,andS.H.Strogatz,Collectivedynamicsof“small-world”networks.Nature.(B)S.H.Strogatz,Exploringcomplexnetworks.Nature.(C)R.Albert,andA.L.Barabasi,Statisticalmechanicsofcomplexnetworks.ReviewsofModernPhysics.(D)A.L.Barabasi,andR.Albert,Emergenceofscalinginrandomnetworks.Science.(E)M.E.J.Newman,Thestructureandfunctionofcomplexnetworks.SIAMReview.,.,18,(A),(D)WattsDJ,StrogatzSH.Collectivedynamicsofsmall-worldnetworksJ.Nature,1998,393:440-442.BarabsiAL,AlbertR,EmergenceofScalinginRandomNetworksJ,Science,1999,286(5439):509-512.先后排序为:(A_1998),(D_1999),(B_2001),(C_2002),(E_2003).,Answer,.,19,第8题,考虑一个大规模的无标度计算机网络,其中节点是由若干个巨大的服务器和大量的小电脑PC组成.用什么最好的搜索方式可以利用最少可能的信息和最少可能的操作步骤就能从这个巨大计算机网络中找到一个服务器?,.,20,首先从网络中随机的选取一个节点,然后从它的邻居寻找最大的节点,以此类推,继续在下一个邻居里找到最大的节点,这样很快就能找到一个服务器.原因:因为无标度是不均匀的,第一个捡到的很可能是一个小PC.但是,也正是由于无标度特性,这个PC很可能与一个服务器直接相连,因此是该PC邻居里的最大节点.如果不是,则再走一、二步一、二步，则应该能找到一个服务器。请看下图：,Answer,.,21,第9题,“复杂网络”应该说是Nature和Science杂志上的”常客”.请问,在下面列出的复杂网络研究方向中,有相关文章在上述两个杂志发表的有哪些?(a)网络的自导航能力(Navigability)(b)网络上的病毒传播(Epidemic)(c)社会标签系统的模块(Motif)分析(d)社会网络演化的实证研究(e)无标度网络上的拥塞(Jamming)问题,.,22,a,b,d,e,Answer,.,23,第10题,BA网络是偏好连接且增长的网络，每次引进一个新的节点按节点度优先连接。现在考虑新的节点按老节点的年龄优先连接，假设连接老节点的概率正比于，其中是老节点的年龄。问：当从负值增长到正值时，这样生成的网络的结构有什么变化？譬如等于10，0，10时，所生成的网络分别是什么类型的网络？,.,24,当从负值增长到正值时，新节点按老节点的年龄优先连接的程度减弱，负的很大时新节点倾向于连接年龄最大的节点，正的很大时新节点倾向于连接年龄最轻的节点。等于10，0，10时，所生成的网络基本上是星形，随机（与年龄无关）和链状的网络。,Answer,.,25,第11题,指出下面图示的混沌系统的名称.,(c),(d),(b),(a),.,26,(a)Lorenz系统(b)Chen系统(c)Chua系统(d)Rossler系统,Answer,.,27,第12题,什么是混沌？指出数学上对混沌有哪些定义？举出1-2个。给出数学上判别混沌的3-5种常用指标。,.,28,(1)混沌是一种貌似无规则的运动，是在确定性非线性系统中不需要附加任何随机因素出现类似随机行为。混沌系统的最大特点在于系统的非线性演化对初始条件十分敏感。(2)Devany对混沌的定义:i)对初值敏感依赖;ii)拓扑传递性;iii)周期点集的稠密性.Li-Yorke提出的混沌定义,周期3意味着混沌(3)正李亚普诺夫指数、正熵、分数维数、连续功率谱、共轭于符号动力系统、Melnikov函数具有单零点、满足Shilnikov不等式条件、存在Smale马蹄，等等,Answer,.,29,第13题,举出中国人在混沌与应用方面有影响的几项工作和贡献。,.,30,李天岩提出的“周期3意味着混沌”蔡少棠提出的Chua电路陈关荣提出的Chen系统吕金虎提出的L系统,Answer,.,31,第14题,有哪些混沌控制的常用方法？请列举3-5个，并评论其优缺点。,.,32,OGY方法，延时控制法，非线性控制法，微扰控制法，自适应控制法，状态反馈控制法，智能控制法,Answer,.,33,第15题,混沌同步有哪些方法？有什么应用？,.,34,驱动-响应同步法主动-被动同步法微扰反馈同步法自适应同步法牵制控制法可以应用于混沌编码、信息隐藏和保密通信、多周期信号发生器、弱信号检测、心电图脑电图病理分析、湍流分析等方面。,Answer,.,35,第16题,对混沌的研究引起越来越多学者们的关注.我国学者在国内外出版了一系列有关混沌与应用的专著.指出下列的专著的作者是谁？(任选4项回答即可)（可能有遗漏）：(A)Lorenz系统族的动力学分析、控制与同步(B)ControllingChaosandBifurcationinEngineeringSystems(C)Chaos-BasedDigitalCommunicationSystem,NewYork:Springer-Verlag,2003.(D)驾驭混沌与发展高新技术(E)混沌时间序列分析及其应用(F)混沌动力学基础及其应用(G)混沌动力学初步,.,36,(A)陈关荣，吕金虎(B)陈关荣(G.Chen)(C)刘重明，谢智刚(F.C.M.Lau/C.K.Tse)(D)方锦清(E)吕金虎，陆君安，陈士华(F)刘宗华(G)陈士华，陆君安,Answer,.,37,第17题,混沌在工程技术方面有一些熟知的应用。指出下列选项中哪些混沌应用和常规方法相比在某些方面更具有明显的独特优点？(A)混沌保密通信系统(B)混沌信号雷达与混沌激光雷达汽车防撞系统(C)混沌交织器(D)基于半导体激光器的混沌激光测距方法及装置(E)混沌激振器(F)超混沌保健装置(G)混沌流体搅拌器,.,38,A,B,C,D,E,F,G,Answer,.,39,第18题,在耗散系统中，随着能量的消耗，系统相空间收缩，最终趋向一个相对稳定的极限状态，这些极限状态在相空间里表现为一个低维的小“区域”，对不稳定的点具有“吸附”作用，故称为吸引子。“吸收”的过程意味这系统的演化，系统中各个子系统的自由度越来越少，相互联系和整体约束越来越强。问:什么是混沌吸引子？它具有什么特性？,.,40,混沌吸引子,是指在相空间中经过无数次的靠拢和分离，来回折叠形成的轨线的极限点集。具有分数维数，具有自相似性，具有正熵，具有对邻近轨道的吸引性。,Answer,.,41,1963年著名气象学家在美国大气科学（JAtmosSci）上提出了第一个混沌模型Lorenz系统，当时还没有“Chaos”这个词，到了1975年美国数学家J.约克和李天岩在美国数学月刊（TheAmerican.MathematicalMonthly）发表PeriodThreeImpliesChaos首先引入了Chaos的名称，但是事实上前苏联的哪位数学家早在哪一年就建立了比“周期3蕴含混沌”更一般的定理？,第19题,.,42,Answer,沙可夫斯基（SarkovskiAN）早在1964年在乌克兰数学学报（UkranianMath.J）发表了沙可夫斯基定理，指出将自然数排列一个序，如果m排在n前面,那么一个连续函数如果有周期m，则一定有周期n，而排在第一个正是3，所以沙可夫斯基定理包括了“周期3蕴含无穷多个周期”的结果。但是，李.约克定理的核心是scrambledset-它是混沌的本质（沙可夫斯基定理没有这个内容）,.,43,第20题,举出迄今世界上最大的3个复杂网络及其主要特性？,.,44,互联网，万维网，大脑神经网络，等等。它们都有小世界特性和无标度特性,Answer,.,45,第21题,哪国的计算机三兄弟首先怎么证明互联网的幂律分布特性？,.,46,加拿大Faloutsos三兄弟于年首先揭示了Internet拓扑的一些幂律分布，他们是通过分析年月至年月AS层面Internet的统计数据而获得，从此开拓了Internet拓扑研究的新方向。后来他们又进一步拓广到AS层面上Internet拓扑演化，得到四种幂律分布。,Answer,.,47,第22题,“网络科学”的报告最早何国、何时和由何单位或谁提出来的？请说明实际背景。,.,48,最早由美国国防部所属委员会于年月发表一个研究报告：“网络科学”。背景是美国国防部海军作战部部长在年提出“网络中心战”，随后美国政府几国防部实施了一系列与网络科学相关的研究，例如个重电研究机会，年月美国科学院国家研究委员会所属“陆军科学技术专业委员会”开展了“网络科学在未来陆军的应用”项目研究，在一系列研究活动的基础上发表了“网络科学”报告。,Answer,.,49,第23题,“网络科学与工程”报告在何国、何时和由何单位或谁提出来的？请说明实际背景。,.,50,2009年9月由美国麻省理工大学等十所著名大学联合组成了“美国网络科学与工程委员会”.在专题报告“网络科学与工程的研究议事日程”中，空前强调了美国今后加强网络科学与工程应用研究的重大意义和研究方向，要求政府必须加大研究经费的投入力度。,Answer,.,51,第24题,迄今国际上出版了一系列“网络科学”方面的书籍.请将下列书名和作者对号入座.(任选3项回答即可),(A)Linked:TheNewScienceofNetworks(B)SixDegrees:TheScienceofaConnectedAge(C)Networks:AnIntroduction(D)LargeScaleStructureandDynamicsofComplexNetworks:FromInformationTechnologytoFinanceandNaturalScience(E)NetworkScienceTheoryandApplications,A.L.BarabasiGuidoCaldarelliTedG.LewisM.E.J.NewmanD.J.Watts,.,52,Answer,(A)Linked:TheNewScienceofNetworks(B)SixDegrees:TheScienceofaConnectedAge(C)Networks:AnIntroduction(D)LargeScaleStructureandDynamicsofComplexNetworks:FromInformationTechnologytoFinanceandNaturalScience(E)NetworkScienceTheoryandApplications,A.L.BarabasiGuidoCaldarelliTedG.LewisM.E.J.NewmanD.J.Watts,.,53,第25题,网络的同配性系数(assortativitycoefficient)反映了网络的度相关性质,即:与度大节点相连接的节点的度偏高还是偏低.指出下列给出的网络通常是同配性网络还是异配性网络?(A)技术网络(B)生物网络(C)AS层面的Internet(D)社会网络,.,54,Answer,(A)异配性(B)异配性(C)异配性(D)同配性,.,55,第26题,很多人可能都有这样的经历:偶尔碰到一个陌生人,同他聊了一会儿后发现你认识的某个人居然他也认识,然后你们会一起发出”这个世界真小”的感叹.著名的小世界实验(社会调查)表明:地球上任意两个人之间的平均距离是6.问:该推断最早由国际上哪位学者提出?,.,56,Answer,20世纪60年代美国哈佛大学的心理学家StanleyMilgram(1933-1984),.,57,第27题,下面是与混沌相关的一些比较著名的图形，请分别指出图的名称。,A,B,C,.,58,Answer,A)蝴蝶效应B)Mandelbrot集C)Henon映射不动点,.,59,第28题,研究项目”混沌反控制与广义Lorenz系统族的理论及其应用”,获得2008年国家自然科学二等奖.该项目的主要完成人有:陈关荣，吕金虎，周天寿，陆君安.问:什么叫混沌的反控制?又问：国内外目前唯一的一本混沌反控制的书，书名是什么？作者是谁？,.,60,Answer,为了利用混沌,通过设计控制器的方法,将系统混沌化.陈关荣、汪小帆：动力系统的混沌化理论、方法与应用,上海交通大学出版社（2006）,.,61,第29题,复杂动力网络的同步研究具有非常广泛的实际意义,例如,夏日晚间萤火虫的同步发光,Internet上的路由器周期性地发布路由消息,生物界中鱼群鸟群的集群行为.Kuramoto振子的同步,等等.你能说出三种或三种以上研究复杂动力网络同步的常用方法吗?,.,62,Answer,主稳定函数(masterstabilityfunction)方法Lyapunov函数方法基于连接图的稳定性方法(connectiongraphbasedstabilitymethod)牵制(pinning)控制法,.,63,第30题,网络科学的历史可以分为3个阶段：初期阶段(17361960)、中期阶段(19601998)、现代阶段(1998present).请说说这3个阶段的特点和代表性的工作。,.,64,Answer,初期阶段(17361960)：1736,七桥问题，Euler建立图论。中期阶段(19601998):1960,Erdos和Renyi建立ER随机图;开始某些应用，如社会科学（六度分离）。现代阶段(1998present)：小世界、无标度特性的发现和建模，模拟现实复杂系统。,.,65,近年我国与复杂网络、复杂系统有关的成果陆续获得省(市)、部科技奖励。请至少举出获得省(市)、部一等奖的1-3单位及其个人名字？还能够举出第四、第五单位和个人获奖单位和个人名字吗？（多一个，加1分）。,第31题,.,66,Answer,获省部级奖励（可能有遗漏）：1.脉冲动力系统的稳定与控制,教育部一等奖,华中科技大学，关治洪,廖锐全,王燕舞,钱同惠,陈武华，20052.几类典型复杂系统的建模、分析与应用，教育部一等奖，武汉大学,吕金虎,陆君安,何克清,禹思敏,陈士华,李兵,吴晓群,周进，20073.复杂动态网络同步与控制研究，上海市一等奖，上海交通大学，汪小帆,李翔，20084.面向交通运输系统的复杂网络理论与方法,教育部一等奖,北京交通大学，高自友,吴建军,李克平,黄海军,孙会君,赵小梅,郑建风,赵晖,李新刚，20095.复杂网络的结构、功能与动力学研究,教育部一等奖，中国科学技术大学，汪秉宏,王文旭,周涛,谢彦波,赵明,殷传洋，20096.神经信息分析的理论、方法与应用，教育部一等奖，电子科技大学，尧德中,李春光,陈华富,徐鹏，2009,.,67,网络同步有着广泛的应用，请举几个应用例子。,第32题,.,68,Answer,网络同步有着广泛的应用，譬如:网络同步可以解释生物现象,例如萤火虫群1,蟋蟀群2,神经振子3和心肌细胞群4;在认识大脑认知紊乱5,神经计算6,解释人类集体行为如掌声响起来78,还有在激光系统,超导材料和通信系统中也有重要应用。,.,69,Answer,可以参考：1J.Buck,“SynchronousrhythmicflashingoffirefliesII,”Q.Rev.Biol.,1988,63(3):2652892T.J.Walker,“Acousticsynchrony:Twomechanismsinthesnowytreecricket,”Science,1969,166(3907):8918943D.HanselandH.Sompolinsky,“Synchronizationandcomputationinachaoticneuralnetwork,”Phys.Rev.Lett.,1992,