CS

メモ

CS

ゲーム(対戦・盤面固定) 将棋 囲碁 チェス オセロ ゲーム(盤面可変・パラメータを付ける) 数独(ナンプレ)→NP完全(ASP完全) ぷよぷよ(四色全消判定問題)→NP完全 テトリス→NP完全 他にも色々あったよな。後で調べてみよう。

2年後くらいに

CS

きっと2年後までには「一般化数独(ナンバープレイス)のNP完全性」とかいう卒論が書かれるに違いない。多分出来るんじゃないかしら? 既にあったよ(;´Д`) Takayuki YATO and Takahiro SETA: Complexity and Completeness of Finding Another Solution a…

MD5の脆弱性

暗号化アルゴリズム『MD5』に欠陥、ファイル攻撃の恐れ@Japan.internet.com Dan Kaminsky “MD5 To Be Considered Harmful Some Day”をメモ。Crypto2004のランプセッションの人とは違う人か? 中国の研究(名前忘れた)→フランスの誰か(ランプ・セッション)…

Mathematical breakthrough could bring disaster for ecommerce ところでこれ本当? リーマン予想って素数の分布を示唆した覚えがあるんだけどな。 「拡張リーマン予想が正しければ素数判定が強力になる」って結果をどこで読んだのだったか。はて。

適当な纏め。

CS

Adleman考案のLatticeを改造したLatticeのSVPを求めたら、Sauerの定理を改造して利用してsubset sum problemの改造版であるrestricted subset sum problemが解けると。ややこしい。 全部改造してるので難易度アップ。

[[リーマン予想]]

CS

米数学者、リーマン予想の証明を宣言@ITmediaNews /.jp リーマン予想解決される?

続き

なので自体は有理数なんだけど、 と全部整数で扱うから、行列の各要素は整数で出力されないとおかしい。さてはて。

LLLアルゴリズム

出来たと思ったら、下三角化しただけだった。 整数行列入れたら整数が出てくる筈なのにな。 バグ取るか。

Gram-Shmidt直交化

一度はうまくいったが、to_r関係で嵌る。 class Matrix def to_ra return self.to_a.each {|x| x.to_r} end end これでいくか仕方がない。 リファレンスにはMatrix#to_rってあるのにな。なぜか動かないんだよな、これが。

random

CS

線形合同法をPerlで実装するのはどうだろう。俺。

Robert Sedgewick『Algorithms 2nd』(ISBN:0201066734)

CS

日本では取り扱って無い様子。今でも入手可能な『Algorithms in C++』や『Algorithms in Java』も同じ内容っぽいのでそっち読んだ方が良いのだろうな。 で、ゼミが来週の火曜日なので担当分の35.Random Numbers 509-520を読む。D.E.Knuthの『The Art of Prog…

今日のメモ

CS

Lアルゴリズム→LLL LLLやべぇ。応用範囲広過ぎ。 モルフォロジー(Mathematical Morphology)