[موسیقی بجانے] 

پروفیسر: ٹھیک. یہ CS50 ہے اور یہ ہے ہفتے میں تین کے اختتام. تو ہم آج یہاں موجود ہونا، نہیں Sanders میں بجائے Weidner لائبریری میں تھیٹر،. جس کے اندر ایک سٹوڈیو ہے Hauser سٹوڈیو کے طور پر جانا، یا ہم سٹوڈیو ایچ کہنا، یا کریں گے آپ اس مذاق سے لطف اندوز اگر ہم say--، اس سے اصل میں ہے سہپاٹھی، مارک، آن لائن، جو ٹویٹر کے ذریعے جتنا مشورہ دیا. اب کے بارے میں ٹھنڈا کیا ہے ایک سٹوڈیو میں یہاں کیا جا رہا ہے میں ان سبز سے گھرا ہوا ہوں ہے کہ دیواروں، ایک سبز رنگ کی سکرین یا chromakey، تو CS50 کی جس کا مطلب ہے، بات کرنے کے لئے مجھ سے لوگ شاید نہ جانتے پروڈکشن ٹیم، اب، رکھا جائے ڈال سکتا مجھے سب سے زیادہ دنیا میں کہیں بھی، بہتر کے لئے یا برے کے لئے. 

اب آگے کیا، مسئلہ سیٹ جھوٹ دو، اس ہفتے کے لئے آپ کے ہاتھ میں ہے لیکن مسئلہ کے ساتھ قائم تین اس آنے والے ہفتے، آپ کے ساتھ چیلنج کیا جائے گا 15 کے نام نہاد کھیل، ایک پرانی پارٹی کے حق کہ آپ کو موصول ہونے یاد کر سکتے ہیں ایک پوری چڑھانے ہے کہ ایک بچے کے طور پر نیچے، سلائڈ سکتا ہے کی تعداد کی وجہ سے، بائیں اور دائیں، اور ایک فرق ہے پہیلی، اندر جس میں آپ اصل میں ان لوگوں پہیلی ٹکڑے ٹکڑے سلائڈ کر سکتے ہیں. آخر میں آپ کو ملے کچھ نیم بے ترتیب ترتیب میں پہیلی، اور مقصد کے لئے ہے سب سے نیچے، سب سے اوپر اس کو الگ الگ، ایک سے، بائیں سے دائیں 15 کے ذریعے تمام راستہ. 

بدقسمتی سے، پر عمل درآمد آپ کے ہاتھ میں پڑے گا سافٹ ویئر کی جا رہی ہے کی بنیاد پر، جسمانی طور پر نہیں. تم واقعی میں لکھنے کے لئے جا رہے ہیں کوڈ ہے جس میں ایک طالب علم یا صارف کر سکتے ہیں کے ساتھ 15 کھیل کھیلنے. اور حقیقت میں، ہیکر میں 15 کے کھیل کے ایڈیشن، آپ کو ایک چیلنج کے نفاذ کے لیے ہو جائے گا، اس پرانے اسکول کی نہ صرف کھیل کھیل، بلکہ حل اس کا، خدا موڈ کو لاگو کرنے، لہذا، بات کرنے کے لئے اصل میں اس انسان کے لئے پہیلی کو حل کرتی ہے، اشارہ کے ساتھ ان کو فراہم کی طرف سے، اشارہ کے بعد، اشارہ کے بعد. کہ اگلے ہفتے پر تو زیادہ. لیکن اس آگے جھوٹ ہے. 

اب کے لئے یاد ہے کہ اس ہفتے کے اوائل اگر آپ ہم، اس cliffhanger کے تھا جس کے تحت ہم چھانٹ رہا ہے کر رہے تھے سب وار ن O بڑی کے ایک اوپری پابند کیا گیا تھا مربع. دوسرے الفاظ میں، بلبلا طرح، انتخاب کی طرح، اندراج کی طرح، ان میں سے سب، مختلف ہے جبکہ ان کے عمل میں، چلانے مربع ایک ن میں منتقل بہت بدترین صورت میں وقت. اور ہم عام طور پر فرض ہے کہ چھنٹائی کے لئے بہت بدترین صورت ایک ہے کہ آپ کے آدانوں ہے مکمل طور پر پیچھے کی طرف ہو. اور یقینا، یہ بہت چند قدم لیا ان الگورتھم میں سے ہر ایک کو لاگو کرنے کے. 

اب کلاس کے آخر میں یاد، ہم بلبلا قسم مقابلے ایک دوسرے کے خلاف انتخاب کی طرح کے خلاف کہ ہم، وقت طرح ضم بلایا اور میں نے اسے لے جا رہا ہے کہ تجویز ہفتے سے ایک سبق کا فائدہ صفر، تقسیم اور فتح. اور کسی نہ کسی طرح کسی قسم کا حصول لوگارتمی بالآخر وقت چل رہا ہے، بجائے کچھ کے یہ خالصتا چوکور ہے. اور یہ بہت لوگارتمی نہیں ہے اس کے مقابلے میں تھوڑا زیادہ ہے. لیکن آپ کو کلاس سے یاد تو، یہ زیادہ تیزی سے، زیادہ تھا. ہم چھوڑ دیا جہاں پر ایک نظر ڈالیں. 

انتخاب بمقابلہ بلبلا طرح ضم طرح طرح بمقابلہ. اب وہ سب میں، چل رہا ہے کر رہے ہیں نظریہ، ایک ہی وقت میں. CPU ایک ہی رفتار سے چل رہا ہے. لیکن آپ کو کس طرح بورنگ یہ محسوس کر سکتے ہیں بہت تیزی سے بننے جا رہا ہے، اور صرف کتنی تیزی سے، ہم جب انجیکشن ہفتے صفر کی یلگوردمز کا تھوڑا سا، ہم چیزوں کو تیز کر سکتے. 

تو نشان طرح حیرت انگیز لگتا ہے. کس طرح ہم نے آرڈر میں، یہ بیعانہ کر سکتے ہیں زیادہ تیزی سے اعداد و شمار کو حل کرنے. چلو واپس سوچنے دو ایک جزو ہے کہ ہم کی ہے کہ، ہفتے صفر میں تھا ایک فون کی کتاب میں کسی کے لئے تلاش، اور یاد ہے کہ ہم تجویز کہ pseudocode، جس کے ذریعے ہم حاصل کر سکتے ہیں مائیک سمتھ کی طرح کسی، اس طرح ایک چھوٹا سا کچھ دیکھا. 

اب خاص طور پر ایک نظر ڈالیں لائن پر 7 اور 8، اور 10 اور 11، ہم رکھا جس کے تحت، جو کہ لوپ دلانا ایک بار پھر، اور دوبارہ واپس لائن 3 کے لئے جا رہا، اور ایک بار پھر. لیکن یہ ہم دیکھ سکتے ہیں کہ باہر کر دیتا ہے اس الگورتھم، یہاں pseudocode میں، زیادہ holistically کا ایک چھوٹا سا. اصل میں، میں کیا کر رہا ہوں یہاں کی سکرین پر، تلاش کرنے کے لئے ایک الگورتھم ہے صفحات میں سے کچھ سیٹ میں مائیک سمتھ. اور بے شک، ہم اس کو آسان بنانے کے کر سکتے ہیں ان لائنوں 7 اور 8 میں الگورتھم، اور 10 اور 11 صرف، اس کا کہنا ہے جس میں پیلے رنگ میں یہاں پیش کیا ہے. دوسرے الفاظ میں، اگر مائیک سمتھ، پہلے کتاب میں ہے ہم قدم کی وضاحت کرنے کی ضرورت نہیں ہے قدم کی طرف سے اب کس طرح اس کو تلاش کرنے کے لئے جانا. ہم وضاحت کرنے کی ضرورت نہیں لائن 3 پر واپس جانے کے لئے، کیوں ہم صرف اس کی بجائے ایسا نہیں کرتے، کہو، زیادہ عام طور پر، میں مائیک کے لئے تلاش کتاب کے بائیں نصف. 

برعکس، مائیک ہے اصل میں بعد میں کتاب میں، کیوں ہم صرف unquote جو تلاش حوالہ نہیں کتاب کے دائیں نصف میں مائیک کے لئے. دوسرے الفاظ میں، کیوں ہم صرف نہیں قسم کے خود کہہ کے پنٹ، اس میں مائیک کے لئے تلاش کتاب کے اپسمچی، اور ہمارے موجودہ پر چھوڑ الگورتھم ہمیں بتانا میں مائیک تلاش کرنے کے لئے کس طرح کتاب کے اس بائیں نصف. دوسرے الفاظ میں، ہمارے الگورتھم ہے کہ آیا کام اس کے اس کی موٹائی کے ایک فون کی کتاب، موٹائی، یا کسی بھی موٹائی. تو ہم کر سکتے ہیں تکراری اس الگورتھم کی وضاحت. دوسرے الفاظ میں، پر یہاں کی سکرین، ایک الگورتھم ہے مائیک سمتھ کی تلاش کے لئے ایک فون کی کتاب کے صفحات کے درمیان. تو اوپر 7 اور 10 میں، چلو صرف بالکل کا کہنا ہے کہ. اور میں اس اصطلاح کو ایک لمحے کا استعمال پہلے، اور بے شک، تکرار buzzword ہے، اب کے لئے ہے اور اس عمل ہے کسی نہ کسی طرح کی طرف سے چکریی کچھ کرنے کے آپ نے پہلے ہی ہے کہ کوڈ کا استعمال کرتے ہوئے، اور، ایک بار پھر بلا اور پھر، اور پھر. اب یہ اہم ہونے جا رہا ہے ہم کسی نہ کسی طرح نیچے کہ باہر، اور infinitely طویل ایسا نہ کرو. دوسری صورت میں ہم جا رہے ہیں یقینا ایک لامتناہی لوپ ہے. لیکن ہم اس خیال قرضے لے سکتے ہیں تو دیکھتے ہیں ایک تکرار کی، ایک بار پھر کچھ کر اور بار بار، کو حل کرنے کے ضم کے ذریعے چھانٹ رہا مسئلہ قسم، سب سے زیادہ مؤثر طریقے سے. 

