生命情報学

Size: px
Start display at page:

Download "生命情報学"

Transcription

1 生命情報学 34 進化系統樹推定 阿久津達也 京都大学化学研究所 バイオインフォマティクスセンター

2 進化系統樹

3 進化系統樹 種間 もしくは遺伝子間 の進化の関係を表す木 以前は形態的特徴をもとに構成 現在は配列情報をもとに構成

4 有根系統樹と無根系統樹 有根系統樹 : 根 共通の祖先に対応 がある系統樹 無根系統樹 : 根のない系統樹 いずれも葉にのみラベル 種に対応 がつく 有根系統樹 無根系統樹 系統樹を扱う際は 頂点でなく節点という用語を使う

5 進化系統樹の個数

6 系統樹の同型性 同型な系統樹 : 本質的に同じつながり方 グラフとして同型 をした系統樹 a と b: 同型 a と c: 非同型 d と e: 同型 d と f: 非同型

7 系統樹の個数 葉の個数と節点の個数の関係 葉の個数 = n 有根系統樹 : n- 個の節点 n- 本の枝無根系統樹 : n- 個の節点 n-3 本の枝 無根系統樹と有根系統樹の関係 根は無根系統樹の任意の枝に設定可能 有根系統樹の個数 =n-3 無根系統樹の個数枝が n-3 本の無根系統樹に 本の枝を追加 n-3 種類の異なる無根系統樹 # 葉 # 枝 無根系統樹 # 無根系統樹 # 有根系統樹 n n-3 n-5!! n-3!!

8 系統樹の個数 例 根は無根系統樹の任意の枝に設定可能 有根系統樹の個数 =n-3 無根系統樹の個数 枝が n-3 本の無根系統樹に 本の枝を追加 n-3 種類の異なる無根系統樹

9 UPGMA 法

10 UPGMA 法 Unweighed pai goup mehod uing aihmeic aveage 距離行列法の一つ 距離行列法 : 葉のペアの距離データから系統樹を構成 アルゴリズム 各配列のみからなるクラスタを作成クラスタが 個になるまで以下を繰り返す クラスタ間距離が最小のクラスタどうしを併合 新しくできたクラスタと他のクラスタ間の距離を計算 クラスタ間距離 D kl C k 距離の性質 D kl D il C C C i i l D C ic jl j d j k C l C j ij

11 UPGMA 法の例 C C 6 8 C C 4 7 C C 5 3 {45} {3} C 7 C 9 C C C 6 C {} 8 {345}

12 UPGMA 法の正当性 分子時計 = 進化速度一定性の仮定 枝長 = 分子時計により刻まれた時間 分子時計仮説が成立 任意の葉までの枝長の和が等しい が任意節点について成立 UPGMA 法は系統樹を正しく再構成以下の例で a は仮説を満たさないが b は満たす

13 近隣結合法

14 近隣結合法 UPGMA 法では以下の例 a で と 3 が最初に選ばれたため 正しい系統樹を再構成できなかった 最初に 3 と 4 もしくは と が選ばれれば良い つまり 兄弟関係 近隣関係 にある葉が選ばれれば良い 近隣結合法では 距離が加法性を満たすという仮定のもとで 常に近隣関係にある葉を選ぶ

15 近隣結合法 近隣結合法 距離が加法性を満たせば系統樹を正しく再構成ただし 計算されるのは無根系統樹 加法性 : 節点間の距離 = 節点間を結ぶパスの枝長の和

16 近隣結合法 3 加法性 : 節点間の距離 = 節点間を結ぶパスの枝長の和 i と j の親を k とすると 葉 m に対し以下が成立 d km d im d jm d ij

17 近隣結合法 : アルゴリズム M を葉集合とし L=M とする L > の間 以下を繰り返す L の中から D ij が最小となるペア ij を選ぶ 新しい節点 k を作り L 中のすべての m について d km d im とする k を M に追加し k と i j を枝で結び 枝長を d ik ij i j を L から削除し k を L に追加する i j 間に枝をはり その長さを d ij とする i d jm j d d ij d jk d ij d ik とする ただし Dij dij i j i L kl d ik

18 アウトグループ 近隣結合法 : 無根系統樹しか計算されない 無根系統樹における根の決定法 最も長い葉の間の中点を根とする 対象とする種と離れていることが明らかな種 アウトグループ を追加して系統樹を作成し アウトグループに接続する節点を根とする

19 最節約法

20 最節約法 : 問題設定 最小コストの置換で各配列を生成する系統樹を計算 種類の探索が必要 系統樹の形状 トポロジー 難しい 内部節点への配列の割り当て 動的計画法で計算可能

21 最節約法 : アルゴリズム Ska : 節点 k に塩基 a を割り当てた時のコスト Sab : a を b に置換するためのコスト 動的計画法により葉から根へという順で Ska を計算 配列割り当ては各位置ごとに独立に計算可能 k が内部節点の場合 ij は k の子節点 S k a min S b S a b min S b S a b b i b j k が葉の場合 S k a 0 if a k [] ohewie

22 最節約法 : 実行例 S k a min S b S a b min S b S a b b i b j

23 進化の確率モデル

24 進化の確率モデル 長さ の枝をたどることにより塩基 a が塩基 b に置換される確率 Pb a : Py x : 長さ の枝をたどることにより配列 x が配列 y に置換される確率 置換行列 置換確率行列 P y x P yu xu u S 乗法性 PA A PA C PA G PA T PC A PC C PC G PC T S S S PG A PG C PG G PG T PT A PT C PT G PT T

25 Juke-Cano 行列 置換速度行列を R とし を仮定 S の乗法性より よって ACGT が対等であるとして 対称性より よって R I S R R S S R I S S S S S S R S d ds S 3 3 d d d d

26 Juke-Cano 行列 をに代入して これを解いてこの S が Juke-Cano 行列は十分時間が経つと ACGT の割合いが等しくなることを意味する R R S d ds S 3 3 d d d d e e if 4

27 Juke-Cano 行列の応用例 TATAT=x が 時間後に TTAAA=y に置換する確率は PT A PA T 4 e 4 より PT T PA A 4 3e 4 P y x 4 3e e

28 系統樹の尤度 確率 配列 n に対し 尤度最大の系統樹のトポロジー T と 枝長 i を計算 ただし pi は i の親節点 この計算は難しく 様々な手法が提案されている最尤法による系統樹推定 n i i i p i n n P P T P n n

29 塩基あたりの尤度 配列全体の尤度尤度計算の例 a u u a u u a x P a x P q T x x P N i u u T x x P T x x P

30 CG のみからなる配列 n 個は同じで n 個は変化 この例では n=8 n=3 尤度計算の例 CGGGCCGGCCG CCGGCCGCGCG e CG 3e 3 CC T A G C T P q q q q T P e 3e n n n n T x x P よって 系統樹全体の尤度は 尤度は + が一定なら変わらないことに注意 根の位置の任意性

31 ブートストラップ法 系統樹の信頼性 推定された系統樹の信頼性は不明 信頼性評価の必要性 必ずしも系統樹全体でなくても 大きな分岐などの特定の特徴の信頼性を評価できれば良い ブートストラップ法による評価 ある確率モデルのもとで ブートストラップ法による頻度 特徴の事後確率 系統樹に対するブートストラップ法. もとのアラインメントから各カラムを重複を許してランダムに抽出. ステップ で作ったアラインメントから系統樹を推定 3. ステップ を数多く 例えば 000 回 繰り返し 各特徴の頻度分布を計算し 頻度により信頼性を評価

32 最大合致部分系統樹

33 最大合致部分系統樹 maximum ageemen ubee 系統樹推定には様々な方法 複数の系統樹を統合 一部の種だけを考えることにより 複数の系統樹から共通の系統樹を得る 種の数の最大化 入力 : 同じラベル集合 { n} を持つ有根系統樹 T T T N 出力 : T i B がすべて同型となる要素数最大の B T i B: B に含まれない葉とそれに接続する枝を削除し さらに子が一つになった内部節点を繰り返し縮約して得る B={3568}

34 最小共通祖先 LCA: Lea Common Anceo lca i ab: ab をラベルにもつ葉の共通の祖先で最も根から遠いもの 半順序 : 節点 u が節点 v の子孫 u v u v LCA の例 : lca i 3 : lca i 47 : lca i 57

