deterministic VS non-deterministic algorithm

[***以下為個人理解，如有錯誤歡迎指證***]
[***This article may contain mistakes and thus any correction is greatly appreciated***]

今天在複習 apriori algorithm 時，由於書上說 association rule mining 的結果是唯一性的，讓我想到個問題：這個演算法是 deterministic 還是 non-deterministic ?
唯一性的直覺是 deterministic，只是當下無法說出 deterministic、non-deterministic、NP的定義，所以趕緊來複習一下。(慚愧...)

[non- deterministic]
(1) an algorithm exhibits different behaviors in different runs.
(2) WIKI 的例子：若用從 1 input 到 1 outcome 的 1 1path 表示 deterministic algo.，則 non-deterministic algo. 表示 1 input 到 N outcomes 的 M paths 的其中一條.
(3) 在 computational theory 中，我們所講的 algorithms 大多都是屬於 deterministic algo.。
(4) 似乎一些研究都是透過 deterministic algo 加上一些手法 ex. approximation、probabilistic random 來解決現實中 non-deterministic 的問題。

[NP] non-deterministic and polynomial
*記得P = NP 問題已經在前一年被 Stamford 的學生證明了。


[參考]
1. wiki

Comments

Post a Comment

Popular posts from this blog

股票評價(Stock Valuation) - 股利折現模型

Image
這邊討論的是股價(普通股)的評價，包括股利折現模型、成長機會模型與本益比模型。 1. 股利折現模型( The Dividend Discount Model, DDM ) 股票的現金流可以分為兩個部分：股利的收入及股價的變動 先來定義 Pt：第t期的每股股價 Dt：第t期的每股股利 Rs：股利折現率(或稱為股東的必要報酬率) 當下的股票現值P0 =  D1/(1+Rs)  + P1/(1+Rs) ... (1) 一年後的股票現值 P1 = D2/(1+Rs) + P2/(1+Rs) ... (2) 將(1)代入(2)可得  P0 = D1/(1+Rs) + D2/[(1+Rs) ^2] + P2/[(1+Rs)^2] 可推得 P0 = D1/(1+Rs) + D2/[(1+Rs) ^2] + D3/[(1+Rs)^3] + ... =   SIGMA(t=1, infinite)  D1/[(1+Rs)^t] 常見的股利折現模型有三種， a. 零成長型(Zero Growth) , 即D1=D2=D3=...    利用等比級數公式, a0=D1/(1+Rs), r= 1/(1+Rs)  =>  p0 = D1/Rs      [*這跟永續年金的結果相同] b. 固定成長(Constant Growth) , 即股利按固定比率ｇ成長, D2=D1*(1+g), ...    => P0 = D1/(Rs-g)    b.1這個模型又稱為戈登模型(Gordon Model)或股利成長模型(dividend growth model)         因為這個模型提供我們很好的直覺：         b.1.1 當公司宣布年底股利增加, D1上升, P0上升 b.1.2 當公司盈餘成長, g上升, P0上升         b.1.3 當資本或風險提升，Rs上升, P0下降    b.2固定成長型的資本利得率＝股利成長率, g = (P0-P1)/P0 c. 超成長型(Supernormal or Nonconstant Growth) , 即一開始公司有高成長率，幾年後才回到一般成長。 EX. yahoo公司預期未來四年有高度成長25%, 之後皆以8%穩定成長, 其折現率20%. 今發行4塊股利： 這邊P0需分為兩個部分, 一為超成長部分及穩定成長部分.
Read more

openwrt feed的使用

最近又回去看Openwrt發現feed, 來記錄一下. feed 是一個挺有趣的東西, 在Openwrt 理面它是一堆 packages 的集合,  我想應該是因為不同的 packages 可能來自不同的地方, 透過 feed 提供介面管理這些 packages. (1) where is feeds     放在 scripts/feeds (2) feeds command     update:        撿查 feeds.conf  # or feeds.conf.default       將各自的feeds下載後放到 feeds/        建立 XXX.index      list:       透過 XXX.index, 列出 feeds/ 的feeds     install:       建立symbolic link. # from feeds/XXX  to packages/feeds/XXX (3)自己建立 feeds       1. svn co svn://svn.openwrt.org/openwrt/trunk/[BRANCH]  [OPENWRT]       2. svn co svn://svn.openwrt.org/openwrt/package  [OPENWRT]/packages       3. 撰寫自己的 feeds.conf       4. >script/feeds update -a       5. >script/feeds install       6. make menuconfig        參考Openwrt 連結         
Read more

How to convert Markdown into HTML

Nice solution to convert MarkDown to html!!! Steps as follows: 1. open link StackEdit 2. draft what you intend to memo 3. menu -> import/export -> export as HTML (choose Plain HTML ) Welcome to StackEdit! Hi! I’m your first Markdown file in StackEdit . If you want to learn about StackEdit, you can read me. If you want to play with Markdown, you can edit me. Once you have finished with me, you can create new files by opening the file explorer on the left corner of the navigation bar. Files StackEdit stores your files in your browser, which means all your files are automatically saved locally and are accessible offline! Create files and folders The file explorer is accessible using the button in left corner of the navigation bar. You can create a new file by clicking the New file button in the file explorer. You can also create folders by clicking the New folder button. Switch to another file All your files and folders are presented as a tree in the file explorer. You
Read more