C遗留代码到Matlab的封装

C2M是一个把C语言遗留代码转换为Matlab中使用的mex封装文件的半自动化系统.该系统主要由C2Mmap和C2Mrule这两个彼此独立但又相关的工具构成.C2Mmap是一个半自动化转换工具,帮助用户在Matlab与C语言之间建立映像;C2Mrule为C函数自动生成相关的封装文件.描述了C2Mmap和C2Mrule,用例说明了封装代码的实际过程.     

Exact Algorithms for MAX-SAT

The maximum satisfiability problem (MAX-SAT) is stated as follows: Given a boolean formula in CNF, find a truth assignment that satisfies the maximum possible number of its clauses. MAX-SAT is MAX-SNP-complete and received much attention recently. One of the challenges posed by Alber, Gramm and Niedermeier in a recent survey paper asks: Can MAX-SAT be solved in less than 2ⁿ “steps”? Here, n is the number of distinct variables in the formula and a step may take polynomial time of the input. We answered this challenge positively by showing that a popular algorithm based on branch-and-bound is bounded by O(2ⁿ) in time, where n is the maximum number of occurrences of any variable in the input.When the input formula is in 2-CNF, that is, each clause has at most two literals, MAX-SAT becomes MAX-2-SAT and the decision version of MAX-2-SAT is still NP-complete. The best bound of the known algorithms for MAX-2-SAT is O(m2^m/5), where m is the number of clauses. We propose an efficient decision algorithm for MAX-2-SAT whose time complexity is bound by O(n2ⁿ). This result is substantially better than the previously known results. Experimental results also show that our algorithm outperforms any algorithm we know on MAX-2-SAT.     

一个P2P网络仿真模型

现有的P2P网络仿真器都有其各自的弊端,不能够对现实中的P2p的一些实际应用进行仿真.把P2P网络中的各个元素按实际情况模型化,设计一个能够用于对现有P2P应用进行仿真测试的P2P仿真器是十分必要的.本文设计了一个尽可能真实反映P2P实际运行环境的仿真模型,该仿真模型用于仿真现有的很多P2P应用.该模型根据现实P2P资源共享系统中用户的行为的基本特点设计了Peer的各种属性,包容了现有常见的P2P资源共享应用中peers选择和pieces选择策略,并为进一步设计P2P底层覆盖网络拓扑结构提供了接口.该仿真器初步运行结果表明,它能够反映现实P2P应用中的真实情况.     

A constructive algorithm for the complete set of compensators for two-dimensional feedback system design

In the recent factorization approach to linear feedback system design, it has been found that in order to completely solve a generalized Ω-stabilization problem, a coprime condition in the ring of Ω-stable transfer functions must be solved. In this note, two-dimensional (2- D) systems are considered, and this Ω-stable coprime condition is solved for Ω-stable rings. A well-known 2-D zero-coprime condition is a special case of this condition. This is the first constructive method for obtaining the complete set of solutions, or compensators, for 2-D feedback system design. Some examples of systems treated as 2-D systems are: temporal-spatial, spatial-spatial, delay-differential, multipass, etc.     

对等网络安全访问控制方案

提出一个安全对等访问控制方案,该方案采用两层访问控制策略：一层主要对成员资格进行审核,屏蔽一些不符合对等网络安全要求的成员;另一层基于可信值的访问控制策略,对进入对等网络后的成员行为进行评估,根据评估的可信值来决定赋予该成员访问网络资源的权限。当发现恶意成员时,网络能废除这些成员,实现对等网络的安全访问控制。     

Fast parallel algorithm for distance transform

