from Roar’s blog:
April 13
姚的课
上半节课，讲二分图匹配，引出来一个问题，stable marriage（稳定的婚姻），就开始举例子：“我看我们这里，女生都比较少，这样，假设，每个男生，回去以后，都把所有的女生列个ranking，然后女生做同样的事情，不过，女生要花的时间很多，我们有太多的男生了。然后，大致就是这样的吧，假设女生比较积极，每个周末，女生就开始给list上的第一个男生打电话，dating，当然，u can dream，有很多女生给你打电话，那么，你有个ranking，就选择一个最好的，和她订婚，当然，订了婚还可以break，然后拒绝其他的，把她们从你的list里面划掉，然后，女生也是，如果被reject，就把那个男生划掉。然后每周都是这样的，如果有更好的打来电话，那么，就break前一个，直到没有人打电话为止，这个算法，我们下节课证明，它会产生稳定的婚姻，现在我需要几个volunteers……那么，你们说，这种情况，谁比较吃亏，men or women？（回答：男的），这个，我不知道你们为什么这么聪明，但是考虑到所有的women被reject了以后都会越来越选到list下面的人，所有的men都是选择最好的，为什么你们会说是men吃亏呢？不过事实是，men比较吃亏，所以说，积极一点是比较好的，关于为什么，我们下节课证明。”
然后……有个以色列口音的教授……讲了一节课的P vs NP，愣是没听懂说什么，虽然知道他说什么。（这个应该是说Oded Goldriech，ft，刚写到这行他跑过来借剪子）
April 18th, 2006 at 5:21 am
这些有MIT血统的人都喜欢这个stable marriage问题。extended version是homosexual的婚姻不能找到一个stable solution.