分類: 技術

排列組合小註解

終於咱家女兒上到了排列組合, 這個令很多人一頭霧水的數學單元. 它大概有幾種情況.

1. N 個不同的東西依序排列, 其順序有意義的話, 第一個位置有 N 個可能, 第二個位置剩下 N -1 種可能, 依此類推, 共有 N! 種排列方式.

2. 如果有 N 種東西, 只能搶 K 個位置, 當然第一個位置仍然有 N 種可能, 第二個位置剩下 N -1 種可能, 第 K 個位置剩下 N – K + 1 個可能. 也就是 Pnk = N! / (N-K)!.

3. 如果 K 個位置中, N 個東西可以重複出現, 那麼排列就有 Nm 種, 稱為重複排列.

來個應用題, 7 個人搭 3 輛車, 可以有幾種排列方式? P73? 37, 73?

如果是 P73, 其實表示最後只有 3 個人上得了車, 每車一個人. 就像是玩大風吹那樣.

如果是 73, 表示每輛車可以從 7 個人中選一個人來上車 (我們就假設車子有意志好了), 第一輛車選上了甲, 而在重複排列的條件下, 第二輛車還是可以選甲. 以至於受歡迎的甲會被兩三輛車子載走 (how? 聽起來不合邏輯), 而其他人可能只得乾瞪眼.

因此可以放在假數 (mantissa ) 位置的, 必須是容器, 可以重複出現的. 放在指數 (exponent) 位置的, 必須是獨立不可切割的, 或是獨立事件.

4. 更進一步是, 若排列物的本身就無法分辨其差異, 例如紅球, 白球, 鉛筆之類的東西. 排列出來也要再打個折扣. 也就是要除以不能分辨的子集合的排列數. 三支鉛筆和五個橡皮擦的排列. 將會得到:

(3+5)! / 3!5!

5. 組合的概念和排列不同, 排列強調有序, 組合只考慮一堆一堆的. 這裡會出現大家熟悉的 Cnk. 也就是從 n 個東西裡面拿出 k 個的組合方式. 既然已經變成無差別的一堆了, 就等於 Pnk /K! = N! / (N-K)!K! = Cnk.

由於這個式子和情況 4 的狀態很像, 我們可以想像成把 n 個東西分成兩堆, 第一堆表示選上了, 第二堆表示沒選上. 選上的那堆無差別, 像是紅球或是鉛筆, 另一推落選的也無差別, 像是白球或是橡皮擦.

6. 再來就是重複組合, 重複組合的公式很簡單, 但是觀念比較難. 網路上的這個例題不錯.

候選人４名，選舉人 18 名，且無廢票，下列各種情形之下結果有幾種？解答

  1. 記名投票之情形。

  2. 不記名投票之情形。

第一小題的答案當然是 418.

第二小題的部分, 此時可以把投票結果想像成票有 4 堆, 堆與堆之間用空格來分別那是誰的票.

由於每一堆代表一位候選人的票, 這個排列是有序的. 而選票本身未記名, 所以它是無差別的. 只要插入一些空格, 它完全符合情況 4 的描述.

因此本小題相當於 18 張票和 3 個空格在排列. 我們套用情況 4 的概念, 組合數是 C 4+18-1 3 或 C 4+18-1 18種. 

DASH 小註解

DASH 這邊是指 MPEG DASH (Dynamic Adaptive Streaming over HTTP), 也就是用 HTTP 傳輸動態碼流的意思. 聽到這個名詞不得不令人想到 Apple 的 HLS (HTTP Live Streaming), 沒錯！這兩個規格是互相競爭的. 類似的規格還有 Microsoft Smooth Streaming 和 Adobe Dynamic Streaming. 據說這類的規格 80% 長得一樣, 但 100% 不相容.

為什麼會有這種規格上的需求呢？因為在網路上傳輸影片是一個不可逆的趨勢 – 例如 VOD (video on demand) 或 streaming, 而網路環境中又很難握實際的頻寬, 所以動態傳輸當然有必要. 接著講到 HTTP, 為啥用 HTTP 呢？因為防火牆一般不會擋它. 公司要是擋了 HTTP 就不能 Google 啦！所以 HTTP 影片可以順勢穿透防火牆, 也可以善用各種 proxy 或是 cache 的設備. 兩個因素加起來, 就導致了 HTTP streaming  的興起.

為了適應不同螢幕解析度和頻寬, 在 server 當然得準被各種規格影片. 此外, 所謂的動態當然需要靠偵測結果作為依據, 每個規範的著眼點也不一樣, 大致上是用 client 的 CPU loading 或是頻寬.

Server 動態偵測 切割方式 Container CODEC
Adobe RTMP Streaming Server 假設靜態 AMF, SWF, FLV and F4V Adobe assigned
Adobe’s HTTP-based Dynamic Streaming (HDS) HTTP CPU utilization time-code MP4 V: H.264 or VP6

A: AAC or MP3
Microsoft’s

Smooth Streaming

 HTTP or RTSP CPU utilization time-code MP4 V: H.264 or VC1

A: AAC or WMA
Apple’s

HTTP Live Streaming (HLS)

 HTTP buffer status segment M2TS
MPEG DASH HTTP CPU or buffer MPD M2TS or MP4 open
RealNetworks’ RTSP Real Data Transport (RDT) ? ? RM or RMVB RealNetwork assigned
DiVX Plus Streaming (DPS) HTTP delay? HTML5+

segment

 MKV V: H.264
A: AAC, AC3, DTS, DTS Express

