تاريخ علم الخوارزميات

بناء على
صياغة مفهوم الخوارزمية اصبح بالامكان المقارنة بين الخوارزميات من حيث
فعالية خوارزميات كما اصبح بالامكان اختبار تكافؤوصحة الخوارزميات بل وتحديد
المجال الذي يمكن استخدامها فيه
اقدم الخوارزميات المعروقة لدينا هي
خوارزمية اوقليدس المعروفة لايجاد القاسم(العامل) المشترك لعددين طبيعيين

طبعا في تلك الفترة كانت مسالة ايجاد طريقة لفعل شيء معروفة رغم عدم
صياغة مفهوم الخوارزمية فيه و كان الرياضيون
وحتى القرن العشرين يستخدمون
كلمة طريقة (method) لوصف مجموعة من الخطوات التي تستخدم لحل مسالة
معينة.
اول خطوة حقيقية لوضع اسس نظرية الخورازميات الحديثة جاءت من نظرية
في المنطق اثبتها العالم الالماني كورث هيدل
عام 1931 كان مضمون هذه
النظرية ان بعض المعضلات الرياضية لا يمكن حلها من بفئة معينة .ومن هنا جاءت
فكرة البحث عنما إذا كان هذا الشئ ينطبق على الفئات الاخرى واعطت هذه النظرية
دفعا كبيرا لبحث وتحليل واعادة صياغة مفهوم الخوارزمية .
الجدير بالذكر ان
الاعمال الاساسية في هذا امجال كانت منشورة في منتصف 1930 من قبل العلماء
تيورنج وتشرتش وبوست
شكلت هذه النماذج التي وضعها هؤلاء العلماء (الة
تيورنج-الة بوست – ونماذج الدوال التكرارية لتشرتش ) التصورات الاولى لمفهوم
الخوارزمية كانت الفرضية المصاغة التي هولاء العلماء الثلاثة كل على حدة قد
اثبتت تكافوء هذه النماذج فيما
كا ان اهم نتائج من هذه الاعمال هو اثبات
استحالة وجود حل للكثير من المسائل .
في عام 1950 ادخل العالم كولماجوروف
اضافات جديدة على نظرية الخوارزميات مستفيدا من اعمال مواطنه ماركوف(عالمان
روسيان )
في مجال Formal grammar كما تم اثبات تكافؤ النماذج التي وضعها
العلماء الخمسة وهذا يعني امكانية حل المسائل في
كل النماذج الصورية
الخمسة اذا امكن حلها في اي واحد منها على الاقل .
بظهور الحواسيب وانتشار
استخدامها وتوسع مجال المشاكل التي يمكن حلها بالحاسوب في الستينات
والسبعينات ظهرت الفروع التالية لعلم الخوارزميات :
- التيار التقليدي
(صياغة المسالة في اللغات الصورية , تعقيد الفئة, اكتشاف فئة NP,..)
اهم
رواد هذه التيار اديموندس OR-Ben-
- نظرية التحليل المقارب الخورازميات
(مفاهيم: صعوبة وتعقيد الخوارزميات-مبدا تقييم الخوارزمية-طرق الحصول على
الحلول المقاربة و الوقت اللازم لتنفيذ الخوارزمية ) اهم رواد هذا التيار
Knuth,Aho,Hopcroft,Ulman,Karp
- التحليل العملي للخوارزميات الحسابية
واهم مفاهيم هذه المدرسة (الحصول على دالة تمثل صعوبة الخوارزمية وinterval
analysis و طريقة اختيار الخوارزمية الصحيحة وRational algorithm)
اهم
الاعمال التي تمثل هذا ا التيار الفكري هو سلسلة كتب البروفيسور D.knuth فن
البرمجة
the art of the computer programming
هناك اقسام اخرى وثيقة
الصلة بنظرية الخوارزميات اختص منها بالذكر (البرمجة الخطية و greedy
algorithms و
) بتعميم ما سبق من الحديث عن اقسام نظرية الخوارزميات فان
الاتجاهات الرئيسية لعلم الخوارزميات

اقسام نظرية الخوارزميات فان
الاتجاهات الرئيسية لعلم الخوارزميات
في عصرنا الحديث هي
-صياغة مفهوم
الخوارزمية والبحث عن النماذج الخوارزمية الحديثة
-اثبات استحالة حل بعض
المسائل خوارزميا
-تصنيف المشاكل وتحديد الفئات المختلفة
-اثبات تعقيد
الخوارزمية بشكل نظري
-دراسة وتحليل الدوال التكرارية (recursion)

-الحصول على دوال تحدد تعقيد الخوارزمية
-تصميم طرق لتصنيف
الخوارزميات
-دراسة استهلاك الخوارزميات للذاكرة
-وضع اسس يتم بها
المقارنة بين الخورازميات وتطوير اساليب المقارنة بين الخوارزميات
في
الحقيقة (والحق يقال) حققت نظرية الخورزميات العديد من النجاحات في تطبيقاتها
وذلك على الصعيدين النظري و العملي
الصعيد النظري:
عند دراسة العديد من
المشكلات والمسائل اصبح بالامكان الاجابة على سؤال هل من الممكن وجود حل لهذه
المسالة
خوارزميا ؟ وهل بالامكان تحويل هذه المسالة الى مسالة اخرى معروفة
الحل مثلا الة تيورنج
وهل ينتمي هذه المسالة الى المسائل من لنوع مثلا NP
في حالة ما اذا كان الجواب نعم؟ عندئذ فقط نستطيع عن التحدث عن الوقت الذي
تستهلكه الخورازمية المقترحة لحل المشكلة وعن عدم وخوارزمية دقيقة لحل
المسالة وهكذا..
الصعيد العملي
طرق تحليل الخوارزميات واهمها
asymptotic analysis وهذا يمكننا من تنفيذ الاشياء التالية
-الاختيار
السليم من بين مجموعة من الخوارزميات التس تستطيع حل المسالة وذلك حسب معيار
معين Criterion للاختيار
الافضل بين هذه الخوارزميات مثلا الوقت المستهلك
لاتمام المهمة وحجم الذاكرة المستهلكة وهكذا
-الحصول على دوال للتعبير بها
عن تعقيد الخوارزمية
-الحصول على قيم ونتائج تؤكد استحالة حل مسالة معينة
خلال فترة زمنية معينة بمعنى ان المسالة ستحل في كل الحالات بزمن اكبر من
الزمن المحدد في المسالة المعطى في الحقيقة هذا البند الاخير يستند عليه علم
التشفير حيث انك ستعرف انك لن تستطيع فك الشفرة في اقل من 10 سنوات مثلا

-تصميم خوارزميات فعالة ذلت تطبيقات هامة في مجال المعلو
ماتية

قبل ان اكمل المقال احب ان انوه الخوارزمية ايا كانت يجب ان
تتصف بما ياتي
1-وصف محدد للخوارزمية
2-عدد محدد من الخطوات
3-ان
يحل المساله المطلوبة مهما كانت القيم المدخلة
4-ان يعطي حلا صحيحا

بانتظار ردودكم