课程介绍

算法设计与分析是计算机科学、软件工程相关专业的基础和核心课程。算法设计与分析是通过计算机编程解决实际问题的重要能力。从就业的角度来看，近年来随着计算机科学、移动互联网的飞速发展，越来越多的企业将算法设计与分析能力作为面试的主要（甚至是唯一的）考察内容；从学术发展的角度来看，掌握算法设计与分析的能力能够给未来的科学研究打下坚实的基础。学生通过选修算法设计与分析课程能够掌握使用计算机求解实际问题的基本方法以及训练逻辑思维能力和抽象建模能力。

本课程的目标在于培养学生设计针对于一些特定类型的问题的解决方案，并利用微积分、线性代数、离散数学的知识来证明解决方案的正确性以及计算复杂性。简而言之，课程目标可以概括为：培养学生“带着脑子写程序”的能力，即培养学生将所学习的数学知识与程序设计联系起来，从而对于解决复杂问题时写出高效的并且没有漏洞的程序的能力。

先修课程

课程名 课程号
微积分I C108001B
几何与代数 C108004B
概率论与数理统计 C108005B
程序设计基础 M210002B
离散数学 C110001B
数据结构 M310002B

课程组成员

姓名 电子邮箱 办公地点 答疑时间
李令昆（授课教师） kunkun (at) bjtu.edu.cn 逸夫教学楼YF西811 第10至17教学周每周二10:00~12:00
杨梦雅（助教） 22126407 (at) bjtu.edu.cn 逸夫教学楼YF西811 请预约网上答疑

授课时间及地点

周次 时间 地点
第10教学周至第17教学周 周二14:10~16:00 逸夫教学楼YF414
周五14:10~16:00 逸夫教学楼YF613
点此查看暂定教学日程

教学内容

  1. 算法分析的基本方法：算法正确性的证明、时间复杂度和空间复杂度的计算
  2. 简单的问题求解策略：蛮力算法与分治策略
  3. 基本排序算法：插入排序、归并排序、快速排序
  4. 最优子结构：动态规划与贪婪策略
  5. 基本图算法：深度优先搜索、广度优先搜索、并查集和拓扑排序、最短路问题、最小生成树问题
  6. 回溯法与分支限界
  7. NP完全性
  8. 线性规划：松弛形和单纯形、利用软件求解线性规划问题

教材及参考资料

本课程大部分内容来源于下列指定教材：

此外，课程内容还参考了：

成绩分布与评分规则

本课程为百分制课程，成绩分布如下：

  1. 平时成绩50分：包含书面作业和程序设计实践两个部分，其中：
    • 书面作业14分：共7次，每次2分，学生需要提交PDF格式的电子版（使用Word或者LaTeX排版均可）至KL教学平台，该部分由授课教师（或助教）手动评分。
    • 程序设计实践36分：共36题，每题1分，需要提交至KL教学平台，由平台自动评分，学生可以在截止日期不限次数的尝试解决（限C++语言），取最高分。平台使用黑盒测试的方式判断学生提交的程序是否正确，提交的程序代码以通过测试样例的个数比例计分。
  2. 期末考试50分：闭卷考试（不得携带教材、笔记，不得使用计算器、手机、笔记本电脑等电子设备），卷面成绩100分，共计120分钟。

最终录入成绩折算方式：北京交通大学综合教务系统在期末要求任课教师分别登录平时成绩与期末考试成绩，两者在登录时满分均为100分。授课教师在登录平时成绩时将采用“四舍五入”的方式化为整数。例如：若学生甲获得平时成绩74.52分，则录入教务系统平时成绩栏位中的分数为75分；对于期末考试而言，期末考试卷面满分为100分，因此授课教师将学生期末考试卷面成绩直接录入教务系统。

