Leiss - Programmer's Companion to Algorithm Analysis (Taylor, 2007).pdf

(3751 KB) Pobierz
A Programmer’s Companion to Algorithm Analysis
A ProgrAmmer’s ComPAnion
to Algorithm AnAlysis
© 2007 by Taylor & Francis Group, LLC
A ProgrAmmer’s ComPAnion
to Algorithm AnAlysis
ernst l. leiss
University of Houston,
Texas, U.S.A.
© 2007 by Taylor & Francis Group, LLC
Chapman & Hall/CRC
Taylor & Francis Group
6000 Broken Sound Parkway NW, Suite 300
Boca Raton, FL 33487-2742
© 2007 by Taylor & Francis Group, LLC
Chapman & Hall/CRC is an imprint of Taylor & Francis Group, an Informa business
No claim to original U.S. Government works
Printed in the United States of America on acid-free paper
10 9 8 7 6 5 4 3 2 1
International Standard Book Number-10: 1-58488-673-0 (Softcover)
International Standard Book Number-13: 978-1-58488-673-0 (Softcover)
This book contains information obtained from authentic and highly regarded sources. Reprinted
material is quoted with permission, and sources are indicated. A wide variety of references are
listed. Reasonable efforts have been made to publish reliable data and information, but the author
and the publisher cannot assume responsibility for the validity of all materials or for the conse-
quences of their use.
No part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any
electronic, mechanical, or other means, now known or hereafter invented, including photocopying,
microfilming, and recording, or in any information storage or retrieval system, without written
permission from the publishers.
For permission to photocopy or use material electronically from this work, please access www.
copyright.com ( http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC)
222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that
provides licenses and registration for a variety of users. For organizations that have been granted a
photocopy license by the CCC, a separate system of payment has been arranged.
Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and
are used only for identification and explanation without intent to infringe.
Library of Congress Cataloging-in-Publication Data
Leiss, Ernst L., 1952-
A programmer’s companion to algorithm analysis / Ernst L. Leiss.
p. cm.
Includes bibliographical references and index.
ISBN 1-58488-673-0 (acid-free paper)
1. Programming (Mathematics) 2. Algorithms--Data processing. I. Title.
QA402.5.L398 2006
005.1--dc22
2006044552
Visit the Taylor & Francis Web site at
and the CRC Press Web site at
http://www.crcpress.com
© 2007 by Taylor & Francis Group, LLC
 
Preface
The primary emphasis of this book is the transition from an algorithm to a
program. Given a problem to solve, the typical first step is the design of an
algorithm; this algorithm is then translated into software. We will look care-
fully at the interface between the design and analysis of algorithms on the
one hand and the resulting program solving the problem on the other. This
approach is motivated by the fact that algorithms for standard problems are
readily available in textbooks and literature and are frequently used as
building blocks for more complex designs. Thus, the correctness of the algo-
rithm is much less a concern than its adaptation to a working program.
Many textbooks, several excellent, are dedicated to algorithms, their
design, their analysis, the techniques involved in creating them, and how to
determine their time and space complexities. They provide the building
blocks of the overall design. These books are usually considered part of the
theoretical side of computing. There are also numerous books dedicated to
designing software, from those concentrating on programming in the small
(designing and debugging individual programs) to programming in the
large (looking at large systems in their totality). These books are usually
viewed as belonging to software engineering. However, there are no books
that look systematically at the gap separating the theory of algorithms and
software engineering, even though many things can go wrong in taking
several algorithms and producing a software product derived from them.
This book is intended to fill this gap. It is not intended to teach algorithms
from scratch; indeed, I assume the reader has already been exposed to the
ordinary machinery of algorithm design, including the standard algorithms
for sorting and searching and techniques for analyzing the correctness and
complexity of algorithms (although the most important ones will be
reviewed). Nor is this book meant to teach software design; I assume that
the reader has already gained experience in designing reasonably complex
software systems. Ideally, the readers’ interest in this book’s topic was
prompted by the uncomfortable realization that the path from algorithm to
software was much more arduous than anticipated, and, indeed, results
obtained on the theory side of the development process, be they results
derived by readers or acquired from textbooks, did not translate satisfac-
torily to corresponding results, that is, performance, for the developed
software. Even if the reader has never encountered a situation where the
performance predicted by the complexity analysis of a specific algorithm
did not correspond to the performance observed by running the resulting
software, I argue that such occurrences are increasingly more likely, given
© 2007 by Taylor & Francis Group, LLC
the overall development of our emerging hardware platforms and software
environments.
In many cases, the problems I will address are rooted in the different way
memory is viewed. For the designer of an algorithm, memory is inexhaust-
ible, has uniform access properties, and generally behaves
nicely
(I will be
). Programmers, however,
have to deal with memory hierarchies, limits on the availability of each class
of memory, and the distinct nonuniformity of access characteristics, all of
which imply a definite absence of niceness. Additionally, algorithm designers
assume to have complete control over their memory, while software design-
ers must deal with several agents that are placed between them and the
actual memory — to mention the most important ones, compilers and oper-
ating systems, each of which has its own idiosyncrasies. All of these conspire
against the software designer who has the naïve and often seriously disap-
pointed expectation that properties of algorithms easily translate into prop-
erties of programs.
The book is intended for software developers with some exposure to the
design and analysis of algorithms and data structures. The emphasis is
clearly on practical issues, but the book is naturally dependent on some
knowledge of standard algorithms — hence the notion that it is a companion
book. It can be used either in conjunction with a standard algorithm text, in
which case it would most likely be within the context of a course setting, or
it can be used for independent study, presumably by practitioners of the
software development process who have suffered disappointments in apply-
ing the theory of algorithms to the production of efficient software.
niceness
© 2007 by Taylor & Francis Group, LLC
more specific later about the meaning of

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin