et leurs relations avec d'autres problèmes combinatoires
par Donald E. Knuth (Montréal: Les Presses de l'Université
de Montréal, 1976), 106pp.

(Collection de la Chaire Aisenstadt.)

ISBN 2-7606-0529-9

full text (PDF) scanned by Marcin Anholcer (7.6MB)

This is a very stimulating book! -- N. G. de Bruijn, Mededelingen van het wiskundig Genootschap (October 1977)

This book is an excellent (and enjoyable) means of sketching a large area of computer science for specialists in other fields: It requires little previous knowledge, but expects of the reader a degree of mathematical facility and a willingness to participate. It is really neither a survey nor an introduction; rather, it is a paradigm, a fairly complete treatment of a single example used as a synopsis of a larger subject. -- Harry Lewis, SIGACT News (Winter 1978)

This remarkably well written monograph, through its clarity of expression and elegance of style, certainly achieves its aims and more. ... Anyone would enjoy reading this book. If one had to learn French first, it would be worth the effort. -- J.-L. Lassez, Computing Reviews (June 1979)

This short book will provide extremely enjoyable reading to anyone with an interest in discrete mathematics and algorithm design. -- Fabrizio Luccio, in Mathematical Reviews (1980)

The text provides many interesting examples and problems for students to study while learning the topic of algorithm analysis. -- Timothy H. McNicholl, SIGACT News (March 1999)

An English translation by Martin Goldstein, Stable Marriage and its Relation to Other Combinatorial Problems, was published in 1997 by the American Mathematical Society as volume 10 of the series entitled CRM Proceedings and Lecture Notes.

A Russian translation by Olga Kashina and Eduard Lerner will soon be published by the Moscow Center for Continuous Mathematical Education.

This booklet, which reproduces seven expository lectures given by the author in November 1975, is a gentle introduction to the analysis of algorithms, using the beautiful theory of stable marriages as a vehicle to explain the basic paradigms of that subject.

Table of Contents (English):

- Introduction, definitions, and examples
- Existence of a stable matching; the fundamental algorithm
- The principle of late binding; coupon collecting
- Theoretical developments; application to the shortest path problem
- Hashing; average behavior of the fundamental algorithm
- Implementations and variants of the fundamental algorithm
- Research problems

For a list of corrections to known errors in the French edition of this book (in English!), you may download either the errata file in plain TeX format (3474 bytes) or the errata file in DVI format (4364 bytes) or the errata file in compressed PostScript format (23660 bytes); the latter files were generated by the TeX file. (Last updated 27 February 2011.)

For a list of corrections to known errors in the English edition of this book (in English!), you may download either the errata file in plain TeX format (2174 bytes) or the errata file in DVI format (2884 bytes) or the errata file in compressed PostScript format (17419 bytes); the latter files were generated by the TeX file. (Last updated 10 May 2010.)

With these corrections, I hope the book is now error-free.
But (sigh) it probably isn't. Therefore I
will gratefully deposit
`0x$1.00` ($2.56)
to the account of the first person
who finds and reports anything that remains technically, historically,
typographically, or politically incorrect. Please send suggested corrections to
`knuth-bug@cs.stanford.edu`, or send snail mail to
Prof. D. Knuth, Computer Science Department, Gates Building 4B,
Stanford University, Stanford, CA 94305-9045 USA. I may not be able to
read your message until many months have gone by, because I'm working
intensively on
The Art of Computer Programming. However,
I promise to reply in due time.

**DO NOT SEND EMAIL TO KNUTH-BUG EXCEPT TO REPORT ERRORS IN BOOKS!**
And if you do report an error via email, please **do not
include attachments** of any kind; your message should be
readable on brand-X operating systems for all values of X.