لہذا میں آپ کو ضم طرح دے. چلو ایک نظر ڈالیں. تو یہاں pseudocode کے ساتھ، ہے ہم چھانٹ رہا ہے پر عملدرآمد کر سکتے ہیں جس، ضم طرح کہا جاتا ہے اس الگورتھم استعمال کرتے ہوئے. اور یہ بہت صرف یہ ہے. ن عناصر کی ان پٹ پر، دوسرے الفاظ میں، آپ ہیں تو دی این عناصر اور نمبر ان پٹ ہے یا جو کچھ بھی خط، آپ ن عناصر، تو دی کر رہے ہیں تو ن 2 سے بھی کم ہے، صرف واپسی. ٹھیک ہے؟ (ن) ہے، 2 کے مقابلے میں کم ہے کیونکہ اگر مطلب یہ ہے کہ عناصر کی فہرست سائز 0 یا 1 یا تو ہے، اور ان چھوٹی دونوں مقدمات کی میں، فہرست پہلے ہی کے مطابق ہے. کوئی فہرست نہیں ہے تو، اس کے مطابق ہے. اور لمبائی کی ایک فہرست موجود ہے تو 1، یہ واضح طور پر حل ہے. تو الگورتھم صرف کرنے کی ضرورت ہے واقعی دلچسپ کچھ کرنا، ہم دو یا اس سے زیادہ ہے تو عناصر ہمارے لئے دیا. تو تو جادو دیکھو. ورنہ عناصر کے بائیں نصف ترتیب، تو عناصر کے دائیں نصف ترتیب، پھر حل حصوں کو ضم. اور موڑنے دماغ کی قسم کیا ہے یہاں، میں واقعی میں نہیں ہے تم سے کہا ہے لگ رہے ہو ابھی تک کچھ بھی، ٹھیک ہے؟ تمام میں، کی ایک فہرست دی ہے کہا ہے ن عناصر،، بائیں نصف ترتیب پھر دائیں نصف، تو مطابق حصوں کو ضم، لیکن جہاں اصل خفیہ چٹنی ہے؟ الگورتھم کہاں ہے؟ ویسے یہ ان دو لائنوں پتہ چلا ہے کہ سب سے پہلے، عناصر کی طرح بائیں نصف، اور عناصر کے دائیں نصف، پنراورتی کالوں ہیں، تو بات کرنے کی. 

سب کے بعد، اس سے اوپر وقت میں نقطہ، میں ہے جس کے ساتھ ایک الگورتھم عناصر کی ایک پوری چڑھانے الگ الگ؟ جی ہاں. یہ یہیں ہے. یہ سکرین پر یہیں پر ہے، اور تو میں اقدامات کی اسی سیٹ استعمال کر سکتے ہیں بائیں نصف کو حل کرنے، دائیں نصف میں کر سکتا ہوں کے طور پر. اور بے شک، ایک بار پھر، اور پھر. تو کسی نہ کسی طرح یا دوسری، اور ہم جلد ہی کروں گا ، ضم طرح کا جادو اس کو دیکھنے کے کہ بہت فائنل میں سرایت کر رہا ہے لائن، کے مطابق حصوں کو ضم. اور یہ کہ کافی بدیہی لگتا ہے. تم دو حصوں لے، اور کسی نہ کسی طرح، ان کے ساتھ ضم، اور ہم یہ دیکھ لیں گے ٹھوس ایک لمحے میں. 

لیکن یہ ایک مکمل الگورتھم ہے. اور کی بالکل کیوں دیکھتے ہیں. ویسے ہم یہ وہی دی کر رہے ہیں لگتا ہے کہ سکرین پر یہاں آٹھ عناصر، ایک آٹھ کے ذریعے، لیکن وہ کر رہے ہیں بظاہر بے ترتیب ترتیب میں. اور ہاتھ میں مقصد ہے ان عناصر کو حل کرنے. ویسے میں نے کے بارے میں کیسے جا سکتے ہیں ایک بار پھر، کا استعمال کرتے ہوئے کر رہے ہیں، اس pseudocode کے مطابق، ضم طرح؟ اور پھر، میں اس ingrain آپ کے دماغ، صرف ایک لمحے کے لئے. پہلی صورت خوبصورت ہے معمولی، یہ 2 کے مقابلے میں کم ہے تو، صرف کیا جا کرنے کے لئے کوئی کام نہیں ہے، واپس. تو واقعی صرف تین ہے اقدامات واقعی ذہن میں رکھنے کے لئے. ایک بار پھر، اور پھر، میں ہوں کرنا چاہتے ہیں کے لئے جا رہا بائیں نصف کو حل کرنے، دائیں نصف ترتیب، اور پھر ایک بار ان دو حصوں، حل کر رہے ہیں میں ان کے ساتھ ضم کرنے کے لئے چاہتے ہیں ایک کے مطابق کی فہرست میں. تاکہ ذہن میں رکھنے کے. 

تو یہاں اصل فہرست ہے. کی ایک کے طور پر اس کا علاج کرتے ہیں صف، ہم کرنا شروع کر دیا کے طور پر دو ہفتے میں، جس میں ایک ہے میموری کی ملحق بلاک. اس صورت میں، آٹھ ہیں استعمال تعداد، واپس کرنے کے لئے واپس کرنے کے لئے. اور اب ضم طرح کا اطلاق. تو میں نے پہلا حل کرنا چاہتے ہیں اس فہرست کے بائیں نصف، اور اس وجہ سے، چلو 4، 8، 6، اور 2 پر توجہ مرکوز. 

اب میں کے بارے میں کیسے جا سکتا ہوں 4 سائز کے ایک فہرست چھانٹ رہا ہے؟ ویسے میں نے اب غور کرنا ہوگا بائیں نصف کے بائیں چھانٹ رہا ہے. پھر، صرف ایک لمحے کے لئے ماضی دو. pseudocode کے اگر یہ، اور میں آٹھ عناصر دیا رہا ہوں، 8 ظاہر بڑھ کر ہے یا اس سے زیادہ 2 کے برابر. ساتھ تو سب سے پہلے کیس پر لاگو نہیں ہوتا. تو آٹھ عناصر ترتیب، میں سب سے پہلے ، عناصر کے بائیں نصف ترتیب پھر میں نے اس وقت میں ضم، دائیں نصف ترتیب دو کے مطابق حصوں، 4 سائز کے ایک. ٹھیک ہے. 

تم نے مجھے کہا ہے لیکن اگر، الگ الگ اب 4 سائز کے ہے جس میں بائیں نصف،، میں کس طرح بائیں نصف ترتیب کرتے ہیں؟ ویسے میں ایک ہے تو چار عناصر کی ان پٹ، میں سب سے پہلے بائیں ترتیب دو، پھر دائیں دو، اور پھر میں نے ان کے ساتھ ضم. تو ایک بار پھر، یہ تھوڑا سا ہو جاتا ہے دماغ کی یہاں کھیل موڑنے، آپ کی وجہ سے، اس قسم کی، کرنا پڑے آپ کی کہانی میں کہاں ہیں یاد، لیکن دن کے اختتام پر، عناصر میں سے کسی نمبر دیا، آپ سب سے پہلے حل کرنا چاہتے ہیں بائیں نصف، پھر دائیں نصف، تو ان کے ساتھ ضم. کے بالکل ایسا کرنے کے لئے شروع کرتے ہیں. یہاں آٹھ عناصر کی ان پٹ ہے. اب ہم یہاں بائیں نصف دیکھ رہے ہیں. میں کس طرح چار عناصر ترتیب ہے؟ ویسے میں نے سب سے پہلے بائیں نصف ترتیب. اب میں کس طرح بائیں نصف ترتیب کرتے ہیں؟ ویسے میں دو عناصر دیا گیا ہے. تو ان دونوں عناصر کو الگ الگ دو. 2 یا اس سے زیادہ 2 کے برابر، کورس کے. تو اس پہلی صورت لاگو نہیں ہوتا. 

