أنظمة العد
- القيم الموضعية
- الثنائي 2k، الثماني 8k، الست عشري 16k
- إلى العشري
- Σ dk·bk
- من العشري
- اقسم على الأساس، واقرأ البواقي من الأسفل إلى الأعلى
- الست عشري ↔ الثنائي
- رقم ست عشري واحد = 4 بتات
- المتمم الثنائي
- اعكس البتات وأضف 1
أوراق القوانين، وأهم خطوات الحل لكل موضوع، و20 مسألة تدريبية، مع الحلول الكاملة في الخلف.
اكتب −115 كنمط متمم ثنائي ذي 8 بتات. اقرأ النمط كعدد ثنائي بلا إشارة: ما قيمته U في النظام العشري؟
يجب أن يعطي نظام كل واحد من 2599 عنصرًا رمزًا ثنائيًا خاصًا به بالطول نفسه. ما أقل عدد من البتات b يلزم؟
في كم صفًا من الصفوف الثمانية لجدول صدق (r ∨ q) → ((¬r ∨ p) ∨ q) تكون صائبة؟ سمِّ هذا العدد N.
المقدمات a ∨ c; ¬a معطاة. أي استنتاج يلزم عنها؟ انقر عليه.
استخدم خريطة كارنو لإيجاد الصيغة الدنيا لمجموع الجداءات (SOP) للدالة F(A, B, C, D) = Σm(1, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14). كم حد جداء N فيها؟
جد الصيغة الدنيا SOP للدالة F(A, B, C, D) = Σm(0, 1, 8, 9, 10, 11, 12, 15) + d(5, 7, 13)، حيث تشير d إلى حالات عدم الاكتراث. كم حد جداء N فيها؟
حلّ 7x ≡ 1 (mod 17). أعطِ الحل x مع 0 < x < 17.
حلّ 20x ≡ 6 (mod 22). أعطِ أصغر حل موجب x.
ما التعقيد الزمني لخوارزمية البرمجة الديناميكية القياسية لأطول تتابع جزئي مشترك لسلسلتين طولهما m وn؟
أي من مسائل الإرضاء هذه معروف أنه قابل للحل في زمن كثير حدود؟
لديك مرجع إلى عقدة في منتصف قائمة. في أي قائمة يمكنك إزالتها في O(1)؟
إدراج مفتاح في شجرة AVL جعل الشجرة الفرعية اليسرى لعقدة أطول من اللازم، وذهب المفتاح الجديد إلى الشجرة الفرعية اليسرى لابنها الأيسر (حالة يسار-يسار). أي إصلاح يُطبَّق؟
كم دارة هاملتون مختلفة H للبيان التام K4؟ الدارات التي تختلف فقط في رأس البداية أو الاتجاه تُعدّ واحدة.
استخدم خوارزمية ديكسترا لإيجاد طول d(F) أقصر مسار من A إلى F في البيان الموزون.
ماذا يُرجع SELECT COALESCE(phone, 'unknown') FROM customers لعميل قيمة phone لديه NULL؟
للجدول employee(emp_id, dept_id, dept_name) المفتاح emp_id، وdept_id → dept_name. أي عبارة صحيحة؟
لماذا يُفضَّل UDP غالبًا في مكالمات الفيديو المباشرة؟
يحجب جدار حماية كل رسائل ICMP. تعمل طلبات الويب الصغيرة، لكن التنزيلات الكبيرة عبر بعض المسارات تتوقف. ما السبب المرجح؟
يجب تقسيم الشبكة 192.168.10.0/24 إلى 10 شبكات فرعية متساوية على الأقل. إذا استعرت أقل عدد ممكن من البتات، فكم مضيفًا قابلًا للاستخدام H في كل شبكة فرعية؟
تُقسَّم الشبكة 192.168.30.0/24 بتقنية VLSM لهذه الشبكات المحلية: A: 11 مضيفون, B: 31 مضيفون, C: 53 مضيفون, D: 21 مضيفون. تُخصَّص الشبكات الفرعية من .0 صعودًا، بدءًا بالشبكة المحلية ذات أكبر عدد من المضيفين، لكلٍّ منها أصغر شبكة فرعية تكفيها. ما الثُمانية الرابعة x من عنوان شبكة LAN D؟
الإجابة: U = 141
أنظمة العد الموضعية: قيمة كل رقم هي قيمته مضروبة في قوة من قوى الأساس. في النظام الثنائي تساوي المواضع 1، 2، 4، 8، 16، …؛ وفي السداسي عشري 1، 16، 256، …، حيث تمثل A–F القيم 10–15. في المتمم الثنائي ذي 8 بتات تساوي البتة اليسرى −128 بدلًا من +128، وهكذا تُخزَّن الأعداد السالبة.
الإجابة: b = 12 bit
أنظمة العد الموضعية: قيمة كل رقم هي قيمته مضروبة في قوة من قوى الأساس. في النظام الثنائي تساوي المواضع 1، 2، 4، 8، 16، …؛ وفي السداسي عشري 1، 16، 256، …، حيث تمثل A–F القيم 10–15. في المتمم الثنائي ذي 8 بتات تساوي البتة اليسرى −128 بدلًا من +128، وهكذا تُخزَّن الأعداد السالبة.
الإجابة: N = 7
جداول الصدق: للصيغة ذات n متغيرًا مختلفًا 2ⁿ صفًا، صف لكل تركيبة من قيم الصدق (1 = صواب، 0 = خطأ). اعمل من الداخل إلى الخارج وأعطِ كل صيغة جزئية عمودها الخاص. ¬a تقلب القيمة؛ و a ∧ b تساوي 1 فقط عندما تكون القيمتان 1؛ و a ∨ b تساوي 0 فقط عندما تكون القيمتان 0؛ و a → b تساوي 0 فقط عندما a = 1 و b = 0؛ و a ↔ b تساوي 1 عندما يتساوى الطرفان.
الإجابة: c
الكمّمات والحجج: ¬∀x P(x) ≡ ∃x ¬P(x) و ¬∃x P(x) ≡ ∀x ¬P(x). انقل النفي إلى الداخل، وبدّل كل كمّم يمرّ به، وانفِ الصيغة الداخلية بقوانين المنطق القضوي، مثل ¬(a → b) ≡ a ∧ ¬b. تكون الحجة صحيحة عندما يكون الاستنتاج 1 في كل صف تكون فيه كل المقدمات 1. صف واحد بمقدمات صائبة واستنتاج خاطئ هو مثال مضاد ويبيّن أن الحجة غير صحيحة.
الإجابة: N = 5
خرائط كارنو: ترتَّب الخلايا بشيفرة غراي (00, 01, 11, 10)، فتختلف الخلايا المتجاورة، بما فيها تلك التي عبر الحواف، في متغير واحد بالضبط. جمّع الآحاد في مستطيلات من 1 أو 2 أو 4 أو 8 أو 16 خلية، بأكبر حجم وأقل عدد ممكنين، حتى يُغطى كل 1. كل مجموعة حد جداء واحد: المتغيرات التي تبقى ثابتة داخلها. المجموعة من 2ᵏ خلية تفقد k متغيرًا. يجوز استخدام حالات عدم الاكتراث (X) لتكبير المجموعات لكن لا يجب تغطيتها أبدًا. أما تجميع الأصفار فيعطي الصيغة الدنيا POS.
كل مجموعة مستطيل من 2ᵏ خلية؛ وخلايا الحافة جارة للخلايا على الحافة المقابلة.
يوجد تجميع آخر بالحجم نفسه؛ وله عدد الحدود والحروف نفسه.
الإجابة: N = 4
خرائط كارنو: ترتَّب الخلايا بشيفرة غراي (00, 01, 11, 10)، فتختلف الخلايا المتجاورة، بما فيها تلك التي عبر الحواف، في متغير واحد بالضبط. جمّع الآحاد في مستطيلات من 1 أو 2 أو 4 أو 8 أو 16 خلية، بأكبر حجم وأقل عدد ممكنين، حتى يُغطى كل 1. كل مجموعة حد جداء واحد: المتغيرات التي تبقى ثابتة داخلها. المجموعة من 2ᵏ خلية تفقد k متغيرًا. يجوز استخدام حالات عدم الاكتراث (X) لتكبير المجموعات لكن لا يجب تغطيتها أبدًا. أما تجميع الأصفار فيعطي الصيغة الدنيا POS.
أكبر المجموعات التي يمكن تكوينها من الآحاد و X.
يوجد تجميع آخر بالحجم نفسه؛ وله عدد الحدود والحروف نفسه.
الإجابة: x = 5
المعكوسات والتطابقات: للعدد 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).
الإجابة: x = 8
المعكوسات والتطابقات: للعدد 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 · O(mn)
للجدول (m + 1)(n + 1) خلية، وتُحسب كل منها في O(1) من جاراتها.
الإجابة: B · 2-SAT، حيث يحتوي كل بند على حرفيّين (literals) على الأكثر
2-SAT تنتمي إلى P (زمن خطي عبر المكونات قوية الاتصال)، بينما 3-SAT هي NP-تامة.
الإجابة: C · القائمة المترابطة الثنائية
تعرف العقدة في القائمة الثنائية سابقتها، فيمكنك إعادة ربط prev وnext مباشرة، أما القائمة الأحادية فيجب البحث فيها عن السابقة.
الإجابة: C · دوران واحد إلى اليمين عند العقدة غير المتوازنة
في حالة يسار-يسار يرفع دوران واحد إلى اليمين الابن الأيسر ويعيد التوازن، أما الحالات المتعرجة فتحتاج إلى دوران مزدوج.
الإجابة: H = 3
أويلر وهاملتون والأشجار: لبيان متصل دارة أويلر (كل حافة مرة واحدة، والعودة إلى البداية) عندما تكون لكل رأس درجة زوجية، ومسار أويلر ليس دارة عندما تكون لرأسين بالضبط درجة فردية؛ ويسير المسار عندئذ من أحد الرأسين الفرديين إلى الآخر. تزور دارة هاملتون كل رأس مرة واحدة؛ وفي Kn منها (n − 1)!/2. للشجرة على n رأسًا n − 1 حافة، ويحتفظ بيان متصل ذو m حافة بشجرة ممتدة بعد حذف m − n + 1 حافة.
الإجابة: d(F) = 30
أقصر المسارات والأشجار الممتدة: تثبّت خوارزمية ديكسترا رأسًا واحدًا في كل جولة: الرأس غير المثبّت ذا أصغر مسافة مؤقتة. تصبح مسافته نهائية، ويأخذ كل جار v القيمة d(v) = min(d(v), d(u) + w(u, v)). تبني خوارزمية كروسكال شجرة ممتدة دنيا بأخذ الحواف من الأخف إلى الأثقل وتخطّي كل حافة تُغلق دورة؛ وتنمّي خوارزمية برايم شجرة واحدة من رأس البداية بإضافة أخف حافة تغادرها دائمًا. وللشجرة الممتدة على n رأسًا n − 1 حافة.
كل سطر: الرأس المثبَّت، ومسافته النهائية، والجيران الذين تتحسن مسافتهم.
الإجابة: D · 'unknown'
تفحص COALESCE وسائطها من اليسار إلى اليمين وتُرجع أول وسيط ليس NULL، وهو هنا 'unknown'.
الإجابة: B · إنه في 2NF لكنه ليس في 3NF
للمفتاح عمود واحد، فتتحقق 2NF، لكن emp_id → dept_id → dept_name اعتمادية متعدية تخالف 3NF.
الإجابة: C · لأن انخفاض التأخير أهم من إعادة إرسال كل حزمة مفقودة
إعادة إرسال الحزم المفقودة ستزيد التأخير؛ والوسائط في الوقت الحقيقي تتحمل بعض الفقد، لذا تُستخدم بروتوكولات مبنية على UDP مثل RTP.
الإجابة: C · يفشل اكتشاف MTU للمسار لأن رسائل "fragmentation needed" محجوبة
يعتمد PMTUD على رسائل ICMP لمعرفة قيمة MTU الأصغر. فإذا أُسقطت تختفي الحزم الكبيرة بصمت، فينشأ اتصال "ثقب أسود".
الإجابة: H = 14
تقسيم شبكات IPv4: يتكون العنوان من 32 بتة. تحدد البادئة /p عدد البتات الأولى التي تعرّف الشبكة؛ وتُرقّم البتات المتبقية 32 − p المضيفين. تحتوي الشبكة الفرعية على 2³²⁻ᵖ عنوانًا، لكن الأول (عنوان الشبكة) والأخير (عنوان البث) لا يُعطيان للمضيفين، فيتسع 2³²⁻ᵖ − 2 مضيفًا. الاستثناءات: الشبكة /31 (وصلة من نقطة إلى نقطة، RFC 3021) تستخدم كلا عنوانَيها الـ 2 للمضيفين، والشبكة /32 عنوان واحد فقط (مضيف واحد أو عنوان loopback).
الإجابة: x = 128
VLSM: تحصل كل شبكة محلية على أصغر شبكة فرعية تحقّق 2ʰ − 2 ≥ عدد مضيفيها، أي البادئة 32 − h. تخصيص الشبكات الفرعية الأكبر أولًا يُبقي كل كتلة محاذية لمضاعف حجمها، لذا تُستنتج عناوين الشبكات بجمع أحجام الكتل.
LAN D: 192.168.30.128/27.
ExamProblems · examproblems.com/courses/computer-science-fundamentals