アルゴリズムエンジニアリング

アルゴリズム工学は、コンピュータアルゴリズムの設計、分析、実装、最適化、プロファイリング、実験的評価に焦点を当て、アルゴリズム理論とソフトウェア工学におけるアルゴリズムの実際の応用との間のギャップを埋めます。^[1] これは、アルゴリズム研究のための一般的な方法論です。^[2]

1995年に、NSFが主催した「計算理論（TOC）コミュニティの現在の目標と方向性を評価する」ワークショップの報告書では、実践者による理論的洞察の採用の遅さが重要な問題であると指摘され、対策が提案されました。

• 特定の理論上のブレークスルーが、その仕事の分野で実際的な利益につながるかどうかという実務家の不確実性を軽減し、
• アルゴリズムの問​​題に対して安定的でバグのない十分にテストされた実装を提供し、ライブラリ利用者に使いやすいインターフェースを公開する、すぐに使えるアルゴリズムライブラリの不足に取り組みます。^[3]

しかし、有望なアルゴリズム的アプローチも、数学的分析の難しさのために無視されてきました。^[2]

「アルゴリズムエンジニアリング」という用語は、1997年にジュゼッペ・F・イタリアーノが主催した第1回アルゴリズムエンジニアリングワークショップ（WAE97）で初めて具体的に使用されました。^[4]

アルゴリズム エンジニアリングは、アルゴリズム理論に取って代わったり競合したりすることを意図しているのではなく、実験的アルゴリズム(経験的アルゴリズムとも呼ばれる)によって形式的なアプローチを充実、洗練、強化しようとします。

これにより、次のような場合のアルゴリズムの効率とパフォーマンスに関する新たな洞察が得られます。

• 手元のアルゴリズムはアルゴリズム理論の分析にはあまり適していない。
• 形式的な分析は悲観的に、実用的な関心の入力には現れそうにない限界を示唆している。
• このアルゴリズムは、データの局所性、分岐予測、命令ストール、命令の遅延など、アルゴリズム理論で使用されるマシンモデルでは必要な詳細を捉えることができない現代のハードウェアアーキテクチャの複雑さに依存しています。
• 異なる定数コストと漸近的動作を持つ競合アルゴリズム間のクロスオーバーを決定する必要がある。^{[1] [5]}

一部の研究者は、アルゴリズム工学の方法論を、アルゴリズムの設計、分析、実装、実験的評価からなるサイクルと説明し、さらに機械モデルや現実的な入力などの側面が加わっているとしています。彼らは、設計と分析、実装と実験を別々の活動と見なすと、アルゴリズム工学のこれらの要素間の重要なフィードバックループが無視されるため、アルゴリズム工学を実験アルゴリズムと同一視するのは限定的すぎると主張しています。^[2]

特定のアプリケーションはアルゴリズムエンジニアリングの方法論の範囲外ですが、問題とその基盤となるマシンの現実的なモデルを形成する上で重要な役割を果たし、実験のための実際の入力やその他の設計パラメータを提供します。^[2]

通常、アルゴリズムの漸近的動作に重点を置くアルゴリズム理論と比較して、アルゴリズム エンジニアは、アルゴリズムの単純さ、実際のハードウェア上のプログラミング言語での実装可能性、コードの再利用の許可など、さらなる要件を念頭に置く必要があります。さらに、アルゴリズムの定数係数は実際の入力に非常に大きな影響を与えるため、漸近的動作が悪いアルゴリズムの方が、定数係数が低いために実際にはパフォーマンスが向上する場合があります。

いくつかの問題は、決定論的アルゴリズムよりもヒューリスティックスとランダム化アルゴリズムでより簡単かつ効率的に解決できます。残念ながら、微妙な依存関係を考慮する必要があるため、単純なランダム化アルゴリズムでさえ分析が困難になります。^[2]

理論的洞察、定式化されたアルゴリズム、プログラミング言語、ハードウェア間の大きな意味的ギャップは、単純なアルゴリズムであっても効率的な実装に課題をもたらします。これは、実装の詳細が実行動作に波及効果をもたらす可能性があるためです。アルゴリズムの複数の実装を比較する唯一の信頼できる方法は、チューニングとプロファイリングにかなりの時間を費やし、それらのアルゴリズムを複数のアーキテクチャで実行し、生成されたマシンコードを確認することです。^[2]

参照:実験的アルゴリズム

実験に使用されるアルゴリズムの実装は、アプリケーションで使用できるコードとは大きく異なります。前者は、迅速なプロトタイピング、パフォーマンス、実験中の測定のための計測を優先しますが、後者は、徹底したテスト、保守性、シンプルさ、特定の入力クラスの調整を必要とします。^[2]

LEDAのような、安定性があり、十分にテストされたアルゴリズム ライブラリは、アプリケーションへの新しいアルゴリズムの採用を加速することで、技術移転において重要な役割を果たします。このようなライブラリは、学術研究の結果を理解して実装する負担を取り除くため、実務者に必要な投資とリスクを軽減します。

アルゴリズム エンジニアリングに関する 2 つの主要な会議が毎年開催されます。

• 実験アルゴリズムに関するシンポジウム (SEA) は、1997 年に設立されました (旧称 WEA)。
• 1999 年に設立された SIAM アルゴリズム エンジニアリングおよび実験会議 (ALENEX)。

1997 アルゴリズム工学ワークショップ (WAE'97) は、1997 年 9 月 11 日から 13 日にイタリアのベニスで開催されました。第 3 回アルゴリズム工学国際ワークショップ (WAE'99) は、1999 年 7 月にイギリスのロンドンで開催されました。 ^[6] 最初のアルゴリズム工学および実験ワークショップ (ALENEX99) は、1999 年 1 月 15 日から 16 日にメリーランド州ボルチモアで開催されました。^[7]このワークショップは、ラトガース大学にある離散数学および理論計算機科学センター( DIMACS ) が主催し、 SIGACT (ACM アルゴリズムおよび計算理論特別興味グループ) および SIAM (産業応用数学協会)が追加支援しました。^[7]