あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
はてなのCAPTCHAは簡単に破れる
CAPTCHAをご存知でしょうか。 スパム防止のために歪んだ文字とかを入力させる、アレのことなのですが、 はてなのCAPTCHAの強度が妙に低く思えたので検証してみました。 CAPTCHAというのはいわゆる逆チューリングテストという奴で、 人間には可能だが機械には処理しにくいことをさせることで、 ロボットによる操作を弾こうというものです。 たとえば、Gmailのユーザ登録には以下のような画像が表示され、 表示されている文字を入力することが求められます。 CAPTCHAの強度 例えばスパムを送るために大量のGmailアカウントを得ようとしてる人がいたとします。 手作業でGmailを登録するのは骨が折れる。 そこでプログラムによる機械化を試みることになるわけです。 その際、障壁となるのがこのCAPTCHAなのです。 この画像から正解である文字列"vittac"を得ることは機械には難しい。 プロ
Super Technique 講座～ザ・レトロ・アルゴリズム「バイナリサーチ」徹底解説！
このページは昔話...ではない。が、筆者にしてみれば「こんなんジョーシキ！」と思っていたテクニックを使ってみせたら、意外なことにビックリされたので、「こりゃ解説する価値があるか！？」となってしまったことがあるのである。 そのテクニックは「バイナリ・サーチ」である。実は筆者がホント初心者だった遥か昔（大学生だった頃）、コレを教えて貰ってカンドーしちゃったことがあるのである。それ以降、「筆者の技」として結構愛用しているのだが、意外にコレ、使いでがあるんである。しかし...だ。最近のプログラマって言うと、ライブラリだ、クラスだ、フレームワークだ、という話には強くっても、この手の「アルゴリズムの技」には弱い...ってのが傾向である。で、しかも「バイナリ・サーチ」っていうと、基本技には違いないが、その前提となる「ソートされたデータに対して○○する」というタイプの問題が減っているということからか、レト
Super Technique 講座〜ハッシュテーブル
ハッシュテーブルは、中級の基本技である。「ハッカー」と呼ばれる程のプログラマならば、使いなれた自作ハッシュライブラリを持っていて当然である。また、これは非常に検索が速く便利なために、awk から Perl に至るスクリプト言語で、言語仕様に採り入れられてよく「連想配列」などと呼ばれている。要するに、 $List{'http'} = 80; のように、配列なのに文字列を添字として取るような書き方をするアレである。これは「キー」である文字列に対して、「値」である何かのオブジェクトを返すという動作であり、そういう動作こそが「ハッシュテーブル」以外の何者でもない。ものすごく便利なので、ぜひマスターされたい。→ Java 講座の「ハッシュテーブル」 準備～リスト版線形探査 ハッシュテーブルの原理 ライブラリの実装 他の応用 Java の Hashtable クラス 準備～リスト版線形探査 ハッシュテ
Rubyの浮動小数点数リテラルの扱いは正しいのか - hnwの日記
題名の通りなんですが、前回の記事「PHP以外全員不正解」に対して「ダウト！」を頂戴したのでまとめてみます。 Cのこの動作が、唯一無二絶対のものであるとする根拠はどこにあるのでしょうか? strtod によれば、 If the subject sequence has the decimal form and at most DECIMAL_DIG (defined in ) significant digits, the result should be correctly rounded. If the subject sequence D has the decimal form and more than DECIMAL_DIG significant digits, consider the two bounding, adjacent decimal strings L and
横着プログラミング 第9回: sary: Suffix Array のライブラリとツール
最終更新日: 2002-12-18 (公開日: 2002-12-18) Unix Magazine 誌に 2002年1月号から 2003年2月号にかけて連載し ていた記事の元の原稿です。 私にフローチャートだけを見せて、テーブルは見せないとしたら、 私はずっと煙に巻かれたままになるだろう。逆にテーブルが見せて もらえるなら、フローチャートはたいてい必要なくなる。 -- Frederick P. Brooks Jr. *1 プログラミングにおいてはデータ構造が重要であり、正しいデータ 構造を選択すればアルゴリズムは自明なものとなる、という主張が ある。Rob Pike*2 の "Notes on Programming in C" *3 によると、現実的なプログラムに必要なデータ構造は次の 4つであ るという。 配列 (array) 連結リスト (linked list) ハッシュテーブル
関西オープンソース2005発表, 非決定性計算, KOF宴会 - Journal InTime(2005-10-29)
_ 関西オープンソース2005発表 発表してきた。 スライド ちょっと会場入りが遅れたせいもあり、進行がぐだぐだになってしまって、 申し訳なかったです。 Tags: ximapd Rast _ 非決定性計算 今回いちばん面白かったのが、Haskell同好会のセッション。 吉田さんのプレゼンで非決定性計算の話が出て来たのだが、 Wikiでも紹介されていたようだ。 「他の言語じゃこんなことできないでしょ」という話だったが、 実はRubyConf2005のChad FowlerとJim Weirichのチュートリアルでも同じようなデモをやっていた。 それを使って書くと、 require "amb" A = Amb.new baker = A.choose(1, 2, 3, 4, 5) cooper = A.choose(1, 2, 3, 4, 5) fletcher = A.choose(1,
第10回 麻雀の役を判定する：ITpro
図1に示す(1)から(3)までの麻雀（マージャン）の手牌があります。「あがり牌」はすべて山からツモったものとし，リーチはかけていません。またドラやハイテイ＊1なども関係ないものとします。これらの役を判定して，親の場合の点数を計算するプログラムを作ってください。 「ややこしや～ややこしや～」というのは野村萬斎ですが，思わずそううなってしまうことがプログラミングをしているとよくあります。今回の麻雀の役判定は，考えれば考えていくほどややこしく，そうしたものの代表と言えるでしょう。排他処理や優先順位が複雑にからんでいて一筋縄ではいきません。 今回はややこしい組み合わせを解決する方法を考えてみます。麻雀になじみのない方も，ちょっとしたパズル気分で試してみてください。 麻雀の役を考える 麻雀を知らない方のためにルールをおおざっぱに説明しておきましょう＊2。麻雀の牌には，大きく分けて「萬子（マンズ）」「
第8回 倉庫番を解くアルゴリズム - 地球にやさしいアルゴリズム：ITpro
「倉庫番」＊1というゲームをご存じでしょうか。図1のように盤面にはいくつかの「荷物」とそれを運ぶ「人」がいます。人は1個の荷物を押して運ぶことができます。荷物を引っ張ったり，二つ並んだ荷物を同時に押して運ぶことはできません。人と荷物は縦横4方向に動けますが，壁のある位置には進めません。人を使って盤面上の荷物を動かし，すべての荷物を目的地（ゴール）に収めることができればゲーム・クリアとなります。図1の問題を解くための手順を示すアルゴリズムを作ってください。 友人たちと車でスキーに行くとき，いつも困るのは「トランクへ荷物を詰め込む順番」です。大きなスキー靴やかさばるスキーウエアを詰め込んでいるうえ，人によってはゲーム機や本を持ってきたりするので，各自の荷物の量がまったく違うのです。狭い車のトランクには，これら荷物をうまい順番で入れていかないとなかなか全部収まりません。寒い冬の夜中にごそごそと詰
404 Blog Not Found:javascript - Array#sortがオレquicksortより遅い!?
2006年11月23日14:45 カテゴリLightweight Languages javascript - Array#sortがオレquicksortより遅い!? な、なんだってー!? ごっつええブログ - JavaScriptによるソートアルゴリズムの比較実験 『JavaScriptを使って一定以上の数量をもった数値配列をソートする場合は、組み込みメソッドよりもクイックソートを使用したほうが高速である』 自分でも検証してみた。 どうやらMozilla系列のJavaScript実装に関しては嘘ではないらしい。以下で確認してほしい。 Firefox 2に関してはほぼ同等だが、Mac IE 5, Safari 2.0.4, Opera 9.02ではbuiltinの方が速かった。しかしその差は最も大きかったSafariでも3倍程度で、builtinとしてはやはり遅いように見える。 # of
初代Googleのアルゴリズム解説 - GIGAZINE
いまやネットの世界を左右する強力な検索エンジンとなったGoogle。日本ではまだYahoo！の方がはるかに利用者が多いのでさほどではないですが、アルゴリズムの基本的な考えが似ているため、同じような結果が出てきます。つまり、既存の検索エンジンのその基礎となった一番最初のGoogleの検索アルゴリズムを理解すれば、検索エンジン対策にも役立つはず。 ということで、初代Googleのアルゴリズムをできるだけわかりやすく解説してみます。既存の他サイトの解説とは違い、きちんとした最初のGoogleの数式に基づいています。 詳細は以下から。The Anatomy of a Search Engine http://www-db.stanford.edu/~backrub/google.html Googleの画期的なランク付けの方法が数式による全自動のページランクというのは聞いたことがあると思いますが、
定番アルゴリズムを徹底理解！ - 今からでも遅くない！アルゴリズム入門：selfup
このパートでは，プログラミングを勉強するうえで欠かせないアルゴリズムの中でも定番中の定番を紹介します。ソート（並べ替え）やサーチ（検索）などの機能は今では標準のライブラリとして提供されています。実用的なプログラムを作るときにそのものずばりをいちいち書く機会は少ないかもしれません。しかし定番のアルゴリズムは，様々に形を変えて普段のプログラミングに登場します。 解説を読んで仕組みがわかったら，ぜひそれをプログラムにしてみてください。読んだだけではプログラムを書けるようにはなりませんし，プログラムを書いてみて初めて，実は十分に理解できていなかったと気付くことがよくあります。しかもアルゴリズムは特定のプログラミング言語に依存しないので，一度身に付ければ，後でどんな言語を学ぶ場合でも役に立ちます。 1番目から6番目まではソートのアルゴリズム，7番目から9番目まではサーチのアルゴリズムです。一つひとつ
遅延評価 - Wikipedia
評価しなければならない値が存在するとき、実際の計算を値が必要になるまで行わないことをいう。評価法が指示されているが実際の計算が行われていない中間状態の時それをプロミス（英: promise）や、計算の実体をさしてサンク（英: thunk）といい、プロミスを強制（英: force）することで値が計算される。一旦計算された値はキャッシュをすることが可能であり、遅延プロミスは最大で一度しか計算されないようにすることができる。ただし、Haskell の実装によっては、何度でも同じ計算を行う。 遅延評価を行う利点は計算量の最適化である。 ある関数を呼び出すとき、その関数が引数の全てを利用するとは限らない。条件次第で捨ててしまうような値を事前に準備することは非効率的である。このような場合遅延評価を行うと必要なときだけ値が計算されるので計算量を低減できる。 また同じ評価を複数回利用する可能性があるとき、
- サルでもわかる待ち行列
(株)永和システムマネジメント 平鍋健児 作成日：初版 1999, 3/16 第2版 2002, 11/6 第3版 2004, 9/14 第4版 2008, 5/1 情報処理技術社試験の中で良く出て来る「待ち行列」理論を，直感的に覚えやすく解説してみました． 何度もトライしたけど待ち行列が理解できない人向けです． 正確な定義や論理展開は重視せず，いかに効率的にこの理論を覚えることができるかに焦点を絞ってみました．
Reverse Polish notation - Wikipedia
"Operational stack" redirects here. For the English Channel lorry parking procedure, see Operation Stack. Video: Keys pressed for calculating eight times six on a HP-32SII (employing RPN) from 1991 Reverse Polish notation (RPN), also known as reverse Łukasiewicz notation, Polish postfix notation or simply postfix notation, is a mathematical notation in which operators follow their operands, in con
逆ポーランド記法 - Wikipedia
HP-32SIIの8×6の計算で押すキー 逆ポーランド記法（ぎゃくポーランドきほう、英語: Reverse Polish Notation, RPN）は、数式やプログラムの記法の一種。演算子を被演算子の後にすることから、後置記法 (Postfix Notation) とも言う。 その他の記法として、演算子を被演算子の中間に記述する中置記法、前に記述する前置記法（ポーランド記法）がある。 名称の由来は、演算子と被演算子の順序がポーランド記法の逆になっていることによる。 例えば、「3 と 4 を加算する」という演算を、一般的に数式の表記に用いられる中置記法で記述すると、以下のようになる。 3 + 4 一方、逆ポーランド記法では、加算を表す演算子 + を、被演算子である 3 と 4 の後（右）に置いて、以下のよう記述する。 3 4 + 逆ポーランド記法による表現は日本語などSOV型の言語の語順と
Javaによるアルゴリズム辞典
奥村晴彦， 首藤一幸， 杉浦方紀， 土村展之， 津留和生， 細田隆之， 松井吉光， 光成滋生 『Javaによるアルゴリズム事典』 （技術評論社，2003年，ISBN4-7741-1729-3，2580円＋税） のサポートページです。 技術評論社の Javaによるアルゴリズム事典 のページ ソースコードのダウンロード 00README.txt java-algo.zip (約320K，Shift JIS / CRLF) java-algo.tar.bz2 (約130K，EUC-JP / LF) 更新記録 [2003-05-09] 公開 [2003-05-12] BDCbrt.java, BDSqrt.java, BDtoE_Form.java, BinarySplitE.java, BinarySplitPi1.java, BinarySplitPi2.java のコメントを修正しました [
algorithm
奥村晴彦さんの「C言語による最新アルゴリズム事典」技術評論社、1991年、の C 言語プログラムの Ruby への翻訳に挑戦します。プログラムの説明は同書を読んでください。変換はできるだけ逐語的に行っています。プログラムの動作は原作の C プログラムのそれと比較してチェックしていますが、うまく動作しないときは C から Ruby への変換のさいに起きたものです。バグレポートは tnomura@mnet.ne.jp までお願いします。 この Ruby 翻訳版はできるだけレイアウトも含めて原作の C プログラムを変更しないようにしたため、必ずしもRuby らしいコーディングスタイルとは言えないかもしれませんが、プログラムがきちんと動作することを優先しました。C から Ruby への翻訳の著作権に関しては Ruby のライセンスに準じます。配布、改変は自由です。ただし、プログラム本体には原作者の
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://web.sfc.keio.ac.jp/~arith/al06/
C言語による最新アルゴリズム事典の詳細情報 : Vector ソフトを探す！