Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [ 111 ] [112] [113] [114] [115] [116] [117]

6.3. Вероятностные алгоритмы

Центральная предельная теорема (теорема 6.3.3) позволяет нам аппроксимировать ряд дискретных и непрерывных распределений стандартным нормальным распределением N{0, 1). Некоторые примеры можно найти у Росса [81]. Эта аппроксимация часто позволяет значительно упростить вычисления.

В книге Кнута [57] очень детально рассмотрены генераторы случайных чисел. В ней обсуждается выбор параметров алгоритма LCM и дан широкий ассортимент статистических тестов для проверки «случайности» последовательности случайных чисел. Многих читателей книги Кнута может также заинтересовать обсуждение вопроса, что такое случайная последовательность? (Этот материал несколько труден, но по крайней мере вы получите некоторое представление об усилиях, которые необходимо приложить для ответа на этот вопрос.)

Книга Кнута [57], а также работа [47] могут быть использованы при дальнейшем изучении теории и примеров, относящихся к вероятностным алгоритмам. Две отличающихся точки зрения можно найти в статьях Гренандера и Нойтса в сборнике [61].

Статистическая оценка производительности вычислительных систем привлекала до недавнего времени заметное внимание. Интересующиеся читатели могут обратиться к книгам [31], [47]. Для чтения этих книг необходимо иметь некоторое представление об организации вычислительных машин и операционных систем.

Численная оценка сложности вычислений и NP-полные задачи

Существует две важные темы, которых мы не смогли коснуться, так как их включение потребовало бы увеличения объема книги и некоторых сведений из дополнительного курса. удовлетворимся простым их упоминанием и дадим несколько библиографических ссылок.

Предмет численной или аналитической оценки вычислительной сложности относится к проектированию и анализу, численных алгоритмов. Сюда относятся алгоритмы матричных операций, целочисленная арифметика и арифметика многочленов, решение алгебраических и дифференциальных уравнений, быстрые преобразования Фурье и т. д. Интересующийся читатель может обратиться к работам [57], [91], [1] и к статье Трауба в сборнике [61]. Краткий и весьма легкий для чтения обзор содержится в [90].

Было показано, что комбинаторные задачи, относящиеся к широкому классу, включающему задачу о коммивояжере, и общие задачи планирования и упаковки (см. разд. 3.2) - все эквивалентны в том смысле, что либо все они разрешимы, либо ни одна из них не разрешима полиномиальными алгоритмами. Таким образом, если бы удалось показать, что хотя бы для одной из этих задач не может существовать алгоритма решения, имеющего в худшем случае полиномиаль-



ную трудоемкость, то таких алгоритмов не должно существовать и для всех остальных задач этого класса. Наоборот, если можно найти хотя бы для одной из таких задач алгоритм, имеющий в худшем случае полиномиальную трудоемкость, то его можно было бы применить при построении полиномиальных алгоритмов для остальных задач. Задачи из этого класса называются Nр-полными. Наиболее элементарной работой по этому вопросу, по-видт-юму, является [51]. Для более серьезного изучения можно порекомендовать [1].

1. Aho, А. V., J. E.Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, IVIass., 1974(VAM).

2. Barron, D. W., Recursion Techniques in Programming, American Elsevier, New York,

1968(IM). •

. 3, Basili, V. R., C. K. Mesztenyi, and W. C. Reinboldt, "FGRAAL: Fortran Extended Graph Algorithmic Language," Tech. Kept. 179, Computer Science Center, University of Maryland, 1972(1); see also Tech. Rept. 225,1973(1).

4. Belady, L. A., "A Study of Replacement Algorithms for a Virtual Storage

Computer," IBM Syst. J., 5: 78-101 (1966)(1).

5. Eellmore, M., and- J. C. Malone, "Pathology of Traveling Salesman Sublour

Elimination Algorithms," Oper. Res., 19: 278-307 (1971)(AM).

6.-, and G. L. Nemhauser, "The Traveling Salesman Problem: A Survey," Open

Res., 16: БЗ&-558 (1968)(1М).

7. Eerge, C, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973(AM).

8. Berztiss, A. Т., Data Structures; Theory and Practice, Academic, New York, 1971 (IM).

3. Busacker, R. G., and T. L. Saaty, Finite Graphs and Networks, McGraw-Hill, New

York, 1965(IM).

10. Chase, S. M., "GASP-Graph Algorithm Software Package," Q. Tech. Prog. Rept.

(Oct.-Dec. 1969), Department of Computer Science, University of Illinois (I). ll.Coffman, E. G., and P. J. Denning, Operating Systems Theory, Prentice-Hall,

Englewood Cliffs, N.J., 1?73(AM). .

M.Comput. Surv., 6: (1974)(E).

