平成  年  月  日

九州大学工学部地球環境工学科船舶海洋システム工学コース

平成 ¿¼ 年度システム設計工学 定期試験問題
問題１
以下はある造船所で建造された肥大船の主要目と、あるフルード 数におけるその船の流体抵抗値についての水槽試験データである。
要目＼船の番号

            
        

剰余抵抗値





？

このとき以下の問いに答えよ。
（  点）【問１１】
上記の表において、 の船についての剰余抵抗値が不明なので、表のデータを利用して、この新しい船における抵抗値について多重回帰を用いて推定したい。
上記の表データの数字を用いて式を作り、計算手順を説明せよ。
【問１２】（  点）
問１１の推定をより精度良く行うため、以下のような  通りの工夫を検討した。
このとき、明らかに推定計算上不都合が生じると考えられるものを全て挙げ、その理由を説明せよ。ただし単なる計算量の増加は、計算上の不都合とは考えないものとする。

 各船の特徴量として        に加えて、新しい特徴量       を導入し 、問１−１と同様の推定方法で計算をやり直す。
 各船の特徴量として        に加えて、新しい特徴量    

を導入し 、問１−１と同様の推定方法で計算をやり直す。
 上記の特徴量のうち、  の値はど の船もほとんど 変わらないので 、特徴量から除外し 、問１−１と同様の推定方法で計算をやり直す。
 新しく  の船についてのデータをテーブルに追加し 、問１−１と同様の推定方法で計算をやり直す。このとき、この  は  と同型船であるため、       の値は  と完全に同一であるが 、剰余抵抗値は若干異なっている。
 上記のデータのうち、 と  と  の剰余抵抗値は想定された営業フルード 数から大きく外れたフルード 数での抵抗値なので、これら３つのデータをテーブルから除外した上で、問１−１と同様の推定方法で計算をやり直す。

問題２
ボロノイ（  ）分割について以下の問いに答えよ。
【問２１】ボロノイ分割とは何か説明せよ。
（  点）【問２２】 次元平面において、ボロノイ分割の隣接する母点同士を結んだ線で構成される 角形による分割を何と呼ぶか？またその 角形の性質を説明せよ。
（  点）問題３
 点 ½    および ¾    を通り、点 ½ での接線方向ベクトルが接線方向ベクトルが ¾    で与えられる 次多項式曲線½  

 、点 ¾ での         ¼  ½  ¾   ¿ の係数ベクトルを全て求めよ。ただし  点間 ½ ¾ において媒介変数 はのとする。
（  点）

 の値をとるも問題４共役勾配法は、有限要素法などにおいて大規模な連立１次方程式    （ただし  は実対称正定値行列で表された係数行列、 は求める未知変数行列、 は係数行列）を解くのにも利用される。どのようにして共役勾配法により解くのか 、解法を説明せよ。またそれが効率良く解ける理由を説明せよ。
（  点）

問題５
組合せ最適化について、以下の問いに答えよ。
（ 各  点）【問５１】組合せ最適化問題等の難しさは 、それを解くときの「計算量」に基づいて３種類に分類される。このとき、この 種類の分類と、その分類において導入した概念について説明せよ。
【問５２】組合せ最適化問題に対する強力な解法の一つである「分枝限定法」とは、どのようなアルゴ リズムか説明せよ。またその特徴を述べよ。

問題６
解答用紙にある多目的最適化における解候補の目的関数値のプロットにおいて、パレ ート解集合を示せ。
（  点）

問題７
機械  によって製品が生産される工場がある．
機械  は「 稼働」「 不調」「故障」の３状態を有する．



機械の状態遷移は，一日おきに離散的に起きる．



機械が「 稼動」状態にあるとき、次の日は確率
確率  で「不調」状態へ遷移する







 で稼動状態を継続，機械が「 不調」状態にあるとき、次の日は確率  で稼動状態へ復帰，
確率  で「不調」状態を継続，確率  で故障する機械が「 故障」状態に陥ると、そこから抜け出せない機械が「 稼動」状態にある日は，翌日の状態に関係なく  万円の利益を得るが，「不調」状態の日の利益は  万円である（つまり翌日の状態には関係なく  万円の損失）．
「故障」状態では運転を止めるので損益はゼロである．

このとき以下の問に答えよ．
【問７１】「稼働」を状態 ，「 不調」を状態 ，「 故障」を状態 として状態遷移行列および報酬行列を示せ．
（  点）【問７２】「稼働」状態からスタートして故障状態へ陥るまでの平均日数を計算せよ．
（  点）【問７３】「不調」状態からスタートして故障状態へ陥るまでに得る利益合計の期待値を計算せよ．
（  点）

問題８２状態のマルコフ過程モデルを考える。観測データより得られた状態  から  への状態遷移回数を
 のように表す。マルコフモデルにおける状態  から  への状態遷移確率を  のように表す。このとき以下の問に答えよ。
【問８１】このマルコフモデルにおける観測データに関する尤度  を状態遷移確率 および 遷移回数     を用いて表せ。
（  点）  【問８２】このマルコフモデルの状態遷移確率     の最尤推定値 について、遷移回数     を用いて表せ。
（  点）

  【問８３】このマルコフモデルの状態遷移確率     は、構造上    であることが分かっている場合、上記の状態遷移確率の最尤推定値 を遷移回数     を用いて表せ。
（  点）

  

平成 ¿¼ 年度システム設計工学定期試験 解答
問題１【問１１】（  点）各船の特徴量        を以下の変数（説明変数） で表し 、推進抵抗 を以下の多重回帰によって説明する：

                  ただし       は回帰係数、 は確率変動（ 誤差）である。
