当前位置:首页 » 操作系统 » 算法的发展史

算法的发展史

发布时间: 2024-12-29 15:17:57

⑴ 求算术起源至今的发展史 先中国再外国 一一列举

我国数学在世界数学发展史上,有它卓越的贡献。早在远古时代,人们就用绳结表示事物的多少,在彩陶中绘有大量的直线、三角、圆、方、菱形、五边形、六边形等对称图案,在房屋遗址的基地上,亦发现几何图形,表明远古的人们在一定程度上已经具有数和形的概念。

在新石器时期的彩陶钵上,有多种刻画符号,其中丨、、、×、+等,很可能是我国最早的记数符号。产生文字之后,在殷商的甲骨文中出现了记数的专用文字和十进制记数法,并且运用规和矩作为简单的绘图和测量工具。《前汉书·律历志》记载了用竹棍表示数和计算的方法,称为算筹和筹算。在春秋早期乘法口诀被称为“九九”歌,已经成为很普通的知识。

春秋战国时期,学术繁荣,产生了相当精彩和可贵的数学思想;公元前6世纪,已经有了关于简单体积和比例分配问题的算法,在《考工记》中记载了分数和角度的资料;到秦始皇时,统一了度量衡,并且基本上采用了十进制的度量单位,在《墨经》中提出了几何名词的定义和几何命题等。《杜忠算术》和《许商算术》是最早的数学专着,但这两部书都失传了。至今仍保留的古代数学专着是《算数书》,全书共有60多个小标题、90多个题目,书中内容涉及了整数和分数的四则运算、比例问题、面积和体积问题等、并且含有“合分”、“少广”等数学思想。

大约公元前1世纪完成了《周髀算经》(书中大部分内容于公元前7到6世纪完成),书中记述了矩的用途、勾股定理及其在测量上的应用,相似直角三角形对应边成比例的定理、开平方问题、等差级数问题,应用古“四分历”计算相当复杂的分数运算等,此书为重要的宝贵文献。

古代数学的着名着作是《九章算术》,大约成书于公元1世纪东汉初年,全书列举了246个数学问题及解决问题的方法。共有九章:第一章“方田”介绍土地面积的计算、含有正方形、矩形、三角形、梯形、圆、环等面积公式,弓形面积和球形表面积的近似公式,还有分数四则运算法则、约分、通分、求最大公约数等方法;第二章“粟米”介绍了各种粮食折算的比例问题,及解比例的方法,称为“今有术”;第三章“衰(Cuǐ)分”介绍了按等级分配物资或按一定标准摊派税收的比例分配问题、等差数列和等比数列问题等;第四章“少广”介绍了已知正方形面积或正方体体积,求边长或棱长的开平方或开立方的方法,已知球的体积求直径的问题等;第五章“商功”介绍了立体体积计算,包括长方体、棱柱、棱锥、棱台、圆柱、圆锥、圆台、楔形体等体积的计算公式;第六章“均输”介绍了计算按人口多少、物价高低、路程远近等条件,合理摊派税收、民工的正比、反比、复比例、等差级数等问题;第七章“盈不足”介绍了盈亏类问题的算法;第八章“方程”介绍了一次联立方程问题,引入了负数的概念,及正负数的加减法则;第九章“勾股”介绍了勾股定理的应用和简单的测量问题,其后,历史上着名数学家刘徽、祖冲之、李淳风、贾宪等,都曾经深入研究和注释过《九章算术》并且提出许多新的概念和新的方法。在诸如勾股定理的证明、重差术、割圆术、圆周率近似值、球的体积公式、二次和三次方程的解法。同余式和不定方程的解法等方面做出了重要的新贡献。

