Dynamic Programming vs Divide-and-Conquer | Trekhleb
TL;DR In this article I’m trying to explain the difference/similarities between dynamic programing and divide and conquer approaches based on two examples: binary search and minimum edit distance (Levenshtein distance). Also, in the Content-aware image resizing in JavaScript article I went through another powerful but yet simple example of dynamic programming for the Seam Carving algorithm. You mi
(解説) はてなブックマークにおけるアクセス制御 - 半環構造に基づくモデル化 - Hatena Developer Blog
こんにちは、シニアアプリケーションエンジニアのid:taraoです。この記事ははてなデベロッパーアドベントカレンダー2015の10日目です。昨日はid:tapir320によるはてなの組織開発についてでした。 先月開催されたWebDB Forum 2015で、「はてなブックマークにおけるアクセス制御: 半環構造に基づくモデル化」というタイトルの発表をしました。 はてなブックマークにおけるアクセス制御 - 半環構造に基づくモデル化 from Lintaro Ina 発表資料には多くの方に興味をもっていただけたようですが、わかりにくい点も多かったのではないでしょうか。スポンサー企業としての技術報告セッションとはいえ学術会議での発表なので理論面と独自の工夫点にフォーカスした内容であったり、口頭での発表のしかたに大きく依存したスライドの遷移方法になっているので、この資料だけで細かいところまで理解しよ
確率的カウントアルゴリズム Morris Counting の話 - Debug me
ちゃお。舞い降り......† ハイパフォーマンスPython 作者: Micha Gorelick,Ian Ozsvald,相川愛三出版社/メーカー: オライリージャパン発売日: 2015/11/20メディア: 大型本この商品を含むブログ (3件) を見る 11/20にオライリーのHigh Performance Pythonの日本語版が出るようです。 著者のMicha Gorelickさんの紹介文がエキセントリックなことで一部で話題沸騰中な本です。(未来から来たマッドサイエンティストらしい...†) 私は先に出た英語版を読んでMorris Countingという推定カウントアルゴリズムが面白いと思ったんですけど、検索してみたら日本語だとあまりヒットしなかったので、今回はそのお話をしたいと思います。トニーモリス (有名人) の話じゃないよ〜。 さてMorris Counting [Mor
正月の酔っ払い物理学者が数学者の皮を被った天使に出会うお話 | カメリオ開発者ブログ
あけましておめでとうございます。白ヤギの物理担当、シバタアキラ(@punkphysicist)です。 皆様はどんなお正月を過ごされましたか？日本の正月といえば、おせち、日本酒、おばあちゃん、そしてパズル、ですよね。私の正月はそんな感じでした。お節をたらふく食べ、美味しいお酒でほろ酔い気分になっている私の横で、黙々とおばあちゃんがパズルをやっているのに気づいたのです。部屋中をフワフワしている私とは全く対照的に、微動だにせずパズルを続けるおばあちゃん。御年迎えられると辛抱強さが半端ない。 そんなおばあちゃんがやっていたのはかわいいチョコレートのピースとは裏腹にこんな挑発的な文言の書かれたパズルです（この記事はアフィリエイトではありませんが、写真をクリックすると買えます） 何時間たっても答えが出ないおばあちゃん、辛抱強さは人一倍強いですが、私も何とか助けてあげたいと思いトライ。しかし日本酒が・・
あなたの英語がどの方言かを判定してくれるサイト WhichEnglish
WhichEnglish?(どの英語?)は、いくつかの英語の質問に答えていくことで、あなたの英語がどの国・地方の英語なのかを判定してくれるというウェブサイトです。ウェブサイトを使った研究をしているGamesWithWor […] WhichEnglish?(どの英語?)は、いくつかの英語の質問に答えていくことで、あなたの英語がどの国・地方の英語なのかを判定してくれるというウェブサイトです。ウェブサイトを使った研究をしているGamesWithWords.orgプロジェクトによるものです。 最初のページで書いているように、”Throw me down the stairs my shoes”という文章は、カナダのニューファンドランド地方では文法的にまったく正しい英語なんだそうです。全然正しい英語に見えませんが、「靴を階段の下にいる私に放ってくれ」という意味なんでしょうかね。 そのような地域ごと
pixiv のタグ情報を用いた「ラブライブ！ School idol project」のカップリングネットワークの構築 - (iwi) 備忘録
はじめに ネットワーク解析やグラフアルゴリズムの研究者がアルゴリズムを実装した際，動作確認のために最初に実行する toy example をどうするかというのは意外と悩ましい．パスグラフやグリッドグラフのような高い対称性を持つグラフや小さすぎるグラフではいまいち動作に確証が持てない．一方，公開されている実データは最も小規模な Karate Club や Dolphin Social Network 等でも目視には大きすぎる．調度良いサイズの，ある程度非自明な形をしており，アルゴリズムによる出力の意味の解釈がある程度可能であり，できれば愛着が持てるグラフデータが必要とされている． そこで，本研究ではそのような用途に適切なグラフデータとして，「ラブライブ！ School idol project」のキャラクター間のグラフを構築する．データの構築には，pixiv に投稿されている二次創作作品のタ
何回で満点とれる？【ちょまど問題に挑む人々】
@chomado さんの「社内のセキュリティ研修のテスト(4択全10問)」を満点をとるまで延々とやらされる場合に何回やり直せば満点を取れるかという問題に立ち向かった人々の記録です。 ■ちょまど問題（引用・加筆） 4択問題10問のテストを全部埋めて提出すると正解数がわかります。 何回提出すればすべての正解を知ることができますか。 続きを読む
ビットコインの応用で、電子書籍を譲渡可能にするアルゴリズム
サトウヒロシ🐰まずは医療費全世代３割負担。現役世代を苦しめる社会保険料を低減しよう @satobtc (1)今日は、ビットコインの経済的側面ではなく、技術的側面から可能になる未来像について、連続ツイートします。 ビットコインのP2Pネットワークは、あるデジタルデータ（コインでは残高＝お金としている）の所有権を中央の認証機関なしに移転することができるというものです。 2014-02-24 15:42:36 サトウヒロシ🐰まずは医療費全世代３割負担。現役世代を苦しめる社会保険料を低減しよう @satobtc (2)これは、計算機科学的にいうとビザンチン将軍問題というもので、だれか管理者がいなくても分散型のコンピュータはお互いに故障や正しいデータを識別できるか、といったような問題です。これに対する実用的なはじめての回答がビットコイン的な仕組みです。 2014-02-24 15:43:49
CodeIQで結城先生が出題されたCrossingが神がかっていた件 - やねうらおブログ(移転しました)
CodeIQで挑戦者数が400人超えという異例の事態になったCrossingとはどんな問題だったのか。twitterでも恐ろしい勢いで拡散され、最終日に100人を超えるチャレンジがあった、この問題。一体どこにそんな魅力があったのかについて考えてみる。 まず、このように注目されるためには満たすべき条件が二つある。 繁盛する飲食店を考えてもわかるように、まず美味しくなければならない。CodeIQで言うと、問題として良問でなければならない。解答後の達成感がなくてはならない。 次に、飲食店なら、その店に入ってみようという気にさせなければならない。入りにくそうなお店でも、料理さえ美味しければその後口コミで広がることもあるだろうが、それだと繁盛するまでに時間がかかりすぎる。だからCodeIQで言うと、まず問題を解いてみようという気にさせなければならない。 このどちらが欠けても駄目である。この問題はこの
JavaScript でオセロを実装する(AI高速化編) | Webシステム開発／教育ソリューションのタイムインターメディア
これまでのあらすじ まともなオセロの対戦AIの作成を開始したものの、 「4手先を読む」だけでも検討にかかる時間が長く、 とても快適に遊べるとは言えない状態でした。 これでは肝心のAIの形勢判断を調整する以前の問題であり、 先読みする手数を増やしてAIの「腕前」を上げることも困難です。 先読みする手数を減らせば快適に遊べるようにはなりますが、 それでは「目先のことしか考えない」弱いAIにしかなりません。 どうにかしてAIの動作速度を改善できないものでしょうか。 ボトルネックはどこにあるのか これまでのオセロの作成過程を振り返ってみましょう。 最初に4×4の最小盤面で一人二役で遊ぶものを実装しました。 これはほとんどの部分が関数型で書かれた明瞭簡潔な実装だったのですが、 その引き換えに全局面を事前に計算するという超富豪的な実装になっていました。 この問題に対しては各局面の計算を遅延評価すること
高速な文字列マッチング - 気ままなブログ
最近は、簡潔データ構造を中心に調べたりしていたけど、文字列マッチングを考えた場合、別のアプローチもあります。そう、grepのような逐次文字列検索ですね。以下の解説がおもしろいです。 http://www.i.kyushu-u.ac.jp/~takeda/papers/IPSJMagazineCPM.pdf CSAとかFM-Indexに隠れてしまっていますが、実はかなり強力です。特に、クエリが固定で、テキストが頻繁に変更されるようなケースでは有効です。中でも使いやすのは、Aho-Corasick法(AC法)ですね。複数のパターンを同時に検索することができます。KMPを拡張した方法です。 AC法については、日本語だと 情報検索アルゴリズム 作者: 北研二,津田和彦,獅々堀正幹出版社/メーカー: 共立出版発売日: 2002/01メディア: 単行本購入: 6人 クリック: 552回この商品を含むブ
汎用ソート殺し - d.y.d.
00:26 12/12/18 BookLive! 7月に出会ってからずっと電子書籍ストアとして BookLive! をひいきにしているのですが、一体どこが好きなのか語りたくなりました。 ITMedia の これでもう迷わない、電子書店完全ガイド という一連の記事の、 電子書籍の端末の話よりストアの話をしましょうよというコンセプトに思いっきり影響されています。 といっても、第一印象が「普通のことが普通にできるので感激した！！」というもので、 つまり今年の前半に使っていた幾つかの電子書籍ストア/専用アプリが残念だっただけかもしれません。 買った本がどこをクリックすれば読めるのか理解するのに10分かかった、とか、 6冊以上買うと本棚アプリから画面外に本がはみ出るので手でいちいち棚を変えて整理しないと読めない、とか。 本当に普通に使えるという以上に特筆することもないんですが、 あ、でも、今年になる
プログラマの実力は経験だけであがらないことがレベル格差につながる - きしだのはてな
プログラマというのは、道具に慣れることが、実力があがることにならないのですよね。だから、勉強せず業務経験だけだとレベルが低いままということになってしまう。 Javaを10年さわり続けて、Strutsを5年さわり続けても、それだけでは、与えられた画面を手際よく作成できるようになるだけで、たとえばStrutsすらよりよく使えるようになるわけではなかったりする。 Javaにしても、「volatileってなんですか？」という問いに、まあ知らないのはしかたないとしても、解説を見ながらですら答えられない可能性がある。 プログラムの反復生産は、プログラミング能力の向上にあまりつながらない。設定や記述に慣れるだけだ。そして、この「慣れ」というのには「難しいからそもそも実装を回避する」というようなものも含まれる。実力の向上は、作業ができるレベルで止まってしまう。 プログラマとしての実力をあげるための勉強が自
数学の難問「ABC予想」、京大教授が解明か - 日本経済新聞
現代の数学に未解明のまま残された問題のうち、「最も重要」ともいわれる整数の理論「ABC予想」を証明する論文を、望月新一京都大教授（43）が18日までにインターネット上で公開した。整数論の代表的難問であり、解決に約350年かかった「フェルマーの最終定理」も、この予想を使えば一気に証明できてしまう。欧米のメディアも「驚異的な偉業になるだろう」と伝えている。望月教授は取材に対し「論文はあくまでも専門
「フカシギの数え方」の問題を解いてみた
先日、「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。これは自己回避歩行(Self-avoiding walk)と呼ばれている問題らしい。 これだけ聞いてもそれほどインパクトはないのだが、動画に出てくるおねえさんの経路を調べあげる執念がもの凄く、ネット上でも結構な話題になっている。執念と言うよりも狂気に近い。しかし、話題になった割には動画内で言及されている高速なアルゴリズムを実装したという話を聞かなかったので、自分で確かめることにした。 動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。そこで、高速化のため
第2回 川渡り問題
アルゴリズムと聞いて、何を思い浮かべますか。「実際にプログラミングを行う上では何に役立つかよくわからない」と感じている方もおられるのではないでしょうか？ この連載では、「アルゴリズム」を、具体的な問題に対して適用していく際の考え方を紹介します。今回は「川渡り問題」について解説します。 例題3 3人の宣教師（うち2人は子供）と3人の先住民（同）が川岸にいます。川には2人まで乗れるボートが一艘（そう）あります。ボートを漕げるのは、大人だけで、子供はボートを漕ぐことが出来ません。また、どちらかの岸で、先住民の数が宣教師の数より多くなると、先住民は反旗を翻して宣教師に襲いかかってしまいます。全員が無事に対岸に渡るには、どうしたら良いでしょうか？ これは有名な川渡り問題です。これまでの解説を読んだ上でこの問題を見て、この問題をどう解いていくか想像がついたでしょうか？ この問題をグラフに変換することは
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
はてなブックマークにおけるアクセス制御 - 半環構造に基づくモデル化
http://twitter.com/chomado/status/479227070975725569
Netty 4がTwitterのGCオーバーヘッドを1/5に削減
TechCrunch
