フルカラーでわかりやすい! 基礎から学べる1冊

アルゴリズムは、プログラミングを用いて問題を解決していくには欠かせない大切な道具です。一方、アルゴリズムを理解し、そして応用できるようになるためには、ある程度の数学的知識と数学的考察力も大切です。

本書では、中学レベル~大学教養レベルの数学的知識のうちアルゴリズム学習に必要なものについて扱うとともに、有名なアルゴリズムと典型的な数学的考察について丁寧に解説します。さらに、知識をしっかり身に付けるための例題・演習問題が全200問掲載されています。

本書では中学レベル〜大学教養レベルの数学的知識のうちアルゴリズム学習に必要なもの、有名なアルゴリズム、典型的な数学的考察について丁寧に解説します。

フルカラーの解説図を多数掲載。文章の解説だけではわかりづらいアルゴリズム・数学の知識やしくみも、理解しやすくなっています。

全200問の例題・演習問題を通じて、学んだ知識をしっかり身につけることができます。例題・演習問題のうちプログラミング問題については、プログラムが正しいかを判定するための自動判定システムを用意しました。誌面にはC++のサンプルコードを掲載。ほかに、Python・Java・Cのコードを入手可能です。

(目次)

第1章 アルゴリズムと数学の密接なかかわり

1.1 アルゴリズムとは

1.2 なぜアルゴリズムに数学が必要か

1.3 本書の構成/本書による学習について

1.4 本書で扱うアルゴリズム

1.5 本書で扱う数学的知識と数学的考察

第2章 アルゴリズムのための数学の基本知識

2.1 数の分類・文字式・2進法

2.2 基本的な演算と記号

2.3 いろいろな関数

2.4 計算回数を見積もろう ~全探索と二分探索~

2.5 その他の基本的な数学の知識

第3章 基本的なアルゴリズム

3.1 素数判定法

3.2 ユークリッドの互除法

3.3 場合の数とアルゴリズム

3.4 確率・期待値とアルゴリズム

3.5 モンテカルロ法 ~統計的な考え方~

3.6 ソートと再帰の考え方

3.7 動的計画法 ~漸化式の利用~

第4章 発展的なアルゴリズム

4.1 コンピュータで図形問題を ~計算幾何学~

4.2 階差と累積和

4.3 ニュートン法 ~数値計算をやってみよう~

4.4 エラトステネスのふるい

4.5 グラフを使ったアルゴリズム

4.6 効率的な余りの計算

4.7 行列の累乗 ~フィボナッチ数列の高速計算~

第5章 問題解決のための数学的考察

5.1 なぜ数学的考察が大切か

5.2 規則性を考える

5.3 偶奇に着目する

5.4 集合を上手く扱う

5.5 ギリギリを考える

5.6 小問題に分解する

5.7 足された回数を考える

5.8 上界を考える

5.9 次の手だけを考える ~貪欲法~

5.10 その他の数学的考察

最終確認問題

■本書で扱うアルゴリズム(「1.4節」より)

「全探索」「二分探索」「組合せの全探索」「素数判定法」「約数列挙」「ユークリッドの互除法」「モンテカルロ法」「選択ソート」「再帰関数」「分割統治法」「マージソート」「動的計画法」「配列の二分探索」「計算幾何」「累積和」「ニュートン法」「エラトステネスのふるい」「深さ優先探索」「幅優先探索」「繰り返し二乗法」「行列累乗の計算」「勾配降下法」「貪欲法」「A*」

■本書で扱う数学的知識と数学的考察(「1.5節」より)

「数の分類」「文字式」「2進法・3進法」「累乗・ルート」「ビット演算」「一次関数」「二次関数」「多項式関数」「指数関数」「対数関数」「ランダウのO記法」「素数」「最大公約数・最小公倍数」「数列の基本」「集合の基本」「必要条件と十分条件」「絶対誤差と相対誤差」「シグマ記号」「背理法」「積の法則」「階乗と二項係数」「確率と期待値」「期待値の線形性」「平均と標準偏差」「正規分布」「再帰的定義」「数列の漸化式」「平面ベクトル」「微分法」「積分法」「グラフ理論」「合同式」「モジュラ逆数」「行列」「三角関数」

「規則性を考える」「偶奇に着目する」「余事象を考える」「包除原理」「ギリギリを考える」「小問題に分解する」「足された回数を考える」「上界を考える」「次の手だけを考える」「誤差とオーバーフロー」「分配法則」「対称性を使う」「一般性を失わないことを使う」「条件の言い換え」「状態数を考える」