没有合适的资源?快使用搜索试试~ 我知道了~
计算机程序设计艺术.第4卷.第5册C(英文) Dancing Links1
需积分: 0 1 下载量 88 浏览量
2022-08-03
11:12:21
上传
评论
收藏 1.07MB PDF 举报
温馨提示
试读
58页
计算机程序设计艺术.第4卷.第5册C(英文) Dancing Links1
资源推荐
资源详情
资源评论
April 15, 2017
Note to readers:
Please ignore these
sidenotes; they're just
hints to myself for
preparing the index,
and they're often aky!
KNUTH
THE ART OF
COMPUTER PROGRAMMING
VOLUME 4 PRE-FASCICLE 5C
DANCING
LINKS
DONALD E. KNUTH
Stanford University
ADDISON {WESLEY
6
77
April 15, 2017
Internet
Stanford GraphBase
MMIX
Internet page
http://www-s-faulty.stanford.edu/~knu th/taop.html
ontains
urrent information ab out this b ook and related b ooks.
See also
http://www-s-faulty.stanford.edu/~knut h/sgb.html
for information
about
The Stanford GraphBase
, inluding downloadable software for dealing with
the graphs used in many of the examples in Chapter 7.
See also
http://www-s-faulty.stanford.edu/~knut h/mmixware.html
for down-
loadable software to simulate the
MMIX
omputer.
See also
http://www-s-faulty.stanford.edu/~knut h/programs.html
for various
experimental programs that I wrote while writing this material (and some data les).
Copyright
2017 by Addison {Wesley
All rights reserved. No part of this publiation may be reprodued, stored in a retrieval
system, or transmitted, in any form, or by any means, eletroni, mehanial, photo-
opying, reording, or otherwise, without the prior onsent of the publisher, exept
that the oÆial eletroni le may be used to print single opies for p ersonal (not
ommerial) use.
Zeroth printing (revision -76), 11 April 2017
April 15, 2017
SHORT
Internet
PREFACE
With this issue we have terminated the setion \Short Notes."
. . . It has never b een \rystal lear" why a Contribution annot be short,
just as it has oasionally been veried in these pages
that a Short Note might be long.
| ROBERT A. SHORT,
IEEE Transations on Computers
(1973)
This booklet
ontains draft material that I'm irulating to exp erts in the
eld, in hop es that they an help remove its most egregious errors b efore to o
many other p eople see it. I am also, however, p osting it on the Internet for
ourageous and/or random readers who don't mind the risk of reading a few
pages that have not yet reahed a very mature state.
Beware:
This material
has not yet been proofread as thoroughly as the manusripts of Volumes 1, 2, 3,
and 4A were at the time of their rst printings. And alas, those arefully-heked
volumes were subsequently found to ontain thousands of mistakes.
Given this aveat, I hop e that my errors this time will not b e so numerous
and/or obtrusive that you will be disouraged from reading the material arefully.
I did try to make the text both interesting and authoritative, as far as it goes.
But the eld is vast; I annot hop e to have surrounded it enough to orral it
ompletely. So I b eg you to let me know about any deienies that you disover.
To put the material in ontext, this p ortion of fasile 5 previews Setion
7.2.2.1 of
The Art of Computer Programming
, entitled \Daning links." It
develops an imp ortant data struture tehnique that is suitable for
baktrak
programming
, whih is the main fo us of Setion 7.2.2. Several subsetions
(7.2.2.2, 7.2.2.3, et.) will follow.
The explosion of researh in ombinatorial algorithms sine the 1970s has
meant that I annot hop e to b e aware of all the important ideas in this eld.
I've tried my best to get the story right, yet I fear that in many respets I'm
woefully ignorant. So I beg exp ert readers to steer me in appropriate diretions.
Please look, for example, at the exerises that I've lassed as researh
problems (rated with diÆulty level 46 or higher), namely exerises 182, 263,
: : :
; I've also impliitly mentioned or p osed additional unsolved questions in the
answers to exerises 82, 86, 210, 250, 256, 261,
: : :
. Are those problems still
open? Please inform me if you know of a solution to any of these intriguing
iii
April 15, 2017
iv
PREFACE
Jellis
Huang
Siherman
FGbook
Knuth
questions. And of ourse if no solution is known to day but you do make progress
on any of them in the future, I hope you'll let me know.
I urgently need your help also with resp et to some exerises that I made
up as I was preparing this material. I ertainly don't like to reeive redit for
things that have already b een published by others, and most of these results are
quite natural \fruits" that were just waiting to b e \pluked." Therefore please
tell me if you know who deserves to be redited, with respet to the ideas found
in exerises 5, 6, 10, 15, 20, 21, 31, 40, 58, 60, 61, 75, 85, 158, 163, 177, 198(d),
206, 207, 208, 210, 218, 222, 240, 241, 242, 243, 244, 247, 248, 249, 252, 253, 255,
258, 261, 262,
: : :
. Furthermore I've redited exerises
: : :
to unpublished work
of
: : :
. Have any of those results ever app eared in print, to your knowledge?
Speial thanks are due to George Jellis for answering dozens of historial queries,
as well as to Wei-Hwa Huang, George Siherman, and
: : :
for their detailed
omments on my early attempts at exp osition. And I want to thank numerous
other orresp ondents who have ontributed ruial orretions.
I happily oer a \nder's fee" of $2.56 for eah error in this draft when it is rst
reported to me, whether that error b e typographial, tehnial, or historial.
The same reward holds for items that I forgot to put in the index. And valuable
suggestions for improvements to the text are worth 32/ eah. (Furthermore, if
you nd a b etter solution to an exerise, I'll atually do my best to give you
immortal glory, by publishing your name in the eventual b ook:
)
In the prefae to Volume 4B I plan to introdue the abbreviation
FGbook
for my bo ok
Seleted Papers on Fun and Games
(Stanford: CSLI Publiations,
2011), beause I will b e making frequent referene to it in onnetion with
rereational problems.
Cross referenes to yet-unwritten material sometimes app ear as `00'; this
impossible value is a plaeholder for the atual numbers to be supplied later.
Happy reading!
Stanford, California
D. E. K.
99 Umbruary 2016
April 15, 2017
MPR
English words
Internet
Part of the Prefae to Volume 4B
During the years that I've been preparing Volume 4, I've often run aross
basi tehniques of probability theory that I would have put into Setion 1.2
of Volume 1 if I'd been lairvoyant enough to antiipate them in the 1960s.
Finally I realized that I ought to ollet most of them together in one plae,
near the beginning of Volume 4B, b eause the story of these developments is to o
interesting to b e broken up into little piees sattered here and there.
Therefore this volume b egins with a speial setion entitled \Mathematial
Preliminaries Redux," and future setions use the abbreviation `
MPR
' to refer
to its equations and its exerises.
Several exerises involve the lists of English words that I've used in preparing
examples. You'll need the data from
http://www-s-faulty.stanford.edu/~knuth/wordlists.tgz
if you have the ourage to work those exerises.
v
剩余57页未读,继续阅读
资源评论
ShenPlanck
- 粉丝: 55
- 资源: 343
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功