block design:
簡單的說，就是把 subset 當作是 block，給定一些取 subset 的規則。
然後研究他們的性質。
以 t-design 來說，就是指對 a set X, |X|=v, 取大小為 k 的 subsets,
(i.e., blocks) 這些 subsets 的集合為稱為 B。
當然，很直覺的，我們有 (v 取 k) 種取法。
不過如果我們要求所取的 B 必須滿足對任意大小為 t 的 subset of X, 必
同時存在於 \lambda 個 blocks 之中。就不是那麼好取的了。
對於蠻足這樣的條件的"集合系統" (set system)
我們以其參數稱之為 t-(v,k,\lambda) design. 而目前我們所知最多的應
該就是 2-(v,k,\lambda)design.
其形式化的定義如下：
1. 共有 v 個元素
2. 每一個 block 恰包含 k 個不同的元素
3. 任兩個元素 {x,y} \in X 必恰好落在 \lambda 個 blocks 裡。
基本上，所謂的 Block Design (or combinatorical design, design theory)
大致上類似的概念推廣。我個人覺得可以說是，研究在不需要定義任何其他的
性質的情況下， set system 本身能擁有的特性(rigid properties)。
我所謂的"其他的性質", 譬如代數就需要定義 operation, lattice 就要定義
relation 之類的。
目前的研究，其實已經能推廣到很多其他的數學結構，譬如 Latin square,
Hadamand matrix, orthogonal array, 等等。而隨著 axioms 的強弱變化，
也可以定義出很多不同的 block design.....
至於 combinatorics of finite geometries 是書名。內容主要是談將幾何的
公理應用到有限的 set system 之上的推廣。
Combinatorics of Finite Geometries (Paperback)
by Lynn Margaret Batten
# Paperback: 207 pages
# Publisher: Cambridge University Press; 2 edition (May 28, 1997)
# Language: English
# ISBN: 0521599938
譬如，如果我們只有有限個點，例如 GF(q)^n for prime pwoer q, 他的幾何
空間該如何定義？ 不過這樣說感覺很高深。或許是因為 block design 是由
統計方面的人開始研究，所以如果沒有一定的複雜度就沒有應用的價值吧。
這也是我推薦 combinatorics of finite geometries 的原因，這本書的主題
比較集中，也比較有一致性，不像 block design 的書，可能會在大量的各種
design 之間暈了頭.....。
不過其實我也只是大概翻看了一下這本書，我是覺得這本書寫得比較有數學趣
味，但是實用性可能相對低得多了。不過話說回來， block design 在 CS 方
面的應用，還是以通訊最多，主要是用在編碼或者是測試這種需要設計出帶某
種強固性的結構的領域。
有興趣的人可以參考這篇 survey
Applications of combinatorial designs in computer science
http://doi.acm.org/10.1145/66443.66446
(這篇文章在 ACM DL 上，需要權限才可閱讀，如果有興趣 m 兄私下給我 mail吧。)
Applications of Combinatorial Designs to Communications, Cryptography,
and Networking, C.J. Colbourn, J.H. Dinitz, D.R. Stinson
Surveys in Combinatorics, 1993, Walker (Ed.), London Mathematical Society
Lecture Note Series 187, Cambridge University Press
http://citeseer.ist.psu.edu/colbourn99applications.html
至於 Design theory 與圖論和編碼理論的關聯，可以參考下面這本書。
Designs, Graphs, Codes and their Links
Series: London Mathematical Society Student Texts (No. 22)
by P. J. Cameron, J. H. van Lint
http://tinyurl.com/a8gp8
--
1. 這些是我之前查資料查來的，其實我很混修得很爛，目前在祈禱不要被當中...XD
我這麼熱心提供資料，希望老師可以放我一馬....orz
2. 數學家寫的書最喜歡自稱 concise, self-contain, 和 without xxxx background.
每次看到 preface 出現這些字眼，我想到政治芭樂票....orz
Tag: [Math]
沒有留言:
張貼留言