学術情報メディアセンターセミナー「アルゴリズム理論の最先端」

16時30分～17時30分

講演者

Francois Le Gall（京都大学情報学研究科 特定准教授）
※ 使用言語： 英語（同時通訳なし）

講演題目

Overview of the recent progress on matrix multiplication algorithms（行列積アルゴリズムに対する最近の進展）

講演概要

数年前まで、行列積に対する最速のアルゴリズムは、1987年に提案された"Coppersmith-Winograd algorithm"でした。近年、Andrew Stothers, Virginia Vassilevska-Williamsおよび本講演者による一連の研究の結果、計算時間の改良に成功しました。本講演では、行列積に対する計算量研究の歴史と、上述した近年の改良技法について解説します。

17時30分～18時30分

講演者

照山 順一（国立情報学研究所 特任研究員）

講演題目

比較回数を抑えたソーティングアルゴリズム

講演概要

ソーティングは計算機における最も基本的な操作の一つです。既存のソーティングアルゴリズムの多くは、要素の大小比較を基本操作とする「比較ソート」であり、その計算効率を比較回数で計ることとします。最適な比較回数の研究は半世紀以上前から取り組まれていますが、要素数16でも未解決問題となっています。本講演では、少ない要素数に対する比較回数の研究結果を紹介します。また、漸近的に下限に近い比較回数を達成するアルゴリズムについても説明します。