{"created":"2023-06-19T12:42:51.796121+00:00","id":2124,"links":{},"metadata":{"_buckets":{"deposit":"7bbf98bf-8f2c-4598-b2b7-65edfa7a8b6c"},"_deposit":{"created_by":3,"id":"2124","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"2124"},"status":"published"},"_oai":{"id":"oai:tokyo-metro-u.repo.nii.ac.jp:00002124","sets":["465:468:469:854:1019"]},"author_link":["5975","5973","5974"],"item_2_biblio_info_7":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2013-03-25","bibliographicIssueDateType":"Issued"},"bibliographicPageEnd":"50","bibliographicPageStart":"1","bibliographic_titles":[{}]}]},"item_2_creator_2":{"attribute_name":"著者(ヨミ)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"オガワ, コウスケ"}],"nameIdentifiers":[{"nameIdentifier":"5974","nameIdentifierScheme":"WEKO"}]}]},"item_2_creator_3":{"attribute_name":"著者別名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Ogawa, Kousuke"}],"nameIdentifiers":[{"nameIdentifier":"5975","nameIdentifierScheme":"WEKO"}]}]},"item_2_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"計算複雑さの理論の一分野として, AND-OR 木の研究がある.\n我々は, randomized complexity を達成する乱択アルゴリズムを最適乱択アルゴ\nリズムとよび, i-セット(i 2 f0; 1g) に対してコスト期待値が一定の乱択アルゴリズ\nムをEi-乱択アルゴリズムと定義する. 本論文では, 連結閉集合上の乱択アルゴリズ\nムについて, i-セットに対して最適であることとEi であることが同値であることを\n証明する. これは, 鈴木-中村[SuNa] の結果の双対的な結果とみなすことができる.\nまた, 真理値割り当てからなる集合にグラフの構造を入れ、木の高さに関する構造\n定理を示す.\n付録として, 無限組み合わせ論におけるdiamond principle に関連したhitting\nprinciple についての考察を加える. hitting principle をP   へ持ち上げ, P   に\nおけるdiamond principle との関連づけを与える.","subitem_description_type":"Abstract"}]},"item_2_description_5":{"attribute_name":"内容記述","attribute_value_mlt":[{"subitem_description":"首都大学東京, 2013-03-25, 修士（理学）","subitem_description_type":"Other"}]},"item_2_version_type_16":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"小川, 孝典"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2016-08-03"}],"displaytype":"detail","filename":"T00050-001.pdf","filesize":[{"value":"607.7 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"T00050-001.pdf","url":"https://tokyo-metro-u.repo.nii.ac.jp/record/2124/files/T00050-001.pdf"},"version_id":"4fdff6c9-4f9a-4a7d-8b6f-244687dd9b7d"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"thesis","resourceuri":"http://purl.org/coar/resource_type/c_46ec"}]},"item_title":"完全二分AND-OR 木に対する最適乱択アルゴリズムの特徴づけと木転置グラフの構造について","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"完全二分AND-OR 木に対する最適乱択アルゴリズムの特徴づけと木転置グラフの構造について"}]},"item_type_id":"2","owner":"3","path":["1019"],"pubdate":{"attribute_name":"公開日","attribute_value":"2013-08-06"},"publish_date":"2013-08-06","publish_status":"0","recid":"2124","relation_version_is_last":true,"title":["完全二分AND-OR 木に対する最適乱択アルゴリズムの特徴づけと木転置グラフの構造について"],"weko_creator_id":"3","weko_shared_id":3},"updated":"2023-06-19T17:35:16.252684+00:00"}