算法导论MIT课件06sorting

中科大软件学院算法复习概念综合题

一、概念题： （1）排序算法时间复杂度： 排序算法最好最坏平均 插入O(n)O(n2)O(n2) 归并O(nlogn)O(nlogn)O(nlogn) 快排O(nlogn)O(n2)O(nlogn)排序算法空间复杂度： 1、所有简单排序和堆排序都是0(1) 2、快速排序为0(logn)，要为递归程序执行过程栈所需的辅助空间 3、归并排序和基数排序所需辅助空间最多，为O(n) （2）渐近记号 1、渐近确界：Θ(g(n))={f(n):存在正常数c1和c2和n0，使对所有的n>= n0，都有0<=c1g(n)<=f(n)<=c2g(n)}。大Θ记号给出函数的渐进确界。 2、渐近下界：Ω(g(n))={f(n):存在正常数c和n0，使对所有的n>=n0，都有0<=cg(n)<=f(n)}。大Ω记号给出函数的渐进下界。 3、渐近上界：O(g(n))={f(n):存在正常数c和n0，使对所有的n>=n0，都有0<=f(n)<=cg(n)}。大O记号给出函数的渐进上界。 （3）二叉查找树： 执行基本操作的时间与树的高度成正比。搜索、插入、删除的复杂度等于树高，期望O(lgn)，最坏O(n)（数列有序，树退化成线性表） （4）红黑树： 1、时间复杂度： 基本动态集合操作：O(log n)，n是树中元素的数目。 2、性质： 1)节点是红色或黑色。 2)根节点是黑色。 3)每个叶节点（NIL节点）是黑色的。 4)如果一个结点是红的，则它的两个儿子都是黑的（不能有两个连续 红结点） 5)从任一节点到其子孙结点的所有路径都包含相同数目的黑色节点。 3、相关概念，定理： 1）黑高度：从某个结点出发（不包括该结点）到达一个叶结点的任意一条路径上，黑色结点的个数称为该结点x的黑高度，bh(x)。红黑树的黑高度定义为其根节点的黑高度。 2）一颗有n个内结点的红黑树的高度至多为2lg(n+1)。(用2-3-4树理解) 3）在一颗黑高度为K的红黑树中，总结点数最多有22k+1-1，此时内结点

麻省理工-资料-发展经济学讲义(PDF 47页)

1Agriculture:The e?ciency of land use ?Share of agriculture in employment is close to 50%for the world as a whole(50%in China,57% in India). ?Is land used e?ciently? 1.0.1Farm size and productivity:observed rela- tionship ?Farm size productivity di?erences:see table. ?Pro?t-Wealth ration and weather variability(mon- soon outset is a measure of the risk faced by the farmer):see?gure

—The Pro?t-Wealth ratio is always greater for small farmers —Small farmers’pro?ts are hurt much more by uncertainty than large farmers’

1.0.2Why is this surprising??Arguments for increasing returns(the opposite re-lationship) —Technology with?xed costs(tractors,etc..) —Larger farmers have better access to capital —Larger farmers have better access to politi- cally allocated inputs(evidence from Africa in a book by Bates“Market and states in tropical Africa”). —The best farmer will have more land...?Mitigating factors: —Rental markets in farm machinery —Technological change in not very rapid.Savi- ness not that important.

MIT-OCW-麻省理工学院开放式课程