ここで、表のデータを用いて、回帰係数   を求める。行と列を間違えないよう注意しながら表のデータを行列に変換すると、以下のようになる：                                                                                    と表す。ここで 、 行列  の最初の列の要素は  とする
 行列  には推定しようとする船（ここでは  ）のデータを含めない以上の点に注意。このとき      の誤差  の平方和を最小化する回帰係数 は        

剰余抵抗を推定する  の船の要目            
を                へ代入し 、上で求めた回 を使って                  より  の船の剰余抵抗の推定値
帰係数 を得る。この推定の式では誤差  の項は考えない。
【問１２】（  点）説明変数  について、任意の定数   を用いて関係式          に近い関係が成り立つとき、データは強い多重共線関係（ 多重共線性）があるという。このとき回帰係数を求める逆行列計算が不安定になり、無意味な解が出やすい。
ここで、問題文のうち、明らかに１番目の方法は上記の関係式を生み出してし まい、回帰係数ベクトルを求める逆行列計算ができないという不都合が生じる。
 番目の方法は、新しい説明変数を既存の説明変数から生成しているが 、非線形関数になっているので多重共線性は生じず、問題は無い。
番目の方法は説明変数を減らすだけなので何ら問題は生じない。
 番目の方法は、多重回帰は最小２乗法であり、データの重複は問題にはならない。
 番目の方法は、未知変数である回帰係数６コを求めるのにデータを削りすぎてデータが５コしかなくなってしまったので方程式を解くことができず、明らかに不都合が生じる。

問題２【問２１解答】（  点）空間中に配置されている複数の点（母点）の、どの点に最も近いかによって空間を分割してできる図をボロノイ図（   ）といい、その分割をボロノイ分割という。
【問２２解答】（  点）ド ロネー分割・ド ロネー図ド ロネー分割による 角形の外接円の中心はボロノイ分割における各ボロノイ点（ボロノイ分割の多角形の頂点）に等しい



ド ロネー 角形の外接円の内部に、他の母点は含まれない

問題３【 成分について 】点 ½ を通る条件より               点 ¾ を通る
条件より               ，点 ½ の傾きについての条件より             点 ¾ の傾きについての条件より            【 成分について 】点 ½ を通る条件より               点 ¾ を通る
条件より               ，点 ½ の傾きについての条件より            点 ¾ の傾きについての条件より             
以上の連立方程式をについてそれぞれ解いてまとめると、¼  ¿    （  点） ½   ¾    0-0.02-0.04

y-0.06-0.08-0.1-0.12-0.14曲線の形状は図のようになる：-0.1600.20.40.60.81x問題４
連立一次方程式    の各行列を用いて以下の２次形式コスト関数   を考える：

     

このコスト関数   を最小化する  を共役勾配法で求める。このとき、最小点では    より    を満たすので 、求める連立１次方程式の解を得る。
共役勾配法は  次元の２次形式コスト関数に対して  回のラインサーチで効率良く最適化を得られるため、上記の方法で効率良く連立１次方程式の解を得ることができる。
（  点）

問題５【問５１解答】（  点）問題解決（アルゴ リズム）に関して、以下の２つの概念を導入する：
１つは「決定性 !"#"$%#& 」と呼び 、アルゴ リズムの流れが確定していることを表わす。
もう  つは「非決定性 !"#"$%#& 」と呼び 、アルゴ リズムが分岐点にいるとき、常に正しい選択肢を選ぶ能力があることを仮定するものである。
このとき、組合せ最適化問題の難しさは以下の３種類に分類される。
Ｐ：決定性アルゴ リズムで多項式時間内で解決できる全ての問題。

ＮＰ：非決定性アルゴ リズムで、多項式時間内に解決できる全ての問題。

ＮＰ困難：ＮＰよりさらに困難な問題【問５２】（  点）分枝限定法は、解候補をツリー状の列挙図によって列挙・評価していく途中で、解の可能性の無い、あるいは可能性の低い枝を刈ることで探索空間を減らす探索方法である。この枝刈りを行う際、解の可能性の無い枝だけを刈れば最適解を得ることができる。

問題６6Risk3914710285Cost

リスクとコストは小さいほうが良いのでパレ ート解は0  （  点）

問題７
【問７−１解答】（  点）遷移確率は以下のとおり：遷移行列および 報酬行列は以下のとおり

             

【問７２】 点 遷移行列より基本行列  および     を計算すると、

       






よって吸収状態に陥るまでのステップ 数は、












このうち、「稼動」状態   からスタートするので 、答えは．

【問７３】 点 先に計算した     は、スタート状態から吸収状態に陥るまでに各状態を訪問した回数を表すので 、これに報酬行列を掛け合わせることで報酬合計を計算できる：





「不調」状態からスタートするので 、答えは  ．

問題８【問８１】（  点）尤度  は、このモデルからデータが観測される確率を表すので 、  ½½ ½¾ ¾½ ¾¾【問８２】（  点）ラグランジュの未定乗数法によって対数尤度を最大にする  を求めると、

 

ここでは、状態は２つである。よって

   

   

   

   
【問８３】（  点）対数尤度 '  は'  

 '    '    '    '   '    '     '     ' 


½½



を計算して整理すると、最尤推定値は

          

本試験問題および 解答に疑問がある場合は， 月  日（ 水）午後３時までに，Ｗ２号館６階６３４号室の木村まで申し出ること。

() #   *+$,



システム設計工学 解答用紙 学籍番号＿＿＿＿＿＿＿＿氏名＿＿＿＿＿＿＿＿＿＿＿
紙面が足りない場合は裏面も使用すること。

【問６】
6Risk

3
194725108
Cost0