低冗余二维码汉字编码研究

随着二维码应用领域的不断扩大,二维码的优化和改进也势在必行。二维码在汉字编码过程中采用定长编码模式,忽略了汉字使用频率对二维码汉字编码效率的影响,存在着较大的编码冗余。采用变长编码算法可以减少高频汉字的编码长度,降低二维码汉字编码的平均编码长度,增加编码容量。首先,结合常用汉字的使用频率,对二维码的汉字编码进行分段处理,分析并制定基于汉字使用频率的变长汉字编码表;其次,在不破坏二维码原有编码结构的情况下,仅对二维码的汉字编码采用变长编码方式;最后,分析并比较二维码定长汉字编码算法和二维码变长编码算法的时间性能和空间性能,给出优化及改进思路。实验证明,二维码变长编码算法可降低二维码汉字编码18.4%的冗余。     

The ski-rental problem with multiple discount options

We propose the ski-rental problem with multiple discount options in which there are n options to rent an equipment. Every option has a rental duration; the longer the duration, the more the discount. This generalizes the standard ski-rental problem where one can only rent or buy. We present a 4-competitive on-line algorithm for our problem and show that no deterministic algorithm can have a smaller competitive ratio when n is large enough. Comparing with the original ski-rental problem, the competitive ratio becomes larger when there are more options.     

Partition arguments in multiparty communication complexity

Consider the “Number in Hand” multiparty communication complexity model, where k players holding inputs x₁,…,x_k∈{0,1}ⁿ communicate to compute the value f(x₁,…,x_k) of a function f known to all of them. The main lower bound technique for the communication complexity of such problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem.In this paper, we study the power of partition arguments. Our two main results are very different in nature:

(i)

For randomized communication complexity, we show that partition arguments may yield bounds that are exponentially far from the true communication complexity. Specifically, we prove that there exists a 3-argument function f whose communication complexity is Ω(n), while partition arguments can only yield an Ω(logn) lower bound. The same holds for nondeterministiccommunication complexity.

(ii)

For deterministic communication complexity, we prove that finding significant gaps between the true communication complexity and the best lower bound that can be obtained via partition arguments, would imply progress on a generalized version of the “log-rank conjecture” in communication complexity. We also observe that, in the case of computing relations (search problems), very large gaps do exist.

We conclude with two results on the multiparty “fooling set technique”, another method for obtaining communication complexity lower bounds.     

Dynamic normal forms and dynamic characteristic polynomial

We present the first fully dynamic algorithm for computing the characteristic polynomial of a matrix. In the generic symmetric case, our algorithm supports rank-one updates in O(n²logn) randomized time and queries in constant time, whereas in the general case the algorithm works in O(n²klogn) randomized time, where k is the number of invariant factors of the matrix. The algorithm is based on the first dynamic algorithm for computing normal forms of a matrix such as the Frobenius normal form or the tridiagonal symmetric form. The algorithm can be extended to solve the matrix eigenproblem with relative error 2^−b in additional O(nlog²nlogb) time. Furthermore, it can be used to dynamically maintain the singular value decomposition (SVD) of a generic matrix. Together with the algorithm, the hardness of the problem is studied. For the symmetric case, we present an Ω(n²) lower bound for rank-one updates and an Ω(n) lower bound for element updates.     

A distributed control scheme for multiple robotic vehicles to make group formations

This paper presents a novel distributed control scheme of multiple robotic vehicles. Each robotic vehicle in this scheme has its own coordinate system, and it senses its relative position and orientation to others, in order to make group formations. Although there exists no supervisor and each robotic vehicle has only relative position feedback from the others in the local area around itself, all the robotic vehicles are stabilized, which we have succeeded in proving mathematically only in the cases where the attractions between the robots are symmetrical. Each robotic vehicle especially has a two-dimensional control input referred to as a “formation vector” and the formation is controllable by the vectors. The validity of this scheme is supported by computer simulations.     

Ramsey数R（3,28）新下界的并行计算*

寻找有效的参数集,构造素数阶循环图,用并行算法获得二色Ramsey数R（3,q）的新下界:R（3,28）≥164。     

北部湾盆地流沙港组湖相烃源岩的差异

北部湾盆地是中国近海重要的富油盆地,油气发现主要集中于涠西南凹陷、乌石凹陷和福山凹陷,探明原油地质储量约为4.05×10⁸t,但各个主要凹陷的探明油气地质储量存在显著差异。北部湾盆地各凹陷的油气富集程度与其湖相烃源岩的差异密切相关,从涠西南凹陷到乌石凹陷,再到迈陈凹陷和福山凹陷,古近系流沙港组烃源岩的品质总体下降,烃源岩的有机质丰度降低,有机质类型从以腐泥型为主变成以混合型占优势,烃源岩的生烃潜力下降。分析表明,尽管北部湾盆地流沙港组烃源岩在形成期各凹陷普遍具有较高的古湖泊有机质生产力,但各凹陷的有机质来源仍然存在差异,有机质保存条件也存在差异,从涠西南凹陷到乌石凹陷,再到迈陈凹陷、福山凹陷和海中凹陷,湖相藻类来源的有机质减少,陆生高等植物来源的有机质增加,有机质保存条件具有变差的趋势。     

下寒武统优质烃源岩的地球化学特征与形成机制——以鄂西地区天柱山剖面为例

全球范围下寒武统发育的黑色泥岩是一套重要的优质烃源岩。该套烃源岩分布广,但在不同地区厚度和质量差异大,重建其沉积与发育模式对预测优质烃源岩的分布具有重要意义,并可为页岩气勘探提供指导。通过对鄂西地区天柱山剖面下寒武统烃源岩样品开展有机碳、主量元素、微量元素等地球化学分析测试,探讨古气候、古生产力和古海洋环境等对优质烃源岩形成的控制作用,分析下寒武统优质烃源岩的沉积模式、发育机制以及生物活动和海洋环境变化与优质烃源岩形成的耦合关系,结果表明,天柱山剖面下寒武统优质烃源岩段具有高TOC含量（2.63%~8.76%）、高化学蚀变指数（68~76）和高生物来源Ba （平均含量为1 392×10^-6）的特点,且高度富集氧化-还原敏感元素（Mo、U和V）。V/Cr比值、U/Th比值和V/Sc比值指示天柱山剖面下寒武统的水体经历了从硫化缺氧环境到次氧化环境再到氧化环境的变化,与Mo、U富集因子之比指示的氧化-还原环境变化特征相一致。TOC含量与Al、Si、生物来源Ba含量的相关性表明陆源输入对烃源岩有贡献。δ¹³C的变化反映了海平面升降对生物生存环境有影响。研究认为,鄂西地区早寒武世海水的硫化缺氧和表层海洋生产力高是导致有机质大量埋藏、形成优质烃源岩的关键。