ニュートン法とは - IT用語辞典
概要 ニュートン法（Newton’s method）とは、方程式の解を数値計算により近似的に求める手法の一つ。解を求めようとする範囲において微分可能かつ単調増加で下に凸であり、一次導関数が導出できる場合に適用できる。 方程式f（x）=0に対して関数y=f（x）を考え、まず適当なxを取ってf（x）に対する接線を求める。接線がx軸の交点におけるxの値は最初のxよりも解に近いため、このxについて再び接線を求めると、そのx軸との交点はさらに解に近づく。この操作を何度も繰り返し行なっていくと、xの値は解に収束していくため、適当な回数で操作を打ち切ることにより、回数に応じた精度の解の近似値を得ることができる。 非線形方程式を数値的に求める手法として古くから広く知られており、二分法より収束が早く、少ない計算回数で効率よく近似解の精度を高められる。1669年に万有引力の法則などで知られるアイザック・ニュー
)
除算 (デジタル) - Wikipedia
数値的（ディジタル）な除算アルゴリズムはいくつか存在する。それらのアルゴリズムは、低速な除算と高速な除算の2つに分類できる。低速な除算は反復する毎に最終的な商を1桁ずつ生成していくアルゴリズムである。回復型、不実行回復型、非回復型、SRT除算などがある。高速な除算は最初に商の近似値から出発して徐々に正確な値に近づけていくもので、低速な除算よりも反復回数が少なくて済む。ニュートン-ラプソン法とゴールドシュミット法がこれに分類される。 以下の解説では、除算を で表し、 Q = 商 (quotient) N = 被除数（分子 = numerator） D = 除数（分母 = denominator） とする。 余りのある整数除算（符号なし）[編集] ここで示すアルゴリズムでは、N を D で割って、商 Q と余り R (remainder) を得る。いずれの値も符号なし整数として扱う。 proc
Xorshift - Wikipedia
Xorshiftは疑似乱数列生成法の1つである。George Marsaglia（w:George Marsaglia）が2003年に提案した。演算が排他的論理和とビットシフトのみであるため高速である[1] などの特徴がある。 #include <stdint.h> struct xorshift32_state { uint32_t a; }; /* The state word must be initialized to non-zero */ uint32_t xorshift32(struct xorshift32_state *state) { /* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */ uint32_t x = state->a; x ^= x << 13; x ^= x >> 17; x ^=
エラトステネスの篩とは｜sieve of Eratosthenes - 意味/解説/説明/定義 ： IT用語辞典
エラトステネスの篩とは、与えられた整数以下の素数をすべて発見するアルゴリズムの一つ。素数判定法の一種で、古代ギリシャの学者であるエラトステネス（Eratosthenes）が紀元前3世紀頃に考案したとされるため、このように呼ばれる。 このアルゴリズムでは、2から与えられた数までの整数のリストを用意する。まず、このリストの中から最初の素数である2の倍数を消していく。リストに残った整数のうち、先頭にある3が次の素数である。次に、リストの中から3の倍数を消してゆき、残った整数のうち先頭にある5が次の素数である。このように、先頭に残った数の倍数をリストから消してゆき、その都度先頭に残った数を集めると、素数のリストが得られる。 この操作は、先頭に残った素数の自乗が与えられた数を超えるまで繰り返せばよく、これ以降にリストに消されずに残っている数はすべて素数である。整数においてはA×B＝B×Aが成り立つた
二分探索とは - IT用語辞典
概要 二分探索（binary search）とは、データ検索アルゴリズムの一つで、ソート（整列）済みのデータ群の探索範囲を半分に絞り込むを操作を繰り返すことで高速に探索を行う手法。 まず、データを降順（大きい順）あるいは昇順（小さい順）に並べ替え、探索したいデータが中央の要素より大きいか小さいかを調べる。これにより、データが全体の前半分にあるか後ろ半分にあるかを判定することができるため、存在しない側の半分は探索範囲から外すことができる。 半分になったデータ群の中央の要素と再び比較し、前半と後半のどちらにあるかを調べる。この操作を繰り返し行うことで、一回の操作ごとに探索範囲の大きさが半分になっていき、中央の要素が求めるデータに一致するか、探索範囲の要素数が一つになる（求めるデータは見つからなかったことが確定する）と探索は終了する。 値の大小は文字の索引順の前後関係などに適宜置き換えることによ
バックトラッキング - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Backtracking|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があり
LZ78 - Wikipedia
LZ78は、1978年にジェイコブ・ジヴ (Jacob Ziv) とエイブラハム・レンペル (Abraham Lempel) によって開発されたデータ圧縮アルゴリズム。 ジヴ、レンペルらによるLZ77が発表当時ユニバーサル性を証明できていなかったため、完全なユニバーサル性が証明できる本手法が提案された。 1984年に、実用的な改良となるLZWが提案された。 読み込んだ記号列から動的に辞書を作成して、それをもとに入力記号列を置き換えていく。そのため、動的辞書法とも呼ばれる。 また、記号列の長さを増して部分列に分解していくことから、増分分解法とも呼ばれる。 LZ77と同様にすでに符号化が終わっている過去の記号列を参照するが、明示的に破棄しない限り、登録した単語をすべて使用する。
ユークリッドの互除法とは - IT用語辞典
概要 ユークリッドの互除法（Euclidean algorithm）とは、二つの自然数の最大公約数を求める計算手順（アルゴリズム）の一つ。古代ギリシャの数学者ユークリッド（Euclid/エウクレイデス）の発見した古典的な手法で、紀元前4世紀頃に編纂された「原論」に掲載されており、記録に残る最古のアルゴリズムとも言われる。 二数の最大公約数は両者とも割り切ることができる自然数（公約数）のうち最大のものだが、これは大きい方を小さい方で割った余り（剰余）と小さい方との最大公約数に等しいという性質があり、これを利用して効率的に算出する。 aとbの2つの数（a≧bとする）の最大公約数を求める場合、まずaをbで割った余りb'を求める。次に、b'をaで割った余りa'を求める。さらに、a'をb'で割った余りを求め…と交互に余り同士の割り算を繰り返し、初めて割り切れた（余りが0になった）ときの除数（割る方の
二分法 - Wikipedia
この項目では、数値解析における二分法について説明しています。ゼノンのパラドックスの二分法については「ゼノンのパラドックス」を、誤った二分法については「誤った二分法」を、論理学・哲学上の二分法（dichotomy）については「二項対立」を、数理的な二分法については「2値論理」をご覧ください。 数値解析における二分法（にぶんほう、英: bisection method）は、解を含む区間の中間点を求める操作を繰り返すことによって方程式を解く求根アルゴリズム。反復法の一種。 方法[編集] 2分法 赤線は解の存在する範囲。この範囲を繰り返し1/2に狭めていく。 ここでは、となるを求める方法について説明する。 ととで符号が異なるような区間下限と区間上限を定める。 との中間点を求める。 の符号がと同じであればをで置き換え、と同じであればをで置き換える。 2.に戻って操作を繰り返すことにより、となるに近づ
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 :=
エラトステネスの篩 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "エラトステネスの篩" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2019年6月) エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がついている。
ランダウの記号 - Wikipedia
スターリングの公式はランダウの記号を用いてと書くこともできる。 ランダウの記号（ランダウのきごう、英: Landau symbol）は、主に関数の極限における漸近的な挙動を比較するときに用いられる記法である。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （数字の0ではない）を用いることから（バッハマン-ランダウの）O-記法 (Bachmann-Landau O-notation[1])、ランダウのオミクロンなどともいう。 記号 O はドイツ語のOrdnungの頭字にちなむ[2]。 なおここでいうランダウはエトムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。 ランダウの記号 は 、x
末尾再帰 - Wikipedia
一般に再帰呼び出しが可能な言語では、サブルーチン呼び出しのたびにスタックに呼び出し先から戻るための情報を保存する。そのため再帰が深くなりすぎるとスタックオーバーフローでプログラムが異常終了する。 そのような場合、次のようにループに変換して回避する。 { 変換前 } function F (a1:T1, a2:T2, ..., an:Tn) : T0 begin P ; return func (b1, b2, ..., bn) ; end ; { 変換後 } function F (a1:T1, a2:T2, ..., an:Tn) : T0 begin loop P ; a1 := b1 ; a2 := b2 ; : an := bn ; end loop ; end ; { Ti は型、P は手続き、bi は値または a1～an に対する副作用を伴わない式である。 それ以外の識別子は変
幅優先探索 - Wikipedia
ドイツの都市間の接続を示した例 フランクフルトから幅優先検索を行った場合にできる木構造 幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。 幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。最良優先探索とは異なり、ノード探索にヒューリスティクスを使わずに、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する。 アルゴリズム[編集] 根ノードを空のキューに加える。 ノードをキ
深さ優先探索（バックトラック法） - Wikipedia
深さ優先探索のイメージ 深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。 形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードはスタックに貯める。 深さ優先探索の空間計算量は幅優先探索の空間計算量より最悪のケースでは同じだが一般的なケースではずっと小さい。また、探索の種類によっては、分岐を選択するためのヒューリスティックな方
ニュートン法 - Wikipedia
数値解析の分野において、ニュートン法（ニュートンほう、英: Newton's method）またはニュートン・ラフソン法（英: Newton–Raphson method）は、方程式系を数値計算によって解くための反復法による求根アルゴリズムの1つである。対象とする方程式系に対する条件は、領域における微分可能性と2次微分に関する符号だけであり、線型性などは特に要求しない。収束の速さも2次収束なので古くから数値計算で使用されていた。名称はアイザック・ニュートンとジョゼフ・ラフソンに由来する。 ニュートン法の一手順の概念図 (青い線が関数 f のグラフで、その接線を赤で示した). xn よりも xn+1 のほうが、 f(x)=0 の解 x についてのよりよい近似を与えている. この方法の考え方は以下のようである：まず初めに、予想される真の解に近いと思われる値をひとつとる。次に、そこでグラフの接線
二分探索 - Wikipedia
二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。 ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。 大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。 n個のデータがある場合、時間計算量は[1]である（O記法）。 n個のデータの中央の値を見ることで、1回の操作でn/2個程度（奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個）の要素を無視することができる。
ハフマン符号とは - IT用語辞典
概要 ハフマン符号（Huffman code）とは、1952年にデビット・ハフマン（David Albert Huffman）氏が考案した、データ圧縮方式。代表的な可逆圧縮符号の一つで、現代でもファイル圧縮や画像ファイル形式など様々な場面で応用されている。 データの内容を損なわずに短い符号列に変換する圧縮アルゴリズムの一つで、符号化方式を「ハフマン符号化」（Huffman coding）、得られる圧縮符号を「ハフマン符号」（Huffman code）という。圧縮符号を展開すると完全に元通りのデータを復元することができる可逆圧縮である。 基本的な考え方は、対象データ列に出現する各パターンの頻度を調べ、高頻度で現れるパターンには短い符号（ビット列）を、低頻度のパターンには長い符号を割り当てることで全体のデータ長を短縮する。このような圧縮符号を「エントロピー符号」という。 ハフマン符号ではデータ
ユークリッドの互除法 - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Euclidean algorithm|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針につい
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://yaplog.jp/love_rabbit/archive/43
