课程文献中心 更多>>

关键词： 并发数据结构   可线性化   观察等价   Lipton约简  

摘要： 面对多核处理器技术的不断革新,为充分地利用多核资源提升程序的性能,设计和实现高并发的数据结构变得越来越重要。为获得更多的并发和更好的性能,程序开发者会尽可能的采用细粒度同步技术来实现并发数据结构。然而这些数据结构通常复杂灵巧、易出错、可靠性难以保证。因此,形式化验证并发数据结构对提高并发软件的可靠性和安全性有着重要意义。可线性化是一个主流的并发数据结构安全性标准。本文针对并发数据结构可线性化标准及其验证方法方面进行了深入研究。本文分析了可线性化标准的局限性,在此基础上提出了强可线性化标准。验证并发数据结构强可线性化最困难的部分还是验证可线性化。正如Khyzha所说的一样,尽管有大量的可线性化验证技术,要验证复杂并发数据结构的可线性化仍是一项极具挑战性的任务。本文致力于提供简单易用的方法验证并发数据结构的可线性化,具体做了如下几个方面的工作:(1)本文首先分析了可线性化的二个局限性:1)可线性化给用户带来的是观察精化的保证,而不是观察等价的保证;2)即使客户端以和并发数据结构方法非交互的方式直接访问数据结构,可线性化的观察精化保证也会被破坏。针对以上二个局限,提出了并发数据结构的强一致性标准—强可线性化,并证明了强可线性化蕴含观察等价和即使在一个允许客户端以兼容的方式直接访问数据结构的程序模型下,强可线性化的观察等价保证也不会被破坏。本文选择客户端的执行路径作为客户的观察行为,这不仅使得客户能够观察到客户端程序的最终状态,也使得客户能够观察到相关的时态属性。对于强可线性化的一种特例,即并发数据结构的实现和规约有相同状态空间的强可线性化(称这个规约为顺序规约),本文揭示了并发数据结构相对顺序规约的强可线性化与相对其它抽象模型的强可线性化之间的联系。直观上讲,顺序规约可视为并发数据结构最大化的原子抽象,即要证明一个并发数据结构相对一个更抽象的模型是强可线性化的,可简化证明顺序规约和这个抽象模型的相关联系。因为顺序规约和这个抽象模型的方法都是原子的,显然证明后者比证明前者容易的多。(2)提出了基于抽象约简的可线性化验证方法,并应用该方法验证了MS无锁队列、DGLM队列、HSY栈、数据对快照(Pair Snapshot)、基于惰性链表的集合(Lazy Set)、基于乐观锁的集合(the Optimistic List)等这些灵巧复杂的并发数据结构。本文提出的基于抽象约简的可线性化验证方法与其它基于Lipton约简的可线性化验证方法不同之处在于:1)基于抽象的约简仅要求满足抽象语义的子路径是可约简的,而不要求整个路径是可约简的;2)把路径约简从单路径扩展到双路径;3)对于不可约简的读方法,通过可达性证明把读方法转化成一个可达点,可线性化证明化简到证明写方法与可达点的约简性。总之,基于抽象约简的可线性化验证方法既保持了Lipton约简的简单、直观、易用性,同时也将Lipton约简方法应用到更多复杂灵巧的数据结构中。(3)对于一个可线性化的并发数据结构的封装扩展,证明了要验证这个扩展后的并发数据结构的可线性化,可证明由抽象方法代替它里面的具体方法后生成的并发数据结构的可线性化。因为抽象方法都是原子的,证明后者要比验证前者容易的多。依据这个结论,本文使用基于抽象约简的可线性化验证方法验证了一个基于封装扩展的并发哈希表。(4)对于一个采用抵消优化机制的并发栈,证明了只要正常的并发执行(即非抵消优化机制参与的并发执行部分)是可线性化的,那么并发栈就是可线性化的。利用这个结论,可以简化采用抵消优化机制的并发栈的可线性化证明。(5)提出了基于先于偏序关系属性的并发队列和并发栈的可线性化验证方法,并证明了它们是完备的。该方法将并发队列/栈的可线性化证明化简到验证入队/栈操作与出队/栈操作间的先于偏序关系属性,并发数据结构的设计与实现者容易快速的掌握和应用这个方法。本文应用这两个方法验证了HW队列(the Herlihy-Wing queue)、时间戳队列(the Time-Stamped queue)、篮式队列(Baskets Queue)、LCRQ队列和时间戳栈(the Time-Stamped stack)等这些基于抽象约简方法不能处理的、极具挑战性的并发数据结构。

关键词： 电子计算机   数据结构  

ISBN: (纸本)9787302527084

摘要： 本书严格遵守《全国硕士研究生入学考试计算机相关专业综合》大纲，分为考点详解与试题全解2部分。考点详解部分以伪代码进行讲解，关键步骤给出详细的代码注释，并用图形给出算法的流程分析，方便读者从原理上进行理解。试题全解部分以408试题以及部分高校历年真题为例进行详细解析，进一步增强读者的实际解题能力。

