الفرق بين المراجعتين ل"Algorithms"
Wael-aldaghma (نقاش | مساهمات) ط (إشارة لمقال الخوارزميات الشامل) |
|||
| (6 مراجعات متوسطة بواسطة مستخدمين اثنين آخرين غير معروضة) | |||
| سطر 4: | سطر 4: | ||
وتنسب كلمة (خوارزمية) إلى عالم الرياضيات المسلم [https://ar.wikipedia.org/wiki/%D9%85%D8%AD%D9%85%D8%AF_%D8%A8%D9%86_%D9%85%D9%88%D8%B3%D9%89_%D8%A7%D9%84%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A محمد بن موسى الخوارزمي] صاحب كتاب (الكتاب المختصر في الجبر والمقابلة). | وتنسب كلمة (خوارزمية) إلى عالم الرياضيات المسلم [https://ar.wikipedia.org/wiki/%D9%85%D8%AD%D9%85%D8%AF_%D8%A8%D9%86_%D9%85%D9%88%D8%B3%D9%89_%D8%A7%D9%84%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A محمد بن موسى الخوارزمي] صاحب كتاب (الكتاب المختصر في الجبر والمقابلة). | ||
| − | تقدّم الخوارزميات حلولًا لمسائل كثيرة ومتنوعة منها: | + | تقدّم [https://academy.hsoub.com/programming/advanced/%D8%A7%D9%84%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A7%D8%AA/ الخوارزميات] حلولًا لمسائل كثيرة ومتنوعة منها: |
* أحرز مشروع الجينوم البشري تقدّمًا هائلًا في تشخيص جينات الإنسان التي يصل عددها إلى 100,000 جين وتحديد تسلسل 3 بلايين من الأزواج الكيميائية التي تشكّل الدنا البشري، وتحتاج عملية تخزين هذه البيانات وتحليلها والتعامل معها إلى خوارزميات معقدة. | * أحرز مشروع الجينوم البشري تقدّمًا هائلًا في تشخيص جينات الإنسان التي يصل عددها إلى 100,000 جين وتحديد تسلسل 3 بلايين من الأزواج الكيميائية التي تشكّل الدنا البشري، وتحتاج عملية تخزين هذه البيانات وتحليلها والتعامل معها إلى خوارزميات معقدة. | ||
* حماية خصوصية المستخدم ومعلوماته الشخصية مثل رقم بطاقة الائتمان وكلمات المرور وغيرها من الأمور الضرورية في مجال التجارة الإلكترونية، وتستند تقنيات التشفير وتعمية البيانات على خوارزميات رياضية وعلى نظرية الأرقام. | * حماية خصوصية المستخدم ومعلوماته الشخصية مثل رقم بطاقة الائتمان وكلمات المرور وغيرها من الأمور الضرورية في مجال التجارة الإلكترونية، وتستند تقنيات التشفير وتعمية البيانات على خوارزميات رياضية وعلى نظرية الأرقام. | ||
* تستخدم الخرائط الإلكترونية خوارزميات خاصة لتحديد المسافة الأقصر بين نقطتين يختارهما المستخدم على الخريطة. | * تستخدم الخرائط الإلكترونية خوارزميات خاصة لتحديد المسافة الأقصر بين نقطتين يختارهما المستخدم على الخريطة. | ||
| − | + | {{Course|course=cs}} | |
| + | __TOC__ | ||
== [[Algorithms/data structures|بنى المعطيات]] == | == [[Algorithms/data structures|بنى المعطيات]] == | ||
بنى المعطيات Data Structures هي الطريقة المتبعة في ترتيب البيانات في الحاسوب بحيث يمكن استخدامها بفعالية، والهدف من بنى المعطيات هو اختزال المساحة والتعقيد الزمني المطلوب للمهام المختلفة. | بنى المعطيات Data Structures هي الطريقة المتبعة في ترتيب البيانات في الحاسوب بحيث يمكن استخدامها بفعالية، والهدف من بنى المعطيات هو اختزال المساحة والتعقيد الزمني المطلوب للمهام المختلفة. | ||
| + | ==بنى المعطيات الخطية== | ||
| + | ===[[Algorithms/arrays|المصفوفات]]=== | ||
| + | تستخدم المصفوفات في تخزين العناصر المتجانسة في مواقع متجاورة، ويجب تحديد حجم المصفوفة قبل تخزين البيانات فيها. | ||
| + | ====[[Algorithms/linked lists|القوائم المترابطة]]==== | ||
| + | يكون كل عنصر في القائمة المترابطة كائنًا بحد ذاته، ويتكون كل عنصر (أو ما يعرف كذلك بالعقدة) من جزئين: البيانات وإشارة إلى العقدة اللاحقة. | ||
| + | هناك عدة أنواع للقوائم المترابطة منها: | ||
| + | ====[[Algorithms/linked lists|القوائم المترابطة المفردة]]==== | ||
| + | في هذا النوع من القوائم المترابطة تخزّن كل عقدة موقع العقدة اللاحقة أو تشير إليه، وتشير العقدة الأخيرة في القائمة المترابطة إلى القيمة NULL. | ||
| + | ====[[Algorithms/doubley linked lists|القوائم المترابطة المزدوجة]]==== | ||
| + | تمتلك كل عقدة في هذا النوع من القوائم إشارتين، تشير واحدة منهما إلى العقدة التالية والأخرى إلى العقدة السابقة. | ||
| + | ====[[Algorithms/circular linked lists|القوائم المترابطة الدائرية]]==== | ||
| + | ترتبط جميع العقد في هذا النوع من القوائم بعضها ببعض لتشكّل دائرة، ولا وجود لقيمة NULL في نهاية القائمة. | ||
| + | ====[[Algorithms/stacks|المكادس]]==== | ||
| + | الكدس Stack أو LIFO (يدخل أخيرًا، يخرج أوّلًا اختصار last in, first out) هو من بنى المعطيات المجردة والتي تكون على هيئة مجموعة من العناصر التي يمكن أن نؤدي عمليتين أساسيتين عليها وهما عملية إضافة العنصر push وحذف العنصر pop. تجري هاتان العمليتان في المكادس من جهة واحدة وهي قمّة المكدس. | ||
| + | ====[[Algorithms/queues|الأرتال]]==== | ||
| + | الرتل Queue أو FIFO (يدخل أولًا، يخرج أولًا اختصار first in, first out) هو من بنى المعطيات المجردة والتي تكون على هيئة مجموعة من العناصر التي يمكن أن نؤدي عليها عمليتين أساسيتين هما: إضافة العنصر enqueue وإزالة العنصر dequeue. | ||
| + | ===بنى المعطيات الهرمية=== | ||
| + | ====[[Algorithms/binary trees|الأشجار الثنائية]]==== | ||
| + | الأشجار الثنائية هي من بنى المعطيات الهرمية، والشجرة الثنائية هي شجرة بيانات تمتلك كل عقدة فيها على عقدتي أبناء كحدّ أقصى، وتسمّيان بالابن الأيمن والابن الأيسر. | ||
| + | ====[[Algorithms/binary search trees|أشجار البحث الثنائية]]==== | ||
| + | شجرة البحث الثنائية Binary Search Tree هي شجرة ثنائية تمتلك الخصائص الإضافية التالية: | ||
| + | #الشجرة الفرعية اليسرى تتضمن عقدًا تكون مفاتيحها أقل من مفاتيح العقدة التي تتفرع منها. | ||
| + | #الشجرة الفرعية اليمنى تتضمن عقدًا تكون مفاتيحها أكبر من مفاتيح العقدة التي تتفرع منها. | ||
| + | #يجب أن تكون الأشجار الفرعية جميعها أشجار بحث ثنائية. | ||
| + | ====[[Algorithms/tries|شجرة البادئات]]==== | ||
| + | شجرة البادئات (Prefix tree وتعرف أيضًا بالشجرة الرقمية digital tree والتراي Trie) هي بنية معطيات فعالة لاسترجاع المعلومات Information reTrieval data structur. تساعد شجرة البادئات على تقليص التعقيد الزمني لعمليات البحث إلى حدود معقولة. | ||
| + | ====[[Algorithms/heaps|الكومات]]==== | ||
| + | الكومة Heap نوع خاص من بنى المعطيات الشجرية والتي تكون فيها شجرة البيانات شجرة بيانات كاملة complete. | ||
| + | ====[[Algorithms/hashing|دالة التقطيع]]==== | ||
| + | دالة التقطيع Hashing Function هي دالة تحول مفتاحًا كبيرًا إلى عدد صحيح ذي قيمة أصغر ويستخدم كموقع index في جدول التقطيع. | ||
| + | ====[[Algorithms/graphs|الرسم البياني]]==== | ||
| + | يضمّ الرسم البياني Graph المكونات التالية: | ||
| + | #مجموعة محددة من الرؤوس vertices والتي تسمى كذلك بالعقد nodes. | ||
| + | #مجموعة محددة من أزواج مرتّبة وتكون بالهيئة (u,v) وتسمى بالأضلاع edges. | ||
== [[Algorithms/Asymptotic Analysis|تحليل الخوارزميات]] == | == [[Algorithms/Asymptotic Analysis|تحليل الخوارزميات]] == | ||
| سطر 20: | سطر 55: | ||
أساليب الخوارزميات Algorithm Paradigms هي مجموعة من النماذج وأطر العمل التي يستند عليها في بناء وتصميم مجموعة معينة من الخوارزميات. | أساليب الخوارزميات Algorithm Paradigms هي مجموعة من النماذج وأطر العمل التي يستند عليها في بناء وتصميم مجموعة معينة من الخوارزميات. | ||
| − | + | ===[[Algorithms/Brute force|القوة الغاشمة]]=== | |
| + | هذا الأسلوب هو الأبسط Naive ويعتمد على حل المسألة المطروحة بطريقة مباشرة. | ||
| + | ===[[Algorithms/Greedy Algorithms|الخوارزميات الجشعة]]=== | ||
| + | الخوارزميات الجشعة هي إحدى أساليب الخوارزميات التي تصل إلى الحل خطوة فخطوة وذلك بالحرص على أن تقدّم الخطوة التالية أعظم فائدة ممكنة في طريق الوصول إلى الحل | ||
| + | ===[[Algorithms/Dynamic Programming|البرمجة الديناميكية]]=== | ||
| + | يمكن تعريف البرمجة الديناميكية بأنّها عملية تحسين تُجرى على العمليات التعاودية، بمعنى أنّه يمكن استخدام البرمجة الديناميكية في أيّ مكان تظهر فيها استدعاءات تعاودية متكررة تستخدم المدخلات عينها. وتتلخّص عملية التحسين في تخزين النتائج التي نحصل عليها من المشاكل الفرعية وبهذا تنتفي الحاجة إلى إعادة حساب تلك النتائج في وقت لاحق. | ||
| + | ===[[Algorithms/Divide And Conquer|فرق تسد]]=== | ||
| + | يقسِّم نموذج فرِّق تسد المسألة إلى مسائل فرعية تشبه المسألة الأصلية، ويقدّم حلولًا للمسائل الفرعية بطريقة تعاودية، ثم يدمج حلول المسائل الفرعية وذلك لتقديم حلٍّ للمسألة الأصلية. | ||
| + | ===[[Algorithms/Backtracking|التعقب الخلفي]]=== | ||
| + | يستخدم نموذج التعقب الخلفي في حلّ المسائل بطريقة تعاودية محاولًا بناء الحلّ تصاعديًا قطعة قطعة، وحذف الحلول التي تفشل في تحقيق القيود المفروضة من قبل المسألة في أي وقت (يقصد بالوقت هنا الوقت المستغرق للوصول إلى أي مرحلة في شجرة البحث). | ||
== [[Algorithms/Searching Algorithms|خوارزميات البحث]] == | == [[Algorithms/Searching Algorithms|خوارزميات البحث]] == | ||
| − | تتحقق خوارزميات البحث من وجود عنصر معين أو تعيد عنصرًا معيّنًا من بنية المعطيات التي يكون العنصر مخزّنًا فيها. | + | تتحقق خوارزميات البحث من وجود عنصر معين أو تعيد عنصرًا معيّنًا من بنية المعطيات التي يكون العنصر مخزّنًا فيها. |
| − | + | ===[[Algorithms/linear search|البحث الخطي]]=== | |
| + | البحث الخطّي Linear Search من أبسط خوارزميات البحث إذ أنّها تمر على عناصر المصفوفة واحدًا تلو الآخر بحثًا عن العنصر المطلوب. | ||
| + | ===[[Algorithms/binary search|البحث الثنائي]]=== | ||
| + | تبحث خوارزمية البحث الثنائي Binary Search عن عنصر معين في مصفوفة مرتبة وذلك بتقسيمها باستمرار إلى نصفين والتحقق من وجود العنصر المراد البحث عنه في كلّ نصفٍ إلى أن تعثر على العنصر أو تصل إلى مصفوفة فارغة. | ||
| + | ===[[Algorithms/jump search|البحث القفزي]]=== | ||
| + | تتحقق خوارزمية البحث القفزي Jump Search (تعرف كذلك بخوارزمية البحث الكتلي Block Search) من عدد أقل من العناصر (مقارنة بالبحث الخطي) وذلك بالقفز عبر عناصر المصفوفة بخطوات ثابتة، بمعنى تجاوز بعض العناصر عوضًا عن البحث فيها كلّها. | ||
| + | ===[[Algorithms/interpolation search|البحث الاستكمالي]]=== | ||
| + | تعدّ خوارزمية البحث الاستكمالي Interpolation Search تحسينًا على البحث الثنائي في بعض الحالات، إذ تكون القيم موزّعة بانتظام في مصفوفة مرتبة فتجري هذه الخوارزمية عملية التحقّق في مواقع مختلفة بالاعتماد على قيمة المفتاح المراد البحث عنه. | ||
| + | ===[[Algorithms/exponential search|البحث الأسّي]]=== | ||
| + | تقسّم خوارزمية البحث الأسّي Exponential Search المصفوفة التي يجري البحث فيها إلى مصفوفات فرعية يزداد عدد العناصر فيها ازديادًا أسّيًا (1, 2, 4, 8.... وهكذا إلى حين الوصول إلى مصفوفة جزئية يكون فيها العنصر الأخير أكبر من العنصر المطلوب. | ||
== [[Algorithms/Sorting Algorithms|خوارزميات الترتيب]] == | == [[Algorithms/Sorting Algorithms|خوارزميات الترتيب]] == | ||
خوارزميات الترتيب Sorting Algorithms هي خوارزميات تستخدم لإعادة ترتيب مصفوفة معطاة أو قائمة من العناصر بالاعتماد على عامل مقارنة معيّن. يُستخدم عامل المقارنة لتحديد ترتيب العناصر الجديد في بنية المعطيات المراد إعادة ترتيب عناصرها. | خوارزميات الترتيب Sorting Algorithms هي خوارزميات تستخدم لإعادة ترتيب مصفوفة معطاة أو قائمة من العناصر بالاعتماد على عامل مقارنة معيّن. يُستخدم عامل المقارنة لتحديد ترتيب العناصر الجديد في بنية المعطيات المراد إعادة ترتيب عناصرها. | ||
| − | + | ===[[Algorithms/bubble sort|الترتيب بالفقاعات]]=== | |
| + | خوارزمية الترتيب بالفقاعات Bubble Sort هي أبسط خوارزميات الترتيب والتي تعمل على تبديل مواقع العناصر المتجاورة إن كان ترتيبها خاطئًا. | ||
| + | ===[[Algorithms/selection sort|الترتيب بالتحديد]]=== | ||
| + | ترتّب خوارزمية الترتيب بالتحديد selection sort المصفوفة عن طريق العثور على أصغر عنصر (بافتراض أنّ الترتيب سيكون ترتيبًا تصاعديًا) في الجزء غير المرتّب من المصفوفة ووضعه في بدايتها. | ||
| + | ===[[Algorithms/insertion sort|الترتيب بالإدراج]]=== | ||
| + | الترتيب بالإدراج Insertion Sort من خوارزميات الترتيب البسيطة التي تعمل بنفس الطريقة التي ترتّب فيها أوراق اللعب يدويًا. | ||
| + | ===[[Algorithms/merge sort|الترتيب بالدمج]]=== | ||
| + | تقسم خوارزمية الترتيب بالدمج Merge Sort المصفوفة المدخلة إلى نصفين، ثم تستدعي الخوارزمية نفسها على هذين النصفين ثم تدمج نصفي المصفوفة المرتبين بعضهما ببعض. | ||
| + | ===[[Algorithms/quick sort|الترتيب السريع]]=== | ||
| + | تنتقي عنصرًا من عناصر المصفوفة وتجعله محورًا pivot ثمّ تقسّم المصفوفة المعطاة حول ذلك العنصر. | ||
| + | ===[[Algorithms/heap sort|الترتيب بالكومة]]=== | ||
| + | تستند خوارزمية الترتيب بالكومة Heap Sort على [[Algorithms/binary heaps|الكومة الثنائية Binary Heap]]، وهي مشابهة لخوارزمية [[Algorithms/selection sort|الترتيب بالتحديد]] إذ نختار في البداية العنصر الأكبر في المصفوفة ونضعه في نهاية المصفوفة، وتعاد العملية على بقية العناصر. | ||
| + | ===[[Algorithms/counting sort|الترتيب بالعد]]=== | ||
| + | تعمل هذه الخوارزمية عن طريق حساب عد العناصر التي تمتلك قيمة مفتاح فريدة، ثم حساب موقع كل عنصر في التسلسل المخرج. | ||
| + | ===[[Algorithms/radix sort|الترتيب بالجذر]]=== | ||
| + | تتلخص هذه الخوارزمية بإجراء ترتيب للعناصر رقمًا تلو الآخر بدءًا من الرقم الأقل أهمية إلى الرقم الأكثر أهمية. | ||
| + | ===[[Algorithms/shell sort|خوارزمية شِل للترتيب]]=== | ||
| + | ترتب خوارزمية شِل المصفوفة بالنسبة لقيمة كبيرة من <code>h</code> ، ثم تستمر في تقليص قيمة <code>h</code> إلى حين الوصول إلى <code>1</code>. | ||
| + | ===[[Algorithms/bucket sort|الترتيب بالدلو]]=== | ||
| + | تظهر فائدة خوارزمية الترتيب بالدلو Bucket Sort عندما تكون المدخلات موزّعة بانتظام ضمن نطاق معيّن. | ||
| + | ===[[Algorithms/pigeonhole sort|الترتيب ببرج الحمام]]=== | ||
| + | تلائم خوارزمية الترتيب ببرج الحمام Pigeonhole sort قوائم العناصر التي يكون فيها عدد العناصر وعدد القيم المفتاحية الممكنة possible key values متساويين تقريبًا. | ||
| + | ===[[Algorithms/cycle sort|الترتيب بالتدوير]]=== | ||
| + | مبدأ عمل خوارزمية الترتيب بالتدوير Cycle sort هو تدوير مواقع العناصر في المصفوفة إلى حين الحصول على مصفوفة مرتبة بالكامل. | ||
| + | ===[[Algorithms/tree sort|الترتيب بالشجرة]]=== | ||
| + | تعتمد خوارزمية الترتيب بالشجرة Tree Sort في عملها على شجرة البحث الثنائية، إذ أنّها تصنع شجرة بحث ثنائية في البداية من العناصر المتوفّرة في المصفوفة المدخلة ثم تنفّذ عملية تنقل وسطي للحصول على العناصر مرتّبة. | ||
| + | ===[[Algorithms/cocktail sort|الترتيب المخلوط]]=== | ||
| + | تتنقّل خوارزمية [[Algorithms/bubble sort|الترتيب بالفقاعات]] عبر عناصر المصفوفة من جهة اليسار دائمًا وتحرّك أكبر العناصر إلى موقع الصحيح في الدورة الأولى ثم تحرّك ثاني أكبر عنصر في الدورة الثانية وهكذا دواليك. أما خوارزمية الترتيب المخلوط Cocktail sort فتتنقّل عبر عناصر المصفوفة باتجاهين بالتناوب. | ||
| + | ===[[Algorithms/odd even sort|الترتيب فردي-زوجي (الترتيب بالقرميد)]]=== | ||
| + | خوارزمية الترتيب فردي-زوجي Odd-Even Sort (أو الترتيب بالقرميد Brick sort) هي تحوير على خوارزمية [[Algorithms/bubble sort|الترتيب بالفقاعات]]. تقسم هذه الخوارزمية إلى قسمين القسم الفردي والقسم الزوجي. تستمر الخوارزمية في عملها إلى أن تصبح جميع العناصر في المصفوفة مرتبة | ||
== [[Algorithms/String Searching Algorithms|خوارزميات البحث عن النصوص]] == | == [[Algorithms/String Searching Algorithms|خوارزميات البحث عن النصوص]] == | ||
تعدّ خوارزميات البحث عن النصوص (وتسمّى كذلك بخوارزميات البحث عن الأنماط Pattern Searching) جزءًا من خوارزميات النصوص String Algorithms، وتساعد هذه الخوارزميات في البحث عن سلسلة نصية معيّنة في سلسلة نصية أخرى. | تعدّ خوارزميات البحث عن النصوص (وتسمّى كذلك بخوارزميات البحث عن الأنماط Pattern Searching) جزءًا من خوارزميات النصوص String Algorithms، وتساعد هذه الخوارزميات في البحث عن سلسلة نصية معيّنة في سلسلة نصية أخرى. | ||
| − | + | ===[[Algorithms/naive string searching|الخوارزمية البسيطة]]=== | |
| + | تنتقل الخوارزمية عبر جميع الحروف في السلسلة النصية واحدًا تلو الآخر بحثًا عن التسلسل الذي يطابق النمط المعطى. | ||
| + | ===[[Algorithms/KMP|خوارزمية KMP]]=== | ||
| + | تعالج الخوارزمية النمط المراد البحث عنه لتجنّب تكرار البحث عن أنماط جرى البحث عنها في الخطوات السابقة. | ||
| + | ===[[Algorithms/Rabin Karp|خوارزمية رابين-كارب]]=== | ||
| + | تحرّك خوارزمية رابين-كارب Rabin-Karp النمط الذي تبحث عنه عبر السلسلة النصية موقعًا تلو الآخر وتطابق قيمة التقطيع Hash value للنمط المعطى مع قيمة التقطيع لجزء السلسلة الذي تجري معه المقارنة | ||
| + | ===[[Algorithms/Boyer Moore|خوارزمية بوير-مور]]=== | ||
| + | تعتمد خوارزمية بوير-مور Boyer-Moore على الأسلوبين: استكشاف الحروف السيئة، واستكشاف اللاحقة الجيدة. | ||
== [[Algorithms/Graph Algorithms|خوارزميات الرسوم البيانية]] == | == [[Algorithms/Graph Algorithms|خوارزميات الرسوم البيانية]] == | ||
| − | تقدّم خوارزميات الرسوم البيانية طرقًا فعالة للكشف عن الدورات في الرسوم البيانية، إلى جانب إيجاد الشجرة الممتدة الصغرى والمسار الأقصر وغيرها. | + | تقدّم خوارزميات الرسوم البيانية Graph Algorithms طرقًا فعالة للكشف عن الدورات في الرسوم البيانية، إلى جانب إيجاد الشجرة الممتدة الصغرى والمسار الأقصر وغيرها. |
| − | + | ===[[Algorithms/Kruskal MST|خوارزمية كروسكال]]=== | |
| + | تعثر خوارزمية كروسكال Kruskal على الشجرة الممتدة الصغرى في الرسم البياني المعطى، بترتيب الأضلاع تصاعديًا ثم اختيار الضلع الأصغر. | ||
| + | ===[[Algorithms/Prim MST|خوارزمية برم]]=== | ||
| + | تعثر خوارزمية Prim على الشجرة الممتدة الصغرى في الرسم البياني المعطى، وتبدأ بشجرة ممتدة فارغة وتعتمد في عملها على مجموعتين من الرؤوس. | ||
| + | ===[[Algorithms/Boruvka MST|خوارزمية بوروفكا]]=== | ||
| + | تعدّ خوارزمية بوروفكا أقدم خوارزمية لإيجاد الشجرة الممتدة الصغرى وقد وضعها بوروفكا سنة 1926م، قبل اختراع الحواسيب بفترة طويلة، وقد نشرت هذه الخوارزمية كطريقة لبناء شبكة فعّالة من التمديدات الكهربائية. | ||
| + | ===[[Algorithms/Bellman Ford|خوارزمية بِلمان - فورد]]=== | ||
| + | تمتاز هذه الخوارزمية بقدرتها على إيجاد المسار الأقصر في الرسوم البيانية التي تكون فيها أوزان الأضلاع ذات قيم سالبة. | ||
| + | ===[[Algorithms/Dijkstra|خوارزمية ديكسترا]]=== | ||
| + | تنتج خورازمية ديكسترا Dijkstra شجرة المسار الأقصر بدءًا من المصدر المعطى كجذر لهذه الشجرة. | ||
| + | ===[[Algorithms/Floyd Warshall|خوارزمية فلويد وارشال]]=== | ||
| + | تقدّم خوارزمية فلويد-وارشال Floyd-Warshall حلًّا لمشكلة المسار الأقصر لجميع الأزواج. | ||
| + | ===[[Algorithms/Kahn|خوارزمية كان للترتيب الطوبولوجي]]=== | ||
| + | تجري خوارزمية كان عملية الترتيب الطوبولوجي باستخدام [[Algorithms/queues|رتل]]. | ||
== [[Algorithms/Mathematical Algorithms|الخوارزميات الرياضية]] == | == [[Algorithms/Mathematical Algorithms|الخوارزميات الرياضية]] == | ||
تعنى الخوارزميات الرياضية بإيجاد أسرع الحلول الممكنة للمسائل الرياضية المختلفة باستخدام قوانين وعلاقات رياضية معروفة. | تعنى الخوارزميات الرياضية بإيجاد أسرع الحلول الممكنة للمسائل الرياضية المختلفة باستخدام قوانين وعلاقات رياضية معروفة. | ||
| − | + | ===[[Algorithms/GCD|القاسم المشترك الأكبر]]=== | |
| + | القاسم المشترك الأكبر (Greatest Common Divisor GCD) لعددين هو أكبر يقسم هذين العددين قسمة تامة. | ||
| + | ===[[Algorithms/LCM|المضاعف المشترك الأصغر]]=== | ||
| + | المضاعف المشترك الأصغر (Least Common Multiple) لعددين هو أصغر عدد يمكن قسمته بواسطة كلا العددين. | ||
| + | ===[[Algorithms/prime factors|العوامل الأولية]]=== | ||
| + | تحليل العدد إلى عوامله الأولية يعني إيجاد الأعداد الأولية التي يكون حاصل ضربها ببعضها مساويًا للعدد الأصلي. | ||
| + | ===[[Algorithms/square root|الجذر التربيعي]]=== | ||
| + | تحسب هذه الخوارزميات الجذر التربيعي للعدد المعطى. | ||
| + | ===[[Algorithms/cubic root|الجذر التكعيبي]]=== | ||
| + | تحسب هذه الخوارزمية الجذر التكعيبي للعدد المعطى. | ||
| + | ===[[Algorithms/Smith number|عدد سميث]]=== | ||
| + | عدد سميث Smith Number هو عدد مركّب تكون مجموع أرقامه مساوية لمجموع الأرقام في عوامله الأولية. | ||
| + | ===[[Algorithms/Catalan numbers|الأعداد الكاتالانية]]=== | ||
| + | الأعداد الكاتالانية Catalan Numbers هي متتالية من الأعداد الطبيعية والتي تظهر في عدد من مسائل العدّ؟ | ||
| + | ===[[Algorithms/all divisors|إيجاد قواسم عدد طبيعي]]=== | ||
| + | قواسم العدد الطبيعي هي الأعداد التي يقبل القسمة عليها دون باقٍ. | ||
| + | ===[[Algorithms/Fibonacci numbers|أعداد فيبوناتشي]]=== | ||
| + | تشكّل أعداد فيبوناتشي Fibonacci numbers متتالية تدعى بمتتالية فيبوناتشي Fibonacci Sequence يكون كل عدد فيها مساويًا لمجموع العددين الذين يسبقانه في المتتالية، وتبدأ المتتالية بالعددين <code>0</code> و <code>1</code>. | ||
| + | ===[[Algorithms/factorial|مضروب العدد]]=== | ||
| + | مضروب عدد صحيح غير سالب هو حاصل ضرب جميع الأعداد الصحيحة التي تكون أصغر من العدد المعطى أو تساويه. | ||
| + | ===[[Algorithms/prime numbers|الأعداد الأولية]]=== | ||
| + | العدد الأولي هو عدد يكون أكبر من <code>1</code> ويقبل القسمة على <code>1</code> وعلى نفسه فقط. | ||
| + | ===[[Algorithms/Juggler sequence|متتالية لاعب الخفة]]=== | ||
| + | متتالية لاعبة الخفة Juggler Sequence هي متتالية من الأعداد الصحيحة التي يكون فيها العنصر الأول عددًا صحيحًا موجبًا وتتربط الأعداد فيما بينها بعلاقة تعاودية. تتميّز هذه المتتالية بأن الأعداد فيها تبدأ بالصعود تدريجيًا لتصل إلى قمّة معينة ثم تبدأ بعدها بالنقصان تدريجيًا، وأنّ هذه السلسلة تنتهي بالعدد <code>1</code> دائمًا. | ||
| + | ===[[Algorithms/divisibility|قابلية القسمة]]=== | ||
| + | تستخدم هذه الخوارزميات مجموعة من الخصائص والعلاقات الرياضية لمعرفة قابلية قسمة عدد معين على الأعداد من 3 إلى 9. | ||
| + | ===[[Algorithms/difference between sum of two subsets|إيجاد أقل فارق بين مجموعتين فرعيتين]]=== | ||
| + | تقسم هذه الخوارزمية مجموعة معين من الأعداد الصحيحة إلى مجموعتين فرعتين بطريقة يكون فيها الفارق بين مجموع عناصر المجموعة الأولى والثاني أقل ما يمكن. | ||
| + | ===[[Algorithms/Sum of all possible subsets|حساب مجموع كل العناصر من كل المجاميع الفرعية الممكنة]]=== | ||
| + | تحسب هذه الخوارزمية مجموع جميع العناصر المتكوّنة من كل المجموعات الفرعية التي يمكن تكوينها من مجموعة تضمّ <code>n</code> من الأعداد الطبيعية. | ||
| + | ===[[Algorithms/power set|مجموعة القوة]]=== | ||
| + | مجموعة القوة Power Set هي المجموعة التي تضمّ جميع المجموعات المتفرّعة من المجموعة الأصلية. | ||
| + | ===[[Algorithms/numeral systems conversion|التحويل بين أنظمة الأعداد]]=== | ||
| + | هناك طرق عدة لتمثيل الأعداد وذلك بالاعتماد على الأساس base، ويشيع استخدام أربعة أنظمة هي النظام الثنائي Binary، والثماني Octal، والعشري Decimal، والسداسي عشر Hexadecimal. | ||
| + | ===[[Algorithms/infix prefix postfix expressions|التعابير المرتبة وسطيًا وقبليًا وبعديًا]]=== | ||
| + | هناك ثلاث طرق لترتيب العوامل والمعاملات في التعابير الرياضية للإشارة إلى العمليات التي تنال الأولوية عند معالجة التعبير الرياضي من قبل المصرّفات Compilers. هذه الطرق هي: الترتيب الوسطي infix والقبلي prefix والبعدي postfix. | ||
== [[Algorithms/Geometric Algorithms|الخوارزميات الهندسية]] == | == [[Algorithms/Geometric Algorithms|الخوارزميات الهندسية]] == | ||
تعنى الخوارزميات الهندسية Geometric Algorithms بإيجاد الحلول المناسبة للمسائل الهندسية المختلفة. | تعنى الخوارزميات الهندسية Geometric Algorithms بإيجاد الحلول المناسبة للمسائل الهندسية المختلفة. | ||
| − | + | ===الخطوط والقطع المستقيمة=== | |
| + | ====[[Algorithms/two line segments intersect|تقاطع قطعتين مستقيمتين]]==== | ||
| + | تتحقق هذه الخوارزمية من تقاطع قطعتين مستقيمتين. | ||
| + | ====[[Algorithms/intersection 2 lines|إيجاد نقطة تقاطع خطين مستقيمين]]==== | ||
| + | تعثر هذه الخوارزمية على نقطة تقاطع خطين مستقيمين. | ||
| + | ====[[Algorithms/line passing 2 points|إيجاد الخط الذي يمرّ بنقطتين]]==== | ||
| + | تعثر هذه الخوارزمية على معادلة الخط المستقيم الذي يمرّ بنقطتين في مستوى الإحداثيات. | ||
| + | ====[[Algorithms/line passing origin|التحقق من مرور الخط المستقيم عبر نقط الأصل]]==== | ||
| + | تتحقق هذه الخوارزمية من مرور الخط المستقيم ذي الإحداثيات <code>(x1, y1)</code> و <code>(x2, y2)</code> عبر نقطة الأصل ذات الإحداثيات <code>(0,0)</code>. | ||
| + | ====[[Algorithms/midpoint of line|إيجاد نقطة الوسط في خطّ مستقيم]]==== | ||
| + | تعثر هذه الخوارزمية على نقطة الوسط لخطّ مستقيم يبدأ من النقطة <code>(x1, y1)</code> وينتهي بالنقطة <code>(x2, y2)</code>. | ||
| + | ====[[Algorithms/slope of line|إيجاد ميل الخط المستقيم]]==== | ||
| + | تحسب هذه الخوارزمية مقدار ميل الخطّ المستقيم. | ||
| + | ====[[Algorithms/three points colinear|التحقق من وقوع ثلاث نقاط على استقامة واحدة]]==== | ||
| + | تتحقق هذه الخوارزمية من وقوع ثلاث نقاط على استقامة واحدة (colinear). | ||
| + | ====[[Algorithms/equation plane passing 3 points|إيجاد معادلة المستوى الذي يمرّ عبر ثلاث نقاط]]==== | ||
| + | تحسب هذه الخوارزمية معادلة المستوى الذي يمرّ عبر ثلاث نقاط معرّفة بإحداثياتها. | ||
| + | ===المثلثات=== | ||
| + | ====[[Algorithms/point inside triangle|التحقق من أنّ نقطة معينة موجودة داخل المثلث]]==== | ||
| + | تتحقق هذه الخوارزمية من وجود النقطة المعطاة بإحداثياتها (لتكن P) داخل المثلث الذي تحدده أحداثيات أركانه. | ||
| + | ====[[Algorithms/triangle area|إيجاد مساحة المثلث]]==== | ||
| + | تحسب هذه الخوارزمية مساحة المثلث بطرق متعددة. | ||
| + | ====[[Algorithms/Algorithms/equilateral triangle area|إيجاد مساحة ومحيط مثلث متساوي الأضلاع]]==== | ||
| + | تحسب هذه الخوارزمية مساحة المثلث متساوي الأضلاع ومحيطه. | ||
| + | ====[[Algorithms/isosceles triangle area|إيجاد ارتفاع ومساحة مثلث متساوي الساقين]]==== | ||
| + | تحسب هذه الخوارزمية مساحة المثلث متساوي الساقين وارتفاعه. | ||
| + | ===المربعات والمستطيلات=== | ||
| + | ====[[Algorithms/rectangle overlap|التحقق من تداخل مستطيلين]]==== | ||
| + | تتحقق هذه الخوارزمية ممّا إذا كان المستطيلان المعطيان متداخلين مع بعضهما البعض أم لا. | ||
| + | ====[[Algorithms/rectangle area|إيجاد مساحة ومحيط المستطيل]]==== | ||
| + | تحسب هذه الخوارزمية مساحة المستطيل ومحيطه. | ||
| + | ====[[Algorithms/square area|إيجاد مساحة المربع]]==== | ||
| + | تحسب هذا الخوارزمية مساحة المربع. | ||
| + | ===الدوائر=== | ||
| + | ====[[Algorithms/circle area|مساحة الدائرة]]==== | ||
| + | مجموعة من الخوارزميات التي تحسب مساحة الدائرة، ومساحة الدائرة المحيطة بمربع، ومساحة مقطع من الدائرة. | ||
| + | ====[[Algorithms/check point on sector|التحقق من وجود نقطة معينة في قطاع الدائرة]]==== | ||
| + | تتحقق هذه الخوارزمية من وجود النقطة المعطاة في قطاع الدائرة. | ||
| + | ====[[Algorithms/arc length|إيجاد طول القوس]]==== | ||
| + | تحسب هذه الخوارزمية طول القوس الناشئ على محيط الدائرة من زاوية معلومة. | ||
| + | ===أشكال ثلاثية الأبعاد=== | ||
| + | ====[[ِAlgorithms/distance 2 points on earth|إيجاد المسافة بين نقطتين على سطح الكرة الأرضية]]==== | ||
| + | تحسب هذه الخوارزمية المسافة الفاصلة بين نقطتين على سطح الكرة الأرضية. | ||
| + | ====[[Algorithms/sphere volume surface area|إيجاد الحجم والمساحة السطحية للكرة]]==== | ||
| + | تحسب هذه الخوارزمية حجم الكرة ومساحتها السطحية. | ||
| + | ====[[Algorithms/cube volume surface area|إيجاد الحجم والمساحة السطحية للمكعب]]==== | ||
| + | تحسب هذه الخوارزمية حجم المكعب ومساحته السطحية. | ||
| + | ====[[Algorithms/divide cuboid cubes|تقسيم مكعب إلى مكعبات بأقصى حجم ممكن]]==== | ||
| + | المطلوب في هذه الخوارزمية هو تقسيم مكعب معروف الطول والعرض والارتفاع إلى أقل عدد ممكن من المكعبات بشرط أن تكون المكعبات كلها ذات حجم واحد وأن يصل مجموع أحجامها إلى أقصى قيمة ممكنة. | ||
| + | == [[Algorithms/Bitwise Algorithms|خوارزميات الأعداد الثنائية]] == | ||
| + | تستخدم خوارزميات الأعداد الثنائية (البتات) Bitwise Algorithms لتنفيذ عمليات على مستوى البت bit-level أو لإجراء تعديلات على البتات وبطرق مختلفة. | ||
| + | ===[[Algorithms/add one|زيادة عدد بمقدار واحد دون استخدام العوامل]]=== | ||
| + | تضيف هذه الخوارزمية العدد <code>1</code> على العدد المعطى دون استخدام أيٍّ من العوامل الرياضية مثل <code>‘+’, ‘-‘, ‘*’, ‘/’, ‘++’, ‘–‘</code>. | ||
| + | ===[[Algorithms/opposite signs|التحقق من كون رقمين صحيحين يحملان إشارتين متعاكستين]]=== | ||
| + | تتحقّق هذه الخوارزمية ممّا إذا كان رقمان صحيحان يمتلكان إشارتين مختلفتين دون استخدام أيٍّ من العوامل الرياضية. | ||
| + | ===[[Algorithms/find unique number|العثور على العنصر الفريد في المصفوفة]]=== | ||
| + | تعثر هذه الخوارزمية على العنصر الفريد في مصفوفة تضمّ عناصر تتكرر ثلاث مرّات. | ||
| + | ===[[Algorithms/swap bits|تبديل البتات في عدد معين]]=== | ||
| + | تبدّل هذه الخوارزمية بين موقعين (من الجانب الأيمن) في التمثيل البياني للعدد المعطى بشرط عدم حصول تداخل بين مجموعتي البتات، ثم تعيد النتيجة. | ||
| + | ===[[Algorithms/bits rotation|تدوير البتات]]=== | ||
| + | تدوير البتات Bit Rotation (أو الإزاحة الدائرية circular shift) هي عملية مشابهة لإزاحة البتات باستثناء أنّ البتات التي تخرج من أحد الأطراف تعود مرة أخرى من الطرف الآخر. | ||
| + | ===[[Algorithms/total set bits|تعداد البتات المعينة الكلية في الأعداد من 1 إلى العدد المعطى]]=== | ||
| + | هناك عدة طرق لحساب مجموع عدد البتات المعينة في التمثيل الثنائي لجميع الأعداد بدءًا من <code>1</code> وانتهاءً بالعدد المعطى <code>n</code>. | ||
| + | ===[[Algorithms/count set bits|عدّ البتات المعينة في عدد صحيح]]=== | ||
| + | المطلوب في هذه المسألة هو عد البتات المعيّنة (التي تحمل القيمة <code>1</code>) في التمثيل الثنائي للعدد الصحيح المعطى. | ||
| + | ===[[Algorithms/add subtract no operator|إجراء عمليتي الجمع والطرح دون استخدام العوامل الحسابية]]=== | ||
| + | يمكن إجراء عمليتي الجمع والطرح على الأعداد الصحيحة دون استخدام العوامل وذلك بالتعامل مع التمثيلات الثنائية لهذه الأعداد. | ||
| + | ===[[Algorithms/compare no operator|مقارنة عددين صحيحن دون استخدام عوامل المقارنة]]=== | ||
| + | المطلوب في هذه المسألة هو عقد مقارنة بين عددين صحيحن دون استخدام أيٍّ من عوامل المقارنة. | ||
| + | ===[[Algorithms/max min 2 numbers|حساب العدد الأكبر أو الأصغر بين عددين صحيحين دون استخدام التفريع]]=== | ||
| + | تكون عملية التفريع branching مكلفة في بعض الحالات النادرة على بعض الأجهزة؛ لذا فإنّ عملية إيجاد العدد الأكبر أو الأصغر بين عددين باستخدام التفريع ستكون عملية بطيئة. | ||
| + | ===[[Algorithms/min 3 numbers|إيجاد العدد الأصغر من بين ثلاثة أعداد دون استخدام عوامل المقارنة]]=== | ||
| + | المطلوب في هذه المسألة هو إيجاد العدد الأصغر من بين ثلاثة أعداد دون استخدام عوامل المقارنة. | ||
| + | ===[[Algorithms/abs value|حساب القيمة المطلقة لعدد صحيح دون استخدام التفريع]]=== | ||
| + | القيمة المطلقة لعدد معين هي القيمة غير السالبة لذلك العدد دون النظر إلى إشارته، ويرمز لها بالرمز <code>|x|</code>. | ||
| + | ===[[Algorithms/divide numbers no operators|إيجاد ناتج قسمة عددين صحيحين دون استخدام عوامل الضرب والقسمة وباقي القسمة]]=== | ||
| + | المطلوب في هذه المسألة هو إيجاد حاصل قسمة عدد صحيح على عدد صحيح آخر دون استخدام عوامل الضرب والقسمة وباقي القسمة <code>mod</code>. | ||
== [[Algorithms/Randomized Algorithms|الخوارزميات العشوائية]] == | == [[Algorithms/Randomized Algorithms|الخوارزميات العشوائية]] == | ||
الخوارزمية العشوائية هي الخوارزمية التي تستخدم عددًا عشوائيًا لتقرّر الخطوة التالية في سير عملها. | الخوارزمية العشوائية هي الخوارزمية التي تستخدم عددًا عشوائيًا لتقرّر الخطوة التالية في سير عملها. | ||
| + | |||
| + | == [[Algorithms/Recursion|التعاود]] == | ||
| + | تسمى العملية التي تستدعي الدالة فيها نفسها استدعاءً مباشرًا أو غير مباشر بالتعاود recursion، وتسمى هذه الدالة بالدالة التعاودية recursive function. | ||
[[تصنيف: الخوارزميات]] | [[تصنيف: الخوارزميات]] | ||
| + | {{#seo: | ||
| + | description=شرح الخوارزميات - Algorithms باللغة العربية مدعّم بالأمثلة ضمن توثيق موسوعة حسوب الكامل وعالي الجودة لمختلف لغات البرمجة وتقنيات الويب والجوال. | ||
| + | }} | ||
المراجعة الحالية بتاريخ 05:42، 6 يوليو 2023
الخوارزمية Algorithm هي مجموعة من التعليمات البسيطة والدقيقة والواضحة والمحددة والتى يراد بها الوصول إلى هدف معين، وبتعبير أبسط يمكن القول أنّ الخوارزمية هي مجموعة من العمليات الحاسوبية التي تأخذ عددًا من المدخلات وتنتج قيمة أو مجموعة من القيم التي تحوّل المدخلات إلى مخرجات.
وتنسب كلمة (خوارزمية) إلى عالم الرياضيات المسلم محمد بن موسى الخوارزمي صاحب كتاب (الكتاب المختصر في الجبر والمقابلة).
تقدّم الخوارزميات حلولًا لمسائل كثيرة ومتنوعة منها:
- أحرز مشروع الجينوم البشري تقدّمًا هائلًا في تشخيص جينات الإنسان التي يصل عددها إلى 100,000 جين وتحديد تسلسل 3 بلايين من الأزواج الكيميائية التي تشكّل الدنا البشري، وتحتاج عملية تخزين هذه البيانات وتحليلها والتعامل معها إلى خوارزميات معقدة.
- حماية خصوصية المستخدم ومعلوماته الشخصية مثل رقم بطاقة الائتمان وكلمات المرور وغيرها من الأمور الضرورية في مجال التجارة الإلكترونية، وتستند تقنيات التشفير وتعمية البيانات على خوارزميات رياضية وعلى نظرية الأرقام.
- تستخدم الخرائط الإلكترونية خوارزميات خاصة لتحديد المسافة الأقصر بين نقطتين يختارهما المستخدم على الخريطة.
- 57 ساعة فيديو تدريبية
- من الصفر دون الحاجة لخبرة مسبقة
- شهادة معتمدة من أكاديمية حسوب
- متابعة أثناء الدورة من فريق مختص
بنى المعطيات
بنى المعطيات Data Structures هي الطريقة المتبعة في ترتيب البيانات في الحاسوب بحيث يمكن استخدامها بفعالية، والهدف من بنى المعطيات هو اختزال المساحة والتعقيد الزمني المطلوب للمهام المختلفة.
بنى المعطيات الخطية
المصفوفات
تستخدم المصفوفات في تخزين العناصر المتجانسة في مواقع متجاورة، ويجب تحديد حجم المصفوفة قبل تخزين البيانات فيها.
القوائم المترابطة
يكون كل عنصر في القائمة المترابطة كائنًا بحد ذاته، ويتكون كل عنصر (أو ما يعرف كذلك بالعقدة) من جزئين: البيانات وإشارة إلى العقدة اللاحقة.
هناك عدة أنواع للقوائم المترابطة منها:
القوائم المترابطة المفردة
في هذا النوع من القوائم المترابطة تخزّن كل عقدة موقع العقدة اللاحقة أو تشير إليه، وتشير العقدة الأخيرة في القائمة المترابطة إلى القيمة NULL.
القوائم المترابطة المزدوجة
تمتلك كل عقدة في هذا النوع من القوائم إشارتين، تشير واحدة منهما إلى العقدة التالية والأخرى إلى العقدة السابقة.
القوائم المترابطة الدائرية
ترتبط جميع العقد في هذا النوع من القوائم بعضها ببعض لتشكّل دائرة، ولا وجود لقيمة NULL في نهاية القائمة.
المكادس
الكدس Stack أو LIFO (يدخل أخيرًا، يخرج أوّلًا اختصار last in, first out) هو من بنى المعطيات المجردة والتي تكون على هيئة مجموعة من العناصر التي يمكن أن نؤدي عمليتين أساسيتين عليها وهما عملية إضافة العنصر push وحذف العنصر pop. تجري هاتان العمليتان في المكادس من جهة واحدة وهي قمّة المكدس.
الأرتال
الرتل Queue أو FIFO (يدخل أولًا، يخرج أولًا اختصار first in, first out) هو من بنى المعطيات المجردة والتي تكون على هيئة مجموعة من العناصر التي يمكن أن نؤدي عليها عمليتين أساسيتين هما: إضافة العنصر enqueue وإزالة العنصر dequeue.
بنى المعطيات الهرمية
الأشجار الثنائية
الأشجار الثنائية هي من بنى المعطيات الهرمية، والشجرة الثنائية هي شجرة بيانات تمتلك كل عقدة فيها على عقدتي أبناء كحدّ أقصى، وتسمّيان بالابن الأيمن والابن الأيسر.
أشجار البحث الثنائية
شجرة البحث الثنائية Binary Search Tree هي شجرة ثنائية تمتلك الخصائص الإضافية التالية:
- الشجرة الفرعية اليسرى تتضمن عقدًا تكون مفاتيحها أقل من مفاتيح العقدة التي تتفرع منها.
- الشجرة الفرعية اليمنى تتضمن عقدًا تكون مفاتيحها أكبر من مفاتيح العقدة التي تتفرع منها.
- يجب أن تكون الأشجار الفرعية جميعها أشجار بحث ثنائية.
شجرة البادئات
شجرة البادئات (Prefix tree وتعرف أيضًا بالشجرة الرقمية digital tree والتراي Trie) هي بنية معطيات فعالة لاسترجاع المعلومات Information reTrieval data structur. تساعد شجرة البادئات على تقليص التعقيد الزمني لعمليات البحث إلى حدود معقولة.
الكومات
الكومة Heap نوع خاص من بنى المعطيات الشجرية والتي تكون فيها شجرة البيانات شجرة بيانات كاملة complete.
دالة التقطيع
دالة التقطيع Hashing Function هي دالة تحول مفتاحًا كبيرًا إلى عدد صحيح ذي قيمة أصغر ويستخدم كموقع index في جدول التقطيع.
الرسم البياني
يضمّ الرسم البياني Graph المكونات التالية:
- مجموعة محددة من الرؤوس vertices والتي تسمى كذلك بالعقد nodes.
- مجموعة محددة من أزواج مرتّبة وتكون بالهيئة (u,v) وتسمى بالأضلاع edges.
تحليل الخوارزميات
هناك الكثير من الأمور المهمة التي يجب الاعتناء بها عند كتابة الخوارزميات منها الأمان وسهولة الاستخدام والقدرة على التطوير وغيرها، ولكنّ الأهم من كلّ ذلك هو أداء الخوارزمية؛ والسبب في ذلك هو أنّ كل ما سبق هو نتيجة حتمية لأداء الخوارزمية.
أساليب الخوارزميات
أساليب الخوارزميات Algorithm Paradigms هي مجموعة من النماذج وأطر العمل التي يستند عليها في بناء وتصميم مجموعة معينة من الخوارزميات.
القوة الغاشمة
هذا الأسلوب هو الأبسط Naive ويعتمد على حل المسألة المطروحة بطريقة مباشرة.
الخوارزميات الجشعة
الخوارزميات الجشعة هي إحدى أساليب الخوارزميات التي تصل إلى الحل خطوة فخطوة وذلك بالحرص على أن تقدّم الخطوة التالية أعظم فائدة ممكنة في طريق الوصول إلى الحل
البرمجة الديناميكية
يمكن تعريف البرمجة الديناميكية بأنّها عملية تحسين تُجرى على العمليات التعاودية، بمعنى أنّه يمكن استخدام البرمجة الديناميكية في أيّ مكان تظهر فيها استدعاءات تعاودية متكررة تستخدم المدخلات عينها. وتتلخّص عملية التحسين في تخزين النتائج التي نحصل عليها من المشاكل الفرعية وبهذا تنتفي الحاجة إلى إعادة حساب تلك النتائج في وقت لاحق.
فرق تسد
يقسِّم نموذج فرِّق تسد المسألة إلى مسائل فرعية تشبه المسألة الأصلية، ويقدّم حلولًا للمسائل الفرعية بطريقة تعاودية، ثم يدمج حلول المسائل الفرعية وذلك لتقديم حلٍّ للمسألة الأصلية.
التعقب الخلفي
يستخدم نموذج التعقب الخلفي في حلّ المسائل بطريقة تعاودية محاولًا بناء الحلّ تصاعديًا قطعة قطعة، وحذف الحلول التي تفشل في تحقيق القيود المفروضة من قبل المسألة في أي وقت (يقصد بالوقت هنا الوقت المستغرق للوصول إلى أي مرحلة في شجرة البحث).
خوارزميات البحث
تتحقق خوارزميات البحث من وجود عنصر معين أو تعيد عنصرًا معيّنًا من بنية المعطيات التي يكون العنصر مخزّنًا فيها.
البحث الخطي
البحث الخطّي Linear Search من أبسط خوارزميات البحث إذ أنّها تمر على عناصر المصفوفة واحدًا تلو الآخر بحثًا عن العنصر المطلوب.
البحث الثنائي
تبحث خوارزمية البحث الثنائي Binary Search عن عنصر معين في مصفوفة مرتبة وذلك بتقسيمها باستمرار إلى نصفين والتحقق من وجود العنصر المراد البحث عنه في كلّ نصفٍ إلى أن تعثر على العنصر أو تصل إلى مصفوفة فارغة.
البحث القفزي
تتحقق خوارزمية البحث القفزي Jump Search (تعرف كذلك بخوارزمية البحث الكتلي Block Search) من عدد أقل من العناصر (مقارنة بالبحث الخطي) وذلك بالقفز عبر عناصر المصفوفة بخطوات ثابتة، بمعنى تجاوز بعض العناصر عوضًا عن البحث فيها كلّها.
البحث الاستكمالي
تعدّ خوارزمية البحث الاستكمالي Interpolation Search تحسينًا على البحث الثنائي في بعض الحالات، إذ تكون القيم موزّعة بانتظام في مصفوفة مرتبة فتجري هذه الخوارزمية عملية التحقّق في مواقع مختلفة بالاعتماد على قيمة المفتاح المراد البحث عنه.
البحث الأسّي
تقسّم خوارزمية البحث الأسّي Exponential Search المصفوفة التي يجري البحث فيها إلى مصفوفات فرعية يزداد عدد العناصر فيها ازديادًا أسّيًا (1, 2, 4, 8.... وهكذا إلى حين الوصول إلى مصفوفة جزئية يكون فيها العنصر الأخير أكبر من العنصر المطلوب.
خوارزميات الترتيب
خوارزميات الترتيب Sorting Algorithms هي خوارزميات تستخدم لإعادة ترتيب مصفوفة معطاة أو قائمة من العناصر بالاعتماد على عامل مقارنة معيّن. يُستخدم عامل المقارنة لتحديد ترتيب العناصر الجديد في بنية المعطيات المراد إعادة ترتيب عناصرها.
الترتيب بالفقاعات
خوارزمية الترتيب بالفقاعات Bubble Sort هي أبسط خوارزميات الترتيب والتي تعمل على تبديل مواقع العناصر المتجاورة إن كان ترتيبها خاطئًا.
الترتيب بالتحديد
ترتّب خوارزمية الترتيب بالتحديد selection sort المصفوفة عن طريق العثور على أصغر عنصر (بافتراض أنّ الترتيب سيكون ترتيبًا تصاعديًا) في الجزء غير المرتّب من المصفوفة ووضعه في بدايتها.
الترتيب بالإدراج
الترتيب بالإدراج Insertion Sort من خوارزميات الترتيب البسيطة التي تعمل بنفس الطريقة التي ترتّب فيها أوراق اللعب يدويًا.
الترتيب بالدمج
تقسم خوارزمية الترتيب بالدمج Merge Sort المصفوفة المدخلة إلى نصفين، ثم تستدعي الخوارزمية نفسها على هذين النصفين ثم تدمج نصفي المصفوفة المرتبين بعضهما ببعض.
الترتيب السريع
تنتقي عنصرًا من عناصر المصفوفة وتجعله محورًا pivot ثمّ تقسّم المصفوفة المعطاة حول ذلك العنصر.
الترتيب بالكومة
تستند خوارزمية الترتيب بالكومة Heap Sort على الكومة الثنائية Binary Heap، وهي مشابهة لخوارزمية الترتيب بالتحديد إذ نختار في البداية العنصر الأكبر في المصفوفة ونضعه في نهاية المصفوفة، وتعاد العملية على بقية العناصر.
الترتيب بالعد
تعمل هذه الخوارزمية عن طريق حساب عد العناصر التي تمتلك قيمة مفتاح فريدة، ثم حساب موقع كل عنصر في التسلسل المخرج.
الترتيب بالجذر
تتلخص هذه الخوارزمية بإجراء ترتيب للعناصر رقمًا تلو الآخر بدءًا من الرقم الأقل أهمية إلى الرقم الأكثر أهمية.
خوارزمية شِل للترتيب
ترتب خوارزمية شِل المصفوفة بالنسبة لقيمة كبيرة من h ، ثم تستمر في تقليص قيمة h إلى حين الوصول إلى 1.
الترتيب بالدلو
تظهر فائدة خوارزمية الترتيب بالدلو Bucket Sort عندما تكون المدخلات موزّعة بانتظام ضمن نطاق معيّن.
الترتيب ببرج الحمام
تلائم خوارزمية الترتيب ببرج الحمام Pigeonhole sort قوائم العناصر التي يكون فيها عدد العناصر وعدد القيم المفتاحية الممكنة possible key values متساويين تقريبًا.
الترتيب بالتدوير
مبدأ عمل خوارزمية الترتيب بالتدوير Cycle sort هو تدوير مواقع العناصر في المصفوفة إلى حين الحصول على مصفوفة مرتبة بالكامل.
الترتيب بالشجرة
تعتمد خوارزمية الترتيب بالشجرة Tree Sort في عملها على شجرة البحث الثنائية، إذ أنّها تصنع شجرة بحث ثنائية في البداية من العناصر المتوفّرة في المصفوفة المدخلة ثم تنفّذ عملية تنقل وسطي للحصول على العناصر مرتّبة.
الترتيب المخلوط
تتنقّل خوارزمية الترتيب بالفقاعات عبر عناصر المصفوفة من جهة اليسار دائمًا وتحرّك أكبر العناصر إلى موقع الصحيح في الدورة الأولى ثم تحرّك ثاني أكبر عنصر في الدورة الثانية وهكذا دواليك. أما خوارزمية الترتيب المخلوط Cocktail sort فتتنقّل عبر عناصر المصفوفة باتجاهين بالتناوب.
الترتيب فردي-زوجي (الترتيب بالقرميد)
خوارزمية الترتيب فردي-زوجي Odd-Even Sort (أو الترتيب بالقرميد Brick sort) هي تحوير على خوارزمية الترتيب بالفقاعات. تقسم هذه الخوارزمية إلى قسمين القسم الفردي والقسم الزوجي. تستمر الخوارزمية في عملها إلى أن تصبح جميع العناصر في المصفوفة مرتبة
خوارزميات البحث عن النصوص
تعدّ خوارزميات البحث عن النصوص (وتسمّى كذلك بخوارزميات البحث عن الأنماط Pattern Searching) جزءًا من خوارزميات النصوص String Algorithms، وتساعد هذه الخوارزميات في البحث عن سلسلة نصية معيّنة في سلسلة نصية أخرى.
الخوارزمية البسيطة
تنتقل الخوارزمية عبر جميع الحروف في السلسلة النصية واحدًا تلو الآخر بحثًا عن التسلسل الذي يطابق النمط المعطى.
خوارزمية KMP
تعالج الخوارزمية النمط المراد البحث عنه لتجنّب تكرار البحث عن أنماط جرى البحث عنها في الخطوات السابقة.
خوارزمية رابين-كارب
تحرّك خوارزمية رابين-كارب Rabin-Karp النمط الذي تبحث عنه عبر السلسلة النصية موقعًا تلو الآخر وتطابق قيمة التقطيع Hash value للنمط المعطى مع قيمة التقطيع لجزء السلسلة الذي تجري معه المقارنة
خوارزمية بوير-مور
تعتمد خوارزمية بوير-مور Boyer-Moore على الأسلوبين: استكشاف الحروف السيئة، واستكشاف اللاحقة الجيدة.
خوارزميات الرسوم البيانية
تقدّم خوارزميات الرسوم البيانية Graph Algorithms طرقًا فعالة للكشف عن الدورات في الرسوم البيانية، إلى جانب إيجاد الشجرة الممتدة الصغرى والمسار الأقصر وغيرها.
خوارزمية كروسكال
تعثر خوارزمية كروسكال Kruskal على الشجرة الممتدة الصغرى في الرسم البياني المعطى، بترتيب الأضلاع تصاعديًا ثم اختيار الضلع الأصغر.
خوارزمية برم
تعثر خوارزمية Prim على الشجرة الممتدة الصغرى في الرسم البياني المعطى، وتبدأ بشجرة ممتدة فارغة وتعتمد في عملها على مجموعتين من الرؤوس.
خوارزمية بوروفكا
تعدّ خوارزمية بوروفكا أقدم خوارزمية لإيجاد الشجرة الممتدة الصغرى وقد وضعها بوروفكا سنة 1926م، قبل اختراع الحواسيب بفترة طويلة، وقد نشرت هذه الخوارزمية كطريقة لبناء شبكة فعّالة من التمديدات الكهربائية.
خوارزمية بِلمان - فورد
تمتاز هذه الخوارزمية بقدرتها على إيجاد المسار الأقصر في الرسوم البيانية التي تكون فيها أوزان الأضلاع ذات قيم سالبة.
خوارزمية ديكسترا
تنتج خورازمية ديكسترا Dijkstra شجرة المسار الأقصر بدءًا من المصدر المعطى كجذر لهذه الشجرة.
خوارزمية فلويد وارشال
تقدّم خوارزمية فلويد-وارشال Floyd-Warshall حلًّا لمشكلة المسار الأقصر لجميع الأزواج.
خوارزمية كان للترتيب الطوبولوجي
تجري خوارزمية كان عملية الترتيب الطوبولوجي باستخدام رتل.
الخوارزميات الرياضية
تعنى الخوارزميات الرياضية بإيجاد أسرع الحلول الممكنة للمسائل الرياضية المختلفة باستخدام قوانين وعلاقات رياضية معروفة.
القاسم المشترك الأكبر
القاسم المشترك الأكبر (Greatest Common Divisor GCD) لعددين هو أكبر يقسم هذين العددين قسمة تامة.
المضاعف المشترك الأصغر
المضاعف المشترك الأصغر (Least Common Multiple) لعددين هو أصغر عدد يمكن قسمته بواسطة كلا العددين.
العوامل الأولية
تحليل العدد إلى عوامله الأولية يعني إيجاد الأعداد الأولية التي يكون حاصل ضربها ببعضها مساويًا للعدد الأصلي.
الجذر التربيعي
تحسب هذه الخوارزميات الجذر التربيعي للعدد المعطى.
الجذر التكعيبي
تحسب هذه الخوارزمية الجذر التكعيبي للعدد المعطى.
عدد سميث
عدد سميث Smith Number هو عدد مركّب تكون مجموع أرقامه مساوية لمجموع الأرقام في عوامله الأولية.
الأعداد الكاتالانية
الأعداد الكاتالانية Catalan Numbers هي متتالية من الأعداد الطبيعية والتي تظهر في عدد من مسائل العدّ؟
إيجاد قواسم عدد طبيعي
قواسم العدد الطبيعي هي الأعداد التي يقبل القسمة عليها دون باقٍ.
أعداد فيبوناتشي
تشكّل أعداد فيبوناتشي Fibonacci numbers متتالية تدعى بمتتالية فيبوناتشي Fibonacci Sequence يكون كل عدد فيها مساويًا لمجموع العددين الذين يسبقانه في المتتالية، وتبدأ المتتالية بالعددين 0 و 1.
مضروب العدد
مضروب عدد صحيح غير سالب هو حاصل ضرب جميع الأعداد الصحيحة التي تكون أصغر من العدد المعطى أو تساويه.
الأعداد الأولية
العدد الأولي هو عدد يكون أكبر من 1 ويقبل القسمة على 1 وعلى نفسه فقط.
متتالية لاعب الخفة
متتالية لاعبة الخفة Juggler Sequence هي متتالية من الأعداد الصحيحة التي يكون فيها العنصر الأول عددًا صحيحًا موجبًا وتتربط الأعداد فيما بينها بعلاقة تعاودية. تتميّز هذه المتتالية بأن الأعداد فيها تبدأ بالصعود تدريجيًا لتصل إلى قمّة معينة ثم تبدأ بعدها بالنقصان تدريجيًا، وأنّ هذه السلسلة تنتهي بالعدد 1 دائمًا.
قابلية القسمة
تستخدم هذه الخوارزميات مجموعة من الخصائص والعلاقات الرياضية لمعرفة قابلية قسمة عدد معين على الأعداد من 3 إلى 9.
إيجاد أقل فارق بين مجموعتين فرعيتين
تقسم هذه الخوارزمية مجموعة معين من الأعداد الصحيحة إلى مجموعتين فرعتين بطريقة يكون فيها الفارق بين مجموع عناصر المجموعة الأولى والثاني أقل ما يمكن.
حساب مجموع كل العناصر من كل المجاميع الفرعية الممكنة
تحسب هذه الخوارزمية مجموع جميع العناصر المتكوّنة من كل المجموعات الفرعية التي يمكن تكوينها من مجموعة تضمّ n من الأعداد الطبيعية.
مجموعة القوة
مجموعة القوة Power Set هي المجموعة التي تضمّ جميع المجموعات المتفرّعة من المجموعة الأصلية.
التحويل بين أنظمة الأعداد
هناك طرق عدة لتمثيل الأعداد وذلك بالاعتماد على الأساس base، ويشيع استخدام أربعة أنظمة هي النظام الثنائي Binary، والثماني Octal، والعشري Decimal، والسداسي عشر Hexadecimal.
التعابير المرتبة وسطيًا وقبليًا وبعديًا
هناك ثلاث طرق لترتيب العوامل والمعاملات في التعابير الرياضية للإشارة إلى العمليات التي تنال الأولوية عند معالجة التعبير الرياضي من قبل المصرّفات Compilers. هذه الطرق هي: الترتيب الوسطي infix والقبلي prefix والبعدي postfix.
الخوارزميات الهندسية
تعنى الخوارزميات الهندسية Geometric Algorithms بإيجاد الحلول المناسبة للمسائل الهندسية المختلفة.
الخطوط والقطع المستقيمة
تقاطع قطعتين مستقيمتين
تتحقق هذه الخوارزمية من تقاطع قطعتين مستقيمتين.
إيجاد نقطة تقاطع خطين مستقيمين
تعثر هذه الخوارزمية على نقطة تقاطع خطين مستقيمين.
إيجاد الخط الذي يمرّ بنقطتين
تعثر هذه الخوارزمية على معادلة الخط المستقيم الذي يمرّ بنقطتين في مستوى الإحداثيات.
التحقق من مرور الخط المستقيم عبر نقط الأصل
تتحقق هذه الخوارزمية من مرور الخط المستقيم ذي الإحداثيات (x1, y1) و (x2, y2) عبر نقطة الأصل ذات الإحداثيات (0,0).
إيجاد نقطة الوسط في خطّ مستقيم
تعثر هذه الخوارزمية على نقطة الوسط لخطّ مستقيم يبدأ من النقطة (x1, y1) وينتهي بالنقطة (x2, y2).
إيجاد ميل الخط المستقيم
تحسب هذه الخوارزمية مقدار ميل الخطّ المستقيم.
التحقق من وقوع ثلاث نقاط على استقامة واحدة
تتحقق هذه الخوارزمية من وقوع ثلاث نقاط على استقامة واحدة (colinear).
إيجاد معادلة المستوى الذي يمرّ عبر ثلاث نقاط
تحسب هذه الخوارزمية معادلة المستوى الذي يمرّ عبر ثلاث نقاط معرّفة بإحداثياتها.
المثلثات
التحقق من أنّ نقطة معينة موجودة داخل المثلث
تتحقق هذه الخوارزمية من وجود النقطة المعطاة بإحداثياتها (لتكن P) داخل المثلث الذي تحدده أحداثيات أركانه.
إيجاد مساحة المثلث
تحسب هذه الخوارزمية مساحة المثلث بطرق متعددة.
إيجاد مساحة ومحيط مثلث متساوي الأضلاع
تحسب هذه الخوارزمية مساحة المثلث متساوي الأضلاع ومحيطه.
إيجاد ارتفاع ومساحة مثلث متساوي الساقين
تحسب هذه الخوارزمية مساحة المثلث متساوي الساقين وارتفاعه.
المربعات والمستطيلات
التحقق من تداخل مستطيلين
تتحقق هذه الخوارزمية ممّا إذا كان المستطيلان المعطيان متداخلين مع بعضهما البعض أم لا.
إيجاد مساحة ومحيط المستطيل
تحسب هذه الخوارزمية مساحة المستطيل ومحيطه.
إيجاد مساحة المربع
تحسب هذا الخوارزمية مساحة المربع.
الدوائر
مساحة الدائرة
مجموعة من الخوارزميات التي تحسب مساحة الدائرة، ومساحة الدائرة المحيطة بمربع، ومساحة مقطع من الدائرة.
التحقق من وجود نقطة معينة في قطاع الدائرة
تتحقق هذه الخوارزمية من وجود النقطة المعطاة في قطاع الدائرة.
إيجاد طول القوس
تحسب هذه الخوارزمية طول القوس الناشئ على محيط الدائرة من زاوية معلومة.
أشكال ثلاثية الأبعاد
إيجاد المسافة بين نقطتين على سطح الكرة الأرضية
تحسب هذه الخوارزمية المسافة الفاصلة بين نقطتين على سطح الكرة الأرضية.
إيجاد الحجم والمساحة السطحية للكرة
تحسب هذه الخوارزمية حجم الكرة ومساحتها السطحية.
إيجاد الحجم والمساحة السطحية للمكعب
تحسب هذه الخوارزمية حجم المكعب ومساحته السطحية.
تقسيم مكعب إلى مكعبات بأقصى حجم ممكن
المطلوب في هذه الخوارزمية هو تقسيم مكعب معروف الطول والعرض والارتفاع إلى أقل عدد ممكن من المكعبات بشرط أن تكون المكعبات كلها ذات حجم واحد وأن يصل مجموع أحجامها إلى أقصى قيمة ممكنة.
خوارزميات الأعداد الثنائية
تستخدم خوارزميات الأعداد الثنائية (البتات) Bitwise Algorithms لتنفيذ عمليات على مستوى البت bit-level أو لإجراء تعديلات على البتات وبطرق مختلفة.
زيادة عدد بمقدار واحد دون استخدام العوامل
تضيف هذه الخوارزمية العدد 1 على العدد المعطى دون استخدام أيٍّ من العوامل الرياضية مثل ‘+’, ‘-‘, ‘*’, ‘/’, ‘++’, ‘–‘.
التحقق من كون رقمين صحيحين يحملان إشارتين متعاكستين
تتحقّق هذه الخوارزمية ممّا إذا كان رقمان صحيحان يمتلكان إشارتين مختلفتين دون استخدام أيٍّ من العوامل الرياضية.
العثور على العنصر الفريد في المصفوفة
تعثر هذه الخوارزمية على العنصر الفريد في مصفوفة تضمّ عناصر تتكرر ثلاث مرّات.
تبديل البتات في عدد معين
تبدّل هذه الخوارزمية بين موقعين (من الجانب الأيمن) في التمثيل البياني للعدد المعطى بشرط عدم حصول تداخل بين مجموعتي البتات، ثم تعيد النتيجة.
تدوير البتات
تدوير البتات Bit Rotation (أو الإزاحة الدائرية circular shift) هي عملية مشابهة لإزاحة البتات باستثناء أنّ البتات التي تخرج من أحد الأطراف تعود مرة أخرى من الطرف الآخر.
تعداد البتات المعينة الكلية في الأعداد من 1 إلى العدد المعطى
هناك عدة طرق لحساب مجموع عدد البتات المعينة في التمثيل الثنائي لجميع الأعداد بدءًا من 1 وانتهاءً بالعدد المعطى n.
عدّ البتات المعينة في عدد صحيح
المطلوب في هذه المسألة هو عد البتات المعيّنة (التي تحمل القيمة 1) في التمثيل الثنائي للعدد الصحيح المعطى.
إجراء عمليتي الجمع والطرح دون استخدام العوامل الحسابية
يمكن إجراء عمليتي الجمع والطرح على الأعداد الصحيحة دون استخدام العوامل وذلك بالتعامل مع التمثيلات الثنائية لهذه الأعداد.
مقارنة عددين صحيحن دون استخدام عوامل المقارنة
المطلوب في هذه المسألة هو عقد مقارنة بين عددين صحيحن دون استخدام أيٍّ من عوامل المقارنة.
حساب العدد الأكبر أو الأصغر بين عددين صحيحين دون استخدام التفريع
تكون عملية التفريع branching مكلفة في بعض الحالات النادرة على بعض الأجهزة؛ لذا فإنّ عملية إيجاد العدد الأكبر أو الأصغر بين عددين باستخدام التفريع ستكون عملية بطيئة.
إيجاد العدد الأصغر من بين ثلاثة أعداد دون استخدام عوامل المقارنة
المطلوب في هذه المسألة هو إيجاد العدد الأصغر من بين ثلاثة أعداد دون استخدام عوامل المقارنة.
حساب القيمة المطلقة لعدد صحيح دون استخدام التفريع
القيمة المطلقة لعدد معين هي القيمة غير السالبة لذلك العدد دون النظر إلى إشارته، ويرمز لها بالرمز |x|.
إيجاد ناتج قسمة عددين صحيحين دون استخدام عوامل الضرب والقسمة وباقي القسمة
المطلوب في هذه المسألة هو إيجاد حاصل قسمة عدد صحيح على عدد صحيح آخر دون استخدام عوامل الضرب والقسمة وباقي القسمة mod.
الخوارزميات العشوائية
الخوارزمية العشوائية هي الخوارزمية التي تستخدم عددًا عشوائيًا لتقرّر الخطوة التالية في سير عملها.
التعاود
تسمى العملية التي تستدعي الدالة فيها نفسها استدعاءً مباشرًا أو غير مباشر بالتعاود recursion، وتسمى هذه الدالة بالدالة التعاودية recursive function.