我国古代数学专着有《勾股圆方图注》、《九章算术注》、《孙子算经》、《五经算术》、《缀术》等。特别应该指出的是,刘徽在《九章算术注》中对《九章算术》的大部分数学方法作了严密的论证,对于一些数学概念提出了明确的解释,为中国数学发展奠定了坚实的理论基础。祖冲之在《缀术》中得出了比刘徽所提出的值更精密的圆周率,成为举世公认的重大成就。贾宪在《黄帝九章算法细草》中提出的“开方作法本源”图和增乘开方法,以及《孙子算经》中的“孙子问题”,《张邱建算经》中的“百鸡问题”、珠算盘和珠算术等等,均在世界数学发展史上有深远影响。 大约在3000年以前中国已经知道自然数的四则运算,这些运算只是一些结果,被保存在古代的文字和典籍中。乘除的运算规则在后来的“孙子算经”(公元三世纪)内有了详细的记载。中国古代是用筹来计数的,在我们古代人民的计数中,己利用了和我们现在相同的位率,用筹记数的方法是以纵的筹表示单位数、百位数、万位数等;用横的筹表示十位数、千位数等,在运算过程中也很明显的表现出来。“孙子算经”用十六字来表明它,“一从十横,百立千僵,千十相望,万百相当。”
和其他古代国家一样,乘法表的产生在中国也很早。乘法表中国古代叫九九,估计在2500年以前中国已有这个表,在那个时候人们便以九九来代表数学。现在我们还能看到汉代遗留下来的木简(公元前一世纪)上面写有九九的乘法口诀。
现有的史料指出,中国古代数学书“九章算术”(约公元一世纪前后)的分数运算法则是世界上最早的文献,“九章算术”的分数四则运算和现在我们所用的几乎完全一样。
古代学习算术也从量的衡量开始认识分数,“孙子算经”(公元三世纪)和“夏候阳算经”(公元六、七世纪)在论分数之前都开始讲度量衡,“夏侯阳算经”卷上在叙述度量衡后又记着:“十乘加一等,百乘加二等,千乘加三等,万乘加四等;十除退一等,百除退二等,千除退三等,万除退四等。”这种以十的方幂来表示位率无疑地也是中国最早发现的。
小数的记法,元朝(公元十三世纪)是用低一格来表示,如13.56作1356 。在算术中还应该提出由公元三世纪“孙子算经”的物不知数题发展到宋朝秦九韶(公元1247年)的大衍求一术,这就是中国剩余定理,相同的方法欧洲在十九世纪才进行研究。
宋朝杨辉所着的书中(公元1274年)有一个1—300以内的因数表,例如297用“三因加一损一”来代表,就是说297=3×11×9,(11=10十1叫加一,9=10—1叫损一)。杨辉还用“连身加”这名词来说明201—300以内的质数。
(二)属于代数方面的材料
从“九章算术”卷八说明方程以后,在数值代数的领域内中国一直保持了光辉的成就。
“九章算术”方程章首先解释正负术是确切不移的,正象我们现在学习初等代数时从正负数的四则运算学起一样,负数的出现便丰富了数的内容。
我们古代的方程在公元前一世纪的时候已有多元方程组、一元二次方程及不定方程几种。一元二次方程是借用几何图形而得到证明。 不定方程的出现在二千多年前的中国是一个值得重视的课题,这比我们现在所熟知的希腊丢番图方程要早三百多年。具有x3+px2+qx=A和x3+px2=A形式的三次方程,中国在公元七世纪的唐代王孝通“缉古算经”已有记载,用“从开立方除之”而求出数字解答(可惜原解法失传了),不难想象王孝通得到这种解法时的愉快程度,他说谁能改动他着作内的一个字可酬以千金。
十一世纪的贾宪已发明了和霍纳(1786—1837)方法相同的数字方程解法,我们也不能忘记十三世纪中国数学家秦九韶在这方面的伟大贡献。
在世界数学史上对方程的原始记载有着不同的形式,但比较起来不得不推中国天元术的简洁明了。四元术是天元术发展的必然产物。
级数是古老的东西,二千多年前的“周髀算经”和“九章算术”都谈到算术级数和几何级数。十四世纪初中国元代朱世杰的级数计算应给予很高的评价,他的有些工作欧洲在十八、九世纪的着作内才有记录。十一世纪时代,中国已有完备的二项式系数表,并且还有这表的编制方法。
历史文献揭示出在计算中有名的盈不足术是由中国传往欧洲的。
内插法的计算,中国可上溯到六世纪的刘焯,并且七世纪末的僧一行有不等间距的内插法计算。
十四世纪以前,属于代数方面许多问题的研究,中国是先进国家之一。
就是到十八,九世纪由李锐(1773—1817),汪莱(1768—1813)到李善兰(1811—1882),他们在这一方面的研究上也都发表了很多的名着。
(三)属于几何方面的材料
自明朝后期(十六世纪)欧几里得“几何原本”中文译本一部分出版之前,中国的几何早已在独立发展着。应该重视古代的许多工艺品以及建筑工程、水利工程上的成就,其中蕴藏了丰富的几何知识。
中国的几何有悠久的历史,可靠的记录从公元前十五世纪谈起,甲骨文内己有规和矩二个字,规是用来画圆的,矩是用来画方的。
汉代石刻中矩的形状类似现在的直角三角形,大约在公元前二世纪左右,中国已记载了有名的勾股定理(勾股二个字的起源比较迟)。
圆和方的研究在古代中国几何发展中占了重要位置。墨子对圆的定义是:“圆,一中同长也。”—个中心到圆周相等的叫圆,这解释要比欧几里得还早一百多年。
在圆周率的计算上有刘歆(?一23)、张衡(78—139)、刘徽(263)、王蕃(219—257)、祖冲之(429—500)、赵友钦(公元十三世纪)等人,其中刘徽、祖冲之、赵友钦的方法和所得的结果举世闻名。
祖冲之所得的结果π=355/133要比欧洲早一千多年。
在刘徽的“九章算术”注中曾多次显露出他对极限概念的天才。 在平面几何中用直角三角形或正方形和在立体几何中用锥体和长方柱体进行移补,这构成中国古代几何的特点。
中国数学家善于把代数上的成就运用到几何上,而又用几何图形来证明代数,数值代数和直观几何有机的配合起来,在实践中获得良好的效果.
正好说明十八、九世纪中国数学家对割圆连比例的研究和项名达(1789—1850)用割圆连比例求出椭圆周长。这都是继承古代方法加以发挥而得到的(当然吸收外来数学的精华也是必要的)。

