[МУЗЫКА ГУЛЯЕ] СПІКЕР 1: Добра, гэта CS50, і гэта пачатак чацвёртай тыдні, і як вы, магчыма, чулі, ці чытаць, свет быў канец. Хто ідзе ўсё вакол інтэрнэту была ведаў і дасведчанасці за памылкі ў праграму, Мова праграмавання называецца Bash. Гэта было цудоўна фірмовых як Shellshock, або Баш дзверы, але такія артыкулы, як гэта не былі рэдкасцю. І на самай справе, многія з іх прыносяць ўспаміны пра Heartbleed, якія вы, магчыма, заўважылі ў націсніце назад вясной гэтага года, якая было гэтак жа даволі драматычна. Зараз з тых з вас, тут сёння, як многія з вас, нават калі вы не разумееце, што гэта ўсё аб, чулі пра Shellshock? Добра, і як многія з вас ёсць кампутары, якія ўразлівыя? ОК, не павінна быць значна, значна больш рук прама зараз, па прычынах, мы ўбачым. Давайце зірнем на тое, што што адбываецца ў сродках масавай інфармацыі а затым растлумачыць яго крыху тут для нас тэхнічна. СПІКЕР 2: Эксперты па бяспецы маюць папярэдзіў, што сур'ёзны недахоп мог каля паўплываць сотні мільёны карыстальнікаў у свеце вэб. Так што ж такое памылка, было назву Shellshock, і для чаго гэта трэба? Ну, Shellshock таксама вядомы як Bash памылка, праграмнае забеспячэнне яна выкарыстоўвае. Хакеры выкарыстаюць вірус для сканавання ўразлівыя сістэмы, якія працуюць Linux і Unix аперацыйных сістэм, а затым заразіць іх. Bash з'яўляецца абалонкай каманднага радка. Гэта дазваляе каманд пытанне карыстальнікам запусціць праграмы і функцый у рамках праграмнага забеспячэння набраўшы ў тэксце. Гэта, як правіла, выкарыстоўваецца праграмістамі, і не павінны быць адкрыты для больш шырокага свету, хоць Shellshock змяняе, што. Ну, worringly, некаторыя аналітыкі папярэдзіць гэта можа быць вялікая пагроза, таму Shellshock дазваляе поўнае кантроль заражанай машыны, у той час як Heartbleed дапускаецца толькі хакеры, каб шпіёніць за кампутарамі. Гэта настолькі сур'ёзна, што гэта быў ацэнены ў 10 з 10 для цяжару Нацыянальным Ўразлівасць База дадзеных. 2/3 з усіх вэб-сервераў, па меншай рызыка, у тым ліку некаторых кампутарах Mac. Ну, пераканайцеся, што вы залатаць свае сістэмы цяпер. Любы хостынг вэб-сайт працуе пацярпелыя аперацыйныя сістэмы варта прыняць меры як мага хутчэй. Любы, хто можа дазволіць сабе гэта павінна выглядаць да іх прымянення маніторынгу і вэб- брандмаўэр, каб выглядваць любых нападаў. СПІКЕР 3: Горшая рэч што можа здарыцца, што хто б напісаць код, які будзе аўтаматычна ісці і сканаванне Інтэрнэт і паўплывае усе гэтыя кампутары. І як толькі яны робяць, што, ну, самае горшае, што яны маглі зрабіць проста выдаліць усе, або зачыніць сайты ўніз. Такім чынам, мы маглі бачыць пашкоджанні з гэтага пункту гледжання, дзе мы павінны былі б зламыснікам якія проста вырашылі выклікаць хаос шляхам прыцягнення сістэмы ўніз або выдаленне файлы, і таму падобныя рэчы. СПІКЕР 2: Некаторыя кажуць, што гэта адзін з самых цяжка вымераць памылкі ў гады, і гэта можа заняць некалькі тыдняў ці нават месяцаў, каб вызначыць яго канчатковае ўздзеянне. СПІКЕР 1: Так усё гэта праўда, але самае смешнае, амаль усе з вобразаў вы толькі што бачылі, для магчыма клавіятуры выключэннем, не мае нічога агульнага з памылка наогул. Серверы і драты і гэтак далей, яна як бы ўскоснае стаўленне, але ў асноўным гэта на самай справе даволі знаёмыя, што адбываецца тут. На самай справе, мяне адпусцілі ў наша CS50 прыбор. Дазвольце мне ісці наперад і максімальна акно тэрмінала тут. І вы, хлопцы ўжо выкарыстоўваюць гэта, ці ўбудаванага іх версіі, у Gedit для таго, каб пісаць праграмы, ўводзіць каманды, і гэтак далей, і гэта на самай справе, і мае быў на працягу многіх тыдняў, Bash B-A-S-H. Гэта Bourne-Again Shell, , Які з'яўляецца проста мудрагелісты спосаб сказаць, гэта праграма, якая мае міргаць хутка, эфектыўна, што сядзіць там чакае для ўводу для Вас. І гэта каманда лінейны інтэрфейс, праз які вы, хлопцы, былі выканання каманд і у канчатковым рахунку, кампіляцыі і затым працуе праграмы. Але Bash таксама праграмаванне мова ў наступным сэнсе. Вы ведаеце, што ёсць каманды, як кд і Ls, а таксама ляск і іншыя, але вы можаце вызначыць свае ўласныя каманды шляхам ўкаранення іх у Bash. Цяпер мы не збіраемся ўдавацца ў падрабязнасці як біць мова праграмавання, але ведаем, напрыклад, што на дадзены момант, няма каманды называецца "прывітанне". Такім чынам, можна знайсці ў адзін з гэтых пакетаў. Гэта не ўстаноўлены на маім кампутары. Звяртайцеся да адміністратара. Але калі я хачу, каб праграма называецца "прывітанне" у Bash або ў маім запрашэнні, Я магу на самой справе выкарыстаць сінтаксіс вось зусім як C. Гэта не зусім тое ж самае, але гэта выглядае вельмі падобна на Функцыя, хоць адсутнічаюць некаторыя дэталі. Нішто, здаецца, адбудзецца, але цяпер, калі я друкую "прывітанне", Вы можаце на самой справе пісаць Праграма, не ў C, не ў Java, не ў іншым праграмавання мову, але і ў самой Bash. Цяпер Ключавым момантам тут з'яўляецца тое, што я напісаў назваць я хацеў даць гэты новы каманду, і дужкі таксама Сімвалічна гэта з'яўляецца функцыяй. Як у баку, вы таксама можаце зрабіць задавальненне рэчы, і на самай справе, нават на Mac OS, гэта праграма пад назвай Terminal. Ён пастаўляецца убудаваная ў нічые кампутар, які мае Mac у гэтым пакоі, і вы можаце зрабіць тое ж самае ў Mac АС, але вы можаце пайсці больш за што. І гэта крыху па датычнай, але гэта пацешна. Мне нагадалі сёння раніцай, калі думаючы, што гэта праз, маленькай гульні я гуляў з адным з былых TFs CS50 ў прычым у любы час ён будзе хадзіць ад яго клавіятура з яго экрана адмыкнутая, Я выконваю б каманду як это-- "павітацца". І зараз у любы час ён вярнуўся да свайго Клавіятура пасля таго як я ачысьціў экран і ён сядаў, паспрабуйце зрабіць некаторую працу, спіс змесціва яго directory-- [АЎДЫЁ Прайграванне] -Добры. Добры дзень. СПІКЕР 1: Так, справядлівасці дзеля, гэта не было на самай справе "прывітанне". Гэта, як правіла, было нешта больш падобна на that-- [АЎДЫЁ Прайграванне] -Beep. СПІКЕР 1: --that я would-- так што яго кампутар будзе збэшчаны любы час ён фактычна сеў за клавіятуру. І вельмі хутка ён зразумеў, не пакідаць яго экран адмыкнутая. Але гэта кажа пра тое дурнога весялосці, што вам можа мець нешта накшталт Bash. Але гэта крыху больш сур'ёзна, каб быць упэўненым, чым гэта. І на самай справе, гэта адзін з большасць небяспечныя і працяглыя памылкі што сапраўды трапіў у свет ва ўсім свеце. Гэтая памылка была вакол каля 20 гадоў, і вы будзеце здзіўлены ў проста момант па сваёй адноснай прастаце. Так што гэта прадстаўнік камандаваць, што калі вас валодаць Mac, літаральна прама зараз калі ў вас ёсць вечка адкрыта, Вы можаце паспрабаваць ўвесці ў тым, што Праграма называецца Тэрмінал. Тэрмінал знаходзіцца пад Прыкладання Utilities-- на гэты раз, карыстальнікі Windows, не павінны турбавацца аб дадзеным threat-- але тыя з вас з Macs можаце ўвесці гэта ў акно, як я зраблю тут, і калі вы увядзіце што ў гэтую праграму называецца Тэрмінал, як я зраблю зараз, калі вы бачыце слова "уразлівымі" Ваш кампутар уразлівымі для эксплуатацыі. Цяпер што ж гэта на самай справе азначае? І гэта праўда, некаторыя даволі вар'ятам сінтаксіс, але давайце хоць бы выцягнуць некаторыя цікавыя аспекты. Такім чынам, ёсць некаторыя сінтаксіс, які выглядае крыху знаёмыя, па меншай меры, ад C і праграмавання ў цэлым. Я бачу некаторыя дужкі, коскі, фігурныя дужкі, і такія, але аказваецца, што гэта па-дурному тут у жоўты , Па сутнасці, з'яўляецца функцыяй што нічога не робіць. Сродкі тоўстай кішкі нічога не рабіць, а Кропка з коскі азначае спыніць, нічога не робячы. Так ўнутры іх Фігурныя дужкі, той факт, што ў мяне ёсць роўная падпісаць налева, гэта з'яўляецца па сутнасці ствараючы Каманда, або пераменная, называецца х, і прысвойваем яго што жоўты кавалак кода там. Гэта можа быць нешта накшталт "рэха прывітанне "ці" сказаць сігнал "ці што-то падобна таму, што. Але звярніце ўвагу, калі вашы вочы блукаць далей направа, ёсць больш да гэтай лініі, чым проста канец гэтай коскі. "Эхо ўразлівыя", а затым акрамя таго, ёсць яшчэ больш. Іншы коскі, Баш -c:. Так карацей кажучы, гэты радок кода з'яўляецца дастаткова для пераканаўчых Кампутар гэта ўразлівыя для рабіць нешта што вы ад яго хочаце, таму што ёсць памылка ў Bash якой хоць Bash павінен быў спыніць Чытанне радкоў з каманднага правы там пасля жоўтым тэкстам, для 20-плюс-гадовага памылкі, Bash фактычна чытаў за межамі гэтага коскі і даволі шмат робіць тое, што ён сказаў. Так у чым жа падтэкст таго, што ў канчатковым выніку? Я проста сказаў, што "рэха прывітанне" або "рэха ўразлівыя," але тое, што калі вы зрабілі нешта на самай справе злая, як РМ-РФ *, якія вы не маглі б калі-небудзь ўвялі раней, і, шчыра кажучы, вы, верагодна, не павінны занадта рана, таму што вы можаце зрабіць Вялікую шкоду з ім. Чаму? ГТ робіць што, вядома? Выдаляе. * Ці азначае, што? Ўсё. Так што гэта так званы дзікая карта, так гэта азначае, выдаліць усе, што ў бягучы каталог. -r адбываецца з выгляду рэкурсіўны, што азначае, калі тое, што вы выдаляеце з'яўляецца каталогам, і ўнутры ёсць з'яўляецца іншыя файлы і іншыя каталогі, рэкурсіўна пагрузіцца ў там і выдаліць усё, што. І -f з'яўляецца горшым з усіх. Кожны ведае, што -f азначае тут? Force. Так прымусіць сродкі, нават калі гэта дрэнная ідэя, зрабіць гэта, не пытаючыся мяне для далейшага пацверджання. Такім чынам, вы ведаеце, мы смяемся над гэта, але, шчыра кажучы, я, верагодна, увядзіце гэта некалькі разоў у дзень, так як у рэчаіснасці гэта самы хуткі спосаб, каб выдаліць цэлую кучу рэчаў. Але нават я зрабіў некаторыя пашкоджанні. Але калі б вы былі, каб падмануць кампутар у вызначэнні некаторы дурное зменную ці функцыя называецца х, але тады падманваючы кампутар у выкананні за межы, што Функцыя, за гэтай кропкай з коскі, Вы сапраўды можа падмануць кампутар у выкананні то як РМ-РФ або каманда E-mail або каманда Капіяваць. Усё, што літаральна можна зрабіць з кампутар, няхай гэта будзе выдаленне файлаў, стварэнне файлаў, спам каго, выдалена атакаваць некаторыя сервера, калі вы можаце выказаць гэта з камандай, вы можа падмануць кампутар у гэта рабіць. Цяпер тое, што прыклад як вы маглі б гэта зрабіць? Ну, ёсць шмат кампутараў на інтэрнэт праточнай Bash. Усе карыстальнікі нам Mac сярод іх. Шмат сервераў Linux з'яўляюцца аднымі ім таксама, і серверы Unix. Вокны зноў атрымлівае адносна кручка калі вы не ўстаноўлены спецыяльнае праграмнае забеспячэнне. Цяпер шмат сервераў, для Асобнік, працуюць вэб-сэрвэры, а на самай справе Linux з'яўляецца, бадай, самая папулярная аперацыйная сістэма для працы на кампутарах у Інтэрнэце якія абслугоўванні вэб-старонак. Цяпер, як мы ўбачым пазней у семестр, калі Вы адпраўляеце запыт ад Ваш browser-- Chrome, Internet Explorer, whatever-- на выдалены сервер, атрымліваецца, што нават пры тым, Вы толькі што ўвялі www.example.com, ваш браўзэр пасылае паведамленне гэта крыху больш таямніцай, як гэта. Але звярніце ўвагу, трохі нешта дзіўнае. Першыя два радкі Я ніколі не бачыў раней, але яны не выглядаюць асабліва пагрозлівым. Але звярніце ўвагу, што я скраў для трэцяй лініі тут. Калі дрэнны хлопец былі адправіць паведамленне як гэта ад свайго кампутара да ўразлівай Mac або ўразлівыя сервер Linux, Самае смешнае, што Bash, што проста трохі каманднага радка, ўсюдыісны і часта прывык да істоты выканаць змест паведамленне, што ён атрымлівае. І па гэтай логіцы, можна падмануць вэб-сервер, таму, даслаўшы то як User-Agent, які, як правіла, Мяркуецца сказаць Імя Вашага браўзэра. User-Agent Chrome, User-Agent Інтэрнэт Правадыр, User-Agent Firefox, гэта проста вашага браўзэра спосаб ідэнтыфікацыі сябе. Але калі дрэнны хлопец вельмі разумна кажа, мм-мм, я не збіраюся казаць вам, што мой браўзэр, Я замест пашлю табе гэта загадкавы выгляд рэч з РМ-РФ * У ім, вы можаце літаральна падмануць уразлівымі вэб-сервер у Інтэрнэце у выкананні менавіта, што ў ёсць для выдалення ўсіх файлаў. І, шчыра кажучы, гэта не нават самае горшае. Вы можаце рабіць што заўгодна. Вы можаце пачаць распаўсюджвацца адмова ў абслугоўванні нападу калі вы адправілі гэта паведамленне цэлыя гроздья вэб-сервераў а затым былі яны ўсё адбываюцца, для Асобнік, на серверах Harvard.edu, і вы можаце сартаваць Банг чорт з іх сеткавым трафікам, які быў у адваротным выпадку выклікаецца гэтага дрэннага хлопца. Так, карацей кажучы, амаль усё ў гэтым пакоі, хто валодае Mac ўразлівы для гэтага. Прамень надзеі ў тым, што, калі вы не працуе вэб-сервер на вашым ноўтбуку, і калі вы не на самай справе настроены гэта каб нешта накшталт SSH ў яго, вы на самой справе бяспечна. Гэта не ўразлівыя, але няма ніякага адзін, спрабуючы трапіць у вашым ноўтбуку, так што вы можаце роду ўпэўненыя. Аднак Apple хутка быць абнаўленне папраўку для гэтага. Свет Linux ужо выпусціла шэраг выпраўленняў для Fedora і Ubuntu і іншыя версіі Linux, і на самай справе калі вы запусціце абнаўленне 50 ў прыборы, нават, што таксама будзе абнаўляюцца і карэктуюцца. Але гэта таксама не мае сапраўды былі ўразлівыя, таму што, калі ты не маеш важдаўся з машынай і зрабіў свой ноўтбук публічна даступныя ў Інтэрнэце, які ня па змаўчанні, вы, на самай справе быў выдатны, таму што з міжсеткавага экрана і іншых метадаў. Але гэта крайні прыклад памылкі што мы жылі літаральна за 20 гадоў, і хто ведае, калі хто ўвесь гэты час ведаў пра гэта? І на самай справе, гэта адзін з фундаментальныя праблемы што мы ўбачым пазней у семестр аб бяспецы, з'яўляецца тое, што, як і ў рэальным свеце, добрыя хлопцы знаходзяцца ў нявыгадным становішчы. Каб трымаць дрэнных хлопцаў, мы павінны пераканацца, што кожны дзверы зачынены, што кожнае акно знаходзіцца ў бяспецы, што кожная кропка ўваходу ў дом з'яўляецца бяспечным трымаць дрэнных хлопцаў з. Але тое, што робіць дрэнны хлопец павінен зрабіць, каб на самой справе кампраміс ваш дом і выкрасці ў вас? Ён ці яна проста мае, каб знайсці адзін разблакаваны дзверы, адзін разбітае акно, ці нешта ўздоўж гэтых ліній, і гэта Тое ж самае ў галіне кампутарнай бяспекі. Мы можам напісаць мільёны лініі праграмнага кода і марнаваць сотні ці тысячы з гадзін, спрабуючы прымусіць яго правільна, але калі вы робіце толькі адзін памылка ў правільнасці, Вы можаце змясціць усю сістэму і Сапраўды, у гэтым выпадку ўвесь інтэрнэт і свет ў небяспецы. Так што калі вы хацелі б даведацца больш пра гэта, па наступным адрасе тут. Там няма неабходнасці ў дзеянні сёння, калі вы не сярод тых, зручней, што былі запусціць уласны вэб сервер, у гэтым выпадку вы павінны, на самай справе, абнаўляць праграмнае забеспячэнне. І гэта таксама назва гаворка, і цяпер паперы, што мы звязаны на Сайт курсы для пачаткоўцаў на сённяшні дзень. Гэта было хлопец па па імі Кен Томпсан, які прымаў вельмі вядомы Прэмія ў галіне кампутарных навук, і ён даў гэтую гаворка некалькі гадоў таму, па сутнасці, на гэтай жа тэме. Запытаная людзей пытанне, павінны вы сапраўды давер, у канчатковым рахунку, праграмнае забеспячэнне вы атрымалі? Напрыклад, ва ўсіх нас ёсць пісаў праграмы, і мы былі кампіляцыі ім з Clang. І вашым ведам, вы напісалі любыя праграмы для CS50, дзе ёсць задняя дзверы гатункаў, ёсць спосаб што дрэнны хлопец, калі выкананне вашай праграмы, можа прыняць ваш кампутар? Напэўна, не, не так? Марыё, і Прагныя і Крэдыт. Гэта ўсё даволі невялікія праграмы. Вы павінны былі б быць даволі дрэнна, калі вы на самой справе зробіць увесь ваш кампутар уразлівым пасля напісання 10 або 20 радкоў кода, ці, па меншай меры, не ведаюць пра некаторыя аб наступствах бяспекі. Цяпер я кажу, што ў жарт, але мы збіраемся, каб убачыць сёння і на гэтым тыдні гэта на самай справе сапраўды, вельмі лёгка быць дрэнным і зрабіць яшчэ кароткія праграмы ўразлівыя. Але цяпер, як мінімум, зразумець, што пытанне пастаўлены тут аб Clang ў кампілятар. Чаму нас давяраючы Clang на працягу апошніх двух-трох тыдняў? Хто можа сказаць, што той, хто пісаў Clang не было "калі" ўмова ў там што істотна ўводзяць некаторы колькасць нулёў і тыя, у кожную праграму ён кампілюе што дазволіць яму ці ёй доступ кампутар, калі вы спіце і ваш вечка наўтбука адкрыта і ваш кампутар працуе? Дакладна? Мы маем такую ​​сістэмы гонар справа Цяпер, калі мы верым, што Clang з'яўляецца законным. Вы ўпэўненыя, што прыбор з'яўляецца законным. Вы ўпэўненыя, што літаральна кожная праграма на вашым Mac ці PC заслугоўвае даверу. І як відаць з гэтага простага памылка, нават калі гэта не злы, што абсалютна не хутчэй за ўсё, будзе так. Такім чынам, вы павінны быць страшна, як пекла. Шчыра кажучы, няма просты Рашэнне гэтай сябра чым свайго роду грамадскай дасведчанасці з ускладненнем што мы будуем на вяршыні з нашых камп'ютэрных сістэм, і як усё больш уразлівымі мы цалкам можа быць. Цяпер з гэтым сказаў, Breakout. Так Breakout з'яўляецца праблема ўсталяваць тры, і Breakout гэта гульня ад мінулага што вы, магчыма, памятаеце, але для нас у праблему ўсталяваць тры, гэта дазваляе нам прымаць рэчы назад на прыступку вышэй так што, калі мы пішам праграмы, нават у тэрмінальным акне, як гэта, мы можам рэальна працаваць, у выніку, графічныя праграмы не у адрозненне ад тых, каго мы мелі доступ у пустым. Так што гэта супрацоўнікі гатэля Рэалізацыя Breakout, які з'яўляецца толькі гэта цэгла-парушэнне гульня, што вы перамясціць вясло назад і наперад, і вы патрапілі супраць тых каляровага цэглы да верхняй. Так што гэта прыносіць нам роду туды, дзе мы змаглі б вельмі хутка з нуля, і цяпер з C, рэалізацыі нашай уласнай графічныя інтэрфейсы карыстальніка. Але больш за тое, гэта Праблема набор уяўляе першы , У якім мы даем Вы куча кода. І на самай справе, я прыношу відавочнае ўвагу на гэта, таму што асабліва для тых, менш знаёмыя, гэта Праблема ўсталяваць, па меншай меры, на першы погляд, будзе адчуваць сябе, як мы ўзялі яго на прыступку вышэй. Таму што мы далі вам, для некаторых з пошуку і сартавання праблемы ў PSET, куча кода, які мы напісалі, і некалькі каментароў што сказаць "рабіць", дзе вы павінны запоўніць прабелы. Так што не занадта страшна, але гэта ў першы раз мы ўручыць вам код, які вы павінны ўпершыню прачытаў, разумею, а затым дадаць у і завяршыць яго. А потым з Breakout, мы збіраемся зрабіць тое ж самае, даючы вам некалькі дзесяткаў больш ліній кода, які, шчыра кажучы, даць вам шмат рамак для гульня, але спыніцца рэалізацыі цэглу і мяч і вясло, але мы робім рэалізаваць некаторыя іншыя функцыі. І нават тое, што на першы погляд, зноў жа, асабліва калі менш камфортна, можа здацца асабліва складанай і Вы думаеце, што ёсць так шмат новых функцый вам трэба абгарнуць свой розум вакол, і гэта праўда. Але майце на ўвазе, што гэта зусім як за нуль. Хутчэй за ўсё вы не выкарыстоўвалі ўсе часткі галаваломкі ў пустым месцы. Хутчэй за ўсё вы не клапоціцеся, каб абгарнуць ваш розум вакол ўсе з іх таму ўсё, што спатрэбілася было Хуткі погляд, каб зразумець, пра, гэта тое, што я магу зрабіць, з гэтай паззл. І сапраўды, у задачы ўсталяваць 3 спецыфікацыі, мы будзем паказваць вам на дакументацыі, што будзе пазнаёміць вас з некаторымі новымі функцыямі, і ў канчатковым рахунку праграмаванне будуе выкарыстанні. Ўмовы, завесы, зменныя і функцыі будуць ідэнтычныя што мы бачылі да гэтага часу. Так сапраўды, што мы дамо Вы прыклад кода, што дазваляе ствараць акно што выглядае не ў адрозненне ад гэтага, і ў канчатковым выніку ператварыць яго ў нешта зусім так. Так скарыстацца CS50, абмеркаваць працоўныя гадзіны і многае іншае, і суцяшэнне ў тым, што аб'ём кода вы павінны напісаць на самай справе не так ужо і шмат. Першая задача проста, каб акліматызавацца сабе некаторы код мы напісалі. Любыя пытанні па pset3, Кантузія, ці інакш? АЎДЫТОРЫЯ: Здавалася, ісці да канца з Breakout што код амаль аб'ектна-арыентаваны стыль, але я думаў, C быў Аб'ектна-арыентаваны праграмы. СПІКЕР 1: Выдатны пытанне. Такім чынам, у перачытваў Код размеркавання, код мы пісалі для pset3, для тых, хто знаёмы, яго Падобна на тое, што гэта трохі аб'ектна-арыентаваны. Кароткі адказ, гэта. Гэта набліжэнне, як вы можа зрабіць аб'ектна-арыентаваны код, выкарыстоўваючы мова, як C, але гэта канчатковым рахунку, усё працэдурны. Там не існуе метадаў ўнутры зменныя, як вы ўбачыце. Але гэта нагадвае, што. І мы ўбачым гэтую функцыю зноў калі мы дабяромся да PHP і JavaScript да канца семестра. Але цяпер, думаю пра яго, як намёк на тое, што будзе далей. Добры пытанне. Добра. Так сартавання зліццём быў, як мы левыя рэчы ў апошні раз. І сартаванне зліццём было халаднавата адчуванне, што гэта было нашмат хутчэй, па меншай меры, на аснове выпрабаванняў беглым мы зрабілі на мінулым тыдні, чым, скажам, бурбалка сартаваць, выбар роду, сартаванне ўстаўкамі. І тое, што было ахайна занадта проста як лаканічна і чыста Вы можаце выказаць гэта. І што ж мы кажам, гэта было верхняя абмежаванне на часе працы зліцці сартаваць? Так? АЎДЫТОРЫЯ: н § п? СПІКЕР 1: п увайсці н, права. н увайсці н. І мы вернемся да таго, што, што на самай справе азначае ці дзе што адбываецца ад, але гэта было лепш, чым тое, што часу працы што мы бачылі на працягу бурбалка Выбар і сарціроўка ўстаўкамі? Так н квадрат. н квадрат больш, чым гэта, і нават калі гэта не зусім відавочна, ведаю, што часопіс н менш п, так што калі вы п раз то менш, чым п, гэта будзе менш п квадрат. Гэта крыху інтуіцыі ёсць. Але мы заплацілі цану за гэта. Гэта было хутчэй, але тэма, якая пачалася з'яўляцца на мінулым тыдні быў гэты кампраміс. Я атрымаў лепшую прадукцыйнасць Час мудра, але тое, што я павінен выдаткаваць на іншы рука, для таго, каб дасягнуць гэтага? АЎДЫТОРЫЯ: Памяць. СПІКЕР 1: Скажыце яшчэ раз? АЎДЫТОРЫЯ: Памяць. СПІКЕР 1: памяць, або прастору ў цэлым. І гэта не было супер Відавочна, з нашымі людзьмі, але нагадаем, што нашых валанцёраў ступалі наперад і крочыць назад, як быццам ёсць масіў тут, і як бы ёсць Другі масіў тут яны маглі б выкарыстоўваць, таму што мы мелі патрэбу дзе-небудзь, каб аб'яднаць тых людзей. Мы не маглі проста памяняць іх на месцы. Так зліваюцца сартавання рычагі больш месца, якія мы не павінны з іншыя алгарытмы, але ўверх, што гэта значна хутчэй. І, шчыра кажучы, у рэальным сусветнай прасторы гэта days-- RAM, жорсткі дыск space-- з'яўляецца адносна таннай, і так вось не абавязкова дрэнна. Такім чынам, давайце кінем хуткі погляд, трохі больш метадычна, на тое, што мы зрабілі і чаму мы сказалі, што гэта быў п § п. Дык вось гэта восем лічбаў і восем добраахвотнікаў у нас быў апошні раз. І першае, што Merge Сартаваць сказаў нам рабіць было што? АЎДЫТОРЫЯ: Падзяліць на дзве часткі. СПІКЕР 1: Скажыце яшчэ раз? АЎДЫТОРЫЯ: Падзяліць на дзве часткі. СПІКЕР 1: Падзяліць на дзве часткі, прама. Гэта вельмі нагадвае тэлефонная кніга, з прорвы і ўладар ў цэлым. Такім чынам, мы глядзелі на левай палове. А потым, як толькі мы сказалі, накшталт левая палова элементаў, Што ж мы ў наступны раз сказаць? Сартаваць левую палову злева палова, які дазволіў нам, пасля падзелу на дзве часткі, засяродзіцца на чатырох і двух. Як вы адсартаваць спіс зараз, у жоўты, памер два, выкарыстоўваючы Зліццё Сартаваць? Ну падзяліць яго напалову, і сартаваць левую палову. І гэта было, дзе рэчы ёсць трохі дурны коратка. Як вы адсартаваць спіс Вось з Памер адзін, як гэты нумар чатыры тут? Гэта сартуюцца. Вы зрабілі. Але тады, як жа адсартаваць спіс Памер адзін, калі гэта нумар два? Ну, тое ж самае, але зараз тое, што было Трэці і ключавы крок у Merge Сартаваць? Вы павінны былі аб'яднаць левы палова і правая палова. І як толькі мы гэта зрабілі, мы глядзелі у чатыры, мы глядзелі на два. Мы вырашылі ўсё ў парадку, відавочна, два на першым месцы, таму мы змяшчаем два ў яго месца, ідуць чатыры. І зараз у вас ёсць, каб збольшага таму, і гэта з'яўляецца свайго роду характарыстыкай алгарытму, як Merge Сартаваць, перамотка ў памяці. Тое, што было на наступны лінія аповяду? Што я павінен канцэнтравацца на наступны? Правая палова злева палова, што ў шэсць і восем. Такім чынам, дазвольце мне проста крок праз гэта без размове кропку занадта шмат. Шэсць і восем, то шэсць з'яўляецца сартуюцца, восем сартуецца. Зліццё іх разам, як, што, і цяпер наступны вялікі крок ёсць, вядома, сартаваць правую палову ад Самы першы крок гэтага алгарытму. Такім чынам, мы засяродзіцца на адным, трох, сямі, пяці. Мы затым засяродзіцца на левай палове. Левая палова, што, правая палова што, а затым аб'яднаць у адным і тры. Тады правая палова, то левая палова з яго, то правая палова яго. Зліццё гэта, і цяпер тое, што крок застаецца? Зліццё вялікі левую палову і вялікі Правая палова, так што ідзе туды, затым два, затым тры, затым чатыры, затым пяць, то шэсць, то сем, то восем. Так што цяпер, чаму гэты ў канчатковым рахунку, выяўлення, асабліва калі н і лагарыфмы больш як правіла, даволі бегчы табе, па меншай меры, у апошні час? Ну, звярніце ўвагу на вышыню гэтай рэчы. У нас было восем элементаў, і мы падзяліць яго на два, на два, на два. Так увайсці базу два з васьмі дае нам тры. І паверце мне на тым, што калі трохі туманна на што. Але ўвайсці база два з васьмі ў тры, такім чынам, мы зрабілі тры пласта зліцця. І калі мы аб'яднаныя элементы, як многія элементы ж мы паглядзім на на кожнай з гэтых радкоў? У агульнай складанасці п, ці не так? Таму што, каб аб'яднаць верхнюю радок, хоць мы зрабілі гэта па частках, мы ў канчатковым рахунку закрануў кожнае колькасць разоў. І ў другім шэрагу, каб аб'яднаць гэтыя спісы памеру два, мы павінны былі закрануць кожнага элемента адзін раз. А потым тут сапраўды ясна ў апошнім шэрагу, мы павінны былі закрануць кожнага з тых, элементы адразу, а толькі адзін раз, так у гэтым і заключаецца, то, наша н лог н. І цяпер толькі, каб зрабіць рэчы трохі больш фармальны на імгненне, калі вам былі цяпер аналізаваць гэта у свайго роду больш высокім узроўні і паспрабаваць вырашыць, а як можа вы ісці аб выказванні час працы гэтага алгарытму проста зірнуўшы на яго, а не з дапамогай надуманы прыклад? Ну, колькі часу вы можаце сказаць крок, як гэта ў жоўты возьме, калі п <2 вяртанне? Гэта вялікая O чаго? Так я бачу адзін, таму адзін крок, можа быць, два крокі, таму што гэта, калі , А затым вярнуцца, але гэта Пастаянная часу, ці не так? Таму мы сказалі O (1), і гэта як я буду выказваць гэта. T, проста час працы. N з'яўляецца памер ўваходу, так Т (п), толькі мудрагелісты спосаб сказаць бег Час дадзена ўваход аб'ёму п будзе парадку сталай часу, у O (1). Але у адваротным выпадку, тое, што пра гэта? Як бы вы выказаць час працы гэтага жоўтай лініі? T чаго? Вы можаце роду падмануць тут і адказаць на маё пытанне цыклічна. Так што, калі падчас працы ў Наогул мы проста сказаць, Т (п). А цяпер ты роду понтировавшего тут і кажучы, ну проста адсартаваць левую палову, а затым адсартаваць правую палову. Як мы можам сімвалічна ўяўляюць час працы гэтай жоўтай лініі? T чаго? Што памер ўваходу? п над імі. Чаму б мне проста не сказаць, што? І тады гэта яшчэ адзін Т (N / 2), а затым зноў, калі я аб'яднаць два адсартаваных палоўкі, колькі элементаў я збіраюся мець закрануць за ўсё? н. Так што я магу выказаць гэта, проста каб быць свайго роду фантазіі, як часу працы ў цэлым. Т (п) з'яўляецца толькі час працы Т (п / 2), плюс Т (п / 2), пакінуў палову і правую палову, плюс O (п), што, верагодна, п крокаў, але можа быць, калі я выкарыстоўваю два пальцы, гэта ў два разы больш крокі, але гэта лінейная. Гэта некаторы колькасць крокаў вось фактар ​​п, такім чынам, мы маглі б выказаць гэта, як гэта. І гэта, дзе зараз мы Пунт, каб таму з нашай сярэдняй школы па матэматыцы падручніка мы, што рэцыдыву ў канчатковым рахунку, заканчваецца зраўнаваўся гэта, п раз увайсці н, калі вы на самой справе з матэматыка больш фармальна. Дык вось ўсяго два перспектывы. Адзін колькасна з жорстка тыповы прыклад з выкарыстаннем васьмі лічбаў і больш Агульны погляд на тое, як мы дабраліся там. Але што сапраўды цікава тут , Зноў жа, гэта паняцце на ровары. Я не выкарыстоўваю для завес. Я накшталт вызначэння то з пункту гледжання само па сабе, не толькі з гэтым Матэматычная функцыя, але і з пункту гледжання гэтай псеўда-код. Гэта псеўда-код рекурсивен ў гэтым двух сваіх ліній па сутнасці кажу гэта, каб пайсці выкарыстоўваць сябе вырашыць менш Праблема меншага памеру, а затым зноў і зноў і не раз, пакуль мы звесці яго да гэтага так званага базавага варыянту. Так што давайце на самай справе зрабіць больш прывабным вынас з гэтага наступным чынам. Дазвольце мне ісці ў Gedit і прыняць паглядзім на некаторыя з сённяшняй зыходнага кода, У прыватнасці, гэты прыклад тут. Sigma 0, відаць, дадае нумары з першага па п. Такім чынам, давайце паглядзім, што знаёмыя і незнаёмым тут. Упершыню ў нас ёсць пару ўключае ў сябе, так што нічога новага там. Прататып. Я крыху туманна на гэта пасля некалькіх дзён, але тое, што мы казалі Прататып функцыі? АЎДЫТОРЫЯ: [неразборліва]. СПІКЕР 1: Што гэта? АЎДЫТОРЫЯ: Мы аб'яўляем яго. СПІКЕР 1: Мы аб'яўляем яго. Такім чынам, вы вучыце Clang, эй, фактычна не ажыццяўляе гэта яшчэ, а дзе ў гэтым файле, па-відаць, збіраецца быць функцыя называецца тое, што? Sigma. І гэта толькі абяцанне, што гэта будзе выглядаць наступным чынам. Гэта збіраецца заняць цэлае, як input-- і я магу быць больш відавочным і сказаць Int N --І гэта збіраецца вярнуць Int, але кропка з коскі азначае, мм, я абысці у рэалізацыі гэтага крыху пазней. Зноў жа, Clang з'яўляецца нямым. Гэта толькі збіраецца ведаць, што Вы кажаце гэта зверху ўніз, так што мы павінны па крайняй меры даць гэта намёк на тое, што будзе далей. Зараз давайце паглядзім на галоўны тут. Давайце пракруціць ўніз тут і бачыць тое, што галоўны робіць. Гэта не так доўга функцыі, і на самай справе канструкцыя тут знакам. Я абвясціць зменную п, а затым Я прыставаць карыстачу зноў і зноў для цэлага станоўчага колькасці, выкарыстоўваючы GetInt, і адзінае выйсце з гэтай завесы як толькі карыстач выканаў. Рабіць у час, мы выкарыстоўвалі, каб прыставаць да карыстача такім чынам. Зараз гэта цікава. Я абвясціць Int пад назвай "Адказ". Даручаю гэта вяртаецца значэнне функцыі пад назвай "сігма". Я не ведаю, што гэта робіць яшчэ, але Я памятаю, абвясціўшы яе хвіліну таму. І тады я перадаю ў значэнне, якое карыстальнік ўводзіць у N, і тады я паведаміць адказ. Ну давайце пракруткі назад на імгненне. Давайце пойдзем далей у гэты каталог, зрабіць сігма 0, а на самай справе запусціць гэтую праграму і паглядзець, што адбываецца. Так што, калі я іду наперад і бегчы гэтая праграма, ./sigma-0, і я друкую ў станоўчым цэлае, як два, Sigma, як грэцкі сімвал азначае, гэта проста збіраецца скласці ўсе лікі ад нуля на да двух. Так 0 плюс 1 плюс 2. Так што гэта, будзем спадзявацца, даць мне 3. Вось і ўсё, што ён робіць. І сапраўды гэтак жа, калі я запускаю гэта зноў і я даю яму лік тры, вось 3 плюс 2, так што гэта 5, плюс 1 павінен даць мне 6. І потым, калі я атрымліваю сапраўды вар'ят і напішыце тэкст у вялікіх колькасцях, ён павінен даць мне ўсё больш і больш сумы. Дык вось і ўсё. Такім чынам, што ж сігма выглядаць? Ну, гэта даволі проста. Гэта тое, як мы маглі б ажыццяўляцца гэта за апошнія пару тыдняў. "Int" будзе тып якое вяртаецца. Сігма гэтае імя, і ён прымае пераменная м замест п. Я змяню, што да лепшых. Тады гэта проста санітарная праверка. Мы ўбачым, чаму ў дадзены момант. Цяпер я заяўляю яшчэ адну зменную, сума, ініцыялізаваць яго да нуля. Тады ў мяне ёсць гэты цыкл ітэрацыі, па-відаць, для яснасці, ад я = 1 на да = т, што з'яўляецца што карыстач увёў у, а затым я павялічыць суму, як гэта. А потым вярнуць суму. Так пару пытанняў. Адзін, я сцвярджаю, на мой каментар, які гэта пазбягае рызыкі бясконцы цыкл. Чаму перадаючы б у негатыўным колькасці падахвочваць, патэнцыйна, у бясконцы цыкл? АЎДЫТОРЫЯ: Вы ніколі не будзеце дасягаць м. СПІКЕР 1: Ніколі не лезьце м. Але м перадаецца ў, так што давайце Разгледзім просты прыклад. Калі м перадаецца ў па Карыстальнік, як адмоўнага. Незалежна ад асноўнай. Галоўная абараняе нас ад гэта таксама, так што я проста быўшы сапраўды анал з сігма таксама пераканацца, што ўваход не можа быць адмоўным. Такім чынам, калі адмоўная м, то як адмоўнага. Што адбудзецца? Ну, я збіраецца ініцыялізуюцца адзін, і тады я будзе менш або роўна т? Чаканне. Гэта was-- давайце не, давайце Нікс гэтую гісторыю. Я не задаць гэтае пытанне, таму што рызыка таго, што я, намякаючы на не адбудзецца, таму што я гэта заўсёды будзе быць больш than-- ОК, Я выракаюся гэтае пытанне. Добра. Давайце засяродзімся толькі на гэтай частцы тут. Чаму я заяўляю некаторыя па-за цыкла? Апавяшчэнне на лініі 49 У мяне абвешчаныя I ўнутры завесы, але на сайце 48 У мяне заявіў некаторы межамі. Так. АЎДЫТОРЫЯ: [неразборліва]. СПІКЕР 1: Вядома. Так, перш за ўсё, я, вядома, не хачу аб'явіць і ініцыялізаваць суму з нулявой ўнутранай пятля на кожнай ітэрацыі, таму што гэта будзе ясна перамагчы Мэта падвядзення нумары. Я хацеў бы захаваць змены значэнне на нуль. А таксама, што яшчэ адзін больш таямніцай Прычына таго ж дызайнерскае рашэнне? Так. АЎДЫТОРЫЯ: [неразборліва]. СПІКЕР 1: Точно. Я хачу атрымаць доступ да яго па-за завесы таксама на якой лініі? На 53. І на аснове нашага правіла ад пару лекцый назад, зменныя вобласці бачнасці, сапраўды, у Фігурныя дужкі, якія ахопліваюць іх. Так што, калі я не абвясціць суму ўнутры з гэтых знешніх фігурныя дужкі, Я не магу выкарыстоўваць яго ў лініі 53. Іншымі словамі, калі я абвясціў сума ў тут, ці нават на працягу Для цыклу, я не мог атрымаць доступ да яго ў 53. Пераменная б эфектыўна не будзе. Так некалькі прычын там. Але цяпер давайце вернемся і паглядзець, што адбываецца. Так сігма выклікаецца. Ён дадае, 1 плюс 2, або 1 плюс 2 плюс 3, а затым вяртае значэнне, захоўвае яго ў адказ, і Е тут Таму я бачу на экране. Дык гэта тое, што мы называем паўтаральны Падыход, у якім ітэрацыі толькі азначае выкарыстанне пятлю. Для цыклу, у той час як цыкл, Do Хоць цыкл, а проста раблю тое зноў і зноў і зноў. Але сігма выгляд акуратны функцыі ў што я мог рэалізаваць яго па-рознаму. Што з гэтай нагоды, якія проста каб быць крута, дайце мне сапраўды пазбавіцца з вялікага адцягнення таму гэтай функцыі сапраўды вельмі проста. Давайце звесці яго толькі каб яе чатырох асноўных ліній і пазбавіцца ад усіх каментары і фігурныя дужкі. Гэта свайго роду ашаламляльных Альтэрнатыўная рэалізацыя. Добра, можа быць, ня ашаламляльных, але гэта збольшага сэксуальней, усё ў парадку, глядзець на гэта так шмат больш лаканічна. З дапамогай ўсяго толькі чатыры радкі кода, Я спачатку гэта здаровае праверку. Калі т менш або роўная нуля, сігма не мае сэнсу. Гэта толькі павінна быць у гэты выпадак для станоўчых лікаў, так што я проста хачу, каб вярнуць нуль адвольна так што мы па меншай меры, некаторыя так званыя базавы варыянт. Але тут-то і хараство. Сукупнасць гэтай ідэі, дадаючы лікі ад 1 да п, або м у гэтым выпадку, можа быць зроблена па відах перакладання адказнасці. Ну, тое, што з'яўляецца сумай 1 да т? Ну, вы ведаеце, што? Гэта тое ж самае як сума м плюс сума 1 да т мінус 1. Ну вы ведаеце, што? Што сігма м мінус 1? Ну, калі вы, здаецца, прытрымлівацца гэтага лагічна, гэта тое ж самае, як м мінус 1 плюс сігма м мінус 2. Такім чынам, вы можаце роду просто-- гэта як, калі вы проста спрабуе дапячы сябру і яны задаць вам пытанне, вы, здаецца, адказаць на пытанне, Вы можаце збольшага трымаць перакладання адказнасці. Але тое, што ключавым з'яўляецца тое, калі вы трымаеце што робіць гэтае пытанне ўсё менш і менш і менш, вы не пытаючыся, што гэта сігма п, што сігма п, што сігма п? Ты просіш што сігма п, што сігма н мінус 1, што сігма н мінус 2? У рэшце рэшт ваш пытанне збіраецца стаць што? Што Sigma з аднаго або нуля, некаторыя вельмі малое значэнне, і як толькі вы атрымаць, што, ваш сябар, Вы не збіраецеся спытаць тое ж пытанне зноў, вы толькі збіраецеся сказаць, О, гэта нуль. Мы скончылі гуляць гэты від тупы цыклічнага гульні. Так Рэкурсія акт у праграмаванні функцыі, якая называе сябе. Гэтая праграма, пры кампіляцыі і запуску, з'яўляецца збіраецца весці сябе сапраўды гэтак жа, але тое, што ключ, што ўнутры функцыі пад назвай Sigma, ёсць радок кода які адрозніваецца тым, мы называем сябе, якія, як правіла, дрэнна. Напрыклад, што, калі я першы складзены гэты, так што sigma-- зрабіць сігма 1 ./sigma-1. Станоўчае цэлае, калі ласка, 50 1275. Так што мабыць функцыя б, на аснове аднаго тэсту, правільнай. Але што, калі я крыху небяспечна і выдаленне так званага базавага варыянту, і проста сказаць, а я проста зрабіць гэта складаней, чым гэта. Давайце проста вылічыць сігма прымаючы м з наступным даданнем ў сігма м мінус адзін? Ну, тое, што адбудзецца тут? Давайце памяншэння маштабу. Давайце перакампіляваць праграму, захаваць яго, перакампіляваць праграму, а затым гатовы ./sigma-1 маштабавання, увядзіце станоўчае цэлае лік калі ласка, 50. Як многія з вас гатовыя прызнацца да бачачы, што? Добра. Так што гэта можа адбыцца на працягу цэлы шэраг прычын, і адкрыта на гэтым тыдні мы о, каб даць вам некалькі з іх. Але ў гэтым выпадку, паспрабуйце разважаць у адваротным кірунку Што магло б адбыцца тут? Памылка сегментацыі, мы сказалі ў мінулым Час, адносіцца да сегмента памяці. Што-то дрэннае здарылася. Але што ж гэта было механічна, што пайшло не так тут з майго выдалення з гэтай так званай базавай выпадку, дзе я вярнуўся жорстка запраграмаваны значэнне? Што вы думаеце пайшло не так? Так. АЎДЫТОРЫЯ: [неразборліва]. СПІКЕР 1: Ах. Добры пытанне. Так памеру колькасці што я падвядзення атрымаў настолькі вялікі, што ён перавысіў памер памяці. Добрая ідэя, але не прынцыпова збіраецца выклікаць збой. Гэта можа прывесці да цэлалікавае перапаўненне, дзе біты проста перавярнуць і тады мы памылкова сапраўды вялікі нумар для як адмоўны лік, але, што само па сабе не прывядзе да аварыі. Таму што ў канцы дзень Int яшчэ 32 біта. Вы не збіраецеся выпадкова скрасці 33. няшмат. Але добрая думка. Так. АЎДЫТОРЫЯ: [неразборліва]. СПІКЕР 1: Метад ніколі не спыняе працаваць, і гэта сапраўды так называе сябе зноў і зноў і зноў і зноў і зноў, і ні адзін з гэтыя функцыі калі-небудзь скончыць, таму што іх адзінай лініі код выклікае сам сабе зноў і зноў і зноў. І тое, што на самой справе што тут адбываецца, і зараз мы можа збольшага звярнуць на гэта графічна. Дазвольце мне перайсці да карціна на імгненне. Гэта карціна, што у канчатковым выніку будзе канкрэтызаваць больш падрабязна, што адбываецца на ўнутры памяці кампутара. І атрымліваецца, што на Дно гэтай малюнку тое, што называецца стэк. Гэта кавалак памяці, кавалак памяці, вось толькі выкарыстоўвацца ў любы час функцыя выклікаецца. Кожны раз, калі вы, праграміст, выклікаць функцыю, аперацыйная сістэма, як Mac OS, Windows, або Linux, хапае куча байтаў, можа быць, некалькі кілабайт, можа быць, некалькі мегабайт памяці, перадае іх Вам, а затым дазваляе вы вядзеце свой функцыю з дапамогай ўсе зменныя вам трэба. І калі вы затым выклікаць іншы Функцыя і іншая функцыя, вы атрымаеце яшчэ адзін кавалачак памяці і яшчэ кавалачак памяці. І на самай справе, калі гэтых зялёных латкоў ад Анненберг ўяўляюць гэтую памяць, вось што адбываецца першым выкліку функцыі сігма. Гэта як пакласці паднос, як гэта на тым, што першапачаткова пусты стэк. Але тады, калі гэты латок называе сябе, так бы мовіць, выклік у другі экземпляр сігма, гэта як прасіць аперацыйную сістэму, ох, трэба крыху больш памяці, дай мне гэта. І тады ён атрымлівае звалілі на па-над. Але тое, што ключавым тут з'яўляецца тое, што першы латок па-ранейшаму існуе, таму што ён выклікаецца гэты другі латок. Цяпер між тым, сігма называюць сігма, вось як прасіць больш памяці. Атрымлівае звалілі на тут. сігма называюць сігма, гэта ўжо зусім іншая латок, які атрымлівае звалілі на тут. І калі вы працягваеце рабіць гэта, у рэшце рэшт, свайго роду карту гэтага візуальнага у той дыяграме, што адбываецца ў здарыцца са стэкам латкоў? Гэта будзе перавышаць суму памяці кампутара мае. І як толькі гэты зялёны латок перавышае гарызантальную лінію вышэй стэка і вышэй, што слова кучы, якія мы яшчэ вернемся ў будучыні, што гэта дрэнна. Куча адрозніваецца сегмент памяці, і калі вы дазволіце гэта Латкі куча і куча на, вы збіраецеся перавышаць самастойна сегмент памяці, і праграма сапраўды урэжацца. Цяпер як у бок, гэтай ідэі рэкурсіі, таму, можа выразна прывесці да праблем, але гэта не абавязкова дрэнна. Таму што лічу, пасля усё, how-- і, магчыма, гэта патрабуе некаторага прывыкання каб --Як элегантны або як проста што рэалізацыя сігма быў. І мы не збіраемся выкарыстоўваць Рэкурсія усё, што многае ў CS50, але ў CS51, і сапраўды любы клас дзе вы маніпуляваць структуры дадзеных як дрэвы, або сямейных дрэў, што ёсць іерархія, гэта супер, супер карысна. Зараз, як у бок, так, каб вас як якія імкнуцца кампутарных навукоўцаў знаёмыя з некаторымі з Google, ўнутры анекдоты, калі вы ідзяце ў Google і вы паглядзіце, што з'яўляецца вызначэнне, скажам, рэкурсіі, увядзіце. Угу. Як у баку, я пад'ехаў нямногія. Гэта было, як 10 хвілін прамаруджванне сёння раніцай. Калі вам таксама Google "крыва", апавяшчэнне нахіляючы галаву slightly-- і то гэта адно, мабыць, Найбольш жорсткія за ўсё так як хто правёў як іх дзень рэалізацыі гэтага некалькі гадоў ago-- давай. О, wait-- гэта памылка. Так працуе на адным з Найбуйнейшыя сайты свеце гэтыя дурныя маленькія велікодныя яйкі. Яны, верагодна, спажываць нетрывіяльнае колькасць радкоў кода проста так, што мы можам мець маленькія пацешныя рэчы, як, што. Але па крайняй меры цяпер вы атрымліваеце некаторыя з гэтых ўнутраных жартаў. Зараз давайце зірнем на некаторыя з белы ляжыць мы казалі ў апошні час, і пачынаюць адхіліце некаторыя пласты тэхнічна так што вы сапраўды разумееце, што адбывалася на і вы можаце зразумець, некаторыя з пагроз, як Shellshock, што ўжо пачалі, каб стаць на пярэднім краі кожнага увагу, па меншай меры, у сродках масавай інфармацыі. Дык вось гэта вельмі простая функцыя што нічога не вяртае, несапраўднымі. Яго клічуць падпампоўкі. Гэта займае ад двух зменных і гэта нічога не вяртае. Прымае ў а і б. Так кароткі ролік, які дэманструе. Мы прынеслі гэтыя ўверх. Мы маглі б таксама ўзяць крыху разбіць тут на імгненне і ёсць трохі тое, каб піць. Калі хто быў бы не супраць далучэння мне тут на імгненне. Як пра вас у цёмна-бардовы кашулю? Падымайцеся. Толькі адзін сёння. Дзякуй, хоць. Добра, і ў нас ёсць прыдумляць, хто тут? Як цябе завуць? СПІКЕР 4: Лаура. СПІКЕР 1: Лора. Падымайцеся. Так Лора, вельмі просты задачай сёння. Прыемна пазнаёміцца ​​йо. Добра. Таму ў нас ёсць трохі малака сюды і у нас ёсць трохі апельсінавага соку тут і некаторыя кубкі, якія мы запазычаныя з Анненберг сёння. СПІКЕР 4: Пазыковыя. СПІКЕР 1: І збіраюся ісці наперад і даць вам паўшклянкі гэтага. Добра. І мы дамо вам палову шклянку малака. О, і проста так, што вы можаце памятаю, што гэта было, як, Я забыўся прыносіць гэта і сёння. Добра. Калі вы не пярэчыце, давайце паглядзім, што мы можа паставіць іх на Вашых ачкоў калі ты хочаш. Гэта будзе свет ад вачэй Лоры. Добра. Так ваша мэта, улічваючы два кубкі вадкасць тут, малако і апельсінавы сок, будзе памяняць месцамі два змесціва такім чынам, што апельсінавы сок ідзе ў кубак малака і пераходзіць у малако кубак апельсінавага соку. СПІКЕР 4: Ці магу я атрымаць яшчэ адну кубак? СПІКЕР 1: Я так рада, што вы спыталі, хоць гэта было б нашмат лепш, кадры калі б вы не спыталі. Але так, мы можам прапанаваць вам трэці кубак, што там пуста, вядома. Добра. Так своп змесціва там. Вельмі міла. Вельмі добра. Вы робіце гэта дзіўна старанна. І трэцяга кроку. Добра. Выдатна. Вялікі выбух апладысментаў было б добра для Лауры. Добра. У нас ёсць невялікі развітальны падарунак для вас, але дазвольце мне ўзяць гэта. Дзякуй вялікі. Такім чынам, просты прыклад, тым не менш, каб прадэманстраваць, што калі вы робіце хочаце памяняць змесціва з двух кантэйнераў, або назавем іх зменнымі, Вы маеце патрэбу ў некаторым часовае захоўванне на сцэне аднаго са зместу ў так што вы рэальна можаце зрабіць своп. Так сапраўды, гэта зыходны код тут, у C з'яўляецца прадстаўніком менавіта гэта. Калі апельсінавы сок быў і малако было б, і мы хацелі, каб памяняць іх месцамі, Вы можаце паспрабаваць тое творчае шляхам залівання адна ў адну, але, што, верагодна, не будзе у канчатковым асабліва добра. І таму мы выкарыстоўваем трэцюю шклянку, тэлефануйце гэта TMP, T-M-P па пагадненні, і змясціць змесціва OJ ў тым, што, то памяняць адну кубак, затым пакласці OJ ў Арыгінальны кубак, тым самым дасягненні, гэтак жа, як Лаура зрабіў, своп. Так што давайце рабіць менавіта гэта. Дазвольце мне ісці наперад і адкрыць да прыкладу, гэта на самай справе называецца "няма абмяняць, "таму што гэта не як проста зрабіць, як вы думаеце. Такім чынам, у гэтай праграме, заўважылі, што Я выкарыстоўваю stdio.h, наш стары сябар. У мяне ёсць прататып для падпампоўкі там, якія азначае яго рэалізацыя сайт верагодна, унізе, і давайце паглядзім, што гэта галоўнае Праграма будзе рабіць для мяне. Я спачатку аб'явіць Int х атрымлівае адзін, і дзесятковага у атрымлівае два. Так думаць пра тых, як OJ і малако, адпаведна. А потым я проста ёсць Е кажучы х гэта і ў гэта, толькі так я магу наглядна ўбачыць, што адбываецца. Тады я PRINTF сцвярджаючы што я перапампоўкі два, і тады я раздрукаваць сцвярджаюць, што яны памяняліся, і я раздрукаваць х і ў зноў. Так тут, у своп менавіта тое, што зрабіў Лаура, і менавіта тое, што мы бачылі на экран хвіліну таму. Так што давайце ісці наперад і вельмі расчараваныя. Не рабіце своп, і не стварае ніякіх праблем своп, маштабавання на выхадзе тут. Калі ласка, увядзіце х 1, у 2, перапампоўкі месцамі. х па-ранейшаму 1, а ў яшчэ 2. Такім чынам, нават пры тым, што, шчыра кажучы, гэта выглядае сапраўды як, хоць і больш тэхнічна, што зрабіў Лаура, не падобна на працу. Дык чаму ж? Ну, атрымліваецца, што, калі мы пішам праграму, як гэта што абодва галоўны, тут асветлены, а затым яшчэ адна функцыя, як своп, Паказаныя тут, якія ён выклікае, свет выглядае трохі нешта падобнае гэтыя латкі момант таму. Калі асноўная першы выклікаецца, што ўсё роўна што прасіць аперацыйную сістэму для крыху памяці для любой мясцовы зменныя, такія як х і у, што асноўная мае, і яны ў канчатковым выніку прама там. Але калі асноўныя выклікі памяняць, а галоўнае праходзіць памяняць два аргументу, а і б, апельсінавы сок і малако, гэта не так уручаючы апельсінавы сок і малако Лоры. Што робіць кампутар, з'яўляецца яго праходзіць копіі апельсінавага соку і копіі малака да Лауры, так што што ў канчатковым выніку ўнутры гэтага латка гэта адно значэнне, і два ці OJ і малако, але іх копіі, так што на дадзены момант у гісторыі, ёсць гэта OJ і малако ў кожным з гэтых латкоў. Там у адзін і два у кожным з гэтых латкоў, і функцыя падпампоўкі сапраўды працуе. Гэта памяняўшы іх унутры з другога верхняга латка, але, што замена не ўплывае. І на аснове толькі некаторыя Асноўны прынцып мы ў казалі раней, і на самай справе ўсяго некалькі хвілін таму, што можа растлумачыць, чаму змены і б ўнутры свопу не мае ніякага ўплыву на х і у, хоць Я прайшоў х і ў функцыі падпампоўкі. Што тут ключавым словам, што можа спрошчана растлумачыць? Я думаю, што я чуў яго тут? АЎДЫТОРЫЯ: Return. СПІКЕР 1: Вяртанне? Не вярнуцца. Пойдзем з адным іншым. Што гэта? АЎДЫТОРЫЯ: [неразборліва]. СПІКЕР 1: Такім чынам, return-- мы маглі зрабіць зваротны працу ў гэтай гісторыі, але ёсць яшчэ больш простае тлумачэнне. АЎДЫТОРЫЯ: Сфера. СПІКЕР 1: Сфера. Я вазьму сферу. Так сфера, успомніць, дзе наша х і ў абвешчаныя. Яны абвешчаныя ўнутры з асноўнай прама тут. і б, між тым, з'яўляюцца фактычна абвясціў ўнутры своп, не зусім у фігурныя дужкі, але да гэтага часу у агульнай вобласці падпампоўкі. І так на самой справе, а і б існуюць толькі ў гэты латок ад Анненберг, гэта Другі кавалак кода. Такім чынам, мы сапраўды змяняючы копію, але што на самой справе не ўсё, што карысна. Такім чынам, давайце зірнем на гэта крыху ніжэй ўзроўню. Я збіраюся вярнуцца ў Каталог Крыніца, і я збіраюся першы павелічэння тут, і проста каб пацвердзіць, што я знаходжуся ў гэтым больш акно тэрмінала, Праграма па-ранейшаму вядзе сябе як, што. Выкажам здагадку зараз, што гэта ня наўмысна. Відавочна, я хацеў своп для праца, таму ён адчувае сябе, як блашчыцы. Цяпер я мог пачаць дадаваць Шмат Е-х да майго кода, Раздрукаваўшы х тут, у больш тут, тут, бы сюды. Але, шчыра кажучы, гэта, верагодна, што вы рабілі на працягу некалькіх тыдняў Зараз, у працоўны час і дома пры працы на psets, спрабуючы знайсці некаторыя памылкі. Але вы ўбачыце, калі вы яшчэ гэтага не зрабілі, што праблема ўсталяваць тры знаёміць вас на каманду пад назвай GDB, дзе GDB, GNU адладчык, мае сабе цэлую кучу асаблівасці, якія могуць на самай справе давайце зразумець сітуацый як гэта, але больш пераканаўча, вырашаць праблемы і знаходзіць багі. Так што я збіраюся зрабіць гэта. Замест ./noswap, я замест збіраецца запусціць GDB ./noswap. Іншымі словамі, я збіраюся запускаць мае Праграма не ў Bash, наш новы сябар сёння. Я збіраюся запускаць мае Праграма noswap ўнутры гэтай іншай праграме пад назвай GDB, які з'яўляецца адладчык, які гэта праграма, якая была распрацавана, каб дапамагчы вы, людзі, знайсці і выдаліць памылкі. Так што, калі я ударыў Запусціце тут, ёсць зверскае колькасць тэксту што вы сапраўды ніколі не павінны чытаць. Гэта істотна адцягненне з каманднага радка, якая Я збіраюся ударыць Control-L ўставаць у верхняй там. Гэта запрашэнне GDB. Калі я хачу, каб запусціць гэтую праграму зараз, як гэты маленькі шпаргалку на сёння слайд мяркуе, Run з'яўляецца першым Каманды, якія мы мелі на ўвазе ўвесці. І я проста хачу, каб надрукаваць забягаюць сюды ўнутры GDB, і на самай справе ён пабег маю праграму. Зараз ёсць некаторыя дадатковыя Выхады экране, як гэта, але гэта GDB проста быць анальны і кажа нам, што адбываецца. Вы сапраўды не трэба турбавацца аб гэтых дэталях, прама цяпер. Але тое, што сапраўды выдатна аб GDB, калі я зраблю гэта again-- Control-L ачышчае screen-- адпусціць мяне наперад і тып "зламаць галоўны", тым самым, калі я ударыў Enter, усталяваўшы, што гэта завецца кропкай перапынак у noswap.c, радок 16, які з'яўляецца, дзе GDB высветлілі маю праграму на самай справе з'яўляецца, мая функцыя на самай справе. Гэта мы будзем ігнараваць зараз але гэта адрас ў памяці спецыяльна для гэтай функцыі. Так што цяпер, калі я друкую працаваць, заўважыць, што гэта крута тут. Мая праграма разбівае на лініі I сказаў GDB, каб прыпыніць выкананне ст. Так што я не павінен зараз змяніць свой код, дадаць PRINTF-х, перасабраць іх паўтор яго, змяніць, дадаць некаторыя PRINTF-х, захаваць яго, перакампіляваць яго, запусціць яго. Я магу проста хадзіць па маёй праграме крок за крокам за крокам у чалавечай хуткасцю, ня на Intel-ўнутры віду хуткасці. Так што цяпер заўважыць гэтую лінію з'яўляецца тут, і калі я вярнуся у маёй праграме ў Gedit, заўважыць, што гэта на самай справе Самая першая радок кода. Там у лініі 16 ст Gedit. Там у лініі 16 ст GDB, і нават хоць гэтага чорна-белага інтэрфейсу хай не палічыць як карыстальнік прыязны, гэта азначае, што лінія 16 ня быў выкананы пакуль няма, але гэта збіраецца быць. Так бо калі я тыпу друку х, ня Е, проста раздрукаваць х, Я атрымліваю некаторыя фіктыўныя значэння там нуля, таму х ня быў ініцыялізаваны яшчэ. Так што я збіраюся ўвесці наступны, або, калі вам хачу быць незвычайны, проста п на наступны. Але калі я друкую наступны увядзіце, цяпер заўважыце, што ён пераходзіць да радка 17. Так лагічна, калі я выконваецца радок 16 і цяпер я друкую Print X, што я павінен убачыць? Адзін. А цяпер гэта, па агульным прызнанні ў зман. $ 2 гэта проста мудрагелісты спосаб, калі вам хачу звярнуцца да гэтага значэння пазней, Вы можаце сказаць: "знак даляра два." Гэта як зваротнай спасылкі. Але цяпер, проста ігнараваць яго. Што цікава, у чым справа ад знака роўнасці. І зараз, калі я друкую наступны раз і друк у, я павінен бачыць 2. Я таксама магу зараз друкаваць х зноў, і, шчыра кажучы, калі я атрымліваю крыху заблытаўся, дзе я знаходжуся, я магу спіс для спісу увядзіце і проста паглядзець, некаторы кантэкст вакол кропка на самай справе я ў. І зараз я магу тыпу Наступны, і там х 1. Цяпер я друкую наступны. О, у ёсць 2. І зноў, гэта збівае з толку, таму выхад GDB ў будзе змешвацца з маёй уласнай прадукцыі. Але калі вы трымаеце ў розуме, па пазіраючы назад і наперад на ваш код або кладкі яго бок бок, магчыма, вы будзеце бачыць, што на самой справе я проста пакрокавага маёй праграме. Але звярніце ўвагу, што адбудзецца далей, літаральна. Вось радкі 22. Адпусьці мяне над ім, тым самым перамяшчаючы на да 23, а калі я друкую х цяпер, яшчэ адзін. І калі я друкую ў цяпер, яшчэ адзін. Так што гэта не карыснае практыкаванне. Такім чынам, давайце зноўку гэта. Дазвольце мне вярнуцца да зверху і тып запуску зноў. І гэта кажа праграму які адладжваць ўжо пачалася, пачалі з самага пачатку. Так, давайце зробім гэта зноў. І на гэты раз давайце рабіць далей, Далей, наступны, наступны, наступны, але цяпер пачынаецца самае цікавае. Цяпер я хачу, каб ступіць ў своп, так што я не ўводзіце наступны. Я друкую крок, і цяпер заўважаюць падскочыла мяне noswap.c лініі 33. Калі я вяртаюся ў Gedit, што лінія 33? Гэта першае фактычнае радок кода ўнутры свопу. Што прыемна, таму што цяпер я магу выгляд капацца і атрымаць цікава адносна таго, што адбываецца сапраўды там. Дазвольце мне друкаваць TMP. Вау. Чаму TMP ёсць некаторыя з розуму, падробленым значэнне смецце? АЎДЫТОРЫЯ: Гэта не быў ініцыялізаваны. СПІКЕР 1: Гэта не быў ініцыялізаваны. І сапраўды, калі вы запускаеце праграму, Вам даюць цэлы букет памяці аперацыйнай сістэмай, але вы ня ініцыялізуецца любыя значэння, так што біты вы бачым тут, хоць гэта гэты вар'ят вялікі негатыў лік, проста азначае, што тыя рэшткі ад некаторыя папярэднія выкарыстанне гэтай памяці, хоць у мяне не я меў патрэбу ў ім яшчэ. Так што цяпер я збіраюся ісці наперад і тып Наступны, і, калі я цяпер тыпу друку TMP, што я павінен убачыць? Які б ні быў кошт была, першы аргумент, толькі як х быў першым рэч перадаецца ў, так і х павінны быць такімі ж, так друкаваць TMP павінны надрукаваць мне адзін. Так што вы ўбачыце ў праблемнай набору тры падручнік роду на GDB, але разумею, што гэта пачатак з погляду на інструмент, які будзе на самой справе дапамагчы вам вырашыць праблемы такім чынам, значна больш эфектыўна. Што мы, у канчатковым рахунку збіраюся зрабіць у сераду гэта пачаць адхіліце некалькі слаёў і выдаліць некаторыя дадатковыя колы. Гэта, што называецца радок, мы выкарыстоўвалі на працягу некаторага часу, мы збіраемся павольна адняць ад вас і пачаць казаць пра то больш эзатэрычныя вядомы як сімвал *, але мы збіраемся зрабіць гэта прыгожа і спачатку пяшчотна, хоць паказальнікаў, як яны называюцца, можна зрабіць некаторыя вельмі дрэнныя рэчы, калі злоўжываць, гледзячы на ​​невялікі Claymation ад наш сябар Нік Parlante з Стэнфорда Універсітэт, прафесар ў кампутары навука, хто сабраў гэтую прэв'ю таго, што павінна прыйсці ў гэтую сераду. [ВИДЕОВОСПРОИЗВЕДЕНИЕ] Эй, Бинки. Просыпайся. Гэта час для паказальніка весялосці. -што Што? Даведайцеся аб паказальнікаў? О, станоўчы герой! [END ВИДЕОВОСПРОИЗВЕДЕНИЕ] СПІКЕР 1: Гэта чакае вас у сераду. Ўбачымся тады. [ВИДЕОВОСПРОИЗВЕДЕНИЕ] -І Цяпер, Deep Thoughts, па Daven Фарнэме. Чаму мы вывучаем C? Чаму б не +? [Смех] [END ВИДЕОВОСПРОИЗВЕДЕНИЕ]