Information Theory

Size: px
Start display at page:

Download "Information Theory"

Transcription

1 前回の復習 情報をコンパクトに表現するための符号化方式を考える 情報源符号化における基礎的な性質 一意復号可能性 瞬時復号可能性 クラフトの不等式 2 l l M 1 ハフマン符号の構成法 (2 元符号の場合 ) D. Huffman 1

2 前回の練習問題 : ハフマン符号 符号木を再帰的に構成し, 符号を作る A B C D E F 確率 符号語 A B C D E F 平均符号語長は = 2

3 今日の講義の方向性 情報源符号が目指すべきもの 瞬時復号可能性 クラフトの不等式 2 l l M 1 平均符号語長の最小化 この制約の範囲内で, 平均符号語長 M p i l i i=1 を最小化することを考える 3

4 あらすじ 1. 平均符号語長の下界を示す 2. シャノン ファノ符号の紹介 下界に迫る 平均符号語長を持つ符号 ハフマン符号との関係 3. 情報源の拡大と情報源符号化定理 Robert Fano

5 最初の目標 前回からの お約束 定常無記憶情報源 S の発生する記号を一個ずつ符号化 記号は M 通り, 各記号の発生確率は p 1,, p M 瞬時復号可能な符号を考え, 平均符号語長を L で表す 補題 1: 平均符号語長は必ず L H 1 (S) となる シャノンの補助定理 (2 回目の講義で紹介 ) を利用して証明 q q M 1 を満たす非負数 q i に対し, M M p i log 2 q i p i log 2 p i i=1 i=1 5

6 補題 1 の証明 補題 1: 平均符号語長は必ず L H 1 (S) となる 符号語の長さを l 1,, l M とし,q i = 2 l i とする l i = log 2 q i M L = p i l i i=1 M = p i log 2 q i i=1 q q M = 2 l l M 1 ( クラフトの不等式 ) M i=1 ( シャノンの補助定理 ) p i log 2 p i = H 1 (S) 6

7 補題 1 の意味するところ 補題 1: 平均符号語長は必ず L H 1 (S) となる 情報源 S の発生する記号を符号化するためには, 必ず H 1 S ビットの平均符号語長が必要 どれだけ高速なコンピュータや, どれだけスゴイ天才が 将来出現しても,H 1 (S) ビットの壁を超えることはできない エントロピー... 統計的に導かれた 情報理論的な量 平均符号語長の下界... データ圧縮の限界という 操作的な量... 情報理論は, 情報に関する 普遍的な物理法則 を与える 7

8 下界への到達可能性 補題 1: 平均符号語長は必ず L H 1 (S) となる H 1 (S) は, あくまでも平均符号語長の 下界 次の疑問... どこまで H 1 (S) に迫ることができるのか? 補題 2: 平均符号語長が L < H 1 (S) + 1 となる符号を構成可能 シャノンとファノが, 独立に発見した符号の構成法 シャノン ファノ符号 ( 本講義では, シャノン ファノ符号のアイデア部分だけを説明 ) 8

9 補題 2 の証明 補題 2: 平均符号語長が L < H 1 (S) + 1 となる符号を構成可能 符号の構成方法 : x x 以上の整数 step 1: l i = log 2 p i として, 符号語の長さを決定する step 2: 深さ l 1,, l M に葉を持つ符号木を構成する step 3: 符号木から符号語を決定する log 2 p i log 2 p i 確認すべき事項 : 本当に符号木が構成できるのか? 平均符号語長は? p i 9

10 補題 2 の証明 ( 続 ) 本当に符号木が構成できるのか? = l i はクラフトの不等式を満たすのか? l i = log 2 p i より l i log 2 p i さらに変形すると,2 l i 2 log 2 p i = p i 2 l l M p p M = 1 平均符号語長は? l i < log 2 p i + 1であることを利用する : M M L = p i l i < p i ( log 2 p i + 1) i=1 i=1 M M = p i log 2 p i + p i = H 1 S + 1 i=1 i=1 10

11 補題 2 に関する補足 前スライドの証明では... 符号木以降の議論を省略 シャノン ファノ符号... 具体的な符号木の作り方までを規定確率を 2 進数表記したときの, 小数部に着目 証明のために構成された符号 の色合いが強い 一番効率が良い わけではないたとえば,M = 2, p 1 = 0.9, p 2 = 0.1の場合... シャノン ファノ符号では,l 1 = 1, l 2 = 4 ハフマン符号では,l 1 = 1, l 2 = 1 11

12 補題 1+2 補題 1: 平均符号語長は必ず L H 1 (S) となる どんな符号を使っても越えられない壁 補題 2: 平均符号語長が L < H 1 (S) + 1 となる符号を構成可能 シャノン ファノ符号を使えば, 下界に迫ることが可能 ハフマン符号の位置づけは? vs. 12

13 ハフマン符号の最適性 最適符号 = 平均符号語長を最小にする瞬時符号可能符号 定理 : ハフマン符号は最適符号である... 予備的な補題 + 数学的帰納法で証明する 補題 : ハフマン符号の符号木, 最適符号の符号木とも, 確率最小の 2 記号は, 最も深いレベルに兄弟として存在する... 背理法で証明可能 ( 証明略 ) もし, ここの確率が小さければ... 子が 1 個の節点は存在しないはず より深いところと交換して, 平均符号語長の削減が可能 13

14 証明 : ハフマン符号は最適符号である 記号数 M に関する帰納法で証明する M = 1のとき... 自明 M = N 以下で定理の成立を仮定,M = N + 1の場合を考える ハフマン符号の符号木 L 平均符号語長 L L opt のはず... L opt 最適符号の符号木 p N p N+1 p N p N+1 記号数 N + 1 記号数 N 確率最小の 2 記号を併合 L (p N + p N+1 ) L opt (p N + p N+1 ) p N + p N+1 これより L L opt したがって L = L opt p N + p N+1 14

15 補題 1+2, 改良版 補題 1: 平均符号語長は必ず L H 1 (S) となる どんな符号を使っても越えられない壁 補題 2: 平均符号語長が L < H 1 (S) + 1 となる符号を構成可能 ハフマン符号を使えば, 下界に迫ることが可能 H 1 S L opt = L Huffman L Shannon Fano < H 1 S

