離散数学

Save this PDF as:
 WORD  PNG  TXT  JPG

Size: px
Start display at page:

Download "離散数学"

Transcription

1 離散数学 最短経路問題 落合秀也

2 その前に 前回の話 深さ優先探索アルゴリズム 開始点 から深さ優先探索を行うアルゴリズム 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)

3 その前に 前回の話 深さ優先探索アルゴリズム 再帰呼び出しによる方法 深さ優先探索を行うアルゴリズム ( 再帰呼び出し版 ) Funton DFS(v) I F[v] = l Tn, F[v] := tru For no u n A[v] DFS(u) EnFor EnI EnFunton 頂点 から探索を行う場合 : DFS() を実行すれば良い 再帰呼び出しは 実際には 裏ではスタックを使って実行される

4 最短経路問題を考える ラベル付 ( 重み付 ) グラフ G=(V,E) が与えられたとき 頂点 から頂点 t への最短経路 -t を求めたい 辺のラベルの意味 : 地点間の道のり 地点間の移動時間 地点間の移動に要する燃料の量 状態の遷移で失う資金 最小コストでの移動経路を発見したい 9 = = = (*) 実際はコスト の道が存在する t

5 最短経路問題の解法 ダイクストラ法 すべての辺の重みが非負の場合に適用可能 貪欲法 (Gry Alortm) の一種 ベルマン フォード法 辺の重みに負があっても良いケースがある ( 有向グラフで 有向閉路の和が負でない場合 ) 動的計画法 (Dynm Prormmn) の一種 t コストが 資金の支出の場合 マイナスは 収入を意味する

6 ダイクストラ法 (Dktr Alortm) 99 年 : Er Dktr によって考案された H 考え方 -- G(V,E) に対して 開始点 V から各頂点への最短経路を求める問題 いま すでに部分 H に関して 最短経路が導出されているとする からの距離が判明している H と接する v V-H に対し からの距離を考える その距離の最小値を与える v を H に追加する 赤字 : 判明している からの最短距離

7 ダイクストラ法 ( もう少し正確な定義 ) 用語の定義 : グラフ G(V,E) において u, v V, =(u,v) E とする 辺 =(u,v) の長さを l あるいは l (u,v) で表すとする 開始点を とする (u) で から u までの最短距離を表すとする prv(v) で から v への最短経路における v の直前の頂点を表す 挙動の定義 : V の部分集合 H を以下のように作成する 初期状態 : H = {}, ()=, (v)= (v ), prv(v)=null (v V) とする u H で辺 =(u, v) でつながっている v ( V-H) を考え (v) = mn =(u,v):u H { (u) + l } を計算する v V-H において 上記をさらに最小化する v を選定し その v を H に追加し その距離を (v) とおき その時の u を用いて prv(v)=u とす る H l (u,v) (u) (v) = mn {(u)+l } (u) (v) = mn {(u)+l } l (u,v) (v) または (v) のどちらか片方 を決定する

8 練習 以下のグラフに対し ダイクストラ法により 頂点 から各頂点への最短経路とその距離を求めよ

9 解答 : 頂点 最短経路 距離 9

10 ダイクストラ法の実現 : アルゴリズムの設計素直に上述の定義に従って考えると 準備するもの から u までの最小距離を格納する配列 : [u] 初期条件 : []=, (u に対して ) [u]= から v への最短経路で v の直前を格納する配列 : prv[v] 初期条件 : prv[v]=null 辺の長さを与える関数 : lnt(u,v) 最短経路が確定した頂点のリスト : H 初期条件 : H = {} (v) = mn =(u,v):u H { (u) + l } 方針 [v] を最小にする u H, v V-H の辺 (u,v) を見つける 見つかったら prv[v]=u, [v]= [v] とおき v を H に追加する 上記を H=V になるまで繰り返す

11 ダイクストラ法の実現 : アルゴリズムの設計工夫をしてみよう 最短経路が確定した頂点のリスト (H) を考え からの距離 (v) が最小になる v ( V-H) を H に追加していた ( そして これを H=V になるまで繰り返した ) 最短経路が確定していない頂点のリスト (Q) を考え からの距離 (v) を最小にする v( Q) を Q から削除する ( そして これを Q が空になるまで繰り返す ) 各 v( Q) において (v) の候補を常に計算できていれば Q から削除される段階で (v) が最小であれば そこから新たに (v) を計算をする必要はない

12 ダイクストラ法の実現 : 二つのアプローチ H Q その時点の周辺について計算最小値を与える頂点を取り込む最小値を与える頂点を除外する除外された周辺の頂点までの距離を計算する

13 練習 もう一つのダイキストラ法 (Q の中から最小値を与える頂点を取り除く方法 ) で 以下の頂点 から各頂点までの最短経路を求めよ

14 . []= と置く Q からは が取り出される に隣接する, の距離が計算される. Q から Q の中で最小の (u)= を与える が取り出される に隣接する, の距離が計算される

15 . Q から Q の中で最小の (u)= を与える が取り出される に隣接する, の距離が計算される. Q から Q の中で最小の (u)= を与える が取り出される に隣接する, の距離が計算される

16 . Q から Q の中で最小の (u)= を与える が取り出される に隣接する の距離が計算される. Q から Q の中で最小の (u)= を与える が取り出される に隣接する,, の距離が計算される

17 . Q から Q の中で最小の (u)= を与える が取り出される に隣接する の距離が計算される. Q から Q の中で最小の (u)= を与える が取り出される に隣接する の距離が計算される 9

