ヒルベルト曲線 - Gushwell's C# Programming Page
ヒルベルト曲線とは、ドイツの数学者ダフィット・ヒルベルトが考案したフラクタル図形の一つで、再帰的に定義できる空間充填曲線です。 ヒルベルト曲線は、コの字の形状を基本図形とし、以下の４つの基本描画ルールの再帰的組合せで描くことができます。 Ldr(n) = Dlu(n-1), Left, Ldr(n-1), Down, Ldr(n-1), Right, Urd(n-1) Urd(n) = Rul(n-1), Up, Urd(n-1), Right, Urd(n-1), Down, Ldr(n-1) Rul(n) = Urd(n-1), Right, Rul(n-1), Up, Rul(n-1), Left, Dlu(n-1) Dlu(n) = Ldr(n-1), Down, Dlu(n-1), Left, Dlu(n-1), Up, Rul(n-1) ※ n が 0 の時には、何も描画しませ
The Sorting Algorithm Demo
Sorting Algorithms The animations on this page illustrate a number of different sequential and parallel sorting algorithms. The relative execution times of the animations give a very rough idea of the relative speeds of the algorithms. Each algorithm is finished when its colored lines disappear. Speed and Efficiency Analysis. Bubble Sort is a sequential algorithm, with an average case time of O(n2
病みつきになる「動的計画法」、その深淵に迫る
数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。 もしあなたが知ってしまったなら――病みつきになる動的計画法の集中講義 前回の『アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった』で動的計画法とメモ化再帰を説明しましたが、前回の説明ではまだ勘所をつかめていない方がほとんどでしょう。そこで、これらを完全にマスターするため、今回はもう1つ具体例を挙げながら練習したいと思います。 どういった問題を採用するかは悩みましたが、非常に有名な「ナップサック問題」を取り上げて説明します。 ナップサック問題とは以下のような問題です。 幾つかの品物があり、この品物にはそれぞ
Treemapping - Wikipedia
Treemap of Singapore's exports by product category, 2012. The Product Exports Treemaps are one of the most recent applications of these kind of visualizations, developed by the Harvard-MIT Observatory of Economic Complexity. In information visualization and computing, treemapping is a method for displaying hierarchical data using nested figures, usually rectangles. Treemaps display hierarchical (t
Paxosお勉強メモ - スティルハウスの書庫
Paxosのお勉強メモです（以下、分散システムとか無知なのですごく勘違いしてる可能性ありますので要注意） Wikipedia: Paxos algorithm Paxos is a family of protocols for solving consensus in a network of unreliable processors. Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communication medium may experience failures. Paxosは、信頼性の低い複数の処理ノードによるネットワークで「コンセンサス
みずぴー日記
JSXの特徴は、トップページにも書いてあるとおり「faster, safer, easier」の3つです。安全性とか簡単さについては人とか状況によって様々な定義や意見がありますが、唯一Fasterだけは客観的に測れます。 しかしJSXと速度については、トップページにあるBox2Dとshootingのデータ*1とAOBench on JSXぐらいしかありません。 というわけでWebkitで使われているSunSpider 1.0.2 JavaScript BenchmarkをJSXに移植してJavascriptと速度を比較してみました。*2 環境 sunspider Benchmark for JSX - JSX版ベンチマーク Sunspider Benchmark for Javascript - Javascript版ベンチマーク GitHub - mzp/sunspider-jsx: s
人生を最大限に楽しむための方法 〜アルゴリズマー的人生最適化〜 - chokudaiのブログ
今までのブログでもう判ってもらえているかと思いますが、僕は「頭を適切に使って論理的に考えると人生が楽しくなるよ！」って主張を強く持っています。その主張が現状少し弱く感じたので、一つ具体例として、「人生をアルゴリズマー的に最大限楽しむ方法」というのを少し紹介してみようと思います。数式を多用していますが、ぶっちゃけ読み飛ばしても読めると思うので、数学アレルギーの人は適度に読み飛ばして読んでくださいな。 目的を明確に定義する さて、「人生を最大限に楽しむための方法」とありますが、そもそも最大限に楽しむって何だろう？って問題が発生します。そこで、問題を明確に定義しましょう。まずは、貴方が、ある瞬間でどれくらい楽しさを感じているか、という関数fを定義します。この関数fは、貴方の行動、または選択の集合Aと、その時の時間tを与えて、f(A,t)とすることが出来ます。よって、これを人生の間で積分して最大化
XOR交換アルゴリズム - Wikipedia
XOR交換(エックスオアこうかん、XOR swap)は、コンピュータ・プログラミングのアルゴリズムの一種であり、排他的論理和(XOR)を使用して一時変数を使わずに同じデータ型のふたつの変数の(異なる)値を交換する操作である。 このアルゴリズムはXORの対称差という性質を利用したものである。すなわち、任意のA, Bについて、(A XOR B) XOR B = A が成立することである。 標準的な交換アルゴリズムでは一時的な格納場所が必要となる。x と y の値を交換する場合、以下のようになる。 y の値を一時格納域にコピーする：temp ← y y に x の値を代入する：y ← x x に一時格納域の値を代入する：x ← temp あるいは、x と y が整数ならば、以下のようなアルゴリズムで交換することができる。 x := x + y y := x - y x := x - y ただし、
最尤推定 - Wikipedia
最尤推定（さいゆうすいてい、英: maximum likelihood estimationという）や最尤法（さいゆうほう、英: method of maximum likelihood）とは、統計学において、与えられたデータからそれが従う確率分布の母数を点推定する方法である。 この方法はロナルド・フィッシャーが1912年から1922年にかけて開発した。 観測されたデータからそれを生んだ母集団を説明しようとする際に広く用いられる。生物学では塩基やアミノ酸配列のような分子データの置換に関する確率モデルに基づいて系統樹を作成する際に、一番尤もらしくデータを説明する樹形を選択するための有力な方法としても利用される。機械学習ではニューラルネットワーク（特に生成モデル）を学習する際に最尤推定（負の対数尤度最小化として定式化）が用いられる。 最尤推定が解く基本的な問題は「パラメータ が不明な確率分布に
最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ
動的計画法とメモ化再帰 今回は、非常によく用いられるアルゴリズムである、「動的計画法」「メモ化再帰」について説明します。この2つはセットで覚えて、両方使えるようにしておくと便利です。 なお、メモ化再帰に関しては、第5・6回の連載の知識を踏まえた上で読んでいただけると、理解が深まります。まだお読みになっていない方は、この機会にぜひご覧ください。 中学受験などを経験された方であれば、こういった問題を一度は解いたことがあるのではないでしょうか。小学校の知識までで解こうとすれば、少し時間は掛かるかもしれませんが、それでもこれが解けないという方は少ないだろうと思います。 この問題をプログラムで解こうとすると、さまざまな解法が存在します。解き方によって計算時間や有効範囲が大きく変化しますので、それぞれのパターンについて考えます。 以下の説明では、縦h、横wとして表記し、プログラムの実行時間に関しては、
GC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）
GCアルゴリズム詳細解説 日本語の資料がすくないGCアルゴリズムについて詳細に解説します トップページページ一覧メンバー編集 × GC 最終更新： author_nari 2010年03月14日(日) 20:47:11履歴 Tweet このWikiが目指す所 GCとは？ GCを学ぶ前に知っておく事 実行時メモリ構造 基本アルゴリズム編 Reference Counter Mark&Sweep Copying 応用アルゴリズム編 IncrementalGC 世代別GC スナップショット型GC LazySweep TwoFinger Lisp2 Partial Mark and Sweep -Cycle Collection- Mostly Parallel GC train gc MostlyCopyingGC(Bartlett 1989) TreadmillGC(Barker 1992)
d.y.d. - 最短性をチェックする
17:31 10/01/26 言語雑談会 言語雑談会 なるものに行ってきました。 自分は主に最近のD言語の話題 [PDF] [PPTX] についてと、 最近読んだ Pattern Calculus がイマイチ心に響かなかったという話と、 これも最近読んだ Prolog で SAT ソルバ という論文が格好良すぎて卒倒しそうです、などの話題を雑談していました。 SAT の話をしていてふと突然気づいたんですが、私が今までSATソルバに落としてみたことのある問題は、 すべて割と簡単に CNF（SATソルバがそのまま食べてくれる綺麗な形式の論理式） ができあがる問題だったようです、数独とか。 任意の命題論理式をCNFに変換できる指数爆発しない方法をそういえば知らないぞ俺！としゃべってたら soutaro さんが素晴らしい解説 をして下さいました。ありがたや。 あと shinhさんの 「コンピュータ
最短経路の探索 - nojimaの日記
なんか迷路の最短経路を求めよっていう問題がはやってるっぽいので解いてみた。いつもはC++を使ってるけど、今日はなんとなくCで書いてみた。アルゴリズムは幅優先探索。 #include <stdio.h> #include <string.h> #define N (100+2) char field[N][N]; int yqueue[N*N], xqueue[N*N]; int yprev[N][N], xprev[N][N]; const int dy[] = {-1, 0, 1, 0}; const int dx[] = {0, -1, 0, 1}; int main(void) { int i = 0, h = 0, first = 0, last = 0; while (fgets(field[h], N, stdin)) { char *p = strchr(field[h],
「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
A* - Wikipedia
A*探索アルゴリズム A*（A-star、エースター）探索アルゴリズム（エースターたんさくアルゴリズム）は、グラフ探索アルゴリズムの一つ。 最良優先探索を拡張したZ*に、さらにf値として「現時点までの距離」g と「ゴールまでの推定値」h の和を採用したもの[1]。h はヒューリスティック関数と呼ばれる。 A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、ヒューリスティック関数 h(n) という探索の道標となる関数を用いて探索を行うアルゴリズムである。h は各頂点 n からゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまな h を設計することが出来る。例えば、カーナビなどで用いられる単純な二次元の地図での探索では、h としてユークリッド距離 を使うことができ、この値は道に沿った実際の距離のおおまかな予
最短経路問題 - Wikipedia
グラフ理論における最短経路問題（さいたんけいろもんだい、英: shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。 2頂点対最短経路問題 特定の2つのノード間の最短経路問題。一般的に単一始点最短経路問題のアルゴリズムを使用する。 単一始点最短経路問題 (SSSP：Single Source Shortest Path) 特定の1つのノードから他の全ノードとの間の最短経路問題。この問題を解くアルゴリズムとしては、ダイクストラ法やベルマン-フォード法がよく知られている。 全点対最短経路問題 (APSP : All Pair Shortest Path) グラフ内のあらゆる2ノードの組み合わせについての最短経路問題。この問題を解くアルゴリズムとしては、ワーシャル-フロイド法が知られている。 このよう
)
Chord (peer-to-peer) - Wikipedia
In computing, Chord is a protocol and algorithm for a peer-to-peer distributed hash table. A distributed hash table stores key-value pairs by assigning keys to different computers (known as "nodes"); a node will store the values for all the keys for which it is responsible. Chord specifies how keys are assigned to nodes, and how a node can discover the value for a given key by first locating the n
細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック
細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック：最強最速アルゴリズマー養成講座（1/3 ページ） 競技プログラミングはレベルの高い人たちの集まり――そんな考えを持っている初心者の方、TopCoderはあなたのコーディングスキルを爆発的に高める魔法のような場です。今回は、初心者にこそお勧めしたいTopCoderの魅力について考えます。 教育的な観点から見るTopCoder 今回からTopCoderに関する実践的アルゴリズムを解説していく予定でしたが、序盤のうちに触れておきたいことがありましたので、今回の枕は“教育的視点から見るTopCoder”というテーマで少し書こうかと思います。 まず、最初に宣言しておきたいことは、この連載は初心者向きである、ということです。「どう考えても上級者向けだろう」という意見はたくさんの方から寄せられていますが、筆者は、まだプログラミングレ
広く知られているinsertion sortのコードは駄目すぎる - やねうらお−よっちゃんイカを食べながら年収1億円稼げる(かも知れない)仕事術
insertion sortは「挿入ソート」と訳される。(Wikipedia→ http://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88 ) ■ 日本語版 Wikipediaの日本語のページのコードを引用すると次のようになっている。 for (i = 1; i < n; i++) { tmp = data[i]; for (j = i; j > 0 && data[j-1] > tmp; j--) { data[j] = data[j-1]; } data[j] = tmp; }上のコードでは、内側のループでinsertの必要がなかった場合でも最後にdata[j] = tmpでtmp変数をwrite backしており、しかも、insertの必要のなかった場合でもj=iが1回実行される。それらの意味に
降順insertion sortについて - やねうらおブログ(移転しました)
昨日の記事で、世間で広く知られているinsertion sortのコードがいかにひどいかについて書いた。 私の提案したコードをWikipediaにも掲載(注記としてだろう)したほうがいいのではという意見をいくつか頂戴した。 Yuichirou 2009/11/26 02:03 私はyaneuraoさんのコードの方が可読性にも優れていると思います。むしろ日本語版Wikipediaのコードは脱出条件が複雑な内側のループを無理にfor文で書いているため、可読性が落ちています。 yaneuraoさん、ぜひその最後のコードをWikipediaに掲載すべきだと思いますがいかがでしょうか。 上のYuichirouさんの意見は好意からだろうが、はてブでは、次のような否定的な意見も見られる。 shuji_w6e 「馬鹿すぎる」とか「駄目すぎる」とか何様なんだろ？調べて回ったついでに全部書き換えてくればいいの
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
