Algorithms
倪培
1 concept of algotithoms:
Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.
We can also view an algorithm as a tool for solving a well-specified computational problem. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship.
2 What is a good algorithm? Take soring for example.
Which algorithm is best for a given application depends on--among other factors-
(1) The number of items to be sorted
(2) The extent to which the items are already somewhat sorted
(3) Possible restrictions on the item values, and the kind of storage device to be used: main memory, disks, or tapes.
3 Correctness and Incorrectness of algorithms
An algorithm is said to be correct if, for every input instance, it halts with the correct output. We say that a correct algorithm solves the given computational problem.
An incorret algorithm might not halt at all on some input instances. or it might halt with an answer other than the desired one.
Contrary to what one might expect, incorrect algorithms can sometimes be useful, if their error rate can be controlled.
Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.
We can also view an algorithm as a tool for solving a well-specified computational problem. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship.
2 What is a good algorithm? Take soring for example.
Which algorithm is best for a given application depends on--among other factors-
(1) The number of items to be sorted
(2) The extent to which the items are already somewhat sorted
(3) Possible restrictions on the item values, and the kind of storage device to be used: main memory, disks, or tapes.
3 Correctness and Incorrectness of algorithms
An algorithm is said to be correct if, for every input instance, it halts with the correct output. We say that a correct algorithm solves the given computational problem.
An incorret algorithm might not halt at all on some input instances. or it might halt with an answer other than the desired one.
Contrary to what one might expect, incorrect algorithms can sometimes be useful, if their error rate can be controlled.
类似资料：