18 9. Q から Q の中で最小の (u)=9 を与える が取り出される に隣接する の距離が計算される 9. Q から Q の中で最小の (u)= を与える が取り出される に隣接する の距離が計算される 9

19 . Q から Q の中で最小の (u)= を与える が取り出される に隣接する頂点はなし (Q の中で ). Q が空なので 終了 9 頂点 最短経路 距離 9 9

20 装置 Q Q の持つべきインタフェースを考察する 初期化時 : Q に V のすべてを投入する (v) : v V [u] 参照 Empty()? 実行時 : Q が空かどうかを判定する nky() Q から (u) を最小とする u を取り出す Q の内部を で整理する (Q がヒープの場合 ) Q

21 ダイクストラのアルゴリズム For v V [v] :=, prv[v] :=null Q.(v) EnFor [] := Wl Q not mpty u := Q.xtrtMn() For v n A[u] I [v] > [u] + lnt(u, v) Tn, [v] := [u] + lnt(u, v) prv[v]=u ( Q.nKy() -- t mplmntton o Q p ) EnI EnFor EnWl

22 ダイクストラ法 : 計算量の考察 Wl 文の内部は n 回実行される For 文の内部は nm 回実行される 実装によっては O(nm) となりえる Q にリストや配列を使う場合 Q.xtrtMn() に O(n) の時間を要する Q.xtrtMn() は n 回呼び出される O(n ) Wl Q not mpty u := Q.xtrtMn() For v n A[u] I [v] > [u] + lnt(u, v) Tn, [v] := [u] + lnt(u, v) prv[v]=u ( Q.nKy() ) EnI EnFor EnWl Q に 分ヒープを使う場合 Q.xtrtMn() に O(lo n) の時間を要する Q.xtrtMn() の呼び出しは n 回ある O(n lo n) [v] の更新に伴うヒープの組換え処理に O(lo n) の時間を要する [v] の更新は m 回発生する O(m lo n) O( (n+m) lo n )

23 装置 Q の実装 : リストを使った場合 Q.xtrtMn() ポインタ p を用意リストのすべての要素に対して 順に(u) を計算より小さい(u) が発見されたら p に u へのポインタを設定するすべての要素を確認したら p の先を リストから除外し その値を返す 開始 (u) = p

24 装置 Q の実装 : ヒープを使った場合 分ヒープ 親 子の関係になるように構成された 分木 根は最小となる Q.xtrtMn() 根を取り出し 再構成を行う 計算量 O(lo n) []= Q.nKy() []= の変化に合わせて再構成を行う 計算量 O(lo n) []= []= []= []=

25 ベルマン フォード法 Bllmn For Alortm 基本的な考え方 開始点 から への距離を とする 各頂点の開始点 からの距離は 辺の重みを加算しながら から拡散するように伝搬させる 各頂点では距離の最小値を採用する 上記を 頂点数 - 回行う

26 ベルマン フォード法 回目から + 回目への計算 ( 漸化式 ) を考える ここで は 拡散量 ( から伝搬した辺の数 ) に相当する 回目 ( 個の辺の伝搬を考えたとき ) における 頂点 から頂点 v までの最短距離を OPT(,v) とする このとき 以下が言える OPT(+, v) = mn u nr(v) {OPT(,u)+C uv } (*) ここで nr(v) は v の近隣頂点 ( 自分自身も含む ) の集合とするまた C uv は辺 (u,v) のコストとし 便宜上 C vv = とする 初期条件 (= のとき ) OPT(,)=, OPT(,v)= (v V, v )

27 OPT(+, v) = mn u nr(v) {OPT(,u)+C uv } の意味 OPT(,) OPT(,) C v C v v C v OPT(,v) OPT(,v) OPT(,)+C v OPT(,)+C v OPT(,)+C v OPT(,) C vv (=) OPT(+,v) は 上記で最小のものとする

28 練習 以下のグラフに対し ベルマンフォード法により 頂点 から各頂点までの最短距離を求めよ (*) ダイクストラ法との違いも考えてみよ

29 9 回目 回目

30 回目 回目

31 回目 回目

32 回目 回目 9

33 回目 9 回目 9

34 回目以降頂点最短距離 9 9

35 ベルマンフォードのアルゴリズム M[]= M[v]=, prv[v]=null (v V, v ) For =,, n- // n=ount(v) For =(u, v) n E I M[v] > M[u]+C M[v]=M[u]+C prv[v]=u EnI EnFor EnFor 時間計算量 : O(mn)

36 ベルマンフォード法の分散化 グラフ G(V,E) において 各頂点は 辺で接続するもう片方の頂点と通信を行うものとする u OPT(u) + Cuv このとき 各頂点 u から 頂点 v ( nr(u)) に向けて OPT(u)+Cuv を発信する 受信側の頂点 v では 受信した値の中 ( 他者からのものも含む ) で 最小のものを OPT(v) として選ぶ 開始点 の OPT() は に固定する という処理を行うと ベルマンフォード法を分散的に実装できる v

37 ベルマンフォード法の分散化 : 各頂点の動作 v v u u OPT(u) + C uv u OPT(u) OPT(u) + C uv v I OPT(v) > 受信結果 OPT(v) := 受信結果 EnI v u 頂点 u からの送信 ( 定期的に行う ) 頂点 v での受信と処理

38

39 今後の予定 月 日 : 休講 ( レポートで代替 ) 月 日 : 最小全域木 月 日 : 最大流問題 9

離散数学

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

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

離散数学

