へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。 K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。 クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、Restart を押すと好きなパラメータで試すことができます。 こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。 (追記) HTML5 版の K-means 法を D3.js でビジュアライズしてみた も作成しました。Flash を表示できない環境ではそちらをご覧ください。 K-means 法とは K平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージに
世界で闘うプログラミング力を鍛える150問 〜トップIT企業のプログラマになるための本〜 - iwiwiの日記
先行発売のお知らせ (11/7 追記) 以下の店舗で先行発売が行われているらしいです． 紀伊國屋書店 新宿本店 (https://twitter.com/KinoShinjuku/status/265658160222724096) 紀伊國屋書店 新宿南店 (https://twitter.com/kino_Minami/status/265405470548844546) ジュンク堂書店 池袋本店 (https://twitter.com/junkudo_ike_pc/status/265677297430978562) 有隣堂 ヨドバシAKIBA店 (https://twitter.com/yurindo_akb/status/265648944745426945) 丸善 丸ノ内店 なお，電子書籍版の発売も予定しているそうですが，調整中とのことで少し後になりそうです． 原著は既に第5版
「フカシギの数え方」の問題を解いてみた
先日、「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。これは自己回避歩行(Self-avoiding walk)と呼ばれている問題らしい。 これだけ聞いてもそれほどインパクトはないのだが、動画に出てくるおねえさんの経路を調べあげる執念がもの凄く、ネット上でも結構な話題になっている。執念と言うよりも狂気に近い。しかし、話題になった割には動画内で言及されている高速なアルゴリズムを実装したという話を聞かなかったので、自分で確かめることにした。 動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。そこで、高速化のため
第2回 川渡り問題
アルゴリズムと聞いて、何を思い浮かべますか。「実際にプログラミングを行う上では何に役立つかよくわからない」と感じている方もおられるのではないでしょうか？ この連載では、「アルゴリズム」を、具体的な問題に対して適用していく際の考え方を紹介します。今回は「川渡り問題」について解説します。 例題3 3人の宣教師（うち2人は子供）と3人の先住民（同）が川岸にいます。川には2人まで乗れるボートが一艘（そう）あります。ボートを漕げるのは、大人だけで、子供はボートを漕ぐことが出来ません。また、どちらかの岸で、先住民の数が宣教師の数より多くなると、先住民は反旗を翻して宣教師に襲いかかってしまいます。全員が無事に対岸に渡るには、どうしたら良いでしょうか？ これは有名な川渡り問題です。これまでの解説を読んだ上でこの問題を見て、この問題をどう解いていくか想像がついたでしょうか？ この問題をグラフに変換することは
高層ビルのエレベーターホールには、なぜ階数表示がないのか - 本当は怖いHPC & AI
以前に高橋幸雄先生の授業で聞いて非常に面白いと思ったこと。 オフィスビルとかホテルとか、エレベーターが何基も設置されているビルの場合、エレベーターホールに階数表示が無いことが多い。エレベーターホールで画像検索してみればわかると思う。 これはなぜだろうか。 その理由は、「客がいても、その階を通過することができるようにするため」だ。 基本的に、多数のエレベーターを効率よく動かすのは難しい。工夫された高度なアルゴリズムが使われていることが多い。目標は「客の平均待ち時間を短くする」ことだ。ある階でボタンが押された場合、どのエレベーターがその客を迎えに行くか、という判断が平均待ち時間に大きな影響を与える。難しいアルゴリズムの中で、この点がもっとも重要なところだ。 高層ビルの場合、エレベーターはかなりの速度で走っている。既に客を乗せて走っているエレベーターが他の客を乗せるために停止すると、減速→停止→
Rare Are GC Talks
This article is meant to be an easy to understand explanation of GC algorithms to those who think to themselves "I get that garbage collection is useful, but I don’t really understand how it all works". An explanation of how the CRuby*1 GC works will follow. Finally we’ll look a little at recent studies on Ruby GC alternatives. Oh, just to set the record straight, the GC described in this article
『世界でもっとも強力な9のアルゴリズム』で頭を鍛える - HONZ
著者の定義によると、アルゴリズムとは「問題を解決するために必要な手順を正確に規定したレシピ」である。コンピュータ・サイエンスを専門とする大学教授の手による本書は、現在当たり前のように使われている偉大なコンピュータ・アルゴリズムがなぜ必要とされたのか、どのように考え出されたか、そして、それが実際にどのような仕組みで動いているのかを教えてくれる。 このように紹介すると、コンピュータやプログラミングが苦手な人は手が遠のいてしまうかもしれないが、どうかご安心を。本書を楽しむのに、コンピュータプログラミングやコンピュータ科学の知識は必要ない。必要なのはじっくりと考えることだけだ。 一口にサイエンス本といっても面白いポイントはそれぞれに異なるが、本書の面白みは間違いなく、過去の偉人たちの難問への挑戦を疑似体験できるところにある。その面白みを満喫するためにも、頭から煙を出しながらじっくりと考えながら読む
文字列データ圧縮ことはじめ | SlideShare
2012/6/21のPFI全体セミナー, 「文字列データ圧縮ことはじめ」の内容です。データ圧縮の話とそれに纏わる歴史と最近の話を紹介しています。
アルゴリズムを学ぼう
関連サイト出版社による関連ページが公開されています。 アルゴリズムを学ぼう (KADOKAWA/アスキー・メディアワークス) 関連書籍本書の続編『続・アルゴリズムを学ぼう』も好評発売中です。 内容紹介本書のテーマは、ガチのアルゴリズムとデータ構造、そして計算量です。 いや、確かに本書は女の子がいろいろでてきたり、小話が入っていたりと、ゆるふわなオーラが漂っています。しかし、あえていいましょう。それは、見かけだけである、と。 プログラミングを学ぶにあたって、アルゴリズムとデータ構造は、どの言語を用いるにしてもすべての基礎であり、避けて通ることはできない道です。アルゴリズムとデータ構造を知らずにプログラムを書くことは、無免許で車を運転するぐらいに危険な行為です。 しかし、アルゴリズムとデータ構造をきちんと理解せずに、プログラムを書いているプログラマーが多数いるのも事実です。それは、アルゴリズム
サービス終了のお知らせ - NAVER まとめ
サービス終了のお知らせ NAVERまとめは2020年9月30日をもちましてサービス終了いたしました。 約11年間、NAVERまとめをご利用・ご愛顧いただき誠にありがとうございました。
指数時間アルゴリズム入門
2. 自己紹介 TopCoder: ◎wata TCO2010Marathon優勝など Twitter: @wata_orz 東京大学情報理工学系研究科コンピュータ科学専攻 理論計算機科学 (アルゴリズムの理論的な解析とか) プログラミングコンテスト チャレンジブック 2 3. 本日の内容 NP困難問題を解くためのアルゴリズムを扱います 𝑂𝑃𝑇 𝐼 ≤ 𝐴 𝐼 ≤ 𝑐𝑂𝑃𝑇(𝐼) 近似アルゴリズム ヒューリスティック 𝑓 𝑘 𝑝 𝑛 FPT アルゴリズム max 𝑐𝑥|𝐴𝑥 ≤ 𝑏, 𝑥: 整数} { 𝑂∗ 𝑐 𝑛 整数計画 厳密指数時間アルゴリズム 3 4. 効率的な指数時間アルゴリズム 何の指数？ 頂点数? 辺の数? それとも… • 2 𝐸 のアルゴリズムはまず役に立たないが，2 𝑉 のアル ゴリズムならコンテストでもよ
形式言語理論 for Algorithmers
競技プログラマ向け 形式言語理論 入門 稲葉 一浩 JOI 春合宿 2012 文字列やツリーやグラフの 集合 について考える分野 「形式言語理論」とは 文字列やツリーやグラフの 集合 を、どうやって表現するか について考える分野 「形式言語理論」とは 文字列やツリーやグラフの 集合 を、どうやって表現するか について考える分野 「形式言語理論」とは 今日は 文字列の集合だけ 扱います 文字列やツリーやグラフの 集合 を、表現するデータ構造 について考える分野 「形式言語理論」とは #include <set> #include <string> std::set<std::string> ？ 文字列やツリーやグラフの 無限かもしれない集合 の、有限のメモリでの表現 について考える分野 「形式言語理論」とは {“”, “a”, “aa”, “aaa”, “aaaa”, ...} 「長さが
Tumblr
「JPEG Tilt」というページを公開しました。MotionJPEG Builder を作った時に、JPEG のヘッダを読み込む処理を作ったので（結局これは使わなかったんですが）圧縮データの読み込み部分も作ってみようか、という気になって作ったのがこれです。JPEG ファイルで画像が圧縮される様子を視覚的に表現する…… という目標だったのですが、どうでしょうか。まあ内容が内容なので説明無しではさすがに意味が分からないと思います。 ということで、JPEG Tilt の見方を以下で簡単に説明します。 図1は、JPEG Tilt の画面です。画像が iTunes の CoverFlow のように並んでいますが、これの左側は画像の低周波成分のみを抜き出した物で、右に行くとより高周波の成分も含めるように並んでいます（低周波、高周波という言葉の意味はこの先で出てきます） 画像の上にマウスカーソルを乗せ
Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found
2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構
データマイニングで使われるトップ10アルゴリズム | gihyo.jp
統計を専門に扱う方のブログ記事です。データマイニングの学会にて選ばれたアルゴリズムの概要および調査について記した資料「Top 10 algorithms in data mining」の解説を行っています。Top 10に選ばれたアルゴリズムには次のようなものがあります。 C4.5 K-means サポートベクタマシン（SVM） PageRank ナイーブベイズ CART C4.5は、あるルールに従って木構造に分岐させ分類していく決定木（Decision Tree）を生成するためのアルゴリズムです。 K-meansはK個のクラスタに分類するためのアルゴリズムで、最も近い中心のクラスタを繰り返し求めていき、視覚化するのに適しています。 サポートベクタマシンは、あらかじめ与えられたデータで学習を行い未知のデータに対して分類を行う「教師あり学習」アルゴリズムの一つです。 PageRankはGoog
新ソートアルゴリズム「配列挿入ソート」だ! - hp12c
(追記:2012-1-10) id:m11m さんのコメントによりこのソートはバケットソート*1と呼ばれる既知のソートアルゴリズムであることがわかりました ^^; 追記によりお詫び申し上げます (追記:2012-1-12) 記事に対するアクセスが異常なので調べてみると、dankogai氏のネタにされていたという名誉を受けていたことが判明しました^^; 光栄です 404 Blog Not Found:algorithm - bucket sort - 比較しなければソートは相当速い - 以前にスリープソートという ソートアルゴリズムが発見されたよね 常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream で僕はこれに対抗してランニングソート っていうアルゴリズムを見つけたんだよ まあ失敗したんだけど.. sleep sort
データマイニングで使われるトップ10アルゴリズム - データサイエンティスト上がりのDX参謀・起業家
2006年のデータマイニング学会、IEEE ICDMで選ばれた「データマイニングで使われるトップ10アルゴリズム」に沿って機械学習の手法を紹介します（この論文は@doryokujin君のポストで知りました、ありがとうございます！）。 必ずしも論文の内容には沿っておらず個人的な私見も入っていますので、詳細は原論文をご確認下さい。また、データマイニングの全体観をサーベイしたスライド資料がありますので、こちらも併せてご覧下さい。 データマイニングの基礎 View more presentations from Issei Kurahashi 1. C4.5 C4.5はCLSやID3といったアルゴリズムを改良してできたもので、決定木を使って分類器を作ります。決定木といえばCARTが良く使われますが、CARTとの違いは以下のとおりです。 CARTは2分岐しかできないがC4.5は3分岐以上もできる C
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
XXmallocのメモリ管理アルゴリズムについてわかりやすい記事 - Qiita
個人投資家必見、アルゴリズム取引の凄さが何となく分かる動画「アルゴリズムが形作る世界」 : 市況かぶ全力２階建
