2017/11/04 · ここはプログラミング言語OCamlに関する情報を集めたコミュニティサイトです。 ... プログラミング言語です。 型安全な静的型システムを基盤に、バグの ...
2017/11/04 · ここはプログラミング言語OCamlに関する情報を集めたコミュニティサイトです。 ... プログラミング言語です。 型安全な静的型システムを基盤に、バグの ...
Binary decision diagrams (BDDs in short) are a staple of computer science, that are used to represent Boolean functions in a compact manner. BDDs are described at length in the volume 4, fascicule 1 of Knuth's "The art of computer programming", who calls them "wonderful". In the last few months, I have been playing a lot with BDDs and related structures, and the more I play with them the more I lo
Take a map of mainland USA, and consider the following problems: Suppose you want to visit every state capitol exactly once, traveling on highways. Which route is shortest? Which route is longest? What is the mean and standard deviation of all the routes? Weight the states by any means, for example, by reading their two-letter code as a number in base 36. Then find a set of states such that no two
私のブックマーク 決定グラフを用いたデータ構造 科学技術振興機構 ERATO湊離散構造処理系プロジェクト 研究員 川原 純 はじめにBDD (Binary Decision Diagram、二分決定グラフ) はn変数0/1論理関数を効率良く表現するデータ構造である。 BDDは80年代から90年代後半にかけて盛んに研究されており、 主にLSI回路設計やモデル検査の分野において広く使われる技術となった。 2000年代以降は、BDDやその派生形を、 データマイニングや知識発見、確率推論、列挙アルゴリズム設計、バイオインフォマティックス等、 情報科学の様々な分野に適用する動きが広がっている。 また、組合せ集合(集合族)を表現する ZDD(Zero-Suppressed BDD)や、文字列集合を表現する SeqBDD (Sequence BDD)、 置換の集合を表現する πDD (PiDD, Per
社会人になって早7年目、やっと昇給という事象を経験できそうです。こんだけやって給料上がらんかったら転職した方がいいよ、と言われてますが、万が一上がらんかったらまた転職活動しないとならんのかな・・・。しんどいな。 さて、そんな身の回りのことはどうでもいいのですが、OCamlでちまちま色々なものを作ったりしています。ちまちますぎて何もできあがってないのが悲しいです。 そんな中で、とりあえず利用できるかなー、というくらいまできて、自分で利用したりしてみているライブラリがあります。 https://github.com/derui/simplespec 名前は気にしないでください。 作った動機 ぶっちゃけると https://github.com/andrenth/ospec これをめっちゃ参考にしています。というか基本的なコード部分はかなりクローンしていますが・・・。 ただし、個人的にインデント
先日、「『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう!」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。これは自己回避歩行(Self-avoiding walk)と呼ばれている問題らしい。 これだけ聞いてもそれほどインパクトはないのだが、動画に出てくるおねえさんの経路を調べあげる執念がもの凄く、ネット上でも結構な話題になっている。執念と言うよりも狂気に近い。しかし、話題になった割には動画内で言及されている高速なアルゴリズムを実装したという話を聞かなかったので、自分で確かめることにした。 動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。そこで、高速化のため
Take a map of mainland USA, and consider the following problems: Suppose you want to visit every state capitol exactly once, traveling on highways. Which route is shortest? Which route is longest? What is the mean and standard deviation of all the routes? Weight the states by any means, for example, by reading their two-letter code as a number in base 36. Then find a set of states such that no two
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く