完整後設資料紀錄
DC 欄位語言
dc.contributor.author廖敏如en_US
dc.contributor.authorMarina Min-ru, Liaoen_US
dc.contributor.author黃光明en_US
dc.contributor.authorFrank K. Hwangen_US
dc.date.accessioned2014-12-12T02:24:02Z-
dc.date.available2014-12-12T02:24:02Z-
dc.date.issued1999en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#NT880507021en_US
dc.identifier.urihttp://hdl.handle.net/11536/66172-
dc.description.abstract本篇論文分為二個部分:一為偽幣問題,另一為最優分割問題。 偽幣問題大都以有序演算法來討論:如何利用天秤,找出偽幣?假使共測試t次, 每次至多測k個硬幣的情形下,本篇論文第一部份利用無序演算法的測試方式,在某些 t和k值下,對可測試的最大硬幣個數,給出最優解。並提供了測試矩陣的建構方式。 在最優分割上有一個很重要的性質------超模性(Supermodular)。本篇論文第二部份 找到了不管是編號或不編號限制類型分割均不是超模函數的反例。zh_TW
dc.description.abstractThere are two main parts in this thesis, one is the counterfeit coin's problem, the other is the optimal partition problem. The first problem is to find the counterfeit coin using a scale through a nonadaptive algorithm. We give the optimal solution of the maximum number of tested coins in t given tests for some t and k. We also provide the construction of testing matrices. Supermodularity is one of the important properties in optimal partion. In the second part of the thesis, we give two counterexample to show that both labeled and unlabeled constrained-shape-partitions are not supermodular.en_US
dc.language.isozh_TWen_US
dc.subject偽幣zh_TW
dc.subject無序演算法zh_TW
dc.subject超模性zh_TW
dc.subjectcounterfeit coinen_US
dc.subjectnonadaptiveen_US
dc.subjectsupermodularen_US
dc.title兩個組合最優化的問題zh_TW
dc.titleTwo Problems in Combinatorial Optimizationen_US
dc.typeThesisen_US
dc.contributor.department應用數學系所zh_TW
顯示於類別:畢業論文