scientific article; zbMATH DE number 4016186

From MaRDI portal
Publication:3028339





The book is devoted to the modern and fascinating topic of computational complexity of algorithms. In part one a survey of some important results in the synthesis and analysis of sequential algorithms is given. Part two describes some results in the field of parallel algorithms. Both topics are very actual, but the scientific level of presentation is different. The first part (97 pages) brings good and understandable up-to-date results, but the second part (115 pages) is only an introduction to parallel algorithms whereby only Chapters 13, 14 and 15 (Fast Fourier Transform, sorting, and graph algorithms) give a good survey of results. A comprehensive list of references is included together with a short table of notations and with an index. Part one has 9 chapters. After an introduction of the main concepts of sequential computational complexity some interesting fast numerical algorithms are introduced. On some examples the ``divide and conquer approach for recursive calculations is explained. Then, complexity of sorting, searching and updating of sequence of elements is investigated and efficient algorithm design techniques for difficult exponential time algorithms (recursion, optimization, dynamic programming, graph searching) together with some probabilistic algorithms are evaluated. In the last three chapters of the first part of the book, algorithms for theorem proving are studied, a classification of algorithms with polynomial and exponential time is given and some abstract theoretical results are briefly formulated. In Part two the computational complexity of parallel algorithms is studied. After an introduction to architecture of parallel computers, the next three chapters give some simple parallel algorithms: zero-searching algorithms for a non-linear function, iterative synchronized and asynchronous algorithms for solving systems of non-linear equations, and a type of synchronized algorithms for matrix multiplication. The last three chapters of the book give a good survey of parallel FFT algorithms, parallel sorting, and parallel graph search and traversal algorithms. Most of them are not modifications of sequential algorithms, but they were created only for parallel computers. The book is recommended for undergraduate and postgraduate students in computer science, mathematics and software engineering, and also as an introductory book for people who want to solve their scientific-technical problems on some parallel supercomputer.






Describes a project that uses

Uses Software






This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3028339)