计算机科学概论（微课版）课件 第6-10章 数据结构- 人工智能

高等学校计算机专业核心课程精品系列教材计算机科学概论（微课版）第6章数据结构数据表示·数组·链表·结构体·抽象数据类型数据不能杂乱地堆在存储设备里。本章从旅行信息整理与成绩管理两个例子出发，认识四类基本结构，吃透数组、链表与结构体，再抽象出栈、队列、树、图四种数据类型。图6-13树（教材第108页）LEARNINGGOALS学习目标与知识导图第6章知识导图（教材第98页）本章学习目标❶理解数据结构的定义及其在计算机科学中的重要性；❷掌握集合、线性、树状、图状四类结构的特点与应用场景；❸理解数组的定义、操作及多维数组的应用；❹掌握链表的定义、操作及其与数组的比较；❺理解结构体在组织复杂数据时的应用。能力落点：为编程实践和算法设计打下数据结构基础。计算机科学概论（微课版）｜第6章数据结构02CONTENTS本章目录6.1数据表示及数据结构信息世界层的数据表示｜四类基本结构6.2数组数组的定义｜数组的操作｜多维数组6.3链表数组与链表｜链表的操作｜链表的类型6.4结构体结构体的定义｜结构体的操作｜结构体数组6.5抽象数据类型定义｜栈｜队列｜树｜图章末6.6本章小结｜6.7拓展知识｜6.8课后习题计算机科学概论（微课版）｜第6章数据结构036.1数据表示及数据结构·导入信息世界层的数据表示情境：旅行爱好者的信息困境你热爱旅行，每次出行都收集大量信息：景点介绍、交通安排、餐厅推荐……旅行越来越多，信息变得杂乱无章，甚至在目的地迷路——找不到当初记下的重要信息。解决办法：为每次旅行建一个目的地文件夹，下设景点、交通、餐厅、照片子文件夹，再用电子表格记录每日行程。需要时打开对应文件夹即可。这个做法，正是"信息世界层的数据表示"文件夹按目的地归拢信息→计算机中的目录结构电子表格每日行程逐行排列→计算机中的线性结构子文件夹嵌套按天再按上下午细分→计算机中的树状结构好的数据表示，让信息更有结构性、更容易访问——无论旅行还是数字世界。计算机科学概论（微课版）｜第6章数据结构046.1数据表示及数据结构·分类数据结构的四种基本类型数据结构：相互之间存在一种或多种特定关系的数据元素的集合。按关系的不同特征，分为4种基本类型。①集合结构——元素间仅"同属一个集合"，别无关系。例：保存旅行笔记的文件夹；计算机中的结构体。②线性结构——元素间一对一。例："每日行程安排"逐日相接；计算机中的数组、链表。③树状结构——元素间一对多。例：照片按"天→上/下午景点"分层收纳，如一棵树不断分叉。④图状（网状）结构——元素间多对多。例：城市为节点、铁路为连线，每城可与多城相连。图6-1树状结构（教材第99页）图6-2图状结构（教材第100页）计算机科学概论（微课版）｜第6章数据结构056.2数组·定义数组：一个名字管住一批数据情境：开发学生成绩管理系统，要存100名学生的数学成绩。定义mathScores0…mathScores99共100个独立变量？太笨拙——我们希望它们同属一个数据结构，用1个名字统一操作。数组的定义数组是元素的顺序集合，元素通常具有相同的数据类型。用"数组名[索引]"（索引从0开始）表示任意元素：mathScores[0]、mathScores[1]…即第1、2…名学生的成绩。图6-3数组（教材第100页）连续存储：mathScores[i]与mathScores[i+1]在内存中地址相邻。100个成绩一次性存入内存，用索引随取随用——这就是数组的威力。计算机科学概论（微课版）｜第6章数据结构066.2数组·操作数组的两大基本操作①创建数组：先定大小·数组连续存储，创建时必须指定大小，申请一整块连续空间；·已知学生恒为100名→创建大小为100的数组；·若人数事先未知，就无法保证数组装得下——定长是数组的硬约束。②访问元素：索引直达·读/改第20名学生的成绩：直接用mathScores[19]；·索引访问是一步到位的，无需逐个翻看；·比管理100个独立变量高效、简洁、易维护。例：循环求平均分令循环变量i从0递增到99，循环体中把mathScores[i]累加进sum；循环结束后sum÷100即得平均分。若用100个独立变量，同样的累加需要手写100行代码——数组+循环，一段代码通吃。计算机科学概论（微课版）｜第6章数据结构076.2数组·多维数组多维数组：数组的数组学生不只考数学，还有语文、英语……用二维数组studentScores：每一行是一名学生，每一列是一门科目。studentScores[0][0]、[0][1]、[0][2]即第1名学生的语文、数学、英语成绩。图6-4二维数组（教材第101页）两个看二维数组的视角·本质：数组的数组——每个元素本身又是一个数组；·直观：一张二维表格，行=学生，列=科目。行扫与列扫：两类典型统计·求某学生的各科总分：循环遍历这一行的所有元素并累加；·求某科目的全班平均分：循环遍历这一列，累加后除以总行数。计算机科学概论（微课版）｜第6章数据结构086.3链表·数组与链表为什么需要链表情境：班主任保存"谈话学生列表"。月考后顺序频繁调整——不及格的要插队提前，考进前50名的要删除，谈完一个删一个。数组能胜任吗？不能。图6-5删除数组元素（教材第102页）数组删除的两大代价·删掉元素33后，其后所有元素前移一格，计算开销大；·数组大小固定，尾部空出的位置白白浪费。图6-6链表（教材第102页）链表：用指针串起来的集合·每个元素（节点）=数据data+下一节点地址next指针；·最后一个节点的next为空地址NULL；·节点在内存中不必相邻，靠指针串联；·只需保存头节点地址，即可访问整个链表。计算机科学概论（微课版）｜第6章数据结构096.3链表·操作链表操作：访问、插入、删除①访问：只能从头遍历没有索引可用：从头节点出发，沿next指针逐节点前进。找第3个节点，必须先经过第1、2个。②插入：改两个指针·非头部插入：前节点next→新节点；新节点next→后节点；·头部插入：新节点next→原头节点，再更新头节点指针；·就像对小明说"你的下一个是小刚"，对小刚说"你的下一个是小红"。③删除：前节点next改为指向后节点；删头节点则改头指针。"你的下一个不是小刚，而是小红"——小刚即被剔除。图6-7链表的插入和删除（教材第103页）关键：插入与删除都不需要搬动数据，只改指针——这正是链表对数组的最大优势。计算机科学概论（微课版）｜第6章数据结构106.3链表·类型链表的四种类型图6-8链表的类型（教材第103页）①单向链表：只有next指针，从头向后遍历（上图6-8a）。②循环链表：末节点next指向头节点，首尾相接成环，支持循环遍历。③双向链表：每节点含pre+data+next，可正反向遍历（上图6-8c）。④双向循环链表：兼具双向与循环的结构。能力越强，代价越高·遍历方式越多，结构越复杂；·例：删除双向链表的非头尾节点，既要改前节点的next，又要改后节点的pre；·代码更难写，运行也更慢。杀鸡焉用牛刀班主任的谈话列表只需"找下一个"，单向链表足矣——按任务需求选择最合适的结构。计算机科学概论（微课版）｜第6章数据结构116.4结构体·定义与操作结构体：把相关的不同类型绑在一起二维数组的两个软肋·[0][0]是语文还是数学？索引不表意，对应关系全靠记；·数组只能存同类型数据——没法让"小明"（字符串）和95（整数）住进同一个数组。结构体的定义由一组称为成员的不同数据组成，成员可各具类型；成员有名字，用点操作符访问：studentI、studentInfo.score。三步走：①定义结构体类型（studentInfoType：stringname+intscore）→②创建该类型的变量studentInfo→③用"."读写成员。C++代码（教材第104页）structstudentInfoType{stringname;intscore;};studentInfoTypestudentInfo;studentI="小明";studentInfo.score=95;cout<<studentI<<endl;cout<<studentInfo.score<<endl;计算机科学概论（微课版）｜第6章数据结构126.4结构体·结构体数组结构体数组：100名学生全装下一个studentInfo只装一名学生。创建大小为100的数组studentInfos，每个元素都是一个含name和score的结构体——100名学生的姓名与成绩各就各位。图6-9结构体数组（教材第105页）例：统计全班平均分循环变量i从0到99，循环体中累加studentInfos[i].score，最后除以100。索引定位"哪个人"，成员名定位"哪项数据"。三种结构，各归其位·数组：同类型数据的顺序集合；·结构体：相关但不同类型的组合；·结构体数组：两者叠加，程序更有组织、更易理解。计算机科学概论（微课版）｜第6章数据结构136.5抽象数据类型·定义抽象数据类型（ADT）情境：开发社交媒体平台——动态按最新显示、私信按序到达、动态分文件夹收纳、用户互加好友。四种需求，恰好对应栈、队列、树、图四种抽象数据类型。定义：数据+操作的封装体抽象数据类型=与对该数据类型有意义的操作封装在一起的数据类型。定义包含三部分：数据的定义、操作的定义、封装数据和操作。·模型内部：数据结构（数组、链表）+操作（公有/私有）；·应用程序只能通过接口调用公有操作；·私有操作仅供内部使用，实现细节对外隐藏。图6-10抽象数据类型的模型（教材第106页）思想：使用者只关心"能做什么"，不必关心"怎么实现"。计算机科学概论（微课版）｜第6章数据结构146.5抽象数据类型·栈栈：后进先出（LIFO）情境：微博首页要按"新→旧"显示动态——新动态入栈压到栈顶，浏览时从栈顶依次出栈。插入与删除只在同一端（栈顶）进行，这就是栈。图6-11栈的三个示例（教材第106页）四个基本操作①建立一个空栈；②在栈顶插入一个元素（入栈）；③取出栈顶元素（出栈）；④检查栈是否为空。典型应用：倒转数据把(2,4,7,1,6,8)依次入栈再依次出栈，得到(8,6,1,7,4,2)。微博动态"逆时间显示"，本质就是一次数据逆序。计算机科学概论（微课版）｜第6章数据结构156.5抽象数据类型·队列队列：先进先出（FIFO）情境：私信功能——新到的私信插入队尾保存，查看时从队首取出最早一条。插入与删除分别在两端进行，这就是队列。图6-12队列的两个示例（教材第107页）四个基本操作①创建一个空队列；②在尾部插入元素（入列）；③在头部取出元素（出列）；④检查队列是否为空。典型应用：打印缓冲打印机慢、计算机快：待打印任务一次性放入打印队列缓冲，计算机转头去干别的，打印机按先来后到从队首取任务慢慢打——快慢解耦，互不等待。计算机科学概论（微课版）｜第6章数据结构166.5抽象数据类型·树树与二叉树图6-13树（教材第108页）基本术语·元素称节点，连线称弧；·弧直达的节点是子节点，出发端是双亲；同双亲互称兄弟；·节点分三类：根（唯一，无弧可达）、叶子（无弧出发）、内部节点；·以任意节点为根的树=子树。收纳应用：根节点=根目录，内部节点=文件夹，叶子节点=动态。图6-14二叉树（教材第108页）二叉树：最常用的特殊树·任意节点的子节点不超过2个；·六种常用操作：创建空树、插入、删除、检索、判空、遍历；·应用广泛：4.4节的Huffman编码就用到了二叉树。计算机科学概论（微课版）｜第6章数据结构176.5抽象数据类型·树的遍历二叉树的四种遍历方式遍历：按预定顺序处理每个节点，且仅处理一次。线性结构无需考虑顺序，非线性的二叉树必须约定。①前序遍历：根在最前根节点→左子树→右子树②中序遍历：根在中间左子树→根节点→右子树③后序遍历：根在最后左子树→右子树→根节点④层序遍历：逐层推进自上而下、逐层访问所有节点图6-15二叉树的四种遍历方式（教材第108页）计算机科学概论（微课版）｜第6章数据结构186.5抽象数据类型·图图：任意互联的关系网络情境：好友功能——节点表示用户，边表示好友关系。树中每个节点只能有一个双亲，表达不了好友网络；图中每个节点可与任意多个节点相连。图6-16图（教材第109页）有向图与无向图·无向图：边无方向——好友必须互认；·有向图：边有指向——允许"Alice是Bob的好友，但Bob不是Alice的好友"（关注/粉丝）。相关概念·度：无向图中依附顶点的边数；有向图分入度/出度；·权值：边上标注的有含义的数值。存储与遍历·存储：邻接矩阵、邻接表；·遍历：深度优先、广度优先；可用来算网络中两路由器的最短路径。计算机科学概论（微课版）｜第6章数据结构19章末·本章小结第6章小结：数据结构❶数据表示——数据要按一定方式组织管理；按元素间关系分为集合、线性、树状、图状四类基本结构，选对结构直接影响程序质量。❷数组——同类型元素的连续顺序集合，索引直达、定长约束；多维数组用"行×列"组织成绩表类数据。❸链表——节点=data+next指针，插入删除只改指针不搬数据，但访问须从头遍历；有单向、循环、双向、双向循环四种。❹结构体——把相关但不同类型的数据组合成自定义类型，成员具名访问；结构体数组同时驾驭"批量"与"复合"。❺抽象数据类型——数据与操作的封装：栈（LIFO）、队列（FIFO）、树/二叉树（四种遍历）、图（有向/无向、邻接存储、深/广度优先）。下一章预告：第7章算法计算机科学概论（微课版）｜第6章数据结构20拓展知识拓展：数据结构学科的诞生1968年：克努特奠基唐·欧·克努特所著《计算机程序设计技巧》第一卷《基本算法》，首次系统阐述数据的逻辑结构、存储结构及其操作，被公认为创立了数据结构的系统概念。20世纪70年代初，数据结构作为独立课程进入大学课堂。无结构阶段20世纪40—60年代计算机主要用于科学计算，数据间关系以数学公式为主，数据结构概念尚未形成。结构化阶段20世纪60—80年代非数值处理需求增加，数据表示成为重要问题，数据结构及抽象数据类型逐渐确立。面向对象阶段20世纪80年代初至今程序设计在对象的框架内进行，大量封装类降低设计者负担，数据结构更灵活友好。计算机科学概论（微课版）｜第6章数据结构21章末·习题课后习题（教材6.8节）第1题数组和链表的区别是什么？提示：从存储方式、访问方式、插入删除代价、空间利用四个角度对比。第2题结构体的不同成员是否具有相同的数据类型？提示：回顾结构体解决数组的哪两个"软肋"。第3题如何实现社交平台的好友功能？提示：节点与边分别表示什么？双向好友与单向关注各用哪种图？使用建议：1、2题课堂快答；第3题小组讨论后画出示意图。计算机科学概论（微课版）｜第6章数据结构22高等学校计算机专业核心课程精品系列教材计算机科学概论（微课版）第7章算法算法基础·递归与分治·动态规划·贪心·回溯算法是计算机科学的灵魂。本章从《九章算术》与约瑟夫环讲起，依次吃透递归分治、动态规划、贪心、回溯四大经典算法思想及其经典案例。图7-3汉诺塔问题的示意（教材第114页）LEARNINGGOALS学习目标与知识导图第7章知识导图（教材第112页）本章学习目标❶了解算法的起源与定义，掌握算法的五大特征；❷理解时间复杂度与空间复杂度，能比较常见复杂度量级；❸掌握递归与分治思想，能用斐波那契、汉诺塔、二分查找说明；❹理解动态规划，掌握01背包与最长公共子序列的状态转移；❺掌握贪心与回溯的适用场景，了解Prim/Kruskal、八皇后、图着色等经典案例。能力落点：从"会编程"走向"会设计"，能针对问题选择合适的算法策略。计算机科学概论（微课版）｜第7章算法02CONTENTS本章目录7.1算法基础算法的定义｜从实例看算法｜复杂度分析7.2递归与分治算法递归的基本思想及案例｜分治的基本思想及案例7.3动态规划算法思想及案例｜递归与迭代实现｜优化策略7.4贪心算法钱币找零｜区间调度｜Prim与Kruskal7.5回溯算法八皇后问题｜图着色问题｜货郎问题章末7.6本章小结｜7.7拓展知识｜7.8课后习题计算机科学概论（微课版）｜第7章算法037.1算法基础·起源从"术"到Algorithm古代中国称为"术"，最早见于《周髀算经》《九章算术》。《九章算术》收录246个例题，分方田、粟米、衰分、少广、商功、均输、盈不足、方程、勾股九章，涵盖四则运算、最大公约数、埃氏筛、线性方程组的高斯消元法等，堪称算法的启蒙书。三国时期，刘徽给出求圆周率的割圆术。此后历代专著不断：唐《一位算法》、宋杨辉《杨辉算法》、明程大位《算法统宗》、清《开平算法》《算法一得》《算法全书》等，是中国古代人民智慧的结晶，影响远传世界各地。图7-1《九章算术》（教材第112页）"Algorithm"的词源与最早的算法英文名"algorithm"源自9世纪波斯数学家花拉子米（al-Khwarizmi的音转），"算法"原为"algorism"，18世纪演变为"algorithm"。公认的最早算法是欧几里得算法（辗转相除法求最大公约数），记载于《几何原本》第VII卷。计算机科学概论（微课版）｜第7章算法047.1算法基础·定义算法的定义与五大特征算法是解决问题的方法，是为解决某类问题而规定的一个有限的操作序列——一组按特定顺序执行的明确指令。有穷性执行有限步后必须终止，不能陷入无限循环。确切性每一步含义明确无歧义，任何人执行结果都一致。输入有零个或多个输入，刻画问题的初始条件。输出至少有一个输出，即问题求解的结果。可行性每一步都可分解为基本可执行的操作。算法≠程序算法是解决问题的思想与步骤，与具体语言无关；程序是算法在计算机上的具体实现。同一个算法可以用Python、C++、Java等不同语言实现——学算法，学的是"怎么想"，其次才是"怎么写"。计算机科学概论（微课版）｜第7章算法057.1算法基础·从实例看算法实例：约瑟夫环问题问题：41名冒险者围成一圈依次报数，报到3的人离开圈子，如此继续，直到只剩2人。求：站在哪两个位置才能幸存？小明与小华没有硬碰硬地干等，而是按规则一步步推演整个报数过程，算出两个安全位置并站了过去，最终成功脱险。启示面对复杂问题，先弄清规则，再按确定步骤推演——这正是算法思维。这类重复推演交给计算机，瞬间即可完成：把规则写成算法，剩下的交给机器。图7-2约瑟夫环问题（教材第113页）计算机科学概论（微课版）｜第7章算法067.1算法基础·复杂度分析时间复杂度与空间复杂度算法的优劣用时间复杂度（操作单元数量随规模变化的函数）与空间复杂度衡量；评估时间复杂度时通常考虑最坏情况。复杂度记法典型算法/场景常数阶O(1)访问数组的第一个元素对数阶O(logn)二分查找线性阶O(n)顺序遍历一维数组多项式阶O(n²)遍历二维数组O(mn)，m=n时常见时间复杂度对应的算法描述（教材第114页）空间复杂度算法运行过程中占用存储空间大小的度量，也是输入规模的函数。如递归算法执行时，调用堆栈会随问题规模不断增大。什么是"好算法"兼顾时间与空间：执行时间不能太久，也不能占用过多额外空间。解决同一问题时，应养成主动分析复杂度的习惯，挑选时间复杂度更小的算法。计算机科学概论（微课版）｜第7章算法077.2递归与分治算法·递归思想递归：自己调用自己核心思想：在函数执行过程中反复调用自身，每调用一次就把问题规模缩小一点，直到可以直接求解，再把结果层层返回、组合出原问题的答案。关键概念①递归式把大问题与同类小问题的关系写成递推公式，如斐波那契数列f(n)=f(n−1)+f(n−2)，汉诺塔f(n)=2f(n−1)+1。关键概念②递归边界递推不能无限进行，必须有终止条件：f(1)=f(2)=1（斐波那契），f(1)=1（汉诺塔）。到达边界即开始逐层返回。课堂提醒没有递归边界的递归=死循环，还会因调用栈不断加深而耗尽内存。写递归函数先问自己两个问题：递归式是什么？边界在哪里？两者齐备，递归才正确。计算机科学概论（微课版）｜第7章算法087.2递归与分治算法·递归案例案例：神兔与斐波那契数列问题：一对神兔出生后，从第3个月起每月再生一对神兔；新生的神兔也按此规律繁殖。第n个月共有多少对？观察：当月的兔对数=上月已有的+上上月已成熟所生。递归式f(n)=f(n−1)+f(n−2)(n≥3)递归边界f(1)=f(2)=1由此得到数列1,1,2,3,5,8,13,21,…，即著名的斐波那契数列。每一项都由前两项递归生成，是理解递归最经典的入口。图7-4斐波那契数列的递归结构（教材第115页）计算机科学概论（微课版）｜第7章算法097.2递归与分治算法·递归案例案例：汉诺塔问题传说：一块黄铜板上有三根宝石柱，一根柱上从下到上按大小穿好64个金盘。要把全部金盘移到另一根柱上，规则是：小盘上不能放大盘，三根柱之间一次只能移动一个圆盘。递归思路：先把上面n−1个盘移到辅助柱→把最大盘移到目标柱→再把n−1个盘移到目标柱。问题规模每次减1。递归式f(n)=2f(n−1)+1边界f(1)=1解f(n)=2ⁿ−164个盘需移动2⁶⁴−1≈1.8×10¹⁹次——即使每秒移一盘，也要约5800亿年。图7-3汉诺塔问题的示意（教材第114页）计算机科学概论（微课版）｜第7章算法107.2递归与分治算法·分治思想分治：化整为零，各个击破历史中的分治：秦灭六国面对"统一天下"这个庞大目标，秦始皇没有与六国同时开战，而是在公元前230年—前221年的十年间，按韩→赵→魏→楚→燕→齐的顺序逐个击破——把大问题拆成一个个可解决的小问题，正是分治思想。①分解Divide把原问题拆成若干规模更小、结构相同的子问题。②解决Conquer子问题足够小则直接求解，否则递归地继续分解求解。③合并Combine把各子问题的解组合成原问题的最终答案。适用条件：子问题相互独立、且求解方法与原问题相同。递归常作为分治的实现手段：分治是"战略"，递归是"战术"。计算机科学概论（微课版）｜第7章算法117.2递归与分治算法·分治案例案例：二分查找猜数字游戏：在1~100中想一个数，怎么猜最快？第一次就猜中间值(1+100)÷2=50——对方回答"大了"或"小了"，范围立刻缩小一半；再取新范围的中间值继续猜。第1次范围1~100猜50，排除一半第2次范围缩至50个数再猜中间值如此反复每猜一次，候选范围减半最多7次log₂100≈7必定猜中为什么快？与顺序查找对比100个数：顺序查找最坏要查100次；二分查找最多7次——时间复杂度O(logn)。数据量越大优势越惊人：10亿个数，二分最多约30次。前提：数据必须有序。这正是"分治"的威力：每一步都扔掉一半不可能的部分。计算机科学概论（微课版）｜第7章算法127.3动态规划算法·基本思想动态规划：记住算过的答案动态规划（DynamicProgramming）是运筹学的一个分支，用于解决多阶段决策过程的优化问题。把问题拆成若干阶段，记录已解子问题的答案，后续阶段直接查表使用，避免重复计算——"聪明地记住，而不是傻乎乎地重算"。两个核心①状态定义：用什么量描述子问题；②状态转移方程：状态之间如何递推。真实案例：1990年，曾赛星、李寿声在内蒙古河套灌区永联试区，把春小麦、玉米、甜菜三个子区的灌溉水量分配建模为多阶段决策，用动态规划逐阶段优化配水。图7-5河套灌区（教材第117页）计算机科学概论（微课版）｜第7章算法137.3动态规划算法·案例案例：01背包问题游戏情境：王者荣耀中预算2500金币、最多购买6件装备，每件要么买要么不买（01背包），怎样使增加的攻击力最大？装备增加攻击力价格（金币）陨星+451080泣血之刃+1001800无尽战刃+1102140风暴巨剑+80910雷鸣刃+40450铁剑+20250表7-1装备属性一览（教材第118页）图7-6装备（教材第118页）状态定义与转移方程状态dp[i][v]：前i件装备、预算v时的最大攻击力。转移dp[i][v]=max(dp[i−1][v],dp[i−1][v−w[i]]+c[i])不买第i件vs买了它计算机科学概论（微课版）｜第7章算法147.3动态规划算法·案例案例：最长公共子序列（LCS）子序列：从原序列中按顺序挑出若干字符（不必连续）。如"ace"是"abcde"的子序列。问题：给定两个序列，求它们最长公共子序列的长度。状态定义与转移方程状态dp[i][j]：串A前i个字符与串B前j个字符的LCS长度。转移·若A[i]=B[j]：dp[i][j]=dp[i−1][j−1]+1·否则：dp[i][j]=max(dp[i−1][j],dp[i][j−1])边界dp[0][j]=dp[i][0]=0

