Analysis of recursive batched interpolation search

For an ordered file of records with uniformly distributed key values, we examine an existing batched searching algorithm based on recursive use of interpolation searches. The algorithm, called Recursive Batched Interpolation Search (RBIS) in this paper, uses a divide-and-conquer technique for batched searching. The expected-case complexity of the algorithm is shown to beO(m loglog (2n/m) +m), wheren is the size of the file andm is the size of the query batch. Simulations are performed to demonstrate the savings of batched searching using RBIS. Also, simulations are performed to compare alternative batched searching algorithms which are based on either interpolation search or binary search. When the file's key values are uniformly distributed, the simulation results confirm that interpolation-search based algorithms are superior to binary-search based algorithms. However, when the file's key values are not uniformly distributed, a straight-forward batched interpolation search deteriorates quickly as the batch size increases, but algorithm RBIS still outperforms binary-search based algorithms when the batch size passes a threshold value.     

Distributed scheduling using simple learning machines

A new approach to develop parallel and distributed algorithms of scheduling tasks in parallel computers is proposed. A game theoretical model with the use of genetic-algorithms based learning machines called classifier systems as players in a game, serves as a theoretical framework of the approach. Experimental study of such a system shows its self-organizing features and the ability of collective behaviour. Following this approach a parallel and distributed scheduler is described. A simple version of the proposed scheduler has been implemented. Results of the experimental study of the scheduler demonstrate its high performance.     

A multiversion cautious scheduler with dynamic serialization constraints for database concurrency control

Let MC stand for a class of logs (i.e., sequences of read/write steps) that are serializable when multiple versions of the data items are maintained in the database. In this paper we propose a new type of multiversion cautions scheduler for database concurrency control, which dynamically imposes serialization constraints, consisting of all rw(read-write)-constraints and a subset of other serialization constraints that is dynamically determined. We shall show that (i) the key step of our scheduler is carried out by checking the acyclicity of a certain directed graph, and hence can be done in polynomial time, (ii) this scheduler achieves a higher degree of concurrency than any existing cautious schedulers such as MCS(MWW) and MCS(MWRW), if concurrency is measured in terms of their fixed point sets, and (iii) it exhibits neither cancellation nor augmentation anomaly. It is also shown that our scheduler immediately grants all write requests.     

On asymptotic distribution on the a-adic integers

We show that the values of a polynomial with a-adic coefficients at integer and rational prime arguments are asymptotically distributed on the a-adic integers and that the integer parts of certain sequences known to be uniformly distributed modulo one, are uniformly distributed on the a-adic integers.     

Planar piecewise linear random motions with jumps

In this paper, we study persistent piecewise linear multidimensional random motions. Their velocities, switching at Poisson times, are uniformly distributed on a sphere. The changes of direction are accompanied with subsequent jumps of random length and of uniformly distributed orientation. In this paper, we obtain some useful properties and formulae of distributions of these processes. In particular, we get these distributions in the cases of jumps with Gaussian and exponential distributions of jump magnitudes.     

Logical form,mathematical practice,and Frege's Begriffsschrift

For over a century we have been reading Frege's Begriffsschrift notation as a variant of standard notation. But Frege's notation can also be read differently, in a way enabling us to understand how reasoning in Begriffsschrift is at once continuous with and a significant advance beyond earlier mathematical practices of reasoning within systems of signs. It is this second reading that I outline here, beginning with two preliminary claims. First, I show that one does not reason in specially devised systems of signs of mathematics as one reasons in natural language; the signs are not abbreviations of words. Then I argue that even given a system of signs within which to reason in mathematics, there are two ways one can read expressions involving those signs, either mathematically or mechanically. These two lessons are then applied to a reading of Frege's proof of Theorem 133 in Part III of his 1879 logic, a proof that Frege claims is at once strictly deductive and ampliative, a real extension of our knowledge. In closing, I clarify what this might mean, and how it might be possible.     

大几何参数的变厚度开顶扁薄壳的非线性屈曲问题的奇摄动解

该文利用修正多重尺度法研究了大几何参数的变厚度的具有刚性中心的开顶扁球壳，在均布载荷作用下的非线性稳定问题．求得了扁壳几何参数k值较大时，本问题的一致有效的渐进解，并进行了余项误差估计．     

Pure adaptive search in monte carlo optimization

