课程文献中心 更多>>

关键词： 金课建设   课程思政   数据结构  

摘要： 教育部先后提出的'金课建设'计划和课程思政建设倡议,本文重点分析更具有知识广度和综合素养师资队伍建设的紧迫性,并深入剖析'金课'的高阶性、创新性和挑战度中如何有效地契合课程思政内涵,最后给出'金课'建设中'一核心二管理三评价'的高校计算机类专业课程思政教学模式,并在新工科建设背景下,数据结构课程为例进行教学实践.

摘要： A hash table is a type of data structure that enables insertion and probing of keys having same format with an average complexity of O(1). Some hash tables are also more optimized for working on graphics processors (GPU). The goal of this work is to get familiar with programming for GPU using CUDA(r) framework and Template Numerical Library (TNL - www. tnl-project. org) and use it to realize several hashing approaches. Theoretical part describes the idea of hashing and introduces some data structures and algorithms intended to adapt it for parallel programming for GPU. In practical part, some of these approaches (namely, Cuckoo hashing and HashGraphs) are implemented using TNL. Finally, the implementation is tested. The tests compare its performance on GPU and CPU with the implementation of std:: unordered set container in Standard Template Library of the C++ language. The results show that all tested approaches perform faster on GPU. The fastest approach found was HashGraph of version 1.0. Thus, it is the best examined choice to be used in many applications that require storing and probing unordered keys on GPU.

关键词： 数据结构   算法分析   C++语言  

ISBN: (纸本)9787121417887

摘要： 本书采用程序员偏爱的面向对象C++语言来描述数据结构和算法，并把数据结构原理和算法分析技术有机地结合在一起，系统地介绍了各种类型的数据结构，以及排序和检索的各种方法。作者非常注意对每一种数据结构的不同存储方法及有关算法进行分析比较。书中还引入了一些比较高级的数据结构与先进的算法分析技术，并介绍了可计算性理论的一般知识。书中分别给出了C++实现方法和伪码实现方法，便于读者根据情况选择。

关键词： 计算思维   《数据结构》课程   案例教学  

摘要： 随着信息技术的高速发展,数字化和智能化逐渐成为现代社会的基本形态,计算思维被认为是每个人都应学会与使用的应用态度与技能,越来越受到世界各地学者与教育者的重视,各国相继出台政策将计算思维确立为教育教学的重要目标。《数据结构》课程作为计算机相关专业的基础必修课程内容抽象、难度较大,而该课程的教学大多是以传统的教师讲授式为主,教学效果较差,阻碍了学生后续的学习与思维能力的提升。因此为改变《数据结构》课程教学现状,提升教学效果,同时培养和提高学生的计算思维能力,在已有研究成果的基础上设计有效的面向计算思维的《数据结构》课程教学模式非常有必要。本文首先阐述了计算思维日益受到重视的研究背景,指出研究的目的及本研究拟解决的问题。梳理国内外有关计算思维与《数据结构》课程的文献,界定了计算思维的内涵,确定计算思维五个维度:抽象、分解、算法思维、评估与概括,并指出计算思维能力、《数据结构》课程与案例教学三者的关系。在教学模式设计之前对学生进行计算思维能力现状以及学习态度的调查,得到了对教学模式设计的几点启示:(1)注意调动学生的学习积极性,改变学生对计算机相关课程晦涩难懂的以往认知;(2)教学中采用案例教学模式,选用与实际生活紧密联系的案例提高学生的参与度;(3)在教学中引入计算思维的概念,培养学生的计算思维能力。依据学生思维能力发展的特征在宏观上设计了初级、中级和高级三阶段的教学模式,在微观上教学案例与教学环节的设计融合了计算思维五个维度的具体内容,结合《数据结构》课程内容抽象性等特征,决定采用案例教学模式。随后进行教学实践,选取实验班和对照班进行准实验研究,设计计算思维量表及有关问卷,通过前测确保所选班级满足实验条件,然后实施教学并收集相关实验数据。在结果分析阶段,采用问卷调查与访谈法相结合的方式,从学生计算思维能力提升、教学效果提升及对案例教学模式的态度三方面进行,结果发现:实验班学生的计算思维能力在五个维度上都有不同程度的提升;实验班级的学习成绩明显高于对照班级;实验班学生对于案例教学的满意度较高,从而验证教学模式的有效性:(1)该模式可以有效提升学生的计算思维能力;(2)能够改善教学效果,提升学生的学习成绩;(3)学生对该教学模式的满意度较高,对案例教学有较高的期待。最后指出研究周期较短等研究不足与展望。面向计算思维的《数据结构》课程案例教学模式对于提升学生的计算思维能力与教学效果具有一定的积极作用。希望本研究能够改善《数据结构》课程教学现状,帮助提升大专学生计算思维能力,从而并促进新时代创新型人才的培养。

