Algoritmické inženýrství - Algorithm engineering
Algoritmické inženýrství se zaměřuje na návrh, analýzu, implementaci, optimalizaci, profilování a experimentální vyhodnocení počítačových algoritmů , překlenutí propasti mezi teorií algoritmů a praktickými aplikacemi algoritmů v softwarovém inženýrství . Jedná se o obecnou metodiku pro algoritmický výzkum.
Obsah
Počátky
V roce 1995 zpráva z dílny sponzorované NSF „s cílem posoudit současné cíle a směry komunity Theory of Computing (TOC)“ označila pomalou rychlost přijímání teoretických poznatků praktiky jako důležitý problém a navrhla opatření na
- snížit nejistotu odborníků, zda se určitý teoretický průlom promítne do praktických výhod v jejich oblasti práce, a
- řešit nedostatek knihoven algoritmů připravených k použití, které poskytují stabilní, bezchybné a dobře testované implementace pro algoritmické problémy, a zpřístupnit snadno použitelné rozhraní pro spotřebitele knihoven.
Ale také slibné algoritmické přístupy byly zanedbány kvůli obtížím v matematické analýze.
Termín „algoritmické inženýrství“ byl poprvé použit se specifičností v roce 1997, kdy se uskutečnil první Workshop o algoritmickém inženýrství (WAE97), který organizoval Giuseppe F. Italiano .
Rozdíl od teorie algoritmů
Algoritmické inženýrství nemá v úmyslu nahradit nebo konkurovat teorii algoritmů, ale snaží se obohatit, vylepšit a posílit své formální přístupy experimentálními algoritmy (nazývanými také empirické algoritmy).
Tímto způsobem může poskytnout nový pohled na efektivitu a výkonnost algoritmů v případech, kdy
- algoritmus po ruce je méně vhodný pro teoretickou analýzu algoritmu,
- formální analýza pesimisticky naznačuje hranice, které se na vstupech praktického zájmu pravděpodobně neobjeví,
- algoritmus se opírá o složitost moderních hardwarových architektur, jako je datová lokalita, predikce větví, stánky s instrukcemi, latence instrukcí, které strojový model použitý v Algorithm Theory není schopen zachytit v požadovaných detailech,
- je třeba určit přechod mezi konkurenčními algoritmy s různými stálými náklady a asymptotickým chováním.
Metodologie
Někteří vědci popisují metodologii algoritmického inženýrství jako cyklus skládající se z návrhu algoritmu, analýzy, implementace a experimentálního vyhodnocení, ke kterému se připojují další aspekty, jako jsou modely strojů nebo realistické vstupy. Tvrdí, že srovnávání algoritmického inženýrství s experimentálními algoritmy je příliš omezené, protože prohlížení návrhu a analýzy, implementace a experimentování jako samostatných činností ignoruje rozhodující zpětnou vazbu mezi těmito prvky algoritmického inženýrství.
Realistické modely a skutečné vstupy
Zatímco konkrétní aplikace jsou mimo metodiku algoritmického inženýrství, hrají důležitou roli při formování realistických modelů problému a základního stroje a dodávají skutečné vstupy a další konstrukční parametry pro experimenty.
Design
Ve srovnání s teorií algoritmů, která se obvykle zaměřuje na asymptotické chování algoritmů, si inženýři algoritmů musí pamatovat na další požadavky: Jednoduchost algoritmu, implementovatelnost v programovacích jazycích na reálném hardwaru a opětovné použití kódu. Konstantní faktory algoritmů mají navíc tak velký dopad na vstupy v reálném světě, že někdy algoritmus s horším asymptotickým chováním funguje v praxi lépe kvůli nižším konstantním faktorům.
Analýza
Některé problémy lze vyřešit heuristikou a randomizovanými algoritmy jednodušším a efektivnějším způsobem než pomocí deterministických algoritmů. Díky tomu je bohužel obtížné analyzovat i jednoduché randomizované algoritmy, protože je třeba brát v úvahu jemné závislosti .
Implementace
Obrovské sémantické mezery mezi teoretickými poznatky, formulovanými algoritmy, programovacími jazyky a hardwarem představují výzvu pro efektivní implementaci i jednoduchých algoritmů, protože malé podrobnosti implementace mohou mít vlnící se účinky na chování provádění. Jediným spolehlivým způsobem, jak porovnat několik implementací algoritmu, je strávit značné množství času laděním a profilováním, spuštěním těchto algoritmů na více architekturách a prohlížením generovaného strojového kódu.
Experimenty
Aplikační inženýrství
Implementace algoritmů použitých pro experimenty se významně liší od kódu použitelného v aplikacích. Zatímco první upřednostňuje rychlé prototypování, výkon a vybavení pro měření během experimentů, druhý vyžaduje důkladné testování, udržovatelnost, jednoduchost a vyladění pro konkrétní třídy vstupů .
Algoritmické knihovny
Stabilní a dobře otestované knihovny algoritmů, jako je LEDA, hrají důležitou roli v přenosu technologií tím, že urychlují přijímání nových algoritmů v aplikacích. Takové knihovny snižují potřebné investice a riziko pro odborníky, protože tak odstraňují břemeno porozumění a implementace výsledků akademického výzkumu.
Konference
Každoročně se pořádají dvě hlavní konference o Algorithm Engineering, a to:
- Sympózium o experimentálních algoritmech (SEA), založené v roce 1997 (dříve známé jako WEA).
- Setkání SIAM o algoritmickém inženýrství a experimentech (ALENEX), založené v roce 1999.
Workshop z roku 1997 o algoritmickém inženýrství (WAE'97) se konal v Benátkách (Itálie) ve dnech 11. – 13. Září 1997. Třetí mezinárodní workshop o algoritmickém inženýrství (WAE'99) se konal v Londýně ve Velké Británii v červenci 1999. První Workshop o algoritmickém inženýrství a experimentování (ALENEX99) se konal v Baltimore v Marylandu ve dnech 15. – 16. Ledna 1999. Sponzoroval jej DIMACS , Centrum diskrétní matematiky a teoretické informatiky (na Rutgers University ), s další podporou SIGACT , ACM Special Interest Group on Algorithms and Computory Theory a SIAM, společnost pro průmyslovou a aplikovanou matematiku .