アルゴリズムを学ぼう

関連サイト

出版社による関連ページが公開されています。

• アルゴリズムを学ぼう (KADOKAWA/アスキー・メディアワークス)

関連書籍

本書の続編『続・アルゴリズムを学ぼう』も好評発売中です。

続・アルゴリズムを学ぼう【電子書籍】

川中真耶, 杵渕朋彦, 椎名俊輔
KADOKAWA/アスキー・メディアワークス
発行日: 2013-08-02
対応フォーマット: PDF,EPUB

詳細を見る

内容紹介

本書のテーマは、ガチのアルゴリズムとデータ構造、そして計算量です。

いや、確かに本書は女の子がいろいろでてきたり、小話が入っていたりと、ゆるふわなオーラが漂っています。しかし、あえていいましょう。それは、見かけだけである、と。

プログラミングを学ぶにあたって、アルゴリズムとデータ構造は、どの言語を用いるにしてもすべての基礎であり、避けて通ることはできない道です。アルゴリズムとデータ構造を知らずにプログラムを書くことは、無免許で車を運転するぐらいに危険な行為です。

しかし、アルゴリズムとデータ構造をきちんと理解せずに、プログラムを書いているプログラマーが多数いるのも事実です。それは、アルゴリズムが自分で書けないということだけを意味しているのではありません。アルゴリズムは、使うだけでもそのアルゴリズムに対する理解を要求するのです。あるアルゴリズムを実装しているライブラリがあったとしても、単にライブラリを呼んでおしまいではありません。そのアルゴリズムの計算量がどうなっているのか、どういう特性があるのかを理解していなければ、正しくそのアルゴリズムを使いこなすことはできないのです。

(「はじめに」より抜粋)

書誌情報

• 著者: 川中真耶, 杵渕朋彦, 椎名俊輔
• 発行日: 2012-06-01
• 最終更新日: 2013-03-01
• バージョン: 1.1.0
• ページ数: 272ページ(B5PDF版換算)
• 対応フォーマット: PDF, EPUB
• 出版社: KADOKAWA/アスキー・メディアワークス

対象読者

アルゴリズムを学びたい人、とりわけ(擬似コードじゃない)コードと日本語の両方でアルゴリズムをわかりやすく説明してほしい人、TAOCPやコルメン本はちょっとしんどそうなので避けたい人

著者について

川中真耶

某大手検索会社勤務。ふだんWebKit のコードを書く日々。そのうち関数型言語と、自分の作ったサービスで世界を征服したいと思っている。

杵渕朋彦

潜水艦っぽい名前の会社勤務。最近は、プログラミングより開発環境の構成管理のほうがたのしい。知的好奇心に従って生きたい。

椎名俊輔

某パッケージソフトウェア開発会社に勤務。先端技術を調べたり、使ったりしている。現在は、おもにクラウド上のアプリの運用がメイン。技術の変化を最先端で見ていたい。

目次

はじめに

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

索引

著者プロフィール