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

作者： Truszkowski, Jakub University of Waterloo

学位级别：master

One of the most fundamental computational problems in biology is that of inferring evolutionary histories of groups of species from sequence data. Such evolutionary histories, known as phylogenies are usually represented as binary trees where leaves represent extant species, whereas internal nodes represent their shared ancestors. As the amount of sequence data available to biologists increases, very fast phylogenetic reconstruction algorithms are becoming necessary. Currently, large sequence alignments can contain up to hundreds of thousands of sequences, making traditional methods, such as Neighbor Joining, computationally prohibitive. To address this problem, we have developed three novel fast phylogenetic algorithms. The first algorithm, QTree, is a quartet-based heuristic that runs in O(n log n) time. It is based on a theoretical algorithm that reconstructs the correct tree, with high probability, assuming every quartet is inferred correctly with constant probability. The core of our algorithm is a balanced search tree structure that enables us to locate an edge in the tree in O(log n) time. Our algorithm is several times faster than all the current methods, while its accuracy approaches that of Neighbour Joining. The second algorithm, LSHTree, is the first sub-quadratic time algorithm with theoretical performance guarantees under a Markov model of sequence evolution. Our new algorithm runs in O(n^{1+γ(g)} log^2 n) time, where γ is an increasing function of an upper bound on the mutation rate along any branch in the phylogeny, and γ(g) < 1 for all g. For phylogenies with very short branches, the running time of our algorithm is close to linear. In experiments, our prototype implementation was more accurate than the current fast algorithms, while being comparably fast. In the final part of this thesis, we apply the algorithmic framework behind LSHTree to the problem of placing large numbers of short sequence reads onto a fixed phylogenetic tree. Our initial res

关键词： phylogeny randomized algorithm quartet Markov chain

来源：评论

学校读者我要写书评

暂无评论

A Packet Scheduling Mechanism for Wireless Peer-to-Peer Content Distribution

A Packet Scheduling Mechanism for Wireless Peer-to-Peer Cont...

引用

作者： Liu, Yao Texas A&M University

学位级别：硕士

This thesis studies the problem of content distribution in wireless peer-to-peer networks with selfish nodes. In this problem a group of wireless nodes need to exchange a set of files over a lossless broadcast channel. Each node aims to maximize its own download rate and minimize its upload rate. We propose a distributed protocol that provides incentives for selfish nodes to participate in the content exchange. Our protocol does not require any exchange of money and reputation and hence can be easily implemented without additional infrastructure. Then, we will analyze the performance of our protocol by focusing on the import-ant case in which the system contains two files that need to be distributed. We derive a closed-form expression of Nash Equilibrium and characterize the corresponding system performance in discrete time. Furthermore, we propose a distributed mechanism where the strategy of each node is only based on the observed history of the system and not on the private information of other nodes. We also study the performance characteristics of the systems that employ network coding to facilitate data exchange. We show that, due to the free rider problem network coding does not necessary improve the performance of the system and, in some cases, may lead to worse system performance. We propose a novel approach to this problem based on random coding. The performance of the network coding algorithms is validated by performing extensive simulation study.

关键词： Peer-to-Peer Wireless Game Theory Network Coding randomized algorithm Thesis

来源：评论

学校读者我要写书评

暂无评论

Topology optimization with multiple materials, multiple constraints, and multiple load cases

Topology optimization with multiple materials, multiple cons...

引用

作者： Zhang, Xiaojia Shelly Georgia Institute of Technology

学位级别：博士

Topology optimization is a practical tool that allows for improved structural designs. This thesis focuses on developing both theoretical foundations and computational algorithms for topology optimization to effectively and efficiently handle many materials, many constraints, and many load cases. Most work in topology optimization is restricted to linear material with limited constraint settings for multiple materials. To address these issues, we propose a general multi-material topology optimization formulation with material nonlinearity. This formulation handles an arbitrary number of materials with flexible properties, features freely specified material layers, and includes a generalized volume constraint setting. To efficiently handle such arbitrary constraints, we derive an update scheme, named ZPR, that performs robust updates of design variables associated with each constraint independently. The derivation is based on the separable feature of the dual problem of the convex approximated primal subproblem with respect to the Lagrange multipliers, and thus the update of design variables in each constraint only depends on the corresponding Lagrange multiplier. This thesis also presents an efficient filtering scheme, with reduced-order modeling, and demonstrates its application to 2D and 3D topology optimization of truss networks. The proposed filtering scheme extracts valid structures, yields the displacement field without artificial stiffness, and improve convergence, leading to drastically improved computational performance. To obtain designs under many load cases, we present a randomized approach that efficiently optimizes structures under hundreds of load cases. This approach only uses 5 or 6 stochastic sample load cases, instead of hundreds, to obtain similar optimized designs (for both continuum and truss approaches). Through examples using Ogden-based, bilinear, and linear materials, we demonstrate that proposed topology optimization frameworks with the ne