关键词： 微课   “助学型”微课   作业讲评  

摘要： 文章以数据结构课程为例给出了借助于"助学型"微课进行作业讲评的步聚和方法,解决了课堂作业讲评中学时不允许、不同层次学生的个性化无法兼顾和作业讲评时效性等问题,对同行应该具有一定的借鉴价值。

关键词： 大数据时代   数据结构   行为经济统计   心理因素   生理特征   数据转换  

摘要： 上个世纪70年代发展起来的行为经济学将行为人的心理因素及其相关心理学规律纳入经济学的研究,不仅很好地解释了主流经济学的一些“异象”,而且也大大拓展了经济学的研究视域。以噪声交易理论、前景理论、心理账户为代表的行为经济理论,主要通过心理因素来描述个体的行为选择,探求经济现象背后的作用机理,特别是探求现象背后人的行为及其对现象的作用机理与影响;同时,对不确定条件下行为人的决策展开研究,以增强经济学的解释能力。然而,由于行为人心理因素识别的障碍,致使其所涉变量的测度与样本数据的获取极其困难,理论结论难以提供相应的经验证据,这种状识一方面制约了行为经济学本身的发展,另一方面却极大的限制了行为经济学的现实应用价值。为了克服这一障碍,行为经济学家借鉴物理学或工程实验的思想与方法,构建出一套能获取单因素(包括心理因素)作用效应的科学方法,即实验经济学。实验经济学的出现不仅在一定程度上克服了行为经济学研究中心理因素样本数据获取的局限,而且通过对实验数据的观察与计算,经济学家同时也发现一系列行为人经济选择过程中的未解之谜,进一步推进了行为经济学研究的深入与发展。可是,利用实验经济学方法解决样本数据的获取也存在一些明显的不足,其中主要体现在:(1)实验设计要求高,现实的环境条件往往不易获得满足;(2)实验成本过高,实验过程控制困难;(3)实验结果(数据)可能存在较大的偏差,所获数据并不能真实反映研究对象的心理因素,就像证券投资交易中实盘交易与模拟交易那样,实验样本实质上并不能真实地反映对照样本的心理因素。大数据时代的来临为我们克服实验经济学中的上述缺陷带来了希望与机遇,大数据以其海量、完整、多样化、复杂可变的数据结构为我们提供了行为人的选择路径与结果,尤其是它提供的音频、视频、活动轨迹以及经济选择特点等能反映行为人心理因素的非结构数据为我们将其结构化造创了条件,一旦非结构数据结构化成为可能,统计学便在行为经济学的研究中就有了更大的用武之地。因此,在大数据时代,利用大数据带来的契机,构建大数据下的行为经济统计分析体系与架构对于推进行为经济学的研究与发展就具有特殊重要的意义,实现这一目标的基础在于要率先解决行为经济学中心理因素的识别与测度。众所周知,统计分析之所以能被应用于对经济问题的研究得益于它有一套科学完善的估计与推断技术,而能实现统计估计与推断的前提在于有相应的样本数据,如果说统计学的进步与发展是统计估计与推断技术的创新,倒不如说是对样本数据的适应性研究,传统的统计分析之所以在行为经济学研究中缺乏建树,并不是因为估计与推断技术的缺乏,而是无法获取能与之相匹配的样本数据(主要是心理因素数据)。对统计学研究而言,大数据时代的到来,不仅彻底改变了数据的经济内涵,而且更重要的是它带来的样本数据(结构性数据)可得性的变革,当原先不可得的行为人心理因素数据变得易得时,即便是现有的统计分析方法与技术毫无进展,统计分析的价值也会获得显著提升。本文在这种思想指导下,试图系统探讨大数据时代背景下如何获取与行为经济研究相关的心理因素结构性样本数据,并将其应用于行为经济学研究。本文在对相关研究进行系统梳理的基础上,依照行为经济学研究中所涉及心理因素的属性与内涵,密切结合数据挖掘技术与心理因素生理化的研究思路,并充分利用生理特质所提供的结构性数据特点,实现对行为经济学研究中主要心理因素的统计识别与测度,并将其纳入现有的统计分析框架,应用于居民或投资者消费决策或股价预测的研究。本文主要研究了以下几个方面的内容。1.大数据时代带给统计分析的改变。大数据时代,互联网所引爆的信息革命,层出不穷的各类低成本记录与存储设备的广泛应用,正在颠覆传统的统计数据内涵,当统计分析赖以生存的数据基础发生重大变化时,它会给统计分析和统计学科带来什么?本部分试图从分析范式、分析工具、分析方法和分析结果四个方面去寻求答案。2.大数据时代的行为经济学研究。统计分析作为实证研究的工具,实证分析又是检验经济理论的有效手段,在大数据背景下,当统计与统计分析发生重大变革时,它又会给经济理论带来什么?本部分内容试图依据统计分析的变革来论述经济行为人经济选择数据与生理特征数据的易得性,并通过对生理与心理因素相互关系的考察来论证心理因素数据的替代与转换,阐述大数据背景下统计分析与行为经济学的融合,这种融合将使行为经济学的研究可能跨越实验经济学。3.大数据背景下行为经济统计分析的实现路径。大数据背景下,实现统计分析与行为经济学的融合的路径有两条,一是开发与大数据数据特征相一致的统计分析模型,另一是将非结构性数据结构化,并将其纳入现有的统计分析体系。本文以专业分工创造效率为前提,综合经济可行与技术可行两个方面对统计学适应大数据时代的路径选择进行了论证,其论证结论为本文的后续研究奠定了理论基础。4.大数据背景下心理因素

