| 第1話 計算を分解してみよう 1 |
| デジタル化,プログラム,そして計算とは何かについて |
| 1.1 データの基本単位 1 |
| 基本的なデータを表わす |
| どんな大きな数でも表わせるの? |
| 複数のデータを表わす |
| 1.2 アルゴリズムとプログラム 12 |
| 計算⇒アルゴリズム⇒プログラム |
| アルゴリズムを簡単に記述する方法:言語SL |
| プログラムの例 |
| 1.3 アルゴリズムの基本要素 25 |
| 計算に本当に必要なもの:言語PL |
| 本当にこれだけで十分なの? |
| すべての計算を言語PLで表わすことができるとは? |
| 第2話 計算を組み立ててみよう 41 |
| アルゴリズムとその効率の重要性について |
| 2.1 アルゴリズムの良し悪しは天国と地獄の差 41 |
| シラミつぶし的アルゴリズム |
| ユークリッドの互除法 |
| 計算コストの評価方法 |
| 2.2 小さく見える差でも 55 |
| ソート問題と素朴な解法 |
| 再帰:アルゴリズム設計の強力な武器 |
| 再帰を使って整列アルゴリズムを設計する |
| 2.3 難しそう...でも諦めないで! 66 |
| 石選び問題 |
| シラミつぶし的解法:指数関数は恐ろしい |
| なんとかなる場合もある |
| それでも工夫は無駄ではない |
| 第3話 計算の限界を知ろう 79 |
| 計算,現実的計算,精度などの限界について |
| 3.1 計算不可能性:どうしても計算できないことだってある 79 |
| 関数とプログラム |
| 計算不可能性の最初の例:停止性判定問題 |
| 計算不可能性証明ができてしまった訳は?! |
| その他の計算不可能問題 |
| 3.2 現実的計算不可能性:原理的に可能でも現実には 89 |
| 多項式時間:非現実的の基準? |
| NP問題:コロンブスの卵のような問題 |
| NP問題の計算の難しさ |
| 3.3 明らかな不可能性:有限に由来する限界 102 |
| 無限の精度なんてありえない! |
| 真の乱数なんてありえない! |
| 第4話 計算化してみよう 115 |
| 問題の形式化やモデル化の重要性について |
| 4.1 計算化するには? 115 |
| 問題を明確にすることの難しさ |
| 明確化のための道具 |
| 4.2 二次元迷路を解く 123 |
| 問題の説明 |
| コンピュータで扱いやすい問題にする |
| 二次元迷路問題(計算版)のためのアルゴリズム |
| 参考文献 134 |
| 演習問題解答 137 |
| 索引 150 |
| おまけの知識 |
| 1.様々な圧縮技術 5 |
| 2.プログラミング言語概観 16 |
| 3.機械語 コンパイラとインタープリタ 40 |
| 4.公開鍵暗号とナップサック暗号 77 |
| 5.擬似乱数で暗号? 114 |
| 6.コンピュータ・サイエンスと言語学 118 |
| 第1話 計算を分解してみよう 1 |
| デジタル化,プログラム,そして計算とは何かについて |
| 1.1 データの基本単位 1 |
| 基本的なデータを表わす |
| どんな大きな数でも表わせるの? |
| 複数のデータを表わす |
