contemporary algorhythm 05
いままで
basic technique
online algorithm
difficulty computatation time
lack of information
不完全な情報でも、うごくアルゴリズムの開発
株式投資
1000株 A社
ある株式を買うかどうかをきめるには過去の情報しか参考にできない。
未来の情報はない。
example beer restaurant
1杯 500円
1500円 飲み放題
どちらが得なのか?
What is the best algorithm?
翌日に授業があるなら、その日は飲み放題にしないほうがいい。
飲み放題で、注文したら、1杯目をあけたところで、麻雀の誘いの電話がかかってきて
居酒屋をでる必要がでてきたら、まちがった選択をしたことになる。
input
output
drink
then another beer or nomihoudai
algorithm
without any future information
specify the action definitely
algorithm always glass
algorithm2 nomihoudai
algorithm3 2杯目まではglass 3杯目からnomihoudai
which is the best ?
we need evaluation system
use the competitive ratio for evaluating online algorithm
the cost of algorithm when input i
the optimal algorithm for input i その日に5杯のむことがわかっている みたいな。something like God
How well the algorithm play against the god
algorithm 2 cr 3
500 1杯目 cr
1000 2杯目
2500 3杯目以降 cr 1.67
algorithm 3 is best never get better algorithm than 03
ski rental problem
the time when you want to go skiing
buy or rental
linear list search
kana kanji transform
'kanji'
hit the space key
漢字
when it is not what you want again hit the space key
'幹事"
hit again
'感じ'
"監事”
cost the frequency hit the button
「監事」を選んだら、次に、「かんじ」を変換するためにボタンをおすと、最初に出てくるのは「監事」になる。
input initial list sequence of request
action search
一番、はじめの検索で「監事」が欲しいときのコスト4
2階目の仮名漢字変換で再び「監事」が欲しいときのコスト1
goal minimize the total cost
strategy
moving accessed itme forward
question how many position?
to the top
by 2 position
to the middle
theorem
which is the best
move to top cr 2
proof very clever
at the beginning
opt list
move front list
amortized cost
when we lose we get something