教科書は『統計学のための数学入門30講』シリーズ 科学のことばとしての数学 永田 靖 著 朝倉書店 おすすめ度★★★★★ 統計学のための数学入門30講 (科学のことばとしての数学)作者: 永田靖出版社/メーカー: 朝倉書店発売日: 2005/04/01メディア: 単行本購入: 2…

ryamadaのコンピュータ日記の記事へリンク：時間計算量と領域計算量

ryamadaのコンピュータ日記の記事へリンク：時間計算量クラス

ryamadaのコンピュータ日記の記事へリンク：計算可能性

ryamadaのコンピュータ日記の記事へリンク：計算モデル

ryamadaのコンピュータ日記の記事へリンク：アルゴリズム

グラフの問題には、アルゴリズム上の難問が多く知られている。アルゴリズム上の難問は計算量などによって定義・分類されるが、そのための基礎知識のために『アルゴリズムと計算量』(臨時別冊 数理科学 SGCライブラリ43)谷 聖一 サイエンス社おすすめ度★★★☆☆…

ryamadaのコンピュータ日記の記事へリンク：確率的アルゴリズムと近似アルゴリズム

以前、ＰＣクラスタに手を染めるための記事を書いた。ＲのWikiにＲでの並列処理のページも出てきた。ひとまずの目標は、小規模クラスタを組んで、Ｒの単体マシンのプログラムを並列処理させてみることとする。まずは、ハードの勉強かと。 この関係はryamada…

第24講 分割行列による計算 pxn行列は、縦横に区切りを入れて、p1xn1,p1xn2,p2xn1,p2xn2行列に切り分けられる(ただし、p=p1+p2,n=n1+n2)。切り分けた行列を分割行列と呼び、加減および積が行える 多変量で作る確率密度関数の計算においては、変数のうち、あ…

第22講 固有値と固有ベクトル 第23講 対象行列の固有値と固有ベクトル 固有値・固有ベクトル p次の西方行列についてを満足するスカラー量はの固有値と呼ばれ、最大p個存在する。または固有ベクトルと呼ばれる。がの解を持つためには、でなくてはならず、これ…

第19講 行列のランク p次元ベクトル空間上のn個のp次元ベクトルがあるとする。このn個のベクトルの１次独立な最大数が、q[であるとすると、tex:q\le q]であり、であり、n個のベクトルは次元qのベクトル空間を張っている。このとき、pxn行列のランクと言う は…

第18講 部分ベクトル空間 p次元ベクトルはp個の互いに１次独立なp次元ベクトルの１次結合で表せる(このベクトルのセットを基底と呼ぶ) 基底の構成ベクトルは互いに直交する 基底の構成ベクトルは長さが１であると便利であるが、その方法としてグラム・シュミ…

第17講 行列の基本変形 基本行列 (i番目の対角成分のみcで、残りは単位行列と同じ) (単位行列の第i列と第j列を入れ替えたもの) (単位行列で(i,j)成分だけをcに置き換えたもの) 基本行列のはたらき を右からかけると第i列がc倍される を左からかけると第i行が…

第16講 いろいろな行列 単位行列 逆行列 について 直交行列 のときは直交であるという ベクトルに直交行列をかけても長さは不変 対称行列 のときは対称であるという 対角行列 対角成分以外が0である正方行列 対称行列の特殊な場合 三角行列 対角成分の左下の…

第14講 ベクトルと行列の加減 第15講 ベクトルと行列の積 データはサンプルと変数の行列で表される ベクトルや行列を使ってプログラミングができるとき(SやR)、大いに力を発揮する。そうでないと、要素単位での処理をすることになり、うまみが小さい ベクト…

なお、この記事は、『統計学のための数学入門30講』シリーズ 科学のことばとしての数学 永田 靖 著 朝倉書店を教科書とし、遺伝統計学を学ぶための基礎を確認するためのものです。全体の目次はこちら