離散数学 離散数学 グラフ探索アルゴリズム 落合秀也 今日の内容 グラフの連結性 の判定 幅優先探索 幅優先探索の実現方法 深さ優先探索 深さ優先探索の実現方法 木の構造 探索木 パトリシア トライ 2 連結性の判定問題を考える グラフ G(V,E) が与えられたとき G が連結かどうか を判定したい 小さいグラフなら 紙に書いてみればよい 一般には簡単ではない 大きいグラフの場合 コンピュータに判断させる場合

More information

Microsoft PowerPoint - DA2_2017.pptx

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

More information

Microsoft PowerPoint - DA2_2017.pptx

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

More information

Microsoft PowerPoint - DA2_2018.pptx

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

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

Microsoft PowerPoint - 06.pptx

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

More information

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

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

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

2. データ構造ヒープに保存するデータは 番号付けられて保存される 従って リスト L として保存することとする 3. アルゴリズム 3.1. 要素の追加新しい要素の追加は リストの終端に置くことで開始する つまり 最下層の一番右 または新たに最下層を生成してその一番左となる この後 この要素を正し

2. データ構造ヒープに保存するデータは 番号付けられて保存される 従って リスト L として保存することとする 3. アルゴリズム 3.1. 要素の追加新しい要素の追加は リストの終端に置くことで開始する つまり 最下層の一番右 または新たに最下層を生成してその一番左となる この後 この要素を正し 1. はじめに 二分木ヒープ 様々なアルゴリズムにおいて ある要素の集合またはリストから 最小 な要素を取り 出す必要がある そのような場合に使われる標準的データ構造が二分木ヒープ (binary heap) である あるオブジェクトO を考える そのオブジェクトは ラベル O. label と値 O. value を持つとする このようなオブジェクトを保存する二分木ヒープについて考える 二分木ヒープは以下の二つの制約のある二分木である

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

C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ

C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ 今回のプログラミングの課題 次のステップによって 徐々に難易度の高いプログラムを作成する ( 参照用の番号は よくわかる C 言語 のページ番号 ) 1. キーボード入力された整数 10 個の中から最大のものを答える 2. 整数を要素とする配列 (p.57-59) に初期値を与えておき

More information

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

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

More information

Microsoft PowerPoint - 05.pptx

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

More information

alg2015-6r3.ppt

alg2015-6r3.ppt 1 アルゴリズムとデータ 構造 第 6 回探索のためのデータ構造 (1) 補稿 : 木の巡回 ( なぞり ) 2 木の巡回 ( 第 5 回探索 (1) のスライド ) 木の巡回 * (traverse) とは 木のすべての節点を組織だった方法で訪問すること 深さ優先探索 (depth-first search) による木の巡回 *) 木の なぞり ともいう 2 3 1 3 4 1 4 5 7 10

More information

Taro-スタック(公開版).jtd

Taro-スタック(公開版).jtd 0. 目次 1. 1. 1 配列によるの実現 1. 2 再帰的なデータ構造によるの実現 1. 3 地図情報処理 1. 4 問題 問題 1 グラフ探索問題 - 1 - 1. は データの出し入れが一カ所で行われ 操作は追加と削除ができるデータ構造をいう 出入口 追加 削除 操作 最初 111 追加 111 222 追加 111 222 333 追加 111 222 333 444 追加 111 222

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

今回のプログラミングの課題 ( 前回の課題で取り上げた )data.txt の要素をソートして sorted.txt というファイルに書出す ソート (sort) とは : 数の場合 小さいものから大きなもの ( 昇順 ) もしくは 大きなものから小さなもの ( 降順 ) になるよう 並び替えること

今回のプログラミングの課題 ( 前回の課題で取り上げた )data.txt の要素をソートして sorted.txt というファイルに書出す ソート (sort) とは : 数の場合 小さいものから大きなもの ( 昇順 ) もしくは 大きなものから小さなもの ( 降順 ) になるよう 並び替えること C プログラミング演習 1( 再 ) 4 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ 今回のプログラミングの課題 ( 前回の課題で取り上げた )data.txt の要素をソートして sorted.txt というファイルに書出す ソート (sort) とは : 数の場合 小さいものから大きなもの ( 昇順 ) もしくは 大きなものから小さなもの ( 降順

More information

040402.ユニットテスト

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

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

算法の設計と評価

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

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

模擬試験問題(第1章~第3章)

模擬試験問題(第1章~第3章) 基本情報技術者試験の練習問題 - 第 8 回 この問題は平成 19 年度秋期の問題から抜粋しています 問 1 次のプログラムの説明及びプログラムを読んで, 設問 1,2 に答えよ プログラムの説明 スタックを使って, 実数値を 10 進数字列 ( 文字列 ) に変換する副プログラム FloatFormat である (1) FloatFormat は, 実数 Float の値を 10 進数字列に変換し,

More information

Microsoft PowerPoint - kougi9.ppt

Microsoft PowerPoint - kougi9.ppt C プログラミング演習 第 9 回ポインタとリンクドリストデータ構造 1 今まで説明してきた変数 #include "stdafx.h" #include int _tmain(int argc, _TCHAR* argv[]) { double x; double y; char buf[256]; int i; double start_x; double step_x; FILE*

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プログラミング応用演習 第 4 回再帰的構造体 前回の出席確認演習 #include int main() { FILE *fp; int c, linecount, length, maxlength; fp=fopen("/usr/share/dict/words","r"); if (fp == NULL) return 1; linecount=0; length=0;

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

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 回 ) 2016/05/10 DEPARTMENT OF MATHEMATICA INFORMATICS 1 内容 リスト 疎行列 2 連結リスト (inked ists) オブジェクトをある線形順序に並べて格納するデータ構造 単方向連結リスト (signly linked list) の要素 x キーフィールド key ポインタフィールド next x->next:

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

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

