خوارزميات MIT:المحاضرة الأولى

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 نسبة التقدم

انتهت بحمد الله ترجمة المحاضرة. كل التدقيقات والتحسينات للترجمة مرحب بها.

 أمور ادارية

We're going to get started. Handouts are the by the door if anybody didn't pick one up. My name is Charles Leiserson. I will be lecturing this course this term, Introduction to Algorithms, with Erik Demaine. In addition, this is an SMA course, a Singapore MIT Alliance course which will be run in Singapore by David Hsu. And so all the lectures will be videotaped and made available on the Web for the Singapore students, as well as for MIT students who choose to watch them on the Web. If you have an issue of not wanting to be on the videotape, you should sit in the back row. OK? Otherwise, you will be on it.

سنبدأ. مطبوعات التوزيع متوفرة على الباب في حال لم يأخذها أي منكم. اسمي شارلز لايسرسون. سأحاضر هذه المادة في هذا الفصل، وهي مقدمة إلى الخوارزميات، مع إريك دمين. أيضاً، هذه المادة هي ضمن مقرَر SMA، تحالف سنغافورة وإم آي تي، حيث سيدار في سنغافورة من قبل ديفيد شو. لذلك سيتم تصوير كل المحاضرات وستكون متوافرة على الإنترنت للطلاب السنغافوريين، وكذلك لطلاب MIT الذي يفضلون مشاهدة المحاضرات على الإنترنت. إذا كنت لا ترغب بالظهور على شريط الفيديو، عليك أن تجلس في الصف الخلفي، هل هذا جيد؟ وإلا ستظهر على الشريط.

There is a video recording policy, but it seems like they ran out. If anybody wants to see it, people, if they could just sort of pass them around maybe a little bit, once you're done reading it, or you can come up. I did secure one copy. Before we get into the content of the course, let's briefly go over the course information because there are some administrative things that we sort of have to do.

توجد وثيقة سياسة تسجيل الفيديو لكن يبدو أنها نفدت. إذا أراد أحد رؤيتها، يا شباب، إذا استطعتم تمريرها قليلاً، حالما تنتهون من قراءتها، وإلا فعليكم المجيء إليّ ، فقد قمت بتأمين نسخة. فقبل أن ندلف إلى محتوى المادة، دعونا نراجع باختصار معلومات المادة لأنه توجد بعض الأمور الإدارية التي علينا القيام بها نوعاً ما.

As you can see, this term we have a big staff. Take a look at the handout here. Including this term six TAs, which is two more TAs than we normally get for this course. That means recitations will be particularly small. There is a World Wide Web page, and you should bookmark that and go there regularly because that is where everything will be distributed. Email. You should not be emailing directly to, even though we give you our email addresses, to the individual members of the staff. You should email us generally. And the reason is you will get much faster response. And also, for any communications, generally we like to monitor what the communications are so it's helpful to have emails coming to everybody on the course staff. As I mentioned, we will be doing distance learning this term. And so you can watch lectures online if you choose to do that.

كما يمكنكم أن تروا، في هذا الفصل لدينا طاقم كبير. لنلق نظرة على المنشور الموزَع. سيكون لدينا في هذا الفصل ستة مساعدي تدريس، وهذا يعني زيادة مساعدين عما كان في العادة لمثل هذا المقرر. وهذا يعني أن مراجعاتهم ستكون صغيرة العدد. هناك صفحة للمقرر على شبكة الإنترنت، ويجب أن تبوبها وتزورها بانتظام لأن كل شيء سيوزع من خلالها. البريد الإلكتروني. لا ينبغي أن تراسلنا شخصياً، على الرغم من أننا نعطيكم عناوين البريد الإلكتروني لأفراد الطاقم التدريسي. إلا أن عليك مراسلتنا على بريدنا العمومي. والسبب هو أنك سوف تحصل على استجابة أسرع بكثير. وبالإضافة إلى ذلك، وبالنسبة لأية اتصالات، فإننا نحب أن نكون على اطلاع على ماهية المراسلات، لذلك فإنه من المفيد الحصول على رسائل البريد الإلكتروني من قبل جميع أعضاء الفريق التدريسي. كما ذكرت، فإننا سنمارس التعلم عن بعد، لذلك يمكنك مشاهدة المحاضرات عبر الإنترنت إذا اخترت القيام بذلك.

I would recommend, for people who have the opportunity to watch, to come live. It's better live. You get to interact. There's an intangible that comes with having it live. In fact, in addition to the videos, I meet weekly with the Singapore students so that they have a live session as well. Prerequisites. The prerequisites for this course are 6.042, which is Math for Computer Science, and 6.001. You basically need discrete mathematics and probability, as well as programming experience to take this course successfully. People do not have that background should not be in the class. We will be checking prerequisites. If you have any questions, please come to talk to us after class.

أود أن أوصي الأشخاص الذين لديهم فرصة المشاهدة بالقدوم والحضور المباشر. الحضور المباشر أفضل. ستتمكن من التفاعل. هنالك أشياء غير مباشرة وملموسة تتحقق من خلال الحضور المباشر. في الحقيقة، بالإضافة إلى أشرطة الفيديو ، ألتقي بشكل أسبوعي مع طلاب سنغافورة بحيث يحصلون على جلسة مباشرة أيضاً. الشروط المسبقة. الشروط الأساسية لهذه الدورة هي مقرر 6.042 ، وهو الرياضيات لعلم الحاسوب، بالإضافة إلى المقرر رقم 6.001 (وهو مقدمة إلى علم الحاسوب). بالإضافة إلى ذلك تحتاج بشكل أساسي إلى الرياضيات المتقطعة والاحتمالات، وكذلك تجربة مع البرمجة حتى تستفيد من المقرر بشكل ناجح. لا ينبغي لمن ليس لديهم هذه الخلفية أن يكونوا في الصف. سنقوم بالتأكد من توافر هذه الشروط. إذا كانت لديكم أية أسئلة، الرجاء القدوم والتحدث إلينا بعد انتهاء الصف.

Let's see. Lectures are here. For SMA students, they have the videotapes and they will also have a weekly meeting. Students must attend a one-hour recitation session each week. There will be new material presented in the recitation. Unlike the lectures, they will not be online. Unlike the lectures, there will not be lecture notes distributed for the recitations in general. And, yet, there will be material there that is directly on the exams. And so every term we say oh, when did you cover that? That was in recitation. You missed that one. So, recitations are mandatory. And, in particular, also let me just mention your recitation instructor is the one who assigns your final grade. So we have a grade meeting and keep everybody normal, but your recitation has the final say on your grade.

دعونا نرى. المحاضرات ستعطى هنا. بالنسبة لطلاب سنغافورة، لديهم أشرطة فيديو وسيكون لديهم أيضا اجتماع أسبوعي. يجب على الطلاب حضور المحاضرات المصغرة لمدة ساعة كل أسبوع. ستعرض وتقدم خلالها مواد جديدة. وخلافا للمحاضرات، فإنها لن تكون على الإنترنت. وخلافا للمحاضرات، لن يكون هناك توزيع لملاحظات المحاضرات بشكل عام. وحتى الآن، ستكون هنالك مواد تأتي مباشرة في الامتحانات. وهكذا في كل فصل نقول أوه، متى تمت تغطية ذلك؟ لقد كان ذلك في جلسات المحاضرات المصغرة. لقد غبت عنها. لذلك فإن جلسات المحاضرات المصغرة إلزامية. وعلى وجه الخصوص، اسمحوا لي أن أذكر أيضاً أن مساعدي المدرسين في تلك الجلسات هم المسؤولون عن تعيين علامتكم النهائية. بالطبع ستكون لدينا لقاءات للعلامة، وليبق الجميع طبيعياً!ولكن للجلسات المصغرة القول الفصل في علامتك.

Handouts. Handouts are available on the course Web page. We will not generally, except for this one, first handout, be bringing handouts to class. Textbook is this book, Introduction to Algorithms. MIT students can get it any of the local bookstores, including the MIT Coop. There is also a new online service that provides textbooks. You can also get a discount if you buy it at the MIT Press Bookstore. There is a coupon in the MIT Student Telephone Directory for a discount on MIT Press books. And you can use that to purchase this book at a discount. Course website. This is the course website. It links to the Stellar website, which is where, actually, everything will be kept.

بالنسبة لمطبوعات التوزيع فإنها متوفرة على صفحة المقرر الإلكترونية. فنحن بشكل عام -عدا هذه المطبوعة التي بين أيدينا- لن نحضر مطبوعات التوزيع إلى الصف. الكتاب التعليمي هو هذا الكتاب، مقدمة للخوارزميات، يمكن لطلاب إم آي تي أن يحضروه من أي متجر كتب محلي أو من مخزن إم آي تي التعواني، وهناك أيضاً خدمة جديدة على الانترنت تقوم بتأمين الكتب التعليمية. ويمكنكم أيضاً أن تحصلوا على حسم إن اشتريتموه من متجر كتب مطبعة إم آي تي، وهناك قسيمة في دليل هاتف طلاب إم آي تي للحصول على حسم على كتب مطبعة إم آي تي ويمكنكم استخدام ذلك لتشتروا هذا الكتاب بسعر مخفض. هذا هو موقع المقرر. وهو يحوي رابطاً إلى الموقع النجمي وهو المكان الذي سيتم الاحتفاظ بكل شيء ضمنه.

And SMA students have their own website. Some students find this course particularly challenges so we will have extra help. We will post weekly office hours on the course website for the TAs. And then as an experiment this term, we are going to offer homework labs for this class. What a homework lab is, is it's a place and a time you can go where other people in the course will go to do homework.

ولدى طلاب سنجافورة موقعهم الخاص، بعض الطلاب يجدون هذا المقرر صعباًبشكل خاص، لذلك سنحصل على مساعدة إضافية، سوف نضع ساعات مكتبية أسبوعية للمدرسين المساعدين على الموقع الإلكتروني للمقرر، وبعد ذلك وكتجربة في هذا الفصل، سنقوم بتقديم وظائف مخبر لهذا الصف، ما هي وظائف المخبر؟ هي مكان وزمان حيث يمكنك أن تذهب وحيث يذهب باقي الناس الذين يأخذون المقرر ليحلوا وظائفهم.

And there will be typically two TAs who staff the lab. And so, as you're working on your homework, you can get help from the TAs if you need it. And it's generally a place, we're going to schedule those, and they will be on the course calendar for where it is and when it is that they will be held, but usually Sundays 2:00 to 4:00 pm, or else it will be some evening. I think the first one is an evening, right?

وسيدير المخبر عادة مدرسان مساعدان، وهكذا بينما تعملون على وظائفكم يمكنكم الحصول على مساعدة من المدرسين المساعدين إذا احتجتم لذلك. وهو عادة مكان، طبعاً سنقوم بتنظيم تلك الجلسات، وستكون على تقويم المقرر لتحديد المكان والزمان الذي ستقام فيه، ولكنها عادة ما تكون يوم الأحد من 2:00 إلى 4:00 مساءً، وإلا ستكون في مساء يوم ما، أعتقد أن الأولى ستكون مساءً، صحيح؟

Near to when the homework is due. Your best bet is try to do the homework in advance of the homework lab. But then, if you want extra help, if you want to talk over your solutions with people because as we will talk about problem sets you can solve in collaboration with other people in the class. In addition, there are several peer assistance programs. Also the office of Minority Education has an assistance program, and those usually get booked up pretty quickly. If you're interested in those, good idea to make an appointment to get there and get help soon. The homework labs, I hope a lot of people will try that out. We've never done this. I don't know of any other course. Do other people know of courses at MIT that have done this? 6.011 did it, OK.

حين تأخذ وظيفة، فإن أفضل ما تقوم به هو أن تحاول أن تحل الوظيفة قبل الذهاب إلى المخبر لحلها، ولكن عندها إذا أردت مساعدة إضافية، أو إن أردت أن تناقش حلولك مع باقي الأشخاص لأنه كما سنتحدث، سيكون هنالك مجموعات من المسائل التي تستطيعون أن تتعاونوا على حلها مع أشخاص آخرين في الصف. وبالإضافة لذلك هناك عدة برامج للحصول على المساعدة، وكذلك فإن عند مكتب التعليم القاصر برنامج للمساعدة، ويتم حجز هذه البرامج عادة بسرعة كبيرة، إذا كنت مهتماً في هذه البرامج، فإنها فكرة جيدة أن تأخذ موعداً لتحصل على مكان هناك وتحصل على المساعدة قريباً. مختبرات الوظائف، آمل أن يجرب كثير من الأشخاص ذلك، لم نقم بذلك من قبل، لا أعلم أي مواد أخرى قامت به، هل يعلم أناس آخرون عن مقرات في إم آي تي قامت بذلك؟ 6.011 قام به، حسناً.

