课程文献中心 更多>>

关键词： 隐私集合运算   数据结构   同态加密   置换矩阵隐私等值检测  

摘要： 随着云计算、物联网、人工智能等技术的不断发展,人们在享受着前所未有的便捷的同时也面临着隐私数据泄露的风险。安全多方计算允许互不信任的参与方在不泄露各自输入的前提下完成联合计算任务,是目前解决数据流通过程中数据安全问题的关键技术。隐私集合运算作为安全多方计算在集合运算场景下的专用协议,可在保证各个参与方输入隐私的情况下实现各类集合操作,包括计算交集、并集以及交集势等。隐私集合运算在隐私保护的数据挖掘、人类基因组研究、社交网络等场景有着广泛的落地应用。本文聚焦于隐私集合运算,主要研究内容包括:第一,隐私集合运算中的关键数据结构。高效的隐私集合运算协议的设计与多种高级的数据结构密切相关。然而,目前隐私集合运算中各种数据结构缺乏系统梳理且无同一平台上的效率对比结果。针对该问题,本文将常用的数据结构分为三类,分别是哈希表、过滤器和不经意键值存储。在明确各类数据结构的基本定义与构造方式的基础上,本文梳理各数据结构的主要功能作用、总结它们在不同协议中的典型应用,并提供各数据结构的性能对比分析与基准测试结果。第二,高效的非平衡隐私集合交集计算协议。在CCS 2018上,Chen等人首次考虑非平衡场景下的隐私集合交集计算协议。然而,该协议基于通用两方计算导致效率不高,且该协议仅仅只是理论上的成果,并没有给出具体实现。针对该问题,本文在基于全同态加密的特征分享协议基础上,结合Tu等人提出的置换矩阵隐私等值检测协议,构造了高效的隐私集合求交集势协议与隐私集合求交集势与和协议。本文的协议的通信复杂度均与大集合大小亚线性相关。此外,本文给出了基于C++的实现。实验结果表明,相较于目前已知最优协议,本文的协议在通信开销和运行时间上均有明显降低。以本文的隐私集合求交集势协议为例,其通信开销降低至目前最优协议的4%-49%,运行时间降低至目前最优协议的36%-50%。

关键词： 课程思政   混合式教学   数据结构  

摘要： 立德树人是我国高等院校教育的根本任务，实现这一根本任务的有效途径之一是推进课程思政建设。高校计算机专业数据结构课程教学改革从教学目标、教学活动组织、教学评价三方面构建了思政视域下具有多维度教学目标，充分体现“两性一度”教学组织形式、全方位立体化教学评价体系的混合式教学模式。实践证明，新常态下混合式教学模式有效提升了学生的专业能力和思想素养，为高校课程思政建设提供了有效路径。

关键词： 应用型人才   混合式教学   《数据结构》课程   实践环节  

摘要： 本文以应用型人才培养为目标，从《数据结构》课程的教学现状入手，在分析《数据结构》课程特点和传统教学中存在的问题基础上，结合线上线下混合式教学模式，提出了混合式教学改革实施方案和改革措施，并对实施效果进行了分析。结果表明，混合式教学能有效解决传统课堂教学的不足，提高学生学习兴趣，加深学生对知识点的理解和掌握，提高学生综合应用知识解决问题的能力和创新思维能力。

关键词： Concolic execution   Dynamic data structure   Concurrency bugs   Cloud9   Multithreaded programs  

摘要： Concolic execution combines concrete execution with symbolic execution to automatically generate test inputs that exercise different program paths and deliver high code coverage. However, when this technique is extended to multithreaded programs with concurrent dynamic data structures, the lack of support for exploring data shapes (the skeleton that consists of symbolic pointers in node-based linked data structures) and efficiently exploring thread interleavings makes it hard to expose concurrency bugs that manifest only when certain dynamic data structure shapes, program paths, and thread interleavings are exercised. This thesis presents techniques to effectively explore data shapes for concurrent dynamic data structures and optimize the exploration efficiency. The approach presented first generates a data shape for a chosen path. By capturing path constraints, we form a shape that satisfies path constraints and exercises the chosen path. In addition, by capturing pointer-pointee relationships, we find how to adjust the shape and find new shapes that also exercise the same path. Finally, using the shapes for individual paths, we find a consistent shape that causes multiple threads to simultaneously follow their chosen paths for exposing concurrency bugs. We generate shapes for each thread separately and provide an integration algorithm to merge the shapes into a consistent shape. This approach does not require the user to write code that constructs data structures to exercise desired paths by individual threads; rather, it automatically collects constraints to generate consistent shapes during the concolic execution. We also present a summarization-based technique to improve the efficiency of concolic testing further. Via unit testing of key functions that implement a concurrent data structure, function summaries are derived that capture data structure shapes that cause various function paths to be exercised. During the concolic testing of interprocedural paths, th

