基于渐进启发式的《数据结构》线性表的教学

《数据结构》是计算机专业的核心专业课程,在专业课程体系中起着决定性的作用。其中的线性表是该课程的基石,学生在学习时普遍存在"三难"。从教和学的角度出发,按照渐进的方式采用启发式、实例演示式教学,探讨线性表的教学内容和教学过程,藉此帮助学生掌握该课程的学习方法、提高学习兴趣、提升学习效率。     

利用舍伍德算法实现线性表的快速查找

舍伍德算法是概率算法的一种,该文在比较了线性表的顺序存储与链式存储的特点之后,提出了一种较优的数据结构——用数组模拟链表。理论上证明了采用舍伍德算法进行查找运算的时间复尔度为O(n^12),并在计算机上给出了相应数据的模拟。     

线性链表插入元素与删除元素算法的分析

从线性表的链式存储下元素的插入与删除的基本思想出发,分别给出了操作实现的算法思想。分析了算法思想的实现方法,以及具体实现的思路。把实践总结表达出来。还指出了这两个算法的相同点及它们之间存在的差异。最后,总结了算法的实现要点及实现思路。     

带头结点的双向链表算法讨论

本文在现有双向链表算法基础上进行改进，以C语言加图示的方法，介绍了更简便的带头结点双向链表的算法。     

一种基于Fibonacci数的有序线性表查找算法

在设计F ibonacci(菲波那契)查找算法的基础上定义了F ibonacci查找判定树,并利用F ibonacci数的封闭型表达式推导出此种判定树的高度计算公式;证明了在查找成功时,F ibonacci查找的一个优点是总查找长度优于折半查找,F ibonacci查找的另一优点在于访问存放在外存储器上大量的有序表数据时,只需对有序表进行加减运算分割。     

A Radio Coloring of a Hypercube

A radio coloring of a graph G is an assignment of nonnegative integers to its nodes so that each pair of adjacent nodes have color numbers that differ by at least two, and any pair of nodes at distance 2 have different colors. Every graph has a radio coloring by simply assigning the odd integers 1,3, 5, @, but there is then a big difference between the smallest and largest colors. We define the span of a radio coloring of G as one plus the difference between the smallest and largest colors. We study radio colorings of a hypercube with the objective of finding such a coloring with minimum span. We develop a formulation for what we believe is the complete solution to this question in the form of a conjecture.     

Matching Secrets in the Absence of a Continuously Available Trusted Authority

The problem of authentication of mutually suspicious parties is one that is becoming more and more important with the proliferation of distributed systems. In this paper we describe a protocol, based on the difficulty of finding discrete logarithms over finite fields, by which users can verify whether they have matching credentials without revealing their credentials to each other unless there is a match. This protocol requires a trusted third party, but does not require it to be available to the users except when they sign up for the system. Thus it is useful in situations in which a trusted third party exists but is not available to all users at all times.     

CG原画色彩应用浅谈

随着CG(Computer Graphics)技术的普及,CG原画成为许多绘画者的主攻方向。它的应用多在游戏和影视的概念设定中,以2D为主。在游戏中大量的人、物和场景设计都是通过CG原画完成的,用途十分之广。本文通过一些实践和总结,浅谈CG原画的色彩应用。     

Coloring periodicities of two-dimensional mappings

We show how the parameter plane for two-dimensional mappings can be colored according to periodicity to reveal patterns of finite attracting orbits and chaos.     

染色问题的网络特性

染色问题是约束满足问题的一个经典问题,通过分析染色问题的经典实例,发现染色问题具备复杂网络中常见的“小世界”特性,即染色问题所构成的网络中,任意两个节点之间的平均路径长度很小,整个系统呈现出高聚集度的特性,以及节点度的特异分布,这些特性是随机图所不具备的,因此,以随机图做染色问题测试集的传统方法是不完善的,在实验中同时发现,染色问题中最小染色数的大小与系统聚集度的大小密切相关,随聚集度的增大,呈指数关系增大。     

Absence of perspective processing in the pigeon

Pigeons learn no more of the visual projections of a three dimensional object than of an abstract object. They lack the capacity to integrate the transformations of perspective.     

用静态链表和逆序插入算法构成的动态查找表

目前的动态查找表都是树结构,对于结点量很大的情况,其所需存储空间过大且查找效率低的缺点突出.对此.文章设计了一种新的动态查找表,将有序静态链表结构与结点群"逆序插入"算法相结合,相比树结构动态查找表有两个优势:1.所需存储空间小;2.结点群的结点数越多,则动态查找效率越高.该方法的要点是:先将已有结点用静态链表构造出一个有序表,简称"主表".若某"结点群"要插入该主表中,需将该结点群用静态链表构造成一个有序"副表",然后用逆序算法对副表中各结点查找其在主表中的插入点,并从对应的插入点与主表进行链接,最后将链接好的主表和副表一次性收集到一个新的静态链表中.类似的"逆序删除"也可以删除整个副表的结点.     

A DSATUR-based algorithm for the Equitable Coloring Problem

This paper describes a new exact algorithm for the Equitable Coloring Problem, a coloring problem where the sizes of two arbitrary color classes differ in at most one unit. Based on the well known DSatur algorithm for the classic Coloring Problem, a pruning criterion arising from equity constraints is proposed and analyzed. The good performance of the algorithm is shown through computational experiments over random and benchmark instances.     

Approximation Algorithms for the Interval Constrained Coloring Problem

We consider the interval constrained coloring problem, which appears in the interpretation of experimental data in biochemistry. Monitoring hydrogen-deuterium exchange rates via mass spectroscopy experiments is a method used to obtain information about protein tertiary structure. The output of these experiments provides data about the exchange rate of residues in overlapping segments of the protein backbone. These segments must be re-assembled in order to obtain a global picture of the protein structure. The interval constrained coloring problem is the mathematical abstraction of this re-assembly process.     

On the Sum Coloring Problem on Interval Graphs

In this paper we study the following NP-complete problem: given an interval graph G = (V,E) , find a node p -coloring such that the cost is minimal, where denotes a partition of V whose subsets are ordered by nonincreasing cardinality. We present an O(m χ (G) + n log n) time ε -approximate algorithm (ε < 2) to solve the problem, where n , m , and χ #(G) are the number of nodes of the interval graph, its number of cliques, and its chromatic number, respectively. The algorithm is shown to solve the problem exactly on some classes of interval graphs, namely, the proper and the containment interval graphs, and the intersection graphs of sets of ``short' intervals. The problem of determining the minimum number of colors needed to achieve the minimum over all p -colorings of G is also addressed. Received February 1, 1996; revised August 22, 1997.     

Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs

Motivated by applications in batch scheduling of jobs in manufacturing systems and distributed computing, we study two related problems. Given is a set of jobs {J ₁,…,J _n }, where J _j has a processing time p _j , and an undirected intersection graph G=({1,…,n},E), with an edge (i,j) whenever the pair of jobs J _i and J _j cannot be processed in the same batch. We are to schedule the jobs in batches, where each batch completes its processing when the last job in the batch completes execution. The goal is to minimize the sum of job completion times. Our two problems differ in the definition of completion time of a job within a given batch. In the first variant, a job completes its execution when its batch is completed, whereas in the second variant, a job completes execution when its own processing is completed. For the first variant, we show that an adaptation of the greedy set cover algorithm gives a 4-approximation for perfect graphs. For the second variant, we give new or improved approximations for a number of different classes of graphs. The algorithms are of widely different genres (LP, greedy, subgraph covering), yet they curiously share a common feature in their use of randomized geometric partitioning.