Good. And was it successful in that class? It never went, OK. Good. [LAUGHTER] We will see. If it's not paying off then we will just return to ordinary office hours for those TAs, but I think for some students that is a good opportunity. If you wish to be registered in this course, you must sign up on the course Web page. So, that is requirement one. It must be done today. You will find it difficult to pass the course if you are not in the class. And you should notify your TA if you decide to drop so that we can get you off and stop the mailings, stop the spam. And you should register today before 7:00 PM.

جيد. وهل نجح في ذلك المقرر؟ لم ينجح أبداً، حسناً. جيد. سنرى. إذا لم يكن ذلك مجدياً فسنعود إذاً إلى الساعات المكتبية العادية لهؤلاء المدرسين، ولكن أعتقد أن هذه فرصة جيدة لبعض الطلاب. إذا أردت أن يتم تسجيلك في هذا المقرر، يجب عليك التسجيل على الصفحة الإلكترونية للمقرر. إذاً، هذا ما نحتاجه أولاً، يجب القيام بذلك اليوم، ستجدون أنه من الصعب النجاح بالمقرر إذا لم تكونوا في الصف. وعليك أن تنبه مدرسك المساعد إذا قررت أن تترك المقرر حتى نتمكن من إخراجك منه وأن نوقف البريد الإلكتروني، نوقف السبام. وعليكم أن تسجلوا اليوم قبل 7:00 مساءاً.

And then we're going to email your recitation assignment to you before Noon tomorrow. And if you don't receive this information by Thursday Noon, please send us an email to the course staff generally, not to me individually, saying that you didn't receive your recitation assignment. And so if you haven't received it by Thursday Noon you want to. I think generally they are going to send them out tonight or at least by tomorrow morning.

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

Yeah. OK. SMA students don't have to worry about this. Problem sets. We have nine problem sets that we project will be assigned during the semester. A couple things about problem sets. Homeworks won't generally be accepted, if you have extenuating circumstances you should make prior arrangements with your recitation instructor. In fact, almost all of the administrative stuff, you shouldn't come to me to ask and say can I hand in something late? You should be talking to your recitation instructor.

حسناً، حسناً، طلاب سنغافورة ليس عليهم القلق حيال هذا، مجموعات المسائل. لدينا تسع مجموعات مسائل والتي نخطط أن يتم إعطاؤها خلال الفصل، بعض الأشياء فيما يخص مجموعات المسائل، لن تٌقبل الوظائف بشكل عام، إذا كانت لديك ظروف مخففة فإنه عليك أن تقوم بترتيبات مسبقة مع مدرس المحاضرات المصغرة خاصتك. في الواقع، تقريباً بالنسبة لكل ما يتعلق بالأمور الإدارية، عليك ألا تأتي إلي وتطلب مني قائلاً هل يمكنني أن أسلم شيئاً ما متأخراً؟ عليك أن تتحدث بهذه الأمور مع مدرس المحضرات المصغرة خاصتك.

You can read the other things about the form, but let me just mention that there are exercises that should be solved but not handed in as well to give you drill on the material. I highly recommend you doing the exercises. They both test your understanding of the material, and exercises have this way of finding themselves on quizzes. You're often asked to describe algorithms. And here is a little outline of what you can use to describe an algorithm. The grading policy is something that somehow I cover. And always every term there are at least a couple of students who pretend like I never showed them this. If you skip problems it has a nonlinear effect on your grade. Nonlinear, OK?

يمكنكم قراءة الأشياء الأخرى المتعلقة بالاستمارة، ولكن اسمحوا لي فقط أن أذكر أنه هناك تمارين يجب أن تحل ولكن لا يتم تسليمها والهدف منها أن تمرنكم على المادة. أنصحكم بشدة أن تحلوا التمارين. فهي في نفس الوقت تفحص فهمك للمادة، وأحياناً تجد طريقها إلى ورقة الامتحان المفاجئ. غالباً ما يطلب منكم وصف خوارزميات. وهاكم ملخصاً صغيراً لما يمكنكم استخدامه لوصف خوارزمية. سياسة وضع العلامات هي شيء أغطيه بطريقة ما. وهناك دائماً في كل فصل طالبان أو ثلاثة يتظاهرون أني لم أرهم هذا أبداً. إذاً إن ترككم المسائل له أثر غير خطي على علامتكم. غير خطي، فهمتم؟

If you don't skip any problems, no effect on your grade. If you skip one problem, a hundredth of a letter grade, we can handle that. But two problems it's a tenth. And, as you see, by the time you have skipped like five letter grades, it is already five problems. This is not problem sets, by the way. This is problems, OK? You're down a third of a letter grade. And if you don't do nine or more, so that's typically about three to four problem sets, you don't pass the class. I always have some students coming at the end of the year saying oh, I didn't do any of my problems. Can you just pass me because I did OK on the exams? Answer no, a very simple answer because we've said it upfront. So, the problem sets are an integral part of the course. Collaboration policy.

إذا لم تترك أي مسألة، لن تتأثر علامتك, إذا تركت مسألة واحدة, جزء من مئة من الدرجة، يمكننا تدبر ذلك. لكن أن تترك مسألتان فهذا عشر. وكما ترى بمرور الوقت تكون قد تركت خمس درجات، إنها خمس مسائل إلى الآن. هذه ليست مجموعات مسائل بالمناسبة. هذه مسائل، حسناً؟ أنت أقل بثلث من الدرجة. وإذا لم تحل تسعة أو أكثر، وهذا الرقم عادة ما يقارب ثلاث أو أربع مجموعات من المسائل، فلن تنجح في هذا الصف. دئماً يكون لدي بعض الطلاب الذين يأتون في نهاية العام ويقولن أوه، لم أقم بحل أي من مسائلي، هل يمكنك فقط أن تنجحني لأني كنت جيداً في الامتحان؟ الجواب هو لا، جواب بسيط جداً لأننا قلناه منذ البداية، لذا فإن مجموعات المسائل هي جزء لا يتجزأ من المقرر. سياسة التعاون.

This is extremely important so everybody pay attention. If you are asleep now wake up. Like that's going to wake anybody up, right? [LAUGHTER] The goal of homework. Professor Demaine and my philosophy is that the goal of homework is to help you learn the material. And one way of helping to learn is not to just be stuck and unable to solve something because then you're in no better shape when the exam roles around, which is where we're actually evaluating you.

وهذا أمر مهم للغاية فلينتبه الجميع. إذا كنت نائما فاستيقظ الآن. رغم أن هذا لن يوقظ أي شخص، صحيح؟ [ضحك]. الهدف من الوظائف. فلسفتي وفلسفة أستاذ دومن أن الهدف من الواجبات المنزلية هو مساعدتك على تعلم المادة. وإحدى طرق المساعدة على التعلم ليس فقط أن تعلق وتصبح غير قادر على حل شيء ما، لأنك لن تكون في حال أفضل عندما دور الامتحان، وهو المكان الذي نقيمك فيه حقيقة.

So, you're encouraged to collaborate. But there are some commonsense things about collaboration. If you go and you collaborate to the extent that all you're doing is getting the information from somebody else, you're not learning the material and you're not going to do well on the exams. In our experience, students who collaborate generally do better than students who work alone. But you owe it to yourself, if you're going to work in a study group, to be prepared for your study group meeting. And specifically you should spend a half an hour to 45 minutes on each problem before you go to group so you're up to speed and you've tried out your ideas. And you may have solutions to some, you may be stuck on some other ones, but at least you applied yourself to it. After 30 to 45 minutes, if you cannot get the problem, just sitting there and banging your head against it makes no sense.

إذاً، نحن نشجعكم على التعاون. ولكن هناك بعض الأمور البديهية حول التعاون. اذا ذهبت وكنت تتعاون لدرجة أن كل ما نقوم به هو الحصول على معلومات من شخص آخر، فإنك لا تتعلم المواد ولن تقدم للامتحان بشكل جيد. وفقاً تجربتنا ، الطلاب الذين يتعاونون عموما يحققون نتائج أفضل من الطلاب الذين يعملون وحدهم. ولكن عليك أن تلزم نفسك، إذا كنت تريد العمل في مجموعة الدراسة، أن تكون مستعداً لاجتماع فريق دراستك. وعلى وجه التحديد عليك أن تنفق من نصف ساعة إلى 45 دقيقة على كل مسألة قبل ان تذهب الى المجموعة فتكون قادراً على التجاوب بسرعة وتكون قد حاولت أن تجرب أفكارك. وربما تكون لديك حلول لبعضها، وقد تعلق على بعضها الآخر، ولكن على الأقل قمت بتعريض نفسك لها. بعد 30 إلى 45 دقيقة، وإذا لم تتمكن من حل المسألة، فلن يكون مجرد الجلوس هناك وضرب رأسك بها ذا أي معنى.

It's not a productive use of your time. And I know most of you have issues with having time on your hands, right? Like it's not there. So, don't go banging your head against problems that are too hard or where you don't understand what's going on or whatever. That's when the study group can help out. And, as I mentioned, we'll have homework labs which will give you an opportunity to go and do that and coordinate with other students rather than necessarily having to form your own group.

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

And the TAs will be there. If your group is unable to solve the problem then talk to other groups or ask your recitation instruction. And, that's how you go about solving them. Writing up the problem sets, however, is your individual responsibility and should be done alone. You don't write up your problem solutions with other students, you write them up on your own. And you should on your problem sets, because this is an academic place, we understand that the source of academic information is very important, if you collaborated on solutions you should write a list of the collaborators. Say I worked with so and so on this solution. It does not affect your grade. It's just a question of being scholarly.

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

It is a violation of this policy to submit a problem solution that you cannot orally explain to a member of the course staff. You say oh, well, my write-up is similar to that other person's. I didn't copy them. We may ask you to orally explain your solution. If you are unable, according to this policy, the presumption is that you cheated. So, do not write up stuff that you don't understand. You should be able to write up the stuff that you understand. Understand why you're putting down what you're putting down. If it isn't obvious, no collaboration whatsoever is permitted on exams. Exams is when we evaluate you. And now we're not interested in evaluating other people, we're interested in evaluating you. So, no collaboration on exams. We will have a take-home exam for the second quiz.

إنه انتهاك لهذه السياسة أن تقدم حلول المسائل التي لا يمكن أن تُشرح شفويا لأحد طاقم التدريس. ستقول أوه ، حسنا ، إن كتابتي مماثلة لكتابة ذلك الشخص. لم أقم بنسخها. قد نطلب منك أن تشرح الحل شفويا. إذا كنت غير قادر، وفقا لهذه السياسة، فإننا سنفترض أنك قد قمت بالغش. لذلك لا تقم بكتابة أشياء لا تفهمها. عليك أن تكون قادراً على أن تكتب الأشياء التي تفهمها للفريق. يجب أن تكون قادرا على كتابة الأشياء التي تفهمها. إذا لم تكن هذه الحقيقة واضحة، فلا يسمح على الإطلاق بالتعاون في الامتحانات. الامتحان هو المكان الذي نقيمك فيه. ونحن الآن لسنا مهتمين بتقييم الآخرين، نحن مهتمون بتقييمك أنت. لذا، لا تعاون في الامتحانات. وسيكون الاختبار التالي لدينا امتحاناً بيتياً.

You should look at the schedule. If there are problems with the schedule of that, we want to know early. And we will give you more details about the collaboration in the lecture on Monday, November 28th. Now, generally, the lectures here, they're mandatory and you have to know them, but I know that some people say gee, 9:30 is kind of early, especially on a Monday or whatever. It can be kind of early to get up.

ينبغي أن ننظر في الجدول الزمني. إذا كانت لديك مشاكل مع الجدول الزمني، نريد أن نعرف ذلك في وقت مبكر. وسنقدم لكم المزيد من التفاصيل حول التعاون في محاضرة يوم الإثنين، 28 نوفمبر. الآن ، وبشكل عام، المحاضرات هنا إلزامية وعليك أن تعرفها، ولكنني أعلم أن بعض الناس يقولون أوه، التاسعة والنصف إنه وقت مبكر، خصوصا يوم الاثنين أو أيا كان. ويمكن أن يكون من المبكر الاستيقاظ في هذا الوقت.

However, on Monday, November 28th, you fail the exam if you do not show up to lecture on time. That one day you must show up. Any questions about that? That one day you must show up here, even if you've been watching them on the Web. And generally, if you think you have transgressed, the best is to come to us to talk about it. We can usually work something out. It's when we find somebody has transgressed from a third-party or from obvious analyses that we do with homeworks, that's when things get messy. So, if you think, for some reason or other, oh, I may have done something wrong, please come and talk to us. We actually were students once, too, albeit many years ago. Any questions? So, this class has great material.

