頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
ビットを数える・探すアルゴリズム
作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。 はじめに PowerPC 系や Alpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。 集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。 職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。 CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。 例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを
ブルームフィルタ - Wikipedia
この項目では、確率的データ構造について説明しています。画像にぼかし効果を付加する画像フィルタについては「川瀬のブルームフィルター」をご覧ください。 ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の
Bloom Filter « Python recipes « ActiveState Code
ActiveState Code (http://code.activestate.com/recipes/577684/) Space efficient, probabilistic set membership tester. Has no False Negatives but allows a rare False Positive. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 7
Bloom filter - Wikipedia
In computing, a Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this c
常識を覆すソートアルゴリズム！その名も"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 なん…だと
妨害に負けず、個々が判断できる群ロボット(動画) | WIRED VISION
前の記事 浮遊する感覚：ロールスロイスの電気自動車、試乗レビュー 誰もが書籍アプリを作れる『Push Pop Press』 次の記事 妨害に負けず、個々が判断できる群ロボット(動画) 2011年5月10日 IT コメント： トラックバック (0) フィードIT Olivia Solon 一緒に行動する他のロボットと相互交信しなくても、個々の判断で様々な隊形を作ることができる群ロボット・システムを、ジョージア工科大学のTed MacDonald氏が作成した。ロボットたちに、自分たちの位置についてのあらかじめ定義されたメモリや事前知識は入っていない。 上の動画では、15台の『Khepera』ロボットが、同じ情報に基づいてそれぞれ個別に決定を下し、試行錯誤しながら動き回って、自分たちに命じられた隊形を作り上げている。[Khepera(ケペラ)は、スイス連邦工科大学のマイクロ・エレクトロニクス研究
人間の性別は 625 ピクセルで十分に判別可能なのか ? | スラド
スペインはマドリード工科大学の Computational Intelligence Group が、リアルタイムで 25 × 25 ピクセルの顔画像から性別を判定できるシステムを作った (I Programmer の記事、本家 /. 記事より) 。 このシステムで用いられているアルゴリズムは古典的なパターン認識の手法だが、昨今トレンドのサポートベクターマシンを用いた手法よりも良い結果を導出できたという。高速な処理が可能ということで、例えば観客をざっと撮影して男女比を割り出してマーケッティングへ応用させることも考えられる。 つまるところ 625 ピクセルもあれば人間の性別は十分な精度で判定可能ということか。
対象を学習・追跡し続けるカメラ『Predator』(動画) | WIRED VISION
前の記事 旅先でもiPadが使えるレンタルサービス 対象を学習・追跡し続けるカメラ『Predator』(動画) 2011年4月 6日 IT コメント： トラックバック (0) フィードIT Charlie Sorrel Zdenek Kalal氏によるオブジェクト追跡ソフトウェア『Predator』は、気味が悪いくらいすごい性能だ。「すべてを見通すカメラの目」に物体を見せると、それがなんであっても素早く学習して認識し、対象が離れて小さくなっても、似た対象のなかに隠されても、これを追跡する。対象が顔の場合、横を向いても追跡は続く。 まさに、Predator[プレデター]というその名前の通りだ。映画『プレデター』でヘッド・アップ・ディスプレー(HUD)越しにプレデターが見る、拡張された視界が思い浮かぶ。 Kalal氏は英国サリー大学の博士課程に在籍する学生で、ものを見るコンピューターのプロジェ
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
FrontPage - アルゴリズムとデータ構造入門 - Kyoto Univ.
アルゴリズムとデータ構造入門 TAのページ 京都大学 工学部 情報学科 1回生配当の授業 アルゴリズムとデータ構造入門（奥乃先生担当)のTAが管理するページです。 連絡 (2007/10/01) 2007年度用に更新。 (2006/10/31) Meadowの使い方を公開しました。 (2006/11/14) 改行コードで困っていた方が多かったので改行コードに関する設定についてまとめました。 (2006/10/27) 質問掲示板を移行 使い勝手が悪く、あまり評判もよくないので質問掲示板を移行しました。これからは新しい方に質問を書いてください。 (2006/10/13) cygwinとTUTSchemeのインストールの説明に間違いがあったので追加・修正しました。 このページの通りにインストールを行って、Can't find a usable init.tcl in the following
良い乱数・悪い乱数
Ｃ言語標準ライブラリの乱数rand( )は質に問題があり、禁止している学会もある。 他にも乱数には様々なアルゴリズムがあるが、多くのものが問題を持っている。 最も多くの人に使われている乱数であろう Visual Basic の Rnd の質は最低である。 そもそも乱数とは 乱数とは、本来サイコロを振って出る目から得られるような数を意味する。 このような乱数は予測不能なものである。 しかし、計算機を使って乱数を発生させた場合、 次に出る数は完全に決まっているので、予測不能とはいえない。 そこで、計算機で作り出される乱数を疑似乱数(PRNG)と呼び区別することがある。 ここでは、特にことわらない限り乱数とは疑似乱数のことを指すとする。 計算機でソフト的に乱数を発生させることの最大のメリットは、 再現性があることである。 初期状態が同じであれば、発生する乱数も全く同じものが得られる。 このことは
Token bucket - Wikipedia
The token bucket is an algorithm used in packet-switched and telecommunications networks. It can be used to check that data transmissions, in the form of packets, conform to defined limits on bandwidth and burstiness (a measure of the unevenness or variations in the traffic flow). It can also be used as a scheduling algorithm to determine the timing of transmissions that will comply with the limit
第3回 予測インターフェース | gihyo.jp
はじめに 「よろしく」と入力すると「お願い」が候補に出るような「予測入力方式」が、携帯電話などで最近広く使われています。ユーザの次の行動を予測するようなシステムは「予測インタフェース」と呼ばれており、昔からさまざまなシステムが研究されてきています。 ユーザの行動を予測する方法はいろいろなものが考えられます。上の例の場合は「よろしくお願い申しあげます」という表現が世の中でよく利用されているという統計情報を利用して予測を行ったものですが、ユーザの行動履歴や現在のコンテキストなどの情報を利用することもできます。筆者の場合は「増井」という名前を入力する機会が多いため「ま」と入力すると「増井」が予測されます。時刻や位置情報のようなコンテキストを利用できる場合、渋谷で駅名検索するときは「し」から「渋谷」を予測し、新宿で検索するときは「し」から「新宿」を予測するといったこともできるでしょう。「123」
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Ant Colony Systemに基づいた顧客輸送サービスのための車両巡回パターンの動的構築法 | CiNii Research
https://jp.techcrunch.com/2011/08/26/20110825tweaking-the-algorithm-google-gives-a-small-peek-behind-the-curtains/
乱択アルゴリズム紹介(行列乗算の検査&多項式等価性の検査) - Preferred Networks Research & Development
SPYSEE新検索機能の裏側
新訳データ構造とネットワークアルゴリズム