随机算法为每年春季开设的专业选修课，任课老师为前沿计算研究中心助理教授孔雨晴博士。

 

　　课程号：04834010

　　学 分：4

　　先修课：概率论

 

　　什么样的洗牌方法最有“效率”？如果想知道这个问题的答案，欢迎大家选修（旁听）下学期的随机算法课。除了丰富有趣的课堂内容，我们还将按照以下步骤解答这个问题——

 

　　步骤一：一起设计牌面

　　步骤二：将牌实体做出来

　　步骤三：开始以不同方式洗牌

 

图1. 某种神秘的洗牌方式 by ChatGPT

 

　　开个玩笑，我们将会通过学习混合时间（mixing time），耦合（coupling）等概念和方法来解答以上的洗牌效率问题。具体来说，随机算法课程将介绍如何通过掷硬币处理那些确定性算法难以处理或处理效率不高的问题。在分析掷硬币的可靠性时，我们还会介绍各种概率分析工具，包含概率方法、二阶矩方法、马尔科夫链、耦合等内容。

 

　　这门课程的知识点特别多、杂，为了帮助大家以一种有趣的方式更好地理解这些知识点，孔老师于上学期启动了一个将随机算法课程知识点转化为牌面设计的项目。在很多上过随机算法课同学的大力支持下，许多知识点已经被设计了出来，例如：

 

投骰子，图灵机

by 钱一程，莫润冰

 

　　看牌感想

　　上面这张非常可爱的图由钱一程、莫润冰两位同学设计完成。随机算法和确定算法的区别在于随机算法可以引入随机数作为输入的一部分，从而让算法的执行具有随机性。

 

　　上图中，两位同学让猫负责喂随机数，至于为什么选择猫，我只能大胆猜测，也许那是一只薛定谔的猫……

 

　　“想象你需要找到一个隐藏的宝藏，但不知道它在哪里。每次你掷骰子，根据骰子的点数决定你走的方向。有时候，这种随机的走法可以帮你快速找到宝藏，即使你一开始并不知道它在哪里。这就是随机算法的特点：它没有确定的路线。”

---By ChatGPT

 

两个完全独立的随机数可生成若干两两独立的随机数

by 张璐婧

 

　　看牌感想

　　上面这张独具匠心的图由张璐婧同学设计完成。两两独立是我们将要学到的一个非常重要的概念。当随机性也需要花费的时候——例如猫每扔一个骰子都需要花费一条小鱼，我们就需要想办法节省我们的随机性。当我们只需要两两独立而不是完全独立的时候，我们可以通过上图所绘制的方法让两位完全独立的随机数作为”父母”生成许多两两独立的“小孩”。

 

　　“想象一个魔法森林里住着三只小独角兽，它们分别是蓝色的Bella、红色的 Ruby 和绿色的 Emerald。每天，它们可以魔法地改变自己的颜色。如果 Bella 改变颜色，不会影响 Ruby 和 Emerald 改变颜色，反之亦然，那么我们就说它们是“两两独立”的。

 

　　但是这个时候有可能 Bella 和 Ruby 的组合改变会影响到 Emerald，如果我们想要所有独角兽的颜色改变都互不影响，无论是单独一只，两只一起，那么这就是“完全独立”。每只独角兽都在自己的魔法泡泡里，完全不受其他独角兽的魔法影响。”

---by ChatGPT

 

　　现有概念池（不断补充中）：

 

　　目前仍然有一部分知识点没有被设计，希望在此邀请更多同学加入，共同学习、共同设计！

 

　　最后的成品将是牌面游戏，可以是扑克牌（如果有足够多的设计），也可以是其他纸牌类桌游。比如，孔老师最近发现的翻牌桌游就很有趣，大家在玩游戏的过程中还可以顺便复习随机算法知识点。

图2. 宜家的翻牌桌游

 

如何参与

 

　　1. 选修/旁听随机算法，2024春

　　考虑到过去每年一开始随机算法好像都是满的，大家也可以选择旁听，不过根据经验后期会有退课……

　　*上过随机算法课的同学可跳过此步骤。

 

　　2. 获取链接

　　共享设计链接将在课程群发布。

 

　　3. 充分发挥想象力吧！

　　选择一个还没有被设计过的知识点，设计一个牌面。

 

参与之后

 

　　1. 牌面美化

　　后期会在保留大家设计的基础上，进行美化和风格统一化的调整。

 

　　2. 署名权和获赠卡牌

　　每张牌面均会署名创作者。所有参与设计的同学都可以直接获得一副牌。

 

　　3. 创作理念介绍

　　小编还将把大家的创作理念整理出来，陆续发布在公众号上。

 

　　License：Open source，禁止商用。

 

结语

 

　　我一直觉得创作是这个世界上最重要的事情之一，也一直对自己的创意很有信心，但是在看到各位同学的创作以后，我不得不承认，我输了……和我比起来，大家实在是太有创作才华了！所以我决定换条赛道，希望感兴趣的同学可以加入我们的创作队伍，期待以后大家可以在我们共同设计的桌游上进行比拼！