ومع ذلك ، ويوم الاثنين، 28 نوفمبر، سترسب في الامتحان إذا لم تأت للمحاضرة في الوقت المحدد. في ذلك اليوم عليك أن تظهر. هل من أسئلة حول هذا؟ في ذلك اليوم عليك أن تأتي إلى هنا، حتى لو كنت تشاهد المحاضرات على شبكة الانترنت. وعموما ، إذا كنت تعتقد أنك قمت بمخالفة، الأفضل هو ان تأتي إلينا وتتحدث حول هذا الموضوع. وعادة ما يمكننا أن نجد حلاً ما. انه عندما نجد أن شخصاً ما قد تجاوز عن طريق طرف ثالث أو من تحليلات نقوم بها على الواجبات، هذا الوقت الذي تصبح الأمور فيه فوضوية. لذا ، إذا كنت تعتقد ، لسبب أو لآخر ، أوه، أنني ربما قد ارتكبت خطأً، أرجوك، تعال وتحدث إلينا. في الحقيقة لقد كنا طلاباً مرة أيضاً، وإن كان ذلك منذ سنوات عديدة. أي أسئلة؟ إذاً هذا المقرر يحوي مادة ضخمة.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 المقدمة

Fabulous material. And it's really fun, but you do have to work hard. Let's talk content. This is the topic of the first part of the course. The first part of the course is focused on analysis. The second part of the course is focused on design. Before you can do design, you have to master a bunch of techniques for analyzing algorithms. And then you'll be in a position to design algorithms that you can analyze and that which are efficient. The analysis of algorithm is the theoretical study --

المادة رائعة، وهي ممتعة بحق، ولكن عليك العمل بجد. دعونا نتحدث عن المحتوى. هذا هو موضوع الجزء الأول من المقرر. يركز الجزء الأول من المقرر على التحليل. يركز الجزء الثاني من المقرر على التصميم. فقبل أن تصل إلى إمكانية التصميم ، لا بد لك من إتقان مجموعة من تقنيات تحليل الخوارزميات. ثم ستكون بعد ذلك في وضع يمكّنك من تصميم الخوارزميات التي يمكنك تحليلها وتلك التي تتسم بالكفاءة. وتحليل الخوارزمية هو الدراسة النظرية.

-- of computer program performance -- -- and resource usage. And a particular focus on performance. We're studying how to make things fast. In particular, computer programs. We also will discover and talk about other resources such as communication, such as memory, whether RAM memory or disk memory. There are other resources that we may care about, but predominantly we focus on performance. Because this is a course about performance, I like to put things in perspective a little bit by starting out and asking, in programming, what is more important than performance?

-- أداء برنامج الحاسوب -- واستخدام الموارد. والتركيز بشكل خاص على الأداء. سندرس كيفية جعل الأمور تجري بسرعة. لاسيما برامج الحاسوب. بالإضافة إلى ذلك سنكتشف ونتحدث عن موارد أخرى كالاتصالات، والذاكرة ، سواء أكانت ذاكرة الوصول العشوائي RAM أو كانت ذاكرة القرص. وهناك موارد أخرى قد نهتم بها، ولكننا نركز على الأداء على الأغلب. ولأن هذا المقرر هو بالطبع عن الأداء، أود أن وضع الأمور في نصابها قليلا من خلال البدء بسؤال: في البرمجة: ما هو الشيء الأكثر أهمية من الأداء؟

If you're in an engineering situation and writing code, writing software, what's more important than performance? Correctness. Good. OK. What else? Simplicity can be. Very good. Yeah. Maintainability often much more important than performance. Cost. And what type of cost are you thinking? No, I mean cost of what? We're talking software here, right? What type of cost do you have in mind?

إذا كنت تمارس عملاً هندسياً وتكتب الرماز، وتكتب البرمجيات، ما هو الشيء الأكثر أهمية من الأداء؟ اتباع المبادئ. هذا جيد. وماذا ايضا؟ البساطة، نعم قد تكون كذلك. جيد جدا. نعم. الصيانة في كثير من الأحيان قد تكون أكثر أهمية من الأداء. التكلفة. وأي نوع من التكلفة تفكر فيه؟ لا، أقصد تكلفة ماذا؟ نحن نتحدث هنا عن البرنامج، أليس كذلك؟ ما هو نوع التكلفة في ذهنك؟

There are some costs that are involved when programming like programmer time. So, programmer time is another thing also that might be. Stability. Robustness of the software. Does it break all the time? What else? Come on. We've got a bunch of engineers here. A lot of things. How about features? Features can be more important. Having a wider collection of features than your competitors. Functionality. Modularity. Is it designed in a way where you can make changes in a local part of the code and you don't have to make changes across the code in order to affect a simple change in the functionality? There is one big one which definitely, especially in the `90s, was like the big thing in computers.

هناك بعض التكاليف التي تدخل في الحسبان عند البرمجة مثل وقت المبرمج. إذاً فوقت المبرمج قد يكون شيئاً يؤخذ بالحسبان. الاستقرار. قوة البرنامج. هل ينهار في كل الوقت؟ وماذا أيضا؟ هيا. لدينا مجموعة من المهندسين هنا. هناك الكثير من الأشياء. ماذا عن الميزات؟ يمكن أن تكون الميزات ذات أهمية أكبر. وجود مجموعة من الميزات أوسع من مجموعة ميزات منافسيك. الوظيفية. التجزئة بالوحدات. هل تم التصميم بطريقة بحيث يمكنك إجراء تغييرات في جزء من الرماز المحلي دون أن تضطر لإجراء تغييرات أكبر عبر الرماز الكلي من أجل تغيير بسيط في الوظيفة؟ هناك شيء كبير شيء بالتأكيد ، لا سيما في التسعينيات، كان "الشيء الكبير" بالنسبة للحواسيب.

The big thing. Well, security actually. Good. I don't even have that one down. Security is excellent. That's actually been more in the 2000. Security has been far more important often than performance. Scalability has been important, although scalability, in some sense, is performance related. But, yes, scalability is good. What was the big breakthrough and why do people use Macintosh rather than Windows, those people who are of that religion?

"الشيء الكبير". حسنا ، إنه في الواقع الأمن. جيد. لم أعلم أن هذه المعلومة مسجلة لديكم. الأمن ممتاز. وكان هذا بشكل أكبر في عام 2000. لقد كان للأمن في كثير من الأحيان أهمية أكبر بكثير من الأداء. إن قابلية التدرج ذات أهمية، على الرغم من أنها، ذات صلة بشكل أو بآخر بالأداء. ولكن ، نعم ، فقابلية التدرج جيدة. فما كان التفشي الكبير ولماذا يستخدم الناس ماكنتوش بدلا من ويندوز، هؤلاء الناس الذين هم من ذلك الدين؟

User-friendliness. Wow. If you look at the number of cycles of computers that went into user-friendliness in the `90s, it grew from almost nothing to where it's now the vast part of the computation goes into user-friendly. So, all those things are more important than performance. This is a course on performance. Then you can say OK, well, why do we bother and why study algorithms and performance if it's at the bottom of the heap? Almost always people would rather have these other things than performance. You go off and you say to somebody, would I rather have performance or more user-friendliness?

إنه سهولة الاستخدام. واو!. اذا نظرتم الى عدد دورات أجهزة الحواسيب التي كان لها علاقة بسهولة الاستخدام في التسعينيات ، فإنها نمت من لا شيء تقريبا الى أن أصبحت الآن الجزء الأعظم من الحوسبة يتعلق بسهولة الاستخدام. لذا ، فكل هذه الأمور أكثر أهمية من الأداء. وهذا المقرر هو بطبيعة الحال عن الأداء. يمكنك أن تقول الآن: حسنا ، لماذا نتكبد عناء دراسة الخوارزميات والأداء إذا كانا في أسفل الكومة؟ تقريبا الناس دائما يفضلون الأمور الأخرى على الأداء . أنت تنفجر وتقول لشخص ما ، هل أفضّل أن أحصل على أداء جيد أو سهولة في الاستخدام؟!

It's almost always more important than performance. Why do we care then? Yeah? That wasn't user-friendly. Sometimes performance is correlated with user-friendliness, absolutely. Nothing is more frustrating than sitting there waiting, right? So, that's a good reason. What are some other reasons why? Sometimes they have real-time constraints so they don't actually work unless they perform adequately. Yeah? Hard to get, well, we don't usually quantify user-friendliness so I'm not sure, but I understand what you're saying. He said we don't get exponential performance improvements in user-friendliness.

إنها تقريباً دائما ذات أهمية أكبر من الأداء. لماذا نهتم بالأداء إذاً؟ هاه؟ لم يكن ذلك سهل الاستعمال. أحيانا يرتبط الأداء بسهولة الاستخدام ، بالتأكيد. ليس هناك ما هو أكثر احباطا من الجلوس والانتظار، أليس كذلك؟ إذاً هذا سببٌ وجيهٌ. ما هي بعض الأسباب الأخرى، لماذا؟ في بعض الأحيان لديهم قيود الوقت الحقيقي، بحيث لا يمكنهم العمل دون الأداء بشكل كاف. نعم؟ من الصعب الحصول عليها ، حسنا ، نحن لا نقيس عادة سهولة الاستخدام لذلك أنا غير متأكد، ولكنني أفهم ما تقول. لقد قال أننا لا نحصل على تحسينات في الأداء أسياً في سهولة الاستخدام.

We often don't get that in performance either, by the way. [LAUGHTER] Sometimes we do, but that's good. There are several reasons that I think are important. Once is that often performance measures the line between the feasible and the infeasible. We have heard some of these things. For example, when there are real-time requirements, if it's not fast enough it's simply not functional. Or, if it uses too much memory it's simply not going to work for you. And, as a consequence, what you find is algorithms are on the cutting edge of entrepreneurship. If you're talking about just re-implementing stuff that people did ten years ago, performance isn't that important at some level. But, if you're talking about doing stuff that nobody has done before, one of the reasons often that they haven't done it is because it's too time-consuming.

وعلى أية حال، نحن غالبا لا نحصل على هذا في الأداء أيضاً. [ضحك] في بعض الأحيان نحصل عليه، ولكن هذا جيد. هناك العديد من الأسباب التي أعتقد أنها مهمة. فالأداء في كثير من الأحيان يحدد الخط الفاصل بين الممكن وغير قابل للتطبيق. لقد استمعنا إلى بعض من هذه الأمور. على سبيل المثال، عندما تكون هنالك احتياجات آنية، وإذا لم يكن الأداء بالسرعة الكافية فإنها ببساطة غير عملية. أو، إذا كان لدينا استخدام كبير للذاكرة فإنها ببساطة لن تعمل بالنسبة لك. وكنتيجة لذلك ، فإن الخوارزميات تكون في طليعة المشاريع. إذا كنت تتحدث عن مجرد إعادة تنفيذ الاشياء التي قام بها الناس قبل عشر سنوات، فإن الأداء ليس مهماً إلى هذه الدرجة على مستوى ما. ولكن ، إذا كنت تتحدث عن القيام بأشياء لم يقم بها أحد من قبل فإن واحداً من الأسباب التي جعلتهم لا يقومون بها أنها تستغرق وقتا طويلا.

Things don't scale and so forth. So, that's one reason, is the feasible versus infeasible. Another thing is that algorithms give you a language for talking about program behavior, and that turns out to be a language that has been pervasive through computer science, is that the theoretical language is what gets adopted by all the practitioners because it's a clean way of thinking about things. A good way I think about performance, and the reason it's on the bottom of the heap, is sort of like performance is like money, it's like currency. You say what good does a stack of hundred dollar bills do for you? Would you rather have food or water or shelter or whatever? And you're willing to pay those hundred dollar bills, if you have hundred dollar bills, for that commodity.

أشياء لا تتدرج وهكذا. إذاً هذا سبب. الممكن مقابل غير القابل للتطبيق. شيء آخر هو أن الخوارزميات تعطيك لغة للحديث عن سلوك البرنامج، والتي يتبين أنها قد انتشرت عبر علم الحاسوب، وأن اللغة النظرية هي ما يتبناه الممارسون لأنها وسيلة نظيفة للتفكير في الأشياء. هناك طريقة جيدة أفكر من خلالها في الأداء، وسبب كونها في أسفل الكومة، وهو أن الأداء نوعاً ما مثل المال ، مثل العملة. هل أقول لكم ما تنفعك كومة من أوراق المئة دولار؟ هل تفضل الحصول على طعام أو ماء أو مأوى أو أيِ كان؟ وأنت على استعداد لدفع أوراق المئة دولار هذه، إذا كان لديك أوراق من فئة المئة دولار، لقاء تلك السلع الأساسية.

Even though water is far more important to your living. Well, similarly, performance is what you use to pay for user-friendliness. It's what you pay for security. And you hear people say, for example, that I want greater functionality, so people will program in Java, even though it's much slower than C, because they'll say it costs me maybe a factor of three or something in performance to program in Java.

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

But Java is worth it because it's got all these object-oriented features and so forth, exception mechanisms and so on. And so people are willing to pay a factor of three in performance. So, that's why you want performance because you can use it to pay for these other things that you want. And that's why, in some sense, it's on the bottom of the heap, because it's the universal thing that you quantify.

لكن لغة جافا تستحق ذلك نظراً لامتلاكها كل ميزات البرمجة الغرضية التوجه وهكذا، آليات استثناء وهلم جرا. وبالتالي فإن الناس على استعداد لدفع عامل ثلاثة أضعاف في الأداء. لهذا السبب تحتاج الأداء لأنه يمكنك استخدامه لدفع ثمن الأشياء الأخرى التي تريد. ولهذا السبب، بمعنى ما، كان الأداء في الجزء السفلي من الكومة، لأنه هو الشيء العالمي الذي تكممه..

