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

Matching statistics: efficient computation and a new practical algorithm for the Multiple Common Substring Problem

SOFTWARE-PRACTICE & EXPERIENCE 2006年第3期36卷 305-331页

作者： Maass, MG Tech Univ Munich Fak Informat D-85748 Garching Germany

We present new algorithms for computing matching statistics with suffix arrays. We show how the Multiple Common Substring Problem can be solved efficiently in practice with a new approach using matching statistics. This problem consists of finding the common substrings of a set of strings. For the computation of matching statistics we compare seven different methods based on suffix trees and suffix arrays. Most of the suffix array algorithms have an inferior asymptotic worst case running time but a very low memory overhead and small constants in the running time complexity. Our experiments show a good performance in practice. Copyright (c) 2005 John Wiley & Sons, Ltd.

关键词： algorithms and data structures pattern matching Common Substring Problem matching statistics suffix array suffix tree

来源：评论

学校读者我要写书评

暂无评论

Computing 2-Walks in Polynomial Time

引用

ACM TRANSACTIONS ON algorithms 2018年第2期14卷 1–18页

作者： Schmid, Andreas Schmidt, Jens M. Max Planck Inst Informat Campus E1-4 Saarbrucken Germany Tech Univ Ilmenau Ilmenau Germany

A 2-walk of a graph is a walk visiting every vertex at least once and at most twice. By generalizing decompositions of Tutte and Thomassen, Gao, Richter, and Yu proved that every 3-connected planar graph contains a closed 2-walk such that all vertices visited twice are contained in 3-separators. This seminal result generalizes Tutte's theorem that every 4-connected planar graph is Hamiltonian, as well as Barnette's theorem that every 3-connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2-walk is to overcome big overlapping subgraphs in the decomposition, which are also inherent in Tutte's and Thomassen's decompositions. We solve this problem by extending the decomposition of Gao, Richter, and Yu in such a way that all pieces into which the graph is decomposed are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk just mentioned. Its running time is O(n(3)).

关键词： 2-walks 3-connected planar graphs tutte paths 3-trees algorithms and data structures

来源：评论

学校读者我要写书评

暂无评论

Space efficient dynamic orthogonal range reporting

引用

ALGORITHMICA 2007年第2期49卷 94-108页

作者： Nekrich, Y. Univ Bonn Dept Comp Sci D-53117 Bonn Germany

In this paper we present new space efficient dynamic data structures for orthogonal range reporting. The described data structures support planar range reporting queries in time O(log n+k log log (4n/(k+1))) and space O(n log log n), or in time O(log n+k) and space O(nlog(epsilon) n) for any epsilon > 0. Both data structures can be constructed in O(n log n) time and support insert and delete operations in amortized time O(log(2)n) and O(log n log log n) respectively. These results match the corresponding upper space bounds of Chazelle (SIAM J. Comput. 17, 427-462, 1988) for the static case. We also present a dynamic data structure for d-dimensional range reporting with search time O(log(d-1) n+k), update time O(log(d) n), and space O(n log(d-2+epsilon) n) for any epsilon > 0. The model of computation used in our paper is a unit cost RAM with word size log n.

关键词： algorithms and data structures computational geometry orthogonal range searching dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

Approach to Aircraft Handling Qualities Prediction

引用

JOURNAL OF GUIDANCE CONTROL AND DYNAMICS 2024年第11期47卷 2397页

作者： Lampton, Amanda Klyde, David Musso, Dakota Mitchell, David G. Rhinehart, Matthew Syst Technol Inc Hawthorne CA 90250 USA Virgin Galact Flight Controls Mojave CA USA Mitchell Aerosp Res Long Beach CA 90806 USA Naval Air Syst Command NAS Patuxent River Maryland NY 20670 USA

For the decades that followed the publication of the Cooper-Harper report that formalized a standard and universally recognized handling qualities pilot rating scale, researchers have sought to correlate pilot compensation-as well as physical and mental workload-with the assigned rating. A quantitative correlation remains elusive. In recent years, new physiological measurement devices have been developed that, together with software processing tools, can provide accurate measures of psychophysiological measures, including cognitive workload, distraction, and high/low engagement, based on electroencephalogram and electrocardiogram measures (i.e., brain waves and heart rate variability). The pilot compensation referred to in the Cooper-Harper scale is also a function of task performance measures that reflect aircraft characteristics and inceptor activity that reflects upon physical workload. Using a new piloted simulation test database generated in Manned Flight Simulator's containerized rotary-wing simulator with 10 experienced test pilots, a machine-learning-based software algorithm that integrates a disparate mix of pilot-vehicle system, physiological, and task performance measures was used to further develop an approach to predict handling qualities levels and ratings.

关键词： Handling Qualities Aircrafts Support Vector Machine Test Pilots Flight Simulators Rotary Wing algorithms and data structures Structural Modeling and Simulation Generative Adversarial Network Aircraft Flight Control System

