معلومة

2.13: الخوارزميات وهياكل البيانات - علم الأحياء

2.13: الخوارزميات وهياكل البيانات - علم الأحياء


We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

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

سنبدأ بالخوارزميات ، والتي وفقًا لكتاب كلاسيكي حول هذا الموضوع -مقدمة في الخوارزميات بواسطة Thomas H. Cormen و Charles E.Liserson و Ronald L.Revest و Clifford Stein - هم:

أي إجراء حسابي محدد جيدًا يأخذ بعض القيمة ، أو مجموعة من القيم ، كمدخلات وينتج بعض القيمة ، أو مجموعة من القيم ، كإخراج.

بمثل هذا التعريف الواسع ، يمكن تصنيف كل ترميز Python الذي قمنا به بدقة على أنه ممارسة في الخوارزميات. بالمناسبة ، كلمة "خوارزمية" مشتقة من اسم عالم الرياضيات الفارسي الخوارزمي من القرن الثامن ، الذي طور مناهج منهجية لحل المعادلات (من بين إنجازات أخرى). على الرغم من أن معظم الكودات العاملة يمكن وصفها بأنها خوارزمية ، إلا أن الخوارزميات عادة ما تتضمن أكثر من مجرد تجميع البيانات ويتم إقرانها بخوارزمية محددة جيدًا مشاكل، مع توفير مواصفات لماهية المدخلات الصالحة وما هي المخرجات المقابلة التي يجب أن تكون. تتضمن بعض أمثلة المشكلات ما يلي:

  1. نظرا لقائمة الأرقام بترتيب عشوائي ، قم بإعادتها أو نسخة منها بترتيب مرتب. (مشكلة "الفرز".)
  2. نظرا لقائمة الأرقام بالترتيب الفرز ورقم الاستعلامف، إرجاعحقيقيلوفموجود في القائمة وخاطئةإذا لم يكن. (مشكلة "البحث".)
  3. بالنظر إلى خيطين من الطول و، قم بمحاذاةهم مع بعضهم البعض (إدخال شرطات عند الضرورة لجعلها بنفس الطول) لتعظيم النتيجة بناءً على تطابقات الشخصية. (مشكلة "محاذاة السلسلة".)

من الواضح أن بعض المشكلات ، مثل مشكلة محاذاة الأوتار ، لها أهمية خاصة لعلماء الحياة. البعض الآخر ، مثل الفرز والبحث ، موجود في كل مكان. بغض النظر عمن يهتم بالمشكلة ، فإن الخوارزمية الجيدة لحلها يجب أن تفعل ذلك بكفاءة. عادةً ما تعني كلمة "فعال" "في فترة زمنية قصيرة" ، على الرغم من وجود مجموعات البيانات الكبيرة التي تنتجها تقنيات تسلسل الحمض النووي الحديثة ، غالبًا ما تعني أيضًا "استخدام قدر ضئيل من الذاكرة".

تتطلب معظم مشاكل المعلوماتية الحيوية مثل محاذاة السلسلة أساليب معقدة نوعًا ما مبنية من مفاهيم أبسط ، لذلك سنبدأ بالموضوع التمهيدي المعتاد لتصميم الخوارزميات وتحليلها: الفرز. بعد كل ذلك، شخصا ما كان عليك كتابة لغة بايثونمرتبة()تعمل في القوائم ، وتشكل أساسًا جيدًا للدراسة.

ضع في اعتبارك قائمة صغيرة من خمسة أرقام ، بترتيب غير مفروز.

ما الرمز الذي نكتبه لفرز هذه الأرقام؟ مهما كانت ، قد يكون من المنطقي وضعها في دالة تأخذ قائمة غير مرتبة ، وتعيد نسخة منها بترتيب مرتبة (للبقاء متسقًا مع استخدام Python لمبدأ فصل استعلام الأوامر). للبدء ، سنقوم بعمل نسخة من القائمة ، وبعد ذلك سيكون لدينا وظيفة مجرد "إصلاح" بعض الأرقام خارج الترتيب في هذه النسخة من خلال النظر إلى نافذة منزلقة بحجم 2 - أزواج من الأرقام المتجاورة - وتبديل موضعها إذا كانت معطلة.

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

تُعرف خوارزمية الفرز هذه باسم "الفقاعات". بمعنى تقريبي ، كم عدد العمليات التي ستؤديها هذه الخوارزمية ، في أسوأ الحالات ، لقائمة الحجم؟ افترض أن عبارة if تجد دائمًاحقيقي، والأرقام بحاجة للتبديل. في هذه الحالة ، تتطلب كل عملية من الحلقة الداخلية خمس "خطوات زمنية" أو نحو ذلك (أربع مهام ولوالتحقق من). تعمل الحلقة الداخلية مرات (إذا كان هناك الأرقام) ، والتي هي نفسها مكررة مرات في الحلقة الخارجية. خطوة النسخ لإنتاج الجديدc_numsقائمة تستخدم أيضا من الخطوات ، وبالتالي فإن العدد الإجمالي للعمليات الأساسية ، أكثر أو أقل ،

ومع ذلك ، عند تحليل وقت تشغيل الخوارزمية ، فإننا نهتم فقط "بالأشياء الكبيرة".

عند حساب وقت تشغيل الخوارزمية ، فإننا نهتم فقط بأعلى شروط الترتيب ، ونميل إلى تجاهل الثوابت التي لا تتعلق "بحجم" الإدخال. نقول أن وقت التشغيل هو ترتيب من المصطلح الأعلى رتبة (بدون ثوابت) ، والذي نشير إليه بأحرف كبيرة: يكون

نقرأ هذا على أنه "خمسة تربيع ناقص أربعة هو النظام تربيع "أو" خمسة تربيع ناقص أربعة هو كبير أوه تربيع. " نظرًا لأن وقت التشغيل هذا يتحدث عن خوارزمية معينة ، فقد نقول أيضًا "الفقاعات هي الترتيب تربيع. " يشير تدوين Big-O إلى أنه ، تقريبًا ، ستعمل الخوارزمية في الوقت المناسب اقل او يساوي يتم تفسير المعادلة كدالة لحجم الإدخال ، في الحالة الأسوأ (تجاهل الثوابت والمصطلحات الصغيرة).

يفترض تحليل الحالة الأسوأ أننا غير محظوظين مع كل إدخال ، ولكن في كثير من الحالات ، قد تعمل الخوارزمية بشكل أسرع في الممارسة العملية. إذن ، لماذا نقوم بتحليل الحالة الأسوأ؟ أولاً ، يمنح مستخدم الخوارزمية ضمانًا - لا أحد يريد سماع هذا البرنامج قد استخدام قدر معين من الوقت. ثانيًا ، في حين أنه من الممكن أحيانًا إجراء تحليل متوسط ​​الحالة ، فإنه يتطلب معرفة توزيع بيانات الإدخال عمليًا (وهو أمر نادر) أو تقنيات تحليل أكثر تعقيدًا.

لماذا نستخدم تدوين الترتيب لوصف وقت تشغيل الخوارزمية ، وإسقاط المصطلحات الصغيرة والثوابت؟ أولاً ، على الرغم من أننا ذكرنا سابقًا أن كل عملية أساسية هي "خطوة كمبيوتر" واحدة ، فإن هذا ليس صحيحًا حقًا: الخطc_nums [الفهرس + 1] = العدد المتبقييتطلب كلاً من الإضافة والتعيين. ولكن لا أحد يريد حساب كل دورة وحدة معالجة مركزية على حدة ، خاصة إذا كانت النتيجة لن تغير كيفية مقارنة خوارزميتين لمجموعات البيانات الكبيرة ، وهو الغرض الأساسي من تدوين الطلب. إن التخلي عن المصطلحات الثابتة والمصطلحات ذات الترتيب الأدنى له معنى رياضي جيد في هذه الحالات. لمدخلات كبيرة بما يكفي (على سبيل المثال ، الكل أكبر من بعض الحجم) ، حتى المصطلحات التي تبدو وكأنها ستحدث فرقًا كبيرًا ، تبين أنها ليست مهمة ، كما توضح المقارنة الافتراضية التالية.

(من الناحية الفنية في ما سبق هو إساءة للتدوين ؛ يجب أن نقول يكون بناءً على تعريف الترميز.) في هذه الحالة ، أكبر من متي أكبر من 400،024،000 (وهو مثال في هذا المثال).

