フラジョレ講演賞

フィリップ・フラジョレ講演賞は、理論計算機科学の分野における解析的組合せ論とアルゴリズムの分析への貢献に対して授与されます。この賞はフィリップ・フラジョレを記念して名付けられました。

歴史

フラジョレ講演賞は2014年から授与されている。フラジョレ講演賞は奇数年に授与され、受賞者は受賞後、翌年にフラジョレ講演を行う。この講演は、アルゴリズム解析のための確率的、組合せ的、漸近的手法に関する国際会議（AofA）^[1]の基調講演として企画されている。AofA は、1993年にフラジョレらが始めた一連のセミナーから始まった国際会議である。選考委員会は、この分野から3名で構成される。

科学的なトピック

フラジョレ講演賞の受賞者は、アルゴリズムの分析、解析的組合せ論、組合せ論、通信プロトコル、複雑な解析、計算生物学、データマイニング、データベース、グラフ、情報理論、極限分布、マップ、ツリー、確率、統計物理学など、さまざまな分野で活躍しています。

就任講演で、ドン・クヌースは「フィリップが喜んだであろう問題」5つについて論じた。^{[2]クヌースは、}ポリオミノの列挙、数学的タイリング、木の剪定、格子経路、摂動法の5つの問題を概観した。特に、彼はポリオミノの漸近列挙について論じた（背景と歴史についてはOEISエントリA001168 ^{[3]を参照）。クヌースの森林の剪定に関する議論は、ピーター・ルシュニーに}ディック経路との関連を指摘させた（OEISエントリA091866 ^[4]を参照）。傾き2/5の格子経路に関する講演の部分では、中見川と徳重の定理に焦点が当てられた。^[5]^[6]クヌースは、関連する格子経路の列挙についての予想を立て、これは後にシリル・バンデリアとマイケル・ウォールナーによって解決された。^[7]^[8]^{[9]クヌースの格子経路に関する議論は、2つの新しいOEISエントリ、A322632}^[10]とA322633の作成にもつながった。^[11]

2016 年のロバートセジウィックの講演では、フラジョレの初期の論文の 1 つにまで遡るトピック、ストリーミングデータの近似カウント法に焦点が当てられました。講演では、「実用的なコンピューティング」と理論計算機科学とのつながりが描かれました。これらのつながりの重要な例として、セジウィックは、フラジョレがキャリアを通じて近似カウントのトピックを繰り返し取り上げ、確率的カウントのフラジョレマーティンアルゴリズム^{[12]から始めて、Loglog カウント}^[13]とHyperLogLogカウント^[14]の手法の導入を主導したことを強調しました。セジウィックの講演では、基礎理論だけでなく、近似カウントの実験的検証と、クラウドコンピューティングにおけるその最新のアプリケーションも強調されました。また、小規模で頻繁な計算を伴うアプリケーションに適した HyperBitBit と呼ばれるアルゴリズムも紹介されました。

受信者

参照

コンピュータサイエンスの賞一覧

注記

^ シュパンコフスキーの講演は当初2020年のAofAカンファレンスで予定されていたが、COVID-19パンデミックの影響で2022年に延期された。

参考文献