تو اب میں بائیں حل کرنا پڑے ان دو عناصر کی نصف. بائیں نصف، کورس کے، صرف 4 ہے. تو کس طرح میں ایک عنصر کی ایک فہرست ترتیب ہے؟ ٹھیک ہے اب، کہ خصوصی بنیاد کیس سب سے اوپر، تو بات کرنے کی، لاگو ہوتا ہے. 1 کم 2 ہے، اور میرے فہرست میں واقعی کے 1 سائز کے ہے. تو میں صرف واپسی. میں کچھ بھی نہیں ہے. اور بے شک، میں نے کیا کی طرف دیکھو کیا، 4 پہلے ہی حل ہے. جیسا کہ میں نے پہلے سے ہی ہوں یہاں جزوی طور پر کامیاب. 

اب اس قسم کے بیوکوف لگتا ہے دعوی، لیکن یہ سچ ہے. 4 1 سائز کے ایک فہرست ہے. یہ پہلے ہی حل ہے. کہ بائیں نصف ہے. اب میں دائیں نصف ترتیب. میری ان پٹ 8، ایک عنصر ہے اسی طرح، پہلے ہی کے مطابق. پاگل، بھی، لیکن ایک بار پھر، یہ بنیادی اصول اب ہم تعمیر کرنے کے لئے اجازت دینے کے لئے کی جا رہی ہے اس کے سب سے اوپر پر کامیابی. 4، 8 کے مطابق ہے، حل کہ آخری مرحلہ کیا تھا؟ تو تیسرا اور آخری مرحلہ، کوئی وقت آپ کو، ایک فہرست، یاد چھںٹائی کر رہے ، دو حصوں کو ضم کرنے کے لئے تھا بائیں اور دائیں. تو بالکل ایسا دو. میری بائیں نصف، کورس کے، 4 ہے. میری دائیں نصف 8. 

تو ایسا کرنے دو. سب سے پہلے میں مختص کرنے جا رہا ہوں کچھ اضافی میموری، ، میں یہاں کی نمائندگی کریں گے کہ صرف ایک ثانوی سرنی کے طور پر، اس فٹ ہونے کے لئے کافی بڑا ہے. لیکن آپ کو توسیع تصور کر سکتے ہیں کہ مستطیل پوری لمبائی، ہم زیادہ سے زیادہ کے بعد کی ضرورت ہے تو. 4 لے اور 8، اور ضم کیسے ایک ساتھ مل کر 1 سائز کے ان دو فہرستیں؟ یہاں، بھی، بہت آسان. 4 تو، سب سے پہلے آتا 8 آتا. میں حل کرنا چاہتے ہیں کیونکہ اگر بائیں نصف، پھر دائیں نصف، اور پھر ان دو حصوں کو ضم ایک دوسرے کے ساتھ، کے مطابق ترتیب میں، 4 تو، سب سے پہلے آتا 8 آتا. 

تو ہم بھی، پیش رفت کر جائے لگ رہے ہو میں کسی بھی اصل کام نہیں کیا ہے اگرچہ. ہم کہانی میں ہیں جہاں لیکن یاد رکھنا. ہم اصل میں آٹھ عناصر لیا. ہم 4 ہے جو بائیں نصف، حل. پھر ہم بائیں نصف حل 2 تھا جو بائیں نصف، کے. اور ہم یہاں جانا. ہم نے اس قدم کے ساتھ کیا کر رہے ہیں. 

ہم حل ہے تو اب ہم، 2 نصف چھوڑ دیا 2 کے دائیں نصف ترتیب کرنا پڑے. تو 2 کے دائیں نصف ہے یہاں ان دو اقدار، 6 اور 2. تو اب کے سائز کی ایک ان پٹ لے 2، اور پھر بائیں نصف ترتیب، اور دائیں نصف، اور پھر ان کے ساتھ ضم. ویسے میں کس طرح کے سائز کی ایک فہرست ترتیب کرتے 1، نمبر 6 پر مشتمل؟ میں نے پہلے ہی کیا کر رہا ہوں. 1 سائز کی ہے کہ فہرست کے مطابق ہے. 

میں ایک اور فہرست ترتیب کیسے 1 سائز، نام نہاد دائیں نصف. ویسے یہ بھی، پہلے ہی حل ہے. نمبر 2 اکیلی ہے. تو اب میں دو حصوں ہے، بائیں اور ٹھیک ہے، میں ان کے ساتھ ضم کرنے کے لئے کی ضرورت ہے. مجھے اپنے آپ کو کچھ اضافی جگہ دے دو. اور، وہاں 2 ڈال پھر 6 وہاں، اس اس فہرست چھانٹ رہا ہے،، بائیں اور دائیں اور بالآخر، ایک دوسرے کے ساتھ ضم. تو میں نے قدرے بہتر شکل میں ہوں. میں، کیا وجہ نہیں کر رہا ہوں واضح طور پر 4، 8، 2، 6 میں چاہتا ہوں کہ حتمی حکم نہیں ہے. لیکن اب، کہ 2 سائز کے دو فہرستیں ہے دونوں، بالترتیب، کے مطابق کیا گیا ہے. تو اب آپ کو آپ کے دماغ میں ماضی تو آنکھ، کہ جہاں ہمیں چھوڑ دیا؟ میں اس وقت آٹھ عناصر کے ساتھ شروع میں ، 4 کے بائیں نصف کے لئے اس کو آئی پھر 2 کے بائیں نصف، اور پھر 2 کے دائیں نصف، میں بائیں چھنٹائی، لہذا، ختم 2 میں سے نصف، اور 2 کے دائیں نصف، تو تیسرے اور حتمی مرحلے میں یہاں کیا ہے؟ میں ایک ساتھ ضم کرنا پڑے 2 سائز کے دو فہرستوں. تو آگے بڑھو. اور یہاں کی سکرین پر، دے مجھے کچھ اضافی میموری، تکنیکی طور پر، اگرچہ، میں ہے کہ نوٹس خالی جگہ اوپر کی ایک پوری چڑھانے ہے وہاں. مجھے خاص طور پر کرنا چاہتے ہیں موثر خلائی وار، میں صرف عناصر کو منتقل شروع کر سکتا ہے آگے اور پیچھے، اوپر اور نیچے. لیکن صرف بصری وضاحت کے لئے، میں، ذیل میں اس کے نیچے ڈال کرنے کے لئے جا رہا ہوں اچھا اور صاف چیزیں رکھنے. 

تو میں 2 سائز کے دو فہرستیں ہے. پہلی فہرست 4 اور 8 ہے. دوسری فہرست 2 اور 6 ہے. کی ان ضم دو ایک دوسرے کے ساتھ کے مطابق ترتیب میں. 2، کورس کی، سب سے پہلے آتا ہے پھر 4، پھر 6، تو 8. اور اب ہم ہو رہی کرنے لگتے ہیں کہیں دلچسپ. اب میں حل ہے نصف فہرست، اور اتفاق، یہ ہے تمام بھی تعداد، لیکن اس ، بے شک، صرف ایک اتفاق نہیں ہے. اور اب میں بائیں حل ہے نصف، 2، 4، 6، اور 8 ہے تاکہ. کچھ بھی نہیں کے حکم سے باہر ہے. اس پیش رفت کی طرح محسوس ہوتا ہے. 

میں نے کی طرح اب یہ محسوس ہوتا ہے اب ہمیشہ بات کر رہے، تو کیا اگر یہ دیکھا جا کرنے کی ضرورت ہے الگورتھم یقینا، زیادہ موثر ہے. لیکن ہم کے ذریعے جا رہے ہیں یہ سپر طریقے. ایک کمپیوٹر، کورس کے، اس طرح یہ کروں گا. تو ہم کہاں ہیں؟ ہم آٹھ عناصر کے ساتھ شروع کر دیا. میں نے 4 کے بائیں نصف حل. میں اس کے ساتھ کیا جائے لگ رہے ہو. تو اب اگلے مرحلے پر ہے 4 کے دائیں نصف ترتیب. اور اس حصے ہم جا سکتے ہیں ایک چھوٹی سی سے زیادہ کے ذریعے فوری طور پر، آپ کر رہے ہیں اگرچہ صرف، ماضی یا روکنے کے لئے کا خیر مقدم میں اس کے ذریعے لگتا ہے آپ کی اپنی رفتار، لیکن کیا اب ہم ایک موقع ہے چار پر بالکل وہی الگورتھم مختلف تعداد. 

