Algoritmusmérnöki munka - Algorithm engineering

Az algoritmustervezés a számítógépes algoritmusok tervezésére, elemzésére, megvalósítására, optimalizálására, profilozására és kísérleti értékelésére összpontosít , áthidalva az algoritmuselmélet és az algoritmusok gyakorlati alkalmazása közötti szakadékot a szoftverfejlesztésben . Ez az algoritmikus kutatás általános módszertana.

Eredet

1995-ben egy NSF által szponzorált műhelyjelentés "a számítástechnika elméletének (TOC) közösség jelenlegi céljainak és irányainak felmérése céljából" fontos kérdésként azonosította a gyakorlati szakemberek által alkalmazott elméleti betekintés lassú ütemét, és javasolt intézkedéseket javasolt. nak nek

• csökkenti a szakemberek azon bizonytalanságát, hogy egy bizonyos elméleti áttörés gyakorlati haszonnal jár-e a munkaterületen, és
• kezelni kell a használatra kész algoritmus könyvtárak hiányát, amelyek stabil, hibamentes és jól bevizsgált megvalósítást biztosítanak az algoritmikus problémákhoz, és könnyen hozzáférhető felületet fednek fel a könyvtári felhasználók számára.

Ugyanakkor az ígéretes algoritmikus megközelítéseket elhanyagolták a matematikai elemzés nehézségei miatt.

Az "algoritmusmérnöki" kifejezést specifikusan használták 1997-ben, az algoritmusmérnöki műhely (WAE97), amelyet Giuseppe F. Italiano szervezett, első alkalommal .

Különbség az algoritmus elmélettől

Az algoritmustervezés nem az algoritmuselméletet kívánja felváltani, vagy azzal versenyezni, hanem megpróbálja gazdagítani, finomítani és megerősíteni formális megközelítéseit kísérleti algoritmusokkal (más néven empirikus algoritmusokkal).

Ily módon új betekintést nyújthat az algoritmusok hatékonyságába és teljesítményébe olyan esetekben, amikor

• a rendelkezésre álló algoritmus kevésbé alkalmazható az algoritmuselméleti elemzésre,
• a formális elemzés pesszimista módon olyan határokat javasol, amelyek valószínűleg nem jelennek meg a gyakorlati érdeklődésre számot tartó bemeneteknél,
• az algoritmus a modern hardver-architektúrák bonyolultságaira támaszkodik, mint például az adatok lokalitása, az ág-előrejelzés, az utasítás-leállások, az utasítás-késleltetések, amelyeket az algoritmuselméletben használt gépmodell nem képes a kívánt részletekbe foglalni,
• meg kell határozni a különböző állandó költségekkel járó, egymással versengő algoritmusok és az aszimptotikus viselkedés közötti kereszteződést.

Módszertan

Néhány kutató az algoritmusmérnöki módszertant úgy határozza meg, mint egy ciklust, amely algoritmustervezésből, elemzésből, megvalósításból és kísérleti értékelésből áll, és amelyeket további szempontok, például gépi modellek vagy reális bemenetek kapcsolnak össze. Azt állítják, hogy az algoritmusmérés és a kísérleti algoritmus összehasonlítása túlságosan korlátozott, mivel a tervezés és az elemzés, a megvalósítás és a kísérlet külön tevékenységekként történő megfigyelése figyelmen kívül hagyja az algoritmusmérés ezen elemei közötti kritikus visszajelzési hurkot.

Reális modellek és valós inputok

Míg a konkrét alkalmazások kívül esnek az algoritmustervezés módszertanán, fontos szerepet játszanak a probléma és az annak alapjául szolgáló gép reális modelleinek kialakításában, és valós inputokat és egyéb tervezési paramétereket szolgáltatnak a kísérletekhez.

Tervezés

Az algoritmuselmélettel összehasonlítva, amely általában az algoritmusok aszimptotikus viselkedésére koncentrál, az algoritmusmérnököknek szem előtt kell tartaniuk a további követelményeket: az algoritmus egyszerűségét, a programozási nyelvek valós hardveren történő megvalósíthatóságát és a kód újrafelhasználását. Ezenkívül az algoritmusok állandó tényezői olyan jelentős hatást gyakorolnak a valós bemenetekre, hogy a rosszabb aszimptotikus viselkedésű algoritmusok néha jobban teljesítenek a gyakorlatban az alacsonyabb állandó tényezők miatt.

Elemzés

Néhány problémát a heurisztikákkal és a randomizált algoritmusokkal egyszerűbben és hatékonyabban lehet megoldani, mint a determinisztikus algoritmusokkal. Sajnos ez még az egyszerű, randomizált algoritmusokat is megnehezíti az elemzés, mivel apró függőségeket kell figyelembe venni .

Végrehajtás

Az elméleti betekintés, a megfogalmazott algoritmusok, a programozási nyelvek és a hardver közötti óriási szemantikai rések kihívást jelentenek még az egyszerű algoritmusok hatékony megvalósításában is, mivel a kis megvalósítási részletek hullámzó hatással lehetnek a végrehajtási viselkedésre. Az egyetlen megbízható módszer az algoritmus több megvalósításának összehasonlítására, ha jelentős időt töltenek a hangolással és profilozással, ezen algoritmusok futtatásával több architektúrán, és a generált gépi kód megnézésével.

kísérletek

Lásd: Kísérleti algoritmusok

Alkalmazástechnika

A kísérletekhez használt algoritmusok megvalósítása jelentős mértékben különbözik az alkalmazásokban használható kódoktól. Míg az előbbi a kísérletek során a gyors prototípuskészítést, a teljesítményt és a méréstechnikát részesíti előnyben, az utóbbi alapos tesztelést, karbantarthatóságot, egyszerűséget és hangolást igényel az egyes bemeneti osztályok számára .

Algoritmus könyvtárak

A stabil, jól tesztelt algoritmuskönyvtárak, mint például a LEDA , fontos szerepet játszanak a technológiaátadásban, mivel felgyorsítják az új algoritmusok alkalmazását az alkalmazásokban. Az ilyen könyvtárak csökkentik a szakemberek számára szükséges beruházást és kockázatot, mivel kiküszöbölik a tudományos kutatási eredmények megértésének és végrehajtásának terhet.

Konferenciák

Évente két fő konferenciát rendeznek az algoritmusmérnöki témában:

• Szimpózium a kísérleti algoritmusokról (SEA), 1997-ben alakult (korábban WEA néven ismert).
• Az 1999-ben alapított SIAM algoritmusmérnöki és kísérleti találkozó (ALENEX).

Az algoritmusmérnöki 1997. évi műhelyt (WAE'97) Velencében (Olaszország) 1997. szeptember 11–13-án tartották. A harmadik nemzetközi algoritmusmérnöki műhelyt (WAE'99) 1999. júliusában Londonban, az Egyesült Királyságban tartották. Az első Workshop algoritmus Mérnöki és kísérletezés (ALENEX99) tartott Baltimore, Maryland január 15-16 1999. támogatta DIMACS , a Center for Diszkrét matematika és elméleti Computer Science (a Rutgers University ), kiegészítő támogatást SIGACT , az ACM algoritmusok és számításelmélet érdekcsoportja és az SIAM, az Ipari és Alkalmazott Matematika Társasága .

Irodalom