loading
《大数据算法》课程教学大纲
课程代码：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 8 12 12 讲课 2 8 2 2 2 8 2 2 4 8 2 2 实验 4 4 4 上机 2.1 时间亚线性算法 2.2 时间亚线性判定算法 2.3 空间亚线性算法概述 2.4 空间亚线性算法举例 3 外存算法 3.1 外存算法概述 3.2 外存查找结构 3.3 外存图数据算法 3.4 外存算法实验 4 并行算法 4.1 MapReduce概述 4.2 连接算法
4.3 图算法 4.4 非MapReduce的并行算法 4.5 并行算法实验 5 众包算法 5.1 众包算法的定义 5.2 众包算法的要素和关键技术 5.3 众包算法举例 合计 6 40 2 2 6 2 2 2 32 4 8 四、教学内容及基本要求
第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) 掌握估算不同元素数量的基本算法，了解改进算法。