Algorithm Engineering: Bridging the Gap between Algorithm Theory and Practice

الگوریتم‌ها بلوک‌های اساسی سازنده برنامه‌های کامپیوتری هستند. با این حال، پیشرفت‌ها در سخت‌افزار رایانه، که مدل‌های رایانه‌ای سنتی را بیش از پیش غیرواقعی‌تر می‌کند، و تقاضای روزافزون برای راه‌حل کارآمد برای مسائل واقعی دنیای واقعی، منجر به افزایش شکاف بین نظریه الگوریتم کلاسیک و الگوریتم در عمل شده است. رشته نوظهور مهندسی الگوریتم با هدف پر کردن این شکاف است. مهندسی الگوریتم با استفاده از کاربردهای عینی، نظریه را با مزایای آزمایش تکمیل می کند و بر تمام جنبه های ناشی از یک فرآیند حل چرخه ای از مدل سازی واقع گرایانه، طراحی، تجزیه و تحلیل، اجرای قوی و کارآمد تا آزمایش های دقیق تأکید یکسانی دارد. این آموزش - نتیجه سمینار GI-Dagstuhl که در قلعه Dagstuhl در سپتامبر 2006 برگزار شد - جنبه های اساسی این فرآیند را در ده فصل در مورد ایده های اساسی، مسائل مدل سازی و طراحی، تجزیه و تحلیل الگوریتم ها، مدل های کامپیوتری واقعی، جنبه های پیاده سازی و نرم افزار الگوریتمی پوشش می دهد. کتابخانه ها، مطالعات موردی منتخب، و همچنین چالش های مهندسی الگوریتم. هم محققین و هم دست اندرکاران در این زمینه آن را به عنوان یک نظرسنجی پیشرفته مفید می دانند.

Algorithms are essential building blocks of computer applications. However, advancements in computer hardware, which render traditional computer models more and more unrealistic, and an ever increasing demand for efficient solution to actual real world problems have led to a rising gap between classical algorithm theory and algorithmics in practice. The emerging discipline of Algorithm Engineering aims at bridging this gap. Driven by concrete applications, Algorithm Engineering complements theory by the benefits of experimentation and puts equal emphasis on all aspects arising during a cyclic solution process ranging from realistic modeling, design, analysis, robust and efficient implementations to careful experiments. This tutorial - outcome of a GI-Dagstuhl Seminar held in Dagstuhl Castle in September 2006 - covers the essential aspects of this process in ten chapters on basic ideas, modeling and design issues, analysis of algorithms, realistic computer models, implementation aspects and algorithmic software libraries, selected case studies, as well as challenges in Algorithm Engineering. Both researchers and practitioners in the field will find it useful as a state-of-the-art survey.