35 動的計画法アルゴリズム } lca lca { } lca lca { b a b x T b x b a R b a x a T x a b a L i i i i i i } { max } { max b c W c a W b a W a a W b a R b c b a L c a a b として Lab Rab を次のように定義すべての a b に対して Wab を動的計画法で計算ただし Lab Rab のいずれかが空の時は Wab=- } max{ b a W B ab すると B はトレースバックで計算可能

36 動的計画法の例 B={3568} {88} 58 {55 56} 58 {33} 3 {} 3 W W W W W W W W W R L R L 下図の例に対する計算例 一部分

37 時間計算量の解析 定理 : 最大合致部分系統樹問題は On 3 N 時間で計算可能 証明 : 正当性の証明は省略 On 個の ab と N 個の系統樹について LCA を計算するのにかかる時間の合計は On N Lab および Rab 個あたりの要素数は On であり あらかじめ lcaiab 間の半順序関係の表を作っておけば 全体で On 3 N 時間 Wab は全体で On 3 時間で計算可能 子頂点の数が制約されない一般の場合は NP 困難

38 まとめ 系統樹の個数 無根系統樹で n-5!! 有根系統樹で n-3!! 距離行列法 UPGMA 法 : 最小距離のクラスタを結合近隣結合法 : 近隣の節点を結合 最節約法 : 置換コストが最小の系統樹を計算 進化の確率モデル : Juke-Cano 行列を用いて配列間の置換確率を計算最尤法 : 確率が最大となる系統樹を推定ブートストラップ法 : 系統樹の特徴の信頼性評価 最大合致部分系統樹 : 複数の系統樹の比較

生命情報学

生命情報学 生命情報学 5 隠れマルコフモデル 阿久津達也 京都大学化学研究所 バイオインフォマティクスセンター 内容 配列モチーフ 最尤推定 ベイズ推定 M 推定 隠れマルコフモデル HMM Verアルゴリズム EMアルゴリズム Baum-Welchアルゴリズム 前向きアルゴリズム 後向きアルゴリズム プロファイル HMM 配列モチーフ モチーフ発見 配列モチーフ : 同じ機能を持つ遺伝子配列などに見られる共通の文字列パターン

More information

A Constructive Approach to Gene Expression Dynamics

A Constructive Approach to Gene Expression Dynamics 配列アラインメント (I): 大域アラインメント http://www.lab.tohou.ac.jp/sci/is/nacher/eaching/bioinformatics/ week.pdf 08/4/0 08/4/0 基本的な考え方 バイオインフォマティクスにはさまざまなアルゴリズムがありますが その多くにおいて基本的な考え方は 配列が類似していれば 機能も類似している というものである 例えば

More information

生命情報学

生命情報学 生命情報学 (2) 配列解析基礎 阿久津達也 京都大学化学研究所 バイオインフォマティクスセンター 配列アラインメントとは? 配列検索 バイオインフォマティクスにおける基本原理 配列が似ていれば機能も似ている ただし 例外はある 配列検索の利用法 実験を行い機能未知の配列が見つかったデータベース中で類似の配列を検索機能既知の類似の配列が見つかれば その配列と似た機能を持つと推定 機能未知の配列 VLPIKSKLP...

More information

分子進化モデルと最尤系統推定法 東北大 院 生命科学田邉晶史

分子進化モデルと最尤系統推定法 東北大 院 生命科学田邉晶史 分子進化モデルと最尤系統推定法 東北大 院 生命科学田邉晶史 まずはじめに, 最尤系統推定とは 多重モデル選択 である. 最尤系統推定の手順 1. 樹形を固定しての 2. 分子進化モデルの選択 1. 分子進化モデルを固定しての 2. 系統モデル ( 樹形 ) の選択 = 多重モデル選択 分子進化モデル超入門 とりあえず塩基置換モデルで 塩基置換モデルの 3 大要素 塩基置換確率行列 (nucleotide

More information

バイオインフォマティクスⅠ

バイオインフォマティクスⅠ バイオインフォマティクス ( 第 6 回 ) 慶應義塾大学生命情報学科 榊原康文 入力ベクトル 階層クラスタリングの解 : [1] [2] [3] : 0 0 0 B: 1 1 1 C: 2 1 2 D: 3 3 3 D 系統樹 距離行列 : B: C: B: 1.732 C: 3.000 1.414 D: 5.196 3.464 2.449 B C データベース検索 1 データベースの高速検索 問い合わせ配列に類似した配列をデータベースより見出す作業

More information

<4D F736F F D208C51985F82CD82B682DF82CC88EA95E A>

<4D F736F F D208C51985F82CD82B682DF82CC88EA95E A> 群論はじめの一歩 (6) 6. 指数 2の定理と2 面体群 命題 H を群 G の部分群とする そして 左剰余類全体 G/ H 右剰 余類全体 \ H G ともに指数 G: H 2 と仮定する このとき H は群 G の正規部分群である すなわち H 注意 ) 集合 A と B があるとき A から B を引いた差集合は A \ B と書かれるが ここで書いた H \ Gは差集合ではなく右剰余類の集合の意味である

More information

Taro-2分探索木Ⅰ(公開版).jtd

Taro-2分探索木Ⅰ(公開版).jtd 2 分探索木 Ⅰ 0. 目次 1. 2 分探索木とは 2. 2 分探索木の作成 3. 2 分探索木の走査 3. 1 前走査 3. 2 中走査 3. 3 問題 問題 1 問題 2 後走査 4. 2 分探索木の表示 - 1 - 1. 2 分探索木とは 木はいくつかの節点と節点同士を結ぶ辺から構成される 2 つの節点 u,v が直接辺で結ばれているとき 一方を親節点 他方を子節点という ある節点の親節点は高々

More information

オートマトンと言語

オートマトンと言語 オートマトンと言語 4 回目 5 月 2 日 ( 水 ) 3 章 ( グラフ ) の続き 授業資料 http://ir.cs.yamanashi.ac.jp/~ysuzuki/public/automaton/ 授業の予定 ( 中間試験まで ) 回数月日 内容 4 月 日オートマトンとは, オリエンテーション 2 4 月 8 日 2 章 ( 数式の記法, スタック,BNF) 3 4 月 25 日 2

More information

<4D F736F F F696E74202D2091E6824F82538FCD8CEB82E88C9F8F6F814592F990B382CC8CB4979D82BB82CC82505F D E95848D8682CC90B69

<4D F736F F F696E74202D2091E6824F82538FCD8CEB82E88C9F8F6F814592F990B382CC8CB4979D82BB82CC82505F D E95848D8682CC90B69 第 章 誤り検出 訂正の原理 その ブロック符号とその復号 安達文幸 目次 誤り訂正符号化を用いる伝送系誤り検出符号誤り検出 訂正符号 7, ハミング符号, ハミング符号生成行列, パリティ検査行列の一般形符号の生成行列符号の生成行列とパリティ検査行列の関係符号の訂正能力符号多項式 安達 : コミュニケーション符号理論 安達 : コミュニケーション符号理論 誤り訂正符号化を用いる伝送系 伝送システム

More information

Microsoft PowerPoint - DA2_2019.pptx

Microsoft PowerPoint - DA2_2019.pptx Johnon のアルゴリズム データ構造とアルゴリズム IⅠ 第 回最大フロー 疎なグラフ, 例えば E O( V lg V ) が仮定できる場合に向いている 隣接リスト表現を仮定する. 実行時間は O( V lg V + V E ). 上記の仮定の下で,Floyd-Warhall アルゴリズムよりも漸近的に高速 Johnon のアルゴリズム : アイデア (I) 辺重みが全部非負なら,Dikra

More information

配付資料 自習用テキスト 解析サンプル配布ページ 2

配付資料 自習用テキスト 解析サンプル配布ページ   2 分子系統樹推定法 理論と応用 2009年11月6日 筑波大 院 生命環境 田辺晶史 配付資料 自習用テキスト 解析サンプル配布ページ http://www.fifthdimension.jp/documents/molphytextbook/ 2 参考書籍 分子系統学 3 参考書籍 統計的モデル選択とベイジアンMCMC 4 祖先的な形質 問題 OTU左の の色は表現型形質の状態を表している 赤と青

More information

Taro-2分探索木Ⅱ(公開版).jtd

Taro-2分探索木Ⅱ(公開版).jtd 2 分探索木 Ⅱ 0. 目次 5. 2 分探索木の操作 5. 1 要素の探索 5. 2 直前の要素の探索 5. 3 直後の要素の探索 5. 4 要素の削除 5. 5 問題 問題 1-1 - 5. 2 分探索木の操作 5. 1 要素の探索 要素 44 の探索 (1) 要素 と 44 を比較して 左部分木をたどる (2) 要素 33 と 44 を比較して 右部分木をたどる (3) 要素 44 を見つけた

More information

アルゴリズム入門

アルゴリズム入門 アルゴリズム入門 第 11 回 ~ パターン認識 (1)~ 情報理工学系研究科 創造情報学専攻 中山英樹 1 今日の内容 パターン認識問題の 1 つ : アラインメント アルゴリズム 再帰 動的計画法 2 パターン認識 音や画像の中に隠れたパターンを認識する 音素 音節 単語 文 基本図形 文字 指紋 物体 人物 顔 パターン は唯一のデータではなく 似通ったデータの集まりを表している 多様性 ノイズ

More information

Microsoft PowerPoint - DA2_2017.pptx

Microsoft PowerPoint - DA2_2017.pptx // データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (II)/ 全点対最短路 トポロジカル ソート順による緩和 トポロジカル ソート順に緩和 閉路のない有向グラフ限定 閉路がないならトポロジカル ソート順に緩和するのがベルマン フォードより速い Θ(V + E) 方針 グラフをトポロジカル ソートして頂点に線形順序を与える ソート順に頂点を選び, その頂点の出辺を緩和する 各頂点は一回だけ選択される

More information

Microsoft PowerPoint - mp13-07.pptx

Microsoft PowerPoint - mp13-07.pptx 数理計画法 ( 数理最適化 ) 第 7 回 ネットワーク最適化 最大流問題と増加路アルゴリズム 担当 : 塩浦昭義 ( 情報科学研究科准教授 ) hiour@di.i.ohoku.c.jp ネットワーク最適化問題 ( 無向, 有向 ) グラフ 頂点 (verex, 接点, 点 ) が枝 (edge, 辺, 線 ) で結ばれたもの ネットワーク 頂点や枝に数値データ ( 距離, コストなど ) が付加されたもの

More information

Microsoft PowerPoint - algo ppt [互換モード]

Microsoft PowerPoint - algo ppt [互換モード] 平衡木 アルゴリズム概論 - 探索 (2)- 安本慶一 yasumoto[at]is.naist.jp 二分探索木 高さがデータを挿入 削除する順番による 挿入 削除は平均 O(log n) だが, 最悪 O(n) 木の高さをできるだけ低く保ちたい 平衡木 (balanced tree) データを更新する際に形を変形して高さが log 2 n 程度に収まるようにした木 木の変形に要する時間を log

More information

混沌系工学特論 #5

混沌系工学特論 #5 混沌系工学特論 #5 情報科学研究科井上純一 URL : htt://chaosweb.comlex.eng.hokudai.ac.j/~j_inoue/ Mirror : htt://www5.u.so-net.ne.j/j_inoue/index.html 平成 17 年 11 月 14 日第 5 回講義 デジタルデータの転送と復元再考 P ({ σ} ) = ex σ ( σσ ) < ij>

More information

Microsoft PowerPoint - ad11-09.pptx

Microsoft PowerPoint - ad11-09.pptx 無向グラフと有向グラフ 無向グラフ G=(V, E) 頂点集合 V 頂点の対を表す枝の集合 E e=(u,v) 頂点 u, v は枝 e の端点 f c 0 a 1 e b d 有向グラフ G=(V, E) 頂点集合 V 頂点の順序対を表す枝の集合 E e=(u,v) 頂点 uは枝 eの始点頂点 vは枝 eの終点 f c 0 a 1 e b d グラフのデータ構造 グラフ G=(V, E) を表現するデータ構造

More information

Microsoft PowerPoint - mp11-06.pptx

Microsoft PowerPoint - mp11-06.pptx 数理計画法第 6 回 塩浦昭義情報科学研究科准教授 shioura@dais.is.tohoku.ac.jp http://www.dais.is.tohoku.ac.jp/~shioura/teaching 第 5 章組合せ計画 5.2 分枝限定法 組合せ計画問題 組合せ計画問題とは : 有限個の もの の組合せの中から, 目的関数を最小または最大にする組合せを見つける問題 例 1: 整数計画問題全般

More information

aaa

aaa Information an Coing Theory, 07 by Toyoaki Nishia 情報源符号化とその限界 Copyright 07 Toyoaki Nishia All Rights Reserve. 本科目の構成 情報源 information source 情報源符号器 source encoer 通信路符号器 channel encoer 通信路 channel 通信路復号器

More information

nlp1-04a.key

nlp1-04a.key 自然言語処理論 I. 文法 ( 構文解析 ) その 構文解析 sytctic lysis, prsig 文の構文的な構造を決定すること句構造文法が使われることが多い文法による構文木は一般に複数ある 構文木の違い = 解釈の違い 構文解析の目的 句構造文法の規則を使って, 文を生成できる構文木を全て見つけだすこと 文法が入力文を生成できるかどうかを調べるだけではない pro I 構文解析とは 構文木の違い

More information

PowerPoint Presentation

PowerPoint Presentation 算法数理工学 第 2 回 定兼邦彦 クイックソート n 個の数に対して最悪実行時間 (n 2 ) のソーティングアルゴリズム 平均実行時間は (n log n) 記法に隠された定数も小さい in-place ( 一時的な配列が必要ない ) 2 クイックソートの記述 分割統治法に基づく 部分配列 A[p..r] のソーティング. 部分問題への分割 : 配列 A[p..r] を 2 つの部分配列 A[p..q]

More information

PowerPoint Presentation

PowerPoint Presentation 最適化手法 第 回 工学部計数工学科 定兼邦彦 http://researchmap.jp/sada/resources/ 前回の補足 グラフのある点の隣接点をリストで表現すると説明したが, 単に隣接点の集合を持っていると思ってよい. 互いに素な集合のデータ構造でも, 単なる集合と思ってよい. 8 3 4 3 3 4 3 4 E v 重み 3 8 3 4 4 3 {{,},{3,8}} {{3,},{4,}}

More information

™…{,

™…{, 16:30-17:40 1-36 1-37 1-38 1-39 1-40 1-41 1-42 33 10:00-11:10 1-43 1-44 1-45 1-46 1-47 1-48 1-49 12:00-12:50 LS4 34 16:30-17:40 1-50 1-51 1-52 1-53 1-54 1-55 1-56 35 16:30-17:40 1-57 1-58 1-59 1-60 1-61

More information

バイオインフォマティクス第四回

バイオインフォマティクス第四回 IT BIO バイオインフォマティクス第 4 回 藤博幸 本日の講義 (1) 分子系統解析の概要 (2) 犯罪捜査への応用 本日の講義 (1) 分子系統解析の概要 (2) 犯罪捜査への応用 分子系統解析の手続き (1) 相同配列の収集系統分類の場合は オーソロガスな配列を収集 (2) 相同配列のマルチプルアラインメントの作成 (3) アラインメントから分子系統樹を構築 分子系統解析の手続き (1)

More information

Microsoft PowerPoint - 13approx.pptx

Microsoft PowerPoint - 13approx.pptx I482F 実践的アルゴリズム特論 13,14 回目 : 近似アルゴリズム 上原隆平 (uehara@jaist.ac.jp) ソートの下界の話 比較に基づく任意のソートアルゴリズムはΩ(n log n) 時間の計算時間が必要である 証明 ( 概略 ) k 回の比較で区別できる場合の数は高々 2 k 種類しかない n 個の要素の異なる並べ方は n! 通りある したがって少なくとも k n 2 n!

More information

PowerPoint Presentation

PowerPoint Presentation パターン認識入門 パターン認識 音や画像に中に隠れたパターンを認識する 音素 音節 単語 文 基本図形 文字 指紋 物体 人物 顔 パターン は唯一のデータではなく 似通ったデータの集まりを表している 多様性 ノイズ 等しい から 似ている へ ~ だ から ~ らしい へ 等しい から 似ている へ 完全に等しいかどうかではなく 似ているか どうかを判定する パターンを代表する模範的データとどのくらい似ているか

More information

Microsoft PowerPoint - 7.pptx

Microsoft PowerPoint - 7.pptx 通信路 (7 章 ) 通信路のモデル 情報 送信者 通信路 受信者 A a,, a b,, b B m = P( b ),, P( b m ) 外乱 ( 雑音 ) n = P( a,, P( a ) n ) 送信情報源 ( 送信アルファベットと生成確率 ) 受信情報源 ( 受信アルファベッと受信確率 ) でもよい 生成確率 ) 受信確率 ) m n 2 イメージ 外乱 ( 雑音 ) により記号 a

More information

分子系統解析における様々な問題について 田辺晶史

分子系統解析における様々な問題について 田辺晶史 分子系統解析における様々な問題について 田辺晶史 そもそもどこの配列を使うべき? そもそもどこの配列を使うべき? 置換が早すぎず遅すぎない (= 多すぎず少なすぎない ) そもそもどこの配列を使うべき? 置換が早すぎず遅すぎない (= 多すぎず少なすぎない ) 連続長は長い方が良い そもそもどこの配列を使うべき? 置換が早すぎず遅すぎない (= 多すぎず少なすぎない ) 連続長は長い方が良い 遺伝子重複が起きていない

More information

4 段階推定法とは 予測に使うモデルの紹介 4 段階推定法の課題 2

4 段階推定法とは 予測に使うモデルの紹介 4 段階推定法の課題 2 4 段階推定法 羽藤研 4 芝原貴史 1 4 段階推定法とは 予測に使うモデルの紹介 4 段階推定法の課題 2 4 段階推定法とは 交通需要予測の実用的な予測手法 1950 年代のアメリカで開発 シカゴで高速道路の需要予測に利用 日本では 1967 年の広島都市圏での適用が初 その後 1968 年の東京都市圏など 人口 30 万人以上の 56 都市圏に適用 3 ゾーニング ゾーニングとネットワークゾーン間のトリップはゾーン内の中心点

More information

<4D F736F F D E4F8E9F82C982A882AF82E98D7397F1>

<4D F736F F D E4F8E9F82C982A882AF82E98D7397F1> 3 三次における行列 要旨高校では ほとんど 2 2 の正方行列しか扱ってなく 三次の正方行列について考えてみたかったため 数 C で学んだ定理を三次の正方行列に応用して 自分たちで仮説を立てて求めていったら 空間における回転移動を表す行列 三次のケーリー ハミルトンの定理 三次における逆行列を求めたり 仮説をたてることができた. 目的 数 C で学んだ定理を三次の正方行列に応用する 2. 概要目的の到達点として

More information

SAP11_03

SAP11_03 第 3 回 音声音響信号処理 ( 線形予測分析と自己回帰モデル ) 亀岡弘和 東京大学大学院情報理工学系研究科日本電信電話株式会社 NTT コミュニケーション科学基礎研究所 講義内容 ( キーワード ) 信号処理 符号化 標準化の実用システム例の紹介情報通信の基本 ( 誤り検出 訂正符号 変調 IP) 符号化技術の基本 ( 量子化 予測 変換 圧縮 ) 音声分析 合成 認識 強調 音楽信号処理統計的信号処理の基礎

More information

PowerPoint Presentation

PowerPoint Presentation 算法数理工学 第 回 定兼邦彦 クイックソートの 確率的アルゴリズム クイックソートの平均的な場合の実行時間を解析する場合, 入力の頻度を仮定する必要がある. 通常は, すべての順列が等確率で現れると仮定 しかし実際にはこの仮定は必ずしも期待できない この仮定が成り立たなくてもうまく動作するクイックソートの確率的アルゴリズムを示す 確率的 radomized) アルゴリズム 動作が入力だけでなく乱数発生器

