11- الخوارزميات وبنى المعطيات – القائمة المتصلة الدائرية Algorithms and Data Structure – Circular Linked List

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Circular Linked List
الخوارزميات وبنى المعطيات –  القائمة المتصلة الدائرية

القائمة المرتبطة دائريا circular linked list: عبارة عن نسخة معدلة من القائمة المتصلة linked list بحيث يشير الأول الى العنصر الاخير, وكذلك يشير العنصر الاخير الى العنصر الاول.

يمكن لكلا النوعين: “القائمة المتصلة المفردة singly lined list والقائمة المتصلة مزدوجة الارتباط doubly linked list ان تكونا دائريتان بحسب الوصف السابق.

 

القائمة المتصلة  – الدائرية Singly linked list as circular

في القائمة المتصلة احادية الاتجاه, يجب ان يشير المؤشر التالي للعنصر الاخير next pointer of last item الى اول عنصر – عقدة ضمن القائمة.

singly_circular_linked_list.jpg

القائمة المزدوجة الارتباط الدائرية doubly linked list as circular

يجب ان يشير رابط التالي next link للعنصر الاخير الى العنصر الاول في القائمة, وان يشير رابط السابق prev link للعنصر الاول الى اخر عنصر ضمن القائمة.

doubly_circular_linked_list.jpg

وبذلك نحصل على قائمة متصلة دائرية يمكن التجوال فيها باتجاهين

من الاشكال السابقة, نلاحظ بأن هنالك عدة نقاط مهمة يجب التنويه اليها:

في كلا نوعي القوائم المتصلة – المفردة والمزدوجة: نجد بأن رابط التالي next  للعقدة الاخيرة في القائمة يشير الى العنصر الاول في القائمة.

اما في القائمة مزدوجة الارتباط فإن رابط السابق prev link للعنصر الاول يؤشر الى العنصر الاخير ضمن السلسلة

العمليات الاساسية

فيما يلي عدد من العمليات الاساسية المهمة المدعومة ضمن القوائم المتصلة الدائرية:

  • الاضافة insert : اضافة عنصر عند بداية القائمة.
  • الحذف delete: حذف عنصر من بداية القائمة list .
  • العرض display : عرض عناصر القائمة list .

عملية الاضافة insertion operation

الكود التالي يوضح عملية الاضافة الى بداية القائمة المتصلة الدائرية الاحادية

مثال

insert operation.JPG

عملية الحذف deletion operation

الكود التالي يمثل عملية حذف العنصر الاول من قائمة متصلة احادية الاتجاهsingle linked list

delete operation.JPG

عملية عرض القائمة display list operation

الكود التالي يمثل عملية عرض عناصر قائمة متصلة احادية الاتجاهsingle linked list

display op.JPG

وبهذا ننهي حديثنا عن القوائم المتصلة, لننتقل للحديث عن موضوع شيق الا وهو بنية المطيات المكدس Stack data structure

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
قائمة متصلة Linked list
عملية Operation
عقدة Node
رابط Link
زمن التنفيذ Running time/execution time
البحث عن المعطيات Data search
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
https://www.tutorialspoint.com/data_structures_algorithms/

 

 

 

Advertisements

, , , , , , , , , , , , ,

أضف تعليق

10- الخوارزميات وبنى المعطيات – القائمة المتصلة مزدوجة الارتباط Algorithms and Data Structure – Linked List

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Doubly Linked List
الخوارزميات وبنى المعطيات –  القائمة المتصلة المزدوجة الارتباط

القائمة المتصلة المزدوجة الارتباط: عبارة عن نسخة معدلة من القائمة المزودجة, بحيث تمكن التجوال باتجاهين – للامام والخلف – بسهولة التجوال المتواجد ضمن القائمة المتصلة linked list .

فيما يلي قائمة بالمصطلحات المهمة فيما يتعلق بالقائمة المتصلة المزدوجة الارتباط Doubly Linked List:

  • الرابط Link: يمكن لكل رابط – من روابط القائمة المتصلة – ان يخزن المعطيات, وتدعى هذه المعطيات باسم العنصر element.
  • التالي Next: يحوي كل رابط Link ضمن القائمة المتصلة على رابط للعنصر التالي مباشرة, ويدعى هذا الرابط باسم التالي Next.
  • التالي Prev: يحوي كل رابط Link ضمن القائمة المتصلة على رابط للعنصر السابق مباشرة, ويدعى هذا الرابط باسم التالي Prev.

 

