没有合适的资源?快使用搜索试试~ 我知道了~
计算机算法与分析(Aho,Hopcroft,Ullman)
需积分: 13 54 下载量 5 浏览量
2018-10-24
17:38:45
上传
评论 3
收藏 26.95MB PDF 举报
温馨提示
试读
479页
The Design and Analysis of Computer Algorithms [Aho, Hopcroft & Ullman 1974-01-11]
资源推荐
资源详情
资源评论
THE
DESIGN
AND
ANALYSIS
OF
COMPUTER
ALGORITHMS
Alfred
V.
Aho
Bell Laboratories
John
E.
Hopcroft
Cornell University
Jeffrey
D.
U
II
man
Princeton University
A
"
Addison-W~ley
Publishing Company
Reading. Massachusetts
·
Menlo
Park.
California
London
· Amsterdam · Don Mills. Ontario · Sydney
PREFACE
"'
......
The
study
of
algorithms
is
at the very heart
of
c.:omputer science:-
Irr;
-redeht
years a
number
of
significant
advances
in the field
of
algorithms·
have
b'f'en
made.
These
advances
have ranged from
the
development
off~s,te,r;
algori,th~~.
such
as the fast
Fourier
transform. to the startling discovery of-q:rtain
r)atur.~I.
problems·for
which all algorithms
are
inefficient.
These
results have kindled
considerable interest in
the
study
of
algorithms.
and
the
area
of
algorithm de-
sign
and
analysis has blossomed into a field
of
intense interest.
The
intent
of
this
book
is to bring
together
the
fundamental results
in
this area,
so
the
uni-
fying principles and underlying
concepts
of
algorithm design may more easily
be
taught.
THE SCOPE
OF
THE
BOOK
..1
To
analyze the
performance
of
an algorithm some model
of
a
computer
is
necessary.
Our
book begins by formulating several
computer
models which
are
simple enough to establish analytical results
but
which at the
same
time
accurately
reflect
the
salient features
of
real machines.
These
models include
the
random
access
register machine. the
random
access
stored
program
ma-
chine,
and
some specialized variants
of
these.
The
Turing
machine
is intro-
duced in
order
to
prove
the
exponential
lower
bounds
on
efficiency in Chapters,
I 0
and
11. Since the
trend
in
program design is
away
from machine language,
a
high.:..level
language called Pidgin
ALGOL
is
introduced
as
the
main vehicle
for
describing algorithms.
The
complexity
of
a Pidgin
ALGOL
program
is
related to the machine models.
The
second
chapter
introduces basic
data
structures
and
programming
techniques often used
in
efficient algorithms.
It
covers
the use
of
lists. push-
down stores.
queues.
trees.
and
graphs. Detailed explanations
of
recursion.
divide-and-conquer. and dynamic programming
are
giv~n.
along. with
examples
of
their use.
Chapters
3 to 9 provide a sampling
of
the
diverse
areas to which the funda-
mental
techniques
of
Chapter
:!
can
be applied. Otfr eh1phasis
i"n
these··chap~
ters
is.
on developing algo1:ithms that are a·symp.toti.caUy:
th:e
· m
1
ost'
~ffiti'ent
known. Because
of
thiS'
emphasis. some
of
the algorithms.
presented
are.suit-
able only for inputs whose size
is
much larger than what
is
currently
encoun-
·
··
:"
_·
iii
iv
PREFACE
tered
in
practice.
This
is particularly
true
of
some
of
the
matrix multiplication
algorithms
in
Chapter
6,
the
SchOnhage-Strassen
integer-muitiptication algo-
rithm
of
Chap~er
7.
and
some
of
the
polynomial
.and
integer
algorjthms
of
Chapter
8. ,
On
the
o~her
hand,
most
of
the
sorting
algorithms
of
Chapter
3,
the
scarch-
irig
algorithms
of
Chapter
4,
the
graph
a.lgorithms
of
Chapter
5,
the
fast
Fourier
transform
of
Chapter
7,
and
the
string-matching
algorithms
of
Chapter
9
are
widely
used,
since
the
sizes
of
,inputs
for
which
these
algorithms
are
efficient
are
sufficiently
s_maH
to.
be
encountered
in
many
practical
situations
..
Chapters
I 0
through
12
discuss
lower
bounds
on
computational
com-
plexity.
The
inherent
computational
difficulty
of
a
problem
is
of
universal
interest.
both
to
program
design
and
to
an
understanding
of
the
nature
of
com-
putation.
In
Chapter
IO
an
important
class
of
problems,
the
NP-complete
problems,
is
studied.
All
problems
in this
class
are
equivalent
in
computa-
qonal
difficulty. in
that
if
one
problem
in
the
class
has
an
efficient (polynomial
ti-~e-~ound_ed)
solution,
then
all
problems
in
the
class
have
efficient sol.µtions.
Since
-this
class
of
problems
contains
many
practically
important
and
well-
studied
problems,
such
as
the
integer-programming
problem
and
the
traveling
salesman
problem,
there
is
good
r~ason
to
suspect
that
no
problem
in this
class
can
be
solved
efficiently.
Thus,
if a
program
designer
knows
that
the
problem
for
which
he is
trying
to
find
an
effiC:ient
algorithm
is in this
class.
then
he .may
very
well
be
content
to
try
heuristic
approaches
to
the
problem.
In
spite
of
the
overwhelming
empirical
evidence
to the
contrary,
it is still
an
open
question
whether
NP-complete
problems
admit
of
efficient
solutions.
In
Chapter
11
certain
problems
are
defined
for
which
we
can
actually
prove
that
no
efficient
algorithms
exist.
The
material in
Chapters
I 0
and
11
draws
heavily
on
the
concept
of
Turing
machines
introduced
in
Section~
1.6
and
1.7. · ·
In
the
final
chapter
of
the
book
w.~
relate
concepts
of
computational
dif-
ficulty
to
notions
of
linear
independence
in
vector
spaces.
The
material in this
~hapter
provides
techniques
for
proving
lower
bounds
for
much
simpler
prob-
lems
than
those
considered
in
Chapters
I 0
and
11.
PREFACE v
THE USE
OF
THE BOOK
This: book
is
intended as a first course in the design and analysis
of
algorithms.
The emphasis
is
on ideas and ease
of
un~erstanding
rather than implementa-
tion details or
progra~ming
tricks. Informal, intuitive
~xplanations
are often
used in place
of
long tedious proofs.
The
book
is
self-contained and assumes
no specific background
iri
mathematics
or
programming languages. However,
a certain amount
of
maturity in being able to handle mathematical concepts
is
desirable, as
is
some exposure to a higher-level programming language such as
FORTRAN
\or
ALGOL.
Some knowledge
of
linear
algeb~a
is
needed for a
full understanding
of
Chapters
6;
7, 8, and 12.
This book has been used
in
graduate and undergraduate c'ourses
in
algo-
rithm design. In a one-semester course most
of
Chapters 1-5 and
9-10
were
covered,
aiong with a smattering
of
topics from the remaining chapters. In
introductory courses the emphasis was on material from Chapters
1~5.
but
Se·ctions 1.6, 1.7, 4.13, 5.11, and Theorem 4.5 were generally not covered.
The book can also be used in more advanced courses emphasizing the
th~ory
of
algorithms. Chapters
6-12
could serve as the foundation for such a course.
Numerous exercises have been provided at the end
of
each chapter to
provide an instructor with a wide range
of
homework problems. The exercises
are graded according to difficulty. Exercises with no stars are suitable for
in-
troductory courses, singly starred exercises for more advanced courses, and
doubly starred exercises. for advanced graduate courses. The bibliographic
notes at the end
of
every chapter attempt to point to a published source for
each
of
the .algorithms and results contained
in
the text and the exercises.
ACKNOWLEDGMENTS
The material
in
this book has been derived from class notes for courses taught
by the authors at Cornell,
Princeton, and Stevens Institute ofTechnoiogy. The
authors would like to thank the
many people who have criticaily read various
portions
of
the manuscript and offered many helpful suggestions. In particular
we
would like to thank Kellogg Booth, Stan Brown, Steve Chen, Allen Cypher.
vi PREFACE
Arch Davis, Mike Fischer. Hania Gajewska. Mike Garey. Udai Gupta.
Mike Harrison. Matt Hecht, Harry Hunt. Dave
Johnson. Marc Kaplan,
Don
Johnson, Steve Johnson, Brian Kernighan. Don Knuth, Richard Ladner,
Anita LaSalle, Doug Mcllroy, Albert Meyer, Christos·
Papadimitr~ou,
Bill
Plauge~.
John Savage, Howard Siege!, Ken Steiglit;::, Larry Stockmeyer,
Tom
Szymanski, and Theodore Yen.
Special thanks
go
to Gemma Carnevale, Pauline Cameron. Hannah
Kresse, Edith
Purser, and Ruth Suzuki for their cheerful and careful typing
of
the manuscript.
The
authors are also grateful to Bell Laboratories and Cornell. Princeton,
and the University
of
California at Berkeley for providing facilities for the
preparation
of
the manuscript.
June
1974 A. V. A.
J.E.
H.
J. D. U.
剩余478页未读,继续阅读
资源评论
linearLife
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功