12月家の歌声



  • マーモセットさん、面白いお題でした。

    個人的には3次元までは絵が描きやすいですが4次元になりますと、ついつい代数的になりますねえ。

    地道に数えたのちにソムさんが天井の土管から顔をスルスルと……マーモセットさんの反応の意味を掴むまでに
    《激しく時間を使いました》
    水平思考って難しいです。……


  • Global Moderator

    @マーモセット さん

    イマジネーションが刺激される楽しいお題と解説ありがとうございました。答えも分からず(笑)解説もまだ見ることはできませんが、きっと素晴らしい謎解きが書かれているのでしょう! 解ける日はそのうち来るはずなので、開けるときを楽しみにします。

    「ダイナミック・プログラミング(動的計画法)」は、階段の昇り方もそうですが、問題がより小さな問題の重複から出来ている場合に有効な方法ですね。https://ja.wikipedia.org/wiki/動的計画法 をいまあらためて見ていたのですが、「マルチプルアラインメントのように表が三次元以上必要になると」というところにピピピと来ました。皆さんが話されている「次元」とは何かと思って居たのですが、関係ありそうです。マルチプルアライメントは、バイオ系では、DNAの塩基配列やタンパク質のアミノ酸配列の比較に日常的に用いられています。よく似た配列同士(例えば異なる動物種で、対応する遺伝子など)をできるだけ一致するように沿わせて並べる行為のことです。Blastというソフトウェア(アルゴリズム)が効率的で有名です。世界中で使われています。またこの行為を文章などの文字単位、あるいは、行単位で行うことは、情報処理の世界では基本的な行為で、Diff というソフトウェアが有名です。しかし、マルチプルアライメントで動的計画法が利用されていることは知りませんでした。「三次元以上必要になる」表とは何か? ヒントになりそうです。ちょっと勉強してみます。

    アルファベットを使った、マルチプルアライメントの例

    配列1 ABCDEFG
    配列2 BBCDEFG
    配列3 BBC―EFG
    配列4 ―BCCEGG
    

    「―」は並べるときに対応する文字がないので、すき間を空けているところです(階段を一段飛ばした?ところです)。


  • Global Moderator

    「ダイナミック・プログラミング」という言葉の分かりにくいところは、この手法はコンピューター・プログラミングの世界で使われますが、前者のプログラミングの意味は、「コンピューター・プログラミング」のことでないことだと思います。その元であるところの、より広い意味の言葉だと言うこことです。...何を言っているのか分かりにくいですね。

    「ダイナミック・プログラミング」の「プログラミング」とは、日本語訳にあるような、《計画》や《やりくり》みたいな意味だと思います。例えば、「演奏会のプログラム」と言って、演奏会の進行表・計画表のようなものを渡されます。そのプログラムの意味だと思います。

    辞書では、

    1. the planning, scheduling, or performing of a program

    というのが第一の意味として載っていて、2つめに、もう少し狭い意味の、「麻薬撲滅プログラム」「コンピューター・プログラム」などに相当する意味が載っていました。

    言葉(用語)の理解は難しいことが多いですが、理屈の理解や相互理解の、根幹にあるものだと思います。教科書を読んでいて分からなくなるのは、たいていは、言葉が分からないことに起因すると思います。そうして、私の場合は、既に前の章に説明があった言葉を、いい加減に見過ごしていることが原因みたいです。


  • Global Moderator

    マルチプルアライメントに常用されるBlast の開発者の一人の Myers 博士の、初期の配列比較アルゴリズムの古典的論文があります:

    "An O(ND) Difference Algorithm and Its Variations",
    Eugene W. Myers, 1986

    です。この論文の図1はこんなでした:
    0_1524359277961_edit-graph.png

    配列のアライメントを、「エディット・グラフ」と呼ぶものの、道順の問題に置き換えて考えるというアイデアみたいです。むむむ。


  • Global Moderator

    訂正:

    マルチプルアライメントという用語の使用に誤りがありましたので、ここに訂正します。アライメントを用いて、データベースから類似の配列を検索するのにBlastを常用します。このとき複数の配列がアライメントされます。しかし、これは、クエリー配列(調査したい配列)と、データベース中の配列の、2つの配列のアライメントを行い、その結果、ある以上の類似が見付かった配列を複数並べたものです。マルチプルアライメントというのは、3つ以上の配列を同時に比較することを指すので、Blastをマルチプルアライメントのツールと呼ぶのは正しくないと思います。これまで Blast の説明に用いたのは、マルチプルアライメント→アライメント と読み替えて下さい。マルチプルアライメントには、専用の別のプログラム(アルゴリズム)を使います。

    追加)ここまでの理解:

    • 2つの配列のアライメント=ペアワイズ・アライメント
      3つ以上の配列のアライメント=マルチプル・アライメント

    • ペアワイズ・アライメントを動的計画法で行うと、2次元の表が必要になる。
      http://www.dna.bio.keio.ac.jp/lecture/jikken/data/kadai2/pair_align.pdf

    • 3つの配列のアライメントを動的計画法で行うと、3次元の表が必要になる。だから、マルチプル・アライメントでは、「表が三次元以上必要になる」。

    追加2)三次元
    0_1524369684316_yamane-77.png
    重大なミスに気がついたので修正しました:
    0_1524366714368_yamane-77.png



  • @Hannibal さん
    こちらこそ、いい勉強になりました。
    もともと発展形は考えていなかったのですが、考えていくと面白いですね。

    @ソム さん
    いろいろと新しい言葉が出てきて半分以上理解できない状態ですが、

    配列のアライメントを、「エディット・グラフ」と呼ぶものの、道順の問題に置き換えて考えるというアイデアみたいです。むむむ。

    「エディット・グラフ」は、面白そうですね。
    もう少し早くに知っておきたかったです(謎)
    ご紹介のグラフで(0,0)から(7,6)までの最短経路の場合の数を応用すると面白い問題が出来そうな…
    関心の方向がちょっと違いますね(^_^;)

    問題がより小さな問題の重複から出来ている

    今回の想定解のやり方は、機械的に数え上げていくだけですが、途中で計算間違いがあると、正しい結果が得られません。
    そのため、 @Hannibal さんの検算式のような検証が重要なんですね。
    同じことを2回やるだけでなく、違う方法で確認することで、結果の信頼が増します。
    前段階で間違ってしまうと、結果が正しく得られないことは、色々な場面で起こるものなので、こうしたことを常に気をつけておきたいと思います。



  • お礼が遅くなりました。
    ご参加の皆さんありがとうございました。
    solved
    にします。



  • @マーモセット さん

    本日偶然にも、マーモセットさんから御提示いただいたものとは異なる公式があるのを知りました。

    T(m, n) = 0!1!..(n-1)! (mn)! / ( m!(m+1)!..(m+n-1)! )

    だそうです。

    m=3,n=4 を代入すると

    ((0!) * (1!) * (2!) * (3!) * (12!)) / ((3!) * (4!) * (5!) * (6!)) = 462

    となりました。

    公式の参照元は以下です。

    http://oeis.org/A060854



  • @Hannibal さん
    ご紹介ありがとうございます。
    すでに公式の形でいろいろ出ていたんですね。
    自分で公式を導けたら面白いでしょうね。
    でも、そこまでする気合が入りません。(単にできるだけの脳みそがないだけですが… …)

    お母さま、大変でしたね。
    早く回復されますように



  • @マーモセット さん

    有難うございます。

    本日、救急指定病院から、リハビリテーション病院に転院いたしました。

    ここからがいよいよ勝負となります。

    寝たきりになるか、あるいは、自力で歩けるか。

    私が頑張るだけではなんともならず、母にリハビリのモチベーションを持ってもらうために色々と工夫しなければなりません。



パズルハウスへの接続が失われたと思われます。再接続されるまでしばらくお待ちください。