关键词： 电网设备全路径名称   名称转换   线性神经网络  

摘要： 电网设备全路径名称是电网设备的一种命名规范,其中包含该设备及其应用的各种信息,是电力系统进行调度控制的重要信息来源之一。然而基于不同的标准,同一设备生成的的电网设备全路径名称格式也不尽相同。在本地调度机构使用外部机构的电网设备全路径名称之前,需要将其转换为本地使用的标准才能使用。然而随着电网设备逐渐增加,此项工作也愈发繁琐。论文依据人工神经网络的自学习、联想存储、高速寻找优化解的优点,提出了基于线性神经网络的电网设备全路径名称数据结构化及转换方法。论文主要工作为:首先应用不同数据编码对电网设备全路径名称数据化,应用电力术语字典和改进KMP算法对电网设备全路径名称结构化,使其转化为易于分析处理的结构化数据。然后构建了线性神经网络模型对结构化的电网设备全路径名称进行转换。同时提出了基于余弦相似度的不良数据处理方法和基于min-max标准化的数据归一化处理方法。并设计了神经网络训练方式,和程序实现等问题。最后应用实际数据对本文所研究方法进行实证分析,证明本文所研究方法的有效性。本文研究的基于线性神经网络的电网设备全路径名称数据结构化及转换方法在实际应用中可以自动进行基于不同标准的电网设备全路径名称转换,解决了长久以来依靠人力进行名称转换的问题,同时提高了工作效率。

关键词： C++语言   数据结构  

ISBN: (纸本)9787115554062

摘要： 本书共10章，介绍了数据结构的基本理论及方法，主要有绪论、线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、内部排序，以及算法设计与分析等内容。配备了微课视频、演示动画，扫码即可观看，同时，还提供课堂教学指导、习题课教学指导、实验教学指导、自学辅导、综合训练等资源。

关键词： 布谷鸟哈希表   布隆过滤器   数据结构   Sketch   网络测量  

