WEKO3
アイテム
完全二分AND-OR 木に対する最適乱択アルゴリズムの特徴づけと木転置グラフの構造について
http://hdl.handle.net/10748/5634
http://hdl.handle.net/10748/5634b75bedc3-4c80-4c5f-ae28-4381df50a3aa
名前 / ファイル | ライセンス | アクション |
---|---|---|
T00050-001.pdf (607.7 kB)
|
|
Item type | 学位論文 / Thesis or Dissertation(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2013-08-06 | |||||||
タイトル | ||||||||
タイトル | 完全二分AND-OR 木に対する最適乱択アルゴリズムの特徴づけと木転置グラフの構造について | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_46ec | |||||||
資源タイプ | thesis | |||||||
著者 |
小川, 孝典
× 小川, 孝典
|
|||||||
著者(ヨミ) |
オガワ, コウスケ
× オガワ, コウスケ |
|||||||
著者別名 |
Ogawa, Kousuke
× Ogawa, Kousuke |
|||||||
抄録 | ||||||||
内容記述タイプ | Abstract | |||||||
内容記述 | 計算複雑さの理論の一分野として, AND-OR 木の研究がある. 我々は, randomized complexity を達成する乱択アルゴリズムを最適乱択アルゴ リズムとよび, i-セット(i 2 f0; 1g) に対してコスト期待値が一定の乱択アルゴリズ ムをEi-乱択アルゴリズムと定義する. 本論文では, 連結閉集合上の乱択アルゴリズ ムについて, i-セットに対して最適であることとEi であることが同値であることを 証明する. これは, 鈴木-中村[SuNa] の結果の双対的な結果とみなすことができる. また, 真理値割り当てからなる集合にグラフの構造を入れ、木の高さに関する構造 定理を示す. 付録として, 無限組み合わせ論におけるdiamond principle に関連したhitting principle についての考察を加える. hitting principle をP へ持ち上げ, P に おけるdiamond principle との関連づけを与える. |
|||||||
内容記述 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 首都大学東京, 2013-03-25, 修士(理学) | |||||||
書誌情報 | p. 1-50, 発行日 2013-03-25 | |||||||
著者版フラグ | ||||||||
出版タイプ | VoR | |||||||
出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 |