Asymptotic Solutions to Problems Arising in Computer Science and Information Theory

计算机科学和信息论中出现的问题的渐近解

• 批准号: 0202815
• 负责人: Charles Knessl
• 金额: $ 15.2万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-08-15 至 2006-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0202815&HistoricalAwards=false
• 关键词: Asymptotic; Solutions; Problems; Arising; Computer

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.

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