摘要： The purpose of this thesis is to provide practical, high-performance tools for working with string diagrams for the specific application of machine learning. The thesis consists of two main lines of research towards this aim. In Part I, we define a family of categories of differentiable circuits suitable for machine learning. This construction is made in a modular way: we first give an alternative axiomatisation of Reverse Derivative categories which is then used to prove a functional completeness result showing that these circuits are sufficiently expressive. We then show how 'gradient-like' learning can be understood in terms of morphisms of these categories and discuss how to generalise gradient-based methods as applied to neural networks to new settings by varying the 'underlying arithmetic' of models. Part II of the thesis is concerned with how to represent and manipulate large string diagrams, specifically with an eye to those defined in Part I. We develop data structures and define efficient algorithms for tensor and composition of string diagrams in terms of simple linear-algebraic operations. We show that complexity of operations is linear in the size of the resulting diagram and validate our claims with empirical evidence that our approach can handle diagrams constructed from millions of generators. Finally, we give a graphical calculus allowing terms of non-strict monoidal categories to be represented by our data structure, which in turn yields novel proofs of Mac Lane's strictness and coherence theorems.

关键词： 知识图谱   学科知识图谱   数据结构   命名实体识别   可视化交互  

摘要： 随着信息技术的快速发展,人工智能技术广泛用于教育领域中,互联网中涌现出大量的数字化教育资源。同时,教育资源伴随着知识分散、知识间缺少关联的现象,导致知识迷航问题。面对这些类型多样、关系复杂和数量巨大的学科知识,学科知识图谱正是这样一种优秀的知识组织与表示技术。在数据结构学科领域,数据结构知识图谱的研究还存在一些问题,如过度依赖于人工的构建方式,知识图谱的质量不一,缺少用户与知识图谱便捷交互的方式。因此,本文对数据结构知识图谱的构建与其在可视化交互场景中的应用进行研究,主要工作如下:1.提出数据结构知识图谱的半自动构建方法。通过自顶向下与自底向上相结合的方式进行知识图谱构建,利用基于规则的模式匹配和深度学习的方法进行知识抽取与处理;另外,对各环节的结果加以人工辅助筛选,保障构建质量。该方法提高了构建效率、减少构建成本,该数据结构知识图谱具有本体明确、知识层次清晰、质量较好的特点。2.提出数据重标注的数据结构知识图谱实体识别方法。面对数据结构学科领域中实体识别数据集缺乏、已有数据集训练的实体识别模型效果不佳的问题,提出数据重标注方法对已有数据集语料中的实体进行重标注。进一步,采用目前性能优异的ERNIE-Bi LSTM-CRF模型进行实体识别,实验表明识别效果得到一定提升。3.设计实现学科知识图谱可视化交互系统。利用Java Web前后端开发技术实现浏览、查询、操作知识图谱的功能,提供对知识图谱更加便捷的编辑操作方式,促进了知识图谱与用户间双向的数据交互,进一步发挥了知识图谱在学科领域的作用。

关键词： 数据结构   OBE理念   阶梯式实践教学   混合式教学   考核与评价机制  

摘要： 本文针对数据结构教学中存在的课程间关联与衔接性弱、学生综合能力训练不足、课程综合考核单一、教学资源过于碎片化等问题，从构建基于OBE理念的数据结构课程教学设计、线上线下混合式教学模式、“基础、应用、综合、创新”四个维度阶梯式实践教学体系、完善课程考核与评价机制等方面，进行课程教学改革与实践，形成了属于学生自己专有的成果资源库，学生的学习由点到面、由碎片化到系统化、由数据类型到数据结构的思维转变，不断引导学生在主动学习过程中，发现问题、思考问题、解决问题。实践表明，该教学改革有利于提升学生主动参与性、激发学生学习能动性、提高学生实践能力，显著提高学生的主动学习能力、动手能力、解决实际问题能力，达成学生学习的成果，学生满意度较高，教学成效显著。