Pure adaptive search constructs a sequence of points uniformly distributed within a corresponding sequence of nested regions of the feasible space. At any stage, the next point in the sequence is chosen uniformly distributed over the region of feasible space containing all points that are equal or superior in value to the previous points in the sequence. We show that for convex programs the number of iterations required to achieve a given accuracy of solution increases at most linearly in the dimension of the problem. This compares to exponential growth in iterations required for pure random search.     

A framework for an interactive project scheduling system under limited resources

In this paper, we propose a framework for an interactive project scheduling system under limited resources. The framework includes a modelling module (model) and a scheduling module (scheduler). The modelling module model allows the Decision Maker (DM) to develop his/her own model with features such as alternative operating modes for activities; renewable, nonrenewable and/or doubly-constrained resource constraints; general cash flow patterns, related to the realization of activities or events; and progress payments distributed over the project span. The performance criteria include the maximization of Net Present Value (NPV), and either the minimization of maximum tardiness (when a project due date exists) or the minimization of the project duration (when there is no project due date). The scheduler is developed on a constraint-based scheduling algorithm, which is called Local Constraint Based Analysis (lcba) and which has previously been tested and shown to produce near-optimal results with respect to the criterion of minimizing project duration. The decisions taken in the scheduler consist of determining the start times of activities and the specific operating modes in which they are to be realized. The decisions are taken by activating relevant essential conditions in lcba and in cases where resource conflicts are not resolved, the DM reaches a final decision by testing the alternatives proposed by lcba through a what-if routine. The scheduler represents a realistic scheduling system which is useful not only in the planning phase of a project but can also be employed during the progress of a project for updating the project plan, if necessary. An important feature is that the project plan can be updated by performing the least modification of future commitments. It is possible to freeze the activities already scheduled in the near future while admitting the changes in the activity/network information.     

Reading mathematics for understanding—From novice to expert

As students progress through the college mathematics curriculum, enter graduate school and eventually become practicing mathematicians, reading mathematics textbooks and journal articles appears to become easier and leads to increased proficiency and understanding. This study was designed to begin to understand how mathematically more advanced readers read for understanding in mathematical exposition as it appears in textbooks compared to first-year undergraduate students. Three faculty members and three graduate students participated in this study and read from a first-year graduate textbook in an area of mathematics unfamiliar to each of them. The observed reading strategies of these more mathematically advanced readers are compared to observed reading strategies of first-year undergraduate students from an earlier study. The reading methods of the faculty level mathematicians were all quite similar and were markedly different from those that have been identified for undergraduate students, as well as from those used by the graduate students in this study. A Mathematics Reading Framework is proposed based on this study and previous research documenting the strategies that first-year undergraduate students use for reading exposition in their mathematics textbooks.     

Pure adaptive search in global optimization

Pure adaptive seach iteratively constructs a sequence of interior points uniformly distributed within the corresponding sequence of nested improving regions of the feasible space. That is, at any iteration, the next point in the sequence is uniformly distributed over the region of feasible space containing all points that are strictly superior in value to the previous points in the sequence. The complexity of this algorithm is measured by the expected number of iterations required to achieve a given accuracy of solution. We show that for global mathematical programs satisfying the Lipschitz condition, its complexity increases at mostlinearly in the dimension of the problem.This work was supported in part by NATO grant 0119/89.     

On measures of uniformly distributed sequences and Benford's law

The metric theory of uniform distribution of sequences is complemented by considering product measures with not necessarily identical factors. A necessary and sufficient condition is given under which a general product measure assigns the value one to the set of uniformly distributed sequences. For a stationary random product measure, almost all sequences are uniformly distributed with probability one. The discrepancy is estimated byN ^–1/2log³ N for sufficiently largeN. Thus the metric predominance of uniformly distributed sequences is stated, and a further explanation for Benford's law is provided. The results can also be interpreted as estimates of the empirical distribution function for non-identical distributed samples.     

均布荷载作用下压电材料简支梁的解析解

采用逆解法求解了均布荷载作用下压电材料简支梁的解析解。首先给出应力函数和电位移函数的多项式表达式,进而根据相容方程以及应力和电位移、位移和电势的边界条件,求得了同时考虑材料弹性参数、密度参数和压电参数呈梯度变化时,简支梁在均布荷载作用下的解析解。作为特例还得到了常体力以及材料参数为常数时的解答。并对结果进行了讨论。     

A stochastic and dynamic model for the single-vehicle pick-up and delivery problem