关键词： Topology optimization Multi-material topology optimization Nonlinear topology optimization Multi-objective optimization Density-based method Ground structure method Truss layout optimization Michell structures Optimality conditions Material nonlinearity Hyperelastic model Multiple constraints Multiple load cases Discrete filter Material selection algorithm Update scheme ZPR update algorithm Stochastic sampling randomized algorithm Additive manufacturing

来源：评论

学校读者我要写书评

暂无评论

Mit :: Lcs :: Tr :: Mit-Lcs-Tr-651

引用

2016年

Mit :: Lcs :: Tr :: Mit-Lcs-Tr-651 by published by

关键词： adversary algorithm chapter execution general model lemma mit-lcs-tr-651 mutual exclusion optimal randomized player probability probability distribution probability space random random variable random variables randomized randomized algorithm randomized algorithms randomized computing set

来源：评论

学校读者我要写书评

暂无评论

Signature-Free Asynchronous Byzantine Consensus with t < n/3 and O(n²) Messages 14

Signature-Free Asynchronous Byzantine Consensus with <i>t</i...

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Mostefaoui, Achour Moumen, Hamouma Raynal, Michel Univ Nantes LINA F-44322 Nantes France Univ Bejaia Bejaia Algeria Univ Rennes Inst Univ France Rennes France Univ Rennes IRISA Rennes France

ISBN: (纸本)9781450329446

This paper presents a new round-based asynchronous consensus algorithm that copes with up to t < n/3 Byzantine processes, where n is the total number of processes. In addition of not using signature, not assuming a computationally-limited adversary, while being optimal with respect to the value of t, this algorithm has several noteworthy properties: the expected number of rounds to decide is four, each round is composed of two or three communication steps and involves O(n(2)) messages, and a message is composed of a round number plus a single bit. To attain this goal, the consensus algorithm relies on a common coin as defined by Rabin, and a new extremely simple and powerful broadcast abstraction suited to binary values. The main target when designing this algorithm was to obtain a cheap and simple algorithm. This was motivated by the fact that, among the first-class properties, simplicity -albeit sometimes under-estimated or even ignored- is a major one.

关键词： Abstraction Asynchronous message-passing system Broadcast abstraction Byzantine process Common coin Consensus Distributed algorithm Optimal resilience randomized algorithm Signature-free algorithm Simplicity

来源：评论

学校读者我要写书评

暂无评论

randomized self-updating process for clustering large-scale data

引用

Statistics and Computing 2024年第1期34卷 47-47页

作者： Shiu, Shang-Ying Chin, Yen-Shiu Lin, Szu-Han Chen, Ting-Li Department of Statistics National Taipei University New Taipei Taiwan Institute of Statistics National Tsing Hua University Hsinchu Taiwan Institute of Statistical Science Academia Sinica Taipei Taiwan

This paper introduces the randomized self-updating process (rSUP) algorithm for clustering large-scale data. rSUP is an extension of the self-updating process (SUP) algorithm, which has shown effectiveness in clustering data with characteristics such as noise, varying cluster shapes and sizes, and numerous clusters. However, SUP’s reliance on pairwise dissimilarities between data points makes it computationally inefficient for large-scale data. To address this challenge, rSUP performs location updates within randomly generated data subsets at each iteration. The Law of Large Numbers guarantees that the clustering results of rSUP converge to those of the original SUP as the partition size grows. This paper demonstrates the effectiveness and computational efficiency of rSUP in large-scale data clustering through simulations and real datasets. © 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

关键词： Clustering analysis Large-scale data randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

FLIP-FLOP SPECTRUM-REVEALING QR FACTORIZATION AND ITS APPLICATIONS TO SINGULAR VALUE DECOMPOSITION

引用

ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS 2019年 51卷 469-494页

作者： Feng, Yuehua Xiao, Jianwei Gu, Ming Shanghai Univ Engn Sci Sch Math Phys & Stat Shanghai Peoples R China Univ Calif Berkeley Dept Math Berkeley CA 94720 USA

We present the Flip-Flop Spectrum-Revealing QR (Flip-Flop SRQR) factorization, a significantly faster and more reliable variant of the QLP factorization of Stewart for low-rank matrix approximations. Flip-Flop SRQR uses SRQR factorization to initialize a partial column-pivoted QR factorization and then computes a partial LQ factorization. As observed by Stewart in his original QLP work, Flip-Flop SRQR tracks the exact singular values with "considerable fidelity". We develop singular value lower bounds and residual error upper bounds for the Flip-Flop SRQR factorization. In situations where singular values of the input matrix decay relatively quickly, the low-rank approximation computed by Flip-Flop SRQR is guaranteed to be as accurate as the truncated SVD. We also perform a complexity analysis to show that Flip-Flop SRQR is faster than the randomized subspace iteration for approximating the SVD, the standard method used in the Matlab tensor toolbox. We additionally compare Flip-Flop SRQR with alternatives on two applications, a tensor approximation and a nuclear norm minimization, to demonstrate its efficiency and effectiveness.

