CCS3403 Computing Algorithms - Lecture 1

مجموعة فلاش كاردز شاملة للمحاضرة الأولى في مادة خوارزميات الحوسبة، تغطي التعريفات، الخصائص، أنواع التحليل، والتعقيد الزمني والمكاني.

ما هو رمز المادة واسم المحاضر لهذه الدورة؟

رمز المادة هو CCS3403 واسم المحاضر هو Dr. Mostafa M. Elsherbini.

ما هو موضوع المحاضرة الأولى؟

مقدمة في خوارزميات الحوسبة (Introduction to Computing Algorithms).

ما هو الكتاب المقرر لهذه المادة؟

كتاب Introduction to the Design and Analysis of Algorithms للمؤلف Anany Levitin، الطبعة الثالثة 2012.

اذكر أسماء مؤلفي المرجع Introduction to Algorithms.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.

ماذا قال W. Edwards Deming عن وصف ما نفعله كعملية؟

قال: "إذا لم تستطع وصف ما تفعله كعملية، فأنت لا تعرف ما تفعله".

ما هي خطوات خوارزمية حساب جذور المعادلة التربيعية $ax^2 + bx + c = 0$؟

الخطوة 1: تحديد المعاملات $a$، $b$، و $c$. الخطوة 2: تطبيق الصيغة x = rac{-b imes ext{sqrt}(b^2 - 4ac)}{2a}. الخطوة 3: إيجاد $x_1$. الخطوة 4: إيجاد $x_2$.

ما هو التعريف العام للخوارزمية حسب الصفحة رقم 7؟

هي مجموعة من الخطوات الواضحة وغير الغامضة لإنجاز مهمة أو حل مشكلة.

كيف تُعرف الخوارزمية في علوم الحاسب؟

هي سلسلة من التعليمات غير الغامضة لحل مشكلة، للحصول على مخرجات مطلوبة من أي مدخلات مشروعة في وقت محدود.

لماذا تعتبر الخوارزمية هي العلم في "علوم الحاسب"؟

لأنها تبدأ ببيانات المدخلات، وتجري حسابات معقدة، وتتوقف عند العثور على الإجابة.

ما هو الفرق الرئيسي بين الخوارزمية والبرنامج من حيث التجريد؟

الخوارزمية هي تصميم مجرد (Abstract Design)، بينما البرنامج هو تنفيذ ملموس (Concrete Implementation).

أيهما يعتمد على الأجهزة ونظام التشغيل: الخوارزمية أم البرنامج؟

البرنامج يعتمد على الأجهزة ونظام التشغيل (HW & OS-dependent)، بينما الخوارزمية مستقلة عنهما (HW & OS-independent).

قارن بين لغة كتابة الخوارزمية والبرنامج.

الخوارزمية يمكن كتابتها بأي لغة، بينما البرنامج يتطلب لغة برمجة محددة.

ما هي الخصائص الخمس الأساسية للخوارزمية؟

المدخلات (Input)، المخرجات (Output)، الوضوح (Definiteness)، المحدودية (Finiteness)، والفعالية (Effectiveness).

ماذا تعني خاصية "الوضوح" (Definiteness) في الخوارزمية؟

أن تكون الخطوات غير غامضة وواضحة (Unambiguity and Clearness).

ما هو شرط خاصية "المحدودية" (Finiteness)؟

يجب أن تنتهي الخوارزمية (Must terminate).

ما هو شرط خاصية "الفعالية" (Effectiveness)؟

استهلاك وقت ومساحة أقل (Less time and space).

ما هي الطرق الثلاث لكتابة الخوارزمية؟

اللغة الطبيعية (Natural Language)، المخطط الانسيابي (Flowchart)، والشيفرة الوهمية (Pseudocode).

كيف نحكم على جودة الخوارزمية؟

عن طريق الصحة (Correctness)، الكفاءة (Efficiency)، وسهولة التنفيذ (Ease of Implementation).

ماذا ينتج عن استخدام خوارزمية سيئة؟

تؤدي إلى وقت تنفيذ أطول.

كيف يتم حساب مجموع الأرقام من 1 إلى $10^{12}$ باستخدام خوارزمية جيدة؟

باستخدام الصيغة الرياضية مباشرة sum = rac{n imes (n + 1)}{2}.

ماذا فعل العالم غاوس (Gauss) عندما طُلب منه جمع الأرقام من 1 إلى 100؟

كتب الإجابة 5050 في ثوانٍ معدودة باستخدام التفكير الرياضي بدلاً من الجمع اليدوي المطول.

ما هو التعقيد الزمني لطريقة غاوس مقارنة بطريقة التكرار (Loop)؟

تعقيد غاوس هو $O(1)$ بينما طريقة التكرار هي $O(n)$.

ما هو تعريف المشكلة القابلة للحل (Decidable Problem)؟

هي المشكلة التي توجد لها خوارزمية فعالة (تستغرق وقتاً متعدد الحدود Polynomial Time أو أقل للتنفيذ).

ما هو تعريف المشكلة غير القابلة للحل (Undecidable Problem)؟

هي المشكلة التي لا توجد لها خوارزمية فعالة (تستغرق وقتاً أسياً Exponential Time للتنفيذ).

ما هو تحليل الخوارزميات (Algorithm Analysis)؟

دراسة أداء الخوارزمية بناءً على استهلاك الوقت ومساحة الذاكرة.

قارن بين التحليل المسبق (Priori) والتحليل البعدي (Posteriori) من حيث وقت الحساب.

التحليل المسبق هو تقدير قبل التنفيذ، بينما التحليل البعدي هو حساب بعد التنفيذ.

أيهما يعتمد على لغة البرمجة والأجهزة: التحليل المسبق أم البعدي؟