لذلك ، على الرغم من أن تدوين الترتيب يبدو وكأنه طريقة غامضة للنظر في كفاءة الخوارزمية ، إلا أنها طريقة محددة بدقة ومعقولة للقيام بذلك.[1] نظرًا لأن بعض لغات البرمجة أسرع من غيرها - ولكن فقط بعامل ثابت (ربما يكون كود C المترجم أسرع 100 مرة من Python) - غالبًا ما تتفوق الخوارزمية الجيدة التي يتم تنفيذها بلغة بطيئة على خوارزمية متوسطة يتم تنفيذها بلغة سريعة!

الآن ، وقت تشغيل ليس جيدًا جدًا: الوقت المستغرق لفرز قائمة الأرقام سيزداد تربيعًا مع حجم القائمة.

ليس رائعًا ، ولكن بالنسبة لمشكلة الفرز ، يمكننا تحسين أدائنا ، وسنعود إلى دراسة الخوارزميات والفرز لاحقًا. أولاً ، دعنا نلتف ونتحدث عن طرق شيقة يمكننا من خلالها تنظيم البيانات ، باستخدام المتغيرات والأشياء التي تشير إليها.

هيكل البيانات عبارة عن منظمة لجمع البيانات التي تسمح بشكل مثالي بالوصول السريع والعمليات المعينة على البيانات. لقد رأينا اثنين من هياكل البيانات بالفعل في بايثون: القوائم والقواميس. بالنظر إلى هذا الهيكل ، قد نطرح أسئلة مثل:

  • هل تحتفظ بنية البيانات بعناصرها بترتيب معين (مثل الترتيب المصنف)؟ إذا استخدمنا.ألحق()لإضافة عناصر إلى القوائم ، يتم الاحتفاظ بالقوائم بترتيب إضافة العناصر. إذا أردنا أن تظل القائمة مرتبة ، فسيتعين علينا التأكد من إدراج العناصر الجديدة في المكان الصحيح.
  • كم من الوقت تستغرق إضافة عنصر جديد؟ بالنسبة لقوائم Python ، فإن ملف.ألحق()الطريقة تعمل في الوقت المناسب ، وهو ما يعني أنه يمكن إضافة عنصر واحد إلى النهاية ، والوقت المستغرق لا يعتمد على حجم القائمة. لسوء الحظ ، لن يكون هذا صحيحًا إذا احتجنا إلى الاحتفاظ بالقائمة مرتبة ، لأن الإدراج في المنتصف يتطلب إعادة ترتيب طريقة تخزين البيانات.
  • كم من الوقت يستغرق العثور على أصغر عنصر؟ لأن استخدام.ألحق()يضيف عناصر إلى نهاية القائمة ، ما لم نبقي القائمة مرتبة ، نحتاج إلى البحث في القائمة بأكملها عن أصغر عنصر. هذه العملية تستغرق وقتا ، أين هو طول القائمة. إذا تم فرز القائمة ، فسيستغرق الأمر فقط حان الوقت لإلقاء نظرة على الجزء الأمامي منه.

هناك مقايضات يمكننا القيام بها عند التفكير في كيفية استخدام هياكل البيانات. لنفترض ، على سبيل المثال ، أننا أردنا العثور بسرعة على أصغر عنصر في القائمة ، حتى عند إضافة العناصر إليها. أحد الاحتمالات هو فرز القائمة بعد كل إضافة ؛ إذا فعلنا ذلك ، فسيكون أصغر عنصر دائمًا في الفهرس0للاسترجاع السريع. لكن هذا يتطلب الكثير من العمل ، وسيبدأ إجمالي الوقت المستغرق في الفرز يفوق فوائد الاحتفاظ بالقائمة مرتبة في المقام الأول! والأفضل من ذلك ، يمكننا كتابة دالة تقوم (1) بإدراج العنصر الجديد في النهاية ثم (2) فقاعه للخلف إلى موقعه الصحيح ؛ ستكون هناك حاجة إلى فقاعات واحدة فقط لكل إدخال ، ولكن كل منها عبارة عن ملف العملية (ما لم نتمكن بطريقة ما من ضمان إضافة عناصر كبيرة فقط).

من السهل العثور على العنصر الأصغر ، حيث نعلم أنه موجود دائمًا في الفهرس0.

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

ستحتفظ بنية البيانات الخاصة بنا ، والتي تسمى "قائمة مرتبطة مرتبة" ، بمجموعة من العناصر في ترتيب مرتبة ، وستقوم بعمل إدراج عناصر جديدة في المكان الصحيح بهذا الترتيب. يمكن أن تكون هذه العناصر أعدادًا صحيحة أو عائمة أو سلاسل ، أي شيء يمكن مقارنته بـ<عامل التشغيل (الذي ، تذكر ، يقارن السلاسل بترتيب معجمي ؛ كما تمت مناقشته في الفصول السابقة ، يمكننا حتى تحديد أنواع الكائنات الخاصة بنا التي يمكن مقارنتها مع>من خلال التنفيذ.__ lt __ (),.__ مكافئ __ ()وطرق مماثلة).

لإنجاز هذه المهمة ، سنستخدم الفئات والكائنات بشكل مكثف ، وحقيقة أن المتغير (حتى متغير الحالة) هو اسم يشير إلى كائن.

ستتمثل الإستراتيجية في الحصول على نوعين من الكائنات: الأول ، والذي سنطلق عليه اسملينكدليست، سيكون النوع الرئيسي للكائن الذي ستتفاعل معه برامجنا (يشبه إلى حد كبير تفاعلنا معهكروموسومالأشياء في الفصول السابقة ، بينماSNPالأشياء التي تم التعامل معها من قبلكروموسومأشياء). اللينكدليستالكائن سيكون له طرق مثل.insert_item ()و.get_smallest (). ستكون الكائنات الأخرى من النوعالعقدة، ولكل منها متغير حالةالبند الذاتيالتي ستشير إلى العنصر الذي تم تخزينه من قبل الفردالعقدة. لذلك ، رسم الكائنات في ذاكرة الوصول العشوائي فقط ، لدينا قائمة مرتبطة مرتبة من ثلاثة عناصر (4,7، و9) قد يبدو كالتالي:

(من غير المحتمل أن يتم تنظيم الكائنات بدقة بهذه الطريقة في ذاكرة الوصول العشوائي - فنحن نعرضها في سطر للتوضيح فقط.) تشير الأسهم في هذا الشكل إلى أنه بعد إنشاء عنصر جديدلينكدليستكائن يسمىقائمة البند، هذا المتغير هو اسم يشير إلى كائن ، وإلى كل منهماالعقدةالكائن لديهالبند الذاتيمتغير مثيل يشير إلى كائن "بيانات" من نوع ما ، مثل عدد صحيح أو سلسلة.[2]

الآن ، إذا كانت هذه المجموعة من الكائنات موجودة كما هو موضح ، فلن يكون ذلك مفيدًا. سيكون برنامجنا قادرًا فقط على التفاعل معقائمة البندالكائن ، وفي الحقيقة لا توجد متغيرات تشير إلى الفردالعقدةالكائنات ، لذلك سيتم حذفها عن طريق جمع القمامة.

إليك الحيلة: إذا كان متغير المثيل مجرد متغير (وبالتالي مرجع إلى كائن) ، فيمكننا إعطاء كلالعقدةكائن أself.next_nمتغير المثيل الذي سيشير إلى العقدة التالية في السطر. وبالمثل ، فإنلينكدليستالكائن سيكون لهself.first_nمتغير المثال الذي سيشير إلى المتغير الأول.

الاخيرالعقدةأشياءself.next_nيعود الىلا أحد، عنصر نائب يمكننا استخدامه للسماح للمتغير بالإشارة إلى "لا شيء هنا". في الواقع،لا أحدستكون القيمة الأولية لـself.next_nعندما يتم إنشاء عقدة جديدة ، فسنضطر إلى إضافة طرق لهاget_next_n ()وset_next_n ()التي تسمح لنا بالحصول على ملفالعقدةnext_nمتغير في الإرادة. The LinkedListsأول نسيتم بالمثل تهيئة المتغير كـلا أحدفي المنشئ.