关键词： QR factorization randomized algorithm low-rank approximation approximate SVD higher-order SVD nuclear norm minimization

来源：评论

学校读者我要写书评

暂无评论

Blockchain-based immunization against kleptographic attacks

引用

Science China(Information Sciences) 2024年第7期67卷 172-183页

作者： Changsong JIANG Chunxiang XU Jie CHEN Kefei CHEN School of Computer Science and Engineering University of Electronic Science and Technology of China Yangtze Delta Region Institute (Huzhou) University of Electronic Science and Technology of China Department of Mathematics Hangzhou Normal University

Adversarial implementations of cryptographic primitives called kleptographic attacks cause the leakage of secret information. Subliminal channel attacks are one of the kleptographic attacks. In such attacks, backdoors are embedded in implementations of randomized algorithms to elaborately control randomness generation, such that the secrets will be leaked from biased outputs. To thwart subliminal channel attacks, double-splitting is a feasible solution, which splits the randomness generator of a randomized algorithm into two independent generators. In this paper, we instantiate double-splitting to propose a secure randomness generation algorithm dubbed SRG using two physically independent generators: ordinary and public randomness generators. Based on public blockchains, we construct the public randomness generator,which can be verified publicly. Hashes of a sufficient number of consecutive blocks that are newly confirmed on a blockchain are used to produce public randomness. In SRG, outputs from the two generators are taken as inputs of an immunization function. SRG accomplishes immunization against subliminal channel ***, we discuss the application strategies of SRG for symmetric and public-key encryption.

关键词： kleptographic attacks subliminal channel blockchain immunization randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Volume formula and growth rates of the balls of strings under the edit distances

引用

APPLIED MATHEMATICS AND COMPUTATION 2023年第1期458卷

作者： Koyano, Hitoshi Hayashida, Morihiro Natl Agr & Food Res Org Res Ctr Agr Informat Technol 1-31-1 Kannondai Tsukuba Ibaraki 3050856 Japan Matsue Coll Natl Inst Technol Dept Elect Engn & Comp Sci 14-4 Nishiikumacho Matsue Shimane 6908518 Japan

Analogs of balls in n-dimensional Euclidean space are defined in the monoid of strings composed of letters of an alphabet if a metric is defined on the monoid. These analogs are not only balls in the monoid of strings but also regular languages. Since the Leven-shtein distance, a reasonable metric between strings, was introduced in 1965, researchers have aimed to determine a formula for computing the volumes of balls of strings under this distance and their growth rate. However, this problem remains open. In this paper, we first derive a formula for the volumes of balls of strings under a metric obtained by ex-tending the Hamming distance as a metric on the whole monoid and subsequently reveal the growth rate of balls of strings under the Levenshtein distance using this formula. Fur-thermore, we describe a conjecture on the formula for the volumes of spheres of strings under the Levenshtein distance. Next, we construct an efficient randomized algorithm that computes estimates of the volumes of the balls whose estimation errors are less than a given value with a probability greater than a specified value. Finally, we examine the va-lidity of the proposed conjecture, using the (true) volumes obtained by exhaustive searches for small spheres and estimates of the volumes obtained by this algorithm for large ones.& COPY;2023 Elsevier Inc. All rights reserved.

关键词： Ball of strings Formal language Edit distance Ball volume formula Growth rate randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

COUNTING WEIGHTED INDEPENDENT SETS BEYOND THE PERMANENT

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2021年第2期35卷 1503-1524页

作者： Dyer, Martin Jerrum, Mark Muller, Haiko Vuskovic, Kristina Univ Leeds Sch Comp Leeds LS2 9JT W Yorkshire England Queen Mary Univ London Sch Math Sci Mile End Rd London E1 4NS England

Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671-697] showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are perfect graphs and are known to be precisely the class of (claw, diamond, odd hole)-free graphs. So how far does the result of Jerrum, Sinclair, and Vigoda extend? We first show that it extends to (claw, odd hole)-free graphs, and then show that it extends to the even larger class of (fork, odd hole)-free graphs. Our techniques are based on graph decompositions, which have been the focus of much recent work in structural graph theory, and on structural results of Chvatal and Sbihi [J. Combin. Theory Ser. B, 44 (1988)], Maffray and Reed [J. Combin. Theory Ser. B, 75 (1999)], and Lozin and Milanic [J. Discrete algorithms, 6 (2008), pp. 595-604].

关键词： independent set counting randomized algorithm fully polynomial randomized approximation scheme FPRAS claw-free graph fork-free graph decomposition

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：