本棚登録 : 
感想 : 
http://kashiwabaray.com/blog/index.php?itemid=355
厳選した9つのアルゴリズムについて、分かりやすくイメージを説明しています。どちらかというと、初心者向けの1冊となりますので、専門知識を持っている人には少し物足りない内容だと思います。文系の方でも十分読める内容となっています。
■オープンな場で「共有された秘密」を作る方法
この方法を「ディフィー＝ヘルマン鍵交換」と呼んでいるが、私たちは「絵具混合トリック」と呼ぶことにしよう。
－絵具混合トリック
ステップ１ あなたとアーノルドは、「秘密の色」と呼ぶ。
ステップ２ あなたかアーノルドが、これらとは異なる色の作り方を公表する。この色を「公開色」と呼ぶことにする。
ステップ３ あなたとアーノルドは、それぞれ公開色1壺と秘密色1壺を混ぜた絵具を作る。こうすると、「公開秘密混合色」が作られる。
ステップ４ 部屋の中央からアーノルドの公開秘密混合色の絵具を手に入れて自分の秘密スペースに持ち帰る。
その絵具に自分の秘密色の壺を1つ混ぜる。一方、アーノルドはあなたの公開秘密混合色を自分の秘密スペースに持ち帰り、自分の秘密色の絵具を1壺それに混ぜる。
―数値による絵具混合
ステップ１ あなたとアーノルドは、それぞれ「秘密の色」の代わりに「秘密の数値」を選ぶ。
ステップ２ 2人のどちらかが「公開の数値」（絵具混合トリックのときの公開色の代わり）を公表する。
ステップ３ 秘密の数値（４）と公開の数値（７）を掛け合わせて、「公開秘密混合値」の28を得る。アーノルドも、自分の秘密の数値について同じことを行う。6×7で42という公開秘密混合値を発表する。
ステップ４ アーノルドの公開秘密混合値の42を取り、それに自分の秘密の数値である4を掛け、「共有された秘密値」である168を得る。
一方、アーノルドはあなたの公開秘密混合値の28を取り、自分の秘密の数値の6を掛け、28×6=168で、驚くべきことに同じ「共有された秘密値」を得る。
実際に使われている絵具混合
完全なものにするためには、簡単に実行できて（絵具を混ぜ合わせるように）、取り消しが実質的に不可能な（絵具の分解のように）数学処理が必要である。コンピュータで実際にこれを行うとき、混合処理は「離散べき乗」、分解処理は「離散対数」と呼ばれる。
通鍵暗号方式における鍵の受け渡しを安全に行うために提案されたDiffie-Hellman鍵共有。絵具混合という方法によってわかりやすく説明されている。イメージがつかみやすい説明で一度イメージを掴めば忘れないだろう。
■誤り検出と誤り訂正のニーズ
コンピュータには、基本的な仕事が3つある。もっとも重要な仕事は、計算を実行することだ。コンピュータが実行するほかの２つの非常に重要な仕事がなければ、答えを計算できる能力があっても何の役にも立たないだろう。その２つとは、データを保存する仕事とデータを伝送する仕事だ。
20Mバイトのプログラムをダウンロードしたときに、システムが100万字に1つずつ解釈を誤ったとすると、ダウンロードしたプログラムには20個を超える誤りが含まれることになる。これらの誤りは、どれも予想外のタイミングでシステムをクラッシュさせる要因になり得る。
誤り検出、誤り訂正は大学でも学んだ分野。こちらも誰でもイメージが掴めるように説明をしている。もう少し深く知りたいと思う分野であったため、内容は少し物足りないものだったが、概要を思い出すには十分であった。
■ロスなし圧縮 ― 究極のフリーランチ
コンピュータは、「ロスなし」と「ロスあり」の２つの大きく異なるタイプの圧縮を使っていることをまず覚えておこう。ロスなし圧縮アルゴリズムは、データファイルを受け付けると、もとのサイズの数分の1に圧縮する。そして、圧縮を解除するとまったく同じものが復元される。ロスあり圧縮は、圧縮を解除したあと、もとのファイルとは少し違うものになってしまう。
ロスなし圧縮を見ていこう。基本的なアイデアは、互いに同じになっている部分を見つけ、何らかのトリックを使ってその部分をもっと効率よく記述するということだ。データに反復が含まれているときには、このような圧縮は特に簡単である。このトリックをRLEと呼んでいる。反復する一続きの部分（run）に反復の長さ（length）を添えて符号化（encoding）しているという意味だ。
RLEの最大の問題点は、データ内の反復箇所が隣り合っていなければならないことである。そこで、コンピュータ科学たちは、基本的な発想をそのまま使いつつ、反復が隣り合っていなくてもうまく機能するより高度なトリックをいくつも考え出した。「前と同じ」、「より短いシンボル」の2つだけを見ていく。
―「より短いシンボル」のトリック
よく使われる文字については短いコードを使うようにしてみよう。一部のコードを長くするのである。
ステップ１ 「前と同じ」のトリックを使ってもとの圧縮されていないファイルを変換する。
ステップ２ 変換後のファイルを解析して、頻繁に登場するシンボルを見つける。頻繁に使われるシンボルには短い数値コード、あまり使われないシンボルには長い数値コードを与える。
ステップ３ ステップ２で作った数値コードを使ってファイルを変換する。
圧縮も興味深い分野の１つ。こちらもイメージを掴めるように、とても分かりやすく説明されている。これももう少し深くまで入っていきたい分野だったので、もう少し他の専門書で学んでみたいと思う。
【1読書1アウトプット】
イメージを大事にする
0
- 感想投稿日 : 2014年1月4日
- 読了日 : 2013年11月16日
- 本棚登録日 : 2013年11月1日
みんなの感想をみる
