算法导论Word版：计算机科学经典读物

3星 · 超过75%的资源需积分: 9 17 浏览量更新于2024-08-01 收藏 5.62MB DOC 举报

《算法导论（第二版）》是计算机科学领域的一部经典著作，由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein四位作者共同编撰，隶属于麻省理工学院电气工程与计算机科学系系列教材。本书由The MIT Press出版，并通过与McGraw-Hill Book Company的合作协议进行分发。该版本的书籍特别适合在电脑屏幕上阅读，对于想要深入理解算法理论和实践的读者来说，它是一本不可或缺的参考文献。书中详细讲解了算法设计、分析和应用的基本原理，涵盖了排序、图算法、动态规划、数据结构等多个核心主题，帮助读者建立起坚实的算法基础。《算法导论》不仅阐述了算法的理论概念，还提供了大量实际问题的解决方法和步骤，适合于初学者入门，同时也是高级程序员和研究者提升技能的宝贵资源。书中还强调了算法设计的重要性，鼓励读者通过逻辑思考和实践来理解和掌握这些关键概念。版权方面，本书享有2001年的版权，首次出版日期为1990年，所有内容未经书面许可不得以任何形式复制或通过电子或机械手段（如复印、录音或信息存储和检索）进行传播。如果你欲购买或获取本书，请根据地区选择相应的订购渠道：北美地区的订单应寄往McGraw-Hill Book Company，而北美以外的订单则需联系The MIT Press 或其当地经销商。《算法导论（第二版）》是一本全面且深入的算法教材，无论你是想系统学习还是寻求特定问题的解决方案，都将从中受益匪浅。无论是作为学术研究资料，还是技术开发者的工具书，都具有极高的价值。

strategies we will use throughout this book, and many of the fundamental ideas used in

algorithm analysis. Later parts of this book will build upon this base.

Chapter 1 is an overview of algorithms and their place in modern computing systems.

This

chapter defines what an algorithm is and lists some examples. It also makes a case that

algorithms are a technology, just as are fast hardware, graphical user interfaces,

objectoriented

systems, and networks.

In Chapter 2, we see our first algorithms, which solve the problem of sorting a sequence

of n

numbers. They are written in a pseudocode which, although not directly translatable to

any

conventional programming language, conveys the structure of the algorithm clearly

enough

that a competent programmer can implement it in the language of his choice. The sorting

algorithms we examine are insertion sort, which uses an incremental approach, and merge

sort, which uses a recursive technique known as "divide and conquer." Although the time

each requires increases with the value of n, the rate of increase differs between the two

algorithms. We determine these running times in Chapter 2, and we develop a useful

notation

to express them.

Chapter 3 precisely defines this notation, which we call asymptotic notation. It starts by

defining several asymptotic notations, which we use for bounding algorithm running

times

from above and/or below. The rest of Chapter 3 is primarily a presentation of

mathematical

notation. Its purpose is more to ensure that your use of notation matches that in this book

than

to teach you new mathematical concepts.

Chapter 4 delves further into the divide-and-conquer method introduced in Chapter 2. In

particular, Chapter 4 contains methods for solving recurrences, which are useful for

describing the running times of recursive algorithms. One powerful technique is the

"master

method," which can be used to solve recurrences that arise from divide-and-conquer

algorithms. Much of Chapter 4 is devoted to proving the correctness of the master

method,

though this proof may be skipped without harm.

Chapter 5 introduces probabilistic analysis and randomized algorithms. We typically use

probabilistic analysis to determine the running time of an algorithm in cases in which,

due to

the presence of an inherent probability distribution, the running time may differ on

different

inputs of the same size. In some cases, we assume that the inputs conform to a known

probability distribution, so that we are averaging the running time over all possible

inputs. In

other cases, the probability distribution comes not from the inputs but from random

choices

made during the course of the algorithm. An algorithm whose behavior is determined not

only

by its input but by the values produced by a random-number generator is a randomized

algorithm. We can use randomized algorithms to enforce a probability distribution on the

inputs-thereby ensuring that no particular input always causes poor performance-or even

