ترجمة آلية تحت المراجعة
الأسبوع 3: الخوارزميات
المصدر الأصلي على CS50المحاضرة الثالثة (Lecture 3)
- مرحبًا!
- البحث الخطي
- البحث الثنائي
- وقت التشغيل
- search.c
- phonebook.c
- الهياكل
- الفرز والفرز بالتحديد
- فرز الفقاعة
- العودية
- دمج الفرز
- التلخيص
مرحبًا! (Welcome!)
- في الأسبوع صفر، قدمنا فكرة : صندوق أسود قد يأخذ مدخلات وينشئ مخرجات.
- سنتوسع هذا الأسبوع في فهمنا للخوارزميات من خلال الشيفرة الكاذب وفي الشيفرة نفسه.
- أيضًا، سننظر في كفاءة هذه الخوارزميات. في الواقع، سنبني على فهمنا لكيفية استخدام بعض المفاهيم التي ناقشناها الأسبوع الماضي في بناء الخوارزميات.
-
خذ بعين الاعتبار الرسم البياني التالي:
- يمكن أن تكون الخوارزميات بطيئة، وتتطلب وقتًا وتكلفة معالجة مرتفعين، أو سريعة، وتتطلب معالجة وتكلفة زمنية منخفضة.
- مع دخولنا هذا الأسبوع، يجب أن تفكر في الطريقة التي يمكن بها للطريقة التي تعمل بها الخوارزمية مع المشكلة أن تحدد الوقت المستغرق لحل المشكلة! يمكن تصميم الخوارزميات لتكون أكثر كفاءة إلى الحد الأقصى.
- سنركز اليوم على تصميم الخوارزميات وكيفية قياس كفاءتها.
البحث الخطي (Linear Search)
- تذكر أنه في الأسبوع الماضي، تعرفت على فكرة مصفوفة، كتل الذاكرة المتتالية: جنبًا إلى جنب مع بعضها البعض.
-
يمكنك أن تتخيل مجازيًا مصفوفة مثل سلسلة من سبع خزائن حمراء على النحو التالي:
[0] [1] [2] [3] [4] [5] [6] - يسمى الموضع أقصى اليسار الموقع 0 أو بداية المصفوفة. موقف اليمين المتطرف هو الموقع 6 أو نهاية المصفوفة.
- يمكننا أن نتخيل أن لدينا مشكلة أساسية تتمثل في الرغبة في معرفة "هل الرقم
50داخل مصفوفة؟" يجب أن ينظر الكمبيوتر إلى كل خزانة ليتمكن من معرفة ما إذا كان الرقم أم لا50بالداخل. نحن نسمي هذه العملية للعثور على مثل هذا الرقم أو الحرف أو السلسلة أو أي عنصر آخر البحث. - من المحتمل أن نتمكن من تسليم المصفوفة الخاصة بنا إلى خوارزمية، حيث ستقوم الخوارزمية الخاصة بنا بالبحث في خزائننا لمعرفة ما إذا كان الرقم
50موجود خلف أحد الأبواب، ويعيد القيمةtrueأوfalse. -
يمكننا أن نتخيل تعليمات مختلفة قد نقدمها للخوارزمية الخاصة بنا للقيام بهذه المهمة على النحو التالي:
For each door from left to right If 50 is behind door Return true Return falseلاحظ أنه تم استدعاء التعليمات المذكورة أعلاه الشيفرة شبه البرمجية يعد: نسخة قابلة للقراءة من التعليمات التي يمكننا توفيرها للكمبيوتر.
-
يمكن لعالم الكمبيوتر أن يترجم هذا الشيفرة الكاذب على النحو التالي:
For i from 0 to n-1 If 50 is behind doors[i] Return true Return falseلاحظ أن ما ورد أعلاه لا يزال ليس رمزًا، ولكنه تقريبي قريب جدًا لما قد يبدو عليه الشيفرة النهائي.
البحث الثنائي (Binary Search)
-
بحث ثنائي شيء آخر خوارزمية البحث التي يمكن استخدامها في مهمتنا للعثور على
50. -
بافتراض أن القيم الموجودة داخل الخزانات قد تم ترتيبها من الأصغر إلى الأكبر، فإن الشيفرة المستعار للبحث الثنائي سيظهر كما يلي:
If no doors left Return false If 50 is behind middle door Return true Else if 50 < middle door Search left half Else if 50 > middle door Search right half -
باستخدام تسميات الشيفرة، يمكننا تعديل الخوارزمية الخاصة بنا كما يلي:
If no doors left Return false If 50 is behind doors[middle] Return true Else if 50 < doors[middle] Search doors[0] through doors[middle - 1] Else if 50 > doors[middle] Search doors[middle + 1] through doors[n - 1]لاحظ أنه من خلال النظر إلى هذا التقريب للكود، يمكنك تقريبًا تخيل الشكل الذي قد يبدو عليه هذا في الشيفرة الفعلي.
وقت التشغيل (Running Time)
- يمكنك التفكير في مقدار الوقت الذي تستغرقه الخوارزمية لحل المشكلة.
-
وقت التشغيل يتضمن تحليلًا باستخدام كبير O التدوين. ألق نظرة على الرسم البياني التالي:
- بدلاً من أن يكونوا محددين للغاية بشأن الكفاءة الرياضية للخوارزمية، يناقش علماء الكمبيوتر الكفاءة من حيث ترتيب أوقات تشغيل مختلفة.
- في الرسم البياني أعلاه، الخوارزمية الأولى هي \(O(n)\) أو بالترتيب n. والثاني موجود في \(O(n)\) أيضًا، حيث يتم إسقاط الثوابت في O الكبير. والثالث موجود في \(O(\log n)\).
-
إنه شكل المنحنى الذي يوضح كفاءة الخوارزمية. بعض أوقات التشغيل الشائعة التي قد نراها هي:
- \(O(n^2)\)
- \(O(n \log n)\)
- \(O(n)\)
- \(O(\log n)\)
- \(O(1)\)
- من بين أوقات التشغيل المذكورة أعلاه، يعتبر \(O(n^2)\) هو أبطأ وقت تشغيل. \(O(1)\) هو الأسرع.
- كان البحث الخطي ذا ترتيب \(O(n)\) لأنه قد يستغرق n الخطوات في أسوأ الحالات للتشغيل.
- كان البحث الثنائي ذا ترتيب \(O(\log n)\) لأنه سيستغرق خطوات أقل وأقل للتشغيل، حتى في أسوأ الحالات.
- يهتم المبرمجون بكل من أسوأ الحالات، أو الحد الأعلى، والحالة الأفضل، أو الحد الأدنى.
- يتم استخدام الرمز \(\Omega\) للإشارة إلى أفضل حالة للخوارزمية، مثل \(\Omega(\log n)\).
- يتم استخدام الرمز \(\Theta\) للإشارة إلى تماثل الحد الأعلى والحد الأدنى: حيث تكون أفضل حالة وأوقات تشغيل أسوأ حالة هي نفسها.
- التدوين المقارب هو مقياس مدى جودة أداء الخوارزميات عندما يصبح الإدخال أكبر فأكبر.
- مع استمرارك في تطوير معرفتك في علوم الحاسوب، سوف تستكشف هذه المواضيع بمزيد من التفصيل في الدورات التدريبية المستقبلية.
search.c
-
يمكنك تنفيذ البحث الخطي عن طريق الكتابة
code search.cفي نافذتك الطرفية وكتابة الشيفرة على النحو التالي:// Implements linear search for integers #include <cs50.h> #include <stdio.h> int main(void) { // An array of integers int numbers[] = {20, 500, 10, 5, 100, 1, 50}; // Search for number int n = get_int("Number: "); for (int i = 0; i < 7; i++) { if (numbers[i] == n) { printf("Found\n"); return 0; } } printf("Not found\n"); return 1; }لاحظ أن السطر يبدأ بـ
int numbers[]يسمح لنا بتحديد قيم كل عنصر من عناصر المصفوفة أثناء إنشائه. ثم، في حلقةfor، لدينا تطبيق للبحث الخطي.return 0يستخدم للإشارة إلى النجاح والخروج من البرنامج. يتم استخدامreturn 1للخروج من البرنامج بوجود خطأ (فشل). - لقد قمنا الآن بتنفيذ البحث الخطي بأنفسنا في لغة C!
-
ماذا لو أردنا البحث عن سلسلة داخل مصفوفة؟ قم بتعديل الشيفرة الخاص بك كما يلي:
// Implements linear search for strings #include <cs50.h> #include <stdio.h> #include <string.h> int main(void) { // An array of strings string strings[] = {"battleship", "boot", "cannon", "iron", "thimble", "top hat"}; // Search for string string s = get_string("String: "); for (int i = 0; i < 6; i++) { if (strcmp(strings[i], s) == 0) { printf("Found\n"); return 0; } } printf("Not found\n"); return 1; }لاحظ أننا لا نستطيع الاستفادة
==كما في نسختنا السابقة لهذا البرنامج. بدلا من ذلك، نستخدمstrcmp، والذي يأتي منstring.h.strcmpسيعود0إذا كانت السلاسل متماثلة. لاحظ أيضًا أن طول المصفوفة6عبارة عن ترميز ثابت، وهي ليست ممارسة برمجية جيدة. - في الواقع، تشغيل هذا الشيفرة يسمح لنا بالتكرار على هذه المجموعة من السلاسل لمعرفة ما إذا كانت هناك سلسلة معينة بداخلها. ومع ذلك، إذا رأيت أ خطأ في التجزئة، حيث تم لمس جزء من الذاكرة بواسطة برنامجك والذي لا ينبغي له الوصول إليه، تأكد من أنك قمت بذلك
i < 6المذكور أعلاه بدلاً منi < 7. - يمكنك معرفة المزيد عنه
strcmpفي صفحات دليل CS50.
phonebook.c
-
يمكننا دمج هذه الأفكار المتعلقة بالأرقام والسلاسل في برنامج واحد. اكتب
code phonebook.cفي نافذتك الطرفية واكتب الشيفرة كما يلي:// Implements a phone book without structs #include <cs50.h> #include <stdio.h> #include <string.h> int main(void) { // Arrays of strings string names[] = {"Kelly", "David", "John"}; string numbers[] = {"+1-617-495-1000", "+1-617-495-1000", "+1-949-468-2750"}; // Search for name string name = get_string("Name: "); for (int i = 0; i < 3; i++) { if (strcmp(names[i], name) == 0) { printf("Found %s\n", numbers[i]); return 0; } } printf("Not found\n"); return 1; }لاحظ أن رقم كيلي يبدأ بـ
+1-617، رقم هاتف ديفيد يبدأ بـ+1-617، ورقم جون يبدأ بـ+1-949. ولذلك،names[0]هو كيلي، وnumbers[0]هو رقم كيلي. سيسمح لنا هذا الرمز بالبحث في دليل الهاتف عن رقم محدد لشخص ما. -
أثناء عمل هذا الرمز، هناك العديد من أوجه القصور. في الواقع، هناك احتمال ألا تتطابق الأسماء وأرقام الهواتف مع بعضها البعض. ألن يكون رائعًا لو تمكنا من إنشاء نوع بيانات خاص بنا حيث يمكننا ربط شخص ما برقم هاتفه؟
الهياكل (Structs)
- اتضح أن لغة C تسمح لنا بإنشاء أنواع البيانات الخاصة بنا عبر ملف
struct. -
أليس من المفيد إنشاء نوع بيانات خاص بنا يسمى a
personالذي يحتوي بداخله علىnameو أnumber؟ خذ بعين الاعتبار ما يلي:typedef struct { string name; string number; } person;لاحظ كيف يمثل هذا نوع البيانات الخاص بنا المسمى a
personيحتوي على سلسلة تسمىnameوسلسلة أخرى تسمىnumber. -
يمكننا تحسين الشيفرة السابق الخاص بنا عن طريق تعديل برنامج دليل الهاتف الخاص بنا على النحو التالي:
// Implements a phone book with structs #include <cs50.h> #include <stdio.h> #include <string.h> typedef struct { string name; string number; } person; int main(void) { person people[3]; people[0].name = "Kelly"; people[0].number = "+1-617-495-1000"; people[1].name = "David"; people[1].number = "+1-617-495-1000"; people[2].name = "John"; people[2].number = "+1-949-468-2750"; // Search for name string name = get_string("Name: "); for (int i = 0; i < 3; i++) { if (strcmp(people[i].name, name) == 0) { printf("Found %s\n", people[i].number); return 0; } } printf("Not found\n"); return 1; }لاحظ أن الشيفرة يبدأ بـ
typedef structحيث تم استدعاء نوع بيانات جديد تم تعريفperson. داخل أpersonهي سلسلة تسمىnameو أstringnumber. فيmain، نبدأ بإنشاء مصفوفة تسمىpeopleمن النوعpersonبحجم 3. ثم نقوم بتحديث أسماء وأرقام هواتف الأشخاص الثلاثة في موقعناpeopleمصفوفة. والأهم من ذلك، لاحظ كيف تدوين نقطي، مثلpeople[0].nameيسمح لنا بالوصول إلىpersonفي الموقع 0 وقم بتعيين اسم لهذا الفرد.
الفرز والفرز بالتحديد (Sorting and Selection Sort)
- الفرز هو عملية أخذ قائمة قيم غير مصنفة وتحويل هذه القائمة إلى قائمة مرتبة.
- عندما يتم فرز قائمة، فإن البحث في هذه القائمة يكون أقل عبئًا على الكمبيوتر. تذكر أنه يمكننا استخدام البحث الثنائي في قائمة مرتبة ولكن ليس في قائمة غير مصنفة.
- اتضح أن هناك العديد من الأنواع المختلفة لخوارزميات الفرز.
- فرز التحديد هي إحدى خوارزميات الفرز هذه.
-
يمكننا تمثيل مصفوفة على النحو التالي:
[0] [1] [2] [...] [ن-3] [ن-2] [ن-1] -
خوارزمية فرز التحديد في الشيفرة الكاذب هي:
For i from 0 to n–1 Find smallest number between numbers[i] and numbers[n-1] Swap smallest number with numbers[i] -
بتلخيص هذه الخطوات، تستغرق المرة الأولى للتكرار عبر القائمة
n - 1الخطوات. في المرة الثانية، يستغرق الأمرn - 2الخطوات. ومن خلال تنفيذ هذا المنطق، يمكن تمثيل الخطوات المطلوبة على النحو التالي:(n - 1) + (n - 2) + (n - 3) + ... + 1 - يمكن تبسيط ذلك إلى n(n-1)/2 أو بشكل أكثر بساطة \(O(n^2)\). في أسوأ الحالات أو الحد الأعلى، يكون فرز التحديد بالترتيب \(O(n^2)\). في أفضل الأحوال أو الحد الأدنى، يكون فرز التحديد بالترتيب \(\Omega(n^2)\).
فرز الفقاعة (Bubble Sort)
- فرز الفقاعة هي خوارزمية فرز أخرى تعمل عن طريق تبديل العناصر بشكل متكرر إلى "فقاعة" العناصر الأكبر حجمًا حتى النهاية.
-
الشيفرة المستعار لفرز الفقاعة هو:
Repeat n-1 times For i from 0 to n–2 If numbers[i] and numbers[i+1] out of order Swap them If no swaps Quit - بينما نقوم بفرز المصفوفة بشكل أكبر، نعلم أن المزيد والمزيد منها يتم فرزه، لذلك نحتاج فقط إلى النظر إلى أزواج الأرقام التي لم يتم فرزها بعد.
-
يمكن تحليل نوع الفقاعة على النحو التالي:
- \((n - 1) \times (n - 1)\)
- \(n^2 - n - n + 1\)
- \(n^2 - 2n + 1\)
- أو ببساطة \(O(n^2)\).
- في أسوأ الحالات أو الحد الأعلى، يكون فرز الفقاعة بالترتيب \(O(n^2)\). في أفضل الأحوال أو الحد الأدنى، يكون فرز الفقاعات بالترتيب \(\Omega(n)\).
- يمكنك ذلك تصور مقارنة بين هذه الخوارزميات.
العودية (Recursion)
- كيف يمكننا تحسين كفاءتنا في الفرز؟
-
العودية هو مفهوم ضمن البرمجة حيث تستدعي الوظيفة نفسها. لقد رأينا هذا سابقًا عندما رأينا…
If no doors left Return false If number behind middle door Return true Else if number < middle door Search left half Else if number > middle door Search right halfلاحظ أننا نتصل
searchعلى تكرارات أصغر وأصغر لهذه المشكلة. -
وبالمثل، في الشيفرة المستعار الخاص بنا للأسبوع 0، يمكنك معرفة مكان تنفيذ التكرار:
1 Pick up phone book 2 Open to middle of phone book 3 Look at page 4 If person is on page 5 Call person 6 Else if person is earlier in book 7 Open to middle of left half of book 8 Go back to line 3 9 Else if person is later in book 10 Open to middle of right half of book 11 Go back to line 3 12 Else 13 Quit -
كان من الممكن تبسيط هذا الشيفرة لتسليط الضوء على خصائصه العودية كما يلي:
1 Pick up phone book 2 Open to middle of phone book 3 Look at page 4 If person is on page 5 Call person 6 Else if person is earlier in book 7 Search left half of book 9 Else if person is later in book 10 Search right half of book 12 Else 13 Quit - A الحالة الأساسية يتم تعريف على أنه الشرط الذي يمنع التكرار من الاستمرار إلى أجل غير مسمى، مما يمنع الحلقات اللانهائية.
-
A حالة متكررة يتم تعريف على أنه جزء من الدالة العودية التي تستدعي نفسها بإدخال معدل، وتتحرك نحو الحالة الأساسية.
-
ضع في اعتبارك كيف أردنا في الأسبوع الأول إنشاء هيكل هرمي كما يلي:
# ## ### #### -
النوع
code iteration.cفي نافذتك الطرفية واكتب الشيفرة كما يلي:// Draws a pyramid using iteration #include <cs50.h> #include <stdio.h> void draw(int n); int main(void) { // Get height of pyramid int height = get_int("Height: "); // Draw pyramid draw(height); } void draw(int n) { // Draw pyramid of height n for (int i = 0; i < n; i++) { for (int j = 0; j < i + 1; j++) { printf("#"); } printf("\n"); } }لاحظ أن هذا الشيفرة يبني الهرم عن طريق التكرار.
-
لتنفيذ ذلك باستخدام العودية، اكتب
code recursion.cفي نافذتك الطرفية واكتب الشيفرة كما يلي:// Draws a pyramid using recursion #include <cs50.h> #include <stdio.h> void draw(int n); int main(void) { // Get height of pyramid int height = get_int("Height: "); // Draw pyramid draw(height); } void draw(int n) { // If nothing to draw if (n <= 0) { return; } // Draw pyramid of height n - 1 draw(n - 1); // Draw one more row of width n for (int i = 0; i < n; i++) { printf("#"); } printf("\n"); }لاحظ أن الحالة الأساسية ستضمن عدم تشغيل الشيفرة إلى الأبد. الخط
if (n <= 0)ينهي التكرار لأنه تم حل المشكلة. في كل مرةdrawيطلق على نفسه، يطلق على نفسه اسمn-1. في مرحلة ما،n-1سوف يساوي0، مما أدى إلى تعود وظيفةdraw، وسينتهي البرنامج.
دمج الفرز (Merge Sort)
- يمكننا الآن الاستفادة من التكرار في سعينا للحصول على خوارزمية فرز أكثر كفاءة وتنفيذ ما يسمى فرز الدمج، خوارزمية فرز فعالة للغاية.
-
الشيفرة المستعار لفرز الدمج قصير جدًا:
If only one number Quit Else Sort left half of numbers Sort right half of numbers Merge sorted halves -
فكر في قائمة الأرقام التالية:
6341 -
أولاً، يسألك فرز الدمج، "هل هذا رقم واحد؟" الجواب هو "لا"، لذلك تستمر الخوارزمية.
6341 -
ثانيًا، سيؤدي فرز الدمج الآن إلى تقسيم الأرقام إلى المنتصف (أو إلى أقرب ما يمكن) وفرز النصف الأيسر من الأرقام.
63|41 -
ثالثًا، سينظر الفرز المدمج إلى هذه الأرقام الموجودة على اليسار ويسأل، "هل هذا رقم واحد؟" وبما أن الإجابة هي لا، فسيتم تقسيم الأرقام الموجودة على اليسار إلى المنتصف.
6|3 -
رابعًا، سيسألك الفرز المدمج مرة أخرى، "هل هذا رقم واحد؟" الجواب نعم هذه المرة! ولذلك، فإنه سيتم إنهاء هذه المهمة والعودة إلى المهمة الأخيرة التي كان يقوم بها في هذه المرحلة:
63|41 -
خامسًا، سيؤدي فرز الدمج إلى فرز الأرقام الموجودة على اليسار.
36|41 -
الآن، نعود إلى حيث توقفنا في الشيفرة المستعار بعد فرز الجانب الأيسر. ستحدث عملية مماثلة من الخطوات من 3 إلى 5 مع الأرقام اليمنى. سيؤدي هذا إلى:
36|14 -
تم الآن فرز كلا النصفين. وأخيرا، سوف تقوم الخوارزمية بدمج كلا الجانبين. وسوف ننظر إلى الرقم الأول على اليسار والرقم الأول على اليمين. وسوف يضع الرقم الأصغر أولا، ثم الثاني الأصغر. ستقوم الخوارزمية بتكرار ذلك لجميع الأرقام، مما يؤدي إلى:
1346 - اكتمل فرز الدمج، وتم إنهاء البرنامج.
- يعد فرز الدمج خوارزمية فرز فعالة للغاية مع أسوأ حالة \(O(n \log n)\). أفضل حالة هي \(\Omega(n \log n)\) لأن الخوارزمية لا تزال بحاجة لزيارة كل مكان في القائمة. لذلك، يكون فرز الدمج أيضًا \(\Theta(n \log n)\) نظرًا لأن أفضل حالة وأسوأ حالة هي نفسها.
- نهائي التصور تمت مشاركة .
التلخيص (Summing Up)
في هذا الدرس، تعلمت كيفية التفكير الخوارزمي وبناء أنواع البيانات الخاصة بك. وعلى وجه التحديد، تعلمت…
- الخوارزميات.
- كبير O التدوين.
- البحث الثنائي والبحث الخطي.
- خوارزميات فرز مختلفة، بما في ذلك فرز الفقاعات، وفرز التحديد، وفرز الدمج.
- العودية.
نراكم في المرة القادمة!