摘要： 近年来,网络飞速发展对大数据的快速存储、查询和处理的要求越来越高。云计算服务器需要及时、准确地处理并分析大量数据,因此高效的查询模块对于存储系统非常重要。哈希表是一种能进行快速存储、访问的高效数据结构,广泛应用于各种领域,如数据库、网络、存储、安全等。目前存在许多哈希表算法,如:布谷鸟哈希、Peacock Hash、Double Hash、Link Hash和d-left Hash等。但是这些哈希表中依然存在着一些问题,如占用内存空间过大、插入查找等操作时间过长以及插入过程中遇到死循环而导致插入失败需要进行重新哈希。本文主要是在布谷鸟哈希表的踢出机制上进行改进,并将改进的哈希表与另一种数据结构Sketch进行结合,用于数据流测量和查询中。本文通过将哈希表与辅助数据结构布隆过滤器和位图进行结合,并通过预先判定插入时踢出操作是否有必要来减少内存访问次数,构造出了奇偶哈希表(Odd-Even Hash Table)。该结构在布谷鸟哈希表的踢出方法上进行改进,能够实现存储、查找、删除等操作,有效减少了操作时间,极大的提升哈希表的负载率。在相同的内存空间下,奇偶哈希表的负载率最多能达到Link Hash负载率的1.5倍,且负载率均大于其他哈希表;插入时内存访问次数能降低至Linear Hash内存访问次数的一半,且除了Link Hash之外的内存访问次数最少;查找时内存访问次数能够降低至d-left Hash内存访问次数的0.2倍,且除了Link Hash之外奇偶哈希表的内存访问次数最少。本文还将奇偶哈希表与CBFSketch进行结合,形成了OEBSA Sketch(Odd-Even-Based Self-Adaption Sketch),该结构可以根据所需测量的网络流量的大小动态地申请空间,并使用奇偶哈希表代替原有的Counting Bloom Filter来存储Sketch的层数,提高了查询的准确性。为了验证本文方案的有效性和效率,实验将OEBSA Sketch与几个典型的Sketch以及原有CBFSketch进行对比。实验结果表明,该方案Heavy Hitter的精度比其他Sketch提高了4倍,Heavy Changer的精度最大提高了16倍,平均绝对误差与CBFSketch相比减少了约50%,在达到相同平均相对误差时,使用的空间可以减少50%。综上所述,本文提出的奇偶哈希表能节省内存空间,减少查找操作时间,综合性能优于其他几种哈希表。奇偶哈希表的应用OEBSA Sketch提高了原有算法的准确性以及节省了部分内存空间,更适合用于高速网络测量。

关键词： 数据结构   C语言  

ISBN: (纸本)9787302585725

摘要： 本书共8章，涵盖“数据结构”课程的主要内容，同时兼顾题目的广度和深度。每章包括内容概述、典型题解析、自测试题及其参考答案、实验题及其参考答案 (除第1章外)、思考题及其参考答案和主教材习题解答。

关键词： HEVC解码   多核处理平台   并行处理   像素解码重构   数据结构   CTU  

摘要： H.265/HEVC视频编解码标准和H.264标准相比,不仅继承了H.264编解码标准中优良特性,同时也引入了很多新的技术,包括灵活的四叉树划分方式、多角度帧内预测等,这些新技术的引入不仅保证了视频的编解码质量,也减少一半的码率。但是相较于H.264,HEVC标准的处理复杂度也提升了接近2至3倍。另外,由于HEVC面向高清和超高清视频编解码,相较于普通视频,会带来更大的工作量,因此,提供了多种层次的并行编码方法。同时,多核处理器技术的发展也为并行编解码的实现提供了硬件实现基础。因此,基于HEVC编解码标准的并行编解码技术成为了众多国内外学者的研究的课题。本文以包含36个核心的TileraGx36多核处理器为研究平台,研究基于多核处理器的HEVC解码主要模块并行处理技术与实现。论文的主要研究内容有以下几点:(1)设计并实现了一种基于多线程负载均衡的像素解码重构算法,实现了像素解码重构模块的多线程并行解码。由于图像区域的纹理特性和CTU四叉树划分方式的不确定性,导致每个CTU的解码复杂度不同,即解码时间不同,当前线程如果不能解码完当前CTU,那么依赖于当前CTU的待解码CTU就需要等待当前CTU解码完成,此时待解码CTU占有线程资源,导致多核资源的浪费。针对这一问题,提出了一种CTU复杂度估计算法,以CTU的划分深度以及CU到PU的划分方式来确定CTU的解码复杂度,再将相同复杂度的CTU组分配给多个线程进行并行处理,从而实现像素解码重构时的多线程负载均衡。(2)设计并实现了一种基于数据结构优化的并行解码算法。解码过程中CTU的解码状态等信息是访问量最多的数据之一,普通的数组存储不利于多线程的快速读写,针对这一问题,在解码过程中设计了一种使用位图记录CTU解码状态信息的方案,既节省存储空间,又提高了存储和查询效率。四叉树划分是HEVC新引入的CTU划分方式,在数据结构层面建立增强四叉树数据结构,仅在四叉树的叶子节点存储解码信息,同时在解码前,读取位图中存储的CTU解码状态信息,再对当前CTU进行解码。这种增强四叉树数据结构节约了非叶子节点的存储空间,增加了数据索引的效率和稳定性。同时,实现存储、查询等一系列的方法,进一步提高数据读写效率。(3)设计并实现了一种基于读写锁的数据级和任务级融合的并行解码方案。通过在位图和四叉树等数据结构中引入读写锁,实现多个线程同时读取共享数据,多个线程对解码信息的读取会产生资源冲突现象。结合Tilera多核平台的特性,在数据级和任务级融合的并行解码算法的基础上实现了解码效率的进一步提升。本文所有的设计都是在Tilera-Gx36多核处理平台上编程实现,以最新的libde265作为基本参考软件,对包括高清、超高清在内的多个分辨率的视频测试序列进行解码测试。根据实验结果,提出的基于多线程负载均衡的像素解码重构算法相较于前任提出的基于核心模块融合的HEVC并行解码算法,并行加速比平均提升了约7.9%;基于数据结构优化的并行解码方案相较于OWF和基于CTU的HEVC帧内/帧间融合并行解码算法,并行解码加速比分别提升了约22.9%和3.4%;基于读写锁的数据级和任务级融合并行解码算法相较于基于核心模块融合的HEVC并行解码算法,并行加速比平均提升了约11.2%。

