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

OPTIMAL EXTRACTION OF IRREDUNDANT MOTIF BASES

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2010年第6期21卷 1035-1047页

作者： Apostolico, Alberto Tagliacollo, Claudia Georgia Inst Technol Coll Comp Atlanta GA 30318 USA Univ Padua Dipartimento Ingn Informaz I-35100 Padua Italy

The problem of extracting a basis of irredundant motifs from a sequence is considered. In previous work such bases were built incrementally for all suffixes of the input string s in O(n(3)), where n is the length of s. Faster, non-incremental algorithms have been based on the landmark approach to string searching due to Fischer and Paterson, and exhibit respective time bounds of O(n(2) log n log vertical bar Sigma vertical bar) and O(vertical bar Sigma vertical bar n(2) log(2) n log log n), with Sigma denoting the alphabet. The algorithm by Fischer and Paterson makes crucial use of the FFT, which is impractical with long sequences. The present paper describes an off-line algorithm for binary strings that takes O(n(2)) time. The algorithm does not need to resort to the FFT and yet its performance is optimal for finite Sigma.

关键词： design and analysis of algorithms pattern matching motif discovery irredundant motif basis

来源：评论

学校读者我要写书评

暂无评论

Randomized Memoryless algorithms for the Weighted and the Generalized k-server Problems

引用

ACM TRANSACTIONS ON algorithms 2020年第1期16卷 14-14页

作者： Chiplunkar, Ashish Vishwanathan, Sundar Indian Inst Technol Delhi New Delhi 110016 India Indian Inst Technol Mumbai 400076 Maharashtra India

The weighted k-server problem is a generalization of the k-server problem wherein the cost of moving a server of weight A through a distance d is beta(i ). d. On uniform metric spaces, this models caching with caches having different page replacement costs. A memoryless algorithm is an online algorithm whose behavior is independent of the history given the positions of its k servers. In this article, we develop a framework to analyze the competitiveness of randomized memoryless algorithms. The key technical contribution is a method for working with potential functions defined implicitly as the solution of a linear system. Using this, we establish tight bounds on the competitive ratio achievable by randomized memoryless algorithms for the weighted k-server problem on uniform metrics. We first prove that there is an alpha(k)-competitive memoryless algorithm for this problem, where alpha(k) = alpha(2)(k-)(1) + 3 alpha(k-1 )+1 alpha(1)= 1. We complement this result by proving that no randomized memoryless algorithm can have a competitive ratio less than alpha(k). Finally, we prove that the above bounds also hold for the generalized k-server problem on weighted uniform metrics.

关键词： design and analysis of algorithms Caching and paging algorithms k-server algorithms

来源：评论

学校读者我要写书评

暂无评论

An Efficient Algorithm for Approximate Pattern Matching with Swaps

An Efficient Algorithm for Approximate Pattern Matching with...

引用

14th Prague Stringology Conference (PSC)

作者： Campanelli, Matteo Cantone, Domenico Faro, Simone Giaquinta, Emanuele Univ Catania Scuola Super Catania I-95123 Catania Italy

ISBN: (纸本)9788001044032

The Pattern Matching problern with Swaps consists in finding all occurrences of a pattern P in a text T, when disjoint local swaps in the pattern are allowed. In the Approximate Pattern Matching problem with Swaps one seeks to compute, for every text location with a swapped match of P the number of swaps necessary to obtain a match at the location. in this paper, we present new efficient algorithms for the Approximatc, Swap Matching problem. In particular, we first present a O(nm(2)) algorithm, where fn is the length of the pattern and n is the length of the text, which is a variation of the BACKWARD-CROSSSAMPLING algorithm, a recent solution to the swap matching problem. Subsequently, we propose an efficient implementation of our algorithm, based on the bit-parallelism technique. The latter solution achieves a O(mn)-time and O(sigma)-space complexity, where a is the dimension of the alphabet. From an extensive comparison with some of the most recent and effective algorithms for the approximate swap matching problem, it turns out that our algorithms are very flexible and achieve very good results in practice.

关键词： approximate pattern matching with swaps nonstandard pattern matching combinatorial algorithms on words design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributing evacuees method to appropriate routes according to variation of person number 6

Distributing evacuees method to appropriate routes according...

引用

IEEE 6th Global Conference on Consumer Electronics (GCCE)

作者： Kimura, Takeru Funahashi, Kenji Itoh, Hirotaka Nagoya Inst Technol Dept Comp Sci Nagoya Aichi Japan