^ ab 「アルゴリズムの分析」。 2021年3月20日閲覧。
^ ドナルド・クヌース著「フィリップが愛したであろう問題」（PDF）。スタンフォード大学。 2022年3月23日閲覧。
^ NJA Sloane. 「n個のセルを持つ固定ポリオミノの数」。オンライン整数列百科事典。 2022年3月23日閲覧。
^ Emeric Deutsch. 「ピラミッドの重みがkである半長さnのDyckパスの数」。オンライン整数列百科事典。 2022年3月23日閲覧。
^ 中上川、智樹;徳重憲英（2012）「新しいサイクル補題を介した格子パスの計算」。離散数学に関する SIAM ジャーナル。26 (2)。工業および応用数学協会: 745–754。CiteSeerX 10.1.1.220.6893。土井：10.1137/100796431 。2022 年3 月 23 日に取得。
^ Hugo Pfoertner. 「a(n) = 2*binomial(7*n-1,2*n)/(7*n-1)」。オンライン整数列百科事典。 2022年3月23日閲覧。
^ Banderier, Cyril; Wallner, Michael (2015). 「傾き 2/5 の格子パス」2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) . pp. 105–113. arXiv : 1605.02967 . doi :10.1137/1.9781611973761.10. ISBN 978-1-61197-376-1. S2CID 15496496。
^ Banderier, Cyril; Wallner, Michael (2015). 「Lattice paths of slope 2/5」. Society for Industrial and Applied Mathematics, Meeting on Analytic Algorithmics and Combinatorics . 2022年3月23日閲覧。
^ Banderier, Cyril; Wallner, Michael (2019). 「有理勾配線以下の格子パスに対するカーネル法」。Andrews, George; Krattenthaler, Christian; Krinik, Alan (編)。格子パスの組合せ論と応用。数学の発展。第58巻。Springer。pp. 119–154。doi : 10.1007 /978-3-030-11102-1。ISBN 978-3-030-11101-4. S2CID 197480284 . 2022年3月23日閲覧。
^ Hugo Pfoertner. 「23*x^5 - 41*x^4 + 10*x^3 - 6*x^2 - x - 1 = 0 の実数解の10進展開」。オンライン整数列百科事典。 2022年3月23日閲覧。
^ Hugo Pfoertner. 「11571875*x^5 - 5363750*x^4 + 628250*x^3 - 97580*x^2 + 5180*x - 142 = 0 の実数解の 10 進展開に 3/7 を掛けたもの」。オンライン整数列百科事典。2022年3 月 23 日閲覧。
^ Flajolet, Philippe; Nigel Martin, G. (1985). 「データベースアプリケーションのための確率的カウントアルゴリズム」(PDF) . Journal of Computer and System Sciences . 31 (2): 182–209. doi : 10.1016/0022-0000(85)90041-8 .
^ デュランド、マリアンヌ、フラジョレ、フィリップ (2003)。「大きな基数のログログカウント」(PDF)。アルゴリズム - ESA 2003。コンピュータサイエンスの講義ノート。第 2832 巻。p. 605。doi : 10.1007 /978-3-540-39658-1_55。ISBN 978-3-540-20064-2. 2022年3月23日閲覧。
^ Flajolet, Philippe; Fusy, Éric; Gandouet, Olivier; Meunier, Frédéric (2007). 「Hyperloglog: 近似最適カーディナリティ推定アルゴリズムの分析」.離散数学および理論計算機科学論文集. AH .ナンシー、フランス: 137–156 . 2022年3月23日閲覧。
^ “AofA 2014” . 2021 年3 月 20 日に取得。
^ 「フランスのINRIAにあるHAL学際的オープンアクセスアーカイブからのAofA 2014の会議議事録のフロントページ」。 2021年3月20日閲覧。
^ 「フランスのINRIAにあるHAL学際的オープンアクセスアーカイブからのAofA 2014の完全な科学会議議事録」。 2021年3月20日閲覧。
^ 「ドン・クヌースの2014年の公開講義」。2022年3月23日閲覧。
^ Bob Sedgewick (2020年10月16日). 「Cardinality Estimation」.
^ “AofA 2016” . 2021 年3 月 20 日に取得。
^ 「クラクフのヤギェウォ大学によるAofA 2016の完全な科学会議議事録」（PDF）。 2021年3月20日閲覧。
^ Luc Devroye. 「編集された議事録の記事」.
^ “AofA 2018”. 2019年8月22日時点のオリジナルよりアーカイブ。2021年3月20日閲覧。
^ 「Dagstuhl Research Online Publication Server の AofA 2018 の完全な科学会議議事録」(PDF) 。2021 年3 月 20 日閲覧。
^ 「AofA 2018から選ばれた論文を掲載したAlgorithmicaジャーナルの特別号」。 2021年3月20日閲覧。
^ 「Szpankowski がフラジョレ賞を受賞」。2020年2月11日。 2021年3月20日閲覧。
^ “AofA2024” . 2023年6月29日閲覧。

外部リンク

アルゴリズムの分析国際コミュニティウェブサイト

[26] シュパンコフスキーの講演は当初2020年のAofAカンファレンスで予定されていたが、COVID-19パンデミックの影響で2022年に延期された。

[aofasite-1] 「アルゴリズムの分析」。 2021年3月20日閲覧。

[lecture2014-2] ドナルド・クヌース著「フィリップが愛したであろう問題」（PDF）。スタンフォード大学。 2022年3月23日閲覧。

[3] NJA Sloane. 「n個のセルを持つ固定ポリオミノの数」。オンライン整数列百科事典。 2022年3月23日閲覧。

[4] Emeric Deutsch. 「ピラミッドの重みがkである半長さnのDyckパスの数」。オンライン整数列百科事典。 2022年3月23日閲覧。

