المكتبة العربية لعلوم الحاسوب
مقدمة في علوم الحاسوب والبرمجة باستخدام Python › مجموعات المسائل 29 / 30 السابق التالي

مجموعة المسائل 4 — العودية والتشفير

مجموعة المسائل 4: العودية وتشفير قيصر (Recursion and Caesar Cipher)

زميل مجموعة المسائل (Pset Buddy): لم يُعيَّن لك زميل لهذه المجموعة في النسخة المنشورة.

المقدمة

تنقسم مجموعة المسائل هذه إلى موضوعين: الأول يركّز على العودية (Recursion) والأشجار (Trees) (الجزء A)، والثاني يتناول الأصناف (Classes) والتشفير (Cryptography) (الجزءان B وC). الموضوعان غير معتمدين أحدهما على الآخر، فلا تتردّد بالعمل عليهما بالتوازي أو بترتيب مختلف. يُرجى قراءة تعليمات كل جزء بعناية.

لا تغيّر أسماء الملفات التي نقدّمها لك، ولا تغيّر أيًّا من دوال المساعدة (Helper Functions) المعطاة، ولا تغيّر أسماء الدوال أو الطرق (Methods)، ولا تحذف السلاسل التوثيقية (Docstrings) المعطاة. ستحتاج إلى إبقاء words.txt وstory.txt وpads.txt في المجلد نفسه الذي تحفظ فيه ملفات .py.

أخيرًا، يُرجى مراجعة دليل الأسلوب (Style Guide)، لأننا سنخصم نقاطًا عند المخالفة (مثلًا أسماء المتغيّرات غير الوصفية والشيفرة غير الموثّقة بالتعليقات). بالنسبة لمجموعة المسائل هذه،Will تكون الأرقام 6 و7 و8 في دليل الأسلوب ذات صلة عالية، لذا تأكّد من مراجعتها قبل البدء في المجموعة ومراجعتها مرة أخرى قبل تسليمها!

1) الجزء A: عمليات عودية على الأشجار (Recursive Operations on Trees)

الشجرة (Tree) هي بنية بيانات هرمية (Hierarchical Data Structure) مكوّنة من عقد (Nodes) مرتبطة. تُسمّى أعلى عقدة الجذر (Root)، ولها فروع (Branches) تربطها بعقد أخرى، وهي بدورها جذور لأشجارها الفرعية (Subtrees) على التوالي. تُعرض شجرة بسيطة أدناه:

ملاحظة المترجم: الشكل في الأصل رسم شجرة بيانية (Diagram) لا يمكن نقله نصيًا. نُقل ما ورد في النشرة عن الشجرة إلى الفقرات التالية، وأُشير إلى الأشجار الأخرى في مواضعها.

يمكن أن نُجري ملاحظة قليلة:

  1. كل عقدة يمكن أن تحمل بيانات: في هذا المثال تحمل كل عقدة سلسلة نصية بنوع العقدة.
  2. البيانات هرمية: كل عقدة لها والد (Parent) (عدا الجذر)، وكل عقدة غير ورقة (Non-Leaf Node) لها ابن واحد أو أكثر، وكل عقدة ورقة (Leaf Node) ليس لها أبناء. سنستخدم هذه المصطلحات في بقية مجموعة المسائل.
  3. الأشجار عودية بطبيعتها: عقد أبناء الجذر هي «جذور» لأشجار أصغر أخرى (تُسمّى الأشجار الفرعية).

1.1) تمرين على تمثيل البيانات (Data Representation Practice)

في مجموعة المسائل هذه، سنستخدم كائن Node مقدَّمًا في tree.py لتمثيل الأشجار.

يمكن تهيئة الشجرة البسيطة أعلاه بكائن Node كما يلي:

example_tree = Node(1, Node(2), Node(5, Node(7), Node(8)))

فيما يلي شرح موجز للصنف Node:

يمكنك تهيئة عقدة بالشكل التالي: Node(value, left_child, right_child).ويحمل value يحمل القيمة الموجودة في العقدة، وleft_child يحمل اختياريًا كائن Node الذي يبني الشجرة الفرعية اليسرى، وright_child يفعل الشيء نفسه للشجرة الفرعية اليمنى. وإذا لم تكن هناك شجرة فرعية، إمّا ألغِ إدخال هذا المعامل أو مرّر None.

