MIT 6.04J Spring 2015 | 计算机中的数学

课程官网

MIT 6.042J | Mathematics for Computer Science

MIT 6.042J | Online Publications 在线互动课程，注册账户登录后可以保存课程进度，提交前保存答案，以及其他更多功能！

课程时间安排

讲座：每周 3 次，每次 1.5 小时

课程简介

本课程介绍了面向计算机科学和工程的离散数学。

课程内容分为三个部分：

1. 数学的基本概念：定义、证明、集合、函数。
2. 离散结构：初等数

论、图论、计数。 3. 离散概率论。

先修课程

先修课程为 18.01 单变量微积分。特别是需要熟悉序列和级数、极限以及一元函数的微分与积分。

课程目标

完成 6.042J 后，学生将能够解释并应用计算机科学中离散（非连续）数学的基本方法。他们将能够在后续课程中运用这些方法来设计和分析算法、可计算性理论、软件工程和计算机系统。

具体来说，学生将能够：

1. 在计算机算法和系统中，对使用的基本数据类型和结构（如数字、集合、图、树）进行数学推理；区分严格定义和结论与仅仅看似合理的结论；综合基础性证明，特别是归纳证明。
2. 使用分析和组合方法对计算过程进行建模和分析。
3. 应用离散概率原理计算简单随机过程的概率和期望。
4. 在小组中完成上述所有目标。

学习成果

在课程结束时，学生将能够：

1. 使用逻辑符号定义并推理集合、关系、函数和整数等基本数学概念。
2. 评估基础数学论证并识别谬误推理（不仅仅是谬误结论）。
3. 综合归纳假设和简单的归纳证明。
4. 证明模算术的基本性质并解释其在计算机科学中的应用，例如在密码学和哈希算法中。
5. 应用图论模型解决数据结构和状态机的连接性和约束满足问题（例如调度）。
6. 应用不变量方法和良基序方法证明过程和状态机的正确性和终止性。
7. 从级数和递归中导出封闭形式和渐近表达式，以描述过程的增长速率。
8. 计算基本组合过程（如排列和组合）的可能结果数量。
9. 计算简单组合过程的概率和离散分布；计算期望值。
10. 与同学在小组中进行问题解决和学习。

团队问题解决

6.042J 是一门“翻转课堂”课程：学生通过完成指定阅读并在课前回答在线问题进行准备。课堂时间几乎全部用于围绕桌子坐的 6 到 8 名学生的小组问题解决，每个小组附近有一块白板可以书写解决方案。参与团队课程占最终成绩的 25%。

这些课程是开卷的，鼓励使用笔记本电脑、平板电脑等查看课程相关材料。

每个小组有一名教学助理/实验助理教练，对学生的解决方案提供反馈。教练最初会避免直接回答关于材料的问题，而是首先尝试找到一个小组成员向其余团队解释答案。当然，当整个小组陷入困境时，教练会提供提示和解释。教师在各组间巡视，监督课堂活动。

好消息是，积极参与问题解决课程对大多数学生来说是掌握材料的有效且愉快的方式。团队课程还为学生提供了一个获得和练习技术交流技能的监督环境。学生的团队问题解决成绩取决于积极、准备充分的参与程度，而不是问题解决的成功与否。课程的目标是让学生在课程结束时理解如何解决问题，而不是在课堂上测试学生解决问题的能力。

坏消息是，团队问题解决的教学方法要求学生在课程中做好准备：他们需要在课前完成（尽管不需要仔细研究）指定的阅读材料并完成在线问题。团队问题解决旨在帮助巩固学生已经看到的材料的理解。观看指定视频或至少浏览讲义通常是有帮助的，但不是必须的。我们预计，课堂准备（包括指定阅读和在线材料）将花费每节课 1.5 小时。

作业

作业占最终成绩的 15%。对于大多数学生来说，在作业上投入合理的努力对于掌握课程材料至关重要。作业设计在 3 小时内完成；时间通过学生报告进行监控。

在线反馈问题

在线问题在大多数课程前发布在课程网站上。这些问题由提供关于指定材料的有用反馈的简单问题组成。有些学生更喜欢在阅读文本或观看视频之前尝试在线问题，以便提前了解材料内容；这也可以。观看指定视频或至少浏览讲义通常是有帮助的，但不是必须的。

与课堂上的团队问题解决一样，在线问题仅根据参与情况评分：只要学生尝试了问题，即使答案错误，也可以获得满分。在线反馈问题占最终成绩的 5%。

合作

鼓励你在团队合作完成课堂问题时也在作业上进行合作。然而，你必须列出所有的合作者，并引用在处理问题时参考的所有超出本学期课堂材料的来源——例如，除了 6.042J 教职员之外的“专家”顾问，或其他文本——这些都必须在提交时包括在内。

有时，先前学期的问题可能会被再次分配而不做更改。如果你找到已发表的解决方案，你应予以引用，并且不能仅仅复制它。相反，你应提交对已发表解决方案的评论、改进后的解决方案或改进或变体版本的建议——基本上是任何显示出对材料参与程度的评论，这种参与程度应与自行解决问题所需的参与程度相当。

期中考试

将进行三次 80 分钟的期中考试。每次期中考试占最终成绩的 10%。

期中考试的问题通常是课堂和作业之前问题的变体，最好的准备方式是回顾这些问题的已发表解决方案。第一次考试涵盖所有前几周的内容；后续考试重点是上次考试之后的内容。归纳将在期中考试 1 中涵盖。每次期中考试允许带一张双面备忘单。

期末考试

将进行一次为期三小时的期末考试。此考试占最终课程成绩的 25%。

期末考试将涵盖整个学科，但会更侧重于期中考试 3 之后的内容。大多数考试问题将是学期中分配的问题（作业、课堂、期中考试和在线问题）的变体。它可能包含少数几个最初单独覆盖的主题组合的问题。期末考试允许带两张双面备忘单（总计：4 页）。

成绩

课程成绩基于以下权重：

活动	百分比
课堂参与	25%
在线反馈问题	5%
作业	15%
期中考试	30%
期末考试	25%

最低的作业分数和最低的三次课堂分数将不计入成绩计算。