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če algoritmy, překlenutí propasti mezi teorií algoritmů a praktickými aplikacemi algoritmů ve Windows softwarové inženýrství.^[1]Jedná se o obecnou metodiku pro algoritmický výzkum.^[2]

Počátky

V roce 1995 byla zpráva od NSF - sponzorovaný seminář „s cílem posoudit současné cíle a směry komunity Theory of Computing (TOC)“ označil pomalou rychlost přijímání teoretických poznatků odborníky jako důležitý problém a navrhl opatření k

• snížit nejistotu odborníků, zda se určitý teoretický průlom promítne do praktických přínosů v jejich oblasti práce, a
• řešit nedostatek knihoven algoritmů připravených k použití, které poskytují stabilní, bezchybné a osvědčené implementace pro algoritmické problémy, a zpřístupnit snadno použitelné rozhraní pro spotřebitele knihoven.^[3]

Slibné algoritmické přístupy však byly opomíjeny kvůli obtížím v matematické analýze.^[2]

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ý Giuseppe F. Italiano.^[4]

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í algoritmy (nazývané také empirické algoritmy).

Tímto způsobem může poskytnout nový pohled na efektivitu a výkon 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 pravděpodobně neobjeví na vstupech praktického zájmu,
• algoritmus se opírá o složitost moderních hardwarových architektur, jako je datová lokalita, predikce větví, stánky instrukcí, latence instrukcí, které model stroje použitý v teorii algoritmu nedokáže 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.^[1][5]

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í, spojený s dalšími aspekty, jako jsou modely strojů nebo realistické vstupy. Tvrdí, že srovnávat algoritmické inženýrství s experimentální algoritmy je příliš omezené, protože prohlížení designu a analýzy, implementace a experimentování jako samostatných činností ignoruje rozhodující zpětnou vazbu mezi těmito prvky inženýrství algoritmů.^[2]

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.^[2]

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 umožnění opětovného použití kódu. Konstantní faktory algoritmů navíc mají takový značný 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ů. To však bohužel dělá i jednoduché randomizované algoritmy obtížné analyzovat, protože je třeba brát v úvahu jemné závislosti.^[2]

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.^[2]

Experimenty

Vidět: Experimentální algoritmy

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 rychlé experimenty důkladné testování, udržovatelnost, jednoduchost a vyladění pro konkrétní třídy vstupů.^[2]

Algoritmické knihovny

Stabilní a dobře otestované knihovny algoritmů LEDA hrají důležitou roli v přenosu technologií urychlením přijetí nových algoritmů v aplikacích. Takové knihovny snižují požadované investice a riziko pro odborníky, protože tak odstraňují břemeno porozumění a provádění 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.^[6]První workshop o algoritmickém inženýrství a experimentování (ALENEX99) se konal v Baltimore v Marylandu ve dnech 15. – 16. Ledna 1999.^[7] Sponzorovalo to DIMACY, Centrum diskrétní matematiky a teoretické informatiky (v Rutgersova univerzita ), s další podporou od SIGACT ACM Special Interest Group on Algorithms and Computory Theory, a SIAM, the Společnost pro průmyslovou a aplikovanou matematiku.^[7]

Reference