MIT OCW 麻省理工学院开放式课程 原文: 麻省理工学院的开放式课程计划”目前上线了九百门课程，已经到达了2007年所有课程上线的目标的一半。这些课程包括了麻省理工学院五个领域的三十三个不同学科的课程。 中文简体: 中文繁体: JHSPH约翰霍普金斯大学彭博公共卫生管理学院开放式课程 原文: 我们网站初期将先公布两门课程，在2005年4月之前预计再开放八门，在接下来的数年中则会公布更多的课程。 中文简体： 中文繁体： USU OpenCourseWare犹他州立大学开放课程 原文： 犹他州立大学开放课程是提供世界各地的学生、自学者和教育家们免费、自由开放的教育资源。开放式课程符合犹他州立大学透过学习、发现和投入来服务公众的目标。即是引导犹他州立大学的理念：「学术优先。」不管你是寻求额外协助的学生、想要准备新课程的教师、或是仅想要学习感兴趣主题的自学者，我们都希望犹他州立大学的开放式课程对您是有价值的。犹他州立大学开放课程并不提供学分或学位，也不提供与犹他州立大学师资的联络管道。犹他州立大学开放课程给您自由取用的是本校各个课程中所使用的资源与内容。 中文简体： 中文繁体： 大阪大学开放式课程计划 日文: 大阪大学坚守“立足本土、放眼世界”的格言，为了培养同时享有社会信赖的判断力、丰富的策划力以及和不同文化背景交流的沟通能力的人才，敝校以“教养”、“设计”、“国际”为具体的

教育目标，努力不懈。推动研究进步首重“网络”和“连结”，而在善用各种合作以发展学门融合的新学术领域的同时，希望也可向教育界反应其成果。国内六所大学首度携手合作，将所进行的教育及研究资产公开于麻省理工学院所提倡的开放式课程网页上，共同构筑一个“知识网络”。此举对负有知识交流场的使命的大学来说，是理所当然的责任，也是社会贡献的一环。另外，相信藉由此本知识网络上所提供的有限的教材，将可实现敝校“设计”、“国际”等教育目标。 中文简体： 中文繁体: 京都大学开放式课程网页 日文: 京都大学开放式课程网页从“具创造性的全球与在地知识社群”的全人类视点出发，希望可对国际知识资产的累积做出贡献，提高京都大学的能见度，招收全世界优秀的教员及学生，并增进国际网络教育的进展。 中文简体: 中文繁体: 庆应义塾开放式课程网页 日文： 本网站无偿提供庆应义塾大学部份电子化的实际讲义内容。不限于庆应义塾的在学生或毕业生，有志向学的大众亦可参考使用。本企画和美国麻省理工大学开放式课程网页合作，矢志将世界的知识提供给需要的人。 中文简体： 中文繁体： 东京工业大学开放式课程网页 日文： 东京工业大学开放式课程网页是东京工业大学为了因应全球化后的网络社会，所提供的核心学术资源的一部份。本网站向全世界无偿公开课程讲义资料，以此为平台，让最高水准的理工教育成为全世界共有的财产。

地下水水文学(麻省理工讲义)

1.72, Groundwater Hydrology Prof. Charles Harvey Lecture Packet #1: Course Introduction （课程简介）, Water Balance Equation(水量平衡) Hydrologic cycle with yearly flow volumes based on annual surface precipitation on earth, ~119,000 km 3/year. 3000 BC – Ecclesiastes 传道书1:7 (Solomon) “All the rivers run into the sea; yet the sea is not full; unto （直到） the place from whence the rivers come, thither they return again.” Greek Philosophers (Plato, Aristotle 柏拉图，亚里士多德) embraced the concept （接受这个概念）, but mechanisms were not understood. 17th Century – Pierre Perrault showed that rainfall （降雨） was sufficient to explain flow of the Seine. 地表径流 径流排泄 蒸腾和蒸发 渗透 地下水补给 地下水流动 低渗透地层

Latitude The Earth’s Energy (Radiation) Cycle: The Space Atmosphere Ocean and Land Circulation redistributes energy 20 0 -20 -60 4.0 3.0 T o tal Flux 2.0 Latent 1.0 Heat 0 Ocean -1.0 Currents Sensible Heat -2.0 -3.0 -4.0 En er gy Tra nsf er (10 22 cal /yr ) Ne t ra dia tio n flu x (10 1 cal cm 2 /yr ) 90 0 N 60 0 30 0 0 0 30 0 60 0 90 0 S