16 2 ページの例で確認 符号木を再帰的に構成し, 符号を作る 平均符号語長は L Huffman = 2.5 エントロピーは H S = 0.3 log log log = 2.45 A B C D E F 確率 符号語 H 1 S L opt = L Huffman L Shannon Fano < H 1 S ?

17 シャノン ファノ符号の場合 l i = log 2 p i log 2 p i p i A B C D E F 確率 l i 符号語 vs. ハフマン L Shannon Fano = = 3.0 H 1 S L opt = L Huffman L Shannon Fano < H 1 S

18 ここまでのまとめ 補題 1: 平均符号語長は必ず L H 1 (S) となる どんな符号を使っても越えられない壁 補題 2: 平均符号語長が L < H 1 (S) + 1 となる符号を構成可能 ハフマン符号を使えば, 下界に迫ることが可能 H 1 S L opt = L Huffman L Shannon Fano < H 1 S + 1 この +1 が気になる 18

19 お約束 を破る : 符号化の単位とブロック化 1 個の記号を,1 個の符号語に変換する A 0 平均符号語長は, 必ず 1 以上となる 2 元情報源の符号化を考えても, 意味がない B 10 A 0 C 11 C 11 A 0 記号確率 A 0.8 B 0.2 平均符号語長 C C 複数の記号をまとめて符号化 ( ブロック符号化 ) すると... 1 記号あたりの平均符号長を1 以下にできるかも... 2 元情報源の符号化にもチャンスが... A B A C C A

20 ブロック符号化のイメージ 記号の系列 ABCBCBBCAA... ブロック化 ブロック化された記号の系列 AB CBC BB CAA... ハフマン符号化 符号語系列 ( 実際には, 符号語の間のスペースはナシ...) 20

21 ブロック符号化の例 (2-1) A B 確率 符号語 0 1 平均符号語長は = 1.0 AA AB BA BB 確率 符号語 長さ2のブロックを考える AAの発生確率 = = 平均符号語長は = 1.56 記号 1 個当たりでは,1.56 / 2 = 元情報源でも, 効率改善 21

22 ブロック符号化の例 (2-2) AAA AAB ABA ABB BAA BAB BBA BBB 確率 符号語 ブロック長を大きくすると, 1 記号あたり平均符号語長は小さくなる ( 効率が良くなる ) 長さ 3 のブロックを考える AAA の発生確率 = = 平均符号語長は = 記号 1 個当たりでは,2.184 / 3 = ブロック長 : 1 記号あたり平均符号語長 : 22

23 ブロック符号の平均符号長 ブロック長を大きくすると,1 記号あたり平均符号語長は小さくなる... ただの偶然? n 個単位でブロック化した記号 =n 次拡大情報源 S n の記号 1 個 記号を 1 個ずつ符号化する 場合の 議論が適用できる ブロック長 n のときの平均符号語長を L n とすると 平均符号語長は必ず L n H 1 (S n ) となる平均符号語長が L n < H 1 S n + 1 となる符号を構成可能 23

24 不等式の変形 H 1 S n L n < H 1 S n + 1 n で割る H 1 S n n L n n < H 1 S n + 1 n H 1 S n lim n n 極限を取る L n lim n n < lim H 1 S n + 1 n n 極限エントロピーで表現する H S L n n < H S + ε 1 記号あたりの平均符号語長 24

25 情報源符号化定理 情報源 S に対し, 瞬時復号可能な符号を構成する 構成した符号の,1 記号あたりの平均符号長を L とする H S L n n < H S + ε シャノンの情報源符号化定理 逆定理 L < H(S) であるような符号は存在しない 順定理 L が H(S) に限りなく近い符号を構成することができる 25

26 情報源符号化定理の意味するところ 逆定理 L < H(S) であるような符号は存在しない どれだけブロック長を大きくしても, エントロピーの壁は 越えられない 順定理 L が H(S) に限りなく近い符号を構成することができる ブロック長を大きく設定し, ハフマン符号を使えば, いくらでも下界に近づくことができる A B 確率 符号語 0 1 H(S) = ブロック長 : 一通報あたり平均符号長 : ε 26

27 別視点からの説明 ブロック化すると, どうして効率が良くなるか? 理想的な符号語長は実数値 l i = log 2 p i p 1 = 0.8, p 2 = 0.2 の場合, 理想的な符号語の長さは l l 2 min s.t. 2 l l 2 1 l 1 = log l 2 = log 現実には, 符号語長は整数値しか許されない シャノン ファノ符号の場合,l i = log 2 p i 符号語長は, 理想的な場合の log 2 p i log 2 p i 倍になる 27

28 別視点からの説明 ( 続 ) 確率値が大きくなると, 理想と現実のギャップが顕著に log 2 p i log 2 p i 0 p i ブロック化すると... 各記号の発生確率が比較的小さくなる 理想と現実の間に多少ギャップがあっても, 1 記号あたり で考えるために n で割れば, 影響は小さくなる 28

29 本日のまとめ シャノンの情報源符号化定理 逆定理 L < H(S) であるような符号は存在しない 順定理 LがH(S) に限りなく近い符号を構成することができる情報源をブロック化し, ハフマン符号を使えばよい 理論的には完結しているが, 実用上の問題は残る符号化 復号の ( 時間 空間 ) 計算量削減前提条件の緩和 ( 確率分布が未知のケース etc.) 可逆でない 情報源符号化 続きは,III 期の 符号理論 で... 29

30 練習問題 ハフマン符号を構成するプログラムを作成せよ さらに, 拡大情報源に対して利用できるよう改良せよ 30

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

Information Theory

Information Theory 前回の復習 講義の概要 chapter 1: 情報を測る... エントロピーの定義 確率変数 X の ( 一次 ) エントロピー M H 1 (X) = p i log 2 p i (bit) i=1 M は実現値の個数,p i は i 番目の実現値が取られる確率 実現値 確率 表 裏 0.5 0.5 H 1 X = 0.5 log 2 0.5 0.5log 2 0.5 = 1bit 1 練習問題の解答

More information

untitled

