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

5th International Symposium on IT in Medicine and Education, ITME 2013

作者： Zheng, Yunping Sarem, Mudar School of Computer Science and Engineering South China University of Technology 510006 Guangzhou China School of Software Engineering Huazhong University of Science and Technology 430074 Wuhan China

ISBN: (纸本)9789400776173

The ACM/ICPC (ACM International Collegiate Programming Contest) is famous as the world's largest and highest level of international collegiate programming contest. In this paper, by considering some problems of the traditional teaching mode of the "design and analysis of algorithms" (which is abbreviated as "algorithms"), we propose a new ACM/ICPC-based teaching reform mode of the "algorithms". Some principles and characteristics of the exercises based on the ACM/ICPC are presented. And, some merits and features of our reform mode are analyzed. Also, by giving the shortcomings of the ACM online judging system, the corresponding reason and the solving strategy are presented. The ACM/ICPC-based teaching reform mode of the "algorithms" cultivates the students' interest in participating in the ACM/ICPC, greatly improves the initiative and enthusiasm to learn "algorithms", and strengthens cultivation of the team spirit and creative ability. Our proposed reform mode improves the teaching quality, which achieves the obvious effect. Also, our mode was highly praised and generally welcomed by students. Therefore, it has some demonstrated functions for teaching reform of the "algorithms". © Springer Science+Business Media Dordrecht 2014.

关键词： ACM design and analysis of algorithms ICPC Teaching reform and exploration Traditional teaching mode

来源：评论

学校读者我要写书评

暂无评论

On efficient algorithms for bottleneck path problems with many sources

引用

OPTIMIZATION LETTERS 2024年第5期18卷 1273-1283页

作者： Kaymakov, Kirill V. Malyshev, Dmitry S. Coleman Tech LLC 40 Mira Ave Moscow 129090 Russia Natl Res Univ Higher Sch Econ Lab Algorithms & Technol Networks Anal 136 Rodionova Str Nizhnii Novgorod 603093 Russia

For given edge-capacitated connected graph and two its vertices s and t, the bottleneck (or maxmin\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\max \min $$\end{document}) path problem is to find the maximum value of path-minimum edge capacities among all paths, connecting s and t. It can be generalized by finding the bottleneck values between s and all possible t. These problems arise as subproblems in the known maximum flow problem, having applications in many real-life tasks. For any graph with n vertices and m edges, they can be solved in O(m) and O(t(m, n)) times, respectively, where t(m,n)=min(m+nlog(n),m alpha(m,n))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t(m,n)=\min (m+n\log (n),m\alpha (m,n))$$\end{document} and alpha(center dot,center dot)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha (\cdot ,\cdot )$$\end{document} is the inverse Ackermann function. In this paper, we generalize of the bottleneck path problems by considering their versions with k sources. For the first of them, where k pairs of sources and targets are (offline or online) given, we present an O((m+k)log(n))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O((m+k)\log (n))$$\end{document}-time randomized and an O(m+(n+k)log(n))\documentclass[12pt]{minimal} \usepa

关键词： design and analysis of algorithms Computational complexity Bottleneck path problem

来源：评论

学校读者我要写书评

暂无评论

Dynamic Convex Hulls for Simple Paths

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2025年 1-36页

作者： Brewer, Bruce Brodal, Gerth Stolting Wang, Haitao Univ Utah Kahlert Sch Comp Salt Lake City UT 84112 USA Aarhus Univ Dept Comp Sci Aabogade 34 DK-8200 Aarhus N Denmark

