Рейтинг@Mail.ru
Rambler's Top100




Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

реферат на тему: Алгоритмы

скачать реферат

room assignment, once it is discovered, can easily be exhibited. Of course, a solution could be found by exhaustive search, albeit inefficiently. With luck a suitable assignment, if there is one, can be guessed quickly. Map coloring is a problem in the class NP that concerns mathematicians more than it does cartographers. The question is whether the countries on a given map can be colored with a given number of colors so that no two countries that share a border have the same color. It is easy to find out if a map can be colored with two colors, it can be if there are no places on the map where an odd number of countries meet at one point. It is even easier to tell if a map can be colored with four colors; indeed, there is no need even to look at the map, since Kenneth Appel and Wolfgang Haken of the University of Illinois proved in 1975 that four colours suffice for any map. Surprisingly, however, no efficient algorithm is known for determining whether three colors are enough for a given map. The problem is in the class NP, since a correctly colored map can-serve to certify a yes answer. Map coloring can be regarded as a special case of another problem called graph coloring. Any map can be converted into a graph by reducing each country to a point and drawing a line between two points if the corresponding countries share a border. Coloring the graph is then equivalent to coloring the map, subject to the rule that two points connected by a line cannot have the same color. Graph coloring, however, is a more general problem, with applications outside graph theory. For example, a graph can represent the scheduling of work in a factory. Each point of the graph stands for some job to be done, and two points are connected by a line, if the jobs cannot be done concurrently, perhaps because they require the same piece of machinery. A coloring of the graph with three colors would then supply a schedule dividing the work of the factory into three shifts. Like map coloring, the graph-coloring problem is in the class NP. It often happens that if one problem can be solved efficiently, so can many others. For example, if an efficient algorithm could be found for the problem of graph coloring, it could be applied with only minor modifications to the problems of map coloring and factory scheduling. Map coloring and factory scheduling are therefore said to be efficiently reducible to graph coloring. In the past several years it has become apparent that some of the problems in the class NP have a remarkable property: all the problems in NP are efficiently reducible to them. These elite problems within the class NP are called NP-complete. If any one of them has an efficient algorithm, then every problem in NP can be solved efficiently. The first proof that a problem is NP-complete was presented in 1971 by Stephen A. Cook of the University of Toronto. His reasoning follows a path essentially parallel to the path of Turing's earlier work on mathematical machines and their relation to problems of formal logic. Cook stated his proof in terms of the prepositional calculus, the formal language in which separate logical statements, which individually may be either true or false, are joined together by the lexical elements "and," "or" and "not." In general a sentence in the propositional calculus can be shown to be either true or false depending on which of its component statements are assumed to be true or false. Certain sentences, however, cannot
Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ




be true under any interpretation because they are self-contradictory. Sentences that cannot be made true are said to be unsatisfactory. Cook employed the propositional calculus to describe the operation of the nondeterministic Turing machines, the mechanized guessing devices essential to the definition of the class NP. He showed that the calculations of any such machine can be described succinctly by sentences of the propositional calculus. When the machine is given a yes insfance of a problem in NP, its operation is described by a satisfiable sentence, whereas the operation of a machine given a no instance is described by a sentence that cannot be satisfied. It follows from Cook's proof that if one could efficiently determine whether a sentence in the propositional calculus can be satisfied, one could also determine efficiently in advance whether the problem presented to a nondeterministic Turing machine will be answered yes or no. Since the problems in the class NP are by definition all those that can be solved by nondeterministic Turing machines, one would then have an efficient method for solving all those problems. The catch, of course, is that there is no known efficient method of determining whether a sentence in the propositional calculus can be satisfied. Cook's argument states in essence that the propositional calculus is a universal language for describing problems in the class NP. Every instance of such a problem corresponds to a sentence in that language, and if the sentence is satisfiable, the instance has a yes answer. Many other problems have since been shown to be NP-complete because the satisfiability problem can efficiently be reduced to them. Hamilton's problem, the problem of matching groups of three roommates and the problem of coloring graphs with three colors are all NP-complete. The first to point out the broad applicability of this theory was Richard M. Karp of the University of California at Berkeley. Similar investigations were independently conducted by the Russian mathematician P. A. Levin. Since NP-complete problems capture the difficulty of all other problems in NP, it is widely thought today that all NP-complete problems are computationally intractable. A proof that a problem is NP-complete is usually considered a strong argument for abandoning further efforts to devise an efficient algorithm for its solution. Even the assumption that all NP-complete problems are intractable would not settle all questions about the class NP. In addition to the mystery of the NP-complete problems there is an even more obscure area: problems in NP for which no efficient algorithms are known but which have not been proved to be NP-complete either. The problem of composite numbers is one of these. Not all problems that can be solved by a computer are of the yes-or-no. type. Another common type is the optimization problem. For example, suppose one is given the positions of some cities on a map and asked to find the shortest possible railroad network connecting them. In one version of this problem one is allowed to lay down a straight section of track between any two cities, but one is not allowed to install isolated junction points; tracks can be joined only at cities. One property of the solution to this problem is immediately apparent: the optimum network can never include a closed circuit, because if it did, the network could be made shorter simply by omitting one link in the circuit. Thus the best net-work always

скачать реферат
первая   ... 2 3 4 5 6

Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

Внимание! Студенческий отдых и мегатусовка после сессии!


Обратная связь.

IsraLux отзывы Израиль отзывы