复杂算法分析与设计课程手写笔记-电子版

复杂算法分析与设计课程手写笔记-电子版。包括找max/min,max+min,second,k-th，最小生成树kruskal，素数测试 prime test，最小割 min_cut，DAG k-path，集合分割 set_split，顶点覆盖 vertex_cover，集合覆盖 set_cover，最大割 max_cut，MAX_SAT，多机调度，背包问题knapsack，线性规划LP。 《复杂算法分析与设计》是一门深入探讨计算机科学核心领域的课程，主要关注如何高效地解决各种计算问题。这些手写笔记涵盖了多个经典算法及其应用，包括优化问题、图论问题和理论计算复杂度分析。以下是笔记中涉及的主要知识点的详细说明： 1. **找 max/min, max+min, second, k-th**：这是关于数据结构和排序的基本操作，例如查找数组中的最大值、最小值、次大值以及第k小（大）元素。快速选择和二分查找等高效算法可以用于这类问题。 2. **最小生成树 Kruskal**：Kruskal算法是一种解决图论问题的方法，用于找到一个加权无向图的最小生成树。该算法基于贪心策略，按边的权重从小到大加入，避免形成环路。 3. **素数测试 prime test**：素数测试涉及到判断一个整数是否为素数。常见的方法有质数筛法、Miller-Rabin测试和AKS测试等，其中后两者是概率性测试，效率较高但可能有错误概率。 4. **最小割 min_cut**：在图论中，最小割问题是寻找将图分成两个部分，使得边的权重之和最小。这在网络流问题、电路设计和资源分配中有广泛应用。 5. **DAG k-path**：DAG（有向无环图）中的k路径问题寻找从一个节点到另一个节点的最长路径，具有k个中间节点。这个问题可以通过拓扑排序和动态规划来解决。 6. **集合分割 set_split**：集合分割问题旨在将一个集合分成多个非空子集，满足特定条件，如所有子集的大小相等或尽可能接近。这可能涉及到组合优化和贪心算法。 7. **顶点覆盖 vertex_cover**：顶点覆盖问题是在图中找到最小数量的顶点，使得每个边至少与其中一个顶点相连。它是NP完全问题，可以采用近似算法解决。 8. **集合覆盖 set_cover**：集合覆盖问题是要找到覆盖整个集合所需的最少子集数量。它也是NP完全问题，常见解法有贪心算法和近似算法。 9. **最大割 max_cut**：与最小割相反，最大割问题寻找将图分成两部分，使得边的权重之和最大。它在社会网络分析、电路设计等领域有应用。 10. **MAX_SAT**：MAX-SAT是满足性问题（SAT）的优化版本，目标是找到尽可能多的满足公式子句的变量赋值。 11. **多机调度**：在多台机器上分配任务以最小化完成时间或最大化吞吐量，通常涉及贪心策略、动态规划或近似算法。 12. **背包问题 knapsack**：背包问题是一种优化问题，要求在给定容量限制下，选择物品以最大化总价值。0-1背包、完全背包和多重背包是其不同变种。 13. **线性规划 LP**：线性规划是数学优化的一个分支，目的是在满足一组线性约束条件下，最大化或最小化一个线性目标函数。常用的求解方法有单纯形法和内点法。 14. **P, NP, NPH, NPC**：P类问题是指能在多项式时间内解决的决定性问题，NP类问题是在多项式时间内验证解的正确性的问题。如果一个NP问题能在多项式时间内找到解，则它属于P类。NP难（NPH）问题是指所有NP问题都能在多项式时间内归约到它。NPC（NP完全）问题是最难的NP问题，任何NPC问题的多项式时间算法都能解决所有NP问题。 15. **近似比**：在NP难问题中，近似算法无法找到最优解，但能提供一个接近最优解的解决方案。近似比衡量了算法得到的解与最优解之间的差距。 以上是复杂算法分析与设计课程笔记中的主要内容，每个主题都涉及到计算机科学的核心思想和技术，对于理解和解决实际问题至关重要。通过深入学习这些概念和算法，可以提高解决问题的能力，并为从事算法设计、系统优化和复杂问题求解打下坚实基础。