contemporary algorhythm 05

いままで
basic technique

online algorithm

difficulty computatation time

lack of information
不完全な情報でも、うごくアルゴリズムの開発

株式投資
１０００株　A社
ある株式を買うかどうかをきめるには過去の情報しか参考にできない。
未来の情報はない。

example beer restaurant
１杯　５００円
１５００円　飲み放題

どちらが得なのか？
What is the best algorithm?
翌日に授業があるなら、その日は飲み放題にしないほうがいい。

飲み放題で、注文したら、１杯目をあけたところで、麻雀の誘いの電話がかかってきて
居酒屋をでる必要がでてきたら、まちがった選択をしたことになる。

input

output

drink
then another beer or nomihoudai
algorithm
without any future information
specify the action definitely

algorithm always glass
algorithm2 nomihoudai
algorithm3 ２杯目まではglass ３杯目から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 その日に５杯のむことがわかっている　みたいな。something like God

How well the algorithm play against the god
algorithm 2 cr 3
500 １杯目　cr
1000　２杯目
2500　３杯目以降 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
一番、はじめの検索で「監事」が欲しいときのコスト４

２階目の仮名漢字変換で再び「監事」が欲しいときのコスト１

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