Chapter 1 The role of algorithms in computing 算法在编程中的作用
1.1 What are algorithms?
-
Algorithms is any well-defined computational procedure. 算法是任意一个定义明确的可计算过程。
-
well-defined: know what to do each step; always halts(stop) with correct answer. -
efficiency: good or bad? -
Algorithm is a tool for solving a well-specified(定义良好的) computational problem.
The charactieristics of the algorithm:
- Output: at least one.
- Correct: An algorithm is said to be correct if, for every input instance, it halts with the correct output.
- Feasible(可行性)
- Practical(实际可行)
Incorrect algotithm: might not halt at all on some input instances, or might halt with an answer other than the desired one can sometimes be useful (if error rate can be controlled)
1.1.1 What kinds of problems are solved by algotithms
- Genome Project 基因组计划
- Internet
- finding good routes; search engine
- Electronic commerce 电子商务
- Manufacturing(制造商) and other commercial settings(environment)
- Finding the shortest path from one vertex to another
- Matrices product
1.1.2 Data structures
Algorithms + Data structures = Program