تو آگے بڑھو، اور پر توجہ مرکوز ہم یہاں ہیں جو دائیں نصف،. اس کے بائیں نصف دائیں نصف، اور اب بائیں بازو کی بائیں نصف اس کا حق نصف میں سے نصف، اور میں کے سائز کی ایک فہرست ترتیب کیسے 1 بس نمبر 1 ہیں استعمال؟ یہ پہلے سے ہی کیا ہے. میں نے ایک فہرست کے لئے بھی ایسا ہی کریں کیسے صرف 7 پر مشتمل 1 سائز کے؟ یہ پہلے سے ہی کیا ہے. تو اس نصف کے لئے تین مرحلہ ان دونوں عناصر کو ضم کرنے کے لئے ہے سائز 2، 1 اور 7 کی ایک نئی فہرست میں. سب کیا ہے کے لئے نہیں لگتے کہ بہت دلچسپ کام. اگلے کیا ہوتا ہے دیکھتے ہیں. میں صرف کے بائیں نصف حل اپنے اصل ان پٹ کے دائیں نصف. اب صحیح طرح دو 5 اور 3 پر مشتمل ہے جس نصف،. پھر بائیں دیکھو نصف، حل، صحیح نصف، حل، اور ایک دوسرے کے ساتھ ان دو ضم کچھ اضافی خلا میں، 3 پھر، سب سے پہلے آتا 5 آتا ہے. اور تو اب، ہم کے مطابق ہے دائیں نصف کے بائیں نصف اصل مسئلہ کی، اور دائیں نصف کے دائیں نصف اصل مسئلہ کی. تیسرے اور آخری مرحلہ کیا ہے؟ اچھی طرح مل کر ان دو حصوں کو ضم کرنے کے لئے. تو مجھے اپنے آپ کو کچھ حاصل کرنے کی اجازت پھر اضافی جگہ، لیکن، میں کہ فالتو جگہ اوپر استعمال ہو سکتا ہے. لیکن ہم رکھنے کے لئے جا رہے ہیں ضعف یہ آسان. اب مجھے 1 میں ضم، اور پھر 3، اور پھر 5، اور پھر 7. اس طرح کے ساتھ اب مجھے چھوڑ کر اصل مسئلہ کے دائیں نصف کہ بالکل مطابق ہے. 

تو کیا رہ گیا ہے؟ میں کہہ رہی رکھنے مجھے لگتا ہے جیسے ایک بار پھر، اور پھر وہی چیزیں، لیکن اس کا عکاس ہے ہم تکرار استعمال کر رہے ہیں حقیقت یہ ہے کہ. ایک استعمال کے عمل ایک بار پھر، اور پھر الگورتھم، کے چھوٹے ذیلی سیٹ پر اصل مسئلہ. تو اب میں ایک بائیں کے مطابق ہے اصل مسئلہ کے نصف. میں نے ایک صحیح مطابق نصف ہے اصل مسئلہ کی. تیسرے اور آخری مرحلہ کیا ہے؟ اوہ، یہ ضم ہے. تو یہ کرتے ہیں. کچھ اضافی مختص ہیں میموری، لیکن میرے خدا، ہم اب اسے کہیں بھی ڈال سکتے ہیں. ہم اتنی جگہ دستیاب ہے ہم سے، لیکن ہم اسے سادہ رکھیں گے. اس کے بجائے واپس جانے اور آگے ہماری اصل میموری، صرف یہ کرنا چلو ضعف یہاں نیچے، ضم ختم کرنے کے لئے بائیں نصف اور دائیں نصف. 

ولی کی طرف سے تو، مجھے کیا کرنا کی ضرورت ہے؟ میں آرڈر میں عناصر لے جانا چاہتا ہوں. تو بائیں نصف کو دیکھ کر، میں سب سے پہلے نمبر 2 دیکھیں. میں صحیح نصف میں نظر آتے ہیں، میں سب سے پہلے نمبر دیکھیں تو ظاہر ہے، 1 ہے جو تعداد، میں باہر توڑ کرنا چاہتے ہیں اور میرا آخری فہرست میں پہلے ڈال دیا؟ کورس کے، 1. اب میں نے اس ایک ہی سوال پوچھنا چاہتا ہوں. بائیں نصف پر، میں نے اب بھی 2 نمبر ہے. صحیح نصف پر، میں نمبر 3 ہے. جس سے ایک ہے منتخب کرنے کے لئے چاہتے ہیں؟ کورس کے، نمبر 2 اور اب امیدواروں نوٹس دائیں بائیں، 3 4. کی، کورس کے، 3 کا انتخاب کرتے ہیں. اب امیدواروں 4 پر ہیں دائیں بائیں، 5. ہم، کورس کے، 4، اتارنا منتخب کریں. دائیں بائیں، 5 پر 6. ہم، کورس کے، 5 منتخب کریں. دائیں بائیں، 7 6. ہم نے 6 منتخب کریں، اور پھر ہم 7 منتخب کریں، اور پھر ہم 8 منتخب کریں. Voila آئرلینڈ. 

الفاظ کی تو ایک بڑی تعداد کے بعد، ہم نے آٹھ عناصر کی اس فہرست کے مطابق ہے آٹھ کے ذریعے ایک کی فہرست میں، کہ، ہر قدم کے ساتھ اضافہ ہو رہا ہے لیکن کتنا وقت تھا یہ ایسا کرنے کے لئے ہمیں لے. ویسے میں نے جان بوجھ کر ہے pictorially کا رکھی چیزیں یہاں، تاکہ ہم کر سکتے ہیں کی قسم دیکھیں یا ڈویژن کی تعریف فتح میں ہو رہا ہے. 

آپ تناظر میں واپس دیکھو اگر واقعی، میں ان بندیدار لائنوں کی تمام چھوڑ دیا جگہ ہولڈرز میں، آپ کر سکتے ہیں، قسم کے، معکوس ترتیب میں، دیکھیں، آپ کی قسم میں واپس نظر آتے ہیں تو تاریخ اب، اپنے اصل فہرست سائز 8، کورس کے، ہے. اور پھر پہلے، میں تھا 4 سائز کے دو فہرست کے ساتھ نمٹنے، اور پھر 2 سائز کے چار فہرستوں، اور اس کے بعد 1 سائز کے آٹھ فہرستوں. 

تو یہ کیا کرتا ہے، قسم کے، کی یاد دلاتے؟ سے اچھی طرح، بے شک، کوئی ہم نے یلگوردمز اس طرح اب تک میں دیکھا جہاں ہم تقسیم، اور تقسیم، اور تقسیم، پھر چیزیں رکھنے، اور ایک بار پھر، اس عام خیال کے نتیجے میں. اور اس طرح وہاں کچھ ہے لوگارتمی یہاں کیا ہو رہا. اور یہ (ن) کے بہت لاگ ان، نہیں ہے لیکن لاگرتھمی جزو ہے ہم صرف کیا ہے کرنے کے لئے. 

اب کہ اصل میں ہے کہ کس طرح غور کریں. تو ایک بار پھر، (ن) کے لاگ ان تھا ایک بہت اچھا چل رہا وقت، ہم جیسے کچھ کیا جب بائنری تلاش، اب ہم یہ کہتے ہیں کے طور پر، تقسیم اور فتح حکمت عملی جس کے ذریعے ہم مائیک سمتھ پایا. اب تکنیکی. یہاں تک کہ، (ن) کے لاگ ان بیس 2 سب سے زیادہ ریاضی کی کلاس میں اگرچہ، 10 عام طور پر آپ فرض ہے کہ بنیاد ہے. لیکن کمپیوٹر سائنسدانوں تقریبا ہمیشہ لگتا ہے اور بنیاد 2 کی شرائط میں بات، تو ہم عام طور پر صرف کے لاگ ان کا کہنا ہے کہ (ن)، بجائے (ن) کے لاگ ان بیس 2، لیکن وہ بالکل ایک اور ہیں کمپیوٹر کی دنیا میں ایک ہی سائنس، اور ایک ایک طرف کے طور پر، ایک مستقل عنصر ہے دونوں کے درمیان فرق، یہ ہے تو زیادہ رسمی وجوہات کی بنا پر، ویسے بھی موٹ. 

لیکن اب کے لئے، ہم کیا دیکھ بھال کے بارے میں یہ مثال ہے. تو مثال کے طور پر کی طرف سے ثابت نہیں ہیں، لیکن میں کم از کم تعداد کی ایک مثال کا استعمال کرتے ہیں ہاتھ میں ایک وویک چیک کے طور پر، اگر آپ. تو پہلے فارمولے لاگ بنیاد تھا (ن) کے 2، لیکن اس معاملے میں (ن) ہے. میں (ن) اصل تعداد تھا، یا 8 اصل تعداد کی خاص طور پر. اب یہ ایک تھوڑا سا گیا ہے جبکہ، لیکن میں ہوں خوبصورت اس بات کو یقینی لاگ بنیاد 2 8 3 قدر کی، اور بے شک، کیا اس کے بارے میں اچھی بات ہے 3 کہ اوقات کے بالکل تعداد ہے آپ کو ایک فہرست کی تقسیم کر سکتے ہیں ایک بار پھر، اور پھر لمبائی 8، اور ایک بار پھر، آپ کو چھوڑ رہے ہیں یہاں تک کہ صرف 1 سائز کی فہرست کے ساتھ. ٹھیک ہے؟ 8، 4 جاتا ہے 2 میں چلا جاتا ہے، 1 کو جاتا ہے، اور یہ کہ بالکل اس کا عکاس تصویر ہم صرف ایک لمحے پہلے تھا. تو ایک چھوٹا سا وویک جہاں کے طور پر چیک کریں لاگرتھم اصل ملوث ہے. 

