الخوارزميات وهياكل البيانات
مقدمة في دوال التكرار
ما هي البيانات؟
أي معلومات مفيدة - يمكن تخزينها أو حفظها للرجوع إليها في المستقبل على سبيل المثال في المنظمة يمكن أن تكون اسم الموظف والعمر والقسم والعنوان وما إلى ذلك
هياكل البيانات
بنية البيانات هي طريقة لتنظيم كل عنصر في البيانات الذي لا يأخذ فقط في الاعتبار العنصر المخزن ولكن أيضًا علاقتها ببعضها البعض.
يمكن البحث في أي مؤسسة لمجموعة من السجلات أو معالجتها بأي ترتيب أو تعديلها.
يمكن أن يؤدي اختيار بنية البيانات والخوارزمية إلى إحداث فرق بين البرنامج الذي يتم تشغيله في بضع ثوانٍ أو عدة أيام.
الكفاءة: يُقال إن الحل يكون فعالًا إذا كان يحل المشكلة ضمن قيود موارده (المكان والزمان)
حدد هيكل البيانات كما يلي:
* تحليل المشكلة لتحديد قيود الموارد التي يجب أن يفي بها الحل.
* تحديد العمليات الأساسية التي يجب دعمها.
حدد قيود الموارد لكل عملية.
* حدد هيكل البيانات الذي يلبي هذه المتطلبات على أفضل وجه.
تعريف الريكيرشن.
تُعرف الدالة التي تستدعي نفسها بالريكيرشن.
وهي طريقة لتعريف الدوال حيث يتم تطبيق الدالة التي يتم تعريفها ضمن تعريفها الخاص ، فهي تقنية خوارزمية حيث تقوم الدالة من أجل إنجاز مهمة ، باستدعاء نفسها مع جزء من المهمة.
تعرض الدالة سلوكًا تكراريا و يمكن تعريفها بخاصيتين أو قاعدتين
1. حالة أساسية بسيطة (أو حالات)
2. مجموعة من القواعد التي تقلل جميع الحالات الأخرى تجاه الحالة الأساسية و تسمى الحالة التكرارية.
تتكون الحالة التكرارية من ثلاثة مكونات:
(أ)تقسّم المشكلة إلى جزء واحد أو أكثر أبسط أو أصغر من المشاكل ،
(ب) استدعاء الدالة (بشكل متكرر) على كل جزء ،
(ج) الجمع بين حلول والأجزاء في حل المشكلة.
مثال 1 : العامل " عملية رياضية لحساب عاملي عدد معين او كما تسمى بالانجليزية factorial
سنبدأ بمثال العامل ، والمشار إليه "!".
3! = 3* 2* 1
5! = 5* 4 *3 *2 *1
X! = X *(X − 1)* (X − 2)* (X − 3) *...* 3* 2* 1
0! = 1
فكيف نحسب ذلك !؟
هذه دالة تكرارية تقوم بذلك:
n!=n*(n − 1)! for n> 1, و n! = 1 for n ≤ 1. ie
• عامل (0) هو 1 [في الحالة الأساسية]
• عامل (1) هو 1 [في الحالة الأساسية]
نرمز بn لجميع الأعداد الصحيحة n> 1: * عاملي العدد (n ‐ 1) [تعريف متكرر]
ويتم تحويله لبرنامج جافا كما يلي
int factorial(int n)
{
if (n <= 1)
return 1;
else
return n * factorial(n‐1);
}
مثال 2: متتالية فيبوناتشي Fibonacci
 |