تمثيل القائمة المتصلة المزدوجة الارتباط doubly linked list representation

doubly_linked_list

فيما يلي بعض النقاط الهامة التي يجدر الانتباه اليها في القائمة المتصلة المزدوجة الارتباطdoubly linked list :

  • تحوي على رابط يدعلى الرابط الاول first link, وعلى رابط يدعى الرابط الاخير last link.
  • كل رابط Link يحوي على حقل معطيات – او عدة حقول – وعلى حقلين خاصين بالروابط links يدعيان التالي next والسابق Prev.
  • يحوي العنصر الاخير على رابط next يشير الى القيمة Null معلنا بذلك نهاية القائمة.

العمليات الأساسية:

فيما يلي قائمة بالعمليات الاساسية المدعومة ضمن القائمة المتصلة:

  • الاضافة insertion : اضافة عنصر الى بداية القائمة المتصلة
  • الحذف deletion: حذف عنصر من بداية القائمة المتصلة
  • الاضافة للاخير insert last: اضافة عنصر الى اخر القائمة المتصلة
  • حذف العنصر الاخير delete last: حذف عنصر من نهاية السلسلة.
  • الاضافة بعد عنصر insert after: اضافة عنصر بعد عنصر محدد من القائمة>
  • الحذف delete : حذف عنصر من القائمة باستخدام مفتاح محددkey .
  • العرض قدما Display forward: عرض كامل السلسلة من البداية للنهاية
  • العرض بشكل تراجعي display backward: عرض كامل محتويات السلسلة بشكل تراجعي من النهاية للبداية.

 

عملية الاضافة Insertion Operation

الكود التالي يبين عملية اضافة عنصر الى بداية القائمة المتصلة المزدوجة الارتباط doubly linked list

مثال:

insert begining 1.JPG

عملية الحذف Deletion Operation

الكود التالي يمثل عملية الحذف لعنصر من بداية القائمة المتصلة المزدوجة الارتباط

مثال:

delete example.JPG

الاضافة الى نهاية السلسلة Insertion at the End of an doubly linked list

الكود ادناه يمثل عملية اضافة عنصر الى نهاية قائمة متصلة مزدوجة.

insert at the end of the list.JPG

وبهذا القدر ننتهي من الحديث عن القائمة المتصلة المزدوجة الارتباط

كتمرين, بامانكم كتابة خوارزمية تنفيذ بقية العمليات على هذا النوع من القوائم

نلتقي في الدرس القادم للحديث عن القوائم المتصلة الدائرية

circular linked list

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
قائمة متصلة Linked list
عملية Operation
عقدة Node
رابط Link
زمن التنفيذ Running time/execution time
البحث عن المعطيات Data search
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
https://www.tutorialspoint.com/data_structures_algorithms/index.htm

 

 

 

, , , , , , , , , , , , ,

أضف تعليق

9- الخوارزميات وبنى المعطيات – القائمة المتصلةAlgorithms and Data Structure – Linked List

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Linked List
الخوارزميات وبنى المعطيات –  القائمة المتصلة

 

ننتقل اليوم بالحديث الى نوع اخر من بنى المعطيات, الا وهو القائمة المتصلة linked list
وسنستمر ضمن الحلقتين القادمتين بالحديث عن الانواع المختلفة من هذه القوائم.

القائمة المتصلة: عبارة عن تتالي لبنى معطيات data structure, التي يتم ربطها مع بعضها البعض عبر مايعرف باسم الروابط Links.

يمكننا القول بأن القائمة المتصلة عبارة عن سلسلة من الروابط Links التي تحوي عناصر items.
كل رابط Link يحوي ايضا وصلة الى رابط اخر another link.
تعتبر القائمة المتصلة ثاني اكثر بنية معطيات مستخدمة بعد المصفوفات.
فيما يلي بعض اهم المصطلحات المستخدمة فيما يتعلق بمفهوم القائمة المتصلة Linked List

  • الرابط Link: يمكن لكل رابط – من روابط القائمة المتصلة – ان يخزن المعطيات, وتدعى هذه المعطيات باسم العنصر element.
  • التالي Next: يحوي كل رابط Link ضمن القائمة المتصلة على رابط للعنصر التالي مباشرة, ويدعى هذا الرابط باسم التالي Next.
  • القائمة المتصلةLinkedList : تحوي القائمة المتصلة مايعرف برابط البداية الذي يشير الى اول رابط ضمن القائمة. ويعرف هذا الرابط باسم “الاول”First .

