Информатика и вычислительная техника
  • формат pdf
  • размер 55.32 МБ
  • добавлен 23 сентября 2011 г.
Bednorz W. (ed.) Advances in Greedy Algorithms
Издательство InTech, 2008, -596 pp.
Сборник статей

The greedy algorithm is one of the simplest approaches to solve the optizmization problem in which we want to determine the global optimum of a given function by a sequence of steps where at each stage we can make a choice among a class of possible decisions. In the greedy method the choice of the optimal decision is made on the information at hand without worrying about the effect these decisions may have in the future. Greedy algorithms are easy to invent, easy to implement and most of the time quite efficient. However there are many problems that cannot be solved correctly by the greedy approach. The common example of the greedy concept is the problem of ‘Making Change’ in which we want to make a change of a given amount using the minimum number of US coins. We can use five different values: dollars (100 cents), quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent). The greedy algorithm is to take the largest possible amount of coins of a given value starting from the highest one (100 cents). It is easy to see that the greedy strategy is optimal in this setting, indeed for proving this it suffices to use the induction principle which works well because in each step either the procedure has ended or there is at least one coin we can use of the actual value. It means that the problem has a certain optimal substructure, which makes the greedy algorithm effective. However a slight modification of ‘Making Change’, e.g. where one value is missing, may tu the greedy strategy to be the worst choice. Therefore there are obvious limits for using the greedy method: whenever there is no optimal substructure of the problem we cannot hope that the greedy algorithm will work. On the other hand there is a lot of problems where the greedy strategy works unexpectedly well and the purpose of this book is to communicate various results in this area. The key point is the simplicity of the approach which makes the greedy algorithm a natural first choice to analyze the given problem. In this book there are discussed several algorithmic questions in: biology, combinatorics, networking, scheduling or even pure mathematics, where the greedy algorithm can be used to produce the optimal or nearly optimal answer.
The book was written in 2008 by the numerous authors who contributed the publication by presenting their researches in a form of a self-contained chapters. The idea was to coordinate the inteational project where specialists all over the world can share their knowledge on the greedy algorithms theory. Each chapter comprises a separate study on some optimization problem giving both an introductory look into the theory the problem comes from and some new developments invented by author(s). Usually some elementary knowledge is assumed, yet all the required facts are quoted mostly in examples, remarks or theorems. The publication may be useful for all graduates and undergraduates interested in the algorithmic theory with the focus on the greedy approach and applications of this method to various concrete examples. Most of scientists involved in the project are young at the full strength of their career, hence the presented content is fresh and acquaints with the new directions where the theory of greedy algorithms evolves to.
On the behalf of authors I would like to acknowledge all who made the publication possible, in particular to Vedran Kordic who coordinated this huge project. Many thanks also for those who helped in the manuscripts preparation making useful suggestions and finding errors.
Читать онлайн
Похожие разделы
Смотрите также

Atallah M.J., Blanton M. (eds.) Algorithms and Theory of Computation Handbook. General Concepts and Techniques

Справочник
  • формат pdf
  • размер 8.46 МБ
  • добавлен 30 января 2012 г.
Издательство Chapman&Hall/CRC Press, 2010, -990 pp. The design and analysis of algorithms and data structures form the foundation of computer science. As current algorithms and data structures are improved and new methods are introduced, it becomes increasingly important to present the latest research and applications to professionals in the field. This series aims to capture new developments and applications in the design and analysis of al...

Atallah M.J., Blanton M. Algorithms and Theory of Computation Handbook: Special Topics and Techniques

  • формат pdf
  • размер 10.74 МБ
  • добавлен 22 августа 2011 г.
Chapman and Hall/CRC, 2009. - 950 pages. Algorithms and Theory of Computation Handbook, Second Edition: Special Topics and Techniques provides an up-to-date compendium of fundamental computer science topics and techniques. It also illustrates how the topics and techniques come together to deliver efficient solutions to important practical problems. Along with updating and revising many of the existing chapters, this second edition contains mo...

Brassard G., Bratley P. Algorithmics: Theory and Practice

  • формат pdf
  • размер 3.85 МБ
  • добавлен 03 января 2011 г.