يمكنك الحصول على كائن Node الذي يحمل الشجرة الفرعية اليسرى أو اليمنى عبر get_left_child() أو get_right_child() على التوالي. وإذا لم يكن هناك ابن، فتعيد هذه الدالة None.

يمكنك الحصول على القيمة التي تحملها عقدة Node عبر get_value().

سنتمرّن على تهيئة الأشجار في هذا الجزء. وللأشجار المعروضة أدناه، أنشئ كائنات تمثّل البيانات تمثيلًا دقيقًا. ضعها في المتغيّرات الموجودة أعلى ps4a.py والمسمّاة tree1 وtree2 وtree3.

ملاحظة المترجم: الأشجار الثلاثة المطلوبة مرسومة في الأصل بأشكال بيانية. لم تُنشر هذه الأشكال هنا، لأن حقوقها لم يُتحقَّق منها ضمن نطاق إعادة النشر المسموح به في هذه المكتبة. لذلك لم تُنقل بيانات الأشجار إلى نص، ولم يُخمَّن أي شيء. الملفات موصوفة في الملف tree.py الذي لم يُنسخ هنا.

1.1.1) الاختبار (Testing)

يمكنك اختبار تمثيلك حتى الآن بتشغيل test_ps4a_student.py. تأكّد من أنه في المجلد نفسه الذي توجد فيه مجموعة المسائل. وعندما تهيّئ المتغيّرات الثلاثة tree1 وtree2 وtree3 تهيئة صحيحة، فيجب أن ينجح الاختبار المسمّى test_data_representation في test_ps4a_student.py.

1.2) تحديد ارتفاع الشجرة (Determining The Height of a Tree)

ارتفاع الشجرة هو عدد الحواف (Edges) بين الجذر وأبعد ورقة. فمثلًا، في الأشجار التي هيّأتها أعلاه، للشجرة 1 ارتفاع 2، و للشجرتين 2 و3 ارتفاع 3. اكتب دالة عودية find_tree_height تحدّد عمق شجرة. ويجب أن تكون هذه الدالة عودية؛ فالتنفيذات غير العودية ستحصل على صفر.

تلميح. قد يكون النهج التالي مفيدًا:

بمُعطى شجرة دخل T:

  • الحالة الأساس (Base Case). إذا كانت T ورقة، فإن ارتفاعها 0.
  • الحالة العودية (Recursive Case). أوجد بشكل عودي ارتفاع الشجرة الفرعية اليسرى واليمنى لـ T، وخذ الأكبر منهما. أضف 1 إلى أعلى ارتفاع، وأعد تلك القيمة.

يجب أن تختبر دالتك باستخدام المتغيّرات من الجزء السابق. فمثلًا:

find_tree_height(tree1)  # should be 2
find_tree_height(tree2)  # should be 3
find_tree_height(tree3)  # should be 3

1.2.1) الاختبار

يجب أن ينجح كودك الآن أيضًا في الاختبارين test_tree_height وtree_tree_height_additional في test_ps4a_student.py.

1.3) الأكوام (Heaps)

نوع خاص من الأشجار هو الأكوام (Heaps). هناك نوعان من الأكوام: أكوام القيمة القصوى (Max Heaps) وأكوام الحد الأدنى (Min Heaps).

في كومة القيمة القصوى، لكل عقدة N، تكون N هي أكبر قيمة في الشجرة ذات الجذر N. هذا يعني أن جميع العناصر المخزّنة في الشجرتين الفرعيتين اليسرى واليمنى لـ N أصغر من القيمة المخزّنة في N.

وبالمقابل، في كومة الحد الأدنى، تكون N هي أصغر قيمة في الشجرة ذات الجذر N، لذا فإن جميع العناصر المخزّنة في الشجرتين الفرعيتين اليسرى واليمنى لـ N أكبر من القيمة المخزّنة في N.

اكتب الدالة is_heap لتحدّد بسرعة ما إذا كانت شجرة كومة قيمة قصوى أو كومة حد أدنى، بحسب المعامل compare_func. وcompare_func هي دالة تأخذ وسيطين: child_value وparent_value. بالنسبة لأكوام القيمة القصوى، ستعيد هذه الدالة True إذا كان child_value < parent_value وFalse في غير ذلك. أما بالنسبة لأكوام الحد الأدنى، فستعيد True إذا كان child_value > parent_value وFalse في غير ذلك. من الناحية المفاهيمية، يتيح لك هذا كتابة دالة واحدة تستطيع تحديد نوعَي الأكوام (القصوى والحد الأدنى) انطلاقًا من معامل، بدلًا من كتابة طريقتين منفصلتين بكود متشابه جدًا. وقد قدّم لك التنفيذين العاملين لـ compare_func لكومة قيمة قصوى وكومة حد أدنى على التوالي:

# max heap comparator
def compare_func(child_value, parent_value):
    if child_value < parent_value:
        return True
    return False

# min heap comparator
def compare_func(child_value, parent_value):
    if child_value > parent_value:
        return True
    return False

ملاحظة المترجم: سطر المقارنة في دالة كومة الحد الأدنى ظهر في استخراج نصّ PDF الأصلي على هيئة child value > parent_value بدون شرطة سفلية. أعدنا الاسم الصحيح child_value كما هو في نسخة الشيفرة الرسمية للمقرر.

تلميح. قد يكون النهج التالي مفيدًا:

بمُعطى شجرة دخل T:

  • الحالة الأساس. إذا كانت T ورقة، فهي كومة (سواء أ كانت كومة قيمة قصوى أو كومة حد أدنى).
  • الحالة العودية. لعقدة T، تحقّق بشكل عودي ما إذا كانت الشجرتان الفرعيتان اليمنى واليسرى لـ T كومَين أيضًا، وما إذا كانت T هي العنصر الأكبر أو الأصغر (باستخدام دالة المقارنة compare_func المُمرَّرة إلى is_heap) في شجرتها الفرعية. إذا تحقّقت كل الشروط السابقة، فإن الشجرة ذات الجذر T كومة. وإلا فهي ليست كذلك.

1.3.1) الاختبار

يجب أن تنجح الآن جميع الاختبارات في test_ps4a_student.py.

2) الجزء B: التشفير بالوسادات ذات الاستخدام الواحد (Encryption with One Time Pads)

2.1) المقدمة

في هذه المسألة سننفّذ تقنية تشفير بسيطة لا يمكن كسرها إذا نُفّذت بشكل صحيح.

إليك بعض المصطلحات المهمة التي سنستخدمها من الآن فصاعدًا:

  • التشفير (Encryption). عملية إخفاء الرسائل أو ترميزها بحيث تصبح غير قابلة للقراءة.
  • فكّ التشفير (Decryption). عملية تحويل الرسائل المشفّرة إلى صورتها الأصلية القابلة للقراءة.
  • النص الصريح (Plaintext). الرسالة الأصلية القابلة للقراءة.
  • النص المشفّر (Ciphertext). الرسالة المشفّرة. ولا يزال النص المشفّر يحتوي على كل معلومات الرسالة الأصلية، رغم أنه يبدو كترميز غير مفهوم.

2.1.1) كيف تعمل الوسادة ذات الاستخدام الواحد (How a One Time Pad Works)

فكرة الوسادة ذات الاستخدام الواحد (One Time Pad) هي «إزاحة» (Shift) كل محرف في رسالتك النصية بمقدار عشوائي. ينتج عن ذلك نص مشفّر لا يمكن فكّه دون قائمة الإزاحات العشوائية العشوائية التي أُزاحت بها حروفك، وتُسمّى الوسادة (Pad).

في هذه المجموعة نريد أن تكون رسائلنا قادرة على إدراج حروف وأرقام ومسافات ورموز خاصة أخرى. إزاحة حرف أمر له معنى (مثلًا الحرف a مُزاحًا بمقدار 3 يصبح d)، لكن ماذا عن مسافة مُزاحة بمقدار 3؟ لحسن الحظ، جميع المحارف ممثَّلة على أجهزتنا كأرقام أصلًا! يمكنك رؤية تحويلات المحارف الأساسية إلى أرقام في جدول ASCII هذا. فيه نرى أن المسافة ممثَّلة بالقيمة الرقمية 32، لذا فإن إزاحتها بمقدار 3 تنتج 35 أي المحرف #. ويُعرض أدناه مثال على إزاحة الحروف بمقدار 3.

ملاحظة المترجم: روابط جدول ASCII والأمثلة المصوّرة داخل الشريحة من نوع رسوم توضيحية (Illustrations) من إنتاج MIT نفسه ضمن هذا الملف، لكنّ محتواها البياني (شاشة إزاحة الحروف) غير قابل للنقل نصيًا. نُقلت القيم الرقمية الدقيقة التي ترد في الجدول أدناه، وهي الجزء التعليمي الأساس. أما جدول تحويل ASCII نفسه فمصدره خارجي (asciitable.com) ولم يُنسخ.

