检索结果-内蒙古大学图书馆

Conference on Spatial Light Modulators

作者： Lueder, E Display Res Labs San Diego CA USA

ISBN: (纸本)0819441716

The electro-optical analog processor for discrete algorithms like the discrete Fourier transform (DFT) or filtering contains as components an LCD as picture source, a lens array for the duplication of the picture, a 2nd LCD or a mask as multiplier and a sensor array for the addition of the results. It works with incoherent light. The components perform a massive parallel processing the speed, bandwidth and data rate of which are discussed. The set of space discrete equations of the algorithms such as a DFT are translated into the architecture of a compact processor sized 8,5 cm in diameter and 17 cm long. The microlenses and the multiplier are clamped together tightly which renders them immune against vibrations and shocks. Examples for the DFT and for a DCT are given. The errors lie in the range of 4% to 11%, the latter for a 2-bit only processing.

关键词： electro-optical signal processing analog processing incoherent light processor discrete algorithms

来源：评论

学校读者我要写书评

暂无评论

Concomitant Group Testing

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第10期70卷 7179-7192页

作者： Bui, Thach V. Scarlett, Jonathan Natl Univ Singapore Dept Comp Sci Singapore 117417 Singapore Natl Univ Singapore Fac Engn Singapore 117575 Singapore Natl Univ Singapore Dept Math Dept Comp Sci Singapore 117417 Singapore Natl Univ Singapore Inst Data Sci Singapore 117417 Singapore

In this paper, we introduce a variation of the group testing problem capturing the idea that a positive test requires a combination of multiple "types" of items. Specifically, we assume that there are multiple disjoint semi-defective sets, and a test is positive if and only if it contains at least one item from each of these sets. The goal is to reliably identify all of the semi-defective sets using as few tests as possible, and we refer to this problem as Concomitant Group Testing (ConcGT). We derive a variety of algorithms for this task, focusing primarily on the case that there are two semi-defective sets. Our algorithms are distinguished by (i) whether they are deterministic (zero-error) or randomized (small-error), and (ii) whether they are non-adaptive, fully adaptive, or have limited adaptivity (namely, 2 or 3 stages). Both our deterministic adaptive algorithm and our randomized algorithms (non-adaptive or limited adaptivity) are order-optimal in broad scaling regimes of interest, and improve significantly over baseline results that are based on solving a more general problem as an intermediate step (e.g., hypergraph learning).

关键词： Testing Drugs Standards Diseases Decoding Chemicals Upper bound Group testing sparsity discrete algorithms information-theoretic bounds

来源：评论

学校读者我要写书评

暂无评论

Storage controlled pile-up systems, theoretical foundations

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1997年第3期103卷 515-530页

作者： Rethmann, J Wanke, E UNIV DUSSELDORF DEPT COMP SCID-40225 DUSSELDORFGERMANY

This paper presents the theoretical foundations for controlling pile-up systems. A pile-up system consists of one or more stacker cranes picking up bins from a conveyor and placing them onto pallets with respect to costumer orders. The bins usually arrive at a conveyor from an orderpicking system. We give a mathematical definition of the pile-up problem, define a data structure for control algorithms, introduce polynomial time algorithms for deciding whether a system can be blocked by making bad decisions, and show that the pile-up problem is in general NP-complete. For pile-up systems with a restricted storage capacity or with a fixed number of pile-up places the pile-up problem is proved to be solvable very efficiently. (C) 1997 Elsevier Science B.V.

关键词： computational analysis complexity discrete algorithms

来源：评论

学校读者我要写书评

暂无评论

Decentralized redistribution for cooperative patrol

引用

INTERNATIONAL JOURNAL OF ROBUST AND NONLINEAR CONTROL 2008年第2期18卷 165-195页

作者： Moore, Brandon J. Passino, Kevin M. Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA

This paper addresses the problem of enabling a group of autonomous vehicles to effectively patrol an environment significantly larger than their communication and sensing radii. Our formulation uses an a priori spatial decomposition of the environment into smaller areas in order to provide a framework for the allocation of vehicles to different parts of the environment. We develop a distributed cooperative control algorithm that transfers vehicles between these areas based on only local information and prove that it achieves the proper environment-wide distribution of vehicles within a finite time interval. Various applications are discussed and simulations are included to illustrate convergence dynamics as well as to quantify practical performance as a function of problem parameters. Copyright (c) 2007 John Wiley & Sons, Ltd.

关键词： cooperative control resource balancing discrete algorithms

