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

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

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.