Just as a cook learns both general techniques such as how to sauté or how to reduce a sauce and a repertoire of specific recipes, a student of computer science learns both general problem-solving principles and the details of common algorithms. These include a variety of algorithms for organizing data , for numeric problems, and for the manipulation of data structures. A working programmer faced with a new task first tries to think of familiar algorithms that might be applicable to the current problem, perhaps with some adaptation. For example, since a variety of well-tested and well-understood sorting algorithms have been developed, a programmer is likely to apply an existing algorithm to a sorting problem rather than attempt to come up with something entirely new. Indeed, for most widely used programming languages there are packages of modules or procedures that implement commonly needed data structures and algorithms.
If a problem requires the development of a new algorithm, the designer will first attempt to determine whether the problem can, at least in theory, be solved . Some kinds of problems have been shown to have no guaranteed answer. If a new algorithm seems feasible, principles found to be effective in the past will be employed, such as breaking complex problems algorithm down into component parts or building up from the simplest case to generate a solution. For example, the merge-sort algorithm divides the data to be sorted into successively smaller portions until they are sorted, and then merges the sorted portions back together. Another important aspect of algorithm design is choosing an appropriate way to organize the data.
For example, a sorting algorithm that uses a branching structure would probably use a data structure that implements the nodes of a tree and the operations for adding, deleting, or moving them .Once the new algorithm has been outlined, it is often desirable to demonstrate that it will work for any suitable data. Mathematical techniques such as the finding and proving of loop invariants can be used to demonstrate the correctness of the implementation of the algorithm.
Practical Considerations:-
It is not enough that an algorithm be reliable and correct, it must also be accurate and efficient enough for its intended use. A numerical algorithm that accumulates too much error through rounding or truncation of intermediate results may not be accurate enough for a scientific application. An algorithm that works by successive approximation or convergence on an answer may require too many iterations even for today’s fast computers, or may consume too much of other computing resources such as memory. On the other hand, as computers become more and more powerful and processors are combined to create more powerful supercomputers, algorithms that were previously considered impracticable might be reconsidered. Code profiling and techniques for creating more efficient code can help in some cases. It is also necessary to keep in mind special cases where an otherwise efficient algorithm becomes much less efficient.
Sometimes an exact solution cannot be mathematically guaranteed or would take too much time and resources to calculate, but an approximate solution is acceptable. A socalled “greedy algorithm” can proceed in stages, testing at each stage whether the solution is “good enough.” Another approach is to use an algorithm that can produce a reasonable if not optimal solution. For example, if a group of tasks must be apportioned among several people so that all tasks are completed in the shortest possible time, the time needed to find an exact solution rises exponentially with the number of workers and tasks.
But an algorithm that first sorts the tasks by decreasing length and then distributes them among the workers by “dealing” them one at a time like cards at a bridge table will, as demonstrated by Ron Graham, give an allocation guaranteed to be within 4/3 of the optimal result—quite suitable for most applications.An interesting approach to optimizing the solution to a problem is allowing a number of separate programs to “compete,” with those showing the best performance surviving and exchanging pieces of code with other successful programs. This of course mimics evolution by natural selection in the biological world.
No comments:
Post a Comment