关系数据库的逻辑设计与应用实例

数据库技术重要且应用广泛,文中介绍了数据库的三级模式和二级映像结构,在该结构下关系数据库的逻辑设计内容和设计方法,最后引入具体实例应用实践该方法并对实例作简单分析。     

基于De Bruijn图的De Novo序列组装软件性能分析

随着新一代测序技术的发展,一些新的全基因组组装算法应运而生,特别是针对第三代高通量测序仪产生的海量短序列的组装软件被不断开发出来,这些组装软件渐渐走向市场。但是,由于这些组装软件的适用性和其性能的差别,选择一款性能优良的组装工具或者开发并行高吞吐的组装工具成为了当前面临的一大难题。本文选取基于 De Bruijn 图算法开发的 4 款 De Novo 组装的软件（Velvet、SOAPdenovo、IDBA、ABySS）对 4 种物种的基因组的模拟数据进行测试,并从软件的算法、组装性能和组装质量 3 个方面分析这 4 个软件的性能,同时根据其算法特点推断影响这些软件性能的关键因素,并给出软件的使用建议以及开发并行序列组装工具来组装超大规模的基因数据应该注意的问题。     

参数为k的几乎树中的染色多路割

染色多路割问题源于对等网络中的数据分片,是传统多路割问题的推广。给定颜色相关边赋权图G和G上若干特异顶点的局部染色,将该局部染色扩展到所有顶点上,使得两端点染不同颜色的边的权和最小。对于参数为k的几乎树,给出了多项式时间精确算法。也就是说,染色多路割问题是固定参数可解的,其中的参数k是使得G中任意双连通分支C成为树所要拿掉的最大边数。     

基于OSG的粒子特效仿真研究

针对虚拟现实领域中特殊天气、战斗等场景中需要雾、雨、云、火焰、爆炸等场景特效来提高场景逼真度与兼顾渲染实时性的问题,提出采用基于OSG的粒子系统特效。本文在分析粒子系统实现原理的基础上,利用Open Scene Graph（OSG）2．8．2开源场景图形开发库建立粒子特效系统模块,从而有效地解决特殊场景中对粒子效果的要求。给出一个飞行场景中降雪效果的示例,通过分析帧速率等指标说明OSG可以快速绘制粒子系统。试验结果表明,基于OSG的粒子特效能够很好地满足虚拟现实中对粒子特效逼真度和实时性的要求。     

基于DirectShow的视频监控采集系统

基于DirectShow框架开发视频监控采集系统,充分利用DirectShow与WDM视频采集卡的良好集成特性,采用三层系统架构,在实际应用中取得满意的效果。介绍系统的总体设计和软硬件架构,接着对系统运行流程和具体实现技术进行详细分析,最后总结开发心得和经验。     

基于VRML和JAVA3D的图形协同模式

对于网络三维图形协同系统而言,如何构建在异地、异构CAD系统下能为各设计方所普遍接受的讨论模型是该系统的关键。本文结合VRML的强大表征功能和JAVA3D的强大操作功能,应用了基于VRML模型范本生成JAVA3D世界中的镜像,从而直接在JAVA中对该镜像进行协同浏览的设计模式。根据这一模式,结合即时通讯和电子白板模块,作者实现了一个网络图形协同的原型系统。     

A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements

We introduce a simple, linear time algorithm for recognizing trivially perfect (TP) graphs. It improves upon the algorithm of Yan et al. [J.-H. Yan, J.-J. Chen, G.J. Chang, Quasi-threshold graphs, Discrete Appl. Math. 69 (3) (1996) 247–255] in that it is certifying, producing a P₄ or a C₄ when the graph is not TP. In addition, our algorithm can be easily modified to recognize the complement of TP graphs (co-TP) in linear time as well. It is based on lexicographic BFS, and in particular the technique of partition refinement, which has been used in the recognition of many other graph classes [D.G. Corneil, Lexicographic breadth first search—a survey, in: WG 2004, in: Lecture Notes in Comput. Sci., vol. 3353, Springer, 2004, pp. 1–19].     

Finding a dominating set on bipartite graphs

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O^∗(²n−z), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O^∗(²n/2). Another implication is an algorithm for general graphs whose running time is O(n^1.7088).     

A tree-covering problem arising in integrity of tree-structured data

We introduce and solve a problem motivated by integrity verification in third-party data distribution: Given an undirected tree, find a minimum-cardinality set of simple paths that cover all the tree edges and, secondarily, have smallest total path lengths. We give a linear time algorithm for this problem.