时间:2023-04-23 15:28:03
序论:写作是一种深度的自我表达。它要求我们深入探索自己的思想和情感,挖掘那些隐藏在内心深处的真相,好投稿为您带来了七篇协同通信论文范文,愿它们成为您写作过程中的灵感催化剂,助力您的创作。
关键词: 协作通信; 中继节点; 中继节点的最优选择; 慢衰落信道
中图分类号:TN925 文献标志码:A 文章编号:1006-8228(2012)03-37-03
A selection scheme for optimal relay nodes under slowly fading channel environment
Duanmu Chunjiang, Wang Pei, Yang Yongduo
(Zhejiang Normal University, Jinhua, Zhejiang 321004, China)
Abstract: Selection of optimal relay node is an important problem in cooperative communications. In the previous literature, only single-path channel environments were considered, while in reality, communication channels are mostly multi-path fading channels. For this reason, it is proposed in this paper a selection scheme for optimal relay nodes under a multi-path fading channel environment. The experimental results demonstrate that the optimal relay nodes selected by this scheme are usually not the optimal relay nodes selected by the conventional methods, which only consider single-path. Thus, this scheme is more suitable for real environments and may significantly boost system performance.
Key words: cooperative communications; relay node; optimal relay node selection, multi-path fading channels
0 引言
与直接通信相比,协作通信能提供空间分集增益,实现目标用户高速、高可靠性的数据传输。协作通信技术利用多个不同用户的天线组成虚拟天线阵,从而获得多输入多输出(MIMO)系统的性能增益。其概念最早由Sendonaris[1,2]等人提出;Laneman[3]等人研究了瑞利衰落环境下的各种协作通信协议,如解码转发、放大转发等,并将由协作带来的分集称为协作分集。
协作分集的基本思想是源节点通过中继的帮助向目的节点发送信息。协作通信中的一个关键问题是如何分配和管理中继节点,有很多文献都对此进行了研究。文献[4-5]提出了基于单个中继节点的最佳中继节点选取算法。文献[6-7]分别对基于放大转发(AF,amplify-and-forward)和译码转发(DF,decode-and-forward)中继系统的中继节点选择算法进行了研究。文献[8]为了避免多个中继同时竞争最佳中继而出现冲突导致失败,引入候选节点限制策略,从而在实现快速选择节点的同时降低了选择失败的概率。文献[9]提出一种改进的最佳中继选择算法,在源站受到最佳中继发出的标志分组后发送选择确认消息,中继节点在冲突发生后进行回避。文献[10]分析了解码中继(DF)情况下协作传输的中断概率。但是这些文献中讨论的都是单径信道下的信号传输和中继节点的选择问题,而没有考虑多径衰落信道下的中继选择问题。为此,本文针对放大转发协作通信网络,以降低系统误码率为目标,进行多径信道下的中继节点的优化选择。
1 系统模型
图1 协作通信系统模型
协作通信的系统的模型如图1所示。此系统中除有源节点到目的节点之间的信道外,还存在源节点到各中继节点以及各中继节点到目的节点之间的信道。最优中继的选择问题,是要从所有的候选的中继节点中选择一个最优的节点以辅助源节点的信息传输。
在已有的文献中,都假设源节点到目的节点、源节点到各中继节点、以及各中继节点到目的节点间的信道是单径的,即只存在一个信道增益。而在实际情况中,由于信号的反射和折射等原因,源节点到目的节点、源节点到各中继节点,以及各中继节点到目的节点间的信道都是多径衰落的,即每两个节点之间存在着多条可达路径,各条路径上都具有相应的信道增益。因此,本文将讨论在实际情况下协同通信中的中继节点的选择问题,以使所提出的方案更符合实际的情况和提高系统的实际性能。
图2 多径衰落的二进制数字接收机的系统模型
图2是一个具有多径衰落的二进制数字接收机的系统模型。系统信道有L条路径传送携带有相同的信息的信号,假设每条路径为频率非选择的、慢衰落的且其包络统计特性为瑞利分布,再假设L条路径之间的衰落过程是相互统计独立的,每条路径的信号受到零均值加性高斯白噪声过程的恶化。
因为L条路径的噪声过程是相互统计独立的,且具有相同的自相关函数。于是,第L条路径上的信道等效低通接收信号为
(k=1,2…,L,m=1,or 2) ⑴
式中,表示L条路径的衰减因子和相移,skm(t)表示第k条信道的第m个信号值,zk(t)表示第k条路径上的加性高斯白噪声。在集合{skm(t)}内的所有信号具有相同的能量。这里假设传输中使用的是BPSK调制方法。
2 多径衰落信道下的中继节点的优化选择方案
这里中继节点的选择是从最小误码率的目标来考虑的。由通信原理的基本知识可知,在接收机最大比合并的情况下,从节点A到节点B的多径信道的误码率可表示为:
⑵
其中,对于BPSK的调制方法发射信号间的相关系数ρr=-1,Q(x)的定义为:
⑶
从节点A到节点B的平均信噪比,其定义为:
⑷
其中,PA为发射节点A的发射功率,N0为噪声的平均功率,为从节点A到节点B的第k条路径上的增益的模。
这样,可以利用式⑵来计算多径衰落情况下从源节点S到第i个候选中继节点Ri之间的误码率。在第i个候选节点Ri接收正确的情况下,通过单个Ri的辅助,从源节点到目的节点之间的误码率可表示为:
⑸
其中γi的定义为
⑹
式⑹中,PS为源节点S的发射功率,PRi为中继节点Ri的发射功率,一般情况下要求总功率PS+PRi不能超过一门限值P。为从源节点S到目的节点D之间的第S条路径上的增益的模,为从中继节点Ri到目的节点D之间的第m条路径上的增益的模。在第i个候选节点Ri接收不正确的情况下,它不发射功率,即此时它不能辅助信息的传输。此时,从源节点到目的节点之间的误码率可表示为:
⑺
其中φi的定义为:
⑻
这样,当选中单个第i个中继节点Ri时,其平均误码率可表示为:
⑼
在本论文所提出的算法中,将根据Pe(i)的值的大小,选择使误码率Pe(i)最小的中继节点m*作为最优中继节点,即:
⑽
3 仿真结果与分析
图3 采用所提出的方法和传统的方法的对比效果图
我们设计了一个试验来验证所提出的算法能带来性能的较大提高。现假设有两个候选的中继节点,其中源节点S到中继节点S的多径衰落信道的增益的模分别为6,2,1,1,1,中继节点R1到目的节点的多径衰落信道的增益的模分别为10,3,2,1,1。源节点S到中继节点R2的多径衰落信道的增益的模分别为5,4,4,4,4,中继节点R2到目的节点的多径衰落信道的增益的模分别为9,8,8,8,8。源节点S到目的节点D的多径衰落信道的增益分别为3,2,2,1,1。噪声的功率谱N0=1,源节点S和所选择的最优中继节点平分总功率。在这种情况下,传统的中继选择算法会选择中继节点R1作为最佳中继节点,因为从源节点S到中继节点R1的主径6大于从源节点S到R2的主径5,同时中继节点R1到目的节点D的主径10大于中继节点R2到目的节点的主径9。而在本论文所提出的方法中,会选择中继节点R2作为最优中继节点(因为在实际情况下Pe(2)
4 结束语
本文提出的最优中继节点的选择方案,由于考虑了实际通信系统中的多径效应,因此更符合和贴近实际情况。仿真结果显示,本方案可在很大程度上提高系统的性能,即在同样的误码率的要求下,大幅减少系统的发射总功率。
参考文献:
[1] SENDONARIS A, ERKIP E,AAZHANG B. User cooperation
diversity: part Ⅰ:system description [J]. IEEE Transactions on Communications,2003.51(11):1927~1938
[2] SENDONARIS A,ERKIP E,AAZHANG B. User cooperation
diversity :part Ⅱ implementation aspects and performance analysis [J].IEEE Transaction on Communications,2003.51(11):1939~1948
[3] LANEMAN J N,TSE D N C,WORNELL G W. Cooperative diversity in
wireless networks: Efficient protocols and outage behavior [J].IEEE Transactions on Information Theory,2004.50(12):3062~3080
[4] Chen Yan, Cheng Peng, Qiu Peiliang, et al. Optimal partner
selection strategies in wireless cooperative networks with fixed and variable transmit power [C]//WCNC 2007.Hong Kong: IEEE Press,2007:4080~4084
[5] Truman Chiu-Yam Ng, Wei Yu. Joint optimization of relay
strategies and resource allocations cellular networks [J].IEEE Journal on Selected Areas in Communications,2007.25(2):328~339
[6] Agggelos B, Hyundong S, Moe Z W. Outage optimality of
opportunistic amplify-and-forward relaying [J].IEEE Communication Letters,2007.11(3):261~263
[7] Aggelos B, Hyundong S, Moe Z W, et al. Cooperative diversity
with opportunistic relaying [C]//IEEE WCNC06.Las Vegas: IEEE Press,2006:1034~1039
[8] 顾文珊,张会生,李立欣等.基于协作通信的最佳中继选择方案[J].信
息安全与通信保密,2010.2.
[9]罗瑛.协作通信中一种改进的最佳中继选择算法[J].中国新通信,
2009.3.
[10] ZHAO Yi, ADVE R.LIM T J. Outage probability at arbitrary SNR
with cooperative diversity [J].IEEE Communications Letters.2005.9(8):700~703
关键词:计算思维;表述体系;计算;层次结构;教育;思维习惯
一、问题的提出
2006年3月,周以真(Jeannette M. Wing)教授在国际著名计算机杂志Communications of the ACM上发表了《计算思维》一文[1],并用3种技能定义了“计算思维”,该定义被国际学术界广泛采用。然而人们仍然在问,计算思维是什么?计算思维的核心是什么?计算思维的组成元素是什么?计算思维会因学科的不同而不同吗[2]?
显然,要给出计算思维的一个内涵式的定义是困难的,周以真教授为此给出了一个外延式的定义,并请大家尽可能地补充。周以真教授希望人们不要将精力放在计算思维的定义上,而更多的是将精力放在计算思维的运用上,通过计算思维在各自学科领域创造性地进行科学发现与技术创新。周以真是成功的,她联合美国国家科学基金会的各个学科部门,推动了美国两个重大的国家科学基金研究计划CDI和CPATH,促进了美国以计算思维引领的各学科的发展。在她退出美国国家基金会后不久,她又得到了微软公司的邀请,担任了微软负责研发的副总裁职务。毫无疑问,周以真教授的建议是正确的,通过计算思维,可以在多学科的行动中,进行根本的、范式变化的研究与发现。
一般来说,一个好的研究“主题”在开始的时候,可以先用外延式的方式尽可能拓展开来,随着研究的深入,人们希望建立一个框架,让更多的人更容易理解这个“主题”,持续地发挥这个“主题”的作用,进一步拓展它的应用范围。教育部高等学校大学计算机课程教学指导委员会遵循这样的基本原则,鼓励学校、教师先实践[3-7]。在已有的大量实践基础上,教指委认为,目前很有必要尽快给出计算思维表述体系的一个基本框架,进一步推动这项改革。本文作者受教指委的委托,对此展开了研究工作。
二、计算思维教育的目的
在构建计算思维的表述体系之前,人们希望先明确计算思维的教育目的之所在。本文认为,计算思维教育的目的是培养一种思维习惯,一种像计算机科学家思考问题那样的习惯。
在研究层面,对于一个问题的解决,著名计算机科学家、1998年图灵奖获得者詹姆士・格雷(James Gray)的思路(习惯)是这样的:
(1)首先,对问题进行非常简单的陈述,即要说明解决一个什么样的问题。他认为,一个能够清楚表述的问题,能够得到周围人的支持。虽然不清楚具体该怎么做,但对问题解决之后能够带来的益处非常清楚。
(2)其次,解决问题的方案和所取得的进步要有可测试性。
(3)最后,是整个研究和解决问题的过程能够被划分为一些小的步骤,这样的话就可以看到中间每一个取得进步的过程。
在技术层面,美国华盛顿大学教授、美国国家研究立法委员会计算机文化协会主席史耐德(Snyder Lawrence)教授在其撰写的《新编信息技术导论:技能、概念和能力》一书中指出,人们可以从抽象的角度来思考信息技术。他写道,当你成为数字文人之后,你可以从抽象的角度来思考技术,而且更喜欢(习惯)提以下问题:
(1)对于这个软件,我必须学会用哪些功能,才能帮助我完成任务?
(2)该软件的设计者希望我知道些什么?
(3)该软件的设计者希望我做些什么?
(4)该软件向我展示了哪些隐喻?
(5)为完成指定任务,该软件还需要其他哪些信息?
(6)我是否在其他软件中见到过这个软件中的操作?
在专业层面,对于一个专业的计算问题,笔者认为:从计算的手段来看,我们应当使计算机械化(如算盘、手摇计算机、模拟计算机、电子数字计算机);从计算的过程来看,我们应当使计算形式化(如图灵机、计算理论);从计算的执行来看,我们应当使计算自动化(如冯・诺依曼机)。
在计算思维的研究中,教育部高等学校大学计算机课程教学指导委员会主任委员李廉教授认为,在传统的教学中,计算思维是隐藏在能力培养内容中的,要靠学生“悟”出来,现在要把这些明白地讲出来,让学生自觉地去学习,提高培养质量,缩短培养的时间。从软件开发的角度,他提出了抽象与绑定的研究思路,大致是,抽象是构建和理解复杂系统的工具,规范是现实世界到虚拟世界的抽象;而绑定是虚拟世界到现实世界的重现,所有的软件开发,无非都是抽象与绑定的结果。
美国计算机科学技术教师协会则认为,计算思维的教育应存在于每一所学校的每一堂课程的教学中。他们认为衡量是否采用了计算思维,取决于对于一个要解决的问题,教师能否有意识(习惯)地提出以下问题[8]:
(1)人与计算机的计算能力有多大,各自的局限性是什么?
(2)研究的问题复杂性有多大?
(3)问题解决的判定条件是什么?
(4)什么样的技术可以应用于当前的问题讨论中?
(5)什么样的计算策略更能有效地解决当前的问题?
以上是计算机科学家以及计算机教师协会关于问题解决的思维习惯。随着研究的深入,人们不仅需要总的一般性的认识,人们还希望建立在某种合理框架上的认识,以便系统地、有步骤地、鲜明地培养这种习惯,最终全面提高人们的计算思维能力。
三、计算思维表述体系的框架
计算思维表述体系的框架,涉及计算思维的组成元素以及这些组成元素之间的相互关系。在美国CPATH计划的支持下,经过几年的努力,已取得一些成果。如在CPATH计划的支持下,美国德保罗大学(DePaul University)的教授们就在ACM前主席Denning“伟大的计算原理”概念分类的基础上构建了一个教学框架,把通识教育中的核心技能――逻辑推理、写作和伦理联系了起来[9]。Denning设想,在向各学科介绍计算原理时要力争做到通俗易懂,通过大众化的解读来建立一种超越学科范畴的计算共识,由此构建不同学科之间的全新关系。他表示,计算原理可以被归为7个类别,每个类别都从一个独特的视角去看待计算本身。根据Denning的观点,7个伟大的计算原理分别是:计算、通信、协作、记忆、自动化、评估和设计[10]。
1.基于“伟大的计算原理”计算思维表述体系框架
Denning的7项“伟大原理”奠定了一个基础,这个基础可以帮助人们认识和组织计算思维的实例,并将它们进行有效的分类。同时,这个基础也可以认为是一个框架,这个框架可以帮助人们将计算思维运用到计算机科学以外的领域。在基于“伟大的计算原理”研究中,我们认为,“抽象”也是一个伟大的计算原理,应纳入框架之中。另外,Denning划分的概念之间没有层次和逻辑关系,还需进一步完善。下表给出基于“伟大的计算原理”构建的计算思维表述体系框架。
2.计算思维表述体系中的基本概念
在周以真的文章中,计算思维指的是一种能力,这种能力通过熟练地掌握计算机科学的基础概念而得到提高。周以真将这些基础概念用外延的形式给出:约简、嵌入、转化、仿真、递归、并行、抽象、分解、建模、预防、保护、恢复、冗余、容错、纠错、启发式推理、规划、学习、调度等。周以真希望人们对这些基础概念继续补充,本文认为,这些基础概念至少还应该包括CC1991 给出的12个核心概念:绑定、大问题的复杂性、概念模型和形式模型、一致性和完备性、效率、演化、抽象层次、按空间排序、按时间排序、重用、安全性、折中与结论。显然,12个核心概念与周以真给出的基础概念有些是重合的,如“建模”与“概念模型和形式模型”。下面,对以上概念进行分类,力求减少它们的交集。另外,我们希望更多的学者对这些概念(包括扩展的基础概念)在研究的基础上进行更有效的分类,以使该框架更加完善。
在本文给出的计算思维表述体系框架中,“计算”是一个中心词,是第一层次的概念,其他7个概念以“计算”为中心并服务于“计算”;7个概念中的“抽象、自动化和设计”为第二层次的概念,是从不同方面对“计算”进行的描述;“通信、协作、记忆、评估”蕴含在“抽象、自动化和设计”三个概念之中,是计算机科学中仅次于“抽象、自动化和设计”的基础概念,属框架中第三层次的概念(如下图所示)。对这些概念的理解,有助于加深人们对“计算”的认知。下面,分别对这些概念进行定义。
计算思维基本概念的层次关系图
(1)计算(Computation)是执行一个算法的过程。从一个包含算法本身的初始状态开始,输入数据,然后经过一系列中间级状态,直到达到最终也即目标状态。计算不仅仅是数据分析的工具,它还是思想与发现的原动力。可以认为,计算学科及其所有相关学科的任务归根结底都是“计算”,甚至还可以进一步地认为,都是符号串的转换。效率是计算问题的核心,以计算思维为切入点的大学计算机教学改革最大的亮点在于充分地重视“计算复杂性”这个与“效率”有密切联系的核心概念。一般来说,掌握一个概念往往需要举出反映该概念本质的3个经典案例和3个反例。计算包含的核心概念有:大问题的复杂性、效率、演化、按空间排序、按时间排序;计算的表示、表示的转换、状态和状态转换;可计算性、计算复杂性理论等。
(2)抽象(Abstraction)是计算的“精神”工具。周以真认为,计算思维的本质是抽象化。至少在两个方面,计算学科中的抽象往往比数学和物理学更加丰富和复杂。第一,计算学科中的抽象并不一定具有整洁、优美或轻松的可定义的数学抽象的代数性质,如物理世界中的实数或集合。例如,两个元素堆栈就不能像物理世界中的两个整数那样进行相加,算法也是如此,不能将两个串行执行的算法“交织在一起”实现并行算法。第二,计算学科中的抽象最终需要在物理世界的限制下进行工作,因此,必须考虑各种的边缘情况和可能的失败情况。抽象包含的核心概念有:概念模型与形式模型、抽象层次;约简、嵌入、转化、分解、数据结构(如队列、栈、表和图等)、虚拟机等。
(3)自动化(Automation)是计算在物理系统自身运作过程中的表现形式(镜像)。什么能被(有效地)自动化是计算学科的根本问题。这里的“什么”通常是指人工任务,尤其是认知任务,可以用计算来执行的任务。我们能够使用计算机来下棋吗?能够解决数学问题吗?给出关键字能够在因特网上搜索到我们头脑中想要的东西吗?能够实时地将汉语和英语互译吗?能够指引我们开车穿过偏僻地形的地区吗?能够准确地标记图像吗?能够看到我们眼睛看到的东西吗?在周以真的论文中,她认为,计算是抽象的自动化。自动化意味着需要某种计算机来解释抽象。这种计算机是一个具有处理、存贮和通信能力的设备。计算机可以被认为是一台机器,也可以是一个人,还可以是人类和机器的组合。自动化包含的核心概念有:算法到物理计算系统的映射,人的认识到人工智能算法的映射;形式化(定义、定理和证明)、程序、算法、迭代、递归、搜索、推理;强人工智能、弱人工智能等。
(4)设计(Design)是利用学科中的抽象、模块化、聚合和分解等方法对一个系统、程序或者对象等进行组织。在软件开发中,设计这个词意味着两件事:体系结构和处理过程。一个系统的体系结构可以划分为组件以及组件之间的交互活动和它们的布局。处理过程意味着根据一系列步骤来构件一个体系结构。好的设计有正确性、速度、容错性、适应性等4个标准。正确性意味着软件能符合精确的规格。软件的正确性是一项挑战,因为对一个复杂系统来说精确的规格是很难达到的,而证明本身就是一个棘手的问题。速度意味着我们能够预测系统在我们所期望的时间内完成任务。容错性意味着尽管有一些小错误但软件和它的主系统仍然能够正确地运行。适应性意味着一个系统的动态行为符合其环境的使用。设计包含的核心概念有:一致性和完备性、重用、安全性、折中与结论;模块化、信息隐藏、类、结构、聚合等。
(5)通信(Communication)是指信息从一个过程或者对象传输到另一个过程或者对象。通信包含的核心概念有:信息及其表示、香农定理、信息压缩、信息加密、校验与纠错、编码与解码等。
(6)协作(Coordination)是为确保多方参与的计算过程(如多人会话)最终能够得到确切的结论而对整个过程中各步骤序列先后顺序进行的时序控制。协作包含的核心概念有:同步、并发、死锁、仲裁;事件以及处理、流和共享依赖,协同策略与机制;网络协议、人机交互、群体智能。
(7)记忆(Recollection)是指通过实现有效搜索数据的方法或者执行其他操作对数据进行编码和组织。计算思维表述体系中的记忆是人们讨论大数据背后的原理之所在,没有“记忆”这个伟大原理,大数据就是空谈。记忆包含的核心概念有:绑定;存储体系、动态绑定(names、Handles、addresses、locations)、命名(层次、树状)、检索(名字和内容检索、倒排索引);局部性与缓存、trashing抖动、数据挖掘、推荐系统等。
(8)评估(Evaluation)是对数据进行统计分析、数值分析或者实验分析。评估包含的核心概念有:可视化建模与仿真、数据分析、统计、计算实验;模型方法、模拟方法、benchmark;预测与评价、服务网络模型;负载、吞吐率、反应时间、瓶颈、容量规划等。
四、计算思维的作用
计算思维表述体系的建立,有助于计算领域以外的人了解和运用计算思维,伴随经典实例的计算概念讲授,可以让计算领域以外的人了解计算的美丽与愉悦,拓展计算思维的应用范围。虽说计算作为一门学科存在的时间不长,但人们已经认识到计算在科学界的影响力。1982年,诺贝尔物理学奖得主Ken Wilson在他的获奖演讲中就提到计算在他的工作中扮演的重要角色。2013年的诺贝尔物理学奖、生理学或医学奖都与“计算”有关,化学奖的主要成果“复杂化学系统多尺度模型的创立”,这更是一个典型的用计算思维的方式――结构和算法的过程得到科学新发现的实例。
在分子生物学领域取得的研究进展中,计算和计算思维已经成为其核心内容。如今在研究许多复杂的物理过程(如群鸟行为)时,最佳方式也是将其理解为一个计算过程,然后运用算法和复杂的计算工具对其进行分析。从计算金融学到电子贸易,计算思维已经渗透到整个经济学领域。随着越来越多的档案文件归入各种数据库中,计算思维正在改变社会科学的研究方式。甚至音乐家和其他艺术家也纷纷将计算视为提升创造力和生产力的有效途径。
总的来说,计算思维为人们提供了理解自然、社会以及其他现象的一个新视角,给出了解决问题的一种新途径,强调了创造知识而非使用信息,提高了人们的创造和创新能力。
1.理解自然、社会等现象的新视角
在许多不同的科学领域,无论是自然科学还是社会科学,底层的基本过程都是可计算的,可以从计算思维的新视角进行分析。其中,“人类基因组计划”就是一个典型案例。
用数字编码技术来解析DNA串结构的研究是计算思维的一个经典实例,其为分子生物学带来了一场革命。将有机化学的复杂结构抽象成4个字符组合而成的序列后,研究人员就可以将DNA看作一长串信息编码。DNA串结构实际就是控制有机体发育过程的指令集,而编码是这一指令集的数据结构,基因突变就类似于随机计算,细胞发育和细胞间的相互作用可视为协同通信的一种形式。沿着这一思路,研究人员已经在分子生物学领域取得了长足的进展,最具代表性成绩就是“人类基因组计划”中包括的人体内全部DNA解码、基因测序并绘制人类基因图谱、开发基因信息分析工具等一系列任务的圆满完成。
2.解决问题的新方法
折纸又称“工艺折纸”,是一种以纸张折成各种不同形状的艺术活动。折纸发源于中国,在日本得到了很大的发展,历经若干世纪,现在的日本折纸已成为一项集艺术审美、数学和计算机科学于一身的新艺术,而且还催生了名为“计算折纸”的新领域。该领域通过与折纸算法有关的理论来解答折纸过程中遇到的问题。如在折出某个物品之前事先将这一物品的外形抽象成一张图,这就用到了图论。一旦将某个物体抽象为图的形式就可以得到描述整个折叠顺序的算法,这就意味着该物品对应的折纸过程完全可以实现自动化,运用计算思维的这种抽象和自动化方法还可以做出更多更为复杂的折纸。折纸艺术家可以在完成折纸工序自动化的过程中,从折纸创新的角度向人们更为具体地介绍折纸的基本概念。在美国德保罗大学基于计算思维的教学改革中,已成功地将这种解决问题的新方法及其案例融入课程,特别是人文类课程的教学中[9]。
3.创造知识
采用计算思维还可以创造大量的新知识,比如,亚马逊公司“网上购物推荐系统”创造的新知识。亚马逊公司成立时间并不长,但通过客户浏览网站的痕迹和购物的历史记录,该公司已经积累了大量的客户信息。传统的统计方法成为亚马逊公司手中的有力杠杆,借力这些信息,公司得以及时跟踪客户的喜好和兴趣以及公司的库存产品。但是这些累积信息中可能包含一些无法基于视觉或者手动检测的数据模式,而知识的创造过程就是发现并且明确地表述出那些藏而不露但意义深远的数据模式。亚马逊公司利用各种方法对这些数据进行深入挖掘并用于各项决策中,比如给某位顾客推荐某些书。亚马逊的推荐系统正是建立在这些客户留下的数据信息的基础上,比如该客户的历史购物记录以及购买了同一件商品的其他客户的购物记录。就是这些规则构成了亚马逊的推荐系统,而它正是该公司商业模式的核心部分,也是Netflix prize算法竞赛中列举的在线商务系统的核心。
4.提高创造力和创新力
计算思维可以极大地提高人们的创造力。比如在音乐制作领域,依靠计算机的软硬件可以产生大量的合成声音,创作音乐。从最简单到最复杂的任何声音都可以通过计算机的软件来合成。基于声音物理特性的理解以及对这种特性在计算机中存储的认识,人们可以采用计算思维了解声音的合成过程与音乐的制作过程。通过音乐合成软件的研制,人们可以很自然地将编程和作曲思维变成一种平行关系,并采用这些软件产生大量的高质量音乐作品。实际上,鉴于这个目的,人们已经开发出不少功能强大的音乐制作编程语言,如Nyquist、JFugue、DarkWave Studio等。
参考文献:
[1] Jeannette M. Wing. Computational Thinking[J]. Communications of the ACM, 2006, 49(3).
[2] National Research Council. Report of a workshop on the scope and nature of computational thinking[M]. National Academies Press, 2010.
[3] 教育部高等学校大学计算机课程教学指导委员会. 计算思维教学改革宣言[J]. 中国大学教学,2013(7).
[4] 九校联盟(C9)计算机基础教学发展战略联合声明[J]. 中国大学教学,2010(9).
[5] 陈国良. 计算思维:大学计算教育的振兴,科学工程研究的创新[J]. 中国计算机学会通信,2012,8(1).
[6] 陈国良,董荣胜. 计算思维与大学计算机基础教育[J]. 中国大学教学,2011(1).
[7] 李廉. 以计算思维培养为导向深化大学计算机课程改革[J]. 中国大学教学,2013(4).
[8] Pat Philips. Computational Thinking: A problem-solving tool for every classroom[EB/OL]. http:///Resources/sub/ ResourceFiles/ComputationalThinking.pdf.