DASH 看似比大公司推出的規範更有公信力, 但是也受到某些苛責. 例如 DASH 並沒有指定 video CODEC, 所以號稱支援 DASH 的 browser 也就得多才多藝, 什麼格式都得解. 製作 DASH content 的人,  也要考慮接收端是否什麼都能解？而得把各式菜色都煮好才能端出來. 不過往好處想, DASH 開放了 CODEC 和 DRM (digital rights management) 的 support.

上表中 MPEG DASH 的 MPD (Media Presentation Description) 代表一個用 XML 管理的方式. 它把各個時間片段, 各種頻寬需求的影片 URL 一次給足. 因此 client 永遠知道下一個 byte 要去哪個 URL 撈. 抓一個圖解釋如下.

IAD 小註解

LTE IAD 這個名詞剛剛才接觸到, 網路上相關訊息也很少. LTE (Long Term Evolution) 大家都知道吧, 就是 4G 通訊中打敗 WiMax 的規格. 至於 IAD 呢？基本上 Google 查不太到. 

由於 IAD 常常和 router 這個字同時出現, 所以依據網路通信的習慣, 我們可以猜出 A 代表 Access, D 代表 Device. 果不其然, IAD 就是 Integrated Access Device.

IAD 也是  router 的一種, 它不但是網路設備 (data communication) , 也可以用來打電話 (telecommmunication), 送簡訊. 這就解釋了 integrated 這個字的含意. 舉 D-link 的產品為例, 只要插上 4G SIM 卡, 就可以提供無限網路 （包括支援 WIFI phone）與 USB 周邊 (如印表機). 這樣的東西看起來滿好用的.

BML 小註解

什麼是 BML 呢？它和體檢時令人尷尬的 BMI 沒有關係, BML 全名是 Broadcast Markup Language (廣播標記語言). 它在 1999 年由日本提出來, 記載在 ARIB STD B24 標準之中. 如同它的名字顯示的, 這是 XML 的一種, 又用在數位電視廣播.

網路上相關的訊息很少, 最好的一個 link 可能是這個：New Generation TV platform API and Privacy Protection

試想, 如果電視台送過來的訊息是一個 XML file, 那麼傳輸效率還挺高的, 只要接收端的 browser 夠強, 就可以達到節省頻寬的目的.

至於在歐洲推動了很多年的 MHP (Multimedia Home Platform) 架構, 則是在接收端建好 Java 的虛擬機, 等著 run 傳過來 Java 程式 (例如用 DSM-CC), 相形之下效率就低了些. 

最近在歐洲比較紅的 HbbTV 基本上也是以 CE-HTML 做互動.未來更將改用 HTML5  取代 CE-HTML. 在那一天還沒有來臨之前, 我們先關心一下歷經市場十多年考驗的 BML 吧,它的 API 多達 229 個! 有些功能連 HTML5 都還沒有.

BML Broadcasting Extension API 包括：

• EPG API

• VOD/Broadcasting base on Home Server API

• Storage API

• Interactive/Presentation API

• Other TV set Control API

比方說, BML 還支援把節目的畫面用印表機印出來, 這樣夠炫了吧！更別說什麼連續劇預約錄影, 硬碟儲存權限保護等等了. 因此, 在上面提到的那篇文章中, 作者認為 BML + HTML5 會是最佳互動電視的解決方案.

不過, 個人以為 BML 幾乎只有日本人在用, 而 HTML5 可以無限改版擴充, 總有一天 HTML X 樣樣都會比 BML 強!

在 Word 製作文件目錄

最近在寫文件的時候, 剛好需要製作三種目錄, 包括 TOC (table of cotents), 圖形與表格的目錄 (table of figures). 雖然套用別人的樣板就沒有問題, 但是其實自己不會做這個東西. 上網查了一下, 大多數都是英文的網頁, 而且沒有 Office for Mac 的版本, 其實搞不懂關鍵何在?

雖然我也看到 Word 給我的提示, 不過那只適用於 Table of Contents, 對 Table of Figures 只能算是誤導吧？

List of Tables

No table of figures entries found.
In your document, select the words to include in the table of contents, and then on the Home tab, under Styles, click a heading style. Repeat for each heading that you want to include, and then insert the table of contents in your document. To manually create a table of contents, on the Document Elements tab, under Table of Contents, point to a style and then click the down arrow button. Click one of the styles under Manual Table of Contents, and then type the entries manually.

如果要製作 table of content, 首先要決定標題的形式, 也就是 style. 比方說最大的標題 (Heading 1) 要選 1, 次大的標題 (Heading 2) 要選 1.1, 再下一級標題 (Heading 3) 要是 1.1.1…之類的. 這邊用 mouse 的右鍵可以選到這個 style 適用的字體或是字型大小, 還可以把整份文件的同一個 style 都改成一致的格式.

最後, 在需要插入 TOC (table of contents) 的地方, 從 word 的工具列選擇 insert, 然後再選擇 index and table (索引及表格) , 就可以自動把 TOC 建出來, 而且還可以在這裡選擇表現方式, 有沒有顏色? 要不要排縮等等.

至於製作 figure 和 table 的 table, 那就需要事先告知 Word. 首先對於每個圖形或是表格, 不是光把字打上去就算了. 像是 Figure 1. System Overview 這樣是不行的, 難以寄望 word 自己就能把表給建出來. 每個說明文字要先插入一個標題 (caption). 去工具列選 insert → caption, 就可以接著選擇這是公式, 圖形或是表格. 至於標題的 style 是啥都不要緊.

同樣在需要插入 table of figure 的地方, 再去選一次 insert → index and table, 選擇 table of figure, 再從中選擇是建立 equation, figure, 還是 table 的 index 就可以了.