第10回セミナー・勉強会
日時: | 2021.05.24 Mon. 10:00-12:00
|
---|---|
会場: | オンライン |
話者: | 照山 順一(兵庫県立大学,B01班) |
題目: | 比較回数を抑えた整列アルゴリズム |
概要: | ソーティングは計算機における最も基本的な操作の一つである.既存のソーティングアルゴリズムの多くは,要素の大小比較を基本操作とする「比較ソート」であり,その計算効率を比較回数で計ることとする.最適な比較回数の研究は半世紀以上前から取り組まれているが,要素数16でも未だ未解決問題となっている.本講演では,少ない要素数に対する比較回数の研究結果を紹介する.また,一般の要素数に対して,漸近的に下限に近い比較回数を達成するアルゴリズムについても説明する.
|
2021.05.11 更新