课堂规则

  1. 出勤：本课堂期望学生出席全部课程。若学生无法出席课程，应持有学院出具的请假条（本科生院网站上下载表格，由副院长和副书记审批后经教学科和团委盖章）或医生出具的书面证明，符合请假要求的，允许延期提交作业、延期参与随堂考试、缓考期末考试，延期的时间由授课教师酌情决定。授课教师有权在任意时间检查出勤情况，授课教师在检查出勤情况之后拒绝迟到学生的补出勤要求，缺勤或迟到累计两次及以上者，取消考核资格。
  2. 作业：提交作业的截止时间为公告的截止日期当日00:00分，即前一日的23:59:59（北京时间）。书面作业迟交一日的，得分减去所得分数的15%；迟交两日的，减去所得分数的30%；迟交三日及以上的不得分。程序设计实践不接受迟交作业。为了保障学生的学习质量，我们将尽力在作业截止日期之后的一周内反馈作业成绩和尽可能详细的扣分说明。
  3. 重新评分：虽然我们每次力求精准的判断作业答案的正确性，但是错误有时也会发生，如果学生认为自己的作业评分有误，可以在作业成绩发布后的一周内通过课程平台提交重新评分申请。重新评分申请只能通过课程平台提交，通过邮件提交的不予受理，超出截止日期的重新评分申请不予受理。
  4. 重要公告：课程进展过程中的通知公告一般在KL教学平台上发布，一些紧急的通知会通过校内邮箱发给大家，请定期查看KL教学平台和查收邮件。
  5. 课程资料的使用授权：由于课程资料（讲义、作业等）尚不具备出版资质，同时课程资料中的内容也不完全符合完全原创性与商用许可的规范（例如图片可能来源于其它文献，同时也未征得原作者的商用许可）。因此课程资料仅限课堂内部使用，未经授课教师许可不得在课程进行过程中以及课程结束之后公开发布或分发给课堂之外的第三人。违反此项规定者，应当承担由此引发的各种法律后果，同时授课教师有权对其寻求纪律处理。
  6. 课程礼仪：学生在参与课程过程中应当符合课程礼仪。行为举止及言语应当符合日常行为规范，不得出现谩骂他人，故意影响他人学习的行为。不遵守课程礼仪情节严重的，取消考核资格。
  7. 课程平台：学生不得使用任何技术手段攻击课程平台，如果课程平台存在漏洞应及时与授课教师联系。同时，学生有义务保证自己的账号安全，并不得将自己的课程平台账号借与他人使用。否则由此引发的一切后果由学生本人承担。
  8. 免听：依照《北京交通大学本科教学基本规范（校发〔2021〕35号）》第二十八条规定，学生通过自学或其他途径已掌握了某门课程的内容，或因为选课冲突要兼顾两门课程的学习，可以提出免听申请。免听申请应当通过教务系统提出，由授课教师审批。获准免听的同学可以不参与出勤检查，但仍需要按本细则的各项要求完成课程作业以及参与期末考试。授课教师将尽全力在第10周周末之前审批完成所有免听申请，然而由于授课教师工作繁多，因此可能有所延误，学生在等待授课教师审批免听申请期间或者免听申请被拒绝的，应当保证出勤，否则按缺勤处理。
  9. 因病造成学习困难的特殊政策：本课堂致力于为全部同学提供一种平等的学习环境。因病而造成学习困难的，例如焦虑症、理解障碍、抑郁症、双相情感障碍、精神分裂症等，可以在学期中的任何时间凭医院的诊断证明寻求任课教师力所能及的额外帮助（包括但不限于：允许延期提交作业，降低作业难度等），但仍然需要遵守课程的学业诚信的相关规定，授课教师保证保护当事同学的隐私。

答疑和电子邮件

  1. 请讲究提问的艺术：答疑不是让老师替你写作业，如果你需要答疑，那么你需要首先对自己的问题先有一些思考，然后再跟老师和其他同学讨论。我们不会回答简单的“XXX题目怎么做？”这种提问，正确的提问方式应该是“XXX题目我的想法是XXX，但是因为XXX，我发现我的想法是不对的，请问我应该怎样去思考（或者我的想法有什么问题）？”。
  2. 所有答疑的问题必须先发送到课程平台的讨论区中，因为你有的问题可能别人也有，公开答疑过程可以提高答疑的效率。同时学生应当在提问之前仔细阅读其它同学已经提出的问题并查看下方的讨论和回答，避免重复提问。
  3. 针对于课程材料和作业的问题通过邮件提问一律不予回复，我们非常乐意回复关于其它内容的提问，例如免听、请假、寻求专业建议等。同时，永远不要发类似“老师我就差1分就90分了，我还有什么办法可以得到这一分？”的邮件，这是不合适的。
  4. 未在课程平台的讨论区提问的而直接在答疑时间来办公室提问的，授课教师将要求学生先在讨论区发帖提问，如果有必要再请学生来办公室讨论。
  5. 请慎重在讨论区公开张贴自己的代码，因为这样可能导致其他同学直接复制粘贴你的代码作为自己的作业提交，而进一步导致你的代码被查重系统判为互相抄袭。如果确实要粘贴代码的，请在讨论区发帖时勾选“仅课程组成员可见”。
  6. 尽早提问，我们尽量会在问题提出的24小时内给出回复，但是我们不保证一定在作业截止日期前回复。如果同学们都只在作业截止日期的前一两天提问，那么我们肯定是没法及时答疑的，由此造成作业未完成的情况需自行承担后果。
  7. 尽可能的回答他人提出的问题，要积极的与他人交流，这不仅会帮助他人解决困惑，也会整理自己的思路，同时也有助于发现自己潜意识当中没有认识到的问题以便授课教师帮助你弄清楚。
  8. 授人以鱼不如授人以渔，我们虽然鼓励大家积极的回答其他同学提出的问题，参与讨论区当中的讨论，但是一个好的回答应该能够启发别人的思考。例如对于提问“我希望能够对一个有n个元素的数组从小到大排序，请问在C++语言当中要怎么做？”，一个不好的回答是：“sort(a, a+n)”，而好的回答应该是：“标准库algorithm中有一个sort函数，它不仅可以实现简单的排序，还可以按照你定义的大小关系对一般对象进行排序。这个函数一般接受两个参数，是要排序容器的两个用于标注界限的迭代器，也可以接受第三个参数明确排序方式。你可以参考https://cplusplus.com/reference/algorithm/sort/来学习该函数的具体用法”。
  9. 所有问题都可以提问。不要觉得自己的问题很初级，提问了会让老师和同学觉得自己怎么这么简单的问题都不会，如果你有这个想法，你可以在讨论区发起匿名提问，这样一来就不会有人知道问题是谁提出的了！

