計算機程序設(shè)計藝術(shù)

內(nèi)容概要

本冊揭開了計算機程序設(shè)計藝術(shù)目前最長一章的序幕，而論述組合算法的這章將包括完整的3卷。非正式地說，組合算法是對量非常大的對象，如alan或圖元素，進行高速處理的技術(shù)。組合模式或排列技術(shù)可解決大量的現(xiàn)實問題，而處理這些問題的現(xiàn)代方法比起以前所采用的直接過程快上千倍。本冊是后面章節(jié)的基礎(chǔ)，這里首先討論的是組合學的本質(zhì)，接著介紹在計算機內(nèi)部如何有效處理0和1的基本思想，包括布爾基礎(chǔ)和布爾求值等內(nèi)容。如常。為了強化作者的闡述，書中包括了大量細心組織、包括使用說明和詳細解答的新的習題。

作者簡介

作者：（美國）唐納德 E.克努特（Donald E.Knuth） 譯者：黃林鵬 等唐納德 E.克努特，Donald E. Knuth，中文名高德納。由于在算法和程序設(shè)計技術(shù)方面的先驅(qū)性工作，由于發(fā)明了計算機排版系統(tǒng)TEX和METAFONT。以及由于他的富于創(chuàng)造力的、影響深遠的論著，Knuth名揚全球。作為斯坦福大學計算機程序設(shè)計藝術(shù)的榮譽退休教授，Knuth現(xiàn)在正投入全部的精力來完成這些分冊以及包含這些分冊的七卷著作。

書籍目錄

PREFACE iii PREFACE TO VOLUME Chapter 7 Combinatorial Searching 7.1 Zeros and Ones 7.1.1 Boolean Basics 7.1.2 Boolean Evaluation Answers to Exercises Index and Glossary 譯者序 前言 第4卷前言 第7章 組 合 搜 索 　7.1　0和1 　　7.1.1　布爾基礎(chǔ) 　　7.1.2　布爾求值 　　習題答案

章節(jié)摘錄

插圖：Aren't we missing the point if we merely shuffle such questions off to machines, to be solved by brute force instead of by rational thought? George Brewster, writing to Martin Gardner in 1963, expressed a widely held view as follows: “Feeding a recreational puzzle into a computer is no more than a step above dynamiting a trout stream. Succumbing to instant recreation.”Yes, but that view misses another important point: Simple puzzles often have generalizations that go beyond human ability and arouse our curiosity. The study of those generalizations often suggests instructive methods that apply to numerous other problems and have surprising consequences. Indeed, many of the key techniques that we shall study were born when people were trying to solve various puzzles. While writing this chapter, the author couldn't help relishing the fact that puzzles are now more fun than ever, as computers get faster and faster, because we keep getting more powerful dynamite to play with. Further comments appear in the author's essay, “Can toy problems be useful?”, originally written in 1976; see Selected Papers on Computer Science (1996), 169-183.Puzzles do have the danger that they can be too elegant. Good puzzles tend to be mathematically clean and well-structured, but we also need to learn how to deal systematically with the messy, chaotic, organic stuff that surrounds us every day. Indeed, some computational techniques are important chiefy because they provide powerful ways to cope with such complexities. That is why, for example, the arcane rules of library-card alphabetization were presented at the beginning of Chapter 5, and an actual elevator system was discussed at length to illustrate simulation techniques in Section 2.2.5.A collection of programs and data called the Stanford Graph Base (SGB) has been prepared so that experiments with combinatorial algorithms can readily be performed on a variety of real-world examples. SGB includes, for example, data about American highways, and an input-output model of the U.S. economy; it records the casts of characters in Homer's Iliad, Tolstoy's Anna Karenina, and several other novels; it encapsulates the structure of Roget's Thesaurus of 1879; it documents hundreds of college football scores; it specifies the gray-value pixels of Leonaxdo da Vinci's Gioconda (Mona Lisa). And perhaps most importantly, SGB contains a collection of five-letter words, which we shall discuss next. The five-letter words of English. Many of the examples in this chapter will be based on the following list of five-letter words:  aargh, abaca, abaci, aback, abaft, abase, abash……zooms, zowie. (8)(There are 5757 words altogether——too many to display here; but those that are missing can readily be imagined.) It's a personal list, collected by the author between 1972 and 1992, beginning when he realized that such words would make ideal data for testing many kinds of combinatorial algorithms.

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    計算機程序設(shè)計藝術(shù) PDF格式下載

---