genkai-shobo.jp
KS情報科学専門書

問題解決力を鍛える!アルゴリズムとデータ構造


著者:大槻兼資/著 秋葉拓哉/監修
価格:3,000円+税
刊行日:2020/10/02

出版社:講談社
ISBN:978-4-06-512844-2
Cコード:3055
[単行本](電子通信)

入門書を標榜しながら、AtCoderの例題、C++のコードが充実。入門書であり実践書でもある、生涯役立つテキストを目指した



内容紹介


★この本を買わずして何を買う!!★

競技プログラミング経験が豊富な著者が、「アルゴリズムを自分の道具としたい」という読者に向けて執筆。入門書を標榜しながら、AtCoderの例題、C++のコードが充実。入門書であり実践書でもある、生涯役立つテキストを目指した。

【推薦の言葉】
プログラムが「書ける」ことと、効率の良い結果を得ることには大分ギャップがある。本書は、どのようにすれば効率のよい結果が得られるか? すなわちどのようなアルゴリズムを採用すればよいか? という点に対して、幅広くかつ明快に解説している。
また本書は、アルゴリズム初心者に対して、アルゴリズムへの興味を惹かれるように記述されている。アルゴリズム上級者への初めの一歩には最適であろう。
――河原林健一(国立情報学研究所副所長)

【全体を通して、アルゴリズムの設計技法を重視した構成】
まず、1、2章でアルゴリズムと計算量について概観します。そして、3~7章が、早くも本書のメインパートといえる部分であり、「アルゴリズムの設計技法」について詳しく解説します。これらの設計技法に関する話題は、多くの書籍では、最後の方で簡単に説明しています。しかし本書は、現実世界の問題を解決するための実践的なアルゴリズム設計技法の鍛錬を目指しています。そこで、アルゴリズム設計技法について前半で詳しく解説する構成としました。そして、これらの設計技法が後半の章でも随所に使われていくことを示していきます。

その後、8~11章では、設計したアルゴリズムを効果的に実現するうえで重要となるデータ構造を解説します。データ構造について学ぶことで、アルゴリズムの計算量を改善したり、また、C++やPythonなどで提供されている標準ライブラリの仕組みを理解して、それらを有効に活用したりすることができるようになります。

そしていったん、12章でソートアルゴリズムについての話題を挟んだ後に、13~16章でグラフアルゴリズムについて解説します。グラフは、非常に強力な数理科学的ツールです。多くの問題は、グラフに関する問題として定式化することで、見通しよく扱うことができるようになります。また、グラフアルゴリズムを設計するとき、3~7章で学ぶ設計技法や、8~11章で学ぶデータ構造が随所で活躍します。

最後に、17章で PとNPに関する話題を解説し、世の中には「効率的に解くアルゴリズムを設計することができそうにない難問」が多数あることを見ます。18章で、これらの難問に取り組むための方法論をまとめます。ここでも、動的計画法 (5章) や貪欲法 (7章) といった設計技法が活躍します。

もくじ

1章 アルゴリズムとは
2章 計算量とオーダー記法
3章 設計技法(1):全探索
4章 設計技法(2):再帰と分割統治法
5章 設計技法(3):動的計画法
6章 設計技法(4):二分探索法
7章 設計技法(5):貪欲法
8章 データ構造(1):配列、連結リスト、ハッシュテーブル
9章 データ構造(2):スタックとキュー
10章 データ構造(3):グラフと木
11章 データ構造(4):Union-Find
12章 ソート
13章 グラフ(1):グラフ探索
14章 グラフ(2):最短路問題
15章 グラフ(3):最小全域木問題
16章 グラフ(4):ネットワークフロー
17章 PとNP
18章 難問対策

大槻 兼資

現在、株式会社NTTデータ数理システム所属。 雑誌「Software Design」にて、「パズルで鍛えるアルゴリズム力」の連載を執筆している。その他 Qiita などで、アルゴリズム関連の話題を解説する啓蒙活動を推進中。競技プログラミングには現在も趣味の一環として参加している。

秋葉 拓哉

現在、株式会社Preferred Networks執行役員。機械学習システム、大規模並列分散機械学習の研究開発に従事。 著書に『プログラミングコンテストチャレンジブック 第2版』マイナビ(2012)などがある。学生時代には競技プログラミングに夢中になり、国内大会では優勝多数、国際決勝大会への出場を10度以上経験。