Design and Analysis of Information
Systems
情報システム評価学
徳山 豪Takeshi TokuyamaSelf Introduction 自己紹介
• Takeshi Tokuyama– Mathematician, and computer scientist• Graduate （Dr. Science in math) in 1985
– Ph. D Thesis, Group representation theory• Joined IBM Research, Tokyo Research Lab.
– Computer Science– Solve math problems• Answer to anything– Algebra, geometry,analysis,statistics, …

– Tohoku U from 1999

How to learn mathematics• Study modern mathematical theory and advanced topics
最新の数学理論やトピックを学ぶ： 通常の大学講義– It is important to know why you want to study it
なぜそれを学ぶのかが判っていないと身につかない•••

History of mathematics
Big projects of modern mathematics
Important applications of the theory– Read books about history /documentary of mathematics
そのためには、数学の歴史や啓蒙書を読みなさい
•
•
•
•
•

E.T. Bell: Men of mathematics (数学を作った人々）
Simon Singh： The Code Book (暗号解読）
S.Singh:Fermat’s last theorem (フェルマーの最終定理)
秋月康夫： 輓近代数学の展望
P．Hoffman： The man who loved only numbers （放浪の数学者エルデシュ）• Learn from interesting mathematical problems and solutions
面白い問題と解答から学んでいく： 私の好きな方法– My favorite style!

Lecture outline （講義概要）• Joy of mathematics 数学の楽しみ– Use some mathematical puzzles– Know typical way of thinking of mathematics
数学パズルを通して数学の考え方を学ぶ• How to use mathematics to computer science– Algorithms and Computation– Complexity Theory
数学のコンピュータサイエンスへの利用を学ぶ•

Text of today– Peter Winkler ： Mathematical Puzzle• He was a research staff in Bell Lab, ATT

Day 1
Game ,Gamble, and Probability

Problem 1• Alice choose any two natural numbers a and bsuch that a<b<53 , and write them on two sheets.
アリスは２つの自然数を選んでそれぞれ紙に書く• Tom choose any one of sheets, and see thenumber. トムはどちらか片方を見る• Tom tells which he saw, a or b.
トムは見た数がa かbか答える• What is Tom’s strategy? トムの戦略は？
– If Alice knows the strategy???

• What is Alice’s strategy?アリスの戦略は？

A variation• Alice choose any two natural numbers a and bsuch that a<b<53 , and write them on two sheets.
アリスは２つの自然数を選んでそれぞれ紙に書く• Alie choose any one of sheets, and let Tom see
the number. アリスは好きなほうを選びトムに見せる• Tom tells which he saw, a or b.
トムは見た数がa かbか答える• What is Tom’s strategy? トムの戦略は？
• What is Alice’s strategy?アリスの戦略は？

Problem 2
You go to casino in Las Vegas, and the dealer
reveals 52 cards (26 red, 26 black) one by one.
• You have 1000 dollar, and can bet to “red”
and “black” 52 times. You can split money tocents, and also bet the money you obtained sofar. What is your strategy?
• You need to pay x dollars to trip to Las
Vegas(you can pay after coming back). Whatis the value of x you afford to pay?

Expectation• 2n C n ~ 22n / (nπ ) ½• 2n=52  22n /9• A very elementary case of central limit theorem• Loomis’s lemma
In two-player’s game, for any given distribution ofstrategy of the opponent, there is a pure strategy tomaximize the profit.
(A key lemma for von Neumann’s minmax theorem) Expectation is know, then, derandomize!
 Method of conditional probability

Ramdomized Algorithm• Rajeev Motwani and Prabhakar Raghavan
Randomized Algorithms (Cambridge Press 1995)
Rajeev was supervisor of Brin and Page (foundersof Google) , and he was a mentor of Google andmany venture business at Silicon valley
Prabhakar was my colleague in IBM Research,and now director of Yahoo Research