ISBN: (纸本)9781509040452

We often use shortest route to reach safety place when disaster occurs, that is because it takes shorter time than others in many cases. However, it sometimes cause congestion and make evacuation time longer. In this paper we propose a method of selecting appropriate route for each evacuee according to variation of person number. We explain algorithms to select appropriate route for each evacuee and to simulate evacuation using selected route.

关键词： Evacuation route Transportation Emergency management design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling Algorithm to Select Optimal Programme Slots in Television Channels: A Graph Theoretic Approach

引用

International Journal of Applied and Computational Mathematics 2017年第3期3卷 1931-1950页

作者： Pal, Madhumangal Pal, Anita Department of Applied Mathematics with Oceanology and Computer Programming Vidyasagar University Midnapore 721 102 India Department of Mathematics National Institute of Technology Durgapur Mahatma Gandhi Avenue Durgapur 713 209 West Bengal India

In this paper, it is shown that all programmes of all television channels can be modelled as an interval graph. The programme slots are taken as the vertices of the graph and if the time duration of two programme slots have non-empty intersection, the corresponding vertices are considered to be connected by an edge. The number of viewers of a programme is taken as the weight of the vertex. A set of programmes that are mutually exclusive in respect of time scheduling is called a session. We assume that a company sets the objective of selecting the popular programmes in k parallel sessions among different channels so as to make its commercial advertisement reach the maximum number of viewers, that is, a company selects k suitable programme slots simultaneously for advertisement. The aim of the paper is, therefore, to help the companies to select the programme slots, which are mutually exclusive with respect to the time schedule of telecasting time, in such a way that the total number of viewers of the selected programme in k parallel slots rises to the optimum level. It is shown that the solution of this problem is obtained by solving the maximum weight k-colouring problem on an interval graph. An algorithm is designed to solve this just-in-time optimization problem using O(kMn ² ) time, where n and M represent the total number of programmes of all channels and the upper bound of the viewers of all programmes of all channels respectively. The problem considered in this paper is a daily life problem which is modeled by k-colouring problem on interval graph. © 2016, Springer India Pvt. Ltd.

关键词： design and analysis of algorithms Graph colouring Graph theory Interval graphs Modelling

来源：评论

学校读者我要写书评

暂无评论

Approximate swapped matching 20th

引用

20th Conference on Foundations of Software Technology and Theoretical Computer Science

作者： Amir, A Lewenstein, M Porat, E Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel

ISBN: (纸本)3540414134

Let a text string T of n symbols and a pattern string P of rn symbols from alphabet Sigma be given. A swapped version P' of P is a length m string derived from P by a series of local swaps, (i.e. p'(l) <-- p(l+1) and p'(l+1) <-- p(l)) where each element can participate in no more than one swap. The Pattern Matching with Swaps problem is that of finding all locations i of T for which there exists a swapped version P' of P with an exact matching of P' in location i of T. Recently, some efficient algorithms were developed for this problem. Their time complexity is better than the best known algorithms for pattern matching with mismatches. However, the Approximate Pattern Matching with Swaps problem was not known to be solved faster than the pattern matching with mismatches problem. In the Approximate Pattern Matching with Swaps problem the output is, for every text location i where there is a swapped match of P, the number of swaps necessary to create the swapped version that matches location i. The fastest known method to-date is that of counting mismatches and dividing by two. The time complexity of this method is O(n rootm log m) for a general alphabet Sigma. In this paper we show an algorithm that counts the number of swaps at every location where there is a swapped matching in time O(n log m log sigma), where sigma = min(m, \Sigma\). Consequently, the total time for solving the approximate pattern matching with swaps problem is O(f(n, m) + n log m log a), where f (n, m) is the time necessary for solving the pattern matching with swaps problem.

关键词： design and analysis of algorithms combinatorial algorithms on words pattern matching pattern matching with swaps nonstandard pattern matching approximate pattern matching.

来源：评论

学校读者我要写书评

暂无评论

The String Matching algorithms Research Tool 20

The String Matching Algorithms Research Tool

引用

Prague Stringology Conference (PSC)

作者： Faro, Simone Lecroq, Thierry Borzi, Stefano Di Mauro, Simone Maggio, Alessandro Univ Catania Viale A Doria 6 I-95125 Catania Italy Univ Rouen LITIS EA 4108 F-76821 Mont St Aignan France

ISBN: (纸本)9788001059968