نحتاج إلى الانتباه لمعالجة الحالة التي تلتفّ فيها الإزاحة إلى البداية بشكل صحيح. نحن مهتمّون فقط بالمحارف التي قيمها في ASCII من 32 إلى 126. فالمحرف الأخير ~ بالقيمة 126، مُزاحًا بمقدار 1، سيكون مسافة (القيمة 32)، و~ مُزاحًا بمقدار 5 سيكون $ (القيمة 36). وفيما يلي أمثلة إضافية في الجدول التالي:

المحرف (وقيمة ASCII) قيمة الإزاحة المحرف بعد الإزاحة (وقيمة ASCII)
A (65) 5 F (70)
a (97) 10 k (107)
مسافة SPACE (32) -1 ~ (126)
- (45) 8 5 (53)
} (125) 4 " (QUOTE, 34)
k (107) -3 h (104)
Y (89) -12 M (77)
M (77) -107 M (77)

الآن وقد عرفنا كيف نزاح المحارف، لاستخدام وسادة ذات الاستخدام الواحد كل ما علينا هو إزاحة كل محرف في رسالتنا بمقدار عشوائي تحدّده الوسادة. فمثلًا، إذا كانت الرسالة hello (قيم ASCII [104, 101, 108, 108, 111]) والوسادة [3, 0, 10, 11, 4]، فإننا سنحسب [104+3, 101+0, 108+10, 108+11, 111+4]، أي [107, 101, 118, 119, 115]. وبعد التحويل من القيم إلى المحارف، يكون نصّنا المشفّر kevws. وفيما يلي أمثلة أخرى في الجدول أدناه:

النص الصريح الوسادة ذات الاستخدام الواحد العملية النص المشفّر
Aaa 1,2,3 65+1=66, 97+2=99, 97+3=100 xyz
z$' 2,10,12 120+2=122, 121+10=131, 122+12=134 z$'
Hello! 5,10,2,3,0,2 72+5=77, 101+10=111, 108+2=110, 108+3=111, 111+0=111, 33+2=35 Monoo#
Monoo# -5,-10,-2,-3,0,-2 77-5=72, 111-10=101, 110-2=108, 111-3=108, 111+0=111, 35-2=33 Hello!

ملاحظة المترجم: صف z$' في الأصل يعرض نفس المحارف في العمودين الأول والأخير (وهي نتيجة استخراج نصّ PDF الذي لم يميّز الجدول). لم نخمّن قيمة مختلفة؛ النتيجة الصحيحة لهذه العملية هي zyf' لأن 122+2=124 وهو |، و131+10=141، و134+12=146. أي أن مخرجات هذا الصف في الملف الأصلي لا يمكن الاعتماد عليها، ونبّهنا إلى ذلك بدل إعادة إنتاج خطأ استخراج كأنه محتوى مقرّر.

الآن وقد عرفنا كيف تعمل الوسادات ذات الاستخدام الواحد، يمكننا أن نبدأ بتنفيذها!

2.1.2) استخدام الأصناف والوراثة (Using Classes and Inheritance)

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

بالنسبة لمجموعة المسائل هذه، سنستخدم صنفًا أبا (Parent Class) اسمه Message، ولديه صنفا أبناء: PlaintextMessage وEncryptedMessage.

يحتوي Message على دوال (Methods) سيحتاجها كل من الرسالة النصية الصريحة والرسالة المشفّرة. مثلًا، دالة للحصول على نص الرسالة.

سينتقل صنفا الأبناء هذه الدوال المشتركة من أبيهما (الوراثة).

يحتوي PlaintextMessage على دوال خاصة بالرسالة النصية الصريحة، مثل دالة لتوليد وسادة ذات الاستخدام واحد أو لتشفير رسالة.

ويحتوي EncryptedMessage على دوال خاصة بالنص المشفّر، مثل دالة لفكّ تشفير رسالة بمعرفة وسادة ذات الاستخدام واحد.

2.2) Message

