随机算法为每年春季开设的专业选修课,任课老师为前沿计算研究中心助理教授孔雨晴博士。
课程号:04834010
学 分:4
先修课:概率论
什么样的洗牌方法最有“效率”?如果想知道这个问题的答案,欢迎大家选修(旁听)下学期的随机算法课。除了丰富有趣的课堂内容,我们还将按照以下步骤解答这个问题——
步骤一:一起设计牌面
步骤二:将牌实体做出来
步骤三:开始以不同方式洗牌
图1. 某种神秘的洗牌方式 by ChatGPT
开个玩笑,我们将会通过学习混合时间(mixing time),耦合(coupling)等概念和方法来解答以上的洗牌效率问题。具体来说,随机算法课程将介绍如何通过掷硬币处理那些确定性算法难以处理或处理效率不高的问题。在分析掷硬币的可靠性时,我们还会介绍各种概率分析工具,包含概率方法、二阶矩方法、马尔科夫链、耦合等内容。
这门课程的知识点特别多、杂,为了帮助大家以一种有趣的方式更好地理解这些知识点,孔老师于上学期启动了一个将随机算法课程知识点转化为牌面设计的项目。在很多上过随机算法课同学的大力支持下,许多知识点已经被设计了出来,例如:
投骰子,图灵机
by 钱一程,莫润冰
看牌感想
上面这张非常可爱的图由钱一程、莫润冰两位同学设计完成。随机算法和确定算法的区别在于随机算法可以引入随机数作为输入的一部分,从而让算法的执行具有随机性。
上图中,两位同学让猫负责喂随机数,至于为什么选择猫,我只能大胆猜测,也许那是一只薛定谔的猫……
“想象你需要找到一个隐藏的宝藏,但不知道它在哪里。每次你掷骰子,根据骰子的点数决定你走的方向。有时候,这种随机的走法可以帮你快速找到宝藏,即使你一开始并不知道它在哪里。这就是随机算法的特点:它没有确定的路线。”
---By ChatGPT
两个完全独立的随机数可生成若干两两独立的随机数
by 张璐婧
看牌感想
上面这张独具匠心的图由张璐婧同学设计完成。两两独立是我们将要学到的一个非常重要的概念。当随机性也需要花费的时候——例如猫每扔一个骰子都需要花费一条小鱼,我们就需要想办法节省我们的随机性。当我们只需要两两独立而不是完全独立的时候,我们可以通过上图所绘制的方法让两位完全独立的随机数作为”父母”生成许多两两独立的“小孩”。
“想象一个魔法森林里住着三只小独角兽,它们分别是蓝色的Bella、红色的 Ruby 和绿色的 Emerald。每天,它们可以魔法地改变自己的颜色。如果 Bella 改变颜色,不会影响 Ruby 和 Emerald 改变颜色,反之亦然,那么我们就说它们是“两两独立”的。
但是这个时候有可能 Bella 和 Ruby 的组合改变会影响到 Emerald,如果我们想要所有独角兽的颜色改变都互不影响,无论是单独一只,两只一起,那么这就是“完全独立”。每只独角兽都在自己的魔法泡泡里,完全不受其他独角兽的魔法影响。”
---by ChatGPT
现有概念池(不断补充中):
目前仍然有一部分知识点没有被设计,希望在此邀请