算法导论复习资料

算法导论复习资料 一、选择题：第一章的概念、术语。 二、考点分析： 1、复杂度的渐进表示，复杂度分析。 2、正确性证明。 考点：1）正确性分析（冒泡，归并，选择）；2）复杂度分析（渐进表示O，Ｑ，?，替换法证明，先猜想，然后给出递归方程）。 循环不变性的三个性质： 1）初始化：它在循环的第一轮迭代开始之前，应该是正确的； 2）保持：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确； 3）当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。 插入排序算法： INSERTION-SORT(A) 1 for j ← 2 to length[A] 2 do key ←A[j] 3 ?Insert A[j] into the sorted sequence A[1，j - 1]. 4 i ←j - 1 5 while i > 0 and A[i] > key 6 do A[i + 1] ←A[i] 7 i ←i - 1 8 A[i + 1] ←key 插入排序的正确性证明：课本11页。 归并排序算法：课本17页及19页。 归并排序的正确性分析：课本20页。 3、分治法（基本步骤，复杂度分析）。——许多问题都可以递归求解 考点：快速排序，归并排序，渐进排序，例如：12球里面有一个坏球，怎样用最少的次数找出来。（解：共有24种状态，至少称重3次可以找出不同的球） 不是考点：线性时间选择，最接近点对，斯特拉算法求解。 解：基本步骤： 一、分解：将原问题分解成一系列的子问题； 二、解决：递归地解各子问题。若子问题足够小，则直接求解； 三、合并：将子问题的结果合并成原问题的解。 复杂度分析：分分治算法中的递归式是基于基本模式中的三个步骤的，T(n)为一个规模为n的运行时间，得到递归式 T(n)=Q(1) n<=c T(n)=aT(n/b)+D(n)+C(n) n>c 附加习题：请给出一个运行时间为Q(nlgn)的算法，使之能在给定的一个由n个整数构成的集合S 和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。

中科大软件学院第一学期总结