تو اب، اور کیا یہاں شامل ہے؟ (ن). تو ہر کہ محسوس وقت میں، فہرست تقسیم تاریخ میں معکوس ترتیب میں ہی سہی یہاں، میں اب بھی ن باتیں کر رہا تھا. اس ولی قدم کی ضرورت میں، اعداد و شمار میں سے ہر ایک کو چھو میں سلائڈ کرنے کے لئے اس کی مناسب جگہ. تو اگرچہ اس کی اونچائی آریھ، (ن) یا 3 کا سائز لاگ ان ن کی ہے خاص طور پر، دوسرے الفاظ میں، میں یہاں تین ڈویژنوں کیا. کتنا کام میں افقی کیا اس چارٹ ہر وقت کے ساتھ ساتھ؟ 

ویسے، میں ن اقدامات کیا میں نے کیونکہ اگر، کام ، چار عناصر اور چار عناصر ملا اور میں ان کے ساتھ ضم کرنے کے لئے کی ضرورت ہے. میں کے ذریعے جانے کی ضرورت ہے ان چار اور ان چار، بالآخر ان ضم کرنا واپس آٹھ عناصر میں. برعکس تو میں نے آٹھ انگلیوں مل گیا ہے میں نہیں ہے جس میں، یہاں، اور آٹھ fingers-- sorry-- میں ہے تو ، یہاں چار انگلیاں ملا میں، چار انگلیاں ہیں جس یہاں، جس میں کرنا، پھر اس پر ایک ہی ہے مثال کے طور پر پہلے، میں نے ایسا کرتے ہیں تو اگرچہ آٹھ انگلیوں ہے میں، قسم کے، کر سکتے ہیں جس، کل. میں بالکل، یہاں کر سکتے ہیں تو میں یقینی طور پر کر سکتے ہیں ان فہرستوں کے تمام ضم ایک ساتھ مل کر 1 سائز کے. لیکن میں یقینی طور پر دیکھنے کے لئے ہے ہر عنصر میں بالکل ایک بار. تو اس عمل کے عروج، لاگ ان ن ہے اس عمل کی چوڑائی، تو بات کرنے کی تو ہم کیا لگتے، (ن) ہے بالآخر، ہے، حاصل کرنے کے لئے سائز N اوقات کے ایک وقت چل رہا لاگ ان ن. 

دوسرے الفاظ میں، ہم تقسیم فہرست، لاگ ان ن اوقات، لیکن ہم نے کیا ہے ہر وقت، ہم نے عناصر میں سے ہر ایک کو چھونا ان کو ضم کرنے کے لئے سب ایک ساتھ، جس میں قدم ن تو ہم نے (ن) بار لاگ ان ن تھا، یا ایک کمپیوٹر سائنسدان کا کہنا ہے کہ کے طور پر، asymptotically، جس بڑا لفظ ہو جائے گا اوپری کی وضاحت کرنے کے ایک وقت چل رہا پر پابند، ہم نے ایک بڑا O میں چل رہے ہیں لاگ ان ن وقت کی، تو بات کرنے کی. 

اب اس وجہ سے، بہت اہم ہے چلانے اوقات تھے کیا یاد بلبلا طرح، اور انتخاب کے ساتھ ترتیب دیں، اور اندراج کی طرح، اور موجود ہے کہ یہاں تک کہ چند دوسروں، (ن) میں تھے جہاں تھا مربع. اور تم قسم کی، یہاں یہ دیکھ سکتے ہیں. مربع ن تو واضح طور پر (ن) بار ہے (ن)، لیکن یہاں ہم نے (ن) اوقات (ن) لاگ ان کریں، اور ہم نے پہلے ہفتے سے جانتے ہیں صفر، لاگ ان ن، لوگارتمی، کچھ لکیری سے بہتر ہے. سب کے بعد، تصویر کو یاد سرخ اور پیلے رنگ کے ساتھ ہم مبذول کرائی ہے کہ اور سبز لائنز، سبز لوگارتمی لائن بہت کم تھی. اور اس وجہ سے، زیادہ سے زیادہ بہتر اور تیز تر براہ راست پیلے اور سرخ لائنوں کے مقابلے میں، (ن) بار یقینا ہے، (ن) لاگ ان کریں، بہتر (ن) بار سے (ن)، یا ن مربع. 

تو ہم ہے لگ رہے ہو ایک الگورتھم ضم شناخت قسم زیادہ میں چلتا ہے تیزی سے وقت، اور بے شک، یہی وجہ ہے کہ، اس ہفتے کے اوائل، جب ہے ہم بلبلا کے درمیان مقابلہ دیکھا قسم، انتخاب کی طرح، اور ضم قسم، قسم واقعی جیت ضم. اور بے شک، ہم بھی انتظار نہیں کیا بلبلا طرح اور انتخاب کی طرح کے لئے ختم کرنے کے لئے. 

اب ایک دوسرے کے پاس لے اس پر، ایک تھوڑا سا زیادہ سے رسمی طور پر نقطہ نظر، صرف کیس، یہ بہتر گونج کہ اعلی سطح پر بحث کے مقابلے میں. تو یہاں الگورتھم دوبارہ ہے. کی خود سے پوچھنا دو، کیا چل رہا ہے وقت یہ مختلف اقدامات الگورتھم ہے؟ کی پہلی میں تقسیم کرتے ہیں کیس اور دوسری صورت. تو ایسی صورت میں تو اور کچھ، N 2 سے کم ہے تو، صرف واپسی. مسلسل وقت کی طرح محسوس ہوتا ہے. یہ دو قدم کی طرح، قسم کی، ہے، N 2 سے کم ہے تو، اس کے بعد واپس. لیکن ہم نے پیر کو کہا کہ، مسلسل وقت، یا 1 اے بڑے، دو مراحل، تین ہو سکتا ہے اقدامات، یہاں تک کہ 1،000 اقدامات. کیا فرق پڑتا ہے یہ ہے کہ اقدامات کی ایک مسلسل تعداد. تو پیلے رنگ کے pseudocode پر روشنی ڈالی یہاں، ہم اسے فون کروں گا، میں چلتا ہے مسلسل وقت. تو زیادہ رسمی طور پر، اور ہم اس کی ضروریات جا رہے ہیں حد ہو جائے گا جس میں ہم (ن) کے ٹی now-- اس حق کو رسمی طور پر، ایک مسئلہ کی رننگ ٹائم کہ، ان پٹ کے طور N somethings کے لیتا ہے ، ایک اے بڑے برابر N 2 سے کم ہے تو. تو یہ اس پر مشروط ہے. (ن) سے بھی کم ہے تو، صاف ہو جائے کرنے کے لئے 2، اس کے بعد ہم، ایک بہت ہی مختصر فہرست ہے (ن) ہے جہاں چل رہا ہے وقت (ن) کے، ٹی، 1 یا 0، اس بہت ہی خاص صورت میں، یہ صرف مسلسل وقت ہونے جا رہا ہے. یہ ایک لے جا رہا ہے ، جو، دو قدم قدم. یہ اقدامات کی ایک مقررہ تعداد ہے. 

تو رسیلی حصہ ضرور میں ہونا ضروری ہے pseudocode میں دوسری صورت. ورنہ کیس. عناصر کے بائیں نصف ترتیب، دائیں عناصر میں سے نصف، مطابق حصوں کو ضم. ان اقدامات میں سے ہر ایک کے لئے کتنا وقت لگتا ہے؟ ٹھیک ہے، اگر چلانے ن عناصر کو الگ الگ کرنے کے لئے وقت ہے، چلو اس کا بہت بلالے عام، ٹی (ن) کے، پھر بائیں چھنٹائی عناصر میں سے نصف ہے، قسم کی، کہہ طرح، 2 سے تقسیم (ن) کے ٹی، اور اسی طرح حق نصف چھانٹ عناصر میں سے ایک ہے، اس قسم کی، کہہ طرح، (ن) کے ٹی 2 تقسیم، اور پھر کے مطابق حصوں کو ضم. ویسے میں ہے تو کچھ یہاں عناصر کی تعداد، چار، اور کچھ تعداد کی طرح یہاں عناصر کی، چار کی طرح، اور میں ان چار میں سے ہر ایک ضم کرنا پڑے میں، اور ان چار میں سے ہر ایک، ایک میں کے بعد، تاکہ بالآخر میں نے آٹھ عناصر ہیں. یہ اقدامات کو ن اے بڑا ہے کی طرح محسوس ہوتا؟ میں انگلیوں اور میں سے ہر ایک (ن) مل گیا ہے تو ان کی جگہ میں ضم کیا جا کرنے کے لئے ہے، کہ ایک دوسرے ن اقدامات کی طرح ہے. 

