The Art of Computer Programming 3 정렬과 검색

Art of Computer Programming

by Donald Ervin Knuth, 류광 (Traslator)

이 책은 다른 기본적인 구조적 착안들에 선형 순서 자료의 개념을 더하는 것이므로, 제1권 제2장의 정보 과학 내용과 관련해서, 그 자연스러운 속편에 해당한다. "정렬과 검색"이라는 제목 때문에, 이 책을 범용 정렬 루틴이나 정보 조회를 위한 응용프로그램에 관계되는 시스템 프로그래머들만을 위한 책으로 오해할 수도 있으나 사실 이 책에서 다루는 내용은 다음과 같은 다양한 종류의 주요 주제들에 대한 이상적인 틀을 제공한다.

- 좋은 알고리즘은 어떻게 발견되는가?
- 알고리즘과 프로그램을 개선하려면?
- 알고리즘의 효율을 수학적으로 분석하려면?
- 같은 과제를 위한 서로 다른 알고리즘들 중 적절한 것을 합리적으로 선택하려면?
- 어떤 의미 하에서 알고리즘이 "가능한 최고"임을 증명할 수 있는가?
- 컴퓨팅 이론이 현실의 고려사항들과 어떻게 연동되는가?
- 커다란 데이터베이스를 위해 테이프, 드럼, 디스크 같은 외부 기억장치들을 효율적으로 사용하려면?

Genres: Programming, Computer Science, Reference, Algorithms, Technical, Nonfiction, Computers

937 pages, Hardcover

First published January 1, 1973

About the author

Donald Ervin Knuth, born January 10th 1938, is a renowned computer scientist and Professor Emeritus of the Art of Computer Programming at Stanford University.

Author of the seminal multi-volume work The Art of Computer Programming ("TAOCP"), Knuth has been called the "father" of the analysis of algorithms, contributing to the development of, and systematizing formal mathematical techniques for, the rigorous analysis of the computational complexity of algorithms, and in the process popularizing asymptotic notation.

In addition to fundamental contributions in several branches of theoretical computer science, Knuth is the creator of the TeX computer typesetting system, the related METAFONT font definition language and rendering system, and the Computer Modern family of typefaces.

A prolific writer and scholar, Knuth created the WEB/CWEB computer programming systems designed to encourage and facilitate literate programming, and designed the MMIX instruction set architecture.

Reviews

[Roger · Rating 5 out of 5]

I felt smart having it on myshelf. I felt dumb trying to fathom it

[Josh Berry · Rating 5 out of 5]

There are definitely sections of the book that are hard to appreciate. In that I probably did not. The majority of it is approachable and really gives an appreciation for the decisions that go into how to organize data. The section on retrieval by secondary key was a real delight.

The feeling at each section of "that data structure is awesome" followed by a more apt one is impressive. Especially for how often it happens. Even seeing I was coming to the end of the book, I got used to the surprise of yet another way to do things.

I do hope he gets the next version out with some of the items on Persistent Data Structures out. I am not completely sold that those are necessary for most applications, but I suspect I'll be proven wrong. :)

[Bernie4444 · Rating 5 out of 5]

Just try sorting and searching without this book.

I just bought the book I needed out of the set. I needed to build a database that did not use any commercial package (this gives full access and no royalties). This book saved my bacon. I almost did not buy it when all I saw in it was math. But I was desperate and it paid off. Turns out you could not explain it any other way. This book goes way beyond binary, and bubble sorts. I use it primarily for balanced trees. I may try something more exotic later. I can not tell you about the other volumes but this one will defiantly pay for itself.

[Topilno]

Creating Web Pages for Dummies

[marcel · Rating 4 out of 5]

Because of the emphasis placed on sorting and searching algorithms in the undergraduate curriculum, this volume is the most likely to show up on a computer science class' "recommended reading" list. True to its title, Volume 3 is split almost evenly between sorting, in the first half, and searching in the second. All of the bread-and-butter algorithms and data structures are covered, from quicksort to binary heaps to tries, which makes this a very important volume, but also perhaps a bit boring, since any computer science major will have seen many these concepts in undergraduate classes (though certainly in only a fraction of the detail that Knuth devotes to them). There is a somewhat large section, complete with a wonderful foldout, devoted to the ins-and-outs of merging large files stored on huge physical rolls of magnetic tape. I found this section quite entertaining because of the novelty of learning about how people used to store data, but most of it is quite useless to the modern reader. I believe that Knuth intends to scrap it and replace it with something else in the next edition.

[Abdellah · Rating 4 out of 5]

The Art of Computer Programming: Volume 3: Sorting and Searching is considered a comprehensive reference on the subject of sorting and searching algorithms. The book covers a wide range of algorithms, including basic methods such as insertion and bubble sort, as well as more advanced methods such as quicksort and merge sort. The book also covers searching algorithms, including linear search, binary search, and hash tables. The book is written in a clear, easy-to-understand style and includes numerous examples and exercises to help readers understand the concepts.

In addition to its coverage of algorithms, the book also includes chapters on data structures such as linked lists, trees, and graphs. The book also includes a discussion of computational complexity and performance analysis of algorithms, which is essential for understanding the trade-offs between different algorithms.

The book has been widely used as a textbook in computer science education and is also widely used as a reference by professionals in the field. It is considered an essential resource for anyone interested in the field of algorithms and data structures.

[Robert Fishell · Rating 5 out of 5]

Of the first 3 volumes in this series, this is the most essential after the first. Sorting and searching are among the most important concepts programmers need to master in order to become master programmers.

[Gaetano Venezia · Rating 4 out of 5]

Lives up to the hype as an excellent reference book, but definitely a difficult/tedious read without a specific goal and problem in mind. Cleared up several ambiguous ideas I had about search and sort algorithms and time complexity.

[Tuấn Kiệt · Rating 5 out of 5]

nice

[Manoj Khatri · Rating 5 out of 5]

The LEGEND.

[Jeffrey]

I haven't read this through, but I have used it is a reference.