أنظمة العد
- القيم الموضعية
- الثنائي 2k، الثماني 8k، الست عشري 16k
- إلى العشري
- Σ dk·bk
- من العشري
- اقسم على الأساس، واقرأ البواقي من الأسفل إلى الأعلى
- الست عشري ↔ الثنائي
- رقم ست عشري واحد = 4 بتات
- المتمم الثنائي
- اعكس البتات وأضف 1
أوراق القوانين، وأهم خطوات الحل لكل موضوع، و20 مسألة تدريبية، مع الحلول الكاملة في الخلف.
النمط ذو 8 بتات 1101 1111 يخزّن عددًا صحيحًا بإشارة بصيغة المتمم الثنائي. ما قيمته N في النظام العشري؟
صورة غير مضغوطة أبعادها 1920 × 1080 بكسل و8 بت لكل بكسل. كم تشغل من الذاكرة M بوحدة KiB (1 KiB = 1024 بايت)؟
هل (q ∨ r) → (q ∧ r) حشو أم تناقض أم ممكنة؟ انقر على إجابتك.
الحجة ذات المقدمات r → q; ¬r والاستنتاج ¬q غير صحيحة. انقر على صف جدول الصدق الذي يمثل مثالًا مضادًا.
بسّط F = BC + ABC + ABC′ إلى الصيغة الدنيا لمجموع الجداءات. كم حرفًا L يحتوي التعبير المبسَّط؟
قلّاب D يُحفَّز بالحافة الموجبة يبدأ بـ Q = 0 ويتلقى المداخل المعروضة. انقر على أول حافة ساعة ينتقل عندها Q من 1 عائدًا إلى 0.
جد معكوس 30 بالنسبة إلى 79: العدد x مع 0 < x < 79 و 30·x ≡ 1 (mod 79).
يستخدم مفتاح RSA القيم p = 7 و q = 13 و e = 11. فكّ تشفير النص المشفّر c = 45: جد الرسالة m.
بقطع نقدية من فئات 1 و3 و4 ومبلغ 6، كم قطعة تستخدم الطريقة الجشعة "أكبر قطعة أولًا" مقارنةً بالحل الأمثل؟
أي عبارة عن ترميز o الصغير صحيحة؟
لعقدة في شجرة بحث ثنائية شجرة فرعية يمنى. أين يقع تاليها في الترتيب الوسطي (in-order successor)؟
لماذا تستخدم قواعد البيانات غالبًا أشجار B+ بدلًا من أشجار B العادية للفهارس؟
كم دارة هاملتون مختلفة H للبيان التام K4؟ الدارات التي تختلف فقط في رأس البداية أو الاتجاه تُعدّ واحدة.
استخدم خوارزمية ديكسترا لإيجاد طول d(F) أقصر مسار من A إلى F في البيان الموزون.
أي عبارة عن HAVING صحيحة؟
ما العيب المعروف لتفكيك الجداول إلى BCNF مقارنة بـ 3NF؟
تنتقل إشارة مسافة 2000 km عبر الألياف بسرعة نحو 2 × 10⁸ m/s. ما تأخير الانتشار؟
لا يستطيع المضيفون في VLAN 10 وVLAN 20 على المبدّل نفسه الاتصال ببعضهم. ما المطلوب؟
يحتاج قسم إلى 630 عنوان مضيف في شبكة فرعية واحدة. ما أطول بادئة p (أصغر شبكة فرعية) تكفي؟
عنوان مضيف هو 10.20.115.64/26. ما الثُمانية الرابعة x من آخر عنوان مضيف قابل للاستخدام في شبكته الفرعية؟
الإجابة: N = −33
أنظمة العد الموضعية: قيمة كل رقم هي قيمته مضروبة في قوة من قوى الأساس. في النظام الثنائي تساوي المواضع 1، 2، 4، 8، 16، …؛ وفي السداسي عشري 1، 16، 256، …، حيث تمثل A–F القيم 10–15. في المتمم الثنائي ذي 8 بتات تساوي البتة اليسرى −128 بدلًا من +128، وهكذا تُخزَّن الأعداد السالبة.
تحتفظ البتات الأخرى بقيمها الموجبة المعتادة.
الإجابة: M = 2025 KiB
أنظمة العد الموضعية: قيمة كل رقم هي قيمته مضروبة في قوة من قوى الأساس. في النظام الثنائي تساوي المواضع 1، 2، 4، 8، 16، …؛ وفي السداسي عشري 1، 16، 256، …، حيث تمثل A–F القيم 10–15. في المتمم الثنائي ذي 8 بتات تساوي البتة اليسرى −128 بدلًا من +128، وهكذا تُخزَّن الأعداد السالبة.
الإجابة: ممكنة
التكافؤ المنطقي: تتكافأ صيغتان (≡) عندما يكون لهما القيمة نفسها في كل صف من جدول الصدق. الحشو يساوي 1 في كل صف، والتناقض يساوي 0 في كل صف، والممكن ليس هذا ولا ذاك. قوانين مفيدة: دي مورغان، ¬(a ∧ b) ≡ ¬a ∨ ¬b و ¬(a ∨ b) ≡ ¬a ∧ ¬b؛ و a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (العكس النقيض)؛ و ¬(a → b) ≡ a ∧ ¬b؛ وقوانين التوزيع، a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
الإجابة: q = 1, r = 0
الكمّمات والحجج: ¬∀x P(x) ≡ ∃x ¬P(x) و ¬∃x P(x) ≡ ∀x ¬P(x). انقل النفي إلى الداخل، وبدّل كل كمّم يمرّ به، وانفِ الصيغة الداخلية بقوانين المنطق القضوي، مثل ¬(a → b) ≡ a ∧ ¬b. تكون الحجة صحيحة عندما يكون الاستنتاج 1 في كل صف تكون فيه كل المقدمات 1. صف واحد بمقدمات صائبة واستنتاج خاطئ هو مثال مضاد ويبيّن أن الحجة غير صحيحة.
حجة بهذه الصيغة تبدو قاعدة صحيحة، لكن صفًا واحدًا يكفي لإثبات أنها ليست كذلك.
الإجابة: L = 4
الجبر البولياني: القواعد التي تبسّط التعابير هي X + X′ = 1 و X·X′ = 0، و X + X = X، والامتصاص X + X·Y = X، وقاعدة الدمج X·Y + X·Y′ = X، و X + X′Y = X + Y، ومبرهنة الإجماع XY + X′Z + YZ = XY + X′Z. تحوّل قوانين دي مورغان (X·Y)′ إلى X′ + Y′ و (X + Y)′ إلى X′·Y′. وتطبّق خريطة كارنو هذه القواعد بيانيًا: كل مجموعة من خليتين متجاورتين هي استخدام واحد لـ XY + XY′ = X.
الإجابة: حافة الساعة 4
القلّابات والعدّادات: لا يتغير القلّاب إلا عند الحافة الفعالة للساعة. يَنسخ D مدخله (Q⁺ = D)؛ و T يتبدّل عندما T = 1؛ و JK يحتفظ عند 00، ويصفّر عند 01، ويضبط عند 10، ويتبدّل عند 11. للعدّاد الثنائي ذي n بتّات 2ⁿ حالة ويعدّ بالنمط 2ⁿ؛ وعدّاد mod-N يعدّ 0 و 1 … حتى N − 1 ثم يعود إلى 0، ويحتاج إلى أصغر n يحقق 2ⁿ ≥ N قلّابات. تُنصّف كل مرحلة في العدّاد المتموّج التردد، فيعمل الخرج الأخير لعدّاد mod-N بالتردد fclk/N. لعدّاد جونسون من n قلّابات 2n حالة، وللعدّاد الحلقي n.
يَنسخ قلّاب D القيمة D عند كل حافة صاعدة: Q⁺ = D.
الإجابة: 30−1 mod 79 = 29
المعكوسات والتطابقات: للعدد a معكوس بالنسبة إلى n بالضبط عندما gcd(a, n) = 1. تكتب خوارزمية إقليدس الموسّعة 1 = s·n + t·a، ثم a⁻¹ ≡ t (mod n). التطابق a·x ≡ b (mod n) مع gcd(a, n) = 1 حلّه x ≡ a⁻¹·b. لتطابقين x ≡ r₁ (mod m₁) و x ≡ r₂ (mod m₂) بمقياسين أوليين فيما بينهما حل واحد بالنسبة إلى m₁·m₂ (مبرهنة الباقي الصينية). تعدّ φ(n) لأويلر الأعداد من 1 إلى n التي أولية مع n: φ(n) = n·∏(1 − 1/p).
يُكتب كل باقٍ r بالشكل r ≡ t·30 (mod 79).
الإجابة: m = 89
القوى المودولية وRSA: احسب aᵏ mod n بالتربيع المتكرر: اكتب k بالنظام الثنائي، وربّع، واختزل بعد كل خطوة، واضرب القوى التي بتّها 1. فيرما: aᵖ⁻¹ ≡ 1 (mod p) لعدد أولي p لا يقسم a، فيمكن اختزال الأس بالنسبة إلى p − 1. RSA: اختر عددين أوليين p و q، و n = p·q و φ(n) = (p − 1)(q − 1)؛ الأس العام e أولي مع φ(n)، والأس الخاص d = e⁻¹ mod φ(n). شفّر بـ c = mᵉ mod n وفكّ التشفير بـ m = cᵈ mod n.
الإجابة: B · تستخدم الجشعة 3 قطع، والأمثل 2
تأخذ الطريقة الجشعة 4 + 1 + 1 = 3 قطع، لكن 3 + 3 تستخدم قطعتين فقط، فالجشعة ليست مثلى لهذا النظام النقدي، أما البرمجة الديناميكية فمثلى.
الإجابة: B · n = o(n²)، لكن n ليست o(n)
f = o(g) تعني أن f(n) / g(n) تؤول إلى 0، وn / n² تؤول إلى 0، لكن n / n = 1 لا تؤول إليه.
الإجابة: D · العقدة الأقصى يسارًا في شجرتها الفرعية اليمنى
كل المفاتيح الأكبر القريبة من العقدة في شجرتها الفرعية اليمنى، وأصغرها هو العقدة الأقصى يسارًا هناك.
الإجابة: B · لأن كل السجلات في أوراق مترابطة، ما يجعل مسح المدى فعالًا
في شجرة B+ لا توجّه العقد الداخلية إلا البحث، والأوراق مترابطة بترتيب المفاتيح، فيجد استعلام المدى المفتاح الأول ثم يسير على طول الأوراق.
الإجابة: H = 3
أويلر وهاملتون والأشجار: لبيان متصل دارة أويلر (كل حافة مرة واحدة، والعودة إلى البداية) عندما تكون لكل رأس درجة زوجية، ومسار أويلر ليس دارة عندما تكون لرأسين بالضبط درجة فردية؛ ويسير المسار عندئذ من أحد الرأسين الفرديين إلى الآخر. تزور دارة هاملتون كل رأس مرة واحدة؛ وفي Kn منها (n − 1)!/2. للشجرة على n رأسًا n − 1 حافة، ويحتفظ بيان متصل ذو m حافة بشجرة ممتدة بعد حذف m − n + 1 حافة.
الإجابة: d(F) = 26
أقصر المسارات والأشجار الممتدة: تثبّت خوارزمية ديكسترا رأسًا واحدًا في كل جولة: الرأس غير المثبّت ذا أصغر مسافة مؤقتة. تصبح مسافته نهائية، ويأخذ كل جار v القيمة d(v) = min(d(v), d(u) + w(u, v)). تبني خوارزمية كروسكال شجرة ممتدة دنيا بأخذ الحواف من الأخف إلى الأثقل وتخطّي كل حافة تُغلق دورة؛ وتنمّي خوارزمية برايم شجرة واحدة من رأس البداية بإضافة أخف حافة تغادرها دائمًا. وللشجرة الممتدة على n رأسًا n − 1 حافة.
كل سطر: الرأس المثبَّت، ومسافته النهائية، والجيران الذين تتحسن مسافتهم.
الإجابة: D · يمكنها استخدام الدوال التجميعية لترشيح المجموعات
تُرشّح HAVING المجموعات بعد التجميع ويمكنها الإشارة إلى الدوال التجميعية؛ أما WHERE فلا يمكنها ذلك.
الإجابة: D · قد لا يعود ممكنًا التحقق من بعض الاعتماديات الدالية داخل جدول واحد
يوجد دائمًا تفكيك BCNF غير فاقد، لكنه قد لا يحفظ الاعتماديات؛ أما 3NF فيمكن دائمًا أن تكون غير فاقدة وحافظة للاعتماديات معًا.
الإجابة: D · 10 ms
2 × 10⁶ m / 2 × 10⁸ m/s = 0,01 s = 10 ms. ويتوقف تأخير الانتشار على المسافة والوسط، لا على حجم الحزمة.
الإجابة: D · موجّه أو مبدّل من الطبقة 3 للتوجيه بين شبكات VLAN
شبكات VLAN معزولة في الطبقة 2، فيجب توجيه الحركة بينها، مثلًا بموجّه على وصلة trunk ("router on a stick") أو بمبدّل من الطبقة 3.
الإجابة: p = 22
تقسيم شبكات IPv4: يتكون العنوان من 32 بتة. تحدد البادئة /p عدد البتات الأولى التي تعرّف الشبكة؛ وتُرقّم البتات المتبقية 32 − p المضيفين. تحتوي الشبكة الفرعية على 2³²⁻ᵖ عنوانًا، لكن الأول (عنوان الشبكة) والأخير (عنوان البث) لا يُعطيان للمضيفين، فيتسع 2³²⁻ᵖ − 2 مضيفًا. الاستثناءات: الشبكة /31 (وصلة من نقطة إلى نقطة، RFC 3021) تستخدم كلا عنوانَيها الـ 2 للمضيفين، والشبكة /32 عنوان واحد فقط (مضيف واحد أو عنوان loopback).
الإجابة: x = 126
تقسيم شبكات IPv4: يتكون العنوان من 32 بتة. تحدد البادئة /p عدد البتات الأولى التي تعرّف الشبكة؛ وتُرقّم البتات المتبقية 32 − p المضيفين. تحتوي الشبكة الفرعية على 2³²⁻ᵖ عنوانًا، لكن الأول (عنوان الشبكة) والأخير (عنوان البث) لا يُعطيان للمضيفين، فيتسع 2³²⁻ᵖ − 2 مضيفًا. الاستثناءات: الشبكة /31 (وصلة من نقطة إلى نقطة، RFC 3021) تستخدم كلا عنوانَيها الـ 2 للمضيفين، والشبكة /32 عنوان واحد فقط (مضيف واحد أو عنوان loopback).
ExamProblems · examproblems.com/courses/computer-science-fundamentals