大数据算法教学大纲

课程代码：090141128

课程英文名称：Big Data Algorithm

课程总学时：40  讲课：32  实验：8  上机：0

适用专业：信息与计算科学

大纲编写（修订）时间：2017.11    

一、大纲使用说明

（一）课程的地位及教学目标

大数据不论在研究还是工程领域都是热点之一，算法是大数据管理与计算的核心主题，因此将大数据算法作为信息与计算科学专业的一门选修课程。通过本课程的学习，使学生能掌握一些大数据算法设计的基本思想，较好的理解和传统算法课程不一样的算法设计与分析思路，通过实践练习初步掌握大数据算法设计与分析的技术，并能够将其中的思想应用于实际的研究和开发。从而提高学生的创新实践能力，加强学生开展科研工作能力。为今后进行更深入的研究奠定良好的理论基础。

通过本课程的学习，学生将达到以下要求：

1. 掌握大数据算法设计的基本思想，较好的理解大数据算法设计与分析的基本思路；

2. 初步掌握大数据算法设计与分析的基本方法和技术；

3. 初步具备将大数据算法应用于实际开发的能力，并能够分析算法效率。

（二）知识、能力及技能方面的基本要求

    1.基本知识：掌握大数据算法设计和分析的基本思想，掌握概率算法、I/O有效算法、并行算法等大数据算法的基本思想。

    2.基本理论和方法：掌握大数据算法设计的一般原理和步骤。要求学生能够掌握亚线性算法、外存算法、并行算法等算法的设计方法和分析技术。

    3.基本技能:具备运用亚线性算法、外存算法、并行算法等算法综合解决实际问题的能力，初步具备将大数据算法应用于实际开发的技能。

（三）实施说明

1．教学方法：本课程涉及大数据理论、算法设计技术、算法分析方法，涉及知识面广且比较抽象。建议采用案例教学并结合演示让学生理解和掌握各种算法设计方法，通过课堂讨论、课后作业和实验训练，加强学生对大数据算法设计方法的掌握。采用启发式教学，培养学生思考问题、分析问题和解决问题的能力；以最新的研究成果为导向，引导和鼓励学生通过查阅文献、实践获取知识，让学生了解大数据算法的前沿知识，培养学生的自学能力；增加讨论课，调动学生学习的主观能动性。

    2．教学手段：本课程建议采用课堂讲授、讨论、多媒体教学相结合的教学形式，以确保在有限的学时内，全面、高质量地完成课程教学任务。

3．教师在授课过程中可以根据实际情况酌情安排各部分的学时，课时分配表仅供参考。

（四）对先修课的要求

    本课程的教学必须在完成先修课程算法设计与分析之后进行，该课程的学习为算法的设计奠定了基础。

（五）对习题课、实践环节的要求

1．对重点、难点章节（如亚线性算法、外存算法、并行算法等）安排习题课，针对本章的算法进行回顾和总结，讲解典型算法设计题。课堂讲解算法思路，要求学生课后自己进行算法实现。

    2．课后作业要少而精，内容要多样化，作业题可以有几个同学合作完成，作业的完成情况应作为评定课程成绩的一部分。作业要能起到巩固理论，掌握算法设计方法和技巧，提高分析问题、解决问题能力，对作业中的重点、难点，课上应做必要的提示。学生必须、按时完成课外习题和作业，作业的完成情况应作为评定课程成绩的一部分。

    3．每个学生要完成大纲中规定的必修实验，通过实验环节，学生应掌握大数据算法的基本设计方法。实验成绩作为评定课程成绩的一部分。

    4．安排大作业，大作业成绩作为平时成绩的一部分。

（六）课程考核方式

    1．考核方式：采用五分制考查方式考核

    2．考核目标：在考核学生对大数据算法设计与分析的基本知识、基本原理和方法的基础上，重点考核学生的设计能力以及解决实际问题的能力。

    3．成绩构成：本课程的总成绩主要由三部分组成：平时成绩（包括作业情况、出勤情况等）占25%，实验成绩占25%，期末考试成绩占50%。

（七）参考书目

《大数据算法》，王宏志编著，机械工业出版社，2015

《算法导论》（第3版），(美)Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, and  Clifford Stein著，陈建平，徐云等译，机械工业出版社, 2007.

《概率与计算》，(美)Michael Mitzenmacher，史道齐译，机械工业出版社, 2007.

二、中文摘要

本课程是信息与计算科学专业学生必修的一门实践性很强的主干基础课程。课程通过对各种基本算法以及算法分析内容的讲授，使学生掌握算法设计的基本知识、基本思想，并具有设计算法和分析算法的能力。课程主要内容包括分治算法、动态规划算法、贪心算法、回溯算法以及分支限界算法等。本课程将为后续课程的学习以及相关课程设计、毕业设计等奠定重要的基础。

三、课程学时分配表

第1部分  大数据算法概述

总学时(单位：学时):2  讲课:2  实验:0    上机:0

具体内容： 