摘要： This study examines the claim that individuals misinterpret the mean of a dataset (displayed as a scatterplot) more when the convex hull of the dataset is less representative of the data. In addition, this study also tests whether outliers in the data can predict the magnitude of error that individuals make in interpreting the mean of the dataset. Lastly, the study investigates whether individuals' interpretations are predicted better by the mean of the convex hull than by the full dataset's mean. The method used to conduct these investigations is through a survey, followed by several linear regression analyses. Applications of this study include improving the communication of data in economic policy and business contexts, along with broader applications in extending models that heavily rely on agents' interpretations of information: especially bounded rationality and social norm-based models. The results show that convex hull unrepresentativeness correlates positively with error in mean interpretation; however, that the convex hull mean is not predictive of the interpretations' direction. Overall, the study contributes to the field of visual information interpretation by investigating the effect of data structure on its interpretation – an unexplored area of research. This is done while initiating the concretization of bounded rationality in economics, by exploring the idea that individuals perceive a general shape of the information presented to them rather than a detailed, full picture. This can lead to misinterpretations whenever the general shape (convex hull) is not representative of the dataset.

关键词： 图像质量   成像系统   隐藏信息   数据压缩   均方根量化   人眼视觉系统  

摘要： 图像获取、传输、显示时，需要根据人眼视觉属性最大限度保留有用信息。相机原始数据(RAW)保留了相机的初始图像信息，它包含了最初的外部场景信息。RAW格式数据没有利用人眼视觉系统(HVS)进行外界场景的感知，需要通过成像系统将RAW图像转换成人眼视觉系统感知合适的RGB彩色图像。在图像系统中，需要对数据进行压缩、存储、传输。由于不同成像和压缩系统性能存在差异，通常会影响到输出图像的视觉效果。成像系统是为了获取高质量图像，而图像压缩是消除数据冗余便于存储和传输。实现图像高质量获取和对显示前端呈现RAW图像高保真度，是本文研究内容的重点。具体研究内容如下：　　提出了双阶段色阶映射的成像系统框架。针对成像系统中高光溢出现象和图像信息损失问题，首先在图像高光区域，利用RGB通道相关性优化G通道数值，解决高光溢出现象。其次对成像系统的单阶段色阶映射造成部分图像输出动态范围变小和图像高低光区域信息损失，采用双阶段色阶映射消除输出结果与HVS感知不匹配。最后利用第二阶段色阶映射对输出图像的动态范围进行微调，保留图像隐藏的信息，保持最后输出高质量的显示图像。　　提出基于改进Golomb熵编码算法的RAW图像有损压缩。针对Bayer结构RAW图像数据冗余，采用优化星型变换，将RAW图像转成Y,Cb,Cr,△四个分量。首先根据相机图像固有噪声对压缩编码影响，证明抑制相机图像引入的额外噪声熵，采用8-9数字位深可获得近12-16位精度高质量图像。其次通过恰好匹配相机图像固有噪声分布，设计均方根量化算法，消除图像噪声熵编码冗余。最后对RAW图像应用均方根量化算法二次量化，结合熵编码实现RAW图像无损压缩进一步提升压缩比。　　综上所述，本文设计的双阶段色阶映射成像系统有效保留原始图像信息，克服高光溢出现象，提供高质量的输出图像。同时应用抑制噪声和二次量化进行压缩，提高了压缩比。实验结果表明：本文提出的RAW图像压缩算法有效降低数据冗余，与线性量化的无损压缩相比，实现50%的压缩率提升。在bpp为1.5时，提出的有损压缩算法，比JPEG2000压缩算法应用于重构RAW,PSNR提升4dB左右。而在转换后的RGB彩色图像空间内，比JPEG2000压缩算法将RAW图像转换出的RGB彩色图像的PSNR上提升近1.5dB。

摘要： Model checking is a popular technique to verify (software) systems, where calculating properties of Markov Models is common practice. Many algo- rithms exist that achieve this, one of which is state elimination. Optimizing these algorithms provides more accurate results and more performance. In this paper we specifically address the underlying data structures for stor- ing models in memory. We develop a novel data structure, implement it within the framework of an existing model checker and benchmark it against a more traditional object-oriented data structure. Furthermore, we evalu- ate heuristics regarding the elimination order of states. We show that the data structure used may have a significant impact on performance. Within the realm of Markov Decision Processes, the problem of transition blowup emerges which renders a state elimination algorithm unfit without further optimizations. For Discrete-Time Markov Chains, elimination order has impact on memory usage. However, the effects of a heuristic are highly dependent on the characteristics of the model used.