ملاحظة:
من المهم جدا حفظ هذه المصطلحات كما هي باللغة الانكليزية بالاضافة لفهمها باللغة العربية.

تمثيل القائمة المتصلة Linked List Representation

يمكن تمثيل القائمة المتصلة على شكل سلسلة من العقد nodes, حيث تشير كل عقدة node الى العقدة التالية.

linked_list

هنالك بعض النقاط الهامة التي يجدر الانتباه اليها في الشكل السابق:

  • تحوي القائمة المتصلة linked list على عنصر رابط يدعى بالاول “first”
  • يوجد مع كل رابط link حقل معطيات ( او مجموعة حقول), بالاضافة الى رابط للعنصر التالي Next link.
  • يحوي الرابط الاخير last link على رابط يشير الى القيمة null, ليدل بذلك على نهاية القائمة.

انواع القائمة المتصلة Types of Linked List

هنالك عدة انواع من القوائم المتصلة:

  • القائمة المتصلة البسيطة Simple Linked List: بالامكان التجوال داخل هذه القائمة باتجاه واحد
  • القائمة المتصلة على نحو مضاعف double linked list: ويمكن التجوال ضمن هذه القائمة باتجاهين : الامام والخلف
  • القائمة المتصلة الدائرية Circular Linked List: العنصر الاخير يحوي على رابط للعنصر الاول من هذه القائمة, وكذلك يحوي العنصر الاول على رابط يشير الى اخر عنصر من القائمة next link.

العمليات الأساسية:

فيما يلي قائمة بالعمليات الاساسية المدعومة ضمن القائمة المتصلة:

  • الاضافة insertion : اضافة عنصر الى بداية القائمة المتصلة
  • الحذف deletion: حذف عنصر من بداية القائمة المتصلة
  • العرض display: عرض كافة محتويات القائمة المتصلة.
  • البحث search: البحث عن عنصر باستخدام مفتاح معين key ضمن القائمة المتصلة

عملية الاضافة Insertion operation

إن عملية إضافة عقدةnode  جديدة في القائمة المتصلة linked list لا تتم عبر خطوة واحدة. سوف نتعلم هذا مع الرسوم البيانية هنا. أولاً ، قم بإنشاء عقدةnode  باستخدام نفس البنية , ثم ابحث عن الموقع الذي يجب إدراجه فيه.

linked_list_insertion_0

تخيل بأننا نقوم باضافة عقدة جديدة باسم B newNode, وذلك بين العقدة A LeftNode ,العقدة C rightNode. ومن ثم نجعل B.next يؤشر على C

insert node 2

linked_list_insertion_1.jpg

الآن, يجب ان توشر القعدة الموجودة على اليسار الى العقدة الجديدة

insert node 3

linked_list_insertion_2

وبهذا تكون قد توضعت العقدة الجديدة بين العقدتين. ويكون الشكل النهائي للقائمة المتصلة كالتالي:

يجب اتخاذ خطوات مشابهه في اضافة العقدة الى بداية القائمة. اما بالنسبة للاضافة الى نهاية القائمة, عندها يجب ان يؤشر رابط التالي next link للعقدة الاخيرة الى العقدة الجديدة, بينما يكون مؤشر رابط التالي next link للعقدة الجديدة يؤشر الى القيمة null كدلالة على نهاية السلسلة.

linked_list_insertion_3.jpg

عملية الحذف Deletion Operation

عملية البحث ايضا لا تتم بخطوة واحدة, كما سنوضح بالصور.

اولا, يجب ايجاد العقدة الهدف – المطلوب ازالتها -, وذلك باستخدام احد خوارزميات البحث.

linked_list_deletion_0.jpg

يجب ان تؤشر العقدة السابقة للعقدة الهدف, على نفس العنصر الذي تؤشر عليه العقدة الهدف كعنصر تالي:

delete 1.JPG

linked_list_deletion_1.jpg

