Richard Bellman’s contributions to computer science. (English) Zbl 0602.01014
The paper is devoted to the review of Richard Bellman’s contributions to computer science. He was an early advocate of computers. The review is presented from the standpoint of a computer scientist. It is stated that Bellman’s contributions have direct relevance to computer software and programming problems (especially dynamic programming). The author first discusses Bellman’s personal contributions and then reviews many of the ways in which his work has been extended.
Reviewer: R.Murawski
MSC:
| 01A70 | Biographies, obituaries, personalia, bibliographies |
| 01A65 | Development of contemporary mathematics |
| 68-03 | History of computer science |
Keywords:
dynamic programmingBiographic References:
Bellman, R.References:
| [1] | Bellman, Richard, List of publications, IEEE Trans. Automat. Control, AC-26, 1213-1223 (1981) |
| [2] | Bellman, R., Dynamic Programming (1957), Princeton Univ. Press: Princeton Univ. Press Princeton, N. J · Zbl 0077.13605 |
| [3] | Bellman, R.; Dreyfuss, S., Applied Dynamic Programming (1962), Princeton Univ. Press: Princeton Univ. Press Princeton, N. J · Zbl 0106.34901 |
| [4] | Bellman, R., Eye of the Hurricane: An Autobiography (1984), World Scientific: World Scientific Singapore · Zbl 0566.01008 |
| [5] | Bellman, R., Adaptive Control Processes: A Guided Tour (1961), Princeton Univ. Press: Princeton Univ. Press Princeton, N. J · Zbl 0103.12901 |
| [6] | Bellman, R.; Holland, J.; Kalaba, R., On an application of dynamic programming to the synthesis of logical systems, J. Assoc. Comput. Mach., 6, 486-493 (1959) · Zbl 0097.35501 |
| [7] | Bellman, R., Sequential machines, ambiguity and dynamic programming, J. Assoc. Comput. Mach., 7, 24-28 (1960) · Zbl 0097.35502 |
| [8] | Bellman, R., Dynamic programming treatment of the traveling salesman problem, J. Assoc. Comput. Mach., 9, 61-63 (1962) · Zbl 0106.14102 |
| [9] | Bellman, R.; Juncosa, M.; Kalaba, R., Some numerical experiments using Newton’s method for nonlinear parabolic and elliptic boundary-value problems, Comm. ACM, 4, 187-191 (1961) · Zbl 0166.13102 |
| [10] | Bellman, R., Successive approximation and computer storage problems in ordinary differential equations, Comm. ACM, 4, 222-223 (1961) · Zbl 0103.11102 |
| [11] | Bellman, R., Estimation of hearth parameters using skin potential measurements, Comm. ACM, 7, 666-668 (1964) |
| [12] | Bellman, R.; Buell, J.; Kalaba, R., Numerical integration of a differential-difference equation with a decreasing time-lag, Comm. ACM, 8, 227-228 (1965) · Zbl 0135.17902 |
| [13] | Bellman, R.; Kagiwada, H.; Kalaba, R., Wengert’s numerical method for partial derivatives, orbit determination, and quasi-linearization, Comm. ACM, 8, 231-232 (1965) · Zbl 0171.38401 |
| [14] | Bellman, R.; Kagiwada, H.; Kalaba, R., Nonlinear extrapolation and two-point boundary problems, Comm. ACM, 8, 511-512 (1965) · Zbl 0131.14601 |
| [15] | Bellman, R.; Kagiwada, H.; Kalaba, R., Quasi-linearization and the calculus of eigenvalues, Comm. ACM, 9, 522-524 (1966) · Zbl 0171.36103 |
| [16] | Bellman, R.; Buell, J.; Kalaba, R., Mathematical experimentation in time-lag modulation, Comm. ACM, 9, 752-754 (1966) |
| [17] | Bellman, R., Invariant imbedding and the numerical integration of boundary-value problems for unstable linear systems of ordinary differential equations, Comm. ACM, 10, 100-102 (1967) · Zbl 0148.39205 |
| [18] | Bellman, R.; Kagiwada, H.; Kalaba, R., Quasi-linearization and the estimation of differential operators from eigenvalues, Comm. ACM, 11, 255-256 (1968) · Zbl 0172.19703 |
| [19] | Bellman, R.; Kalaba, R.; Kotkin, B., Polynomial approximation—a new computational technique in dynamic programming—Allocation processes, Math. Comp., 17, 155-161 (1963) · Zbl 0123.37303 |
| [20] | Bellman, R., On the approximation of curves by line segments using dynamic programming, Comm. ACM, 4, 284 (1961) · Zbl 0100.12901 |
| [21] | Bellman, R.; Kalaba, R.; Kotkin, B., Differential approximation applied to the solution of convolution equations, Math. Comp., 18, 487-491 (1964) · Zbl 0131.14602 |
| [22] | Bellman, R.; Cooke, K.; Lockett, J., Algorithms, Graphs, and Computers (1970), Academic Press: Academic Press New York |
| [23] | Bellman, R., On a routing problem, Quart. Appl. Math., 16, 87-90 (1958) · Zbl 0081.14403 |
| [24] | Bellman, R.; Kalaba, R., On \(k\) th best policies, J. SIAM, 8, 582-588 (1960) · Zbl 0096.34304 |
| [25] | Bellman, R., An application of dynamic programming to the coloring of maps, ICC Bull., 4, 3-6 (1965) |
| [26] | Bellman, R.; Zadeh, L., Local and fuzzy logics, (Dunn, J. M.; Epstein, G., Modern Uses of Multiple-valued Logic (1977), Reidel: Reidel Dordrecht), 103-165 · Zbl 0382.03017 |
| [27] | Bellman, R., An introduction to Artificial Intelligence—Can Computers Think? (1978), Boyd and Fraser: Boyd and Fraser San Francisco |
| [28] | Bellman, R., Computers and decision making, Comput. Autom., 12, 10-14 (1963) |
| [29] | Bellman, R.; Zadeh, L., Decision-making in a fuzzy environment, Management Sci., 17, 141-164 (1970) · Zbl 0224.90032 |
| [30] | Bellman, R.; Freund, M.; Kurland, L., Simulation of the initial psychiatric interview, Comput. Behav. Sci., 389-399 (1965) |
| [31] | Bellman, R., Computer vignettes: a research tool for the study for the initial psychotherapeutic interview, J. Cybern., 1, 19-27 (1971) |
| [32] | Bellman, R., On proving theorems in plane geometry via digital computer, Amer. Math. Monthly, 73, 1108-1109 (1966) · Zbl 0151.22304 |
| [33] | Bellman, R., Dynamic programming, pattern recognition and location of faults in complex systems, J. Appl. Probab., 3, 268-271 (1966) · Zbl 0151.25102 |
| [34] | Bellman, R., On the application of dynamic programming to the determination of optimal play in chess and checkers, (Proc. Nat. Acad. Sci. U.S.A., 53 (1965)), 244-247 · Zbl 0126.36504 |
| [35] | Bellman, R., Dynamic programming and Lewis Carroll’s game of doublets, Bull. Inst. Math. Appl., 17, 86-87 (1968) |
| [36] | Bellman, R.; Esogbue, A. D.; Nabeshima, I., Mathematical Aspects of Scheduling and Applications (1982), Pergamon: Pergamon Oxford · Zbl 0498.90018 |
| [37] | Bellman, R., Some applications of the theory of dynamic programming—a review, J. Oper. Res. Soc. of Amer., 2, 275-288 (1954) · Zbl 1414.90350 |
| [38] | Bellman, R., Mathematical aspects of scheduling theory, J. SIAM, 4, 168-205 (1956) · Zbl 0074.14901 |
| [39] | Bellman, R.; Dreyfuss, S., Dynamic programming and the reliability of muiticomponent devices, Oper. Res., 6, 200-206 (1958) · Zbl 1414.90352 |
| [40] | Bellman, R.; Kalaba, R., Dynamic programming and statistical communication theory, (Proc. Nat. Acad. Sci. U.S.A., 43 (1957)), 749-751 · Zbl 0079.35202 |
| [41] | Kaufmann, A., Graphs, Dynamic Programming, and Finite Games (1967), Academic Press: Academic Press New York · Zbl 0161.39201 |
| [42] | Reingold, E. M.; Hansen, W. J., Data Structures (1983), Little, Brown: Little, Brown Boston |
| [43] | Aho, A. V.; Ullman, J. D., (The Theory of Parsing, Translation, and Compiling, Vol. I (1972), Prentice-Hall: Prentice-Hall Englewood Cliffs, N. J) |
| [44] | Coffman, E. G.; Denning, P. J., Operating Systems Theory (1973), Prentice-Hall: Prentice-Hall Englewood Cliffs, N. J · Zbl 0308.68007 |
| [45] | Hu, T. C., Combinatorial Algorithms (1982), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0505.68022 |
| [46] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0207.01701 |
| [47] | Winston, P. H., Artificial Intelligence (1984), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0598.68056 |
| [48] | Fu, K. S., Sequential Methods in Pattern Recognition and Machine Learning (1968), Academic Press: Academic Press New York · Zbl 0188.52303 |
| [49] | (Vick, C. R.; Ramamoorthy, C. V., Handbook of Software Engineering (1984), Van Nostrand-Reinhold: Van Nostrand-Reinhold New York) |
| [50] | Karp, R. M.; Held, M., Finite-state processes and dynamic programming, SIAM J. Appl. Math., 15, 693-718 (1967) · Zbl 0155.28701 |
| [51] | Bonzon, P., Necessary and sufficient conditions for dynamic programming of combinatorial type, J. Assoc. Comput. Mach., 17, 675-682 (1970) · Zbl 0223.49021 |
| [52] | Lew, A., Optimal resource allocation and scheduling among parallel processes, (Feng, T., Parallel Processing (1975), Springer-Verlag: Springer-Verlag New York/Berlin) · Zbl 0302.68037 |
| [53] | Lew, A., Optimal conversion of extended-entry decision tables with general cost criteria, Comm. ACM, 21, 269-279 (1978) · Zbl 0369.68026 |
| [54] | Wagner, R. A., Common phrases and minimum-space text storage, Comm. ACM, 17, 148-152 (1974) |
| [55] | Peterson, J. L.; Bitner, J. R.; Howard, J. H., The selection of optimal tab settings, Comm. ACM, 21, 1004-1007 (1978) · Zbl 0387.68018 |
| [56] | Knuth, D., Optimum binary search trees, Acta Inform., 1, 14-25 (1971) · Zbl 0233.68010 |
| [57] | Bayes, A. J., The optimised placing of files on disk using dynamic programming, (Anderssen, R. S.; Jennings, L. S.; Ryan, D. M., Optimisation (1972), Univ. Queensland Press: Univ. Queensland Press St. Lucia), 182-186 · Zbl 0321.68051 |
| [58] | Ramamoorthy, C. V.; Chandy, K. M.; Gonzalez, M. J., Optimal scheduling strategies in a multiprocessor system, IEEE Trans. Comput., C-21, 137-146 (1972) · Zbl 0232.68014 |
| [59] | Horowitz, E.; Sahni, S., Exact and approximate algorithms for scheduling nonidentical processors, J. Assoc. Comput. Mach., 23, 317-327 (1976) · Zbl 0329.68041 |
| [60] | Aho, A. V.; Denning, P. J.; Ullman, J. D., Principles of optimal page replacement, J. Assoc. Comput. Mach., 18, 80-93 (1971) · Zbl 0217.53504 |
| [61] | Ingargiola, G.; Korsh, J. F., Finding optimal demand-paging algorithms, J. Assoc. Comput. Mach., 21, 40-53 (1974) · Zbl 0279.68027 |
| [62] | Kernighan, B. W., Optimal sequential partitions of graphs, J. Assoc. Comput. Mach., 18, 34-40 (1971) · Zbl 0214.51703 |
| [63] | Wagner, R. A.; Fischer, M. J., The string-to-string correction problem, J. Assoc. Comput. Mach., 21, 168-173 (1974) · Zbl 0278.68032 |
| [64] | Younger, D. H., Recognition and parsing of context free languages in time \(n^3\), Inform, and Control, 10, 189-208 (1960) · Zbl 0149.24803 |
| [65] | Godbole, S. S., On efficient computation of matrix chain products, IEEE Trans. Comput., C-22, 864-866 (1973) |
| [66] | Aho, A. V.; Johnson, S. C., Optimal code generation for expression trees, J. Assoc. Comput. Mach., 23, 488-501 (1976) · Zbl 0334.68022 |
| [67] | Fu, K. S.; Chien, Y. T.; Cardillo, G. P., A dynamic programming approach to sequential pattern recognition, IEEE Trans. Electron. Comput., EC-16, 790-803 (1967) · Zbl 0178.22504 |
| [68] | Sakoe, H.; Chiba, S., Dynamic programming algorithm optimization for spoken word recognition, IEEE Trans. Acoustics, Speech. Signal Process, ASSP-26, 43-49 (1978) · Zbl 0371.68035 |
| [69] | Kalaba, R., On some communication network problems, (Proceedings 10th AMS Sympos. on App. Math. (1960)) · Zbl 0096.14604 |
| [70] | Lew, A., Computer Science: A Mathematical Introduction (1985), Prentice-Hall International: Prentice-Hall International London · Zbl 0639.68002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
