皆様

東北大学の鈴木 悠大です 以下の通りセミナーを開催いたしますのでご案内いたします

https://sites.google.com/view/sendai-logic/

日時：8月4日(金) 16:00- 場所：東北大学理学研究科合同A棟801号室 (当日はzoom配信を実施予定です．zoomにて参加を希望される方は，鈴木([email protected] )までご連絡ください)

講演者：伊藤風輝(東京都立大学) タイトル：AND-OR木探索の乱択アルゴリズムとその均衡値

アブストラクト：AND-OR木は同じ変数が1度のみ現れるようなブール関数の計算モデルであり、その計算コストは変数のクエリー回数によって定義される。本講演では主に乱択アルゴリズムを興味の対象とする。乱択アルゴリズムによるコスト均衡値、すなわち最小化された最悪計算量は、ランダムでないアルゴリズムのみを用いる場合に比べて真に小さくなることがSaksとWigderson(1986)により示されている。Saksらの手法をベースとして、最適な乱択アルゴリズムの一意性や、乱択アルゴリズムを深さ優先(depth-first)・一方向性(directional)などの条件で制限した場合の均衡値の大小関係について解説する。本研究の一部は鈴木登志雄氏との共同研究である。

どうぞよろしくお願いいたします