1)理解大数据的定义与特征，了解大数据的应用；

2)理解大数据算法的定义与特征，大数据算法设计与分析技术；

3)理解大数据算法的难度，了解大数据算法的应用；

重  点:

    大数据算法的定义与特征

重  点：

算法效率分析的基本方法和表示方法、递归算法的效率分析

难  点：

大数据算法设计与分析技术

习  题:

查找资料了解大数据的应用，并分析该大数据应用涉及到的数据规模、资源约束、时间约束和涉及到的算法。

第2部分  亚线性算法

总学时(单位：学时):10  讲课:8  实验:0  上机:0

第2.1部分 时间亚线性算法 (讲课2学时)

具体内容： 

1)掌握亚线性算法的定义；

2)通过实例理解什么是亚线性算法：

3)掌握最小生成树代价估计算法。

第2.2部分 时间亚线性判定算法 (讲课2学时)

1)理解时间亚线性判定算法的基本思想；

2）了解亚线性判定算法的应用。

第2.3部分 空间亚线性算法概述(讲课2学时)

具体内容：

1)理解空间亚线性算法的基本思想；

2）掌握水库抽样问题。

第2.4部分 空间亚线性算法(讲课2学时)

具体内容：

1）理解寻找频繁元素的非随机算法与随机算法的基本思想；

2)掌握估算不同元素数量的基本算法，了解改进算法。

重  点:

     时间亚线性计算方法，全0数组判定，平面图直径，最小生成树代价估计分治算法的设计、数组有序性判定，水库抽样问题。

难  点：

最小生成树代价估计分治算法的设计、数组有序性判定。

习  题:

写出一个判定问题并用时间亚线性算法解决.

第3部分  外存算法

总学时(单位：学时):10  讲课:8  实验:4  上机:0

第3.1部分 外存算法概述 (讲课2学时)

具体内容： 

1)理解外存存储结构，掌握外存算法的定义；

2)通过实例掌握外存排序算法；

3)理解外存搜索树算法。

第3.2部分  外存查找结构(讲课2学时)

具体内容

1)掌握B树的查找结构；

2)掌握KD树的查找结构。

第3.3部分  外存图数据算法 (讲课4学时)

具体内容

1）理解线性表排名问题；

2）掌握线性表排名问题的算法；

3）通过实例掌握缩图法；

4）理解单源最短路径问题的Dijkstra算法的I/O高效版本；

5）了解时间前向处理方法。

重  点: 

外存排序算法、缩图法的基本思想与步骤，外存查找结构，线性表排名问题，Dijkstra算法的I/O高效版本。

难  点：

外存排序算法、外存查找结构，线性表排名问题

习  题:

设计一个I/O有效的外存算法并分析其I/O复杂度；针对问题，设计外存有效的算法并分析I/O复杂度。

实  验：外存算法实验（4学时）

第4部分  并行算法

总学时(单位：学时):10  讲课:8  实验:4  上机:0

第4.1部分  MapReduce概述(讲课2学时)

具体内容： 

1)了解MapReduce的基本模型；

2)理解MapReduce的算法设计方法；掌握两种重要的算法设计模式——词对法和条块法；

3)了解MapReduce算法设计与算法实现技巧。

第4.2部分 连接算法(讲课2学时)

具体内容:

1)掌握普通连接算法的步骤；

2)理解相似连接算法的基本思想。

第4.3部分 图算法(讲课2学时)

具体内容：

1）理解基于广度优先搜索的MapReduce图处理算法的基本思想，掌握基本步骤；

2）掌握最小生成树的MapReduce算法；

3）了解使用图算法的注意事项。

第4.4部分 非MapReduce的并行算法(讲课2学时)

具体内容：

1）了解基于迭代处理平台的并行算法的基本思想；

2）了解基于图处理平台的并行算法的基本思想与基本步骤。

重  点:

MapReduce的基本模型，MapReduce的算法设计方法，普通连接算法，图处理算法。

难  点：

普通连接算法，图处理算法。

习  题:

针对问题，设计MapReduce算法，并进行优化。

实  验：并行算法实验（4学时）

第5部分  众包算法

总学时(单位：学时):6  讲课:6  实验:0  上机:0

第5.1部分 众包算法的定义(讲课2学时)

具体内容： 

1)掌握众包算法的定义；

2)通过实例理解众包算法。

第5.2部分  众包算法的要素和关键技术(讲课2学时)

具体内容:

1)掌握众包的流程、众包的报酬等基本概念；

2)理解众包中的关键技术。

第5.1部分 众包算法举例 (讲课2学时)

具体内容： 

1）掌握众包算法求解问题的的基本步骤；

2）通过实例理解众包算法如何应用。

重  点: 

众包算法的定义，众包的流程，众包的报酬，众包中的关键技术

难  点：

众包的流程，众包的报酬

习  题:

现实当中的数据有很多错误，有些错误是能够根据规则自动修复的，但是有一些错误计算机无从知道如何修费，请设计策略，利用众包有效修复数据中的错误。