افترض أن لدينا بنية البيانات هذه ، ونريد إضافة الرقم2؛ سيكون هذا العنصر الجديد "الأصغر". للقيام بذلك نحتاج إلى الجريitemlist.insert_item (2)، وستأخذ هذه الطريقة في الاعتبار الأسئلة التالية للتعامل مع جميع الحالات المحتملة لإدراج عنصر (باستخدام عبارات if):

  1. يكونself.first_nيساويلا أحد؟ إذا كان الأمر كذلك ، فإن العنصر الجديد هو ملف فقط عنصرًا ، فقم بإنشاء ملفالعقدةعقد العنصر الجديد وتعيينهself.first_nلتلك العقدة.
  2. لوself.first_nيكون ليس يساويلا أحد:
    1. هل العنصر الجديد أصغر منself.first_nالعنصر؟ إذا كان الأمر كذلك ، فقم (1) بإنشاء ملفالعقدةالاحتفاظ بالعنصر الجديد ، (2) اضبطهnext_nإلىself.first_n، ثم (3) اضبطself.first_nإلى العقدة الجديدة. فيما يلي توضيح لهذه الحالة:
    2. وإلا ، فإن العقدة الجديدة لا تنتقل بين ملفلينكدليستالكائن والأولالعقدةموضوع. في هذه الحالة ، يمكننا التعامل معself.first_nكائن كما لو كان هو نفسهلينكدليست، فقط لو هو - هي إمتلك.insert_item ()طريقة.

هذه الحالة (ب) هي حقًا قلب استراتيجية القائمة المرتبطة: كل منهاالعقدةالكائن سيكون له أيضًا.insert_item ()طريقة. علاوة على ذلك ، كل عقدةinsert_item ()سيتبع نفس المنطق على النحو الوارد أعلاه: إذاself.next_nيكونلا أحد، فإن العقدة الجديدة تتبع تلك العقدة. إذا لم يكن الأمر كذلك ، فإن العقدة تحتاج إلى تحديد ما إذا كان يجب على العقدة الجديدة الانتقال بينها وبين العقدة التالية ، أو ما إذا كان يجب "تمرير باك" إلى العقدة التالية في السطر.

الآن يمكننا أن ننتقل إلى الكود. أولاً ، إليك رمزلينكدليستصف دراسي.

الخطوط الموضحة أعلاه هي تلك الموضحة في الخطوة 2 أ وهي حاسمة ؛ على وجه الخصوص ، فإن الترتيب الذي يتم به تعيين المتغيرات المختلفة يصنع الفارق. ماذا سيحدث لوself.first_n = newnodeكان يسمى قبلnewnode.set_next (self.first_n)؟ سنفقد كل المراجع لبقية القائمة:itemlist.first_nسيشير إليهnewnode، العقدة الجديدة.next_nسيشير إليهلا أحد، ولن يشير أي متغير إلى عقد العقدة3—سيتم فقده في ذاكرة الوصول العشوائي وسيتم جمع القمامة في النهاية.

كما ذكر أعلاه ، فإن فئة أالعقدةمشابه تمامًا. في الواقع ، من الممكن إنشاء قوائم مرتبطة بنوع كائن واحد فقط ، ولكن هذا يتطلب عقدة "وهمية" لتمثيل قائمة فارغة على أي حال (ربما تخزينلا أحدفي ذلكالبند الذاتي).

هيكل البيانات الجديد سهل الاستخدام نسبيًا ، ويحافظ على ترتيب نفسه بشكل جيد:

تعتبر فكرة "تمرير المسؤولية" بين العقد ذكية جدًا ، وتتيح لنا كتابة استعلامات معقدة حول بنية البيانات لدينا بسهولة. لنفترض أننا أردنا أن نسأل عما إذا كان عنصر معين موجودًا بالفعل في القائمة.

لحل مشكلة مثل هذه ، يمكننا التفكير في كل عقدة على أنها تنفذ إجراء قرار (باستخدام طريقة ، مثل.is_item_present (استعلام)). اللينكدليستسيعود كائن الواجهةخاطئةإذا كانself.first_nيكونلا أحد(للإشارة إلى أن القائمة فارغة ، لذلك لا يمكن أن يكون عنصر الاستعلام موجودًا). إذا كانself.first_nليسلا أحد، يدعوself.first_n.is_item_present (استعلام)، مترقب الذي - التي عقدة للعودةحقيقيأوخاطئة.

بالنسبة للعقدة ، يكون إجراء القرار أكثر تعقيدًا:

  1. تحقق مما إذا كانالبند الذاتييساوياستفسار. إذا كان الأمر كذلك ، أحقيقييمكن إعادتها بأمان.
  2. خلاف ذلك:
    1. لوself.next_nيكونلا أحد، من ثمخاطئةيمكن إرجاعها ، لأنه إذا تم تمرير باك إلى نهاية القائمة ، فلن تتطابق أي عقدة معاستفسار.
    2. لوself.next_nموجود ، من ناحية أخرى ، ما عليك سوى تمرير القيمة أسفل السطر ، والاعتماد على الإجابة للعودة ، والتي يمكن إرجاعها.

فيما يلي عرض سريع للاستخدام (يمكن العثور على النص بأكمله في الملف linklist.py):

لاحظ التشابه في جميع هذه الطرق: تحدد كل عقدة أولاً ما إذا كان يمكنها الإجابة على المشكلة - إذا كان الأمر كذلك ، فإنها تحسب الإجابة وتعيدها. إذا لم يكن الأمر كذلك ، فإنه يتحقق من وجود عقدة لتمرير المشكلة إليها ، وإذا وجدت واحدة ، فسيتم تمرير الحزمة. لاحظ أنه في كل مرة يتم استدعاء الطريقة نفسها - يتم استدعاؤها فقط لكائن مختلف. وفي كل مرة تقل "المشكلة" الإجمالية مع تناقص عدد العقد المتبقية لتمرير المسؤولية.

كم من الوقت يستغرق إدراج عنصر في قائمة طويلة بالفعل؟ نظرًا لأنه قد يتعين نقل العنصر الجديد في نهاية القائمة ، فقد يلزم تمرير المبلغ مرات ، وهذا يعني أن الإدراج هو . ماذا عن الحصول على أصغر عنصر؟ في اللينكدليست.get_smallest ()الأسلوب ، فإنه يحتاج فقط إلى تحديد ما إذا كانself.first_nيكونلا أحد، وإذا لم يكن كذلك ، فإنها تُرجع العنصر المخزن في تلك العقدة. لأنه لا يوجد وقت يمر ، فقد حان الوقت .

لم يجعلنا إنشاء بنية القائمة المرتبطة المصنفة أكثر من مجرد قائمة أكثر وضوحًا يتم الاحتفاظ بها بترتيب مرتب عبر الفقاعات ، ولكن الأفكار التي تم تنفيذها هنا تمهد الطريق لحلول أكثر تعقيدًا.

تمارين

  1. كم من الوقت سيستغرق الإدراج التسلسلات في قائمة Python ، ثم في النهاية قم بفرزها باستخدام الفقاعات في أسوأ سيناريو (باستخدام تدوين الطلب)؟
  2. كم من الوقت سيستغرق الإدراج العناصر في قائمة مرتبطة مرتبة تبدأ فارغة ، في أسوأ سيناريو (باستخدام تدوين الطلب)؟ (لاحظ أن الإدخال الأول سريع ، لكن العنصر الثاني قد يستغرق مرحلتي باك ، والثالث قد يستغرق ثلاثة ، وهكذا).
  3. أضف طرق "pass the buck" إلى ملفلينكدليستوالعقدةالفئات التي ينتج عنها طباعة كل عنصر بالترتيب.
  4. اكتب طرق "pass the buck" التي تؤدي إلى طباعة قائمة العناصر ، ولكن بتنسيق يعكس ترتيب.
  5. أضف طرقًا إلى ملفلينكدليستوالعقدةفئات بحيث يمكن تحويل القائمة المرتبطة إلى قائمة عادية (بأي ترتيب ، على الرغم من أن الترتيب العكسي هو الأكثر طبيعية). على سبيل المثال،طباعة (itemlist.collect_to_list ())يجب طباعة شيء مثل['9', '3', '7'].

حتى الآن ، كانت كل من الخوارزمية (الفقاعات) وهيكل البيانات (قائمة مرتبطة مرتبة) قمنا بدراستها ذات طبيعة خطية. هنا ، سنرى كيف يمكن توسيع هذه الأفكار بطرق "متشعبة".

دعنا نفكر في القائمة المرتبطة التي تم فرزها من القسم الأخير ، والتي تم تحديدها بواسطة فئة "التحكم" (ملفلينكدليست) وعدد من متطابقة تقريباالعقد، كل منها بإشارة إلى "التالي"العقدةكائن في السطر. طالما تم اتباع قواعد معينة (على سبيل المثال ، تم الاحتفاظ بالقائمة بترتيب فرز) ، فقد سمح ذلك لكل عقدة بعمل محلي القرارات التي نتج عنها عالمي إجابات على الأسئلة.