关键词： 数据结构   算法   计算机软件  

摘要： 数据结构是计算机专业学生的必修课程之一,本文分析了数据结构学习的含义及课程设计的主要内容,提出了学生学好数据结构的具体措施,为学生学会数据结构及计算机专业奠定基础.

关键词： C语言  

ISBN: (纸本)9787302531159

摘要： 本书是为“数据结构”课程编写的教材。系统地介绍了数据结构基础理论知识及算法设计方法，前半部分从抽象数据类型角度讨论了各种基本类型的数据结构及其应用，主要包括：线性表、栈和队列、串、数组和广义表、树与二叉树及图。

摘要： For many real world problems solved using various algorithmic techniques, traditional algorithms are theoretically optimal but as soon as we move on to real world data, based on the nature of data the algorithm efficiency degrades drastically. For massive data which is stored in external memory, algorithms designed for internal memory which are otherwise efficient will fail due to I/O bottleneck. Moreover in most real world scenarios data is dynamic i. e. changes with time. Novel and very different design techniques are needed to manage this dynamic and massive real world data. This thesis contributes to the vast research of such results. In this era of information explosion, the flood of data emerging on daily basis has made data handling and management a very crucial task. In this study, we are looking in to this data from two different perspectives: massive data and dynamic data. For dynamic data, we are considering the implementation of Retroactive data structures specific to some application and then using the proposed implementation to analyse the performance. Dynamic shortest path algorithms modify the existing shortest paths by considering the changes in the underlying graph configuration. Basic approach used in literature to solve this shortest path problem is to dynamize the Dijkstra algorithm: widely used algorithm for the static case. Different solutions already exist for the problem but we are using the concept of retroactive data structures for incorporating the dynamic changes into the solution. In this work algorithms for the different operations of retroactive priority queue are given. Also an algorithm has been proposed for the solution of dynamic shortest path problem as dynamic Dijkstra which uses the retroactive priority queue for its dynamization. The proposed approach is a suitable solution for the dynamic shortest path problem. For massive data, we are extending the novel approach of incremental suffix array construction using Lyndon factoriz

关键词： 人工智能   数据结构   教学改革   知识学习  

摘要： 深度学习理论的突破,极大地推动了人工智能的进一步发展与应用。人工智能的应用广泛,需要在我们的高等教育知识体系中融入人工智能相关知识,让学生感受人工智能应用的科技魅力,激发学生主动学习的热情。通过分析人工智能的本质以及发展中需要解决的问题,讨论了在人工智能背景下数据结构课程教学中如何利用智能信息平台多维度的为学生提辅助学习资源与服务,推动学生主动参与到课程的学习中。将数据结构课程的知识点与人工智能进一步融合,使学生可以更早地认知人工智能、接触人工智能深层知识,为进一步学习、应用人工智能打好基础。

关键词： 时态GIS   数据结构   时空目标   实体  

摘要： 时态GIS的关键核心就在于时空数据结构。本研究主要针对时空过程分类、时空目标标识进行了分析,在此基础上对当下时空数据、属性数据组织方法进行归纳和整理,并对不同特征及深层问题开展探究,以期更好的指导时态GIS数据结构未来研究工作的开展。

关键词： Computer science  

摘要： Pathfinding is an essential part of many applications, including video games and robot navigation. A pathfinding algorithm usually finds a path from the given starting point to the endpoint. Many different implementations of pathfinding solutions exist in the industry. One of the most known and used of these algorithms is A*. A* will find the shortest path from the starting point to the endpoint. Classic A* algorithm can guarantee the shortest path to the desired destination which was introduced in 1968 by Hart, Nilsson, and Raphael. A* is widely used in the game industry to solve the shortest path problem. The A* algorithm utilizes two data structures. A* explores the nodes in the graph from the start position one by one and assign them a value of F which is the sum of G cost and H cost. G Cost is the actual cost of exploring the node from the starting position to the current node, and H cost is the estimation of the cost of from the current node to the goal node. The Open List keeps all of the nodes that are not explored at each iteration of the algorithm. In each iteration, the algorithm removes the node with the least value of F cost and run the algorithm. If the node is not the goal, it will be added to the closed list. Interactions with the open list, which are insert (current node) and remove Min, are the costliest part of the algorithm. It is well known that using a priority queue will increase the performance of this algorithm. A number of priority queues have been used to implement A* and improve the performance of this algorithm. We propose to use a Lazy binary heap and evaluate its performance compared to other data structures. We expect that due to decreasing the size of the current open list, it will outperform other binary heaps.