国科大卜东波算法期末考试资料平时作业

### 国科大卜东波算法期末考试资料平时作业知识点解析 #### 一、课程背景与目标 在《算法设计与分析》课程中，学生将深入学习如何有效地设计和分析算法，解决各种复杂问题。本课程由国科大的卜东波教授主讲，通过理论讲解与实践练习相结合的方式，帮助学生掌握算法的基本概念、设计技巧以及分析方法。期末考试及平时作业是检验学生学习成果的重要手段之一。 #### 二、关键知识点解析 ##### 1.1 Stable Matching Problem (稳定匹配问题) **知识点**: 稳定匹配问题主要探讨如何在一组男人和一组女人之间找到一种稳定的配对方式，使得不存在一对男女，他们相互更愿意与对方而不是当前的配对对象。该问题的经典应用场景包括医学院学生的分配、工作市场的招聘等。 **例题**: 假设有一个人 \(m\) 和一个人 \(w\)，其中 \(m\) 在 \(w\) 的偏好列表中排名第一，同时 \(w\) 也在 \(m\) 的偏好列表中排名第一。那么在所有可能的稳定匹配中，\((m, w)\) 都会是一对。 **解析**: - **证明**: 使用反证法。假设存在一个稳定匹配 \(S\)，在这个匹配中 \((m, w)\) 不属于 \(S\)。这意味着存在另外两个人 \(w'\) 和 \(m'\)，使得 \((m, w')\) 和 \((m', w)\) 属于 \(S\)。但由于 \(m\) 更偏好 \(w\) 而非 \(w'\)，同样 \(w\) 更偏好 \(m\) 而非 \(m'\)，这会导致 \((m, w)\) 成为一个不稳定配对，与 \(S\) 是稳定匹配的前提矛盾。因此，在任何稳定匹配中，\((m, w)\) 必须是一对。 - **结论**: 此题中的命题为真。 ##### 1.2 G-S Algorithm (Gale-Shapley 算法) **知识点**: Gale-Shapley 算法是一种用于解决稳定匹配问题的有效算法。它通过模拟一系列提议和拒绝的过程来找到一个稳定的匹配结果。 **例题**: 在由 Gale-Shapley 算法生成的稳定匹配 \(S\) 中，每个女性都被配对给了她的最差有效伴侣。 **解析**: - **证明**: 设 \(w_1\) 的最差有效伴侣为 \(m_1\)。如果 G-S 算法生成的稳定匹配 \(S\) 中 \(w_1\) 没有与 \(m_1\) 相配，而是与 \(m_2\) 相配，则 \(w_1\) 更喜欢 \(m_2\) 而非 \(m_1\)（因为 \(m_1\) 是 \(w_1\) 的最差有效伴侣）。假设另一个匹配 \(S^*\) 中 \(w_1\) 与 \(m_1\) 相配，\(m_2\) 与 \(w_2\) 相配，并且 \(m_2\) 的最好有效伴侣为 \(w_1\)。在这种情况下，由于 \(m_2\) 更喜欢 \(w_1\) 而非 \(w_2\)，同时 \(w_1\) 更喜欢 \(m_2\) 而非 \(m_1\)，这导致 \(w_1\) 和 \(m_2\) 形成不稳定配对，与 \(S^*\) 作为稳定匹配相矛盾。 - **结论**: 此题中的命题为真。 ##### 1.3 Stable Scheduling Problem (稳定排期问题) **知识点**: 稳定排期问题是在两个电视台之间分配黄金时段的问题。每个电视台都有多个节目，每个节目有一个固定的评分。目标是让每个电视台尽可能多地赢得时间槽。 **例题**: 给定两个电视台 A 和 B，每个电视台都有 n 个黄金时段和 n 个节目。对于每个时段，评分较高的节目获胜。稳定的一对排期是指没有哪个电视台能够单方面改变自己的排期以赢得更多的时间槽。 **解析**: - **命题**: 对于任何给定的节目和评分集合，总存在一对稳定的排期。 - **证明**: 该命题为假。考虑当 n=2 时的情况，假设 A 有两个节目的评分分别为 \(a_1, a_2\)，B 有两个节目的评分分别为 \(b_1, b_2\)，并且满足 \(a_1 > b_1 > a_2 > b_2\)。在这种情况下，无论如何安排节目，都无法形成稳定的一对排期，因为 A 总是可以通过调整节目顺序来赢得更多的时段。 - **结论**: 此题中的命题为假。 #### 三、总结 通过对这些例题的解析，我们可以看到算法设计与分析课程不仅注重理论知识的学习，还强调实际问题的应用能力。学生需要理解并掌握算法的基本原理，同时学会如何利用算法解决具体问题。在后续的学习过程中，应该更加重视实践操作，提高解决实际问题的能力。