计算机（网络）的文章分为了三部分：
此为第一部分。
分类：计算机科学
常用标签：
算法 10， 算法复杂度 7， 理论计算机初步 6， 机器统治世界 5， 密码学 5， 王小云 3， 理论计算机 3， 理论计算机课堂笔记 3， 完美洗牌问题 3， MD5 3
-
Tox 是一个开源的实时通信协议，不需要中央服务器，提供多种跨平台的客户端。
-
现在越来越多的软件支持端到端加密，服务器和第三方即使获取所有网络流量，也无法查看具体数据内容，从数学和工程上提供安全性。
-
迪菲－赫尔曼密钥交换（ Diffie–Hellman key exchange ，简称「D–H」） 是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道建立起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。
-
机器统治世界，其中一个重要的部分便是安全计算。而这一领域的开创性工作便是姚期智先生的「姚氏百万富翁问题」。相关的工作发表于 1982 年 FOCS 上的的《Protocols for secure computations》。
-
想起比多中心的匿名投票协议，有一种很简单的使用盲签名的投票协议，可以做到匿名投票。
-
今天北京车牌摇号开奖，如果只有一倍概率，中签概率只有万分之四，估计这一辈子都中不了吧。北京车牌目前有巨大的利益，组织者如何保证其中没有猫腻呢？
-
在机器统治世界提到，随着科技的发展，我们可以直接用机器来替代政府。所谓机器统治世界，并不意味着机器是世界的主人。机器还是听命于人类，只不过以一种无法被干预的民主投票的方式。所以，机器统计世界的第一要解决的问题就是投票协议。
-
最近《流浪地球》的热映，掀起了科幻热潮。很多人都在为电影和小说里的情节和逻辑争论不休。而我更感兴趣的是政府形态。
-
春节到了，又是了抢红包的时节。不过我对于这背后的数学和算法更感兴趣。
-
比特币协议里使用了 ECDSA （椭圆曲线签名算法），我之前以为它和基于大数分解的 RSA 公钥密码体系差不多。这两天看了下维基百科，才发现它们之间的差异挺大。
-
2007 年，我们讨论过一个算法问题， perfect shuffle ，据称是个微软面试题：
-
最大回撤是一个重要的风险指标。对于对冲基金和数量化策略交易，这个指标比波动率还重要。
-
-
-
以前提到过，理论计算机这门课会邀请一些正在这边访问的教授来讲课，由于是本科生，所以这些教授一般都是讲些有趣的东西，比如之前的overhang 堆积木 - 能伸出桌面多远？。今天这次课，来自 Aarhus 的Peter Bro Miltersen讲了一个很有趣的游戏问题。
-
PS: PCP 可以说是理论计算机领域近 20 年来的最重要的结果之一，它给了NP 问题一个新的刻画，并且提供了一种证明近似算法下界的方法。下面是 yijia 写的 PCP 介绍。
-
递归算法的复杂度通常很难衡量，一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大，如果我们可以保存每次子递归的结果的话，递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。
-
注: 这个问题来自China Theory Week 2008的 Open Problems Session。
-
姚期智教授给清华大学新入学研究生开的一门课，课程内容：
-
英文是 communication complexity ，不知道该翻译成通信复杂性，还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域，在过去 30 年衍生了很多东西。它是我的研究的主要内容，这里简略介绍一下。
-
上篇文章扫雷是 NP 完全问题之后，You Xu提到＂不光扫雷是 NP 完全问题，空当接龙问题也极有可能是一个 NP 完全问题。目前最好的通用 planner 只能解半副牌＂。他说对了，不光扫雷， Windows 自带的游戏都是 NP 完全的。Windows 自带的游戏除了扫雷，还有空当接龙和蜘蛛纸牌。
-
本科时有同学扫雷最快可以在 60 多秒完成高级难度，让我这种最快 130 秒的人非常惭愧，当时就想着编一个全自动的扫雷程序，不过一直也没写。今天才知道，原来扫雷问题是NP 完全的...
-
给定$ n\times n$ 的实数矩阵，每行和每列都是递增的，求这$ n^2$ 个数的中位数。
-
珍爱生命，远离政治。我们继续讨论算法。
-
Xie Xie 给我看了一个链接性能调优--永远超乎想象，里面提到了素数筛法的复杂度，作者用实验发现此筛法是线形的。
-
Rob Pike, 最伟大的 C 语言大师之一 , 在Notes on C Programming(英文原文)中从另一个稍微不同的角度表述了 Unix 的哲学:
-
更新：证明的关键一步发现错误，作者更新了论文，结论甚至论文标题都改了（废话），新版本On the graph isomorphism problem。
-
Game Theory 即博弈论，目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖)。但在最近几年，理论计算机界对它的研究也很热。
-
在从 hash 函数到王小云的 MD5 破解我们介绍了 hash 函数的一些基本概念和 MD5 碰撞的一个「应用」，最近在这个问题上又有了新的进展。
-
很多人一看到 NP-hard ，就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话，这个论断是不正确的。从算法角度来看， NP-hard 问题的确比 NP 难，但比 NP 还难（指花费时间更多）的问题却不见得是 NP-hard 的。
-
理论计算机(I)课上讲的一个问题，很有意思。
-
一个面试题，号称是微软的
-
题外话：此篇隶属于理论计算机(TCS)系列。
-
这个问题在 Yao 的理论计算机课上整整讨论了 2 节课。它是一个算法设计问题，也极具趣味性。下面是它的一些介绍和解决方案([1])。
-
密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在 hash 函数破解上做出重大贡献的王小云教授的工作，不过前两天新闻报道《王小云获得求是杰出科学家奖以及 100 万奖金》，在媒体上又掀起了一轮宣传狂潮，但是有些报道极端弱智，错误百出，所以我趁机纠正一下，并介绍密码学的一个组成部分——hash 函数，以及王小云老师在这上面的工作。
-
-
上篇文章已经提到， P vs NP 是理论计算机科学的核心问题。从数学的角度来说，它和其他历史上有名的数学问题一样，给与人们一个智力上重大的挑战。而更为重要的是，在无数与计算有关的的学术领域中， NP-完全问题以各种不同形式层出不穷。因此，这并不是一个纯粹的与世独立的智力游戏，而是对计算机科学有全面影响力的问题。
-
P = NP?
-
下面是 wikipedia 上算法的定义：
-
我所学的专业英文名是 Theoretical Computer Science ，理论计算机科学，在这里我就简化成理论计算机了。具体研究些什么呢，下面是Andrew Yao的研究方向
