كتاب "مهام علوم الحاسوب الكلاسيكية في بيثون"

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

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

من هو هذا الكتاب ل؟

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

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

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

مقتطفات. 1.5. أبراج هانوي

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

هدفنا هو نقل جميع محركات الأقراص من البرج A إلى البرج C ، مع مراعاة القيود التالية.

• لا يمكن نقل الأقراص إلا في وقت واحد.
• محرك الأقراص الوحيد المتاح للتحرك هو الموجود في الجزء العلوي من أي برج.
• لا يمكن وضع محرك أقراص أوسع على قمة محرك أضيق.
  بشكل تخطيطي ، تظهر المهمة في الشكل. 1.7.

1.5.1. نمذجة البرج

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


ادراج 1.20. hanoi.py

from typing import TypeVar, Generic, List T = TypeVar('T') class Stack(Generic[T]): def __init__(self) -> None: self._container: List[T] = [] def push(self, item: T) -> None: self._container.append(item) def pop(self) -> T: return self._container.pop() def __repr__(self) -> str: return repr(self._container) 

تطبق فئة Stack المقدمة طريقة __repr __ () ، مما يجعل من السهل فحص محتويات البرج. __repr __ () هو ما سيتم إخراجه عند تطبيق وظيفة print () على المكدس.

كما هو مذكور في المقدمة ، يتم استخدام التعليقات التوضيحية في الكتاب. يتيح استيراد Generic من وحدة إدخال أن يكون Stack فئة معلمية لنوع معين في التعليقات التوضيحية للنوع. يتم تعريف النوع التعسفي T في T = TypeVar ('T'). تي يمكن أن يكون أي نوع. عند استخدام التعليق التوضيحي للكتابة فيما بعد لـ Stack في حل مشكلة برج هانوي ، ستكون المطالبة هي Stack [int] ، أي ، سيتم استخدام type int بدلاً من T. بمعنى آخر ، هنا المكدس هو كومة من الأعداد الصحيحة. إذا كنت تواجه صعوبة في كتابة التعليقات التوضيحية ، فقم بإلقاء نظرة على الملحق "ب".

الأكوام مثالية لتحدي برج هانوي. من أجل نقل القرص إلى البرج ، يمكننا استخدام عملية الدفع. من أجل نقل القرص من برج إلى آخر ، يمكننا دفعه من أول (pop) ووضعه على (push) الثاني.

حدد الأبراج على أنها كائنات مكدس واملأ أول الأقراص بأقراص (القائمة 1.21).

القائمة 1.21. hanoi.py (تابع)

 num_discs: int = 3 tower_a: Stack[int] = Stack() tower_b: Stack[int] = Stack() tower_c: Stack[int] = Stack() for i in range(1, num_discs + 1): tower_a.push(i) 

1.5.2. حل مشكلة أبراج هانوي

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

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

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

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

1. انقل أعلى محركات الأقراص n - 1 من البرج A إلى البرج B (مؤقت) ، باستخدام C كبرج وسيط.
2. نقل محرك أقل من ألف إلى C.
3. نقل الأقراص n - 1 من البرج B إلى البرج C ، البرج A متوسط.

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

القائمة 1.22. hanoi.py (تابع)

 def hanoi(begin: Stack[int], end: Stack[int], temp: Stack[int], n: int) -> None: if n == 1: end.push(begin.pop()) else: hanoi(begin, temp, end, n — 1) hanoi(begin, end, temp, 1) hanoi(temp, end, begin, n - 1) 

بعد الاتصال hanoi () ، تحتاج إلى التحقق من الأبراج A و B و C للتأكد من أن محركات الأقراص قد تم نقلها بنجاح (إدخال 1.23).

ادراج 1.23. hanoi.py (تابع)

 if __name__ == "__main__": hanoi(tower_a, tower_c, tower_b, num_discs) print(tower_a) print(tower_b) print(tower_c) 

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

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

1.6. تطبيقات حقيقية

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

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

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

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

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

هذه الطرق هي لبنات بناء البرامج ؛ تعتمد الخوارزميات الأخرى عليها. في الفصول التالية سترى مدى تطبيقها.

عن المؤلف

ديفيد كوبيك محاضر أول في علوم الكمبيوتر والابتكار في كلية شامبلين في بيرلينجتون ، فيرمونت. وهو مطور برمجيات خبير ومؤلف كتاب "مشاكل علوم الكمبيوتر الكلاسيكية في سويفت" (Manning، 2018) و Dart for Absolute Beginners (Apress، 2014). حصل ديفيد على درجة البكالوريوس في الاقتصاد ودرجة الماجستير في علوم الكمبيوتر من كلية دارتموث. يمكنك الاتصال به على Twitter بواسطةdavekopec.

»يمكن الاطلاع على مزيد من المعلومات حول الكتاب على موقع الناشر
» المحتويات
» مقتطفات

خصم 25٪ على كوبون الباعة المتجولين - بيثون

عند دفع النسخة الورقية من الكتاب ، يتم إرسال كتاب إلكتروني عبر البريد الإلكتروني.