考研究生调剂到了中科大软件学院，现在看来是一件让我觉得十分幸运的事情。中科大的学习气氛非常的浓，课程的内容也十分有新意，虽然有新意，但是又都是很基础的内容，让我收获很大，很多课程给我带来了很大的启发。直到过年时候，才腾出时间来写上一篇总结，记录我这一学期的生活和学习。我一直是一个地地道道的北方人，生在北京，长在北京，却跑到哈尔滨读了四年书。哈工大学习负担不轻，假期也很短，一直没有时间到处玩玩，再加上自己比较懒，大学期间也就去了趟长春。这次考到了中科大苏州研究院，心中对于南方的风土人情很是期待，内心中也不乏有些忐忑。 开学前，我直接跑到了南京玩了一周，玩的十分痛快，题外话暂且不提，然后从南京坐高铁到了苏州。中科大苏州研究院地处独墅湖高教园区，正巧高铁有工业园区一站，我就在工业园区站下了车。人生地不熟找不到合适的公交，直接拦下一辆出租车奔着学校这边就来了。苏州的出租车司机素质感觉比较高，礼让行人等做的都很不错，开车也很规矩。出租车司机还很健谈，就像北京的老师傅一样，听说我是来上学的，给我说了很多苏州的情况。我是提前一天前来报道的，物业态度很不好，不过好在顺利办理了入住手续，搬进了宿舍。宿舍两人寝，上床下桌，屋子不小，但是什么都没有，不过比较干净，我开学前几天都在置备东西。苏州的空气很好，略显湿润但却不潮湿，气温跟北京差不多，略高3℃左右，我很适应。住宿的地方离学校不近，走路30分钟左右，不过每天都有班车。中科大开的课程都很有意思，很多课程我遗憾的没有抢到，不过幸好没有全抢到我喜欢的课程，不然估计得累到爆。曾经我很不理解哈佛的学生为什么一学期只有8门课程还累得要死，知道我来到了号称不要命的来科大的中科大，才彻底理解了原因。中科大的课很有意思，难度也颇高，想要学好，就要付出150%的努力，而且基本上我学的所有的课都需要这种程度的努力。 下面说说我都上了些什么课，都有什么好玩的内容。英语免修过关考试侥幸水过，让我能够选一些其他我感兴趣的课程。一开始我选的是实用算法设计一课，第一节课时，老师负责任的指出此课程针对于没有算法基础的同学，恰巧此时算法分析与设计一课有一个空位，我就改选了算法分析与设计。实用算法设计一课使用的是《程序员实用算法》一书，说实在的，里面的例子都是经过精心编写的算法，非常优美，很多细节处理的十分精妙，可惜我还是更喜欢算法分析与设计一课。算法分析与设计使用的教材是经典的《算法导论》一书，整个课程跳过了一些简单的章节，但是覆盖到了算法导论中的大部分章节(不含第七部分和第八部分)。这课说实在的，超赞啊!我本科学的算法课用的是《算法概论》一书，比较偏重于算法设计，《算法导论》则是设计与分析并重。自己看《算法导论》的时候真心看不进去，这门课程一口气跟下来觉得并不吃力，而且有一种融会贯通的感觉。发现很多的时候，一个算法的时间复杂度暗示了其设计思想。上这门课的感觉还是很多问题都似曾相识，比如说经典的八皇后问题，这些问题以前在遇到的时候都是采用一些固定的策略来进行处理，并不知道为什么要采用这样的策略。这门课程让我认识到了三类基本问题：组合计数、组合优化、组合设计，每一类问题都有很多数学工具来对其进行分析和解决。顺便说一下，书中对于如何构造GF(pk)讲解的实在是让人有点稀里糊涂的，恰巧我另一门课程密码学及其应用中讲到了这些内容，让我在这点上没有稀里糊涂的跳过去。随机过程是一门神奇的课，说实在的，我一直都挺怕概率论的，我觉得概率论十分的违反直觉，很多时候得出的答案都令我十分费解，也不能够肯定是否正确。这有助于我们抛弃一些不必要的tricks，在关键的时候进行优化。(这也是CSAPP所需要达到的一个目标之一) 说完这两门课程，不妨看看上面提到过的密码学及其应用一课。在上这门课程以前，我一直认为密码学领域主要是一些数学问题，程序员需要关注的内容很少;上了这门课程后，我发现，所有的程序员都应该学习一下密码学的基本知识，走出密码学的误区。在这门课程上，我了解了，即便是有了安全的加密方式，如果使用不当的话，仍然可能会泄密或收到被攻击者伪装成正常消息而受到欺骗，非对称加密并不比对称加密更安全，反而，非对称加密方式由于加密速度较慢，使用范围会受到限制。有些不

北京航空航天大学 《算法导论》期末参考题(有一部分考到了)

一、选择题 1.算法分析中，记号O表示（B），记号?标售（A）,记号Θ表示（D） A 渐进下界 B 渐进上界 C 非紧上界 D 紧渐进界 E 非紧下界 2.以下关于渐进记号的性质是正确的有：（A） A f(n) =Θ(g(n)),g(n) =Θ(h(n))?f(n) =Θ(h(n)) B f(n) =O(g(n)),g(n) =O(h(n)) ?h(n) =O(f(n)) C O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D f(n) = O(g(n)) ?g(n) = O(f(n)) 3. 记号O的定义正确的是（A）。 A O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤ cg(n) }； B O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤cg(n) ≤ f(n) }； C O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有：0 ≤f(n)0，存在正数和n0 >0使得对所有n≥n0有：0 ≤cg(n) < f(n) }； 4. 记号?的定义正确的是（B）。 A O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤ cg(n) }； B O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤ f(n) }；

