グラフ理論（Graph theory） - kanetaiの二次記憶装置
(無向)グラフの要素 要素が頂点(vertex), 点(point), 節点(node)の集合 辺(edge)と呼ばれる頂点の順序対の集合 隣接(adjacent) : 辺(u,v)が存在するとき頂点は隣接するという。 接続(incident) : が辺の端点(endpoint)であるとき、はに接続するという。 多重グラフ(multigraph) : 多重辺(multiple edges)または自己ループ(roop)を含むグラフ ※多重辺やループのない多重グラフをグラフと定義している。 部分グラフ(subgraph) : induced subgraph : 両端点がにある辺を全てが含むならば、をによって生成された(generated)部分グラフと呼ぶ。 次数(degree) 次数(degree) : に接続する辺の個数 孤立点(isolated vertex) : 次数0の頂点 の倍数
Wavelet Treeをもう一度 - 気ままなブログ
文字列本のメインであるウェーブレット木をもう一度素直に見直すことにした。 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 15人 クリック: 324回この商品を含むブログ (5件) を見る Wavelet Treeに関する著者のスライドは以下である。 http://www.slideshare.net/pfi/ss-15916040 ふらふらと論文を眺めていたら、Navarro神の「Wavelet Trees for All」というサーベイ論文が加筆されて更新されていた。内容自体はあまり変わっていないと思うが図が増えていた。以下がその論文である。 http://www.dcc.uchile.cl/~gnavarro/ps/jda13.pdf 大半の内
Non-Uniform Random Variate Generation
Non-Uniform Random Variate Generation (originally published with Springer-Verlag, New York, 1986) Luc Devroye School of Computer Science McGill University Preface to the Web Edition When I wrote this book in 1986, I had to argue long and hard with Springer Verlag to publish it. They printed a small number of copies, and never bothered with a second printing, even though, surprisingly, there seemed
高速な文字列マッチング - 気ままなブログ
最近は、簡潔データ構造を中心に調べたりしていたけど、文字列マッチングを考えた場合、別のアプローチもあります。そう、grepのような逐次文字列検索ですね。以下の解説がおもしろいです。 http://www.i.kyushu-u.ac.jp/~takeda/papers/IPSJMagazineCPM.pdf CSAとかFM-Indexに隠れてしまっていますが、実はかなり強力です。特に、クエリが固定で、テキストが頻繁に変更されるようなケースでは有効です。中でも使いやすのは、Aho-Corasick法(AC法)ですね。複数のパターンを同時に検索することができます。KMPを拡張した方法です。 AC法については、日本語だと 情報検索アルゴリズム 作者: 北研二,津田和彦,獅々堀正幹出版社/メーカー: 共立出版発売日: 2002/01メディア: 単行本購入: 6人 クリック: 552回この商品を含むブ
今年の研究振り返り - Preferred Networks Research & Development
吉田です。弊社では主に研究開発に携わっていますが、最近は顧問的なポジションになっている気がします。 普段は国立情報学研究所 (NII)という所で研究していて、よく論文を国際会議に投稿するということをします。 先日、CIKMという会議の結果が帰ってきて、今年開催される国際会議の結果が全て出そろったので、思い出話をしてみたいと思います。 紹介する論文の順番は、各会議が開催された(る)順です。 所々、専門用語を説明なしに使っていますがご容赦ください。 Yoichi Iwata and Yuichi Yoshida, Exact and Approximation Algorithms for the Constraint Satisfaction Problem over the Point Algebra. (STACS’13) 初めて東大の岩田君と書いた論文です。 岩田君は弊社でインターンや
拡張ユークリッド互除法について
「(省略) これは、a * x + b * y = 1 となる(x, y)を求める問題に他ならない。この式から明らかなようにgcd (a, b) != 1のときは、整数解(x, y)は存在しません。」
円と円の交点
半径r1 中心(x1,y1) の円と半径r2 中心(x2,y2) の円との交点。 連立方程式による解法 円の方程式は (x-x1)^2+(y-y1)^2-r1^2 = 0 …(1) (x-x2)^2+(y-y2)^2-r2^2 = 0 …(2) (1)-(2): (2 x2-2 x1)x + (2 y2 - 2 y1)y + (x1-x2)(x1+x2)+(y1-2)(y1+y2)-(r1-r2)(r1+r2) = 0 …(3) これは円と円の2つの交点を通る直線になっているので、円と直線の交点の問題に帰着できる。(3)の係数を a = 2(x2-x1) b = 2(y2-y1) c = (x1-x2)(x1+x2)+(y1-y2)(y1+y2)-(r1-r2)(r1+r2) と計算しておくとax+by+c = 0の形になる。 解法 : 直線と円の交点 JavaScript 若干計算量削減
4段階の思考スキルレベル - Chikirinの日記
将棋ソフトに関しておもしろかったのは、先日も書いた「探索」と「局面評価」という思考プロセスです。 １）探索＝とりうる選択肢を、自分の選択肢→相手の対応策（選択肢）→自分の選択肢、と深掘りしつつリストアップ ２）局面評価＝上記の過程で現れる局面を、どの程度、自分に有利か（不利か）評価する ３）その上で、自分にとって最も有利な局面につながる選択肢を選ぶ 探索とは、下記のような図＝探索木＝ツリーのイメージです。 （『人間に勝つコンピュータ将棋の作り方』より） この探索と局面評価というステップは、ビジネスや個人生活などあらゆる意思決定の場面で使われてます。 将棋のような完全情報ゲームでないため、より複雑ですが、ビジネスでは、 ・自社が値段を下げる→他社が対抗してくる→自社はどうする？・・・であったり、 ・自社が買収を提案する→第三者が価格を釣り上げる→公正取引委員会がいちゃっもんをつける→自社はど
暗記なんかで勝てたりしません - Chikirinの日記
今日は、将棋ソフトがどのように“将棋を学んできたのか”について、まとめておきます。 今から40年ほど前の 1975年頃、人工知能研究の一環として将棋ソフトの開発は始まったそうです。 その進化の流れは、ざっくり言えばこんな感じ？ １．ルールを覚えさせる ２．金言などをプログラム化する ３．探索と駒得で手を選ばせる ４．局面評価について、機械学習をさせる １の「ルールを覚えさせる」というのは、各駒の動ける場所を教え、“二歩”など反則となるルールを教えるってことです。 でも、駒の動かし方がわかるようになっただけでは勝てたりはしません。今の私と同じです。 ちなみに「反則にならない手」は合法手と呼ばれます。 次に「金言をプログラム化する」ってことが行われたみたいです。 将棋には勝ちやすくなるための格言がたくさんあります。 「玉飛接近すべからず」「二枚替えなら歩ともせよ」みたいな言葉ですが、そういうの
SRM580 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
SRM580のwriterをしていました。 点数はsolveまでの時間にも依存するので必ずしも600が激ムズという訳では一応ないです。 Div2 Easy 概要：区間が与えられるので重なってるペアの個数を数えよ。 解法：区間が50個しかないので全ペアについて試す。 Div2 Medium, Div1 Easy 概要：うなぎが区間として与えられるので、２点を選んでそれらのうちどちらか又は両方を含む 区間を最大化せよ。 解法：tから２つ選ぶのを全て試す。 Div2 Hard 概要：コストまたは通れないマスが書かれたgridがあるので、うまく横方向の壁を置いて左上のマスから下の段までの上移動を使わないpathのコストを最大化せよ。 解法：dp[i][j] = i段目に初めて到達したマスが左からj個目である時のコスト Div1 Medium 謝罪：TCでO(N^2)という制約はこういう入力にするし
Interval graph - Wikipedia
Seven intervals on the real line and the corresponding seven-vertex interval graph. In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. Interval graphs are chordal graphs and perfect graphs. They can be recogni
ヒルベルト曲線 | じゃりてん日記
２次元のヒルベルト曲線というかヒルベルト走査・・・。 大学のときちょっとやったのを思い出しながら自力で考えた。 要は再帰使ってぐにゃぐにゃ動いていけばいいわけで、最初はぐにゃぐにゃの基本パターンを全部配列にしてたけど、規則性が分かればテーブルなしでもOK。 ヒマがあれば３次元にも挑戦。。。したいかも Cのソースリストのインデントがまともにでません。。 スペース2個じゃだめ？ 一応 BLOCKQUOTE してみたのだけど・・・だめだこりゃ 念のため著作権表示を入れてみました。使う人いないと思うけど。 これ、okWebという質問サイトに投稿したのと一緒のものです。あっちではJaritenCatと名乗ってますです。 #include <stdio.h> #include <stdlib.h> /* データ用変数 */ struct xy { int x; int y; } *hil; int i
ヒルベルト曲線 - Gushwell's C# Programming Page
ヒルベルト曲線とは、ドイツの数学者ダフィット・ヒルベルトが考案したフラクタル図形の一つで、再帰的に定義できる空間充填曲線です。 ヒルベルト曲線は、コの字の形状を基本図形とし、以下の４つの基本描画ルールの再帰的組合せで描くことができます。 Ldr(n) = Dlu(n-1), Left, Ldr(n-1), Down, Ldr(n-1), Right, Urd(n-1) Urd(n) = Rul(n-1), Up, Urd(n-1), Right, Urd(n-1), Down, Ldr(n-1) Rul(n) = Urd(n-1), Right, Rul(n-1), Up, Rul(n-1), Left, Dlu(n-1) Dlu(n) = Ldr(n-1), Down, Dlu(n-1), Left, Dlu(n-1), Up, Rul(n-1) ※ n が 0 の時には、何も描画しませ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
就活分析録 Sudoku(数独)の問題自動生成アルゴリズム第2弾
サービス終了のお知らせ
WUPC2nd E問題
慶應大学 理工学部 講義 数値計算法 第十ニ回 モンテカルロ法
大堀龍一 (Ryuichi OHORI) on Twitter: "@kazucchi4465 参考文献 http://t.co/3Elu4wwL6Y http://t.co/vELpmpoLI9 http://t.co/YD57WM05p4 http://t.co/4WJIx35TLD http://t.co/ubuSec7koF"
Sweep and prune - Wikipedia
Convex hull trick - PEGWiki