Crossroads of Information Theory and Computer Science: Analytic Algorithmics, Combinatorics, and Information Theory

信息论和计算机科学的十字路口：分析算法、组合学和信息论

• 批准号: 0513636
• 负责人: Wojciech Szpankowski
• 金额: $ 24.14万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-01 至 2009-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0513636&HistoricalAwards=false
• 关键词: Crossroads; Information; Theory; Computer; Science

The interplay between information theory (IT) and computer science (CS)dates back to the founding father of information theory, Claude E.Shannon. Ever since Shannon's work on both information theory andcomputer science, the research in the interplay between IT and CS hascontinued and expanded in many exciting ways. In 2003 the first NSFsponsored Workshop on the IT and CS Interface was held in Chicago,while in 2004 a graduate course on analytic methods in informationtheory and analysis of algorithms was organized at MSRI, Berkeley. Webuild on this momentum and propose to work on problems of informationtheory, combinatorics, and analysis of algorithms. Following Knuth'sand Hadamard's precept, we study such problems using techniques ofcomplex analysis. This program, which applies complex-analytic toolsto information theory, constitutes ``analytic information theory''.This research is focused on some facets of source coding, such as theredundancy rate problem, method of types, entropy evaluation, channelcapacity, and joint channel-source coding. The redundancy rate problemfor a class of sources is the determination of how far the actual codelength exceeds the optimal (ideal) code length, while the method oftypes is a powerful technique in information theory, large deviations,and analysis of algorithms. It is argued that counting types can beaccomplished efficiently by enumerating Eulerian paths (Markov types)or binary trees with a given path length (universal types). Likewise,analysis of the redundancy rate problem for memoryless and Markovsources leads us to interesting generating functions such as treegenerating functions (e.g., arising in counting labeled rooted trees),which are studied extensively in computer science.

信息论（IT）和计算机科学（CS）之间的相互作用可以追溯到信息论之父克劳德·e·香农（Claude E.Shannon）。自从Shannon在信息理论和计算机科学方面的工作以来，对IT和CS之间相互作用的研究以许多令人兴奋的方式继续和扩展。2003年，第一届由nsf赞助的IT和CS接口研讨会在芝加哥举行，2004年，伯克利MSRI组织了一门关于信息理论和算法分析方法的研究生课程。我们以这种势头为基础，建议研究信息论、组合学和算法分析方面的问题。遵循Knuth和Hadamard的原则，我们使用复杂分析技术来研究这类问题。该课程将复杂分析工具应用于信息论，构成了“分析信息论”。本文主要对信源编码的冗余率问题、类型方法、熵评价、信道容量、信道-信源联合编码等方面进行了研究。一类源的冗余率问题是确定实际码长超过最佳（理想）码长有多远，而类型方法是信息论、大偏差和算法分析中的一项强大技术。有人认为，计数类型可以通过枚举欧拉路径（马尔可夫类型）或具有给定路径长度的二叉树（通用类型）来有效地完成。同样，对无记忆源和马尔可夫源的冗余率问题的分析使我们得到了有趣的生成函数，如树生成函数（例如，在计数标记根树时产生），这在计算机科学中得到了广泛的研究。