关于课程内合作与学业诚信的特别规定

  1. 课程资料的讨论原则：在过去的教学实践中，授课教师认为学习课程资料的最佳方式是互相讨论课程资料的内容。因此课程鼓励大家通过线上（组织交流群、在课程平台讨论区发帖等）、线下（学习小组、答疑时间）等方式讨论学习课程资料，但是讨论的过程中不应当直接给出用于课程评分的作业答案，同时学生在学习过程中不得直接参考和讨论以往学期发布的任何用于课程评分的作业答案。也就是说，涉及到用于课程评分的部分必须是学生独立完成的成果。学生若实在无法想出作业的解决思路，正确的方法是通过邮件、课程平台、或者在答疑时间联系授课教师，寻求帮助。
  2. 课程作业的查重：课程将对书面作业的重复情况酌情进行衡量；同时使用如下代码重复检测系统检测学生提交的全部编程实践作业： 特别提示：使用修改变量名、修改函数名、修改函数定义顺序等简单的拷贝—粘贴—修改的作弊方式将不能通过代码重复检测系统的查重。过去的教学实践表明，通过代码查重的唯一方法是独立完成代码的编写。 往期课程中发现的抄袭案例可以点击这里查看。
  3. 考试纪律：课程中的所有考试均为闭卷考试，学生在考试过程中的行为应当符合《北京交通大学考试管理规定》中的各项要求。
  4. 违反本特别规定的后果：学生违反本特别规定的，一份《学业不诚信报告》将归档至课程档案。同时，若是针对于课程作业的不诚信行为，该项作业成绩记为0分。若是违反考试纪律的，课程总评成绩记为0分，并视情节轻重寻求纪律处分。
  5. 学业不诚信报告制度：第一次被记录《学业不诚信报告》的，予以警告并取消当次作业成绩，第二次及以上被记录《学业不诚信报告》的，视情节予以总成绩扣分（直至扣至0分），或者取消考核资格，直至依照《北京交通大学本科生学籍管理规定》第十九条之规定，总成绩记为0分，并备注“作弊”。

考核资格的相关规定

  1. 依照《北京交通大学本科生课程考核与成绩管理办法》的相关规定，任课教师有权根据学生课堂出勤、作业和阶段测试等环节的完成情况决定是否取消学生的考核资格。被取消考核资格的学生，不能参加课程考核，不具有对任课教师评价的资格。任课教师应将被取消考核资格的学生的课程总评成绩记为零分或者“F”，并在备注中注明“取消资格”。该管理办法同时还规定了被取消考核资格的学生不得申请参加补考，只能选课重修。
  2. 授课教师取消学生的考核资格，应当在决定取消考核资格时通过校内电子邮件的形式向被取消考核资格学生送达取消考核资格决定，并按学校教学规定面向课堂公告。
  3. 北京交通大学本科生院通常将于期末考试前组织取消考核资格的统计工作以取消学生的评教资格，但是不排除出现本科生院因各种原因未组织取消考核资格统计工作的情况，当此情况发生时，无论学生是否具备评教资格，任课教师仍然会在综合教务系统中登录学生的成绩为零分，备注“取消资格”，并将相关情况报告学院教学科。
  4. 学生被决定取消考核资格后，课程平台不再接受该学生提交的作业。