String matching is the problem of finding all occurrences of a given pattern in a given text. It is an extensively studied problem in computer science because of its direct application to several areas such as text, image and signal processing, speech analysis and recognition, data compression, information retrieval, computational biology and chemistry. Since 1970 more than 85 string matching algorithms have been proposed, and more than 50% of them in the last ten years. In this paper we present Smart, an efficient and flexible tool designed for developing, testing, comparing and evaluating string matching algorithms. It also provides the most comprehensive survey of online exact single string matching algorithms together with a set of corpora available for testing purposes.

关键词： string matching text processing design and analysis of algorithms testing framework algorithms survey experimental evaluation

来源：评论

学校读者我要写书评

暂无评论

Contextualized mobile game-based learning application for computing education

引用

EDUCATION AND INFORMATION TECHNOLOGIES 2021年第3期26卷 2539-2562页

作者： Yadav, Alok Kumar Oyelere, Solomon Sunday Univ Eastern Finland Sch Comp FIN-80101 Joensuu Finland

This paper intends to present an overview of a mobile game-based learning application, BaghLearn that develops and upskills programming and algorithmic knowledge by cross-curricular capabilities through a traditional world-based game. The focus of this research was to explore the learning effectiveness of BaghLearn on students. Mixed method research approach was applied to collect, process and analyze the research data in which undergraduate students who had some prior knowledge or had taken algorithm courses were instructed to test the mobile game learning application. This study exhibits the idea of integrating learning with contextual mobile game as an effective approach in understanding the influence of games towards cognitive achievements of students in computing education. In addition, there are no major requirements for the use of this application (can be maintained in resource-constrained contexts such as Nepal), which makes it expressively satisfying and useful for students who are relentlessly using mobile devices. Besides, this study evaluated the influence of BaghLearn towards learning of the design and analysis of algorithm course, which is a compulsory course for most undergraduate computing education program. Furthermore, the study findings can be used as a guideline for developing learning solutions and usability evaluation of such solutions, especially for infrastructure-constrained contexts. Students using the BaghLearn opined that the application is easy to use, supportive and lead to improved learning satisfaction.

关键词： BaghLearn Computing education design and analysis of algorithms Game-based learning Nepalese higher education system Usability evaluation

来源：评论

学校读者我要写书评

暂无评论

Bit-(Parallelism)²: Getting to the Next Level of Parallelism

Bit-(Parallelism)<SUP>2</SUP>: Getting to the Next Level of ...

引用

5th International Conference on Fun with algorithms

作者： Cantone, Domenico Faro, Simone Giaquinta, Emanuele Univ Catania Dipartimento Matemat & Informat I-95124 Catania Italy

ISBN: (纸本)9783642131219

We investigate the problem of getting to a higher instruction-level parallelism in string matching algorithms. In particular, starting from an algorithm based on bit-parallelism, we propose two flexible approaches for boosting it with a higher level of parallelism. These approaches are general enough to be applied to other bit-parallel algorithms. It turns out that higher levels of parallelism lead to more efficient solutions in practical cases, as demonstrated by an extensive experimentation.

关键词： string matching bit parallelism text processing design and analysis of algorithms instruction-level parallelism

来源：评论

学校读者我要写书评

暂无评论

Poster: Modified Dynamic Beta RED - A New AQM Algorithm for Internet Congestion Control 23

Poster: Modified Dynamic Beta RED - A New AQM Algorithm for ...

引用

ACM on Internet Measurement Conference (IMC)

作者： Gimenez, Angel Bonastre, Oscar M. Valero, Jose Amigo, Jose M. Miguel Hernandez Univ Elche Spain

ISBN: (纸本)9798400703829

In this work we present a performance study of modified Dynamic Beta RED (mDBetaRED), a new Active Queue Management (AQM) RED-type algorithm based on dynamical variants with the ability to adapt to the characteristics of mixed networks. As well, we rely on real campus traffic traces to build a traffic model on which we evaluate our proposal under the NS3 simulator. The parameters of our AQM algorithm are dynamically adjusted so that the queue length remains stable around a predetermined reference value and according to changing network traffic conditions. We present a performance comparison of mDBetaRED with other AQM algorithms and diverse flows of Internet. Of all the AQM algorithms compared, the mDBetaRED algorithm offers the best throughput while effectively controlling delay and stability.

关键词： design and analysis of algorithms mathematics of computing network algorithms network performance analysis network performance evaluation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：