The Art of Computer Programming: Combinatorial Algorithms, Volume 4B (Hardcover)

Knuth, Donald

  • 出版商: Addison Wesley
  • 出版日期: 2022-10-08
  • 售價: $2,880
  • 貴賓價: 9.5$2,736
  • 語言: 英文
  • 頁數: 640
  • 裝訂: Hardcover - also called cloth, retail trade, or trade
  • ISBN: 0201038064
  • ISBN-13: 9780201038064
  • 相關分類: R 語言Algorithms-data-structures
  • 立即出貨 (庫存 < 3)

買這商品的人也買了...

商品描述

The Art of Computer Programming is Knuth's multivolume analysis of algorithms. With the addition of this new volume, it continues to be the definitive description of classical computer science.

Volume 4B, the sequel to Volume 4A, extends Knuth's exploration of combinatorial algorithms. These algorithms are of keen interest to software designers because . . . a single good idea can save years or even centuries of computer time.

The book begins with coverage of Backtrack Programming, together with a set of data structures whose links perform delightful dances and are ideally suited to this domain. New techniques for important applications such as optimum partitioning and layout are thereby developed.

Knuth's writing is playful, and he includes dozens of puzzles to illustrate the algorithms and techniques, ranging from popular classics like edge-matching to more recent crazes like sudoku. Recreational mathematicians and computer scientists will not be disappointed!

In the second half of the book, Knuth addresses Satisfiability, one of the most fundamental problems in all of computer science. Innovative techniques developed at the beginning of the twenty-first century have led to game-changing applications, for such things as optimum scheduling, circuit design, and hardware verification. Thanks to these tools, computers are able to solve practical problems involving millions of variables that only a few years ago were regarded as hopeless.

The Mathematical Preliminaries Redux section of the book is a special treat, which presents basic techniques of probability theory that have become prominent since the original preliminaries were discussed in Volume 1.

As in every volume of this remarkable series, the book includes hundreds of exercises that employ Knuth's ingenious rating system, making it easy for readers of varying degrees of mathematical training to find challenges suitable to them. Detailed answers are provided to facilitate self-study.

Professor Donald E. Knuth has always loved to solve problems. In Volume 4B he now promotes two brand new and practical general problem solvers, namely (0) the Dancing Links Backtracking and (1) the SAT Solver. To use them, a problem is defined declaratively (0) as a set of options, or (1) in Boolean formulae. Today's laptop computers, heavily armoured with very high speed processors and ultra large amounts of memory, are able to run either solver for problems having big input data. Each section of Volume 4B contains a multitudinous number of tough exercises which help make understanding surer. Happy reading! --Eiiti Wada, an elder computer scientist, UTokyo

Donald Knuth may very well be a great master of the analysis of algorithms, but more than that, he is an incredible and tireless storyteller who always strikes the perfect balance between theory, practice, and fun. [Volume 4B, Combinatorial Algorithms, Part 2] dives deep into the fascinating exploration of search spaces (which is quite like looking for a needle in a haystack or, even harder, to prove the absence of a needle in a haystack), where actions performed while moving forward must be meticulously undone when backtracking. It introduces us to the beauty of dancing links for removing and restoring the cells of a matrix in a dance which is both simple to implement and very efficient. --Christine Solnon, Department of Computer Science, INSA Lyon

Register your book for convenient access to downloads, updates, and/or corrections as they become available.

商品描述(中文翻譯)

《計算機程式設計藝術》是Knuth對演算法的多卷分析。隨著這本新卷的加入,它繼續成為古典計算機科學的權威描述。

第4B卷是第4A卷的續集,延伸了Knuth對組合演算法的探索。這些演算法對軟體設計師非常重要,因為一個好的想法可以節省數年甚至數世紀的計算機時間。

本書以回溯編程為開端,介紹了一組數據結構,其連結執行著令人愉悅的舞蹈,非常適合這個領域。同時,還開發了最佳分割和佈局等重要應用的新技術。

Knuth的寫作風格富有趣味性,他包含了數十個謎題來說明演算法和技術,從流行的經典遊戲如拼邊到最近的熱潮如數獨。愛好數學和計算機科學的人不會失望!

在書的後半部分,Knuth討論了滿足性問題,這是計算機科學中最基本的問題之一。21世紀初開發的創新技術已經帶來了具有改變遊戲規則的應用,例如最佳排程、電路設計和硬體驗證。多年前被認為是絕望的涉及數百萬個變數的實際問題,現在得以通過這些工具解決。

書中的數學前提部分是一個特別的享受,介紹了自第1卷討論以來變得重要的概率理論基本技巧。

與這個卓越系列的每一卷一樣,本書包含數百個練習,使用Knuth獨特的評分系統,讓不同程度的數學訓練的讀者都能找到適合自己的挑戰。提供詳細答案以便自學。

Donald E. Knuth教授一直喜歡解決問題。在第4B卷中,他現在推出了兩個全新且實用的通用問題求解器,即(0) Dancing Links回溯和(1) SAT Solver。使用這些求解器,可以將問題以聲明方式定義(0)為一組選項,或(1)為布林公式。現在的筆記型電腦配備了高速處理器和大容量記憶體,能夠運行這兩個求解器來處理大型輸入數據的問題。第4B卷的每個部分都包含大量的難題練習,有助於更好地理解。祝閱讀愉快!--Eiiti Wada,資深計算機科學家,東京大學

Donald Knuth可能是算法分析的偉大大師,但他更是一位令人難以置信且不知疲倦的故事講述者,總能在理論、實踐和樂趣之間取得完美的平衡。《第4B卷,組合演算法,第2部分》深入探索了搜索空間的迷人之處(有點像在一堆乾草中尋找針一樣困難,甚至更難,要證明一堆乾草中沒有針),在前進時執行的操作必須在回溯時仔細撤銷。它向我們介紹了舞蹈連結的美妙之處,用於刪除和恢復矩陣的單元格,這種方法既容易實現又非常高效。--Christine Solnon,計算機科學系,INSA里昂

註冊您的書,以便方便地獲取下載、更新和/或更正。```

作者簡介

Donald E. Knuth is known throughout the world for his pioneering work on algorithms and programming techniques, for his invention of the TEX and METAFONT systems for computer typesetting, and for his prolific and influential writing (26 books, 161 papers). Professor Emeritus of The Art of Computer Programming at Stanford University, he currently devotes full time to the completion of his seminal multivolume series on classical computer science, begun in 1962 when he was a graduate student at California Institute of Technology. Professor Knuth is the recipient of numerous awards and honors, including the ACM Turing Award, the Medal of Science presented by President Carter, the AMS Steele Prize for expository writing, and, in November, 1996, the prestigious Kyoto Prize for advanced technology. He lives on the Stanford campus with his wife, Jill.

作者簡介(中文翻譯)

Donald E. Knuth以他在算法和編程技術方面的開創性工作而聞名於世,他發明了用於計算機排版的TEX和METAFONT系統,並以其豐富而有影響力的著作(26本書,161篇論文)而聞名。他是斯坦福大學計算機編程藝術的名譽教授,目前全職致力於完成他在經典計算機科學領域的重要多卷系列著作,該系列始於1962年,當時他是加州理工學院的研究生。Knuth教授獲得了許多獎項和榮譽,包括ACM圖靈獎、由卡特總統頒發的科學獎章、AMS Steele獎(用於解說性寫作)以及1996年11月的著名京都獎(用於先進技術)。他與妻子Jill居住在斯坦福大學校園內。