Microsoft PowerPoint - algo ppt [互換モード] ( 復習 ) アルゴリズムとは アルゴリズム概論 - 探索 () - アルゴリズム 問題を解くための曖昧さのない手順 与えられた問題を解くための機械的操作からなる有限の手続き 機械的操作 : 単純な演算, 代入, 比較など 安本慶一 yasumoto[at]is.naist.jp プログラムとの違い プログラムはアルゴリズムをプログラミング言語で表現したもの アルゴリズムは自然言語でも, プログラミング言語でも表現できる

More information

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

Microsoft PowerPoint - 13.ppt [互換モード] 13. 近似アルゴリズム 1 13.1 近似アルゴリズムの種類 NP 困難な問題に対しては多項式時間で最適解を求めることは困難であるので 最適解に近い近似解を求めるアルゴリズムが用いられることがある このように 必ずしも厳密解を求めないアルゴリズムは 大きく分けて 2 つの範疇に分けられる 2 ヒューリスティックと近似アルゴリズム ヒュ- リスティクス ( 発見的解法 経験的解法 ) 遺伝的アルゴリズム

More information

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

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

More information

次に示す数値の並びを昇順にソートするものとする このソートでは配列の末尾側から操作を行っていく まず 末尾の数値 9 と 8 に着目する 昇順にソートするので この値を交換すると以下の数値の並びになる 次に末尾側から 2 番目と 3 番目の 1

次に示す数値の並びを昇順にソートするものとする このソートでは配列の末尾側から操作を行っていく まず 末尾の数値 9 と 8 に着目する 昇順にソートするので この値を交換すると以下の数値の並びになる 次に末尾側から 2 番目と 3 番目の 1 4. ソート ( 教科書 p.205-p.273) 整列すなわちソートは アプリケーションを作成する際には良く使われる基本的な操作であり 今までに数多くのソートのアルゴリズムが考えられてきた 今回はこれらソートのアルゴリズムについて学習していく ソートとはソートとは与えられたデータの集合をキーとなる項目の値の大小関係に基づき 一定の順序で並べ替える操作である ソートには図 1 に示すように キーの値の小さいデータを先頭に並べる

More information

PowerPoint Template

PowerPoint Template プログラミング演習 Ⅲ Linked List P. Ravindra S. De Silva e-mail: ravi@cs.tut.ac.jp, Room F-413 URL: www.icd.cs.tut.ac.jp/~ravi/prog3/index_j.html 連結リストとは? 一つひとつの要素がその前後の要素との参照関係をもつデータ構造 A B C D 連結リストを使用する利点 - 通常の配列はサイズが固定されている

More information

離散数学

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

More information

計算幾何学入門 Introduction to Computational Geometry

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

More information

memo

memo 計数工学プログラミング演習 ( 第 6 回 ) 2017/05/16 DEPARTMENT OF MATHEMATICAL INFORMATICS 1 今日の内容 : 再帰呼び出し 2 分探索木 深さ優先探索 課題 : 2 分探索木を用いたソート 2 再帰呼び出し 関数が, 自分自身を呼び出すこと (recursive call, recursion) 再帰を使ってアルゴリズムを設計すると, 簡単になることが多い

More information

学習指導要領

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

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

Taro-リストⅢ(公開版).jtd

Taro-リストⅢ(公開版).jtd リスト Ⅲ 0. 目次 2. 基本的な操作 2. 1 リストから要素の削除 2. 2 リストの複写 2. 3 リストの連結 2. 4 問題 問題 1 問題 2-1 - 2. 基本的な操作 2. 1 リストから要素の削除 まず 一般的な処理を書き つぎに 特別な処理を書く 一般的な処理は 処理 1 : リスト中に 削除するデータを見つけ 削除する場合への対応 特別な処理は 処理 2 : 先頭のデータを削除する場合への対応

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

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

スライド 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

データ構造

データ構造 アルゴリズム及び実習 7 馬青 1 表探索 定義表探索とは 表の形で格納されているデータの中から条件に合ったデータを取り出してくる操作である 但し 表は配列 ( 連結 ) リストなどで実現できるので 以降 表 の代わりに直接 配列 や リスト などの表現を用いる場合が多い 表探索をただ 探索 と呼ぶ場合が多い 用語レコード : 表の中にある個々のデータをレコード (record) と呼ぶ フィールド

More information

Microsoft PowerPoint - 6.pptx