ماذا لو أعطينا كل عقدة المزيد من القوة؟ بدلا من واحدself.next_nمتغير المثال ، ماذا لو كان هناك اثنان: أself.left_nو أالنفس. right_n؟ سنحتاج إلى قاعدة مقابلة للحفاظ على تنظيم الأشياء: العناصر الأصغر تتجه نحو اليسار ، والعناصر الأكبر (أو ذات الحجم المتساوي) تتجه نحو اليمين. هيكل البيانات هذا معروف جيدًا شجرة ثنائية.

يبدو الرسم التوضيحي أعلاه أكثر تعقيدًا بعض الشيء. ولكن إذا فحصنا هذا الهيكل عن كثب ، فسيكون مشابهًا تمامًا للقائمة المرتبطة:[3] هناك فئة مسيطرة منشجرة ثنائية، وبدلاً من أself.first_nمتغير مثيل ، له متغير حالة يسمىself.root_n، لأن العقدة التي تشير إليها هي "جذر" الشجرة. قبل إدخال أي عناصر ،self.root_nسوف يكونلا أحد. عند إدخال عنصر ، إذاself.root_nيكونلا أحد، العنصر الجديد يذهب هناك ؛ خلاف ذلك ، يتم بالضرورة تمرير المسؤولية إلىself.root_n. سنرى لماذا في لحظة.

الآن ، من أجلالعقدةclass ، سنحتاج إلى منشئ ، بالإضافة إلى أساليب "get" و "set" لكليهماleft_nوصح، والتي تم ضبطها في البداية علىلا أحد.

ماذا عن العقدة.insert_item ()طريقة؟ ما نوع عملية صنع القرار التي يجب أن تحدث؟ العملية أبسط حتى من القائمة المرتبطة المصنفة. إذا كانت كل عقدة تتبع دائمًا القاعدة التي تنص على أنه يمكن العثور على العناصر الأصغر إلى اليسار والعناصر الأكبر أو المتساوية يمكن العثور عليها دائمًا على اليمين ، فيمكن دائمًا إدراج العناصر الجديدة في الجزء السفلي من الشجرة. في الشجرة أعلاه ، على سبيل المثال ، عقد عقد8سيتم وضعها على يمين (و "أسفل") عقد العقدة7. وبالتالي ، فإن عملية اتخاذ القرار للعقدة هي كما يلي:

  1. هو العنصر الجديد لإدراج أقل من لديناالبند الذاتي؟ إذا كان الأمر كذلك ، ينتقل العنصر الجديد إلى اليسار:
    1. يكونself.left_nيساويلا أحد؟ إذا كان الأمر كذلك ، فسنحتاج إلى إنشاء عقدة جديدة تحمل العنصر الجديد وتعيينهself.left_nلتلك العقدة.
    2. إذا لم يكن الأمر كذلك ، فيمكننا نقل المسؤولية إلىself.left_n.
  2. خلاف ذلك ، يجب أن يكون العنصر أكبر من أو يساويالبند الذاتي، لذلك يجب أن تذهب إلى اليمين:
    1. يكونالنفس. right_nيساويلا أحد؟ إذا كان الأمر كذلك ، فسنحتاج إلى إنشاء عقدة جديدة تحمل العنصر الجديد وتعيينهالنفس. right_nلتلك العقدة.
    2. إذا لم يكن الأمر كذلك ، فيمكننا نقل المسؤولية إلىالنفس. right_n.

في الشكل السابق للشجرة ،8سيذهب إلى يمين7,6سيذهب إلى يسار7,18سيذهب إلى اليمين11، وما إلى ذلك وهلم جرا. وبالتالي ، فإن منطق إدراج عنصر جديد بسيط للغاية ، من وجهة نظر العقدة:

الطريقة المتبقية للنظر فيها هي الشجرة.get_smallest (). في حالة القائمة المرتبطة ، كان العنصر الأصغر (إذا كان موجودًا) هو العقدة الأولى في القائمة ، وبالتالي يمكن الوصول إليها بدون تمرير باك. لكن في حالة الشجرة الثنائية ، هذا ليس صحيحًا: يمكن العثور على أصغر عنصر على طول الطريق إلى اليسار. رمز.get_smallest ()في الشجرةفئة وما يقابلهاالعقدةالطبقة تعكس هذا.

في حالة العقدة ، إذاself.left_nيكونلا أحد، من ثم الذي - التي يجب أن يكون عنصر العقدة هو أصغر عنصر ، لأنه يمكن أن يفترض أن الرسالة قد تم تمريرها فقط باتجاه اليسار فقط. يوضح رمز الاستخدام المماثل للقائمة المرتبطة أن هذا الهيكل الرائع (binarytree.py) يعمل حقًا:

السؤال الأكثر إثارة للاهتمام هو: كم من الوقت يستغرق إدراج عنصر جديد في شجرة تحتوي بالفعل العناصر؟ الجواب يعتمد على شكل الشجرة. افترض أن الشجرة جميلة و "كثيفة" ، مما يعني أن جميع العقد باستثناء تلك الموجودة في الأسفل لها عقد على اليسار واليمين.

الوقت المستغرق لإدراج عنصر هو عدد المرات التي يجب أن يمر فيها باك للوصول إلى أسفل الشجرة. في هذه الحالة ، في كل عقدة ، يتم تقليل العدد الإجمالي للعقد في الاعتبار بمقدار النصف ؛ أول، من ثم ، من ثم ، وهكذا ، حتى يكون هناك مكان واحد فقط يمكن أن ينتقل إليه العنصر الجديد. كم مرة يمكن لعدد تقسم إلى النصف حتى تصل إلى القيمة 1 (أو أصغر)؟ الصيغة . يستغرق العثور على أصغر عنصر لشجرة كثيفة نفس القدر من الوقت ، لأن الطول أسفل الجانب الأيسر هو نفسه أي مسار آخر إلى "ورقة شجر" في الشجرة.

بشكل عام ، لوغاريتم أصغر بكثير من نفسها ، لذا فإن الشجرة الثنائية تتقاضى بعض السرعة في إيجاد أصغر عنصر للسرعة في الإدراج.

لاحظ ، مع ذلك ، أن شكل الشجرة يعتمد على الترتيب الذي يتم به إدراج العناصر ؛ على سبيل المثال إذا10يتم إدخاله في شجرة فارغة ، متبوعًا بـ9، ال9سيذهب إلى اليسار. مزيد من الإدراج8سيضعها على يسار9. وبالتالي ، من الممكن ألا تكون الشجرة في الواقع كثيفة ، ولكنها غير متوازنة تمامًا. على سبيل المثال المتطرف ، إذا كانت الأرقام من بهذا الترتيب ، ستبدو الشجرة كما يلي:

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

الهياكل الأكثر تعقيدًا التي تسمى الأشجار الثنائية "المتوازنة" لها تعديلات على طرق الإدراج التي تضمن بقاء الشجرة كثيفة ، بغض النظر عن ترتيب العناصر التي يتم إدخالها. يعد هذا أمرًا صعبًا ، لأنه يتطلب معالجة هيكل الشجرة بعد عمليات الإدراج ، ولكن لا يمكن أن يستغرق التلاعب بالهيكل نفسه وقتًا طويلاً أو تضيع فائدة الإدراج. تشمل الأمثلة على الأشجار الثنائية المتوازنة ما يسمى بالأشجار ذات اللون الأحمر والأسود وأشجار AVL (التي سميت على اسم جورجي أديلسون-فيلسكي وإيفجيني لانديس ، اللذين وصفهما لأول مرة).

في الممارسة العملية ، لا نميز بين الأشجار الثنائية "كثيفة" و "غير كثيفة": أشجار البحث الثنائي البسيطة هي لكليهما.insert_item ()و.get_smallest ()، لأننا لا نستطيع ضمان الأدغال (تذكر أننا نفترض أداء أسوأ الحالات عند تحليل خوارزمية). وبالتالي ، فإن التطبيقات الحقيقية تستخدم أشجار AVL أو الأشجار ذات اللون الأحمر والأسود أو غيرها من هياكل البيانات الأكثر تعقيدًا.

