辞書を参考にしながら。NAISTのI期辺りでやったはずなんだが、かなりすっ飛んでいる。デジタル人工知能学事典 [CD-ROM付]作者: 人工知能学会出版社/メーカー: 共立出版発売日: 2008/05/16メディア: 単行本購入: 1人 クリック: 6回この商品を含むブログ (6件)…

どういうときに何ができるのかについて。この辺見ながら。問題定義品物がN個あったとする。品物iには価値と体積が与えられている。は1のとき品物iを取る、0のときに取らないということを表すバイナリ変数であるとする。持って行ける品物の総体積がbまでであ…

実験で使いそうなベースラインがページランク的なアルゴリズムだったので、Rubyの実装を適当にC++に翻訳してみただけ。超簡単なのでよい。 Rubyでもっとも重要なライブラリは何か？PageRankで計算してみた - aikeの日記 #include <map> #include <cmath> #include <iostream> #incl</iostream></cmath></map>…

自分用メモ。データ構造とちょっとしたコードの例。StackA stack is a last in, first out data structure. There are two main fundamental operation for stack: push and pop. The push operation adds an item to the top of the stack. The pop operati…

が、色々網羅する前に力尽き(ry。 深さ、幅優先探索 強連結成分分解 ベルマンフォード法 くらいしか書いてない。 #include <iostream> #include <string> #include <vector> #include <map> #include <queue> #include <math.h> #include <boost/assign.hpp> #include <boost/shared_ptr.hpp> #include <boost/foreach.hpp> template </boost/foreach.hpp></boost/shared_ptr.hpp></boost/assign.hpp></math.h></queue></map></vector></string></iostream>

#include <iostream> #include <string> #include <map> // ref http://infoshako.sk.tsukuba.ac.jp/~yamamoto/Courses/files/page2_13.pdf class KnuthMorrisPatt { public: std::string text; std::string pattern; int n; int m; std::map<int, int> pi; // prefix function KnuthMorrisPat</int,></map></string></iostream>…

The Boyer-Moore string search algorithm is one of the efficient string searching algorithm. This is based on a naive string searching algorithm which slides a pattern forward by 1 position and verifies whether a substring of text matches t…

どのようなときにAho Corasick法が必要か辞書構築した後の応用先(?)の一つとして、辞書を元にした転置インデックスを作ることがあげられる。「どのキーワードがどの文章に登場したか」が一番簡単な転置インデックスだと思うんだけど、今回は登場した文章のど…

グラフに対する基本的な問題として 最小全域木 最短路問題 最大フロー の3つがあると思う。で、最小全域木は離散最適の課題としてPrim法を使って解いてみたし、最短路問題はベルマンフォードのアルゴリズムをRubyとC++で解いてみた。となったら、最大フロー…

アルゴリズムの経過をアニメーションgifにするために書いたはいいものの、アルゴリズムとは関係ないコードが増えてしまったので、C++で書き直してみた。以下コード。 #include <iostream> #include <string> #include <map> #include <vector> #include <math.h> using namespace std; class Directe</math.h></vector></map></string></iostream>…

離散最適化理論の課題が出ていたので、ベルマンフォードのアルゴリズムを実装してみることにした。アルゴリズムが実行されていく様子の例もレポートに貼ろうと思ったんだけど、アルゴリズムはもうあるんだから、その様子をruby-graphvizとかで吐けばいいじゃ…

この前Rubyでソースを書いたりしてましたが、ちゃんと発表するための資料も作ってましたよっと。ホワイトボードで説明するんだけどな!!ということで図とかほとんど入ってないですが。。。 Algorithm Design from syou6162 ところでkeynoteが使えるようになっ…

離散最適化理論の課題を提出し終わったので、貼ってみるテスト。トポロジカルソートのためのところは前にちょちょいと書いたんですが 説明用の図 巨大なグラフを作る用の関数 計算時間をplotするための関数 などなどの付近も書いたので、貼ってみます。例を…

アルゴリズムデザインのゼミを4、5回くらい聞いて今週発表なので、準備してたらなんとなくどういう流れで説明すればいいのか分かってきた。ちょっとまとめるとこんな感じ。 そのアルゴリズムはどういう問題で、どういうところで応用されたりしているのか 動…

動的計画法分かんない しかも、なんか一次元じゃなくて二次元っぽいから怖い＞＜ と思ってgkbrしていた次回アルゴリズムデザインのゼミで担当の系列アライメント(p246 6.6)のアルゴリズムですが、ミスドでホットカフェオレを3杯くらいおかわりしていたら結構…

昨日までに書いていたグラフはコストとかそういうの考えていなかったんだけど、ダイクストラをやろうということでコストも考えることにしました。ダイクストラでedgeとそこまでの距離のhashを作りながら、そこまでのを記憶しておくhashも用意。最短路を探す…

トポロジカル順序付けは有向無閉路グラフ(directed acyclic graph)について定義されるものである。閉路がない有向グラフだと必ず順番のようなものを付けることができる。具体的にどういうものに使えるか、というと 仕事の順番 服を着る順番 講義科目の履修順…

有向グラフにおける連結成分の集合みたいなのがどうだったか忘れたので、無向グラフ化(両方を有向にするっぽい感じで)して考えることにした。 # -*- coding: utf-8 -*- require 'pp' require 'set' class Graph def initialize(edges) @edges = edges @nodes…

バックトラックとかしなくていいので、結構簡単にできた。 # -*- coding: utf-8 -*- require 'pp' class Graph def initialize(edges) @edges = edges @nodes = Hash.new{|h,k| h[k] = []} end def add_edge(edge) @edges.push edge unless @edges.index(edg…

index グラフの勉強だけじゃなくてRubyの勉強にもなりそうなソースだなーと思ったので、メモしておく。ファイルは2つとなっていて把握しやすい。 graph.rb graph_algorithm.rb graph.rb module Graphとclass DirectedHashGraph、DirectedHashGraphを拡張した…

アルゴリズムデザインのゼミでmiyaga50が「counting inversions」について発表していた。 マージソートな考え方を使っているアルゴリズム 協調フィルタリングのようなランキングを使うようなシステムで使われる 嗜好がどれくらい違うかを測る尺度に使える メ…

数学的基礎とデータ構造 (アルゴリズムイントロダクション)のp28付近にあるマージソートをRubyでそのまま書きくだす簡単なお仕事。2行で書けるとかそんなの知るか。 require 'pp' def merge_sort(a, p = 1, r = a.length) def merge(a, p, q, r) n1 = q - p …

Rejectセキュリティ&プログラミングキャンプでは極度の体調不良*1により、あんまりコーディングしてる時間が取れなかったのですが、それでもなんとか自分がやろうと思っていたところができました。集合知プログラミングの11章「進化する知性」ということで、…