Microsoft PowerPoint - 6.pptx 6. データ構造入門 6-1. 連結リスト (Linked List) 6-2. スタック (Stack) 6-. キュー (Queue) 6-4. デク (Double-Ended-Queue) 6-. 抽象データ型 (Abstract Data Type) データ構造とは データの保存を効率的に行うもの 1 ito 2.712.14 suzuki データ構造 1 2 6-1. 連結リスト (Linked

More information

14.Graph2

14.Graph2 アルゴリズム論第 (1クラス) 第 14 回 (2018/01/17) 情報学専攻庄野逸 (shouno@uc.c.jp) ( 3 号館 313 号室 ) 本 のお題 [ 復習 ] グラフとは グラフの基本概念と 語 グラフの実現 法 グラフを いた問題 最短経路問題 Dijkstr アルゴリズム,APSP 問題と Floy アルゴリズム 有向グラフ (DAG) とトポロジカルソート 最 全域 (Minimum

More information

学習指導要領

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

More information

プログラミングI第10回

プログラミングI第10回 プログラミング 1 第 10 回 構造体 (3) 応用 リスト操作 この資料にあるサンプルプログラムは /home/course/prog1/public_html/2007/hw/lec/sources/ 下に置いてありますから 各自自分のディレクトリにコピーして コンパイル 実行してみてください Prog1 2007 Lec 101 Programming1 Group 19992007 データ構造

More information

目次 ペトリネットの概要 適用事例

目次 ペトリネットの概要 適用事例 ペトリネットを利用した状態遷移テスト 和田浩一 東京エレクトロン SDC FA グループ 目次 ペトリネットの概要 適用事例 ペトリネットの概要 - ペトリネットとは ペトリネット (Petri Net) とは カール アダム ペトリが 1962 年に発表した離散分散システムを数学的に表現する手法である 視覚的で 数学的な離散事象システムをモデル化するツールの一つである ペトリネットの概要 - ペトリネットの表記と挙動

More information

ミクロ経済学Ⅰ

ミクロ経済学Ⅰ 労働需要 労働力を雇う側の意思決定 労働力を雇うのは企業と仮定 企業は利潤を最大化する 利潤最大化する企業は どのように労働力を需要するか? まず 一定の生産量を生産する際の 費用最小化問題から考察する 企業の費用最小化 複数の生産要素を用いて生産活動を行なう企業を想定 min C( w, r; y) = wl + rk LK, subject to FKL (, ) y Cwr (, ; y) 費用関数

More information

INTRODUCTION TO ALGORITHMS

INTRODUCTION TO ALGORITHMS 20.7.7 関根渓 ( 情報知識ネットワーク研究室 B4) INTRODUCTION TO LGORITHMS 6. Heapsort CONTENTS 6. ヒープ (Heap) 6.2 ヒープ条件の維持 (Maintaining the heap property) 6.3 ヒープの構成 (Building a heap) 6.4 ヒープソート (The heapsort algorithm)

More information

学習指導要領

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

More information

講義の進め方 第 1 回イントロダクション ( 第 1 章 ) 第 2 ~ 7 回第 2 章 ~ 第 5 章 第 8 回中間ミニテスト (11 月 15 日 ) 第 9 回第 6 章 ~ 第 回ローム記念館 2Fの実習室で UML によるロボット制御実習 定期試験 2

講義の進め方 第 1 回イントロダクション ( 第 1 章 ) 第 2 ~ 7 回第 2 章 ~ 第 5 章 第 8 回中間ミニテスト (11 月 15 日 ) 第 9 回第 6 章 ~ 第 回ローム記念館 2Fの実習室で UML によるロボット制御実習 定期試験 2 ソフトウェア工学 第 7 回 木曜 5 限 F205 神原弘之 京都高度技術研究所 (ASTEM RI) http://www.metsa.astem.or.jp/se/ 1 講義の進め方 第 1 回イントロダクション ( 第 1 章 ) 第 2 ~ 7 回第 2 章 ~ 第 5 章 第 8 回中間ミニテスト (11 月 15 日 ) 第 9 回第 6 章 ~ 第 12 14 回ローム記念館 2Fの実習室で

More information

Microsoft PowerPoint - 7.pptx

Microsoft PowerPoint - 7.pptx 7. 木構造 7-1. データ構造としての木 グラフ理論での木の定義 根付き木 7-2.2 分探索木 7-3. 高度な木 ( 平衡木 ) AVL 木 B 木 1 7-1 1. データ構造としての木 2 木構造 木構造を表すデータ構造の一つとしてヒープがある しかし ヒープでは 配列を用いプではるため 要素数で木の形状が一通りに決定してしまった ここでは 再帰的なデータ構造を用いることにより より柔軟な木構造が構築可能なより柔軟な木構造が構築可能なことを見ていく

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション プログラミング応用演習 第 4 回再帰的構造体 プログラミングを 余談 : 教えることの難しさ 丁寧に説明しないと分かってもらえない 説明すると 小難しくなる学生が目指すべきところプログラム例を説明されて理解できる違うやり方でも良いので自力で解決できる おっけー 動けば良い という意識でプログラミング 正しく動くことのチェックは必要 解答例と自分のやり方との比較が勉強になる 今日のお題 再帰的構造体

More information

Microsoft PowerPoint - ppt-7.pptx

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

More information

[Problem D] ぐらぐら 一般に n 個の物体があり i 番目の物体の重心の x 座標を x i, 重さを w i とすると 全体の n 重心の x 座標と重さ w は x = ( x w ) / w, w = w となる i= 1 i i n i= 1 i 良さそうな方法は思いつかなかった

[Problem D] ぐらぐら 一般に n 個の物体があり i 番目の物体の重心の x 座標を x i, 重さを w i とすると 全体の n 重心の x 座標と重さ w は x = ( x w ) / w, w = w となる i= 1 i i n i= 1 i 良さそうな方法は思いつかなかった [Problem D] ぐらぐら 一般に n 個の物体があり 番目の物体の重心の x 座標を x, 重さを w とすると 全体の n 重心の x 座標と重さ w は x = ( x w ) / w, w = w となる = n = 良さそうな方法は思いつかなかった アイデア募集中!!! ので 少し強引に解いている 入力データの読み込みは w と h を scanf で読み込み getchar でその行の行末コードを読み込み

More information

Microsoft PowerPoint - 09.pptx

Microsoft PowerPoint - 09.pptx 情報処理 Ⅱ 第 9 回 2014 年 12 月 22 日 ( 月 ) 関数とは なぜ関数 関数の分類 自作関数 : 自分で定義する. ユーザ関数 ユーザ定義関数 などともいう. 本日のテーマ ライブラリ関数 : 出来合いのもの.printf など. なぜ関数を定義するのか? 処理を共通化 ( 一般化 ) する プログラムの見通しをよくする 機能分割 ( モジュール化, 再利用 ) 責任 ( あるいは不具合の発生源

More information

技術知識 11 ディスタンスベクターとリンクステート ディスタンスベクターとは 噂話が好きな奥様達による伝言ゲームである リンクステートとは 同じカーナビをつけた走り屋の集団である... 私の先輩の格言より * * * ルーティングプロトコルの仕組みに

技術知識 11 ディスタンスベクターとリンクステート ディスタンスベクターとは 噂話が好きな奥様達による伝言ゲームである リンクステートとは 同じカーナビをつけた走り屋の集団である... 私の先輩の格言より * * * ルーティングプロトコルの仕組みに 技術知識 11 ディスタンスベクターとリンクステート ----------------------- ディスタンスベクターとは 噂話が好きな奥様達による伝言ゲームである リンクステートとは 同じカーナビをつけた走り屋の集団である... 私の先輩の格言より * * * ルーティングプロトコルの仕組みには 大別して ディスタンスベクター型 と リンク ステート型 の 2 種類がある というようなことが

More information

学習指導要領

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

More information

Microsoft PowerPoint - C4(反復for).ppt

Microsoft PowerPoint - C4(反復for).ppt C 言語プログラミング 繰返し ( for 文と while 文 ) 例題 (10 個のデータの平均を求める ) 手順 入力データをx1,x2,,x10 として, (x1+x2+x3+x4+x5+x6+x7+x8+x9+x10)/10 を計算する データ数が,1000 個,10000 個, となったらどうする? データ数個分の 変数の宣言, scanf 関数の呼出し, 加算式の記述 が必要 1 総和を求めること

More information

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

Microsoft PowerPoint - ca ppt [互換モード] 大阪電気通信大学情報通信工学部光システム工学科 2 年次配当科目 コンピュータアルゴリズム 良いアルゴリズムとは 第 2 講 : 平成 20 年 10 月 10 日 ( 金 ) 4 限 E252 教室 中村嘉隆 ( なかむらよしたか ) 奈良先端科学技術大学院大学助教 y-nakamr@is.naist.jp http://narayama.naist.jp/~y-nakamr/ 第 1 講の復習

More information

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

Microsoft PowerPoint - LDW.ppt [互換モード] グラフ系列マイニング 猪口明博大阪大学産業科学研究所科学技術振興機構さきがけ 研究の背景 データマイニング インフラ技術の高度化 多様で大規模な情報やデータへのアクセス, 蓄積が容易. 多様で大規模なデータから有用な知識を発掘することは重要な課題. 頻出アイテム集合マイニング [Arawal 9] 頻出アイテム集合列挙問題 一般に多くの事例を説明する知識は有用である. バスケット分析 Raw Data

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション 部内向けスキルアップ研修 組込み OS 自作入門 2014 年 2 月 10st ステップ担当 : 中村 目次 はじめに OSの役割 メモリ管理 メモリ管理実装 プログラムの実行 まとめ はじめに 前回やったこと OS の原型を作成 今回やること 9th ステップでは CPU 時間 という資源管理 本ステップでは メモリ という資源管理 10.1 OS の役割 10.1.1 コンピュータの 3 大要素

More information

NetworkKogakuin12

NetworkKogakuin12 最短経路をもとめるダイクストラ法 ダイクストラ法はグラフの各点から特定の点への最短距離 ( 経路 ) を逐次的に (= 1 台のコンピュータで ) もとめる方法である. ダイクストラ法 = ダイクストラののアルゴリズム 数学的なネットワーク ( グラフ ) のアルゴリズムとしてもっとも重要なものの ひとつである. 入力 グラフ ( ネットワーク ) グラフ上の終点 ( 特定の点 ) 14 3 4 11

More information

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

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

More information

学習指導要領

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

More information

Microsoft Word - no202.docx

Microsoft Word - no202.docx 6.4 ポインタと配列 ポインタ変数は前回説明したように 値の入っているアドレスを示す変数です では 配列はどの ようにメモリ上に格納されるか調べてみましょう ex67.c /* ポインタと配列の関係 */ int a[3]={1, 2, 3; /* int 型の大きさ 3 の配列として宣言 */ int *i; /* int 型へのポインタとして宣言 */ double x[3] = {1.0,

More information

Microsoft Word - no202.docx

Microsoft Word - no202.docx 1.4 ポインタと配列 ポインタ変数は前回説明したように 値の入っているアドレスを示す変数です では 配列はどの ようにメモリ上に格納されるか調べてみましょう ex07.c /* ポインタと配列の関係 */ int a[3]={1, 2, 3; /* int 型の大きさ 3 の配列として宣言 */ int *i; /* int 型へのポインタとして宣言 */ double x[3] = {1.0,

More information

学習指導要領

学習指導要領 (1) 数と式 学習指導要領ア数と集合 ( ア ) 実数数を実数まで拡張する意義を理解し 簡単な無理数の四則計算をすること 都立大江戸高校学力スタンダード 平方根の意味を理解し 平方根の計算法則に従って平方根を簡単にすることができる ( 例 1) 次の値を求めよ (1)5 の平方根 () 81 ( 例 ) 次の数を簡単にせよ (1) 5 () 7 1 (3) 49 無理数の加法や減法 乗法公式を利用した計算がで

More information

memo

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

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

アクション講座 第1回目

アクション講座 第1回目 アクション講座第 1 回目 講師 : ウェンディアーサー (WENDY ARTHUR) 講座資料のプロジェクトファイル (zip ファイル ) はソフメ wiki にアップしてますので予めダウンロードしておいてください 講座資料のプロジェクトファイル (zip ファイル ) は解凍してソリューションファイルを開く URL は下記 http://softmedia.sakura.ne.jp/wiki/2017%e5%b9%b4%e5%ba%a6_%e3%82%a2%e3

More information

nlp1-04a.key

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

More information

2006年10月5日(木)実施

2006年10月5日(木)実施 2010 年 7 月 2 日 ( 金 ) 実施 ファイル処理ファイルとはファイル (file) は日常用語では紙などを綴じたものを表すが, コンピュータ用語ではデータの集合体を指す言葉である ファイルは例えば, 文書ファイルやプログラムファイルのように, 用途によって分類されることもあれば, また, テキストファイルやバイナリファイルのように, ファイルの作り方によって分類されることもある なお,

More information

生命情報学

生命情報学 生命情報学 34 進化系統樹推定 阿久津達也 京都大学化学研究所 バイオインフォマティクスセンター 進化系統樹 進化系統樹 種間 もしくは遺伝子間 の進化の関係を表す木 以前は形態的特徴をもとに構成 現在は配列情報をもとに構成 有根系統樹と無根系統樹 有根系統樹 : 根 共通の祖先に対応 がある系統樹 無根系統樹 : 根のない系統樹 いずれも葉にのみラベル 種に対応 がつく 有根系統樹 無根系統樹

More information

(c) 規模に関して収穫一定の生産技術をもっているから, 総費用は直線で表され, また平均費用も限界費用も同様に直線で表されかつフラットな形状になる. 問 (b) の解答より, 1 脚当たりの総費用は $65( $390 / 6 ) であるから, 各費用関数は図 9.12 のように描くことができる.

(c) 規模に関して収穫一定の生産技術をもっているから, 総費用は直線で表され, また平均費用も限界費用も同様に直線で表されかつフラットな形状になる. 問 (b) の解答より, 1 脚当たりの総費用は $65( $390 / 6 ) であるから, 各費用関数は図 9.12 のように描くことができる. 第 9 章生産技術と費用最小化 練習問題 9.1 の解答 (a) 椅子 4 脚および 6 脚に対応する等量曲線は以下の図 9.10 のようになる.6 脚の場合の等量曲線について説明しておこう. 最低 12 時間の労働と 6 時間の旋盤加工が必要であり, かつ, 合計 36 時間の投入要素の組み合わせが必要になる. (b) 図 9.11 を用いて, 椅子 6 脚をつくる場合の最も安価な生産方法を求めてみる,

More information

PowerPoint Presentation

PowerPoint Presentation パターン認識入門 今回の話題 : パターン認識 長大な列 ( 例えば文章 ) から興味深い部分 ( 例えばある文字列を含む部分 ) を取り出したい ある文字列を含む web ページを抽出 プログラム中の特定の関数の呼び出しを DNA から面白そうな塩基配列を 例えば特定の塩基をたくさん含む場所を スパムメールの識別 B-CAS だけでなく B-C@S なども検出したい 2 簡単なパターン認識 : 文字列検索

More information

Microsoft Word - NumericalComputation.docx

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

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

Microsoft PowerPoint - exp2-02_intro.ppt [互換モード]

Microsoft PowerPoint - exp2-02_intro.ppt [互換モード] 情報工学実験 II 実験 2 アルゴリズム ( リスト構造とハッシュ ) 実験を始める前に... C 言語を復習しよう 0. プログラム書ける? 1. アドレスとポインタ 2. 構造体 3. 構造体とポインタ 0. プログラム書ける? 講義を聴いているだけで OK? 言語の要素技術を覚えれば OK? 目的のプログラム? 要素技術 データ型 配列 文字列 関数 オブジェクト クラス ポインタ 2 0.

More information

自然言語は曖昧性だらけ! I saw a girl with a telescope 構文解析 ( パージング ) は構造的な曖昧性を解消 2

自然言語は曖昧性だらけ! I saw a girl with a telescope 構文解析 ( パージング ) は構造的な曖昧性を解消 2 自然言語処理プログラミング勉強会 12 係り受け解析 Graham Neubig 奈良先端科学技術大学院大学 (NAIST) 1 自然言語は曖昧性だらけ! I saw a girl with a telescope 構文解析 ( パージング ) は構造的な曖昧性を解消 2 構文解析の種類 係り受け解析 : 単語と単語のつながりを重視 I saw a girl with a telescope 句構造解析

More information

Microsoft PowerPoint - 4.pptx

Microsoft PowerPoint - 4.pptx while 文 (1) 繰り返しの必要性 while の形式と動作 繰り返しにより平 根を求める ( 演習 ) 繰り返しにより 程式の解を求める ( 課題 ) Hello. をたくさん表示しよう Hello. を画面に 3 回表示するには, 以下で OK. #include int main() { printf("hello. n"); printf("hello. n");

More information

チェビシェフ多項式の2変数への拡張と公開鍵暗号(ElGamal暗号)への応用

チェビシェフ多項式の2変数への拡張と公開鍵暗号(ElGamal暗号)への応用 チェビシェフ多項式の 変数への拡張と公開鍵暗号 Ell 暗号 への応用 Ⅰ. チェビシェフ Chbhv Chbhv の多項式 より であるから よって ここで とおくと coθ iθ coθ iθ iθ coθcoθ 4 4 iθ iθ iθ iθ iθ i θ i θ i θ i θ co θ co θ} co θ coθcoθ co θ coθ coθ したがって が成り立つ この漸化式と であることより

More information

Microsoft PowerPoint - 5Chap10.ppt

Microsoft PowerPoint - 5Chap10.ppt 第 11 章関数について 11.1 標準ライブラリ関数 11. 関数呼び出しのオーバーヘッド 11. 大域変数 11.4 プロトタイプ宣言数学関数の自作 11.1 標準ライブラリ関数 予め定義されており ユーザが定義 作成しなくても使える関数 ヘッダ部に以下のマクロが必要 #iclude pritf, scf 等の入出力関数 sqrt, si 等の数学関数 #iclude

More information

Microsoft Word _Gmail利用マニュアル.doc

Microsoft Word _Gmail利用マニュアル.doc Gmail 利用マニュアル メディアセンター 2014/4/10 Ver1.3 目次 1. ログイン 1 2. メールの受信 2 3. メールの削除 振り分け 5 4. メールの返信 7 5. メールの作成 9 6. ログアウト 10 7. メールの自動転送 11 8. 便利に使うために 13 1. ログイン (1) ログインメールアドレス パスワードを入力してください メール 部分に @ マーク以降のドメインを含むメールアドレスを入力してください

More information

プログラミング実習I

プログラミング実習I プログラミング実習 I 05 関数 (1) 人間システム工学科井村誠孝 m.imura@kwansei.ac.jp 関数とは p.162 数学的には入力に対して出力が決まるもの C 言語では入出力が定まったひとまとまりの処理 入力や出力はあるときもないときもある main() も関数の一種 何かの仕事をこなしてくれる魔法のブラックボックス 例 : printf() 関数中で行われている処理の詳細を使う側は知らないが,

More information

66~ 274~600 ~26,948 ~961. ~ 66~ 69~ ~ ~53

More information

Taro-リストⅠ(公開版).jtd

Taro-リストⅠ(公開版).jtd 0. 目次 1. 再帰的なデータ構造によるリストの表現 1. 1 リストの作成と表示 1. 1. 1 リストの先頭に追加する方法 1. 1. 2 リストの末尾に追加する方法 1. 1. 3 昇順を保存してリストに追加する方法 1. 2 問題 問題 1 問題 2-1 - 1. 再帰的なデータ構造によるリストの表現 リストは データの一部に次のデータの記憶場所を示す情報 ( ポインタという ) を持つ構造をいう

More information

スライド タイトルなし

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

More information

学習指導要領

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

More information

ファイナライザを理解する ~ ファイナライザに起因するトラブルを避けるために ~ 2013 年 11 月 25 日 橋口雅史 Java アプリケーションでファイナライザ (finalize() メソッド ) を使用したことがあるプログラマーは多いと思います しかし ファイナライザの仕組みや注意点につ

ファイナライザを理解する ~ ファイナライザに起因するトラブルを避けるために ~ 2013 年 11 月 25 日 橋口雅史 Java アプリケーションでファイナライザ (finalize() メソッド ) を使用したことがあるプログラマーは多いと思います しかし ファイナライザの仕組みや注意点につ ファイナライザを理解する ~ ファイナライザに起因するトラブルを避けるために ~ 2013 年 11 月 25 日 橋口雅史 Java アプリケーションでファイナライザ (finalize() メソッド ) を使用したことがあるプログラマーは多いと思います しかし ファイナライザの仕組みや注意点について 理解したうえで使っているでしょうか? アプリケーション プログラムでファイナライザを使用する場合は

More information

コンピュータグラフィックスS 演習資料

コンピュータグラフィックスS 演習資料 コンピュータグラフィックス S 演習資料 第 4 回シェーディング マッピング 九州工業大学情報工学部システム創成情報工学科講義担当 : 尾下真樹 1. 演習準備 今回の演習も 前回までの演習で作成したプログラムに続けて変更を行う まずは シェーディングの演習のため 描画処理で 回転する一つの四角すいを描画するように変更する 画面をクリア ( ピクセルデータと Z バッファの両方をクリア ) glclear(

More information

8. 自由曲線と曲面の概要 陽関数 陰関数 f x f x x y y y f f x y z g x y z パラメータ表現された 次元曲線 パラメータ表現は xyx 毎のパラメータによる陽関数表現 形状普遍性 座標独立性 曲線上の点を直接に計算可能 多価の曲線も表現可能 gx 低次の多項式は 計

8. 自由曲線と曲面の概要 陽関数 陰関数 f x f x x y y y f f x y z g x y z パラメータ表現された 次元曲線 パラメータ表現は xyx 毎のパラメータによる陽関数表現 形状普遍性 座標独立性 曲線上の点を直接に計算可能 多価の曲線も表現可能 gx 低次の多項式は 計 8. 自由曲線 曲面. 概論. ベジエ曲線 曲面. ベジエ曲線 曲面の数学. OeGLによる実行. URS. スプライン関数. スプライン曲線 曲面. URS 曲線 曲面 4. OeGLによる実行 8. 自由曲線と曲面の概要 陽関数 陰関数 f x f x x y y y f f x y z g x y z パラメータ表現された 次元曲線 パラメータ表現は xyx 毎のパラメータによる陽関数表現 形状普遍性

More information

同期 - Synchronization

同期 - Synchronization 同期 - Synchronization JOI Open Contest 2013 問題の概要 木があり 頂点 i は最初情報 i を持っている 1 2 3 4 5 問題の概要 各辺には ON/OFF の属性があり,ON の辺を介した 2 つの頂点の持っている情報が異なると情報がコピーされて両方の頂点が同じ情報を持つようになる 1 2 3 4 5 問題の概要 最初すべての辺が OFF だが 辺の属性が変更されまくる

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