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

Size: px
Start display at page:

Download "Microsoft PowerPoint - 13.ppt [互換モード]"

Transcription

1 13. 近似アルゴリズム 1

2 13.1 近似アルゴリズムの種類 NP 困難な問題に対しては多項式時間で最適解を求めることは困難であるので 最適解に近い近似解を求めるアルゴリズムが用いられることがある このように 必ずしも厳密解を求めないアルゴリズムは 大きく分けて 2 つの範疇に分けられる 2

3 ヒューリスティックと近似アルゴリズム ヒュ- リスティクス ( 発見的解法 経験的解法 ) 遺伝的アルゴリズム (GA) アニ-リング ( 焼きなまし法 ) 精度保証無し タブサーチ実験的評価が主ローカルサーチニューラルネット等 近似アルゴリズム定数近似アルゴリズム (APX) 多項式近似スキーム (PTAS) 精度保証付き完全多項式近似スキーム (FPTAS) 理論的解析が主 ここでは 近似アルゴリズムについてみていく 3

4 α 近似アルゴリズム 最小化問題に対して いつも最適解のα 倍以下の解を入力サイズの多項式時間で求めるようなアルゴリズムをα 近似アルゴリズムという ここで α であり 1 α を近似率という すなわち 最適解を f と表し ( OPT x ) アルゴリズムの解の評価値を f ( AL xと表すと 常 ) に次の式を満足する fal( x) f OPT ( x ) OPT α f ( x ) α f ( x ) AL OPT 4

5 β 近似アルゴリズム 最大化問題に対して いつも最適解のβ 倍以上の解を入力サイズの多項式時間で求めるようなアルゴリズムをβ 近似アルゴリズムという ここで β であり 1 β を近似率という また βを近似保証ということもある すなわち 最適解をと表し アルゴリズムの解 f ( OPT x ) の評価値をと表すと 常に次の式を満足す f ( ) AL x る f AL ( x) β f OPT ( x) f ( x ) β f ( x ) AL OPT 5

6 APX α( あるいはβ) 定数であるようなアルゴリズムが存在するクラスを APX(APproXimation) p ) という 6

7 PTAS と FPTAS 近似率 α(β) を限りなく1に近づけることができるとき そのようなα 近似アルゴリズムをPTAS(Polynomial Time Approximation Scheme, 多項式時間近似スキーム ) という すなわち 任意の正数 ε > 0 に対して とできる入力サイズの多項式時間アルゴリズムを α = 1 + ε PTASという さらに 入力サイズと精度 n の多項 1 ε 式時間アルゴリズムFPTAS(Fully Polynomial Time Approximation Scheme, 完全多項式時間近似スキーム ) という 問題によっては PTASが存在しない ( 知られていない ) ものがある また 定数近似すら存在しない問題もある このようなアルゴリズムの出力は入力サイズに依存した近似値になってしまう 7

8 近似アルゴリズムの存在 近似アルゴリズムが存在するクラス APX が存在するクラス PTAS が存在するクラス FPTAS が存在するクラス 8

9 13-2. 巡回セールスマン問題 巡回セールスマン問題には ネットワーク型と 幾何型とがある ネットワーク型の巡回セールスマン問題では 入力は辺重み付きのグラフであり 出力は頂点を全て辿る閉路で重みの総和が最小のものである

10 三角不等式を満足しないようなネットワーク型の巡回セールスマン問題は 近似アルゴリズムを得ることすら NP- 困難である 具体的には 定数近似アルゴリズムが存在するとと NP 完全問題であるハミルトン閉路問題が多項式時間で解けてしまう つまり ハミルトン閉路問題をネットワーク型の定数近似巡回セールスマン問題に帰着できてしまう このことより ネットワーク型の巡回セールスマン問題には定数近似アルゴリズムは存在しないと考えられている 10

11 ハミルトン閉路問題と巡回セールスマン問題 名称 : ハミルトン閉路問題インスタンス : グラフ G 問い :G 中に 全ての頂点を丁度 1 度だけ通るような閉路は存在するか? 名称 : 巡回セールスマン (NTSP) インスタンス : ネットワークN 正数 K 問い : ネットワーク中の全ての頂点を通るような閉路で重みの総和がK 以下となるようなもの存在するか? 11

12 巡回セールスマン問題への帰着 ネットワーク型の巡回セールスマン問題を解くα 近似アルゴリズムが存在すると 次のようにハミルトン閉路問題を巡回セールスマン問題に帰着できる つまり ハミルトン閉路問題のインスタンスであるグラフGから巡回セールスマン問題のインスタンスである辺重み付きグラフ ( ネットワーク N) と整数 Kを定めればめることができる まず Gの辺に全て1の重みをつけてネットワークNを構 n 成する 次に Kとして K = として 巡回セールスマ α ン問題へ帰着する このとき αの定数近似であるapxが存在すると 多項式時間でハミルトン閉路の存在判定ができてしまう 以上のことより P NP である限り ネットワーク型の巡回セールスマン問題を解く多項式時間アルゴリズムはない 12

13 幾何巡回セールスマン問題 (GTSP) 実は 幾何巡回セールスマン問題には 定数近似アルゴリズムが存在する ネットワーク型と 幾何型での最大のちがいは 三角不等式が成り立つかどうかである ここで三角不等式とは 任意の xyz,, 対して 次が成り立つことである dxy (, ) dxz (, ) + dyz (, ) 13

14 2 次元 ( ユークリッド ) 平面上の点集合を考えれば 2 点間の距離は自動的に三角不等式を満たす このことは 利用できる情報 ( 三角不等式 ) が多くなったということであり ネットワーク型よりも幾何型の方が問題が簡単であることを意味する. 実際 幾何型の巡回セールスマン問題は FPTASを持つことが最近 (19 98 年 ) に示された このアルゴリズムは複雑なので ここでは2 近似アルゴリズムとそれを改善した1.5 近似アルゴリズムを示す 14

15 NTSP と GTSP 近似アルゴリズムが存在するクラス NTSP APX が存在するクラス PTAS が存在するクラス GTSP FPTAS が存在するクラス 15

16 2 近似アルゴリズム GTSPに対する2 近似アルゴリズム 1. 点集合を連結する最小全域木 MST Tを求める 2.Tの辺を辿りながら 全ての点を通る巡回路 C を求める (Tの辺を全て2 重化すればいい ) 3. C で一度通過した点をショートカットする順回路を求める C ' 次にこのアルゴリズムの動作を示す 16

17 2 近似アルゴリズムの動作入力 ( 点集合 ) 最小木 T 2 重化ショートカット 17

18 近似率の解析 最適な順回路をC OPT とし アルゴリズムで得られる順回路をC AL とする また COPT, CAL でそれぞれの長さを表すものとする 順回路 C OPT から任意に一本辺を除去すると 全域木が得られる よって 最小全域木 T の方が辺の重み総和は小さい ( そもそも 頂点を連結するもののなかで 重みが最小なものが最小全域木であった ) よって 次が成り立つ T C OPT 18

19 また アルゴリズムで得られる閉路では 最小木を2 重化したものより小さいので 次が成り立つ C 以上より AL C 2 T AL T 2 C AL 2 T C 2 C C C AL AL OPT 2 OPT C OPT 19

