期限：2月9日.
2問以上選択して「徳山にとって満足な解答」をしてください。
(満足な解答の無い場合は可になり、まともなレポートで無い場合は不可もある)。
ただし、 1問でもセンスのいい回答には高得点をあげます。 オリジナリティーを高く評価します.
問題１
スキーレンタル問題のオンラインアルゴリズムで、授業では競合比２を示し、決定的アルゴリズムでは最適であることを示しました。 ランダムアルゴリズムを用いてこの競合比が改良できるかどうか検討し、改良できるならアルゴリズムと解析を、出来ない場合は出来ないと考えた理由を示しなさい
問題2
平面上に軸方向の単位正方形の障害物が多数あるとします。ロボットが原点を出発し、終点$(n,0)$ までの経路を探すとします。
障害物は互いに接触せず、ロボットは平面上の点と見なし、障害物間をすり抜けることが出来るとします。
ロボットは東西南北のどちらかに向きを変えることができ、障害物に触れると障害物の位置（端点の位置）をセンサーで知る事が出来ます。 ロボットは計算能力と記憶装置を持ち、自分の位置と方向の情報、終点の座標を知っていますが，
障害物の位置について事前知識は無く、触れていない障害物の位置はわかりません。
ロボットが終点までできるだけ短い経路で到達するようなアルゴリズムを設計し、最適経路長を$L$とした場合、$L$に対する競合比
を求めなさい。 下記文献を調べても良い(電気通信研究所図書にあるはず)
Christos
H. Papadimitriou, Mihalis Yannakakis: Shortest Paths Without a Map. Theor.
Comput. Sci. 84(1): 127-150 (1991)
問題3 2人のプレーヤーAとBが対戦します。 それぞれが0もしくは１を出力し、同時にAは0から2までの数を指定します。
AとBの出力和が指定通りならAが1点獲得します。 プレーヤーAのシステムをオンライン学習理論を用いて考案しなさい。 いくつかの戦略を考え、それらをエキスパートとして最も良いエキスパートとほぼ同等の結果を出せるシステムにすること。
問題 4
上記のシステムを実装し、実験しなさい。 Bの戦略としては、１． ランダム、 2．負けた場合だけ出力を変更 ３．０と１を交互
など数通り考える事。
問題 5 同様にじゃんけんを行うシステムを考案しなさい。 もしくは問題3において，各プレイヤーが０，１，２を出力し、Aが0から4までの
数を指定するというシステムでもよい。
問題 6フォンノイマンの最大最小原理の証明を行いなさい （参考書使用可。但し、利用する定理や道具はすべて解説するように）
問題 7 問題３のゲームでのフォンノイマンの最大最小原理の意味での均衡戦略を求めなさい。 但し、BはAの得点を最小化する。 均衡戦略でのAの得点の期待値を求めなさい。
問題 8 ページング問題のアルゴリズムをいくつか実装し、実験しなさい。 実験の場合のアクセスは（メモリサイズをｋとした時に）
ｋ＋２個のページを用いて、ランダム生成と、「１，２，３，４，.., ｋ＋２」を
繰り返すアクセス 、 繰り返しアクセスとランダムを適当に混ぜたアクセスの3通りを試しなさい。
問題 9
自分が専門とし、興味を持っている科学の問題について 徳山にわかるように説明してください。