الخوارزميات والرسوم البيانية والبرمجة الديناميكية وقواعد البيانات العلائقية

32 بطاقة مراجعة بمستوى جامعي عن الترتيب وخوارزميات الرسوم البيانية والبرمجة الديناميكية وSQL والفهارس والمعاملات. تفترض معرفة بأساسيات البرمجة وهياكل البيانات وSQL.

Category
Computer Science
Level
basic
Languages
ar → ar
Cards
32
Markdown
الخوارزميات والرسوم البيانية والبرمجة الديناميكية وقواعد البيانات العلائقية (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1ما القراءة القذرة، وما أول مستوى عزل معياري يمنعها؟قراءة بيانات غير مثبتة من معاملة أخرى، سواء أُلغيت تلك المعاملة لاحقًا أم لا. يمنع READ COMMITTED ومستويات العزل المعيارية الأقوى القراءات القذرة.
2لماذا قد يستغرق الترتيب السريع Θ(n²)، وكيف تساعد العشوائية؟التقسيمات المتكررة شديدة الاختلال، كاختيار أصغر مفتاح من مفاتيح مختلفة كل مرة، تسبب عملًا تربيعيًا. عند اختلاف المفاتيح أو معالجة التكرارات معالجة مناسبة، تعطي المحاور العشوائية زمنًا متوقعًا O(n log n). اختيار وسيط ثلاثة عناصر أسلوب إرشادي مفيد وليس ضمانًا للحالة الأسوأ.
3كيف تتعامل خوارزمية بيلمان–فورد مع الحواف السالبة وتكشف دورة سالبة يمكن بلوغها؟تُرخى جميع الحواف حتى V−1 مرة. يدل تحسّن إضافي من رأس يمكن بلوغه على دورة سالبة يمكن الوصول إليها من المصدر. الزمن الأسوأ O(VE)؛ ولا توجد كلفة منتهية لأقصر مسار إلى الرؤوس التي يمكن بلوغها من هذه الدورة.
4ما معنى خصائص المعاملات ACID؟الذرية: جميع الآثار أو لا شيء. الاتساق: تحافظ المعاملات الصحيحة على القيود وثوابت التطبيق. العزل: يلتزم السلوك المتزامن بمستوى العزل المختار. الديمومة: تنجو الآثار المثبتة من الأعطال التي تشملها ضمانات قاعدة البيانات المضبوطة.
5كيف يختلف WHERE عن HAVING في استعلام مجمّع؟يرشّح WHERE صفوف المدخل قبل التجميع. ويرشّح HAVING المجموعات الناتجة ويمكنه استخدام شروط تجميعية مثل COUNT(*)>1.
6ما علاقة البرمجة الديناميكية لطول أطول تتابع جزئي مشترك (LCS)؟لتكن L[i,j] طول LCS لبادئتين طولاهما i,j. ضع L[0,j]=L[i,0]=0. إذا تطابق الحرفان الأخيران، فإن L[i,j]=1+L[i−1,j−1]؛ وإلا L[i,j]=max(L[i−1,j],L[i,j−1]). يستخدم الجدول الكامل O(mn) زمنًا ومساحة.
7ما الفرق بين الفهرس العنقودي وغير العنقودي لمخزن الصفوف في SQL Server؟يخزن الفهرس العنقودي صفوف الجدول بترتيب المفتاح، لذا لا يملك الجدول أكثر من واحد. للفهرس غير العنقودي مفاتيحه ومحددات مواقع الصفوف، وقد يضم أعمدة أخرى. تختلف المصطلحات وتفاصيل التخزين بين أنظمة قواعد البيانات.
8متى تصح خوارزمية ديكسترا، وما حدّ تنفيذها المعتاد بالكومة؟مع أوزان حواف غير سالبة، تثبّت مرارًا الرأس ذا أقل مسافة مؤقتة. يستغرق التنفيذ بقوائم تجاور وكومة دنيا ثنائية O((V+E) log V). قد تُبطل الحواف السالبة حجة أن المسافة المثبتة نهائية.
9ما الفرق بين الحفظ التذكري والبرمجة الديناميكية من أسفل إلى أعلى؟يحسب الحفظ التذكري المسائل الفرعية عند الحاجة، عادة بالاستدعاء الذاتي، ويخزن النتائج. أما النهج من أسفل إلى أعلى فيحسب الحالات بترتيب تكون فيه اعتمادياتها متاحة مسبقًا، عادة بملء جدول.
10كيف يعمل الترتيب بالإدراج، وما الذي يحدد زمنه عندما تكون البيانات شبه مرتبة؟يُدرج كل عنصر في بادئة مرتبة. النسخة المعتادة التي تُزيح العناصر المتجاورة أو تتبادلها تستغرق Θ(n+I)، حيث I عدد أزواج الانقلاب. تكون خطية عندما I=O(n)؛ وصغر المدخل وحده لا يغيّر حد الحالة الأسوأ Θ(n²).
11كيف تختلف الخوارزمية الجشعة عن البرمجة الديناميكية؟تلتزم الجشعة باختيار محلي وتحتاج برهانًا على أن هذه الاختيارات تحافظ على الحل الأمثل. تقارن البرمجة الديناميكية البدائل بعلاقة عودية وتعيد استخدام نتائج المسائل الفرعية. يتطلب الحل الأمثل العام نموذجًا وعلاقة صحيحين، لا مجرد اسم «برمجة ديناميكية».
12ما القراءة غير القابلة للتكرار، وأي مستوى عزل معياري يمنعها؟تعطي إعادة قراءة صف بيانات متغيرة، أو يختفي الصف، بعد أن تثبّت معاملة أخرى تحديثًا أو حذفًا. يمنع REPEATABLE READ وSERIALIZABLE هذه الظاهرة.
13كيف يجد البحث بالعرض أقصر المسارات في رسم بياني غير موزون؟يستخدم BFS طابور FIFO ويستكشف الرؤوس بحسب المسافة بعدد الحواف. تعليم الرأس عند إدخاله الطابور يمنع تكرار زيارته. أول مسار مكتشف إلى رأس يمكن بلوغه يحوي أقل عدد من الحواف.
14ماذا تتطلب الأشكال الطبيعية الأول والثاني والثالث؟1NF: قيم سمات ذرية. 2NF: تحقق 1NF وألا تعتمد سمة غير مفتاحية على مجموعة جزئية حقيقية من سمات أي مفتاح مرشح. 3NF: تحقق 1NF، ولكل اعتماد غير تافه X→A يكون X مفتاحًا فائقًا أو تكون A ضمن مفتاح مرشح ما. السمة غير المفتاحية لا تنتمي إلى أي مفتاح مرشح.
15ما الترتيب الطوبولوجي، وكيف تجده خوارزمية كان؟في رسم موجه لا دوري، تقتضي كل حافة u→v أن يسبق u الرأس v. أخرج مرارًا رأسًا درجة دخوله صفر، واحذف حوافه الخارجة، وأضف إلى الطابور الرؤوس التي أصبحت درجة دخولها صفرًا. إذا خرج أقل من V رأسًا، فالرسم الموجه يحوي دورة.
16ما حدّا الزمن والمساحة الإضافية في أسوأ حالة لترتيب الكومة في موضعه؟يستغرق بناء الكومة O(n)، ثم تستغرق عمليات الاستخراج مجتمعة O(n log n). باستخدام الغربلة التكرارية إلى أسفل داخل مصفوفة المدخل، يكون الزمن الأسوأ O(n log n) والمساحة الإضافية O(1).
17ما الذي يجعل خوارزمية ترتيب مستقرة؟تحافظ العناصر ذات المفاتيح المتساوية على ترتيبها النسبي الأصلي. يمكن أن يكون ترتيب الدمج مستقرًا بأخذ العنصر الأيسر أولًا عند التعادل؛ أما الترتيب السريع المعتاد داخل المصفوفة فعادة غير مستقر. يعتمد الاستقرار على التنفيذ.
18ما الفرق بين INNER JOIN وLEFT JOIN؟يعيد INNER JOIN تركيبات الصفوف التي تحقق شرط الربط. يحتفظ LEFT JOIN أيضًا بكل صف أيسر بلا تطابق، ويضع NULL في أعمدة الجانب الأيمن. قد تنتج عدة صفوف يمنى مطابقة عدة صفوف ناتجة لصف أيسر واحد.
19كيف تبني خوارزميتا كروسكال وبريم شجرة امتداد صغرى؟في رسم موزون متصل وغير موجه، يفحص كروسكال الحواف بترتيب وزن تصاعدي ويستخدم Union–Find لرفض الدورات. ينمّي بريم شجرة واحدة باختيار أقل حافة وزنًا تعبر من الشجرة إلى رأس خارجها كل مرة.
20كيف يدعم WAL في PostgreSQL الديمومة عند التثبيت المتزامن المعتاد؟تصل سجلات اليومية ذات الصلة إلى تخزين دائم قبل تأكيد التثبيت وقبل كتابة صفحات البيانات المعدلة. بعد التعطل، يمكن لـWAL إعادة تطبيق تغييرات لم تصل إلى صفحات البيانات. قد يفقد التثبيت غير المتزامن معاملات حديثة سبق تأكيدها.
21كيف يكتشف البحث بالعمق دورة في رسم بياني موجه؟يتعمق DFS باستخدام الاستدعاء الذاتي أو مكدس صريح. الحافة إلى رأس ما يزال نشطًا على مسار DFS الحالي هي حافة خلفية تثبت دورة موجهة؛ ولا تكفي حافة إلى أي رأس سبق زيارته.
22ما علاقة العودية القياسية لحقيبة الظهر 0/1 ذات السعة الصحيحة W؟لتكن D[i,w] أفضل قيمة باستخدام أول i عنصرًا بسعة w، مع أوزان صحيحة موجبة wᵢ. ضع D[0,w]=0. إذا كان wᵢ>w، انسخ D[i−1,w]؛ وإلا خذ max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). الزمن O(NW) شبه متعدد الحدود.
23كيف يعمل ترتيب المصفوفة بالدمج بصورته المعتادة، وما حدّا الزمن والمساحة؟يرتب نصفين استدعائيًا ثم يدمجهما في زمن خطي. تستغرق النسخة المعتادة Θ(n log n) زمنًا وO(n) مساحة إضافية، بافتراض مقارنات ثابتة الزمن.
24لماذا تفيد أشجار B+ في فهارس قواعد البيانات واستعلامات النطاق؟يحافظ عدد التفرعات الكبير على قلة ارتفاع الشجرة، فيقل الوصول إلى الصفحات. تدعم المفاتيح المرتبة والأوراق المترابطة مسح النطاقات. تستهدف فهارس التجزئة البحث بالمساواة ولا توفر بطبيعتها الوصول المرتب نفسه إلى النطاقات.
25ما مرحلتا القفل ثنائي الطور (2PL)؟النمو: اكتساب أقفال دون تحريرها. الانكماش: تحرير الأقفال دون اكتساب جديدة. مع أقفال قراءة وكتابة متعارضة مناسبة، يضمن 2PL جداول تنفيذ قابلة للتسلسل بحسب التعارض، لكن يظل الجمود المتبادل ممكنًا.
26ماذا يتطلب البحث الثنائي، ومتى يعمل في زمن O(log n)؟يقسم مجال البحث إلى نصفين مرارًا في بيانات مرتبة وفق علاقة المقارنة. في مصفوفة تتيح الوصول بالفهرس في O(1) ومقارنات ثابتة الزمن، يستغرق البحث بين n عنصرًا زمن O(log n).
27لماذا تفيد البرمجة الديناميكية في مسائل تحسين كثيرة؟تتيح البنية الجزئية المثلى التعبير عن الحل الأمثل عبر حلول مثلى لمسائل فرعية. عندما تتداخل المسائل الفرعية، يمنع تخزين إجاباتها تكرار العمل. يجب أن تمثل تعريفات الحالات وعلاقة العودية المسألة الأصلية تمثيلًا صحيحًا.
28متى يمكن للترتيب بالعد أو بالمراتب أن يعمل في زمن خطي؟يكلف الترتيب بالعد O(n+k) لعدد n من المفاتيح ضمن مجال من k قيمة. ويكلف ترتيب المراتب ذو d تمريرات مستقرة على الخانات وأساس b مقدار O(d(n+b)). لا يكونان خطيين إلا إذا سمحت المعلمات بذلك؛ فهما يستفيدان من بنية المفاتيح، لا من المقارنات وحدها.
29كيف تُقارن مصفوفة التجاور بقوائم التجاور العادية؟لعدد V من الرؤوس وE من الحواف، تستخدم المصفوفة O(V²) مساحة وتختبر وجود حافة في O(1). تستخدم القوائم O(V+E)؛ والبحث عن الحافة (u,v) في قائمة غير مرتبة يستغرق O(deg(u))، حيث deg(u) طول تلك القائمة.
30ما القراءة الوهمية، وكيف تُمنع؟يجد تكرار استعلام بشرط مجموعة مختلفة من الصفوف المطابقة بعد تثبيت تغييرات معاملة أخرى. يمنع SERIALIZABLE الصفوف الوهمية في النموذج المعياري؛ وبعض التطبيقات، ومنها PostgreSQL REPEATABLE READ، تمنعها أيضًا في مستوى أدنى.
31ما الترتيب المنطقي المبسط لمعالجة استعلام SQL SELECT؟لاستعلام بلا CTE أو دوال نافذة أو عمليات مجموعات: FROM/JOIN → WHERE → GROUP BY والتجميعات → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. هذا نموذج منطقي، وليس بالضرورة ترتيب التنفيذ الفعلي الذي يختاره المُحسِّن.
32ما الفرق بين المفتاح الأساسي والخارجي في PostgreSQL؟يُعرّف المفتاح الأساسي الصفوف بقيم فريدة وغير NULL. يتطلب المفتاح الخارجي تطابقًا مع قيم المفتاح المشار إليه، مع مراعاة قواعد NULL الخاصة به. ويمكن أن يشير إلى مفتاح UNIQUE مؤهل أو مفتاح أساسي في الجدول نفسه أو غيره.