C (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有：0 ≤f(n)0，存在正数和n0 >0使得对所有n≥n0有：0 ≤cg(n) < f(n) }； 5. T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是( C ) A T（n）= T（n – 1）+1，T（1）=1 B T（n）= 2n2 C T（n）= T（n/2）+1，T（1）=1 D T（n）= 3nlog2n 6. 动态规划算法的基本要素为（C） A 最优子结构性质与贪心选择性质 B 重叠子问题性质与贪心选择性质 C 最优子结构性质与重叠子问题性质 D 预排序与递归调用 7.下列不是动态规划算法基本步骤的是（ A ）。 A 找出最优解的性质 B 构造最优解 C 算出最优解 D 定义最优解 8.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A） A 最优子结构性质与贪心选择性质 B 重叠子问题性质与贪心选择性质 C 最优子结构性质与重叠子问题性质

麻省理工,MIT, 线性代数,讲义11

https://www.sodocs.net/doc/bc9985576.html, 18.06 Linear Algebra, Spring 2005 Please use the following citation format: Gilbert Strang, 18.06 Linear Algebra, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare). https://www.sodocs.net/doc/bc9985576.html, (accessed MM DD, YYYY). License: Creative Commons Attribution- Noncommercial-Share Alike. Note: Please use the actual date you accessed this material in your citation. For more information about citing these materials or our Terms of Use, visit: https://www.sodocs.net/doc/bc9985576.html,/terms

https://www.sodocs.net/doc/bc9985576.html, 18.06 Linear Algebra, Spring 2005 Transcript – Lecture 11 OK. This is linear algebra lecture eleven. And at the end of lecture ten, I was talking about some vector spaces, but they're --the things in those vector spaces were not what we usually call vectors. Nevertheless, you could add them and you could multiply by numbers, so we can call them vectors. I think the example I was working with they were matrices. So the --so we had like a matrix space, the space of all three by three matrices. And I'd like to just pick up on that, because --we've been so specific about n dimensional space here, and you really want to see that the same ideas work as long as you can add and multiply by scalars. So these new, new vector spaces, the example I took was the space M of all three by three matrices. OK. I can add them, I can multiply by scalars. I can multiply two of them together, but I don't do that. That's not part of the vector space picture. The vector space part is just adding the matrices and multiplying by numbers. And that's fine, we stay within this space of three by three matrices. And I had some subspaces that were interesting, like the symmetric, the subspace of symmetric matrices, symmetric three by threes. Or the subspace of upper triangular three by threes. Now I, I use the word subspace because it follows the rule. If I add two symmetric matrices, I'm still symmetric. If I multiply two symmetric matrices, is the product automatically symmetric? No. But I'm not multiplying matrices. I'm just adding. So I'm fine. This is a subspace. Similarly, if I add two upper triangular matrices, I'm still upper triangular. And, that's a subspace. Now I just want to take these as example and ask, well, what's a basis for that subspace? What's the dimension of that subspace? And what's bd-dimension of the whole space? So, there's a natural basis for all three by three matrices, and why don't we just write it down. So, so M, a basis for M. Again, all three by threes. OK. And then I'll just count how many members are in that basis and I'll know the dimension. And OK, it's going to take me a little time. In fact, what is the dimension? Any idea of what I'm coming up with next? How many numbers does it take to specify that three by three matrix? Nine. Nine is the, is the dimension I'm going to find. And the most obvious basis would be the matrix that's that matrix and then this matrix with a one there and that's two of them, shall I put in the third one, and then onwards, and the last one maybe would end with the one. OK. That's like the standard basis.

中科大算法导论实验报告