تمارين

  1. أضف طرق "تمرير المسؤولية" إلىشجرة ثنائيةولهالعقدةفئة ل.print_in_order ()و.print_reverse_order ()، مما يؤدي إلى طباعة العناصر بترتيب فرز وترتيب عكسي ، على التوالي.
  2. يضيف.count_nodes ()الطرق التي تُرجع العدد الإجمالي للعناصر المخزنة في الشجرة. كم من الوقت يستغرق التدوين بالترتيب؟ هل هذا يعتمد على ما إذا كانت الشجرة كثيفة أم لا؟ إذا كان الأمر كذلك ، فما هو وقت الجري لشجرة كثيفة مقابل شجرة غير كثيفة؟
  3. يضيف.count_leaves ()الطرق التي تُرجع العدد الإجمالي للأوراق (العقد ذاتلا أحدفيleft_nوصح).
  4. تسمى أشجار البحث الثنائية بهذا الاسم لأنها تستطيع بسهولة وفعالية تحديد ما إذا كان عنصر الاستعلام موجودًا أم لا. يضيف.is_item_present ()الطرق التي تعودحقيقيإذا كان عنصر الاستعلام موجودًا في الشجرة وخاطئةخلاف ذلك (على غرارلينكدليست.is_item_present ()). كم من الوقت يستغرق التدوين بالترتيب؟ هل هذا يعتمد على ما إذا كانت الشجرة كثيفة أم لا؟ إذا كان الأمر كذلك ، فما هو وقت الجري لشجرة كثيفة مقابل شجرة غير كثيفة؟
  5. قم بتعديل رمز الشجرة الثنائية بحيث لا يمكن تخزين العناصر المكررة في عقد منفصلة.

رجوع إلى الفرز

سبق أن تركنا موضوع الفرز بعد التطورفقاعة الفرز، و طريقة لفرز قائمة بسيطة من العناصر. يمكننا بالتأكيد القيام بعمل أفضل.

واحدة من الميزات المثيرة للاهتمام فيinsert_item ()الطريقة المستخدمة من قبل العقد في كل من الشجرة والقائمة المرتبطة هي أن هذه الطريقة ، لأي عقدة معينة ، تستدعي نفسها ، ولكن في عقدة أخرى. في الواقع ، لا توجد نسخ متعددة للطريقة المخزنة في ذاكرة الوصول العشوائي. بدلاً من ذلك ، يتم تقاسم طريقة واحدة بينهما ، وفقطالذاتالمعلمة تتغير حقا. إذن ، هذه الطريقة (التي هي مجرد وظيفة مرتبطة بالفئة) تستدعي بالفعل بحد ذاتها.

بطريقة ذات صلة ، اتضح أن أي وظيفة (غير مرتبطة بكائن) يمكنها استدعاء نفسها. لنفترض أننا أردنا حساب دالة العوامل ، المعرفة على أنها

واحدة من أكثر ميزات دالة العوامل إثارة للاهتمام هي أنه يمكن تعريفها من حيث نفسها:

إذا أردنا أن نحسبمضروب (7)، الطريقة المنطقية للتفكير هي: "أولاً ، سأحسب مضروب الرقم 6 ، ثم أضربه في 7." هذا يقلل من مشكلة الحوسبةمضروب (6)، والتي يمكننا حلها منطقيًا بنفس الطريقة. في النهاية سنرغب في الحسابمضروب (1)، وأدرك أن هذا هو فقط 1. الكود يتبع هذا المنطق بدقة:

بقدر ما قد يكون مفاجئًا ، فإن هذا الجزء من الكود يعمل حقًا.[4] والسبب هو أن المعلمةنهو متغير محلي ، وبالتالي في كل استدعاء للوظيفة يكون مستقلاً عن أي وظيفة أخرىنمتغير قد يكون موجودًا.[5] الدعوة إلىمضروب (7)لديهنيساوي 7 ، الذي يدعومضروب (6)، والتي بدورها تحصل على ملكيتهانيساوي6، وما إلى ذلك وهلم جرا. كل مكالمة تنتظر عندsubanswer = عاملي (ن -1)الخط ، وفقط عندمامضروب (1)يتم الوصول إليه هل تبدأ المرتجعات في الترشيح احتياطيًا لسلسلة المكالمات. لأن استدعاء الوظيفة هو عملية سريعة () ، الوقت المستغرق للحسابعاملي (ن)يكون ، واحد لكل مكالمة وإضافة محسوبة في كل مستوى.

هذه الإستراتيجية - الوظيفة التي تستدعي نفسها - تسمى العودية. عادة ما تكون هناك حالتان على الأقل يتم النظر فيهما بواسطة دالة تكرارية: (1) الحالة الأساسية، والتي تُرجع إجابة فورية إذا كانت البيانات بسيطة بدرجة كافية ، و (2) حالة متكررة، والتي تحسب إجابة فرعية واحدة أو أكثر وتعديلها لإرجاع الإجابة النهائية. في الحالة العودية ، يجب أن تكون البيانات المراد العمل عليها "أقرب" إلى الحالة الأساسية. إذا لم يفعلوا ذلك ، فلن تنتهي سلسلة المكالمات أبدًا.

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

للحصول على إستراتيجية شاملة ، سنقوم بتنفيذ الفرز العودي في دالة تسمىالترتيب السريع (). أول شيء يجب التحقق منه هو ما إذا كانت القائمة بطول 1 أو 0: إذا كان الأمر كذلك ، فيمكننا ببساطة إعادتها لأنها مرتبة بالفعل. (هذه هي الحالة الأساسية للطريقة العودية.) إذا لم يكن الأمر كذلك ، فسنختار عنصر "محوري" من قائمة الإدخال ؛ عادة ، سيكون هذا عنصرًا عشوائيًا ، لكننا سنستخدم العنصر الأول كمحور لتبدأ به. بعد ذلك ، سنقسم قائمة الإدخال إلى ثلاث قوائم:لتر، تحتوي على العناصر الأقل من المحور ؛مكافئ، تحتوي على عناصر مساوية للمحور ؛ وجي تي، التي تحتوي على عناصر أكبر من المحور. بعد ذلك ، سنقوم بالفرزلتروجي تيلانتاجlt_sortedوgt_sorted. الجواب إذن هو قائمة جديدة تحتوي أولاً على العناصر منlt_sorted، ثم العناصر منمكافئ، وأخيرًا العناصر منgt_sorted.

الأجزاء المثيرة للاهتمام من الكود أدناه هي الأسطر المميزة: كيف نقوم بالفرزلتروجي تيلانتاجlt_sortedوgt_sorted?

يمكننا استخدام لغة Python المدمجةمرتبة()وظيفة ، ولكن من الواضح أن هذا غش. يمكننا استخدام الفقاعات ، ولكن القيام بذلك سيؤدي إلى معاناة وظيفتنا في نفس الوقت المحدد لخاصية الفقاعات (نقول "مرتبط بوقت" لأن تدوين الترتيب يوفر بشكل أساسي حدًا أعلى لاستخدام الوقت). الجواب هو استخدام العودية: لأنلتروجي تييجب أن يكون كلاهما أصغر من قائمة الإدخال ، نظرًا لأن المشكلات الفرعية تقترب من الحالة الأساسية ، ويمكننا استدعاءالترتيب السريع ()عليهم!

دعونا نحاول تحليل وقت تشغيلالترتيب السريع ()- هل سيكون أفضل من ، أو يساوي ، أو أسوأ من الفقاعات؟ كما هو الحال مع الأشجار الثنائية التي تمت تغطيتها سابقًا ، اتضح أن الإجابة هي "هذا يعتمد".

أولاً ، سننظر في المدة التي تستغرقها الوظيفة للتشغيل - دون احتساب الاستدعاءات الفرعيةالترتيب السريع ()—في قائمة الحجم. الخطوة الأولى هي اختيار المحور ، وهو سريع. بعد ذلك ، قمنا بتقسيم قائمة الإدخال إلى ثلاث قوائم فرعية. لأن الإلحاق بالقائمة سريع ، لكن الكل العناصر التي يجب إلحاقها بواحد من العناصر الثلاثة ، الوقت الذي يقضيه هذا القسم هو . بعد الاستدعاءات الفرعية ، يجب إلحاق إصدارات القوائم التي تم فرزها بملفإجابهقائمة ، ولأن هناك الأشياء التي يجب إلحاقها ، هناك وقت أيضًا . وبالتالي ، بدون احتساب الاستدعاءات الفرعية العودية ، يكون وقت التشغيل هو زائد الذي .

ولكن هذه ليست نهاية القصة - لا يمكننا فقط تجاهل الوقت المستغرق لفرز القوائم الفرعية ، على الرغم من أنها أصغر. من أجل الجدل ، لنفترض أننا دائمًا ما "محظوظون" ، والمحور هو العنصر الوسيط لقائمة الإدخال ، لذلكلين (لتر)ولين (GT)كلاهما تقريبًا . يمكننا تصور تنفيذ استدعاءات الوظائف كنوع من "شجرة الاتصال" ، حيث يمثل حجم العقد حجم قائمة المدخلات.