| ليوناردو فيبوناتشي - عالم رياضيات |
يمكن إنشاء تسلسل فيبوناتشي من خلال دالة تكرارية تشبه إلى حد بعيد وظيفة عامل التكرار.
الاختلاف الوحيد هو القاعدة التي تخص متوالية فيبوناتشي
is fib(n)= fib(n − 1) + fib(n − 2) for n> 1, and fib(n) = 1 for n > 1.
يظهر هذا النوع من التعريف التكراري "الركيرشن" بشكل متكرر في الرياضيات ، ويسمى أيضًا علاقة التكرار.
• فيبوناتشي (0) تساوي 0 [في الحالة الأساسية]
• فيبوناتشي (1) هي 1 [في الحالة الأساسية]
نرمز لجميع الأعداد الصحيحة n> 1
n> 1: Fib (n) is (Fib (n ‐ 1) + Fib (n ‐ 2)) [متكررتعريف]
ويتم تمثيله بلغة الجافا كما يلي :
int fib(int n)
{
if (n == 0)
return 0;
elseif (n == 1)
return 1;
else
return (fib(n‐1)+ fib(n‐2));
}
مثال 3: دالة القوى او الاسس
تعد دالة القوى أيضًا مثالًا على التكرار "recursion". قاعدة دالة القوة هي القوة (x, n) =
x * power(x , n‐1) for n> 0, and power(x , n ) = 1 for n = 0.
int power(double x, int n)
{
if (n == 0)
return 1;
else
return x * power(x,n‐1);
}
طرق الاستدعاء وتنفيذ التكرار "الركيرشن "
سجل التنشيط
يتكون مكدس الاستدعاء "stack" من إطارات مكدسة (تسمى أيضًا سجلات التنشيط أو إطارات التنشيط).
هذه هياكل بيانات تعتمد على الآلة تحتوي على معلومات حالة الروتين الفرعي.
يتوافق كل إطار مكدس مع استدعاء لإجراء فرعي لم ينته بعد ويقوم بالعودة.
إطار المكدس الموجود أعلى المكدس مخصص للإجراء العمليات المنفذه حاليًا.
يشتمل إطار المكدس عادةً على العناصر التالية على الأقل:
• رابط ديناميكي لسجل تنشيط المستدعيات
• عنوان المرسل إلى المستدعي الروتيني
• قيمة الإرجاع (إن وجدت)
مخطط الكتلة :
تفصيل استدعاء التكرار
• ضع في اعتبارك مثال العامل المستخدم سابقًا
int factorial(int n) {
if(n == 0) { return 1; }
else { return n * factorial(n‐1); }
}
فكر الآن في الكود التالي لـ دالة main ()
void main() {
int f = factorial(3);
System.out.print(f);
}
طريقة عمل استدعاء التكرار
تحليل التعقيد:
هو تحليل لحساب مقدار الوقت والمساحة التي ستستغرقها الخوارزمية / الدالة لإكمال العمليات من خلال حساب عدد العمليات الإجمالية.
يُشار إليه عادةً بـ Θ
دعنا نقول الدالة T (n) تشير إلى عدد العمليات الأولية التي يؤديها استدعاء الوظيفة Sum (n).
int Sum(n int) {
if n == 1 {
return 1
}
return n + Sum(n-1)
}
نحدد خاصيتين لـ T (n).
نظرًا لأن Sum (1) يتم حسابه باستخدام عدد ثابت من الدوال k1 ، T (1) = k1.
إذا كانت n> 1 ، فستؤدي الدالة عددًا ثابتًا من العمليات k2 ، وبالإضافة إلى ذلك ، ستقوم بإجراء استدعاء متكرر
لمجموع (n-1). سيؤدي هذا الاستدعاء المتكرر عمليات T (n-1).و في المجموع نحصل على T (n) = k2 + T (n-1).
إذا كنا نبحث فقط عن تقدير مقارب لتعقيد الوقت ، فلا نحتاج إلى تحديد القيم الفعلية للثابتين k1 و k2. بدلاً من ذلك ، ندع k1 = k2 = 1 لإيجاد التعقيد الزمني لدالة الجمع Sum ، يمكن بعد ذلك تقليلها إلى حل علاقة التكرار
T(1) = 1
T(n) = 1 + T(n-1), حيث n > 1.
من خلال تطبيق هذه العلاقات بشكل متكرر ، يمكننا حساب T (n) لأي رقم موجب n.
T(n) = 1 + T(n-1)
= 1 + (1 + T(n-2))
= 2 + T(n-2)
=2 + (1 + T(n-3))
= 3 + T(n-3) = …
=k + T(n-k) = …
= n - 1 + T(1)
= n - 1 + 1= Θ(n)
تكرار الذيل. او تيل ريكيرشن "TAIL RECURSION."
يتميز تكرار الذيل باستخدام استدعاء تكراري واحد فقط
في نهاية تنفيذ الدالة. الاستدعاء التكراري ليس فقط العبارة الأخيرة في الكود ، ولكن لا توجد فيه اسادعاءات تكراريه سابقة ، مباشرة أو غير مباشرة
مثال :
Example:
void tail (int i)
{
if (i>0)
{
System.ou t.p rintln(i);
tail(i‐1);
}
}
تكرار الذيل هو مجرد حلقة او لوب "loop" ويمكن استبداله بسهولة بمثل هذا الكود.
void IterativeEquivalentofTail(int i)
{
for ( ; i>0; i‐‐)
System.ou t.p rint(i);
}
* يمكن للمترجمات الذكية "compilers" اكتشاف تكرار الذيل وتحويله إلى تكراري لتحسين التعليمات البرمجية.
* يستخدم لتنفيذ الحلقات في اللغات التي لا تدعم هياكل الحلقة بشكل صريح. (مثل برولوج prolog).
* في اللغات المدعومة بحلقة أو ما يعادلها ، مثل إذا تم دمج العبارة مع تعليمة goto ، فإن تكرار الذيل ليس ميزة موصى بها.
عدم تكرار الذيل NON‐TAIL RECURSION.
تسمى الطرق التكرارية التي لا تكون متكررة الذيل non-tail recursion
هنا يجب أن تقوم الدالة بإجراء طباعة واستدعاء آخر بعد الدالة التكرارية الأولى ، وبالتالي فهي مثال على عدم تكرار الذيل
الإدخال: "ABC" ، يصف التغييرات في المكدس او stack وقت التشغيل أثناء تنفيذ العكس ()
ملاحظة - من الكاتب - : يصعب احيانا ترجمة بعض عمليات الخورزميات للعربية لعدم وجود مصطلحات عربية معتمدة في مجال علوم الحاسب بشكل عام لذلك اقوم بعرضها باللغتين لتصل الفكرة
تكمن مشكلة الخوارزمية غير الطرفية في أنها تستهلك الكثير من عمليات المكدس stack وليست فعالة
تحويل عدم تكرار الذيل إلى تكرار الذيل
يمكن تحويل طريقة التكرار غير الذيلية إلى طريقة تكرار الذيل عن طريق معلمة "مساعدة auxiliary" تُستخدم لتشكيل النتيجة.
يتم استخدام هذه التقنية عادةً مع دالة "مساعدة auxiliary".
وذلك ببساطة للحفاظ على بناء الجملة البرمجية بشكل نظيف وإخفاء حقيقة أن هناك حاجة إلى المعلمات المساعدة.
هل طريقةعامل العدد "factorial" هي طريقة الذيل التكراري ؟
int fact(int x){
if (x==0)
return 1;
else
return x*fact(x‐1);
}
عند العودة من استدعاء متكرر ، لا يزال هناك عملية واحدة معلقة ، وهي الضرب.
لذلك ، العامل يعتبر طريقة عدم تكرار الذيل "non‐tail recursive"
تحويل عدم تكرار الذيل إلى تكرار الذيل بالمثال البرمجي :
int fact_aux(int n, int result) {
if (n == 1)
return result;
return fact_aux(n ‐ 1, n * result)
}
int fact(n) {
return fact_aux(n, 1);
}
التكرار المفرط "Excessive Recursion"
عندما تكرر الطرق التكرارية في العمليات الحسابية لبعض المعلمات ،ينتج عن ذلك وقت حساب طويل حتى بالنسبة للحالات البسيطة.
وبذلك قد تكون هناك إمكانية لتكرار الحلول المحسوبة بالفعل.
على سبيل المثال: أرقام fibananci
باستخدام هذا المثال ، يمكننا بسهولة إظهار مدى عدم كفاءة الصيغة التكرارية، دعنا نحاول معرفة كيفية تقييم Fib (6).
هنا تم حساب fibananci للـ 4 مرتين ، 3 محسوبة 3 مرات ، 2 محسوبة 5 مرات ، 1 محسوبة 8 مرات و 0 محسوبة 5 مرات. هذا يعني أنه يتم حساب نفس الدالة مرات عديدة دون داع
التراجع BACKTRACKING
يتيح لنا التراجع تجربة جميع السبل المتاحة بشكل منهجي من نقطة معينة الى نقطة اخرى
باستخدام التراجع ، يمكننا دائمًا العودة إلى الموقف الذي يوفر إمكانيات أخرى لحل المشكلة بنجاح
ولناخذ على سبيل المثال مشكلة تحركات حجر الملكة في لعبة الشطرنج على طاولة تتيح مساحة تحرك 4*4
حيث يمكن تحريك كل حجر في اي من المسارات المجاورة عمودية او افقية شريطة الا يعترضها اي حجر اخر
مشكلة تحركات حجر الملكة في لعبة الشطرنج على طاولة تتيح مساحة تحرك 8*8
التهيئة
الملكة الأولى
الخ ...
مثال برمجي على خوارزمية التراجع
المرجع :
تعليقات
إرسال تعليق
شاركنا الآراء ،،