untitled 2010824 1 2 1031 5251020 101 3 0.04 % 2010.8.18 0.05 % 1 0.06 % 5 0.12 % 3 0.14 % 2010.8.16 5 0.42 % 2010.7.15 25 5 0.42 % 0.426% 2010.6.29 5 0.496 % 2010.8.12 4 0.85 % 2010.8.6 10 0.900 % 2010.8.18 2.340

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

Microsoft PowerPoint - 14MDL.pptx

Microsoft PowerPoint - 14MDL.pptx オッカムの剃刀 (Occam s razor) MDL 原理 データマイニング 機械学習の仕事は データを表現するモデルを探すことだと言える 例 : ガウス混合モデル, ( 等方正規分布の ) 混合 (k means 法 ). Model vs Hypotesis では 正しいモデルとは何か? どうやって選ぶか? オッカムの剃刀 : それ以外の条件が全て同じなら, 最も単純なモデルが最良である. 人生訓としてもよかろう

More information

オートマトンと言語

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

More information

離散数学

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

More information

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

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

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

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

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

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

オートマトン 形式言語及び演習 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 1 非対称通信路の通信路容量を達成する 符号化法に関する最近の進展 東京大学大学院新領域創成科学研究科複雑理工学専攻講師本多淳也 情報理論研究会 2018/5/18 概要 2 非対称通信路の符号化 polar 符号を用いる方式 無歪み圧縮を用いた符号化法の一般的な枠組み Miyake-Muramatsuの方式 連鎖構造に基づく方式 無歪み圧縮の逆操作について 通信路符号化 3 ノイズを含む通信路を用いて情報を伝送したい

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

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

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 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

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

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

<4D F736F F D208CF68BA48C6F8DCF8A C30342C CFA90B68C6F8DCF8A7782CC8AEE967B92E8979D32288F4390B394C529332E646F63>

<4D F736F F D208CF68BA48C6F8DCF8A C30342C CFA90B68C6F8DCF8A7782CC8AEE967B92E8979D32288F4390B394C529332E646F63> 2. 厚生経済学の ( 第 ) 基本定理 2 203 年 4 月 7 日 ( 水曜 3 限 )/8 本章では 純粋交換経済において厚生経済学の ( 第 ) 基本定理 が成立することを示す なお より一般的な生産技術のケースについては 4.5 補論 2 で議論する 2. 予算集合と最適消費点 ( 完全 ) 競争市場で達成される資源配分がパレート効率的であることを示すための準備として 個人の最適化行動を検討する

More information

学習指導要領

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

More information

2-1 / 語問題 項書換え系 4.0. 準備 (3.1. 項 代入 等価性 ) 定義 3.1.1: - シグネチャ (signature): 関数記号の集合 (Σ と書く ) - それぞれの関数記号は アリティ (arity) と呼ばれる自然数が定められている - Σ (n) : アリ

