アルゴリズムを学ぼう
アスキー
著者：川中真耶、杵渕朋彦、椎名俊輔
はじめに
目次
第0講はじまり
明日木大学、入学式！
キャラクター紹介
伯方涼子（はかたりょうこ）
日比野萌来（ひびのめぐる）
澤戸うい（さわどうい）
倉科莉紗（くらしなりさ）
第1講 アルゴリズムと計算量
1.1 アルゴリズムをはじめよう！
1.2 アルゴリズムとは？
1.3 アルゴリズムを学ぶことの重要性
1.4 まずは肩慣らしの問題
1.4.1 二分探索
1.5 計算量
1.6 計算量の表わし方
1.7 計算量の求め方
1.8 ようこそ！ 技育部へ！
第2講 データ構造――初級編
2.1 アルゴリズム温泉！
2.2 基礎的なデータ構造
2.3 配列（Array）とベクター（Vector）
2.3.1 ベクター(Vector)
2.3.2 ベクターの挙動
2.3.3 配列・ベクター中の検索
2.4 連結リスト(Linked List)
2.4.1 連結リストの表わし方
2.4.2 連結リストへの要素の挿入
2.5 スタック、キュー
2.6 木
2.6.1 二分木（Binary Tree）
2.6.2 二分探索木
2.7 連なる花火はアルゴリズムの味
第3講 ソート
3.1 エアコン求めて三千里
3.2 並び替えのアルゴリズム
3.3 いろいろなソート
3.3.1 バブルソート
3.3.2 選択ソート
3.3.3 挿入ソート
3.4 マージソート
3.4.1 分割統治法
3.5 クイックソート
3.5.1 ピボット選択
3.6 ヒープソート
3.6.1 ヒープ
3.7 炎天下の延長戦・・・・・・？
第4講 グラフと探索
4.1 夏だ！ 海だ！ アルゴリズムだ！！
4.2 探索
4.3 グラフ
4.4 基本的な探索
4.4.1 深さ優先探索
4.4.2 幅優先探索
4.4.3 DFS とBFS の差
4.5 A* 探索
4.6 A* 探索で迷路を解く
4.7 メモ付き探索
4.8 夏の夕方はバーベキュー！
第5講 データ構造――上級編
5.1 ハロウィンの準備
5.2 ちょっと難しいデータ構造
5.3 平衡木
5.4 AVL木
5.4.1 AVL木へのノードの挿入
5.4.2 AVL木のノード
5.4.3 AVL木への挿入
5.4.4 AVL木へからのノードの削除
5.4.5 AVL木の高さの調節
5.5 赤黒木
5.5.1 赤黒木のノード
5.5.2 赤黒木への挿入
5.5.3 赤黒木からの削除
5.6 ユニオンファインド
5.7 ハッシュテーブル
5.7.1 オープンハッシュ法（チェインハッシュ法）
5.7.2 クローズハッシュ法（オープンアドレスハッシュ法）
5.8 ベストドレッサーは誰？
第6 講最短経路問題
6.1 クリスマスイブの暴走
6.2 最短経路問題
6.3 重み付きのグラフ
6.4 最短経路問題が使われるところ
6.5 グラフ上の最短経路のアルゴリズム
6.5.1 ベルマン・フォードのアルゴリズム
6.5.2 ダイクストラのアルゴリズム
6.5.3 ワーシャル・フロイドのアルゴリズム
6.6 クリスマスプレゼント
第7講 グラフの上級アルゴリズム
7.1 倉科莉紗の優雅なお正月
7.2 ちょっと難しいグラフのアルゴリズム
7.3 最小全域木
7.3.1 プリムのアルゴリズム
7.3.2 クラスカルのアルゴリズム
7.4 最大フロー問題
7.4.1 残余ネットワーク
7.4.2 エドモンズ・カープのアルゴリズム
7.5 二部グラフの最大マッチング
7.6 お年玉争奪戦場外乱闘
第8講 NP完全問題
8.1 ぼくの かんがえた さいきょうの チョコレート
8.2 NP完全と決定問題
8.3 PとNP
8.4 NP完全問題
8.5 代表的なNP完全問題
8.5.1 SAT
8.5.2 ナップサック問題
8.6 動的計画法と擬多項式時間アルゴリズム
8.6.1 動的計画法
8.7 近似解法
8.7.1 トラベリングセールスマン問題
8.8 名状しがたいチョコレートのようなもの
第9講暗号（前編）
9.1 伯方涼子の実力
9.2 アルゴリズムを支える数学
9.3 暗号とは
9.3.1 定義と例
9.3.2 暗号に必要な要件
9.3.3 用語と概念
9.4 単純な暗号（換字式暗号）
9.4.1 カエサル暗号
9.4.2 攻撃方法の分類
9.4.3 運用に対する攻撃
9.4.4 総当たりによる攻撃（理論に基いた攻撃）
9.4.5 出現頻度による攻撃（理論に基づいた攻撃）
9.5 対称鍵暗号
9.5.1 用語と概念
9.6 DESとそのアルゴリズム
9.6.1 鍵を用意する
9.6.2 鍵作成の流れ
9.6.3 鍵の分割
9.6.4 左巡回シフト
9.6.5 鍵の連結
9.6.6 平文の暗号化の流れ
9.6.7 初期置換と最終置換
9.6.8 拡張処理
9.6.9 鍵とXOR を取り、S ボックスで変換
9.6.10 XOR を取り、並べ替え
9.6.11 攻撃方法
9.6.12 対称鍵暗号の問題点
9.7 暗号の奥深さ
第10講暗号（後編）
10.1 アルゴリズム部門、決戦！
10.2 暗号とは（復習）
10.3 公開鍵暗号
10.3.1 落とし戸関数とは
10.4 べき乗と離散対数
10.4.1 余りを考えたべき乗
10.4.2 べき乗とRSA 暗号
10.4.3 オイラーのφ関数とその計算量
10.4.4 離散対数問題
10.4.5 ディフィー・ヘルマン鍵共有
10.5 楕円曲線暗号
10.5.1 楕円曲線
10.5.2 離散対数問題
10.5.3 楕円曲線上でのディフィー・ヘルマン鍵共有
10.6 破られる可能性がある暗号
10.7 決着
第11講エピローグ
11.1 大会を終えて
索引
著者プロフィール