We present an O((log log N)/sup 2/) -time algorithm for computing the distance transform of an N /spl times/ N binary image. Our algorithm is designed for the common concurrent read concurrent write parallel random access machine (CRCW PRAM) and requires O(N/sup 2+/spl epsi///log log N) processors, for any /spl epsi/ such that 0 < /spl epsi/ < 1. Our algorithm is based on a novel deterministic sampling scheme and can be used for computing distance transforms for a very general class of distance functions. We also present a scalable version of our algorithm when the number of processors is available p/sup 2+/spl epsi///log log p for some p < N. In this case, our algorithm runs in O((N/sup 2//p/sup 2/)+(N/p) log log p + (log log p)/sup 2/) time. This scalable algorithm is more practical since usually the number of available processors is much less than the size of the image.     

Optimal quadtrees for image segments

Quadtrees are compact hierarchical representations of images. In this paper, we define the efficiency of quadtrees in representing image segments and derive the relationship between the size of the enclosing rectangle of an image segment and its optimal quadtree. We show that if an image segment has an enclosing rectangle having sides of lengths x and y, such that 2N-1 × max (x, y) ? 2N, then the optimal quadtree may be the one representing an image of size 2N × 2N or 2N+1 × 2N+1. It is shown that in some situations the quadtree corresponding to the larger image has fewer nodes. Also, some necessary conditions are derived to identify segments for which the larger image size results in a quadtree which is no more expensive than the quadtree for the smaller image size.     

Sufficient optimality conditions for Pontryagin extremals

L₁-local optimality of a given control (·) in an optimal control problem for an affine control system with bounded controls is investigated. Starting from the Pontryagin Maximum Principle, which is a first-order necessary optimality condition, we develop it in two directions: (1) extending the notions of 1st and 2nd variations of the system along (·), we obtain 1st and 2nd-order sufficient optimality conditions for bang-bang Pontryagin extremals; (2) developing Legendre-Jacobi-Morse-type results for the extended second variation we obtain 2nd-order sufficient optimality conditions for general (bang-bang-singular) type of Pontryagin extremals.     

背包问题的最优并行算法

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2^n/4)^1-ε个并行处理机单元,0≤ε≤1,O(2^n/2)个存储单元,在O(2^n/4(2^n/4)^ε)时间内求解n维背包问题,算法的成本为O(2^n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.     

Structural two-dimensional principal component analysis for image recognition

In this paper, a new technique called structural two-dimensional principal component analysis (S2DPCA) is proposed for image recognition. S2DPCA is a subspace learning method that identifies the structural information for discrimination. Different from conventional two-dimensional principal component analysis (2DPCA) that only reflects within-row information of images, the goal of S2DPCA is to discover structural discriminative information contained in both within-row and between-row of the images. By contrast with 2DPCA, S2DPCA is directly based on the augmented images encoding corresponding row membership, and the projection directions of S2DPCA are obtained by solving an eigenvalue problem of the augmented image covariance matrix. Computationally, S2DPCA is straightforward and comparative with 2DPCA. Like 2DPCA, the singularity problem is completely avoided in S2DPCA. Experiments on face recognition and handwritten digit recognition are presented to show the effectiveness of the proposed approach.     

2D C-Tree Spatial Representation for Iconic Image

The 2D string approaches provide a natural way of constructing iconic indexing for images. The 2D C-string representation with an efficient cutting mechanism is more characteristic of spatial knowledge and efficient in the representation of iconic images. However, the computation of object ranks in a 2D C-string might make the inference of spatial reasoning somewhat complicated. This shortcoming is overcome by the 2D C-tree representation. The 2D C-tree not only keeps the comprehensive spatial knowledge in the original 2D C-string, but also the ordered labeled tree is more suitable for spatial reasoning and image retrieval. The spatial knowledge can be derived directly from the inference rules embedded in the characteristic structure of the 2D C-tree representation.     

Steelmaking technology for a sustainable society

For the reduction of CO₂ emission, two major developments are being conducted in COURSE50 (“ CO₂ Ultimate Reduction in the Steelmaking Process by Innovative Technologies for Cool Earth 50”). The one is separation of CO₂ gas from BFG (Blast Furnace Gas) and recharge of the rest of BFG including H₂ and CO into blast furnace. Hydrogen iron ore reduction technology is also going to be developed. The other one is amplification of H₂ gas from CH₄, for example, in COG (Coke Oven Gas). The produced hydrogen gas will be supplied to the society or the reformed COG will be charged to blast furnace. In addition to these drastic challenging technology developments, a variety of measures for CO₂ reduction is under taken. In the frame of Asia-Pacific Partnership on Clean Development and Climate, the best available technology for energy savings are discussed to be transferred within seven member nations, which has the effect of 1.27 million ton reduction of CO₂ emission a year. By supplying energy saving steel products to society such as high strength steels for automobiles and ships, which realizes the fuel consumption reduction, high performance electrical steels for motors and transformers, which realize electricity loss reduction, and by recycling waste city plastics and tires in steel processes for hydrogen gas generation, chemical raw material conversion and iron ore reduction, etc., it is expected that equivalent 10% reduction of CO₂ gas emission in steel production is counted. In steelmaking process the reduction of refining slags contributes materials use efficiency and less emission of unuseful byproducts. The control and utilization of nonmetallic inclusions, such as deoxidation products, are one of the key technology for obtaining product performance, which is required in the above-mentioned steel products. In order to optimize steelmaking process for these purposes, computational thermodynamics is applied. Optimization of demanganization, and control of chemical composition of nonmetallic inclusions by the use of computational thermodynamics are mentioned.     

A novel method for parallel image processing applications

It is the aim of this paper to introduce a novel method for the calculation of 2-D convolution/correlation for image processing application. The technique combines a recently developed 2-D transform based on the Mersenne numbers with the 2-D Fermat number transform, using the 2-D mixed radix conversion. The resulting combination uses fast two dimensional residue transforms which can be implemented in parallel for high speed and high throughput rate. The technique is suitable for parallel calculation of 2-D convolution/correlation for digital image processing applications purposes.     

二维离散小波提升变换算法的并行结构设计

提出了一种二维离散小波提升变换（2DDWT）的2×2并行结构。该结构充分利用了2DDWT算法固有的行并行、列并行、行列并行的三种并行性,有效提高了算法执行速度,同时显著降低了硬件存储需求。处理N×N图像的时间为N2/4+N/2+1,系统存储需求为3N。FPGA实现结果证明了本设计的正确性和有效性。     

Plasma planarization for sensor applications

Filling trenches in silicon using phosphosilicate glass (PSG) provides many possibilities for novel device structures for sensors and actuators. This paper describes a plasma planarization technique that provides fully planarized PSG filled silicon trenches for sensor applications. The technique consists of planarizing the substrate using two photoresist layers and plasma etching-back. The lower resist layer is the AZ5214 image reversal resist, which is patterned and then thermally cured. The upper resist layer is a global HPR204 coating. The plasma etching-back is carried out using CHF₃/C₂F ₆ gas mixture with an O₂ addition. It is shown that by using the image reversal photoresist approach, fully planarized surface coating can be obtained without resorting to an additional mask. By adding 25 sccm (14%) O₂ into the 137 sccm CHF₃+18 sccm C₂F₆ gas mixture, the etch rates for the photoresist and PSG can be matched. Process optimization for the two layer resist coating and plasma etching is discussed     

Exact Algorithms for Graph Homomorphisms

Graph homomorphism, also called H-coloring, is a natural generalization of graph coloring: There is a homomorphism from a graph G to a complete graph on k vertices if and only if G is k-colorable. During recent years the topic of exact (exponential-time) algorithms for NP-hard problems in general, and for graph coloring in particular, has led to extensive research. Consequently, it is natural to ask how the techniques developed for exact graph coloring algorithms can be extended to graph homomorphisms. By the celebrated result of Hell and Nesetril, for each fixed simple graph H, deciding whether a given simple graph G has a homomorphism to H is polynomial-time solvable if H is a bipartite graph, and NP-complete otherwise. The case where H is the cycle of length 5, is the first NP-hard case different from graph coloring. We show that for an odd integer , whether an input graph G with n vertices is homomorphic to the cycle of length k, can be decided in time . We extend the results obtained for cycles, which are graphs of treewidth two, to graphs of bounded treewidth as follows: if H is of treewidth at most t, then whether input graph G with n vertices is homomorphic to H can be decided in time .     

A numerical method for exact boundary controllability problems for the wave equation

The computational approximation of exact boundary controllability problems for the wave equation in two dimensions is studied. A numerical method is defined that is based on the direct solution of optimization problems that are introduced in order to determine unique solutions of the controllability problem. The uniqueness of the discrete finite-difference solutions obtained in this manner is demonstrated. The convergence properties of the method are illustrated through computational experiments. Efficient implementation strategies for the method are also discussed. It is shown that for smooth, minimum L²-norm Dirichlet controls, the method results in convergent approximations without the need to introduce regularization. Furthermore, for the generic case of nonsmooth Dirichlet controls, convergence with respect to L² norms is also numerically demonstrated. One of the strengths of the method is the flexibility it allows for treating other controls and other minimization criteria; such generalizations are discussed. In particular, the minimum H¹-norm Dirichlet controllability problem is approximated and solved, as are minimum regularized L²-norm Dirichlet controllability problems with small penalty constants. Finally, a discussion is provided about the differences between our method and existing methods; these differences may explain why our methods provide convergent approximations for problems for which existing methods produce divergent approximations unless they are regularized in some manner.     

Hot-potato algorithms for permutation routing

We develop a methodology for the design of hot-potato algorithms for routing permutations. The basic idea is to convert existing store-and-forward routing algorithms to hot-potato algorithms. Using it, we obtain the following complexity bounds for permutation routing: n×n Mesh: 7n+o(n) steps; 2ⁿ hypercube: O(n²) steps; n×n Torus: 4n+o(n) steps. The algorithm for the two-dimensional grid is the first to be both deterministic and asymptotically optimal. The algorithm for the 2ⁿ-nodes Boolean cube is the first deterministic algorithm that achieves a complexity of o(2ⁿ) steps     

类人足球机器人决策系统的设计

类人机器人足球比赛是机器人足球比赛的最高赛事.类人足球机器人的决策系统是基于独立视觉的自主决策系统,很大程度上决定着比赛的胜败.介绍了自主研发的类人足球机器人决策系统的架构及实现方法,并在此基础上运用有限状态机理论,对单个机器人的自主进攻策略进行了详细分析和研究,真实环境中的实验及比赛结果证明了其有效性.该决策系统的设计及研究工作对基于自主决策的多智能体协作以及服务性机器人决策系统的研究都具有重要的价值.     

Random walks for selected boolean implication and equivalence problems

This paper is concerned with the design and analysis of a random walk algorithm for the 2CNF implication problem (2CNFI). In 2CNFI, we are given two 2CNF formulas f₁{\phi_{1}} and f₂{\phi_{2}} and the goal is to determine whether every assignment that satisfies f₁{\phi_{1}} , also satisfies f₂{\phi_{2}} . The implication problem is clearly coNP-complete for instances of kCNF, k ≥ 3; however, it can be solved in polynomial time, when k ≤ 2. The goal of this paper is to provide a Monte Carlo algorithm for 2CNFI with a bounded probability of error. The technique developed for 2CNFI is then extended to derive a randomized, polynomial time algorithm for the problem of checking whether a given 2CNF formula Nae-implies another 2CNF formula.