算法与理论计算机2020people.math.harvard.edu编辑精选
通信的数学理论
A Mathematical Theory of Communication
进阶 · 约 120 分钟读完前置知识：概率论基础、微积分、通信系统基础
导读
这篇论文是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。它奠定了信息论，并深刻影响通信、计算与统计。
HN 关注点：作为二十世纪奠基性论文的持久可读性与历史地位，并讨论香农与维纳对“信息”的不同定义。
后来怎么样
这篇论文奠定了信息论，信息熵、信源编码和信道容量等概念成为通信与信息科学的标准框架，并深刻影响计算、统计与数据压缩等领域。
HN 评论精选
这几条评论里：支持 2 补充 1
支持香农以自由度/不确定性定义信息，比维纳的负熵/语义解释更客观但反直觉。
这大概是二十世纪最重要的十几篇出版物之一。讽刺的是，最终进入大众语汇的是维纳对信息的解释（恰好是香农的定义减一），因为它直观得多。维纳把信息视为负熵（或“秩序”）；香农则把它解释为一种自由度，或不确定性。维纳的问题在于其底层认识论带有主观倾向，把信息等同于“意义”或语义内容。香农的定义作为客观度量最终更优越，尽管远不直观（按他的解释，随机字符串在技术上是最信息饱和的构造，因为它具有最高的自由度）。
noema查看英文原文
Probably one of the dozen or so most important publications of the twentieth century. Ironically though it would be Norbert Wiener's interpretation of information (exactly Shannon's times minus one) that would cement itself in the popular lexicon due to it being far more intuitive. Where Wiener posits information as negative-entropy (or "order"), Shannon interprets it as representing a degree of freedom, or uncertainty. The problem with Wiener's is that the underlying epistemology carries a subjective bent, where information is equivocal to "meaning" or semantic content. Shannon's, meanwhile is ultimately superior as an objective metric, though far less intuitive (under his interpretation, a random string is technically the most information-saturated construct possible, because it possesses the highest degrees of freedom).
支持论文可读性强且至今仍被用作教材，香农硕士论文还奠基了数字电路理论。
我觉得很说明问题的是，香农这篇论文读起来非常容易。即使今天，许多电气工程院校仍几乎原封不动地用它教授通信理论。另一个有趣事实：香农的硕士论文很可能是史上影响最大的硕士论文：它把布尔代数与带开关的电路联系起来，基本发明了数字电路理论。
markus92查看英文原文
What I think is telling, is how easy to read Shannon’s paper is. Even today it is used pretty much as is at many EE colleges to teach communication theory. Another cool fact: Shannon’s master thesis is most likely the most influential one of all time: in it, he linked Boolean algebra to electrical circuits with switches, essentially inventing digital circuit theory.
补充推荐先读 Hartley 1928 论文以更好理解香农的细微论点。
顺便说，这是第一页引用的 Hartley 的论文；它同样非常好读且有洞见。我发现先读它有助于厘清香农论文中一些更细微的要点。http://keszei.chem.elte.hu/entropia/Hartley1928text.pdf
danharaj查看英文原文
BTW here's the paper by Hartley cited on the first page it is also very readable and insightful. I found it helped clarify some of the subtler points in Shannon's paper to read it as well. http://keszei.chem.elte.hu/entropia/Hartley1928text.pdf
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2020Hacker News 讨论帖197 分 · 39 评
- 2024Hacker News 讨论帖298 分 · 52 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选近线性时间内的最大流与最小费用流
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
给出了最大流与最小费用流的近线性时间精确算法，是理论计算机科学的重要突破。
算法与理论计算机2022 · 230 分 · 40 评 · 引用 8专业 · 约 120 分钟编辑精选