(四)属于三角方面的材料
三角学的发生由于测量,首先是天文学的发展而产生了球面三角,中国古代天文学很发达,因为要决定恒星的位置很早就有了球面测量的知识;平面测量术在“周牌算经”内已记载若用矩来测量高深远近。

刘徽的割圆术以半径为单位长求圆内正六边形,十二二边形等的每一边长,这答数是和2sinA的值相符(A是圆心角的一半),以后公元十二世纪赵友钦用圆内正四边形起算也同此理,我们可以从刘徽、赵友钦的计算中得出7.5o、15o、22.5o、30o、45o等的正弦函数值。

在古代历法中有计算二十四个节气的日晷影长,地面上直立一个八尺长的“表”,太阳光对这“表”在地面上的射影由于地球公转而每一个节气的影长都不同,这些影长和“八尺之表”的比,构成一个余切函数表(不过当时还没有这个名称)。

十三世纪的中国天文学家郭守敬(1231—1316)曾发现了球面三角上的三个公式。 现在我们所用三角函数名词:正弦,余弦,正切,余切,正割,余割,这都是我国十六世纪已有的名称,那时再加正矢和余矢二个函数叫做八线。

在十七世纪后期中国数学家梅文鼎(1633—1721)已编了一本平面三角和一本球面三角的书,平面三角的书名叫“平三角举要”,包含下列内容:(1)三角函数的定义;(2)解直角三角形和斜三角形;(3)三角形求积,三角形内容圆和容方;(4)测量。这已经和现代平面三角的内容相差不远,梅文鼎还着书讲到三角上有名的积化和差公式。十八世纪以后,中国还出版了不少三角学方面的书籍。

⑵ 算法的历史

“算法”即算法的大陆中文名称出自《周髀算经》;而英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi,因为al-Khwarizmi在数学上提出了算法这个概念。“算法”原为algorism,意思是阿拉伯数字的运算法则,在18世纪演变为algorithm。欧几里得算法被人们认为是史上第一个算法。 第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解伯努利方程的程序,因此Ada Byron被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机,这个算法未能在巴贝奇分析机上执行。 因为well-defined procere缺少数学上精确的定义,19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了着名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,图灵的思想对算法的发展起到了重要作用。

⑶ 算法的描述、特性以及概念

描述算法的方法有多种,常用的有自然语言、结构化流程图、伪代码和PAD图等,其中最普遍的是流程图。

分类:算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法,厄米变形模型,随机森林算法。

特征:有穷性,算法的有穷性是指算法必须能在执行有限个步骤之后终止;确切性,算法的每一步骤必须有确切的定义;输入项:一个算法有0个或多个输入,;输出项;可行性,算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步,即每个计算步都可以在有限时间内完成。