In this paper a stochastic and dynamic model for the Pick-up and Delivery Problem is developed and analyzed. Demands for service arrive according to a Poisson process in time. The pick-up locations of the demands are independent and uniformly distributed over a service region. A single vehicle must transport the demands from the pick-up to the delivery location. Once a demand has been picked up it can only be dropped off at its desired delivery location. The delivery locations are independent and uniformly distributed over the region, and they are independent of the pick-up locations. The objective is to minimize the expected time in the system for the demands. Unit-capacity vehicle and multiple-capacity vehicle variations are considered. For each variation, bounds on the performance of the routing policies are derived for light and heavy traffic. The policies are analyzed using both analytical methods and simulation.     

Improved Self-Stabilizing Algorithms for L(2, 1)-Labeling Tree Networks

The L(2, 1)-labeling problem for a graph G is a variation of the standard graph coloring problem. Here, we seek to assign a label (color) to each node of G such that nodes a distance of two apart are assigned unique labels and adjacent nodes receive labels which are at least two apart. In a previous paper—presented at the 23rd IASTED International Multi-Conference: Parallel and Distributed Computing and Networks, Innsbruck, Austria—we presented, to the best of our knowledge, the first self-stabilizing algorithm which {Δ +  2}-L(2, 1)-labels rooted trees. That algorithm was shown to require an exponential number of moves to stabilize on a global solution (which is not uncommon in self-stabilizing systems). In this paper, we present two self-stabilizing algorithms which {Δ +  2}-L(2, 1)-label a given rooted tree T in only O(nh) moves (where h is the height and n is the number of nodes in the tree T) under a central scheduler. We also show how the algorithms may be adapted to unrooted trees, dynamic topology changes, and consider the correctness of the protocols under the distributed scheduler model.     

在边缘线布载荷作用下开顶扁球壳的非线性稳定问题的奇摄动解

本文利用奇异摄动方法计算了在内边缘线布载荷作用下无刚性中心的开顶扁球壳的非线性稳定问题,得到了几何参数k值较大时本问题的一致有效的渐近解.     

夹层圆板轴对称非线性弯曲和屈曲的样条函数解法

以三次B样条函数为试函数,用配点法计算夹层圆板的非线性弯曲．支座可以是弹性的．夹层板采用Reissner模型．荷载可为多项式型的分布荷载、均布边缘力矩、均布径向压力或均布径向预应力及它们的组合．首次用非线性理论计算了夹层圆板的压曲临界荷载．在均布荷载作用下的结果同幂级数解的结果作了比较,说明样条配点法具有收敛范围大、精度高、编写程序通用的优点．     

On search by address computation

We study the effect of data distribution on address computation data structures for searching, as typified by the priority queue problem. We compare several techniques showing that, in contrast to sorting, neither one nor multilevel bucket methods are uniformly efficient for this task. However, an enhancement of order preserving extendible hashing is shown to behave asymptotically independently of the amount of data and its distribution. Also conclusions regarding multiattribute file structures are presented.     

Implementing pure adaptive search for global optimization using Markov chain sampling

The Pure Adaptive Search (PAS) algorithm for global optimization yields a sequence of points, each of which is uniformly distributed in the level set corresponding to its predecessor. This algorithm has the highly desirable property of solving a large class of global optimization problems using a number of iterations that increases at most linearly in the dimension of the problem. Unfortunately, PAS has remained of mostly theoretical interest due to the difficulty of generating, in each iteration, a point uniformly distributed in the improving feasible region. In this article, we derive a coupling equivalence between generating an approximately uniformly distributed point using Markov chain sampling, and generating an exactly uniformly distributed point with a certain probability. This result is used to characterize the complexity of a PAS-implementation as a function of (a) the number of iterations required by PAS to achieve a certain solution quality guarantee, and (b) the complexity of the sampling algorithm used. As an application, we use this equivalence to show that PAS, using the so-called Random ball walk Markov chain sampling method for generating nearly uniform points in a convex region, can be used to solve most convex programming problems in polynomial time.     

Uniformly Distributed Systems of Elements on Metabelian Lie Rings

In this article, the notion of a uniformly distributed systems of elements on the variety of metabelian Lie algebras is introduced. This notion is analogous to one of a measure preserving systems of elements on group varieties. As the main result of the article, it was shown that on the variety of metabelian Lie algebras a system of elements is primitive iff it is uniformly distributed.