分治法和高德纳

快捷方式: 差异，相似，杰卡德相似系数，参考。

分治法和高德纳之间的区别

分治法 vs. 高德纳

在计算机科学中，分治法是建基於多項分支遞歸的一种很重要的算法範式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 这个技巧是很多高效算法的基础，如排序算法（快速排序、归并排序）、傅立叶变换（快速傅立叶变换）。 另一方面，理解及設計分治法算法的能力需要一定時間去掌握。正如以歸納法去證明一個理論，為了使遞歸能夠推行，很多時候需要用一個較為概括或複雜的問題去取代原有問題。而且並沒有一個系統性的方法去適當地概括問題。 分治法這個名稱有時亦會用於將問題簡化為只有一個細問題的算法，例如用於在已排序的列中尋找其中一項的折半搜索算法（或是在數值分析中類似的勘根算法）。這些算法比一般的分治算法更能有效地執行。其中，假如算法使用尾部遞歸的話，便能轉換成簡單的迴圈。但在這廣義之下，所有使用遞歸或迴圈的算法均被視作「分治算法」。因此，有些作者考慮「分治法」這個名稱應只用於每個有最少兩個子問題的算法。而只有一個子問題的曾被建議使用減治法這個名稱。 分治算法通常以數學歸納法來驗證。而它的計算成本則多數以解遞迴關係式來判定。. 德納（Donald Ervin Knuth，音譯：唐納德·爾文·克努斯，），出生於美国密尔沃基，著名计算机科学家，斯坦福大学计算机系榮譽退休教授。高德纳教授為现代计算机科学的先驅人物，創造了演算法分析的領域，在數個理論計算機科學的分支做出基石一般的貢獻。在计算机科学及数学领域发表了多部具广泛影响的论文和著作。1974年圖靈獎得主。 高德纳最為人知的事蹟是，他是《计算机程序设计艺术》的作者。此書是計算機科學界最受高度敬重的參考書籍之一。此外還是排版軟件tex和字型設計系統Metafont的发明人。提出文学编程的概念，並創造了WEB與CWEB軟體，作為文學編程開發工具。.

计算机科学

计算机科学用于解决信息与计算的理论基础，以及实现和应用它们的实用技术。 计算机科学（computer science，有时缩写为CS）是系统性研究信息与计算的理论基础以及它们在计算机系统中如何与应用的实用技术的学科。 它通常被形容为对那些创造、描述以及转换信息的算法处理的系统研究。计算机科学包含很多分支领域；有些强调特定结果的计算，比如计算机图形学；而有些是探討计算问题的性质，比如计算复杂性理论；还有一些领域專注于怎样实现计算，比如程式語言理論是研究描述计算的方法，而程式设计是应用特定的程式語言解决特定的计算问题，人机交互则是專注于怎样使计算机和计算变得有用、好用，以及随时随地为人所用。 有时公众会误以为计算机科学就是解决计算机问题的事业（比如信息技术），或者只是与使用计算机的经验有关，如玩游戏、上网或者文字处理。其实计算机科学所关注的，不仅仅是去理解实现类似游戏、浏览器这些软件的程序的性质，更要通过现有的知识创造新的程序或者改进已有的程序。 尽管计算机科学（computer science）的名字里包含计算机这几个字，但实际上计算机科学相当数量的领域都不涉及计算机本身的研究。因此，一些新的名字被提议出来。某些重点大学的院系倾向于术语计算科学（computing science），以精确强调两者之间的不同。丹麦科学家Peter Naur建议使用术语"datalogy"，以反映这一事实，即科学学科是围绕着数据和数据处理，而不一定要涉及计算机。第一个使用这个术语的科学机构是哥本哈根大学Datalogy学院，该学院成立于1969年，Peter Naur便是第一任教授。这个术语主要被用于北欧国家。同时，在计算技术发展初期，《ACM通讯》建议了一些针对计算领域从业人员的术语：turingineer，turologist，flow-charts-man，applied meta-mathematician及applied epistemologist。 三个月后在同样的期刊上，comptologist被提出，第二年又变成了hypologist。 术语computics也曾经被提议过。在欧洲大陆，起源于信息（information）和数学或者自动（automatic）的名字比起源于计算机或者计算（computation）更常见，如informatique（法语），Informatik（德语），informatika（斯拉夫语族）。 著名计算机科学家Edsger Dijkstra曾经指出：“计算机科学并不只是关于计算机，就像天文学并不只是关于望远镜一样。”（"Computer science is no more about computers than astronomy is about telescopes."）设计、部署计算机和计算机系统通常被认为是非计算机科学学科的领域。例如，研究计算机硬件被看作是计算机工程的一部分，而对于商业计算机系统的研究和部署被称为信息技术或者信息系统。然而，现如今也越来越多地融合了各类计算机相关学科的思想。计算机科学研究也经常与其它学科交叉，比如心理学，认知科学，语言学，数学，物理学，统计学和经济学。 计算机科学被认为比其它科学学科与数学的联系更加密切，一些观察者说计算就是一门数学科学。 早期计算机科学受数学研究成果的影响很大，如Kurt Gödel和Alan Turing，这两个领域在某些学科，例如数理逻辑、范畴论、域理论和代数，也不断有有益的思想交流。.

分治法和计算机科学 · 计算机科学和高德纳 · 查看更多 »