هندسة الخوارزميات

يركز هندسة الخوارزميات على تصميم وتحليل وتنفيذ وتحسين وتحديد خصائص وتقييم الخوارزميات الحاسوبية تجريبياً ، مما يسد الفجوة بين نظرية الخوارزميات والتطبيقات العملية للخوارزميات في هندسة البرمجيات . ^{[ 1 ]} وهي منهجية عامة لأبحاث الخوارزميات. ^{[ 2 ]}

الأصول

في عام 1995، أشار تقرير صادر عن ورشة عمل برعاية مؤسسة العلوم الوطنية "بهدف تقييم الأهداف والتوجهات الحالية لمجتمع نظرية الحوسبة " إلى بطء وتيرة تبني الممارسين للرؤى النظرية كقضية مهمة، واقترح تدابير لـ

تقليل حالة عدم اليقين لدى الممارسين بشأن ما إذا كان تحقيق اختراق نظري معين سيترجم إلى مكاسب عملية في مجال عملهم، و
معالجة النقص في مكتبات الخوارزميات الجاهزة للاستخدام، والتي توفر تطبيقات مستقرة وخالية من الأخطاء ومختبرة جيدًا للمشاكل الخوارزمية، وتوفر واجهة سهلة الاستخدام لمستخدمي المكتبة. ^{[ 3 ]}

لكن أيضاً، تم إهمال الأساليب الخوارزمية الواعدة بسبب الصعوبات في التحليل الرياضي . ^{[ 2 ]}

تم استخدام مصطلح "هندسة الخوارزميات" لأول مرة بشكل محدد في عام 1997، مع أول ورشة عمل حول هندسة الخوارزميات (WAE97)، والتي نظمها جوزيبي إف. إيتاليانو . ^{[ 4 ]}

الفرق عن نظرية الخوارزميات

لا تهدف هندسة الخوارزميات إلى استبدال نظرية الخوارزميات أو منافستها، ولكنها تحاول إثراء وتطوير وتعزيز مناهجها الرسمية من خلال الخوارزميات التجريبية (وتسمى أيضًا الخوارزميات التجريبية).

وبهذه الطريقة، يمكن أن يوفر ذلك رؤى جديدة حول كفاءة وأداء الخوارزميات في الحالات التي

إن الخوارزمية قيد الدراسة أقل قابلية للتحليل النظري للخوارزميات،
يشير التحليل الرسمي بتشاؤم إلى حدود من غير المرجح أن تظهر في المدخلات ذات الأهمية العملية.
تعتمد الخوارزمية على تعقيدات بنى الأجهزة الحديثة مثل موضع البيانات، وتوقع التفرع، وتوقفات التعليمات، وزمن استجابة التعليمات، وهي أمور لا يستطيع نموذج الآلة المستخدم في نظرية الخوارزميات استيعابها بالتفاصيل المطلوبة.
يجب تحديد نقطة التقاطع بين الخوارزميات المتنافسة ذات التكاليف الثابتة المختلفة والسلوكيات التقاربية المختلفة. ^{[ 1 ]}^{[ 5 ]}

المنهجية

يصف بعض الباحثين منهجية هندسة الخوارزميات بأنها دورة تتألف من تصميم الخوارزمية وتحليلها وتنفيذها وتقييمها تجريبياً، بالإضافة إلى جوانب أخرى مثل نماذج الآلات أو المدخلات الواقعية. ويجادلون بأن مساواة هندسة الخوارزميات بالخوارزميات التجريبية أمرٌ قاصر، لأن اعتبار التصميم والتحليل والتنفيذ والتجريب أنشطة منفصلة يتجاهل حلقة التغذية الراجعة الحاسمة بين هذه العناصر في هندسة الخوارزميات. ^{[ 2 ]}

نماذج واقعية ومدخلات حقيقية

على الرغم من أن التطبيقات المحددة تقع خارج نطاق منهجية هندسة الخوارزميات، إلا أنها تلعب دورًا مهمًا في تشكيل نماذج واقعية للمشكلة والآلة الأساسية، وتوفر مدخلات حقيقية ومعايير تصميم أخرى للتجارب. ^{[ 2 ]}

