An O(n+m) Certifying Triconnnectivity Algorithm for?Hamiltonian Graphs

A graph is triconnected if it is connected, has at least 4 vertices and the removal of any two vertices does not disconnect the graph. We give a certifying algorithm deciding triconnectivity of Hamiltonian graphs with linear running time (this assumes that the cycle is given as part of the input). If the input graph is triconnected, the algorithm constructs an easily checkable proof for this fact. If the input graph is not triconnected, the algorithm returns a separation pair.     

A Unified O(log N) and Optimal Sorting Vector Algorithm

A unified vector sorting algorithm(VSA) is proposed,which sorts N arbitrary numbers with c log2 N-bits on an SIMD multi-processor system (SMMP) with p=N^1 ε/u processors and a composite interconnected network in T=c/ε(4 log2 N-2 log2 u 10u) time,where c is an arbitrary positive constant.When ε is an arbitrary small positive constant and u=log2 N,it is an O(log N) algorithm and p=N^1 ε/log2 N;when ε=1/log N and u=2 log2 N,it is an optimal algorithm (p=N/log2 N,T=O(log^2 N),pT=O(N log N));where u=1,c=1 and ε=0.5 (a constant).     

A parallel O(log n) algorithm for the drawing of algebraic curves in an n × n square

A parallel O(log n) algorithm for the drawing of algebraic curves in the digital plane is described. The algorithm contains a systolic subroutine and is implemented in a parallel computer structure called pyramid cellular automaton (PCA). The constructibility of conics and especially of circles (Sakoda's (1981) circle problem) in O(log n) time follows as a special case.     

An O(nlog n)-SPACE Decision Procedure for the Propositional Dummett Logic

We present a tableau calculus for propositional Dummett logic, also known as LC (Linear Chain), where the depth of the deductions is linearly bounded by the length of the formulas to be proved. We then show that it is possible to decide propositional Dummett logic in O(nlogn)-SPACE.     

An $\tilde{O}(m^{2}n)$ Algorithm for Minimum Cycle Basis of Graphs

We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Minimum cycle basis are useful in a number of contexts, e.g. the analysis of electrical networks and structural engineering. The previous best algorithm for computing a minimum cycle basis has running time O(m ^ω n), where ω is the best exponent of matrix multiplication. It is presently known that ω<2.376. We exhibit an O(m ² n+mn ²log n) algorithm. When the edge weights are integers, we have an O(m ² n) algorithm. For unweighted graphs which are reasonably dense, our algorithm runs in O(m ^ω ) time. For any ε>0, we also design an 1+ε approximation algorithm. The running time of this algorithm is O((m ^ω /ε)log (W/ε)) for reasonably dense graphs, where W is the largest edge weight. A preliminary version of this paper appeared in Kavitha et al. (31st International Colloquium on Automata, Languages and Programming (ICALP), pp. 846–857, 2004). T. Kavitha and K.E. Paluch were in Max-Planck-Institut für Informatik, Saarbrücken, Germany, while this work was done.     

An \mathcal O (N \log N) Fast Direct Solver for Partial Hierarchically Semi-Separable Matrices

This article describes a fast direct solver (i.e., not iterative) for partial hierarchically semi-separable systems. This solver requires a storage of $\mathcal O (N \log N)$ and has a computational complexity of $\mathcal O (N \log N)$ arithmetic operations. The numerical benchmarks presented illustrate the method in the context of interpolation using radial basis functions. The key ingredients behind this fast solver are recursion, efficient low rank factorization using Chebyshev interpolation, and the Sherman–Morrison–Woodbury formula. The algorithm and the analysis are worked out in detail. The performance of the algorithm is illustrated for a variety of radial basis functions and target accuracies.     

An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph

Although there are polynomial algorithms of finding a 2-partition or a 3-partition for a simple undirected 2-connected or 3-connected graph respectively,there is no general algorithm of finding a k-partition for a k-connected graph G=(V,E),where k is the vertex connectivity of G.In this paper,an O(k^2n^2) general algorithm of finding a k-partition for a k-connected graph is proposed,where n=|V|.     

An Explicit Formula for the L 2-Discrepancy of (n α)-Sequences

Assume that α is an irrational number with continued fraction expansion [a₀;a₁, . . .] and convergents ,n= 0, 1 . . . . Every positive integer N has a unique expansion N=b₀q₀+b₁q₁+ . . . +b_mq_m, where the digits b_i are nonnegative integers with b₀<a₁,b_i≤a_i+1 and such that b_i=a_i+1 implies b_i−1=0, the so-called Ostrowski expansion of N to base α. On the other hand let c_[0,x) be the characteristic function of the half-open interval [0,x) and let be the L₂-discrepancy of the sequence (nα) mod 1, where {y} denotes the fractional part of the real number y. In this paper, we give an explicit formula for D*⁽²⁾_N(α) entirely in terms of the digits b₀, . . . ,b_m. This formula enables one to compute the L₂-discrepancy in at most O(log⁴N) steps, where the O-constant does not depend on α, while in the classical formulae for the L₂-discrepancy N²/2 calculation steps are necessary. The fastest algorithm so far was found by S. Heinrich [3] and works (for all sequences) in O(N log N) steps. Dedicated to Prof. W. G. Nowak on the occasion of his 50th birthday.     

5(1/4)英寸固定式磁盘机

5(1/4)″固定式磁盘机巳投放市场,满足了用户对外存贮器小形、低价及大容量的需要。本公司最近开发的产品,其外形尺寸与标准的微型软盘驱动器相同,其最大记录容量为26.6MB;位密度为9100bpi;道密度为360 tPi;平均存取时间为85 ms。在开发过程中,主要解决的技术问题是:使热偏道量减至最小(小于 4.sμm);使磁头的浮动高度保持稳定(最内道为0.43μm);缩短平均存取时间;减小印刷电路板的尺寸等等。本文介绍本产品的特点和设计思想以及上述的一些技术问题。     

θ(1) Time Algorithm for Structural Characterization of Multi-Leveled Images and its Applications on a Reconfigurable Mesh Computer

Given a multi-leveled image of size n × n, stored in a reconfigurable mesh computer of the same size one point per processing element (PE). In this paper, we propose a parallel algorithm for structural characterization of all the components of the image. The algorithm is based on the representation of component contour by straight line segments to reduce the volume of data processing. The resulted contours are simultaneously processed using the contour running approach. The pertinent data obtained after the component characterization are used in the filtering application and to develop an algorithm for the convex hull search for all the image components. Our algorithm is assigned to be implemented on a reconfigurable mesh computer and is of θ(1) time complexity.     

具有3(3/4)位显示的A/D转换器接口

带有 LCD 或 LED 显示驱动器的单片A/D 转换器能大大地简化人们对传感器的接口设计。然而较典型的3(1/2)位(1999计数)A/D 转换器的分辨率常常显得精度不高。另外,单片 A/D 转换器的直接驱动输出很难和过程控制所要求的微处理器进行接口。而且3(1/2)A/D 转换器的显示常常被限制在每秒约三次的读数,这样的速度对某些系统的应用似乎慢了一点。     

论(Cl_2BN_3)_n(n=1-4)簇合物

用密度泛函论B3LYP/6-311+G*法,计算(C1_2BN_3)_n(n=1-4)簇合物的结构和性质.发现,多聚体(C1_2BN_3)_n(n=2-4)的优化构型原来是由不同子体系的叠氮基α-N和B原子相连而形成的环状结构。几何参数的比较分析还发现N_α-B、N_α-N_β、N_β-N_Υ和B-Cl的键长与聚合度密切相关,环状构型中B-N_α-B键角总比N_α-B-N_α大。同时计算所有优化构型的振动频率,将其IR谱归类.通过热力学计算,发现簇合物的稳定性为3A>3B;4A>4B.由焓变可知,从单体形成二聚体于热力学不利,而形成最稳定三聚体和四聚体的温度分别达800K和500K仍是有利的.     

用3(1/2)位A/D转换器制成3(4/3)位数字仪表的一种方法

三位半A/D转换器5G14433因有BCD码及其它功能输出,在数字仪表中被广泛地应用。但其满量程输出的数字仅为1999,当仪表的量程超过2000时,便无法利用它的首位,只得使用后三位,将三位半的A/D转换器降格为三位,使仪表的分辨率及精度降低一个数量级。这在器件功能上是一种浪费。如果对线路稍加改进,就可以使它的量程扩大至2000以上。原则上可以用三位半A/D转换器制用四位的仪表。其改造成为显示数字3999的数字仪表最为简单易行。下面介绍本人在研制某控温仪表过程中利用5G14433的一些输出功能,配合少量逻辑电路和电子模拟开关,用三位半的A/D转换器做成测量范围为-199.9～ 399.9℃的数字仪表的一些尝试。图1为本仪器有关部分的电原理图。其中测温桥路的输出信号经放大及非线性校正后送至三位半A/D转换器5G14433,经5G4511译码后显示温度数值。电     

151—3/4型计算机管理程序(GX73)

<正> 一、序言本文介绍151机模块式数据处理系统的通用实时管理程序。151是大型、多机、可扩充,可系列化的数据处理系统,它采用了自动的并行处理和适当的中断系统,既适应通用计算、又满足实时处理的要求。(一)151机的基本结构机器的设计基本上全是模块化的。处理机模块由二个运算器、先行控制及后行送数等组成。全机当前包括二个处理机模块,可扩充到四个。     

循环图C2n(1,2n/3)的2-偶匹配可扩性

文章主要刻画了循环图C2n(1,2n/3)的k-偶匹配可扩性,得出对任意的n(n＞3),C2n(1,2n/3)是2-偶匹配可扩性的.     

Variable Precision Algorithm for the Numerical Computation of the Fermi–Dirac Function ℱj(x) of Order j=−3/2

The purpose of this technical note is to present a piecewise Chebyshev expansion for the numerical computation of the Fermi–Dirac function _–3/2(x), –<x<. The variable precision algorithm we given automatically adjusts the degrees of the Chebyshev expansions so that _–3/2(x) can be efficiently computed to d significant decimal digits of accuracy, for a user specified value of d in the range 1d15.     

Editorial board page for “Digital Creativity (Intelligent Tutoring Media)”, Volume 5, Number 3-4

Abstract

This is a scanned image of the original Editorial Board page(s) for this issue     

4(1/2)、5(1/2)位单片A/D转换器AD7555的应用

AD7555是美国模拟器件公司研制的具有八十年代水平的多功能A/D转换器。我国已有进口并在国产智能仪表中使用。本文重点介绍该器件的实际应用。     

3(1/2)位、4(1/2)位A/D转换器与微机的接口

<正> 随着计算机技术的飞速发展,人们对测量仪表的性能和智能化要求也相应提高。不仅要求对测量仪表采集的信息进行分析和处理;而且也要求对一些数据进行补偿和修正。完成这些功能,目前最有效的方法就是利用计算机技术。一般说来,测量仪表在生产现场所采集的信息,大部分是模拟量信号。对于模拟量信号,必须通过A/D转换器,转变成数字计算机或微处理器能够接受的数字量信号。目前国内批量生产的