More information

講義「○○○○」

講義「○○○○」 講義 信頼度の推定と立証 内容. 点推定と区間推定. 指数分布の点推定 区間推定 3. 指数分布 正規分布の信頼度推定 担当 : 倉敷哲生 ( ビジネスエンジニアリング専攻 ) 統計的推測 標本から得られる情報を基に 母集団に関する結論の導出が目的 測定値 x x x 3 : x 母集団 (populaio) 母集団の特性値 統計的推測 標本 (sample) 標本の特性値 分布のパラメータ ( 母数

More information

Microsoft PowerPoint - kougi10.ppt

Microsoft PowerPoint - kougi10.ppt C プログラミング演習 第 10 回二分探索木 1 例題 1. リストの併合 2 つのリストを併合するプログラムを動かしてみる head1 tail1 head2 tail2 NULL NULL head1 tail1 tail1 があると, リストの併合に便利 NULL 2 #include "stdafx.h" #include struct data_list { int data;

More information

memo

memo 数理情報工学特論第一 機械学習とデータマイニング 4 章 : 教師なし学習 3 かしまひさし 鹿島久嗣 ( 数理 6 研 ) kashima@mist.i.~ DEPARTMENT OF MATHEMATICAL INFORMATICS 1 グラフィカルモデルについて学びます グラフィカルモデル グラフィカルラッソ グラフィカルラッソの推定アルゴリズム 2 グラフィカルモデル 3 教師なし学習の主要タスクは

More information

Microsoft PowerPoint - 06.pptx

Microsoft PowerPoint - 06.pptx アルゴリズムとデータ構造第 6 回 : 探索問題に対応するデータ構造 (2) 担当 : 上原隆平 (uehara) 2015/04/22 内容 スタック (stack): 最後に追加されたデータが最初に取り出される 待ち行列 / キュー (queue): 最初に追加されたデータが最初に取り出される ヒープ (heap): 蓄えられたデータのうち小さいものから順に取り出される 配列による実装 連結リストによる実装

More information

Slide 1

Slide 1 MEGA5 と Perl を用いた 分子進化解析の基礎 野澤昌文 2012 年 1 月 16 日基礎生物学研究所 ハンズオンセミナー 1 分子進化研究における一般的手法 相同な配列の比較 塩基配列 配列名塩基配列 A A T G G T A C A C B A T G A T A C A C C A T G G T A C A T アミノ酸配列 配列名 アミノ酸配列 A Met Val His B

More information

データ解析

データ解析 データ解析 ( 前期 ) 最小二乗法 向井厚志 005 年度テキスト 0 データ解析 - 最小二乗法 - 目次 第 回 Σ の計算 第 回ヒストグラム 第 3 回平均と標準偏差 6 第 回誤差の伝播 8 第 5 回正規分布 0 第 6 回最尤性原理 第 7 回正規分布の 分布の幅 第 8 回最小二乗法 6 第 9 回最小二乗法の練習 8 第 0 回最小二乗法の推定誤差 0 第 回推定誤差の計算 第

More information

オートマトン 形式言語及び演習 3. 正規表現 酒井正彦 正規表現とは 正規表現 ( 正則表現, Regular Expression) オートマトン : 言語を定義する機械正規表現 : 言語

オートマトン 形式言語及び演習 3. 正規表現 酒井正彦   正規表現とは 正規表現 ( 正則表現, Regular Expression) オートマトン : 言語を定義する機械正規表現 : 言語 オートマトン 形式言語及び演習 3. 酒井正彦 www.trs.css.i.nagoya-u.ac.jp/~sakai/lecture/automata/ とは ( 正則表現, Regular Expression) オートマトン : 言語を定義する機械 : 言語を記号列で定義 - 記述しやすい ( ユーザフレンドリ ) 例 :01 + 10 - UNIX の grep コマンド - UNIX の

More information

離散数学

離散数学 離散数学 ブール代数 落合秀也 前回の復習 : 命題計算 キーワード 文 複合文 結合子 命題 恒真 矛盾 論理同値 条件文 重条件文 論法 論理含意 記号 P(p,q,r, ),,,,,,, 2 今日のテーマ : ブール代数 ブール代数 ブール代数と束 そして 順序 加法標準形とカルノー図 3 今日のテーマ : ブール代数 ブール代数 ブール代数と束 そして 順序 加法標準形とカルノー図 4 ブール代数の法則

More information

2015年度 信州大・医系数学

2015年度 信州大・医系数学 05 信州大学 ( 医系 ) 前期日程問題 解答解説のページへ 放物線 y = a + b + c ( a > 0) を C とし, 直線 y = -を l とする () 放物線 C が点 (, ) で直線 l と接し, かつ 軸と共有点をもつための a, b, c が満 たす必要十分条件を求めよ () a = 8 のとき, () の条件のもとで, 放物線 C と直線 l および 軸とで囲まれた部

More information

コンピュータ応用・演習 情報処理システム

コンピュータ応用・演習 情報処理システム 2010 年 12 月 15 日 データエンジニアリング 演習 情報処理システム データマイニング ~ データからの自動知識獲得手法 ~ 1. 演習の目的 (1) 多種多様な膨大な量のデータを解析し, 企業の経営活動などに活用することが望まれている. 大規模データベースを有効に活用する, データマイニング技術の研究が脚光を浴びている 1 1. 演習の目的 (2) POS データを用いて顧客の購買パターンを分析する.

More information

umeda_1118web(2).pptx

umeda_1118web(2).pptx 選択的ノード破壊による ネットワーク分断に耐性のある 最適ネットワーク設計 関西学院大学理工学部情報科学科 松井知美 巳波弘佳 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 0 / 20 現実のネットワーク 現実世界のネットワークの分析技術の進展! ネットワークのデータ収集の効率化 高速化! 膨大な量のデータを解析できる コンピュータ能力の向上! インターネット! WWWハイパーリンク構造

More information

オートマトン 形式言語及び演習 1. 有限オートマトンとは 酒井正彦 形式言語 言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110,

オートマトン 形式言語及び演習 1. 有限オートマトンとは 酒井正彦   形式言語 言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110, オートマトン 形式言語及び演習 1 有限オートマトンとは 酒井正彦 wwwtrscssinagoya-uacjp/~sakai/lecture/automata/ 形式言語 言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110, } 形式言語 : 数学モデルに基づいて定義された言語 認識機械 : 文字列が該当言語に属するか? 文字列 機械 受理

