Category Archives: 世界でもっとも強力な9のアルゴリズム

「世界でもっとも強力な9のアルゴリズム」第16回(12月28日)

Posted on by 0 comment

参加者 沼田(読み手)、今井、青木(記)
範囲 pp.292-312

第10章 決定不能性とはなにか

  • 10.6 不可能なプログラムにはどのような意味があるか
    • 決定不能性と頭脳

第11章 まとめ
――指先の天才はもっと賢くなるか

  • 11.1 いくつかの偉大になる可能性のあるアルゴリズム
    下から6行目「まだああまり」→「まだあまり」
  • 11.2 偉大なアルゴリズムが消えていくことはあるのか
  • 11.3 私たちは何を学んだのか
  • 11.4 終点から私たちの旅の目的を振り返る

謝辞

参考資料

「世界でもっとも強力な9のアルゴリズム」第15回(12月25日)

Posted on by 0 comment

参加者 青木(読み手)、沼田、今井(記)
範囲 pp.274-292

第10章 決定不能性とはなにか

  • 10.4 存在し得ないプログラム
    • AlwaysYes.exe — ほかのプログラムを解析するイエスノープログラム
      • p.276 AlwaysYes.exeって作るの難しいよね。
        → 次節に「実際にこのプログラムを書いたわけではない」とあるし、それ以降に不可能であることの説明がありました。
    • YesOnSelf.exe — AlwaysYes.exeのちょっとした変種
    • AntiYesOnSelf.exe — YesOnSelf.exeの逆
  • 10.5 クラッシュ検出プログラムの不可能性
    • p.289
      図10.11(p.287)の矢印の変換部分が明確になっていないから、CanCrash.exeが存在しないという証明がもうひとつピンとこない。
    • 停止性問題と決定不能
  • 10.6 不可能なプログラムにはどのような意味があるか
    • 決定不能性とコンピュータの利用

「世界でもっとも強力な9のアルゴリズム」第14回(12月21日)

参加者 今井(読み手)、沼田(記)
範囲 pp 255 – 274(単純なイエスノープログラムのさいごまで)

第9章 デジタル署名
――このソフトウェアを本当に書いたのは誰か

  • 9.6 デジタル署名の実際
  • 9.7 パラドックスの解決

第10章 決定不能性とはなにか

  • 10.1 バグ、クラッシュ、ソフトウェアの信頼性
  • 10.2 あることが真ではないことの証明
  • 10.3 ほかのプログラムを分析するプログラム
    • p.267 コラム
      3つ目の方法はtxtファイルを入力として起動しているのではなく、起動してからtxtファイルを開いている。
  • 10.4 存在しえないプログラム

「世界でもっとも強力な9のアルゴリズム」第13回(12月18日)

Posted on by 0 comment

参加者 沼田(読み手)、今井、青木(記)
範囲 pp.234-254

第9章 デジタル署名

— このソフトウェアを本当に書いたのは誰か

  • 9.4 掛け算南京錠による署名 (p.234 最下行から)
  • 9.5 指数南京錠による署名
    • RSAのセキュリティ
    • RSAと素因数分解のつながり
    • RSAと量子コンピュータのつながり

「世界でもっとも強力な9のアルゴリズム」第12回(12月14日)

Posted on by 0 comment

参加者 青木(読み手)、沼田、今井(記)
範囲 pp.216-234

第8章 データベース

— 一貫性の追求

  • 8.3 リレーショナルデータベースと仮想テーブルトリック
    • キー
      • p.218 l.5
        B木はB-Treeのこと。
        (WikipediaにもB木(びーき)として載っていましたし、ネットを検索してもB木はB-Treeの日本語として普通に使われているようです。)
    • 仮想テーブルトリック
      • p.219 l.3 中ほど、衍字
        1つにまとめるすることだ。
        → 1つにまとめるすることだ。 (または、1つにまとめるすることだ。)
      • p.221 下から5行目~
        ここに書いてある技術的なコメントはどういう意味?
        → SQLのSELECTでは、結合と射影と選択を別々にせずに、一度にできるということだろう。
    • リレーショナルデータベース
  • 8.4 データベースの人間サイド

第9章 デジタル署名

— このソフトウェアを本当に書いたのは誰か

  • 9.1 デジタル署名は実際には何のために使われているのか
  • 9.2 紙に書く署名
  • 9.3 南京錠つきの署名
    • p.230 図9.3
      錠と鍵が3個ずつ書いてあるが、イメージ的には鍵は1つのような感じがする。
  • 9.4 掛け算南京錠による署名 (p.234 下から2行目まで)
    • p.234 l.7
      「時計算」の読み方は?
      → Wikipediaでは「とけいざん」とあるが、この本で言っている剰余を用いたものとは別のものだし、ネット上を検索してもWikipediaにかかれている時計算が普通のようだ。
    • p.234 l.15 衍字
      これからこのサイズの

