講師：永田銕男（アルファシステムズ）

SOR法（Succesive Over-Relaxation Method） ω：加速係数（ω=1：ガウズ・ザイデル法）：一般に1〜2の値 ガウス・ザイデル法の数倍の速さで収束する SORの意味 ガウス・ザイデル法では下のようであった。 上の方の式より、 上式の左辺はx1のk+1回目とk回目の…

ベイズ統計・推定・Error 例）三種類のコインがある。 w1=10% 表の出る確率θ1=0.8 w2=40% 表の出る確率θ2=0.6 w3=50% 表の出る確率θ3=0.3ある1個のコインを取り出してn回投げてx回表が出たとする。 コインがどのコインかを推定する方法は？ ベイズの定理 計…

7.4 最小スパニング木 連結な無向グラフの全ての頂点を含む部分グラフで木であるものをスパニング木という。 行列木定理 連結な無向グラフGのスパニング木の個数はL(G)*1の任意の対角要素に関する余因子の値に等しい。 重み付きグラフの重みを最も小さくする…

連言・選言標準形 以下の議論では限量子を含むものは考えない 連言標準形 (P1 ∨ P2)∧(P3 ∨ P4)∧(P5 ∨ P6)のように、∨で結合した節(clause)を∧で結合した形。 選言標準形 (P1 ∧ P2)∨(P3 ∧ P4)∨(P5 ∧ P6)のように、∧で結合したもの（特に名前はない）を∨で結合…

4.1 通信路のモデル 通信路の統計的性質 定常：時間をずらしても統計的性質が変わらない 無記憶：その時点の入力のみに出力が依存し、他の時点での入力や出力とは無関係 一般に 入力アルファベット＝入力記号の集合：X={a1,a2,...,ar} 出力アルファベット＝…

変換方法 s-z変換に基づく方法（間接設計法） アナログフィルタの伝達関数からディジタルフィルタを求める ディジタルフィルタとして設計する方法（直接設計法） 標準z変換法（インパルス不変法） 伝達関数をラプラス逆変換して、インパルス応答を求める イ…

LU分解 http://www.fuka.info.waseda.ac.jp/~kozo/suuchi/simple_equation/simple_equation_3.html 計算量 LU分解 O(n^3) 代入 (n^2) ヤコビ法 http://www2.ee.knct.ac.jp/el/E4/H15-E406/hanpuku.html 計算法は略。単純 収束性の必要十分条件 において、Bの…

3囚人の問題 Ω(A)=Aが釈放されること X(B)=看守が「Bは処刑される」と答えること P(Ω(A))＝P(Ω(B))＝P(Ω(C))＝1/3(1) Aが釈放される→BとCが処刑される。 (2) Bが釈放される→AとCが処刑される。 (3) Cが釈放される→AとBが処刑される。P(X(B)|Ω(A))=1/2,P(X(B)…

Gの完全性の証明（続き） 復習 公平な導出木 ΦとΨ（各辺の無限経路のある位置以上の位置に存在し続ける論理式の和集合） 任意のシークェントに対して公平な導出木が存在する。 →展開レベルの小さいものから展開する。 補題6.7.6 ※このとき、有限な公理で終了…

算術符号 情報源シンボル系列⇒系列の累積確率[0,1)の2進表現（符号も2元） 例） P(0)=0.7 P(1)=0.3 累積確率二進表現符号 P(000)=0.343 0 .00000...00 P(001)=0.147 0.343 .01010...010 P(010)=0.147 0.49 .01111...011 P(011)=0.063 0.637 .10100...1010 P(…

フィルタとは、ある帯域の信号は通過し、それ以外の帯域の信号は遮断する装置 低域通過フィルタ 高域通過フィルタ 帯域通過フィルタ 帯域阻止フィルタ（ノッチフィルタを含む） FIRフィルタ FIRフィルタは直線位相特性を実現できる。 ・・・理解不能 いや、…

連立一次方程式 計算方法 直接法（消去法）変数をひとつずつ消す ガウスの消去法 LU分解法 反復法：繰り返し演算により解を収束させる。 ヤコビ法 ガウス・ザイデル法 SOR法

先週の ・基底ベクトルの正規直交性 より後ろあたりから。 両辺転置すると（Σは対象行列なので） 正規直交性があるので これより (…でなんだったんだっけ？) パラメトリックな学習とノンパラメトリックな学習 （教科書範囲外） ベイズ統計とか（テストに出す…

グラフの表現 隣接行列 接続リスト 隣接リスト n+1頂点の根付き木とn頂点の2分木の頂点の集合は1対1に対応する。 ダイクストラのアルゴリズム 最短路木を作ってやれば、最短路を求めることができる 作り方：Uからuを取り出したときに、その親との関係を保持…

Gの完全性 エルブラン解釈 一階言語の部分集合Sについての構造みたいな感じのMについて Mがエルブラン構造で、V(x)=x for all x ∈ Var_s なら、I=(M,V)はエルブラン解釈エルブラン構造 |M|＝Hs=T(Fun_s,Ver_s) M［[f]］(t1,...,tn)=f(t1,...,tn) M［[P]］は…

復習 定理3.2,3.2は重要 シャノンの符号化 ファノの符号化法 情報源のシンボルをなるべく等確率になるように二つに分けることを繰り返す。（言いたいことはわかるけどなるべく等確率になるようにの判断が難しいな…） ハフマン符号 省略させてください ハフマ…

DFTの定義式 より（中略） バタフライ演算 ビットリバーサル 演算回数の比較 複素乗算回数 DFT:N^2 FFT:{N(logN - 1)}/2 複素加算回数 DFT:N(N-1) FFT:NlogN 5.4,5.5は飛ばす FFTの応用 スペクトル推定（何がやりたいのだろう） 循環たたみ込み 循環たたみ込…

特徴空間の変換 正規化 次元の削減 より良い特徴量を選択 線形変換により次元を削減 識別に適した空間を作る⇒Fisherの方法 KL展開 KL展開は識別に適した空間を作っているわけではない。 KL展開により、元の空間をできるだけ保存したより次元の低い空間を作る…

ωn = 1の原始n乗根 n乗して初めて1になる数。 n=2:-1 n=3:(-1±√(3)i)/2 n=4:±i n=5:5個 離散フーリエ変換(Discrete Fourier Transform) 入力x=(x0,x1,x2,…,xn-1) 出力y=Ax Aはn次正方行列。 単純な計算を行うとO(n^2)となる。 たたみこみ(convolution) 例：…

6.4 その他のシークェント計算 カット規則 等号に関する公理シークェント 等式論理という分野がある。 その他の規則 弱化規則 縮約規則 シークェント計算の健全性 （書けなかった） シークェント計算の完全性 =Γ⇒Δならば├Γ⇒Δ 対偶を証明する。 （全部やる…の…

スライドは第6回・17枚目から 4.4 離散時間システムの周波数特性 4.4.1 システムの正弦波応答 4.4.2 周波数特性 周波数特性はωT＝Ωとすれば によって定義される。振幅特性と位相特性： 群遅延特性： 幾何学的表現 振幅特性は、Ω（単位円上の点）から各零点ま…

講師：若林一敏（NEC）すごいひとだった。

台形公式(続き) 台形公式の誤差 F(x):2点に対してラグランジュ補間の1次多項式近似をしている。 補間の誤差公式 より 誤差→ 台形公式の計算順序 終了条件：Nを増やす→解が収束→終了 （Nを先に決めないと計算できないようなアルゴリズムでは良いアルゴリズム…