2025 高中信息技术数据与计算之算法的关键路径算法课件

一、为何要学习关键路径算法？从生活场景到学科价值的双重视角演讲人01为何要学习关键路径算法？从生活场景到学科价值的双重视角02关键路径算法的核心概念与计算逻辑：从术语到步骤的逐层拆解03关键路径算法的实践应用与教学建议：从课堂到生活的迁移拓展04总结：关键路径算法的核心价值与学科意义目录2025高中信息技术数据与计算之算法的关键路径算法课件各位老师、同学们：作为一名深耕高中信息技术教学十余年的一线教师，我始终认为“数据与计算”模块是培养学生计算思维的核心载体。而关键路径算法作为项目管理与任务调度的经典算法，不仅是《普通高中信息技术课程标准（2017年版2020年修订）》中“数据与计算”主题下的重要内容，更是将抽象算法与真实问题解决相联结的典型案例。今天，我们将以“关键路径算法”为核心，从概念解析到实践应用，逐步揭开这一算法的神秘面纱。01为何要学习关键路径算法？从生活场景到学科价值的双重视角1生活中的“卡脖子”问题：关键路径的直观感知大家是否遇到过这样的场景？周末计划为家人准备一顿丰盛的午餐，需要完成洗菜（10分钟）、切菜（15分钟）、炒菜（20分钟）、蒸米饭（30分钟）、摆碗筷（5分钟）。如果按顺序操作，总时长会是10+15+20+30+5=80分钟，但实际最优安排是：先蒸米饭（30分钟），在蒸米饭的同时完成洗菜（10）、切菜（15）、炒菜（20），最后摆碗筷（5），总时长仅需30+5=35分钟。这里的“蒸米饭”就是整个任务的“关键”——它的时长直接决定了总工期，这就是关键路径的雏形。类似的场景在生活中比比皆是：校园文化节的筹备（场地布置、节目排练、物资采购）、暑假研学活动的规划（路线设计、住宿预订、安全预案）……当任务被分解为多个子活动且存在依赖关系时，如何找到“最耗时的路径”，从而优化资源分配、缩短总工期，正是关键路径算法的核心价值。2学科中的“计算思维”：从算法到素养的进阶《课程标准》明确指出，“数据与计算”模块需培养学生“通过分析问题，抽象特征，建立模型，合理组织数据；通过算法设计与实现，解决实际问题”的能力。关键路径算法恰好涵盖了这一完整过程：问题抽象：将任务分解为活动（Activity）与事件（Event），构建有向无环图（DAG）；模型建立：通过节点表示事件（任务的开始或结束），边表示活动（任务的执行过程），边权为活动时长；算法实现：计算每个事件的最早开始时间（EarliestTime,ET）与最晚开始时间（LatestTime,LT），确定关键路径（CriticalPath）；2学科中的“计算思维”：从算法到素养的进阶问题解决：通过调整关键路径上的活动，优化总工期。这一过程不仅能强化学生对“图结构”“动态规划”等数据结构与算法的理解，更能培养其系统思维、优化意识与工程实践能力——这正是信息时代公民必备的核心素养。02关键路径算法的核心概念与计算逻辑：从术语到步骤的逐层拆解1基础术语：构建算法的“语言体系”要理解关键路径算法，首先需明确以下核心术语（结合图1-任务流程图示例讲解）：|术语|定义|示例（以“午餐准备”为例）||---------------------|----------------------------------------------------------------------|--------------------------------------------||活动（Activity）|任务中的具体操作，需消耗时间和资源，用有向边表示（如A→B）|洗菜、切菜、蒸米饭等具体操作||事件（Event）|活动的开始或结束点，是状态的转变，用节点表示（如节点1、节点2）|“开始准备午餐”（节点1）、“米饭蒸熟”（节点3）|1基础术语：构建算法的“语言体系”|有向无环图（DAG）|所有边有方向且无环的图，用于表示活动间的依赖关系|蒸米饭需在“开始准备”后（节点1→3），炒菜需在切菜后（节点2→4）||最晚开始时间（LT）|事件最晚必须发生的时间，等于所有后继事件LT减去对应活动时长的最小值|节点2（切菜完成）的LT=节点4（炒菜完成）LT-20分钟||最早开始时间（ET）|事件最早可能发生的时间，等于所有前驱事件ET加上对应活动时长的最大值|节点4（炒菜完成）的ET=节点2（切菜完成）ET+20分钟||关键路径|从起点到终点所有路径中，总时长最长的路径（ET=LT的事件组成的路径）|蒸米饭（30分钟）→摆碗筷（5分钟），总时长35分钟|2计算步骤：前向与后向的双向推导关键路径的计算可分为两个阶段：前向计算（确定ET）与后向计算（确定LT），最终通过比较ET与LT确定关键活动（CriticalActivity），进而找到关键路径。以下以“校园文化节舞台搭建”任务为例（图2-舞台搭建任务流程图），详细说明计算过程：2计算步骤：前向与后向的双向推导2.1前向计算：从起点到终点推导ET起点事件（节点1）的ET=0（任务尚未开始）；后续事件的ET=max{前驱事件ET+对应活动时长}：例如，节点2（材料进场完成）的ET=节点1（项目启动）ET+材料运输时长（2天）=0+2=2天；节点3（框架搭建完成）的ET=节点2（材料进场完成）ET+框架搭建时长（3天）=2+3=5天；节点4（灯光安装完成）的ET=节点2（材料进场完成）ET+灯光运输时长（1天）+灯光安装时长（2天）=2+1+2=5天（或直接取前驱事件ET+活动时长：节点2→4的活动时长为3天，故ET=2+3=5天）；2计算步骤：前向与后向的双向推导2.1前向计算：从起点到终点推导ET终点事件（节点5）的ET=max{节点3→5的时长（2天）+节点3的ET（5天），节点4→5的时长（1天）+节点4的ET（5天）}=max{5+2=7,5+1=6}=7天（总工期为7天）。2计算步骤：前向与后向的双向推导2.2后向计算：从终点到起点推导LT终点事件（节点5）的LT=ET=7天（总工期不能延长）；前驱事件的LT=min{后继事件LT-对应活动时长}：例如，节点3（框架搭建完成）的LT=节点5（舞台完成）LT-框架收尾时长（2天）=7-2=5天；节点4（灯光安装完成）的LT=节点5（舞台完成）LT-灯光调试时长（1天）=7-1=6天；节点2（材料进场完成）的LT=min{节点3的LT-框架搭建时长（3天）=5-3=2天，节点4的LT-灯光安装时长（3天）=6-3=3天}=2天；起点事件（节点1）的LT=节点2的LT-材料运输时长（2天）=2-2=0天（与ET一致，说明无缓冲时间）。2计算步骤：前向与后向的双向推导2.2后向计算：从终点到起点推导LT2.2.3确定关键路径：ET=LT的事件与活动当某个事件的ET=LT时，该事件为关键事件；若活动的起点事件ET+活动时长=终点事件ET（即该活动无缓冲时间），则该活动为关键活动。在“舞台搭建”案例中：节点1（ET=0,LT=0）、节点2（ET=2,LT=2）、节点3（ET=5,LT=5）、节点5（ET=7,LT=7）为关键事件；活动1→2（材料运输，2天）、活动2→3（框架搭建，3天）、活动3→5（框架收尾，2天）为关键活动；关键路径为1→2→3→5，总时长2+3+2=7天（与总工期一致）。3常见误区：从“计算错误”到“概念混淆”的避坑指南在教学实践中，学生常出现以下问题，需重点提醒：忽略“max”与“min”的选择：前向计算ET时，需取所有前驱路径的最大值（因为必须等所有前置活动完成才能开始后续活动）；后向计算LT时，需取所有后继路径的最小值（因为后续活动的最晚开始时间限制了当前活动的最晚完成时间）。混淆活动与事件的时间：活动的时长是边权，事件的时间是节点属性；关键路径由关键活动组成，而非关键事件的简单连接。遗漏“虚活动”的处理：在复杂任务中，可能存在“虚活动”（DummyActivity，时长为0，仅表示依赖关系），需在计算时将其视为普通活动，但不影响总时长。03关键路径算法的实践应用与教学建议：从课堂到生活的迁移拓展1真实情境下的算法应用：从教材到生活的联结关键路径算法并非仅存在于理论模型中，其在实际项目管理中有着广泛应用。以下是两个典型场景：1真实情境下的算法应用：从教材到生活的联结1.1软件开发项目管理某团队开发一款校园考勤APP，任务分解如下：需求分析（5天）→原型设计（3天）→后端开发（7天）→前端开发（6天）→联调测试（4天）；同时，需求分析（5天）→数据库设计（4天）→后端开发（7天）。通过绘制DAG并计算关键路径（需求分析→原型设计→前端开发→联调测试？或需求分析→数据库设计→后端开发→联调测试？），学生可发现：后端开发需等待数据库设计完成（5+4=9天），而前端开发需等待原型设计完成（5+3=8天），因此关键路径为需求分析（5）→数据库设计（4）→后端开发（7）→联调测试（4），总工期5+4+7+4=20天。若要缩短工期，需优化关键路径上的活动（如并行数据库设计与原型设计）。1真实情境下的算法应用：从教材到生活的联结1.2个人学习计划优化学生可将关键路径算法应用于备考规划：数学复习（基础题3天→综合题4天→真题训练2天）；语文复习（古诗文2天→阅读3天→作文2天）；需同时完成物理实验报告（1天），可穿插在数学或语文复习的间隙。通过计算，数学的关键路径为基础题（3）→综合题（4）→真题训练（2），总9天；语文的关键路径为古诗文（2）→阅读（3）→作文（2），总7天。因此，总备考周期由数学的9天决定，物理实验报告可在语文复习的第3天（阅读阶段）完成，不影响总工期。2高中课堂的教学策略：从“学算法”到“用算法”的转变为帮助学生真正掌握关键路径算法，建议采用以下教学策略：2高中课堂的教学策略：从“学算法”到“用算法”的转变2.1情境驱动：用“学生身边的问题”激活兴趣选择学生熟悉的场景（如社团招新筹备、运动会组织、研学活动规划）作为案例，让学生通过小组合作分解任务、绘制DAG、计算关键路径。例如，在“校园文化节筹备”项目中，学生需明确“场地布置”“节目排练”“物资采购”等活动的依赖关系（如物资采购完成后才能布置场地），并计算总工期。2高中课堂的教学策略：从“学算法”到“用算法”的转变2.2工具辅助：从手工计算到编程实现的进阶初级阶段：使用纸笔画图，手工计算ET与LT，强化对算法逻辑的理解；进阶阶段：借助Excel表格或在线绘图工具（如Visio、ProcessOn）自动生成DAG，并验证手工计算结果；高阶阶段：用Python编写关键路径算法程序（示例代码如下），输入活动列表（包含前驱活动与时长），输出关键路径与总工期。defcritical_path(activities):#构建事件节点与邻接表nodes=set()adj={}forainactivities:2高中课堂的教学策略：从“学算法”到“用算法”的转变2.2工具辅助：从手工计算到编程实现的进阶start,end,duration=anodes.add(end)ifstartnotinadj:adj[start]=[]adj[start].append((end,duration))#前向计算ETet={node:0fornodeinnodes}fornodeinsorted(nodes):#按拓扑顺序遍历ifnodeinadj:nodes.add(start)2高中课堂的教学策略：从“学算法”到“用算法”的转变2.2工具辅助：从手工计算到编程实现的进阶for(end,duration)inadj[node]:ifet[end]et[node]+duration:et[end]=et[node]+duration#后向计算LTlt={node:et[max(nodes)]fornodeinnodes}#终点LT=总工期fornodeinreversed(sorted(nodes)):#逆拓扑顺序遍历ifnodeinadj:for(end,duration)inadj[node]:2高中课堂的教学策略：从“学算法”到“用算法”的转变2.2工具辅助：从手工计算到编程实现的进阶iflt[node]lt[end]-duration:lt[node]=lt[end]-duration2高中课堂的教学策略：从“学算法”到“用算法”的转变#确定关键活动critical_activities=[]forainactivities:start,end,duration=aifet[start]==lt[start]andet[end]==lt[end]andet[start]+duration==et[end]:critical_activities.append(a)returncritical_activities,et[max(nodes)]示例输入：活动列表（起点,终点,时长）2高中课堂的教学策略：从“学算法”到“用算法”的转变#确定关键活动activities=[("A","B",2),("A","C",3),("B","D",4),("C",