Do you want to spend a factor of two on this or spend a factor of three on security, et cetera? And, in addition, the lessons generalize to other resource measures like communication, like memory and so forth. And the last reason we study algorithm performance is it's tons of fun. Speed is always fun, right? Why do people drive fast cars, race horses, whatever? Rockets, et cetera, why do we do that? Because speed is fun. Ski. Who likes to ski? I love to ski. I like going fast on those skis. It's fun. Hockey, fast sports, right? We all like the fast sports. Not all of us, I mean. Some people say he's not talking to me. OK, let's move on. That's sort of a little bit of a notion as to why we study this, is that it does, in some sense, form a common basis for all these other things we care about.

هل تريد أن تنفق ضعفين على هذا أو ثلاثة أضعاف على الأمن، الخ؟ وبالإضافة إلى ذلك، فإن الدروس تعمم لتدابير الموارد الأخرى مثل الاتصالات، مثل الذاكرة وهكذا. والسبب الأخير الذي ندرس من أجله أداء الخوارزمية هو أطنان المرح! فالسرعة ممتعة دوماً، أليس كذلك؟ لماذا يقود الناس السيارات بسرعة، سباق الخيول ، أيا كان؟ الصواريخ ، وهلم جرا ، لماذا نفعل كل ذلك؟ لأن السرعة متعة. التزلج. من يحب التزلج؟ أنا أحب التزلج على الجليد. وأحب الانطلاق بسرعة على هذه الزلاجات. إنها متعة. الهوكي، الرياضات السريعة، أليس كذلك؟ كلنا يحب الرياضات السريعة. طبعاً ليس كل واحد منا.أعني، البعض يقول انه لا يتحدث معي. حسنا، لنتابع. لقد كان كل هذا نوعاً ما ملاحظة حول سبب دراستنا لهذا المقرر، وهو أنه، بمعنى ما، يشكل أساسا مشتركا لجميع الأشياء الأخرى التي نهتم بها.

 تحليل الخوارزميات: الفرز Sorting

And so we want to understand how can we generate money for ourselves in computation? We're going to start out with a very simple problem. It's one of the oldest problems that has been studied in algorithms, is the problem of sorting. We're going to actually study this for several lectures because sorting contains many algorithmic techniques. The sorting problem is the following. We have a sequence a_1, a_2 up to a_n of numbers as input. And our output is a permutation of those numbers.

إذاً نحن نريد أن نفهم كيف نولد لأنفسنا مالاً في الحوسبة؟ سنبدأ بمشكلة بسيطة جداً إنها واحدة من أقدم المشاكل التي تم دراستها في عالم الخوارزميات، ألا وهي مشكلة الفرز. سنقوم حقيقة بدراسة الفرز على عدة محاضرات لأن الفرز يتضمن تقنيات خوارزمية عديدة. إن مسألة الفرز هي كالتالي: لدينا سلسلة a_1,a_2 ... الى a_n من الأعداد كدخل، يكون الخرج هو تباديل لتلك الأرقام.

 الفرز بالإدراج Insertion sort

A permutation is a rearrangement of the numbers. Every number appears exactly once in the rearrangement such that, I sometimes use a dollar sign to mean "such that," a_1 is less than or equal to a_2 prime. Such that they are monotonically increasing in size. Take a bunch of numbers, put them in order. Here's an algorithm to do it. It's called insertion sort. And we will write this algorithm in what we call pseudocode. It's sort of a programming language, except it's got English in there often. And it's just a shorthand for writing for being precise.

التبديل هو إعادة ترتيب للأرقام. كل عدد يظهر مرة واحدة فقط في إعادة الترتيب بحيث يكون - أنا أستخدم أحيانا علامة الدولار للدلالة على تعبير "بحيث يكون" - a_1 أقل من أو يساوي a_2 الرئيسي. بحيث تتزايد هذه الأعداد في الحجم بصورة متناغمة. خذ مجموعة من الأرقام ، وضعها بالترتيب . هاك خوارزمية لتفعل ذلك. و هي تدعى الفرز بالإدراج. وسوف نكتب هذه الخوارزمية في ما نسميه بلغة شبه الرماز. و هي نوعاً ما لغة برمجة، إلا إنها تستخدم اللغة الإنجليزية في كثير من الأحيان. و حتى نكون دقيقين هي مجرد اختزال للكتابة .

So this sorts A from 1 to n. And here is the code for it. This is what we call pseudocode. And if you don't understand the pseudocode then you should ask questions about any of the notations. You will start to get used to it as we go on. One thing is that in the pseudocode we use indentation, where in most languages they have some kind of begin-end delimiters like curly braces or something in Java or C, for example.

إذاً هذه الخوارزمية تفرز A من 1 إلى n. وهنا رماز لهذه الخوارزمية. هذا هو ما نسميه شبه الرماز. وإذا كنت لا تفهم شبه الرماز فيجب عليك أن تسأل أسئلة حول أي من الرموز. ستبدأ بالاعتياد عليه بينما نستمر. أحد الأشياء هو أنه في شبه الرماز نستخدم المسافة البادئة، بينما في معظم اللغات هناك نوع من المحددات التي توضح البداية والنهاية كالأقواس المجعدة أو شيء من هذا القبيل في جافا أو C ، على سبيل المثال.

We just use indentation. The whole idea of the pseudocode is to try to get the algorithms as short as possible while still understanding what the individual steps are. In practice, there actually have been languages that use indentation as a means of showing the nesting of things. It's generally a bad idea, because if things go over one page to another, for example, you cannot tell what level of nesting it is.

نحن نستخدم المسافة البادئة فقط. الفكرة الأساسية من شبه الرماز هو محاولة جعل الخوارزميات أقصر ما يمكن مع المحافظة على فهم كل خطوة من الخوارزمية. في الواقع هناك لغات تستخدم المسافة البادئة لإظهار التداخل بين الأشياء. إنها فكرة سيئة بشكل عام لأن الأمر إذا تجاوز إحدى الصفحات لأخرى, على سبيل المثال, لا يمكنك تحديد في أي مستوى من التداخل أنت.

Whereas, with explicit braces it's much easier to tell. So, there are reasons why this is a bad notation if you were doing software engineering. But it's a good one for us because it just keeps things short and makes fewer things to write down. So, this is insertion sort. Let's try to figure out a little bit what this does. It basically takes an array A and at any point the thing to understand is, we're setting basically, we're running the outer loop from j is 2 to n, and the inner loop that starts at j minus 1 and then goes down until it's zero.

بينما مع الأقواس الواضحة يكون ذلك أسهل بكثير. لذا، توجد أسباب تجعل هذا الترميز سيئاً إذا كنت تعمل في هندسة البرمجيات. لكنها فكرة جيدة بالنسبة لنا من أجل إبقاء الأشياء قصيرة وكتابة أمور أقل. إذا هذا هو الفرز بالإقحام. دعونا نحاول أن نفهم قليلا ما الذي يفعله هذا. إنه بالأساس يأخذ مصفوفة A،وفي أي نقطة الشيء الذي عليك فهمه،إننا نضع بالأساس، نحن نشغل الحلقة الخارجية من j بقيمة 2 إلى n، والحلقة الداخلية التي تبدأ من j-1 ومن ثم تنخفض حتى تصل قيمتها إلى الصفر.

Basically, if we look at any point in the algorithm, we essentially are looking at some element here j. A of j, the jth element. And what we do essentially is we pull a value out here that we call the key. And at this point the important thing to understand, and we'll talk more about this in recitation on Friday, is that there is an invariant that is being maintained by this loop each time through.

بشكل أساسي، وإذا نظرنا إلى أي مرحلة في الخوارزمية، فإننا بالأساس ننظر إلى عنصر ما j، فـA[j] هو العنصر رقم j من المصفوفة. وما نفعله بالأساس هو أننا نسحب قيمة من هنا ونسميها "المفتاح". والشيء الذي يجب فهمه عند هذه النقطة، والذي سنتحدث عنه بشكل أكبر في الجلسات المصغرة يوم الجمعة، هو أنه يوجد شيء ثابت تحتفظ به الحلقة في كل دورة من دوراتها.

And the invariant is that this part of the array is sorted. And the goal each time through the loop is to increase, is to add one to the length of the things that are sorted. And the way we do that is we pull out the key and we just copy values up like this. And keep copying up until we find the place where this key goes, and then we insert it in that place. And that's why it's called insertion sort. We just sort of move the things, copy the things up until we find where it goes, and then we put it into place. And now we have it from A from one to j is sorted, and now we can work on j plus one.

والشيء الثابت هو أن هذا الجزء من المصفوفة قد رتب. والهدف في كل مرة خلال الحلقة هو زيادة، هو إضافة واحد إلى طول الأشياء التي تم ترتيبها. والطريقة التي نفعل بها ذلك هي أننا نسحب المفتاح وفقط ننسخ القيم بهذا الشكل. ونستمر بالنسخ حتى نجد المكان الذي يجب أن يوضع فيه هذا المفتاح ، ومن ثم نقوم بإدراجه في ذاك المكان. ولهذا تسمى الطريقة الفرز بالإدراج. فنحن فقط نوعاً ما نحرك الأشياء، وننسخ الأشياء حتى نجد مكانها، ومن ثم نضعها في مكانها. والآن أصبحت لدينا من A أصبحت العناصر من 1 إلى j مرتبة، والآن يمكننا العمل على j+1

Let's give an example of that. Imagine we are doing 8, 2, 4, 9, 3, 6. We start out with j equals 2. And we figure out that we want to insert it there. Now we have 2, 8, 4, 9, 3, 6. Then we look at the four and say oh, well, that goes over here. We get 2, 4, 8, 9, 3, 6 after the second iteration of the outer loop. Then we look at 9 and discover immediately it just goes right there. Very little work to do on that step. So, we have exactly the same output after that iteration. Then we look at the 3 and that's going to be inserted over there.

دعونا نعطي مثالا على ذلك. تخيل أننا نريد فرز الأرقام التالية 8 ، 2 ، 4 ، 9 ، 3 ، 6. نبدأ مع j يساوي 2. ونعرف أننا نريد أن أن ندخله هناك. الآن لدينا 2 ، 8 ، 4 ، 9 ، 3 ، 6. ننظر إلى الرقم 4 ونقول: أوه، حسناً، مكانها هنا. نحصل على 2 ، 4 ، 8 ، 9 ، 3 ، 6 بعد تكرار هذه العمليات مرة ثانية عن طريق الانتقال إلى الرقم الذي بعده في الحلقة الخارجي. ننظر إلى 9 نكتشف فوراً أنها صحيحة في مكانها. عمل قليل جداً يجب القيام به على تلك الخطوة. لذا ، لدينا تماماً نفس الخرج بعد ذلك التكرار. ثم ننظر إلى 3، وسندرجها هناك.

2, 3, 4, 8, 9, 6. And finally we look at the 6 and that goes in there. 2, 3, 4, 6, 8, 9. And at that point we are done. Question? The array initially starts at one, yes. A[1...n], OK? So, this is the insertion sort algorithm. And it's the first algorithm that we're going to analyze. And we're going to pull out some tools that we have from our math background to help to analyze it. First of all, let's take a look at the issue of running time.

وأخيرا ننظر إلى 6 فنجدها تدخل هناك. 2 ، 3 ، 4 ، 6 ، 8 ، 9. وعند هذه النقطة نكون قد انتهينا. سؤال. المصفوفة تبدأ عند الواحد. نعم. [1... n] ، حسناً؟ فهذه هي خوارزمية الفرز بالإدراج. وهي الخوارزمية الأولى التي نحن بصدد تحليلها. وسنستخدم شيئاً من خلفيتنا الرياضية لمساعدتنا على تحليلها. بادئ ذي بدء ، دعونا نلقي نظرة على مسألة وقت التشغيل.

The running time depends, of this algorithm depends on a lot of things. One thing it depends on is the input itself. For example, if the input is already sorted -- -- then insertion sort has very little work to do. Because every time through it's going to be like this case. It doesn't have to shuffle too many guys over because they're already in place. Whereas, in some sense, what's the worst case for insertion sort? If it is reverse sorted then it's going to have to do a lot of work because it's going to have to shuffle everything over on each step of the outer loop.

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

In addition to the actual input it depends, of course, on the input size. Here, for example, we did six elements. It's going to take longer if we, for example, do six times ten to the ninth elements. If we were sorting a lot more stuff, it's going to take us a lot longer. Typically, the way we handle that is we are going to parameterize things in the input size. We are going to talk about time as a function of the size of things that we are sorting so we can look at what is the behavior of that. And the last thing I want to say about running time is generally we want upper bonds on the running time.

