أنظمة العد
- القيم الموضعية
- الثنائي 2k، الثماني 8k، الست عشري 16k
- إلى العشري
- Σ dk·bk
- من العشري
- اقسم على الأساس، واقرأ البواقي من الأسفل إلى الأعلى
- الست عشري ↔ الثنائي
- رقم ست عشري واحد = 4 بتات
- المتمم الثنائي
- اعكس البتات وأضف 1
أوراق القوانين، وأهم خطوات الحل لكل موضوع، و20 مسألة تدريبية، مع الحلول الكاملة في الخلف.
النمط ذو 8 بتات 1010 0100 يخزّن عددًا صحيحًا بإشارة بصيغة المتمم الثنائي. ما قيمته N في النظام العشري؟
اضبط البتات على الناتج بـ 8 بتات لـ 0100 1100 OR 1000 1100. ما قيمة الناتج R بالعشري؟
أي صيغة تكافئ r ∧ (p ∨ q) منطقيًا؟ انقر عليها.
الحجة ذات المقدمات q → r; ¬q والاستنتاج ¬r غير صحيحة. انقر على صف جدول الصدق الذي يمثل مثالًا مضادًا.
لمضاعِف 4-إلى-1 مدخلا الاختيار S₁ = A و S₀ = B، ومداخل بياناته موصولة بـ I₀ = 1, I₁ = C, I₂ = 0, I₃ = 1. في كم من تركيبات A و B و C الثماني يكون المخرج F = 1؟ جد N.
للدالة F(A, B, C, D) = Σm(1, 6, 8, 9) + d(4, 5, 7, 15)، حيث تشير d إلى حالات عدم الاكتراث، جد عدد N المضمّنات الأولية الجوهرية (essential prime implicants).
جد أصغر عدد صحيح موجب x مع x ≡ 2 (mod 8) و x ≡ 6 (mod 9).
يستخدم مفتاح RSA العددين الأوليين p = 29 و q = 43 والأس العام e = 17. جد الأس الخاص d (0 < d < φ(n)).
أي خوارزمية تجد أقصر المسارات من مصدر واحد في رسم بياني أوزان أضلاعه غير سالبة؟
ما الكلفة الزمنية والمكانية لحساب عدد فيبوناتشي رقم n بحلقة لا تحتفظ إلا بآخر قيمتين؟
يُستخدم المخزن المؤقت الدائري (ring buffer) عادةً لتنفيذ:
أي خاصية تُبقي كل شجرة B متوازنة تمامًا؟
بيان متصل له 16 رؤوس و26 حافة. كم حافة k يجب حذفها لتبقى شجرة ممتدة؟
استخدم خوارزمية ديكسترا لإيجاد طول d(C) أقصر مسار من A إلى C في البيان الموزون.
لماذا تُنشأ الفهارس على الأعمدة؟
ماذا يُرجع الاستعلام التالي: SELECT name FROM students WHERE grade > (SELECT AVG(grade) FROM students)؟
لماذا يُفضَّل UDP غالبًا في مكالمات الفيديو المباشرة؟
تصل المحطتان A وC كلتاهما إلى نقطة الوصول B لكنهما لا تسمعان بعضهما، فتتصادم إطاراتهما عند B. كيف يساعد 802,11؟
يحتاج قسم إلى 1661 عنوان مضيف في شبكة فرعية واحدة. ما أطول بادئة p (أصغر شبكة فرعية) تكفي؟
عنوان مضيف هو 10.20.4.47/30. ما الثُمانية الرابعة x من عنوان شبكته؟
الإجابة: N = −92
أنظمة العد الموضعية: قيمة كل رقم هي قيمته مضروبة في قوة من قوى الأساس. في النظام الثنائي تساوي المواضع 1، 2، 4، 8، 16، …؛ وفي السداسي عشري 1، 16، 256، …، حيث تمثل A–F القيم 10–15. في المتمم الثنائي ذي 8 بتات تساوي البتة اليسرى −128 بدلًا من +128، وهكذا تُخزَّن الأعداد السالبة.
تحتفظ البتات الأخرى بقيمها الموجبة المعتادة.
الإجابة: R = 204
ضبط البتات: قيمة كل بت قوة للعدد اثنين (128 و64 … و1). الرقم السداسي عشري الواحد يساوي أربع بتات تمامًا، وفي المتمم الثنائي بـ 8 بتات تساوي قيمة البت الأيسر −128. وتعمل العمليات على مستوى البت على كل موضع بت على حدة.
تعطي OR القيمة 1 حيث يكون أحد البتين على الأقل 1.
الإجابة: (r ∧ p) ∨ (r ∧ q)
التكافؤ المنطقي: تتكافأ صيغتان (≡) عندما يكون لهما القيمة نفسها في كل صف من جدول الصدق. الحشو يساوي 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 = 0, r = 1
الكمّمات والحجج: ¬∀x P(x) ≡ ∃x ¬P(x) و ¬∃x P(x) ≡ ∀x ¬P(x). انقل النفي إلى الداخل، وبدّل كل كمّم يمرّ به، وانفِ الصيغة الداخلية بقوانين المنطق القضوي، مثل ¬(a → b) ≡ a ∧ ¬b. تكون الحجة صحيحة عندما يكون الاستنتاج 1 في كل صف تكون فيه كل المقدمات 1. صف واحد بمقدمات صائبة واستنتاج خاطئ هو مثال مضاد ويبيّن أن الحجة غير صحيحة.
حجة بهذه الصيغة تبدو قاعدة صحيحة، لكن صفًا واحدًا يكفي لإثبات أنها ليست كذلك.
الإجابة: N = 5
المضاعِف (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 = 2
خرائط كارنو: ترتَّب الخلايا بشيفرة غراي (00, 01, 11, 10)، فتختلف الخلايا المتجاورة، بما فيها تلك التي عبر الحواف، في متغير واحد بالضبط. جمّع الآحاد في مستطيلات من 1 أو 2 أو 4 أو 8 أو 16 خلية، بأكبر حجم وأقل عدد ممكنين، حتى يُغطى كل 1. كل مجموعة حد جداء واحد: المتغيرات التي تبقى ثابتة داخلها. المجموعة من 2ᵏ خلية تفقد k متغيرًا. يجوز استخدام حالات عدم الاكتراث (X) لتكبير المجموعات لكن لا يجب تغطيتها أبدًا. أما تجميع الأصفار فيعطي الصيغة الدنيا POS.
أكبر المجموعات التي يمكن تكوينها من الآحاد و X.
الإجابة: x = 42
المعكوسات والتطابقات: للعدد 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).
الإجابة: d = 761
القوى المودولية و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 · خوارزمية ديكسترا (Dijkstra)
تعمل خوارزمية ديكسترا مع الأوزان غير السالبة؛ وتتعامل خوارزمية بيلمان–فورد مع الأوزان السالبة؛ وتبني خوارزمية كروسكال أشجارًا ممتدة صغرى.
الإجابة: C · زمن O(n) ومساحة O(1)
لا تحتاج كل خطوة إلا إلى القيمتين السابقتين، فيمكن استبدال جدول الطريقة التصاعدية بمتغيرين.
الإجابة: D · طابور ثابت الحجم
يستخدم المخزن الدائري فهرسَي head وtail يلتفّان إلى البداية، مما يوفّر enqueue وdequeue في O(1) ضمن ذاكرة ثابتة.
الإجابة: D · كل الأوراق على العمق نفسه
تنقسم العقد إلى الأعلى حين تمتلئ، ولا يزداد ارتفاع الشجرة إلا حين ينقسم الجذر، فتبقى الأوراق كلها دائمًا على المستوى نفسه.
الإجابة: k = 11
أويلر وهاملتون والأشجار: لبيان متصل دارة أويلر (كل حافة مرة واحدة، والعودة إلى البداية) عندما تكون لكل رأس درجة زوجية، ومسار أويلر ليس دارة عندما تكون لرأسين بالضبط درجة فردية؛ ويسير المسار عندئذ من أحد الرأسين الفرديين إلى الآخر. تزور دارة هاملتون كل رأس مرة واحدة؛ وفي Kn منها (n − 1)!/2. للشجرة على n رأسًا n − 1 حافة، ويحتفظ بيان متصل ذو m حافة بشجرة ممتدة بعد حذف m − n + 1 حافة.
الإجابة: d(C) = 9
أقصر المسارات والأشجار الممتدة: تثبّت خوارزمية ديكسترا رأسًا واحدًا في كل جولة: الرأس غير المثبّت ذا أصغر مسافة مؤقتة. تصبح مسافته نهائية، ويأخذ كل جار v القيمة d(v) = min(d(v), d(u) + w(u, v)). تبني خوارزمية كروسكال شجرة ممتدة دنيا بأخذ الحواف من الأخف إلى الأثقل وتخطّي كل حافة تُغلق دورة؛ وتنمّي خوارزمية برايم شجرة واحدة من رأس البداية بإضافة أخف حافة تغادرها دائمًا. وللشجرة الممتدة على n رأسًا n − 1 حافة.
كل سطر: الرأس المثبَّت، ومسافته النهائية، والجيران الذين تتحسن مسافتهم.
الإجابة: D · لتسريع عمليات البحث والربط على تلك الأعمدة
تُسرّع الفهارس (غالبًا أشجار B-tree) عمليات البحث، لكنها تشغل مساحة وتُبطئ عمليات INSERT و UPDATE التي يجب أن تحدّثها.
الإجابة: A · الطلاب الذين تزيد درجاتهم عن متوسط الدرجات
يحسب الاستعلام الفرعي القياسي (scalar subquery) المتوسط، ويحتفظ الاستعلام الخارجي بالطلاب الذين تزيد درجاتهم عنه.
الإجابة: A · لأن انخفاض التأخير أهم من إعادة إرسال كل حزمة مفقودة
إعادة إرسال الحزم المفقودة ستزيد التأخير؛ والوسائط في الوقت الحقيقي تتحمل بعض الفقد، لذا تُستخدم بروتوكولات مبنية على UDP مثل RTP.
الإجابة: D · بتبادلات RTS/CTS الاختيارية: تخبر رسالة CTS من نقطة الوصول جميع المحطات القريبة بالانتظار
ترسل المحطة طلب الإرسال (Request to Send)، فترد نقطة الوصول بإذن الإرسال (Clear to Send) الذي تسمعه كل محطة في نطاقها، فتؤجل المحطات المخفية الإرسال طوال المدة المحجوزة.
الإجابة: p = 21
تقسيم شبكات IPv4: يتكون العنوان من 32 بتة. تحدد البادئة /p عدد البتات الأولى التي تعرّف الشبكة؛ وتُرقّم البتات المتبقية 32 − p المضيفين. تحتوي الشبكة الفرعية على 2³²⁻ᵖ عنوانًا، لكن الأول (عنوان الشبكة) والأخير (عنوان البث) لا يُعطيان للمضيفين، فيتسع 2³²⁻ᵖ − 2 مضيفًا. الاستثناءات: الشبكة /31 (وصلة من نقطة إلى نقطة، RFC 3021) تستخدم كلا عنوانَيها الـ 2 للمضيفين، والشبكة /32 عنوان واحد فقط (مضيف واحد أو عنوان loopback).
الإجابة: x = 44
تقسيم شبكات IPv4: يتكون العنوان من 32 بتة. تحدد البادئة /p عدد البتات الأولى التي تعرّف الشبكة؛ وتُرقّم البتات المتبقية 32 − p المضيفين. تحتوي الشبكة الفرعية على 2³²⁻ᵖ عنوانًا، لكن الأول (عنوان الشبكة) والأخير (عنوان البث) لا يُعطيان للمضيفين، فيتسع 2³²⁻ᵖ − 2 مضيفًا. الاستثناءات: الشبكة /31 (وصلة من نقطة إلى نقطة، RFC 3021) تستخدم كلا عنوانَيها الـ 2 للمضيفين، والشبكة /32 عنوان واحد فقط (مضيف واحد أو عنوان loopback).
ExamProblems · examproblems.com/courses/computer-science-fundamentals