こちらに共通ヘッダが追加されます。

離散数理研究室

教員

  • 渡邊 芳英 (教授) Yoshihide WATANABE
    Researcher Database

    研究分野: 計算機代数と組合せ論 研究室: YE-218
    TEL: 0774-65-6298 FAX:
    E-mail: yowatana

研究内容

 

研究テーマ

(1) グレブナー基底を用いた2元符号の最尤復号

グレブナー基底を用いて、2元最尤復号を行う池上-楫アルゴリズムはグレブナー基底の計算時間あまりに大きく、実用的ではない。そこで本研究では、最尤復号に必要となるイデアルのグレブナー基底を符号の組み合わせ論的な性質から導けないかと考える。それにより、符号の数学的構造と最尤復号のメカニズムに対して新たな視点を与えることができるかもしれない。

 

(2) グレブナー基底とネットワーク最適化問題

ネットワーク最適化問題は多くの場合整数計画問題として定式化できる。従って、そこからトーリックイデアルを定義することができる。このようなトーリックイデアルの生成元またはグレブナー基底とネットワークの構造との関連を調べる。

 

(3) 生命情報学における様々な組み合わせ最適化問題

生命情報学においては、最適化問題の立場からみても興味深い様々な組み合わせ最適化問題が現れる。このような問題を整数計画問題として定式化し、その数学的な構造を調べる。

 

 

研究の概要

最適化とは、与えられた制約条件のもとで、ある目的関数を最大化または最小化することであり、応用数理の代表的な研究テーマである。最適化問題には、扱う変数が連続的な値をとる連続の最適化問題と、変数が離散的な変数をとる離散最適化問題がある。当研究室では、主として離散最適化問題、とくに整数計画問題をその数学的な構造と観点から研究する。キーワードはトーリックイデアルまたは格子イデアルであり、用いる道具は多項式環のイデアルのグレブナー基底である。現在興味をもって研究している具体的な離散最適化問題はグラフ上のネットワーク最適化問題、誤り訂正符号における最尤復号の問題、生命情報学における様々な組み合わせ最適化問題などである。