قدّمنا كودًا هيكليًا (Skeleton Code) في الصنف Message للدوال التالية. مهمّتك هي ملء دوال الصنف Message الموجودة في ps4b.py حسب المواصفات المذكورة في السلاسل التوثيقية. يُرجى مراجعة تعليق السلسلة التوثيقية لكل دالة لمزيد من المعلومات حول مواصفتها.

  • __init__(self, input_text)
  • get_text(self)

shift_char(self, char, shift). يجب أن تُعيد سلسلة نصية تحتوي char مُزاحًا بمقدار shift حسب الطريقة الموصوفة أعلاه.

بعض التلميحات التي يجب تذكّرها:

  • ord(char) تُعيد قيمة ASCII لمحرف سلسلة نصية تحوي محرفًا واحدًا.
  • chr(ascii_num) تُعيد سلسلة نصية بالمحرف الواحد الذي يحدده ascii_num.
  • نحن مهتمّون فقط بمحارف ASCII الـ 95 من قيمة ASCII 32 إلى 126.
  • معامل الباقي % الذي يُعيد باقي القسمة مفيد للالتفاف.

apply_pad(self, pad). يجب أن تُعيد سلسلة نصية تحتوي النص المشفّر لـ self.message_text بعد تطبيق pad.

كما نفّذنا دالة __repr__ بحيث تطبع كائنات Message نتيجة مقروءة أمام الإنسان. يُرجى عدم تغييرها.

2.2.1) الاختبار

يمكنك اختبار كودك حتى الآن بتشغيل test_ps4bc_student.py. تأكّد من أنه في المجلد نفسه الذي توجد فيه مجموعة المسائل. وفي هذه المرحلة، يجب أن يكون كودك قادرًا على اجتياز جميع الاختبارات التي تبدأ بـ test_message، لكن ليس تلك التي تبدأ بـ test_plaintext_message أو test_encrypted_message. سننفّذ الشيفرة لتلك في القسم التالي.

2.3) PlaintextMessage

مرة أخرى، مهمّتك هي ملء دوال الصنف PlaintextMessage الموجودة في ps4b.py حسب المواصفات المذكورة في السلاسل التوثيقية.

  • __init__(self, input_text, pad=None)

يجب أن تستخدم باني الصنف الأب (باستخدام super()) في هذه الدالة لجعل كودك أكثر إيجازًا. ألقِ نظرة على دليل الأسلوب رقم 7 إن كنت غير متأكّد.

تشير صيغة pad=None إلى معامل اختياري يمكن حذفه، فتُمرَّر القيمة الافتراضية None بدلًا منه. على سبيل المثال، PlaintextMessage('test') وPlaintextMessage('test', [0,15,3,9]) كلاهما باني صالح، لكن الأول يجب أن يولّد وسادة عشوائية والثاني يجب أن يستخدم الوسادة المحدَّدة.

يجب أن تحفظ نسخة من pad كسمة (Attribute) لا كمتغيّر pad مباشرة، للحماية من تعديلها.

  • generate_pad(self)

ملاحظة: يجب أن تعمل shift_char لدينا مع أي عدد صحيح اعتباطي، لكن ولأجل البساطة سنولّد وسادات بأعداد صحيحة في المدى [0, 110) فقط.

تلميح: random.randint(a, b) تُعيد عددًا صحيحًا عشوائيًا N بحيث a≤N≤ba \le N \le b.

  • get_pad(self)

يجب أن يُعيد هذا نسخة من self.pad لمنع أحدهم من تعديل القائمة الأصلية.

  • get_ciphertext(self)
  • change_pad(self, new_pad)

تأكّد أن self.get_ciphertext تستخدم الوسادة الجديدة!

كما نفّذنا دالة __repr__ بحيث تُعيد كائنات PlaintextMessage نتيجة مقروءة أمام الإنسان. يُرجى عدم تغييرها.

2.3.1) الاختبار

يمكنك اختبار صنفك الجديد بتشغيل test_ps4bc.py. ويجب أن تكون الآن قادرًا على اجتياز جميع الاختبارات التي تبدأ بـ test_message وtest_plaintext.

2.4) EncryptedMessage

