خوارزميات 1 PDF

# الجامعة الوطنية الخاصة ## كلية الهندسة ### قسم هندسة الحاسوب الاتصالات - **المقرر:** الخوارزميات وبنى المعطيات (1) - **المحاضرة:** الأولى - **Dr. Mohammed AL-Mohammed** ## Chapter 1: مقدمة ### في الخوارزميات وبنى المعطيات #### مبادئ أساسية ## الخوارزميات وبنى المعطيات ### تألف المادة من قسمي...

# الجامعة الوطنية الخاصة ## كلية الهندسة ### قسم هندسة الحاسوب الاتصالات - **المقرر:** الخوارزميات وبنى المعطيات (1) - **المحاضرة:** الأولى - **Dr. Mohammed AL-Mohammed** ## Chapter 1: مقدمة ### في الخوارزميات وبنى المعطيات #### مبادئ أساسية ## الخوارزميات وبنى المعطيات ### تألف المادة من قسمين: 1. **الخوارزميات** _Algorithms_: تتحدث عن طريقة صياغة البرنامج وكفاءته. 2. **بنى المعطيات** _Data structures_: سنتحدث ضمنها عن ما يسمى باللوائح وعن المكدسات والأرتال والجداول والأشجار ... ### تجريد الخوارزمية وفعاليتها _Algorithm Abstraction and Efficiency_ التجريد _abstraction_ هو عملية تعريف خواص محددة للغرض و من ثم استخدامها لتحديد غرض جديد يمثل تبسيطا للغرض الذي تم الإشتقاق منه. - من المستويات العليا للتجريد الحاسوبي بنى المعطيات _data structures_ و _algorithms_ الخوارزميات ### يطبق التجريد بناحيتين: الخوارزميات وبنى المعطيات ## Introduction - **An algorithm** is a set of steps of operations to solve a problem performing calculation, data processing, and automated reasoning tasks. An algorithm is an efficient method that can be expressed within finite amount of time and space. - **An algorithm** is the best way to represent the solution of a particular problem in a very simple and efficient way. - **If we have an algorithm** for a specific problem, then we can implement it in any programming language, meaning that the algorithm is independent from any programming languages. ## الخوارزميات _Algorithm_ ### الخوارزمية - هي سلسلة من الخطوات التعليمات) _instruction_ المنطقية والواضحة (غير مبهمة) أي لا تقبل التأويل والحصول بشكل صحيح على المخرجات المطلوبة من أي مدخلات (شرط أن تكون منطقية) وفي وقت محدد من أجل حل مشكلة ما. ### الخوارزمية _Algorithm_: - **تتابع محدد** من الخطوات التي تؤدي إلى حل مسألة معينة خلال مدة محدودة من الزمن. - **مستقلة** عن القيود المفروضة من البنية الحاسوبية - **هي طريقة حل** مجردة عن الآلة تُكتب بعدة لغات والمترجم يقوم بتحويلها للغة الآلة - **أو هي إجراء** يسمح بحل مشكلة معينة مهما كان الدخل وتقدم حلاً بعدد منته من الخطوات. ## خصائص الخوارزمية - **يجب أن تكون صحيحة**: ويجب أن تتضمن سلسلة من الخطوات المحددة. (عدة خطوات تمثل الحل الصحيح لمسألة ما وليس كل تسلسل واضح للخطوات هو حل صحيح). - **يجب أن لا يكون هناك أي غموض** في الخطوة التالية التي يجب أن تنفذ أي يجب أن تكون مرتبة ترتيب صحيح. - **يجب أن تتألف من عدد نهائي** من الخطوات. - **يجب أن تتوقف في النهاية**: (يجب أن تنتهي و تتوقف عند نقطة معينة). - **البرنامج الحاسوبي** هو إنجاز لخوارزمية محددة بلغة محددة أي البرنامج مستنسخ عن الخوارزمية. ## مثال: حل معادلة من الدرجة الثانية. ## القاسم المشترك الأكبر: هناك ثلاثة طرق لحساب القاسم المشترك الأكبر لعددين طبيعيين _(gcdm,n)_ : 1. **الطريقة المدرسية**: أولاً نحلله إلى عوامله الأولية ونأخذ العوامل المشتركة بأصغر أس. 2. **الطريقة التكرارية**: $gcd(m,n) ∈ {t, t − 1, t – 2, ..., 1}$ $T = min(m, n)-2$ $gcd(m, n) = gcd(n,m%n)$ $gcd(m, 0) = m$ 3. **الطريقة الإقليدية** ## تحليل فعالية الخوارزمية _Algorithm Analysis_ وهو اختيار من بين عدة خوارزميات تحل هذه المشكلة وهو يعنى بدراسة ومقارنة الخوارزميات وفعاليتها بشكل عام أي بشكل مستقل عن النظام الحاسوبي ومكوناته أو مستقلة عن تحديد ماهية المشكلة (بحالة عامة لأي مجال). ### المعايير أو الباراميترات التي سنعتمدها لمعرفة الفعالية (الأفضلية): _Efficiency_ 1. **المساحة التخزينية**: ينبغي أن تكون صغيرة. 2. **عدد الخطوات**: ينبغي أن يكون أقل من أجل تسهيل الكود. 3. **دقة النتائج**: ينبغي أن تكون أكبر. 4. **زمن التنفيذ**: ينبغي أن تكون أقل. 5. **الشمولية**: أي شمل كافة الحالات. 6. **التعميم**: نعممها لكل الحالات (أرقام، أحرف، عمليات منطقية ..... ### تقاس فاعلية الخوارزمية اعتماداً على مدى استهلاكها لكل من الزمن والذاكرة (السعة _Space_). - **فاعلية السعة _Space Efficiency_**: مقدار حجم الذاكرة التي تستخدمه الخوارزمية عند تنفيذها. - **فاعلية الزمن _Time Efficiency_**: المدة الزمنية التي تتطلبها الخوارزمية لإتمام عملها. ## _Data Structure_ بنى المعطيات إن أهم معيارين هما المساحة التخزينية وزمن التنفيذ وينبغي أن يستقل هذان الشرطان عن نوع الحاسب ولغة البرمجة أما باقي المعايير فلا نأخذها بعين الاعتبار (لا نحتاجها). إن دراسة المساحة التخزينية معيار مهم ولكننا سنهمله لصعوبة حسابه وسنركز على معيار واحد فقط هو زمن التنفيذ - إن الخوارزمية ذات الزمن الأقل هي الأكثر فعالية من بين الخوارزميات. - يجب عند قياس كفاءة خوارزمية معينة أن نزيل كافة عوامل التشويش لهذا القياس وأن نركز على الأفكار التي تؤثر فعلياً على زمن تنفيذ هذه الخوارزمية. ### هذه الأفكار هي: 1. **عدد البيانات** التي تعالجها الخوارزمية "حجم المسألة". 2. **عدد العمليات المنفذة** على هذه المعطيات فكل ما كان عدد العمليات المنفذة أقل كلما كانت الخوارزمية أفضل. لمعرفة الخوارزمية فيما إذا كانت فعالة أم لا يجب ايجاد علاقة بين عدد المعطيات الموجودة(ويرمز لها ب(n) وبين الوقت المستغرق في المعالجة. ## _Data Structure_ بنى المعطيات دائماً ما نجد أن الأشياء تمتاز بمجموعة صفات ، وهذه الصفات تعتبر الخصائص المميزة والمحددة للأشياء ، وتنتظم هذه الصفات طبيعياً بشكل بنائي منظم حيث يعبر الجد عن الجذر _"tree"_ فمثلاً أن أسماء أفراد العائلة تنتظم تحت بناء يشبه الشجرة فيها والأبناء عن الفروع وكذلك الأحفاد وهكذا . وكمثال آخر ينتظم الناس في طابور لشراء حاجة ما يعبر الواقف أولاً عن رأس الطابور والأخير عن ذيل الطابور ودليل التلفون وغيرها من الأمثلة كل هذه الأمثلة تبين لنا حقيقة واحدة ، هي أن المعلومات تمتاز بالترتيب أو التنظيم هذا الترتيب يعرف _"data structure"_ بالهيكل أو البنية فنقول هياكل أو بنى المعطيات إذاً تعريف بنية المعطيات هو تشكيل منظم لمجموعة من البيانات التي تشترك بصفة أو أكثر فيما بينها وذلك لتؤدي غرضاً محدداً حول شيء أو مجموعة أشياء محددة فمثلاً دليل التلفون يضم في كل صفحة من صفحاته عمودين أحدهما يدل على أسماء أشخاص معينين ، أو مؤسسات أو هيئات محددة والعمود الأخر يدل على أرقام الهواتف التي يملكها الأفراد أو المؤسسات أو الهيئات الموجودة في العمود الأول ## _Data Structure_ بنى المعطيات _Data Structure_: can be defined as the group of data elements which provides an efficient way of storing and organising data in the computer so that it can be used efficiently ## هياكل البيانات _Data structure_ - **هياكل بيانات ثابته** - **هياكل متغيره** - **الأبجديات _Alphabet_** - **المصفوفه _Array_** - **السجل _Record_** - **الجدول _Table_** - **هياكل بيانات خطيه** - **هياكل بيانات غير خطيه** - **الملفات _Files_** - **المكدسة _Stack_** - **الصف _Queue_** - **الشجره _Tree_** - **المخطط _Graph_** ## بنى المعطيات _Data structure_ - **Primitive Data Structure** - **Non-Primitive Data Structure** - **Linear** - **Static** - **Array** - **Dynamic** - **Linked List** - **Stack** - **Queue** - **Non Linear** - **Tree** - **Graph** ## بنى المعطيات _Data structure_ هي نوع من المعطيات مؤلفة من معطيات أبسط منها ، وبنى المعطيات تمثل تجريد لأنواع معطيات تؤمنها لغة برمجة معينة. ### أنواع المعطيات _Data Types_ - **بسيطة**: _int, float, double char_ - **مركبة**: _arrays, strings, records_ 1. **معطيات بسيطة**: لا يمكن تحليلها إلى أبسط منها مثل _integer_ فهو وحدة قائمة بذاتها لا يمكن تحليله إلى أبسط من ذلك وكذلك ال_float_ و ال_character_ ... إلخ. 2. **معطيات مهيكلة**: تسمح بتحليلها لمعطيات أبسط منها مثل المصفوفة التي تتألف من أكثر من عنصر. ### ملاحظة: يستطيع المبرمج تعريف أنواع معطيات جديد غير موجودة بلغة البرمجة. ## _The need for Data structures_ سبب الحاجة لبنى المعطيات 1. **تقوم بنى المعطيات بتنظيم** المعطيات ضمن ذاكرة الحاسوب فهذا يعطى برامج أكثر كفاءة. 2. **الحواسيب ذات الكفاءة العالية** تمكننا من صياغة تعليمات أعقد ضمنها. 3. **كل ما كانت التطبيقات معقدة أكثر** فإن هذا يستلزم حسابات أعقد. حيث أن تلك البرامج المعقدة تحتاج عدد أكبر من العمليات الحاسوبية. 4. **إن أي تنظيم لمجموعة من المعلومات يمكن البحث** ضمنه, معالجة محتواه بأي ترتيب, و تعديل ذاك المحتوى بسهولة. 5. **إن اختيار بنية المعطيات و خوارزمية البرمجة بشكل مناسب** قد يحدد الفرق بين برنامج ينهي عمله خلال عدة ثواني و آخر يحتاج عدة أيام. ## _Data structures philosophy_ فلسفة بنى المعطيات كل بنية معطيات لها تكلفة وفائدة وبنى المعطيات تحتاج لما يلي: - **مكان تخزين** في الذاكرة. - **زمن لتنفيذ** كل تعليمة من التعليمات. - **جهود برمجية.** ### ملاحظة: كل مسألة من المسائل لها قيود وشروط فيما يتعلق بحجم الذاكرة المطلوب وسرعة التنفيذ. أي عندما تكون المسألة بسيطة فإن ذاكرة الحاسوب ستكون بالنسبة لمستلزمات هذه المسألة واسعة وكافية أما إذا كانت المسألة معقدة فإن ذاكرة الحاسوب ستكون محدودة. ## _Data Structure_ بنى المعطيات - **تنظم المعطيات** ضمن الذاكرة. - **مع الملاحظة أن اختيار البنية المناسبة للمعلومات** يمكن أن يسبب اختلاف في زمن التنفيذ وفعاليته حيث يمكن أن تحل مسألة معينة بطريقتين كل منها بنمط معطيات معين تكون الأكثر فعالة ذات زمن التنفيذ الأقل. ### كل بنية معطيات لها كلفة: 1. **زمن التنفيذ.** 2. **حجم التخزين.** 3. **جهدين كبير أو صغير** للمعالجة والاستخدام. ### ملاحظات: - **لا يوجد بنية مناسبة لكل التطبيقات** حيث لكل تطبيق بنية مناسبة له. - **مثلا المصفوفة** يحدد حجمها و يتم حجزه في حال استخدامناه أو لا، أما اللائحة فهي تحجز ما تستخدمه فقط. - **كل مسألة لها شروط و قيود** في التعامل معها مثل حجم الذاكرة و التنفيذ. ## _Abstract Data Type - ADT_ نوع المعطيات المجرد يستخدم لتعريف بنية معطيات تتطلب بالإضافة الى تحديد بنى القيم لهذا النوع الجديد تحديد كامل مجموعة العمليات _methods or functions_ التي يمكن إجراءها على المكونات البيانية - اي الاغراض - لهذا النوع. إن بنية المعطيات هي التوظيف الفيزيائي لنوع المعطيات المجرد. يشير مصطلح بنية المعطيات لتنظيم البيانات بشكل محدد ضمن ذاكرة الوصول العشوائي. بينما يشير مصطلح بنية الملفات لتنظيم تلك البيانات ضمن وسائط التخزين الطرفية كالقرص الصلب. إن كل عملية مقرونة بنوع المعطيات المجرد يتم توظيفها من قبل واحد او اكثر من الروتينات الفرعية لها ) أي المشتقات من ذاك النوع ). ## _Run Time_ زمن التنفيذ: (حقيقي) تعريف زمن تنفيذ الخوارزمية: هو عدد العمليات الأولية التي تنجزها الخوارزمية حتى الحصول على النتائج (جمع – طرح – باقي قسمة – استدعاء دالة) وهنا عمليات من مستوى عالي "منطقية" عدد العمليات الأقل يعطي خوارزمية أفضل. ### لنقارن بين خوارزميتين كما يأتي: - A و B - $T_A(n) < T_B(n)$ إن الخوارزمية B هي الأفضل ... أولاً زمن التنفيذ يتوقف على مكونات الحاسب الأساسي ويتوقف على مجال وبنية وحجم المدخلات وبالتالي: إن استخدام مقياس لقياس الزمن الحقيقي لتنفيذ الخوارزمية كباراميتر مقارنة غير دقيق وغير موثوق. لذلك سندرس زمن التنفيذ نظرياً بشكل مستقل عن طبيعة الحاسوب ومكوناته أو طبيعة المدخلات. ## _growth of functions_ تزايد التوابع عندما يكون حجم المعطيات " كبير يكون من غير المهم أن نعرف هل تحتاج خوارزمية ما إلى " أم إلى 5 n عملية أساسية، ويمكن في معظم الأحيان إهمال الثوابت الضربية. فمثلاً عندما نريد مقارنة الخوارزمية A التي عدد عملياتها الأساسية 12 مع الخوارزمية B التي عدد عملياتها الأساسية 47 فإن الخوارزمية B أفضل من 4 من أجل جميع قيم " التي هي أكبر من 4. تؤول التقريبات السابقة إلى إيجاد ما يسمى مرتبة كبر تابع، وتجري مقارنة الخوارزميات على أساس مرتبةِ الكبر لتوابع التعقيد الزمني ( عدد العمليات الأساسية من أجل مقارنة الخوارزميات في حالة حجوم معطيات كبيرة، لابد إذا من استخدام بعض التعاريف الرياضية الأساسية. ## _Big-oh Notation_ تدوين Big-oh ### تعريف: ليكن لدينا التابعان f و g والمعرفان على كافة القيم الموجبة الصحيحة أو الحقيقية. نقول عن التابع / إنه مُسيطر عليه تقاربياً من قبل التابع g وترمز إلى ذلك بـ (( f ( x ) = ( x إذا وجد ثابتان C و k بحيث x > k من أجل كل |f(x)|C|g(x(| . ### ملاحظة: من التعريف السابق (( f ( x ) = ( x يمكن القول أن التابع ( f ( x يتزايد بشكل أبطأ من التابع ( g ( x . ## _Big-oh Notation_ تدوين Big-oh تعبر عن تابع نمو خوارزمية ما لعدد محدود من المعالجة ليكن لدينا (f (n تابع معرف على القيم الموجبة لـ N. (T (n: عدد العمليات اللازمة لتنفيذ خوارزمية حجمها . ### c: ثابت الربط بين (f (n و (n). + ### العلاقة بين التابعين هي: (n) ≤ (n) ### من أجل قيم n = no وبزمن تنفيذ أقل من (n). من أجل جميع البيانات التي يتم معالجتها والتي هي كبيرة بما فيه الكفاية أي n × no الخوارزمية دائماً تنفذ في زمن مقداره أصغر من (cf (n أي أن ( n) ( f) يشير Big – oh Notation إلى الحد الأعلى لزمن التنفيذ أو إلى الحد الأعلى لعدد التعليمات اللازمة لمعالجة n حد. نقول عن الخوارزمية أن لها نمو من المرتبة ( ( f ) ## مثال: بين أن f (x) = x² + 2x + 1 = 0 (x2( ### الحل: - من أجل x < 1 لدينا > x2 و x < x2 : بالتالي x² + 2x + 1 ≤ x² + 2x2 + x2 = 4x2 :1 بالتالي 0≥x² + 2x + 1≤x² + 2x2 + x2 = 4x2 :1 بالتالي - )k = 1 و C = 4) f (x) = 0 (x2( بالتالي - ومن أجل x < 2 لدينا ≥x2 2 وx2 x2 بالتالي 0، بالتاليx2 + 2x + 1≤x² + 2x2 + x2 = 3x2 - )k = 2 و C = 3) f (x) = (x2( أيضاً ## _Big-oh Notation_ تدوين Big-oh - T(n) = n² + 2n - T(n) ≤ cf(n) - n² + 2n ≤ n² + n² - n² + 2n ≤ 2n² - 2n ≤ 2n² – п² ### 2n ≤ n² → 0(n²) - n = 2 - 2 × 2 = 22 - 4= 4 ### لنعرف n الحدية : - **المتراجحة صحيحة** - n = 3 - 2×3<9 - **المتراجحة صحيحة** 9 - 6 - وبالتالي فإن المتراجحة صحيحة لجميع قيم 2 2 n. ## مثال 2 : - T(n) = 3n² ≤ 3n² - T(n) ≤ c f(n) ### فإن الثابت ، هو 3 - ولدينا f (n) = n2 حيث أن 1 = n - ⇒ 0(n²) ## مثال 1: - T(n) = n² n - ² + 6n - n² + 6n ≤ 2n² - 6n ≤ n² → 0(n²) - نلاحظ أن المتراجحة صحيحة من 6 = n الحدية - 36 = 36 - فالمتراجحة صحيحة طالما 6 < . ## مثال 3 : ## أمثلة: ### مثال 1: for (k = 0; k<n/2; k++) { for (j=0;j<n*n; j++) { } } - n/2 * n² = n³/2 → O(N³) ### مثال 2: for (k = 0; k<n/2; k++) { } for (j=0;j<n*n; j++) { } - n/2 + n² → O(N2) ### مثال 3: k = n while (k > 1) { k-k/2 } - O(log2 N) ### (عدد المرات التي يمكن تقسيم k على 2 حتى تصل قيمتها إلى (1) مثال : راجع الشريحة التالية ## _Big-oh Notation_ تدوين Big-oh - **نَقْصِيَّة** _Big-O Notation_ - **تعبر عن تابع نمو** خوارزمية ما لعدد محدود من المعالجة ليكن لدينا - (f (n تابع معرف على القيم الموجبة لـ N. - (T (n: عدد العمليات اللازمة لتنفيذ خوارزمية حجمها . ### c: ثابت الربط بين (f (n و (n). - + > **العلاقة بين التابعين هي: (n) ≤ (n)** ### من أجل قيم n = no وبزمن تنفيذ أقل من (n). ### من أجل جميع البيانات التي يتم معالجتها والتي هي كبيرة بما فيه الكفاية أي n × no الخوارزمية دائماً تنفذ في زمن مقداره أصغر من (cf (n أي أن ( n) ( f) يشير Big – oh Notation إلى الحد الأعلى لزمن التنفيذ أو إلى الحد الأعلى لعدد التعليمات اللازمة لمعالجة n حد. **نقول عن الخوارزمية أن لها نمو من المرتبة ( ( f )** ## أمثلة: ### مثال 1: for(int i=0; i<n; i++) { } - n → O(N) ### مثال 2 (حلقتا for متداخلتان): for(int i=0; i<n; i++) { for(int k=0;k<n; k++) { } } - n* n = n² → O(N2) ### مثال 3 (حلقتا for متتاليتان): for(int i=0; i<n; i++) { } for(int k=0;k<n;k++) { } - n + n = 2n → 0(N) ### مثال 4: for(int i=-0;i<n/2;i++) { for(int k=0;k<n*n;k++) { } } - n - n*n²=O(N³) ### مثال 5 : void main() { int m=1,p=3,1=5; for(int i=1;i<=n;i++) { m=m+1; p=p*2; 1=1+3; } } - Σ3*1 - Σ3 - 3n = O(n) ### مثال 6 : void main() { int m=1, p=3, 1=5; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { m=m+1; p=p*2; 1=1+3; } } - ΣΣ - ΣΣ - 3n2 = 0(n2) ### مثال 7 : void main() { int m=1, p=3, 1=5; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) { m=m+1; p=p*2; 1=1+3; } } - ΣΣ - ΣΣ - 3n(n + 1) - 0(n²) ### مثال 8 : int var; for(int i=0;i<n;i++) { If(var%2==0){ for(int j=0;j<n;j++) { } else var=var-7; } ### هنا لدينا حالتين على حسب قيمة var المدخلة: - **الحالة الأولى** أن var عدد فردي و بالتالي لا يدخل على حلقة if الأولى. )( :أي - **الحالة الثانية** أن var عدد زوجي و بالتالي يدخل على حلقة if الأولى. )2( أي ### لكن في هذه الحالة نختار دائماً الحالة الأسوأ للمقارنة )2( أي ## تطبيق: حساب الزمن الخوارزمية حسب القيمة المتوسطة 1.Read n 1 2.Sum = 0 1 3.i= 1 1 4.While i<= n do n+1 T(n) = 4n + 5 A.Read Number n B.Sum = Sum + Number n C.i= i+ 1 n 5.Calculate Mean = Sum / n 1 ## حساب الزمن الخوارزمية حسب القيمة المتوسطة ### T(n) = 4n + 5 - **علاقة زمن التنفيذ هي تابع** خطي لعدد العناصر n - **نقول زمن تنفيذ الخوارزمية (T(n** تابع من مرتبة n - **ونعبر عنه (n) = (n** ## تمرينات ### تمرين 1 1- **استنتج العبارة الرياضية** التي تعطي زمن تنفيذ مقطع البرنامج المعطى جانباً بدلالة العمليات المنفذة من أجل عدد الحدود n. 2- **احسب حجم تنفيذ مقطع البرنامج المعطى** اذا كان حجم المسألة 1000 = n و زمن تنفيذ التعليمة الواحدة u sec أي 1 ميكرو ثانية. 3- **استنتج تابع نمو مقطع البرنامج المعطى** حسب تدوین Big-o و أوجد no و co. ## تمرين 2 أوجد تابع نمو الخوارزمية الممثلة بهذا التابع حسب تدوين Big-O-Notation. void function(int a[], int n) { int j=0; bool done; for(int k=1;k<n;k++) { j=k; done=false; while(j>=1 && !done) if (a[j]<a[j-1]){ swap(a,j,j-1); j--; } else done=true; } } ## تدريبات - 1- كم سيصبح زمن تعقيد الخوارزمية ذات تعقيد أسي (10) 0 عندما تعمل على مسألة بحجم 1000 عنصر؟ علماً بأنها تأخذ 10 ميلي ثانية عندما تعمل على مسألة بحجم 10 عناصر. - 2- أوجد تعقيد الخوارزمية التالية. for(k=0;k<n/2; k++) { for(j=0; j<n*n ; j++) } - 3- ابحث في كل ممايلي : - **Savitch's Theorem:** نظرية سافيتش - **صفوف التعقيد Complexity Classes والعلاقة بينها** - **نهاية المحاضرة**