تصميم

بالمقارنة مع نظرية الخوارزميات، التي تركز عادةً على السلوك التقاربي للخوارزميات، يحتاج مهندسو الخوارزميات إلى مراعاة متطلبات إضافية: بساطة الخوارزمية، وإمكانية تنفيذها بلغات البرمجة على أجهزة حقيقية، والسماح بإعادة استخدام الكود . بالإضافة إلى ذلك، فإن العوامل الثابتة للخوارزميات لها تأثير كبير على مدخلات العالم الحقيقي، لدرجة أنه في بعض الأحيان قد يكون أداء الخوارزمية ذات السلوك التقاربي الأسوأ أفضل عمليًا نظرًا لانخفاض هذه العوامل الثابتة.

تحليل

يمكن حل بعض المشكلات باستخدام الطرق الاستدلالية والخوارزميات العشوائية بطريقة أبسط وأكثر كفاءة من الخوارزميات الحتمية. مع ذلك، فإن هذا يجعل حتى أبسط الخوارزميات العشوائية صعبة التحليل لوجود تبعيات دقيقة يجب أخذها في الاعتبار . ^{[ 2 ]}

تطبيق

تشكل الفجوات الدلالية الهائلة بين الرؤى النظرية والخوارزميات المصاغة ولغات البرمجة والأجهزة تحديًا أمام التنفيذ الفعال حتى للخوارزميات البسيطة، لأن تفاصيل التنفيذ الصغيرة قد يكون لها تأثيرات متتالية على سلوك التنفيذ. والطريقة الموثوقة الوحيدة لمقارنة عدة تطبيقات لخوارزمية ما هي تخصيص وقت طويل لضبطها وتحليل أدائها، وتشغيل تلك الخوارزميات على بنى معمارية متعددة، والاطلاع على شفرة الآلة الناتجة . ^{[ 2 ]}

التجارب

انظر: الخوارزميات التجريبية

هندسة التطبيقات

تختلف تطبيقات الخوارزميات المستخدمة في التجارب اختلافًا كبيرًا عن الشيفرة البرمجية القابلة للاستخدام في التطبيقات. فبينما تُعطي الأولى الأولوية للنماذج الأولية السريعة والأداء العالي وأدوات القياس أثناء التجارب، تتطلب الثانية اختبارًا شاملًا وسهولة الصيانة والبساطة والضبط لأنواع محددة من المدخلات . ^{[ 2 ]}

مكتبات الخوارزميات

تلعب مكتبات الخوارزميات المستقرة والمختبرة جيدًا، مثل LEDA، دورًا هامًا في نقل التكنولوجيا من خلال تسريع تبني الخوارزميات الجديدة في التطبيقات. وتُقلل هذه المكتبات من الاستثمار المطلوب والمخاطر التي يتحملها الممارسون، لأنها تُزيل عبء فهم نتائج البحوث الأكاديمية وتطبيقها.

المؤتمرات

يتم تنظيم مؤتمرين رئيسيين سنوياً حول هندسة الخوارزميات، وهما:

ندوة حول الخوارزميات التجريبية (SEA) ، التي تأسست عام 1997 (المعروفة سابقًا باسم WEA).
اجتماع SIAM حول هندسة الخوارزميات والتجارب (ALENEX)، الذي تم تأسيسه في عام 1999.

