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) 之间的相互作用可以追溯到信息论之父克劳德·香农 (Claude E.Shannon)。自从香农在信息论和计算机科学方面的工作以来，IT 和 CS 之间相互作用的研究一直在以许多令人兴奋的方式继续和扩展。 2003 年，第一届 NSF 赞助的 IT 和 CS 接口研讨会在芝加哥举行，2004 年，伯克利 MSRI 举办了信息论分析方法和算法分析研究生课程。 我们以此为基础，提出致力于信息论、组合学和算法分析等问题的研究。 遵循 Knuth 和 Hadamard 的戒律，我们使用复杂分析技术来研究此类问题。 该程序将复杂分析工具应用于信息论，构成了“分析信息论”。本研究集中于信源编码的一些方面，如冗余率问题、类型方法、熵评估、信道容量和联合信道-源代码。 一类信源的冗余率问题是确定实际码长超出最优（理想）码长多少，而类型方法是信息论、大偏差和算法分析中的强大技术。 有人认为，通过枚举欧拉路径（马尔可夫类型）或具有给定路径长度的二叉树（通用类型）可以有效地完成类型计数。同样，对无记忆源和马尔可夫源的冗余率问题的分析使我们得到有趣的生成函数，例如树生成函数（例如，在计算标记的有根树时出现），这些函数在计算机科学中得到了广泛的研究。