来源：评论

学校读者我要写书评

暂无评论

Casting an Object with a Core

引用

ALGORITHMICA 2009年第1期54卷 72-88页

作者： Ahn, Hee-Kap Bae, Sang Won Cheng, Siu-Wing Chwa, Kyung-Yong POSTECH Dept Comp Sci & Engn Pohang South Korea Korea Adv Inst Sci & Technol Div Comp Sci Taejon 305701 South Korea HKUST Dept Comp Sci & Engn Pohang Hong Kong Peoples R China

This paper addresses geometric problems in manufacturing objects by casting. In casting, molten material is poured into the cavity of the cast and allowed to solidify, after which the cast is removed. The cast has two cast parts to be removed in opposite directions. To manufacture more complicated objects, the cast may also have a side core to be removed in a direction skewed to the removal directions for the cast parts. We address the following problem: Given an object and the removal directions for the cast parts and the side core, can a cast be constructed such that the cast parts and the side core can be removed in the directions specified without colliding with the object or each other? We give necessary and sufficient conditions for the problem, as well as a discrete algorithm to perform the test in O(n(3) log n) time for polyhedral objects, where n is the number of vertices, edges, and facets. If the test result is positive, a cast with complexity O(n(3)) can be constructed within the same time bound. We also present an example to show that a cast may have Omega(n(3)) complexity in the worst case.

关键词： Manufacturing Casting Core discrete algorithms

来源：评论

学校读者我要写书评

暂无评论

Mutual search

引用

JOURNAL OF THE ACM 1999年第4期46卷 517-536页

作者： Buhrman, H Franklin, M Garay, JA Hoepman, JH Tromp, J Vitányi, P Ctr Wiskunde & Informat NL-1098 SJ Amsterdam Netherlands Xerox Corp Palo Alto Res Ctr Palo Alto CA 94304 USA Bell Labs Murray Hill NJ 07974 USA Univ Twente Dept Comp Sci NL-7500 AE Enschede Netherlands Univ Amsterdam Amsterdam Netherlands

We introduce a search problem called "mutual search" where k agents, arbitrarily distributed over n sites, are required to locate one another by posing queries of the form "Anybody at site i?". We ask for the least number of queries that is necessary and sufficient. For the case of two agents using deterministic protocols, we obtain the following worst-case results: In an oblivious setting (where all pre-planned queries are executed), there is no savings: n - 1 queries are required and are sufficient. In a nonoblivious setting, we can exploit the paradigm of "no news is also news" to obtain significant savings: in the synchronous case 0.586n queries suffice and 0.536n queries are required;in the asynchronous case 0.896n queries suffice and a fortiori 0.536n queries are required;for o(root n) agents using a synchronous deterministic protocol less than n queries suffice;there is a simple randomized protocol for two agents with worst-case expected 0.5n queries and all randomized protocols require at least 0.25n worst-case expected queries. The graph-theoretic framework we formulate for expressing and analyzing algorithms for this problem may be of independent interest.

关键词： coalition forming computational complexity computer networks datastructures discrete algorithms distributed computation mutual search

来源：评论

学校读者我要写书评

暂无评论

The generic combinatorial algorithm for image matching with classes of projective transformations

引用

INFORMATION AND COMPUTATION 2020年 275卷 104550-104550页

作者： Rosenke, Christian Liskiewicz, Maciej Univ Rostock Inst Informat Albert Einstein Str 22 D-18059 Rostock Germany Univ Lubeck Inst Theoret Informat Ratzeburger Allee 160 D-23538 Lubeck Germany

Image matching is an important task arising in video compression, optical character recognition, medical imaging, watermarking and in many others fields. Given two digital images A and B, image matching determines a transformation f for A such that it most closely resembles B. In this paper, we introduce the first general discretization technique that works for the class of projective transformations as well as plenty of its subclasses such as affine transformations and several combinations of scaling, rotation and translation. Based on this, we provide a fully generic image matching algorithm for all these classes that runs in polynomial time. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Digital image matching discrete algorithms Discretization of function spaces Projective transformations Computational geometry

来源：评论

学校读者我要写书评

暂无评论

A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotation

引用

THEORETICAL COMPUTER SCIENCE 2009年第51期410卷 5317-5333页

作者： Hundt, Christian Liskiewicz, Maciej Nevries, Ragnar Univ Rostock Inst Informat D-2500 Rostock 1 Germany Univ Lubeck Inst Theoret Informat Lubeck Germany

