الخوارزميات

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

وتنسب كلمة (خوارزمية) إلى عالم الرياضيات المسلم محمد بن موسى الخوارزمي صاحب كتاب (الكتاب المختصر في الجبر والمقابلة).

تقدّم الخوارزميات حلولًا لمسائل كثيرة ومتنوعة منها:

أحرز مشروع الجينوم البشري تقدّمًا هائلًا في تشخيص جينات الإنسان التي يصل عددها إلى 100,000 جين وتحديد تسلسل 3 بلايين من الأزواج الكيميائية التي تشكّل الدنا البشري، وتحتاج عملية تخزين هذه البيانات وتحليلها والتعامل معها إلى خوارزميات معقدة.
حماية خصوصية المستخدم ومعلوماته الشخصية مثل رقم بطاقة الائتمان وكلمات المرور وغيرها من الأمور الضرورية في مجال التجارة الإلكترونية، وتستند تقنيات التشفير وتعمية البيانات على خوارزميات رياضية وعلى نظرية الأرقام.
تستخدم الخرائط الإلكترونية خوارزميات خاصة لتحديد المسافة الأقصر بين نقطتين يختارهما المستخدم على الخريطة.

دورة علوم الحاسوب

62 ساعة فيديو تدريبية
من الصفر دون الحاجة لخبرة مسبقة
شهادة معتمدة من أكاديمية حسوب
متابعة أثناء الدورة من فريق مختص

اشترك الآن

بنى المعطيات

بنى المعطيات 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.