والان نزيل الرابط الذي كان يؤشر على العقدة الهدف. وكذلك نزيل الرابط الذي تؤشر عليه العقدة الهدف كعنصر تالي:

delete 2

linked_list_deletion_2

في حال لم نكن بحاجة الى استخدام العقدة المحذوفة, عندها يجب ازالتها من الذاكرة deallocate – ازالة حجزها من الذاكرة – وبذلك تنتهي هذه العقدة للابد.

linked_list_deletion_3.jpg

عملية العكس Reverse Operation

وتهدف هذه العملية الى عكس اتجاه السير ضمن القائمة المتصلة, بحيث يؤشر رابط نهاية السلسلة الى العنصر قبل الاخير فيها, ويتحول العنصر الاخير الى العنصر الاول, وهكذا

linked_list_reverse_0.jpg

في البداية ننتقل – عبر التجوال ضمن القائمة المتصلة – الى اخر عنصر ضمن القائمة المتصلة. والذي يؤشر مؤشر Next ضمنه الى القيمة null. والآن, يجب ان ندعه يؤشر الى العنصر قبل الاخير ضمن القائمة المتصلة.

linked_list_reverse_1.jpg

يجب ان نتاكد من عدم فقدان العقدة الاخيرة. لذلك سنلجأ الى بعض العقد المؤقته, والتي ستبدو مشاببه للعقدة الرئيسية head node, وتشير الى العقدة الاخيرة last node
يجب علينا الآن جعل كل الروابط التي تشير الى العنصر التالي في القائمة المتصلة, تشير للعنصر السابق previous .

linked_list_reverse_1.jpg

باستثناء العقدة الاولى التي يجب ان تؤشر الى القيمة null.

linked_list_reverse_2.jpg

الآن, يجب ان نجعل عقدة الرأس head node تشير الى اول عقدة وذلك بالاستفادة من العقدة المؤقته

linked_list_reverse_4.jpg

تم عكس القائمة المتصلة الان.

فيما يلي كود عملية العكس باستخدام لغة C

implementation in c

عملية عكس القائمة المتصلة باستخدام لغة سي

العملية ليست بهذا الوضوع وتحتاج الى خيال, وتجريب رسم السلسلة على الورق وفهم العملية بشكل جيد عبر تطبيق الخطوات.

والى لقاء في درس جديد نتحدث فيه عن القائمة المتصلة المضاعفة double linked list

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
قائمة متصلة Linked list
عملية Operation
عقدة Node
رابط Link
زمن التنفيذ Running time/execution time
البحث عن المعطيات Data search
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
http://www.baeldung.com/java-hill-climbing-algorithm

 

 

 

, , , , , , , , , , ,

أضف تعليق

8- الخوارزميات وبنى المعطيات – المصفوفات Algorithms and Data Structure – Arrays

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Arrays
الخوارزميات وبنى المعطيات –  المصفوفات

سنتحدث اليوم عن احد اشهر بنى المعطيات, الا وهي المصفوفات Arrays
المصفوفة Array: وهي عبارة عن مستوعب – حاوية – تستطيع ان تحوي ضمنها عدد محدد من العناصر , ويجب ان تكون هذه العناصر من نفس نمط المعطيات.

معظم بنى المعطيات تستفيد من المصفوفات arrays بهدف تطبيق خوارزمياتها.

ملاحظة:
يمكن استخدام اي لغة برمجة من اجل تطبيق الامثلة الواردة ضمن الدروس, ويفضل التطبيق العملي

فيما يلي احد اهم المصطلحات التي يجب فهمها من اجل استيعاب مفهوم المصفوفة Array.

  • العنصر Element: كل عنصر يتم تخزينه ضمن المصفوفة يدعى ب “element”
  • الدليل Index: يشار الى موقع كل عنصر ضمن المصفوفة بواسطة دليل – فهرس – وهو عبارة عن دليل رقمي numerical index, ويستخدم لتحديد موقع العنصر ضمن المصفوفة.

 

تمثيل المصفوفة Array Representation

يمكن تعريف المصفوفة بواسطة اساليب مختلفة وذلك بحسب لغة البرمجة المستخدمة.

للتوضيح, سوف نستخدم لغة البرمجة C للتصريح عن مصفوفة

2- array_representation

1- array_declaration