20 1.5 近似アルゴリズム GTSPに対する1.5 近似アルゴリズム 1. 点集合を連結する最小全域木 MST Tを求める 2.T において 次数が奇数の点からなる完全グラフを作り 最小重みマッチングMを求める 3.T+M はオイラーグラフであるのでグラフであるので 一筆書きに対応する順回路 Cを求める 4.3の順回路 Cからできるだけショートかっとして 順回路を構成する C ' 20

21 2 近似アルゴリズムの動作入力 ( 点集合 ) 最小木 T マッチング M ショートカット 21

22 近似率の解析 最適な順回路をC OPT とし アルゴリズムで得られる順回路をC AL とする また COPT, CAL でそれぞれの長さを表すものとする 2 近似アルゴリズムの解析と同様にして を得る T C OPT また C OPT 上で 次数が奇数の点 ( 奇点 ) を結ぶパスを考える C OPT 上で 奇点を結ぶパスを交互に選ぶことにより 上の辺集合を2つに分類する C OPT 22

23 奇点が偶数個しかないことに注意すると いつもきちんと 2 分割することができることがわかる C OPT このように C OPT の辺集合を と分割できる もちろん P1 2 P C OPT = P P 1 2 よって COPT = P + P2 1 23

24 また 三角不等式がなりたっているので パスで結ぶより直接辺でたどったほうが短い よって 最小マッチング M の重み総和に関して, 次が成り立つ M P P min {, } OPT 1 2 C = P + P 1 2 2min P, 2 M P { }

25 一方 アルゴリズムより C T + M AL 以上より C T + M AL C C AL opt C + = 3 2 opt C opt C opt 25

26 このように いろいろな技法を組み合わせて 近似率の改善が行われる NP 完全問題に対しても 厳密解でななくてもよければ 近似アルゴリズムの適用を考えてみると良い 26

27 13-3. ナップザック問題 ナップザック問題の一般形は次のよう書ける P ナップザック x = 特徴ベクトル 1 2 最大化 n f( x) = vx i i 条件 n i= 1 sx i i i=1= 1 b t (,,, ) x1 x2 x n xi {0,1} 27

28 ナップザック問題における欲張り法 ( グリーディ法 Greedy 法 ) 連続ナップザック問題のように 単位価値の高い法から順に選んでいく方法を考察する このように 部分的に評価関数を改善するだけの方法を欲張り法 (Greedy y法 ) という ( 欲張り法でも近似アルゴリズムになっていることもある これらは 問題やアルゴリズムをきちんと解析しないとわからない ) 28

29 ナップザックに対する欲張り法 1. 単位価値の高い順にならべる すなわち 必要なら添え字を付け換えて v v v s s s 1 2 n とする 2. から まで順番に i = n i 1 n x = 1 s b s x i j j j= 1 そうでないなら x i x = とする 0 なら i とし 29

30 欲張り法の性能 欲張り法で得られる解を x g = ( x g 1, x g 2,, x g n ) x o = ( o, o,, o ) とおく 最適解を x1 x2 x n とおき x g = 以下では x o x なら 欲張り法と最適解が一致している g x o のときを考えよう このときは 最適解には採用されたが 欲張り解には採用されなかった最初の要素を考えてその添え字をとする すなわち j g o 0 = x < x = 1 j j このとき 任意の i g o x x j j j 1 に対して である 30

31 よって n j j j g g g o g o f ( x ) = vx vx = vx + v ( x x ) i i i i i i i i i i= 1 i= 1 i= 1 i= 1 v v + = + j j j j j o j g o o j g 0 vx i i si( xi xi ) vx i i sx i i sx i i i= 1 i= 1 sj i= 1 sj i= 1 i= 1 という式が成り立つ ここで 次のようなことに注意する i j 任意の i j + 1 に対して である 欲張り法で j v s i が選ばれなかったことから j j 1 g g sx i i = sx i i > b sj i= 1 i= 1 v s j 最適解でも制約式を満たすので n i= 1 sx i o i b j n 0 0 sx i i b sx i i i= 1 i= j+ 1 31

32 以上より 次の関係式が導ける v s j j j j n g 0 v j o sx i i sx i i ( b sj) b sx i i i= 1 i= 1 s j i= j+ 1 v n n j o o sx i i s j vx i i vj s j i=+ j 1 i=+ j 1 j n g o vj ( ) o f x vx i i + sx i i s j i= 1 s j i= j+ 1 n o o o vx i i vj f( x ) vj f( x ) v i= 1 max なお ここで vmax は価値 vi の最大値である 32