实验一常见排序算法的实现与性能比较 一、实验环境 操作系统：Windows XP操作系统 编程语言：C语言 开发工具：Microsoft Visual C++ 6.0 二、问题描述 实现合并排序，插入排序，希尔排序，快速排序，冒泡排序，桶排序算法 三、实验要求 A．在随机产生的空间大小分别为 N = 10， 1000，10000，100000 的排序样本（取值为[0,1]）上测试以上算法。 B．结果输出: 1） N=10时，排序结果。 2） N=1000，10000，100000时，对同一个样本实例，不同排序完 成所需的时间。 3） N=1000，10000，100000时，每个排序用不同的样本多试验几次（最低5次）得出平均时间，比较不同排序算法所用的平均时间。 四、各种排序算法的原理及算法语言描述 （1）合并排序算法 1）合并排序的原理： 采用分治法。分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括n/2 个元素。治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作。合并: 合并两个排好序的子序列,生成排序结果。 2）合并排序算法语言描述： void Merge(float A[],int p,int q,int r){ int n1,n2,i,j,k; float L[10],R[10]; n1=q-p+1; n2=r-q; for(i=1;i<=n1;i++){ L[i]=A[p+i-1]; } for(j=1;j<=n2;j++){ R[j]=A[q+j]; } L[n1+1]=MAX; R[n2+1]=MAX; i=1; j=1;

麻省理工 系统与有效数字 讲义

Module 1: Units and Significant Figures 1.1 The Speed of Light When we observe and measure phenomena in the world, we try to assign numbers to the physical quantities with as much accuracy as we can possibly obtain from our measuring equipment. For example, we may want to determine the speed of light, which we can calculate by dividing the distance a known ray of light propagates over its travel time, distance speed of light =. (1.1.1) time In 1983 the General Conference on Weights and Measures defined the speed of light to be c=299,792,458meters/second. (1.1.2) This number was chosen to correspond to the most accurately measured value of the speed of light and is well within the experimental uncertainty. 1.2 International System of System of Units The three quantities – time, length, and the speed of light – are directly intertwined. Which quantities should we consider as “base” and which ones as “derived” from the base quantities? For example, are length and time base quantities while speed is a derived quantity? This question is answered by convention. The basic system of units used throughout science and technology today is the internationally accepted Système International (SI). It consists of seven base quantities and their corresponding base units: Mechanics is based on just the first three of these quantities, the MKS or meter-kilogram-second system. An alternative metric system to this, still widely used, is the so-called CGS system (centimeter-gram-second). So far as distance and time measurements are concerned, there is also wide use of British Imperial units (especially in the USA) based on the foot (ft), the mile (mi), etc., as units of length, and also making use of the minute, hour, day and year as units of time.

中科大软院算法导论区间树实验报告

区间树实验报告 1.区间树的实验源码见另外一个文件 2.区间树实验分析 2.1 需求分析 基础数据结构选择红黑树，每个结点x 包含一个区间域int[x]，x 的关键字为区间的低端点low[int[x]]，对树；进行中序遍历就可按低端点的次序列出个区间，结点还包含一个max[x]，即以x 为根的子树中所有区间的端点的最大值。如： 实验要求：将红黑树扩展为区间树 (1)区间的端点为正整数，随机生成； (2)内部节点数为n：2^4，2^6,2^8,2^10,2^12； (3)测试插入，删除，查找的时间并绘出曲线，运行次数为10 次； 2.2 程序设计 区间树的操作基本和红黑树的相同，在其基础上增加了一个新方法： INTERVAL_SEARCH(T,i）；它用来找出树中覆盖区间i 的那个结点。如果树中不存在，则返回nil[T]指针。代码如下： ITNode* IntervalTree::Interval_Search(Interval i){ ITNode* x=root; while(x!=Nil && !x->Overlap(i)){ // x != nil and i doesn't overlap int[x] if (x->left!=Nil && x->left->max>=i.low) x=x->left; else x=x->right; } return x; } 区间树的插入、删除除了有可能改变红黑树性质，还有可能改变结点的max 值。前者向红黑树那样处理就可以了，又 max[x] = max(high[int[x]], max[left[x]], max[right[x]]) 为解决后者，增加一方法Nodemax（），让它来维护结点的max 值。Nodemax()如下：void ITNode::NodeMax(ITNode* xl, ITNode* xr){ Type tp=this->interval->high;

mit-讲义-mincostflow

Makeup3:30–5in36-144on10/15 1Min-Cost Flow Many di?erent max-?ows in a graph.How compare? ?cost c(e)to send a unit of?ow on edge e ??nd max-?ow minimizing c(e)f(e) ?costs may be positive or negative! ?note:pushing?ow on cost c edge create residual cost?c edge. ?also easy to?nd min-cost?ow of given value v less than max(add bottle-neck source edge of capacity v) Clearly,generalizes max-?ow.Also shortest path: ?How send?ow1unit of?ow? ?just use shortest path ?more generally,?ow decompose into paths and cycles ?cost of?ow is sum of costs of paths and cycles. ?each path costs at most nC(C=max cost) ?cost of?ow at most mUC Min-cost circulation: ?no source or sink ?just?nd?ow satisfying balance everywhere,min-cost ?if satisfy balance everywhere,all?ow must be going in circles! ?more formally:circulation can be decomposed into just cycles. ?hard to de?ne in max-?ow perspective,but makes sense once allow nega-tive cost arcs. ?reduction to min-cost?ow:add disconnected s,t. ?reduction from min-cost?ow: –add s-t arc of“in?nite”capacity,“in?nite”negative cost –of course,circulation will push max possible through this edge –how much can it?max s-t?ow –so of course,su?to assign capacity equal to max-?ow value 1

算法导论学习报告

算法设计与分析 学 习 报 告

第一部分学习内容归纳 “计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述。”（参考文献：百度百科）《算法设计与分析》是一门面向设计，在计算机科学中处于核心地位的课程。这门课程主要讲授了在计算机应用中经常遇到的问题和求解的方法，分治法、动态规划法、随机算法等设计算法的基本原理、技巧和算法复杂性的分析，以及计算理论简介。 第一部分“概论和数学准备”在简单了解了算法的基本概念和复杂性、研究步骤等几个重要知识点后，着重学习了算法的数学基础，包括生成函数、差方方程的求解等，主要适用于求解算法的时间复杂性。 “任何可以用计算机求解的问题所需要的计算时间都与其规模有关：问题的规模越小，解题所需的计算时间往往也越短，从而也就比较容易处理。”（参考文献：《计算机算法设计与分析（第3版）》）而第二部分介绍的算法常用技术之首——分治法就运用了这样的思想。分治法的要领在于Divide（子问题的划分）-Conquer（子问题的求解）-Combine（子问题解的组合）。由于子问题和原问题是同类的，递归的思想在分治法中显得尤其重要，它们经常同时运用在算法设计中。这部分内容从Select（求第k小元）算法，寻找最近点对算法和快速傅立叶变换FFT等实际应用中深化对分治法思想的理解，同时也强调了平衡思想的重要性。 第三部分“动态规划”与分治法类似，同样是把问题层层分解成规模越来越小的同类型的子问题。但与分治法不同的是，分治法中的子问题通常是相互独立的，而动态规划法中的子问题很多都是重复的，因此通常采用递推的方法以避免重复计算。然而，也不是所有的情况下都采用递推法，当有大量的子问题无需求解时，更好的方式是采用动态规划法的变形——备忘录方法。通常需要用到动态规划法求解的问题都具有子问题的高度重复性和最优子结构性质两大特征，这也是我们分析问题和设计算法时的关键点。最长公共子序列LCS问题和最优二分搜索树就是从动态规划法的两个主要特征角度分析问题，进而设计出相应的解决算法的。而这部分内容中的另一个问题——流水作业调度，则告诉我们采用动态规划时偶尔也得不到高效的算法，我们要学会将已有的知识灵活运用，适当加工。 第四部分“集合算法”中首先介绍了一种分析算法复杂度的手法——平摊分析（Amortized Analysis）。与之前我们所接触的算法分析方法即逐一考虑执行每条指令所需的时间复杂度再进行累加的方法不同，平摊分析是对若干条指令从整体角度考虑其时间复杂度，通过这样的方法获得的时间复杂度更加贴近实际的情况。平摊分析的主要方法有聚集方法，会计方法和势能方法。聚集方法将指令的时间复杂度分类计算再相加；会计方法采用了耗费提前计算的思想；势能方法引入了势函数的概念，从每步操作的数据结构状态和势函数的关系角度分析得出操作的平摊代价。“集合算法”这一部分主要分析了Union（合并集合）和Find （给出元素所在集合名）这两种运算。从上学期的《数据结构》课程的学习中，我们就已经发现集合和树之间的关系是密不可分的，我们经常用树结构来表示集合。而2-3树是一种特殊的每个内结点都只有2个或3个儿子的树，广泛的应用于可实现Member（查找）、Insert（插入）、Delete（删除）操作的数据结构——字典，可实现Insert、Delete、Union和Min（查找最小叶结点）的数据结构——可并堆，可实现Insert、Delete、Find、Concatenate（保序合并）和Split

麻省理工计算机

还有另一种方法可以计数，我可以取1到10内所有整数的顺序排列，效果和我们前面做的毫无二致，可以从排列中的第一个数开始，执行某某，再到下一个数，执行某某，我可以逐个取到元素列中的每个元素。这是更为普遍的循环结构：for循环。for循环为此而生，它应用更为普遍。 for循环的格式是for<任意变量名> in<某数据列>之后是循环用的代码块，它表达的语义是，取占位符中的变量，令其值在数据列中从第一个开始逐个取到，并在取每一个值时，一次次执行代码块。这样的好处是，我们不用再为计数变量的变化操心了，它们会自动变化。只要数据列是有限的，循环就会终止。 x=10 for i in range(1,x): if x % i == 0: print 'divisor',i 1到10是怎么生成的呢？range是python的内建函数。 之前我们考虑了一个整数列，现在集中考虑数据列逐个取值，数据列是可以任意取的，它不一定要是整数列，我可以取这样一个集合，将某球员的击球数作为元素，不管取怎样的数据列，for总可以逐个取到，数据不需要按特定顺序排列，可以任意集合，我可以用for语句改写讲义上求平方根的那段代码。 回到约数的例子，对某个数，求其约数，现在的代码只是逐个打印出来给我，如果我想拿这些约数做点什么，求和，求积什么的，也就是说我需要一种收集数据的方式，这无法通过range实现，这是我们见到的第一种复合数据结构，称为“元组”。指的是有序的元素列。它是不可变的。如何创建元组，表示法用到方括号，（）里面填入元素，用【】是创建列表。用，分开。给test赋值有序元素列。还可以要求打印test的第0个元素。 >>> test=(1,2,3,4,5) >>> test (1, 2, 3, 4, 5) >>> test[0] 1 下面讲这段奇怪的悠久历史，元组都是从0开始计数的，元组可以使用逆顺序 >>> test[-1] 5 这就是元素选取，类似foo[0]这样的方式来选取特定元素，还可以取一部分。 >>> test[1:3] (2, 3) 得到这部分的复制品，这叫做切片。很好的性质，可以去头或尾。 >>> test[:3] (1, 2, 3) >>> test[0:] (1, 2, 3, 4, 5) >>> test[1:] (2, 3, 4, 5) 也就是：可以把range当作，实际上是一个列表，而并非元组，它是一种对所有元素的明确表示。好了，这与约数的例子有什么关联，这意味着可以创建元组，回到约数的例子，我想积累途中的元素，我可以一次加一部分进去，这里的代码能够实现此目的，循环内程序会收集数据，给他取个元祖名，这里的初始值称为“空元组”，元组内什么都没有，之后还是运