واستنادا الى الصورة التوضيحية اعلاه, سوف ندرج بعض النقاط المهمة فيمايلي:

  • يبدأ دليل المصفوفة من الصفر Index starts with 0
  • طول المصفوفة 10, بالتالي يمكن تخزين فقط عشر عناصر ضمن المصفوفة
  • يمكن الوصول الى كل عنصر عبر الدليل index, على سبيل المثال نحتاج الى الدليل رقم 6 للوصول الى العنصر ذوق القيمة 27.

 

العمليات الاساسية Basic Operations

فيما يلي قائمة بالعمليات operations التي تدعمها بنية المعطيات “مصفوفة array”

  • التجوال Traverse: طباعة كل عناصر المصفوفة واحدا تلو الاخر
  • الاضافة insertion : اضافة عنصر عند دليل محدد index .
  • الحذف :Deletion حذف عنصر عند دليل محدد.
  • البحث : البحث عن عنصر باستخدام دليل العنصر index او قيمة العنصر value
  • التعديل update: تعديل قيمة عنصر ما.

 

بالنسبة للغة البرمجة C – على سبيل المثال – عند يتم تحديد حجم مصفوفة array size, عندها يتم تهيئة المصفوفة بشكل افتراضي بالقيم المناسبة بحسب نوع عناصر المصفوفة – كما هو موضح بالجدول التالي

C init array.JPG

عملية الاضافة Insertion Operation

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

الخوارزمية:

لنفترض بأنه لدينا المصفوفة LA, ومؤلفة من N عنصر

وk يمثل عدد صحيح واقع ضمن المجال K<=N.

فيما يلي الخوارزمية التي تبين اضافة العناصر ضمن الموقع K من المصفوفة LA
insert array.JPG

مثال:

فيما يلي مثال على تطبيق الخوارزمية السابقة

algorithm.JPG

تنفيذ البرنامج يعطي الخرج التالي:

algorithm output

عملية الحذف Deletion Operation

تشير عملية الحذف الى ازالة عنصر موجود من المصفوفة واعادة تنظيم كل العناصر في المصفوفة

الخوارزمية

لنفترض بأن AL عبارة عن مصفوفة مؤلفة من N عنصر, ويمثل K عدد صحيح موجب بحيث ان K<=N

فيما يلي خوارزمية تمثل عملية حذف العنصر الموجود في الموقع K من المصفوفة LA.

delete algorithm.JPG

مثال:

المثال التالي عبارة عن تطبيق للخوارزمية السابقة

delete example.JPG

عند تنفيذ المثال السابق نحصل على الخرج التالي:

delete outptu.JPG

عملية البحث Search Operation

يمكن البحث عن عنصر في مصفوفة بالاعتماد على دليل العنصر index او على قيمة العنصر

الخوارزمية

لنفترض بأن AL عبارة عن مصفوفة مؤلفة من N عنصر, ويمثل K عدد صحيح موجب بحيث ان K<=N

فيما يلي خوارزمية تمثل عملية البحث عن العنصر ذو ا لقيمة ITEM بواسطة البحث المتتالي ضمن المصفوفة

search algorithm.JPG

مثال:

المثال التالي تطبيق للخوارزمية اعلاه

search example.JPG

عند تطبيق المثال السابق سوف نحصل على الخرج التالي:

search output.JPG

عملية التعديل Update Operation

تشير عملية التعديل عنصر موجود ضمن المصفوفة في موقع محدد

الخوارزمية

لنفترض بأن AL عبارة عن مصفوفة مؤلفة من N عنصر, ويمثل K عدد صحيح موجب بحيث ان K<=N

فيما يلي خوارزمية تمثل عملية تعديل العنصر الموجود في الموقع K

update algorithm.JPG

مثال:

المثال التالي تطبيق للخوارزمية اعلاه

update example.JPG

عند تطبيق المثال السابق سوف نحصل على الخرج التالي:

update output.JPG

ارجو ان يكون درس المصوفات واضحا بالنسبة لكم, ويعتبر هو وعملياته اساس لشروحات عدد من الدروس القادمة

في الدرس القادم سنتحدث عن القائمة المتصلة Linked List

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
الواجهة Interface
التنفيذ Implementation
العمليات Operations
التعقيد الزمني Time Complexity
زمن التنفيذ Running time/execution time
البحث عن المعطيات Data search
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
https://www.tutorialspoint.com/data_structures_algorithms/index.htm

 

 

 

