We can give a Simple informal definition of an algorithm as "a set of instructions for solving a problem" and we illustrated this definition with a recipe, directions to a friend's house, and instructions for changing the oil in a car engine. You also created your own algorithm for putting letters and numbers in order. While these simple algorithms are fine for us, they are much too ambiguous for a computer. In order for an algorithm to be applicable to a computer, it must have certain characteristics.
We will specify these characteristics in our formal definition of an algorithm
We will specify these characteristics in our formal definition of an algorithm
We can identify five important characteristics of algorithms.
1. Algorithms are well-ordered.
2. Algorithms have unambiguous operations.
3. Algorithms have effectively computable operations.
4. Algorithms produce a result.
5. Algorithms halt in a finite amount of time.
Algorithms are well-ordered
An algorithm is a collection of operations or instructions. We must know the correct order in which to execute the instructions. If the order is unclear, we may perform the wrong instruction or we may be uncertain which instruction should be performed next. This characteristic is especially important for computers. A computer can only execute an algorithm if it knows the exact order of steps to perform.
Algorithms have unambiguous operations
Each operation in an algorithm must be sufficiently clear so that it does not need to be simplified. Given a list of numbers, you can easily order them from largest to smallest with the simple instruction "Sort these numbers." A computer, however, needs more detail to sort numbers. It must be told to search for the smallest number, how to find the smallest number, how to compare numbers together, etc. The operation "Sort these numbers" is ambiguous to a computer because the computer has no basic operations for sorting. Basic operations used for writing algorithms are known as primitive operations or primitives. When an algorithm is written in computer primitives, then the algorithm is unambiguous and the computer can execute it.
Algorithms have effectively computable operations
Each operation in an algorithm must be doable, that is, the operation must be something that is possible to do. Suppose you are giving an algorithm for planting a garden where the first step instructed you to remove all large stones from the soil. This instruction may not be doable if there is a four ton rock buried just below ground level. For computers, many mathematical operations such as division by zero or finding the square root of a negative number are also impossible. These operations are not effectively computable so they cannot be used in writing algorithms.
Algorithms produce a result
In our simple definition of an algorithm, we stated that an algorithm is a set of instructions for solving a problem. Unless an algorithm produces some result, we can never be certain whether our solution is correct. Have you ever given a command to a computer and discovered that nothing changed? What was your response? You probably thought that the computer was malfunctioning because your command did not produce any type of result. Without some visible change, you have no way of determining the effect of your command. The same is true with algorithms. Only algorithms which produce results can be verified as either right or wrong.
Algorithms halt in a finite amount of time
Algorithms should be composed of a finite number of operations and they should complete their execution in a finite amount of time. Suppose we wanted to write an algorithm to print all the integers greater than 1. Our steps might look something like this:
1. Print the number 2.2. Print the number 3.
3. Print the number 4.
.
.
.
While our algorithm seems to be pretty clear, we have two problems. First, the algorithm must have an infinite number of steps because there are an infinite number of integers greater than one. Second, the algorithm will run forever trying to count to infinity. These problems violate our definition that an algorithm must halt in a finite amount of time. Every algorithm must reach some operation that tells it to stop.
" There is no universally accepted breakdown for the various types of algorithms, there are common classes that algorithms are frequently agreed to belong to. Among these are:"
• Dynamic Programming Algorithms: This class remembers older results and attempts to use this to speed the process of finding new results.
• Greedy Algorithms: Greedy algorithms attempt not only to find a solution, but to find the ideal solution to any given problem.
• Brute Force Algorithms: The brute force approach starts at some random point and iterates through every possibility until it finds the solution.
• Branch and Bound Algorithms: Branch and bound algorithms form a tree of sub problems to the primary problem, following each branch until it is either solved or lumped in with another branch.
• Randomized Algorithms: This class includes any algorithm that uses a random number at any point during its process.
• Backtracking Algorithms: Backtracking algorithms test for a solution, if one is found the algorithm has solved, if not it recurs once and tests again, continuing until a solution is found.
• Simple Recursive Algorithms: This type of algorithm goes for a direct solution immediately, and then backtracks to find a simpler solution.
• Divide and Conquer Algorithms: A divide and conquer algorithm is similar to a branch and bound algorithm, except it uses the backtracking method of recurring in tandem with dividing a problem into sub problems
No comments:
Post a Comment