アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
過去10年間のComputer Science系論文で被引用数トップ10を作ってみた - 情報科学屋さんを目指す人のメモ（FC2ブログ版）
何かのやり方や、問題の解決方法をどんどんメモするブログ。そんな大学院生の活動「キャッシュ」に誰かがヒットしてくれることを祈って。 2000年以降の論文に限定して、 CS系論文の被引用数ランキングを作って分析してみた。 この作業を通じて予想以上に得るものがあった。 ランキングの作り方 CiteSeerXが公開している「Most Cited Computer Science Articles (2010/9/14)」を元データに採用した。 ここから2000年以降の文章に限定した後、ハンドブックや雑誌記事などを取り除いて論文だけのランキングを作成した。 被引用数は時間が経つほど増える一方なので、2000年・2001年あたりの論文が有利であることに注意する必要がある。 ただし、このことがかえって得るものを増やしてくれた。 アブストラクトをチェック 良い機会であるので、 各論文の概要や結論をチェック
Peter Selinger: Potrace
For changes prior to version 1.14, see the file NEWS. For a more detailed list of changes, see the ChangeLog. September 17, 2019: Release 1.16. This release consists of bugfixes and minor portability improvements. A potential arithmetic overflow was fixed. Rotation angles are now normalized to between -180 and 180. We now use binary file I/O on the OS/2 platform. The test suite tolerances were adj
常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream (legacy)
TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 なん…だと
Confidence Weightedで ランク学習を実装してみた
2. 自己紹介：徳永 拓之 ● twitter id:tkng ● (株) Preferred Infrastructure 勤務 ● 守備範囲：レコメンド・NLPなど ● カレーを食べるのが趣味 ● 上野デリーのコルマカレーが好きです ● 早売りの週刊少年ジャンプを読むのも好き 3. 宣伝：NLP2011で発表します C4-6 日本語かな漢字変換における識別モデル の適用とその考察 ○徳永拓之, 岡野原大輔 (PFI) 3月10日(木) 13:00-15:30 (A1-201教室) ● 今日の発表でここが一番NLPっぽい 4. 発表の概要 ● ランク学習とは ● Confidence Weightedとは ● Confidence Weightedによるランク学習 中身の薄い発表なのでゆったりと リラックスした気持ちで聞くのが オススメ！
ソートアルゴリズムを映像化してみた - jsdo.it - Share JavaScript, HTML5 and CSS
よくあるやつです。ぼんやり眺めてると、とても癒されます。 2014/2/25 追記: 全面的に書き直しました。 // https://github.com/norahiko/sort-visualize var helper = { range: function(min, max) { var res = []; for(var i = min; i < max; i++) { res.push(i); } return res; }, shuffle: function(ary) { for(var i = ary.length - 1; 0 <= i; i--) { var rnd = Math.random() * (i + 1) | 0; helper.swap(ary, i, rnd); } }, swap: function(ary, a, b) { if(a < 0 ||
Rediscover the Monte Carlo - 西尾泰和のはてなダイアリー
僕個人はゲームの思考ルーチンを作ることなどには興味があるので、みんな知っていることだと思っていたのですが、意外と「現在世界最強の囲碁の思考ルーチンはモンテカルロ」ってのは知られてないみたいですね。うっかりすると「そんなわけないだろー」とか言われてしまう。その根底には「モンテカルロはとても収束が遅くて使いものにならない」という過去の記憶があるのかなー。ちょうどJavaScriptが使いものにならないおもちゃ言語だと思われていたように。 囲碁の思考ルーチンを著しく進化させた新しいモンテカルロが昔の単純なモンテカルロとどう違うかというと、UCB1という評価関数で「もっと探索するとヨサゲな局面」を判断して、ヨサゲな局面から優先的に探索するという点なんだけど、そういう定性的な話をしてもピンと来ないよね。同じ発想をモンテカルロで円周率を求めるプログラムに適用したら収束の速さが定量的にはっきり見えて面白
【公式アナウンス】Google、スパムコンテンツの検出アルゴリズムを強化
GoogleのMatt Cutts(マット・カッツ)氏は、オンページのスパム的なコンテンツを検出する仕組みを改良したことを米Googleの公式ブログでアナウンスしました。 “オンページ”のコンテンツというのは、単語や文など、ページに書かれているコンテンツのことです。 たとえば、自動ツールで生成した文章や自作自演のブログコメントなど、スパムにありがちな言葉が繰り返されている価値のないコンテンツです。 この技術の向上はページ単位での検出が可能になってます。 他のサイトをコピーしたりオリジナルコンテンツに乏しかったりするサイトに主に大きく影響を与えるアルゴリズム変更も今回の変更に含まれています。 またハッキングを受けたサイトを検出する能力も大幅に向上させました。 Matt Cutts氏によれば、Googleの検索結果に出てくる英語のスパムサイトは5年前の半分以下に減っており、英語以外の他の言語で
オンライン最適化とRegret最小化 - DO++
大量のデータから、何か有益な情報を求める問題の多くは最適化問題を解くことに帰着されます． 最適化問題とは与えられた関数fの値を最小（最大）にするような変数xを探すといった問題です。 例えば、機械学習（これを利用する自然言語処理、情報検索など）、画像処理、AI(ロボットの経路制御）、 など多くの分野で最適化問題は登場します。 その中でもオンライン最適化（機械学習の文脈でいえばオンライン学習）と呼ばれる最適化手法は 実用性の高さと実装のしやすさから多く利用されるようになってきました。 このオンライン最適化は近年Regret（後悔）最小化というゲーム理論などで使われていた枠組みで 解析されることが多くなってきました。 今回はこのRegret最小化について簡単に解説してみようと思います。 （機械学習が詳しい人向けに補足すると、VC次元など他の機械学習を解析する手法と比べてRegret最適化の面白い
kd tree（kd木）を使った近傍点検索 - higepon blog
kd tree を使った近傍点検索のメモ。 kd tree の日本語の説明はkd木 - 日本語版 Wikipedia。 近傍点検索の擬似コードがあり、日本語版の元となっているのはkd-tree - 英語版 Wikipedia。 実際に動くコードで分かりやすいものは弾さんのところ。404 Blog Not Found:algorithm - 最近点検索をkd-treeで。 他には An intoductory tutorial on kd-trees という PDF があるが難しい。 kd tree の構築は、平衡木にするためのロジックがいくつかある事をのぞけばとても簡単。弾さんのコードを読めば分かると思う。 近傍点の検索は k 次元で説明されているものが多く分かりづらいと思った。自分で単純な2次元の場合にして考えれば良い。 流れは以下の通り。 検索対象点 p を kd tree 上で bi
正規表現で素数判定 - NO!と言えるようになりたい
追記：ハッキリ言ってこの正規表現はネタなので，実際に素数判定を行いたい場合は，もっと別な賢いアルゴリズムを使ったほうが良いです 正規表現で素数が判定できるという記事を見たので試してみた． http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/ この記事によると /^1?$|^(11+?)\1+$/ という正規表現を使うと，素数判定が出来るらしい．ある整数 n が素数かどうか判定したい場合は，"1" * nという文字列がこの正規表現にマッチするかどうかを調べればよく，マッチすれば非素数，マッチしなければ素数となる．ただし，"1" * n は，例えば，n が 4 ならば "1111" と 1 が 4 回連続して続く文字列となる． Rubyで書いた素数判定プログラムはこん
PFI seminar 2010/05/27 統計的機械翻訳
8. 統計的機械翻訳(SMT: Statistical Machine translation)パラレルコーパスを用いて翻訳ルールを獲得c.f. ロゼッタストーン言語の専門家がいなくてもよい（国家的な理由も）高品質・大量のパラレルコーパスは国連・EUの国際会議の議事録などで大量に入手可LDC, Acquis, OPUS, Communautaire, …例：Europarlの場合 11言語毎に4000万単語言語のスケーラビリティが高いコーパスさえあれば良い c.f .Google 50言語間 9. 統計的機械翻訳の歴史 (1/2)～1980 用例ベース機械翻訳1989 IBMResearchによる著名な論文NLP業界での引用数第2位 (約1000件）翻訳システムのパラメータをパラレルコーパスから自動推定する簡単な手法から順に IBMモデル1 - 5がある提案者自身らは金融業界へと去っていっ
病みつきになる「動的計画法」、その深淵に迫る
数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。 もしあなたが知ってしまったなら――病みつきになる動的計画法の集中講義 前回の『アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった』で動的計画法とメモ化再帰を説明しましたが、前回の説明ではまだ勘所をつかめていない方がほとんどでしょう。そこで、これらを完全にマスターするため、今回はもう1つ具体例を挙げながら練習したいと思います。 どういった問題を採用するかは悩みましたが、非常に有名な「ナップサック問題」を取り上げて説明します。 ナップサック問題とは以下のような問題です。 幾つかの品物があり、この品物にはそれぞ
あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定
あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定：makeplex salon（2/2 ページ） 問題 麻雀の手牌が入力として与えられたとき、「待ち」を出力するプログラムを書いてください。 字牌なし・萬子のみの想定、つまり、いわゆる「チンイツ」限定で結構です（プログラミングの本質的にはこの限定でまったく問題ないため） 1～9の数字13個からなる文字列を受け取り、できている順子・刻子・アタマを()、待ちの部分を[]でくくって出力してください 面前かつ槓子は存在しない前提でOKです ()[]の出力順は自由ですが、順序だけが違うものは同一視してください（例：111222を刻子2つで構成するとき、(111)(222)が(222)(111)に入れ替わるだけのものは同一解答とします） 多面待ちのときも含めすべての待ちを出力してください 待ちがないときは何も出力しないでください コメント
あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定
あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定：makeplex salon（1/2 ページ） この問題ができたから優秀な人材とは限らないけれど、できない人は“ほぼ確実に”優秀ではない――プログラマーの皆さまの実力を計るコーディングスキル判定問題を用意しました。あなたはこの問題が解けるでしょうか？ 新年度が始まり、新たに社会人となった読者の方も多いかと思います。あるいは、転職で心機一転がんばろうという読者もおられるでしょう。 あなたがもしプログラマーやSEといった職種であれば、ぜひ面白い仕事を手がけていただきたいと思いますが、そもそも開発分野で本当に面白い仕事とは何かを考えたことはありますか？ その答えを論ずる前に、少し前に話題となったトピックを取り上げたいと思います。それは、岡嶋大介氏の「人材獲得作戦」についてです。ご存じない方のために少し補足しておくと、岡嶋氏は、株価
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
大規模ソーシャルサーチエンジンの構造 - file-glob こと k.daibaの日記
はじめに Googleのように，どのドキュメントが適切なのかを選ぶのではなく，質問を誰にするのが適切かを選ぶ検索エンジンをAardvarkという会社が作り，その構造を論文で公開しました．この会社はもともとGoogleの社員だった人達が作った物で，最近Googleが買い上げました．今日はその論文の要旨をまとめてみました． タイトルと著者 タイトルはGoogle創始者のLarry PageさんとSergey Brinさんが1988年に発表した"Anatomy of a Large-Scale Hypertextual Search Engine"と韻を踏んでいます．論文を発表したのは，Aardvark社のDamon HorowitzさんとStanford Univ.のSepandar D. Kamvarさんです．以下小見出しが章，少々見出しが節という形式で進めます． ABSTRACT Aard
「ガベージコレクションのアルゴリズムと実装」という本を書きました。
gcbook, gcai, GCGCLoverのみなさん、お待たせしました。「ガベージコレクションのアルゴリズムと実装」の情報公開です。 書名：ガベージコレクションのアルゴリズムと実装 著者：中村 成洋／相川 光 監修：竹内 郁雄 ページ数：472ページ 本体価格：3,200円 発売開始日：2010年3月17日（水） ※地域・書店によって遅れることがあります ISBN：978-4-7980-2562-9 C3055 読み所 本書は次の2つのテーマを扱います。 1.GCのアルゴリズム（アルゴリズム編） 2.GCの実装（実装編） アルゴリズム編では、これまでに考案されてきた数多くのGCアルゴリズムの中 から、重要なものを厳選して紹介します。伝統的かつ基本的なものから、やや 高度なアルゴリズムを選定しています。GC独特の考え方や各アルゴリズムの特 性などを理解していただくのがアルゴリズム編の最大
Bayesian Setsによる関連文書検索システムStupa - mixi engineer blog
都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。 Bayesian Setsとは Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に"Inspired by Google Sets"と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、 クエリ 出力 apple, banana chocolate, strawberry, vanilla, cherry, ... apple, macintosh software, windows, mac,
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
紙だけでサイトごとに異なるパスワードを生成する暗号、米研究者が考案 