التحليل البعدي (Posteriori Analysis) يعتمد على لغة البرمجة والأجهزة.

ما هي ميزة التحليل المسبق (Priori Analysis)؟

سريع وعملي ومستقل عن الأجهزة ولغة البرمجة.

ما هو معدل النمو (Growth Rate) في تحليل الخوارزميات؟

هو المعدل الذي يزداد به وقت التشغيل كدالة في حجم المدخلات $(n)$.

ما هي طريقة عد التكرار (Frequency Count Method)؟

طريقة لإيجاد معدل نمو الخوارزمية من خلال عد عدد المرات التي يتم فيها تنفيذ كل تعليمية أساسية.

ماذا يمثل الرمز $F(n)$ والرمز $S(n)$؟

$F(n)$ هي دالة الوقت (Time Function)، و $S(n)$ هي دالة المساحة (Space Function).

في خوارزمية الجمع (result = a + b)، ما هي قيم $F(n)$ و $S(n)$؟

$F(n) = 3$ و $S(n) = 3$، وهي دوال ثابتة.

عند تحليل الخوارزميات، هل نهتم بالقيم الدقيقة لـ $F(n)$؟

لا، نحن مهتمون بمعدلات النمو (Growth Rates) ورتبة معدلات النمو.

ما هو التحليل التقاربي (Asymptotic Analysis)؟

طريقة لوصف السلوك المحدود (Limiting Behavior) للدالة عندما تؤول $n$ إلى ما لا نهاية.

كيف يتم تحديد تدوين Big O؟

تحديد الحد المهيمن (Dominant Term)، تحديد رتبة النمو، ثم كتابة التدوين وتبسيطه.

ما هو تدوين Big O للدالة $f(n) = 3n^3 + 2n^2 + 5n + 1$؟

التدوين المبسط هو $O(n^3)$.

ما هو تدوين Big O للدالة $F(n) = 6n^2 + 100n + 3000$؟

$O(n^2)$.

ما هو تدوين Big O للدالة الثابتة $F(n) = 4$؟

$O(1)$.

اذكر أنواع الأشكال الثلاثة الشائعة للتدوين التقاربي.

تدوين big-O (الحد العلوي)، big-oldsymbol{ ext{ extohm}} (الحد السفلي)، و big-oldsymbol{ ext{ exttheta}} (الحد المتوسط).

رتب رتب التعقيد التالية من الأفضل إلى الأسوأ: $O(n)$, $O(1)$, $O(n^2)$.

الأفضل $O(1)$، ثم $O(n)$، ثم الأسوأ $O(n^2)$.

ماذا يمثل التعقيد $O(N!)$؟

النمو المضروبي (Factorial).

ماذا يمثل التعقيد $O(2^n)$؟

النمو الأسي (Exponential).

ما هو تصنيف الكفاءة لتعقيد $O(n ext{ log } n)$؟

يصنف ككفاءة "سيئة" (Bad) مقارنة بالخطي والجيد، ولكنه أفضل من التربيعي.

ما هو التعقيد الذي يعتبر "الأفضل" (Best) دائماً؟

التعقيد الثابت $O(1)$.

ما هو نوع التعقيد للدالة $F(n) = 4 ext{log}_2(n) + 40$؟

$O( ext{log}_2 n)$.

اذكر ثلاثة أنواع من المشكلات المهمة في الحوسبة.

الفرز (Sorting)، البحث (Searching)، ومعالجة النصوص (String processing).

ما هي المشكلات التي تتعلق بالنقاط والخطوط والمضلعات؟

المشكلات الهندسية (Geometric problems).

ماذا تسمى المشكلات التي تتعلق بالأشياء والرسوم البيانية؟

مشاكل الرسم البياني (Graph problems).

اذكر اثنين من نماذج (Paradigms) الخوارزميات.

الخوارزميات الجشعة (Greedy Algorithms) وفلسفة فرق تسد (Divide and Conquer).

ما هو النموذج الذي يعتمد على البحث الشامل؟

البحث بالقوة الغاشمة (Brute-Force search).

اذكر مثالاً لنماذج خوارزميات مستوحاة من البيئة.

الخوارزميات المستوحاة من الطبيعة (Nature-inspired Algorithms).

ما هو الفرق بين $F(n)$ و $S(n)$ في خوارزمية جمع مصفوفتين ($n imes n$)؟

كلاهما يعتمد على $n^2$ كونه تكرار متداخل ومساحة تخزين مصفوفة.

في الصفحة 33، ما هو تعقيد $F(n) = 2n^3 + 3n^2 + 100n$؟

$O(n^3)$.

كيف يتم تبسيط تدوين Big O؟

عن طريق إسقاط الحدود الأقل أهمية والمعاملات الثابتة.

ما هو تعريف مشاكل التوافق (Combinatorial problems)؟

هي واحدة من أنواع المشكلات المهمة المذكورة في تصنيفات الخوارزميات (الصفحة 37).

ماذا يدرس تحليل الخوارزميات فيما يخص الشبكة؟

يدرس الوصول إلى الشبكة (Network Access) كجزء من استهلاك الموارد.

ماذا يدرس تحليل الخوارزميات فيما يخص الطاقة؟

استهلاك الطاقة (Power Consumption).

ما هو الغرض من استخدام Pseudocode؟

هو وسيلة لتمثيل الخوارزمية تمزج بين اللغة الطبيعية وهياكل لغة البرمجة.

لماذا نستخدم التحليل التقاربي لوصف أداء الخوارزمية؟

لأنه يركز على الجزء المهم من وقت تشغيل الخوارزمية مع نمو حجم المدخلات.

ما هي الموارد التي يستهلكها البرنامج ويجب مراقبتها؟

الوقت والبايتات (Time and Bytes).