「世界でもっとも強力な9のアルゴリズム」第11回(12月11日)

参加者 今井(読み手)、青木、沼田(記)
範囲 pp 193(下から3行目) – 216(キーの手前まで)

第8章 データベース

  • 8.1 トランザクションとto-doリストトリック
  • 8.2 レプリケートされるデータベースのための「準備してからコミット」トリック
    • 準備してコミットトリックは、ここの説明では通信が切れないのが前提になっている。
  • 8.3 リレーショナルデータベースと仮想テーブルトリック
    • データの正規化の利点として、記憶スペースが節約できることおもに説明しているが、むしろ、後のほうに書かれているデータ更新作業の効率化とか、データの矛盾が発生するのを避けることのほうが大事なのでは。

「世界でもっとも強力な9のアルゴリズム」第10回(12月7日)

Posted on by 0 comment

参加者 沼田(読み手)、今井(記)
範囲 pp 176 – 193

第7章 データ圧縮

— 無から有を生み出す

  • 7.2 ロスあり圧縮—フリーランチではないがとても割安な食事 (p.176 除外トリックから)
    • p.176 中ほど
      画像データの個々のピクセルがモニターやテレビ画面を間近でみれば見えるように書いてるが、画像データのピクセルとモニターやテレビ画面で見える点は別の物のはず。
    • p.179 第二段落中ほど
      320 x 240 = 7万6800ピクセルが230Kバイト以上の記憶スペースはなぜ?
      → ここまでは0~100の101階調モノクロ画像で説明してきているが、ここでの計算では、1ピクセル RGB各1バイトで計算しているのだろう。
      76,800 × 3 = 230,400
    • p.181 JPEGフォーマットの8×8に関連して
      JPEGのトリミングアプリなどでは、この8×8の単位でしかトリミングできなくして、JPEGの復元、再圧縮をすることなく、無劣化でトリミングできるものがある。
      8×8を考慮しないアプリだと、読込み(復元)→トリミング→保存(再圧縮)を行うので劣化する。
  • 7.3 圧縮アルゴリズムの起源

第8章 データベース

— 一貫性の追求

  • p.188 上のほう
    “トリック”が「」内に含まれていたり、「」の後ろに書かれていたりするのは何か意味があるのだろうか。
  • p.190 中ほど
    「AがBと結婚しているなら、BはAと結婚していなければならない」というルールだけでは、上方の「AがBと結婚しているのに、BがCと結婚していたら…」は違反にならないね。
  • 8.1 トランザクションとto-doリストトリック (p.193 下から4行目まで)

「世界でもっとも強力な9のアルゴリズム」第9回(12月4日)

Posted on by 0 comment

参加者 今井(読み手)、沼田(記)
範囲 pp 157 – 176(除外トリックの手前まで)

第6章 パターン認識
――経験から学ぶ

  • 6.5 パターン認識の過去、現在、未来

第7章 データ圧縮
――無から有を生み出す

  • 7.1 ロスなし圧縮――究極のフリーランチ
    • p.163 下から3行目
      …書き方をすることもあるろう。
  • 7.2 ロスあり圧縮――フリーランチではないがとても割安な食事

「世界でもっとも強力な9のアルゴリズム」第8回(11月30日)

Posted on by 0 comment

参加者 沼田(読み手)、今井、青木(記)
範囲 pp 138 – 154

第6章 パターン認識
— 経験から学ぶ

  • 6.3 決定木—20の質問トリック (p.138 最下行から)
  • 6.4 ニューラルネットワーク
    p.154 l12 「当たられる」について、「当たられる」という言葉はあるようですが、ここでは意味が違いそうです。

「世界でもっとも強力な9のアルゴリズム」第7回(11月27日)

Posted on by 0 comment

参加者 青木(読み手)、沼田、今井(記)
範囲 pp 122 – 138

第5章 誤り訂正符号
— 自分で誤りを訂正するシステム

  • 5.6 実際の誤り検出、誤り訂正
    • p.124 中ほど
      CRC-32のCRCは、Cyclic Redundancy Checkの略。伝送通信装置でよく使われている。

第6章 パターン認識
— 経験から学ぶ

  • 6.1 問題は何か
  • 6.2 再近傍法
  • 6.3 決定木—20の質問トリック (p.138 下から2行目まで)