وبالإضافة إلى اعتمادها على الإدخال الفعلي، بالطبع، فهي تعتمد على حجم المدخلات. هنا، على سبيل المثال ، رتبنا ستة عناصر. سوف نستغرق وقتا أطول،لو على سبيل المثال ،رتبنا 6 ضرب 10 أس 9 عنصراً. إذا كنا نقوم بفرز اشياء أكثر، فإنها ستستغرق وقتا أطول بكثير. عادة، نتعامل مع هذا بأن نرمز الأمور بدلالة حجم المدخلات. ونحن بصدد الحديث عن الوقت كتابع لحجم الأشياء التي نحن نرتبها حتى نتمكن من النظر إلى سلوك الخوارزمية. شيء آخر أريد أن أقوله حول وقت التشغيل وهو أننا عموما نهتم بالحدود العليا لوقت التشغيل اللازم.

We want to know that the time is no more than a certain amount. And the reason is because that represents a guarantee to the user. If I say it's not going to run, for example, if I tell you here's a program and it won't run more than three seconds, that gives you real information about how you could use it, for example, in a real-time setting. Whereas, if I said here's a program and it goes at least three seconds, you don't know if it's going to go for three years. It doesn't give you that much guarantee if you are a user of it. Generally we want upper bonds because it represents a guarantee to the user.

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

There are different kinds of analyses that people do. The one we're mostly going to focus on is what's called worst-case analysis. And this is what we do usually where we define T of n to be the maximum time on any input of size n. So, it's the maximum input, the maximum it could possibly cost us on an input of size n. What that does is, if you look at the fact that sometimes the inputs are better and sometimes they're worse, we're looking at the worst case of those because that's the way we're going to be able to make a guarantee.

هناك أنواع مختلفة من التحليلات التي يقوم بها الناس. التحليل الذي سنركز عليه بشكل أساسي هو ما يسمى بتحليل أسوأ الحالات. وهذا هو ما نقوم به عادة حيث نعرف T من n على أنه الحد الأعظمي للوقت على أي إدخال من الحجم n. إذاً، فإنه الإدخال الأعظمي ، والحد الأعظمي يمكن أن نتكلفه من أجل إدخال بحجم n. الذي يحصل هو أنه، اذا نظرت الى حقيقة أنه في بعض الأحيان تكون المدخلات أفضل وفي أحيان أخرى تكون أسوأ. نحن نبحث في أسوأ هذه الحالات لأن هذه الطريقة هي التي تحقق لنا ضماناً.

It always does something rather than just sometimes does something. So, we're looking at the maximum. Notice that if I didn't have maximum then T(n) in some sense is a relation, not a function, because the time on an input of size n depends on which input of size n. I could have many different times, but by putting the maximum at it, it turns that relation into a function because there's only one maximum time that it will take.

أن تعلم أنها تقوم دوماً بشيء ما أفضل من أن تعلم أنها أحياناً تقوم بشيء ما. لهذا، نحن نبحث في الحد الأقصى. لاحظ أنه إذا لم يكن لدي الحد الأقصى، فسيكون T(n) بمعنى ما علاقة، وليس تابعاً، وذلك لأن الوقت اللازم لدخل من الحجم n يعتمد على أي نوع من المدخلات من الحجم n. يمكن أن تكون لدي أوقات مختلفة كثيرة، ولكن عندما أضع الوقت الأعظمي عليها، فإن تلك العلاقة تتحول إلى تابع لأنه يوجد فقط وقت أعظمي واحد يمكن أن تستغرقه [الخوارزمية].

Sometimes we will talk about average case. Sometimes we will do this. Here T of n is then the expected time over all inputs of size n. It's the expected time. Now, if I talk about expected time, what else do I need to say here? What does that mean, expected time? I'm sorry. Raise your hand. Expected inputs. What does that mean, expected inputs? I need more math. What do I need by expected time here, math? You have to take the time of every input and then average them, OK. That's kind of what we mean by expected time. Good. Not quite. I mean, what you say is completely correct, except is not quite enough.

أحيانا سوف نتحدث عن حالة وسطية. أحيانا سنقوم بهذا. هنا T من أجل n سيكون الوقت المتوقع من أجل كل أنواع الدخل من الحجم n. إنها الوقت المتوبع. الآن، إذا تحدثت عن الوقت المتوقع، ما الذي علي أن أقوله أيضاً؟ ما الذي يعنيه الوقت المتوقع؟ أنا آسف. ارفعوا أيديكم. المدخلات المتوقعة. ما الذي تعنيه المدخلات المتوقعة؟ أحتاج الى مزيد من الرياضيات. ما الذي أحتاجه من الرياضيات للتعبير عن الوقت المتوقع هنا؟ عليك ان تأخذ الوقت اللازم لكل دخل، ثم تحسب القيمة المتوسطة لها، حسناً. هذا نوعاً ما، ما نعنيه بالوقت المتوقع. جيد. ليس تماما. أعني، ما تقوله صحيح تماما،إلا أنه غير كاف.

Yeah? It's the time of every input times the probability that it will be that input. It's a way of taking a weighted average, exactly right. How do I know what the probability of every input is? How do I know what the probability a particular input occurs is in a given situation? I don't. I have to make an assumption. What's that assumption called? What kind of assumption do I have to meet?

نعم؟إنه الوقت اللازم لكل دخل مضروباً باحتمال أن يكون هو الإدخال وسيلة لأخذ المتوسط المرجح ، صحيح تماما. كيف أعرف ما احتمال كل إدخال؟ كيف أعرف ما احتمال أن يحصل مدخل معين؟ في وضع معين. أنا لا أعرف .عليّ بناء الافتراض . ماذا يدعى هذا الافتراض ؟ ما نوع هذا الافتراض لا بد لي من أن أجده ؟

I need an assumption of the statistical distribution of inputs. Otherwise, expected time doesn't mean anything because I don't know what the probability of something is. In order to do probability, you need some assumptions and you've got to state those assumptions clearly. One of the most common assumptions is that all inputs are equally likely. That's called the uniform distribution. Every input of size n is equally likely, that kind of thing. But there are other ways that you could make that assumption, and they may not all be true. This is much more complicated, as you can see. Fortunately, all of you have a strong probability background. And so we will not have any trouble addressing these probabilistic issues of dealing with expectations and such.

أحتاج إلى توزيع المدخلات الإحصائيّة على كلّ الفرضيات وإلا، فالوقت المتوقع لن يعني أيّ شيء, لأنّني لا أعرف ما هو احتمال وقوع ذلك الشيء .من أجل حساب الاحتمال, فإنّك بحاجة إلى بعض الفرضيات, وعليك أن تحدد تلك الفرضيات بشكل واضح. واحدة من الفرضيات الأكثر شيوعاً هو أنّ جميع المدخلات متساوية (احتمالياً) على الأرجح. هذا ما يسمى التوزيع المنتظم. كل المدخلات الممكنة من الحجم n لها درجة الوقوع نفسها. ولكن هنالك طرق أخرى تمكنك من بناء فرضيتك , ولكن قد لا تكون دوماً صحيحة.فهو كما ترون أكثر تعقيداً بكثير.لحسن الحظ، كلكم لديه خلفية قوية عن موضوع الاحتمالات الرياضيّة. وهكذا لن يكون لدينا أي مشكلة في معالجة هذه القضايا الاحتمالية في التعامل مع مثل هذه التوقعات.

If you don't, time to go and say gee, maybe I should take that Probability class that is a prerequisite for this class. The last one I am going to mention is best-case analysis. And this I claim is bogus. Bogus. No good. Why is best-case analysis bogus? Yeah? The best-case probably doesn't ever happen. Actually, it's interesting because for the sorting problem, the most common things that get sorted are things that are already sorted interestingly, or at least almost sorted. For example, one of the most common things that are sorted is check numbers by banks. They tend to come in, in the same order that they are written.

إذا لم تكن لديك تلك الخلفية، فعليك أن تذهب وتقول لنفسك ربما ينبغي علي أن أدخل صف الاحتمالات الذي هو شرط أساسي لهذه المقرر. آخر شيء سأذكره هو تحليل أفضل حالة. وهذا الشيء أنا أدعي أنه زائف . كاذب و ليس جيداً. لماذا تحليل أفضل حالة هو تحليل وهمي؟ نعم؟ لأن أفضل حالة ربما لا تقع على الإطلاق. في الواقع، قد يكون مثيراً للاهتمام فمن أجل مسألة الفرز, فأكثر الأشياء التي ترتب هي الأشياء المرتبة مسبقاً أو لنقل شبه المرتبة.فعلى سبيل المثال ، فواحدة من أكثر الأمور الأكثر شيوعا التي يتم فرزها هي أرقام الشيكات في البنوك. فهي تميل إلى أن تأتي بالترتيب نفسه الذي أدخلت فيه.

They're sorting things that are almost always sorted. I mean, it's good. When upper bond, not lower bound? Yeah, you want to make a guarantee. And so why is this not a guarantee? You're onto something there, but we need a little more precision here. How can I cheat? Yeah? Yeah, you can cheat. You cheat. You take any slow algorithm that you want and just check for some particular input, and if it's that input, then you say immediately yeah, OK, here is the answer. And then it's got a good best-case.

انهم يفرزون الأشياء التي تمَّ فرزها تقريباً . أعني ، إنها جيدة. عندما تكون الكفالة عليا ، وليس الحد الأدنى ؟ نعم ، كنت تريد أن أعمل لك ضماناً. و لهذا السبب إنه ليس ضماناً ؟ كنت على شيء هناك ، ولكن نحن بحاجة إلى دقة أكثر قليلا هنا. كيف يمكنني الغش؟ نعم؟ نعم ، يمكنك الغش. لك الغش. تأخذ أي خوارزمية بطيئة تريدها وتدقق فقط بعض المدخلات الخاصة، وإذا كان هذا المدخل ، ثم تقول على الفور نعم ، حسنا ، هذا هو الجواب. ثم هذه هي أجود أفضل حالة .

But I didn't tell you anything about the vast majority of what is going on. So, you can cheat with a slow algorithm that works fast on some input. It doesn't really do much for you so we normally don't worry about that. Let's see. What is insertion sorts worst-case time? Now we get into some sort of funny issues. First of all, it sort of depends on the computer you're running on. Whose computer, right? Is it a big supercomputer or is it your wristwatch? They have different computational abilities.

لكنني لم أقل لكم شيئاً عن الغالبية العظمى مما يجري حالياً . لذلك ، يمكنك الغش مع الخوارزمية البطيئة التي تعمل بسرعة على بعض المدخلات. إنها في الواقع لا تقدم لك الكثير لذلك نحن عادة لا نقلق بشأن ذلك. دعونا نرى. ما هو الوقت اللازم لمعالجة أسوأ حالة في الفرز بالإدراج ؟ نحن الآن ندخل في نوعٍ مضحكٍ من القضايا. بادئ ذي بدء ، إنه نوع من الأنواع التي تعتمد على جهاز الحاسوب الذي تعمل عليه ، أليس كذلك؟ هل هو الحاسوب العملاق الكبير ام أنه ساعة اليد الخاصة بك؟ لديهم قدرات حسابية مختلفة.

And when we compare algorithms, we compare them typically for relative speed. This is if you compared two algorithms on the same machine. You could argue, well, it doesn't really matter what the machine is because I will just look at their relative speed. But, of course, I may also be interested in absolute speed. Is one algorithm actually better no matter what machine it's run on? And so this kind of gets sort of confusing as to how I can talk about the worst-case time of an algorithm of a piece of software when I am not talking about the hardware because, clearly, if I had run on a faster machine, my algorithms are going to go faster. So, this is where you get the big idea of algorithms.

وعندما نقارن الخوارزميات، فإننا غالباً ما نقارنها من أجل سرعة نسبية. عندما تقارن خوارزميتين على الجهاز نفسه. ربما تقول، حسنا، لا يهمني حقاً ما هو الجهاز لأنني سأنظر فقط إلى سرعتيهما النسبيتين. ولكن، بالطبع، قد أكون مهتماً أيضا أنا في سرعة مطلقة. هل توجد في الواقع خوارزمية أفضل مهما كانت الآلة التي تعمل عليها؟ وهذا ربما يقودنا إلى نوع من الخلط، إذ كيف يمكنني الحديث عن وقت أسوأ حالة لخوارزمية قطعة من برنامج عندما لا أتحدث عن العتاد.. لأنه من الواضح أنه إذا كنت أعمل على جهاز أسرع، فإن خوارزمياتي ستنفذ بشكل أسرع. بذلك ، هنا نصف إلى الفكرة الكبيرة للخوارزميات.

Which is why algorithm is such a huge field, why it spawns companies like Google, like Akamai, like Amazon. Why algorithmic analysis, throughout the history of computing, has been such a huge success, is our ability to master and to be able to take what is apparently a really messy, complicated situation and reduce it to being able to do some mathematics. And that idea is called asymptotic analysis.

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