More information

スライド 1

スライド 1 Keal H. Sahn A R. Crc: A dual teperature sulated annealng approach for solvng blevel prograng probles Coputers and Checal Engneerng Vol. 23 pp. 11-251998. 第 12 回論文ゼミ 2013/07/12( 金 ) #4 M1 今泉孝章 2 段階計画問題とは

More information

Microsoft PowerPoint - ppt-7.pptx

Microsoft PowerPoint - ppt-7.pptx テーマ 7: 最小包含円 点集合を包含する半径最小の円 最小包含円問題 問題 : 平面上に n 点の集合が与えられたとき, これらの点をすべて内部に含む半径最小の円を効率よく求める方法を示せ. どの点にも接触しない包含円 すべての点を内部に含む包含円を求める 十分に大きな包含円から始め, 点にぶつかるまで徐々に半径を小さくする 1 点にしか接触しない包含円 現在の中心から周上の点に向けて中心を移動する

More information

アルゴリズムとデータ構造

アルゴリズムとデータ構造 講義 アルゴリズムとデータ構造 第 2 回アルゴリズムと計算量 大学院情報科学研究科情報理工学専攻情報知識ネットワーク研究室喜田拓也 講義資料 2018/5/23 今日の内容 アルゴリズムの計算量とは? 漸近的計算量オーダーの計算の方法最悪計算量と平均計算量 ポイント オーダー記法 ビッグオー (O), ビッグオメガ (Ω), ビッグシータ (Θ) 2 お風呂スケジューリング問題 お風呂に入る順番を決めよう!

