第六届全国网络科学论坛暨 第二届全国混沌应用研讨会 知识趣味竞赛 2010年7月,网络论坛与混沌应用知识 欢迎参加知识竞赛,知识游戏与竞赛规则,整个游戏和竞赛过程,既要热烈踊跃参与,又要遵守秩序,服从主持人统一指挥. 主持人宣布题目后才能举手抢答,由主持人确定谁最先回答. 参与者每人获得抢答的机会最多不超过3次,如果回答不对一次,则扣除一次. 每次回答正确者,奖励一个纪念品.,第1题,考虑一个标准的国际象棋的棋盘，如图(a)所示。定义一个新的棋子，每步只能往对角线方向移动一格，如图(b)所示。 问：棋盘上是否存在一个作为起点的黑格，使得新棋子从这个黑格起步后可以走遍所有的黑格，不重复不遗漏，最后回到起点？为什么？,(a),(b),Answer,不能. 该问题等价于：图(c)所示的网络是否为一个欧拉图？即，是否存在一条路径，经过所有的节点，不重复不遗漏，最后回到起点？此问题有解的充分必要条件是图中所有节点的度都为偶数。但显然有两个节点的度是奇数，所以此图不是欧拉图，故此问题无解。,(c),另一种解法: 如图(d)所示，如果该黑点角落是出发点的话，棋子不重复经过对角线上的黑格它就回不了原处；如果从外面进入这个黑点角落的话，它就不能重新走出去。因此，图示的黑点角落是个死角（对称的另一个黑点角落也是个死角）。原问题无解。,(d),Answer,第2题,考虑对 Barabasi-Albert 的基本模型作稍微改动如下： 第一步：从一个 m 个节点的星型网络开始。 第二步：每次引进一个新的节点。这个新节点带进 n(m)条边。每条新的边和老的节点连接的概率为 其中 ki 为节点 i 的度。 问：这样生成的网络是什么类型的网络？为什么？,生成的网络是一个均匀的随机网络，因为大的节点具有小的概率被新节点连接，而小的节点却有大的概率被新节点连接。这样，慢慢地，小的节点逐渐变大，而原来大的节点逐渐相对地变小，最后所有节点都差不多大小，并且具有差不多相同的概率与新节点连接。,Answer,人类行为模式的分析是近期国内外的一个研究热点. 当前的实证研究表明: 人们处理某些事件的时候, 事件间隔时间(inter-event time, 用 表示) 并不是以往大家认为的泊松分布, 而是呈现胖尾的幂律分布, 即 . 如下图所示的三个活动序列对应着三种不同指数 的幂律活动模式 ( 已归一化处理). 请迅速扫一眼, 然后给出其对应的指数 之间的大小关系.,第3题,第3题,实际上这三个序列分别是用 生成的,Answer,第4题,考虑下面一个复杂网络模型. 算法步骤如下: 1. (开始)一个很大尺寸的完全连接图. 2. (过程) 对于每个可能的连接节点对, 用概率p (0p1) 删除它们之间的边. 随时删除可能出现的孤立节点. 3. (结束) 对每个可能的节点对都如上操作一次, 不重复不遗漏, 然后停止. 问: 最后, 会得到一个什么类型的网络?,最终的网络是原来随机网络的补图. 因此, 它也是一个随机网络.,Answer,第5题,考虑下面复杂网络模型. 步骤如下: 1. (开始)一个很大尺寸的完全连接图. 2. (过程)随机地捡起一条边: 如果删去这条边并不会使整个网络变得不连通, 则删除它; 如果删除这条边将使网络变得不连通, 则什么也不要做. 继续从余下的网络中再随机地捡起另外一条边, 然后重复上述操作. 3. (结束) 对每个可能的连接边都运作一次, 不重复不遗漏, 然后停止. 问: 最后会得到一个什么类型的网络?,最终的网络是一个生成树(Spanning Tree).,Answer,第6题,我国召开哪两个系列复杂网络会议? 它们的第一届分别在何年何地举行? (A) 第一届全国复杂网络论坛(2004, 太湖) (B) 第一届全国复杂网络会议(2005, 武汉) (C) 国际复杂性会议(2009, 上海) (D) 国际复杂性会议(2009, 成都),(A), (B),Answer,第7题,小世界, 无标度网络模型的提出, 引起了科学界的广泛关注, 并由此形成”复杂网络”这个交叉学科. 请问下列选项中, 提出小世界模型和无标度模型的分别是哪两篇? 并请按照文章发表的先后进行排序. (A) D.J. Watts, and S. H. Strogatz, Collective dynamics of “small-world” networks. Nature. (B) S. H. Strogatz, Exploring complex networks. Nature. (C) R. Albert, and A. L. Barabasi, Statistical mechanics of complex networks. Reviews of Modern Physics. (D) A. L. Barabasi, and R. Albert, Emergence of scaling in random networks. Science. (E) M. E. J. Newman, The structure and function of complex networks. SIAM Review.,(A), (D) Watts D J, Strogatz S H. Collective dynamics of small-world networksJ. Nature, 1998, 393:440-442. BarabsiA L, Albert R, Emergence of Scaling in Random NetworksJ, Science, 1999, 286(5439): 509-512. 先后排序为: (A_1998),(D_1999),(B_2001),(C_2002),(E_2003).,Answer,第8题,考虑一个大规模的无标度计算机网络,其中节点是由若干个巨大的服务器和大量的小电脑PC组成.用什么最好的搜索方式可以利用最少可能的信息和最少可能的操作步骤就能从这个巨大计算机网络中找到一个服务器?,首先从网络中随机的选取一个节点,然后从它的邻居寻找最大的节点,以此类推,继续在下一个邻居里找到最大的节点,这样很快就能找到一个服务器. 原因:因为无标度是不均匀的,第一个捡到的很可能是一个小PC.但是,也正是由于无标度特性,这个PC很可能与一个服务器直接相连,因此是该PC邻居里的最大节点.如果不是,则再走一、二步一、二步，则应该能找到一个服务器。请看下图：,Answer,第9题,“复杂网络”应该说是Nature 和Science 杂志上的”常客”. 请问, 在下面列出的复杂网络研究方向中, 有相关文章在上述两个杂志发表的有哪些? (a) 网络的自导航能力(Navigability) (b) 网络上的病毒传播(Epidemic) (c) 社会标签系统的模块(Motif)分析 (d) 社会网络演化的实证研究 (e) 无标度网络上的拥塞(Jamming)问题,a, b, d, e,Answer,第10题,BA网络是偏好连接且增长的网络，每次引进一个新的节点按节点度优先连接。现在考虑新的节点按老节点的年龄优先连接，假设连接老节点的概率正比于 ，其中 是老节点的年龄。问：当 从负值增长到正值时，这样生成的网络的结构有什么变化？譬如等于10，0，10时，所生成的网络分别是什么类型的网络？,当从负值增长到正值时，新节点按老节点的年龄优先连接的程度减弱，负的很大时新节点倾向于连接年龄最大的节点，正的很大时新节点倾向于连接年龄最轻的节点。等于10，0，10时，所生成的网络基本上是星形，随机（与年龄无关）和链状的网络。,Answer,第11题,指出下面图示的混沌系统的名称.,(c),(d),(b),(a),(a) Lorenz 系统 (b) Chen 系统 (c) Chua 系统 (d) Rossler 系统,Answer,第12题,什么是混沌？ 指出数学上对混沌有哪些定义？举出1-2个。 给出数学上判别混沌的3-5种常用指标。,(1) 混沌是一种貌似无规则的运动，是在确定性非线性系统中不需要附加任何随机因素出现类似随机行为。混沌系统的最大特点在于系统的非线性演化对初始条件十分敏感。 (2) Devany对混沌的定义: i) 对初值敏感依赖; ii) 拓扑传递性; iii) 周期点集的稠密性. Li-Yorke提出的混沌定义, 周期3意味着混沌 (3) 正李亚普诺夫指数、正熵、分数维数、连续功率谱、共轭于符号动力系统、Melnikov 函数具有单零点、满足Shilnikov 不等式条件、存在Smale 马蹄，等等,Answer,第13题,举出中国人在混沌与应用方面有影响的几项工作和贡献。,李天岩提出的“周期3意味着混沌” 蔡少棠提出的Chua电路 陈关荣提出的Chen系统 吕金虎提出的L系统 ,Answer,第14题,有哪些混沌控制的常用方法？请列举3-5个，并评论其优缺点。,OGY方法， 延时控制法， 非线性控制法， 微扰控制法， 自适应控制法， 状态反馈控制法， 智能控制法 ,Answer,第15题,混沌同步有哪些方法？有什么应用？,驱动-响应同步法 主动-被动同步法 微扰反馈同步法 自适应同步法 牵制控制法 可以应用于混沌编码、信息隐藏和保密通信、多周期信号发生器、弱信号检测、心电图脑电图病理分析、湍流分析等方面。,Answer,第16题,对混沌的研究引起越来越多学者们的关注. 我国学者在国内外出版了一系列有关混沌与应用的专著. 指出下列的专著的作者是谁？(任选4项回答即可) （可能有遗漏）： (A) Lorenz系统族的动力学分析、控制与同步 (B) Controlling Chaos and Bifurcation in Engineering Systems (C) Chaos-Based Digital Communication System, New York: Springer-Verlag, 2003. (D) 驾驭混沌与发展高新技术 (E) 混沌时间序列分析及其应用 (F) 混沌动力学基础及其应用 (G) 混沌动力学初步,(A) 陈关荣，吕金虎 (B) 陈关荣 (G. Chen) (C) 刘重明，谢智刚 (F.C.M. Lau / C.K. Tse) (D) 方锦清 (E) 吕金虎，陆君安，陈士华 (F) 刘宗华 (G) 陈士华，陆君安,Answer,第17题,混沌在工程技术方面有一些熟知的应用。 指出下列选项中哪些混沌应用和常规方法相比在某些方面更具有明显的独特优点？ (A) 混沌保密通信系统 (B) 混沌信号雷达与混沌激光雷达汽车防撞系统 (C) 混沌交织器 (D) 基于半导体激光器的混沌激光测距方法及装置 (E) 混沌激振器 (F) 超混沌保健装置 (G) 混沌流体搅拌器,A, B, C, D, E, F, G,Answer,第18题,在耗散系统中，随着能量的消耗，系统相空间收缩，最终趋向一个相对稳定的极限状态，这些极限状态在相空间里表现为一个低维的小“区域” ，对不稳定的点具有“吸附”作用，故称为吸引子。“吸收”的过程意味这系统的演化，系统中各个子系统的自由度