場所：九州大学理学部３号館３３１１室

  Sturmfels-Weismantel-Ziegler (*1)は、整数計画問題を解く Conti-Traberso 
(*2)
  アルゴリズムを整数格子上の問題に拡張した。CT アルゴリズムの特徴は、
  整数格子から自然に生成される 2 項式イデアルのグレブナ基底を用いることである。 

  彼らのアルゴリズムにより、拡張された整数計画問題と2 項式イデアルの
  性質の間に興味深い関係(最適解とグレブナ基底による正規形計算)が見出せる。
  本発表では、彼らの結果をできるだけ平易に紹介するとともに、符号理論への
  応用(*3)を紹介する。符号理論の主な問題の一つに、軟判定最尤復号問題と
  呼ばれる問題がある。この問題はそのままでは、CT アルゴリズムが適用できない
  のだが、ちょっとしたトリックを使うことにより適用ができ、その結果、
  符号理論と 2 項式イデアルの間にも同様の関係が現れることがわかる。
  keywords: integer programming, soft decision decoding, Groebner basis,
            binomial ideal, integral lattice

  (*1) : B. Sturmfels, R. Weismantel and G. Ziegler,
   "Groebner bases of lattices, corner polyhedra and integer programming",
   Beitr age zur Geometrie und Algebra, No.36, pp. 281 -- 298.
  (*2) : P. Conti and C. Traverso,
   "Buchberger algorithm and integer programming",
   AAECC-9, vol. 539 LNCS, pp. 130--139, Springer, 1991.
  (*3) : 池上 大介,
   "An algebraic maximum likelihood decoding algorithm and a sub-optimum
    decoding algorithm for linear codes", 博士論文, NAIST, 2003.

  (+α) おまけの発表 「Agda + Computer Algebra system」
  対話型定理証明/プログラム記述システム Agda と、Agda を計算代数システムに接続する
  プラグイン機構を紹介する。
  Agda は、定理証明のためのシステムという一面と、対話型プログラム記述の
  ためのシステムという一面を持つ。この発表では、定理証明システムとしての
  機能に注目する。Agda では、ユーザが命題とその証明を記述することができ、
  その証明が数学的な意味で妥当かどうか (矛盾していないか、使ってよい仮定と公理 

  のみから正しく推論しているかなど)を計算機が検証する。しかし、この検査は計算時間と
  メモリの両方を大量に必要とするという欠点がある。もし、計算を確かめる部分を
  外部の計算代数システムに頼むことができれば、この欠点を軽減することが期待できる。