33 欲張り法で悪い評価値を出すインスタンス A a 1 s 1 = 1 v = 1 2 a a 2 s = v = s = v = a B = 10 a 4 s 4 = 10 v 4 = 10 S = (1,1,1,10) V = (2, 2,2,10) 2 b = 10 x g = (1,1,1, (,,, 0) g f ( x ) = 6 x o = (0,0,0,1) o f ( x ) = 10 33

34 ナップザックの 1/2 近似アルゴリズム ナップザックに対する 1/2 近似アルゴリズム 1. 欲張り法によって解を求める 2. 価値が最大のものを一つだけ選ぶ a 3. 上の 2 つのうちで大きい方を解 x として出力する x g 34

35 近似率 アルゴリズムの出力 ( 解 ) が成り立つ a x とする このとき 以下の式 f x a ( ) f x g ( ) + vmax f x o ( ) 以上より 1/2 近似アルゴリズムであることがわかる 35

36 ナップザック問題に対する FPTAS ナップザック問題に対しては 任意の正数 ε に対する近似保証のアルゴリズムが知られている ( 1 ε) ナップザックに対する FPTAS εv 1. 与えられた ε max に対して K = とおく n vi 2. 各要素 i に対して 価値を vi ' = と修正する K r 3. 修正した価値のもとで ナップザックの最適解 x を動的計画法で求める x r 4. 上記の解と最初の価値のもとでの最大値を比べて a 評価値の高いものをアルゴリズムの出力 ( 解 ) とする x 36

37 FPTAS の評価 v i ' v K i = とおいていることにより 0 v Kv ' < K x f '( x) よって 任意の解に対して, その修正後の評価値に関して次式が成立する 一方 また 0 f ( x) Kf '( x) < nk r x は修正した価値での最適解なので r o f '( x ) f '( x ) a f ( x ) v max i i 37

38 よって f ( x a ) f( x r ) Kf '( x r ) Kf '( x o ) f ( x ) nk = f ( x ) εv f ( x ) εf ( x ) o o o a max 以上より a o (1 + ε) f ( x ) f ( x ) a 1 o o f ( x ) f( ) > (1 ε) f( ) 1 + ε x x 38

39 計算時間 ステップ 3 の動的計画法の部分について考察しよう まず 動的計画法に基づくナップザックアルゴリズムとして 大きさが決まっているときの価値の最大値を表として構成していた この動的計画法に基づいた場合 Onb ( ) 時間のアルゴリズムが得られた ここでは この動的計画法を以下の方針に切り替える 価値が決まってているときに 大きさの最小値として構成する このような動的計画法も構成できることに注意する この場合 価値の最大値は v max であるので 評価値の最大値は である よって アルゴリズムの計算量は Onv ( ) max 2 max Onv ( ) 時間である FPTASでは修正した値を用いるので 結局 2 vmax 2 n 1 3 On ( ) = On ( ) = O( n) K ε ε 39

40 ナップザック問題の近似可能性 近似アルゴリズム ナップザック APX PTAS FPTAS 40

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

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

スライド タイトルなし

スライド タイトルなし アルゴリズム入門 (8) ( 近似アルゴリズム ) 宮崎修一京都大学学術情報メディアセンター 近似アルゴリズムとは? 効率よく解ける問題 ( 多項式時間アルゴリズムが存在する問題 ) ソーティング 最短経路問題 最小全域木問題 効率よく解けそうにない問題 (NP 困難問題 ) 最小頂点被覆問題 MX ST MX CUT 本質的に問題が難しいのだが 何とか対応したい 幾つかのアプローチ ( 平均時間計算量

More information

Microsoft Word - NumericalComputation.docx

Microsoft Word - NumericalComputation.docx 数値計算入門 武尾英哉. 離散数学と数値計算 数学的解法の中には理論計算では求められないものもある. 例えば, 定積分は, まずは積分 ( 被積分関数の原始関数をみつけること できなければ値を得ることはできない. また, ある関数の所定の値における微分値を得るには, まずその関数の微分ができなければならない. さらに代数方程式の解を得るためには, 解析的に代数方程式を解く必要がある. ところが, これらは必ずしも解析的に導けるとは限らない.

More information

Microsoft PowerPoint - H21生物計算化学2.ppt

Microsoft PowerPoint - H21生物計算化学2.ppt 演算子の行列表現 > L いま 次元ベクトル空間の基底をケットと書くことにする この基底は完全系を成すとすると 空間内の任意のケットベクトルは > > > これより 一度基底を与えてしまえば 任意のベクトルはその基底についての成分で完全に記述することができる これらの成分を列行列の形に書くと M これをベクトル の基底 { >} による行列表現という ところで 行列 A の共役 dont 行列は A

More information

memo

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

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

2011年度 大阪大・理系数学

2011年度 大阪大・理系数学 0 大阪大学 ( 理系 ) 前期日程問題 解答解説のページへ a a を自然数とする O を原点とする座標平面上で行列 A= a の表す 次変換 を f とする cosθ siθ () >0 および0θ

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

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

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション 解けない問題 を知ろう 保坂和宏 ( 東京大学 B2) 第 11 回 JOI 春合宿 2012/03/19 概要 計算量に関して P と NP NP 完全 決定不能 いろいろな問題 コンテストにおいて Turing 機械 コンピュータの計算のモデル 計算 を数学的に厳密に扱うためのもの メモリのテープ (0/1 の列 ), ポインタ, 機械の内部状態を持ち, 規則に従って状態遷移をする 本講義では

More information

グラフ理論における偶奇性の現象

グラフ理論における偶奇性の現象 グラフ理論における偶奇性に関連する現象 (3 回目の講義 ) 加納幹雄 (Mikio Kano) 茨城大学名誉教授 講義の概略 1 回目入門的な話証明の多くを演習問題とします 2 回目マッチングと 1- 因子の一般化に関連する話 3 回目因子 = ある条件を満たす全域部分グラフ最近の因子理論のなかで偶奇性に関連するものの紹介 連結グラフ G と G-S の成分 G S S V(G) iso(g-s)=3

More information

学習指導要領

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

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

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

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

More information

Microsoft Word - 微分入門.doc

Microsoft Word - 微分入門.doc 基本公式 例題 0 定義式 f( ) 数 Ⅲ 微分入門 = の導関数を定義式にもとづいて計算しなさい 基本事項 ( f( ), g( ) が微分可能ならば ) y= f( ) g( ) のとき, y = y= f( ) g( ) h( ) のとき, y = ( f( ), g( ) が微分可能で, g( ) 0 ならば ) f( ) y = のとき, y = g ( ) とくに, y = のとき,

More information

2011年度 筑波大・理系数学

2011年度 筑波大・理系数学 0 筑波大学 ( 理系 ) 前期日程問題 解答解説のページへ O を原点とするy 平面において, 直線 y= の を満たす部分をC とする () C 上に点 A( t, ) をとるとき, 線分 OA の垂直二等分線の方程式を求めよ () 点 A が C 全体を動くとき, 線分 OA の垂直二等分線が通過する範囲を求め, それ を図示せよ -- 0 筑波大学 ( 理系 ) 前期日程問題 解答解説のページへ

More information

アルゴリズム論 Theory of Algorithms

アルゴリズム論 Theory of Algorithms 実践的アルゴリズム理論 Theory of Advanced Algorithms 11. 近似アルゴリズム 担当 : 上原隆平 今後の予定 : 21 日 ( 水 ): レポート締め切り 28 日 ( 水 ): 講義時間に最後の講義チュートリアルアワーに期末試験 (23 日は祝日,29 日と 12 月 3 日は休講 ) 1/46 Theory of Advanced Algorithms 実践的アルゴリズム理論

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

umeda_1118web(2).pptx

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

More information

横浜市環境科学研究所

横浜市環境科学研究所 周期時系列の統計解析 単回帰分析 io 8 年 3 日 周期時系列に季節調整を行わないで単回帰分析を適用すると, 回帰係数には周期成分の影響が加わる. ここでは, 周期時系列をコサイン関数モデルで近似し単回帰分析によりモデルの回帰係数を求め, 周期成分の影響を検討した. また, その結果を気温時系列に当てはめ, 課題等について考察した. 気温時系列とコサイン関数モデル第 報の結果を利用するので, その一部を再掲する.

More information

Math-Aquarium 例題 図形と計量 図形と計量 1 直角三角形と三角比 P 木の先端を P, 根元を Q とする A 地点の目の位置 A' から 木の先端への仰角が 30,A から 7m 離れた AQB=90 と なる B 地点の目の位置 B' から木の先端への仰角が 45 であ るとき,

Math-Aquarium 例題 図形と計量 図形と計量 1 直角三角形と三角比 P 木の先端を P, 根元を Q とする A 地点の目の位置 A' から 木の先端への仰角が 30,A から 7m 離れた AQB=90 と なる B 地点の目の位置 B' から木の先端への仰角が 45 であ るとき, 図形と計量 直角三角形と三角比 P 木の先端を P, 根元を Q とする 地点の目の位置 ' から 木の先端への仰角が 0, から 7m 離れた Q=90 と なる 地点の目の位置 ' から木の先端への仰角が であ るとき, 木の高さを求めよ ただし, 目の高さを.m とし, Q' を右の図のように定める ' 0 Q' '.m Q 7m 要点 PQ PQ PQ' =x とおき,' Q',' Q' を

More information

学習指導要領

学習指導要領 (1 ) 数と式 ア数と集合 ( ア ) 実数数を実数まで拡張する意義を理解し 簡単な無理数の四則計算をすること 自然数 整数 有理数 無理数の包含関係など 実 数の構成を理解する ( 例 ) 次の空欄に適当な言葉をいれて, 数の集合を表しなさい 実数の絶対値が実数と対応する点と原点との距離で あることを理解する ( 例 ) 次の値を求めよ (1) () 6 置き換えなどを利用して 三項の無理数の乗法の計

More information

周期時系列の統計解析 (3) 移動平均とフーリエ変換 nino 2017 年 12 月 18 日 移動平均は, 周期時系列における特定の周期成分の消去や不規則変動 ( ノイズ ) の低減に汎用されている統計手法である. ここでは, 周期時系列をコサイン関数で近似し, その移動平均により周期成分の振幅

周期時系列の統計解析 (3) 移動平均とフーリエ変換 nino 2017 年 12 月 18 日 移動平均は, 周期時系列における特定の周期成分の消去や不規則変動 ( ノイズ ) の低減に汎用されている統計手法である. ここでは, 周期時系列をコサイン関数で近似し, その移動平均により周期成分の振幅 周期時系列の統計解析 3 移動平均とフーリエ変換 io 07 年 月 8 日 移動平均は, 周期時系列における特定の周期成分の消去や不規則変動 ノイズ の低減に汎用されている統計手法である. ここでは, 周期時系列をコサイン関数で近似し, その移動平均により周期成分のがどのように変化するのか等について検討する. また, 気温の実測値に移動平均を適用した結果についてフーリエ変換も併用して考察する. 単純移動平均の計算式移動平均には,

More information

算法の設計と評価

算法の設計と評価 情報数理科学 Ⅶ/ 広域システム特論 Ⅴ/ 広域システム科学特殊講義 Ⅳ 算法の設計と解析 http://www.graco.c.u-tokyo.ac.jp/~kawamura/t/ad/ 平成 29 年 5 月 8 日河村彰星 Dynamic Programming 動的計画法とは 漸化式を使って値を順次記録しながら求める方法 問題 フィボナッチ数列の第 n 項を求める 1 n = 0 のとき f

More information

2018年度 東京大・理系数学

2018年度 東京大・理系数学 08 東京大学 ( 理系 ) 前期日程問題 解答解説のページへ関数 f ( ) = + cos (0 < < ) の増減表をつくり, + 0, 0 のと sin きの極限を調べよ 08 東京大学 ( 理系 ) 前期日程問題 解答解説のページへ n+ 数列 a, a, を, Cn a n = ( n =,, ) で定める n! an qn () n とする を既約分数 an p として表したときの分母

More information

Microsoft PowerPoint - DA2_2017.pptx

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

More information

Microsoft PowerPoint - 9.pptx

Microsoft PowerPoint - 9.pptx 9/7/8( 水 9. 線形写像 ここでは 行列の積によって 写像を定義できることをみていく また 行列の積によって定義される写像の性質を調べていく 拡大とスカラー倍 行列演算と写像 ( 次変換 拡大後 k 倍 k 倍 k 倍拡大の関係は スカラー倍を用いて次のように表現できる p = (, ' = k ' 拡大前 p ' = ( ', ' = ( k, k 拡大 4 拡大と行列の積 拡大後 k 倍

More information

Microsoft PowerPoint - 9.pptx

Microsoft PowerPoint - 9.pptx 9. 線形写像 ここでは 行列の積によって 写像を定義できることをみていく また 行列の積によって定義される写像の性質を調べていく 行列演算と写像 ( 次変換 3 拡大とスカラー倍 p ' = ( ', ' = ( k, kk p = (, k 倍 k 倍 拡大後 k 倍拡大の関係は スカラー倍を用いて次のように表現できる ' = k ' 拡大前 拡大 4 拡大と行列の積 p ' = ( ', '

More information

Microsoft PowerPoint SIGAL.ppt

Microsoft PowerPoint SIGAL.ppt アメリカン アジアンオプションの 価格の近似に対する 計算幾何的アプローチ 渋谷彰信, 塩浦昭義, 徳山豪 ( 東北大学大学院情報科学研究科 ) 発表の概要 アメリカン アジアンオプション金融派生商品の一つ価格付け ( 価格の計算 ) は重要な問題 二項モデルにおける価格付けは計算困難な問題 目的 : 近似精度保証をもつ近似アルゴリズムの提案 アイディア : 区分線形関数を計算幾何手法により近似 問題の説明

More information

三者ミーティング

三者ミーティング Corral Puzzle の 整数計画法による解法と評価 第 11 回組合せゲーム パズル研究集会 2016 年 月 7 日 ( 月 ) 大阪電気通信大学 弘中健太鈴木裕章上嶋章宏 2016//7 第 11 回組合せゲーム パズル研究集会 2 発表の流れ 研究の背景 整数計画法と先行研究 2 Corral Puzzle ルールと定義 定式化 2 種類の閉路性の定式化 7 1 6 評価 計測結果と考察

More information

2011年度 東京大・文系数学

2011年度 東京大・文系数学 東京大学 ( 文系 ) 前期日程問題 解答解説のページへ x の 次関数 f( x) = x + x + cx+ d が, つの条件 f () =, f ( ) =, ( x + cx+ d) dx= をすべて満たしているとする このような f( x) の中で定積分 I = { f ( x) } dx を最小にするものを求め, そのときの I の値を求めよ ただし, f ( x) は f ( x)

More information

Microsoft Word - 201hyouka-tangen-1.doc

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

More information

重要例題113

重要例題113 04_ 高校 数学 Ⅱ 必須基本公式 定理集 数学 Ⅱ 第 章式の計算と方程式 0 商と余り についての整式 A をについての整式 B で割ったときの商を Q, 余りを R とすると, ABQ+R (R の次数 ) > 0

More information

Microsoft PowerPoint - mp11-02.pptx

Microsoft PowerPoint - mp11-02.pptx 数理計画法第 2 回 塩浦昭義情報科学研究科准教授 shioura@dais.is.tohoku.ac.jp http://www.dais.is.tohoku.ac.jp/~shioura/teaching 前回の復習 数理計画とは? 数理計画 ( 復習 ) 数理計画問題とは? 狭義には : 数理 ( 数学 ) を使って計画を立てるための問題 広義には : 与えられた評価尺度に関して最も良い解を求める問題

More information

学力スタンダード(様式1)

学力スタンダード(様式1) (1) 数と式 学習指導要領ア数と集合 ( ア ) 実数数を実数まで拡張する意義を理解し 簡単な無理数の四則計算をすること 稔ヶ丘高校学力スタンダード 有理数 無理数の定義や実数の分類について理解し ている 絶対値の意味と記号表示を理解している 実数と直線上の点が一対一対応であることを理解 し 実数を数直線上に示すことができる 例 実数 (1) -.5 () π (3) 数直線上の点はどれか答えよ

More information

0 21 カラー反射率 slope aspect 図 2.9: 復元結果例 2.4 画像生成技術としての計算フォトグラフィ 3 次元情報を復元することにより, 画像生成 ( レンダリング ) に応用することが可能である. 近年, コンピュータにより, カメラで直接得られない画像を生成する技術分野が生

0 21 カラー反射率 slope aspect 図 2.9: 復元結果例 2.4 画像生成技術としての計算フォトグラフィ 3 次元情報を復元することにより, 画像生成 ( レンダリング ) に応用することが可能である. 近年, コンピュータにより, カメラで直接得られない画像を生成する技術分野が生 0 21 カラー反射率 slope aspect 図 2.9: 復元結果例 2.4 画像生成技術としての計算フォトグラフィ 3 次元情報を復元することにより, 画像生成 ( レンダリング ) に応用することが可能である. 近年, コンピュータにより, カメラで直接得られない画像を生成する技術分野が生まれ, コンピューテーショナルフォトグラフィ ( 計算フォトグラフィ ) と呼ばれている.3 次元画像認識技術の計算フォトグラフィへの応用として,

More information

学習指導要領

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

More information

PowerPoint プレゼンテーション

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

More information

2013年度 信州大・医系数学

2013年度 信州大・医系数学 03 信州大学 ( 医系 ) 前期日程問題 解答解説のページへ () 式 + + a a a3 を満たす自然数の組 ( a, a, a3) で, a a a3とな るものをすべて求めよ () r を正の有理数とする 式 r + + a a a を満たす自然数の組 ( a, a, a3) で, 3 a a a3となるものは有限個しかないことを証明せよ ただし, そのよう な組が存在しない場合は 0 個とし,

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

<4D F736F F F696E74202D2091E6824F82538FCD8CEB82E88C9F8F6F814592F990B382CC8CB4979D82BB82CC82505F D E95848D8682CC90B69

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

More information

20~22.prt

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

More information

DVIOUT-SS_Ma

DVIOUT-SS_Ma 第 章 テイラー展開 次の図のように関数のグラフをのグラフ ( 積み木のようなものと考えます ) を積み重ねて作ってみましょう ただ単純に足すだけではうまく作れません 色々と削ることが必要になります 次のように半分にしたり, 分のに削らなくてはなりません どうですか? たった枚の積み木を積み重ねただけで, ほぼのグラフに近づきまし たね これから学ぶのがこのテイラー展開のお話です 初等関数の微分 初等関数の微分まずは

More information

2015-2017年度 2次数学セレクション(複素数)解答解説

2015-2017年度 2次数学セレクション(複素数)解答解説 05 次数学セレクション解答解説 [ 筑波大 ] ( + より, 0 となり, + から, ( (,, よって, の描く図形 C は, 点 を中心とし半径が の円である すなわち, 原 点を通る円となる ( は虚数, は正の実数より, である さて, w ( ( とおくと, ( ( ( w ( ( ( ここで, w は純虚数より, は純虚数となる すると, の描く図形 L は, 点 を通り, 点 と点

More information

<8D828D5A838A817C A77425F91E6318FCD2E6D6364>

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

More information

PowerPoint Presentation

PowerPoint Presentation 付録 2 2 次元アフィン変換 直交変換 たたみ込み 1.2 次元のアフィン変換 座標 (x,y ) を (x,y) に移すことを 2 次元での変換. 特に, 変換が と書けるとき, アフィン変換, アフィン変換は, その 1 次の項による変換 と 0 次の項による変換 アフィン変換 0 次の項は平行移動 1 次の項は座標 (x, y ) をベクトルと考えて とすれば このようなもの 2 次元ベクトルの線形写像

More information

Microsoft Word - 補論3.2

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

More information

ボルツマンマシンの高速化

ボルツマンマシンの高速化 1. はじめに ボルツマン学習と平均場近似 山梨大学工学部宗久研究室 G04MK016 鳥居圭太 ボルツマンマシンは学習可能な相互結合型ネットワー クの代表的なものである. ボルツマンマシンには, 学習のための統計平均を取る必要があり, 結果を求めるまでに長い時間がかかってしまうという欠点がある. そこで, 学習の高速化のために, 統計を取る2つのステップについて, 以下のことを行う. まず1つ目のステップでは,

More information

データ解析

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

More information

微分方程式による現象記述と解きかた

微分方程式による現象記述と解きかた 微分方程式による現象記述と解きかた 土木工学 : 公共諸施設 構造物の有用目的にむけた合理的な実現をはかる方法 ( 技術 ) に関する学 橋梁 トンネル ダム 道路 港湾 治水利水施設 安全化 利便化 快適化 合法則的 経済的 自然および人口素材によって作られた 質量保存則 構造物の自然的な性質 作用 ( 外力による応答 ) エネルギー則 の解明 社会的諸現象のうち マスとしての移動 流通 運動量則

More information

DVIOUT-SS_Ma

DVIOUT-SS_Ma 第 章 微分方程式 ニュートンはリンゴが落ちるのを見て万有引力を発見した という有名な逸話があります 無重力の宇宙船の中ではリンゴは落ちないで静止していることを考えると 重力が働くと始め静止しているものが動き出して そのスピードはどんどん大きくなる つまり速度の変化が現れることがわかります 速度は一般に時間と共に変化します 速度の瞬間的変化の割合を加速度といい で定義しましょう 速度が変化する, つまり加速度がでなくなるためにはその原因があり

More information

1999年度 センター試験・数学ⅡB

1999年度 センター試験・数学ⅡB 99 センター試験数学 Ⅱ 数学 B 問題 第 問 ( 必答問題 ) [] 関数 y cos3x の周期のうち正で最小のものはアイウ 解答解説のページへ 0 x 360 のとき, 関数 y cos3x において, y となる x はエ個, y となる x はオ 個ある また, y sin x と y cos3x のグラフより, 方程式 sin x cos3x は 0 x 360のときカ個の解をもつことがわかる

More information

040402.ユニットテスト

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

More information

航空機の運動方程式

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

More information

学習指導要領

学習指導要領 (1) 数と式 ア数と集合 ( ア ) 実数数を実数まで拡張する意義を理解し 簡単な無理数の四則計算をすること 自然数 整数 有理数 無理数 実数のそれぞれの集 合について 四則演算の可能性について判断できる ( 例 ) 下の表において それぞれの数の範囲で四則計算を考えるとき 計算がその範囲で常にできる場合には を 常にできるとは限らない場合には を付けよ ただし 除法では 0 で割ることは考えない

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

学習指導要領

学習指導要領 () いろいろな式 学習指導要領ア式と証明 ( ア ) 整式の乗法 除法 分数式の計算三次の乗法公式及び因数分解の公式を理解し それらを用いて式の展開や因数分解をすること また 整式の除法や分数式の四則計算について理解し 簡単な場合について計算をすること 都立清瀬高校学力スタンダード 変数の 次式の展開や因数分解ができる ( 例 ) 次の式を展開せよ y ( 例 ) 次の式を因数分解せよ 8 7y

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

DVIOUT

DVIOUT 最適レギュレータ 松尾研究室資料 第 最適レギュレータ 節時不変型無限時間最適レギュレータ 状態フィードバックの可能な場合の無限時間問題における最適レギュレータについて確定系について説明する. ここで, レギュレータとは状態量をゼロにするようなコントローラのことである. なぜ, 無限時間問題のみを述べるかという理由は以下のとおりである. 有限時間の最適レギュレータ問題の場合の最適フィードバックゲインは微分方程式の解から構成される時間関数として表現される.

More information

Microsoft PowerPoint - 応用数学8回目.pptx

Microsoft PowerPoint - 応用数学8回目.pptx 8- 次の 標 : 複素関数 ( 正則関数 ) の積分 8- 実関数 : 定積分 講義内容 名城 学理 学部材料機能 学科岩 素顕 複素関数の積分について学ぶ 複素関数の積分 複素積分の性質 周回積分の解法 コーシーの積分定理 コーシーの積分公式 グルサーの公式 - 定義 複素関数の積分 : 線積分 今後の内容 区分的に滑らかな曲線に沿って複素関数の積分を計算する 複素関数の積分の性質に関して議論する

More information

2017年度 長崎大・医系数学

2017年度 長崎大・医系数学 07 長崎大学 ( 医系 ) 前期日程問題 解答解説のページへ 以下の問いに答えよ () 0 のとき, si + cos の最大値と最小値, およびそのときの の値 をそれぞれ求めよ () e を自然対数の底とする > eの範囲において, 関数 y を考える この両 辺の対数を について微分することにより, y は減少関数であることを示せ また, e< < bのとき, () 数列 { } b の一般項が,

More information

学習指導要領

学習指導要領 (1) 数と式 ア整式 ( ア ) 式の展開と因数分解二次の乗法公式及び因数分解の公式の理解を深め 式を多面的にみたり目的に応じて式を適切に変形したりすること (ax b)(cx d) acx (ad bc)x bd などの基本的な公式を活用して 二次式の展開や因数分解ができる また 式の置き換えや一文字に着目するなどして 展開 因数分解ができる ( 例 ) 次の問に答えよ (1) (3x a)(4x

More information

Microsoft PowerPoint - DA2_2017.pptx

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

More information

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

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

More information

2018年度 2次数学セレクション(微分と積分)

2018年度 2次数学セレクション(微分と積分) 08 次数学セレクション問題 [ 東京大 ] > 0 とし, f = x - x とおく () x で f ( x ) が単調に増加するための, についての条件を求めよ () 次の 条件を満たす点 (, b) の動きうる範囲を求め, 座標平面上に図示せよ 条件 : 方程式 f = bは相異なる 実数解をもつ 条件 : さらに, 方程式 f = bの解を < < とすると > である -- 08 次数学セレクション問題

More information

学習指導要領

学習指導要領 (1) 数と式 学習指導要領ア数と集合 ( ア ) 実数数を実数まで拡張する意義を理解し 簡単な無理数の四則計算をすること 千早高校学力スタンダード 自然数 整数 有理数 無理数の用語の意味を理解す る ( 例 ) 次の数の中から自然数 整数 有理 数 無理数に分類せよ 3 3,, 0.7, 3,,-, 4 (1) 自然数 () 整数 (3) 有理数 (4) 無理数 自然数 整数 有理数 無理数の包含関係など

More information

Microsoft PowerPoint - mp13-07.pptx

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

More information

パソコンシミュレータの現状

パソコンシミュレータの現状 第 2 章微分 偏微分, 写像 豊橋技術科学大学森謙一郎 2. 連続関数と微分 工学において物理現象を支配する方程式は微分方程式で表されていることが多く, 有限要素法も微分方程式を解く数値解析法であり, 定式化においては微分 積分が一般的に用いられており. 数学の基礎知識が必要になる. 図 2. に示すように, 微分は連続な関数 f() の傾きを求めることであり, 微小な に対して傾きを表し, を無限に

More information

Microsoft PowerPoint - H20第10回最短経路問題-掲示用.ppt

Microsoft PowerPoint - H20第10回最短経路問題-掲示用.ppt 最短経路問題とは プログラミング言語 I 第 0 回 から終点へ行く経路が複数通りある場合に 最も短い経路を見つける問題 経路の短さの決め方によって様々な応用 最短経路問題 埼玉大学工学部電気電子システム工学科伊藤和人 最短経路問題の応用例 カーナビゲーション 現在地から目的地まで最短時間のルート 経路 = 道路 交差点において走る道路を変更してもよい 経路の短さ = 所要時間の短さ 鉄道乗り換え案内

More information

vecrot

vecrot 1. ベクトル ベクトル : 方向を持つ量 ベクトルには 1 方向 2 大きさ ( 長さ ) という 2 つの属性がある ベクトルの例 : 物体の移動速度 移動量電場 磁場の強さ風速力トルクなど 2. ベクトルの表現 2.1 矢印で表現される 矢印の長さ : ベクトルの大きさ 矢印の向き : ベクトルの方向 2.2 2 個の点を用いて表現する 始点 () と終点 () を結ぶ半直線の向き : ベクトルの方向

More information

経済数学演習問題 2018 年 5 月 29 日 I a, b, c R n に対して a + b + c 2 = a 2 + b 2 + c 2 + 2( a, b) + 2( b, c) + 2( a, c) が成立することを示しましょう.( 線型代数学 教科書 13 ページ 演習 1.17)

経済数学演習問題 2018 年 5 月 29 日 I a, b, c R n に対して a + b + c 2 = a 2 + b 2 + c 2 + 2( a, b) + 2( b, c) + 2( a, c) が成立することを示しましょう.( 線型代数学 教科書 13 ページ 演習 1.17) 経済数学演習問題 8 年 月 9 日 I a, b, c R n に対して a + b + c a + b + c + a, b + b, c + a, c が成立することを示しましょう. 線型代数学 教科書 ページ 演習.7 II a R n がすべての x R n に対して垂直, すなわち a, x x R n が成立するとします. このとき a となることを示しましょう. 線型代数学 教科書

More information

2010年度 筑波大・理系数学

2010年度 筑波大・理系数学 00 筑波大学 ( 理系 ) 前期日程問題 解答解説のページへ f( x) x ax とおく ただしa>0 とする () f( ) f() となるa の範囲を求めよ () f(x) の極小値が f ( ) 以下になる a の範囲を求めよ () x における f(x) の最小値をa を用いて表せ -- 00 筑波大学 ( 理系 ) 前期日程問題 解答解説のページへ つの曲線 C : y six ( 0

More information

固体物理2018-1NKN.key

固体物理2018-1NKN.key , `, m`, m s ` ` apple m` apple ` m` m s m s ± E H m x () () () A si x A si x () () () () H m x () aaac6ichve9bxqxejciriboeglooqufipmfcakpagacop8cemkbhy+yhv7vxvafhbldsrfeqefge+bk/agk/asumkgfmzuruq+bmxqpw+e58m7sivwlhcjjz/uwxkfhrumjq/fmkpowzsv8zmsjtprgraxqvgmfvbyjvrzgkesre9z/++obrixg5tvhxtrhiwahfqlv9ea8k5tjopqtyfsqygtfyyztithg6gq9bp5qo89ctuamhkjq7roxw+ykzxbsfocupwtuwztmfygqv6zatapsggiyaoqrkwqqhxbcgxjgicyociwicvqmphtqgaeuuswcgeylimgftmytjbkwhsxo8svrjuhzthfq9rwym58o8iifkk/lmvpff6lihr5epuj9bu9urp/+ritfbepvh9c+zxtgutgrwtgslpwub6wevk9xhkpuvlajh+9+sifmetqmeprdmv/yhfdg/hvfbgsjyaguwf+ut8igyqzmyr7v+yeswygibpfamvtvejc/9/6evz9k9bscwvomp/x5bvrq

More information

Chap2

Chap2 逆三角関数の微分 Arcsin の導関数を計算する Arcsin I. 初等関数の微積分 sin [, ], [π/, π/] cos sin / (Arcsin ) 計算力の体力をつけよう π/ π/ E. II- 次の関数の導関数を計算せよ () Arccos () Arctan E. I- の解答 不定積分あれこれ () Arccos n log C C (n ) n e e C log (log

More information

2014年度 千葉大・医系数学

2014年度 千葉大・医系数学 04 千葉大学 ( 医系 ) 前期日程問題 解答解説のページへ 袋の中に, 赤玉が 3 個, 白玉が 7 個が入っている 袋から玉を無作為に つ取り出し, 色を確認してから, 再び袋に戻すという試行を行う この試行を N 回繰り返したときに, 赤玉を A 回 ( ただし 0 A N) 取り出す確率を p( N, A) とする このとき, 以下の問いに答えよ () 確率 p( N, A) を N と

More information

様々なミクロ計量モデル†

様々なミクロ計量モデル† 担当 : 長倉大輔 ( ながくらだいすけ ) この資料は私の講義において使用するために作成した資料です WEB ページ上で公開しており 自由に参照して頂いて構いません ただし 内容について 一応検証してありますが もし間違いがあった場合でもそれによって生じるいかなる損害 不利益について責任を負いかねますのでご了承ください 間違いは発見次第 継続的に直していますが まだ存在する可能性があります 1 カウントデータモデル

More information

2015年度 金沢大・理系数学

2015年度 金沢大・理系数学 05 金沢大学 ( 理系 ) 前期日程問題 解答解説のページへ四面体 OABC において, 3 つのベクトル OA, OB, OC はどの つも互いに垂直で あり, h > 0 に対して, OA, OB, OC h とする 3 点 O, A, B を通る平面上の点 P は, CP が CA と CB のどちらとも垂直となる点であるとする 次の問いに答えよ () OP OA + OB とするとき, と

More information

" 01 JJM 予選 4 番 # 四角形 の辺 上に点 があり, 直線 と は平行である.=,=, =5,=,= のとき, を求めよ. ただし,XY で線分 XY の長さを表すものとする. 辺 と辺 の延長線の交点を, 辺 と辺 の延長線の交点を G とする. 5 四角形 は直線 に関して線対称な

 01 JJM 予選 4 番 # 四角形 の辺 上に点 があり, 直線 と は平行である.=,=, =5,=,= のとき, を求めよ. ただし,XY で線分 XY の長さを表すものとする. 辺 と辺 の延長線の交点を, 辺 と辺 の延長線の交点を G とする. 5 四角形 は直線 に関して線対称な 1 " 数学発想ゼミナール # ( 改題 ) 直径を とする半円周上に一定の長さの弦がある. この弦の中点と, 弦の両端の各点から直径 への垂線の足は三角形をつくる. この三角形は二等辺三角形であり, かつその三角形は弦の位置にかかわらず相似であることを示せ. ( 証明 ) 弦の両端を X,Y とし,M を線分 XY の中点,, をそれぞれ X,Y から直径 への垂線の足とする. また,M の直径

More information

平成 年 月 7 日 ( 土 第 75 回数学教育実践研究会アスティ 45 ビル F セミナールーム A 札幌医科大学 年 P ab, を正の定数とする 平面上において ( a, を中心とする円 Q 4 C と (, b を中心とする円 C が 原点 O で外接している また P を円 C 上の点と

平成 年 月 7 日 ( 土 第 75 回数学教育実践研究会アスティ 45 ビル F セミナールーム A 札幌医科大学 年 P ab, を正の定数とする 平面上において ( a, を中心とする円 Q 4 C と (, b を中心とする円 C が 原点 O で外接している また P を円 C 上の点と 平成 年 月 7 日 ( 土 第 75 回数学教育実践研究会アスティ 45 ビル F セミナールーム 微分積分の拡張 変数関数問題へのアプローチ 予選決勝優勝法からラグランジュ未定乗数法 松本睦郎 ( 札幌北高等学校 変数関数の最大値 最小値に関する問題には多様なアプローチ法がある 文字を固定した 予選決勝優勝法, 計算のみで解法する 文字消去法, 微分積分を利用した ラグランジュ未定乗数法 がある

More information

ディジタル信号処理

ディジタル信号処理 ディジタルフィルタの設計法. 逆フィルター. 直線位相 FIR フィルタの設計. 窓関数法による FIR フィルタの設計.5 時間領域での FIR フィルタの設計 3. アナログフィルタを基にしたディジタル IIR フィルタの設計法 I 4. アナログフィルタを基にしたディジタル IIR フィルタの設計法 II 5. 双 次フィルタ LI 離散時間システムの基礎式の証明 [ ] 4. ] [ ]*

More information

<4D F736F F D2094F795AA95FB92F68EAE82CC89F082AB95FB E646F63>

<4D F736F F D2094F795AA95FB92F68EAE82CC89F082AB95FB E646F63> 力学 A 金曜 限 : 松田 微分方程式の解き方 微分方程式の解き方のところが分からなかったという声が多いので プリントにまとめます 数学的に厳密な話はしていないので 詳しくは数学の常微分方程式を扱っているテキストを参照してください また os s は既知とします. 微分方程式の分類 常微分方程式とは 独立変数 と その関数 その有限次の導関数 がみたす方程式 F,,, = のことです 次までの導関数を含む方程式を

More information

学習指導要領

学習指導要領 (1) 数と式 ア数と集合 ( ア ) 実数数を実数まで拡張する意義を理解し 簡単な無理数の四則計算をすること 自然数 整数 有理数 無理数の包含関係など 実数 の構成を理解する ( 例 ) 次の空欄に適当な言葉をいれて, 数の集合を表しなさい ア イ 無理数 整数 ウ 無理数の加法及び減法 乗法公式などを利用した計 算ができる また 分母だけが二項である無理数の 分母の有理化ができる ( 例 1)

More information

喨微勃挹稉弑

喨微勃挹稉弑 == 全微分方程式 == 全微分とは 変数の関数 z=f(, ) について,, の増分を Δ, Δ とするとき, z の増分 Δz は Δz z Δ+ z Δ で表されます. この式において, Δ 0, Δ 0 となる極限を形式的に dz= z d+ z d (1) で表し, dz を z の全微分といいます. z は z の に関する偏導関数で, を定数と見なし て, で微分したものを表し, 方向の傾きに対応します.

More information

計算幾何学入門 Introduction to Computational Geometry

計算幾何学入門 Introduction to  Computational Geometry テーマ 6: ボロノイ図とデローネイ 三角形分割 ボロノイ図, デローネイ三角形分割 ボロノイ図とは 平面上に多数の点が与えられたとき, 平面をどの点に最も近いかという関係で分割したものをボロノイ図 (Voronoi diagram) という. 2 点だけの場合 2 点の垂直 2 等分線による分割 3 点の場合 3 点で決まる三角形の外接円の中心から各辺に引いた垂直線による分割線 2 点からの等距離線

More information

< 中 3 分野例題付き公式集 > (1)2 の倍数の判定法は 1 の位が 0 又は偶数 ( 例題 )1~5 までの 5 つの数字を使って 3 ケタの数をつくるとき 2 の倍数は何通りできるか (2)5 の倍数の判定法は 1 の位が 0 又は 5 ( 例題 )1~9 までの 9 個の数字を使って 3

< 中 3 分野例題付き公式集 > (1)2 の倍数の判定法は 1 の位が 0 又は偶数 ( 例題 )1~5 までの 5 つの数字を使って 3 ケタの数をつくるとき 2 の倍数は何通りできるか (2)5 の倍数の判定法は 1 の位が 0 又は 5 ( 例題 )1~9 までの 9 個の数字を使って 3 () の倍数の判定法は の位が 0 又は偶数 ~ までの つの数字を使って ケタの数をつくるとき の倍数は何通りできるか () の倍数の判定法は の位が 0 又は ~9 までの 9 個の数字を使って ケタの数をつくるとき の倍数は何通りできるか () の倍数の判定法は 下 ケタが 00 又は の倍数 ケタの数 8 が の倍数となるときの 最小の ケタの数は ( 解 ) 一の位の数は の 通り 十の位は一の位の数以外の

More information

数学 ⅡB < 公理 > 公理を論拠に定義を用いて定理を証明する 1 大小関係の公理 順序 (a > b, a = b, a > b 1 つ成立 a > b, b > c a > c 成立 ) 順序と演算 (a > b a + c > b + c (a > b, c > 0 ac > bc) 2 図

数学 ⅡB < 公理 > 公理を論拠に定義を用いて定理を証明する 1 大小関係の公理 順序 (a > b, a = b, a > b 1 つ成立 a > b, b > c a > c 成立 ) 順序と演算 (a > b a + c > b + c (a > b, c > 0 ac > bc) 2 図 数学 Ⅱ < 公理 > 公理を論拠に定義を用いて定理を証明する 大小関係の公理 順序 >, =, > つ成立 >, > > 成立 順序と演算 > + > + >, > > 図形の公理 平行線の性質 錯角 同位角 三角形の合同条件 三角形の合同相似 量の公理 角の大きさ 線分の長さ < 空間における座漂とベクトル > ベクトルの演算 和 差 実数倍については 文字の計算と同様 ベクトルの成分表示 平面ベクトル

More information

Microsoft PowerPoint - 第3回2.ppt

Microsoft PowerPoint - 第3回2.ppt 講義内容 講義内容 次元ベクトル 関数の直交性フーリエ級数 次元代表的な対の諸性質コンボリューション たたみこみ積分 サンプリング定理 次元離散 次元空間周波数の概念 次元代表的な 次元対 次元離散 次元ベクトル 関数の直交性フーリエ級数 次元代表的な対の諸性質コンボリューション たたみこみ積分 サンプリング定理 次元離散 次元空間周波数の概念 次元代表的な 次元対 次元離散 ベクトルの直交性 3

More information

相加平均 相乗平均 調和平均が表す比 台形 の上底 下底 の長さをそれぞれ, とするとき 各平均により 台形の高さ はどのように比に分けられるだろうか 相乗平均は 相似な つの台形になるから台形の高さ を : の 比に分ける また 相加平均は は : の比に分けます 調和平均は 対角線 と の交点を

相加平均 相乗平均 調和平均が表す比 台形 の上底 下底 の長さをそれぞれ, とするとき 各平均により 台形の高さ はどのように比に分けられるだろうか 相乗平均は 相似な つの台形になるから台形の高さ を : の 比に分ける また 相加平均は は : の比に分けます 調和平均は 対角線 と の交点を 台形に潜むいろいろな平均 札幌旭丘高校中村文則 台形に調和平均 相加平均をみる 右図の台形 において = = とする の長さを, を用いて表してみよう = x = y = c とすると であることから : = : より c y = x + y であることから : = : より c x = x + y を辺々加えると x + y c + = より + = x + y c となる ここで = = c =

More information

Microsoft PowerPoint - 測量学.ppt [互換モード]

Microsoft PowerPoint - 測量学.ppt [互換モード] 8/5/ 誤差理論 測定の分類 性格による分類 独立 ( な ) 測定 : 測定値がある条件を満たさなければならないなどの拘束や制約を持たないで独立して行う測定 条件 ( 付き ) 測定 : 三角形の 3 つの内角の和のように, 個々の測定値間に満たすべき条件式が存在する場合の測定 方法による分類 直接測定 : 距離や角度などを機器を用いて直接行う測定 間接測定 : 求めるべき量を直接測定するのではなく,

More information

Chap2.key

Chap2.key . f( ) V (V V ) V e + V e V V V V ( ) V V ( ) E. - () V (0 ) () V (0 ) () V (0 ) (4) V ( ) E. - () V (0 ) () V (0 ) O r θ ( ) ( ) : (r θ) : { r cos θ r sn θ { r + () V (0 ) (4) V ( ) θ θ arg( ) : π π

More information

Math-quarium 練習問題 + 図形の性質 線分 は の二等分線であるから :=:=:=: よって = = = 線分 は の外角の二等分線であるから :=:=:=: よって :=: したがって == 以上から =+=+= 右の図において, 点 は の外心である α,βを求めよ α β 70

Math-quarium 練習問題 + 図形の性質 線分 は の二等分線であるから :=:=:=: よって = = = 線分 は の外角の二等分線であるから :=:=:=: よって :=: したがって == 以上から =+=+= 右の図において, 点 は の外心である α,βを求めよ α β 70 Math-quarium 練習問題 + 図形の性質 図形の性質 線分 に対して, 次の点を図示せよ () : に内分する点 () : に外分する点 Q () 7: に外分する点 R () 中点 M () M () Q () () R 右の図において, 線分の長さ を求めよ ただし,R//Q,R//,Q=,=6 とする Q R 6 Q から,:=:6=: より :=: これから,R:=: より :6=:

More information

Microsoft PowerPoint - DA2_2018.pptx

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

More information

<4D F736F F D2097CD8A7793FC96E582BD82ED82DD8A E6318FCD2E646F63>

<4D F736F F D2097CD8A7793FC96E582BD82ED82DD8A E6318FCD2E646F63> - 第 章たわみ角法の基本式 ポイント : たわみ角法の基本式を理解する たわみ角法の基本式を梁の微分方程式より求める 本章では たわみ角法の基本式を導くことにする 基本式の誘導法は各種あるが ここでは 梁の微分方程式を解いて基本式を求める方法を採用する この本で使用する座標系は 右手 右ネジの法則に従った座標を用いる また ひとつの部材では 図 - に示すように部材の左端の 点を原点とし 軸線を

More information

<4D F736F F D FCD B90DB93AE96402E646F63>

<4D F736F F D FCD B90DB93AE96402E646F63> 7 章摂動法講義のメモ 式が複雑なので 黒板を何度も修正したし 間違ったことも書いたので メモを置きます 摂動論の式の導出無摂動系 先ず 厳密に解けている Schrödiger 方程式を考える,,,3,... 3,,,3,... は状態を区別する整数であり 状態 はエネルギー順に並んでいる 即ち は基底状態 は励起状態である { m } は相互に規格直交条件が成立する k m k mdx km k

More information

計算機シミュレーション

計算機シミュレーション . 運動方程式の数値解法.. ニュートン方程式の近似速度は, 位置座標 の時間微分で, d と定義されます. これを成分で書くと, d d li li とかけます. 本来は が の極限をとらなければいけませんが, 有限の小さな値とすると 秒後の位置座標は速度を用いて, と近似できます. 同様にして, 加速度は, 速度 の時間微分で, d と定義されます. これを成分で書くと, d d li li とかけます.

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

大気環境シミュレーション

大気環境シミュレーション 第 3 回 (Q) 各自 eelを用いて 次の漸化式 + = の解の初期値依存性を調べよ.は50まで () 0 =.0 () 0 =.5 (3) 0 =.0 締切 04 年 月 6 日 ( 月 ) 夕方まで 提出先 347 室 オーバーフロー失敗ゴメンなさい (Q) 各自 eelを用いて 次の漸化式 + = の解の初期値依存性を調べよ.は50まで () 0 =.330 () 0 =.33 (3) 0

More information