グラフを扱うJavaライブラリ「Jung」の紹介 - Twitterのグラフ構造を視覚化 - public static void main
java-ja 第12回のLTで話そうと思ったのですが、出番がなかったので資料をブログで公開しておきます。 Jungは研究などでグラフ構造が出たときに、理解しやすくするために可視化するのに使っています。他にもいくつかグラフを扱うライブラリは存在していますが、日本語の資料があったのと拡張可能なことが多かったのでJungを結果的に使うようになりました。 以下はそのJungについての簡単な解説です。 Jungとは Jungの正式名称はJava Universal Network/Graph Frameworkで、ネットワーク(グラフ) 構造の分析や視覚化を行うためのJavaのOSSライブラリです。グラフ理論、データマイニング、ソーシャルネットワーク分析のアルゴリズムを数多く実装しています。 安定バージョンは1.7.6で最新は2.0betaで、BSDライセンスで使用できます。 http://jun
Laboratory for Web Algorithmics - Home
Mambo - the dynamic portal engine and content management systemUbiCrawler is a scalable, fault-tolerant and fully distributed web crawler developed in collaboration with the Istituto di Informatica e Telematica. The first report on the design of UbiCrawler won the Best Poster Award at the Tenth World Wide Web Conference. Once a part of the web has been crawled, the resulting graph is very large—yo
DO++: 左傾赤黒木
漢字で書くと仰々しいが、赤黒木 (wikipedia) red-black tree (english wikipedia)という平衡二分木で最も多くつかわれているデータ構造の、改善版が出てたそうだ。 left-leaning red-black tree (pdf) 日本語に訳すと左傾赤黒木かな。簡単な漢字を並べている感じがしてしまう 赤黒木の詳細については、wikipediaなどをよんでもらうとして、これは更新時間が定数で更新箇所が局所的（これはマルチスレッドとかでロックする箇所をかなり細かい単位で、できるという強い利点もある）のだが、実装が結構面倒くさい。例えばC++ stl のmapとかの赤黒木の実装のstl_tree.h(google code search)は大変なことになっている（特にRb_tree_rebalance_for_eraseとか） 赤黒木というのは動的データ構造
講義資料 配列解析アルゴリズム特論I 情報生命科学基礎/演習 他 -渋谷哲朗
平成20年度 東京大学大学院 情報理工学系研究科・コンピュータ科学専攻 配列解析アルゴリズム特論I 4/10 4/17 4/24 5/1 5/8 5/15 5/22 5/29 (The problem to be reported - in English) 6/5 6/12 6/19 7/3 7/10 7/17 東京大学 理学部・情報科学科 情報科学特別講義３ （情報科学とバイオインフォマティクス） 6/10 7/15 7/22 東京大学大学院 新領域創成科学研究科・情報生命科学専攻 情報生命科学基礎/演習 5/27 6/17 京都大学大学院 薬学研究科・医薬創成情報科学専攻 情報科学概論 6/3 中央大学大学院 理工学系研究科・物理学専攻 物理学特別講義第二 TBA 創価大学工学部 生命情報工学科 TBA TBA 戻る Copyright (c) 2004- Tetsuo
初めて学ぶソートアルゴリズムは何がいい？ | スラド Slashdotに聞け
ソートについて学ぶといえばまずストレートインサーションあたりから入り、バブルソートが出てくるのはソートの章の中頃、というのが昔の定番だったように思います。 ところが最近では、定番としてバブルソートを出してくる解説WEBページや、 ソートの章の最初の事例がバブルソート（単純交換ソート）を出してくるアルゴリズムとデータ構造の書籍があるのを発見し、びっくりしました。 はたしてソートについて学び始めるときに、最初に取り組むアルゴリズムはどれが適切なのでしょうか。バブルソートははたして適任でしょうか？
ボゴソート - Wikipedia
ボゴソート (bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。「bogo」は、"bogus"[1]に由来する。 英語では、random sort(ランダムソート), shotgun sort(「数撃ちゃ当たる」ソート), monkey sort(「猿でもできる」ソート) などといった表現がある。なお最後のものは「猿でもできる」というよりも、無限の猿定理を指しているかもしれない。 トランプを順に並べる場合を例にすると、次のようになる。 トランプ52枚の束を放り投げて、ばらばらにする。 1枚ずつ無作為にすべてを拾い集める。 ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。 カードの束をひたすらシャッフルし続けて順番に並ぶまで待つアルゴリズムと考えてもよ
DO++ : 乱択アルゴリズム
「乱択アルゴリズム」が共立出版から出ているので読んでいます 乱択アルゴリズム(wikipedia)（ランダマイズドアルゴリズムの方が一般的かもしれない）はアルゴリズムの中に（擬似）乱数が含まれており、動作が決定的ではなく、乱数に依存して動きます。 有名な例では、クイックソートのアルゴリズム中にピボットを選択するところがあるのですが、そこを決定的に最初や真ん中の値ではなく、適当に乱数でランダムに選んだ場合がそれに当たります。 クイックソートは最悪計算量が要素数がnの時、O(n^2)かかってしまう問題点がありますが、ランダムにピボットを選んだ場合、かなり高い確率でO(nlogn)で動作することが言えます。もっとはっきりいうと、比較の回数がαnlogn（αは5よりちょっと大きいぐらい）より大きくなる確率は1/(n^2)以下だということが言えます。つまりnが大きい場合は殆ど間違いなくO(nlogn
著名ソーシャルメディアが使っているアルゴリズムを大公開！ | Moz - SEOとインバウンドマーケティングの実践情報
“アルゴリズム”は、もっとも非人間的なものの代表だともいえる。ソーシャルメディアにとって、そのアルゴリズムが不可欠だというのは、実に皮肉めいている。 僕はこの間、グーグルがどうやってユーザーデータを集めているかについて書いた記事を掲載した（前編、後編）。今回は、著名なソーシャルメディアサイトが、ユーザーデータを活用する上でどのようにアルゴリズムを用いているのか、白日の下にさらそう。 ソーシャルメディアを成り立たせているのは人間の力だが、ユーザーが入力したデータを利用できる状態にする仕組みは、アルゴリズムによって作られている。現在活動している無数のソーシャルメディアサイトで実証済みのことだが、ユーザーの関与とアルゴリズムによる処理ルールの上手いバランスを見出すことは、とても難しくなりがちだ。これから紹介するアルゴリズムは、悪意のないユーザーと結びついて初めてうまくいくものだ。 人気ソーシャル
組み合わせ最適化問題とぷよぷよ - おびなたん☆
先月の電子情報通信学会論文誌の「組合せ最適化問題としてのぷよぷよの連鎖数判定問題」を読むことができた。過去にぷよぷよというゲームそれ自体についての論文が無い*1ので、その数理モデルの定義から議論を始めている。で、結論として4色以上のぷよぷよでは、ある盤面と落ちてきたピース列から連鎖数を判定することはNP完全であることを証明している。以後の課題としては、4色以下のときに、NP完全となるかどうか。さらに関連研究で、与えられたぷよが全て落ちたときに、全消しできるかどうかはNP完全であることも分かっているらしい。 ぐぐってみると、第一著者の松金輝久さんは「第２回ぷよマスターズ」決勝戦進出者。趣味が功奏しての論文ということか。 *1:ゲームのWebサイトをリファレンスしている
ゲームと困難性 - 186 @ hatenablog
前置き CiNii - ぷよぷよはNP完全 はてなブックマーク - CiNii - ぷよぷよはNP完全 全て頭に一般化が付きます. 色々結果はありますが, 問題の定式化によって当然難しさが変わりますのでご注意を. 定義は元論文を見て確認してください. 2人ゲーム オセロ PSPACE完全 (岩田, 笠井 1994) 将棋 EXPTIME完全 (安達, 亀川, 岩田 1987) 囲碁 EXPTIME完全 チェッカー EXPTIME完全 (Robson 1984) チェス EXPTIME完全 一般化しりとり PSPACE完全 マスターマインド NP完全 (de Bondt 2004, Stuckman and Zhang 2005) 一般化アマゾン PSPACE完全 (清見, 宇野 2005) シャノンのスイッチングゲーム PSPACE完全 1人ゲーム 一般化詰め将棋 EXPTIME完全 (横
GoogleのMapReduceアルゴリズムをJavaで理解する
GoogleのMapReduceアルゴリズムをJavaで理解する：いま再注目の分散処理技術（前編）（1/2 ページ） 最近注目を浴びている分散処理技術「MapReduce」の利点をサンプルからアルゴリズムレベルで理解し、昔からあるJava関連の分散処理技術を見直す特集企画（編集部） いま注目の大規模分散処理アルゴリズム 最近、大規模分散処理が注目を浴びています。特に、「MapReduce」というアルゴリズムについて目にすることが多くなりました。Googleの膨大なサーバ処理で使われているということで、ここ数年の分散処理技術の中では特に注目を浴びているようです（参考「見えるグーグル、見えないグーグル」）。MapReduceアルゴリズムを使う利点とは、いったい何なのでしょうか。なぜ、いま注目を浴びているのでしょうか。 その詳細は「MapReduce : Simplified Data Proc
覆面していても顔認識できる新しいアルゴリズム | WIRED VISION
覆面していても顔認識できる新しいアルゴリズム 2008年3月26日 サイエンス・テクノロジー コメント： トラックバック (0) Bryan Gardiner Allen Yang氏の顔認識アルゴリズムを使うと、たとえ画像が破損していたり、部分的にさえぎられていても、該当する人物を的確に見つけ出すことが可能だ。Photo: Allen Yang 忍者の覆面はもう意味がない。カリフォルニア大学バークレー校とイリノイ大学アーバナ・シャンペーン校(UIUC)の研究者たちが開発した新しい顔認識アルゴリズムは、たとえ目、鼻、口の部分が不明瞭でも、90％から95％の正確さで個人の顔を認識できるのだ。 「多くのアルゴリズムでは、目、鼻、口といったいわゆる重要な顔の特徴を使って個人を確認している」と、新しいアルゴリズムを開発したバークレー校工学部の研究者Allen Yang氏は述べる。 「しかし、それだと
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 こんなことやって意味あるのかどうか正直言って迷いました。プログラマはたいてい知っているような内容だし見る人もいないんじゃないかと思いましたが、これからプログラミングを始めてみようという方にとっては参考になるかもしれないし、何よりも自分にとって頭の中を整理できたりするので、これから定期的にやっていこうかと考えてます。 ところで、紹介する内容はほとんど過去に出版された書物関係から抜粋しています。一応下の方に参考文献として挙げておきますので興味を持たれた方は書店などで探してみてはいかがでしょうか？ ということで、まずはライン・ルーチン(画面に直線を描画する)についての紹介です。
Animated Sorting Algorithms
Discussion These pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to: Show how each algorithm operates. Show that there is no best sorting algorithm. Show the advantages and disadvantages of each algorithm. Show that worse-case asymptotic behavior is not the deciding factor in choosing an algorithm. Show that the initial condition (inp
はてな村の地図『HatenarMaps』を公開しました - kaisehのブログ
『はてな村』のアナロジーを本当に地図にできたら面白いだろうなと思って、週末を潰して作ってみました。TopHatenarが蓄積しているDBを一部活用したサービスになっています。 Blogopolis このサービスを簡単に説明すると、はてなダイアリーのユーザに、獲得ブクマ数に応じた領土面積を割り当て、さらに似た者同士の領土を隣接させるという試みです。 地図の全体を見渡すことで、はてダの大まかなトレンドを掴むこともできるし、スケールを拡大していけば個別記事に到達することもできます。さらに、Google Mapsで検索するような感覚ではてなidやキーワードを入力して地図を探索したり、「去年と今年で勢力図がどう変わったか」を調べることもできます。 HatenarMapsはTopHatenarと同様、Javaで開発しました。フレームワーク構成もTopHatenarと一緒で、Cubby+Mayaa+S2
Safe from the Losing Fight » How to implement smudge and stamp tools
smarter than your average squirrel, on most non-acorn related topics I like the smudge tool because, like the brush, it has a real world analog, which means it’s a bit easier for new users to figure out how it works. Just about everyone has played with finger paints before, and knows what happens when you drag your finger through paint. I originally thought the smudge tool would be rather complex.
統計的機械学習(Hiroshi Nakagawa)
統計的機械学習 (under construction) 導入ppt pdf 情報の変換過程のモデル化 ベイズ統計の意義 識別モデルと生成モデル 次元の呪い 損失関数, bias, variance, noise 数学のおさらいppt pdf 線形代数学で役立つ公式 情報理論の諸概念 (KL-divergenceなど) 指数型分布族、自然共役 正規分布(条件付き、および事前分布) 評価方法ppt pdf 順位なし結果の評価(再現率、精度、適合率、F値) 順位付き結果の評価 線形回帰と識別ppt pdf 線形回帰 正規方程式 正規化項の導入 線形識別 カーネル法ppt pdf 線形識別の一般化 カーネルの構築法 最大マージン分類器 ソフトマージンの分類器 SVMによる回帰モデル SVM実装上の工夫 モデル推定ppt pdf 潜在変数のあるモデル EMアルゴリズム 変分ベイズ法 Expecta
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
はてなブログ | 無料ブログを作成しよう
Octave
CiNii - ぷよぷよはNP完全