数据结构与算法的关系教学设计高中信息技术新浙教版选修1数据与数据结构.docx

数据结构与算法的关系教学设计课程标准 和教学目标数据结构与算法的关系教材内容：5. 1数据结构与算法的关系适应的课程标准：1.3结合生活实际，理解数据结构的概念，认识数据结构在解决问题过程中的重要作用。1.7通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。教学目标：能结合具体程序实例，理解算法效率分析 的一般方法。回顾线性结构的特性，总结不同数据结构 对算法效率的影响。指向的核心素养：信息意识：本条目通过设置真实问题情境，引导 学生发现不同的数据结构对算法效率有不同的影 响，在处理实际问题能够有意识地选择合适的数据 结构进行问题建模。计算思维：运用简化、归约的基本思想方法，即 排除掉其它无关的影响因素，从理论角度对实际程 序进行算法的效率分析，对算法的运行效率进行评 估、预测，并进行验证。算法与数据结构关系密切， 不同的数据结构对算法的效率也有影响，考虑到实 际运用场景的需要，能够选择合适的数据结构。数字化实践：通过创设数字化学习环境，鼓励学 生根据实际解决问题的需要，使用思维导图等数字 化工具开展自主学习和协作探究，演示不同数据结 构对算法的影响，提升数字化实践素养。信息社会责任：能够思考、归纳出数据结构与算 法在社会生活中的各项运用，它所带来的效率提升 对科技发展、社会进步的重要意义。学习环境：网络机房、算法可视化工具建议课时：1课时教学活动 设计教学环节教学过程设计意图情境导入导入1:在多媒体课件上展示“高斯故事”，请学生对算 术求和的公式法和累加求和算法的差异之处，以对算法 效率形成初步感性认识。导入2：互联网的搜索引擎能够快速地访问与检索信息， Google做过一个试验，显示10条搜索结果的页面载入 需要0. 4秒,显示30条搜索结果的页面载入需要0. 9秒， 结果后者使得Google总的流量和收入减少了 20%o Google地图上线的时候,首页大小有100KB,后来下降 到7080KB。结果，流量在第一个星期上升了 10%,接下 来的3个星期又再上升了 25%O Amazon的统计也显示了 相近的结果，首页打开时间每增加100毫秒，网站销售 量会减少1%O通过导入生活中的算法问题和计算机科学 领域的算法问题，以便顺利过渡到算法“时 间复杂度”、“空间复杂度”的分析。新课教学活动一通过分析上述“导入1”案例，请学生比较教材中“算 法一”、“算法二”及其延伸等具体程序实例。算法一：n=int (input ()#执行1次s=(l+n) *n/2#执行1次print (s)#执行1次n=int (input ()#执行1次s=0#执行1次for i in range (1,n+1)：#执行n+1次s = s+i#执行n次print (s)#执行1次算法二:算法二的延伸：n=int (input ()# 执行 1 次s=0x=0for i in range(1,n+1):for j in range(1,n+1):x=x+l#执行n*n次s=s+xprint (s)# 执行 1 次 有了对实际程序实例的对比分析后，学生 对算法的时间复杂度概念有了基本的理 解。这里主要侧重于理论分析，即比较不 同程序的执行次数。需要注意的是，“时间 复杂度”并不与程序实际运行的“时间耗 费”完全等价。程序的时间耗费依赖于不 同的计算机硬软件等环境因素，并且程序 的运行时间往往还与测试数据的规模也有 很大关系，比如排序时，小量数据在不同 算法测试时可能差异几乎为零，而有一百 万、一千万随机数字进行排序，那不同算 法的差异就比较大了。通过教材中简单易 懂的三个程序实例，搭建起学习的“脚手 架”，可以让学生初步理解算法的时间复杂 度分析的一般方法。通过对实际案例的对 比分析，引导学生自主阅读教材内容，加 深理解，从而实现知识的内化。在此基础 上，教师可以引入“阶”的概念，简单介 绍不同阶的时间复杂度。小组讨论新课教学活动二接着引导学生分析“导入2”案例，并与教材中下列案 例进行比较分析： 天气预报程序必须在指定时间前完成气象指数的 计算。如果不能按时计算出预报结果，这个算法就毫无 价值。 数字相机的人脸识别程序，必须在几分之一秒内完 成工作。过慢的算法会带来糟糕的用户体验，照相机的 制造商不可能采用。问题导学：以我们曾经学习过的数组和链表为例，试回 忆元素访问、插入、删除方面的效率差异，并完成下列 表格。算法效率对实际生活产生非常大的影响， 对算法效率分析可以从两个维度展开：“时 间复杂度”即算法的时间耗费，“空间复杂 度”即算法的空间耗费。在此基础上，可 以设问：“举例说明算法时间复杂度与空间 复杂度存在怎样的关系？ ”引导学生回忆 前面所学知识，教师可以提供如下案例： 某程序需要判断某年是不是闰年，每次给 一个年份，都要通过计算得到是否是闰年 的结果。如果这种计算比较频繁的话，还 有另一个办法就是，事先建立一个有2050 个元素的数组(年数略比现实多一点)，然 后把所有的年份按下标的数字对应，如果 是闰年，此数组项的值就是1,如果不是值 为0o这样，所谓的判断某一年是否是闰年, 就变成了查找这个数组的某一项的值是多 少的问题。假设输入数据规模为n,这时算 法的时间复杂度降为0(1),但是空间耗费 变大了，需要存储2050个0或1。这就是 典型的“以空间换时间”的算法。通过对以前所学知识的总结与归纳、提升, 可以立足于“最近发展区”，通过旧知构建 新知，实现抽象概念建立的平滑过渡，培数组链表应适合数据规模确不需要预先分配用定且在处理过程存储空间，结点个场中保持数据规模数不受限制景稳定的问题组用一段连续的存由结点构成，每个织储单元来依次存结点中包含数据结储数组元素区域和指针区域，构相邻结点间通过 指针链接操访问：数据访问访问：需要从头结作效率较高点开始寻找特时间复杂度：时间复杂度：性插入或删除：需插入或删除：只要要移动大量数组找出某个结点位元素置，可以方便操作时间复杂度：时间复杂度：教师可以快速展示数组、链表中插入新元素之后的基本 操作过程，或者引导学生使用相应的信息工具直观呈现 二者操作的算法效率差异养学生数据结构与算法关系密切相关的意 识。本任务可以看成是任务一在本任务中 的自然延伸。学生在回顾数组、链表中元 素访问、插入、删除的操作时，可以利用 相关信息工具进行直观演示即可，并不需 要代码具体实现，从而可以保证课堂效率。引自教材 图2.1. 5数组中插入新数据的过程引自教材图2.2. 3单向链表中插入新结点过程拓展学习有人认为现代计算机的运行速度足够快了，已经没有必 要研究算法的效率了，通过导入2中的案例，你有什么 体会？可以让学生自主学习和分组讨论。教师总结：大数据时代对算法的效率要求 更图了，而不是口有口J无。帮助学生建立起算法效率分析的一般方 法，并能与数据结构联系起来。课堂小结1 .算法效率分析的一般方法，时间复杂度的基本概念；2 .数据结构与算法的紧密关系；3 .合理评估算法效率的重要性。概念学习需要先从生活实例出发，通过分 析实例，培养学生对概念的感性认识，为 深刻理解概念提供事实基础；有了事实基 础和体验过程，还需要对知识进行归纳和 总结，纳入原有知识结构，实现知识的升 华。作业布置所有学生都应当完成本节课的1个问题与讨论和2个思 考与练习。教学设计 思路本课内容分配1课时完成，内容为数据结构与算法的关系。本节内容可在回忆、梳理本书前四章内容的基础上进 行归纳、提升，相关概念在本章后续学习中进一步深化。本节第一部分通过“算法一”、“算法二”及其延伸等具体 程序实例，介绍算法效率分析中的时间复杂度分析方法。第二部分则从学生已经熟悉的线性结构出发，简要分析数组 与链表在元素访问、插入、删除方面的效率差异，体现出数据结构与算法效率之间的紧密关系。首先，要让学生对“时间复杂度”的概念建立初步认识，可以举一些学生比较熟悉的生活实例，或者熟悉的故事。 教材中的示例程序“算法一”、“算法一”即可引用伟大数学家高斯小学时的故事展开。算法不同的实现方式，导致 解决问题的效率上差异。其次，在对“时间复杂度”有一定认识的基础上，可以对“算法二”进行延伸，引导学生分析程序中的时间复杂 度与数据规模的关系，进而引出不同“阶”的时间复杂度。再次，解决同一个问题，因为算法设计、数据结构选择的不同导致算法效率特别是运行时间上的差异。在课前准 备一些与算法效率相关的程序实例，在课堂上老帅可以结合这些实例，直观呈现程序运行时间上的差异结果。本节在全章中起到提纲挈领的作用，教学中既要注重基本概念的理解和掌握，又要关注兴趣的形成。数据结构、 逻辑结构、存储结构、算法效率、时间复杂度、空间复杂度这些知识比较抽象，应避免单一的概念讲解，立足学生最 近发展区，充分挖掘前面四章的铺垫、展现学生熟悉的算法实例（项目），结合这些实例的剖析，使学生从抽象到具 体地理解数据结构与算法的紧密联系，算法效率的一般分析方法，如教材中有关线性结构中数组与链表之间区别的问 题与讨论。在学生掌握时间复杂度的基础上，让学生主动探究空间复杂度的度量问题，此时可结合教材的“空间复杂 度度量”问题与讨论。针对 核心素养 培养的 设计考虑信息意识、信息社会责任：本条目通过设置真实问题情境，引导学生发现不同的数据结构对算法效率有不同的影响， 在处理实际问题能够有意识地选择合适的数据结构进行问题建模。本节课在导入时选择了两个案例，第一个案例简单 易懂，贴近学生的学习实际，可以方便迁移到新知。第二个案例涉及到的算法比较复杂，尽管有的学生可能有所了解.， 但不宜展开多讲。教师引导总结提升到理论层次的方式，目的是培养学生重视算法效率，并选择合适的数据结构。能 够思考、归纳出数据结构与算法在社会生活中的各项运用，它所带来的效率提升对科技发展、社会进步的重要意义。 日算思维：实际生活场景中如搜索引擎、智能地图、自动驾驶的算法非常复杂，也难以进行详细、具体、全面的分析， 需要运用简化、归约的基本思想方法，即排除掉其它无关的影响因素，从理论角度对实际程序进行算法的效率分析， 对算法的运行效率进行评估、预测，并进行验证。通过导入的案例一，即三个简单的小程序即可阐明算法复杂度的基 本概念。数字化学习与创新：通过创设数字化学习环境，鼓励学生根据实际解决问题的需要，使用思维导图等数字化工具开展 自主学习和协作探究，演示不同数据结构对算法的影响，提升数字化实践素养。本节在任务一中，主要是总结线性结构中各种基本操作基础上，进一步提炼升华旧知，回顾数组、链表操作的过程中，鼓励学生根据实际解决问题的需要, 恰当选择信息工具，不需要实现代码，仅演示相应操作即可，以达到提高效率的目的。