تو یقینا formulaically، ہم، اس کا اظہار کر سکتے ہیں سب سے پہلے میں ایک چھوٹا سا میں Scarily سہی نظر، لیکن یہ کچھ ہے کہ بالکل اس منطق قبضہ. وقت چل رہا، ٹی (ن) کے، اگر (ن) یا اس سے زیادہ 2 کے برابر ہے. اس صورت، کسی صورت میں، (ن) کے ٹی ہے 2 سے تقسیم (ن) کے، کے علاوہ ٹی 2 سے تقسیم، علاوہ (ن) کے O بڑی، کچھ اقدامات کی لکیری تعداد، شاید بالکل N، شاید 2 بار (ن)، لیکن یہ تقریبا ن کی ترتیب ہے. تاکہ، بھی، کہ ہم کس طرح کر سکتے ہیں ہے formulaically اس کا اظہار. اب آپ جب تک یہ پتہ نہیں کریں گے آپ، آپ کے دماغ میں یہ درج ہے یا اس کو نظر واپس ایک نصابی کتاب کے، کہ ایک چھوٹا سا ہو سکتا ہے آخر میں شیٹ کو دھوکہ، لیکن یہ، یقینا، کی جا رہی ہے لاگ ان ن ن O ایک بڑی ہمیں دے، تکرار کی وجہ سے آپ کی سکرین پر دیکھ رہے ہیں آپ اصل میں کے ساتھ، اس کے باہر کیا تو مثالوں کے ایک لامتناہی تعداد میں، یا آپ formulaically یہ کیا، تم کروگی ، یہ ہے کہ کو دیکھنے کے اس فارمولے کی وجہ سے خود کی ٹی کے ساتھ، پنراورتی ہے N دائیں کچھ زیادہ، بائیں پر (ن) کے ٹی اور، یہ کر سکتے ہیں اصل میں کا اظہار کیا جا، بالآخر، ن لاگ ان ن کے طور پر بڑے جاؤ. اس بات پر یقین نہیں ہے تو، ہے ، اب کے لئے ٹھیک صرف بے شک، کہ ہے کہ، ایمان پر لے، کہ تکرار کی طرف جاتا ہے کیا، لیکن یہ ایک کا صرف تھوڑا سا زیادہ ہے تلاش کرنے کے لئے ریاضی کے نقطہ نظر ضم طرح کی رننگ ٹائم میں اکیلے اس کے pseudocode پر مبنی. 

اب ایک کا تھوڑا سا لے اس کا سب سے سانس، اور ایک پر ایک نظر ڈالیں بعض سابق سینیٹر، جو ایک چھوٹا سا واقف نظر ہو سکتا ہے، جو گوگل کی ایرک کے ساتھ بیٹھ گیا ایک انٹرویو کے لئے کچھ وقت پہلے شمٹ،، اسٹیج پر، ایک پوری چڑھانے کے سامنے لوگوں کے، بالآخر کے بارے میں بات ایک موضوع، کہ بہت اب واقف ہے. چلو ایک نظر ڈالیں. 

ایرک شمٹ: اب سینیٹر، آپ گوگل میں یہاں ہو اور میں سوچنے کے لئے پسند ایک کام کے انٹرویو کے طور پر صدارت. اب یہ صدر کے طور پر ایک ملازمت حاصل کرنے کے لئے مشکل ہے. صدر اوباما: ٹھیک ہے. ایرک شمٹ اور تم اب [اشراوی] کیا کرنے جا. یہ گوگل میں ایک ملازمت حاصل کرنے کے لئے بھی مشکل ہے. صدر اوباما: ٹھیک ہے. 

ایرک شمٹ: ہم سوالات ہیں، اور ہم نے اپنے امیدواروں سے سوالات پوچھتے ہیں، اور یہ ایک لیری Schwimmer کی طرف سے ہے. 

صدر اوباما: ٹھیک ہے. 

ایرک شمٹ: کیا؟ تم لوگوں کو میں مذاق کر رہا ہوں؟ یہ یہیں ہے. سب سے زیادہ موثر طریقے سے کیا ہے ایک ملین 32 بٹ integers کے الگ الگ؟ 

صدر اوباما: Well-- ایرک شمٹ: کبھی کبھی، شاید میں معافی چاہتا ہوں، maybe-- صدر اوباما: نہیں، نہیں، نہیں، نہیں، نہیں، میں think-- ایرک شمٹ کہ اندازہ لگانے والے نہیں ہے صدر اوباما: میں لگتا ہے، میں بلبلا لگتا قسم جانا غلط طریقہ ہو گا. ایرک شمٹ: چلو. اسے یہ بتایا؟ ٹھیک ہے. میں نے کمپیوٹر سائنس نہیں کیا on-- 

صدر اوباما: ہمہے. وہاں میں اپنے جاسوس ہے. پروفیسر: ٹھیک. اب ہمارے پیچھے چھوڑ دو یلگوردمز کی نظریاتی دنیا asymptotic تجزیہ میں اس، اور کچھ موضوعات پر واپس ہفتے صفر اور ایک، اور شروع سے کچھ تربیت پہیوں دور کرنے کے لئے، اگر آپ. تم واقعی سمجھتے ہیں کہ تو بالآخر زمین سے، کیا ہے ، جب آپ ہڈ کے نیچے جا ، لکھنا، مرتب، اور پروگرام پر عمل. یہ تھا کہ، خاص طور پر یاد کرتے ہیں ہم نے دیکھا پہلی سی کے پروگرام، ایک وہیت، سادہ پروگرام قسم کے، نسبتا بول، جس، یہ، ہیلو دنیا پرنٹ. اور میں عمل، نے کہا کہ یاد کہ منبع کوڈ سے گزرتا ہے بالکل یہ ہے. آپ کے منبع کوڈ لے، منتقل یہ ایک سنکلک کے ذریعے، بجنا طرح، اور باہر کہ، اعتراض کوڈ آتا ہے اس، zeros اور ہیں کی طرح نظر ہو سکتا ہے کمپیوٹر کے سی پی یو، مرکزی ہے کہ پروسیسنگ یونٹ یا دماغ، بالآخر سمجھتا. 

یہ ایک ہے کہ باہر کر دیتا ہے ایک oversimplification کے تھوڑا سا، ہم میں ہیں پوزیشن کے علاوہ چڑھانا واقعی رہا ہے سمجھنے کے لئے ہڈ کے نیچے جا آپ کو چلانے کے ہر وقت بجنا، یا اس سے زیادہ عام طور پر، ہر وقت آپ کو ایک پروگرام بنانے بنائیں اور سییف 50 IDE کا استعمال کرتے ہوئے. خاص طور پر، سامان کی طرح یہ پہلا، پیدا کیا جاتا ہے جب آپ سب سے پہلے اپنے پروگرام مرتب. دوسرے الفاظ میں، جب آپ آپ کے منبع کوڈ لے اور جو سب سے پہلے ہے، اسے مرتب بجنا کی طرف سے outputted کیا جا رہا ہے اسمبلی کوڈ کے طور پر جانا جاتا ہے کچھ ہے. اور حقیقت میں، یہ بالکل اس طرح لگ رہا ہے. 

میں ایک کمانڈ بھاگ گیا پہلے کمانڈ لائن. بجنا ڈیش دارالحکومت ے hello.c کے، اور یہ ایک فائل پیدا مجھے بلایا hello.s یہ کے لئے، جس کے اندر بالکل تھے ان مواد، اور ایک چھوٹا سا زیادہ اوپر اور نیچے ایک چھوٹا سا، لیکن میں juiciest ڈال دیا ہے یہاں کی سکرین پر کے بارے میں معلومات. آپ کو قریب سے نظر آتے ہیں تو، آپ کو نظر آئے گا کم از کم چند واقف مطلوبہ الفاظ. ہم سب سے اوپر اہم ہے. ہم مشرق میں printf کا ہے. اور ہم بھی دنیا کے خوش ہیں نیچے واوین میں (ن). 

یہاں میں کسی اور سب کچھ بہت کم سطح ہدایات ہے کمپیوٹر کے سی پی یو سمجھتا ہے. میموری منتقل CPU ہدایات کے ارد گرد، میموری کی طرف سے بوجھ ڈور، اور بالآخر، پرنٹ سکرین پر چیزوں. اب اس کے بعد اگرچہ ہوتا اس اسمبلی کوڈ پیدا کیا جاتا ہے؟ آخر، آپ بے شک، کرتے، اب بھی اعتراض کے کوڈ پیدا. لیکن اقدامات واقعی ہے کہ ہڈ کے نیچے چل رہا اس طرح ایک چھوٹا سا زیادہ نظر آتے ہیں. ماخذ کوڈ، اسمبلی کوڈ بن جاتا ہے جو اس کے بعد اعتراض کوڈ بن جاتا ہے، اور یہاں آپریٹو الفاظ ہیں، کہ آپ کے منبع کوڈ مرتب جب، باہر تو اسمبلی کوڈ، اور آتا ہے آپ کو آپ کی اسمبلی کا کوڈ جمع جب، باہر آبجیکٹ کوڈ آتا ہے. 

اب بجنا، سپر بہتر ہے مرتب کی ایک بہت کی طرح، اور یہ ان اقدامات کے تمام کرتا ہے ایک دوسرے کے ساتھ، اور یہ ضروری نہیں کرتا پیداوار کسی بھی انٹرمیڈیٹ آپ کو بھی دیکھ سکتے ہیں کہ فائلوں. یہ صرف چیزوں سے آگاہ کریں، جو عام اصطلاح ہے کہ اس پورے عمل کی وضاحت. لیکن اگر آپ واقعی چاہتے ہیں تو خاص طور پر ہونا، وہاں ہے ایک سے زیادہ بہت کے ساتھ ساتھ وہاں پر جا. 