The problem of two-dimensional pattern matching invariant under a given class of admissible transformations F is to find matches of transformed versions f (P) of a pattern P in a given text T, for all f in F. In this paper, pattern matching invariant under compositions of real valued scaling and rotation are investigated. We give a new discretization technique for this class of transformations and prove sharp lower and upper bounds on the number of different possibilities to transform a pattern in this way. Subsequently, we present the first efficient pattern matching algorithm invariant under compositions of scaling and rotation. The algorithm works in time O(m(2) n(6)) for patterns of size m(2) and texts of size n(2). We conclude with an experimental section to support the practical use of our results. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Combinatorial pattern matching Digital image matching discrete rotations and scalings discrete algorithms

来源：评论

学校读者我要写书评

暂无评论

Further thoughts on the syntenic distance between genomes

引用

ALGORITHMICA 2002年第2期34卷 157-180页

作者： Pisanti, N Sagot, MF Univ Pisa Dipartimento Informat I-56125 Pisa Italy Univ Marne La Vallee Inst Gaspard Monge Noisy Le Grand France Univ Lyon 1 INRIA Rhone Alpes Lab Biometrie & Biol Evolut F-69622 Villeurbanne France

The syntenic distance between two multi-chromosomal genomes is the minimum number of fusion (union), fission (split), and translocation (exchange) operations necessary to transform a genome into another. Genomes are therefore seen as unlabeled bags of genes and the syntenic distance as the number of moves needed to obtain the same bags. This paper introduces the following new results concerning syntenic distance: Using a direct proof, we solve a conjecture by Liben-Nowell [ 1] for the syntenic diameter size, that is, for the length of the longest optimal move sequence for an instance of size n. showing that it is, in fact, not 2n - 3 but 2n - 4 (an independent and different proof of this was provided by Kleinberg and Liben-Nowell in [2]). The structure of the proof further enables us to characterize the minimum number of translocations an optimal sequence of moves must have. This has important consequences for algorithmical purposes. The result is then generalized to what we call bidimensional syntenic diameter. When the initial instance has more than one component, we suggest a way of performing inter-component moves, something that was not done in previous algorithms. We show however that, even in simple cases with more than two components involved, an optimal solution for a general instance of the problem using such moves is NP-hard to obtain. We introduce, we believe, a simpler, more general and efficient algorithm for obtaining a move sequence that is optimal for the cases that Liben-Nowell and Kleinberg called in [3] nested synteny, exact and linear (this last one is the case addressed in [3]). We sketch an extension of the algorithm which we conjecture may optimally solve the connected nested synteny (without requiring linearity). We prove an inclusion theorem for the general synteny that is an extension of the one shown for linear synteny in [3].

关键词： genome rearrangement genome distance syntenic distance nested synteny syntenic diameter discrete algorithms computational biology

来源：评论

学校读者我要写书评

暂无评论

Strategies for maximizing seller's profit under unknown buyer's valuations

引用

INFORMATION SCIENCES 2000年第1-4期124卷 219-239页

作者： Belegradek, B Kalpakis, K Yesha, Y Univ Maryland Baltimore Cty Dept Comp Sci & Elect Engn Baltimore MD 21250 USA NASA Goddard Space Flight Ctr Ctr Excellence Space Data & Informat Sci Greenbelt MD 20771 USA

Suppose there is a seller that has an unlimited number of units of a-single product for sale. The seller at each moment of time posts a price for his/her product. Based on the posted pricer at each moment of time, a buyer decides whether or not to buy a unit of that product from the seller. The only information about the buyer available to the seller is,the seller's sales history. Further, we assume that the maximal unit price the buyer is willing to pay does not change over time. The question then is how should the seller price his/her product to maximize profits? To address this question, we use the notion of loss functions. Intuitively, a loss function is a measure, at each moment of time, of the lost opportunity to make a profit. In particular, we provide a polynomial-time algorithm that finds a:pricing algorithm (strategy) for the seller that minimizes the average (total) losses over time, Further, we provide efficient algorithms for finding pricing strategies for maximizing the cumulative seller's profits when the sales period is limited, there is a limited supply of the product for sale, and the buyer's valuation is a non-increasing function of time, where those functions are known to the seller. We also present preliminary results on pricing strategies that minimize the maximum loss, and we show show that there is no strategy minimizing both the total loss and the maximum loss at the same time. (C) 2000 Elsevier Science Inc. All rights reserved.

关键词： pricing strategies market models electronic commerce computational learning theory dynamic programming search trees discrete algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：