, , , , , , , , , , , ,

أضف تعليق

7- الخوارزميات وبنى المعطيات – المفاهيم الاساسية Algorithms and Data Structure – Basic Concepts

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Basic Concepts
الخوارزميات وبنى المعطيات –  المفاهيم الاساسية

نعود الان الى بنى المعطيات بعد شرح مختصر ومفيد عن الخوارزميات, لنتحدث اليوم عن المفاهيم والمصطلحات الاساسية في بنى المعطيات.
هذا الدرس بسيط جدا, ويطرح المفاهيم الاساسية وبعض انواع المعطيات التي سنتطرق الى شرحها في دروس قادمة

اثناء تعريف البيانات يجب ان نتوخى النقاط التالية في التعريف:

  • Atomic: يحدد التعريف هنا مفهوما واحدا
  • الصحة Accurate: يجب ان يكون التعريف واضحا لا لبس فيه
  • الوضوح والايجاز Clear and concise: يجب ان يكون التعريف قابلا للفهم

لنبدأ الآن بشرح مفهوم

غرض البيانات Data Object

يمثل غرض يحوي معطيات .

كلمة Object  ترد كثيرا ايضا في مجال البرمجة غرضية التوجه Object Oriented Programming

نمط المعطيات Data Type

نمط المعطيات: وهي طريقة لتصنيف انواع المعطيات المختلفة, مثل: الاعداد الصحيحة integer, السلاسل المحرفية string, … والتي تحدد انواع القيم التي من الممكن استخدامها لهذا النوع من نمط المعطيات, بالاضافة انواع العمليات operations التي من الممكن تطبيقها على المعطيات من هذا النوع.
هنالك نوعين من المعطيات:

  • انماط البيانات الاساسية(المدمجة) built-in Data Types
  • انماط البيانات المشتقة Derived Data Types

 

انماط البيانات الاساسية(المدمجة) Built-in Data types

تعرف  انماط البيانات التي يتواجد ضمن معظم اللغات دعم مدمج built-in support مسبقا لها باسم انماط البيانات المدمجة (الاساسية) built-in data types.

على سبيل المثال, توفر معظم اللغات الانماط التالية المدمجة من البيانات:

  • نمط integer
  • النمط المنطقي Boolean وياخد احد قيمتي true or false
  • النمط العائم float ويستخدم للارقام العشرية
  • النمط المحرفي character and strings

انماط البيانات المشتقة Derived Data Types

تعرف انماط البيانات هذه بأنها مستقلة عن التنفيذ implementation independent , حيث يمكن تنفيذها باكثر من طريقة.

عادة ما يتم انشاء انواع البيانات هذه عبر جمع اكثر من نوع من انواع البيانات الاساسية ( المدمجة) مع مجموعة من العمليات التي من الممكن تطبيقها عليهم.

مثال :

  • القائمة List
  • المصفوفة Array
  • المكدس Stack
  • الرتل Queue

 

العمليات الاساسية Basic Operations

يتم معالجة البيانات الموجودة ضمن بنى المعطيات عبر مجموعة معينة من العملياتoperations .
لهذه العمليات اهمية كبيرة جدا.

امثلة عليها:

  • التجوال Traversing
  • البحث Searching
  • الاضافة Insertion
  • الحذف Deletion
  • الفرز Sorting
  • الدمج Merging

ملاحظة:
يتم استخدام كلمة “بيانات” تارة وكلمة “معطيات” تارة, وكلاهما يحمل نفس المعنى, سواء قلنا بنى المعطيات او بنى البيانات فنحن نشير الى نفس المفهوم Data Structure

اعتقد بأنه اصبح لدينا الآن فكرة واضحة عن المفاهيم الاساسية للمعطيات, بامكاننا الآن وعبر الدرس القادم الشروع بشرح هذه البنى, لتكون اول بنية نقوم بشرحها هي المصفوفة Array.

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
الواجهة Interface
التنفيذ Implementation
العمليات Operations
التعقيد الزمني Time Complexity
زمن التنفيذ Running time/execution time
البحث عن المعطيات Data search
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
https://www.tutorialspoint.com/data_structures_algorithms/index.htm

 

 

 