abcdea11111c11222e11223A=ace，B=abcde的dp表（右下角3即答案）填表过程自左向右、自上向下，每个格子只依赖上方、左方、左上方三个已知格子——这就是"记住已解子问题"的具体体现。计算机科学概论（微课版）｜第7章算法157.3动态规划算法·实现方式递归实现vs迭代实现#递归求斐波那契deffib(n):ifn<=2:#递归边界return1returnfib(n-1)+fib(n-2)

print(fib(10))#55递归实现代码直观、与递归式一一对应；但存在大量重复计算（如fib(3)被反复求解），且调用栈开销大，规模稍大就慢得难以接受。#迭代求斐波那契deffib(n):a,b=1,1for_inrange(n-2):a,b=b,a+breturnb

print(fib(10))#55迭代实现按状态转移顺序自底向上计算，每个状态只算一次，时间与空间表现都更好；动态规划实践中通常采用迭代（填表）方式。计算机科学概论（微课版）｜第7章算法167.4贪心算法·基本思想贪心：每步都选当前最优阿里巴巴与四十大盗：阿里巴巴进入藏宝洞，宝物可以分割装袋。想让背走的价值最大，策略很简单——优先装单位重量价值最高的宝物。这种"只看眼前最优"的策略就是贪心：不从整体最优出发，而是每一步都做出当前看来最好的选择。贪心算法的一般步骤①设定初始条件（如背包为空）；②迭代：每次选出局部最优，问题规模随之缩小；③把各步的选择综合为全局（近似）最优解。图7-7阿里巴巴与四十大盗（教材第121页）计算机科学概论（微课版）｜第7章算法177.4贪心算法·案例案例：钱币找零问题问题：要找零41分，面额有25分、10分、5分、1分，怎样使用最少的硬币？贪心策略：每次都选不超过剩余金额的最大面额。41分选25分剩余41−25=16分16分选10分剩余16−10=6分6分选5分剩余6−5=1分1分选1分剩余0，完成✓结果：41=25+10+5+1，共4枚硬币。注意：贪心不保证处处最优标准面额体系下贪心恰好最优；但若面额为1、3、4分要找6分，贪心给出4+1+1（3枚），而最优是3+3（2枚）。使用贪心前，先论证问题具备"贪心选择性质"，否则应改用动态规划。计算机科学概论（微课版）｜第7章算法187.4贪心算法·案例案例：区间调度问题问题：数轴上有N个开区间，要从中选出尽可能多的区间，使它们互不相交。例如多门课程时间冲突时，如何安排才能上最多的课？贪心策略：每次选择左端点最大（开始最晚）的区间，选中后把与之相交的区间全部排除，再在剩余区间中重复——从右向左一步步"贪"出最多的不相交区间。为什么这样"贪"是对的？开始得越晚，给左侧留下的可用空间就越大，后续能容纳的区间就越多——局部最优选择恰好不破坏全局最优，因此贪心成立。图7-8区间调度问题（教材第121页）计算机科学概论（微课版）｜第7章算法197.4贪心算法·案例案例：最小生成树Prim与Kruskal情境：斯巴达克斯率军行军，要用最少的"代价"把所有据点连通——即求连通图的最小生成树。两种经典算法都是贪心。Prim算法：点贪心把顶点分为已入选集合A与未入选集合B。①每步在A、B之间找权值最小的边；②把该边在B端的顶点并入A；③重复，直到所有顶点进入A。Kruskal算法：边贪心把所有边按权值从小到大排序。①依次考察每条边：两端点若不在同一连通块，就加入该边；②在同一连通块则跳过（避免成环）；③选够顶点数−1条边即完成。图7-9斯巴达克斯行军（教材第122页）两种算法贪心对象不同（点vs边），但都能得到同一棵最小生成树——条条大路通罗马。计算机科学概论（微课版）｜第7章算法207.5回溯算法·基本思想回溯：碰壁就回头回溯法是一种试探性的算法：沿一个方向向前走，每步都做一种选择；发现当前选择走不通时，就退回到上一步，换另一种选择重新尝试。好比走迷宫：一路尝试不同方向，碰壁之后退回来，再选别的路，直到找到出口。经典问题：八皇后——在8×8棋盘上放置8个皇后，使任意两个皇后都不在同一行、同一列、同一对角线上（互不攻击）。回溯vs暴力枚举回溯不是傻枚举：一旦发现当前方案已不可能成功，立即放弃整条分支（剪枝），不必走到最后才回头——效率远高于穷举。图7-10八皇后问题的棋盘（教材第123页）计算机科学概论（微课版）｜第7章算法217.5回溯算法·案例四皇后问题的回溯过程把棋盘缩小为4×4、只放4个皇后。皇后放在(1,1)后，其同行、同列、同对角线位置（黑色标识）都不能再放；第二行只能放(2,3)，但第三行随即无解——退回重选(2,4)仍不行，继续回溯，第一行改放(1,2)重新尝试。图7-11四皇后问题的棋盘（教材第123页）图7-12解决过程（一）（教材第124页）图7-13解决过程（二）（教材第124页）核心思想一句话：当前方案走不通，就回溯并重新选择。理解四皇后，八皇后只是规模放大。计算机科学概论（微课版）｜第7章算法227.5回溯算法·案例图着色问题与货郎问题图着色问题（著名的NP完全问题之一）给定无向图G=(V,E)，V为顶点集合、E为边集合。要求把V划分为K个颜色组，每组形成一个独立集——组内没有相邻顶点，即相邻顶点不同色。判定版：K种颜色够不够用（回溯逐点试色，冲突即回退）；优化版：求所需的最小K值。图7-14图着色问题与一种着色方案（教材第124页）货郎问题（TSP）问题：货郎要到若干城市卖货，每个城市恰好经过一次，最后回到起点，要求总路程最小。回溯思路：把路径看作逐城市的选择序列，一边走一边累加路程；若当前部分路径已超过已知最优，立即剪枝回退。城市一多，组合爆炸，即便回溯也很吃力——这正是NP难问题的特点。计算机科学概论（微课版）｜第7章算法23章末·本章小结第7章小结：算法❶算法基础——算法是解决问题的有限操作序列，具备有穷、确切、输入、输出、可行五特征；优劣用时间/空间复杂度衡量，评估看最坏情况。❷递归与分治——递归=递归式+递归边界（斐波那契、汉诺塔）；分治三步"分解—解决—合并"（秦灭六国），二分查找每次减半，仅O(logn)。❸动态规划——面向多阶段决策，记录已解子问题的答案；关键是状态定义与状态转移方程（01背包、LCS）；迭代实现优于朴素递归。❹贪心算法——每步取局部最优以逼近全局最优（阿里巴巴选宝）；找零、区间调度（选左端点最大）、最小生成树Prim（点贪心）/Kruskal（边贪心）；须先论证贪心选择性质。❺回溯算法——试探前进、碰壁回退并剪枝（走迷宫）；八皇后、图着色（NP完全）、货郎问题（TSP）都是其经典舞台。下一章预告：第8章大数据计算机科学概论（微课版）｜第7章算法24拓展知识拓展：高级算法一览本章只是算法世界的入口。以下方向在科研与工程中都极为活跃，供学有余力的同学按图索骥。图算法深入最短路径：Dijkstra、Bellman-Ford、Floyd-Warshall；最小生成树进阶；拓扑排序Kahn算法。高级动态规划状态压缩DP、斜率优化；配合滚动数组、记忆化搜索、倍增、四边形不等式等优化手段。流网络最大流：Ford-Fulkerson、Edmonds-Karp、Dinic；最小割定理及其在资源分配中的应用。随机化算法蒙特卡洛方法（以概率换正确性）与拉斯维加斯方法（以时间换确定性）。字符串算法模式匹配：KMP、Boyer-Moore；后缀数组等高级数据结构。近似与并行A*、模拟退火、遗传算法求近似解；MapReduce并行框架、锁与无锁并发设计。计算机科学概论（微课版）｜第7章算法25章末·习题课后习题（教材7.8节，共12题）递归·第1—3题1勇士与龙2魔法塔楼梯（每次走1或2级）3花田三角要点：写出递归式与递归边界。动态规划·第4—6题4地下城之宝5魔法背包6符文拼图要点：定义状态，写出状态转移方程。贪心·第7—9题7龙珠挑选8黄金通道9魔法药剂配比要点：说明贪心策略及其正确性理由。回溯·第10—12题10迷宫探秘11魔法阵谜题12神秘钥匙和门要点：画出搜索过程，说明回退条件。使用建议：每类各选1题课堂演练，其余课后完成，下节课对照讲评。计算机科学概论（微课版）｜第7章算法26高等学校计算机专业核心课程精品系列教材计算机科学概论（微课版）第8章大数据概述·采集·存储·分析·处理为什么有的广告让你忍不住想买？本章沿大数据处理周期逐一拆解：从5V特征与三类数据源，到HDFS、HBase，再到数据挖掘、可视化与MapReduce。图8-82022年《政府工作报告》标签云（教材第145页）LEARNINGGOALS学习目标与知识导图第8章知识导图（教材第129页）本章学习目标❶理解大数据究竟"大"在哪里，掌握5V特征；❷了解大数据的发展历程：萌芽、成熟、应用三阶段；❸按处理流程掌握核心技术：采集、存储、分析、处理；❹掌握HDFS、HBase等分布式存储的核心概念；❺了解大数据在工业、农业、政府、体育等领域的应用方式。能力落点：理解大数据基本技术，为使用大数据解决实际问题打基础。计算机科学概论（微课版）｜第8章大数据02CONTENTS本章目录8.1大数据概述从数据到大数据｜核心技术｜应用8.2大数据采集数据源｜ETL｜网络爬虫8.3大数据存储分布式文件系统｜分布式数据库8.4大数据分析理解与预处理｜数据挖掘｜数据可视化8.5大数据处理大数据计算框架｜MapReduce章末8.6小结｜8.7拓展知识｜8.8课后习题计算机科学概论（微课版）｜第8章大数据038.1大数据概述·从数据到大数据什么是大数据数据（data）是事实或观察所得的结果，是对客观事物的逻辑归纳、未经加工的初始素材：连续的（音频、图像）称模拟数据，离散的（符号、文字）称数字数据。关于"大数据"，目前尚无统一定义——《大数据时代》舍恩伯格、库克耶不用随机分析法（抽样调查）这样的捷径，而是对所有数据进行分析处理。美国国家科学基金委员会由科学仪器、传感器、网上交易、电子邮件、视频、点击流等数字源生成的大规模、多样、复杂、分布式的数据集。麦肯锡全球研究所规模大到在获取、存储、管理、分析方面远超传统数据库软件能力的数据集合。综合定义用传统数据处理工具无法在可容忍时间内获取、管理和处理分析的海量数据，需要特殊的体系架构支撑。描述大数据的特征，业界通用"5V"模型——下一页详解。计算机科学概论（微课版）｜第8章大数据048.1大数据概述·特征大数据的5V特征Volume数据量大大数据通常达PB级及以上。2011年全球数据总量1.87ZB，刻成光盘排开可绕地球约20圈；1986—2010年间增长100倍。Velocity处理速度快生成与变化都极快：2023年Google每日响应85亿次搜索、处理超20PB；Dremel几秒内完成亿级表的聚合查询。Variety数据多样由单一结构化转向以非结构化、半结构化为主：网络日志、图片、社交信息、地理位置；物流、医疗、金融等领域数据爆发式增长。Value价值密度低经获取、清洗、挖掘后，有效数据不足20%。一天的监控视频中，有价值的或许只有几秒——如何低成本"沙里淘金"是关键。Veracity真实性强内容与真实世界事件紧密相连，但也存在偏差与错误——必须保证采集与清洗后留存的数据准确可信，才能支撑解释与预测。计算机科学概论（微课版）｜第8章大数据058.1大数据概述·发展历程大数据发展的三个阶段萌芽阶段20世纪80年代—90年代个人计算机普及、互联网出现，数据量爆炸式增长。·1980托夫勒《第三次浪潮》赞其为"华彩乐章"·1997首篇使用"大数据"术语的论文发表·1999IEEE首设大数据专题讨论存储靠胶卷、光盘、磁盘，离线集中处理。成熟阶段21世纪初—2010年Web2.0迅猛发展，非结构化数据大量产生，传统方法难以应对。·2003/2004谷歌发表GFS、MapReduce两篇论文·2005奥莱利："数据将是下一项技术核心"形成并行计算与分布式系统两大核心技术，Hadoop等开源架构盛行。应用阶段2010年至今从技术研究转向应用研究，渗透商业、医疗、政府、教育等各领域。·2011《大数据时代》出版·2012美国启动"大数据发展计划"·2013《中国大数据技术与产业发展白皮书》·2015国务院《促进大数据发展行动纲要》·2017工信部《大数据产业发展规划》计算机科学概论（微课版）｜第8章大数据068.1大数据概述·核心技术大数据处理周期与核心技术图8-1大数据处理周期及核心技术（教材第131页）①采集与预处理RFID、传感器、社交网络等获取海量数据；抽取、清洗"去噪"，转为易处理形式。→8.2节②存储与管理分布式文件系统（DFS）+关系型/NoSQL数据库，解决存储、表示、可靠性与传输。→8.3节③分析与挖掘从噪声数据中提取潜在有用的信息与知识；文本/图形可视化辅助洞察。→8.4节④安全保障透明加解密、分布式访问控制、数据审计、隐私保护与推理控制、完整性验证。计算机科学概论（微课版）｜第8章大数据078.1大数据概述·应用大数据在各行业的应用工业：福特汽车400万辆汽车装配车载传感器；FusionEnergi单车74个传感器，每小时回传约25GB数据，用于改进油耗与安全设计、制定个性化充电计划。农业：大豆产量预测中国农科院用东北、黄淮两大产区173个县域气象站、34年单日气象数据与分县产量数据建模，建立高精度大豆单产预测模型，支撑供需平衡监测预警。政府：用数据说话分析社会、经济、人文规律，为宏观调控与产业布局提供依据；提升公共服务水平；城市管理由粗放式向精细化转变。体育：德国队的"第十二人"2014年巴西世界杯，德国队用大数据分析己方球员特点、优化团队配置，并研究对手技术数据制定战术——大数据被称为夺冠的"秘密武器"。回扣开篇：精准广告=从海量非结构化用户数据中分析特征与偏好，把"对的广告"投给"对的人"计算机科学概论（微课版）｜第8章大数据088.2大数据采集·数据源五类主要数据源开篇问题：智能家电厂商如何收集用户体验数据？先看清数据从哪里来——①传感器数据压力、温度、流量、声音、电参数等各类传感器感知环境并转为电信号输出；DV录像、手机拍照也属此类，适应恶劣环境。②互联网数据门户新闻、社交资讯、电商购买记录与评价、论文网站观点等；多为结构化数据、价值密度高，常借助网络爬虫采集。③日志文件业务平台每日产生的操作记录：网络流量管理、股票记账、Web访问行为、设备状态上报等，可挖掘出支撑决策与性能评估的信息。④企业业务系统数据沃尔玛每小时收集2.5PB销售数据（存量为美国国会图书馆的167倍），借购物行为分析优化商品陈列；Amazon靠Kindle阅读标记做图书推荐。⑤政府数据财政、税务、海关、医疗等部门业务系统数据：真实性、权威性、实时性、指向性强，是重要的采集来源。计算机科学概论（微课版）｜第8章大数据098.2大数据采集·ETLETL：抽取·转换·装载ETL=Extract（抽取）+Transform（转换）+Load（装载）：把企业内部分散、零乱、标准不统一的数据整合格式化，供后续分析处理。主流工具：DataPipeline、Kettle、Talend、Informatica、Datax、OracleGoldengate。图8-2ETL体系结构（教材第135页）①数据抽取全量抽取：整库照搬，直观简便但有冗余、效率低；增量抽取：靠日志对比、时间戳只抽新增/修改的数据。②转换和加工抽取的数据未必符合目的库需求——格式不符、输入有误、数据不完整，须在ETL引擎中或抽取过程中同步清洗转换。③数据装载最后环节。两种方式：SQL语句插入/更新/删除（有日志、可恢复）；批量装载（bcp、bulk等，大数据量时效率高）。计算机科学概论（微课版）｜第8章大数据108.2大数据采集·网络爬虫网络爬虫的工作原理网络爬虫：从指定的链接入口（种子URL）出发，按照某种策略，从互联网中自动获取有用信息的程序——搜索引擎正是靠它抓取网页、建立索引。图8-3通用的爬虫框架流程（教材第136页）抓取流程（循环直至待爬队列为空）①指定入口URL，加入种子URL队列；②种子队列并入待抓取URL队列；③依次读取URL，经DNS解析后下载网页，存入下载网页库；④从网页中抽取新的链接加入待爬队列，已完成的转入已抓取队列；⑤循环③④，直到待爬队列为空，爬虫停止。回扣开篇：ETL整合家电传感器与日志数据，爬虫抓取论坛评论——厂商由此全面掌握用户体验计算机科学概论（微课版）｜第8章大数据118.3大数据存储·分布式文件系统分布式文件系统与HDFS2021年Facebook日活29.1亿、每天产生约4PB数据——单磁盘必然读写慢、可靠性差。分布式文件系统（DFS）把文件系统从单一节点扩展到网络中的众多节点，用户像用本地文件系统一样使用它。常见实现：GFS、HDFS、Lustre、Ceph等；HDFS是GFS思想的开源实现。核心概念①数据块BlockHDFS以块为独立存储单元，默认64MB（磁盘块通常512B）：大块降低寻址开销；任意大的文件都能切块存到多块磁盘；不足一块的文件不占整块空间。核心概念②容错每个块默认三副本存放在不同机器上，部分节点故障也能恢复数据；对访问频繁的文件做块缓存提升读性能。namenode（管理者）掌控文件系统命名空间：维护文件系统树（镜像文件+编辑日志持久保存），记录各块所在的datanode；集群中仅一个。datanode（工作者）按需存储并检索数据块（受客户端或namenode调度），定期向namenode上报所存块的列表；集群中有多个。计算机科学概论（微课版）｜第8章大数据128.3大数据存储·分布式文件系统HDFS体系结构：一次读操作图8-4客户端读取HDFS中数据的流程（教材第138页）读流程六步①客户端open请求打开文件②namenode返回起始块位置等元数据③客户端获得输入流，调用read④从距离最近的datanode读第一块⑤重复读取后续每个块⑥读完调用close结束namenode容错：①元数据同时写入本地磁盘与远程NFS；②辅助namenode定期合并镜像（监测点），故障时接管恢复。计算机科学概论（微课版）｜第8章大数据138.3大数据存储·分布式数据库HBase：为什么需要它淘宝、京东要应付"双十一"级别的高并发随机读写，传统关系数据库在并发性、可扩展性、可用性上暴露出弱点，完备的事务机制反成负担。HBase：高可靠、高性能、面向列、可伸缩的分布式存储系统，可在廉价PCServer上搭建大规模集群。图8-5HBase与HDFS和MapReduce的关系（教材第139页）海量数据关系库在亿字节级查询愈发迟缓；HBase对TB、PB级数据依然高效。无模式每行一个可排序主键+任意数量的列，列可动态增加，同行不同列亦可；数据皆为字符串，无类型之分。高并发支持高并发读写；按行键（RowKey）查询极快，支撑每天上亿字节级访问。计算机科学概论（微课版）｜第8章大数据148.3大数据存储·分布式数据库HBase的逻辑模型与物理模型逻辑模型：本质是键值（Key-Value）数据库列必须归属于列族（ColumnFamily），由列修饰符（Qualifier）标识；一行=行键+若干列及值。Key=RowKey+ColumnFamily+ColumnQualifier+TimeStamp+KeyType。修改数据=新增一个时间戳版本；读取时按版本排序，取最近一次修改，保障读写高性能；特别适合稀疏记录。图8-6HBase的逻辑模型（教材第139页）物理模型：面向列族存储每个列族在磁盘上拥有自己的HFile集合（二进制文件，按列族隔离管理）；HBase不存空记录（NULL不写盘），读取时只读用到的列族——稀疏数据因此存得省、读得快。一行中列族的数据在物理上存放在一起，按行键范围划分存储到不同的Region——Region是数据的逻辑与管理单元。计算机科学概论（微课版）｜第8章大数据158.3大数据存储·分布式数据库HBase体系结构与NoSQL家族图8-7HBase架构图（教材第140页）四大组件（主从架构）Client：访问接口，缓存元数据加速访问。ZooKeeper：协调服务，保障Master高可用、监控RegionServer、保存元数据入口。Master：Region分配、DDL操作、故障恢复。RegionServer：处理读写，管理Region；内存分MemStore（写）与BlockCache（读）。写入流程：Client经ZooKeeper找到RegionServer→定位Region与列族→先写MemStore，达阈值后溢写（Flush）为StoreFile（HFile）。NoSQL家族（NotonlySQL）：列式HBase、键值Redis、文档MongoDB、图Neo4j——以灵活扩展、灵活数据模式、与云计算紧密融合而迅速发展。计算机科学概论（微课版）｜第8章大数据168.4大数据分析·理解与预处理淘沙之前：数据理解与预处理采集存储后的数据犹如河滩淘来的沙，须经"淘沙提炼"才见黄金——理解与预处理是分析的第一步。数据多样性（四个方面）①格式多样：数值、文本、图形、图像、音频、视频等异构类型；②组织方式多样：属性-值型（如成绩表）与链接型（如社交关系图）；③时序性：以时间为下标的数据序列，需时序挖掘、流数据分析等专门方法；④交互性：被观察对象会"有意加工"自己产生的数据，数据与对象相互耦合。数据规范化（Normalization）按比例缩放数据到较小特定区间，去除度量单位限制，便于比较与加权；含同趋化与无量纲化两方面。·最小-最大规范化：线性映射到[0,1]·Z分数规范化：按均值与标准差转为正态分布特征工程用领域知识从原始数据中提取可用特征：·特征表示：原始数据→可计算的特征向量·特征提取：重构新特征Y=f(X)，降维去噪·特征选择：选出最优特征子集（筛选器/封装器评价）计算机科学概论（微课版）｜第8章大数据178.4大数据分析·数据挖掘关联分析与数据分类关联分析：啤酒与尿布1993年安格沃尔提出关联规则，源于超市购物篮分析。沃尔玛发现"啤酒"与"尿布"常同现——年轻父亲买尿布时顺便买啤酒，于是把两者同区陈列，销量大增。Apriori算法核心=先验原理：项集频繁⇒其所有子集必频繁；项集非频繁⇒其所有超集必非频繁。借此"连接—剪枝—验证"逐层找出频繁项集。数据分类：有监督的三步用带标签数据构建分类模型，预测未分类样本的类别（如垃圾邮件识别）。①训练集构建模型；②测试集评估优化；③实际应用：对真实数据实时分类预测。常用分类算法简要描述（教材表8-1，第143页）决策树按树状结构把数据分成若干分支，每个分支体现类别归属共性K-近邻最经典简单的有监督方法，依据K个最近邻样本类别决定对象类别朴素贝叶斯基于贝叶斯定理与特征条件独立假设的概率分类方法SVM在样本空间中寻找超平面，把不同类别的样本分开神经网络模拟人脑神经元，调整连接权重与阈值，经激活函数产生输出计算机科学概论（微课版）｜第8章大数据188.4大数据分析·数据挖掘数据回归与数据聚类数据回归：预测性建模研究因变量与自变量的关联，用于预测分析、时间序列与因果探寻（如疲劳驾驶与事故数量的关系）。①建立定量关系式，最小二乘法估参；②检验关系式的可信度；③判别影响显著的自变量，纳入模型、剔除不显著者；④用关系式进行预测或控制。数据聚类：无监督的"物以类聚"对无标签数据按相似性度量分组：类内相似度高、类间相似度低；分几类、各归哪类事先均未知。应用：生物信息学中聚类动植物特征认知种群结构；商业中按客户数据聚类辅助选址与营销。常用聚类算法简要描述（教材表8-2，第144页）K-means以平均值为类中心的分割聚类，把n个对象分成K个簇，最经典PAM/CLARA对K-means的改进：削弱离群点敏感度；抽样寻代表对象提升效率DBSCAN基于高密度连通区域，把"类"定义为高密度相连点的最大集合OPTICS克服DBSCAN不足，生成增广簇排序并据此提取类簇谱聚类基于图论，可在任意形状样本空间聚类并收敛于全局最优计算机科学概论（微课版）｜第8章大数据198.4大数据分析·数据可视化四类常见数据可视化①文本数据可视化标签云按词频排序布局，字号代表重要性，快速识别主题热度——如2022年《政府工作报告》标签云。图8-8（教材第145页）②关系数据可视化以节点与连接呈现网络中隐匿的关联——某篇论文与其他论文的引用关系一目了然。图8-9（教材第145页）③时空数据可视化融合地理制图与可视化：美国任一地点到最近麦当劳的距离图，越亮越近；流式地图、时空立方体进一步发展。图8-10（教材第146页）④统计数据可视化运用最早：饼图、直方图、散点图、柱形图等，是PPT、报表、新闻中最常见的沟通方式。计算机科学概论（微课版）｜第8章大数据208.5大数据处理·计算框架批处理·流处理·内存计算批处理（离线计算）先把数据存到硬盘，再对静态数据集中计算。Hadoop是典型架构：HDFS存储+MapReduce分配计算到各数据节点。用于电影渲染、生物数据分析、金融保险分析等。图8-11（教材第147页）流处理（在线计算）数据到来即算，及时反馈，不等全部到齐——在数据有效期内获取价值。架构：多源采集→Kafka消费（日志清洗）→Flink/Spark处理计算。用于金融服务、网络监控、传感监测、微博热搜等。图8-12（教材第147页）内存计算把数据载入内存处理以避免I/O，是提升时效性的重要途径。Spark把中间结果弹性分布式数据集（RDD）尽可能放入内存，迭代与多查询都快得多。图8-13（教材第148页）选择口诀：数据齐了再算选批处理；来了就要算选流处理；反复迭代要快选内存计算计算机科学概论（微课版）｜第8章大数据218.5大数据处理·MapReduceMapReduce：分而治之的并行模型Google于2003—2004年发表论文提出MapReduce，初衷是解决搜索引擎大规模网页数据的并行化；思想源自函数式语言（Lisp）的map/reduce原语。2004年DougCutting受启发开发出开源的Hadoop，成为Apache最重要的项目之一。图8-14MapReduce模型（教材第149页）Map阶段读入分片转为键值对→map函数逐一处理→按键分区、排序、分组，相同键的值聚合。Reduce阶段Shuffle：复制本分区结果→合并排序后调用reduce函数→输出保存到文件（HDFS副本）。计算机科学概论（微课版）｜第8章大数据228.5大数据处理·MapReduce实例：Wordcount词频统计#Wordcount伪代码#key：字符串偏移量#value：文件中一行内容map(key,value){words=splitIntoToken(value)for(eachwordinwords){set(word,1)#(单词,1)}}

