アルゴリズムパズル

アルゴリズムパズル
	初版
著者	アナニー・レヴィティン、マリア・レヴィティン
出版社	オックスフォード大学出版局
発行日	2011

『アルゴリズミック・パズルズ』は、計算論的思考に基づいたパズル集です。コンピュータ科学者のアナニー・レヴィティンとマリア・レヴィティンによって執筆され、2011年にオックスフォード大学出版局から出版されました。

トピック

本書は、バックトラッキング、分割統治法、動的計画法といった古典的なアルゴリズム設計手法、アルゴリズムの分析手法、そしてそれらの例題への応用を紹介する「チュートリアル」から始まります。^{[ 1 ]}^{[ 2 ]}パズル自体は、難易度順に50問ずつ3つのセットにまとめられています。最後の2章では、パズルの簡単なヒントとより詳細な解答が示され、^{[ 2 ]}本書の大部分は解答で構成されています。^{[ 3 ]}

いくつかのパズルはよく知られた古典的なパズルであり、いくつかは既知のパズルのバリエーションでよりアルゴリズム的なものになっており、いくつかは新しいものです。^{[ 4 ]}これらには以下が含まれます。

チェス盤を使ったパズル（8つのクイーンのパズル、ナイトのツアー、破損したチェス盤の問題など） ^{[ 1 ]}^{[ 3 ]}^{[ 4 ]}
バランスパズル^{[ 3 ]}
川渡りパズル^{[ 3 ]}^{[ 4 ]}
ハノイの塔^[⁴^]
データストリーム内の欠落要素の検出^{[ 1 ]}
マンハッタン距離の幾何中央値問題^[¹^]

観客と反応

この本に掲載されているパズルは幅広い難易度を網羅しており、一般的に高校レベル以上の数学の知識を必要としません。^{[ 3 ]}ウィリアム・ガサーチは、パズルをテーマではなく難易度でグループ化することは、読者に解答のヒントを少なくするため、実際には利点があると指摘しています。^{[ 1 ]}

評論家のナラヤナン・ナラヤナン氏は、本書をパズル愛好家やアルゴリズム思考力を伸ばしたいと考えているすべての人に推奨しています。^{[ 4 ]}評論家のマーティン・グリフィス氏は、アルゴリズム思考力の力を示す例を探している読者、教師、大学教員にも推奨しています。^{[ 3 ]} ガサーチ氏は、本書をあらゆるコンピューター科学者に推奨し、「素晴らしい」と評価しています。^{[ 1 ]}

参考文献

^ ^a ^b ^c ^d ^e ^f Gasarch, William (2013年12月)、「アルゴリズムパズルのレビュー」（PDF）、ACM SIGACT News、44（4）：47– 48、doi：10.1145/2556663.2556674
^ ^a ^bローズブロック、ステファン、「アルゴリズムパズルのレビュー」、zbMATH、Zbl 1233.00005
^ ^a ^b ^c ^d ^e ^fグリフィス、マーティン（2014年3月）、「アルゴリズムパズルのレビュー」、数学ガゼット、98（541）：188、doi：10.1017/S0025557200001182、JSTOR 24496640
^ ^a ^b ^c ^d ^eナラヤナン、ナラヤナン（2012）、「アルゴリズムパズルのレビュー」、数学レビュー、MR 2866446

[gasarch-1] ^ ^a ^b ^c ^d ^e ^f Gasarch, William (2013年12月)、「アルゴリズムパズルのレビュー」（PDF）、ACM SIGACT News、44（4）：47– 48、doi：10.1145/2556663.2556674

[rosebrock-2] ローズブロック、ステファン、「アルゴリズムパズルのレビュー」、zbMATH、Zbl 1233.00005

[griffiths-3] グリフィス、マーティン（2014年3月）、「アルゴリズムパズルのレビュー」、数学ガゼット、98（541）：188、doi：10.1017/S0025557200001182、JSTOR 24496640

[narayanan-4] ナラヤナン、ナラヤナン（2012）、「アルゴリズムパズルのレビュー」、数学レビュー、MR 2866446

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]