, , , , , , , ,

أضف تعليق

6- الخوارزميات وبنى المعطيات – البرمجة الديناميكية Algorithms and Data Structure – Dynamic Programming

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Dynamic Programming
الخوارزميات وبنى المعطيات –  البرمجة الديناميكية

حديثنا في هذه الحلقة عن البرمجة الديناميكية dynamic programming

يعتبر منهنج البرمجة الديناميكية dynamic programming مقاربا لمنهج فرق تسد divide and conquer من حيث تقسيم المسألة قيد الحل الى مسائل جزئية.

ولكن على خلاف منهج فرق تسد divide and conquer, فإن لا يتم حل المسائل الجزئية بشكل مستقل. وانما يتم الاحتفاظ بحلول هذه المسائل الجزئية واستخدامه من اجل حل المسائل المشابهه او المترابطة.

 

يستخدم منهج البرمجة الديناميكية dynamic programming approach عندما يكون لدينا مسائل يمكن تقسيمها الى مسائل جزئية متشابهه, وبالتالي فإنه يمكن اعادة استخدام النتائج.
في الغالب, يتم استخدام هذا المنهج في مسائل الأمثلة optimization problems.
قبل البدء بحل مسألة جزئية من المسألة الاصلية, تقوم الخوارزمية الديناميكية بالبحث عن نتائج حلول سابقة لمسائل جزئية مماثلة.
يتم دمج حلول المسائل الجزئية من أجل الوصول الى أفضل حل.
بإمكاننا القول بأن:

  • يجب أن تكون المشكلة قابلة للتقسيم إلى مسائل جزئية متداخلة.
  • يمكن الوصول الى حل مثالي عبر استخدام الحلول المثالية للمسائل الجزئية الاصغر
  • تستخدم الخوارزميات الديناميكية Dynamic algorithms خاصية التذكر memorization.

 

المقارنة Comparison

على نقيض الخوارزميات الجشعة greedy algorithms, حيث تكون الحلول الامثلية المحلية مرغوبة, فإن الخوارزميات الديناميكية تسعى نحو حل مثال للمسألة ككل.

على نقيض خوارزميات فرق تسد divide and conquer, حيث يتم تجميع الحلول الجزئية من اجل الوصول الى حل المسألة الكاملة, فإن منهج الخوارزميات الديناميكية يتسخدم خرج output المسائل الجزئية الصغيرة من اجل امثلة optimize  حلول المسائل الجزئية الأكبر.

تستخدم الخوارزميات الديناميكية خاصية التذكر memorization من اجل تذكر نتائج الحلول المسائل الجزئية لكي يتم استخدامها لاحقا في امثلة حلول المسائل الجزئية الاكبر.

امثلة:

فيما يلي قائمة بعدد من مسائل الكمبيوتر التي من الممكن حلها عن طريق منهج البرمجة الديناميكية

  • سلسلة فيبوناشي Fibonacci number series
  • مسألة حقيبة الظهر Knapsack problem
  • All pair shortest path by Floyd-Warshall
  • Shortest path by Dijkstra
  • جدولة المشاريع Project scheduling

يمكن استخدام البرمجة الديناميكية بطريقتين
top-down and bottom-up
تعتبر عملية استخدام الحلول السابقة للمسائل الجزئية من اجل تحسين وتسهيل الحصول على حلول جيدة للمسائل الاكبر ارخص من عملية اعادة حساب الحل من الصفر, وذلك من حيث عدد دورات المعالج CPU.

وبذلك نكون انهينا حديثنا عن الخورازميات, لننتقل بالحلقة القادمة للحديث عن المفاهيم الاساسية في بنى المعطيات وانواعها

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
الواجهة Interface
التنفيذ Implementation
العمليات Operations
التعقيد الزمني Time Complexity
زمن التنفيذ Running time/execution time
البحث عن المعطيات Data search
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
https://www.tutorialspoint.com/data_structures_algorithms/index.htm

 

 

 

, , , , , , , ,

أضف تعليق

5- الخوارزميات وبنى المعطيات – خوارزمية فرق تسد Algorithms and Data Structure – Divide and Conquer Algorithm

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Divide and Conquer
الخوارزميات وبنى المعطيات –  خوارزمية فرق تسد

