资 源 简 介
并行算法的设计与分析 第3版 陈国良编著 2009年8月出版高清扫描pdf版，值得大家收藏~~另外：并行计算——结构·算法·编程（修订版）—陈国良编著 2003，请参看我的上传列表作者介绍陈国良中国科学技术大学教授,博士生导师,中国科学院院上.首届高等学校国家教学名师。1938年6月生于安微省颍上县1961年毕业于西安交通大学无线电系计算数学与计算仪器专业19811983年在美国普度大学作访问学者,1984年至今曾多次应邀赴东京大学、普度大学、澳大利亚国立大学、新南威尔土大学、昆上兰大学、格里福斯大学、堪萨斯城市大学、衣阿华大学、威斯康星大学、 Maharishi国际大学、香港理T大学、澳门大学、北京大学、國防科技大学等讲学交流。现任中国科学技术大学软件学院院长,国家高性能计算中心(合肥)主任,国际高性能计算(亚洲)常务理事,教育部高等学校计算机基础课程教学指导委员会主仼,中国计算机学会理事和高性能计算专业委员会主任等。曾任教育部高等学校计算机科学与技术教学指导委员会副主仁,安徽省计算机学会理事长,全国自然科学名词审定委员会委员和中国科学技术大学计算机系主任等。陈国良教授长期从事计算机科学技术的研究与教学作。主要研究领域为并行算法和高性能计算及其应用等。先后承担10多项国家863计划、国家攀登计划、国家自然科学基金、国家973计划、教育部博士点基金等科研项目。取得了多项被国内外广泛引用、达国际先进水平的科研成果,发表论文200多篇,出版著作9部、译著5部,参与主编计算机类辞典、词汇5部。曾获国家科技进步二等奖、国家级教学成果二等奖、教育部科技进步一等奖、中国科学院科技进步二等奖和自然科学三等奖、仝国优秀教材一等奖、全国学术著作优秀奖、水利部大禹一等奖、安徽省科技进步二等奖、安徽省教学成果特等奖和一等奖、国家科委高技术研究与发展计划三等奖、教育部科技进步三等奖共19项,并获2001年度“国家863计划15周年先进个人重要贞献奖”。陈国良教授长期以来,围绕着并行算法的教学与研究,逐渐形成了…套完整的“算法理论—算法设计—算法实现一算法应用”的并行算法学科体系,提出了“并行机结构—并行算法一并行编程”一体化的并行计算研究方法,营造了我国并行算法类的教学基地。他先后指导培养研究生I00多名,为我国培养了一批在国内外从事算法研究的高级人才。曾荣获安徽省优秀教师、安徽省劳动模范称号和20υ1年度宝钢教育基金优秀教师特等奖。陈国良教授是我国非数值并行算法研究的学科带头人。他率先创建的我国第一个国家高性能计算中心是我国并行算法研究、环境科学与工程计算软件的重要基地,在学术界和教育界有一定的影响和地位。序言高性能计算机是一个国家经济和科技实力的综合体现,也是促进经济、科技发展,社会进步和国防安全的重要工具,已成为世界各国竞相争夺的战略制高点。一些发达国家纷纷制定战略计划,提出很高目标,投入大量资金,加速研究开发步伐。多年来,随着大规模集成电路技术的不断进步,以多CPU为基础的高性能并行计算机得到了迅速的发展,其高端系统正向百万亿次、千万亿次迈进。我国近十年来,对高性能并行计算的研究开发也给予了很大重视,取得了长足进步和可贵经验,研制出了具有相当水平的并行机系统,但与发达国家相比,差距仍然甚大,在高性能并行计算的应用开发与相关的人才培养教育方面尤显不足。如何使高性能并行机系统深入充分地在国民经济、科研和社会应用的发展中发挥作用,实为当务之急,引起人们的普遍关心。由中国科技大学陈国良教授主编的这套丛书,正适应了我国高性能并行计算研究、开发、应用、教育之需。本丛书由《并行算法的设计与分析》、《并行计算机体系结构》和《并行算法实践》三大部分组成,而以《并行计算—结构·算法·编程》为全丛书之提要。该丛书以并行计算为主题,对并行计算的硬件平台(当代主流并行计算机系统)、并行计算的理论基础(并行算法的设计与分析)和并行计算的软件支撑(并行程序设计)全面系统地展开了讨论,内容丰富,取材新近,具有相当的深度和广度,涵盖了并行计算机体系结构和并行算法的理论、设计和实践的各个方面,是国内外不多见的优秀著作。陈国良教授是国家高性能计算中心(合肥)主任,长期从事并行算法和并行计算机体系结构的研究,本套丛书是作者几十年从事教学与科研工作的结晶,是目前国内该领域内容涵盖最为全面的系列著作。它的出版必将对进一步推动我国并行计算学科的发展与应用推广产生深远的影响。张政2002年8月第3版前言指导思想本着贯彻教育部质量工程,提高教学质量和培养学生创新能力的精神,我们修订了《并行算法的设计与分析》。在计算机科学中,并行算法是比较偏理论的,我们试图通过一些思想新奇、设计精巧和分析严谨的算法,来激发学生的原始创新能力。在学习此课程时,不仅仅是为了学习某些具体算法的设计和分析方法,更重要的是,要了解这些算法产生的背景,源于什么动机,它的来龙去脉,为什么会设计出如此令人惊叹叫绝和鲜为人知以及对学科有着深远影响的经典算法,这才是我们学习此书的初衷。《并行算法的设计与分析》是“并行计算系列丛书”中的一个分册。修订此书时,在对整个丛书的内容统规划和分工的基础上,按照各分册的主题内容,对各分册的内容进行了必要的调整。本分册是并行计算的理论基础部分,所以着重讲述并行算法的设计和分析方法,同时也涉及了并行算法中比较偏理论的一些内容。至于并行算法的实现(硬件平台和软件支撑)就划分给丛书的其他分册了。内容规划《并行算法的设计与分析》的章节内容可大致分为①基础篇:包括绪论(第一章)、设计技术(第二章)、前缀计算(第三章)、排序和选择网络(第四章)。②并行算法篇:包括排序和选择算法(第五章)、分布式算法(第六章)、并行搜索(第七章)选路算法(第八章)、串匹配(第九章)表达式求值(第十章)、上下文无关语言(第|一章)、图论算法(第十五章)、计算几何(第十六章)。③数值并行算法篇:包括矩阵运算(第十二章)、数值计算(第十三章)、快速傅氏变换(第十四章)。④理论篇:包括组合搜索(第十七章)、随机算法(第十八章)、ⅥLSI计算理论(第十九章)、并行计算理论(第二十章)。修订说明此次修订对前一版作了大幅度的修改。重写了第一章(绪论)。第二章设计技术)保留不变。新增加了第三章(前缀计算),改写了原书第三章的第34节(AKS网络)并重新编号为第四章排序和选择网络)。整合了原书第四章和第五章的第5.1节及5.2节形成了第五章(排序和选择算法)。将原书第五章的第5.3节至第5.6节与新增加的“构造生成树算法”和“环上选举算法”合在一起形成了第六章(分布式算法)。第七章(并行搜索)保留不变。第八章(选路算法)中新增加了第8.5.2节(阻塞网络中的自选路算法)和第8.5.3节(可重排网络中的中级选路算法)。重写了第九章(串匹配)。第十章(表达式求值)中新增加了第10.53节(有限自动机确定化并行算法)和第10.5.4节(确定自动机的最小化并行算法)。第十一章(上下文无关语言)中新增加了第11.3节(任意上下文无关语言的并行语法分析)。第十二章(矩阵运算)中的第12.1.4节的内容替换为“SIMD-CC模型上的矩阵转置”。第十三章(数值计算)中新增加了第13.1节(三对角方程组的求解)。第十四章(快速傅氏变‖第3版前言换)和第十五章(图论算法)保留不变。第十六章中,删去了图像分析的内容,加强了计算几何的内容,将原书第16.3节、16.4节和16.5节整合并加以补充成为新的第16.1节(判定问题),保留原书第16.6节(构造问题),新增加了第16.3节( Voronoi图问题)和笫16.4节(平面点集的三角剖分)。将原书第七章的第71节和第73节的内容压缩后放入第十七章(组合搜索)的第17.1节,第7.2节和第7.4节的内容压缩后放入第17.2节,删去了原书第17.4节,新增加了第17.5节(动态规划)。第十八章(随机算法)和第十九章(ⅥSI计算理论)保留不变。改写了原书第二十章中第20.5节的部分内容。此外,对全书中的专业术语都加注了英文名,这样书末附录C就变成了“专业术语中英文对照表及索引”。同样,书末的附录B也作了相应的修改与补充。最后,对全书的某些排版错误也进行了纠正,但有些错误可能仍然存在,欢迎读者批评指正。使用指南本书内容相当丰富,在教学中由于受学时的限制,所以只能讲授最最基本的内容。若以60学时为限,则建议讲授章节及其学时分配为:第一章:4学时,第二章:4学时,第三章:3学时,第四章:3学时,第五章:4学时,第六章:3学时,第八章:3学时,第九章4学时,第十二章:4学时,第十三章:3学时,第十四章:3学时,第十五章:4学时,第十六章:3学时,第十七章:4学时,第十八章4学时,第十九章:4学时,第二十章3学时。具体讲授时,请教师按照各章前的讲授要点,根据不同的专业要求和听课对象,自行选取和调整之感谢本次修订,邀请了曾经听取我讲授此课,现在已工作在教学和科研第一线具有丰富实践经验的几位老师及几位研究生参加了有关章节的修订工作:他们是徐云教授和赵裕众同学(第三章、第9.1.4节第12.1.4节和第131节),黄刘生教授和方维同学(第六章),钟诚教授(第九章),孙玉强教授(第10.5.3节、10.54节和第11.3节),裴继红教授和董兰芳教授(第十六章),孙广中老师(第十七章)和吕敏老师(第3.4节和第20.5节)等。特别是,孙广中老师领导国家高性能计算中心(合肥)的吕强、方维吴超、袁晶、闾明等同学完成了书稿的电子文档,作了全书的专业术语中英文对照表及索引(附录C),并对书末的附录B进行了修改和补充。对于他们的辛勤劳动,作者尤为感谢。另外,我们也非常感谢国家自然基金委对本书出版工作的大力支持和资助。尽管我们尽了最大努力修订了此书,但限于业务能力和时间仓促,仍有不少章节内容尚待进一步修订,作者为此深感歉意。陈国良中国科学技术大学2008年11月17日修订版前言并行算法类的教学体系20世纪80年代初期,中国科学技术大学就开始了并行算法的研究和教学工作。20年来我们围绕着并行算法的教学,相继开设了如下图所示的以并行算法的设计与分析(包括并行排序和选择算法、VSI计算理论与并行算法、并行图论算法、分布式算法等)为核心的并行计算机体系结构、并行算法编程实践、并行计算、高性能计算导论、可计算性与计算复杂性和算法研究的数学甚础等11门课程,逐渐形成了一套完整的并行算法类的教学体系。教学对象从计算机专业的研究生扩大到本科生,从计算机专业拓宽到非计算机专业,从而带动了教材建设,促进了学科发展,壮大了师资队伍,完善了教学环节。与此同时也逐渐形成了我国并行算法研究的一套完整的学科体系,即算法理论一算法设计与分析一算法实现一算法应用基础。专业面向可计算性与算法研究的博计计算复杂性数学基础士算生机命中香斯命e带命命司中命中中手申省啦中啦b啦算法理论算法设计与分析算法实现算法应用基础开行和S算理轮并行图论算法分布式算法_选择算法并行算法类课程教学网站并行算法的设计与分折并行算法类课程实践面向计算机专业硕士生并行算法并行计算机编程实践体系结构并行计算或计算面向计科算学机的专高性能计算导论研业究生本科生修订说明近几年来由于各式各样的并行计算机,特别是PC机群的普遍使用,广大读者对学习并行算法的热忱也日益高涨。《并行算法的设计与分析》自出版到现在已有8l修订版前言年之久,此书早已脱销,且部分内容也待修订。为了尽快满足全国广大读者的急需以及考虑到1999年曾出版了《并行计算——结构·算法·编程》一书(此书有些章节已是本书所要修订的内容),所以本次只对原并行算法的设计与分析作了稍许的修订。具体修订部分包括:①在每一章开头都补充了木章“讲授要点”,这是从作者多年讲授并行算法课程中归纳出来的,仅供讲课老师参考;②重新改写了第一章,对当今主流的并行计算机的体系结构,更实用的并行计算模型以及并行算法的编程实现模型等均补充了新内容;③在第十八章中补充了“随机算法的设计方法”一小节(18.1.3),对随机算法的最新设计思路、方法和技术作了总结;④为了反映学科的新进展,有些章节中补充了新的参考文献,以期读者跟踪阅读;⑤附录B中增加了第三章比较器网络中算法复杂度一览表;⑥增加了专业术语和有关名词的索引;⑦对全书的错误进行了纠正,但有些错误可能仍然存在。修订教材的使用方法《并行算法的设计与分析》经过长期的教学使用,对原来建议的讲授章节及学时分配,重新调整如下建议讲授章节供参考的学时分配第一章:1.1,1.2,1.4第二章:2.1~2.5,2.7第三章:3.1,3.2第四章:4.1,4.2,4.5,4.7第五章:5.1,5.3第六章:6.2,6.5,6.6第八章:8.2,8.3,8.4第九章:9.1~9.3第十二章:12.1,12.2,12.4第十三章:13.1,13.3,13.4第十四章:14.1,14.3第十五章:15.1,15.2,15.3,15.4第十六章:16.1,16.4,16.6第十七章:17.1,17.2,17.3,17.544242244443434433第十八章:18.1,18.2,18.5,18.6第十九章:19.1,19.3,19.5第二十章:20.1,20.2,20.5
