>> [Музички]
>> ЗВУЧНИЦИ 1: Во ред, ова е CS50, и ова е почеток на недела четири,
и како може да се чуе или читање, светот е крај.
Случува во целиот интернет е знаењето и свеста
на бубачки во програмата, програмски јазик наречен баш.
Ова е прекрасно брендирани како Shellshock, или баш врата,
но статии како овие не е невообичаено.
И всушност, многу од нив донесе врати сеќавањата на Heartbleed,
што може да се забележи во притиснете назад минатата пролет, кој
на сличен начин беше прилично драматична.
Сега на оние од вас тука денес, колку од вас имаат,
дури и ако не го разбирате она што тоа е за сите, слушнале за Shellshock?
Добро, и колку од вас имаат компјутери кои се ранливи?
Добро, треба да има далеку, далеку повеќе раце до сега, од причини што ќе видиме.
>> Ајде да ги погледнеме во она што е се случува во медиумите
а потоа го објаснам малку тука за нас технички.
>> ЗВУЧНИЦИ 2: Експертите за безбедност предупреди дека сериозен недостаток можев
биде за да се влијае на стотици милиони во светот интернет корисници.
Значи, што точно е бубачка што е создадено наречен Shellshock, и она што не го прават тоа?
Па, Shellshock е исто така познат како Баш грешка, софтверот го експлоатира.
Хакери употреба на вирусот на скенирање ранливи системи за трчање Linux и Unix
оперативни системи и потоа да ги зарази.
Баш е командната линија школка.
Ова им овозможува на корисниците прашање команди за да започне програми и функции во рамките софтвер
со впишување на текст.
Тоа обично се користи од страна на програмерите и не треба да биде отворен за надворешниот свет,
иако Shellshock менува тоа.
>> Па, worringly, некои аналитичари предупредуваат дека би можело да биде поголема закана,
бидејќи Shellshock овозможува целосно контрола на инфицирани машина,
додека Heartbleed дозволено само хакери да ги шпионираат компјутерите.
Тоа е така сериозна, тоа е беше оценет 10 од 10
за сериозноста од страна на Националната База на податоци за ранливост.
2/3 од сите веб-сервери се во ризик, вклучувајќи и некои Mac компјутери.
Па, бидете сигурни дека се закрпи на вашиот системи.
Секој хостинг веб-сајт трчање погодените оперативни системи
треба да се преземе акција што е можно поскоро.
Секој кој може да си дозволи таа треба да изгледа на нивните следење и веб апликација
firewalls да внимавате за било напади.
ЗВУЧНИЦИ 3: Најлошото нешто што може да се случи е
дека некој ќе напише код кој автоматски ќе одат и скенирање
на интернет и да влијае сите овие компјутери.
И еднаш тоа го прават, добро, најлошото нешто што можеше да стори
е само избришете сè, или затвори сајтови надолу.
Па ние може да се види штета од таа точка на гледање,
каде што ќе има злобници кои само одлучи да предизвика хаос
со тоа што системите надолу или бришење на датотеки, и работи како што.
ЗВУЧНИЦИ 2: Некои велат дека ова е една од најтешките да се измери
грешки во години, и тоа може да трае со недели или дури
месеци за да се утврди неговата крајна влијание.
>> ЗВУЧНИЦИ 1: Значи сето тоа е вистина, но смешно е, скоро сите
на слики го видеше, освен можеби на тастатурата,
нема никаква врска со бубачки она.
Сервери и жици и така натаму, Тоа е вид на тангенцијално поврзани,
но во суштина тоа е всушност прилично запознаени што се случува тука.
Всушност, дозволете ми да одат во нашите CS50 апаратот.
Дозволете ми да оди напред и да се зголеми на прозорецот на терминалот тука.
А вие момци го користат ова, или вградени верзија од него,
во gedit со цел да им пишуваат програми, тип команди, и така натаму,
и ова е всушност, и има е за недели, баш, B-A-S-H.
Ова е Bourne-школка повторно, која е само фенси начин да се каже,
ова е програма која има трепка брзо, ефикасно,
кој седи таму те чека за влез за вас.
И тоа е команда линија интерфејс преку кој
вие момци се работи команди и конечно составување, а потоа работи
програми.
>> Но, баш е исто така програмирање јазик во следните смисла.
Вие знаете дека постојат команди како CD и ls и, исто така, ѕвекот и други,
но може да се дефинира свој команди од нивно спроведување во баш.
Сега не се случува да се оди во големи детали
како да баш на програмскиот јазик, но знаат, на пример, дека во овој момент,
нема команда наречен "здраво".
Така што може да се најде во еден од овие пакети.
Тоа не е инсталиран на мојот компјутер.
Прашајте го вашиот администратор.
Но, ако јас сакам да има програма наречен "Здраво" во баш или во мојата брза,
Јас всушност може да го користат синтаксата што е слично C. Тоа не е сосема ист,
но изгледа доста сличен на функција, иако недостасуваат некои детали.
Ништо не чини да се случи, но сега, ако јас типот "здраво"
што всушност може да напише програма, а не во C, не е во Јава,
не во друга програмирање јазик, но во баш себе.
>> Сега клучот овде е дека сум го напишала на именува сакав да даде оваа нова команда,
и загради, исто така, симбол на ова е во функција.
Како настрана, исто така можете да направите забава работи, а всушност, дури и на Mac OS,
ова е програма наречена терминал.
Таа доаѓа вграден во никого компјутер кој има Мек во оваа соба,
и може да направи слични работи во Mac Оперативен систем, но може да се оди повеќе од тоа.
И ова е малку површни, но тоа е вид на забава.
Бев потсети ова утро, кога размислувам ова преку,
на малку игра јас се користи да игра со една од поранешните TFS CS50 на
при што секој пат кога тој би одиме подалеку од неговата тастатура со екран отклучен,
Би извршување на команда како this-- ", велат здраво."
И сега секој пат кога тој се врати во својата тастатура откако ќе го отвори екранот
и тој ќе седне, се обиде да направи некои работи,
листа на содржината на неговиот directory--
>> [AUDIO ИЗВЕДБА]
>> -Hello.
Здраво.
>> ЗВУЧНИЦИ 1: Значи, во праведноста, тоа не е всушност "здраво".
Тоа беше обично нешто повеќе слично на that--
[AUDIO ИЗВЕДБА]
-Beep.
ЗВУЧНИЦИ 1: --that јас would-- па неговиот компјутер ќе
колнам во него секое време тој всушност седна на тастатурата.
И многу брзо го сфатиле нема да го напушти неговиот екран отклучена.
Но, ова сугерира вид глупаво забава што ќе
може да има со нешто како баш.
Но, тоа е малку повеќе сериозни, да бидете сигурни, од тоа.
И всушност, ова е еден од најопасниот и долготрајни грешки
што навистина го погоди светот на глобално ниво.
Овој баг е околу за некои 20 години,
и ќе се удри во само момент од својата релативна едноставност.
>> Значи ова е претставник команда дека ако
поседувате Мек, буквално во моментов кога имате капакот се отвори,
може да се обидете пишување во кои програма наречена терминал.
Терминал е под Апликации Utilities--
еднаш, на Windows корисниците не мора да се се грижи за овој конкретен threat--
но оние од вас со Macs да напишете ова во прозорец како ќе го направите тука,
и ако не напишеш дека во оваа програма
наречен терминал, како јас ќе се направи сега, ако видите зборот "ранливи"
Вашиот компјутер е подложни на експлоатација.
>> Сега што значи дека всушност значи?
И ова е значително некои прилично лудо синтакса,
но ајде барем извлече некои од интересните аспекти.
Значи има некои синтакса што изгледа малку познато, барем од C
и програмирање поопшто.
Гледам некои загради, semicolons, кадрави загради, и такви,
но излегува дека овој глупава работа тука во жолта
во суштина е функција дека не прави ништо.
Дебелото црево средства не прават ништо, и запирка значи да престане да прави ништо.
Па во внатрешноста на овие кадрави загради, фактот
што имаат еднаков знак на лево, овој
е суштински креирајќи на команда или променлива,
наречен X, и пренесување дека жолта малку код таму.
Тоа би можело да биде нешто како "ехо здраво "или" велат бип "или нешто
слично на тоа.
Но известување, ако твоите очи талкаат понатаму кон десно,
има уште оваа линија од само на крајот на таа точка-запирка.
"Ехо ранливи", а потоа после тоа има уште повеќе.
Друга точка-запирка, баш -c :.
>> Па скратам приказната, оваа линија на кодот е
доволни за огромна компјутер, кој е
подложни на правење на нешто што сакате тоа да се направи,
бидејќи има грешка во баш при иако баш требаше да престанат
читање линии на командата право таму по жолта текст,
за 20-плус години бубачка, Баш всушност бил читање
надвор од тоа запирка и прилично многу прави она што е кажано.
>> Значи она што е импликација на што на крајот?
Јас само рече "ехо Здраво" или "ехо ранливи"
но што ако сте направиле нешто всушност злонамерни, како РМ -rf *,
кои вие не би некогаш напишан пред,
и искрено најверојатно не треба прерано,
бидејќи може да се направи многу штета со неа.
Зошто?
РМ го прави она што, се разбира?
Отстранува.
* Значи што?
Сите.
Па тоа е т.н. вајлд карта, па тоа значи дека
избришете се што е во на тековниот директориум.
-r се случува да значи рекурзивен, што значи дека ако она што сте бришење
е директориум, и во внатрешноста на таму е други датотеки и други директориуми,
рекурзивно се нурне во таму и бришење на сето тоа.
И ѓ е најлошиот на сите нив.
Некој знае што значи -f тука?
Сила.
Па сила средства, па дури и ако ова е лоша идеја,
го прават тоа без мене поттикнувајќи за понатамошно потврда.
Па, знаете, ние се смееме на ова, но искрено, јас веројатно
тип овој повеќе пати на ден, бидејќи реалноста
е тоа е најбрзиот начин да се избришете цел куп работи.
Но, дури и имам направено некои штета.
>> Но, ако сте во ситуација да трик компјутер во дефинирање на некои глупави променлива
или функција наречена X, но потоа трикови на компјутер во извршување
надвор од границите на кои функција, надвор од тоа точка-запирка,
сте навистина би можеле да трик компјутер во извршување на нешто како РМ -rf
или е-мејл команда или командата Copy.
Нешто буквално можете да го направите со компјутер, без разлика дали тоа е бришење на датотеки,
создавање на датотеки, спамирање некого, напад некои на серверот од далечина,
ако може да се изрази со командата,
може да трик компјутер во тоа го прават.
>> Сега што е пример за како може да го направите ова?
Па, има многу на компјутери на интернет трчање баш.
Сите од нас Mac корисниците се меѓу нив.
А многу Линукс сервери се меѓу нив, како и, и Unix сервери.
Прозорци повторно добива релативно сноселе
освен ако не сте го инсталирале специјален софтвер.
Сега многу сервери, за пример, работи веб сервери,
и всушност Линукс е можеби најпопуларниот оперативен систем
да работат на компјутери на интернет кои се служи веб страни.
Сега како што ќе видиме подоцна во семестар, кога
ќе испрати барање од Вашиот browser-- Хром,
Internet Explorer, whatever-- со оддалечен сервер,
излегува дека иако само ја внеле www.example.com,
Вашиот интернет пребарувач е испраќање на порака тоа е малку повеќе arcane, како ова.
>> Но забележите малку нешто чудно.
Првите две линии Никогаш не сум видел,
но тие не изгледаат особено опасни.
Но се забележи она што сум го украдени за третата линија овде.
Ако лошо момче биле за да пратите порака како оваа од неговиот или нејзиниот компјутер
на ранливи Mac или ранливи Линукс сервер,
смешно е што баш, тоа е толку едноставно малку командната линија,
е сеприсутно и честопати се користи за суштина изврши
на содржината на порака што ја добива.
И со таа логика, може да се трик на веб сервер, според тоа,
со испраќање на нешто како Корисникот застапник, кои обично
би требало да се каже името на вашиот интернет пребарувач.
Корисникот застапник Хром, пристап Агент Интернет Истражувач, пристап Агент Firefox, овој
е само на вашиот интернет пребарувач начин на идентификување на себе.
Но ако лошо момче многу умно вели, мм мм, јас сум
нема да ви кажам она што мојот интернет пребарувач е,
Јас наместо ќе ви испрати оваа криптичната изглед нешто со РМ -rf
* Во него, вие буквално може да измамува ранливи веб сервер на интернет
во извршување токму тоа има за бришење на сите датотеки.
И искрено, тоа не е дури и на најлошото од него.
Можете да направите ништо.
Можете да започнете дистрибуирани denial of service напади
ако ви испрати оваа порака на Целиот гроздовете на веб сервери
а потоа ги имаше сите нив слезе, за пример, на Harvard.edu сервери,
и можете да го решите тресне на подлец од нив
од страна на мрежата на сообраќајот, кој беше во спротивно предизвикани од овој лошо момче.
>> Значи, скратам приказната, речиси сите во оваа соба кој е сопственик на Mac
е подложен на тоа.
На надеж е дека освен ако не сте водење на веб сервер на вашиот лаптоп,
и освен ако не сте всушност конфигуриран тоа да се овозможи нешто како SSH во неа,
сте всушност безбедно.
Тоа е ранлив, но нема еден се обидува да добие во вашиот лаптоп,
така што вид на може да бидат сигурни.
Сепак, на Apple наскоро биде ажурирање на фикс за ова.
Светот на Linux веќе има издадено голем број на поправки за Fedora и Ubuntu
и други верзии на Linux, и навистина ако извршувате ажурирање 50 во апаратот,
дури и дека исто така ќе биде ажурирани и корегирани.
Но, тоа исто така не има навистина е ранлива,
бидејќи освен ако немате tinkered со апаратот
и направи вашиот лаптоп јавно достапен на интернет, кој не е
стандардно, сте всушност е во ред, бидејќи
на firewalling и други техники.
>> Но, тоа е екстремен пример за бубачка дека ние сме живееле за буквално 20
години, и кој знае дали некој сето ова време знае за тоа?
И всушност, ова е еден од основните предизвици
што ќе видиме подоцна во семестар за безбедноста,
е дека исто како и во реалниот свет, добрите момци се на штета.
Да се ​​задржи на лошите момци надвор, ние треба да бидете сигурни дека секој вратата е заклучена,
дека секој прозорец е сигурно, дека секоја точка на влез во дом
е безбеден да се задржи на лошите момци надвор.
Но, она што го прави лош човек мора да направите за да всушност компромис вашиот дом
и крадат од вас?
Тој или таа само треба да се најде еден отклучен врата, еден скршен прозорец, или нешто
заедно оние линии, а тоа е истото во компјутерска безбедност.
Може да се напишат милиони линии на програмски код
и да потрошат стотици или илјадници на часови обидувајќи се да го поправи,
но ако се направи само една грешка во точноста,
може да се стави на целиот систем и навистина во овој случај, на целата интернет
и светот во ризик.
>> Значи, ако сакате да дознаете повеќе во врска со овој, одете на овој URL тука.
Нема потреба за акција вечерва освен ако не сте
меѓу оние кои се чувствуваат поудобно дека се работи свој веб-
сервер, во кој случај треба, Всушност, надградба на вашиот софтвер.
>> И тоа исто така е насловот на говор, а сега на хартија,
дека ние сме поврзани на веб-страница се разбира за денес.
Тоа беше од страна на колеги име Кен Томпсон, кој
е прифаќање на многу познати награда во компјутерски науки,
и тој даде говор неколку години Пред, во суштина на оваа иста тема.
Барајќи луѓе на прашањето, треба навистина
доверба, во крајна линија, софтвер кој сте биле дадени?
На пример, сите ние имаме Пишувам програми,
и ние сме биле составувањето на нив со ѕвекот.
И да го вашето знаење, сте писмени сите програми за CS50 каде што има
задната врата на сорти, има начин дека лошо момче, ако водење на вашата програма,
би можел да го преземе вашиот компјутер?
Веројатно не, нели?
Марио и алчен, и кредит.
Овие се сите прилично мали програми.
Ќе треба да биде прилично лошо ако, всушност,
направи вашиот целиот компјутер ранливи по пишување 10 или 20 линии на код,
или барем не се свесни за некои на безбедносните импликации.
Сега велам дека шеговито, но ние сме случува да се види и денес
и оваа недела тоа е всушност навистина, навистина лесно
да биде лошо и да се направи дури и кратки програми ранливи.
>> Но, за сега, барем, да сфатат дека прашањето се бара тука
е за ѕвекот на компајлерот.
Зошто сме биле верувајќи ѕвекот во последните две или три недели?
Кој е да се каже дека секој кој пишува ѕвекот немаа многу "ако" состојба таму
што во суштина се инјектира некои нули и оние во секоја програма се подготвува
кои ќе ги споделите со него или неа пристап вашиот компјутер кога сте во сон
и вашиот лаптоп капак е отворен и вашиот компјутер се извршува?
Нели?
Имаме овој вид на чест систем право сега каде се надеваме дека ѕвекот е legit.
Верувате дека апаратот е legit.
Верувате дека буквално секоја програма на вашиот Mac или PC е сигурен.
И како што сугерира оваа едноставна грешка, дури и ако тоа не е злопамтило,
тоа е апсолутно не веројатно да биде случај.
>> Значи треба да се плаши како пекол.
Искрено, не постои едноставна решение на овој и други
од еден вид на општествена свест на зголемување на комплексноста
дека ние сме зграда на врвот на нашите компјутерски системи,
и како се повеќе ранливи ние многу добро може да биде.
>> Сега со тоа, рече, Збег.
Па Збег е проблем постави три, и Збег е игра од недалечното минато
кои може да се сети, но за нас во проблем постави три,
тоа ни овозможува да се земе работите назад до еден степен
така што кога ние пишуваме програми, дури и во терминален прозорец како овој,
ние всушност може да работи, во крајна линија, графички програми не
за разлика од оние што ги имаше Пристап до гребење.
Значи ова е на вработените имплементација на Збег,
што е само оваа тула кршење игра, што се движите лопатка назад
и назад, и ќе го погоди топката против оние обоените цигли до врвот.
Па ова ни носат вид на врати таму каде
бевме во можност да биде многу брзо со нула, а сега со Ц,
спроведување на нашите сопствени графички кориснички интерфејси.
>> Но повеќе од тоа, овој проблем сет претставува првиот
во која ние си даваат сте еден куп на код.
И всушност, јас донесе експлицитна внимание на ова, затоа што особено
за оние кои се помалку удобно, овој Проблемот се постави, барем на прв поглед,
се случува да се чувствуваат како ние ги направивме до еден степен.
Бидејќи ние сме ви даде, за некои од пребарување
и сортирање на проблеми во pset, еден куп на код кој што напиша,
и неколку коментари кои велат "да"
каде што треба да се пополни во празни места.
Па не е премногу страшно, но тоа е прв пат
ние ви предавање код кој треба да се Првиот читаат, разбираат, а потоа додадете на
и заврши тоа.
>> А потоа со Збег, ние ќе го стори истото,
ви даваат неколку десетици повеќе линии на кодот кој, искрено, да ви даде
многу на рамката за играта, но запре кратко
спроведување на тули и топката и лопатка,
но ние не се имплементираат некои други карактеристики.
Па дури и дека на прв поглед, повторно, особено ако помалку удобно,
може да изгледа особено тешка и мислите дека има толку многу нови функции
што треба да заврши вашиот ум околу себе, и тоа е вистина.
Но, имајте на ум, тоа е слично на гребење.
Шансите се не сте ги користите сите сложувалката парчиња во гребење.
Шансите се дека не се грижи да заврши вашиот ум околу сите нив
затоа што сите го зеде беше брз поглед да се разбере, ох,
тоа е она што можам да направам со што загатка парче.
И навистина, во проблемот поставени 3 спецификации, ние ќе ви укаже
на документација која ќе ве запознаам со некои нови функции,
и на крајот на програмирање конструира што ги користите.
Услови, јамки, променливи и функции
ќе бидат идентични со она што сум го видел досега.
>> Па навистина, она што ние ќе им даде вас е некои мостра кодот кој
Ви овозможува да се создаде прозорец тоа не изгледа за разлика од ова,
и на крајот ја претвори во нешто сосема вака.
Па ги искористат предностите на CS50, разговараат канцеларија часа и повеќе,
и да ги преземат утеха во фактот дека на износот на кодот треба да се напише
е, всушност, не толку многу.
Првиот предизвик е само да се аклиматизирам се на некои кодот што сум напишал.
>> Прашања на pset3, Shellshock, или на друг начин?
>> ПУБЛИКАТА: Тоа изгледаше како минува низ со Збег
дека кодот е речиси објектно-ориентиран стил,
но мислев Ц беше објектно-ориентирана програма.
ЗВУЧНИЦИ 1: Одличен прашање.
Па во потрага преку дистрибуција код, кодот
ние напиша за pset3, за оние кои се запознаени, тоа
изгледа како да е малку објектно-ориентирана.
Краткиот одговор е, тоа е.
Тоа е приближување на тоа како ќе може да направи објектно-ориентиран код користење
јазик како C, но тоа е сепак на крајот процедурални.
Нема методи во внатрешноста на променливи, како што ќе видите.
Но, тоа е потсетува на тоа.
И ние ќе се види дека функцијата повторно кога ќе го добиеме во PHP и го вклучите Javascript-
кон крајот на семестарот.
Но, за сега, мислам на тоа како навестување на она што е да дојде.
Добро прашање.
Во ред.
Па се спојат вид беше како левата работи последен пат.
И се спојат вид е кул во смисла дека тоа беше толку многу побрзо,
најмалку врз основа на површен тестови што го правевме минатата недела, отколку, да речеме, меур
сортирање, селекција вид, вметнување вид.
И она што беше уредно премногу е само како посочно и чисто
можете да го изразиме.
И што да кажеме дека тоа е горниот граница на трчање време на спојување
вид?
Да?
>> ПУБЛИКАТА: N најавите n?
>> ЗВУЧНИЦИ 1: n најавите n, во право. n најавите n.
А ние ќе се вратам на она што навистина значи или каде што доаѓа од,
но ова е подобро од она трчање време
што сме го виделе за меур селекција и вметнување вид?
Па n квадрат. N на квадрат е поголем од овој,
па дури и ако тоа не е очигледно, знаат дека најавите n е помал од n,
Значи, ако правиш n пати нешто помал од n,
тоа се случува да биде помал од n квадрат.
Тоа е малку на интуиција таму.
Но, ние плати цената за тоа.
Тоа беше побрзо, но една тема која започна да се појават минатата недела беше ова Губитокот.
Добив подобри перформанси временски, но она што
морав да помине на други страна, со цел да се постигне тоа?
>> ПУБЛИКАТА: Мемориски.
ЗВУЧНИЦИ 1: Кажи повторно?
ПУБЛИКАТА: Мемориски.
ЗВУЧНИЦИ 1: Меморија, или простор поопшто.
И тоа не беше супер очигледно со нашите луѓе,
но се сети дека нашите волонтери се повлекува напред и излегувајќи
назад иако има низа тука, и како да има
втор низа тука тие би можеле да ги користат, затоа што
потребни некаде да се спојат овие луѓе.
Ние не само може да ги трампа во место.
Па се спојат вид потпора повеќе простор, кој
ние не треба со на други алгоритми,
но главата е дека тоа е многу побрзо.
И искрено, во реалниот свет простор овие days-- RAM меморија, хард диск space--
е релативно евтина, и така тоа е не е нужно лоша работа.
>> Значи, да се земе брз поглед, малку повеќе методично, во она што ние го сторивме
и зошто рече дека е n најавите n.
Значи тука се осум броеви и осум волонтери имавме последен пат.
И првото нешто што се спојуваат Вид ни кажа да направам е што?
ПУБЛИКАТА: Поделба на два дела.
ЗВУЧНИЦИ 1: Кажи повторно?
ПУБЛИКАТА: Поделба на два дела.
ЗВУЧНИЦИ 1: Поделба на два дела, во право.
Ова е многу потсетува на книгата на телефонот, на поделбата
и го освои поопшто.
Па ние погледна на левата половина.
А потоа еднаш рековме, вид на левата половина од елементите,
она што не можеме следната кажам?
Сортирате левата половина од левата половина, што ни овозможи да,
по делење на два дела, се фокусира на четири и два.
>> Како да го решите листа сега, во жолта, на големината на две, употребувајќи го спојуваат Сортирај?
И ја делат на половина, и сортирање на левата половина.
И ова беше местото каде што работи доби малку глупаво кратко.
Како да сортирате листата што е на големина на една, како овој број четири овде?
Тоа е подредени.
Ќе завршиш.
>> Но тогаш како ќе го решите листа на големина на една кога тоа е број два?
Па, истото, но сега она што беше третиот и клучен чекор во Merge Сортирај?
Ти мораше да се логирате на левата половина и десната половина.
И штом ќе го направи тоа, ние погледна на четири, ние погледна две.
Решивме сите во право, очигледно два прво место,
па ние се стави две во својата место, по што четири.
И сега мора да се вид на премотам касетата, и ова е вид на карактеристични
на алгоритам како Merge Вид, ја премотам касетата во меморијата.
Она што беше следната линија на приказната?
Што треба да се фокусира на следно?
На десната половина на левата половина, што е шест и осум.
>> Значи, дозволете ми само чекор во текот на овој без belaboring точка премногу.
Шест и осум, а потоа шест е сортирани, осум се подредени.
Се спојат заедно, како што, и сега следниот голем чекор
е, се разбира, сортирање десната половина од првиот чекор на овој алгоритам.
Значи ние се фокусира на еден, три, седум, пет.
Ние потоа се фокусираат на левата половина.
Левата половина од тоа, на десната половина на тоа, а потоа се спојат во еден и три.
Потоа на десната половина, а потоа левата половина на неа, а потоа на десната половина од тоа.
Се спојат во, и сега што чекор останува?
Се спојат големите левата половина и големите десната половина, па оди таму долу,
потоа две, а потоа три, а потоа четири, потоа пет, а потоа шест, а потоа седум, а потоа осум.
>> Па сега зошто е тоа на крајот открива, особено ако n и логаритмите повеќе
генерално доста да избега, барем во поновата историја?
Па, се забележи на висината на оваа работа.
Ние имавме осум елементи, и ние поделена тоа од страна на две, од страна на две, од страна на две.
Значи се најавите база две од осум ни дава три.
И да ми верувате дека ако малку маглива на тоа.
Но се најавите база две од осумте е три, па ние го направивме три слоеви на спојување.
И кога ќе се спои елементи, како многу елементи
се гледаме на секоја од овие редови?
Вкупно n, нели?
Бидејќи да се логирате на горниот ред, иако ние го сторивме тоа парче,
ние на крајот допре секој број еднаш.
А во вториот ред, да спојат овие списоци на големината две,
моравме да допре секој елемент еднаш.
А потоа тука навистина јасно во последниот ред,
моравме да се допре секоја од овие елементи еднаш, но само еднаш,
па тука лежи, тогаш, нашиот n најавите n.
>> И сега само да се направат работите малку повеќе формални за само еден миг, ако
беа до сега анализира овој на еден вид на повисоко ниво
и да се обидат да се одлучи, добро како може да се обратите за изразување на
трчање време на овој алгоритам само со гледање на неа, и не
со користење на contrived пример?
Па, колку време ќе ви кажам чекор како оваа во жолта ќе ги преземе,
ако n <2 врати?
Тоа е голема О на што?
Па јас гледам еден, па уште еден чекор, можеби два чекори, бидејќи тоа е ако
а потоа се врати, но тоа е постојана време, нели?
Па рековме О (1), и тоа е како ќе го изразат тоа.
Т, само да се работи време.
n е големината на влез, па t (n), само стилизиран начин
на велејќи дека работи време подадената на големина n
ќе биде од редот на постојана време, во O (1).
>> Но во спротивно, она што за ова?
Како би ја изразуваат трчање време на овој жолта линија?
Т на што?
Можете вид на може да измамник тука и одговори на моето прашање циклично.
Значи, ако трчање време во принцип ние само велат дека е T (n).
И сега сте вид на punting тука и велејќи дека, добро, само ги сортирате левата половина,
а потоа ги сортирате десната половина.
Како може ние симболично претставуваат трчање време на овој жолта линија?
Т на што?
Што е големината на влез?
N текот на две.
Зошто не можам да го кажам тоа?
И тогаш ова е уште една T (n / 2), а потоа повторно, ако јас се спојат две сортирани половини,
колку елементи одам мора да допре вкупно?
n.
За да можам да го изразат тоа, само за да биде вид на фенси,
како трчање време, воопшто.
T (n) е само трчање време на T (n / 2), плус T (n / 2), лево и десно половина половина,
плус О (n), што е веројатно n чекори, но можеби, ако јас сум со користење на два прста,
тоа е двојно повеќе чекори, но тоа е линеарна.
Тоа е некои број на чекори дека е фактор на n,
па ние би можеле да го изразат тоа што е оваа.
И ова е местото каде што сега ние ќе залог на назад на нашата гимназија по математика учебник
ние сме дека повторување на крајот завршува изедначување ова, n пати најавите n,
ако навистина прават математика повеќе формално.
>> Па тоа е само две перспективи.
Еден бројно со хард-кодирани репрезентативен примерок
користејќи осум броеви, и повеќе општ поглед на тоа како стигнавме таму.
Но, она што е навистина интересно овде е, пак, овој поим на велосипед.
Јас не сум се користи за петелки.
Јас сум вид на дефинирање на нешто во однос на себе,
не само со овој математичка функција,
но исто така и во смисла на овој псевдо код.
Оваа псевдо код е рекурзивен со тоа што две од своите редови
во суштина го кажувам да одат се користат за решавање на помали
проблемот на помала големина, а потоа повторно и повторно
и повторно се додека ние го омаловажавам до овој т.н. база случај.
>> Значи, да всушност подготви повеќе привлечни се-далеку од тоа како што следи.
Дозволете ми да одат во gedit и ги погледнеме некои од денешните изворниот код,
особено овој пример тука.
Сигма 0, која очигледно додава бројките со n.
Да видиме што е познато и непознати тука.
Прво имаме неколку вклучува, па ништо ново таму.
Прототип.
Јас сум малку маглива на ова по неколку дена,
но што велиме прототип на функција е?
ПУБЛИКАТА: [Беззвучен].
ЗВУЧНИЦИ 1: Што е тоа?
ПУБЛИКАТА: Ние го најавува.
ЗВУЧНИЦИ 1: Ние го најавува.
Значи сте настава ѕвекот, еј, всушност не спроведување на ова сеуште,
но некаде во оваа датотека, веројатно, ќе биде функција наречена што?
Сигма.
И ова е само ветување дека тоа се случува да изгледа вака.
Тоа се случува да се земе цел број како input-- и јас може да биде поексплицитни
и велат int n --and тоа е ќе се врати int,
но запирка средства, мм, ќе добие околу за спроведување на овој малку подоцна.
Повторно, ѕвекот е нем.
Тоа е само ќе треба да се знае што ви го кажам врвот до дното,
па ние треба барем да даде тоа навестување на она што е да дојде.
>> Сега да ги погледнеме главните тука.
Ајде да дојдете тука и види она што главната прави.
Тоа не е толку долго на функцијата и всушност конструкција тука е познато.
Јас декларирате променлива n, а потоа Јас отегчавам корисникот повторно и повторно
за позитивен цел број со користење getInt, и единствениот излез од овој циклус
еднаш на корисникот почитуваат.
Направите додека, ние се користи за да отегчавам на корисникот на тој начин.
Сега ова е интересно.
Јас прогласи int наречен "одговор".
Јас го вратената вредност се додели на функција наречена "Сигма".
Јас не знам што се уште, но Се сеќавам прогласување пред една момент.
И тогаш јас сум поминува во вредност, која на корисникот внесе во, n,
а потоа јас го пријавите одговорот.
Па ајде да дојдете назад за само еден миг.
Ајде да одиме напред во овој директориум, осигурајте се сигма 0, а всушност ја извршите оваа програма
и да видиме што се случува.
Значи, ако јас одам напред и да ја стартувате оваа програма, ./sigma-0,
и јас напишете во позитивна цел број како две, Сигма,
како грчки симбол имплицира, е само случува да додадете до сите броеви од
нула на до две.
Значи 0 плус 1 плус 2.
Значи ова се надевам дека треба да ми даде 3.
Тоа е се што прави.
И слично на тоа, ако јас ја извршите оваа повторно и јас го даде бројот три,
тоа е 3 плус 2, па тоа е 5, плус 1 треба да ми даде 6.
А потоа, ако јас се навистина луди и почнете да пишувате во поголеми броеви,
тоа треба да ми даде поголем и поголем износ.
Па тоа е се.
>> Значи она што не сигма изгледа?
Па, тоа е прилично јасна.
Тоа е како да се имплементира ова во изминатите неколку недели.
"Int" ќе биде тип на враќање.
Сигма е името, и тоа трае променлива m наместо n.
Ќе се смени до врвот.
Тогаш ова е само здрав разум чек.
Ќе видиме зошто во еден момент.
Сега Изјавувам друга променлива, сума, да се иницијализира на нула.
Тогаш имам За јамка процесирањето, очигледно за јасност,
од i = 1 на до некоја = m, кое е без оглед на корисникот внесе во, а потоа
подигање на збирот вака.
А потоа се врати сумата.
>> Значи неколку прашања.
Еден, тврдам во мојот коментар дека ова избегнува ризикот од бесконечна јамка.
Зошто би преминува во негативен број предизвикаат, потенцијално, бесконечна јамка?
>> ПУБЛИКАТА: Вие никогаш не ќе стигнам м.
>> ЗВУЧНИЦИ 1: Никогаш не се постигне м.
Но м е донесен во, па ајде сметаат едноставен пример.
Ако m е донесен од страна на корисникот како негативна.
Без оглед на главните.
Главната нè штити од тоа исто така, па јас сум само
се навистина анален со сигма исто така да бидете сигурни дека
дека влезот не може да биде негативен.
Значи, ако m е негативен, нешто како негативна.
Што ќе се случи?
Па, јас ќе се се иницијализира на еден,
и тогаш ќе биде помалку од или еднакво на m?
>> Стојат од страна.
Дека was-- за да не, ајде да Никта оваа приказна.
Јас не побара тоа прашање, бидејќи ризикот дека јас сум алудирајќи на
нема да се случи, затоа што е секогаш ќе биде поголема than-- ред,
Го повлекувам тоа прашање.
Во ред.
Ајде да се фокусира само на овој дел овде.
Зошто Изјавувам некои надвор од јамка?
Известување на линија 49 Јас сум прогласена з внатрешноста на јамка,
но онлајн 48 Јас сум прогласена за некои надвор.
Да.
ПУБЛИКАТА: [Беззвучен].
ЗВУЧНИЦИ 1: Секако.
Значи прво и основно јас секако не сакаат да пријават и се иницијализира Збирот
на нула во внатрешноста на циклус на секоја итерација,
бидејќи ова јасно ќе победи Целта на сумирање на броеви.
Јас би ги менува вредноста назад до нула.
И, исто така, она што е уште повеќе arcane Причината за истата дизајн одлука?
Да.
>> ПУБЛИКАТА: [Беззвучен].
ЗВУЧНИЦИ 1: Токму така.
Сакам да го пристап надвор на јамка премногу за тоа што линија?
На 53.
И врз основа на нашето правило на палецот од неколку предавања пред,
променливи се scoped, навистина, на кадрави загради, кои ги опфаќаат.
Значи, ако јас не ја декларираат Збирот внатре на овие надворешните големи загради,
Јас не може да го користи во согласност 53.
Стави некој друг начин, ако јас прогласи сума во тука, или дури и во рамките на
За телефонска линија, не можев да го пристап во 53.
Променливата ефикасно ќе исчезнат.
Па неколку причини таму.
Но сега да се вратиме и да видиме што се случува.
Па сигма добива се нарекува.
Тоа додава до 1 плус 2 или 1 плус 2 плус 3, а потоа се враќа на вредноста,
продавници тоа во одговорот и printf тука Затоа гледам на екранот.
Значи ова е она што ние ќе го наречеме итеративен пристап, каде повторување само
значи со помош на телефонска линија.
A За јамка, додека јамка, а направите додека јамка, само прави нешто повторно
и повторно и повторно.
>> Но сигма е вид на уредни функција во кој би можел да се имплементира поинаку.
Што за тоа, што само да се вид на ладно,
дозволете ми да навистина се ослободи на многу забава
бидејќи оваа функција е навистина едноставно.
Ајде да омаловажавам одредување на само на своите четири основни линии
и да се ослободи од сите коментари и големи загради.
Ова е вид на умот-дува алтернатива имплементација.
Добро, можеби не ум-дува, но тоа е вид на посекси, сите во право,
да се погледне на овој многу повеќе посочно.
Со само четири линии на код, Јас прв пат ја имаат оваа разумност проверка.
Ако m е помалку од или еднакво на нула, сигма прави никаква смисла.
Тоа само би требало да биде во овој случај за позитивни броеви,
па јас сум само ќе врати нула произволно
така што ние барем имаме некои т.н. база случај.
>> Но, тука е убавината.
Интегритет на оваа идеја, додавајќи дека броеви од 1 до n, или m во овој случај,
може да се направи според начинот на полагање на префрлуваат одговорноста.
Па, што е сума од 1 до м?
Па, знаеш што?
Тоа е исто како збир на м плус сума од 1 до m минус 1.
И знаеш што?
Што е сигма од м минус 1?
Па, ако сте вид на следат овој логично, тоа е исто како м минус 1
плус сигма од м минус 2.
Па можете да вид на just-- ова е како, ако сте само
обидувајќи се да одиме на нерви на пријател и тие ви поставам едно прашање,
можете вид на одговори со прашање, можете вид на може да ги задржи полагање на префрлуваат одговорноста.
Но, она што е клучот е во тоа што ако продолжуваш правење на прашањето помали и помали
и помали, ќе бидете не прашувајќи што е сигма
на n, што е сигма од n, што е сигма од n?
Прашувате што е сигма од n, што е сигма
од n минус 1, што е сигма од n минус 2?
На крајот на вашето прашање се случува да стане она што?
Што е сигма од една или нула, некои многу мала вредност,
и веднаш штом ќе се добие тоа, вашиот пријател,
не се случува да побараат истото прашање повторно,
сте само ќе да се каже, ох тоа е нула.
Сме готови да игра овој вид глупаво циклична игра.
>> Па рекурзијата е чин во програмирање на функција која себеси се нарекува.
Оваа програма, кога состави и да ја стартувате, е ќе се однесуваат на ист начин,
но она што е клучот е во тоа што во на функција наречена сигма,
постои линија на код кадешто ние се јавувате,
кои нормално би било лошо.
На пример, што ако јас прв пат составена оваа, така бидете sigma--
направи сигма 1 ./sigma-1.
Позитивен цел број, ве молам, 50 1275.
Па што функција се чини дека биде, врз основа на еден тест, точни.
Но, што ако јас се добие малку опасна и да го избришете т.н. база случај,
и само велат, добро јас сум само што овој покомплицирано отколку што е.
Ајде да се пресмета сигма со преземање на m и потоа додавање на
во сигма од м минус еден?
Па, што ќе се случи овде?
Ајде да одзумирате.
Ајде да го прекомпајлирате програма, освен тоа, повторно компајлирајте на програмата,
а потоа подготвени ./sigma-1 зумирање, внесете позитивен цел број ве молам, 50.
Колкумина од вас се подготвени да fess до види тоа?
>> Во ред.
Така што ова може да се случи за голем број на причини,
и искрено оваа недела ние сме за да ви даде повеќе од нив.
Но, во овој случај, обидете се на разумот наназад
она што може да се случи овде?
Сегментација грешка, ние, изјави минатата време, се однесува на еден сегмент на меморија.
Нешто лошо се случило.
Но, она што беше механички дека отиде криво
тука, бидејќи на мојата отстранување на таа т.н. база случај,
каде што се вратив на хард-кодирани вредност?
Што мислите беше во ред?
Да.
>> ПУБЛИКАТА: [Беззвучен].
ЗВУЧНИЦИ 1: Ах.
Добро прашање.
Па големината на бројот дека сум бил сумирање
доби толку голема што надминува големината на меморијата простор.
Добра идеја, но не суштински ќе предизвика несреќата.
Кои можат да предизвикаат број преливник, каде битовите само флип над
и тогаш грешка навистина голем број за како негативен број,
но тоа само по себе не ќе предизвика несреќата.
Бидејќи на крајот на ден еден int се уште е 32 бита.
Вие нема да случајно украде 33. малку.
Но и добра мисла.
Да.
>> ПУБЛИКАТА: [Беззвучен].
ЗВУЧНИЦИ 1: Методот никогаш не престане да работи,
и навистина се нарекува повторно и повторно и повторно и повторно
и повторно, и ниту еден од тие функции некогаш
заврши, бидејќи нивната единствена линија на код себеси повикува повторно и повторно
и повторно.
И она што е навистина случува овде, а сега
вид на може да се подготви овој сликовито.
Дозволете ми да одам во текот на слика за само еден миг.
Оваа слика, која на крајот ќе месо од
во повеќе детали, за она што се случува внатрешноста на меморијата на вашиот компјутер.
И излегува дека на на долниот дел од оваа слика
е нешто што се нарекува на магацинот.
Ова е еден дел од меморија, парче на RAM меморија,
тоа е само користи во секое време функција се нарекува.
Во секое време ви, програмер, јавете се на функција,
оперативниот систем, како Mac OS, Windows или Linux,
зграпчува еден куп на бајти, можеби неколку килобајти, можеби неколку мегабајти
меморија, ги рацете за вас, а потоа им овозможува на
ќе се кандидира на вашиот функција со користење на без оглед на променливи што ви треба.
И ако тогаш се јавите на друг функција и друга функција,
ќе добие уште една парче на меморија и уште парче од меморијата.
>> И, навистина, ако овие зелени коцки од Annenberg претставуваат дека меморијата,
тука е она што се случува првиот кога ќе се јавите функција сигма.
Тоа е како ставање на послужавник вака на она што е првично празен оџакот.
Но, тогаш, ако тоа послужавник се нарекува себеси, така да се каже,
повикувајќи друг пример на СИГМА, тоа е
како да прашуваш оперативниот систем, ooh, треба малку повеќе меморија,
дај ми го тоа.
И тогаш таа добива наредени на на врвот.
Но, она што е клучот овде е дека првата лента е сеуште тука,
бидејќи тој се повикува оваа втората лента.
Сега меѓувреме, сигма јавите сигма, тоа е како да прашуваш за повеќе меморија.
Добива наредени на овде.
сигма јавите сигма, тоа е друга лента што добива наредени тука.
И ако продолжите да го прават тоа, на крајот, каков вид на сајтот овој визуелен
за таа шема, што ќе се се случи со магацинот на коцки?
Тоа се случува да го надмине износот на меморијата на вашиот компјутер има.
И штом оваа зелена лента надминува хоризонтална линија
над магацинот и над зборот грамада, што ќе се вратиме во иднина,
тоа е лоша работа.
Грамада е различен сегмент на меморија,
и ако нека овие пепелниците купот и купот на,
ви се случува да се надмине свој сегмент на меморија,
и програма навистина се случува да се сруши.
>> Сега како настрана, оваа идеја на рекурзијата, според тоа,
јасно може да доведе до проблеми, но тоа не е нужно лоша работа.
Бидејќи сметаат дека, по сите, how-- и можеби
Ова се некои добивање навикнати да --how домот или како едноставна
дека спроведувањето на Сигма беше.
И ние нема да ги користат рекурзија сите дека многу во CS50,
но во CS51, и навистина било класа каде што можете да манипулира со структури на податоци
како дрвја или семејни стебла, кои имаат некои хиерархија,
тоа е супер, супер корисни.
Сега, како настрана, така што ќе како стремат компјутерски научници
се запознаени со некои од Гугл домашните шеги, ако одите на Google
и ќе се погледне до она што е дефиниција на, да речеме, рекурзија, влезе.
УХ-нели.
Како настрана, јас го зафрла неколку.
Ова беше како 10 минути маене ова утро.
Ако, исто така Гугл "накриво" известување со наведнување на главата slightly--
и тогаш ова е можеби повеќето грозоморно на сите
бидејќи некој поминал како нивниот ден спроведување на овој
неколку години ago-- ајде.
Ох, wait-- тоа е грешка.
>> Па се извршува на еден од Најголемата веб-сајтови во светот
се овие глупави малку велигденски јајца.
Тие веројатно се консумираат nontrivial бројот на линии на код
само така што ќе може да има малку забава работи како што.
Но барем сега ќе се некои од оние домашните шеги.
>> Сега ајде да ги разгледаме во некои од бели лаги ние сме кажувам на крајот,
и да почне да лупам назад некои слоеви технички
така што навистина се разбере она што се случува
и може да се разбере некои од заканите,
како Shellshock, дека сега започна да станува
на чело на секого внимание, барем во медиумите.
Па тука е многу едноставна функција што не враќа ништо, празнина.
Нејзиното име е трампа.
Таа ги зема во две променливи и тоа не враќа ништо.
Зема во a и b.
Така брз демонстрација.
Ние донесе овие горе.
Ние, како може да потрае малку се скрши тука за само еден миг
и имаат малку нешто да се напие.
Ако некој не би ум приклучување мене се тука за само еден миг.
Како за вас во канелени кошула?
Ајде до.
Само еден денес.
Ви благодарам, иако.
Добро, и ние имаме кои доаѓаат тука?
Што е вашето име?
>> ЗВУЧНИЦИ 4: Лаура.
>> ЗВУЧНИЦИ 1: Лаура.
Ајде до.
Па Лаура, многу едноставна предизвик денес.
Убаво да се Ио се исполнат.
Во ред.
Значи имаме малку млеко овде и имаме некои сок од портокал овде
и некои чаши дека ние позајмени од Annenberg денес.
>> ЗВУЧНИЦИ 4: позајмени.
ЗВУЧНИЦИ 1: И ќе одам напред и да ви даде половина чаша ова.
Во ред.
И ние ќе ви даде половина чаша млеко.
О, и само така што ќе може се сеќавам што тоа беше како,
Се сетив да се донесе ова и за денес.
Во ред.
Ако не би ум, ајде да видиме, ние може да ги стави над вашата очила
ако сакаш.
Ова ќе биде на светот од очите на Laura.
Во ред.
Значи вашата цел, со оглед две чаши течни тука, млеко и сок од портокал,
е се разменуваат две содржини, така што на сок од портокал оди во млеко чаша
и млекото оди во сок од портокал куп.
>> ЗВУЧНИЦИ 4: Дали можам да добијам друг чаша?
ЗВУЧНИЦИ 1: Јас сум толку мило те праша, иако тоа би било многу подобро снимка
ако не сте го праша.
Но да, можеме да ви понудиме една третина чаша тоа е празен, се разбира.
Во ред.
Па се разменуваат содржината таму.
Многу убаво.
Многу добар.
Го правиш ова извонредно внимателно.
И чекор три.
Во ред.
Одличен.
Голема аплауз ќе биде добро за Лаура.
Во ред.
Имаме малку разделба подарок за вас, но дозволете ми да ги преземат овие.
Ви благодарам многу.
Така едноставен пример, иако, да се покаже дека ако не
сакате да се разменуваат содржината на два контејнери,
или ајде да ги наречеме променливи, ви треба некои привремено чување
на сцената еден од содржината во толку дека всушност можете да го направите на swap.
Па навистина, ова изворниот код тука во C е претставник на токму тоа.
Ако сок од портокал е и млеко беше б, и сакавме да се разменуваат со две,
може да се обиде нешто креативно со истурање еден во друг,
но тоа веројатно не би заврши особено добро.
И така ние се користи од трети чаша, повик тоа мали, Т-М-Па од Конвенцијата,
и го стави на содржината на ОВ во тоа, тогаш се разменуваат една чаша,
тогаш стави ОВ во оригинални чаша, на тој начин
постигнување, токму онака како што Laura не, трампа.
>> Значи, да го стори токму тоа.
Дозволете ми да оди напред и да се отвори до еден пример што е
всушност, наречен "бр разменуваат ", затоа што тоа не е
едноставно направено како што мислат.
Значи во оваа програма, да се забележи дека Јас сум со користење stdio.h, нашиот стар пријател.
Имам прототип за swap до таму, кои
значи нејзино спроведување на веројатно долу,
и да видиме што оваа главна програмата ќе го направи за мене.
Јас прв пат прогласи int x добива еден, а int y добива две.
Значи мислам на оние што ОВ и млеко, соодветно.
А потоа јас само имаат printf велејќи дека x е ова
и y е ова, само за да можам да визуелно да видиме што се случува.
Тогаш сум printf тврдејќи дека сум Замена на две,
а потоа јас испечатите тврдат дека тие се заменети,
и јас испечатите x и y се повторно.
Значи овде во трампа е токму она што Лаура не,
и токму она што го видов на на екранот пред една момент.
>> Значи, да оди напред и да бидат длабоко разочарани.
Не прават трампа, и да ја стартувате без swap, зумирање во на излез тука.
Внесете x е 1, y е 2, Замена заменети.
x е уште 1, и y се уште е 2.
Значи иако, искрено, ова изгледа точно се допаѓа, иако повеќе технички,
она што Лаура не, не чини да се работи.
Значи, зошто е тоа така?
Па, излегува дека кога ние пишуваме програма како оваа
што има и главната, истакна тука, а потоа уште една функција, како и размената,
Нагласени тука, што го нарекува, светот
изгледа малку нешто како овие коцки пред една момент.
Кога главната прво ќе се вика, тоа е како да прашуваш оперативен систем
за малку меморија за сите локални променливи како x и y дека главната има,
и тие завршуваат тука.
Но, ако главната повици се разменуваат, како и главните минува да се разменуваат два аргументи, a и b,
сок од портокал и млеко, тоа не е како предавање на сок од портокал и млеко
Лора.
Што компјутер го прави тоа, тоа е поминува копии од сок од портокал
и копии од млеко за Лаура, така што она што е во крајна линија во внатрешноста на оваа лента
е вредноста еден и два, или ОВ и млеко, но копии од него,
така што во овој момент во приказната, има
е ОВ и млеко во секоја од овие коцки.
Има еден и два во секоја од овие коцки,
и swap функција е навистина работат.
Тоа им Замена внатре на вториот највисок послужавник,
но тоа Замена нема влијание.
И врз основа на само некои основниот принцип ние сме
зборуваше за порано, и навистина Пред само неколку минути, што
може да се објасни зошто се менува a и b во внатрешноста на swap
нема ефект на x и y, иако Јас помина x и y на swap функција.
Што е клучен збор што simplistically може да се објасни?
Мислам дека јас го слушнав тука?
ПУБЛИКАТА: Враќање.
ЗВУЧНИЦИ 1: Враќање?
Не се вратат.
Ајде да одиме со еден друг.
Што е тоа?
>> ПУБЛИКАТА: [Беззвучен].
>> ЗВУЧНИЦИ 1: Добро, така што можеме да return-- направи враќање работа во приказна,
но таму е уште поедноставно објаснување.
ПУБЛИКАТА: Обем.
ЗВУЧНИЦИ 1: Обем.
Ќе го земам обем.
Значи обемот, се сеќавам каде нашите x и y објавени.
Тие се прогласени внатре на главниот право тука.
a и b, пак, се ефикасно прогласени за
во внатрешноста на swap, не е сосема во на големи загради, но сепак
во општата област на swap.
И така навистина, a и b постојат само во овој послужавник
од Annenberg, ова Вториот парче од код.
Значи ние сме навистина промена на копија, но тоа не е навистина сето тоа корисно.
>> Па ајде да ги разгледаме во ова малку пониско ниво.
Одам да се врати во Извор директориум,
и јас одам да се прво зумирате тука, и само
да потврди дека сум во оваа поголем терминал,
На програмата се уште се однесуваме како тоа.
Да претпоставиме сега дека ова не е намерна.
Јасно сакав трампа на работа, па таа се чувствува како бубачка.
Сега би можел да започне додавајќи многу printf да мојот код,
печатење х овде, y над тука, тука, б овде.
Но, искрено, тоа е веројатно она што сте биле прави за неколку недели
сега, во работното време и дома кога работат
на psets обидува да најде некои грешки.
Но ќе видите, ако веќе не сте, тој проблем постави три се воведува
на команда наречен GDB, каде GDB, ГНУ дебагерот,
себе има бројни карактеристики кои всушност може да
нека се разбере ситуации вака, но повеќе убедливо,
решавање на проблеми и да се најде грешки.
Па јас ќе одам да го направите тоа.
Наместо ./noswap, јас сум наместо случува да се кандидира GDB ./noswap.
Со други зборови, јас ќе одам да се кандидира ми програмата не е во баш, нашиот нов пријател
денес.
Одам да се кандидира ми програма noswap внатре
на овој друг програма наречена GDB, која е дебагерот, кој
е програма која е дизајнирана да им помогне на сте луѓето ги најдете и избришете грешки.
Значи, ако јас хит Стартувај тука, има на крволочен количина на текст
дека навистина никогаш не треба да ја прочитате.
Тоа е во суштина одвраќање од брза, која
Одам да ја погоди Control-L да се нагоре на врвот таму.
Ова е GDB прашува.
Ако сакате да ја извршите оваа програма сега, како оваа мала измамник лист на денешната
слајд покажува, Run е првиот команди дека со цел да се воведе.
И јас сум само ќе да напишеш се кандидира до тука внатрешноста на GDB,
и навистина се стрча мојата програма.
Сега има некои дополнителни излези на екранот вака,
но тоа е само да се биде анален GDB и ни кажува што се случува.
Вие навистина не треба да се грижите за овие детали во моментов.
Но, она што е навистина кул за GDB, ако го направам ова again--
Контрола-L отвора screen-- да си одам напред и тип "скрши главни", со што,
кога ќе притиснете Ентер, поставување она што е наречен брејк на noswap.c,
линија 16, каде што е GDB сфатиле мојата програма, всушност,
е, мојот функцијата всушност е.
Ова ќе ги игнорираат за сега но тоа е адреса
во меморијата конкретно на оваа функција.
Па сега кога ќе внесете ден, забележи она што е кул овде.
Мојата програма крши на линија јас изјави GDB за да го паузирате извршување на.
Па јас не треба да сега ги променам моите кодот, додадете некои printf е, прекомпајлирате тоа, повторување
тоа, промена, да додадете некои printf е, освен тоа, повторно компајлирајте ја, таа работи.
Јас само може да оди преку мојата програма чекор по чекор по чекор на човечки брзина,
не на Интел-во вид на брзина.
>> Па сега забележите оваа линија се појавува овде, и ако се вратам
во мојата програма во gedit, забележите дека тоа е всушност
самиот првата линија на кодот.
Има линија 16 во gedit.
Има линија 16 во GDB, па дури и иако ова црно и бело интерфејс
не е скоро како корисник пријателски, тоа значи
таа линија 16 не е извршена сеуште, но тоа е за да се биде.
Па ако навистина сум тип на печатење x, не printf, само печати x,
Јас се некои лажни вредност има на нула, бидејќи x се уште не е иницијализирана.
Па ќе одам до напишеш, или, ако сакате да биде фенси, само N за следната.
Но, кога ќе тип следната влезат, сега забележите што се движи кон линијата 17.
Па логично, ако сум егзекутирани линија 16 и јас сега пишувате печатење x,
што треба да се види?
Еден.
>> А сега ова е значително збунувачки.
2 $ е само стилизиран начин, ако сакате да се однесуваат на таа вредност подоцна,
може да се каже "долар потпише две."
Тоа е како назад референца.
Но, за сега, само да го игнорираат.
Она што е интересно е она што е на правото на еднакви знак.
И сега, ако сум тип следната повторно и печатење на Y, јас треба да се види 2.
Јас може да исто така, сега се печати x еднаш, и искрено,
ако јас сум добивање малку збунет како да каде сум, јас да напишете листа за листа
и само да видиме некои контекст околу момент јас сум всушност во.
И сега јас да напишете следната, а x е 1.
Сега сум тип следната.
Ох, y е 2.
И повторно, тоа е збунувачки, бидејќи излез GDB на
се commingled со мојот излез.
Но, ако се има предвид, од страна на обѕрне назад и напред во вашиот код
или врска од страна од страна можеби, ќе
види дека навистина сум само Менувајќи мојата програма.
>> Но се забележи она што се случува следно, буквално.
Еве линија 22.
Дозволете ми да одат преку него, а со тоа да се пресели на до 23, и ако јас се печати х сега, уште еден.
И ако јас y печати сега, уште еден.
Така што ова не е корисна вежба.
Значи, да се повтори ова.
Дозволете ми да се вратам до врвот и видот се кандидира повторно.
И тоа е велејќи дека програмата тоа е се дебагира
почна веќе, започна од почетокот.
Да, да го направиме тоа повторно.
И овој пат да го направиме следниот, следната, следниот, следната, следниот,
но сега работите се интересни.
Сега сакам да влезете во swap, па јас не тип следната.
Јас тип чекор, и сега забележите дека ми скокна на noswap.c линија 33.
Ако јас се вратиме на прегледувачот, што е линија 33?
Тоа е првиот вистински линија код во внатрешноста на swap.
Што е убаво, бидејќи сега можам вид на ѕиркаат наоколу и да се љубопитни
за тоа што се случува навистина таму.
Дозволете ми да печатите мали.
Стој.
Зошто мали имаат некои луда лажен ѓубре вредност?
ПУБЛИКАТА: Тоа не е иницијализиран.
ЗВУЧНИЦИ 1: Не е иницијализиран.
И навистина, кога ќе ја стартувате програмата, ти си даде цел куп на меморија
од оперативниот систем, но не се иницијализира никакви вредности,
па што битови сте гледате тука, иако тоа е
овој луд големи негативни број, едноставно значи
дека тие се остатоци од некои претходни користење на тоа RAM меморија,
иако не сум мене тоа се потребни уште.
Па сега јас ќе одам да се оди напред и видот следната, и ако јас сега пишувате печатење мали,
што треба да се види?
Без оглед на вредноста на беше, a е првиот аргумент, само
како X е првиот нешто се пренесува во,
па и x треба да бидат исти, па печати мали треба да ми се печати една.
>> Па што ќе видите во проблем сет три е еден туториал на сорти на GDB,
но сфати дека ова е почеток на изглед на алатка која, всушност, ќе
да ви помогне да ги реши проблемите толку многу поефикасно.
Она што ние сме на крајот случува да се направи во средата
е да започнете да лупам назад неколку слоеви и се отстранат некои помошни тркала.
Дека нешто што се нарекува стринг ние сме се користи за некое време,
ние си оди за да полека го одземат тоа од вас и да почнам да зборувам за
нешто повеќе езотерично познат како char *,
но ние си оди за да се направи ова убаво и нежно на прв, иако покажувачи,
како тие се нарекува, може да направи некои Многу лоши работи ако злоупотребувани,
од страна гледајќи во малку claymation од нашиот пријател Ник Parlante од Стенфорд
Универзитет, професор во компјутер науката кои се стави заедно овој преглед
на она што е да дојде оваа среда.
>> [Видео репродукција]
Еј, Binky.
Се разбудам.
Тоа е време за покажувачот забава.
>> Што е тоа?
Учат за покажувачи?
Ох, стрина!
[END видео репродукција]
ЗВУЧНИЦИ 1: Тоа што го чека во среда.
Ќе се видиме тогаш.
[Видео репродукција]
-И сега, длабоки мисли, од Daven Farnham.
>> Зошто сме ние учење Ц?
Зошто не А +?
>> [Смеа]
>> [END видео репродукција]