And the basic idea of asymptotic analysis is to ignore machine-dependent constants -- -- and, instead of the actual running time, look at the growth of the running time. So, we don't look at the actual running time. We look at the growth. Let's see what we mean by that. This is a huge idea. It's not a hard idea, otherwise I wouldn't be able to teach it in the first lecture, but it's a huge idea. We are going to spend a couple of lectures understanding the implications of that and will basically be doing it throughout the term.

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

And if you go on to be practicing engineers, you will be doing it all the time. In order to do that, we adopt some notations that are going to help us. In particular, we will adopt asymptotic notation. Most of you have seen some kind of asymptotic notation. Maybe a few of you haven't, but mostly you should have seen a little bit. The one we're going to be using in this class predominantly is theta notation.

وإذا كنت تود الاستمرار لتكون مهندساً ممارساً فسوف تقوم بذلك طوال الوقت. ولكي نفعل ذلك، فإننا سنعتمد بعض الترميزات التي ستساعدنا. وعلى وجه الخصوص، سنتبنى الترميز المقارب. لقد شهد معظمكم نوعا ما من الترميز مقارب. ربما عدد قليل لم يشهدوا، ولكن على الغالب لا بد أنك قد رأيت قليلا. الذي سنستخدمه في هذا الصف هو ترميز ثيتا.

And theta notation is pretty easy notation to master because all you do is, from a formula, just drop low order terms and ignore leading constants. For example, if I have a formula like 3n^3 = 90n^2 - 5n + 6046, I say, well, what low-order terms do I drop? Well, n^3 is a bigger term n^2 than. I am going to drop all these terms and ignore the leading constant, so I say that's Theta(n^3). That's pretty easy. So, that's theta notation. Now, this is an engineering way of manipulating theta notation. There is actually a mathematical definition for this, which we are going to talk about next time, which is a definition in terms of sets of functions. And, you are going to be responsible, this is both a math and a computer science engineering class.

من السهل جداً إتقان ترميز ثيتا لأن كل ما عليك فعله هو ، بدءاً من صيغة ما، فقط أسقط العبارات المنخفضة المستوى وتجاهل الثوابت الرئيسية. على سبيل المثال ، إذا كان لدي صيغة مثل 3N ^ 3 ^ 2 = 90n -- 5N 6046 ، ما هي العبارات المنخفضة المستوى التي يمكنني أن أسقطها؟ حسنا، إن 3^n حد أكبر من 2^n. فسأقوم بإسقاط جميع هذه الحدود وتجاهل الثابت الرئيسي ، لذلك أقول هذه ثيتا(n^3). هذا سهل جداً. فهذا هو ترميز ثيتا. الآن ، توجد وسيلة هندسية للتعامل مع ترميز ثيتا.يوجد في الحقيقة تعريف رياضي له، والتي سنتحدث عنه في المرة القادمة، وهو تعريف يعتمد على مجموعات من التوابع. وسوف تكونون مسؤولين، فهذا درس في كل من الرياضيات وهندسة علم الحاسوب.

Throughout the course you are going to be responsible both for mathematical rigor as if it were a math course and engineering commonsense because it's an engineering course. We are going to be doing both. This is the engineering way of understanding what you do, so you're responsible for being able to do these manipulations. You're also going to be responsible for understanding the mathematical definition of theta notion and of its related O notation and omega notation.

طوال المقرر ستكون مسؤولا عن كل من الصرامة الرياضية كما لو كنت في مقرر رياضيات وبديهيات الهندسة لأنه مقرر هندسة. نحن بصدد القيام به على حد سواء. هذه طريقة هندسية لفهم ما تقوم به، لذلك ستكون مسؤولاً عن القدرة على القيام بهذه المهارات. وستكون مسؤولا عن فهم التعريف الرياضي لترميز ثيتا وترميز أوه ذو الصلة، وترميز أوميغا.

If I take a look as n approached infinity, a Theta(n^2) algorithm always beats, eventually, a Theta(n^3) algorithm. As n gets bigger, it doesn't matter what these other terms were if I were describing the absolute precise behavior in terms of a formula. If I had a Theta(n^2) algorithm, it would always be faster for sufficiently large n than a Theta(n^3) algorithm. It wouldn't matter what those low-order terms were. It wouldn't matter what the leading constant was. This one will always be faster.

لو ألقيت نظرة على n باقترابها من اللانهاية ، فإن خوارزمية ثيت (n^2) تغلب، في نهاية المطاف ، خوارزمية ثيتا(n^3). وبازدياد n فلا يهم ما هي هذه الشروط الأخرى إذا كنت أوصف السلوك المطلق الدقيق باستخدام صيغة ما. إذا كان لدي خوارزمية ثيتا(n^2)، فستكون دوماً، من أجل مقدار n كبير بما فيه الكفاية، أسرع من خوارزمية ثيتا(n^3). ولا يهم ما هي تلك الحدود ذات الترتيب المنخفض . ولا يهم ما كان الثابت الرئيسي. ستكون هذه الخوارزمية دوماً أسرع.

Even if you ran the Theta(n^2) algorithm on a slow computer and the Theta(n^3) algorithm on a fast computer. The great thing about asymptotic notation is it satisfies our issue of being able to compare both relative and absolute speed, because we are able to do this no matter what the computer platform. On different platforms we may get different constants here, machine-dependent constants for the actual running time, but if I look at the growth as the size of the input gets larger, the asymptotics generally won't change. For example, I will just draw that as a picture. If I have n on this axis and T(n) on this axis.

وحتى لو قمت بتشغيل خوارزمية ثيتا(n^2) على حاسوب بطيء وخوارزمية ثيتا(n^3) على حاسوب سريع. إن الشيء العظيم في الترميز المقارب هو أن يعطي قضيتنا حقها من التمكن من مقارنة كل من السرعة النسبية والمطلقة، لأننا قادرون على القيام بذلك مهما كانت منصة الحاسوب. قد تحصل على ثوابت مختلفة هنا بالنسبة لمنصات مختلفة، ثوابت تعتمد على آلة لتشغيل، ثوابت من أجل وقت التشغيل الفعلي، لكن إذا ألقيت نظرة على النمو مع ازدياد حجم المدخلات، فإن المقاربات عموما لن تتغير. على سبيل المثال ، أود فقط أن أرسم ذلك كصورة. إذا كان لدي n على هذا المحور و T(n) على هذا المحور.

This may be, for example, a Theta(n^3) algorithm and this may be a Theta(n^2) algorithm. There is always going to be some point n_o where for everything larger the Theta(n^2) algorithm is going to be cheaper than the Theta(n^3) algorithm not matter how much advantage you give it at the beginning in terms of the speed of the computer you are running on. Now, from an engineering point of view, there are some issues we have to deal with because sometimes it could be that that n_o is so large that the computers aren't big enough to run the problem. That's why we, nevertheless, are interested in some of the slower algorithms, because some of the slower algorithms, even though they may not asymptotically be slower, I mean asymptotically they will be slower.

قد تكون هذه، على سبيل المثال، خوارزمية ثيتا(n^3)، وهذا قد تكون هذه خوارزمية ثيتا(n^2). ستكون دوماً هناك نقطة n_o من أجل كل n أكبر منها، ستكون خوارزمية ثيتا(n^2) أرخص من خوارزمية ثيتا(n^3) بغض النظر عن مقدار التفوق الذي تعطيه لها في البداية من حيث سرعة الكمبيوتر الذي تعمل عليه. الآن، من وجهة نظر هندسية، توجد بعض القضايا التي يجب علينا التعامل معها لأنه في بعض الأحيان قد تكون n_o كبيرة جدا بحيث أن أجهزة الحواسيب ليست كبيرة بما يكفي لتشغيل خوارزمية هذه المسألة. هذا هو السبب في أننا، مع ذلك، نبدي اهتماماً ببعض الخوارزميات الأبطأ، وذلك لأن بعض الخوارزميات الأبطأ، على الرغم من أنها قد لا تكون أبطأ مقاربةً،أعني أنها ستكون أنها ستكون أبطأ بالمقاربة.

They may still be faster on reasonable sizes of things. And so we have to both balance our mathematical understanding with our engineering commonsense in order to do good programming. So, just having done analysis of algorithms doesn't automatically make you a good programmer. You also need to learn how to program and use these tools in practice to understand when they are relevant and when they are not relevant. There is a saying.

يمكن أن تبقى أسرع على أحجام معقولة من الأشياء. ولذا يتعين علينا أن نحقق توازناً في كل من فهمنا الرياضي مع المنطقية الهندسة لدينا من أجل القيام ببرمجة جيدة. لذلك ، فإن مجرد وجود تحليل للخوارزميات لا يجعلك تلقائيا مبرمجا جيداً. تحتاج أيضا إلى معرفة كيفية البرمجة واستخدام الأدوات في الواقع لفهم متى تكون مناسبة ومتى لا تكون كذلك. وهناك قول مأثور.

If you want to be a good program, you just program ever day for two years, you will be an excellent programmer. If you want to be a world-class programmer, you can program every day for ten years, or you can program every day for two years and take an algorithms class. Let's get back to what we were doing, which is analyzing insertion sort. We are going to look at the worse-case. Which, as we mentioned before, is when the input is reverse sorted. The biggest element comes first and the smallest last because now every time you do the insertion you've got to shuffle everything over.

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

You can write down the running time by looking at the nesting of loops. What we do is we sum up. What we assume is that every operation, every elemental operation is going to take some constant amount of time. But we don't have to worry about what that constant is because we're going to be doing asymptotic analysis. As I say, the beautify of the method is that it causes all these things that are real distinctions to sort of vanish.

يمكنك كتابة وقت التشغيل من خلال النظر في تداخل الحلقات. ما نقوم به هو أن نلخص. ما نفترضه هو أن كل عملية ، كل عملية عنصرية ستستغرق مقداراً ثابتاً ما من الوقت. ولكن ليس علينا القلق حول ما هو ذلك الثابت لأننا سنقوم بالتحليل المقارب. كما أقول، إن جمال الأسلوب هو الذي يجعل كل هذه الأشياء التي تشكل فوارق حقيقية تتلاشي.

We sort of look at them from 30,000 feet rather than from three millimeters or something. Each of these operations is going to sort of be a basic operation. One way to think about this, in terms of counting operations, is counting memory references. How many times do you actually access some variable? That's another way of sort of thinking about this model. When we do that, well, we're going to go through this loop, j is going from 2 to n, and then we're going to add up the work that we do within the loop. We can sort of write that in math as summation of j equals 2 to n. And then what is the work that is going on in this loop? Well, the work that is going on in this loop varies, but in the worst case how many operations are going on here for each value of j?

نحن نوعاً ما ننظر إليها من 30000 قدم بدلا من ثلاثة ملليمترات أو شيئاً من هذا. كل من هذه العمليات سيكون نوعاً ما عملية أساسية. أحد الطرق الممكنة للنظر للأمر، بالنسبة لعد العمليات، هو عد مرات الرجوع للذاكرة. كم مرة تقوم بالوصول إلى متغير معين؟ هذ هي طريقة أخرى للتفكير في هذا النموذج. عندما نفعل ذلك، حسنا، سندخل خلال هذه الحلقة، j يتغير من 2 إلى n، ثم سنقوم بإضافة العمل الذي نقوم به داخل الحلقة. يمكننا أن نكتب هذا رياضياً كمحصلة j تساوي 2 إلى n. ثم ما هو العمل الذي يجري في هذه الحلقة؟ حسنا ، العمل الذي يجري في هذه الحلقة متفاوت، ولكن في أسوأ الأحوال ما هو عدد العمليات التي تجري هنا من أجل كل قيمة من j؟

For a given value of j, how much work goes on in this loop? Can somebody tell me? Asymptotically. It's j times some constant, so it's theta j. So, there is theta j work going on here because this loop starts out with i being j minus 1, and then it's doing just a constant amount of stuff for each step of the value of i, and i is running from j minus one down to zero. So, we can say that is theta j work that is going on. Do people follow that?

من أجل قيمة معينة لـ j، ماهو مقدار العمل الذي يجري في هذه الحلقة؟ هل يمكن لأي شخص أن يقول لي؟ مقاربياً. انها j مضروبة بثابت ما، إذاً فهي ثيتا(J). لذا ، هناك عمل ثيتا(j) يجري هنا لأن هذه الحلقة تبدأ بـ i آخذة القيمة j-1، ومن ثم تقوم بقدر ثابت من الأشياء من أجل كل قيمة من قيم i، وi يتغير من j-1 إلى الصفر. لذا، يمكننا القول بأن العمل الذي يجري هو ثيتا j. هل أنتم متابعون لهذا؟

OK. And now we have a formula we can evaluate. What is the evaluation? If I want to simplify this formula, what is that equal to? Sorry. In the back there. Yeah. OK. That's just Theta(n^2), good. Because when you're saying is the sum of consecutive numbers, you mean what? What's the mathematic term we have for that so we can communicate? You've got to know these things so you can communicate. It's called what type of sequence? It's actually a series, but that's OK. What type of series is this called? Arithmetic series, good. Wow, we've got some sharp people who can communicate.