(3)算法的发展史扩展阅读

算法历史:

“算法”即算法的大陆中文名称出自《周髀算经》;而英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi,al-Khwarizmi在数学上提出了算法这个概念。“算法”,意思是阿拉伯数字的运算法则,在18世纪演变为"algorithm"。

因为巴贝奇未能完成他的巴贝奇分析机,这个算法未能在巴贝奇分析机上执行。 20世纪的英国数学家图灵提出了着名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,图灵的思想对算法的发展起到了重要作用。

⑷ 求排序算法的发展史

对于今天排序技术的探索可以追溯到19世纪,美国人口统计局的Herman Hollerith发明了第一批具有排序装置的制表机,成功地应用到1890年的美国人口普查。关于Hollerith及其制表机的故事,Leon E. Truesdell曾在【The Development of Punch Card Tabulation(Washington: U. S. Bureau of the Census, 1965)】中进行了有趣而详尽地描述。

排序例程曾经是为存储程序式计算机编写的第一个程序,因为它集中体现了计算机潜在的非数值应用。冯·诺伊曼在1954年为了检验EDVAC计算机指令代码的适用性以及评价他所建议的计算机组织的优点,编写了内部归并排序程序,Knuth在【Computing Surveys 2(1970), 247~260】中描述了这个发展细节。

在德国,K. Zuse于1945年独立编写了用于直接插入排序的程序,作为他的Plankalkul语言中线性表操作的例子之一,这一开创性的工作推迟了近30年才发表。

1946年在穆尔学校举行的有关计算的专题讨论会上,John Mauchly作了“排序和整理”的演讲,是第一个公开发表的关于计算机排序的讨论,包括直接插入排序和折半插入排序。

到1952年左右,内部排序的许多方法已在程序设计领域广为流传,但理论上的研究却相对很少。Daniel Goldenberg用Whirlwind计算机编写了5个不同方法的排序程序,分别就最好情况和最坏情况进行了分析。

由Howard B. Demuth于1956年撰写的博士论文【Electronic Data Sorting. Stanford University, 1956】可以说是一篇非常值得关注的论文,因为这篇论文有助于奠定计算复杂性理论的基础。论文利用循环的、线性的以及随机的存储器,考虑了排序问题的3个抽象模型,并对每个模型提出了最优(或接近最优)的方法。Demuth的论文建立了如何把理论同实践相联系的重要思想。

事实上,计算的大多数早期历史都出现在比较难以得到的报告中,因为那时仅有少数人同计算机打交道。有关排序文献的第一次付印是在1955年,用的是三篇重要的综述性文章。第一篇文章是由J. C. Hosken撰写的【Proc. Eastern Joint Computer Conference 8(1955), 39~55】,综述了在计算机上进行排序的方法,以及所有可利用的专用设备,文中的54项参考文献大多数是以厂家的手册为基础的。第二篇文章是由E. H. Friend撰写的【Sorting on Electronic Computer Systems. Journal of the ACM 3(1956), 134~168】是排序技术发展史的一个重要里程碑,Friend对相当多的内部和外部排序算法给出了细致的描述。第三篇文章是由D. W. Davies撰写的【Proc. Inst. Elec. Engineers 103B, Supplement 1(1956), 87~93】。

1962年11月ACM主持召开了一次关于排序的研讨会,在会上宣读的大多数论文都发表在COMMUNICATIONS OF THE ACM1963年5月的刊物上,这些论文是当时技术发展水平的很好代表。

热点内容
c语言计算ab的值 发布:2025-01-01 07:38:52 浏览:629
如何配置好健康保障 发布:2025-01-01 07:38:52 浏览:862
0基础怎样快速学习编程 发布:2025-01-01 07:34:35 浏览:718
安卓的动态效果在哪里 发布:2025-01-01 07:32:49 浏览:114
win10ftp下载 发布:2025-01-01 07:30:31 浏览:814
江西南昌电信ip服务器云服务器 发布:2025-01-01 07:22:44 浏览:997
图形学算法书 发布:2025-01-01 07:20:41 浏览:562
ftp不安全的服务器 发布:2025-01-01 07:19:34 浏览:556
pdf加密了不能复制 发布:2025-01-01 07:12:05 浏览:501
魔兽插件配置码怎么用 发布:2025-01-01 07:11:25 浏览:793