2-1 / 語問題 項書換え系 4.0. 準備 (3.1. 項 代入 等価性 ) 定義 3.1.1: - シグネチャ (signature): 関数記号の集合 (Σ と書く ) - それぞれの関数記号は アリティ (arity) と呼ばれる自然数が定められている - Σ (n) : アリ 2-1 / 32 4. 語問題 項書換え系 4.0. 準備 (3.1. 項 代入 等価性 ) 定義 3.1.1: - シグネチャ (signature): 関数記号の集合 (Σ と書く ) - それぞれの関数記号は アリティ (arity) と呼ばれる自然数が定められている - Σ (n) : アリティ n を持つ関数記号からなる Σ の部分集合 例 : 群 Σ G = {e, i, } (e Σ

More information

Microsoft PowerPoint - multi_media05-dct_jpeg [互換モード]

Microsoft PowerPoint - multi_media05-dct_jpeg [互換モード] マルチメディア工学 マルチメディアデータの解析データ圧縮 : 離散コサイン変換と JPEG マルチメディア工学 : 講義計画 イントロダクション コンピュータグラフィックス (Computer Graphics: CG) マルチメディアデータの解析 佐藤嘉伸 大阪大学大学院医学系研究科放射線統合医学講座 yoshi@image.med.osaka u.ac.jp http://www.image.med.osaka

More information

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

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

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

Microsoft PowerPoint - multi_media05-dct_jpeg [互換モード]

Microsoft PowerPoint - multi_media05-dct_jpeg [互換モード] マルチメディア工学マルチメディアデータの解析データ圧縮 : 離散コサイン変換と JPEG 佐藤嘉伸 マルチメディア工学 : 講義計画 マルチメディアデータの解析 基礎数理 代表的解析手法 データ圧縮 : 離散コサイン変換 JPEG データ表現 : 形状の主成分分析 奈良先端科学技術大学院大学情報科学研究科生体医用画像研究室 yoshi@is.naist.jp http://icb lab.naist.jp/members/yoshi/

More information

2017年度 千葉大・理系数学

2017年度 千葉大・理系数学 017 千葉大学 ( 理系 ) 前期日程問題 1 解答解説のページへ n を 4 以上の整数とする 座標平面上で正 n 角形 A1A A n は点 O を中心とする半径 1 の円に内接している a = OA 1, b = OA, c = OA 3, d = OA4 とし, k = cos とおく そして, 線分 A1A3 と線分 AA4 との交点 P は線分 A1A3 を n :1に内分するとする

More information

SAP11_03

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

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

koji07-02.dvi

koji07-02.dvi 007 I II III 1,, 3, 4, 5, 6, 7 5 4 1 ε-n 1 ε-n ε-n ε-n. {a } =1 a ε N N a a N= a a

More information

Microsoft PowerPoint - mp13-07.pptx

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

More information

<4D F736F F F696E74202D2091E6824F82538FCD8CEB82E88C9F8F6F814592F990B382CC8CB4979D82BB82CC82505F D E95848D8682CC90B69

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

More information

00 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.... 0........ 0 0 0 0 0 0 0 0 0 0..0..........0 0 0 0 0 0 0 0 0 0 0.... 0........ 0 0 0 0 0 0 0 0 0 0... 0...... 0... 0 0 0 0 0 0..0 0... 0 0 0 0 0.0.....0.

More information

2014年度 千葉大・医系数学

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

More information

イントロ

イントロ 2013 DISCLOSURE CONTENTS A W A B A N K 2 0 1 3 AWA BANK REPORT 2013 AWA BANK REPORT 2013 200 192 195 194 188 150 140 147 100 120 50 80 73 61 89 0 40 0 100 90 80 60 40 47 41 36 20 0 8,000 6,000 4,000

More information

学習指導要領

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

More information

2014年度 筑波大・理系数学

2014年度 筑波大・理系数学 筑波大学 ( 理系 ) 前期日程問題 解答解説のページへ f ( x) = x x とする y = f ( x ) のグラフに点 P(, ) から引いた接線は 本あるとする つの接点 A (, f ( )), B(, f ( )), C(, f ( )) を頂点とする三角形の 重心を G とする () + +, + + および を, を用いて表せ () 点 G の座標を, を用いて表せ () 点 G

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

_KyoukaNaiyou_No.4

_KyoukaNaiyou_No.4 理科教科内容指導論 I : 物理分野 物理現象の定量的把握第 4 回 ( 実験 ) データの眺め ~ 統計学の基礎続き 統計のはなし 基礎 応 娯楽 (Best selected business books) 村平 科技連出版社 1836 円 前回の復習と今回以降の 標 東京 学 善 郎 Web サイトより データ ヒストグラム 代表値 ( 平均値 最頻値 中間値 ) 分布の散らばり 集団の分布

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

2018年度 筑波大・理系数学

2018年度 筑波大・理系数学 筑波大学 ( 理系 ) 前期日程問題 解答解説のページへ < < とする 放物線 上に 点 (, ), A (ta, ta ), B( - ta, ta ) をとる 三角形 AB の内心の 座標を p とし, 外心の 座標を q とする また, 正の実数 a に対して, 直線 a と放物線 で囲まれた図形の面積を S( a) で表す () p, q を cos を用いて表せ S( p) () S(

More information

基礎統計

基礎統計 基礎統計 第 11 回講義資料 6.4.2 標本平均の差の標本分布 母平均の差 標本平均の差をみれば良い ただし, 母分散に依存するため場合分けをする 1 2 3 分散が既知分散が未知であるが等しい分散が未知であり等しいとは限らない 1 母分散が既知のとき が既知 標準化変量 2 母分散が未知であり, 等しいとき 分散が未知であるが, 等しいということは分かっているとき 標準化変量 自由度 の t

More information

高ゼミサポSelectⅢ数学Ⅰ_解答.indd

高ゼミサポSelectⅢ数学Ⅰ_解答.indd 数と式 ⑴ 氏点00 次の式を展開せよ ( 各 6 点 ) ⑴ (a-)(a -a+) ⑵ (x+y+)(x+y-5) 次の式を因数分解せよ (⑴⑵ 各 6 点, ⑶⑷ 各 8 点 ) ⑴ x y+x -x-6y ⑵ x -x - ⑶ a +5b ⑷ (x+y+z+)(x+)+yz 数と式 ⑵ 氏点00 次の問いに答えよ ( 各 6 点 ) ⑴ 次の循環小数を分数で表せ. a-5 = ⑵ 次の等式を満たす実数

More information

相関係数と偏差ベクトル

相関係数と偏差ベクトル 相関係数と偏差ベクトル 経営統計演習の補足資料 07 年 月 9 日金沢学院大学経営情報学部藤本祥二 相関係数の復習 r = s xy s x s y = = n σ n i= σn i= n σ n i= n σ i= x i xҧ y i തy x i xҧ n σ n i= y i തy x i xҧ x i xҧ y i തy σn i= y i തy 式が長くなるので u, v の文字で偏差を表すことにする

More information

そもそも情報とはなに? ある事柄に関して知識を得たり判断のより所としたりするために不可欠な 何らかの手段で伝達 ( 入手 ) された種々の事項 ( の内容 ) ( 新明解国語辞典第 6 版 三省堂より一部抜粋 ) コンピュータで取り扱う情報の定義 Claud Elwood Shannon( 情報理論

そもそも情報とはなに? ある事柄に関して知識を得たり判断のより所としたりするために不可欠な 何らかの手段で伝達 ( 入手 ) された種々の事項 ( の内容 ) ( 新明解国語辞典第 6 版 三省堂より一部抜粋 ) コンピュータで取り扱う情報の定義 Claud Elwood Shannon( 情報理論 情報理論の基礎 l 自己情報量 (self information) l 平均情報量 (average information) l エントロピー (entropy) l 最大エントロピー (maximum entropy) l 冗長度 (redndancy) 可逆圧縮の原理と実践 l ランレングス符号化 l ハフマン符号化 ( エントロピー符号化 ) そもそも情報とはなに? ある事柄に関して知識を得たり判断のより所としたりするために不可欠な

More information

Microsoft PowerPoint slide2forWeb.ppt [互換モード]

Microsoft PowerPoint slide2forWeb.ppt [互換モード] 講義内容 9..4 正規分布 ormal dstrbuto ガウス分布 Gaussa dstrbuto 中心極限定理 サンプルからの母集団統計量の推定 不偏推定量について 確率変数, 確率密度関数 確率密度関数 確率密度関数は積分したら. 平均 : 確率変数 分散 : 例 ある場所, ある日時での気温の確率. : 気温, : 気温 が起こる確率 標本平均とのアナロジー 類推 例 人の身長の分布と平均

More information

モジュール1のまとめ

モジュール1のまとめ 数理統計学 第 0 回 復習 標本分散と ( 標本 ) 不偏分散両方とも 分散 というのが実情 二乗偏差計標本分散 = データ数 (0ページ) ( 標本 ) 不偏分散 = (03 ページ ) 二乗偏差計 データ数 - 分析ではこちらをとることが多い 復習 ここまで 実験結果 ( 万回 ) 平均 50Kg 標準偏差 0Kg 0 人 全体に小さすぎる > mea(jkke) [] 89.4373 標準偏差

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション コンパイラとプログラミング言語 第 3 4 週 プログラミング言語の形式的な記述 2014 年 4 月 23 日 金岡晃 授業計画 第 1 週 (4/9) コンパイラの概要 第 8 週 (5/28) 下向き構文解析 / 構文解析プログラム 第 2 週 (4/16) コンパイラの構成 第 9 週 (6/4) 中間表現と意味解析 第 3 週 (4/23) プログラミング言語の形式的な記述 第 10 週

More information

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

Microsoft PowerPoint - qcomp.ppt [互換モード] 量子計算基礎 東京工業大学 河内亮周 概要 計算って何? 数理科学的に 計算 を扱うには 量子力学を計算に使おう! 量子情報とは? 量子情報に対する演算 = 量子計算 一般的な量子回路の構成方法 計算って何? 計算とは? 計算 = 入力情報から出力情報への変換 入力 計算機構 ( デジタルコンピュータ,etc ) 出力 計算とは? 計算 = 入力情報から出力情報への変換 この関数はどれくらい計算が大変か??

More information

a n a n ( ) (1) a m a n = a m+n (2) (a m ) n = a mn (3) (ab) n = a n b n (4) a m a n = a m n ( m > n ) m n 4 ( ) 552

a n a n ( ) (1) a m a n = a m+n (2) (a m ) n = a mn (3) (ab) n = a n b n (4) a m a n = a m n ( m > n ) m n 4 ( ) 552 3 3.0 a n a n ( ) () a m a n = a m+n () (a m ) n = a mn (3) (ab) n = a n b n (4) a m a n = a m n ( m > n ) m n 4 ( ) 55 3. (n ) a n n a n a n 3 4 = 8 8 3 ( 3) 4 = 8 3 8 ( ) ( ) 3 = 8 8 ( ) 3 n n 4 n n

More information

2019年度 千葉大・理系数学

2019年度 千葉大・理系数学 9 千葉大学 ( 理系 ) 前期日程問題 解答解説のページへ a, a とし, のとき, a+ a + a - として数列 { a } () のとき a+ a a a - が成り立つことを証明せよ () åai aaa + が成り立つような自然数 を求めよ i を定める -- 9 千葉大学 ( 理系 ) 前期日程問題 解答解説のページへ 三角形 ABC は AB+ AC BCを満たしている また,

More information

2018年度 神戸大・理系数学

2018年度 神戸大・理系数学 8 神戸大学 ( 理系 ) 前期日程問題 解答解説のページへ t を < t < を満たす実数とする OABC を 辺の長さが の正四面体とする 辺 OA を -t : tに内分する点を P, 辺 OB を t :-tに内分する点を Q, 辺 BC の中点を R とする また a = OA, b = OB, c = OC とする 以下の問いに答えよ () QP と QR をt, a, b, c を用いて表せ

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

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

スライド 1

スライド 1 ブール代数 ブール代数 集合 { 0, 1 } の上で演算 AND, OR, NOT からなる数学的体系 何のため? ある演算をどのような回路で実現すればよいのか? どうすれば回路が小さくなるのか? どうすれば回路が速く動くのか? 3 復習 : 真理値表とゲート記号 真理値表 A B A B 0 0 0 0 1 0 1 0 0 1 1 1 A B A+B 0 0 0 0 1 1 1 0 1 1 1

More information

( 最初の等号は,N =0, 番目は,j= のとき j =0 による ) j>r のときは p =0 から和の上限は r で十分 定義 命題 3 ⑵ 実数 ( 0) に対して, ⑴ =[] []=( 0 または ) =[6]+[] [4] [3] [] =( 0 または ) 実数 に対して, π()

( 最初の等号は,N =0, 番目は,j= のとき j =0 による ) j>r のときは p =0 から和の上限は r で十分 定義 命題 3 ⑵ 実数 ( 0) に対して, ⑴ =[] []=( 0 または ) =[6]+[] [4] [3] [] =( 0 または ) 実数 に対して, π() 伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊 伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊 数研通信 70 号を読んで チェビシェフの定理の精密化 と.5 の間に素数がある 伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊 さい才 の 野 せ瀬 いちろう 一郎 伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊 0. はじめに このたび,

More information

2015年度 京都大・理系数学

2015年度 京都大・理系数学 05 京都大学 ( 理系 ) 前期日程問題 解答解説のページへ つの関数 y= si( x+ ) と y = six のグラフの 0 x の部分で囲まれる領域 を, x 軸のまわりに 回転させてできる立体の体積を求めよ ただし, x = 0 と x = は領域を囲む線とは考えない -- 05 京都大学 ( 理系 ) 前期日程問題 解答解説のページへ次の つの条件を同時に満たす四角形のうち面積が最小のものの面積を求めよ

More information

A ,000 7,539 7,593

A ,000 7,539 7,593 A+ 64 1 300 16 6,000 7,539 7,593 13 3,329 178 1,168 12% 11% 35 3 26 3 761.2 6 8,947 6,044 432 7,774 CONTENTS 01 02 04 07 11 20 38 6,677 6,706 6,044 5,519 5,489 2011 2012 2013 2014 2015 866 796 522

More information

2016年度 京都大・文系数学

2016年度 京都大・文系数学 06 京都大学 ( 文系 ) 前期日程問題 解答解説のページへ xy 平面内の領域の面積を求めよ x + y, x で, 曲線 C : y= x + x -xの上側にある部分 -- 06 京都大学 ( 文系 ) 前期日程問題 解答解説のページへ ボタンを押すと あたり か はずれ のいずれかが表示される装置がある あたり の表示される確率は毎回同じであるとする この装置のボタンを 0 回押したとき,

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

2017年度 金沢大・理系数学

2017年度 金沢大・理系数学 07 金沢大学 ( 理系 前期日程問題 解答解説のページへ 次の問いに答えよ ( 6 z + 7 = 0 を満たす複素数 z をすべて求め, それらを表す点を複素数平面上に図 示せよ ( ( で求めた複素数 z を偏角が小さい方から順に z, z, とするとき, z, z と 積 zz を表す 点が複素数平面上で一直線上にあることを示せ ただし, 偏角は 0 以上 未満とする -- 07 金沢大学

More information

, 1. x 2 1 = (x 1)(x + 1) x 3 1 = (x 1)(x 2 + x + 1). a 2 b 2 = (a b)(a + b) a 3 b 3 = (a b)(a 2 + ab + b 2 ) 2 2, 2.. x a b b 2. b {( 2 a } b )2 1 =

, 1. x 2 1 = (x 1)(x + 1) x 3 1 = (x 1)(x 2 + x + 1). a 2 b 2 = (a b)(a + b) a 3 b 3 = (a b)(a 2 + ab + b 2 ) 2 2, 2.. x a b b 2. b {( 2 a } b )2 1 = x n 1 1.,,.,. 2..... 4 = 2 2 12 = 2 2 3 6 = 2 3 14 = 2 7 8 = 2 2 2 15 = 3 5 9 = 3 3 16 = 2 2 2 2 10 = 2 5 18 = 2 3 3 2, 3, 5, 7, 11, 13, 17, 19.,, 2,.,.,.,?.,,. 1 , 1. x 2 1 = (x 1)(x + 1) x 3 1 = (x 1)(x

More information

学習指導要領

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

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 - statistics pptx

Microsoft PowerPoint - statistics pptx 統計学 第 17 回 講義 母平均の区間推定 Part- 016 年 6 14 ( )3 限 担当教員 : 唐渡 広志 ( からと こうじ ) 研究室 : 経済学研究棟 4 階 43 号室 email: kkarato@eco.u toyama.ac.jp website: http://www3.u toyama.ac.jp/kkarato/ 1 講義の目的 標本平均は正規分布に従うという性質を

More information

学習指導要領

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

More information

CAEシミュレーションツールを用いた統計の基礎教育 | (株)日科技研

CAEシミュレーションツールを用いた統計の基礎教育 | (株)日科技研 CAE シミュレーションツール を用いた統計の基礎教育 ( 株 ) 日本科学技術研修所数理事業部 1 現在の統計教育の課題 2009 年から統計教育が中等 高等教育の必須科目となり, 大学でも問題解決ができるような人材 ( 学生 ) を育てたい. 大学ではコンピューター ( 統計ソフトの利用 ) を重視した教育をより積極的におこなうのと同時に, 理論面もきちんと教育すべきである. ( 報告 数理科学分野における統計科学教育

More information

重要例題113

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

More information

Ⅰ 情報圧縮はやわかり夢の圧縮法? すべてのファイルを 1/100 のサイズに圧縮します 詐欺 長さ1000 ビットのファイル 個 長さ10 ビットのファイル 2 10 個 長さ999 ビットのファイル 個 N 個のものを N-1 個に入れたら.. かならず人のほうががあま

Ⅰ 情報圧縮はやわかり夢の圧縮法? すべてのファイルを 1/100 のサイズに圧縮します 詐欺 長さ1000 ビットのファイル 個 長さ10 ビットのファイル 2 10 個 長さ999 ビットのファイル 個 N 個のものを N-1 個に入れたら.. かならず人のほうががあま 情報理論と統計科学 今日の講義のねらい (1) 物理専攻だとシャノン流の情報理論を ぜんぜん習っていない ( かもしれない ) やはりいちどは聞いておくべきもの シャノン理論情報圧縮の理論 ( 雑音なし ) 今回こちら誤り訂正の理論 ( 雑音あり ) 情報圧縮 身近な話題になってきているテキスト lha,gzip,zip,bzip2 ( 可逆 ) 画像 jpeg( 非可逆 ) png,gif( 可逆

More information

Microsoft Word - t30_西_修正__ doc

Microsoft Word - t30_西_修正__ doc 反応速度と化学平衡 金沢工業大学基礎教育部西誠 ねらい 化学反応とは分子を構成している原子が組み換り 新しい分子構造を持つことといえます この化学反応がどのように起こるのか どのような速さでどの程度の分子が組み換るのかは 反応の種類や 濃度 温度などの条件で決まってきます そして このような反応の進行方向や速度を正確に予測するために いろいろな数学 物理的な考え方を取り入れて化学反応の理論体系が作られています

More information

母平均 母分散 母標準偏差は, が連続的な場合も含めて, すべての個体の特性値 のすべての実現値 の平均 分散 標準偏差であると考えてよい 有限母集団で が離散的な場合, まさにその意味になるが, そうでない場合も, このように理解してよい 5 母数 母集団から定まる定数のこと 母平均, 母分散,

母平均 母分散 母標準偏差は, が連続的な場合も含めて, すべての個体の特性値 のすべての実現値 の平均 分散 標準偏差であると考えてよい 有限母集団で が離散的な場合, まさにその意味になるが, そうでない場合も, このように理解してよい 5 母数 母集団から定まる定数のこと 母平均, 母分散, . 無作為標本. 基本的用語 推測統計における基本的な用語を確認する 母集団 調査の対象になる集団のこと 最終的に, 判断の対象になる集団である 母集団の個体 母集団を構成する つ つのもののこと 母集団は個体の集まりである 個体の特性値 個体の特性を表す数値のこと 身長や体重など 特性値は, 変量ともいう 4 有限母集団と無限母集団 個体の個数が有限の母集団を 有限母集団, 個体の個数が無限の母集団を

More information

千葉大学 ゲーム論II

千葉大学 ゲーム論II 千葉大学ゲーム論 II 第五, 六回 担当 上條良夫 千葉大学ゲーム論 II 第五 六回上條良夫 本日の講義内容 前回宿題の問題 3 の解答 Nash の交渉問題 Nash 解とその公理的特徴づけ 千葉大学ゲーム論 II 第五 六回上條良夫 宿題の問題 3 の解答 ホワイトボードでやる 千葉大学ゲーム論 II 第五 六回上條良夫 3 Nash の二人交渉問題 Nash の二人交渉問題は以下の二つから構成される

More information

æœ•å¤§å–¬ç´—æŁ°,æœ•å°‘å–¬å•“æŁ°,ã…¦ã…¼ã‡¯ã…ªã……ã…›ã†®äº™éŽ¤æ³Ł

æœ•å¤§å–¬ç´—æŁ°,æœ•å°‘å–¬å•“æŁ°,ã…¦ã…¼ã‡¯ã…ªã……ã…›ã†®äº™éŽ¤æ³Ł 最大公約数, 最小公倍数, ユークリッドの互除法 最大公約数, 最小公倍数とは つ以上の正の整数に共通な約数 ( 公約数 ) のうち最大のものを最大公約数といいます. と 8 の公約数は,,,,6 で, 6 が最大公約数 つ以上の正の整数の共通な倍数 ( 公倍数 ) のうち最小のものを最小公倍数といいます. と の公倍数は, 6,,8,,... で, 6 が最小公倍数 最大公約数, 最小公倍数の求め方

More information

NOTE P, A,. A P ( A, P ),,.,. P A. (set) (set), (). (element), (element).,.,. ( A, B, X, Y, P ), { } (),..3 (union) A, B,A B, A B (union),. A B = {x x

NOTE P, A,. A P ( A, P ),,.,. P A. (set) (set), (). (element), (element).,.,. ( A, B, X, Y, P ), { } (),..3 (union) A, B,A B, A B (union),. A B = {x x 2. (set)............... 2.2,.... 2.3 (union)............ 2.4 (intersection)......... 2.5 (power set)......... 3.6 (cartesian product set)... 3 2, 3 2. (length)........ 3 2.2 (epsilon)............ 3 2.3

More information

Microsoft Word - 町田・全 H30学力スタ 別紙1 1年 数学Ⅰ.doc

Microsoft Word - 町田・全 H30学力スタ 別紙1 1年 数学Ⅰ.doc (1) 数と式 学習指導要領 都立町田高校 学力スタンダード ア 数と集合 ( ア ) 実数 根号を含む式の計算 数を実数まで拡張する意義を理解し 簡単な 循環小数を表す記号を用いて, 分数を循環小数で表 無理数の四則計算をすること すことができる 今まで学習してきた数の体系について整理し, 考察 しようとする 絶対値の意味と記号表示を理解している 根号を含む式の加法, 減法, 乗法の計算ができる

More information

Microsoft PowerPoint - Inoue-statistics [互換モード]

Microsoft PowerPoint - Inoue-statistics [互換モード] 誤差論 神戸大学大学院農学研究科 井上一哉 (Kazuya INOUE) 誤差論 2011 年度前期火曜クラス 1 講義内容 誤差と有効数字 (Slide No.2~8 Text p.76~78) 誤差の分布と標準偏差 (Slide No.9~18 Text p.78~80) 最確値とその誤差 (Slide No.19~25 Text p.80~81) 誤差の伝播 (Slide No.26~32 Text

More information

工業数学F2-04(ウェブ用).pptx

工業数学F2-04(ウェブ用).pptx 工業数学 F2 #4 フーリエ級数を極める 京都大学加納学 京都大学大学院情報学研究科システム科学専攻 Human Systems Lab., Dept. of Systems Science Graduate School of Informatics, Kyoto University 復習 1: 複素フーリエ級数 2 周期 2π の周期関数 f(x) の複素フーリエ級数展開 複素フーリエ係数

More information

情報量と符号化

情報量と符号化 I. ここでの目的情報量の単位はビットで 2 種の文字を持つ記号の情報量が 1 ビットです ここでは 一般に n 種の文字を持つ記号の情報量を定義します 次に 出現する文字に偏りがある場合の平均情報量を定義します この平均情報量は 記号を適当に 0,1 で符号化する場合の平均符号長にほぼ等しくなることがわかります II. 情報量とは A. bit 情報量の単位としてbitが利用されます 1bitは0か1の情報を運びます

More information

調和系工学 ゲーム理論編

調和系工学 ゲーム理論編 ゲーム理論第三部 知的都市基盤工学 5 月 30 日 ( 水 5 限 (6:30~8:0 再掲 : 囚人のジレンマ 囚人のジレンマの利得行列 協調 (Cooperte:C プレイヤー 裏切 (Deect:D ( 協調 = 黙秘 裏切 = 自白 プレイヤー C 3,3 4, D,4, 右がプレイヤー の利得左がプレイヤー の利得 ナッシュ均衡点 プレイヤーの合理的な意思決定の結果 (C,C はナッシュ均衡ではない

More information

融合規則 ( もっとも簡単な形, 選言的三段論法 ) ll mm ll mm これについては (ll mm) mmが推論の前提部になり mmであるから mmは常に偽となることがわかり ll mmはllと等しくなることがわかる 機械的には 分配則より (ll mm) mm (ll mm) 0 ll m

融合規則 ( もっとも簡単な形, 選言的三段論法 ) ll mm ll mm これについては (ll mm) mmが推論の前提部になり mmであるから mmは常に偽となることがわかり ll mmはllと等しくなることがわかる 機械的には 分配則より (ll mm) mm (ll mm) 0 ll m 知識工学 ( 第 5 回 ) 二宮崇 ( ninomiya@cs.ehime-u.ac.jp ) 論理的エージェント (7 章のつづき ) 証明の戦略その 3 ( 融合法 ) 証明の戦略その 1 やその 2 で証明できたときは たしかにKKKK ααとなることがわかるが なかなか証明できないときや 証明が本当にできないときには KKKK ααが成り立つのか成り立たないのかわからない また どのような証明手続きを踏めば証明できるのか定かではない

More information

Microsoft PowerPoint - while.ppt

Microsoft PowerPoint - while.ppt 本日の内容 繰り返し計算 while 文, for 文 例題 1. 自然数の和例題 2. 最大公約数の計算例題 3. ベクトルの長さ while 文例題 4. 九九の表 for 文と繰り返しの入れ子例題 5. ド モアブルの公式計算誤差の累積 今日の到達目標 繰り返し (while 文, for 文 ) を使って, 繰り返し計算を行えるようになること ループカウンタとして, 整数の変数を使うこと 今回も,

More information

Microsoft Word - 201hyouka-tangen-1.doc

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

More information

() ): (1) f(x) g(x) x = x 0 f(x) + g(x) x = x 0 lim f(x) = f(x 0 ), lim g(x) = g(x 0 ) x x 0 x x0 lim {f(x) + g(x)} = f(x 0 ) + g(x 0 ) x x0 lim x x 0

() ): (1) f(x) g(x) x = x 0 f(x) + g(x) x = x 0 lim f(x) = f(x 0 ), lim g(x) = g(x 0 ) x x 0 x x0 lim {f(x) + g(x)} = f(x 0 ) + g(x 0 ) x x0 lim x x 0 (1) 3 連続関数と逆関数 定義 3.1 y = f (x) のグラフが x = a でつながっているとき f (x) は x = a において連続と いう. 直感的にはこれが わかりやすい x = a では連続 x = b ではグラフがちぎれているので 不連続 定義 3. f (x) が x = a の近くで定義され lim f (x) = f (a) をみたす時 x a f (x) は x =

More information

Microsoft PowerPoint - 画像工学 印刷用

Microsoft PowerPoint - 画像工学 印刷用 教室 : 14-202 JURY 08 画像工学 2007 年度版 Imaging Science and Technology 画像工学 2007 年度版 11 慶応義塾大学理工学部 中島真人 教授 今日で最後です! 6. デジタル画像の性質と取り扱い 6-1. 画像のサンプリング サンプリングした画像のフーリエ変換 画像のサンプリング付随して生じるエラー 6-2. デジタル画像のフーリエ変換 周期関数のフーリエ変換

More information

Microsoft PowerPoint - 基礎・経済統計6.ppt

Microsoft PowerPoint - 基礎・経済統計6.ppt . 確率変数 基礎 経済統計 6 確率分布 事象を数値化したもの ( 事象ー > 数値 の関数 自然に数値されている場合 さいころの目 量的尺度 数値化が必要な場合 質的尺度, 順序的尺度 それらの尺度に数値を割り当てる 例えば, コインの表が出たら, 裏なら 0. 離散確率変数と連続確率変数 確率変数の値 連続値をとるもの 身長, 体重, 実質 GDP など とびとびの値 離散値をとるもの 新生児の性別

More information

Microsoft PowerPoint L03-Syntex and Semantics-1-students ( )

Microsoft PowerPoint L03-Syntex and Semantics-1-students ( ) プログラミング言語論 A (Concepts on Programming Languages) 趙建軍 (Jianjun Zhao) http://stap.ait.kyushu-u.ac.jp/~zhao/course/2018/concepts of Programming Languages.html 1 第 3 回 構文と意味 (1) (Syntax and Semantics) 2017.04.26

More information

学習指導要領

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

More information

Microsoft PowerPoint - 9.pptx

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

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 PowerPoint - 9.pptx

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

More information

第 6 回の目的 確定年金現価の算式について理解する 終身年金現価の算式について理解する 簡単な例で掛金の計算をしてみる 極限方程式を理解する 年金数理第 6 回 2

第 6 回の目的 確定年金現価の算式について理解する 終身年金現価の算式について理解する 簡単な例で掛金の計算をしてみる 極限方程式を理解する 年金数理第 6 回 2 東京工業大学大学院経営工学専攻 年金数理第 6 回 年金現価 終価 極限方程式 講師 : 渡部善平 (( 株 )IIC パートナーズ ) 第 6 回の目的 確定年金現価の算式について理解する 終身年金現価の算式について理解する 簡単な例で掛金の計算をしてみる 極限方程式を理解する 年金数理第 6 回 2 確定年金現価 終身年金現価 確定年金 確定年金現価 確定年金 : 年金受給者の生死にかかわらず一定期間の支払いを約束する年金

More information

2017年度 神戸大・理系数学

2017年度 神戸大・理系数学 7 神戸大学 ( 理系 前期日程問題 解答解説のページへ を自然数とする f ( si + とおく < < 4 であることを用い て, 以下の問いに答えよ ( < < のとき, f ( < であることを示せ ( 方程式 f ( は < < の範囲に解をただ つもつことを示せ ( ( における解を とする lim であることを示し, lim を求めよ 7 神戸大学 ( 理系 前期日程問題 解答解説のページへ

More information

2013年度 九州大・理系数学

2013年度 九州大・理系数学 九州大学 ( 理系 ) 前期日程問題 解答解説のページへ a> とし, つの曲線 y= ( ), y= a ( > ) を順にC, C とする また, C とC の交点 P におけるC の接線をl とする 以下 の問いに答えよ () 曲線 C とy 軸および直線 l で囲まれた部分の面積をa を用いて表せ () 点 P におけるC の接線と直線 l のなす角を ( a) とき, limasin θ(

More information

2014年度 信州大・医系数学

2014年度 信州大・医系数学 4 信州大学 ( 医系 ) 前期日程問題 解答解説のページへ 3 個の玉が横に 列に並んでいる コインを 回投げて, それが表であれば, そのときに中央にある玉とその左にある玉とを入れ替える また, それが裏であれば, そのときに中央にある玉とその右にある玉とを入れ替える この操作を繰り返す () 最初に中央にあったものが 回後に中央にある確率を求めよ () 最初に右端にあったものが 回後に右端にある確率を求めよ

More information

2016年度 九州大・理系数学

2016年度 九州大・理系数学 0 九州大学 ( 理系 ) 前期日程問題 解答解説のページへ 座標平面上の曲線 C, C をそれぞれ C : y logx ( x > 0), C : y ( x-)( x- a) とする ただし, a は実数である を自然数とするとき, 曲線 C, C が 点 P, Q で交わり, P, Q の x 座標はそれぞれ, + となっている また, 曲線 C と直線 PQ で囲まれた領域の面積を S,

More information

2015-2018年度 2次数学セレクション(整数と数列)解答解説

2015-2018年度 2次数学セレクション(整数と数列)解答解説 015 次数学セレクション問題 1 [ 千葉大 文 ] k, m, n を自然数とする 以下の問いに答えよ (1) k を 7 で割った余りが 4 であるとする このとき, k を 3 で割った余りは であることを示せ () 4m+ 5nが 3 で割り切れるとする このとき, mn を 7 で割った余りは 4 ではないことを示せ -1- 015 次数学セレクション問題 [ 九州大 理 ] 以下の問いに答えよ

More information

学習指導要領

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

More information

<4D F736F F F696E74202D2091E6824F82568FCD8CEB82E892F990B382CC8CF889CA82BB82CC82515F B834E838A B9797A3959C8D F A282E982C682AB82CC8CEB82E897A62E >

<4D F736F F F696E74202D2091E6824F82568FCD8CEB82E892F990B382CC8CF889CA82BB82CC82515F B834E838A B9797A3959C8D F A282E982C682AB82CC8CEB82E897A62E > 第 7 章 誤り訂正の効果その : ユークリッド距離復号法を用いるときの誤り率 ユークリッド距離に基づく最尤復号ブロック符号のユークリッド距離に基づく最尤復号畳み込み符号のユークリッド距離に基づく最尤復号 安達 : コミュニケーション符号理論 ユークリッド距離に基づく最尤復号 送信情報系列 Xx x x x x x 5.. を符号化して得られた符号系列 5.. を送信する. 伝送路途中の雑音のため誤りが発生するので,

More information