هنا ، تمثل "العقدة" العلوية العمل الذي أنجزته المكالمة الأولى ؛ قبل أن ينتهي ، يجب أن يستدعي لفرزلترالقائمة في الطبقة الثانية ، والتي يجب أن تستدعي مرة أخرى لفرز الطبقة الخاصة بهالترlist وهكذا ، حتى الطبقة السفلية ، حيث يتم الوصول إلى الحالة الأساسية. يمكن تتبع مسار التنفيذ في الشكل على طول الخط. لتحليل وقت تشغيل الخوارزمية ، يمكننا ملاحظة أن مقدار العمل المنجز في كل طبقة هو ، لذا فإن إجمالي حجم العمل هو هذه القيمة مضروبة في عدد الطبقات. في الحالة التي تقسم فيها المحاور القوائم إلى النصف تقريبًا ، تكون النتيجة هي نفس عدد الطبقات في الشجرة الثنائية كثيفة الأشجار: . وبالتالي ، في هذا السيناريو المثالي ، يكون إجمالي وقت التشغيل ، وهو أفضل بكثير من من الفقاعات.[6]

This equation assumes that the pivots split the input lists more or less in half, which is likely to be the case (on average), if we choose the pivots at random. But we didn’t choose at random; we usednums[0]. What would happen if the input to the list happened to be already sorted? In this case, the pivot would always be the first element,ltwould always be empty, andجي تيwould have one fewer element. The “work tree” would also be different.

In this “unlucky” case, the work on each level is approximately , and so on, so the total work is الذي . Does this mean that in the worst casequicksort()is as slow as bubblesort? Unfortunately, yes. But some very smart people have analyzedquicksort()(assuming the pivot element is chosen at random, rather than using the first element) and proved that in the average case the run time is , and the chances of significantly worse performance are astronomically small. Further, a similar method known as “mergesort” operates by guaranteeing an even 50/50 split (of a different kind).

Using random selection for pivot,quicksort()is fast in practice, though mergesort and similar algorithms are frequently used as well. (Python’s.sort()وsorted()use a variant of mergesort called “Timsort.”) Although as mentioned above worst-case analysis is most prevalent in algorithms analysis,quicksort()is one of the few exceptions to this rule.

These discussions of algorithms and data structures might seem esoteric, but they should illustrate the beauty and creativeness possible in programming. Further, recursively defined methods and sophisticated data structures underlie many methods in bioinformatics, including pairwise sequence alignment, reference-guided alignment, and Hidden Markov Models.

تمارين

  1. The first step for writingmergesort()is to write a function calledmerge()؛ it should take two sorted lists (together comprising elements) and return a merged sorted version. على سبيل المثال،merge([1, 2, 4, 5, 8, 9, 10, 15], [2, 3, 6, 11, 12, 13])should return the list[1, 2, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15], and it should do so in time ، أين is the total number of elements from both lists. (Note that.append()on a Python list is time , as are mathematical expressions likec = a + b, but other list operations like.insert()are not.)

    الmergesort()function should first split the input list into two almost-equal-sized pieces (e.g.,first_half = input_list[0:len(input_list)/2]); these can then be sorted recursively withmergesort(), and finally themerge()function can be used to combine the sorted pieces into a single answer. If all steps in the function (not counting the recursive calls) are , then the total time will be .

    Implementmerge()وmergesort().

  2. The Fibonacci numbers (1, 1, 2, 3, 5, 8, 13, etc.) are, like the factorials, recursively defined:

    Write a recursive functionfib()that returns theth Fibonacci number (fib(1)should return1,fib(3)should return2,fib(10)should return55).

  3. Next, write a function calledfib_loop()that returns theth Fibonacci by using a simple loop. What is the run time, in order notation, in terms of؟ Compare how long it takes to computefib(35)عكسfib_loop(35), and then tryfib(40)عكسfib_loop(40). Why do you thinkfib()takes so much longer? Try drawing the “call trees” forfib(1),fib(2),fib(3),fib(4),fib(5)، وfib(6). Could you make a guess as to what the run time of this function is in order notation? Can you imagine any ways it could be sped up?


69443 - ALGORITHMS AND DATA STRUCTURES FOR COMPUTATIONAL BIOLOGY

At the end of the cycle of lessons, the student has the basic knowledge of the methodologies and issues for the definition and complexity analysis of correct and efficient algorithms and data structures. In particular, the student has basic knowledge on abstract data types and is able to design scalable and arbitrarily complex data structures functional to the algorithmic requirements. The student will be able to create a functional synergy between the design of correct and efficient algorithms and the corresponding well designed data structures for common computational tasks, under the optimization criteria of both computational and space complexity for algorithms execution. The algorithmic methodologies will be presented with concrete examples and applications, including iterative and recursive programming, divide et impera, greedy and dynamic programming techniques. The student will be able to analyze the complexity of existing algorithms and data structures, using analysis methodologies for algorithmic complexity evaluation, and will be trained on the design and analysis new algorithms and data structures for computational biology.


2.13: Algorithms and Data Structures - Biology

يتم توفير جميع المقالات المنشورة بواسطة MDPI على الفور في جميع أنحاء العالم بموجب ترخيص وصول مفتوح. لا يلزم الحصول على إذن خاص لإعادة استخدام كل أو جزء من المقالة المنشورة بواسطة MDPI ، بما في ذلك الأشكال والجداول. بالنسبة للمقالات المنشورة بموجب ترخيص Creative Common CC BY ذي الوصول المفتوح ، يجوز إعادة استخدام أي جزء من المقالة دون إذن بشرط الاستشهاد بالمقال الأصلي بوضوح.

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

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

تستند مقالات اختيار المحرر على توصيات المحررين العلميين لمجلات MDPI من جميع أنحاء العالم. يختار المحررون عددًا صغيرًا من المقالات المنشورة مؤخرًا في المجلة والتي يعتقدون أنها ستكون مثيرة للاهتمام بشكل خاص للمؤلفين أو مهمة في هذا المجال. الهدف هو تقديم لمحة سريعة عن بعض الأعمال الأكثر إثارة المنشورة في مجالات البحث المختلفة بالمجلة.


Data Structure and Algorithm

Searching involves deciding whether a search key is present in the data. For example, looking up a phone book or address book. The searching algorithm includes:

  • Linear Search: See "Linear Search".
  • Recursive Binary Search for sorted list
  • Binary Tree Search

Linear Search

Complexity

The worst-case and average-case time complexity is O(n). The best-case is O(1).

Binary Search

A binary search (or half-interval search) is applicable only to a sorted array. It compares the search key with the middle element. If there is a match, it returns the element's index. If the search key is less then the middle element, repeat searching on the left half otherwise, search the right half. If the remaining element to be searched is zero, return "no found".

Complexity

The worst-case and average-case time complexity for binary search is O(log n). The best-case is O(1).

فرز

Sorting involves arranging data in ascending or descending order, according to a certain collating sequence (or sorting sequence). The sorting algorithm includes:

  • Insertion Sort: See "Insertion Sort".
  • Selection Sort: See "Selection Sort".
  • Bubble Sort: See "Bubble Sort"
  • Merge Sort (Recursive Top-Down or Interactive Bottom-up)
  • Quick Sort (Recursive)
  • Bucket Sort
  • Heap Sort
  • Binary Tree Sort

Bubble Sort

Complexity

The average-case and worst-case time complexity is O(n 2 ).

Insertion Sort

Complexity

The average-case and worst-case time complexity is O(n 2 ).

Selection Sort

Complexity

The average-case and worst-case time complexity is O(n 2 ).

Merge Sort

Recursive Top-Down Merge Sort

The algorithm is as follows:

  1. Recursively divide the list into 2 sublists.
  2. When the sublists contain 1 element (a list of 1 element is sorted), merge two sublists in the right order. Unwind the merging recursively.
Interactive Bottom-up Merge Sort

Treat the list as sublists of length 1, and interactively merge a pair of sublists bottom-up, until there is only one sublist.

Complexity

The worst-case and average-case time complexity is O(n log n). The best-case is typically O(n log n). However, merge sort requires a space complexity of O(n) for carrying out the merge-sorting.

Quick Sort

Quick sort is a divide and conquer algorithm. It picks a pivot and divides the list into two sub-lists: the low elements and the high elements, and recursively sorts the sub-lists.

  1. Pick a element, called pivot, from the list.
  2. Partition the list so that the smaller elements are before the pivot, and the larger elements after the pivot.
  3. Recursively sort the sub-lists.

Partition: The partition procedure are:

Choosing the pivot: If the list is already sorted, choosing the first or last element as pivot results in worst performance of O(n 2 ). We choose the middle element, and swap the the element at the right end, so as not to interfere with the partition process.

