いまさら学ぶPageRankアルゴリズム - け日記
情報検索 (IR) のみならず、いろいろな分野で応用されているPageRankアルゴリズムについてまとめます。 PageRank PageRankはリンク分析 (link analysis) に分類されるアルゴリズムで、1998年に提案されました (提案論文PDF) 。以下の特徴を持ってます。 リンク構造が明確なコンテンツに向いている 最初はWebの検索エンジンに適用された クローリングで取得したhtmlファイルのリンクタグを抽出するだけで良いため 現在はソーシャルネットワークや自然言語処理などでも応用されてます Python: LexRankで日本語の記事を要約する - け日記で紹介した要約アルゴリズムもPageRankから着想を得てます コンテンツの解析だけでランキング化ができる 検索結果に対してこのページはクリックされた/されなかった、などのフィードバックが不要 アルゴリズムを大雑把
強くなるためのプログラミング -様々なプログラミングコンテストとそのはじめ方- - ぴよぴよ.py
みなさんは何のためにプログラミングをしていますか？ 仕事のため、何かをつくるため。 それも良いけれど、「強くなる」ためにプログラミングしてみませんか。 様々なジャンルのプログラミングコンテストとまだ見ぬライバルたちがあなたを待っています。 今回はアルゴリズム/AI/機械学習/セキュリティ等の様々なジャンルのコンテストとその始め方について紹介したいと思います。 ※これはPyConJPでの発表を文字におこしたものです。が、Pythonの話は殆どないです。 プログラミングコンテストとは？ すべてのコンテストに共通する、「コンテストに参加する利点」 1. 自分と同じ問題を解いた、他の人の解法を知ることができる 2. 同じコンテストに出ていた、たくさんのライバルと知り合える アルゴリズムのコンテスト 問題1 問題2 TopCoder Single Round Match CodeForces AtC
「結城浩さんのCodeIQ問題は、なぜ面白いのか？」を7つのポイントで解説！｜CodeIQ MAGAZINE
CodeIQで結城浩さんが出題する問題はいつも大人気！なぜなら結城さんは解答者をどう楽しませるかを考えつくしているから。 今回は結城浩さんご自身に「なぜこんなに面白い問題を作れるのか」そのこだわりを７つのポイントに絞って書いていただきました。 by 馬場美由紀 （CodeIQ中の人） はじめに こんにちは、結城浩です。いつもCodeIQでの出題にご解答いただき、ありがとうございます。 今日は、CodeIQで出題しているときに私が心がけていることをお話しします。 なお、以下でお話しすることはあくまで私が出題する問題に対する心がけです。CodeIQにはたくさんの出題者さんがバリエーション豊かな出題をしています。他の問題に対して批判するという意図はまったくありませんので念のため。 最高の問題 出題するときに心がけていることの第一、それは最高の問題を作ろうということです。 せっかく時間を掛けて問題
Natural Order String Comparison
by Martin Pool This project has moved to github.com/sourcefrog/natsort. Computer string sorting algorithms generally don't order strings containing numbers in the same way that a human would do. Consider: rfc1.txt rfc2086.txt rfc822.txt It would be more friendly if the program listed the files as rfc1.txt rfc822.txt rfc2086.txt Filenames sort properly if people insert leading zeros, but they don't
「どうぶつしょうぎ」の完全解析
田中哲朗 女流棋士の北尾まどか初段によって考案されたボードゲー ム どうぶつしょうぎ(Wikipedia: どうぶつしょうぎ) の初期局面 から(相手のライオンを取れる時は必ず取るという条件で)到達可能な局面すべ てを求め，後退解析(retrograde analysis)により，すべての局面の「勝ち」/ 「引き分け」/「負け」と双方最善を尽くした時の手数を求めるプログラムを作成 しました． ゲーム情報学研究会での発表について 2009年6月26日に開催された第22回ゲーム情報学研究会で発表した際の資料と，プレゼンテーション資料を置きます． なお，資料の図5に誤りがあります．正しい図は， となります． また，参考文献として2009年6月時点で「どうぶつしょうぎ」のオフィシャルサイト を記載しましたが，現在は有効ではないようです． プログラム dobutsu-src-20150109.tar
大規模グラフアルゴリズムの最先端 - iwiwiの日記
昨日，PFI セミナーにて「大規模グラフアルゴリズムの最先端」というタイトルで発表をさせてもらいました．スライドは以下になります． 大規模グラフアルゴリズムの最先端 View more presentations from iwiwi 当日は Ustream もされており，録画された発表もご覧になれます． http://www.ustream.tv/recorded/19713623 内容の流れとしては，以下のようになっています． 導入 アルゴリズム界隈での話題 最新の研究動向 道路ネットワークでの最短路クエリ処理 基礎的な手法：双方向 Dijkstra，A*, ALT 最新の手法：Highway Dimension + Hub-Labeling Algorithm DB 界隈での話題 最新の研究動向 複雑ネットワークでの最短路クエリ処理 基礎的な手法：ランドマークを用いた最短距離推定 最
Additive Pattern Database Heuristics
Journal of Artificial Intelligence Research 22 (2004) 279-318 Submitted 04/04; published 11/04 Additive Pattern Database Heuristics Ariel Felner felner@bgu.ac.il Department of Information Systems Engineering, Ben-Gurion University of the Negev, Beer-Sheva, 85104, Israel Richard E. Korf korf@cs.ucla.edu Department of Computer Science, University of California, Los Angeles, 90095 Sarit Hanan sarit@e
Why are virtually all elevator algorithms so inefficient, and what are the reasons they have yet to be optimized?
Answer (1 of 14): When I was younger I was at a hotel with some family. They stuck all the kids in one room, and taking advantage of this, I wandered around in the middle of the night. I took the elevator to the ground floor, pressed all the buttons and left. I came back a few seconds later, and ...
簡潔データ構造(Succinct Data Structure)で最初に読むと良さそうな論文 - EchizenBlog-Zwei
最近、簡潔データ構造(Succinct Data Structure)まわりの論文を色々読んでいる。その中で良さそうなものをいくつかピックアップしてみた。まだ調査中なので他に良いものがあったら教えてもらえると嬉しいです。 (1) Space-efficient Static Trees and Graphs(link) G. Jacobson; IEEE1989 まずはLOUDS論文。簡潔データ構造の元祖なので最初に読むと良さげ。 (2) Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees and Multisets(link) R. Raman, V. Raman, and S. S. Rao; SODA2002 簡潔ビットベクトルは通常n+o(n)なんだけど、これをnH0+o(n)にしたよ、
合議アルゴリズムはインチキだ - やねうらおブログ(移転しました)
昨年の10月11日に開催された清水市代女流王将とコンピュータ将棋「あから2010」との対局は記憶に新しい。 あから2010は、169台676coreを使った合議によるコンピュータ将棋マシンだった。 「文殊」の論文*1が発表されたときから、私は「合議は全く意味がないし、普通にクラスター並列化したほうが強い」と主張し続けてきた。 「1台のマシンと、そのマシンを3台使って合議させたものとを対局させて、3台合議のほうが有意に勝ち越したから合議は意味がある」みたいな結論を出すのはおかしい。3台のマシンで普通にクラスター並列化したものと、3台で合議したものとをなぜ真っ先に比較しないのか？ 3台のマシンで単純にクラスター並列化したものより3台のマシンで合議したもののほうが圧倒的に弱ければそれは単にマシンリソースの無駄遣いに他ならないし、その比較すらせずに169台のマシン用意しましたって馬鹿じゃないの。大
徹底解剖「G1GC」 アルゴリズム編
書誌情報 著者: 中村成洋 発行日: 2011-06-27 最終更新日: 2012-02-03 バージョン: 1.0.0 ページ数: 62ページ(A4PDF版換算) 対応フォーマット: EPUB, PDF 出版社: 達人出版会 対象読者 高度なGCのアルゴリズムに興味のある方。すでに『ガベージコレクションのアルゴリズムと実装』を読まれていて、続きを読みたい方 著者について 中村成洋 中村成洋（nari）はネットワーク応用通信研究所に勤めているRubyistです。仕事ではRailsを使ってWebアプリケーションを開発しています。高校を卒業してからはアイス工場に2年半いて、それからプログラマに転職しました。 GCに魅了されてしまった人間で、GC歴は4年になります。CRubyのコミッタとして1年に1度のペースでGCの改善に取り組んでいます。去年はCRubyに新しく取り込まれたLazySweepG
SHA1 padding attack - yasulib memo
勇士QさんのKernel/VM Advent Calendar 18日目: CTF 暗号問題 - 勇士Qの日記の問題の解答を書かせて頂きます。まだ、解いていなくて、挑戦したいと言う方は以下、ネタバレを含むのでご注意下さい。なお、勘違い部分もあると思うので間違いがあれば指摘して頂けるとありがたいです。 この問題はCODEGATE2010 CTFの問題が元みたいです。CODEGATEの問題は色んな所で解説が上げられているみたいです。CodeGate 2010 Challenge 15 – SHA1 padding attack 問題の内容はKernel/VM Advent Calendar 18日目: CTF 暗号問題 - 勇士Qの日記を見てください。 目的はadmin権限で認証を突破することです。サーバの認証部分はX'masのやつのヒント的なもの - 勇士Qの日記のようになっています。 つま
10兆までの素数リスト - 雷雲の変奏曲
プログラミングコンテストチャレンジブックを読んでいたら、素数リストの作り方が出てきた。 そういえば、１０兆までの素数リストを作ってみる、なんて記事があったな。 これだ http://itpro.nikkeibp.co.jp/article/Watcher/20100519/348242/?ST=develop 読み返しているうちに、ついつい挑戦してみる気になってしまった。 色々試して意外だったのが、10億までの素数をリストアップした場合でも「試し割り」より「エラトステネスの篩」の方が100倍以上も高速だったことだ。リストが大きくなればその差はますます開いていく。 メモリ上の広い範囲をまんべんなくアクセスするエラトステネスの篩は、実際には効率が悪いのではないかと思ったりしたのだが、見当が外れてしまった。 考察してみるに 試し割りは意外と無駄が多い。まず素数の密度だがn/log(n)に従うらし
2010-11-25 - きしだのはてな - 技術力をあげたいプログラマが読んでおかないと話にならない本10冊
ここにあげた本じゃなくてもいいので、同じ分野でなにか読むとか、本に書いてあるほど詳しくなくてもそれなりに知識をもっておくべき本。 アルゴリズムクイックリファレンス 作者: George T. Heineman,Gary Pollice,Stanley Selkow,黒川利明,黒川洋出版社/メーカー: オライリージャパン発売日: 2010/04/26メディア: 単行本（ソフトカバー）購入: 11人 クリック: 656回この商品を含むブログ (72件) を見る まずはアルゴリズム。クイックって書いてあるけどぜんぜんクイックじゃないｗ。各言語で書かれた入門書を読んでもいいと思う。 実際のプログラムにアルゴリズムの知識を活かすということを知りたいならプログラミングコンテストチャレンジブックがおすすめ。 プログラミングの基礎 ((Computer Science Library)) 作者: 浅井健一
大規模データで単語の数を数える - ny23の日記
大規模データから one-pass で item（n-gram など）の頻度を数える手法に関するメモ．ここ数年，毎年のように超大規模な n-gram の統計情報を空間／時間効率良く利用するための手法が提案されている．最近だと， Storing the Web in Memory: Space Efficient Language Models with Constant Time Retrieval (EMNLP 2010) とか．この論文では，最小完全ハッシュ関数や power-law を考慮した頻度表現の圧縮など，細かい技術を丁寧に組み上げており，これぐらい工夫が細かくなってくるとlog-frequency Bloom filter (ACL 2007) ぐらいからから始まった n-gram 頻度情報の圧縮の研究もそろそろ収束したかという印象（ちょうど論文を読む直前に，この論文の7節の
Suffix Array(接尾辞配列)を学びたい人のためのリンク集 - EchizenBlog-Zwei
私がCompressed Suffix Arrayを学ぶのに参考にした資料へのリンクをまとめてみた。 CSAだけじゃなく、これからSuffix Arrayを学ぶ人にも便利かもしれない。 解説記事 # ［を］ Perl による Suffix Array の実装] SUFARYの開発者、たつを氏による解説 perlで20行くらいでSuffix Arrayが作れる 入門用におすすめ # DO/Suffix Array 岡野原氏によるSuffix Arrayの解説記事 高速化などの高度な話題が豊富 中級者向け # white page Suffix Arrayのリンク集が充実 多くのライブラリが公開されている ツール・ライブラリ # SUFARY 臨時復旧ページ たつを氏によるSuffix Arrayライブラリ 非常に使い勝手が良い # sary: Suffix Arrayのライブラリとツール 高
われわれは100倍、速く書けない - やねうらおブログ(移転しました)
西川 ええと……（笑）。受注生産って、人数に比例してもうけるじゃないですか。でも、われわれは人の100倍は速く書けると思っている。じゃあ、その人に1カ月、その分を払ってくれるのかというと、受注じゃ絶対、無理でしょう。でも、ソフトウェアだと可能。 (中略) 西川 同じ「エンジニア」という職種でも、生産性は100倍くらい違いますよね。コードをその人がただ書くという部分だけじゃなくて、例えばチューニングされたコードをすぐ書けるなら、結果的にシステムが速く動く。遅いコードを書いて100台マシンを使用するとなると、いろいろな人がシステム構築にかかわらないといけない。でも同じ条件で100倍速いコードを書けば、1台のマシンで済む。運用も圧倒的に楽になる。だから、生産性はそのくらい変わってくると思います。 第5回 「われわれは100倍、速く書ける」――PFI 西川徹 http://lab.jibun.at
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Geometry on the Sphere: Google's S2 Library
https://www.saa.or.jp/journal/prize/pdf/2014_oki.pdf
システム・エンジニアの基礎知識