More information

始めに, 最下位共通先祖を求めるための関数 LcaDFS( int v ) の処理を記述する. この関数は値を返さない再帰的な void 関数で, 点 v を根とする木 T の部分木を深さ優先探索する. 整数の引数 v は, 木 T の点を示す点番号で, 配列 NodeSpace[ ] へのカーソル

始めに, 最下位共通先祖を求めるための関数 LcaDFS( int v ) の処理を記述する. この関数は値を返さない再帰的な void 関数で, 点 v を根とする木 T の部分木を深さ優先探索する. 整数の引数 v は, 木 T の点を示す点番号で, 配列 NodeSpace[ ] へのカーソル 概略設計書 作成者築山修治作成日 2012 年 10 月 1 日 概要 ( どのような入力に対して, どのような出力をするかの概要説明 ) * 木 T および質問点対の集合 P が与えられたとき, 各質問点対 p = (v,w) P の最下位共通先祖 ( すなわち木 T において点 v と w の共通の先祖 a で,a の真の子孫には v と w の共通の先祖が無いような点 ) を見出す関数である.

More information

Microsoft PowerPoint - 09re.ppt [互換モード]

Microsoft PowerPoint - 09re.ppt [互換モード] 3.1. 正則表現 3. 正則表現 : 正則表現 ( または正規表現 ) とは 文字列の集合 (= 言語 ) を有限個の記号列で表現する方法の 1 つ 例 : (01)* 01 を繰り返す文字列 つまり 0(0+1)* 0 の後に 0 か 1 が繰り返す文字列 (01)* = {,01,0101,010101,01010101, } 0(0+1)*={0,00,01,000,001,010,011,0000,

More information

離散数学

離散数学 離散数学 最短経路問題 落合秀也 その前に 前回の話 深さ優先探索アルゴリズム 開始点 から深さ優先探索を行うアルゴリズム S.pu() Wl S not mpty v := S.pop() I F[v] = l Tn, F[v] := tru For no u n A[v] S.pu(u) EnFor EnI EnWl (*) 厳密には初期化処理が必要だが省略している k 時間計算量 :O(n+m)

More information

情報処理Ⅰ

情報処理Ⅰ Java フローチャート -1- フローチャート ( 流れ図 ) プログラムの処理手順 ( アルゴリズム ) を図示したもの 記号の種類は下記のとおり 端子記号 ( 開始 終了 ) 処理記号計算, 代入等 条件の判定 条件 No ループ処理 LOOP start Yes データの入力 出力 print など 定義済み処理処理名 end サンプルグログラム ( 大文字 小文字変換 ) 大文字を入力して下さい

More information

数値計算法

数値計算法 数値計算法 008 4/3 林田清 ( 大阪大学大学院理学研究科 ) 実験データの統計処理その 誤差について 母集団と標本 平均値と標準偏差 誤差伝播 最尤法 平均値につく誤差 誤差 (Error): 真の値からのずれ 測定誤差 物差しが曲がっていた 測定する対象が室温が低いため縮んでいた g の単位までしかデジタル表示されない計りで g 以下 計りの目盛りを読み取る角度によって値が異なる 統計誤差

More information

040402.ユニットテスト

040402.ユニットテスト 2. ユニットテスト ユニットテスト ( 単体テスト ) ユニットテストとはユニットテストはプログラムの最小単位であるモジュールの品質をテストすることであり その目的は結合テスト前にモジュール内のエラーを発見することである テストは機能テストと構造テストの2つの観点から行う モジュールはプログラムを構成する要素であるから 単体では動作しない ドライバとスタブというテスト支援ツールを使用してテストを行う

More information

木村の理論化学小ネタ 体心立方構造 面心立方構造 六方最密構造 剛球の並べ方と最密構造剛球を平面上に の向きに整列させるのに次の 2 つの方法がある 図より,B の方が A より密であることがわかる A B 1

木村の理論化学小ネタ   体心立方構造 面心立方構造 六方最密構造 剛球の並べ方と最密構造剛球を平面上に の向きに整列させるのに次の 2 つの方法がある 図より,B の方が A より密であることがわかる A B 1 体心立方構造 面心立方構造 六方最密構造 剛球の並べ方と最密構造剛球を平面上に の向きに整列させるのに次の 2 つの方法がある 図より,B の方が A より密であることがわかる A B 1 体心立方構造 A を土台に剛球を積み重ねる 1 段目 2 2 段目 3 3 段目 他と色で区別した部分は上から見た最小繰り返し単位構造 ( 体心立方構造 ) 4 つまり,1 段目,2 段目,3 段目と順に重ねることにより,

More information

離散数学

離散数学 離散数学 最小全域木と最大流問題 落合秀也 今日の内容 最小全域木 プリムのアルゴリズム 最大流問題 フォード ファルカーソンのアルゴリズム 今日の内容 最小全域木 プリムのアルゴリズム 最大流問題 フォード ファルカーソンのアルゴリズム 最小全域木を考える Minimum Spanning Tree Problem ラベル付 ( 重み付 ) グラフ G(V, E) が与えられたとき ラベルの和が最小となる全域木を作りたい

More information

Probit , Mixed logit

Probit , Mixed logit Probit, Mixed logit 2016/5/16 スタートアップゼミ #5 B4 後藤祥孝 1 0. 目次 Probit モデルについて 1. モデル概要 2. 定式化と理解 3. 推定 Mixed logit モデルについて 4. モデル概要 5. 定式化と理解 6. 推定 2 1.Probit 概要 プロビットモデルとは. 効用関数の誤差項に多変量正規分布を仮定したもの. 誤差項には様々な要因が存在するため,

More information

Microsoft PowerPoint - 2.ppt [互換モード]

Microsoft PowerPoint - 2.ppt [互換モード] 0 章数学基礎 1 大学では 高校より厳密に議論を行う そのために 議論の議論の対象を明確にする必要がある 集合 ( 定義 ) 集合 物の集まりである集合 X に対して X を構成している物を X の要素または元という 集合については 3 セメスタ開講の 離散数学 で詳しく扱う 2 集合の表現 1. 要素を明示する表現 ( 外延的表現 ) 中括弧で 囲う X = {0,1, 2,3} 慣用的に 英大文字を用いる

More information

Microsoft PowerPoint - 09-search.ppt [互換モード]

Microsoft PowerPoint - 09-search.ppt [互換モード] ヒューリスティック探索 ( 経験を用いた探索 ) これまでに到達した探索木の末梢状態から展開される状態のうち, 解に至る可能性の高い状態に注目し, 探索の効率を高める. 末梢状態 : 探索木上で, これまでに探索した端の状態. 展開 : 与えられた節点に対し, 直接移行可能な全ての後継状態を作り出すこと. 探索の効率化に用いる判断基準 ( ヒューリスティック情報 ) 状態 s における評価関数 (

More information

分子系統解析における様々な問題について 田辺晶史

分子系統解析における様々な問題について 田辺晶史 分子系統解析における様々な問題について 田辺晶史 そもそもどこの配列を使うべき? そもそもどこの配列を使うべき? 置換が早すぎず遅すぎない (= 多すぎず少なすぎない ) そもそもどこの配列を使うべき? 置換が早すぎず遅すぎない (= 多すぎず少なすぎない ) 連続長は長い方が良い そもそもどこの配列を使うべき? 置換が早すぎず遅すぎない (= 多すぎず少なすぎない ) 連続長は長い方が良い 遺伝子重複が起きていない

More information

分子系統樹推定の落とし穴と回避法 筑波大 生命環境 田辺晶史

分子系統樹推定の落とし穴と回避法 筑波大 生命環境 田辺晶史 分子系統樹推定の落とし穴と回避法 筑波大 生命環境 田辺晶史 http://www.fifthdimension.jp/wiki.cgi http://www.fifthdimension.jp/documents/molphytextbook/ 分子系統樹推定 の 落とし穴 とは データが 仮定 を満たしていない 仮定その1 相同 である 相同 非相同 相同 相同 同一の祖先形質 に由来する

More information

Microsoft Word - 201hyouka-tangen-1.doc

Microsoft Word - 201hyouka-tangen-1.doc 数学 Ⅰ 評価規準の作成 ( 単元ごと ) 数学 Ⅰ の目標及び図形と計量について理解させ 基礎的な知識の習得と技能の習熟を図り それらを的確に活用する機能を伸ばすとともに 数学的な見方や考え方のよさを認識できるようにする 評価の観点の趣旨 式と不等式 二次関数及び図形と計量における考え方に関 心をもつとともに 数学的な見方や考え方のよさを認識し それらを事象の考察に活用しようとする 式と不等式 二次関数及び図形と計量における数学的な見

More information

布に従う しかし サイコロが均質でなく偏っていて の出る確率がひとつひとつ異なっているならば 二項分布でなくなる そこで このような場合に の出る確率が同じであるサイコロをもっている対象者をひとつのグループにまとめてしまえば このグループの中では回数分布は二項分布になる 全グループの合計の分布を求め

布に従う しかし サイコロが均質でなく偏っていて の出る確率がひとつひとつ異なっているならば 二項分布でなくなる そこで このような場合に の出る確率が同じであるサイコロをもっている対象者をひとつのグループにまとめてしまえば このグループの中では回数分布は二項分布になる 全グループの合計の分布を求め < 解説 > 広告媒体の到達率推定モデル 株式会社ビデオリサーチ常務取締役木戸茂 広告媒体計画の評価指標として広告業界では 有効リーチ あるいは 有効フリークエンシー の概念が一般に用いられている 広告の到達回数分布 Frequency Distribution の推定が重視される背景としては Krugan97977 の3ヒット セオリー Threeexosuretheory を根拠とした 3リーチ

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション グラフの禁止構造条件について 古谷倫貴 ( 北里大学一般教育部 ) 話の流れ 1. 禁止部分グラフ a. 問題設定 b. ハミルトン閉路のための禁止部分グラフ c. 完全マッチングのための禁止部分グラフ d. 禁止部分グラフ条件の完全決定の難易 2. 自明な禁止部分グラフ条件 3. 禁止部分グラフ条件の比較 問題設定 グラフのある性質 P について,P のための ( 十分 ) 条件として良いものを考えたい.

More information

Kumamoto University Center for Multimedia and Information Technologies Lab. 熊本大学アプリケーション実験 ~ 実環境における無線 LAN 受信電波強度を用いた位置推定手法の検討 ~ InKIAI 宮崎県美郷

Kumamoto University Center for Multimedia and Information Technologies Lab. 熊本大学アプリケーション実験 ~ 実環境における無線 LAN 受信電波強度を用いた位置推定手法の検討 ~ InKIAI 宮崎県美郷 熊本大学アプリケーション実験 ~ 実環境における無線 LAN 受信電波強度を用いた位置推定手法の検討 ~ InKIAI プロジェクト @ 宮崎県美郷町 熊本大学副島慶人川村諒 1 実験の目的 従来 信号の受信電波強度 (RSSI:RecevedSgnal StrengthIndcator) により 対象の位置を推定する手法として 無線 LAN の AP(AccessPont) から受信する信号の減衰量をもとに位置を推定する手法が多く検討されている

More information

学習指導要領

学習指導要領 (1) 数と式 ア数と集合 ( ア ) 実数数を実数まで拡張する意義を理解し 簡単な無理数の四則計算をすること 絶対値の意味を理解し適切な処理することができる 例題 1-3 の絶対値をはずせ 展開公式 ( a + b ) ( a - b ) = a 2 - b 2 を利用して根号を含む分数の分母を有理化することができる 例題 5 5 + 2 の分母を有理化せよ 実数の整数部分と小数部分の表し方を理解している

More information

講義「○○○○」

講義「○○○○」 講義 システムの信頼性 内容. 直列システムの信頼性. 並列システムの信頼性 3. 直列 並列の複合システムの信頼性 4. 信頼性向上のための手法 担当 : 倉敷哲生 ビジネスエンジニアリング専攻 システムの構成 種々の機械や構造物, システムを分割していけば. 個々の要素 サブシステム となる. サブシステムの組み合わせ方式 直列系 並列系 m/ 冗長系 待機冗長系 3 直列システムの信頼性 直列系

More information

Microsoft Word - 補論3.2

Microsoft Word - 補論3.2 補論 3. 多変量 GARC モデル 07//6 新谷元嗣 藪友良 対数尤度関数 3 章 7 節では 変量の対数尤度を求めた ここでは多変量の場合 とくに 変量について対数尤度を求める 誤差項 は平均 0 で 次元の正規分布に従うとする 単純化のため 分散と共分散は時間を通じて一定としよう ( この仮定は後で変更される ) したがって ij から添え字 を除くことができる このとき と の尤度関数は

More information

ピタゴラスの定理の証明4

ピタゴラスの定理の証明4 [ 証明 ] この証明を論理的に厳密に行うには 何回か三角形 四角形の合同を証明しなくてはなりません 以下では 直感的な分かりやすさを重視して この証明を行いません 三角形 において であるとする 辺 を一辺とする正方形 を三角形 の外側につくる 辺 を一辺とする正方形 を三角形 の外側につくる 辺 を一辺とする正方形 Fを三角形 の外側につくる 直線 と直線 との交点を J とし 直線 と直線 F

More information

Taro-再帰関数Ⅲ(公開版).jtd

Taro-再帰関数Ⅲ(公開版).jtd 0. 目次 1 1. ソート 1 1. 1 挿入ソート 1 1. 2 クイックソート 1 1. 3 マージソート - 1 - 1 1. ソート 1 1. 1 挿入ソート 挿入ソートを再帰関数 isort を用いて書く 整列しているデータ (a[1] から a[n-1] まで ) に a[n] を挿入する操作を繰り返す 再帰的定義 isort(a[1],,a[n]) = insert(isort(a[1],,a[n-1]),a[n])

More information

gengo1-8

gengo1-8 問題提起その 1 一文字ずつ文字 ( 数字 ) を読み込み それぞれの文字が何回入力されたかを数えて出力するプログラム int code, count_0=0, count_1=0, count_2=0, count_3=0,..., count_9=0; while( (code=getchar())!= EOF ){ } switch(code){ case 0 : count_0++; break;

More information

統計的データ解析

統計的データ解析 統計的データ解析 011 011.11.9 林田清 ( 大阪大学大学院理学研究科 ) 連続確率分布の平均値 分散 比較のため P(c ) c 分布 自由度 の ( カイ c 平均値 0, 標準偏差 1の正規分布 に従う変数 xの自乗和 c x =1 が従う分布を自由度 の分布と呼ぶ 一般に自由度の分布は f /1 c / / ( c ) {( c ) e }/ ( / ) 期待値 二乗 ) 分布 c

More information

Microsoft PowerPoint - 10.pptx

Microsoft PowerPoint - 10.pptx 0. 固有値とその応用 固有値と固有ベクトル 2 行列による写像から固有ベクトルへ m n A : m n n m 行列によって線形写像 f R R A が表せることを見てきた ここでは 2 次元平面の行列による写像を調べる 2 = 2 A 2 2 とし 写像 まず 単位ベクトルの像を求める u 2 x = v 2 y f : R A R を考える u 2 2 u, 2 2 0 = = v 2 0

More information

Microsoft PowerPoint - 05.pptx

Microsoft PowerPoint - 05.pptx アルゴリズムとデータ構造第 5 回 : データ構造 (1) 探索問題に対応するデータ構造 担当 : 上原隆平 (uehara) 2015/04/17 アルゴリズムとデータ構造 アルゴリズム : 問題を解く手順を記述 データ構造 : データや計算の途中結果を蓄える形式 計算の効率に大きく影響を与える 例 : 配列 連結リスト スタック キュー 優先順位付きキュー 木構造 今回と次回で探索問題を例に説明

More information

untitled

untitled 1 (1) (2) (3) (4) (1) (2) (3) (1) (2) (3) (1) (2) (3) (4) (5) (1) (2) (3) (1) (2) 10 11 12 2 2520159 3 (1) (2) (3) (4) (5) (6) 103 59529 600 12 42 4 42 68 53 53 C 30 30 5 56 6 (3) (1) 7 () () (()) () ()

More information

二等辺三角形の性質 (2) 次の図の の大きさを求めなさい () = P=Q P=R Q 68 R P (2) (3) 五角形 は正五角形 = F 50 F (4) = = (5) === = 80 2 二等辺三角形の頂角の外角を 底角を y で表すとき y を の式で表しなさい y 2-5-2

二等辺三角形の性質 (2) 次の図の の大きさを求めなさい () = P=Q P=R Q 68 R P (2) (3) 五角形 は正五角形 = F 50 F (4) = = (5) === = 80 2 二等辺三角形の頂角の外角を 底角を y で表すとき y を の式で表しなさい y 2-5-2 三角形 四角形 二等辺三角形の性質 () 二等辺三角形と正三角形 二等辺三角形 2つの辺が等しい三角形( 定義 ) 二等辺三角形の性質定理 二等辺三角形の底角は等しい 定理 2 二等辺三角形の頂点の二等分線は 底辺を直角に2 等分する 正三角形 3 辺が等しい三角形 ( 定義 ) 次の図で 同じ印をつけた辺や角が等しいとき の大きさを求めなさい () (2) (3) 65 40 25 (4) (5)

More information

学習指導要領

学習指導要領 (1) 数と式 学習指導要領ア数と集合 ( ア ) 実数数を実数まで拡張する意義を理解し 簡単な無理数の四則計算をすること 第 1 章第 節実数 東高校学力スタンダード 4 実数 (P.3~7) 自然数 整数 有理数 無理数 実数のそれぞれの集 合について 四則演算の可能性について判断できる ( 例 ) 下の表において, それぞれの数の範囲で四則計算を考えるとき, 計算がその範囲で常にできる場合には

More information

テンソル ( その ) テンソル ( その ) スカラー ( 階のテンソル ) スカラー ( 階のテンソル ) 階数 ベクトル ( 階のテンソル ) ベクトル ( 階のテンソル ) 行列表現 シンボリック表現 [ ]

テンソル ( その ) テンソル ( その ) スカラー ( 階のテンソル ) スカラー ( 階のテンソル ) 階数 ベクトル ( 階のテンソル ) ベクトル ( 階のテンソル ) 行列表現 シンボリック表現 [ ] Tsor th-ordr tsor by dcl xprsso m m Lm m k m k L mk kk quott rul by symbolc xprsso Lk X thrd-ordr tsor cotrcto j j Copyrght s rsrvd. No prt of ths documt my b rproducd for proft. テンソル ( その ) テンソル ( その

More information

20~22.prt

20~22.prt [ 三クリア W] 辺が等しいことの証明 ( 円周角と弦の関係利用 ) の の二等分線がこの三角形の外接円と交わる点をそれぞれ とするとき 60 ならば であることを証明せよ 60 + + 0 + 0 80-60 60 から ゆえに 等しい長さの弧に対する弦の長さは等しいから [ 三クリア ] 方べきの定理 接線と弦のなす角と円周角を利用 線分 を直径とする円 があり 右の図のように の延長上の点

More information

Microsoft Word - lec_student-chp3_1-representative

Microsoft Word - lec_student-chp3_1-representative 1. はじめに この節でのテーマ データ分布の中心位置を数値で表す 可視化でとらえた分布の中心位置を数量化する 平均値とメジアン, 幾何平均 この節での到達目標 1 平均値 メジアン 幾何平均の定義を書ける 2 平均値とメジアン, 幾何平均の特徴と使える状況を説明できる. 3 平均値 メジアン 幾何平均を計算できる 2. 特性値 集めたデータを度数分布表やヒストグラムに整理する ( 可視化する )

More information

Microsoft PowerPoint - lecture a.pptx

Microsoft PowerPoint - lecture a.pptx 本日 (3 時限目 ) の内容 バイオインフォマティクス ( 生命情報学 ) 応用生命科学 情報生命学第 3 回配列解析入門 生物学と情報学の学際領域の学問分野 目的 生物データに対する情報解析技術の開発 情報解析技術を利用した新たな生物学的知識の発見 生物学の実験技術の革新 ( 例 : 次世代シークエンサー ) 大量のデータ ウェット ( 実験 ) とドライ ( 解析 ) の協力が不可欠 2 3

More information

Microsoft PowerPoint - DA2_2017.pptx

Microsoft PowerPoint - DA2_2017.pptx 1// 小テスト内容 データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (I) 1 1 第 章の構成. 単一始点最短路問題 単一始点最短路問題とは 単一始点最短路問題の考え方 単一始点最短路問題を解くつのアルゴリズム ベルマン フォードのアルゴリズム トポロジカル ソートによる解法 ダイクストラのアルゴリズム 1 1 単一始点最短路問題とは 単一始点最短路問題とは 前提 : 重み付き有向グラフ

More information

Taro-再帰関数Ⅱ(公開版).jtd

Taro-再帰関数Ⅱ(公開版).jtd 0. 目次 6. 2 項係数 7. 二分探索 8. 最大値探索 9. 集合 {1,2,,n} 上の部分集合生成 - 1 - 6. 2 項係数 再帰的定義 2 項係数 c(n,r) は つぎのように 定義される c(n,r) = c(n-1,r) + c(n-1,r-1) (n 2,1 r n-1) = 1 (n 0, r=0 ) = 1 (n 1, r=n ) c(n,r) 0 1 2 3 4 5

More information

3 57 210 57 JR 57325 132 28 IC JCT 28 4.1.1 4.1.1 4.1.2 4.1.2 4.1.1 11 35) 4.1.3 4.1.4 4.1.5 77 4.1.1 4.1.2 4.1.3 4.1.2 11 4.1.4 4.1.5 78 298 299 298 325 298 57 299 471 650 299 298 325 400m 640m 4.1.3

More information

Microsoft PowerPoint - 10.pptx

Microsoft PowerPoint - 10.pptx m u. 固有値とその応用 8/7/( 水 ). 固有値とその応用 固有値と固有ベクトル 行列による写像から固有ベクトルへ m m 行列 によって線形写像 f : R R が表せることを見てきた ここでは 次元平面の行列による写像を調べる とし 写像 f : を考える R R まず 単位ベクトルの像 u y y f : R R u u, u この事から 線形写像の性質を用いると 次の格子上の点全ての写像先が求まる

More information

弾性定数の対称性について

弾性定数の対称性について () by T. oyama () ij C ij = () () C, C, C () ij ji ij ijlk ij ij () C C C C C C * C C C C C * * C C C C = * * * C C C * * * * C C * * * * * C () * P (,, ) P (,, ) lij = () P (,, ) P(,, ) (,, ) P (, 00,

More information

多変量解析 ~ 重回帰分析 ~ 2006 年 4 月 21 日 ( 金 ) 南慶典

多変量解析 ~ 重回帰分析 ~ 2006 年 4 月 21 日 ( 金 ) 南慶典 多変量解析 ~ 重回帰分析 ~ 2006 年 4 月 21 日 ( 金 ) 南慶典 重回帰分析とは? 重回帰分析とは複数の説明変数から目的変数との関係性を予測 評価説明変数 ( 数量データ ) は目的変数を説明するのに有効であるか得られた関係性より未知のデータの妥当性を判断する これを重回帰分析という つまり どんなことをするのか? 1 最小 2 乗法により重回帰モデルを想定 2 自由度調整済寄与率を求め

More information

Taro-最大値探索法の開発(公開版

Taro-最大値探索法の開発(公開版 最大値探索法の開発 0. 目次 1. 開発過程 1 目標 1 : 4 個のデータの最大値を求める 目標 2 : 4 個のデータの最大値を求める 改良 : 多数のデータに対応するため 配列を使う 目標 3 : n 個のデータの最大値を求める 改良 : コードを簡潔に記述するため for 文を使う 目標 4 : n 個のデータの最大値を求める 改良 : プログラムをわかりやすくするため 関数を使う 目標

More information

Microsoft PowerPoint - lecture a.pptx

Microsoft PowerPoint - lecture a.pptx 応用生命科学 情報生命学第 3 回配列解析入門 7 月 14 日 ( 木 ) 3 時限目加藤有己大阪大学大学院医学系研究科講義資料 http://www.med.osakau.ac.p/pub/rna/ykato/lecture/bonfo16/ 授業目的 情報科学と生命科学の融合領域である情報生命科学の基本的な手法を理解することを目的とする 日程 3 時限目 4 時限目 6 月 30 日 ( 木

More information

ver

ver MacVector 基本操作 ( マルチプルアラインメント ) MacVector でマルチプルアラインメントをするために必要な操作の一部を紹介いたしす マルチプルアラインメントに関しての主要な操作は下記のものです A. 配列情報のファイルの入手 B. 配列情報ファイルの作成 ( 新規 ) C. マルチプルアラインメント D. 系統樹の作成 まず MacVector を起動してください ( 注意!MacVector

More information

COMPUTING THE LARGEST EMPTY RECTANGLE

COMPUTING THE LARGEST EMPTY RECTANGLE COMPUTING THE LARGEST EMPTY RECTANGLE B.Chazelle, R.L.Drysdale and D.T.Lee SIAM J. COMPUT Vol.15 No.1, February 1986 2012.7.12 TCS 講究関根渓 ( 情報知識ネットワーク研究室 M1) Empty rectangle 内部に N 個の点を含む領域長方形 (bounding

More information

学習指導要領

学習指導要領 (1) 数と式 学習指導要領 数と式 (1) 式の計算二次の乗法公式及び因数分解の公式の理解を深め 式を多面的にみたり目的に応じて式を適切に変形したりすること 東京都立町田高等学校学力スタンダード 整式の加法 減法 乗法展開の公式を利用できる 式を1 つの文字におき換えることによって, 式の計算を簡略化することができる 式の形の特徴に着目して変形し, 展開の公式が適用できるようにすることができる 因数分解因数分解の公式を利用できる

More information

< F2D837C E95CF CF68A4A94C5816A2E6A>

< F2D837C E95CF CF68A4A94C5816A2E6A> 0. 目次 6. ポインタ変数と文字処理 6. 1 文字 6. 2 文字列定数 6. 3 文字列 6. 4 文字列配列 7. ポインタ変数と関数 8. 問題 7. 1 引数とポインタ変数 7. 1. 1 変数が引数の場合 7. 1. 2 ポインタ変数が引数の場合 7. 2 引数と配列 7. 3 戻り値とポインタ変数 問題 1 問題 2-1 - 6. ポインタ変数と文字処理 6. 1 文字 文字の宣言

More information

ビジネス統計 統計基礎とエクセル分析 正誤表

ビジネス統計 統計基礎とエクセル分析 正誤表 ビジネス統計統計基礎とエクセル分析 ビジネス統計スペシャリスト エクセル分析スペシャリスト 公式テキスト正誤表と学習用データ更新履歴 平成 30 年 5 月 14 日現在 公式テキスト正誤表 頁場所誤正修正 6 知識編第 章 -3-3 最頻値の解説内容 たとえば, 表.1 のデータであれば, 最頻値は 167.5cm というたとえば, 表.1 のデータであれば, 最頻値は 165.0cm ということになります

More information

航空機の運動方程式

航空機の運動方程式 可制御性 可観測性. 可制御性システムの状態を, 適切な操作によって, 有限時間内に, 任意の状態から別の任意の状態に移動させることができるか否かという特性を可制御性という. 可制御性を有するシステムに対し, システムは可制御である, 可制御なシステム という言い方をする. 状態方程式, 出力方程式が以下で表されるn 次元 m 入力 r 出力線形時不変システム x Ax u y x Du () に対し,

More information

<8D828D5A838A817C A77425F91E6318FCD2E6D6364>

<8D828D5A838A817C A77425F91E6318FCD2E6D6364> 4 1 平面上のベクトル 1 ベクトルとその演算 例題 1 ベクトルの相等 次の問いに答えよ. ⑴ 右の図 1 は平行四辺形 である., と等しいベクトルをいえ. ⑵ 右の図 2 の中で互いに等しいベクトルをいえ. ただし, すべてのマス目は正方形である. 解 ⑴,= より, =,= より, = ⑵ 大きさと向きの等しいものを調べる. a =d, c = f d e f 1 右の図の長方形 において,

More information

オートマトン 形式言語及び演習 4. 正規言語の性質 酒井正彦 正規言語の性質 反復補題正規言語が満たす性質 ある与えられた言語が正規言語でないことを証明するために その言語が正規言語であると

オートマトン 形式言語及び演習 4. 正規言語の性質 酒井正彦   正規言語の性質 反復補題正規言語が満たす性質 ある与えられた言語が正規言語でないことを証明するために その言語が正規言語であると オートマトン 形式言語及び演習 4. 正規言語の性質 酒井正彦 www.trs.css.i.nagoya-u.ac.jp/~sakai/lecture/automata/ 正規言語の性質 正規言語が満たす性質 ある与えられた言語が正規言語でないことを証明するために その言語が正規言語であると仮定してを使い 矛盾を導く 閉包性正規言語を演算により組み合わせて得られる言語が正規言語となる演算について調べる

More information

我々のビッグデータ処理の新しい産業応用 広告やゲーム レコメンだけではない 個別化医療 ( ライフサイエンス ): 精神神経系疾患 ( うつ病 総合失調症 ) の網羅的ゲノム診断法の開発 全人類のゲノム解析と個別化医療実現を目標 ゲノム育種 ( グリーンサイエンス ): ブルーベリー オオムギ イネ

我々のビッグデータ処理の新しい産業応用 広告やゲーム レコメンだけではない 個別化医療 ( ライフサイエンス ): 精神神経系疾患 ( うつ病 総合失調症 ) の網羅的ゲノム診断法の開発 全人類のゲノム解析と個別化医療実現を目標 ゲノム育種 ( グリーンサイエンス ): ブルーベリー オオムギ イネ モンテカルロ法による分子進化の分岐図作成 のための最適化法 石井一夫 1 松田朋子 2 古崎利紀 1 後藤哲雄 2 1 東京農工大学 2 茨城大学 2013 9 9 2013 1 我々のビッグデータ処理の新しい産業応用 広告やゲーム レコメンだけではない 個別化医療 ( ライフサイエンス ): 精神神経系疾患 ( うつ病 総合失調症 ) の網羅的ゲノム診断法の開発 全人類のゲノム解析と個別化医療実現を目標

More information

線形代数とは

線形代数とは 線形代数とは 第一回ベクトル 教科書 エクササイズ線形代数 立花俊一 成田清正著 共立出版 必要最低限のことに限る 得意な人には物足りないかもしれません 線形代数とは何をするもの? 線形関係 y 直線 yもも 次式で登場する (( 次の形 ) 線形 ただし 次元の話世の中は 3 次元 [4[ 次元 ] 次元 3 次元 4 次元 はどうやって直線を表すの? ベクトルや行列の概念 y A ベクトルを使うと

More information