おもしろいと思った本の紹介

# はじめに

自分用のメモも含めて、よかった本をメモしたいと思う。

# 本棚

## よく読んだ本

### クラウドを支えるこれからの暗号技術

- http://amzn.asia/iX8Yrex （Amazon）
- https://herumi.github.io/ango/ （PDF）

最も読んだ暗号の本で、PDFが無料で公開されているので必ずしも買う必要はない。結城先生の暗号本の次とかに読むとよい本で、暗号技術の基礎からIDベース暗号や検索可能暗号、準同型暗号といった高機能暗号について数学的背景を交えつつ丁寧に解説してある。

### 暗号と確率的アルゴリズム入門

- http://amzn.asia/hgq3uTt （Amazon, 絶版）

この本はコミットメントや公平な選挙について解説されたなかなかめずらしい本だったが、残念なことに絶版なので中古で手に入れるしかない。一方性関数や暗号アルゴリズムに関する証明についても言及されており、かつて暗号プロトコルを作るときに大変役だった。

### 暗号技術入門（第三版）

- http://amzn.asia/es8EmN0 （Amazon）

結城先生の有名な暗号技術に関する本で、主に暗号技術の基礎的な部分を解説している。RSA暗号やDH鍵交換などを平易な説明で解説している良書。実は僕は高校生のときにこの本の第二版をたまた買ってPHPというプログラム言語でDH鍵交換を実装し、それをレンタルサーバーにデプロイして学校のインターネット検閲を無力化するというプログラムを実装して、それで大学の入試（AC）に合格したのでこの本には特別な思い入れがある。

### 型システム入門（通称 TaPL）

- http://amzn.asia/fiLOPBZ （Amazon）

大学の学部4年生のときの輪講で取り扱い、かつて前職ではこれの勉強会をした。型システムのよく知られた教科書である。型システムとは何か？からはじまり、型なしラムダ計算、それに最も単純な型を入れた単純型付きラムダ計算といったように少しずつ言語の表現力を拡張していく。この本によって新しいプログラム言語の機能もわりと「TaPLのアレが実装されているのね」みたいになるかも。ちなみに“型安全”とは？と誰かに聞かれたら「進行と保存が成り立つことです」と言っておけばツウ（この本を読んだ人）に見える。

### Scala関数型デザイン&プログラミング（通称 FP in Scala）

- http://amzn.asia/2FcyUJt （Amazon）

Scalaの基礎的な文法からはじまり、パーザーや並列処理データ構造の作製を通してファンクターやモナドといった抽象化について学習できる。Scalaで関数型プログラムをやるならば読んでおいて損はない。最後の方の練習問題はかなり難しくて解けないものも多かった。

### 正規表現技術入門

- http://amzn.asia/1CSfUmR （Amazon）

正規表現について背景となるオートマトン理論からRubyに実装されたエンジンの実装まで、理論と実践の両方が書いてある。著者の新家さんは現在秋田大学の助教で、かつては世界でもっとも速い正規表現のエンジンを実装していた。僕はこの本を読んで正規表現のLLVMコンパイラーやJVMへのJITコンパイラーをScalaで実装したことがあり、そのときには非常に役に立った。

### 折り紙のすうり

- http://amzn.asia/aLiSLMA （Amazon）

リンケージ（二次元の棒を1以上の数で接続したもの）や折り紙、そして多面体について次元を行ききするような議論がどんどん展開されていく非常におもしろい本であった。組版も綺麗なカラー刷りで図も豊富な良書だと思う。多面体というのは、たとえばデータ構造で有名な赤黒木よりも数千年といった単位で歴史があるにも関わらず、こんなにも未解決な問題が多いのか！と驚かされる本である。暗号と絡めて、なにか新しい研究のあしがかりにしたい。

### 観測に基づく量子計算

- http://amzn.asia/hfD473M （Amazon）

ゲート型量子計算とは異なる万能量子計算が可能なモデルの解説本で、ブラインド量子計算（セキュアクラウド量子計算）に関する最も詳しい和書であると思う。古典計算機では入力を秘密にしたまま計算を行うためにガーブルドサーキットといった特別な道具が必要となるが、量子計算ではそういうものなしでできるというのが素晴しい。

### ゲームとパズルの計算量

- http://amzn.asia/efJTBHe （Amazon）

ゲームやパズルの中に潜む、オートマトンといった計算機科学の抽象化を明らかにしていく本である。著者のエリック・ドメインは「計算折り紙（Computational Origami）」のパイオニアーであり、折り紙の本も出している。僕はこの本を読んで「量子コンピューターでは容易に解ける一方で古典コンピューターでは正しさの検証しかできないゲーム」を考案できれば、人間のゲーム能力が量子的か古典的かどうかを検証できるのではないか？と考えるきっかけとなった。

### 量子計算理論

- http://amzn.asia/dQGOpSU （Amazon）