#key：单词；values：次数列表reduce(key,values){intresultfor(eachvalueinvalues){result+=value}write(key,result)}图8-15Wordcount任务执行流程（教材第150页）输入切分为若干Split，每个交给一个Map；结果按Reduce个数分区；Reduce把同Key数据聚集求和——"HelloWorld/HelloBigData"最终输出Hello,2World,1Big,1Data,1。回扣开篇：微博热搜=流处理实时清洗分析搜索记录；搜索引擎用MapReduce实现PageRank排序计算机科学概论（微课版）｜第8章大数据23章末·本章小结第8章小结：大数据❶概述——大数据是传统工具无法在可容忍时间内处理的海量数据，特征是5V：量大、速度快、多样、价值密度低、真实性强；发展历经萌芽、成熟、应用三阶段。❷采集——五类数据源（传感器、互联网、日志、企业业务、政府）；两大方法：ETL（抽取—转换—装载）与网络爬虫（种子URL出发循环抓取）。❸存储——HDFS：64MB数据块+三副本，namenode管命名空间、datanode存块；HBase：面向列的键值数据库，RowKey高并发，Region管理，属NoSQL家族。❹分析——先预处理（规范化、特征工程）；再挖掘：关联（Apriori）、分类（有监督）、回归（最小二乘）、聚类（K-means等）；最后用文本/关系/时空/统计四类可视化呈现。❺处理——三种计算框架：批处理（Hadoop离线）、流处理（Kafka+Flink/Spark实时）、内存计算（SparkRDD）；MapReduce用Map分、Reduce合，Wordcount是其"HelloWorld"。下一章预告：第9章云计算计算机科学概论（微课版）｜第8章大数据24拓展知识拓展：大数据与推荐系统本章以"个性化广告"开篇——大数据究竟如何在推荐系统中发挥作用？七个环节一目了然。①数据收集与处理汇聚行为、交易、社交、反馈等多源数据，经清洗→整合→特征抽取三步提炼可用信息。②用户画像构建分析行为模式与偏好，形成年龄、性别、地理位置、浏览与购买历史等详细画像。③推荐算法基于内容（物品特征×用户偏好）、协同过滤（用户/项目相似性）、混合推荐三类，可用机器学习与深度学习训练。④实时推荐借助Spark等分布式框架实时处理点击、浏览、购买行为，快速更新推荐内容。⑤个性化+⑥多样性与新颖性千人千面提升满意度与忠诚度；同时避免"越推越窄"，兼顾多样、新颖的内容。⑦A/B测试与优化用实验对比不同算法与参数的效果，大数据环境支持大规模用户群的统计显著结论，持续优化系统。计算机科学概论（微课版）｜第8章大数据25章末·习题课后习题（教材8.8节，共10题）概念理解·第1—2题1谈谈你对大数据中"大"字的理解。2列举3个大数据技术的应用，分析它们是如何用大数据解决问题的。要点：结合5V特征与8.1.3节案例。采集·第3—4题3用Python（Requests+BeautifulSoup）实现一个简单的爬虫demo。4如何处理不同来源、不同格式的海量数据？要点：ETL三环节与爬虫抓取流程。存储·第5—6题5以HDFS为例，描述分布式文件系统的存储原理及高可用机制。6分析传统关系型数据库处理大数据时会遇到哪些问题。要点：数据块、副本、namenode；对比HBase。分析与处理