bound the error rate of algorithms that are allowed to produce incorrect results on a

limited

basis.

Appendices A-C contain other mathematical material that you will find helpful as you

read

this book. You are likely to have seen much of the material in the appendix chapters

before

having read this book (although the specific notational conventions we use may differ in

some

cases from what you have seen in the past), and so you should think of the Appendices as

reference material. On the other hand, you probably have not already seen most of the

material in Part I. All the chapters in Part I and the Appendices are written with a tutorial

flavor.

Chapter 1: The Role of Algorithms in

Computing

What are algorithms? Why is the study of algorithms worthwhile? What is the role of

algorithms relative to other technologies used in computers? In this chapter, we will

answer

these questions.

1.1 Algorithms

Informally, an algorithm is any well-defined computational procedure that takes some

value,

or set of values, as input and produces some value, or set of values, as output. An

algorithm is

thus a sequence of computational steps that transform the input into the output.

We can also view an algorithm as a tool for solving a well-specified computational

problem.

The statement of the problem specifies in general terms the desired input/output

relationship.

The algorithm describes a specific computational procedure for achieving that

input/output

relationship.

For example, one might need to sort a sequence of numbers into nondecreasing order.

This

problem arises frequently in practice and provides fertile ground for introducing many

standard design techniques and analysis tools. Here is how we formally define the sorting

problem:

. Input: A sequence of n numbers _a1, a2, ..., an_.

. Output: A permutation (reordering) of the input sequence such that

For example, given the input sequence _31, 41, 59, 26, 41, 58_, a sorting algorithm

returns

as output the sequence _26, 31, 41, 41, 58, 59_. Such an input sequence is called an

instance

of the sorting problem. In general, an instance of a problem consists of the input

(satisfying

whatever constraints are imposed in the problem statement) needed to compute a solution

the problem.

Sorting is a fundamental operation in computer science (many programs use it as an

intermediate step), and as a result a large number of good sorting algorithms have been

developed. Which algorithm is best for a given application depends on-among other

factorsthe

number of items to be sorted, the extent to which the items are already somewhat sorted,

possible restrictions on the item values, and the kind of storage device to be used: main

memory, disks, or tapes.

An algorithm is said to be correct if, for every input instance, it halts with the correct

output.

We say that a correct algorithm solves the given computational problem. An incorrect

algorithm might not halt at all on some input instances, or it might halt with an answer

other

than the desired one. Contrary to what one might expect, incorrect algorithms can

sometimes

be useful, if their error rate can be controlled. We shall see an example of this in Chapter

when we study algorithms for finding large prime numbers. Ordinarily, however, we

shall be

concerned only with correct algorithms.

An algorithm can be specified in English, as a computer program, or even as a hardware

design. The only requirement is that the specification must provide a precise description

of the

computational procedure to be followed.

What kinds of problems are solved by algorithms?

Sorting is by no means the only computational problem for which algorithms have been

developed. (You probably suspected as much when you saw the size of this book.)

Practical

applications of algorithms are ubiquitous and include the following examples:

. The Human Genome Project has the goals of identifying all the 100,000 genes in

human DNA, determining the sequences of the 3 billion chemical base pairs that make

up human DNA, storing this information in databases, and developing tools for data

analysis. Each of these steps requires sophisticated algorithms. While the solutions to

the various problems involved are beyond the scope of this book, ideas from many of

the chapters in this book are used in the solution of these biological problems, thereby

剩余63页未读，继续阅读

andybao2010

粉丝: 0
资源: 1

算法导论Word版：计算机科学经典读物

算法导论（word）版

算法导论（第二版）WORD版

算法导论中英word版

算法导论 习题答案 word版

算法导论（二版） word

算法导论的中文答案（word版）

算法导论 计算机专业

算法导论英文版(Word版)---Introduction_to_Algorithms_2nd_Edition

MIT 算法导论 课堂笔记

算法导论答案 很全的版本

最新资源

算法导论习题答案 word版

算法导论计算机专业

MIT 算法导论课堂笔记

算法导论答案很全的版本