數學建模思維day day up#Vol 3:What』s Our Average?
體驗數學魅力,培養建模思維
每次考試結束,你是不是都很想知道同桌考了多少分?不斷的以各種姿勢偷瞄、偷瞄、偷瞄、偷瞄,可還是看不到…
每次發工資的時候,你是不是都很想知道Bob, Kelly, Lucy, Li Lei & Han Meimei的數字?不斷的各種打聽,可誰也不會告訴你,告訴你那不就違反公司規定了哈哈哈…
如今乾的熱火朝天的區塊鏈,各家公司都想拿到別人家的數據來做分析、匹配、認證,你願意自己的數據被其他機構讀取嗎?不然,為什麼大家都那麼熱衷打通產業鏈或者多元化布局。滴滴又打車又外賣的——全方位掌管你的衣食住行,還不是為了方便的取走你的數據(其中一個目的)。
但確實有種演算法可以計算出你的同桌、同桌的同桌和同桌的同桌的同桌…的總分數,總工資或者其他各種各樣你感興趣的總和。
這種演算法就叫做安全多方計算
Secure Multiparty Computation
SMC由圖靈獎獲得者、中國科學院院士姚期智先生首次於1982年提出。Dr. Yao以著名的百萬富翁問題來說明安全多方計算——百萬富翁問題指的是,在沒有可信第三方的前提下,兩個百萬富翁如何不泄露自己的真實財產狀況來比較誰更有錢。
OK,讓我們來看一個具體的例子吧!
如果世界上只有5家櫻桃果農,他們每個人都想知道今年總共的櫻桃產量。為什麼他們想知道總產量呢?因為產量和定價息息相關啊。
每個人都很熱切的期待別人能把自己家果園的產量一個不小心說出來,可是誰是個傻子呢?每個人都不想告訴任何一個人,哪怕是宇宙最靠譜的MathIvy。
有沒有一種方法可以讓他們知道今年的櫻桃總產量呢?慶幸的是,5個果農都非常信任數學。
人啊,一旦有了信任,事情就好辦多了。
下面就給大家展示他們是怎樣計算出櫻桃總產量的。
假設每個果農及其相應櫻桃產量如下:
果農A:20t
果農B:25t
果農C:70t
果農D:60t
果農E:80t
以果農B的計算作為例子,展示如下:
Step1:將自己的產量填入下表
Step2:將產量除以5(因為共有5個果農),填入表格one fifth of value這一行
Step3:generate 4個隨機數,或者自己隨便填4個也可以,我比較懶,用randbetween公式生成了四個數字
Step4:將這四個隨機數字的總和填入sum#1through#4這一行
Step5:將這四個隨機數字的總和round up到100或100的整數倍,例如總和是8就round up to 100,總和是254就round up to 300
Step6:現在我們來計算calculated#5,這個數字等於one fifth of value + sum round up - sum,在這個例子中就是5+300-254=51,至此果農B這一列的數字就計算完成了
Step7:這一步需要交換數字,例如B需要把random#1這個數字給A,random#3這個數字給C,以此類推,即數字編號和字母編號是一一對應的,交換完成後A擁有了random#1這一行的所有數字,B擁有了random#2這一行所有的數字,如下:
Step 8:每個果農手上目前都有了5個數字,將這5個數字求和並對100求餘數,將結果填入倒數第二列
Step9:現在每個果農將這個餘數告訴其他人(例如B把56告訴ACDE),這樣就有了5個餘數,再將這5個餘數求和,最後用這個和對100求餘數,最後的這個餘數就是5個果農櫻桃產量的平均值。匯總表如下:
Step10:最後將這個平均數乘以5就是總產量啦!
是不是很有趣? Wanna have a try? Here is another group of numbers:
A:21 B:25 C:43 D:112 E:80
感興趣的童鞋可以搜索一下這個演算法的原理。不過要注意的是這個演算法的前提是大家要honest,在這個例子中,因為每個果農都迫切想知道總產量,所以假設大家都誠實是很合理的。
那麼,你覺得這個SMC演算法怎麼樣?你相信它能給出對的答案嗎或者能保護個人的隱私嗎?歡迎大家踴躍留言說出自己的評論!
******
數學建模思維Vol 2的課程是Privacy案例討論、分析與presentation,加入這個環節,不僅是訓練學生分析、識別和解釋在不同case中遇到的privacy issues,同時是想培養學生的團隊分工、個人領導力,research能力,presentation能力,勇敢表達自己觀點,以快速適應美國高中或大學的課堂節奏以及自由討論的課堂方式。
TAG:全球大搜羅 |