[5] 中上川、智樹;徳重憲英（2012）「新しいサイクル補題を介した格子パスの計算」。離散数学に関する SIAM ジャーナル。26 (2)。工業および応用数学協会: 745–754。CiteSeerX 10.1.1.220.6893。土井：10.1137/100796431 。2022 年3 月 23 日に取得。

[6] Hugo Pfoertner. 「a(n) = 2*binomial(7*n-1,2*n)/(7*n-1)」。オンライン整数列百科事典。 2022年3月23日閲覧。

[7] Banderier, Cyril; Wallner, Michael (2015). 「傾き 2/5 の格子パス」2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) . pp. 105–113. arXiv : 1605.02967 . doi :10.1137/1.9781611973761.10. ISBN 978-1-61197-376-1. S2CID 15496496。

[8] Banderier, Cyril; Wallner, Michael (2015). 「Lattice paths of slope 2/5」. Society for Industrial and Applied Mathematics, Meeting on Analytic Algorithmics and Combinatorics . 2022年3月23日閲覧。

[9] Banderier, Cyril; Wallner, Michael (2019). 「有理勾配線以下の格子パスに対するカーネル法」。Andrews, George; Krattenthaler, Christian; Krinik, Alan (編)。格子パスの組合せ論と応用。数学の発展。第58巻。Springer。pp. 119–154。doi : 10.1007 /978-3-030-11102-1。ISBN 978-3-030-11101-4. S2CID 197480284 . 2022年3月23日閲覧。

[10] Hugo Pfoertner. 「23*x^5 - 41*x^4 + 10*x^3 - 6*x^2 - x - 1 = 0 の実数解の10進展開」。オンライン整数列百科事典。 2022年3月23日閲覧。

[11] Hugo Pfoertner. 「11571875*x^5 - 5363750*x^4 + 628250*x^3 - 97580*x^2 + 5180*x - 142 = 0 の実数解の 10 進展開に 3/7 を掛けたもの」。オンライン整数列百科事典。2022年3 月 23 日閲覧。

[12] Flajolet, Philippe; Nigel Martin, G. (1985). 「データベースアプリケーションのための確率的カウントアルゴリズム」(PDF) . Journal of Computer and System Sciences . 31 (2): 182–209. doi : 10.1016/0022-0000(85)90041-8 .

[13] デュランド、マリアンヌ、フラジョレ、フィリップ (2003)。「大きな基数のログログカウント」(PDF)。アルゴリズム - ESA 2003。コンピュータサイエンスの講義ノート。第 2832 巻。p. 605。doi : 10.1007 /978-3-540-39658-1_55。ISBN 978-3-540-20064-2. 2022年3月23日閲覧。

[14] Flajolet, Philippe; Fusy, Éric; Gandouet, Olivier; Meunier, Frédéric (2007). 「Hyperloglog: 近似最適カーディナリティ推定アルゴリズムの分析」.離散数学および理論計算機科学論文集. AH .ナンシー、フランス: 137–156 . 2022年3月23日閲覧。

[15] “AofA 2014” . 2021 年3 月 20 日に取得。

[16] 「フランスのINRIAにあるHAL学際的オープンアクセスアーカイブからのAofA 2014の会議議事録のフロントページ」。 2021年3月20日閲覧。

[17] 「フランスのINRIAにあるHAL学際的オープンアクセスアーカイブからのAofA 2014の完全な科学会議議事録」。 2021年3月20日閲覧。

[18] 「ドン・クヌースの2014年の公開講義」。2022年3月23日閲覧。

[19] Bob Sedgewick (2020年10月16日). 「Cardinality Estimation」.

[20] “AofA 2016” . 2021 年3 月 20 日に取得。

[21] 「クラクフのヤギェウォ大学によるAofA 2016の完全な科学会議議事録」（PDF）。 2021年3月20日閲覧。

[22] Luc Devroye. 「編集された議事録の記事」.

[23] “AofA 2018”. 2019年8月22日時点のオリジナルよりアーカイブ。2021年3月20日閲覧。

[24] 「Dagstuhl Research Online Publication Server の AofA 2018 の完全な科学会議議事録」(PDF) 。2021 年3 月 20 日閲覧。

[25] 「AofA 2018から選ばれた論文を掲載したAlgorithmicaジャーナルの特別号」。 2021年3月20日閲覧。

[27] 「Szpankowski がフラジョレ賞を受賞」。2020年2月11日。 2021年3月20日閲覧。

[28] “AofA2024” . 2023年6月29日閲覧。