计算万物的起源和终点-南京大学.PDF

计算：万物的起源和终点 蒋炎岩 南京大学计算机科学与技术系 2014 年 1 月21 日 这是一场怎样的报告？ 如果有时光机 能回到十年之前 面对和你们同龄的自己 我应该对自己说点什么？ 今天带给大家一个和方格有关的故事 Outline 从一个计数问题谈起 一个家喻户晓的计数问题 故事的缘起 进入微观世界 神奇的物理世界 统计物理与计数 生命与心灵的奇迹 生命：物理世界中的计算机 人造的智慧 计算：万物的起源和终点 回归理论计算机科学 起源即是终点 Outline 从一个计数问题谈起 一个家喻户晓的计数问题 故事的缘起 进入微观世界 神奇的物理世界 统计物理与计数 生命与心灵的奇迹 生命：物理世界中的计算机 人造的智慧 计算：万物的起源和终点 回归理论计算机科学 起源即是终点 2 n 覆盖问题 用 1 2 的多米诺骨牌，覆盖2 n 的方格，有多少种不同 的覆盖方法？ 2 n 覆盖问题：解答 假设 Sx 为覆盖如x 所示方格的方案数，考虑覆盖第一列 的两种方案： S ( ) S ( ) S ( ) n n1 n2 f n {1 n 1 2 f n 1 f n 2 n 2 2 2 解法：递推、通项公式、矩阵乘法…… 2 n 覆盖问题：解答 假设 Sx 为覆盖如x 所示方格的方案数，考虑覆盖第一列 的两种方案： S ( ) S ( ) S ( ) n n1 n2 f n {1 n 1 2 f n 1 f n 2 n 2 2 2 解法：递推、通项公