《算法设计与分析_基础篇(英文)》由会员分享，可在线阅读，更多相关《算法设计与分析_基础篇(英文)（11页珍藏版）》请在金锄头文库上搜索。
1、Design and Analysis of Algorithms - Chapter 1,1,Algorithm,An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.,Design and Analysis of Algorithms - Chapter 1,2,Historical Perspective,Eu
2、clids algorithm for finding the greatest common divisorMuhammad ibn Musa al-Khwarizmi 9th century mathematician www.lib.virginia.edu/science/parshall/khwariz.html,Design and Analysis of Algorithms - Chapter 1,3,Notion of algorithm,“computer”,Algorithmic solution,problem,algorithm,input,output,Design
3、 and Analysis of Algorithms - Chapter 1,4,Example of computational problem: sorting,Statement of problem: Input: A sequence of n numbers Output: A reordering of the input sequence so that ai aj whenever i Algorithms: Selection sort Insertion sort Merge sort (many others),Design and Analysis of Algor
4、ithms - Chapter 1,5,Selection Sort,Input: array a1,anOutput: array a sorted in non-decreasing orderAlgorithm:for i=1 to nswap ai with smallest of ai,an,see also pseudocode, section 3.1,Design and Analysis of Algorithms - Chapter 1,6,Some Well-known Computational Problems,Sorting Searching Shortest p
5、aths in a graph Minimum spanning tree Primality testing Traveling salesman problem Knapsack problem Chess Towers of Hanoi Program termination,Design and Analysis of Algorithms - Chapter 1,7,Basic Issues Related to Algorithms,How to design algorithmsHow to express algorithmsProving correctnessEfficie
6、ncy Theoretical analysisEmpirical analysisOptimality,Design and Analysis of Algorithms - Chapter 1,8,Algorithm design strategies,Brute forceDivide and conquerDecrease and conquerTransform and conquer,Greedy approachDynamic programmingBacktracking and Branch and boundSpace and time tradeoffs,Design a
7、nd Analysis of Algorithms - Chapter 1,9,Analysis of Algorithms,How good is the algorithm? Correctness Time efficiency Space efficiencyDoes there exist a better algorithm? Lower bounds Optimality,Design and Analysis of Algorithms - Chapter 1,10,What is an algorithm?,Recipe, process, method, technique
8、, procedure, routine, with following requirements: Finiteness terminates after a finite number of steps Definiteness rigorously and unambiguously specified Input valid inputs are clearly specified Output can be proved to produce the correct output given a valid input Effectiveness steps are sufficiently simple and basic,Design and Analysis of Algorithms - Chapter 1,11,Why study algorithms?,Theoretical importancethe core of computer sciencePractical importanceA practitioners toolkit of known algorithmsFramework for designing and analyzing algorithms for new problems,