来源：评论

学校读者我要写书评

暂无评论

Covering with ellipses

引用

ALGORITHMICA 2004年第1期38卷 145-160页

作者： Efrat, A Hoffmann, F Knauer, C Kriegel, K Rote, G Wenk, C Univ Arizona Dept Comp Sci Tucson AZ 85721 USA Free Univ Berlin Inst Comp Sci D-14195 Berlin Germany

We address the problem of how to cover a set of required points by a small number of axis-parallel ellipses that avoid a second set of forbidden points. We study geometric properties of such covers and present an efficient randomized approximation algorithm for the cover construction. This question is motivated by a special pattern recognition task where one has to identify ellipse-shaped protein spots in two-dimensional electrophoresis;images.

关键词： algorithms and data structures computational geometry approximation algorithm set cover proteomics

来源：评论

学校读者我要写书评

暂无评论

A note on the expected path length of trees with known fringe

引用

INFORMATION PROCESSING LETTERS 1996年第6期59卷 309-315页

作者： DePrisco, R Parlati, G Persiano, G UNIV SALERNO DIPARTIMENTO INFORMAT & APPLICAZ I-84081 BARONISSI ITALY

The path length of a tree, that is, the sum of the lengths of all root-leaf paths, is an important measure of efficiency of the tree. The fringe of a tree is the difference between the lengths of the longest path and the shortest path in the tree. The minimal and the maximal path length of trees with N leaves and given fringe have been well studied. In this paper, we initiate the study of the expected path length of the class of trees with N leaves and fringe Delta by giving a closed expression for the expected path length when Delta = 2.

关键词： algorithms and data structures binary trees path length

来源：评论

学校读者我要写书评

暂无评论

On the optimality of pseudo-polynomial algorithms for integer programming

引用

MATHEMATICAL PROGRAMMING 2023年第1期198卷 561-593页

作者： Fomin, Fedor, V Panolan, Fahad Ramanujan, M. S. Saurabh, Saket Univ Bergen Dept Informat Bergen Norway IIT Hyderabad Dept Comp Sci & Engn Hyderabad India Univ Warwick Coventry W Midlands England HBNI Inst Math Sci Chennai Tamil Nadu India

In the classic Integer Programming Feasibility (IPF) problem, the objective is to decide whether, for a given m x n matrix A and an m-vector b = (b(1) ..... b(m) ), there is a non-negative integer n-vector x such that Ax = b. Solving (IPF) is an important step in numerous algorithms and it is important to obtain an understanding of the precise complexity of this problem as a function of natural parameters of the input. The classic pseudo-polynomial time algorithm of Papadimitriou [J. ACM 1981] for instances of (IPF) with a constant number of constraints was only recently improved upon by Eisenbrand and Weismantel [SODA 2018] and Jansen and Rohwedder [ITCS 2019]. Jansen and Rohwedder designed an algorithm for (IPF) with running time O(m Delta)(m) log(Delta) log (Delta + parallel to b parallel to(infinity)) + O(mn). Here, Delta is an upper bound on the absolute values of the entries of A. We continue this line of work and show that under the Exponential Time Hypothesis (ETH), the algorithm of Jansen and Rohwedder is nearly optimal, by proving a lower bound of n(O(m/log m)) . parallel to b parallel to(O(m))(infinity). We also prove that assuming ETH, (IPF) cannot be solved in time f (m) . (n . parallel to b parallel to(infinity))(O(m/log m)) for any computable function f. This motivates us to pick up the line of research initiated by Cunningham and Geelen [IPCO 2007] who studied the complexity of solving (IPF) with non-negative matrices in which the number of constraints may be unbounded, but the branch-width of the column-matroid corresponding to the constraint matrix is a constant. We prove a lower bound on the complexity of solving (IPF) for such instances and obtain optimal results with respect to a closely related parameter, path-width. Specifically, we prove matching upper and lower bounds for (IPF) when the path-width of the corresponding column-matroid is a constant.

关键词： Integer programming algorithms and data structures

来源：评论

学校读者我要写书评

暂无评论

Sparse Flow Sensor Placement Optimization for Flight-by-Feel Control of 2D Airfoils

引用

AIAA JOURNAL 2024年第10期62卷 3803-3812页

作者： Hollenbeck, Alex C. Grandhi, Ramana Hansen, John H. Pankonien, Alexander M. US Air Force Dept Aeronaut & Astronaut Inst Technol Wright Patterson AFB OH 45433 USA US Air Force Aerosp Syst Directorate Res Lab Wright Patterson AFB OH 45433 USA

