8時間を0.01秒に短縮 「アルゴリズムの素晴らしさが2分で分かる動画」が今すぐ勉強したくなる分かりやすさ
※本記事はアフィリエイトプログラムによる収益を得ています アルゴリズムの素晴らしさを2分で解説した動画が、とても分かりやすくためになると人気です。なるほど、これがアルゴリズムと仕組みかぁ。 最短経路をアルゴリズムで算出しよう この動画では、迷路を最短手数で解くアルゴリズムについて解説。迷路はマス目状になっており、全部で8900億個の手順が存在するものとなっています。全ての経路を試せば最短手順を導き出せますが、普通のコンピュータでは約8時間かかってしまう計算になります。 全パターンの網羅は非常に時間がかかります そこで計算の手順を変更。スタートに0を書き、その隣1を、また隣に2……と繰り返していきます。こうして進めていくと最終的にゴールは34となり、この34が最短手数となることが分かります。今度はゴールから34，33，32とたどっていけば、最終手数で進む経路の1つが導き出せました。 数字を振
ハミング符号 : データの誤り検知/訂正をインタラクティブに学ぶ | POSTD
今週お話しするのは、誤りの検知についてと、さらに誤りの訂正についてです。 我々が住んでいる世界は完璧ではなく、デジタルの信号(on/off)を扱う時でさえ誤りが生じます。電力の異常によりビットが反転することがあるのです。ハードウェアも失敗を起こすことがあり、信号が歪められることもあります。 デジタル信号に生じた誤りを検知する方法については既に過去に書いたことがあります。もっとも一般的なやり方は、ある種のパリティビット(ご存知なくともご心配なく。以下でパリティの意味を説明します)です。ある長さの単語に対し、シンプルなパリティビットをたった1つ加えることで、単語中のビットが1つ反転した場合にそれを検知することができます。「エラーが起こったことがわかる」ということは有益ですが、1個のパリティビットだけではその誤った信号を修復することができません。また、信号中に2個以上の誤りがあった場合、その誤り
GPUでボロノイ図を描画する : WebGLを用いてスムーズに描画できる高速アルゴリズム | POSTD
GPUに適したJump Floodingおよびボロノイ図と距離変換への応用 注：このページのデモはWebGL機能を使っているためモバイル機器では機能しないことがあります。きちんと表示させるためにはデスクトップコンピュータ上で記事を読むことをお勧めします。 ボロノイ図とはなんでしょうか。下記のデモを見ていただければお分かりになると思います。左のキャンバスをクリックすると、色付きの「母点」が植え付けられます。右のキャンバスでは、各ピクセルが一番近い点の色に着色されます。ドラッグすればより多くの点を配置できます。 デモ#2：左のキャンバスには動いている点が複数あります。右のキャンバスには対応するボロノイ図が表示されています。どちらのキャンバスでも構いませんから、マウスオーバして黄色い点を動かしてみてください。水の中を泳いでいる黄色い魚をイメージしました。 もう1つ面白いデモを用意しました。左のキ
情報理論を視覚的に理解する (1/4) : | POSTD
世界を考察する新しい方法を手に入れたときの感覚が大好きです。特に好きなのは、いずれ具体的なコンセプトに形を変えるボンヤリとした考えがあるときです。情報理論は、その最たる例です。 情報理論は、多くの物事を説明するための正確な言葉を与えてくれます。自分はどのくらい理解できていないのか？質問Aの答えを知ることが、質問Bを答えるのにどのくらい役立つのか？ある種の信念が他の信念とどの程度似ているのか？こういうことに対し、若くて未熟なころから自分なりの考えがありましたが、情報理論に出会って正確で強固な考えとしてはっきりと固まりました。その考えは、桁外れの、例えばデータの圧縮から量子物理学や機械学習、さらにはその間に広がる数多くの分野に応用が利くものです。 残念なことに、情報理論は少々威嚇的に見えてしまうのですが、そう断定すべき根拠は全くないと思います。実際、情報理論の多くの重要な概念は完全に視覚的に説
動きで分かる！試しながらアルゴリズムのことが理解できる「アルゴリズム図鑑」が凄い！ - isuta（イスタ） -私の“好き”にウソをつかない。-
「エクセル」24年春の新作をいち早く大公開！注目はプランプ効果でふっくら唇になれる究極「ベージュリップ」
キャッシュフレンドリーな二分探索 ー データ構造を再考する | POSTD
現代のコンピュータのアーキテクチャに搭載されている高速のキャッシュメモリは、 参照の局所性 に優れた(＝一連のものとしてアクセスした要素が、互いに近いメモリのアドレスに配置されている)データ構造を好みます。これは、 Boost.Containerの平坦な（ツリー状ではない）連想コンテナ のようなクラスを陰で支えている理論的根拠です。要素を連続的に（かつ順序だてて）保存すると同時に、標準的なC++ノードベースの連想コンテナの機能性をエミュレートします。以下にあるのは、要素が0から30の範囲の時、 boost::container::flat_set の中で 二分探索 がどのように行われるのかを示した例です。 探索で目的の値を絞り込むにつれて、アクセスされる要素は次第に近くなっていきます。そのため、最初のうちは大きな距離を飛び越えていくような感じであっても、参照の局所性は このプロセスの最後の
GPUとセルオートマトンで経路探索問題を解いてみる | POSTD
前回は、グラフィックカード上だけで コンウェイのライフゲームを実行するアイデアを説明しました 。このアイデアは、3つ以上の状態を有するオートマトンを含め、 どのような セルオートマトンにも当てはめることができます。今回の投稿では、二次元グリッドの 最短経路問題 をGPUだけで解決するのに、このアイデアを活用してみたいと思います。CPUによる従来の検索と比べても、その速さは遜色ありません。 JavaScript側の状態は基本的に以前と同様なので（2つのテクスチャと、それらを繋いでオートマトンを次のステップに進めるフラグメントシェーダ）、ここでは説明は割愛します。変更したのは次の2点、（オートマトンの全ての状態を表現する）セルの状態のエンコーディングと（新しいルールをプログラムする）フラグメントシェーダです。 オンラインデモ （ ソース ） デバッグや実験のために使ったセルオートマトンの純粋な
数あるソートアルゴリズムをビジュアル化し堪能できるサービス「SORTING」
大小の関係が決められたデータを小さい順や大きい順に並び替える作業はソートと呼ばれ、コンピュータには欠かせないプログラムです。そのため、ソートをより早く・確実に・効率良く実行できるように、さまざまなアルゴリズムが考案されてきました。そんなコンピュータの発展にかかせない役割を果たしてきたソートアルゴリズムをビジュアル化することで直感的に理解できるのが「SORTING」です。 SORTING http://sorting.at/ これがSORTINGのサイトページです。ソートアルゴリズムを選択してページ下の「PLAY」ボタンをクリックすると、そのソートアルゴリズムを使ってボールが並び替えられます。 たとえばアルゴリズム「クイックソート」でランダムに並んだ状態の大きさの異なるボールを左から小さいもの順に並び替えるとこんな感じです。 選べるソートアルゴリズムは、クイックソート・ヒープソート・スムース
JavaScript で重複のない乱数を生成する | Web Design Leaves
重複のない乱数を生成して配列に格納して返す方法。 パラメータに生成する乱数の数を受け取り、重複のない整数の乱数を発生させ、配列に入れて返す関数を作成。例えばパラメータに 10 を指定すると 0 から 9 の間の10個の重複のない整数をランダムに生成する。 パラメータ count の数だけ乱数を発生させる。 Math.random()で取得した値に「count」をかけて、Math.floor() で切り下げて整数にする。 すでに同じ数値が生成されているかは、すでに生成した乱数と発生した乱数を比較。 異なる値が発生されるまで繰り返し。 function generate_randomx(count) { //生成した乱数を格納する配列を初期化 var generated = new Array(); //生成した乱数を格納している配列の長さ（生成した乱数の数） var generatedCou
404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)
2007年12月04日08:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - 二分探索(binary search) 今回は二分探索を取り上げます。 検索:コンピューターの最もよくある利用法 「二分探索って何?」「ググレカス」と言われないためにこの記事は存在するのですが、Webの検索に限らず、「目的のデータを見つけて取り出す」というのは、およそコンピューターの利用法で最もポピュラーなものです。 配列:コンピューターがデータを扱う根本的な方法 そのデータはコンピューターのなかでどう置かれているかというと、非常に単純です。デジタル化されたデータ=数値が一定間隔で並んでいるだけです。こういうデータ構造を、配列(array)といい、この数値一個一個のことを要素(element)と言います。 現代のコンピューターでは、最小要素はバイト(byte)と呼ばれています。このバイトの中には0と1
大量のテキストからランダムに少数の行を抽出したい - Reservoir Sampling - 唯物是真 @Scaled_Wurm
前に以下のような記事を書きましたが、大量のテキストではうまくいかなかったので新たに書きました ファイルからランダムにN行取り出す(shufコマンド) - 唯物是真 @Scaled_Wurm 上の記事ではテキストをランダムに\(k\)行取り出したい時"shuf -n k"コマンドでランダムにシャッフルした\(k\)行を取り出していました ところが非常に大きなテキストファイルに対して上のコマンドを実行すると、一度にデータを全部メモリに読み込み始めているのか、すごい勢いでメモリを消費していきました(sort -Rでも) そこでメモリをあまり使わずにランダムに\(k\)行取り出す方法について調べました まず基本的な非復元抽出のアルゴリズムは以下の記事の発展手法とか追記のあたりの話がわかりやすいと思います 非復元抽出の高速かつ実装が簡単な方法を考える - 睡眠不足？！ この記事の話も一度全部の要素を
【ボイド】JavaScriptとHTML5で『群れ』をシミュレーションしてみよう【プログラミング】 - あのねノート。
2013-09-28 【ボイド】JavaScriptとHTML5で『群れ』をシミュレーションしてみよう【プログラミング】 適当プログラミング解説シリーズ やり方 はじめに。 ボイドを知っていますか？ボイド(Boids)はCraig Raynoldsによって発表された人工生命シミュレーションプログラムです。Boidsとはによると、以下のように記述されています。 Boid（ボイド）とは、1987年にCraig Raynoldsによって発表された理論です。 この理論は、３つのルールを規定するだけで鳥の群れをシミュレーションできるというものです。 ちなみにBoidという名の由来は、鳥もどきという意味の言葉birdoid（バードイド）が短くなりこのように呼ばれるようになりました。 シンプルな3つのルールで生きているかのような群れができるのでとても興味深く、魅力的なゲームです。 ボイドを応用して作られ
川中真耶,杵渕朋彦,椎名俊輔『続・アルゴリズムを学ぼう』を販売開始しました！ - 達人出版会日記
続・アルゴリズムを学ぼう【電子書籍】川中真耶, 杵渕朋彦, 椎名俊輔 アスキー・メディアワークス 発行日: 2013-08-02 対応フォーマット: PDF 詳細を見る 好評だった川中真耶,杵渕朋彦,椎名俊輔『アルゴリズムを学ぼう』に引き続き、『続・アルゴリズムを学ぼう』が公開されました！ 『アルゴリズムを学ぼう』は、弊社が委託販売している書籍の中ではもっとも部数が伸びたものの一つですが、『続・アルゴリズムを学ぼう』はその続編ということで、前作の登場人物に加え、新たに新入生も一人入って来ました。そして彼女がゲーマーということもあり（？）、書籍で扱うアルゴリズムもゲーム寄りな部分が増えているのが特徴です。 第1章は計算量の復習から始まり、続く『ライツアウトの数学』ではゲームが解ける・解けないの判別のために線形代数と体の話が出てきて一瞬心が折れそうになりますが、続く章では文字列や正規表現、準最
遺伝的アルゴリズムとは (イデンテキアルゴリズムとは) [単語記事] - ニコニコ大百科
遺伝的アルゴリズム単語 イデンテキアルゴリズム 4.2千文字の記事 28 0pt ほめる 掲示板へ 記事編集 概要分かりやすい例具体的にやってみよう利点と欠点遺伝的アルゴリズムが深く関わる諸作品関連動画関連商品関連項目掲示板遺伝的アルゴリズムとは、生物群が環境へ適応するときの遺伝学的変化の諸概念（染色体の交叉・突然変異・自然淘汰）を問題解決方法に見立ててその解を探る手法である。英語ではGenetic Algorithm（略語でGA）。 概要 問題の解の候補を生物の各個体の遺伝子に見立て、ランダムに生成した各個体の遺伝子を交換や突然変異により解にふさわしい遺伝子を持つ個体を生み出すように処理を進めていく。各個体が環境にどの程度適応しているかを算出し、遺伝子の適応度が高い個体は子孫を残しやすく、適応度が低い個体は子孫を残しにくくすることから遺伝的アルゴリズムと呼ばれる。 厳密解よりも適度に厳密
![遺伝的アルゴリズムとは (イデンテキアルゴリズムとは) [単語記事] - ニコニコ大百科](https://cdn-ak-scissors.b.st-hatena.com/image/square/5bd1fac8d544d19340796767c18bdf23d7d3493d/height=288;version=1;width=512/https%3A%2F%2Fdic.nicovideo.jp%2Fimg%2Fog_b.jpg)
遺伝的アルゴリズムとは
遺伝的アルゴリズムとは 遺伝的アルゴリズム（ＧＡ）とは自然淘汰により最適な遺伝子が残ってきたようにシステムの中で自然淘汰のシュミレーションを行い最適解を求めようというものです。似たような言葉に遺伝的プログラミング（ＧＰ）がありますが自然淘汰をシュミレーションするという意味では同じですが処理も適用業務も異なるので注意が必要です。 遺伝的アルゴリズムの基本フロー 遺伝的アルゴリズムの簡単なフローは次の通りです。 巡回サラリーマン問題を例に遺伝的アルゴリズムを説明すると あまり良い例ではないかもしれませんが巡回サラリーマン問題を例にして上のフローを適用してみます。 巡回サラリーマン問題とは例えば次の５都市をサラリーマンが巡回する最小ルートを求めよという簡単な問題です。 答えは実は簡単で次のように都市Ａ-Ｂ-Ｃ-Ｄ-Ｅの順番で巡回すれば良いことになります。 これをプログラミングで解決しようとすると
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Jun Rekimoto : 暦本純一 on Twitter: "もう２０年以上前の古典だけど今更みてすばらしい！なんか頑張って生きている命が感じられる。 https://t.co/nXRjjdvRDm"
Choose a Random Option based on a Range | CSS-Tricks
動画の中の人が何をしているか分かるアルゴリズム、開発される
サービス終了のお知らせ
IDEA * IDEA
