自分のコーディング能力にガッカリしていたところに、 友人に誘われたので、 やってみようやってみようと思い続け、とりあえずメンバー登録してみたのですが、 システムかなんかの不具合？で何度やってもハジかれてました。 20回ぐらい試したけど、無理やっ…

アルゴリズム・サイエンス:入口からの超入門 (アルゴリズム・サイエンスシリーズ 1―超入門編)作者: 浅野哲夫出版社/メーカー: 共立出版発売日: 2006/10/10メディア: 単行本購入: 3人 クリック: 77回この商品を含むブログ (27件) を見る アルゴリズムサイエン…

ここんとこ論理パズルが俺の脳をいじめる。 そして、時間をむさぼり食っている。 本来考えることは苦手じゃないし、 あの「わかったあああああああああああああああ！」て瞬間がたまらなく好きなので、 いいんですが、 落ち着いて熟考できる時間と空間があま…

ある辞書が与えられていて、その辞書の中の単語でしりとりをする時、 しりとりの単語数が一番長くなる時の長さは？？？ という、おもしろい問題あったので、解いてみた。 もちろん「ん」で終わるので、逆から考えるのもアリやとは思うけど、 何で始めようと…

ダイクストラ法を実装してみました。 とりあえず1時間半ぐらいで思うがままに書いてみたので、 スパゲッティです。 ダイクストラ法とは、グラフが与えられた時、2点間の最短距離を求めるアルゴリズムですね。 ここでは、 というグラフが与えられた場合に sか…

1.ポスト対応問題 (1)文脈自由言語k=4の例 ポスト対応問題のインスタンスをなんとなく(110,01),(10,0)(001,111),(1,11)とおく。すると、L(x1,x2,x3,x4)={1#10#11#100#110001011} になる。これより、文脈自由文法は S→ij# S xijR S→ε (2)2つの文脈自由文法が…

1.1テープと2テープのTMの性能差 言語{0^n1^n} 2テープ：O(n) 1テープ：O(nlogn) 言語{xcxR} 2テープ：O(n) 1テープ：O(n^2) 教科書にあったの。 説明は直感的でいいみたいなので、交差列の説明とかはいらんかな？？？ 2.空集合問題の非可解性 教科書どおり…

明日テストなので、過去問を解いてみる。ムズすぎる。 間違いだらけやと思うので、おかしいとこは教えてください。＞＜ 1.言語{0^n1^m | n制限なしのポスト対応問題のインスタンスすべての頭にa(決まった記号)をつけるという還元を作る。 制限なしのポスト対…

非可解性の証明や、NP完全性の証明をするときには、 すでに非可解であったり、NP完全であると証明されている問題のインスタンスを 証明したい問題のインスタンスに還元することで証明をする。 これがなんとも分かりにくいので、 解きたい問題とインスタンス…

改訂版：TMの停止問題は非可解であることの証明。 旧版がカオスになったので書き直す。TM停止問題 - hat-tunの日記 L={ρi| TMρiは列ρiに対して停止して受理しない} という言語が必ず停止するTMで認識できないことは証明されているとする。 まず問題を分析す…

TMの停止問題は非可解であることの証明。 L={ρi| TMρiは列ρiに対して停止して受理しない} という言語が必ず停止するTMで認識できないことは証明されているとする。 まず問題を分析する。 TM停止問題が非可解 インスタンスとしてTM Mと列ρ。 Mがρに対して停止…