QuickSort.cpp
Complexity

The worst-case time complexity is O(n 2 ). The average-case (typical) and best-case is O(n log n). In-place sorting can be achieved without additional space requirement.

Bucket Sort

Bucket sort (or bin sort) works by distributing the elements into a number of buckets, and each bucket is then sorted individually. Bucket sort is a distribution sort, and is a cousin of radix sort, in which the sorting begins at the most significant digit and goes down to the less significant ones. Bucket sort is not a comparison sort like bubble sort, insertion sort or selection sort.

The algorithm is as follows:

  1. Set up buckets, initially empty.
  2. Scatter: place each element into an appropriate bucket.
  3. Sort each non-empty bucket.
  4. Gather: Gather elements from buckets and put back to the original array.
Radix Sort (Recursive)

Use 10 buckets to sort from the most-significant down to the least-significant digit.

  • Need to implement the buckets using dynamic array (such as vector ) as their sizes are unknown and to expensive to set to the maximum.

Data Structures

The built-in array has many limitations. It is fixed in size and cannot grow and shrink during execution. The size has to be decided during the declaration.

Many applications require dynamic data structures, that can grow and shrink during execution. The commonly used data structures include:

  • List: Single linked list, double linked list, etc.
  • Queue: FIFO queue, priority queue, etc.
  • Stack: LIFO queue
  • Tree:
  • Map or Associative Array:

Single Linked List

Node.h
List.h
TestList.cpp

Double Linked List

DoubleLinkedNode.h
DoubleLinkedList.h
TestDoubleLinkedList.cpp

Stack (LIFO Queue)

Stack.h
TestStack.cpp

أ شجرة has a root node. Each parent node could have child nodes. A node without child is called a leaf node. A tree with only the root node is called a null tree. The depth of a tree is the length of the path from the root to the deepest node in the tree. A null tree has depth of zero.

في binary tree, a parent node could have up to two child nodes: left child and right child (called siblings with the same parent). They are root of the left subtree and right subtree respectively.

Depth-First Search (DFS)

Start at the root and explore as far as possible along each branch before backtracking. They are 3 types of depth-first search:

  1. Pre-order: visit the root, traverse the left subtree, then the right subtree. E.g., 6 -> 5 -> 4 -> 10 -> 7 -> 9 ->15.
  2. In-order: traverse the left subtree, visit the root, then the right subtree. E.g., 4 -> 5 -> 6 -> 7 -> 9 ->10 -> 15.
  3. Post-order: traverse the left subtree, the right subtree, then visit the root. E.g, 4 -> 5 -> 9 -> 7 -> 15 -> 10 -> 6.

Pre-, in- and post- refer to the order of visiting the root.

Breadth-First Search (BFS)

Begin at the root, visit all its child nodes. Then for each of the child nodes visited, visit their child nodes in turn. E.g., 6 -> 5 -> 10 -> 4 -> 7 -> 15 -> 9.

Binary Search Tree

A binary search tree, without duplicate elements, has these properties:

  1. All values in the left subtree are smaller than the parent node.
  2. All values in the right subtree are larger than the parent node.

The above diagram illustrates a binary search tree. You can retrieve the sorted list or perform searching via in-order depth-first traversal. Take note that the actual shape of the tree depends on the order of insertion.

Node.h
BinaryTree.h
TestBinaryTree.cpp

[TODO] Breadth-First Search: need a FIFO queue to keep the child nodes.

Latest version tested: Cygwin/MinGW GNU GCC 4.62
Last modified: May, 2013


Неделя 2

We consider two fundamental data types for storing collections of objects: the stack and the queue. We implement each using either a singly-linked list or a resizing array. We introduce two advanced Java features—generics and iterators—that simplify client code. Finally, we consider various applications of stacks and queues ranging from parsing arithmetic expressions to simulating queueing systems.

2 материала для самостоятельного изучения

1 практическое упражнение


المشاريع

Design and analysis of algorithms data structures theory of computation combinatorial optimization computational geometry automata theory graph theory on-line algorithms graph drawing algorithms algorithms in discrete tomography.


Tao Jiang

My research has been focused on the design and analysis of algorithms of either theoretical or practical importance. Some of my past work includes approximation algorithms, average-case analysis, computational complexity, and computational learning. My current work is mostly concerned with algorithmic and machine learning problems in bioinformatics and biomedical informatics.

Research interests: computational molecular biology, bioinformatics, design of algorithms, machine learning and data mining.


Yihan Sun

Broad topics in the theory and practice of parallel computing, including algorithms, data structures, frameworks, implementations, and their applications. My work involves improving asymptotical theoretical bounds, simplifying algorithms and proofs, and developing efficient solutions to real-world problems.

My research interests lie in Complexity Theory. More specifically, I am interested in topics related to approximation algorithms, constraint satisfaction problems, analysis of Boolean functions and probabilistically checkable proofs.

My current research interest is design efficient (usually parallel) algorithms for large-scale data with good performance in practice.


MODELS IN BIOLOGY: SCALES AND COMPLEXITY

As already pointed out, any natural phenomena can be observed at different scales thus, in describing the phenomenon by conceptual and quantitative models one needs to choose to appropriate scale to describe the experimental data available.

However, in almost all complex natural phenomena there are aspects that cannot be even observed at just one scale of description (either temporal or spatial). To study these specific facets of reality, multiscale models that represent objects and relationships on different levels of abstraction are required.

Choosing a scale depends on which aspects of the phenomena, from ‘micro’ to ‘macro’, one is interested to analyze. In physics this is already a well defined approach that originates from different research areas, and the distinction between different scales is based upon the characteristic lengths of objects and the characteristic time of the phenomena under investigation. For instance, microphysics refers to areas of physics that study phenomena, which take place on the microscopic scale (length scales <1 mm), such as: molecular physics, atomic physics, nuclear physics and particle physics.

In the life sciences the definition of a scale is a bit more ambiguous. A basic unit available for defining a scale is the ‘cell’ with no regard to its physical dimension. Starting from this, one can define different scales: the ‘sub-cellular’ or ‘intra-cellular’ scale, the ‘cellular’, mesoscopic or ‘inter-cellular scale the ‘macroscopic scale’ and the ‘populations scale’.

Models developed at sub-cellular scale deal with the evolution of the physical and biochemical state of a single cell. This scale involves genes, proteins and signals in cell nucleus and surface, which regulate the evolution of the cell and any signaling processing operations of the cells enabling cell crosstalk.

Modeling the overall activity of a single cell is a very hard problem as many biological details of this activity are unknown.

Biologists and modelers have joined forces to develop and use mathematical and computer science techniques in modeling sub-cellular phenomena. Interested readers can find plenty of references in the scientific literature [ 13].

In the cellular scale, one is interested in describing the evolution of a system consisting of a large number of different interacting cells and molecules. Cell interactions are regulated by signals emitted and received by cells through complex recognition processes. Cellular scale is thus highly connected with the sub-cellular scale but, modeling at this scale, one may forget the details of single cell models and consider them as BBM. The areas of mathematical methods and tools involved in this description refer to statistical mechanics, cellular automata, lattice gas and other similar approaches.

The ‘macroscopic scale’ include tissues, organs (i.e. a collection of tissues joined in structural unit to serve a common function), systems (i.e. a group of organs working together to perform a certain task) and organism.

In this scale, one is interested in describing the dynamical behavior of observable quantities, in most cases, the concentrations of various entities (cells or molecules). Tissues are usually described using techniques originating from physical continuous systems, i.e. ordinary or partial differential equations or moments of kinetic equations. In describing organs, a model is required to describe both the main tissue and the sporadic tissues but also, and most importantly, the biological function. To model a system, one is required to consider a network of organs that perform a specific task. Depending on the modeling goal the model of a biological system can be arranged with different levels of details. Organs can be fully described in their components or simply as BBM performing a given task. Connections between organs (like lymphatic vessels) can be described physically (dynamical description of the fluid motion in the vessels) or simply considering the flux and the time required to move portions of fluid from different organs, i.e. though law of transport.

