基于Modelica的CAN通信系统建模仿真

首先对CAN2.0B通信协议做了分析,介绍了Modelica多领域统一建模语言的优越性.并在CAN2.0B通信协议基础上,采用Modelica统一建模语言,建立了CAN总线的电路模型和时序状态模型.通过对改变双绞线长度和通信节点数两种工况进行仿真,确定了模型的可用性.同时分析了CAN总线相关参数对其通信性能的影响,为CAN通信设计和验证提供参考.     

梯图的点可区别全染色（n≡5（mod8））

一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素及其本身所构成的色集合不同。其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法：三角排序。利用该排序的结果证明了当n≡5（mod8）和C4n-1/2＋2〈m≤C4n/2＋2时,梯图Lm≌Pm×P2的点可区别全色数为n。     

梯图的点可区别全染色（n≡4（mod8））

一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素及其本身所构成的色集合不同,其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法：三角排序。利用该排序的结果证明了当n≡4（mod8）和C4n-1/2＋2〈m≤C4n/2＋2时,梯图Lm■Pm×P2的点可区别全色数为n。     

基于非精确图匹配的CAD模型搜索方法

为了弥补现有的三维CAD模型搜索方法难以搜索到不同近似程度的相似模型的缺陷,提出一种基于面属性化邻接图非精确匹配的CAD模型搜索方法.首先提取CAD模型中的B-rep信息将CAD模型转化为面属性化邻接图;然后计算目标模型与被搜索模型的面属性化邻接图之间的顶点相容程度矩阵和边相容程度矩阵,并由此建立2个模型相似程度的度量作为选择不同顶点匹配矩阵M的优化目标函数;在对匹配矩阵M进行连续化松弛后,运用Sinkhorn行列交替规范化方法求解匹配优化问题.实验结果表明,采用该方法能够搜索到不同近似程度的相似模型;并且由于避免了具有NP复杂性的精确图匹配过程,检索效率也能满足实际要求.     

反向工程中三角网格的加工特征识别

为实现反向工程中的特征重构,提出一种在三角网格上由Morse-Smale复形转换为分割面属性邻接图进行加工特征提取的算法.首先通过移动最小二乘曲面法计算网格顶点曲率,构建曲率特性指标函数,消除因网格连接引起的误差,达到降噪的作用;然后在三角网格上建立和简化Morse-Smale复形,精确提取特征线,将网格分割为边界清晰连续的区域,并获得各区域的邻接关系;最后判断关键点和特征线的性质,将Morse-Smale复形直接转换为分割面属性邻接图进行加工特征识别.实验结果表明,该算法准确、高效,而且不需要人工干预,对于反向工程中大规模、带噪声的网格具有较好的识别效果.     

基于图模型的文本分类方法的研究

图模型是文本分类中一种比较新的方法,它可以很好地表达词与词之间的关联信息,弥补了传统的以向量空间为基础的文本分类方法的不足。本文介绍了图模型的定义、权值的计算、图的建立方法及分类方法。实验表明,这种方法是有效可行的。     

Approximation algorithm for coloring of dotted interval graphs

Dotted interval graphs were introduced by Aumann et al. [Y. Aumann, M. Lewenstein, O. Melamud, R. Pinter, Z. Yakhini, Dotted interval graphs and high throughput genotyping, in: ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 339-348] as a generalization of interval graphs. The problem of coloring these graphs found application in high-throughput genotyping. Jiang [M. Jiang, Approximating minimum coloring and maximum independent set in dotted interval graphs, Information Processing Letters 98 (2006) 29-33] improves the approximation ratio of Aumann et al. [Y. Aumann, M. Lewenstein, O. Melamud, R. Pinter, Z. Yakhini, Dotted interval graphs and high throughput genotyping, in: ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 339-348]. In this work we improve the approximation ratio of Jiang [M. Jiang, Approximating minimum coloring and maximum independent set in dotted interval graphs, Information Processing Letters 98 (2006) 29-33] and Aumann et al. [Y. Aumann, M. Lewenstein, O. Melamud, R. Pinter, Z. Yakhini, Dotted interval graphs and high throughput genotyping, in: ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 339-348]. In the exposition we develop a generalization of the problem of finding the maximum number of non-attacking queens on a triangle.     

Fast Parallel Reordering and Isomorphism Testing of k -Trees

Abstract. In this paper two problems on the class of k -trees, a subclass of the class of chordal graphs, are considered: the fast reordering problem and the isomorphism problem. An O(log ² n) time parallel algorithm for the fast reordering problem is described that uses O(nk(n-k)/\kern -1ptlog n) processors on a CRCW PRAM proving membership in the class NC for fixed k . An O(nk(k+1)!) time sequential algorithm for the isomorphism problem is obtained representing an improvement over the O(n ² k(k+1)!) algorithm of Sekharan (the second author) [10]. A parallel version of this sequential algorithm is presented that runs in O(log ² n) time using O((nk((k+1)!+n-k))/log n) processors improving on a parallel algorithm of Sekharan for the isomorphism problem [10]. Both the sequential and parallel algorithms use a concept introduced in this paper called the kernel of a k -tree.     

A high performance algorithm for static task scheduling in heterogeneous distributed computing systems

Effective task scheduling is essential for obtaining high performance in heterogeneous distributed computing systems (HeDCSs). However, finding an effective task schedule in HeDCSs requires the consideration of both the heterogeneity of processors and high interprocessor communication overhead, which results from non-trivial data movement between tasks scheduled on different processors. In this paper, we present a new high-performance scheduling algorithm, called the longest dynamic critical path (LDCP) algorithm, for HeDCSs with a bounded number of processors. The LDCP algorithm is a list-based scheduling algorithm that uses a new attribute to efficiently select tasks for scheduling in HeDCSs. The efficient selection of tasks enables the LDCP algorithm to generate high-quality task schedules in a heterogeneous computing environment. The performance of the LDCP algorithm is compared to two of the best existing scheduling algorithms for HeDCSs: the HEFT and DLS algorithms. The comparison study shows that the LDCP algorithm outperforms the HEFT and DLS algorithms in terms of schedule length and speedup. Moreover, the improvement in performance obtained by the LDCP algorithm over the HEFT and DLS algorithms increases as the inter-task communication cost increases. Therefore, the LDCP algorithm provides a practical solution for scheduling parallel applications with high communication costs in HeDCSs.     

WSN的对偶密钥路径本地搜索算法

无线传感器网络中基于规则网络的密钥预置方案具有预置开销小、寻径快等特点,但这类方案直接对偶密钥建立的概率较低。该文基于已经存在的节点连通集团,针对传感器网络对偶密钥连通图,提出层次连通框架,定义节点层次连通度,给出节点本地搜索算法。仿真结果表明该算法能提高节点的平均密钥连通度。