We consider the planar dynamic convex hull problem. In the literature, solutions exist supporting the insertion and deletion of points in poly-logarithmic time and various queries on the convex hull of the current set of points in logarithmic time. If arbitrary insertion and deletion of points are allowed, constant time updates and fast queries are known to be impossible. This paper considers two restricted cases where worst-case constant time updates and logarithmic time queries are possible. We assume all updates are performed on a deque (double-ended queue) of points. The first case considers the monotonic path case, where all points are sorted in a given direction, say horizontally left-to-right, and only the leftmost and rightmost points can be inserted and deleted. The second case assumes that the points in the deque constitute a simple path. Note that the monotone case is a special case of the simple path case. For both cases, we present solutions supporting deque insertions and deletions in worst-case constant time and standard queries on the convex hull of the points in O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log n)$$\end{document} time, where n is the number of points in the current point set. The convex hull of the current point set can be reported in O(h+logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(h+\log n)$$\end{document} time, where h is the number of edges of the convex hull. For the one-sided monotone path case, where updates are only allowed on one side, the reporting time can be reduced to O(h), and queries on the convex hull are supported in O(logh)\documentclas

关键词： Dynamic convex hull Convex hull queries Simple paths Path updates Deque Theory of computation Computational geometry design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

On the Longest Common Cartesian Substring Problem^†

引用

COMPUTER JOURNAL 2023年第4期66卷 907-923页

作者： Faro, Simone Lecroq, Thierry Park, Kunsoo Scafiti, Stefano Univ Catania Dept Math & Comp Sci Catania Italy Normandie Univ UNIROUEN LITIS F-76000 Rouen France Seoul Natl Univ Seoul South Korea

A Cartesian tree is associated with a string of numbers and is structured as a heap from which the original string can be recovered. Although Cartesian trees have been introduced 40 years ago, the Cartesian tree matching problem appeared very recently. It consists in finding all substrings of given text, which have the same Cartesian tree as that of a given pattern. In this paper, we address the problem of computing the longest common Cartesian substrings of two strings and present three methods for such problem. Our first method is based on a classical suffix tree construction and solves the problem in randomized linear time and linear space, although the space overhead is quite prohibitive in the case of large strings. Our second solution is based on classical dynamic programming, and our third solution is based on a constructive approach. Both of them run in quadratic worst case time but are more space economical in practice. From our experimental results, it turns out that our second solution runs faster than the standard suffix tree solution for short strings, whereas our third solution is more suitable for large strings, when storing a full suffix tree becomes prohibitive.

关键词： Cartesian tree non-standard string matching longest common substring combinatorial algorithm design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

A weak approach to suffix automata simulation for exact and approximate string matching

引用

THEORETICAL COMPUTER SCIENCE 2022年 933卷 88-103页

作者： Faro, Simone Scafiti, Stefano Univ Catania Dept Math & Comp Sci Viale A Doria 6 I-95125 Catania Italy

String matching is one of the most extensively studied problems in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry. In the last few decades a myriad of alternative solutions have been proposed, based on very different techniques. However, automata have always played a very important role in the design of efficient string matching algorithms. In this paper we present the Range Automaton, a weak yet efficient variant of the non-deterministic suffix automaton of a string whose configuration can be encoded in a very simple form and which is particularly suitable to be used for solving a multitude of text-searching problems. We will firstly develop our approach in the case of exact string matching and present an efficient algorithm, named Backward Range Automaton Matcher, which turns out to be very fast in many practical cases. Later, we will show how the Range Automaton can be adapted in an effective way also to non-standard string matching problems such as swap matching and multiple string matching. Experimental results suggest that our approach is flexible and effective for all three search problems addressed, especially in the case of long patterns. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Exact string matching Swap matching Text processing Automata Experimental algorithms design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Repetitive Processes and Their Surrogate-Model Congruent Encoding for Evolutionary algorithms - A Theoretic Proposal

Repetitive Processes and Their Surrogate-Model Congruent Enc...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Plump, Christina Berger, Bernhard J. Drechsler, Rolf DFKI Cyber Phys Syst Bremen Germany Hamburg Univ Technol Inst Embedded Syst Hamburg Germany Univ Bremen Dept Math Bremen Germany Univ Bremen Dept Comp Sci Bremen Germany

ISBN: (纸本)9798400701207

Evolutionary algorithms are a well-known optimisation technique. They can handle very different optimisation tasks and deal with distorted search spaces as well as non-differentiable optimisation functions. One crucial aspect in the design of evolutionary algorithms is the choice of encoding. Especially its interplay with the other components of the evolutionary algorithm is a relevant factor for the success of an evolutionary algorithm. While some encoding situations are relatively trivial, others pose a challenge. We focus on encoding repetitive processes, i.e. processes that consist of several variations of the same basic process (only with varied parameters). Our work proposes a possible technique that enables the validity of the encoded search space. We also provide adaptions to the standard operators of evolutionary algorithms to ensure they produce valid solutions. Furthermore, we show how this encoding technique is compatible with using a surrogate function for the fitness calculation and may reduce the necessary training data.

关键词： evolutionary algorithm design and analysis of algorithms surrogate model theory and algorithms for application

来源：评论

学校读者我要写书评

暂无评论

Improved Lion Optimization Algorithm for Wavelet Threshold Method in Ground-Borehole Transient Electromagnetic Signal Processing 24

Improved Lion Optimization Algorithm for Wavelet Threshold M...

引用

6th International Conference on Telecommunications and Communication Engineering

作者： Yang, Shuai Cao, Hui Song, Wenxu Chengdu Univ Technol Sch Mech & Elect Engn Chengdu Sichuan Peoples R China Chengdu Univ Technol Sch Geophys Chengdu Sichuan Peoples R China

ISBN: (纸本)9798400709630

This paper proposes a wavelet denoising algorithm based on an improved lion optimization threshold strategy. By introducing weight and adjustment factors into the standard lion optimization algorithm, the local and global optimization capabilities are enhanced. During the algorithm verification, forward modeling and theoretical signals generated with different noise were processed, showing that this algorithm significantly improved the signal-to-noise ratio and root mean square error of the signals. When applied to measured transient electromagnetic signals after data preprocessing, the inversion accuracy was further improved. The results demonstrate that this method can accurately separate useful signals from noise and improve signal quality, making it an effective signal denoising method.

关键词： CCS CONCEPTS Theory of computation design and analysis of algorithms Mathematical optimization Discrete optimization Network optimization Additional Keywords and Phrases: Lion optimization Wavelet denoising algorithm Threshold strategy Data preprocessing

来源：评论

学校读者我要写书评

暂无评论

Revealing the Inner Dynamics of Evolutionary algorithms with Convection Selection

Revealing the Inner Dynamics of Evolutionary Algorithms with...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Komosinski, Maciej Miazga, Konrad Poznan Univ Tech Inst Comp Sci Poznan Poland

ISBN: (纸本)9798400701207

Evolutionary algorithms are stochastic algorithms so they tend to find different solutions when run repeatedly. However, it is not just the solutions that vary - the very dynamics of the search that led to finding these solutions are likely to differ as well. It is especially in the algorithms with complex population structures - such as convection selection where a population is divided into subpopulations according to fitness values - where an opportunity for highly diverse dynamics arises. This work investigates the way evolutionary dynamics of subpopulations influence the performance of evolutionary algorithms with convection selection. We employ a demanding task of evolutionary design of 3D structures to analyze the relation between the properties of the optimization task and the features of the evolutionary process. Based on this analysis, we identify the mechanisms that influence the performance of convection selection, and suggest ways to improve this selection scheme.

关键词： evolutionary algorithms evolutionary dynamics design and analysis of algorithms convection selection

来源：评论

学校读者我要写书评

暂无评论

The Clustered Selected-Internal Steiner Tree Problem

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2022年第1期33卷 55-66页

作者： Chen, Yen Hung Univ Taipei Dept Comp Sci 1 Ai Guo West Rd Taipei 100234 Taiwan

Given a complete graph G = (V,E), with nonnegative edge costs, two subsets R subset of V and R'subset of R, a partition R = {R-1,R-2, ... ,R-k} of R, R-i boolean AND R-j = phi, i not equal j and Script capital R' = {R-1',R-2', ...,R-k'} of R', R-i'subset of R-i, a clustered Steiner tree is a tree T of G that spans all vertices in R such that T can be cut into k subtrees T-i by removing k - 1 edges and each subtree T-i spans all vertices in R-i, 1 <= i <= k. The cost of a clustered Steiner tree is defined to be the sum of the costs of all its edges. A clustered selected-internal Steiner tree of G is a clustered Steiner tree for R if all vertices in R-i' are internal vertices of T-i. The clustered selected-internal Steiner tree problem is concerned with the determination of a clustered selected-internal Steiner tree T for R and R' in G with minimum cost. In this paper, we present the first known approximation algorithm with performance ratio (rho + 4) for the clustered selected-internal Steiner tree problem, where rho is the best-known performance ratio for the Steiner tree problem.

关键词： design and analysis of algorithms approximation algorithms facility allocation in networks clustered Steiner tree selected-internal Steiner tree clustered selected-internal Steiner tree

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：