平成１２年度１０月　最適化とアルゴリズム研究部会

• 日時：10月14日（土） 14:00 〜 17:30
• 場所：上智大学7号館12階第1215号室

• 発表１：浅野 哲夫氏 (北陸先端科学技術大学院大学 情報科学研究科)

  『ディジタルハーフトーニング：実用から理論的側面まで』

  近年，ディジタルカメラが普及するにつれプリンタの性能も飛躍 的に向上している．最近では写真と同じ品質の画像を出力できる装 置（ピクトログラフィー）もあるが，カラープリンタの性能も以前 に比べると格段に改善されている．しかしながら，この性能改善は ハードウェアの進歩によるところが多いのも事実である．ソフト的 にも様々な方法が提案されているが，画期的なものは見当たらない． 日本人は従来から現状の技術を改善することには長けているが，革 新的な技術の開発は不得手だと言われて来た．カラー画像を限られ た色数のインクを使って美しく再生するための技術であるハーフト ーニングについても同様で，実験に基づいたチューニングに代表さ れる小さな改良については様々なアイディアが出されているが，基 本的には一昔前に提案されたアルゴリズムの枠組みから抜け出てい ないのが現状である．この現状を打破するために，従来から数学的 定式化に基づいてこの問題の本質的な難しさを議論することから始 め，アルゴリズムの分野で開発されてきた様々な技術がこの問題に うまく適用できることが最近になって分かってきた．幾何情報の効 率的な処理方法の開発を主とする計算幾何学の成果はもとより，一 見関係がないと思われる概念が関連しているのである．本講演では， 画像処理的技術以外にどのような計算問題が関係しているかを具体 的に説明する．

• 発表２： 渡辺 治 氏 (東京工業大学 数理・計算科学専攻)

  『組合せ問題のテスト例題生成技法について』

  組合せ問題（組合せ最適化問題）に対する各種のプログラムの 効率などを評価する１つの方法は，様々なテストデータの上で 実験してみることである．そのために有効なテスト例題生成技 法について，SAT, MAXSAT を例に解説する．（共同研究者：元 木，上原，内田，堀江）