حسناً. والآن لدينا صيغة يمكننا استخراج قيمتها. ما هو استخراج القيمة؟ إذا أردت تبسيط هذه الصيغة، فما الذي ستساويه؟ عذرا. في الخلف. هناك. نعم. موافق. إنها مجرد ثيتا (n^2) ، جيد. لأنك عندما تتحدث عن مجموع أعداد متتالية، فما الذي تعنيه؟ ما هو مصطلح الرياضيات الذي لدينا حتى نتمكن من التواصل؟ عليك أن تعرف هذه الأمور حتى تتمكن من التواصل. أي نوع من المتسلسلات تدعى هذه؟ انها فعلا متسلسلة، هذا جيد. ماذا يسمى هذا النوع من المتسلسلات؟ سلسلة حسابية، جيد. واو! لدينا بعض الناس اللامعين الذين يستطيعون التواصل.

This is an arithmetic series. You're basically summing 1 + 2 + 3 + 4, some constants in there, but basically it's 1 + 2 + 3 + 4 + 5 + 6 up to n. That's Theta(n^2). If you don't know this math, there is a chapter in the book, or you could have taken the prerequisite. Erythematic series. People have this vague recollection. Oh, yeah. Good. Now, you have to learn these manipulations. We will talk about a bit next time, but you have to learn your theta manipulations for what works with theta. And you have to be very careful because theta is a weak notation. A strong notation is something like Leibniz notation from calculus where the chain rule is just canceling two things.

فهذا عبارة عن متسلسلة حسابية. نحن جمع بشكل أساسي 1 + 2 + 3 + 4، وبعض الثوابت هناك، ولكن في الأساس نحن نقوم بجمع 1 + 2 + 3 + 4 + 5 + 6 إلى أن نصل إلى n. هذا ثيتا (n^2). إذا كنت لا تعرف هذه الرياضيات ، هنالك فصل في الكتاب، أو كان يجب أن تأخذ الشروط المسبقة. السلسلة الهندسية. الناس لديهم هذا ذكريات مبهمة. أوه ، نعم. جيد. الآن، عليك أن تتعلم هذه المهارات. سوف نتحدث بشكل أكبر بقليل في المرة القادمة، ولكن عليك أن تعلم تعاملات ثيتا التي تعمل مع ترميز ثيتا. وعليك أن تكون حذرا جدا لأن ثيتا هو ترميز ضعيف. من الترميزات القوية ترميز ليبنيز من الحساب حيث تكون قاعدة السلسلة مجرد اختصار شيئين اثنين.

t's just fabulous that you can cancel in the chain rule. And Leibniz notation just expresses that so directly you can manipulate. Theta notation is not like that. If you think it is like that you are in trouble. You really have to think of what is going on under the theta notation. And it is more of a descriptive notation than it is a manipulative notation. There are manipulations you can do with it, but unless you understand what is really going on under the theta notation you will find yourself in trouble.

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 الفرز بالدمج

And next time we will talk a little bit more about theta notation. Is insertion sort fast? Well, it turns out for small n it is moderately fast. But it is not at all for large n. So, I am going to give you an algorithm that is faster. It's called merge sort. I wonder if I should leave insertion sort up. Why not. I am going to write on this later, so if you are taking notes, leave some space on the left. Here is merge sort of an array A from 1 up to n.

في المرة القادمة سوف نتحدث قليلا عن تدوين ثيتا. هل الفرز بالإدخال سريع؟ حسنا,ستكون متوسطة السرعة إذا كانت قيمة n صغيرة لكن هذا لا ينطبق عندما تكون n كبيرة . لذلك سأعطيكم خوارزمية وتدعى خوارزمية الفرز بالدمج أتساءل ما إذا كان علي ترك الفرز بالإدخال. لم لا . سأكتب على هذا القسم لاحقاً، لذلك إذا كنت تأخذ ملاحظات اترك فراغا على اليسار. هنا الفرز بالإدخال لمصفوفة A من 1 حتى n

And it is basically three steps. If n equals 1 we are done. Sorting one element, it is already sorted. All right. Recursive algorithm. Otherwise, what we do is we recursively sort A from 1 up to the ceiling of n over 2. And the array A of the ceiling of n over 2 plus one up to n. So, we sort two halves of the input. And then, three, we take those two lists that we have done and we merge them.

وهي بشكل أساسي ثلاث خطوات. إذا كانت n =1 يكون الأمر منتهياً. ترتيب عنصر واحد، فالمصفوفة مرتبة مسبقا. حسنا، الخوارزمية العودية، بخلاف ما سبق, ما نفعله هو فرز بشكل متكرر للمصفوفة A ابتداءً من <1> حتى <n/2>، ومن<n/2]+1]> حتى <n>، فنحن نفرز نصفين من الإدخال ثم، الخطوة الثالثة، نأخذ القائمتين المرتبتين و ندمجهما مع بعضهما.

And, to do that, we use a merge subroutine which I will show you. The key subroutine here is merge, and it works like this. I have two lists. Let's say one of them is 20. I am doing this in reverse order. I have sorted this like this. And then I sort another one. I don't know why I do it this order, but anyway. Here is my other list. I have my two lists that I have sorted. So, this is A[1] to A[|n/2|] and A[|n/2|+1] to A[n] for the way it will be called in this program. And now to merge these two, what I want to do is produce a sorted list out of both of them.