This research introduces the Sparse Sensor Placement Optimization for Prediction algorithm and explores its use in bioinspired flight-by-feel control system design. Flying animals have velocity-sensing structures on their wings and are capable of highly agile flight in unsteady conditions, a proof-of-concept that artificial flight-by-feel control systems may be effective. Constrained by size, weight, and power, a flight-by-feel sensory system should have the fewest optimally placed sensors which capture enough information to predict the flight state. Flow datasets, such as from computational fluid dynamics, are discrete, often highly discontinuous, and ill-suited for conventional sensor placement optimization techniques. The data-driven Sparse Sensor Placement Optimization for Prediction approach reduces high-dimensional flow data to a low-dimensional sparse approximation containing nearly all of the original information, thereby identifying a near-optimal placement for any number of sensors. For two or more airflow velocity magnitude sensors, this algorithm finds a placement solution (design point) which predicts angle of attack of airfoils to within 0.10 degrees and ranks within the top 1% of all possible design points validated by combinatorial search. The scalability and adaptability of this algorithm is demonstrated on several 2D model variations in clean and noisy data, and model sensitivities are evaluated and compared against conventional optimization techniques. Applications for this sensor placement algorithm are explored for aircraft design, flight control, and beyond.

关键词： Tactile Sensors Aircraft Flight Control System Aerodynamic Performance Control System Design Aircraft Design Computational Fluid Dynamics algorithms and data structures Optimization Algorithm Bio Inspired Aircraft

来源：评论

学校读者我要写书评

暂无评论

Optimal eviction policies for stochastic address traces

引用

THEORETICAL COMPUTER SCIENCE 2013年 514卷 36-60页

作者： Bilardi, Gianfranco Versaci, Francesco Univ Padua Dept Informat Engn I-35100 Padua Italy

The eviction problem for memory hierarchies is studied for the Hidden Markov Reference Model (HMRM) of the memory trace, showing how miss minimization can be naturally formulated in the optimal control setting. In addition to the traditional version assuming a buffer of fixed capacity, a relaxed version is also considered, in which buffer occupancy can vary and its average is constrained. Resorting to multiobjective optimization, viewing occupancy as a cost rather than as a constraint, the optimal eviction policy is obtained by composing solutions for the individual addressable items. This approach is then specialized to the Least Recently Used Stack Model (LRUSM), a type of HMRM often considered for traces, which includes V - 1 parameters, where V is the size of the virtual space. A gain optimal policy for any target average occupancy is obtained which (i) is computable in time O(V) from the model parameters, (ii) is optimal also for the Fixed capacity case, and (iii) is characterized in terms of priorities, with the name of Least Profit Rate (LPR) policy. An O(log C) upper bound (being C the buffer capacity) is derived for the ratio between the expected miss rate of LPR and that of OPT, the optimal off-line policy;the upper bound is tightened to O(1), under reasonable constraints on the LRUSM parameters. Using the stack-distance framework, an algorithm is developed to compute the number of misses incurred by LPR on a given input trace, simultaneously for all buffer capacities, in time O(log V) per access. Finally, some results are provided for miss minimization over a finite horizon and over an infinite horizon under bias optimality, a criterion more stringent than gain optimality. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Eviction policies Paging Online problems algorithms and data structures Markov chains Optimal control Multiobjective optimization

来源：评论

学校读者我要写书评

暂无评论

Fluid-Structure Interactions of a Fin over a Compliant Panel in Supersonic Flow

引用

AIAA JOURNAL 2024年第12期62卷 4574-4588页

作者： Mills, John G. Dutton, J. Craig Ehrhardt, David A. Elliott, Greg Univ Illinois 104 S Wright St Urbana IL 61801 USA

The fluid-structure interactions of a blunt fin mounted over a compliant panel in Mach 2 flow were investigated. The test geometry consisted of a thin, flexible panel fixed on all edges with a blunt fin with a hemispherically rounded leading edge mounted in a manner that the leading edge of the fin overhung the panel. The blunt fin was also pivoted to several angles of attack with respect to the oncoming flow. This allowed for the study of the dynamic system created by the interactions between the compliant panel and the blunt fin geometries. Both rigid and compliant panel models were used in order to provide a comparison between the flow with and without the dynamics of the compliant panel. High-speed schlieren and surface oil flow visualizations showed that the time-averaged flow remained almost entirely unchanged between the rigid and compliant panels. The instantaneous flow fields, however, showed a highly dynamic system where the compliant panel induced oscillatory shock waves that were both stationary and freely moving. Simultaneous high-speed schlieren visualization and stereo digital-image correlation showed a strong linkage between the motion of the shock waves and the deformation of the panel. This was demonstrated through frequency analysis and modal decomposition of the panel deformation and shock motions.

关键词： Fluid Structure Interaction Separated Flows Shock Waves Unsteady Reynolds Averaged Navier Stokes Structural Kinematics and Dynamics algorithms and data structures Wind Tunnel Tests Dynamic Fluid Structure Interaction Supersonic Flow over a Flat Plate Shock Wave Interaction

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：