読者です 読者をやめる 読者になる 読者になる

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