アルゴリズム

アルゴリズムを学ぼう

川中真耶
杵渕朋彦
椎名俊輔

アスキー・メディアワークス

はじめに

第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 大会を終えて

索引
著者プロフィール