13. Cornell, D. G., "Graph Isomorphism," doctoral .thesis, Department of Computer Science, University of Toronto. Canada, 1968(AM); see also Tech. Rept. 18, Department of Computer Science, University of Toronto, 1970.

14,--, and C. C. Gotlieb, "An Efficient Algorithm for Graph Isomorphism,"/. ACM,

17:51-64 (1970)(АМ).

IS.Cox, D. R., and D. V. Hinkley, Theoretical Statistics, Chapman and Hall, London, 1974(AM).

16.Dahl, O., E. Dijkstra, and C. A- R. Hoare, Structured Programming, Academic, New

York, 1972(1). 17.Шата<!0п, 19: (1973)(E).

18.DeGroot, M. H., Optimal Statistical Decisions, McGraw-Hill, New York, 1970(VAM).

19.Denning,>. J., "Virtual Memory," Comput. Surv., 2: 153-189 (1970)(l).

20.Peo, N., Graph Theory with Applications to Engineering and Computer Science,

Prentice-Hall,-Englewood Cliffs, N.J., 1974(IM). ,21. Dijkstra, E. W., "A Note on Two Problems in Connexion with Graphs," Numer.

Math.. 1: 269-271 (1959)(IM). 22.Edmonds, J.. "Paths, Trees, and Flowers." Can. J. Math., 17:449-467 (1965)(AM). • 23. Epstein, R. A., The Theory of Gambling and Statistical Logic, Academic, New York, 1. ,iS67(AM).

24. Even. S., Algorithmic Combinatorics, Macmillan. New York. 1973(IM).



25. Feigenbaum. E. A., and J. Feldman, Computers and Thought, McGraw-Hill. New

York. 1963(1).

26. Feller, W., Ли Introduction to Probability theory and Its Applications, 2d ed., vol.

1. Wiley, New York. 1957(IM).

27. Ferguson. L., "PROFILE, A CDC Fortran Profiling Program," Tech. Rept. 75-6.

Department of Applied Mathematics and Computer Science, University of Virginia; 1975(1).

28.Fishman, G. S., Concepts and Methods in Discrete Event Digital Simulation, Wiley,

New York. 1973(IM)., ,

29. Frank, H., and I. T. Friscb, Communications, Transmission, and Transportation

Nefworfo,-Addison-Wesley, Reading, Mass., 1971{AM). SO.Freiberger, W., and U. Grenander, A Short Course in Computational Probability and

Stafisficsr Springer-Verlag. New York; 1971 (VAM).. 31.Freiberger, W. (ed.). Statistical Computer Performance Evaluation, Academic, New

York, 1972(A).

32.Freudenthal. H., Probability and Statistics, Elsevier. Amsterdam. 1965(IM). * 33. Froberg, C.E., Introduction to Numerical Analysis, 2d ed., Addison-Wesley, Reading. Mass,. 1969(AM).

34.Fulkerson, D. R., "Flow Networks and Combinatorial Operations Research," Anu

Math, Mon., 73:115-136 {1966)(IM). 35.Gale, D.. "The Jeep Once More or Jeeper by the Dozen," Am. Math. Moji., Tt:

493-501 (1970)(IM).

36. Gardner, M., The 2nd Scientific American Book of Mathematical Puzzles and

Diversions, Simon and Schuster. New York, 1961 (EM). 37.-, The Unexpected Hanging and Other Mathematical Diversions, Simon and

Schuster, New York, 1969(EM). 38.Garfinkel. R. S., and G. L. Nemhauser, Integer Programming, Wiley, New York,

1972(AM).

39. Golomb, S. W.. and L D. Baumert. "Backtrack Programming,"/. ACM. 12:516-524 (1965)(I).

40.Gordon, G., System Simulation. Prentice-Hall, Englewood Cliffs, N.J., 1969(1). i 41. Graham, R. L, "Bounds on Multiprocessing Anomalies and Related Packing

Algorithms." in Proc. Spring Joint Comput. Conf., 205-217 (1972)(IM). 42.Gunderman, R. E., "A Glimpse into Program Maintenance," Datamation.ЛS: 99-101

(1973)(E).

43.Hamming, R. VJ.,-Introduction to Applied Numerical Analysis, McGraw-HilF, New York. 1971 (IM).

44. Hart, R., "HINT: A Graph Processing Language," Res. Rept., Computer Institute for Social Science Research, Michigan State University, 1969(1).

4Б. Hastings, N. A. J., Dynamic Programming, Crane, Russak, New York, 1973(IM).

АБ. Held, M., and R. M. Karp.- "The Traveling Salesman Problem and Minimum ) Spanning Trees, Part 11." Мй/fc. Prog.. 1: 6-25 (1971)(AM).

47. Heilerman, H., and T. F. Conroy Computer System Рефгтапсе, McGraw-Hill, New York. 1975(AM}.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [ 111 ] [112] [113] [114] [115] [116] [117]

0.0013