أنظمة العد
- القيم الموضعية
- الثنائي 2k، الثماني 8k، الست عشري 16k
- إلى العشري
- Σ dk·bk
- من العشري
- اقسم على الأساس، واقرأ البواقي من الأسفل إلى الأعلى
- الست عشري ↔ الثنائي
- رقم ست عشري واحد = 4 بتات
- المتمم الثنائي
- اعكس البتات وأضف 1
أوراق القوانين، وأهم خطوات الحل لكل موضوع، و20 مسألة تدريبية، مع الحلول الكاملة في الخلف.
اكتب −112 كنمط متمم ثنائي ذي 8 بتات. اقرأ النمط كعدد ثنائي بلا إشارة: ما قيمته U في النظام العشري؟
صورة غير مضغوطة أبعادها 512 × 512 بكسل و24 بت لكل بكسل. كم تشغل من الذاكرة M بوحدة KiB (1 KiB = 1024 بايت)؟
تريد إثبات (a ∨ b) → c بالعكس النقيض. أي استلزام تبرهن بدلًا منه؟ انقر عليه.
كم صفًا من الصفوف الـ 16 لجدول الصدق تجعل (b ∨ ¬c) → ((¬d → b) ↔ (a ∧ ¬c)) صائبة؟ سمِّ هذا العدد N.
لمضاعِف 4-إلى-1 مدخلا الاختيار S₁ = A و S₀ = B، ومداخل بياناته موصولة بـ I₀ = C′, I₁ = C′, I₂ = 0, I₃ = 1. في كم من تركيبات A و B و C الثماني يكون المخرج F = 1؟ جد N.
قلّاب T يُحفَّز بالحافة الموجبة يبدأ بـ Q = 0 ويتلقى المداخل المعروضة عند 8 حافة ساعة صاعدة. كم مرة N يغيّر Q حالته؟
حلّ 13x ≡ 1 (mod 19). أعطِ الحل x مع 0 < x < 19.
61 عدد أولي. استخدم مبرهنة فيرما الصغرى لإيجاد 420983 mod 61.
يستخدم فرز سريع العنصر الأول محورًا دائمًا. على أي مدخل يُظهر سلوك أسوأ الحالات؟
ماذا سيترتب لو وجد أحدهم خوارزمية كثيرة حدود لمسألة NP-تامة واحدة؟
طابور منفّذ بمكدسين: push إلى مكدس "in"، وpop من مكدس "out" مع إعادة ملئه من "in" حين يفرغ. ما الكلفة المستهلَكة لكل عملية؟
أي زوج من الاجتيازات يحدد دائمًا شجرة ثنائية فريدة ذات مفاتيح متمايزة؟
هل للبيان المتصل دارة أويلر، أم مسار أويلر ليس دارة، أم لا هذه ولا تلك؟ انقر على إجابتك.
استخدم خوارزمية ديكسترا لإيجاد طول d(F) أقصر مسار من A إلى F في البيان الموزون.
تزيل الصيغة الطبيعية الثالثة (3NF):
ينفّذ تطبيق UPDATE item SET qty = 4, version = 8 WHERE id = 1 AND version = 7، ويبلّغ عن تعارض إذا لم يُحدَّث أي صف. ما هذه التقنية؟
ما دور البوابة الافتراضية (default gateway) على المضيف؟
بعد التصادمات المتكررة تختار محطات Ethernet الكلاسيكية زمن انتظارها من نطاق يتضاعف في كل مرة. لماذا؟
يجب تقسيم الشبكة 192.168.10.0/24 إلى 3 شبكات فرعية متساوية على الأقل. إذا استعرت أقل عدد ممكن من البتات، فكم مضيفًا قابلًا للاستخدام H في كل شبكة فرعية؟
عنوان مضيف هو 10.20.93.238/27. ما الثُمانية الرابعة x من آخر عنوان مضيف قابل للاستخدام في شبكته الفرعية؟
الإجابة: U = 144
أنظمة العد الموضعية: قيمة كل رقم هي قيمته مضروبة في قوة من قوى الأساس. في النظام الثنائي تساوي المواضع 1، 2، 4، 8، 16، …؛ وفي السداسي عشري 1، 16، 256، …، حيث تمثل A–F القيم 10–15. في المتمم الثنائي ذي 8 بتات تساوي البتة اليسرى −128 بدلًا من +128، وهكذا تُخزَّن الأعداد السالبة.
الإجابة: M = 768 KiB
أنظمة العد الموضعية: قيمة كل رقم هي قيمته مضروبة في قوة من قوى الأساس. في النظام الثنائي تساوي المواضع 1، 2، 4، 8، 16، …؛ وفي السداسي عشري 1، 16، 256، …، حيث تمثل A–F القيم 10–15. في المتمم الثنائي ذي 8 بتات تساوي البتة اليسرى −128 بدلًا من +128، وهكذا تُخزَّن الأعداد السالبة.
الإجابة: ¬c → ¬(a ∨ b)
التكافؤ المنطقي: تتكافأ صيغتان (≡) عندما يكون لهما القيمة نفسها في كل صف من جدول الصدق. الحشو يساوي 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).
العكس النقيض يكافئ العبارة الأصلية، فإثباته يثبت العبارة.
الإجابة: N = 8
جداول الصدق: للصيغة ذات n متغيرًا مختلفًا 2ⁿ صفًا، صف لكل تركيبة من قيم الصدق (1 = صواب، 0 = خطأ). اعمل من الداخل إلى الخارج وأعطِ كل صيغة جزئية عمودها الخاص. ¬a تقلب القيمة؛ و a ∧ b تساوي 1 فقط عندما تكون القيمتان 1؛ و a ∨ b تساوي 0 فقط عندما تكون القيمتان 0؛ و a → b تساوي 0 فقط عندما a = 1 و b = 0؛ و a ↔ b تساوي 1 عندما يتساوى الطرفان.
الإجابة: N = 4
المضاعِف (MUX): يمرّر المضاعِف 2ⁿ-إلى-1 أحد مداخل البيانات إلى المخرج؛ وخطوط الاختيار، مقروءة كعدد ثنائي، تحدد أيّها. لمضاعِف 4-إلى-1 مع الاختيارين S₁S₀ = AB، F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃. وبوصل مداخل البيانات بـ 0 أو 1 أو C أو C′ ينتج المضاعِف أي دالة في A و B و C، وهي طريقة شائعة لبناء المنطق بشريحة واحدة.
الإجابة: N = 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.
يتبدّل قلّاب T عند كل حافة صاعدة مع T = 1 ويحتفظ بقيمته مع T = 0.
الإجابة: x = 3
المعكوسات والتطابقات: للعدد 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).
الإجابة: 420983 mod 61 = 19
القوى المودولية و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.
الإجابة: C · مصفوفة مرتبة مسبقًا
في المدخلات المرتبة يكون المحور دائمًا الأصغر، فيكون أحد الجانبين فارغًا والآخر فيه n − 1 عنصر، فيكون التعقيد O(n²).
الإجابة: B · يمكن حل كل مسألة في NP في زمن كثير حدود، أي P = NP
بما أن كل NP تُختزل إلى أي مسألة NP-تامة في زمن كثير حدود، فإن خوارزمية سريعة لواحدة تعطي خوارزمية سريعة للجميع.
الإجابة: B · O(1)
يُدفع كل عنصر ويُسحب مرتين على الأكثر إجمالًا، فرغم أن إعادة ملء واحدة قد تستغرق O(n)، يكون المتوسط على سلسلة العمليات O(1).
الإجابة: A · القبلي والوسطي
يعطي الاجتياز القبلي الجذر، وموضعه في المتتالية الوسطية يفصل الشجرتين الفرعيتين اليسرى واليمنى، أما القبلي مع البعدي فملتبس حين يكون للعقدة ابن واحد.
الإجابة: مسار أويلر دون دارة
أويلر وهاملتون والأشجار: لبيان متصل دارة أويلر (كل حافة مرة واحدة، والعودة إلى البداية) عندما تكون لكل رأس درجة زوجية، ومسار أويلر ليس دارة عندما تكون لرأسين بالضبط درجة فردية؛ ويسير المسار عندئذ من أحد الرأسين الفرديين إلى الآخر. تزور دارة هاملتون كل رأس مرة واحدة؛ وفي Kn منها (n − 1)!/2. للشجرة على n رأسًا n − 1 حافة، ويحتفظ بيان متصل ذو m حافة بشجرة ممتدة بعد حذف m − n + 1 حافة.
يبدأ مسار أويلر عند أحد الرأسين الفرديين وينتهي عند الآخر.
الإجابة: d(F) = 40
أقصر المسارات والأشجار الممتدة: تثبّت خوارزمية ديكسترا رأسًا واحدًا في كل جولة: الرأس غير المثبّت ذا أصغر مسافة مؤقتة. تصبح مسافته نهائية، ويأخذ كل جار v القيمة d(v) = min(d(v), d(u) + w(u, v)). تبني خوارزمية كروسكال شجرة ممتدة دنيا بأخذ الحواف من الأخف إلى الأثقل وتخطّي كل حافة تُغلق دورة؛ وتنمّي خوارزمية برايم شجرة واحدة من رأس البداية بإضافة أخف حافة تغادرها دائمًا. وللشجرة الممتدة على n رأسًا n − 1 حافة.
كل سطر: الرأس المثبَّت، ومسافته النهائية، والجيران الذين تتحسن مسافتهم.
الإجابة: C · الاعتماديات المتعدية بين السمات غير المفتاحية
في 3NF لا تعتمد أي سمة غير مفتاحية على سمة غير مفتاحية أخرى، كتخزين المدينة والرمز البريدي حين تعتمد المدينة على الرمز البريدي.
الإجابة: B · التحكم المتفائل في التزامن
يفترض القفل المتفائل أن التعارضات نادرة: فيتحقق من عمود الإصدار عند الكتابة ويفشل إذا كانت معاملة أخرى قد غيّرت الصف في هذه الأثناء.
الإجابة: B · هي الموجّه المستخدم لحركة المرور المتجهة إلى شبكات أخرى
يرسل المضيف الحزم الموجهة إلى وجهات غير محلية إلى البوابة الافتراضية، وهي عادةً الموجّه المحلي.
الإجابة: B · لتقليل احتمال التصادم مجددًا عندما تتنافس محطات كثيرة
يشير كل تصادم إضافي إلى تنافس أكبر، فيتسع النطاق العشوائي ويزيد احتمال اختيار المحطات فتحات زمنية مختلفة. وهذا يتكيف مع الحمل دون تحكم مركزي.
الإجابة: H = 62
تقسيم شبكات IPv4: يتكون العنوان من 32 بتة. تحدد البادئة /p عدد البتات الأولى التي تعرّف الشبكة؛ وتُرقّم البتات المتبقية 32 − p المضيفين. تحتوي الشبكة الفرعية على 2³²⁻ᵖ عنوانًا، لكن الأول (عنوان الشبكة) والأخير (عنوان البث) لا يُعطيان للمضيفين، فيتسع 2³²⁻ᵖ − 2 مضيفًا. الاستثناءات: الشبكة /31 (وصلة من نقطة إلى نقطة، RFC 3021) تستخدم كلا عنوانَيها الـ 2 للمضيفين، والشبكة /32 عنوان واحد فقط (مضيف واحد أو عنوان loopback).
الإجابة: x = 254
تقسيم شبكات IPv4: يتكون العنوان من 32 بتة. تحدد البادئة /p عدد البتات الأولى التي تعرّف الشبكة؛ وتُرقّم البتات المتبقية 32 − p المضيفين. تحتوي الشبكة الفرعية على 2³²⁻ᵖ عنوانًا، لكن الأول (عنوان الشبكة) والأخير (عنوان البث) لا يُعطيان للمضيفين، فيتسع 2³²⁻ᵖ − 2 مضيفًا. الاستثناءات: الشبكة /31 (وصلة من نقطة إلى نقطة، RFC 3021) تستخدم كلا عنوانَيها الـ 2 للمضيفين، والشبكة /32 عنوان واحد فقط (مضيف واحد أو عنوان loopback).
ExamProblems · examproblems.com/courses/computer-science-fundamentals