标签: 理论计算机课堂笔记

这是我在读博士期间作为导师姚期智先生的助教所作的一些课程笔记,姚教授授课时没有教材,每堂课都讲一个特定的问题,很多问题都使用了生活中实际的例子,生动而有趣。

这些课都是清华大学理论计算机中心的「姚班」的必修课程,具体信息可参考姚班精品课程介绍姚期智教授个人主页

  1. 以前提到过,理论计算机这门课会邀请一些正在这边访问的教授来讲课,由于是本科生,所以这些教授一般都是讲些有趣的东西,比如之前的 overhang 堆积木 - 能伸出桌面多远? 。今天这次课,来自 Aarhus 的 Peter Bro Miltersen 讲了一个很有趣的游戏问题。
  2. 理论计算机 (I) 课上讲的一个问题,很有意思。
  3. 在大家玩牌的时候,每一局之前都需要重新洗牌 —— 一次洗牌指将牌分为左右两垛然后穿插放牌,但多少次洗牌才是正当的呢?就我多次打牌的观察,多数人都不超过 4 次。
  4. 这个问题在 Yao 的理论计算机课上整整讨论了 2 节课。它是一个算法设计问题,也极具趣味性。下面是它的一些介绍和解决方案 ([ 1 ])。