思维 | 学习计算思维书籍 | 刷社交媒体 … 版权说明:《Bad Choices》是由Ali Almossawi著作的一套计算思维书籍,可以通过https://bookofbadchoices.com/访问本书英文版本。书中通过一系列人物的故事场景,以插画的方式展示了一个个现实生活中遇到的问题,进而引出了一些计算思维的问题,内容丰富且非常有趣。本书的目标读者是计划学习编程的儿童、学生,通过阅读本书可以开拓眼界,培养计算思维习惯。
思维 | 学习计算思维书籍 | 本章背景故事(请孩子阅读,家长伴听)
小D正在加拿大落基山脉徒步旅行。晶莹剔透的绿松石湖一动不动,湖面精准地倒映着上方山脉和树木的非凡壮丽图景。鸟儿在晴朗的天空下唧唧喳喳,随着微微的东风俯冲。那一刻,世界仿佛是最宁静的地方。然而,小D的心思却在别处。
当天早上,当他的团队正要离开温哥华时,一个奇特的景象引起了他的注意。他目睹了一只野鸭在野外环境中摆动行走,就好像它在跳伦巴舞一样。从那以后小D一直在挣扎,努力想寻找一个诙谐而简洁的句子来捕捉那个场景的欢闹,用来在社交媒体上发表一段不超过140个字符的精彩回顾,小D是个认真的人,不能让他的社交圈的读者们失望。
目标:写出一个幽默的状态更新,使其不超过 140 个字符。(如无其他说明,文字均指的是英文)
方法 1:将较长的单词替换为较短但不太聪明的单词。
方法2:省略一些单词中频繁出现的字母,例如元音。
试试看,哪种方法更有效?
思考完成再接着往下看哦!
刷社交媒体 | 分析过程(请家长+孩子分段阅读思考)
神经科学研究表明,我们的大脑具有显著性检测的能力。当你在一个安静的房间里,听到任何类型的噪音时,你的大脑都会听到它。如果您在嘈杂的房间中,听到与那些噪音不同的声音,您的大脑也会听到它。从某种意义上说,出现频率更高的信息被认为意义不大,这就是为什么大脑知道过滤此类输入的原因。
有一种通过省略元音等频繁出现的字母来编写短信的方式,部分来自信息论中的一个想法,据说“Only infrmatn esentil to understandmst b tranmitd”。由于英语语言的各种特性,尽管省略了字母,但可以完全理解前一句,这些字母是可预测的,因此是多余的,可以省略。正是由于这个原因,当我们面临缩短一段文本同时确保它仍然可以理解的两难境地时,就像小D一样,采用这种方法并不是一个坏主意。事实上,在预测文本出现之前,我们一直都这样做。作为节省空间的回报,这种方法确实会导致数据丢失,尽管是非必要的数据。
请注意:到目前为止,我们之前各章讨论的所有主题都涉及能否以更快或者更慢的方式做某事,而在这里,我们谈论的是如何占用更少的空间。这种平衡反映了我们在评估解决问题的不同方法时,在实践中看到的典型平衡——通常,计算机科学家比较相互竞争的几种方法的相对速度,也称为它们的运行时复杂度;但偶尔,他们会根据它们需要多少内存或磁盘空间,也称为空间复杂度来比较。
令人着迷的是方法二在计算理论中有一个类似情形。 1952 年,计算机科学家霍夫曼( David A. Huffman)提出了一种减少存储数据所需空间的方法。与前面的例子不同,霍夫曼的方法不涉及删除事物,而是专注于优化事物,我们稍后会看到。计算机存储诸如单词之类的数据的方式是通过映射我们的字母表中的字母——以及数字和其他字符——转换为一组数值。 然后使用计算机可以理解的称为二进制的表示形式存储这些值。 每个字符都使用可能由七位组成的二进制代码表示。 例如,字母“a”映射到值 97,在二进制中看起来像这样:
1100001
字母“b”映射到值 98,在二进制中看起来像这样:
1100010
因此,如果我们想用二进制表示单词“hans”,它看起来像这样,每个字母占用 7 位,总共 28 位:
1101000 1100001 1101110 1110011
具有相同长度(在这种情况下为 7 位)的二进制代码的字符的好处是它使解码二进制字符串变得容易。 我们所要做的就是每 7 位读取一次,然后使用映射表将其解码为英文。
然而,霍夫曼是个特立独行的人。他看着那七位数字说:“当然,一定有办法压缩一下。”他的朋友认为不可能,并请他不要过分要求自己。但霍夫曼不在乎,如果这意味着他有可能为一组字符提出最佳二进制表示,他愿意将自己推向一个未知领域。
霍夫曼没有使用固定长度的二进制代码,而是选择了可变长度的代码。他利用了句子中的某些字符比其他字符出现得更频繁的事实,因此他将出现频率较高的字母映射为较小的值,从而将二进制代码较短,而将不太频繁出现的字母映射为较长的二进制代码。例如,假设我们已经确定对于给定的数据体,字符的频率分布如下图所示。
换句话说,字母“e”出现了 705 次,字母“a”出现了 605 次,以此类推。请注意,字符从上到下按最频繁到最不频繁的顺序排序。霍夫曼的方法采用频率最小的一对字符,将它们的值相加,将结果存储在一个新的临时字符中,然后对集合进行排序。它重复这个过程,直到我们没有更多的字符对。
我们最终得到的本质上是一棵树,其中每个节点(一个字符)都通过两条边连接到它来自的一对节点。如果我们用上面的字符集来做,我们最终会得到类似下图的东西,我们首先将“f”和“j”配对,得到f'数值是100+59=159,然后我们将结果与“l”配对,依此类推。从第二列开始的每一列都是算法的一个步骤。
当我们将图表重新排列为树时,一切都变得清晰起来。一个字符的优化二进制代码是当我们从最高节点(根*节点)读取位到该字符节点时得到的字符串。所以在下面的树中,每当我们向左移动时,我们在字符的二进制代码中添加一个零,而每当我们向右移动时,我们向它添加一个 1,这就是字母“e”以两位长结尾的原因二进制代码 11 和字母“f”以 5 位长的二进制代码 10001 结尾。将 1 或 0 分配给霍夫曼树中节点的子节点是任意完成的;也就是说,“e”可能被编码为 01 而不是 11。虽然不能保证二进制代码是唯一的,但可以保证它们是最优的。在任何情况下,霍夫曼树都会与消息一起发送给接收方,以便接收方知道如何解码消息。
这是我们优化的二进制代码的列表。请注意,更频繁的字母现在如何具有更短的代码:
“hans”这个词现在在二进制中看起来如何?
001 01 101 000
我们只需要 11 位而不是 28 位。这种洞察力让人想起近一个世纪前的一项创新——即如何最好地在电报之间传输信息。
塞缪尔·莫尔斯(Samuel Morse)决定使用哪些代码表示哪些字母的方式,也是基于字母在英语中出现的频率。有趣的是,莫尔斯不是通过与专家交谈或进行研究或分析数据来确定各种字母的频率,而是通过计算打印机类型框中的类型数量。所以下次当一个学究质疑你的研究方法时,请振作起来。
像霍夫曼编码这样的数据压缩技术在现实世界中非常重要。充分利用空间,意味着网站加载速度更快——Web 服务器可以在通过网络发送文件之前对其进行压缩,而现代 Web 浏览器可以对它们进行解压缩。当带宽稀缺时,任何这样的速度增益都是至关重要的。压缩还意味着电影、图片和歌曲都可以比其他方式占用更少的空间,从而节省存储和传输费用。 MP3 等音频格式非常有趣,因为它们的压缩模型依赖于针对人类由于生物学或神经学限制而无法听到的音频成分。例如,人耳无法听到高于 20,000 Hz 的声音频率。
下次当您与某人进行语音或视频对话而质量没有任何下降时,请考虑压缩对该活动所做的贡献。技术已经成熟到您的应用程序只需要通过网络发送一些数据,然后可以在另一端推断或重建其余数据。实际上,压缩有助于降低使用技术的障碍。
这一切都很好。但是小D如何了?他的粉丝用户满意了吗?
是的,小D靠着自己的幽默和才智,成功更新了他的状态,成千上万的热心用户得到了他们所期待的点击。
希望小D能够了解到,如何在不损失任何基本品质的情况下,达到最好地压缩信息,并带来类似的快乐结果。
今天学习结束了,下面一起来通过实验体会一下学到的方法吧!
学习计算思维书籍 | 本章延申练习(请家长+孩子共同完成)
用手机拍一张照片,上传到电脑里,看看图片的大小,然后用画图、photoshop等图片处理软件来试着减小文件的大小,你能做到吗?变化后的差别你能看出来吗?
Disclaimer: This english book is written by Ali ALMOSSAWI and souce from https://bookofbadchoices.com/