لیکن یہ بھی ہے کہ اب بھی غور کریں کہ سپر سادہ پروگرام، hello.c کے، ایک تقریب میں بلایا. یہ printf کہا. لیکن میں، یقینا، printf کا نہیں لکھا تھا کہ اس سے بات کرنے، C کے ساتھ آتا. یہ ہے کہ ایک تقریب یاد ہے معیاری io.h، میں اعلان کیا جس میں ایک ہیڈر فائل، ہے جو ایک موضوع ہم واقعی گے ہے طویل عرصے سے پہلے زیادہ گہرائی میں کودو. لیکن ایک ہیڈر فائل ہے عام طور پر ان کے ہمراہ ایک کوڈ فائل، منبع کوڈ فائل، اس کی طرف سے معیاری io.h. موجود زیادہ کی طرح 

کچھ دیر پہلے، کسی، یا کسی، یہ بھی لکھا میں، سٹینڈرڈ io.c نامی ایک فائل جو اصل کی تعریف، یا printf کا نفاذ، اور دیگر افعال کے bunches، اصل میں لکھا جاتا ہے. ہم پر غور تو، کہ دیا یہاں چھوڑ، hello.c کے پر، کہ جب مرتب، یہاں تک کہ اگر، hello.s یہ ہمیں دیتا ہے بجنا ایک جگہ میں بچت کی زحمت نہیں کرتا ہم اسے دیکھ، اور یہ کہ اسمبلی کوڈ کر سکتے ہیں hello.o، میں جمع ہو جاتا ہے جس ، بے شک، پہلے سے طے شدہ نام ہے آپ ماخذ مرتب جب دی اعتراض کے کوڈ میں کوڈ، لیکن نہیں ہیں ابھی تک اس پر عمل کرنے کے لئے بہت تیار، ایک اور قدم ہے کیونکہ ایسا کرنے کے لئے ہے، اور ہے گزشتہ چند کے لئے ہو رہا ہفتے، آپ کو شاید شاید نہ جانتے ہوں. 

خاص طور پر کہیں CS50 IDE میں، اور یہ بھی، ایک کا تھوڑا سا ہو جائے گا ایک لمحے کے لئے سہل، وہاں ہے، یا ایک وقت پر تھا، سٹینڈرڈ io.c نامی ایک فائل، کسی میں مرتب ہے کہ سٹینڈرڈ io.s یا مساوی، اگر کسی کو جمع کیا ہے کہ سٹینڈرڈ io.o میں، یا یہ ایک میں باہر کر دیتا ہے تھوڑا سا مختلف فائل ایک مختلف ہو سکتا ہے کہ شکل مکمل طور پر توسیع فائل، اصول میں اور conceptually، بالکل لیکن ان اقدامات پر کسی نہ کسی شکل میں ہو کرنے کے لئے تھا. ، کا کہنا ہے کہ اب اس کے لئے ہے جو میں نے ایک پروگرام لکھ رہا ہوں جب، hello.c کے، صرف کا کہنا ہے کہ، ہیلو دنیا، اور میں کسی اور کی کوڈ استعمال کر رہا ہوں ایک صلی اللہ علیہ وسلم ایک بار تھا جس printf، طرح وقت، سٹینڈرڈ io.c نامی ایک فائل میں، پھر کسی نہ کسی طرح میں نے اپنے لینے کے لئے ہے آبجیکٹ کوڈ، میری zeros اور ہیں، اور اس شخص کی چیز کوڈ، یا zeros اور ہیں، اور کسی نہ کسی طرح میں ان کے ساتھ منسلک کہ، خوش نامی ایک حتمی فائل، ہے zeros کی سب میرا بنیادی تقریب سے ہیں، اور zeros کے تمام اور printf کے لئے ہیں. 

اور بے شک، کہ گزشتہ عمل ہے کہا جاتا ہے، آپ کے اعتراض کے کوڈ منسلک. پیداوار جن میں ایک executable فائل ہے. تو جانبداری میں، میں دن، کچھ بھی نہیں کے اختتام ایک ہفتے کے بعد سے تبدیل کر دیا گیا، جب ہم پہلا پروگرام مرتب کرنا شروع کر دیا. بے شک، اس کے تمام دیا گیا ہے ہڈ کے نیچے ہو رہا، لیکن اب ہم ایک کی پوزیشن میں ہیں جہاں ہم اصل میں کر سکتے ہیں ان مختلف اقدامات کے علاوہ چڑھاو. اور بے شک، آخر میں دن کی، ہم اب بھی ہیں zeros اور ہیں، کے ساتھ چھوڑ دیا ہے جس ایک عظیم segue کا اب اصل ہے سی کی ایک اور صلاحیت، کہ ہم سب سے زیادہ ہونے کا امکان بیعانہ نہیں ہے آج کی تاریخ میں، bitwise آپریٹرز کے طور پر جانا جاتا ہے. دوسرے الفاظ میں، اس طرح اب تک، کسی بھی وقت ہم نے C میں C یا متغیر میں اعداد و شمار کے ساتھ نمٹا، ہم جیسے چیزوں پڑا ہے حروف اور floats اور انز اور چاہتا اور ڈبلز اور اس طرح، لیکن ان میں سے سب کم از کم آٹھ بٹس ہیں. ہم ابھی تک کرنے کے قابل کبھی نہیں کیا ہے انفرادی بٹس جوڑتوڑ، یہاں تک کہ ایک انفرادی سا اگرچہ، ہم ، 0 اور 1 کی نمائندگی کر سکتے ہیں. اب یہ C میں پتہ چلا ہے کہ، آپ انفرادی بٹس تک رسائی حاصل کر سکتے ہیں، آپ نحو جانتے ہیں تو، جس کے ساتھ ان پر حاصل کرنے کے لئے. 

تو ایک نظر ڈالیں bitwise آپریٹرز میں. تو یہاں تصویر چند علامات ہیں کہ ہم اس قسم کی، قسم کی، پہلے دیکھا ہے. میں، ایک عمودی ایک ایمپرسینڈ دیکھیں بار، اور اس کے ساتھ ساتھ کچھ دوسروں، اور یہ کہ ایمپرسینڈ ایمپرسینڈ یاد ہم نے پہلے دیکھا ہے کچھ ہے. ہے جہاں آپ منطقی اور آپریٹر، ان میں سے دو کے ساتھ مل کر، یا منطقی یا آپریٹر، تم کہاں دو عمودی سلاخوں ہے. Bitwise آپریٹرز، جو ہم کریں گے ، انفرادی بٹس پر کام دیکھیں صرف ایک ایمپرسینڈ استعمال، ایک ایک عمودی بار، جزم کی علامت اگلے، تھوڑا آتا ہے ٹلڈا، اور پھر چھوڑ دیا بریکٹ چھوڑ دیا، یا دایاں بریکٹ دایاں بریکٹ. ان میں سے ہر ایک مختلف معنی ہے. 

اصل میں، ایک نظر ڈالیں. کے پرانے اسکول آج، اور استعمال جانے دو پرانے سے ایک ٹچ اسکرین، ایک سفید بورڈ کے طور پر جانا جاتا ہے. یہ سفید بورڈ ہمیں اجازت دینے کے لئے کی جا رہی ہے کچھ کافی سادہ علامات کا اظہار کرنے، یا بلکہ کچھ کافی سادہ فارمولوں، کہ ہم بالآخر اس کے بعد کر سکتے ہیں بیعانہ، ترتیب میں انفرادی رسائی کے لئے ایک سی پروگرام کے اندر اندر بٹس. دوسرے الفاظ میں، یہ کرتے ہیں. ایک کے لئے چلو پہلی بات ایمپرسینڈ کے بارے میں لمحے، جو bitwise AND آپریٹر ہے. دوسرے الفاظ میں، یہ ہے اجازت دیتا ہے کہ ایک آپریٹر مجھے ایک بائیں ہاتھ تغیر پذیر ہیں کرنا عام طور پر، اور ایک دائیں ہاتھ متغیر، یا ایک انفرادی طور پر قیمت، کہ اگر ہم اور ان کے ساتھ، مجھے ایک حتمی نتیجہ دیتا ہے. تو میں کیا مطلب ہے؟ ایک پروگرام میں، آپ کو ایک متغیر ہے، تو ان اقدار کی دکانوں ہے کہ، یا کی یہ آسان رکھنے کے، اور صرف دو انفرادی طور پر zeros اور لکھنے، ایمپرسینڈ آپریٹر کیسے کام کرتا ہے یہاں ہے. 0 ایمپرسینڈ 0 0 کے برابر کی جا رہی ہے. اب کیوں ہے؟ 