森前先生の量子計算に関する本で、量子計算の基礎から計算量やセキュアクラウド量子計算などについて書かれている。古典計算機をベクトル計算として導入し、それを拡張して量子計算をはじめる説明はかなり気にいった。中盤からは測定型量子計算や量子計算量理論といった分野について詳しく説明し、さらに超量子計算や非ユニバーサル量子計算についてそれらがどのような意味を持つかについても解説している。量子計算の入門書として大変よい本であると思う。

### 計算折り紙入門

- http://amzn.asia/6I9hVvW （Amazon）

計算折り紙という新しい計算モデルに関する本であり、多面体の展開や多角形の敷き詰めといった問題からはじまり、折り計算量や折り判定問題といったコンピューターの関わりの深いテーマについて折り紙の上でそれらがどうなるかについて述べている。折り紙の理論はこの本のスコープ外になるかもしれないが、たとえば折り線と結果の立体には準同型性があるといったことも分っており、立体を利用した新たな暗号が考案できるのではないかと僕は時々考えている。

## そこそこ読んだ本

### 量子プログラミングの基礎

- http://amzn.asia/jcmcr3Y （Amazon）

量子計算の界隈ではいまでも量子回路をいじっているが、複雑なアルゴリズムを回路で記述するのは大変なので、量子コンピューターの上で動作する高級言語を作ろうという趣旨の本。量子計算と線形代数の知識がないとなかなか読むのがキツいかもしれない。while言語に量子ビットを突っ込んだけどこれだと`if`文とか再帰とかが量子的な並行にならないので、量子的並行が可能な言語を最終的に作るらしい。

### 言語の数理

- http://amzn.asia/0c3EtWN （Amazon, 絶版）

電通大図書館の古本市で入手した本で、オートマトンといった形式言語の技術で自然言語に挑むというテーマの本である。形式言語に関する基礎的な説明と、自然言語の研究などがまとまっている。

### ガベージコレクション

- http://amzn.asia/ehDKtzG （Amazon）

筑波大学時代におせわになった前田先生が監修しているGCに関する本で、発売日に買った。よく知られたGCアルゴリズムからはじまり、発展的なGCの話題へ進んでいく。よく知られた部分の解説を読んで満足してしまい、中盤以降はほとんど読んでいない。

### オークション理論の基礎

- http://amzn.asia/iUv7QOL （Amazon）

暗号をやっていてゲーム理論やオークション理論に興味が出たので買った。ナッシュ均衡といった基礎的なことからはじまり、そこまで数学書感を出さずに進んでいく。最後には秘密分散を利用した入札が分からない公平なオークションに言及している。個人的にはもうちょっと形式的にしてもよかったと思った。

### 純粋関数型データ構造（通称 PFDS）

- http://amzn.asia/he0lNsq （Amazon）

原著はとんでもない引用数を誇る関数型データ構造のよく知られた教科書である。翻訳はプロコンで活躍するGoogleの稲葉さんと、TaPLの翻訳で知られる遠藤さん。フィボナッチヒープや赤黒木といった基本的なデータ構造について説明して、各操作に関する計算量に関して学び、遅延評価が計算量に与える影響や、そもそも平均計算量ではない償却計算量を導入する。データ構造について興味がある人は読むとおもしろいと思う。

### ドクター・ハルの折り紙数学教室

- http://amzn.asia/2Z5sqa0 （Amazon）

こちらの本はリンケージや多面体というより、純粋に折り紙に焦点を絞った本である。たとえば「折り線が対象ならば、折ったあとの図形も対象性を持つ」といった折り紙における準同型性について言及したりするようだ。準同型といえば準同型暗号しか思いつかないので、折り紙を使った暗号技術をなんか作れるのではないかと期待している。

### Continuations and Natural Language

- http://amzn.asia/7VERdrb （Amazon）

継続を使って自然言語に意味を与えたりするというのをどこかで聞いたことがあって、それで買ったものの英語を雰囲気でしか読めないためあまり理解できなかった。そのあと電通大で入手した言語の数理を読んでちょっと読むことができた。第二著者のChung Chieh Shanさんはかつて亀山研にいたOlegさんとよく共著で論文を書いていたというのも買った理由のひとつ。

### The Reasoned Schemer: 2nd Edition

- http://amzn.asia/5ZLKXWA （Amazon）

研究室にかつていたOlegさんらが執筆した本であり、それの2nd Editionが出ていたので購入した。MIT Pressから買ったらひどいめにあったので、Amazonで買うほうがいいだろう。Kindle版の組版もしっかりしており、なかなかおもしろい。Prologとかその手の論理プログラミングに興味があれば、おもしろく読めるだろう。

# まとめ

ここに載っていない本も実はたくさん買って放置しています。個人的な意見ですが、本を買ったらその代金を取り戻すために全部読まなければならないとか、今放置している本があるのに新しい本を買うなんてだめだ、といった考えは必要ないと思います。1年前に買った本が何かのきっかけで読めるようになったり、Twitterで流れてきたスライドで放置していた分野に火がつくこともあるでしょう。僕としては本に関しては「とりあえず買う」ことにしていて、気がむいたら読めばよいと思っています。そしてよい本があればどんどん紹介していくとよいと思います。