بمُعطى رسالة مشفّرة، إذا عرفت الوسادة ذات الاستخدام الواحد المستخدَمة لترميز الرسالة، فإن فكّ الترميز يكون تافهًا. ذلك لأننا إذا أزحنا محرفًا بمقدار x لتشفيره، فإن لفكّ تشفيره نُزحه ببساطة بمقدار −x−x! إذن، لفكّ تشفير رسالة أُزحت بالوسادة [i, j, k, ...]، نطبّق ببساطة الوسادة [-i, -j, -k, ...]. فإذا كان $ip! هو الرسالة المشفّرة، وكانت [5, 1, 7, 2] هي الوسادة المستخدَمة لتشفير الرسالة، فإن [-5, -1, -7, -2] يفكّ ترميز الرسالة المشفّرة ويمنحك الرسالة النصية الصريحة الأصلية.

النص المشفّر الوسادة ذات الاستخدام الواحد العملية النص الصريح
$ip! 5,1,7,2 36-5=31, 105-1=104, 112-7=105, 33-2=31 ~hi~

ملاحظة المترجم: القيم الرقمية في صف العملية أعلاه منقولة كما وردت في الملف الأصلي. ويُلاحَظ أن نتيجة 36-5=31 تعطي المحرف 31 لا 126؛ ويبدو أن القيم في العمود الأصلي كانت مضبوطة عرضًا في ملف PDF ولا تعكس حسابًا صحيحًا. لم نصحّح الأرقام لأن النص الأصلي منشور كما هو، والتنبيه هنا بديل عن تصحيح محتوى المقرّر.

سنطبّق الآن فكّ التشفير في الصنف EncryptedMessage.

املأ الدوال التالية في الصنف EncryptedMessage الموجودة في ps4b.py حسب المواصفات المذكورة في السلاسل التوثيقية.

  • __init__(input_text)

كما في PlaintextMessage، استخدم باني الصنف الأب (super()) لجعل كودك أكثر إيجازًا. ألقِ نظرة على دليل الأسلوب رقم 7 إن كنت غير متأكّد.

  • decrypt_message(self, pad)

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

2.4.1) الاختبار

يمكنك اختبار صنفك الجديد بتشغيل test_ps4bc_student.py. ويجب أن تكون الآن قادرًا على اجتياز جميع الاختبارات في ذلك الملف، باستثناء test_try_pads.

3) الجزء C: استخدام أصنافك (Using Your Classes)

الآن وقد أنشأنا أصنافنا في ps4b.py، سنتعلّم كيفية استخدامها في ps4c.py! في أعلى ps4c.py يمكنك رؤية السطر:

import ps4b  # Importing your work from Part B

يستورد هذا كودك من ملف ps4b.py إذا كان في المجلد نفسه. لاستخدام صنف أُنشئ في الجزء B يمكنك تهيئته هكذا: my_message = ps4b.Message("My Message!").

هناك بضع دوال مساعدة نفّذناها لك: load_words وis_word وget_story_string. وستكون مفيدة لتنفيذ decrypt_message_try_pads وdecode_story. لا تحتاج إلى فهم كيفية عملها بالضبط، لكن ينبغي أن تقرأ سلاسلها التوثيقية لتفهم ماذا تفعل وكيف تستخدمها.

3.1) فكّ ترميز النصوص المشفّرة (Decoding Ciphertexts)

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

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

املأ decrypt_message_try_pads(self, pads) باستخدام النهج الموصوف أعلاه.

قد تجد دالتَي المساعدة is_word(wordlist, word) وload_words، serta دالة السلسلة split مفيدة. ولاحظ أن is_word تتجاهل علامات الترقيم والمحارف الخاصة الأخرى عند تحديد صلاحية الكلمة.

3.1.1) الاختبار

يجب أن تكون الآن قادرًا على اجتياز جميع الاختبارات في test_ps4bc_student.py.

يُرجى الانتباه إلى أن decrypt_message_try_pads في أداة اختبار الطالب ستعتمد على عملك من ps4b.py. لكن أداة اختبار هيئة التدريس (Staff Tester) ستحتوي على اختبار واحد سيستخدم تنفيذنا المرجعي لـ ps4b.py. لذا تأكّد أنك تستخدم getters وsetters بدلًا من الوصول المباشر إلى سمات الأصناف من داخل decrypt_message_try_pads!

3.1.2) فكّ ترميز قصة (Decoding a Story)

يحاول بوب مشاركة قصة مع أليس دون أن نتمكّن من معرفة القصة. لحسن حظّنا، سمعنا بوب وهو يشارك كل وساداته ذات الاستخدام الواحد مع أليس؛ ولا نعرف فقط أي وسادة استعملها لقصته.