关键词： 内部并行性   异步IO   固态硬盘   空间数据结构   批量提交算法  

摘要： 近年来,随着信息技术的飞速发展,人们的日常生活越来越依赖于空间数据,空间大数据时代已经到来。因为空间数据数量大、产生速度快、结构复杂、操作特殊等特点,也为其存储、索引、读写带来了新的挑战。虽然已有的基于固态硬盘的优化读写速度的方法取得了不错的效果,但是它们没有充分利用固态硬盘的内部并行性,且仅适用于单一的某种空间数据结构。针对上述问题,本文设计并实现了具有普适性的批量读写算法,并改造不同的空间数据结构使其更好的适用该算法。在此基础上,还研究了批量提交数与固态硬盘内部特征之间的关系。本文的主要工作如下:首先,提出了基于固态硬盘内部并行性的普适性批量读写算法。该算法首先判断空间数据结构类别,根据类别打开对应的空间索引文件,从而应对不同的数据结构。然后针对固态硬盘会因读写耦合而导致性能下降的特点,设计读和写算法来区分读写操作,并将其保存在Linux操作系统异步IO库的上下文中。再通过批量查询和批量更新算法对读写操作进行批量打包,设置阈值,以确保充分利用固态硬盘的内部并行性并实现读写效率最大化从而实现提升速度的目的。其次,为了在不同数据结构上更好的应用以上算法,提出了基于改造空间数据结构的批量提交算法。根据不同的空间数据结构特征改造其结构。即针对R-树容易导致数据分裂、KD-树容易产生空间树不平衡、四叉树可能导致一个数据存储于多个节点的现象,提出批量更新和批量平衡算法,从而对空间数据结构的构建、查询和更新算法进行改进,使得更适用于固态硬盘的内部并行性结构,提升读写速度。最后,本文通过实验进行性能评估。在3个不同类型的固态硬盘上进行了写操作测试、读操作测试和读写操作测试,分别体现在构建索引测试、查询测试和更新测试上,并与传统的方法进行了对比,实验结果证明了算法的有效性。不同的空间数据结构在使用批量提交算法后,读速度提升2.5到3倍,写速度提升1.5到1.7倍。最后,本文研究了批量提交数与固态硬盘内部特征之间的关系,在两个不同类型的固态硬盘中验证其读写效率的变化,观测其曲线的变化趋势及拐点,总结出当批量提交数等于固态硬盘的通道数时是速度最快的结点。