یہ کرنے کے لئے بہت ملتا جلتا ہے بولین اظہار، کہ ہم اس طرح اب تک بات چیت کی ہے. آپ سب کے بعد لگتا ہے، 0 ہے جھوٹے، 0، جھوٹے جھوٹے اور باطل ہے ہم بات چیت کی ہے کے طور پر، منطقی طور پر، بھی جھوٹے. تو ہم اس کے ساتھ ساتھ یہاں 0 حاصل. 0 ایمپرسینڈ لے تو 1، کے ساتھ ساتھ اس، بھی، کیونکہ اس کے لئے، 0 ہونے جا رہا ہے بائیں ہاتھ اظہار، صحیح یا 1 ہونا یہ سچ اور سچ ہونے کی ضرورت ہو گی. لیکن یہاں ہم جھوٹے ہیں اور سچ، یا 0 اور 1. اب ایک بار پھر، ہم 1 ایمپرسینڈ ہے 0،، بھی، 0 ہونے جا رہا ہے کہ، اور ہم 1 ایمپرسینڈ 1 ہے تو، آخر میں ہم ایک 1 سا ہے. تو دوسرے الفاظ میں، ہم نہیں کر رہے ہیں اس آپریٹر کے ساتھ دلچسپ کچھ ابھی تک، اس ایمپرسینڈ آپریٹر. یہ bitwise AND آپریٹر ہے. لیکن یہ اجزاء ہیں جس کے ذریعے ہم کر سکتے ہیں ہم جلد ہی دیکھیں گے کے طور پر دلچسپ چیزیں،. 

اب صرف ایک دیکھو یہیں پر ختم عمودی بار. میں 0 سا اور میں نے تو یا اس کے ساتھ، bitwise OR آپریٹر، ایک 0 بٹ، کہ مجھ 0 دینے جا رہا ہے. میں 0 بٹ اور یا اس کے ساتھ لے تو 1 بٹ، تو میں 1 حاصل کرنے کے لئے جا رہا ہوں. اور حقیقت میں، صرف کے لئے واضح طور پر،، مجھے واپس جانے دو تاکہ میری عمودی سلاخوں 1 کے لئے غلطی نہیں کر رہے ہیں. میرے تمام کو دوبارہ سے لکھنا چلو میرے 1 ایک چھوٹا سا زیادہ ہے میں تو واضح طور پر، تاکہ ہم اگلے، دیکھیں 1 یا 0، کہ ایک 1 جا رہا ہے ہے، اور میں 1 یا 1 ہے کہ ایک ہے، بھی، ایک 1 بننے جا رہی ہے. تو آپ کو منطقی طور پر دیکھیں کہ کر سکتے ہیں آپریٹر بہت مختلف برتاؤ کرتی ہے. ، یہ 0 مجھے دیتا ہے یا 0 مجھ 0 دیتا ہے لیکن ہر دوسرے مجموعہ مجھ 1 دیتا ہے. جب تک میں ایک 1 ہے کے طور پر فارمولا، نتیجہ 1 جا رہا ہے. 

اور اس کے ساتھ اس کے برعکس آپریٹر، ایمپرسینڈ، میں دو 1 کی ہے صرف اس صورت میں مساوات، میں اصل میں ایک 1 باہر حاصل کرتے ہیں. اب چند دیگر موجود ہے آپریٹرز کے ساتھ ساتھ. ان میں سے ایک چھوٹا سا زیادہ ملوث ہے. تو مجھے آگے بڑھو اور مٹانے دو یہ کچھ جگہ کو آزاد کرنے. اور چلو پر ایک نظر ڈالیں صرف ایک لمحے کے لئے جزم کی علامت،. یہ عام طور پر ایک ہے کردار آپ کو ٹائپ کر سکتے ہیں اپنے کی بورڈ انعقاد شفٹ اور اپنے امریکی اوپر نمبروں کی پھر ایک کی بورڈ. 

لہذا اس خصوصی ہے OR آپریٹر، خصوصی یا. تو ہم صرف OR آپریٹر دیکھا. یہ خصوصی یا آپریٹر ہے. اصل میں کیا فرق ہے؟ ویسے صرف فارمولا دیکھو، اور بالآخر اجزاء کے طور پر اس کا استعمال. 0 XOR 0. میں کہنے جا رہا ہوں ہمیشہ 0. اس XOR کی تعریف ہے. 0 XOR 1 1 جا رہا ہے. 1 XOR 0، 1 جا رہا ہے اور 1 1 XOR جا رہا ہے؟ غلط؟ یا ٹھیک ہے؟ مجھ نہیں پتہ. 0. اب کیا ہو رہا ہے یہاں ہے؟ ویسے کے بارے میں سوچنا اس آپریٹر کا نام. خصوصی یا، تو کے طور پر نام، قسم کے،، سے پتہ چلتا ہے جواب صرف کی جا رہی ہے 1 آدانوں خصوصی ہیں، خصوصی طور پر مختلف. تو یہاں آدانوں ہیں اسی، تو پیداوار 0 ہے. یہاں آدانوں ہیں اسی، تو پیداوار 0 ہے. یہاں نتائج وہ مختلف ہیں خصوصی ہیں، اور اس کی پیداوار 1. تو اس کے لئے بہت ملتا جلتا ہے اور، یہ بہت اسی طرح کی ہے یا بلکہ اس سے بہت ملتا جلتا ہے یا، لیکن صرف ایک خصوصی انداز میں. یہ ایک، اب کوئی ایک ہے 1 ہم دو 1 ہے کیونکہ، اور خاص طور پر، ان میں سے صرف ایک. بالکل ٹھیک. دوسروں کا کیا؟ ویسے ٹلڈا، دریں اثنا، ہے اصل میں اچھا اور آسان، شکر ہے. اور یہ ایک یک رکنی ہے جس کا مطلب ہے آپریٹر، یہ صرف ایک ان پٹ پر لاگو کیا ہے ایک اوپیرانڈ، تو بات کرنے کی. ایک بائیں اور حق. دوسرے الفاظ میں، آپ کے ٹلڈا لے تو 0، جواب برعکس ہو جائے گا. اور آپ 1 کی ٹلڈا لے تو، جواب اس کے برعکس ہو جائے گا. تو ٹلڈا آپریٹر ہے تھوڑا سا نفی کا ایک طریقہ، یا سے تھوڑا flipping کی 0 1، یا 0 1. 

اور یہ کہ آخر میں ہمیں چھوڑ دیتا ہے صرف دو فائنل آپریٹرز کے ساتھ، بائیں شفٹ نام نہاد، اور صحیح شفٹ آپریٹر نام نہاد. کی کس طرح ان کے کام کی جگہ پر ایک نظر ڈالیں. لکھا بائیں شفٹ آپریٹر، اس طرح دو زاویہ بریکٹ کے ساتھ، مندرجہ ذیل کے طور پر چلاتا ہے. تو بائیں میرے ان پٹ، یا میرے اوپیرانڈ، شفٹ آپریٹر کافی صرف ایک 1 ہے. اور اگر کمپیوٹر کو بتا 1، سات مقامات کا کہنا ہے کہ تبدیلی چھوڑ، نتیجہ میں اگرچہ کے طور پر ہے 1 لے، اور اسے منتقل سے زیادہ سات مقامات بائیں، اور ڈیفالٹ کی طرف، ہم فرض ہے کہ جا رہے ہیں درست کرنے کے لئے جگہ سے zeros کے ساتھ بولڈ کیا جا رہا ہے. دوسرے الفاظ میں، 1 تبدیلی 7 جا رہا ہے چھوڑ دیا بعد، 1 کہ مجھے دینے کے لئے 1، 2، 3، 4، 5، 6، 7 سے zeros. ایک طرح سے تو، اس کے لئے آپ کی اجازت دیتا ہے 1 کی طرح ایک چھوٹی سی تعداد لے، اور واضح طور پر زیادہ سے زیادہ بنانے کے اس طرح بہت بڑا، بہت، لیکن ہم اصل میں دیکھنے جا رہے ہیں اس کے لئے زیادہ ہوشیار نقطہ نظر بجائے، اس کے ساتھ ساتھ، 

بالکل ٹھیک. اس ہفتے تین کے لئے ہے. ہم آپ کو اگلی بار دیکھیں گے. یہ CS50 تھا. 

[موسیقی بجانے] 

اسپیکر 1: وہ ناشتا میں تھا ایک گرم Fudge کی کے Sundae کھانے روکتے. انہوں نے کہا کہ اس کے چہرے پر یہ سب تھا. انہوں نے کہا کہ داڑھی طرح کہ چاکلیٹ پہنے ہوئے ہے اسپیکر 2: تم کیا کر رہے ہو؟ سپیکر 3: ہاں؟ کیا؟ 

اسپیکر 2: آپ کو صرف ڈبل ڈپ تھا؟ آپ ڈبل چپ ڈوبا. سپیکر 3: معاف کیجئے گا. اسپیکر 2: تم، چپ ڈوبا ایک ٹکڑا لیا، اور آپ کو دوبارہ ڈوبا. 3 اسپیکر: اسپیکر 2: کہ ڈال کی طرح ہے تو ڈپ میں اپنے پورے منہ کا حق. اگلی بار آپ کو ایک چپ لے صرف ایک بار ڈپ، اور اسے ختم. 

سپیکر 3: آپ، ڈین پتہ ہے کیا؟ آپ ڈپ کرنا چاہتے ہیں اس طرح ڈپ. میں ڈپ کرنا چاہتے ہیں اس طرح ڈپ گا.