نتابع في هذه الحلقة حديثنا عن احد الخوارزميات الشائعة الا وهي ” خوارزمية فرق تسد” Divide and Conquer

ضمن منهج خوارزمية “فرق تسد” divide and conquer, يتم تقسم المسألة المطلوب معالجتها الى عدة مسائل جزئية, ومن ثم يتم حل كل مسألة من هذه المسائل الجزئية بشكل مستقل.
عندما نستمر بتقسيم المسائل الجزئية الى مسائل اصغر, تدريجيا سوف نصل الى مرحلة حيث لا يعود بإمكاننا تقسيم المسألة الى مسائل اصغر من ذلك.
عندها يتم حل هذه المسائل الأصغر – تدعى عادة بمصطلح atomic – ومن ثم يتم تجميع الحلول الخاصة بكل المسائل الجزئية من أجل الحصول على حل المسألة الأصلية.

divide_and_conquer

بشكل عام, يمكن توضيح منهجية خوارزمية فرق تسد divide and conquer من خلال ثلاث خطوات:

  1. فرق – التجزئة Divide/Break
  2. السيطرة – الحل Conquer/Solve
  3. الدمج – التجميع Merge/Combine

سنشرح كل خطوة من هذه الخطوات على حدا:

فرق – التجزئة Divide/Break

تتضمن هذه الخطوة عملية تقسيم المسألة الى مسائل جزئية.
حيث ان المسائل الجزئية يجب ان تمثل جزء من المسألة الاصلية.
غالبا تتخذ هذه الخطوة منحى عودي recursive approach من اجل تنفيذها وتقسيم المسألة وصولا الى اصغر مسألة جزئية  ممكنة.
في هذه المرحلة, تتحول المسائل الجزئية الى مايدعى ب atomic – مسائل صغرى من المسألة الاساسية لا يمكن الحصول على اصغر منها – ولكنها لاتزال تمثل جزء من المسألة الاساسية المطلوب حلها.

السيطرة – الحل Conquer/Solve

في هذه المرحلة يكون لدينا عدد من المسائل الصغرى من المسألة الاصلية والتي من المطلوب حلها.

عادة, وضمن هذا المستوى, يتم اعتبار المسائل “محلولة” solved نفسها بنفسها – لانها وصلت لمرحلة من الصغر والبساطة بحيث اصبح الحل ظاهريا.

الدمج – التجميع Merge/Combine

عندما يتم حل المسائل الجزئية, تقوم هذه المرحلة بشكل عودي recursively  بتجميع الحلول الجزئية وصولا لتشكيل الحل الكلي للمسألة.

يعمل منهنج هذه الخوارزمية بشكل عودي recursively.
ملاحظة:

العودية recursion: وهي طريقة ومنهج لحل المسائل وتتضمن تقسيم المسألة الى مسائل جزئية اصغر الى حين الوصول الى اصغر حجم ممكن للمسألة والتي يمكن حلها بسهولة, عادة – برمجيا – تتمثل العودية recursion عبر تابع – دالة- تقوم باستدعاء نفسها بشكل متكرر وصولا الى شرط التوقف الذي يحدد اصغر حجم ممكن للمسألة قيد الحل.

 

أمثلة:

فيما يلي عدد من خوارزميات  الكمبيوتر المبنية على اساس منهجية فرق تسد Divide and Conquer

  • الفرز – الدمج Merge sort
  • الفرز السريع Quick Sort
  • البحث الثنائي Binary Search
  • Strassen’s Matrix Multiplication
  • Closest pair (points)

هنالك عدد كبير من الخوارزميات التي تستخدم هذا المنهج, ولكن الامثلة المطروحة كافية وجيدة لتوضيح هذه الاستراتيجية

نلقاكم ان شاء الله بحلقة قادمة نتحدث فيها عن البرمجة الديناميكية Dynamic programming لننهي بها حديثنا عن الخوارزميات وننتقل بعدها للحديث عن بنى المعطيات

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
الواجهة Interface
التنفيذ Implementation
العمليات Operations
التعقيد الزمني Time Complexity
زمن التنفيذ Running time/execution time
البحث عن المعطيات Data search
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
https://www.tutorialspoint.com/data_structures_algorithms/index.htm

 

 

 

, , , , , , ,

أضف تعليق