Prentice Hall, 1988. - 302 pages. From the Preface of the book: Our book is neither a programming manual nor an account of the proper use of data structures. Still less is it a "cookbook" containing a long catalogue of programs ready to be used directly on a machine to solve certain specific problems, but giving at best a vague idea of the principles involved in their design. On the contrary, the aim of our book is to give the reader some basic...

Cormen T.H. Introduction to algorithms

  • формат chm
  • размер 17.81 МБ
  • добавлен 12 июня 2009 г.
This book provides a comprehensive introduction to the modern study of computer algorithms. It presents many algorithms and covers them in considerable depth, yet makes their design and analysis accessible to all levels of readers. We have tried to keep explanations elementary without sacrificing depth of coverage or mathematical rigor.Each chapter presents an algorithm, a design technique, an application area, or a related topic. Algorithms are...

Geddes K., Czapor S., Labahn G. Algorithms for Computer Algebra

  • формат djvu
  • размер 4.69 МБ
  • добавлен 04 января 2011 г.
Kluwer Academic Publishers, 1992. - 585 pages. Algorithms for Computer Algebra is the first comprehensive textbook to be published on the topic of computational symbolic mathematics. The book first develops the foundational material from modern algebra that is required for subsequent topics. It then presents a thorough development of modern computational algorithms for such problems as multivariate polynomial arithmetic and greatest common divis...

Greene D.H., Knuth D.E. Mathematics for the Analysis of Algorithms

  • формат djvu
  • размер 633.5 КБ
  • добавлен 20 марта 2011 г.
Birkhauser, 1981. - 107 pages. A quantitative study of the efficiency of computer methods requires an in-depth understanding of both mathematics and computer science. This monograph, derived from an advanced computer science course at Stanford University, builds on the fundamentals of combinatorial analysis and complex variable theory to present many of the major paradigms used in the precise analysis of algorithms, emphasizing the more difficul...

Kannan R., Vempala S. Spectral Algorithms

  • формат pdf
  • размер 566.5 КБ
  • добавлен 07 октября 2011 г.
Из серии Foundations and Trends in Theoretical Computer Science издательства NOWPress, 2009, -110 pp. Spectral methods refer to the use of eigenvalues, eigenvectors, singular values, and singular vectors. They are widely used in Engineering, Applied Mathematics, and Statistics. More recently, spectral methods have found numerous applications in Computer Science to discrete as well as continuous problems. This monograph describes modern applicati...

Kao M.-Y. (ed.) Encyclopedia of Algorithms

Энциклопедия
  • формат pdf
  • размер 11.26 МБ
  • добавлен 07 октября 2011 г.
Издательство Springer, 2008, -1219 pp. Серия Springer Reference The Encyclopedia of Algorithms aims to provide the researchers, students, and practitioners of algorithmic research with a mechanism to efficiently and accurately find the names, definitions, key results, and further readings of important algorithmic problems. The work covers a wide range of algorithmic areas, and each algorithmic area is covered by a collection of entries. An encyc...

Mayr E.W., Pr?mel H.J., Steger A. (eds.) Lectures on Proof Verification and Approximation Algorithms

  • формат pdf
  • размер 5.17 МБ
  • добавлен 08 декабря 2011 г.
Издательство Springer, 1998, -337 pp. Proof Verification and Approximation Algorithms - Hardly any area in theoretical computer science has been more lively and flourishing during the last few years. Different lines of research which had been developed independently of each other over the years culminated in a new and unexpected characterization of the well-known complexity class NP, based on probabilistically checking certain kinds of proofs. T...

Van Leeuwen J. (ed.) Handbook of Theoretical Computer Science. Volume A. Algorithms and Complexity

  • формат djvu
  • размер 12.2 МБ
  • добавлен 11 мая 2011 г.
Издательсто Elsiever/MIT Press, 1990, -1010 pp. Всеобъемлющий справочник о различных типах сложности алгоритмов и вычислений Machine Models and Simulations A Catalog of Complexity Classes Machine-Independent Complexity Theory Kolmogorov Complexity and its Applications Data Structures Computational Geometry Algorithmic Motion Planning in Robotics Average-Case Analysis of Algorithms and Data Structures Graph Algorithms Algorithms in Number Theory...