عُقدت ورشة عمل هندسة الخوارزميات لعام 1997 (WAE'97) في مدينة البندقية (إيطاليا) في الفترة من 11 إلى 13 سبتمبر 1997. وعُقدت ورشة العمل الدولية الثالثة لهندسة الخوارزميات (WAE'99) في لندن، المملكة المتحدة، في يوليو 1999. ^{[ 6 ]} وعُقدت ورشة العمل الأولى لهندسة الخوارزميات والتجريب (ALENEX99) في بالتيمور، ميريلاند، في الفترة من 15 إلى 16 يناير 1999. ^{[ 7 ]} وقد رُعيت هذه الورشة من قِبل مركز DIMACS ، مركز الرياضيات المتقطعة وعلوم الحاسوب النظرية (في جامعة روتجرز )، بدعم إضافي من SIGACT ، مجموعة الاهتمام الخاصة بالخوارزميات ونظرية الحوسبة التابعة لجمعية ACM، وجمعية SIAM، جمعية الرياضيات الصناعية والتطبيقية . ^{[ 7 ]}

انظر أيضاً

مراجع

1 2 "هندسة الخوارزميات"، كاميل ديميتريسكو، إيرين فينوكتشي، جوزيبي إف إيتاليانو ، الويب: http://www.dis.uniroma1.it/~demetres/docs/ae.pdf
1 2 3 4 5 6 7 "هندسة الخوارزميات - محاولة لوضع تعريف"، بيتر ساندرز ، الموقع الإلكتروني: http://algo2.iti.kit.edu/documents/definition.pdf ، مؤرشف بتاريخ 27 يوليو 2014 في أرشيف الإنترنت (Wayback Machine).
↑ "الفرص الناشئة لعلوم الحاسوب النظرية"، أهو، جونسون، كارب، كوساراجو، ماكجيوخ، باباديميتريو، الموقع الإلكتروني: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9160
↑ "ورشة عمل حول هندسة الخوارزميات" . مؤرشفة من الأصل بتاريخ 27-09-2018 . تم الاطلاع عليها بتاريخ 14-09-2009 .
↑ "نحو منهج في الخوارزميات التجريبية"، برنارد إم إي موريه، الموقع الإلكتروني: http://infoscience.epfl.ch/record/97865/files/dimacs_algorithmics.pdf
^ هندسة الخوارزميات: ورشة العمل الدولية الثالثة ، جيفري سكوت فيتر، كريستوس د. زارولياجيس، 1999، الويب: BGoogle-sC .
1 2 "ورشة عمل حول هندسة الخوارزميات والتجارب" (نظرة عامة)، JHU.edu، 1999، الموقع الإلكتروني: JHU-ALENEX99 مؤرشف في 2010-10-17 في Wayback Machine .

[AE-1] 1 2 "هندسة الخوارزميات"، كاميل ديميتريسكو، إيرين فينوكتشي، جوزيبي إف إيتاليانو ، الويب: http://www.dis.uniroma1.it/~demetres/docs/ae.pdf

[AEDef-2] 1 2 3 4 5 6 7 "هندسة الخوارزميات - محاولة لوضع تعريف"، بيتر ساندرز ، الموقع الإلكتروني: http://algo2.iti.kit.edu/documents/definition.pdf ، مؤرشف بتاريخ 27 يوليو 2014 في أرشيف الإنترنت (Wayback Machine).

[EOTCS-3] "الفرص الناشئة لعلوم الحاسوب النظرية"، أهو، جونسون، كارب، كوساراجو، ماكجيوخ، باباديميتريو، الموقع الإلكتروني: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9160

[4] "ورشة عمل حول هندسة الخوارزميات" . مؤرشفة من الأصل بتاريخ 27-09-2018 . تم الاطلاع عليها بتاريخ 14-09-2009 .

[TDEA-5] "نحو منهج في الخوارزميات التجريبية"، برنارد إم إي موريه، الموقع الإلكتروني: http://infoscience.epfl.ch/record/97865/files/dimacs_algorithmics.pdf

[6] هندسة الخوارزميات: ورشة العمل الدولية الثالثة ، جيفري سكوت فيتر، كريستوس د. زارولياجيس، 1999، الويب: BGoogle-sC .

[jhu-7] 1 2 "ورشة عمل حول هندسة الخوارزميات والتجارب" (نظرة عامة)، JHU.edu، 1999، الموقع الإلكتروني: JHU-ALENEX99 مؤرشف في 2010-10-17 في Wayback Machine .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]