وللقيام بهذا نستعمل الدمج التكراري والذي سأريكم إياه. إن الإجراء المفتاحي هو الدمج، والطريقة كالتالي .لدي قائمتان. دعونا نقول أن إحداهما 20 . أنا أقوم بهذا بترتيب معكوس. لقد رتبت هذا على هذا النحو. ثم سأرتب الأخرى. لا أعلم لماذا أتبع هذا الترتيب. لكن على أية حال. هنا قائمتي الأخرى. الآن لدي القائمتين اللتين قمت بترتيبهما. لذا هذا [1]a إلى[a[n/2 وهذا [a[n/2+1 إلى[a[n وهذه الطريقة التي ستسدعى من هذا البرنامج. والآن لدمج هاتين القائمتين، ما أريد أن أفعله هو إخراج قائمة مرتبة تتضمن كل منهما.

What I do is first observe where is the smallest element of any two lists that are already sorted? It's in one of two places, the head of the first list or the head of the second list. I look at those two elements and say which one is smaller? This one is smaller. Then what I do is output into my output array the smaller of the two. And I cross it off. And now where is the next smallest element? And the answer is it's going to be the head of one of these two lists. Then I cross out this guy and put him here and circle this one. Now I look at these two guys. This one is smaller so I output that and circle that one. Now I look at these two guys, output 9. So, every step here is some fixed number of operations that is independent of the size of the arrays at each step.

ما أفعله أولا هو معرفة موقع أصغر عنصر في القائمتين اللتين قد رتبتا مسبقا. إنه في أحد مكانين، إما رأس القائمة الأولى أو رأس القائمة الأخرى. أنظر إلى هذين العنصرين وأتساءل أي العنصرين أصغر؟ هذا أصغر .ما أفعله هو أخذ العنصر الأصغر إلى مصفوفة الخرج. وأتخلص منه. والآن. أين هو العنصر الأصغر التالي؟ والجواب سيكون رأس إحدى هاتين القائمتين. ثم سأخرج هذا العدد وأضعه هنا وأضع دائرة حول هذا. والآن أنظر على هذين العديدين. هذا هو الأصغر فسأخرجه وأضع دائرة حول هذا. الآن سأنظر إلى هذين العددين،الخرج 9. لذا كل خطوة هنا هي عدد ثابت من العمليات مستقل عن حجم المصفوفات في كل خطوة.

Each individual step is just me looking at two elements and picking out the smallest and advancing some pointers into the array so that I know where the current head of that list is. And so, therefore, the time is order n on n total elements. The time to actually go through this and merge two lists is order n. We sometimes call this linear time because it's not quadratic or whatever. It is proportional to n, proportional to the input size. It's linear time. I go through and just do this simple operation, just working up these lists, and in the end I have done essentially n operations, order n operations each of which cost constant time.

علي في كل خطوة فقط النظر إلى عنصرين وأخذ الأصغر منهما وتقديم مؤشرات على المصفوفة لمعرفة موضع الرأس الحالي للقائمة . فالوقت تابع من رتبة n على n من العناصر الكلية. الوقت اللازم لتجاوز هذا ودمج القائمتين هو من رتبة n. نسمي هذا أحيانا بالوقت الخطي لأنه ليس درجة ثانية أو شيئاً من هذا القبيل. إنه يتناسب طرداً مع n, يتناسب طرداً مع حجم الإدخال .إنه وقت خطي. أقوم فقط بالمرور على القائمة والقيام بهذه العملية البسيطة، وفقط أعد هذه القوائم، وفي النهاية أكون قد قمت بـ n عملية, أستدعي n عملية والتي يستغرق كل واحد منها زمناً ثابتاً.

That's a total of order n time. Everybody with me? OK. So, this is a recursive program. We can actually now write what is called a recurrence for this program. The way we do that is say let's let the time to sort n elements to be T(n). Then how long does it take to do step one? That's just constant time. We just check to see if n is 1, and if it is we return. That's independent of the size of anything that we are doing. It just takes a certain number of machine instructions on whatever machine and we say it is constant time. We call that theta one. This is actually a little bit of an abuse if you get into it.

فهذا كمحصلة هو زمن من رتبة n. هل الكل معي؟ حسناً. فهذا برنامج عودي. يمكننا الآن كتابة ما يسمى بالعودية لهذا البرنامج. الطريقة هي أن نقول دعونا نفرض أن الوقت اللازم لفرز n عنصراً هو T(n). فكم من الوقت يلزم للقيام بالخطوة واحد؟ إنه وقتٌ ثابت. نحن فقط نتحقق لمعرفة ما إذا كان n = 1، وإن كانت كذلك فإننا نعيد. فهذا مستقل عن حجم أي شيء نقوم به. والأمر يتطلب فقط عددا معينا من تعليمات الجهاز مهما كان ذلك الجهاز ونقول إنه وقت ثابت. نسمي هذا ثيتا. في الواقع، هذا خرق للقواعد إن فكرت في الأمر.

And the reason is because typically in order to say it you need to say what it is growing with. Nevertheless, we use this as an abuse of the notation just to mean it is a constant. So, that's an abuse just so people know. But it simplifies things if I can just write theta one. And it basically means the same thing. Now we recursively sort these two things. How can I describe that? The time to do this, I can describe recursively as T of ceiling of n over 2 plus T of n minus ceiling of n over 2. That is actually kind of messy, so what we will do is just be sloppy and write 2T(n/2). So, this is just us being sloppy.

ذلك لأنه حتى تتمكن من معرفتها عليك معرفة ما الذي ينمو معها. ومع ذلك، فنحن نخرق التدوين فقط للدلالة على أنه ثابت، لذا فليعلم الجميع أن هذا خرق. لكن ذلك سيبسط الأمور إن كان بإمكاني فقط كتابة ثيتا واحد، وهذ يعني أساساً الشيء ذاته. والآن نرتب عودياً هذين الاثنين، كيف يمكنني وصف ذلك؟ الوقت اللازم لذلك، يمكنني وصف ذلك عودياً على أنه T لـ n مقسومة على 2 زائد T لـ n ناقص n مقسومة على 2 . في الواقع هذا فوضوي نوعا ما، لذلك ما سنفعله هو أن نكون مهملين قليلاً ونكتب 2T(n/2). إذاً هذا ما قمنا به مهملين.

And we will see on Friday in recitation that it is OK to be sloppy. That's the great thing about algorithms. As long as you are rigorous and precise, you can be as sloppy as you want. [LAUGHTER] This is sloppy because I didn't worry about what was going on, because it turns out it doesn't make any difference. And we are going to actually see that that is the case. And, finally, I have to merge the two sorted lists which have a total of n elements. And we just analyze that using the merge subroutine. And that takes us to theta n time.

سنرى يوم الجمعة في الجلسة المصغرة بأنه لا بأس بأن نكون مهملين. هذا هو الشيء العظيم في الخوارزميات. بقدر ما يمكنك أن تكون صارماً ودقيقاً بقدر ما يمكنك أن تكون مهملاً. لدي إهمال هنا لأنني لست قلقاً بما يجري ذلك أنه يتبين لنا أنه لا يحدث أي فرق. و سنرى أن هذا هو الحال في الواقع. وأخيراً ينبغي أن أدمج القائمتين المفروزتين المكونتين من n عنصراً. ونحلل هذا فقد باستخدام الدمج التكراري. وهذا يقودنا إلى زمن ثيتا n.

That allows us now to write a recurrence for the performance of merge sort. Which is to say that T of n is equal to theta 1 if n equals 1 and 2T of n over 2 plus theta of n if n is bigger than 1. Because either I am doing step one or I am doing all steps one, two and three. Here I am doing step one and I return and I am done. Or else I am doing step one, I don't return, and then I also do steps two and three. So, I add those together. I could say theta n plus theta 1, but theta n plus theta 1 is just theta n because theta 1 is a lower order term than theta n and I can throw it away. It is either theta 1 or it is 2T of n over 2 plus theta n. Now, typically we won't be writing this.

هذا يمكننا الآن من كتابة عودية لأداء الفرز بالدمج. حيث نقول أن T من n يساوي ثيتا 1 إذا كانت n تساوي 1 و2T من n على 2 زائد ثيتا n إذا كانت n أكبر من الواحد. لأنني إما أن أقوم بالخطوة واحد أو أن أقوم بكل الخطوات واحد، واثنان وثلاثة. هنا أقوم بالخطوة واحد أعيد أنني انتهيت. أو بشكل آخر، أقوم بالخطوة واحد، و لا أعيد شيئاً، ثم أقوم بالخطوة اثنان وثلاثة. لذا، سأضيف هذه جميعاً. أستطيع القول ثيتا n + ثيتا 1 ما هو إلا ثيتا n لأن ثيتا 1 حد صغير أمام ثيتا n ولهذا يمكنني رميه. فهو إما ثيتا 1 أو 2T من n على 2 زائد ثيتا n . طبعاً لن نقوم بكتابة هذا

Usually we omit this. If it makes no difference to the solution of the recurrence, we will usually omit constant base cases. In algorithms, it's not true generally in mathematics, but in algorithms if you are running something on a constant size input it takes constant time always. So, we don't worry about what this value is. And it turns out it has no real impact on the asymptotic solution of the recurrence.

نحن عادة نحذف هذا. إذا كان لا يشكل فرقاً بالنسبة للحل العودي، فإننا عادة نستبعد حالات الأساس العودي الثابتة. هذا ليس صحيحاً بشكل عام في الرياضيات، ولكن في الخوارزميات إذا كنت تقوم بتشغيل شيء ما على حجم ثابت من المدخلات فإنّه سيستغرق وقتاً ثابتاً دوماً. لذا، فإننا لا نقلق بشأن قيمة هذه. واتضح أنه ليس لهذا تأثير حقيقي على حل مقارب للتكرار العودي.

How do we solve a recurrence like this? I now have T of n expressed in terms of T of n over 2. That's in the book and it is also in Lecture 2. We are going to do Lecture 2 to solve that, but in the meantime what I am going to do is give you a visual way of understanding what this costs, which is one of the techniques we will elaborate on next time. It is called a recursion tree technique. And I will use it for the actual recurrence that is almost the same 2T(n/2), but I am going to actually explicitly, because I want you to see where it occurs, plus some constant times n where c is a constant greater than zero. So, we are going to look at this recurrence with a base case of order one.الأمجد توفيق اصطيف 10:35، 3 أكتوبر 2010 (ت‌ع‌م)

كيف تقوم بحل تكرار عودي كهذا. لدي الآن T من n بدلالة T من n/2. هذا في الكتاب، وفي المحاضرة الثانية أيضاً. ستكون المحاضرة الثانية حول حل هذا، أما في الوقت الحالي، فسأقدم طريقة بصرية لفهم ما يكلف هذا، وهي طريقة سنتحدث عنها بالتفصيل في المرة القادمة. إنها تدعى تقنية شجرة العودية، وسأستخدمها للتكرار العودي الحقيقي الذي هو تقريباً دوماً المقدار نفسه 2T(n/2)، لكنني في الواقع سأكون واضحاً، لأنني أريدكم أن تعرفوا كيف تطبق، بإضافة مقدار ثابت ما n، حيث c ثابت أكبر من الصفر. لذلك سننظر إلى هذا التكرار العودي مع حالة أساس عودي من المرتبة الأولى.

I am just making the constant in here, the upper bound on the constant be explicit rather than implicit. And the way you do a recursion tree is the following. You start out by writing down the left-hand side of the recurrence. And then what you do is you say well, that is equal to, and now let's write it as a tree. I do c of n work plus now I am going to have to do work on each of my two children.

أنا هنا، فقط أجعل الثابت ظاهراً بدل من كونه مضمناً. و طريقة رسم شجرة العودية هي كما يلي. نبدأ بكتابة الجانب الأيسر من العودية. ثم ما تقوم به هو أن نقول: جيد .. هذا يساوي إلى ...، الآن دعنا نكتبها كشجرة. سأقوم بعمل c مرة من n، الآن سأكرر ذلك من اجل كل من ابني العنصر.

T of n over 2 and T of n over 2. If I sum up what is in here, I get this because that is what the recurrence says, T(n)=2T(n/2)+cn. I have 2T(n/2)+cn. Then I do it again. I have cn here. I now have here cn/2. And here is cn/2. And each of these now has a T(n/4). And these each have a T(n/4). And this has a T(n/4). And I keep doing that, the dangerous dot, dot, dots. And, if I keep doing that, I end up with it looking like this.

T(n/2)‎ و T(n/2)‎. إذا جمعت كل ما لدي هنا، سأحصل على هذا، لأنه هذا ما تعنيه العودية، T(n)=2T(n/2)+cn . وهنا لدي ‎2T(n/2)+cn . ثم سأقوم بذلك مجدداً. لدي cn هنا وهنا لدي cn/2. و كل من هذين لديه T(n/4)‎ . و هذين لديهما T(n/4)‎ . وأستمر بالقيام بذلك. وإذا أكملنا سنحصل على شيء يبدو هكذا

And I keep going down until I get to a leaf. And a leaf, I have essentially a T(1). That is T(1). And so the first question I ask here is, what is the height of this tree? Yeah. It's log n. It's actually very close to exactly log n because I am starting out at the top with n and then I go to n/2 and n/4 and all the way down until I get to 1. The number of halvings of n until I get to 1 is log n so the height here is log n. It's OK if it is constant times log n. It doesn't matter. How many leaves are in this tree, by the way?

وسأستمر بالنزول حتى أحصل على ورقة. والورقة هي أساساً T(1). فهذا T(1). فالسؤال الأول الذي أسأله هنا هو، ما هو ارتفاع هذه الشجرة؟ نعم.أنه log n. في الواقع إنه قريب جداً من log n، لأنني في الأعلى بدأت بـ n ثم حصلت على n/2 و n/4 وهكذا نزولاً حتى حصلت على 1. فعدد تنصيفات n حتى أحصل على الواحد هو log n لذا ارتفاع الشجرة هو log n. لا بأس إذا كان هناك ثابت مضروب بـ log n. لن يحدث هذا فرقاً. بالمناسبة، كم عدد الأوراق في هذه الشجرة؟

How many leaves does this tree have? Yeah. The number of leaves, once again, is actually pretty close. It's actually n. If you took it all the way down. Let's make some simplifying assumption. n is a perfect power of 2, so it is an integer power of 2. Then this is exactly log n to get down to T(1). And then there are exactly n leaves, because the number of leaves here, the number of nodes at this level is 1, 2, 4, 8.

كم عدد الأوراق على هذه الشجرة ؟ نعم، عدد أوراق الأشجار مرة أخرى، في الحقيقة محصور، في الحقيقة هو n. إذا أخذتها بالكامل حتى الأسفل. لنأخذ افتراضاً مبسطاً. n هي القوة الكاملة ل 2، وهي قوة صحيحة للعدد 2. وهذا هو بالضبط log n نزولاً إلى (1)T. وبالتالي لدينا n ورقة بالضبط. لأن عدد الأوراق هنا، عدد العقد في هذا المستوى هو 1 ، 2 ، 4 ، 8 .

And if I go down height h, I have 2 to the h leaves, 2 to the log n, that is just n. We are doing math here, right? Now let's figure out how much work, if I look at adding up everything in this tree I am going to get T(n), so let's add that up. Well, let's add it up level by level. How much do we have in the first level? Just cn. If I add up the second level, how much do I have? cn. How about if I add up the third level? cn. How about if I add up all the leaves? Theta n.

إذا نزلت بمقدار الارتفاع h، لدي 2 حتى h ورقة، 2 حتى log n، هذا فقط n، نحن نقوم نستخدم الرياضيات هنا، صحيح؟ والآن لنحاول معرفة كم من العمل، إذا نظرت إلى جمع كل ما في الشجرة سأحصل على T(n)، إذاً لنجمع كل ذلك. حسناً لنقم بالجمع مستوى متسوى. كم لدينا في المستوى الأول. cn فقط. إذا جمعت المستوى الثاني، كم يصبح لدي. cn. ماذا لو جمعت المستوى الثالث. cn ماذا لو جمعت كل الأورق؟ ثيتا n

It is not necessarily cn because the boundary case may have a different constant. It is actually theta n, but cn all the way here. If I add up the total amount, that is equal to cn times log n, because that's the height, that is how many cn's I have here, plus theta n. And this is a higher order term than this, so this goes away, get rid of the constants, that is equal to theta(n lg n). And theta(n lg n) is asymptotically faster than theta(n^2). So, merge sort, on a large enough input size, is going to beat insertion sort.

إنه ليس بالضرورة cn لأن حالة الحد الأدنى يمكن أن تحوي ثابتاً مختلفاً. إنها في الحقيقة ثيتا n، لكن cn في جميع الحالات هنا. إذا قمت بجمع المقدار الكلي، فإنه سيساوي cn مرة من log n، لأنه الارتقاع، إنه مقدار ما معي من cn، زائد ثيتا n. وهذا حد ذو رتبة أعلى من هذا، لذلك فإنه يذهب. أتخلص من الثوابت، فيصبح هذا مساوياً لـ (theta (n lg n. وثيتا (n lg n أسرع تقاربياً من ثيتا(n^2)، لذلك الفرز بالدمج، لدخل ذو حجم كبير بما فيه الكفاية، سيتغلب على الفرز بالإدخال.

Merge sort is going to be a faster algorithm. Sorry, you guys, I didn't realize you couldn't see over there. You should speak up if you cannot see. So, this is a faster algorithm because theta(n lg n) grows more slowly than theta(n^2). And merge sort asymptotically beats insertion sort. Even if you ran insertion sort on a supercomputer, somebody running on a PC with merge sort for sufficient large input will clobber them because actually n^2 is way bigger than n log n once you get the n's to be large. And, in practice, merge sort tends to win here for n bigger than, say, 30 or so.

الفرز بالدمج سيكون خوارزمية أسرع. عذراً، يا رفاق، لم أُدرك أنه لا يمكنم أن تَرَوا من هناك. يجب أن تتكلموا عندما لا تتمكنون من الرؤية. إذاً، هذه خوارزمية أسرع لأن ثيتا (ن لوغاريتم ن) ينمو ببطء أكثر من ثيتا (ن مربع). و الفرز بالدمج تقاربياً يتغلب على للفرز بالإدخال . حتى لو قمت بتشغيل الفرز بالإدخال على حاسوب عملاق، وشخص ما يعمل على حاسوب شخصي بواسطة الفرز بالدمج. من أجل كميات ضخمة كافية من المدخلات سيهزمهم. لأنه في الواقع، ن مربع هي أكبر بكثير من ن لوغاريتم ن بمجرد الوصول إلى ن كبيرة. وفي الممارسة العملية، الفرز بالدمج يميل للفوز هُنا من أجل ن أكبر من، لنقل، 30 أو نحو ذلك.

If you have a very small input like 30 elements, insertion sort is a perfectly decent sort to use. But merge sort is going to be a lot faster even for something that is only a few dozen elements. It is going to actually be a faster algorithm. That's sort of the lessons, OK? Remember that to get your recitation assignments and attend recitation on Friday. Because we are going to be going through a bunch of the things that I have left on the table here. And see you next Monday.

إذا كان لديك دخل صغير جداً مثل 30 عنصر،الفرز بالإدخال مناسب تماما للاستخدام. لكن الفرز بالدمج سيكون أسرع بكثير حتى من أجل بضع عشرات من العناصر. سيكون فعلا خوارزمية أسرع. فهذا هو الدرس، حسنا؟ تذكروا أن تحصلوا على جدول الجلسة المصغرة وأن تحضروا الجلسة يوم الجمعة. لأننا سوف نتحدث عن مجموعة من الأشياء التي تركتها على الطاولة هنا. نراكم يوم الاثنين المقبل.

 تسجيل المحاضرة

المحاضرة الأولى:

<embed width="320" height="240" quality="high" bgcolor="#000000" name="main" id="main" >http://media.marefa.org/modules/vPlayer/vPlayer.swf?f=http://media.marefa.org/modules/vPlayer/vPlayercfg.php?fid=2b5af89203c2b78c67c" allowscriptaccess="always" allowfullscreen="false" type="application/x-shockwave-flash"/</embed>

المحاضرة الثانية:

MIT Introduction to Algorithms - Lecture 2.

المحاضرة الثالثة:

<embed width="320" height="240" quality="high" bgcolor="#000000" name="main" id="main" >http://media.marefa.org/modules/vPlayer/vPlayer.swf?f=http://media.marefa.org/modules/vPlayer/vPlayercfg.php?fid=c329e940dda99b12147" allowscriptaccess="always" allowfullscreen="false" type="application/x-shockwave-flash"/</embed>