コンピュータを進化させてきた偉大なるアルゴリズムまとめ
By Kai Schreiber IT技術の進化のスピードには目を見張るものがありますが、それを支えているのはアルゴリズムと呼ばれる処理方法(技術的アイデア)です。さまざまなアルゴリズムの中でも、コンピュータの進化に革命的な影響をもたらしたとされる偉大なアルゴリズムは以下の通りです。 Great Algorithms that Revolutionized Computing http://en.docsity.com/news/interesting-facts/great-algorithms-revolutionized-computing/ ◆ハフマン符号(圧縮アルゴリズム) Huffman coding(ハフマン符号)は、1951年にデービッド・ハフマン氏によって開発されたアルゴリズム。頻出頻度の大小によって対戦するトーナメントツリーを考えて、ブロックごとに0と1の符号をもたせる
第2回将棋電王戦を山崎バニラさんが熱く語る（第2局観戦記） - 週刊アスキー
将棋電王戦第2局・佐藤四段vs.ponanzaの対局は、141手でponanzaの勝利に終わった。これで人間対コンピューターの戦いは1勝1敗の五分になった。対局の速報はこちらをご覧ください。 さて、今回対局を将棋会館で見ていた山崎バニラさんによる観戦記を、まずお届けします。 まず、昨年12月に行なわれた第２回電王戦開催記者発表の質疑応答で私は質問しました。詳しい内容はその時の記事をご参照ください。 第１局を制したプロ棋士・阿部光瑠四段と違い、第２局の佐藤慎一四段には対戦するコンピュータは貸し出されていませんでした。事前にコンピュータの個性を研究できるかどうかは勝敗に大きく関わるはずです。この点、第３回電王戦が開催されるのであれば、ある程度規則を設けるのか、このまま開発者の意思に任せるのか、運営の判断を待ちたいと思います。 事前に貸し出すか否かは開発者が“研究”を重視するか“勝敗”を優先する
Genetic Programming: Evolution of Mona Lisa
Added FAQ here: http://rogeralsing.com/2008/12/09/genetic-programming-mona-lisa-faq/ Added Gallery here: http://rogeralsing.com/2008/12/11/genetic-gallery/ This weekend I decided to play around a bit with genetic programming and put evolution to the test, the test of fine art :-) I created a small program that keeps a string of DNA for polygon rendering. The procedure of the program is quite simpl
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
Boids (Flocks, Herds, and Schools: a Distributed Behavioral Model)
A slightly more elaborate behavioral model was used in the early experiments. It included predictive obstacle avoidance and goal seeking. Obstacle avoidance allowed the boids to fly through simulated environments while dodging static objects. For applications in computer animation, a low priority goal seeking behavior caused the flock to follow a scripted path. In cooperation with many coworkers a
マンデルブロ集合の不思議な世界
最新情報 2020/01/20、HTTPSに対応し、URLが「http://～」から「https://～」に変更となりました。 2017/06/04、サイトリニューアルしました。今後ともどうぞよろしくお願いいたします。 マンデルブロ集合という図形をご存知ですか？見るからに変な形、どんなに拡大しても次々に最初と同じ形が現れる不思議、緻密で深く吸い込まれそうなその模様。マンデルブロ集合は、数学とコンピュータによって描かれるフラクタル図形の一種です。 こんな摩訶不思議な図形が一体どうやって描かれるのか、さぞ難しい数学やアルゴリズムの話が出てくるのかと思いきや、高校数学の複素数と数列くらいまでを知っている人であればすぐに理解できてしまう、非常に簡単な仕組みで成り立っているのです。もちろん、数学は全然分からないという人でも、単純にアートとして楽しむことができます。 マンデルブロ集合の周囲には、全く同
第3回 オブジェクト検出してみよう | gihyo.jp
第1回、第2回と画像認識の基礎とOpenCVについて紹介してきました。第3回目の今回は、いよいよ本連載の目玉であるOpenCVを使ったオブジェクト検出に挑戦してみます。 オブジェクト検出の仕組み 基本原理のおさらい オブジェクト検出のプログラムを書き始める前に、そもそもどんな仕組みでオブジェクト検出を行っているのかを理解しましょう。 第1回では画像認識の原理として、学習フェーズと認識フェーズがあることを説明しましたが、OpenCVに実装されているオブジェクト検出プログラムもこの流れに従います。つまり、画像から特徴量を抽出し、学習アルゴリズムによってオブジェクトを学習します（詳しくは第1回を参照してください）。 図1 画像認識の流れ OpenCVに実装されているオブジェクト検出プログラムは、Paul Violaらのオブジェクト検出の研究［1］をベースに、Rainer Lienhartらが
Boidsとは
Boid（ボイド）とは、1987年にCraig Raynoldsによって発表された理論です。 この理論は、３つのルールを規定するだけで鳥の群れをシミュレーションできるというものです。 ちなみにBoidという名の由来は、鳥もどきという意味の言葉birdoid（バードイド）が短くなりこのように呼ばれるようになりました。 さて、Boidsの３つのルールとは、以下の通りです。 Separationは、近くの鳥や物体に近づきすぎたらぶつからないように離れるルールです。 もし、ボイド同士が近づきすぎてしまったら、前を飛んでいるボイドはスピードを速くし、 後ろを飛んでいるボイドはスピードを遅くするようにします。 障害物、例えば柱とか壁とかに対しては、それにぶつからないように方向転換して衝突を避けるようにします。 Alingmentは、近くの鳥たちと飛ぶスピードや方向を合わせようとするルールです。 すなわ
アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 : 404 Blog Not Found
2009年01月31日01:00 カテゴリLightweight LanguagesMath アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 これなのですが.... 同じ文字列のn回繰り返しを作る最速の方法を探求してみた - muddy brown thang ちょっとした事情により、ある文字列のn回繰り返しを作る関数 (PHPでいうところのarray_repeat(), Perlで言うところの「"..." x n」、RubyやPythonで言うところの「"..." * n」) を高速に実装しなければならない状況に遭遇したのでベンチマークをとってみたところ、その結果がとても新鮮で驚いたので、これを共有しつつもダメ出ししてもらえないかなーと思って晒してみることに。 なぜかもっとシンプルな奴がなかったので。 以下、比較。初期値はIEにあわせてあります。Firefox/Saf
エラトステネスの篩 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "エラトステネスの篩" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2019年6月） エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がついている。 アルゴリズム[編集] 2 から 120 までの数に含まれる素数を探すGIFアニメーション 指定された整数x以下の全ての素数を発見するアルゴリズム。このアニメーションでは以下のステップにそって 2 から
SAT ソルバで数独を解く方法 - まめめも
数独は非常に SAT に変換しやすい問題です。全部参考文献 *1 に載っている内容ですが、なるべくわかりやすく説明してみます。ちょっと長いです。 SAT とは まず SAT をごく簡単に説明します。すでに SAT を知っている人はここは読み飛ばしてください。 命題論理式の形の一つに乗法標準形のというのがあります。変数か変数の否定 (リテラルと言います) を or だけでつないだ式 (節と言います) を and だけでつないだ論理式のことを言います。つまり以下みたいな形です。 ( a1 or !a2 or ... or an) and ( b1 or !b2 or ... or !bn) and ... and (!z1 or z2 or ... or !zn)SAT は「a1 や zn などの変数にうまく true か false を代入して、上の式全体を true にできるか」という問題
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
第10回 麻雀の役を判定する：ITpro
図1に示す(1)から(3)までの麻雀（マージャン）の手牌があります。「あがり牌」はすべて山からツモったものとし，リーチはかけていません。またドラやハイテイ＊1なども関係ないものとします。これらの役を判定して，親の場合の点数を計算するプログラムを作ってください。 「ややこしや～ややこしや～」というのは野村萬斎ですが，思わずそううなってしまうことがプログラミングをしているとよくあります。今回の麻雀の役判定は，考えれば考えていくほどややこしく，そうしたものの代表と言えるでしょう。排他処理や優先順位が複雑にからんでいて一筋縄ではいきません。 今回はややこしい組み合わせを解決する方法を考えてみます。麻雀になじみのない方も，ちょっとしたパズル気分で試してみてください。 麻雀の役を考える 麻雀を知らない方のためにルールをおおざっぱに説明しておきましょう＊2。麻雀の牌には，大きく分けて「萬子（マンズ）」「
第8回 倉庫番を解くアルゴリズム - 地球にやさしいアルゴリズム：ITpro
「倉庫番」＊1というゲームをご存じでしょうか。図1のように盤面にはいくつかの「荷物」とそれを運ぶ「人」がいます。人は1個の荷物を押して運ぶことができます。荷物を引っ張ったり，二つ並んだ荷物を同時に押して運ぶことはできません。人と荷物は縦横4方向に動けますが，壁のある位置には進めません。人を使って盤面上の荷物を動かし，すべての荷物を目的地（ゴール）に収めることができればゲーム・クリアとなります。図1の問題を解くための手順を示すアルゴリズムを作ってください。 友人たちと車でスキーに行くとき，いつも困るのは「トランクへ荷物を詰め込む順番」です。大きなスキー靴やかさばるスキーウエアを詰め込んでいるうえ，人によってはゲーム機や本を持ってきたりするので，各自の荷物の量がまったく違うのです。狭い車のトランクには，これら荷物をうまい順番で入れていかないとなかなか全部収まりません。寒い冬の夜中にごそごそと詰
Part6 C の難関を克服せよ - C/C は永久に不滅です！：ITpro
どんなプログラミング言語でも，学習を進めていくとどこかに乗り越えないといけない壁が存在するものです。C++ではそれがクラスであることが多いようです。特にC++の場合は，ずぶの初心者ではなく，C言語を一通り使いこなした後でC++に移行してくる人が多いというほかのオブジェクト指向プログラミング言語には無い特徴があります。なまじC言語の知識があるため，オブジェクト指向と手続き型の考え方の違いから，クラスで行き詰まってしまうわけです。 では，どうしてクラスは壁となるのでしょうか。その理由は大きく2点あると思います。一つ目は，C++が登場するまで一般のプログラマにほとんどなじみが無かったオブジェクトという概念を理解しなければならないことです。私が知っている限り，C++が登場したころ，C言語からC++への移行がスムーズにできなかったエンジニアが大勢いました。そうした人の大半は，新しく入ってきたオブジェ
プログラムを2倍から4倍早くする方法 - GIGAZINE
プログラミングの話なので、ソフトウェアを使うだけのユーザーには関係ない話です。 要するに実行速度の遅いプログラムを2倍から4倍高速化させるには非常に基本的なトリックというか技術を使えば可能ですよ、というお話。 アルゴリズムの考え方なので、仕事上どうしてもプログラムの実行速度を上昇させる必要があるが、やり方がイマイチよく分からないという人は必見。 Dr. Dobb's | An Algorithm for Compressing Space and Time | 3 1, 2006 かの有名な「ライフゲーム」を例に出し、プログラミングのコードの内容を高速化するにはどういうアプローチを取ればいいのか、その際に使用する再帰的アルゴリズムの考え方、複雑な式を簡単な式に圧縮する方法、圧縮することで実行時間の節約が可能になること、などをやたら詳細に解説しています。 ぶっちゃけ、これが理解できるのであれ
人物の“顔”を自動認識する顔写真トリミングソフト最新版
自動トリミングの流れ 元画像（左）を認識させることで顔位置の検出（中央）と縮小／拡大、画像補正を行い、一定サイズの画像（右）を出力する NECソフトは6月19日、顔認証技術を応用した顔写真トリミングソフト「FacedePhotoEditor」の最新版となるV2.0を発表、7月初旬より発売する。製品価格は作成可能な顔画像の数量により変化、1000人分トリミングで9万5000円、1万人分トリミングで28万円となっている。 FacedePhotoEditor V2.0は、NEC製の顔検出／照合エンジン「NeoFace」を応用した人物写真用トリミングソフト。顔写真付きの社員証や学生証、運転免許証などの作成を前提とした製品で、写真に写った人物の顔部分を自動検出し、顔の位置とサイズを揃えて画像出力を行なうことができる。 今回の新バージョンでは、新たに画像補正機能を搭載。明るさ／コントラスト／シャープ
WhiteForest/白ノ森
画像を拡大縮小するときに使われる補間法はいくつかあります. その中でPhotoshop等で使われている三手法について解説いたします. 補間法として最も単純な方法です. 求めたい位置に最も近い値をそのまま使う手法です. 求めたい座標を(x,y)とすると,その位置の画素値Iは次式で表されます. I(x,y) = f([x + 0.5], [y + 0.5]) Fig - 01 ニアレストネイバーは数式からも分かる通り非常に簡単です. そのため非常に高速に処理をすることができます. しかし,拡大縮小結果では荒くなりジャギーが発生しやすいです. バイリニア補間法では求めたい座標(x,y)の画素値I(x,y)を,周りの4点を使い 次式で表されます. I(x,y) = ([x] + 1 - x)([y] + 1 - y)f([x],[y]) + ([x] + 1 - x)([
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
セクシー女優で学ぶ画像分類入門
中国の剰余定理