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

arXiv 2020年

作者： Vorobyev, Ilya Center for Computational and Data-Intensive Science and Engineering Skolkovo Institute of Science and Technology Moscow127051 Russia Advanced Combinatorics and Complex Networks Lab Moscow Institute of Physics and Technology Dolgoprudny141701 Russia

Group testing is a well-known search problem that consists in detecting of s defective members of a set of t samples by carrying out tests on properly chosen subsets of samples. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests in the worst case. In this work, a multistage group testing problem is considered. Our goal is to construct a multistage search procedure, having asymptotically the same number of tests as an adaptive one. We propose a new approach to designing multistage algorithms, which allows us to construct a 5-stage algorithm for finding 3 defectives with the optimal number 3 log2 t(1 + o(1)) of *** Codes 68R05 Copyright © 2020, The Authors. All rights reserved.

关键词： Well testing

来源：评论

学校读者我要写书评

暂无评论

Duplication with transposition distance to the root for q-ary strings

arXiv

引用

arXiv 2020年

作者： Polyanskii, Nikita Vorobyev, Ilya Institute for Communications Engineering Technical University of Munich Munich80333 Germany Center for Computational and Data-Intensive Science and Engineering Skolkovo Institute of Science and Technology Moscow121205 Russia Advanced Combinatorics and Complex Networks Lab Moscow Institute of Physics and Technology Dolgoprudny141701 Russia

We study the duplication with transposition distance between strings of length n over a q-ary alphabet and their roots. In other words, we investigate the number of duplication operations of the form x = (abcd) → y = (abcbd), where x and y are strings and a, b, c and d are their substrings, needed to get a q-ary string of length n starting from the set of strings without duplications. For exact duplication, we prove that the maximal distance between a string of length at most n and its root has the asymptotic order n/ log n. For approximate duplication, where a β-fraction of symbols may be duplicated incorrectly, we show that the maximal distance has a sharp transition from the order n/ log n to log n at β = (q - 1)/q. The motivation for this problem comes from genomics, where such duplications represent a special kind of mutation and the distance between a given biological sequence and its root is the smallest number of transposition mutations required to generate the sequence. Copyright © 2020, The Authors. All rights reserved.

关键词： DNA sequences

来源：评论

学校读者我要写书评

暂无评论

Constructions of batch codes via finite geometry

arXiv

引用

arXiv 2019年

作者： Polyanskii, Nikita Vorobyev, Ilya Center for Computational and Data-Intensive Science and Engineering Skolkovo Institute of Science and Technology Moscow127051 Russia Advanced Combinatorics and Complex Networks Lab Moscow Institute of Physics and Technology Dolgoprudny141701 Russia

A primitive k-batch code encodes a string x of length n into string y of length N, such that each multiset of k symbols from x has k mutually disjoint recovering sets from y. We develop new explicit and random coding constructions of linear primitive batch codes based on finite geometry. In some parameter regimes, our proposed codes have lower redundancy than previously known batch codes. Copyright © 2019, The Authors. All rights reserved.

关键词： Geometry

来源：评论

学校读者我要写书评

暂无评论

A New Algorithm for Two-Stage Group Testing

arXiv

引用

arXiv 2019年

Group testing is a well-known search problem that consists in detecting of s defective members of a set of t samples by carrying out tests on properly chosen subsets of samples. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests in the worst case. In this work, two-stage group testing is considered. Using the hypergraph approach we design a new search algorithm, which allows improving the known results for fixed s and t → ∞. For the case s = 2 this algorithm achieves information-theoretic lower bound 2 log2 t(1 + o(1)) on the number of tests in the worst case. Also, the problem of finding m out of s defectives is considered. Copyright © 2019, The Authors. All rights reserved.

关键词： Machine learning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：