Asymptotic Solutions to Problems Arising in Computer Science and Information Theory

Knessl0202815调查员与同事和学生一起研究计算机科学、信息论和应用概率中的各种问题。这些方法都有一个共同的特点，那就是可以归结为求解递归方程或微分方程组。有时这些方程可以用变换方法精确地求解。然后，人们可以通过使用拉普拉斯或鞍点方法、Euler-Maclaurin和Poisson求和公式、Watson变换等方法扩展结果来获得渐近信息。许多感兴趣的应用问题(特别是非线性问题)不能被精确地解决。为此，研究人员和同事发展了适当的符号技术，直接分析政府方程。这些都是应用数学方法的变体，例如WKB展开和匹配的渐近展开。后者对于涉及几个不同尺度的渐近问题特别有用。重点放在组合学、数据压缩、算法分析、数字和二叉树、排队和编码中的问题。计算机在我们所有人的生活中扮演着越来越重要的角色。计算机科学中的重要问题包括排序和搜索、有效的数据存储和数据压缩。要决定什么是在某个数据库中搜索给定项的好方法，或者是用最少的内存存储音乐或视频的好方法，重要的是分析方法或算法。例如，可以询问平均搜索时间，或搜索时间将非常长、超过规定容限的可能性。这类问题涉及到“算法分析”。它们通常可以归结为求解某些类型的方程。研究人员和同事开发了数学工具来获得这些方程的解，无论是精确的解还是精确的近似解。近似通常是足够的，因为例如，如果存储的项目总数非常大，搜索问题是最重要的。这种“广度”表现为控制方程中的一个参数，它促进了它的求解。相关的数学问题出现在分子生物学和通信等其他重要领域，因此研究人员的方法和结果应该适用于更广泛的问题。

Knessl0202815 The investigator, together with colleagues and students,studies a variety of problems in computer science, informationtheory, and applied probability. These have the common featurethat they can be reduced to solving recursion or differentialequations. Sometimes these equations can be solved exactly usingtransform methods. Then one can obtain asymptotic information byexpanding the results using methods such as the Laplace or saddlepoint methods, the Euler-Maclaurin and Poisson summationformulas, Watson transformations, etc. Many applied problems ofinterest (especially nonlinear ones) cannot be solved exactly.For these the investigator and colleagues develop appropriateasymptotic techniques that analyze directly the governingequations. These are variants of applied mathematics methods,such as WKB expansions and matched asymptotic expansions. Thelatter are especially useful for asymptotic problems that involveseveral different scales. The focus is on problems incombinatorics, data compression, analysis of algorithms, digitaland binary trees, queuing, and coding. Computers play a progressively greater role in all of ourlives. Important problems in computer science include sorting andsearching, efficient data storage, and data compression. Todecide on what is a good method to search out a given item insome database, or a good method for storing music or video withminimal use of memory, it is important to analyze the method oralgorithm. For example, one might ask for the average searchtime, or for the likelihood that the search time will be verylong, exceeding some prescribed tolerance. Such questions involvethe "analysis of algorithms." They can frequently be reduced tosolving certain classes of equations. The investigator andcolleagues develop mathematical tools for obtaining solutions ofthese equations, either exact ones or accurate approximations.Approximations are often sufficient, because for example thesearching problem is most important if the total number of itemsstored is very large. This "largeness" shows up as a parameter inthe governing equation that facilitates its solution. Relatedmathematical problems arise in other important areas such asmolecular biology and communications, and the investigators'methods and results should thus find applicability to a widerange of problems.