拡張ユークリッド互除法
ユークリッドの互除法は最大公約数を計算する効率的な方法として古くから知られている方法です。 これについては，ユークリッドの互除法の項で説明しました。ここでは，その発展系の一つで色々なところでよく使われている，拡張ユークリッド互除法について説明します。 ユークリッドの互除法は２つの自然数 x，y の最大公約数を効率的に計算する方法でした。 例えば，GCD(13,5) を計算するのに， 13=2*5+3 5=1*3+2 3=1*2+1 2=2*1 を求めて，GCD(13,5)=1 とするものでした。今の場合この計算は，全く自明で，互除法は不要な感じがします。しかし，少し視点を変えるとそうとも言えません。上の式のうち最後の項を除いて，それぞれ，移項すると， 13-2*5=3 5-1*3=2 3-1*2=1 が得られます。ここで，３行
拡張版ユークリッドの互除法
よくある問題 ところで問題です。29リットル入るバケツと17リットル入るバケツがあります。この2つのバケツを使って、別のバケツに1リットルの水を入れなさい。 頭の軟らかさを競うテレビ番組でおなじみですね。これが蚊取り線香になったり縄になったりしますが、すべて同じ問題です。この問題は頭の軟らかさは関係がありません。ユークリッドの互除法を知っているかどうかで決まります。知識の問題です。多くの場合、「頭のやわらかさ」というのは宣伝文句であり、そこにはなにがしかの法則・アルゴリズムが存在します。 この問題の本質は、以下の数式で表すことができます。 29x + 17y = 1 となる(x,y)の組を見つけること このとき、(x,y)のどちらかは必ず負です。当たり前ですが。 拡張版ユークリッドの互除法の実際 ちょっと気づいてほしいのですが、もし、この問題が正しいのならば、全ての数は 29 と 17 で
はてな民に確率の問題を出してみよう - Pashango’s Blog
こんにちは、今回は確率の話です。 以前、職場で余興として問題を出したのですが、ほぼ全員がこの問題を知りませんでした。 理系が多く集まる職場なので、意外にみんな知らないんだなぁと思ったのですが、今度はリテラシーの高い（と勝手に思っている）はてな民に問題を出したら、どうなるんだろうと純粋な好奇心が沸いてきました。 なお有名な問題ですので、答えを知っている方はあまりヒントを出さない方向で・・・ 問１ ティムはテレビのクイズ番組に出演し見事優勝をはたしました、優勝賞品の自動車をゲットするチャンスを得たのです。 司会者は言いました。 「ここにＡ、Ｂ、Ｃの３つのドアがあります。 １つのドアの後ろには自動車、それ以外の２つのドアの後ろにはヤギがいます。 ティムは１つのドアを選び、そのドアの中に自動車が入っていれば賞品をゲットできます。 もし、ヤギが入っていた場合はハズレです。 さぁティム、どのドアを選び
一次不定方程式
を考える．未知数が2個以上あるのに方程式は一つしかない． 実数範囲で解は無数にあり確定しない．それで不定方程式と言われる． この一次不定方程式を満たす整数の組 を 一次不定方程式の整数解という． このように整数係数の方程式を「ディオファントスの方程式」ともいう． ディオファントス(Diophantos 前3世紀ごろ)は アレキサンドリアで活躍したとされるギリシア時代の数学者． 幾何学的であったそれまでの数学に代数学を導入, 著書のなかで二次方程式や不定方程式を解いた． 高校数学では のような2変数の場合が主な対象である． それでまず2変数の場合に調べ，それを一般化するという方向で考えよう． とが互いに素なとき一次不定方程式に関して次の事実が成立する． 整数解が存在する． すべての解を一般的な形にかける． 解を構成するアルゴリズムがある． 本節ではこれを示すいくつかの方法をまとめた後， 一
三項間漸化式を解く
行列で解く ではこれをもとに三項間漸化式を行列で求めよう． 三項間漸化式1に対し，連立二項間漸化式5を作る． 5の行列を とする． であるから， が求まればよい． 行列の 乗を求める方法はいろいろある．最も簡単で便利な方法を用いよう． を変数として を で割った余りを とする.つまり
12章 素因数分解アルゴリズム
概要 ここでは、素因数分解のための各種アルゴリズムについて解説する。 対象は、以下のとおり。 Brute force method ρ method（Pollard, Brent） p-1 method p+1 method 連分数法（Continued Fraction Method） 複数多項式二次ふるい法（MPQS : Multiple Polynomial Quadratic Sieve Method） 楕円曲線法（ECM : Elliptic Curve Method） 目次 Brute force method (Brute force method ～ Sample Program) ρ method p-1 method p+1 method 連分数法（Continued Fraction Method） 複数多項式二次ふるい法（MPQS : Multiple Polyno
カーネル法 正定値カーネルを用いたデータ解析
1 2004 11 24~26 Final version. Nov.26, 2004 2 I 1. 2. � � 3. � � PCA CCA . � � Bochner � representer 3 II 5. � � � ICA, 7. 4 g(x) Parzen window ∑ = − = N i i x x g N x p 1 ) ( 1 ) ( 5 1. � 6 � ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ = N m N m m X X X X X X X L M M L L 1 2 2 1 1 1 1 m N 7 x1 x2 z1 z3 z2 ) 2 , , ( ) , , ( 2 1 2 2 2 1 3 2 1 x x x x z z z = 8 � xi Φ(xi) zi H Ω H Ω H → Ω Φ : 9 � H = feature space
Microsoft PowerPoint - S5-SVM.ppt
5. サポートベクターマシン 5.1 マージン最大化の考え方 5.2 線形分離可能な学習データによるマージン最大化 5.3 線形分離不可能な学習データによるマージン最大化 5.4 サポートベクターマシン 5.1 線形分離可能な場合におけるマージン最大化 I II 次の学習データが与えられたとする。 ( y1 , x1 ), ( y2 , x 2 ),L , ( yl , xl ), x ∈ R n , y ∈ {−1,1} ただし， ⎧ 1 Lカテゴリ I y=⎨ ⎩− 1 Lカテゴリ II 2 パタン理解：サポートベクタマシン 1 パタン理解：サポートベクタマシン マージン最大化 マージン最大化 I I c c II φ x II φ x カテゴリ I とカテゴリ II は，以下の超平面で分離可能 であったとする。 ( x * φ) = c, φ =1
Microsoft Word - SVM.doc
[ 連載 ] フリーソフトによるデータ解析・マイニング第 31 回 Ｒ とカーネル法・サポートベクターマシン 1. カーネル法とは 図 1 に示すように、非線形データ構造を線形構造に変換することができれば、線形データ解 析手法で非線形データを容易に扱うことができる。 図1 変換による線形化のイメージ デ ータを変換することで、非線形構造を線形構造に変換することが可能である。例えば、図 2(a)に示す 2 次元平面座標系( x, y )上の 4 つの点 A1(1,1)、A2(1,-1)、A3(-1,-1)、A4(-1,1)を 考えよう。仮に A1 と A3 がひとつのクラス、A2 と A4 がひとつのクラスだとすると、平面上で クラスの境界線を一本の直線で引くことができない。しかし、新しい変数 z = xy を導入し、2 次 元 平 面 ( x, y )上 の 4 つ の 点
インパルス応答と伝達関数(アナログの場合) - 記
前回と同じことをアナログの場合について述べてみる．デジタルの場合と全く同じ議論ができることに注目されたい． フーリエ変換 フーリエ変換とは，アナログ信号処理における積分変換の1つである． 任意のアナログ信号のフーリエ変換は次式で表される． ただし，積分が発散してしまう場合はフーリエ変換は存在しない．その場合はラプラス変換を使う必要がある．なぜなら，フーリエ変換はラプラス変換の特殊な場合であるからである．ラプラス変換の収束領域が虚軸を含んでいれば，を代入するだけでフーリエ変換となる．逆に，虚軸を含んでいなければ，フーリエ変換は存在しなくなる．また，虚軸上に極がある場合には，としてもフーリエ変換とはならず，別の項を付け加える必要がでてくる． ちなみに，逆フーリエ変換は で表される． フーリエ変換と畳み込み積分 任意のアナログ信号のフーリエ変換をそれぞれ，とする． 今，のフーリエ変換を考えてみる
Cholesky 分解ノート 桂田 祐史 2008 年 6 月 9 日 書きかけである。 • 修正 Cholesky 分解のコード • 帯行列の場合のコード • Sylvester の慣性律のきちんとした説明 などは書いておきたい。それ��
Cholesky 分解ノート 桂田 祐史 2008 年 6 月 9 日 書きかけである。 • 修正 Cholesky 分解のコード • 帯行列の場合のコード • Sylvester の慣性律のきちんとした説明 などは書いておきたい。それから最初のうちは下三角因子 L を求めるように書いておいたが、 実際には上三角因子 U を求めるようにしているプログラムが多いので、いっそのこと、最初 から U を求めるような説明にしておくのが良いかもしれない。 1 序 広い意味の コレスキー, ホレスキー Cholesky 分解とは、対称行列に特化した LU 分解である。 この文書では行列は実行列であるとするが、複素行列の範囲で考えることも可能である (転 置の代りに Hermite 共役、実対称の代りに Hermite とするわけである)。 正則行列の LU 分解は線型計算において重要な基本操作である
cfv21.org - このウェブサイトは販売用です！ - 京大 東大 理工系 入試 問題 大学 早慶 東工大 リソースおよび情報
このウェブサイトは販売用です！ cfv21.org は、あなたがお探しの情報の全ての最新かつ最適なソースです。一般トピックからここから検索できる内容は、cfv21.orgが全てとなります。あなたがお探しの内容が見つかることを願っています！
2 次正方行列の累乗の次数減らし - ヨーキョクデイ
$A=\smqty(a&b\\c&d)$ なる 2 次正方行列があるとして、ケイリー・ハミルトンの定理 を使って $A^n$ の次数を減らそうという試み。 $\alpha = a+d, \beta = ad-bc$ とすると、ケイリー・ハミルトンの定理より、$$ \begin{align}A^2 &= (a+d)A-(ad-bc)E \\ &= \alpha A-\beta E \\ \end{align}$$ $$\begin{align}A^3 &= \alpha A^2-\beta A \\ &= \alpha(\alpha A-\beta E)-\beta A \\ &= (\alpha^2 - \beta)A-\alpha\beta E \\ \end{align}$$ $$\begin{align}A^4 &= (\alpha^2 - \beta)(\alpha A-\beta
その39 知っていると便利？ワールド変換行列から情報を抜き出そう
ホーム < ゲームつくろー！ < DirectX技術編 < 知っていると便利？ワールド変換行列から情報を抜き出そう その39 知っていると便利？ワールド変換行列から情報を抜き出そう 今回はちょっと息抜きです。ワールド変換行列（座標変換行列）は3Dゲームで多分一番よく使う行列だと思います。この行列は回転、スケール、オフセットの3要素から作成します。では、すでに作成されたワールド変換行列からそれらの要素は抜き出す事ができるのでしょうか？またワールド変換行列には具体的にどのような情報が詰め込まれているのでしょうか？この章では、そのようなワールド変換行列から抜き出す事ができる情報について整理してみます。 ① ワールド変換行列の作り方 今更なのですが、ワールド変換行列の基本についてまとめておきます。ワールド変換行列は回転、スケール、オフセットの3要素を表す行列の掛け算で作成するのが一般的です。各行列
Lμcifer @Wiki - オイラー角と行列の相互変換
おすすめリンク | 転職ならen | 転職ならエン | 派遣ならen | アルバイトならen | 就職ならen | デジカメプリント | 年賀状 | ましかくプリント | 辞書 | | 2ch風無料掲示板 | 無料ブログ作成 | ソーシャルプロフィール | 無料掲示板 | 高機能無料掲示板 | 無料ホームページ | 無料SNS |php |ポイント | | 新しいページ | 編集 | 差分 | 編集履歴 | ページ名変更 | アップロード | 検索 | ページ一覧 | タグ | RSS | ご利用ガイド | 管理者に問合せ | @wiki - 無料レンタルウィキサービス | プライバシーポリシー
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
COOL ONLINE - JAPAN - JAPAN ONLINE
http://www.ice.gunma-ct.ac.jp/~mame/kougi/kairo/kairotext2.pdf
生活や実務に役立つ高精度計算サイト