Discuss the principal operations involve in designing non deterministic algorithms
Answers
Answered by
0
The influence of Richard Bellman is seen in algorithms throughout the
computer science literature. Bellman’s principle of optimality has been used
to develop highly efficient dynamic programming solutions to many important
and difficult problems. The paradigm is now well entrenched as one of
the most successful algorithm design tools employed by computer scientists.
The optimality principle was given a broad and general statement by
Bellman [23, making it applicable to problems of diverse types. Since computer
programs are often employed to implement solutions based on the
principle of optimality, Bellman’s impact on computing in general has been
immense. In this paper we wish to focus in particular on the influence of
Bellman’s work on the area of computer science known as algorithm design
and analysis. A primary goal of algorithm design and analysis is to discover
theoretical properties of classes of algorithms (e.g., how efficient they are,
when they are applicable) and thus learn how to better apply the
algorithms to new problems.
From the perspective of algorithm design and analysis, combinatorial
optimization problems form the class of problems on which the principle of
optimality has had its greatest impact. Problem decomposition is a basic
technique for attacking problems of this type-the solution to a large
problem is obtained by combining solutions to smaller subproblems. The
trick of this approach, of course, is to define an efficient decomposition
procedure which assures that combining optimal solutions to subproblems
will result in an optimal solution to the larger problem. As a standard
course of action, computer scientists attempt to define a decomposition
97
0022-247X/86 $3.00
Copyngh, , 1986 by Academrc Press. Inc
All n&his 01 reproductton m any form re%vcd
98 PAULHELMAN
based on Bellman’s principle of optimality. Problem decompositions based
on the principle of optimality not only are at the heart of dynamic
programming algorithms, but are also integral parts of the strategies of
other important classes of algorithms, such as branch and bound.
The remainder of this paper is divided into three sections. Each section
attempts to illustrate the manner in which Bellman’s principle of optimality
has influenced researchers addressing issues arising in one particular area
of algorithm design and analysis. Section 2 samples several problems with
important applications directly in computer science. These problems have
been successfully solved by algorithms based on the principle of optimality.
Section 3 considers the class of NP-complete problems-a large class of
problems for which it is strongly believed that no efficient (i.e., subexponential
time) algorithms exist. We discuss how, for some of these
problems, the principle of optimality has been used to construct algorithms
which are acceptable in certain situations. The final section discusses how
the principle of optimality has been incorporated as a key component of
several formal models of optimization algorithms. We summarize some
significant theoretical results obtained from these models concerning the
applicability and efficiency of dynamic programming.
Answered by
0
Answer:
In computer science, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run.
Similar questions