投稿元:
レビューを見る
ページランキングn説明は面白かったが、公開鍵暗号についてはサイモン・シンの「暗号解読」の方が分かりやすかった。事実により近い説明は本書なんだろうけど。
投稿元:
レビューを見る
・普通のコンピュータユーザーが毎日使っている。
・現実の世界の具体的な問題を解決する。
・CPUやネットワークなどのハードウェアではなくコンピュータ科学理論に関係がある。
この3つの基準を満たすという条件で、世界でもっとも強力なアルゴリズムを9つ選んでいる。タイトルの原文は"Nine Algorithms that Changed the Future"となっている。原文どおり”未来を変えた”と言った方が何が基準であるかがわかりやすいかもしれない。
9つは次の通りで読者は専門家でない一般のコンピュータユーザを対象としている。
1. 検索エンジンのインデクシング
2. ページランク
3. 公開鍵暗号法
4. 誤り訂正符号
5. パターン認識
6. データ圧縮
7. データベース
8. デジタル署名
9. 決定不能性
難しい前提知識は必要なく、一般的な知識と論理だけで説明されていて非常にわかりやすい。公開鍵暗号法では素因数分解と言ってしまえば分かる人が多いと思うが、それは使わず”混ぜた絵具”で説明しているということでもそれがわかる。
この本ではアルゴリズムの中心となる部分を”トリック”とよんでいる。そのため、話の展開が手品の種明かしのように進み、より話に惹きつけられる。
基本的にはコンピュータを仕事としている者として知っていて当たり前な内容だ。しかし、恥かしながら、成程と思うところが多数あった。検索エンジンのインデクシングではフレーズ(句)の検索のトリックは知らなかった。当然であるが、フレーズそのものがインデックスと登録されているというトリックではなかった。
一番興味深かったのはパターン認識の部分である。ニューラルネットワークを使い決定木を解くというアルゴリズムを初めて理解した。
知識が定着していない若手IT技術者に是非薦めたい。
写真: 【世界でもっとも強力な9つのアルゴリズム】・普通のコンピュータユーザーが毎日使っている。・現実の世界の具体的な問題を解決する。・CPUやネットワークなどのハードウェアではなくコンピュータ科学理論に関係がある。 この3つの基準を満たすという条件で、世界でもっとも強力なアルゴリズムを9つ選んでいる。タイトルの原文は"Nine Algorithms that Changed the Future"となっている。原文どおり”未来を変えた”と言った方が何が基準であるかがわかりやすいかもしれない。 9つは次の通りで読者は専門家でない一般のコンピュータユーザを対象としている。 1. 検索エンジンのインデクシング 2. ページランク 3. 公開鍵暗号法 4. 誤り訂正符号 5. パターン認識 6. データ圧縮 7. データベース 8. デジタル署名 9. 決定不能性 難しい前提知識は必要なく、一般的な知識と論理だけで説明されていて非常にわかりやすい。公開鍵暗号法では素因数分解と言ってしまえば分かる人が多いと思うが、それは使わず”混ぜた絵具”で説明しているということでもそれがわかる。 この本ではアルゴリズムの中心となる部分を”トリック”とよんでいる。そのため、話の展開が手品の種明かしのように進み、より話に惹きつけられる。 基本的にはコンピュータを仕事としている者として知っていて当たり前��内容だ。しかし、恥かしながら、成程と思うところが多数あった。検索エンジンのインデクシングではフレーズ(句)の検索のトリックは知らなかった。当然であるが、フレーズそのものがインデックスと登録されているというトリックではなかった。 一番興味深かったのはパターン認識の部分である。ニューラルネットワークを使い決定木を解くというアルゴリズムを初めて理解した。 知識が定着していない若手IT技術者に是非薦めたい。
投稿元:
レビューを見る
http://kashiwabaray.com/blog/index.php?itemid=355
厳選した9つのアルゴリズムについて、分かりやすくイメージを説明しています。どちらかというと、初心者向けの1冊となりますので、専門知識を持っている人には少し物足りない内容だと思います。文系の方でも十分読める内容となっています。
■オープンな場で「共有された秘密」を作る方法
この方法を「ディフィー=ヘルマン鍵交換」と呼んでいるが、私たちは「絵具混合トリック」と呼ぶことにしよう。
-絵具混合トリック
ステップ1 あなたとアーノルドは、「秘密の色」と呼ぶ。
ステップ2 あなたかアーノルドが、これらとは異なる色の作り方を公表する。この色を「公開色」と呼ぶことにする。
ステップ3 あなたとアーノルドは、それぞれ公開色1壺と秘密色1壺を混ぜた絵具を作る。こうすると、「公開秘密混合色」が作られる。
ステップ4 部屋の中央からアーノルドの公開秘密混合色の絵具を手に入れて自分の秘密スペースに持ち帰る。
その絵具に自分の秘密色の壺を1つ混ぜる。一方、アーノルドはあなたの公開秘密混合色を自分の秘密スペースに持ち帰り、自分の秘密色の絵具を1壺それに混ぜる。
―数値による絵具混合
ステップ1 あなたとアーノルドは、それぞれ「秘密の色」の代わりに「秘密の数値」を選ぶ。
ステップ2 2人のどちらかが「公開の数値」(絵具混合トリックのときの公開色の代わり)を公表する。
ステップ3 秘密の数値(4)と公開の数値(7)を掛け合わせて、「公開秘密混合値」の28を得る。アーノルドも、自分の秘密の数値について同じことを行う。6×7で42という公開秘密混合値を発表する。
ステップ4 アーノルドの公開秘密混合値の42を取り、それに自分の秘密の数値である4を掛け、「共有された秘密値」である168を得る。
一方、アーノルドはあなたの公開秘密混合値の28を取り、自分の秘密の数値の6を掛け、28×6=168で、驚くべきことに同じ「共有された秘密値」を得る。
実際に使われている絵具混合
完全なものにするためには、簡単に実行できて(絵具を混ぜ合わせるように)、取り消しが実質的に不可能な(絵具の分解のように)数学処理が必要である。コンピュータで実際にこれを行うとき、混合処理は「離散べき乗」、分解処理は「離散対数」と呼ばれる。
通鍵暗号方式における鍵の受け渡しを安全に行うために提案されたDiffie-Hellman鍵共有。絵具混合という方法によってわかりやすく説明されている。イメージがつかみやすい説明で一度イメージを掴めば忘れないだろう。
■誤り検出と誤り訂正のニーズ
コンピュータには、基本的な仕事が3つある。もっとも重要な仕事は、計算を実行することだ。コンピュータが実行するほかの2つの非常に重要な仕事がなければ、答えを計算できる能力があっても何の役にも立たないだろう。その2つとは、データを保存する仕事とデータを伝送する仕事だ。
20Mバイトのプログラムをダウンロードしたときに、システムが100万字に1つずつ解釈を誤ったとすると、ダウンロードしたプログラムには20個を超える誤りが含まれることになる。これらの誤りは、どれも予想外のタイミングでシステムをクラッシュさせる要因になり得る。
誤り検出、誤り訂正は大学でも学んだ分野。こちらも誰でもイメージが掴めるように説明をしている。もう少し深く知りたいと思う分野であったため、内容は少し物足りないものだったが、概要を思い出すには十分であった。
■ロスなし圧縮 ― 究極のフリーランチ
コンピュータは、「ロスなし」と「ロスあり」の2つの大きく異なるタイプの圧縮を使っていることをまず覚えておこう。ロスなし圧縮アルゴリズムは、データファイルを受け付けると、もとのサイズの数分の1に圧縮する。そして、圧縮を解除するとまったく同じものが復元される。ロスあり圧縮は、圧縮を解除したあと、もとのファイルとは少し違うものになってしまう。
ロスなし圧縮を見ていこう。基本的なアイデアは、互いに同じになっている部分を見つけ、何らかのトリックを使ってその部分をもっと効率よく記述するということだ。データに反復が含まれているときには、このような圧縮は特に簡単である。このトリックをRLEと呼んでいる。反復する一続きの部分(run)に反復の長さ(length)を添えて符号化(encoding)しているという意味だ。
RLEの最大の問題点は、データ内の反復箇所が隣り合っていなければならないことである。そこで、コンピュータ科学たちは、基本的な発想をそのまま使いつつ、反復が隣り合っていなくてもうまく機能するより高度なトリックをいくつも考え出した。「前と同じ」、「より短いシンボル」の2つだけを見ていく。
―「より短いシンボル」のトリック
よく使われる文字については短いコードを使うようにしてみよう。一部のコードを長くするのである。
ステップ1 「前と同じ」のトリックを使ってもとの圧縮されていないファイルを変換する。
ステップ2 変換後のファイルを解析して、頻繁に登場するシンボルを見つける。頻繁に使われるシンボルには短い数値コード、あまり使われないシンボルには長い数値コードを与える。
ステップ3 ステップ2で作った数値コードを使ってファイルを変換する。
圧縮も興味深い分野の1つ。こちらもイメージを掴めるように、とても分かりやすく説明されている。これももう少し深くまで入っていきたい分野だったので、もう少し他の専門書で学んでみたいと思う。
【1読書1アウトプット】
イメージを大事にする
投稿元:
レビューを見る
アルゴリズムの存在自体は知っていただけど、どのようにそれが機能しているかは知らなかったので、ためになった。
投稿元:
レビューを見る
コンピュータ科学という大きな世界。プログラムの知識がなくても、アルゴリズムは説明できるし理解できる。いつも使っているコンピュータ、ブラックボックスを覗いて、驚きや満足を感じられるようになろう。
必要性と存在意義、そして日常的に恩恵を受けていることを改めて感じます。コンピュータ科学、すごい。
投稿元:
レビューを見る
よいテーマだと思う。コンピューターまわりの本で、ビジネスでも個別技術解説でもハードウェアその他でもない分野。
記述は平易で、とても基礎的なことから(たとえば累乗の記述まで噛んで含めるように、また拡張子の解説まで)書かれているので、退屈することもあるのだけれど、それで油断しているとRSAの解説で集中を要求されたり。
最後は計算不能性まで解説していてすばらしい!と言いたいのだけれど、ちょっと物足りないかな。
すごく割り切ってもっと簡単にする、というのでない限り、もう少し踏み込んでくれないと中途半端だった気がする。
PCになじみの薄い高校生とか文系大学生(で理系に拒否反応示さない人)とか向けかなあ。ちょっとターゲット読者層がピンとこないかも。
投稿元:
レビューを見る
【ひとことポイント】
実社会で活躍する未来を変えたアルゴリズム
<情報学部3 年S>
企画コーナー「企画本棚2014-新しい本との出会い」は(2Fカウンター前)にて展示中です。どうぞご覧下さい。展示期間中の貸出利用は本学在学生および教職員に限られます。【展示期間:2014/6/24〜】
湘南OPAC : http://sopac.lib.bunkyo.ac.jp/mylimedio/search/book.do?target=local&bibid=1625215
投稿元:
レビューを見る
デジタル署名や暗号化など身近なコンピュータアルゴリズムの基本が分かりやすく説明してあります。
仕組みが分かってしまうと、なんだ単純な考え方じゃないのと思うけど、これを最初に思い付いた人や現代のITに繋がる実用化をした人はすごいなあ。
投稿元:
レビューを見る
IT関連にかかわる仕事をしている私としては、それなりに理解できているアルゴリズムであったが、用語を知っている程度の人でもわかりやすいようなたとえで説明されていて、自分の理解が正しかったこと、中途半端に理解していたものを再確認できた。
ディジタル書名や公開鍵暗号は、これから学ぶ人にも役立つと思うのでぜひ読んでもらいたい。
うちの若い人たちにも紹介したい一冊である。
投稿元:
レビューを見る
この本では、アルゴリズムの定義として、「問題を解決するために必要な手順を正確に規定したレシピ」とし、それは機械的に感じられ、絶対に正確で、人間の直感や推測を必要としてならないとしており、その本質は何かというと、「チャーチ、チューリングのテーゼ」であると言っている。
無数に上げることができるアルゴリズムについては、3つの基準を設定し、取り上げている。基準は、コンピューターユーザーが普段使っているもの、現実に利用する際の具体的な課題を解決するもの、コンピューター科学理論に関係が深いものとなっている。
投稿元:
レビューを見る
特に新しいものはなかったが復習になった。技術的な用語を使っていないので、人に説明する時の参考にしたい。
投稿元:
レビューを見る
日頃意識せずに使っているシステムが、素晴らしいアイディアの積み重ねで作られていることが分かる本。感動します。
投稿元:
レビューを見る
図解と比喩でわかりやすい、さまざまなアルゴリズムの概念。
アルゴリズムとあるが、具体的なコードの載った実装のための本ではない。
「わたしたちが日常的に用いる、具体的で、コンピュータ科学理論に関連した」アルゴリズムを、情報検索、情報通信から人工知能に至るまで9分野にわたって扱っている。
複雑になりがちなテーマについても、段階を踏んだ説明があり(公開鍵暗号とデジタル署名における指数南京錠、決定不可能性におけるイエスノープログラムなど)、
また適切な図解と比喩が理解を助けている(公開鍵暗号の絵具混合トリック、ページランクのランダムサーファートリック)。
以前から知っているアルゴリズムについても、比喩を通じて核心を理解を深め、他のアルゴリズムとの関連を学ぶことができる。
(データベースのWALプロトコルの有用性:To-doリストトリック。誤り訂正とデータ圧縮:情報理論。)
わたしたちの普段の生活を支えているアルゴリズムに触れ、コンピュータ科学とはなにかというを学ぶことができる一冊。
投稿元:
レビューを見る
現代社会において必要不可欠となっているページランクなどのアルゴリズムを、
技術者以外にも理解できるよう自然言語で表現した一冊。
なるほど丁寧に綴られており理解しやすいが、
多少なりとも比喩がまわりくどくなってしまうきらいがある。
もう少し数式や疑似コードがあるとスマートなのだが…と思ってしまうが、それだと本書のターゲットには難解にうつるだろうから難しいところだ。
投稿元:
レビューを見る
公開鍵暗号法。
鍵が公開されているのに、なんで暗号化できているんだっけ?
何回読んでも忘れる。
今回もそうだろう。
でも、これまでで一番やさしく、かつ、数学的でした。
(以下抜粋。○:完全抜粋、●:簡略抜粋)
●公開鍵暗号法(P.75-78)
ステップ1:A、Bが秘密色を選ぶ
ステップ2:公開色を確認する
ステップ3:A、Bは自分の秘密色と公開色をまぜた混合色を作り、公開する
ステップ4:AがBの混合色を持ってくる
ステップ5:Aは秘密色とBの混合色を混ぜ合わせて、共有用の混合色をBに渡す
ステップ6:Bは受け取った共有用の混合色から、
公開色、Bの秘密色を取り除くと、Aの秘密色がわかる
○混合処理は「離散べき乗」、分散処理は「離散対数」と呼ばれる。
そして、コンピュータが離散対数を効率よく計算する方法は見つかっていないので、
離散べき乗は私たちが探している一方通行操作の一種と考えることができる。(P.85)