Finally, in the population scale, one is interested in describing the dynamics of the populations with respect to one or more characteristics. Models of epidemics or population controls are well known models at this scale. Population dynamics is extremely complex because the effects of all previously mentioned scales and the effects of the environment on a single organism can modify the overall dynamic of the populations. In this class of models, a single organism can or cannot be described in detail, according to the size of the populations one is required to describe. In both cases, changes of the major characteristics of a single organism must be taken into account. For example, to describe the response of a population to large-scale vaccinations (as required in influenza epidemics), one does not describe in detail any single organism but it may be required to consider the age structure of the population and the effects of environments. At variance for small size populations, like modeling the effect of a new vaccine for a small trial, a sufficiently detailed description of the organism and the effect of the vaccine on each organism should be required. A variety of different techniques are available for these classes of models. In the former case, one uses both, ordinary or stochastic differential equations to describe the populations dynamics or agent-based models (simple agents representing a single organism) to study the resulting complex phenomena. In the latter case, a more detailed description of the organism is required and the population dynamics may eventually be extracted from the dynamic response of each organism.

Complexity and multiscale models

Living organisms are complex systems. Using a ‘classical’ definition, a complex system is a system composed of different interconnected parts that, as a whole, exhibit one or more properties which do not obviously arise from the properties of the individual parts. System complexity may be either a ‘disorganized complexity’ or an ‘organized complexity’. In the former case complexity arises from a very large number of parts, whereas in the latter case, complexity is intrinsic to the system, eventually with a limited number of parts, and its connections rules.

In living organisms both situations occurs. A living organism is formed by a collection of different parts which are, each of them, organized complex systems. Cells, organs, systems of the human body are each of the complex systems.

As an example, the immune system is one of the very complex one where complexity arises both from a very large number of parts (organs), constituents (cells and molecules) and rules hierarchically connecting different scales of the parts.

Models including many scales of a phenomenon are now requested both for knowledge discovery and drug discovery. In life sciences not only an entire living organism, but also parts of the organism are too complex to be represented in a single, precise, multiscale model. The resulting model would certainly not be computable. Thus, one is forced to break the conceptual model in a set of models describing only part of the phenomenon (like a single organ, or a definite scale) and connect their outcomes [ 16]. To link models at different scales is a not an easy task. Phenomena occurring at different scales have usually different characteristic time scales and models’ output should be properly fitted. Interested readers are referred to another study [ 3] in this issue.


2.13: Algorithms and Data Structures - Biology

ال Multicore Algorithmics group headed by Prof. Nir Shavit develops techniques for designing, implementing, and reasoning about multiprocessor algorithms, in particular concurrent data structures for multicore machines and the mathematical foundations of the computation models that govern their behavior.

الأساتذه

Prof. Nir Shavit
Quote: “”
My main interests are techniques for designing, implementing, and reasoning about multiprocessor algorithms, in particular concurrent data structures for multicore machines and the mathematical foundations of the computation models that govern their behavior. My research these days is directed at the use of randomness and combinatorial techniques in concurrent algorithm and data-structure design. I am also interested in parallelism in the Brain and what we can learn from it towards the design of futuristic computing machines.

باحثو ما بعد الدكتوراة

Igor Zablotchi
My research focuses on the theory and practice of concurrent algorithms. I am most interested on the impact of emerging technologies, such as RDMA and persistent memory, on the way that we build distributed systems. I am also interested in algorithms for scalable machine learning on multicore machines.

الطلاب المتخرجين

Past Members

Alexander Matveev
Quote: “People who are really serious about software should make their own hardware.”
I am working on practical and efficient synchronization techniques for multi-core systems. In particular, my focus is hardware and software transactional memory designs and implementations.
Rati Gelashvili
Quote: “inveniam viam aut faciam”
I am working on shared memory algorithms and data-structures (full of exciting mathematical challenges). I am also very interested in extending topological framework for distributed computability in various directions.
Justin Kopinsky
Quote: “Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are–by definition–not smart enough to debug it.”
I am primarily interested in concurrent data structures with a focus on using non-blocking algorithms and other methods to achieve scalability. I’m also currently working on producing a model for Hybrid Transactional Memory which is motivated by real architectures but is rigorous enough to allow us to prove interesting lower bounds.
William Leiserson
Quote: “Any technology that is distinguishable from magic is insufficiently advanced.”
I work on concurrent data structures, structures that scale efficiently with the number of cores operating on them. I’m especially interested in the application of hardware transactional memory (HTM) to problems that use locks to guarantee mutual exclusion. HTM has the potential to be lighter-weight than a lock, especially if there is low contention, and lock-freedom has desirable progress guarantees.
Michael Coulombe
Quote: “For the mind does not require filling like a bottle, but rather, like wood, it only requires kindling to create in it an impulse to think independently and an ardent desire for the truth.”
My research interests include provable algorithms and data structures, with applications from concurrency to computational biology, and the methods of expressing and proving them. I am currently working on concurrent, shared memory data structures

Quote: “”An algorithm must be seen to be believed.”I’m mainly interested in distributed algorithms. My main research topics are the complexity of concurrent data structures, and communication in distributed systems.


المراجعات

Reviewed by Stephan Olariu, Professor, Old Dominion University on 6/20/17

This book is not intended to be a comprehensive introduction to algorithms and data structures. For this, there are other books. Instead, the authors have focused on a smattering of fundamental topics that provide the student with tools for the. read more

Reviewed by Stephan Olariu, Professor, Old Dominion University on 6/20/17

تصنيف الشمولية: 5 انظر أقل

This book is not intended to be a comprehensive introduction to algorithms and data structures. For this, there are other books. Instead, the authors have focused on a smattering of fundamental topics that provide the student with tools for the study of other topics that were left out in the book. This book is not for beginners -- and it does not teach students how to program. Throughout the book, algorithmic and data structure-related ideas are cast in Pascal-style pseudo-code that has the benefit of being easy to assimilate and has none of the complications of "modern" programming languages. As the title suggests, this is not a dry text on algorithms and data structures. There is a welcome emphasis on applying the algorithms and the data structures covered to real problems in computer graphics and geometry. In fact, Part VI of the book is intended to show the usefulness of data structures for the purpose of efficient implementation of algorithms that manipulate geometric objects. In spite of being a comprehensive compendium of algorithms and data structures, the book can, and has been used successfully, in undergraduate courses dealing with algorithm design and data structures. It can also be used for self-study by all those who wish to broaden their horizon and wish to acquire a solid footing in the fundamentals of computer science.

Content Accuracy rating: 5

The book is highly accurate and has been tested by the authors in their classes for decades

Relevance/Longevity rating: 5

This is not a new book. It was published (with the same title) in 1993 by Prentice Hall. The topics covered and their tested relevance guarantee that it will always be fresh and timely. I can say without hesitation that his is one of the fundamental books in the computer science literature.

The authors are well known compete scientists and educators. They pedagogical style is perfect. This said, the book is not for everyone. It assumes that the reader has been exposed to the fundamentals of programming.

This book is consistent to the extreme. Notation is consistent end-to-end and the coverage of topics is masterfully orchestrated in a coherent and pleasant way. Each chapter starts out by enumerating the learning objectives and presents motivation for the study of the chapter.

The book is organized into six parts, each of them partitioned into several chapters. The parts are both independent of each other and, at the same time, build on ideas mentioned in previous parts and chapters. It is an exemplary way of organizing a successful book.

Organization/Structure/Flow rating: 5

The algorithmic and data structure topics are organized in a natural order. The various topics are motivated, discussed in some detail and then consolidated by showing how they apply to real problems selected from computer graphics and geometry.

Flawless, I could not identify and problems here.

Grammatical Errors rating: 5

The authors are using perfect English. I was unable to identify any grammatical errors or typos

Cultural Relevance rating: 5

The book does not further any hidden agenda and is not offensive in any way.

I highly recommend this book to all those who wish to acquire a solid footing in the design of algorithms and data structures.


استنتاج

Data structure skills form the bedrock of software development, particularly when it comes to managing large sets of data in today’s digital ecosystem. Leading companies like Adobe, Amazon, and Google hire for various lucrative job positions in the data structure and algorithm domain. And in interviews, recruiters test not only your theoretical knowledge but also your practical skills. So, practice the above data structure projects to get your foot in the door!

If you are curious to learn about data science, check out IIIT-B & upGrad’s PG Diploma in Data Science which is created for working professionals and offers 10+ case studies & projects, practical hands-on workshops, mentorship with industry experts, 1-on-1 with industry mentors, 400+ hours of learning and job assistance with top firms.


شاهد الفيديو: 4- ما هي الخوارزميات ولماذا تأتي دائما مع هياكل البيانات (يوليو 2022).


تعليقات:

  1. Cyneley

    هناك شيء حول ذلك ، وأعتقد أنها فكرة رائعة.

  2. Lache

    هذا الموضوع ببساطة لا يضاهى :) ، إنه أمر مثير للاهتمام بالنسبة لي.

  3. Honaw

    أنا على دراية جيدة في هذا. يمكنني المساعدة في حل المشكلة.



اكتب رسالة