Marsaglia polar method - Wikipedia
The Marsaglia polar method[1] is a pseudo-random number sampling method for generating a pair of independent standard normal random variables.[2] Standard normal random variables are frequently used in computer science, computational statistics, and in particular, in applications of the Monte Carlo method. The polar method works by choosing random points (x, y) in the square −1 < x < 1, −1 < y < 1
黄金分割探索 - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Golden-section search|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針に
Procrustes analysis - Wikipedia
Procrustes superimposition. The figure shows the three transformation steps of an ordinary Procrustes fit for two configurations of landmarks. (a) Scaling of both configurations to the same size; (b) Transposition to the same position of the center of gravity; (c) Rotation to the orientation that provides the minimum sum of squared distances between corresponding landmarks. In statistics, Procrust
Zstandard - Real-time data compression algorithm
Zstandard is a fast compression algorithm, providing high compression ratios. It also offers a special mode for small data, called dictionary compression. The reference library offers a very wide range of speed / compression trade-off, and is backed by an extremely fast decoder (see benchmarks below). Zstandard library is provided as open source software using a BSD license. Its format is stable a
ハノイの塔 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "ハノイの塔" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2017年7月) 8つの円盤のハノイの塔 ハノイの塔（ハノイのとう、英: Tower of Hanoi）は、パズルの一種。 バラモンの塔または ルーカスタワー（英: Lucas' Tower）[注 1]とも呼ばれる。 以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。 円盤を一回に一枚ずつどれかの杭に移動させる
巡回セールスマン問題 - Wikipedia
巡回セールスマン問題を総当たりで解く場合のイメージ。左側で一つずつ探していき、より効率のいいルートが見つかった場合、右側のグラフが更新される。 巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。 問題例の大きさは、都市の数で表される。この問題は、計算複雑性理論においてNP困難と呼ばれる問題のクラスに属する。すなわち、問題例の大きさに関する決定性の多項式時間アルゴリズムが見つかりそうにない、計算量的に困難な問題である。なお、この問題の特殊ケースとして考えられるハミル
うさぎでもわかるP vs NP問題（NP完全、NP困難の違い）
こんにちは、ももやまです。 今回は「P vs NP問題」について少しわかりやすめにまとめました。 この問題は、数学上の未解決問題となっており、2019年6月現在でも6つが解決していません。その問題の1つが「P vs NP問題」となっています。 これらの未解決問題は、アメリカのクレイ数学研究所によって、100万ドル（約1億円）の懸賞金がかけられています。*1トリビアの泉でも紹介されました。 No.681 「数学の世界には解くと賞金１億円がもらえる問題がある」 （番組評価 85/100へえ） もちろん「P vs NP問題」も懸賞金がかけられている問題の1つです。 そんな「P vs NP問題」とはどんな問題なのかをわかりやすく説明していきたいと思います。 ※注意 今回は問題はYesかNoかを判定する問題だけを考えます。このような問題を決定問題と言います。決定問題の例としては、 300円以内で50
汎用検索ツリー - Wikipedia
汎用検索ツリー (GiST: Generalized Search Tree) はディスク上に木構造の検索機能を実現する データ構造 と API である。 GiSTはB+木を一般化したもので、並列実行性能が高くリカバリが可能な高さがバランスされた検索木のフレームワークを提供する。 また、保存できるデータ型や検索クエリに制限が無い。 GiSTは良く利用されるインデックス（B+木, R木, hB木, RD木 など）の実装に利用できる。 また、新しいデータ型に対して特化したインデックスを開発することも容易である。 ただし、GiST を使っても直接的には高さバランスではないツリー構造 (八分木やトライ木) を実装することはできない。 また、GiST は可逆および非可逆の圧縮をサポートしているが、各ノードのデータ型は同一でなければならない。 リーフにはノードとは異なる型を用いることもできる。 データ
局所性鋭敏型ハッシュ - Wikipedia
局所性鋭敏型ハッシュ（きょくしょせいえいびんがたハッシュ、英語: locality sensitive hashing）とは高次元のデータを確率的な処理によって次元圧縮するための手法である。ハッシュの基本的な考え方は類似したデータが高確率で同じバケットに入るようにデータを整理するというものである。多くの場合においてこのバケットの数は入力されるデータサンプルの数よりもずっと小さくなる。 局所性鋭敏型ハッシュを行うためのパラメータの集合をLSH族(Locality Sensitive Hashing Family)と呼ぶ。LSH族は距離空間と閾値、近似因子によって定義される。LSH族[1][2]は2点について次の2つの性質、 ならばとなる確率は以上である。 ならばとなる確率は以下である。 を満たす関数により与えられる族であり，はから一様乱数にしたがって選択される。このときは2点の距離を表す関数
kd木 - Wikipedia
3次元のkd木。根セル（白）をまず2つの部分セルに分割（赤）し、それぞれをさらに2つに分割（緑）している。最後に4つのセルそれぞれを2つに分割（青）している。それ以上の分割はされていないので、最終的にできた8つのセルを葉セルと呼ぶ。黄色の球は木の頂点を表している。 kd木（英: kd-tree, k-dimensional tree）は、k次元のユークリッド空間にある点を分類する空間分割データ構造である。kd木は、多次元探索鍵を使った探索（例えば、範囲探索や最近傍探索）などの用途に使われるデータ構造である。kd木はBSP木の特殊ケースである。 kd木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、kd木の根ノードから葉ノードまでの各ノードには1つの点が格納される[1]。この点もBSP木とは異なり、BSP木では葉ノードのみが点（ま
Edmonds' algorithm - Wikipedia
This article is about the optimum branching algorithm. For the maximum matching algorithm, see Blossom algorithm. In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an optimum branching). It is the directed analog of the minimum spanning tree problem. The algorithm was proposed independently firs
Scale-invariant feature transform - Wikipedia
The scale-invariant feature transform (SIFT) is a computer vision algorithm to detect, describe, and match local features in images, invented by David Lowe in 1999.[1] Applications include object recognition, robotic mapping and navigation, image stitching, 3D modeling, gesture recognition, video tracking, individual identification of wildlife and match moving. SIFT keypoints of objects are first
Kernighan–Lin algorithm - Wikipedia
This article is about the heuristic algorithm for the graph partitioning problem. For the heuristic for the traveling salesperson problem, see Lin–Kernighan heuristic. The Kernighan–Lin algorithm is a heuristic algorithm for finding partitions of graphs. The algorithm has important practical application in the layout of digital circuits and components in electronic design automation of VLSI.[1][2]
グラフ(ネットワーク)を奇麗に描画するアルゴリズム - mfumiの日記
グラフはノードと辺の集合から構成されているだけなので，その描画方法は任意です．例として，以下の3つのグラフはどれも同じです． グラフをどうやって奇麗に描画するかという研究は昔からおこなわれていて，そのうちの一つに力学モデルがあります(Wikipedia)．このモデルではノード間にある力が作用すると考えてそれが安定するような場所を探します．簡単な例ではノードを電荷だと仮定してそれぞれに働くクーロン力を計算し，それをもとにノード位置の修正をおこないます． 力学モデルのアルゴリズムで代表的なものにFruchterman-Reingold アルゴリズムがあります．このアルゴリズムは多くのグラフを扱うライブラリでサポートされているようです． このアルゴリズムの考え方はシンプルで，ノードに影響する力が2つあります．一つは自分以外の全てのノードからの斥力，もう一つが隣接ノードからの引力です．斥力f_rと
TimeComplexity - Python Wiki
This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still-under development versions of CPython) may have slightly different performance characteristics. However, it is generally safe to assume that they are not slower by more than a factor of O(log n). Generally, 'n' is the number of elements current
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
X-tree - Wikipedia
Algorithm Visualizer