カテゴリー別アーカイブ: 未分類

[#プリクラ問題]に対する厳密解の探索(準備編)


前回の投稿から数日、プリクラ問題の議論はますます盛んになっていたようです。またちょっと手出しをしてみたので、その記録を書いておきます。

Togetter「プリクラ問題2」

おさらいすると、プリクラ問題とは「n人の集団でm人ずつプリクラを撮るとき、全てのペアが一緒に撮影されるために必要な最小枚数P(n,m)はどのように求まるか」というものでした。

議論は厳密解の探索が主眼となっているようです。この厳密解というのは結構難しくて、何か適当な方法で解を出すのでは駄目で、それが理論的な下限値であることを証明する必要があります。

つまり真っ直ぐなアプローチとしては、常に効率的な組み合わせを見つける一般的な方法を提案し、また理論値ぴったりの下限値の計算法を求め、これらが一致することを示すことになるわけです。しかし、全ての条件を満たすようにこれを解くのは楽な話ではありません。

ある問題の最小値・最大値がわかっていないというのはそれほど珍しい話ではなく、例えばn次元接吻数(ある球の周囲に何個の球が置けるか)は、いくつかの小さい値についてのみしか知られていません。
計算に関わる話ではビジービーバー関数というものが知られていて、ざっくり「n状態をとる停止するチューリングマシンのうちで最も長く出力を吐き出すもの」という定義です、これは答えがあるにも関わらず計算できないことが示されています。
もう少し近い話ではラムゼーの定理というのもあります。ある大きさの完全グラフをいくつかの色に塗る話で、具体例では「6人いれば互いに知り合いか互いに知らない3人組が必ず存在する」などと表現されます。これも一般のn人の場合は非常に難しい問題になります。

もっと単純な話になると、「この15パズルは最短で何手で解ける?」みたいな問題もあります。

このような一般の場合について理論解が出せないときにしばしば役に立つ強力な武器として、探索があります。つまり、全部の撮影の組み合わせをやってみればいいんですね。あるK枚でやってみて全ての場合で駄目で、またK+1枚で解を見つけた場合、それが文句なく答えになるわけです。6×6のオセロは全ての手が解析され後手必勝が確定しましたし、最近だとルービックキューブの全ての状態は最悪20手で解けるという証明がありました。これらは探索により示されたものです。

さて、プリクラ問題に対して全数探索は役に立つのでしょうか。今回は探索の準備編です。

続きを読む


拍と拍子の概念を宇宙人に伝えよう


先日、こんなツイートを見かけました。

“数学と物理がむちゃくちゃ出来るのだが音楽的センスが全く無いと言う後輩に、拍と拍子の概念を伝えるにはこれでいいのか?”

“先日ツイートした「拍と拍子の概念を数学で表現する」の検証を行いました。 一応計算はできたのですが、拍子の概念を定義するのは非常に難しいということが分かりました。”


「音楽的センスが皆無だが数学と物理なら話が通じる。拍と拍子の概念をどう伝えればよいか?」

ふむ。早い話が宇宙人を想定すればいいのですね。
(私の脳内宇宙人はいつも死ぬほど数学と物理に長けている設定になっています。)

先のツイート内では拍子テンプレート関数なるものを用意していました。これなら拍子以外の要素(コード進行とか?)も考えられそうですが、あまり複雑にすると楽曲のテンポに対しては結果が安定しなくなりそうです。

私ならどうするか。拍子だけならフーリエ変換でもいけそうです。
音をエネルギーか何かの時系列データで表現して、それをフーリエ変換して波数空間で見てあげれば、拍や拍子のピークが見えてもよさそうです。拍の半分の周波数でピークが出れば2拍子、1/3倍の周波数でピークが出れば3拍子です。

と、予想を書いてみるのは簡単ですが、本当にこんなことになるのでしょうか。

というわけで試しにやってみました。
関連文献をあたれば何かしら見つかりそうですが…

続きを読む


卓上栽培セット”Shippon”を頂きました


先日の研究室クリスマスパーティーにてプレゼント交換があり、私も後輩からクリスマスプレゼントを頂きました。

“Shippon”という栽培セットになります。修士論文のおともに良いものを頂きました。

不敵な笑み

不敵な笑み

卓上で草を育てるキットです。今回の草はクローバーです。新規性特徴は土がコップより上に位置していて水を毛細管現象で吸い上げる形式になっていることで、確かにこれで給水できるなら腐らせる心配もないし、水やりの手間が省けて便利です。目指せ研究室の緑化。

ただ、プラスチックのコップの上段に焼き物の犬でその背中に土という、重心をこれでもかと上げた作りになっています。ひっくり返した時のやばさを考えると材料は逆のほうが良い気もしますが、その辺りはデザインなのでしょう。手元の環境だと転倒時のやばさでは先日の温度計のほうが上回っているので、リスクもさほど増えていません。両面テープでも使っておきます。

デザインといえば、この犬は顔のパーツが世界的に有名なビーグル犬によく似ていますね。あちらも直立二足歩行ですし。


さっそく初期設定をします。説明書によると、土をふやかして、種をまけばいいだけです。

続きを読む


【FF13考察】「その章も一本道だぞ」新聞を読みながら教えてくれた親父は、昔 コクーンをパージされたパルスのファルシのルシだった。


タイトルで気づいた方もいるかと思いますが、今回の話題はRPGゲーム “Final Fantasy XIII (FF13)” の感想です。
タイトルの元ネタはこちら

ff13_1

※この記事の画像は全てスクエア・エニックス社のFF13紹介ページから引用したものです。
全ての画像の著作権はスクエア・エニックス社に帰属します。

FF13といえば、往年の名作シリーズの最新作ということで一時は各所で異様に話題になった作品です。

実は最近何人かの友人に「ブログの内容がおかしい」と言われたのをちょっと気にしていて、たまには趣向を変えてゲームの感想でも用意しようと思ってこうなりました。これでこのブログも一般的になれますね!

私がFF13をプレイしたのは1年ほど前のことになります。私はゲームは一人でやって勝手に満足するのが好きなので感想を書くことはほぼないのですが、丁度物語の完結編(FF13:ライトニングリターンズ)が出るとかで盛り上がっていること、ゲーム中思いついたあれこれを放っておくのも勿体無いかと思ったので、ここにFF13の感想を書いておくことにしました。

感想というよりはほとんど考察です。ネタバレを含みます。プレイしていない人でも読めるように書いたつもりですが、内容がわからないと理解困難なところもあるかと思います。あと、私はあまりRPGをプレイしないので、ゲームの感想が一部RPGというジャンルそのものの感想になっているかもしれません。

続きを読む


「ガリレオ温度計」買ってきました。


先日、東急ハンズ渋谷店で気になっていたものをいくつか買ってきました。

本当は低温度差スターリングエンジンを探しに行ったのですが、そちらは今は置いてありませんでした。

東急ハンズ戦利品

今回の注目は左上の品。「ガリレオ温度計」です。浮きに温度が書いてあり、浮き沈みで温度を計るようになっています。

実験用とかではなく、完全なインテリア用です。

花にそえてみたの図

花にそえてみたの図

続きを読む


[お知らせ]blogのお引越しをします (追記:しました)


このblogページのお引越しをします。

ドメインを変更するだけですので、突然見れなくなったり中身が新規になったりするわけではありません。

今まで来てくださった方にも問題が起きないように注意しますが、変更中は何度か不安定になるかもしれません。よろしくお願いします。

引越しが終わりましたらまた連絡します。


追記: 引越しを完了しました。

旧URLは http://oniku64.dyndns.org/blog/ でしたが、

新URLは http://elephnote.com/blog/ となりました。

旧URLにアクセスしても転送されるので問題はありませんが、永久的にではありませんので、ブックマーク等している方がいましたらお手数ですが変更のほうよろしくお願いします。


最近のブログ記事まとめ


ざっくりとまとめておきます。

詳細は各記事へのリンクをどうぞ。


シミュレーション/ビジュアライゼーション系

[フラクタル] マンデルブロー集合 10の200乗倍への挑戦

コンピュータを駆使してグーゴル倍のさらにグーゴル倍まで拡大。なかなか恐ろしい計算でした。
浮動小数点型の限界なんて何のその。

運動方程式の数値計算と速度ベルレ法の威力 (前半)

ちょっと物理のお話。計算結果がずっと安定するという不思議な数値解法。

[作ってみた] [プログラミング] 剛体3重振り子

剛体系の動きをどうコンピュータの世界に落としこむか、という話。かわいい。

[作ってみた] [プログラミング] 反応拡散方程式で遊ぶ

偏微分方程式と戯れる。単純な式から複雑な模様を描く。ぬるぬる。


その他作ってみた系

男子トイレの力学

モンテカルロ法の授業の課題で作ったもの。

続きを読む


おいしいカレーの作り方


ブログを始めたらまずはカレーの作り方を書かなければいけないでしょう,ということでおいしいカレーの作り方です.
今回はWordPressの使い方の練習のために書いているようなものなので.内容はほとんどないのであしからず.

 

カレーの作り方,といえばとっさに書ける文章の代名詞です.
「大学のテストでおいしいカレーの作り方を書いたら単位が来た」なんていうジョークよく 聞きますが,私の周りではこのような例はまだ聞いたことがありません.

個人的にはどうしても単位が欲しかったら土下座したほうが効率がいいんじゃないかと思っています.こっちの事例は2件知っていて,片方は必修で追加レポートを課され,もう1つは選択科目で門前払いをされたそうです.土下座が効いたかどうかは微妙ですね.
カレーのレシピではなおさら無理だと思います.シチューでもボルシチでも駄目でしょう.

 

テストとは少し違いますが,「カレーの作り方」の読みものとして今までで出会った中で最も感動したのは,大学の学祭で活動するサークル「無限次☆計画」さんの「カレーライスの作り方」という論文(?)です.
ちょっとまえがきを見てみましょう.

“カレーライスの構成法を記した文章は多いが、あまり厳密に記したも
のはない。…そこでここでは、白米のみをアプリオリに与えられたも
のと考えた上で、丼もの達から成る集合に入る構造を調べ、それらに対
して特定の性質を満たす食べ物としてカレーライスを定義し、簡単な場
合に構成を行う。”

この論文では丼ものの集合について厳密な定義を行い,たし算(複数の丼を並べる)・かけ算(丼に丼をぶっかける)・丼勘定(具の数を数える),その他単位元(白米だけ)・零元(何もない)等も定義しながら話が進みます.
最後に,カレーライスを「何を追加しても変化しない丼(かけ算に対して変化しない元)」と定義してレシピは終了します.

この読み終わっても何も作ることができない感が私は大好きです.
大学数学ならよくあることで,例えば逆行列の定義なんてのはさくさく説明される割に,その作り方についてはこれっぽっちもわからないなんてことがおきるわけですね.
カレーをその世界に持ち込んだことは画期的だと思います.

 

リアルなカレーの話をすると,大学の近くにおいしいカレー屋さんがいくつかあります.ナンで食べたりするやつです.ちょっと割高なので頻繁には行きませんが,以前別の場所で書いたように,手元で書いたプログラムの出力がNaNだらけになったときは気晴らしに行くこともあるでしょう.

NaN (Not a Number) というのはコンピュータの表現するエラー値のようなもので,特別な振る舞いをします.
例えば,この値には何をかけてもNaNになります.NaNにカレーをかけてもNaNです.
コンピュータは理不尽ですね.

 

全然カレーの作り方書いてないですね.
そんな私はハヤシライスが好きです.

今後もよろしくお願いします.


Hello, World.


ぞうさんです.ブログを始めました.
ソビエトロシアではブログがぞうさんを始めます.

テンプレとか見た目はしばらくふらふらすると思います

Twitterには長くなったりして書きづらいようなものをこっちに退避する予定です.そのうち別の使い方も出てくるかもしれませんが.

あれこれ調べながら作ったわけですが,手順がすっかり洗練されていたので驚きました.
当然といえば当然なのですが,ブログひとつ作るのに別にCPUやOSやネットワークに関する知識なんて必要ないわけです.「トランジスタの動作原理から理解する最強ブログの作り方!」なんて本は見たことないわけですね.いやあったら読みたいですけど.
技術の隠蔽とはすごいものです.

まあ何が言いたいかというと,いまどきブログを書くのにOSのインストールから始めるような人はまれだということです.僕は他の用途でも使うので構いませんが.