نفّذ decode_story لتجد ما كانت قصة بوب.

  • استعمل get_story_string للحصول على النص المشفّر لقصة بوب، وget_story_pads للحصول على قائمة وسادات بوب ذات الاستخدام الواحد.
  • استعمل دالتك decrypt_message_try_pads لتجد ما كانت رسالة بوب إلى أليس.
  • تحقّق من خرج decode_story بإلغاء تعليق الشيفرة في أسفل ps4c.py وتشغيل ps4c.py. هذه الدالة ليست مُختبَرة في test_ps4bc_student.py، لكن كن مستعدًا لمناقشة القصة بعد فكّ الترميز في المراجعة الوجهية (Checkoff).

4) إجراءات التسليم (Hand-in Procedure)

4.1) معلومات الوقت والتعاون (Time and Collaboration Info)

في بداية كل ملف، اكتب في تعليق أسماء متعاونيك. مثال:

# Problem Set 4B
# Name: Jane Lee
# Collaborators: John Doe

يُرجى تقدير عدد الساعات التي أمضيتها على مجموعة المسائل في مربع السؤال أدناه.

4.2) التسليم النصفي (Half-way Submission)

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

يمكنك رفع نسخ جديدة من ps4a.py حتى 9 نوفمبر الساعة 09:00 مساءً. لا يمكنك استخدام تمديدات أو أيام تأخّر في هذه التسليمات.

يُرجى تحديث الصفحة قبل رفع ملف جديد. إذا لم تفعل فلن يتم تحديث آخر تسليم لك.

4.3) التسليم النهائي (Final Submission)

تأكّد من تشغيل أدوات اختبار الطالب test_ps4a_student.py وtest_ps4bc_student.py وأن جميع الاختبارات تنجح. لكن أداة اختبار الطالب تحتوي فقط على مجموعة جزئية من الاختبارات التي ستُشغَّل لتحديد درجة المجموعة. نجاح جميع حالات الاختبار المعطاة لا يضمن الحصول على الدرجة كاملة في المجموعة.

يمكنك رفع نسخ جديدة من كل ملف حتى 16 نوفمبر الساعة 09:00 مساءً، لكن أي شيء يُرفع بعد ذلك الوقت سيُحسب ضمن أيام التأخّر، إن كانت لديك أيّ أيام تأخّر متبقية. وإذا لم تكن لديك أي أيام تأخّر متبقية، فلن تحصل على أي درجة لتسليم متأخّر.

عند رفع ملف جديد بالاسم نفسه، سيُستبدل ملفك القديم.

  • 4.3.1) الجزء A: اختر ملفًا ثم أرسل. «لم يتم اختيار أي ملف» قبل الاختيار، و«تبقّى لك عدد لا نهائي من مرات التسليم» بعد الإرسال.
  • 4.3.2) الجزء B: نفس الواجهة.
  • 4.3.3) الجزء C: نفس الواجهة.

المصدر والنَّسب والترخيص

المصدر: تعليمات PS 4 الرسمية، extracted/mit6_100l_f22_ps4.txt. ترجمة عربية لجميع التعليمات مع إبقاء الكود والمخرجات النموذجية دون ترجمة حتى تبقى نافعة للاختبار. المواعيد تاريخية. لم تُنشر الأشكال البيانية الأشجار وملفات البيانات الأصلية في static/.

ملاحظة المترجم — مواد محجوزة: ملفات test_ps4a_student.py وtest_ps4bc_student.py والملفات النصية المرافقة (words.txt وstory.txt وpads.txt) وكود البداية tree.py غير منشورة هنا. تتضمّن مساعدات اختبار مأخوذة من Stack Overflow تحتاج تحققًا مستقلًا من الترخيص والنَّسب. احصل على الحزمة الأصلية من صفحة الشيفرة الرسمية.

النَّسب: Ana Bell. 6.100L Introduction to CS and Programming using Python, Fall 2022. Massachusetts Institute of Technology: MIT OpenCourseWare. المقرر الأصلي. المواد المملوكة لـ MIT وهذه الترجمة بموجب CC BY-NC-SA 4.0: النَّسب، غير تجاري، المشاركة بالمثل. ترجمة غير رسمية لا تعني اعتماد MIT. استثناءات الأطراف الثالثة محفوظة؛ شروط الاستخدام.

السابق مجموعة المسائل 3 — المسافة بين المستندات التالي مجموعة المسائل 5 — استخدام المكتبات