第21講 射影と射影行列 k個のp次元ベクトルが張る部分ベクトル空間があり、その直交補空間がある。今、p次元ベクトル空間上の任意のベクトルは上のベクトルに分解できてと表せる。をへのをへの射影と呼ぶ。またなるをへの射影行列と呼ぶ 射影行列には次の性…

第20講 行列式 正方行列に定義されたスカラー量の１つ。やと表す WikiPediaにあるサラスの方法が実計算レベルで一番早いか･･･ p次正方行列の行列式の特徴 対角行列の行列式は対角成分の積 三角行列の行列式は対角成分の積 が正則ならば が正則ならば 直交行…

ネットワーク流のグラフでのモデル化には、いくつかの要素を付加する必要がある。ソース(湧出点)とシンク(吸収点)と呼ばれる特殊な２点である(ソースとシンクがそれぞれ１つずつの場合もあれば、これらが複数の場合もある)。また、グラフは重み付き有向グラ…

連結な有向グラフで、有向閉路が存在するとき、ノード同士の関係には、相互に到達可能な関係と、片方のノードから到達可能ながらその逆は到達不能であるような関係の２種類が存在する。相互に到達可能なノードの組を強連結成分とすると、連結な有向グラフは…

連結 グラフを連結成分に分けるには、グラフ探索法により、連結・非連結の判定が必要で、網羅探索をする必要がある。工夫の余地は、連結情報の表現方法であろう。例としては以下のようなものが考えられる 単純に連結成分ごとに保管する方法 ノードに値を与え…

『Algorithms in C アルゴリズム 第３巻 グラフ・数理・トピックス』近代科学社 R.セジウィック 著 野下浩平・星守・佐藤創・田口東 共訳 おすすめ度★★★★☆、ただし、新版が出ている模様。 ３分冊の１冊 アルゴリズムC〈第3巻〉グラフ・数理・トピックス 作者…

グラフ中の有向閉路とは、エッジの向きに進んだときに、ぐるぐると回れてしまうような閉路を言う。今、有向グラフのうち、有向閉路を持たないグラフを無閉路有向グラフと呼ぶ。無閉路有向グラフにおいては、エッジの向きを無視すれば閉路は存在するものの、…

深さ優先探索は再帰表現がしやすく、幅優先探索は非再帰表現がしやすいと言う。その理由は次のようになる。 深さ優先探索では、探索過程において、多段階の保留状態を生み、その多段階の保留状態は、『当該段階』『当該段階より１つ上の段階』『当該段階より…

前項の推移閉包は、グラフにおける到達可能性(到達可能か否か)の情報を全ノードペアについて求める方法である『ウォーシャルの方法』についてであった。これは、到達可能性を全ノードペアについて行うことに他ならないが、同様に、任意の２ノード間の最短径…

(有向)グラフにおいて、あるノードからあるノードへ到達可能であるときに、その２ノード間にエッジを加えて作成したグラフを、そのグラフの推移閉包と言う。一度この推移閉包を作成すれば、(有向)グラフにおける径路の有無の情報はすぐに得られる。密なグラ…

グラフアルゴリズムではノードとノードと隣接関係が対象となっているのに対し、幾何学的アルゴリズムでは、物理的な位置とその距離が対象となっている。物理的な位置の情報を利用すると、探索対象を大幅に減らしうる。ＡＲＧにおいては(おそらく)、ランダム…

重みつきグラフにおいて、すべてのノードを結ぶエッジの集合で、辺の重みの総和が最小のもの 疎グラフの場合 大きくわけてアプローチは２つ １つのノードからスタートし、そのノードを含む木を成長させ、すべてのノードが結ばれるまで続ける(順位優先探索、…

深さ優先探索と同様に、ノードは『訪問済み』『訪問中』『未訪問』の３群に振り分けられる。『訪問中』のノードの中から１つを取り出して、『訪問済み』とする手続きを繰り返す点も深さ優先探索と同じである。違いは次の通り。深さ優先探索では、もっとも新…