[Speel van musiek] 

Spreker 1: Alle reg, dit is CS50, en dit is die begin van die week vier, en as jy dalk gehoor het of lees, het die wêreld is eindig. Gaan rondom die internet is kennis en bewustheid van 'n fout in 'n program, 'n programmeertaal genoem bash. Dit het wonderbaarlik gebrandmerk as Shellshock, of die bash deur, maar artikels soos hierdie het nie ongewoon nie. En in werklikheid, baie van hulle bring herinneringe van Heartbleed, wat jy dalk opgemerk het in die druk terug die afgelope jaar, wat was insgelyks redelik dramaties. Nou die van julle hier vandag, hoeveel van julle het, selfs as jy nie verstaan ​​wat dit is alles oor, hoor Shellshock? Alle reg, en hoeveel van julle rekenaars wat kwesbaar is? OK, daar behoort te wees ver, ver meer hande tot nou, om redes wat ons sal sien. 

Kom ons neem 'n blik op wat is is aan die gang in die media en verduidelik dit dan 'n bietjie hier vir ons tegnies. 

Spreker 2: Sekuriteit kundiges het gewaarsku dat 'n ernstige fout kon wees oor die honderde te beïnvloed miljoene van die wêreld se web gebruikers. So wat presies is die fout wat was genoem Shellshock, en wat beteken dit? Wel, Shellshock is ook bekend as die Bash fout, die sagteware dit uitbuit. Hackers gebruik om die virus kwesbaar te scan stelsels hardloop Linux en Unix bedryfstelsels en dan hulle aansteek. Bash is 'n command line dop. Dit laat gebruikers kwessie beveel om te begin programme en funksies binne sagteware deur te tik in die teks. Dit is tipies gebruik word deur programmeerders en moet nie oop wees vir die res van die wêreld, al Shellshock verander nie. 

Wel, worringly, sommige ontleders waarsku dit kan 'n groter bedreiging wees, omdat Shellshock kan volledige beheer van 'n besmette rekenaar, terwyl Heartbleed slegs toegelaat hackers om te spioeneer op rekenaars. Dit is so ernstig, is dit is aangewys 'n 10 uit 10 vir die erns van die Nasionale Kwesbaarheid databasis. 2/3 van alle webservers is op risiko, insluitend 'n paar Mac rekenaars. Wel, maak seker dat jy pleister jou stelsels nou. Enigiemand gasheer van 'n webwerf loop die geaffekteerde bedryfstelsels moet aksie neem so gou as moontlik. Enigeen wat dit kan bekostig moet kyk om hul monitering en web aansoek firewalls om te kyk uit vir enige aanvalle. SPREKER 3: Die ergste ding wat kan gebeur, is dat iemand kode sou skryf dat outomaties gaan scan die internet en sou raak al hierdie rekenaars. En as hulle dit doen, wel, die ergste ding wat hulle kan doen net alles verwyder, of sluit die plekke af. So kan ons die skade sien vanaf die punt van die oog, waar ons kwaadwillige mense wil hê wat net besluit om chaos te veroorsaak deur te bring stelsels af of verwyder lêers, en dinge soos dat. Spreker 2: Sommige sê dit is een van die mees moeilik om te meet foute in die jaar, en dit Dit kan weke neem of selfs maande die uiteindelike impak te bepaal. 

Spreker 1: So al wat waar is, Maar die snaakse ding is, byna almal van die beelde wat jy nou net gesien het, behalwe vir miskien die sleutelbord, het niks te doen met die fout hoegenaamd nie. Servers en drade en so meer, dit is soort van tangensiaal verwant is, maar by die kern dit is eintlik mooi vertroud wat gaan hier aan. In werklikheid, laat my gaan na ons CS50 toestel. Laat my voort te gaan en te sorg die terminale venster hier. En julle het al met behulp van hierdie, of die ingeboude weergawe daarvan, in gedit om programme te skryf, tik opdragte, en so meer, en dit is eintlik, en het al vir weke, bash, B-A-S-H. Dit is die Bourne-weer dop, wat net 'n fancy manier om te sê, dit is 'n program wat 'n flikkerende vinnige, doeltreffende, dat daar sit en wag vir insette vir jou. En dit is die opdrag line interface via wat julle ouens het al 'bevele en uiteindelik die opstel en dan hardloop programme. 

Maar Bash is ook 'n ontwikkeling taal in die volgende sin. Jy weet dat daar is opdragte soos CD en LS en ook kletteren en ander, maar jy kan jou eie instruksies te definieer deur die implementering van hulle in bash. Nou is ons gaan nie gaan in groot detail as die programmeertaal te bash nie, maar weet, byvoorbeeld, wat op die oomblik, daar is geen opdrag genaamd "hallo." So dit kan gevind word in een van hierdie pakkette. Dit is nie op my rekenaar geïnstalleer. Vra jou administrateur. Maar as ek wil daar 'n program te wees genoem "hallo" in Bash of by my vinnige, Ek kan eintlik gebruik sintaksis wat hou C. Dit is nie heeltemal dieselfde nie, maar dit lyk redelik soortgelyk aan 'n funksie, al is dit ontbreek 'n paar besonderhede. Dit lyk asof niks gebeur, maar nou as ek tik "hallo" jy kan eintlik skryf 'n program, nie in C nie in Java, nie in 'n ander ontwikkeling taal, maar in Bash self. 

Nou is die sleutel hier is dat ek die noem ek wou hierdie nuwe opdrag te gee, en die hakies is ook simbolies van dit is 'n funksie. As 'n eenkant, kan jy ook pret doen dinge, en in die feit, selfs op Mac OS, dit is 'n program genaamd terminale. Dit kom gebou in iemand se rekenaar wat 'n Mac in hierdie kamer, en jy kan soortgelyke dinge in Mac doen OS, maar jy kan meer as dit gaan. En dit is 'n bietjie tangensiaal, maar dit is soort van pret. Ek is vanoggend herinner, Wanneer dit te dink deur middel, van 'n bietjie spel ek gebruik om te speel met een van CS50 se voormalige TFS waardeur enige tyd wat hy sou weg van loop sy klawerbord met sy skerm ontsluit, Ek wil 'n opdrag uit te voer soos this-- "sê hallo." En nou enige tyd kom hy terug na sy klawerbord nadat ek die skoonmaak van die skerm en hy sal gaan sit, probeer om 'n werk te doen, n lys van die inhoud van sy directory-- 

[Audio speel] 

-Hello. Hello. 

Spreker 1: So, in regverdigheid, dit was nie eintlik "hallo." Dit was gewoonlik iets meer verwant aan that-- [Audio speel] -Beep. Spreker 1: --that Ek would-- sodat sy rekenaar sou sweer by hom enige tyd wat hy eintlik gaan sit by sy klavier. En baie vinnig hy uitgepluis nie te laat om sy skerm ontsluit. Maar dit dui op die soort dom pret wat jy kan hê met iets soos Bash. Maar dit is 'n bietjie meer ernstige, om seker te maak, as dit wees. En in werklikheid, dit is een van die gevaarlikste en langdurige foute wat werklik die wêreld wêreldwyd. Hierdie fout is al vir sowat 20 jaar, en jy sal in net 'n getref word oomblik deur sy relatiewe eenvoud. 

So, dit is 'n verteenwoordiger beveel dat as jy self 'n Mac, letterlik nou wanneer jy jou deksel oop, jy kan probeer om te tik in daardie program genoem Terminal. Terminale is onder Aansoeke Utilities-- vir een keer, Windows gebruikers hoef nie te bekommerd wees oor hierdie spesifieke threat-- maar dié van julle met Mac kan tik dit in 'n venster soos ek hier sal doen, en as jy nie tik wat in hierdie program genoem Terminal, soos ek nou sal doen, As jy die woord sien "kwesbaar" jou rekenaar kwesbaar vir uitbuiting. 

Nou wat beteken dit eintlik beteken? En dit is weliswaar 'n paar mooi gek sintaksis, maar laat ons minstens trek uit sommige van die interessante aspekte. So daar is 'n paar sintaksis wat lyk 'n bietjie bekend is, ten minste van C en programmering meer algemeen. Ek sien 'n paar hakies, kommapunte, krulhakies, en so, maar dit blyk dat hierdie dom ding hier in geel is in wese 'n funksie wat doen niks. Die kolon middel niks doen nie, en die kommapunt beteken stop niks doen nie. So binnekant van hierdie krulhakies, die feit dat ek 'n gelyke teken aan die linkerkant, hierdie is in wese skep 'n opdrag of 'n veranderlike, genoem x, en die toeken van dit geel bietjie van die kode is daar. Dit kan iets soos "eggo wees hallo "of" sê beep "of iets soortgelyk aan dié. Maar let as jou oë dwaal verder aan die regterkant, daar is meer aan hierdie lyn as net die einde van die kommapunt. "Echo kwesbaar," en dan as dit nie daar is nog meer. Nog 'n kommapunt, bash -c :. 

So lang storie kort, hierdie lyn van kode is voldoende vir dwingende 'n rekenaar wat kwesbaar om iets te doen wat jy wil om dit te doen, want daar is 'n fout in Bash waardeur selfs al Bash was veronderstel om te stop lees lyne van die opdrag reg daar na die geel teks, vir 'n 20-plus jaar oud fout, Bash het eintlik al lees verder as dit kommapunt en mooi veel om te doen wat dit vertel word. 

So, wat is die implikasie van wat uiteindelik? Ek het net gesê: "eggo hallo" of "eggo kwesbaar," Maar wat as jy iets eintlik kwaadwillige, soos rm-rf *, wat jy dalk nie het ooit getik, en eerlik jy waarskynlik moet nie te gou, want jy kan doen om 'n baie skade met dit. Hoekom? rm doen wat natuurlik? Verwyder. * Beteken wat? Alle. So dit is 'n sogenaamde wild card, so dit beteken alles verwyder in die huidige gids. r gebeur beteken rekursiewe, wat beteken dat as wat jy skrap is 'n gids, en binnekant van daar is ander lêers en ander dopgehou, rekursief duik in daar en verwyder al van dat. En f is die ergste van hulle almal. Wie weet wat f beteken hier? Force. So dwing beteken, selfs As dit is 'n slegte idee nie, doen dit sonder om te vra vir my vir verdere bevestiging. So, jy weet, ons lag , maar eerlik, ek het waarskynlik tik verskeie kere 'n dag, want die werklikheid is dit die vinnigste manier om te verwyder 'n hele klomp van die dinge. Maar selfs ek het 'n bietjie skade gedoen. 

Maar as jy 'n rekenaar te mislei in die definisie van 'n paar dom veranderlike of funksie genoem x, maar dan tricking die rekenaar in die uitvoering van buite die grense van daardie funksie, as dit kommapunt, jy kan wel 'n rekenaar mislei in die uitvoering van iets soos rm-rf of die e-pos opdrag of die opdrag Kopieer. Enigiets letterlik kan jy doen met die rekenaar, of dit nou die verwydering van lêers, skep lêers, spam iemand aanval 'n paar bediener afstand, As jy dit kan uitdruk met 'n opdrag, kan jy kan 'n rekenaar flous om dit te doen. 

Nou wat is 'n voorbeeld van hoe jy dit kan doen? Wel, daar is 'n baie van rekenaars op die internet loop bash. Almal van ons Mac-gebruikers is onder hulle. Baie van die bedieners is onder hulle so goed, en Unix bedieners. Windows kry weer relatief uit die haak tensy jy het geïnstalleer spesiale sagteware. Nou 'n baie bedieners, Byvoorbeeld, loop web bedieners, en in die feit dat Linux is dalk die gewildste bedryfstelsel om te loop op rekenaars op die internet wat dien tot webblaaie. Nou as ons sal later sien in die semester, wanneer jy stuur 'n versoek van jou browser-- Chrome, Internet Explorer, whatever-- na 'n afgeleë bediener dit blyk dat selfs al jy net getik www.example.com, die leser is die stuur van 'n boodskap dit is 'n bietjie meer arcane, soos hierdie. 

Maar let 'n bietjie iets vreemd. Die eerste twee lyne Ek het nog nooit gesien het nie, maar hulle sien nie veral dreigend. Maar let op wat ek gesteel vir die derde reël hier. As 'n slegte man was 'n boodskap te stuur soos dit van sy of haar rekenaar 'n kwesbare Mac of 'n kwesbaar Linux bediener, Die funny ding is dat Bash, dat eenvoudige klein command prompt, is alomteenwoordig en is dikwels gebruik om wese voer die inhoud van 'n boodskap wat dit ontvang. En deur daardie logika, kan jy mislei 'n web bediener, dus deur die stuur van iets soos User-agent, wat gewoonlik veronderstel is om die te sê naam van die leser. Gebruiker-agent Chrome, User-agent Internet Explorer, user-agent Firefox, hierdie is net die leser se manier van die identifisering van self. Maar as 'n slegte ou baie slim sê mm-mm, ek is gaan jou nie te vertel wat my leser is, Ek plaas gaan om dit te stuur kriptiese-soek ding met 'n rm-rf * In dit, kan jy letterlik mislei 'n kwesbaar web bediener op die internet in die uitvoering van presies wat in daar is vir die verwydering van al die lêers. En eerlik, dit is nie selfs die ergste van dit. Jy kan niks doen nie. Jy kan begin met 'n versprei ontkenning van die diens aanval As julle gestuur om hierdie boodskap te hele trosse van web-bedieners en dan het hulle almal toesak, vir Byvoorbeeld, op Harvard.edu bedieners, en jy kan soort van bang die klink van hulle deur 'n netwerk verkeer wat anders veroorsaak deur hierdie slegte ou. 

So, 'n lang storie kort, byna Almal in die kamer wat 'n Mac besit kwesbaar is vir hierdie. Die silwer randjie is dat tensy jy bestuur van 'n web bediener op jou laptop, en tensy jy eintlik ingestel dit iets soos SSH te laat in dit, jy eintlik veilig. Dit is kwesbaar, maar daar is geen een probeer om te kry in jou laptop, sodat jy kan soort van gerus wees. Maar, Apple sal binnekort wees opdatering 'n oplossing vir hierdie. Die wêreld van Linux het reeds vrygestel 'n aantal fixes vir Fedora en Ubuntu en ander weergawes van Linux, en inderdaad as jy loop update 50 in die toestel, selfs dat daar te wees opgedateer en reggestel word. Maar dit het ook nie werklik kwesbaar, want tensy jy tinkered met die toestel en het jou laptop in die openbaar beskikbaar op die internet, wat nie by verstek, het jy eintlik is goed, want van firewall en ander tegnieke. 

Maar dit is 'n uiterste voorbeeld van 'n fout dat ons vir nog geleef het vir letterlik 20 jaar, en wie weet of iemand al hierdie tyd het bekend oor dit? En in werklikheid, dit is een van die die fundamentele uitdagings dat ons later sal sien in die semester oor veiligheid, is dat net soos in die werklike wêreld, die goeie ouens is aan die nadeel. Die slegte ouens uit te hou, moet ons maak seker dat elke deur is gesluit, dat elke venster is veilig, wat elke punt van die inskrywing in 'n huis veilig is om die slegte ouens uit te hou. Maar wat doen die slegte ou te doen om werklik jou huis kompromie en steel van jou? Hy of sy het net een oopgesluit te vind deur, een gebreekte venster, of iets langs die lyne, en dit is die dieselfde ding in rekenaar sekuriteit. Ons kan miljoene skryf lyne van ontwikkeling kode en spandeer honderde of duisende ure probeer om dit korrek te kry, maar as jy net een fout in korrektheid, jy kan die hele stelsel sit en inderdaad in hierdie geval, die hele internet en die wêreld in gevaar stel. 

So as jy wil meer te leer oor hierdie, gaan na hierdie URL hier. Daar is geen behoefte vir aksie vanaand tensy jy onder diegene wat meer gemaklik dat is om jou eie web bediener, in welke geval jy moet, in werklikheid, werk jou sagteware. 

En dit is ook die titel van 'n toespraak, en nou 'n papier, dat ons op die gekoppelde het Natuurlik se webwerf vir vandag. Dit was deur 'n mede- vernoem Ken Thompson, wat is die aanvaarding van 'n baie bekende toekenning in Rekenaarwetenskap, en hy het hierdie toespraak 'n paar jaar gelede, in wese op dieselfde onderwerp. Vra mense die vraag, jy moet regtig trust, uiteindelik, die sagteware wat jy ontvang het? Byvoorbeeld, het ons almal is die skryf van programme, en ons het die samestelling hulle met klang. En om jou kennis, jy het geskryf enige programme vir CS50 waar daar 'n agterdeur van die spesies, daar is 'n manier dat 'n slegte man, as die bestuur van jou program, kon oor jou rekenaar te neem? Waarskynlik nie, reg? Mario en gulsig, en krediet. Dit is alles mooi klein programme. Jy wil hê om mooi wees sleg as jy eintlik jou hele rekenaar kwesbaar gemaak na die skryf van 10 of 20 reëls van die kode, of ten minste bewus van 'n paar van die sekuriteit implikasies. En ek sê dat grappig, maar ons gaan vandag om te sien en dié week is dit eintlik regtig, regtig maklik sleg wees en maak selfs kort programme kwesbaar. 

Maar vir nou, ten minste, besef dat die vraag wat hier gevra is oor die geratel in 'n vertaler. Hoekom het ons vertrou klang vir die afgelope twee of drie weke? Wie is om te sê dat elkeen klang geskryf het nie 'n "as" toestand daar wat in wese 'n paar nulle ingespuit en kinders in elke program dit stel wat sou laat hom of haar toegang jou rekenaar wanneer jy aan die slaap en jou laptop deksel is oop en op jou rekenaar? Reg? Ons het hierdie soort van eer stelsel reg nou waar ons vertrou dat klang is wettig. Jy vertrou dat die toestel is wettig. Jy vertrou dat letterlik elke program op jou Mac of PC is betroubaar. En as hierdie eenvoudige fout dui, selfs al is dit nie kwaadwillig, dit is absoluut nie waarskynlik die geval te wees. 

So moet jy bang soos die hel wees. Om eerlik te wees, daar is nie 'n eenvoudige oplossing vir hierdie ander as 'n soort van sosiale bewustheid van die toenemende kompleksiteit dat ons bou op die top van ons rekenaar stelsels, en hoe meer kwesbaar ons kan baie goed wees. 

Nou met wat gesê het, Breakout. So Breakout is probleem van drie, en Breakout is 'n spel van die verlede dat jy kan onthou nie, maar vir ons in die probleem van drie, dit stel ons in staat om te neem dinge weer op 'n kerf sodat wanneer ons die skryf van programme, selfs in 'n terminaal venster soos hierdie, ons eintlik kan hardloop, uiteindelik, grafiese programme nie Anders as wat ons gehad het toegang tot in nuuts af. So dit is die personeel se implementering van Breakout, wat net die baksteen-breaking spel, wat jy beweeg jou paddle terug en weer, en jy het die bal teen dié gekleurde stene op die top. So dit bring ons soort van terug na waar ons was in staat om baie vinnig met nuuts af, en nou met C, implementering van ons eie grafiese gebruikerskoppelvlakke. 

Maar meer as dit, hierdie probleem stel die eerste waarin ons gee jy 'n klomp van die kode. En in die feit, ek bring eksplisiete aandag aan hierdie, want veral vir diegene wat minder gemaklik, hierdie probleem stel, ten minste op die eerste oogopslag, gaan om te voel soos Ons het dit geneem op 'n kerf. Want ons het jou gegee het, vir 'n paar van die soektog en sorteer die probleme in die pset, 'n klomp van die kode wat ons geskryf het, en 'n paar van die kommentaar wat sê: "doen," waar jy in die spasies in te vul. So nie te skrikwekkend, maar dit is die eerste keer ons uitdeel jy kode wat jy nodig het om te eerste lees, verstaan, en dan voeg by en voltooi dit. 

En dan met Breakout, ons gaan om dieselfde te doen, gee jou 'n paar dosyn meer lyne kode wat, eerlik, gee jou 'n groot deel van die raamwerk vir die spel, maar stop kort van die implementering van die stene en die bal en die paddle, maar ons doen implementeer 'n paar ander funksies. En selfs dit met die eerste oogopslag, weer, veral as minder gemaklik, lyk veral ontmoedigend en jy dink daar is so baie nuwe funksies wat jy nodig het om jou gedagtes te draai rond, en dit is waar. Maar hou in gedagte, is dit hou nuuts af. Kans is jy nie al gebruik die stukke van die legkaart in nuuts af. Kans is jy nie omgee om te draai jou gedagtes rondom almal van hulle want al het dit was 'n vinnige blik te verstaan, o, dit is wat ek kan doen met die legkaart stuk. En inderdaad, in probleem stel 3 spec, sal ons wys jou op die dokumentasie wat sal bekend te stel aan 'n paar nuwe funksies, en uiteindelik die ontwikkeling bou jy gebruik. Voorwaardes, lusse, veranderlikes en funksies identies te wees wat ons tot dusver gesien het. 

So ja, wat ons gee jy is 'n paar voorbeelde kode wat kan jy 'n venster wat lyk nie anders as dit, en uiteindelik draai dit in iets baie soos hierdie. So neem voordeel van CS50, bespreek kantoorure en meer, en troos in die feit dat die bedrag van die kode wat jy hoef te skryf is eintlik nie veel. Die eerste uitdaging is om net te acclimatiseren jouself tot 'n kode wat ons het geskryf. 

Enige vrae oor pset3, Shellshock, of andersins? 

Publiek: Dit het gelyk soos gaan deur met Breakout dat die kode is byna 'n voorwerp-georiënteerde styl, maar ek het gedink C was 'n objek-georiënteerde program. Spreker 1: 'n uitstekende vraag. So in soek deur die verspreiding kode, die kode ons het vir pset3, vir diegene wat vertroud is, is dit lyk soos dit is 'n bietjie voorwerp-georiënteerde. Kort antwoord is, dit is. Dit is 'n aanpassing van hoe jy dalk objekgeoriënteerde kode doen met behulp van 'n taal soos C, maar dit is steeds uiteindelik die proses. Daar is geen metodes binnekant van die veranderlikes, soos jy sal sien. Maar dit is wat herinner aan dit. En ons sal dat die funksie weer te sien wanneer ons by PHP en JavaScript teen die einde van die semester. Maar vir nou, dink aan dit as 'n wenk van wat om te kom. Goeie vraag. Alle regte. So fuseren soort was hoe ons links dinge laaste tyd. En voeg soort was koel in die sin dat dit so baie vinniger, ten minste gebaseer op die vlugtige toetse ons het verlede week, as, sê, borrel soort, seleksie soort, voeg soort. En wat was netjies te net hoe saaklik en skoon jy kan dit uitspreek. En wat het ons gesê dit was 'n bo- gebind op die loop van die tyd van merge sorteer? Ja? 

Publiek: n log n? 

Spreker 1: n log n, reg. n log n. En ons sal terug te kom na wat dit werklik beteken of waar dit vandaan kom, maar dit was beter as wat hardloop tyd wat ons gesien het vir borrel seleksie en voeg soort? So n vierkant. N vierkant is groter as dit, en selfs al is dit nie voor die hand liggend, weet dat log N kleiner as n, So as jy n keer iets kleiner as n, dit gaan minder as N vierkantig wees. Dit is 'n bietjie van intuïsie is daar. Maar ons 'n prys vir hierdie betaal. Dit was vinniger, maar 'n tema wat begin verlede week na vore kom, was hierdie nadeel. Ek het 'n beter prestasie tyd wys, maar wat het ek het om te spandeer op die ander hand, om dit te bereik? 

Publiek: Memory. Spreker 1: Sê weer? Publiek: Memory. Spreker 1: Memory, of ruimte meer in die algemeen. En dit was nie super duidelik met ons mense, maar onthou dat ons vrywilligers is vorentoe stepping en versterking terug asof daar is 'n verskeidenheid hier, en asof daar 'n tweede reeks hier dat hulle kon gebruik nie, want ons nodige êrens dié mense om saam te smelt. Ons kan nie net ruil hulle in plek. So saamsmelt soort hefboom is meer ruimte, wat ons het nie nodig om met die ander algoritmes, maar die voordeel is dat dit baie vinniger. En eerlik, in die werklike wêreld ruimte hierdie days-- RAM, hardeskyf space-- relatief goedkoop is, en so is dit nie noodwendig 'n slegte ding nie. 

So laat ons neem 'n vinnige blik, 'n bietjie meer metodies, op wat ons gedoen het en waarom ons gesê dit is n log n. So hier is die agt nommers en die agt vrywilligers het ons die laaste keer. En die eerste ding wat Merge Kort gesê ons moet doen, is wat? Publiek: Verdeel in twee. Spreker 1: Sê weer? Publiek: Verdeel in twee. Spreker 1: Verdeel in twee, reg. Dit is baie herinner aan die telefoon boek, deel en oorwin meer algemeen. So het ons gekyk na die linker helfte. En dan wanneer ons sê, soort die linker helfte van die elemente, wat het ons die volgende sê? Sorteer die linker helfte van die linker helfte, wat ons toegelaat word om, na die verdeling in twee, fokus op die vier en twee. 

Hoe sorteer jy 'n lys nou, in geel, grootte twee, met behulp van Merge sorteer? Wel verdeel dit in die helfte, en sorteer die linker helfte. En dit was waar dinge het 'n bietjie dom kortliks. Hoe sorteer jy nie 'n lys wat van grootte een, soos hierdie nommer vier hier? Dit is gesorteer. Jy is klaar. 

Maar hoe sorteer jy 'n lys van grootte een wanneer dit is die nommer twee? Wel, dieselfde ding, maar nou wat was die derde en die belangrike stap in Merge sorteer? Jy het die linker om saam te smelt helfte en die regter helfte. En wanneer ons dit doen, het ons gekyk op vier, het ons gekyk na twee. Ons het besluit om al die regte, natuurlik twee kom eerste, So het ons twee in sy plek, gevolg deur vier. En nou moet jy soort van rewind, en dit is 'n soort van kenmerkende van 'n algoritme soos Merge Soort, rewind in die geheue. Wat was die volgende lyn van die storie? Wat moet ek word met die fokus op die volgende? Die regter helfte van die linker helfte, wat ses en agt. 

So laat my net stap vir stap deur hierdie sonder belaboring die punt te veel. Ses en agt, dan ses is gesorteer, agt gesorteer is. Voeg hulle saam soos daardie, en nou is die volgende groot stap is, natuurlik, sorteer die regter helfte van die heel eerste stap van hierdie algoritme. So ons fokus op een, drie, sewe, vyf. Ons fokus dan op die linker helfte. Die linker helfte van dat die regter helfte van dat en dan saam te smelt in een en drie. Toe het die reg om die helfte, dan is die helfte verlaat daarvan, dan is die regter helfte van dit. Merge dit in, en wat nou stap bly? Voeg die groot linker helfte en die groot regter helfte, so een gaan af daar, dan twee, dan drie, dan vier, dan vyf, dan is ses, dan sewe, dan agt. 

So nou waarom is dit uiteindelik die onthulling, veral as N en logaritmes meer algemeen eerder ontsnap jy, ten minste in die onlangse verlede? Wel, let op die hoogte van hierdie ding. Ons het agt elemente, en ons verdeel dit deur twee, twee, met twee. So teken basis twee van agt gee ons drie. En glo my op dat indien 'n bietjie vaag op daardie. Maar teken basis twee van agt is drie, so ons het drie lae van samesmelting gedoen. En wanneer ons saamgesmelt elemente, hoeveel elemente het ons na elk van die rye? 'N Totaal van N, reg? Omdat die boonste ry om saam te smelt, selfs al het ons dit sporadies, ons uiteindelik weer aangeraak elke nommer. En in die tweede ry, te saam te smelt die lyste van grootte twee, Ons het elke element te keer raak. En dan is hier werklik duidelik in die laaste ry, Ons het elkeen van daardie te raak elemente keer, maar slegs een keer, so hierin lê, dan is ons n log n. 

En nou net dinge 'n bietjie te maak meer formele vir net 'n oomblik, as jy was nou ontleed hierdie 'n soort van 'n hoër vlak en probeer om te besluit, asook hoe kan jy gaan oor die uitdrukking die loop van die tyd van hierdie algoritme net deur te kyk na dit en nie deur die gebruik van 'n kunsmatige voorbeeld? Wel, hoeveel tyd sal jy sê 'n stap soos hierdie in geel sou neem, As n <2 terugkeer? Dis 'n groot O van wat? So ek sien een so 'n stap, miskien twee stappe, want dit is as en dan terug te keer, maar dit is konstante tyd, reg? Daarom het ons gesê O (1), en dit is hoe sal ek spreek hierdie. T, net hardloop tyd. N is die grootte van die insette, sodat T (n), net 'n fancy manier sê die bedryf tyd gegee insette van grootte n gaan wees op die einde van konstante tyd, in O (1). 

Maar anders, wat oor hierdie? Hoe sal jy druk die loop van die tyd van hierdie geel streep? T van wat? Jy kan soort oneerlik hier en beantwoord my vraag siklies. Dus, as die loop van die tyd in algemene ons net sê, is T (n). En nou is jy soort vaar hier en sê, goed, net sorteer die linker helfte, en dan sorteer die regter helfte. Hoe kan ons simbolies verteenwoordig die loop van die tyd van hierdie geel streep? T van wat? Wat is die grootte van die insette? N meer as twee. Hoekom het ek nie net sê dat? En dan is dit 'n ander T (n / 2) en dan weer, as ek voeg twee gesorteer helftes, hoeveel elemente gaan ek te hê om aan te raak totaal? n. So ek kan uitdruk nie, net om te soort van fancy, as die loop van die tyd in die algemeen. T (n) is net die loop van die tyd van die T (n / 2), plus T (n / 2), links en regs helfte helfte, plus O (n), wat waarskynlik n stappe, maar miskien, as ek met twee vingers, dit is twee keer soveel stappe, maar dit is lineêr. Dit is 'n paar aantal stappe dit is 'n faktor van N, sodat ons dit kan uitdruk soos hierdie. En dit is hier waar ons nou sal voorspel dat die agterkant van ons hoërskool wiskunde handboek ons is dat herhaling uiteindelik eindig gelykstaande hierdie, n keer log n, as jy eintlik doen uit die wiskunde meer formeel. 

So dit is net twee perspektiewe. Een numeries met 'n hard-gekodeerde verteenwoordigende voorbeeld gebruik agt nommers, en 'n meer algemene blik op hoe ons daar gekom het. Maar wat is regtig interessant hier is, weer, hierdie idee van fietsry. Ek gebruik nie vir loops. Ek is soort van die definisie iets in terme van homself, nie net met hierdie wiskundige funksie, maar ook in terme van hierdie pseudo-kode. Hierdie pseudo-kode is rekursiewe in dat twee van sy lyne is in wese vertel dit om te gaan gebruik self 'n kleiner te los probleem van kleiner, en dan weer en weer en weer totdat ons Whittle dit na hierdie sogenaamde basis geval. 

So laat ons eintlik trek 'n meer dwingende neem-weg van dit soos volg. Laat my gaan in gedit en neem 'n kyk na 'n paar van vandag se bron-kode, in die besonder die voorbeeld hier. Sigma 0, wat blykbaar voeg die getalle van een tot n. So laat ons sien wat vertroud en onbekende hier. Eerste het ons 'n paar sluit, so niks nuuts nie daar nie. Prototipe. Ek is 'n bietjie vaag oor hierdie na n paar dae, maar wat het ons sê 'n prototipe van 'n funksie is? Publiek: [onhoorbaar]. Spreker 1: Wat is dit? Publiek: Ons maak dit bekend. Spreker 1: Ons maak dit bekend. So jy leer klang, hey, eintlik nie die implementering van hierdie nie, maar iewers in hierdie lêer, vermoedelik, gaan word om 'n funksie genoem wat tot? Sigma. En dit is net 'n belofte dat dit gaan lyk soos hierdie. Dit gaan 'n heelgetal te neem as input-- en ek kan meer eksplisiete wees en sê int N --and dit gaan 'n int om terug te keer, maar kommapunt middel, mm, ek sal kry om om die implementering van hierdie 'n bietjie later. Weereens, klang is stom. Dit gaan net om te weet wat vertel dit bo tot onder, sodat ons nodig het om ten minste gee dit 'n aanduiding van wat om te kom. 

Kom ons kyk hier by die hoof nou. Kom ons blaai hier en sien wat hoof doen. Dit is nie so lank van 'n funksie, en in die feit dat die konstruksie hier is vertroud. Ek verklaar 'n veranderlike n, en dan Ek weer en weer teister die gebruiker vir 'n positiewe heelgetal gebruik getInt, en enigste uitgang uit hierdie lus Sodra die gebruiker voldoen het. Doen terwyl ons gebruik het om teister die gebruiker op dié manier. Nou is dit interessant. Ek verklaar 'n int genoem "antwoord." Ek ken dit die terugkeer waarde van 'n funksie genoem "Sigma." Ek weet nie wat dit beteken nie, maar Ek onthou dit 'n oomblik gelede verklaar. En dan is ek verby in die waarde wat die gebruiker getik in, n, en dan rapporteer ek die antwoord. Wel, laat ons blaai terug vir net 'n oomblik. Kom ons gaan voort in hierdie gids, maak Sigma 0, en eintlik hierdie program hardloop en kyk wat gebeur. So as ek gaan voort en run hierdie program, ./sigma-0, en ek tik in 'n positiewe heelgetal soos twee, Sigma, as die Griekse simbool impliseer, is net toe te voeg tot al die getalle van nul tot twee. So 0 plus 1 plus 2. So dit moet hopelik gee my 3. Dit is al wat dit doen. En so, as ek hardloop dit weer en ek gee dit die nommer drie, dit is 3 plus 2, so dit is 5, plus 1 moet gee my 6. En dan as ek kry regtig mal en tik in groter getalle, dit moet my gee groter en groter somme. So dis al. 

So wat beteken sigma lyk? Wel, dit is redelik eenvoudig. Dit is hoe ons kan geïmplementeer dit vir die afgelope paar weke. "Int" gaan die terugkeer tipe te wees. Sigma is die naam, en dit neem 'n veranderlike m in plaas van N. Ek sal dit verander nie tot bo. Dan is dit net 'n gesonde verstand tjek. Ons sal sien waarom in 'n oomblik. Nou verklaar ek 'n ander veranderlike, som, inisialiseer aan nul. Toe ek hierdie For lus iterating, blykbaar vir duidelikheid, van i = 1 op tot 'n = m, wat wat die gebruiker getik in, en dan het ek inkrementeer die som soos hierdie. En dan terug die bedrag. 

So 'n paar vrae. Een, ek eis in my opmerking dat dit vermy die risiko van 'n oneindige lus. Hoekom sou slaag in 'n negatiewe getal veroorsaak, potensieel, 'n oneindige lus? 

Publiek: Jy sal nooit bereik m. 

Spreker 1: Nooit bereik m. Maar m geslaag in, so laat oorweeg om 'n eenvoudige voorbeeld. As m geslaag in die gebruiker as negatiewe een. Ongeag van die belangrikste. Main beskerm ons teen Dit ook, so ek is net synde regtig anale met Sigma ook seker maak dat die insette nie negatief kan wees. So as m negatief is, iets soos negatiewe een. Wat gaan gebeur? Wel, ek gaan kry geïnisialiseer een, en dan is ek gaan wees minder as of gelyk aan m? 

Staan. Dit was-- laat nie, laat se nix hierdie storie. Ek het nie daardie vraag vra, want die risiko dat ek verwys na is nie gaan gebeur nie, want ek is altyd groter wees than-- OK, Ek trek die vraag. OK. Kom ons fokus net op hierdie deel hier. Hoekom het ek verklaar sommige buite die lus? Kennis op die lyn 49 Ek het verklaar ek binnekant van die lus, maar aanlyn 48 Ek het verklaar 'n buite. Ja. Publiek: [onhoorbaar]. Spreker 1: Natuurlik. So in die eerste plek het ek beslis nie doen nie wil verklaar en inisialiseer som nul binnekant van die lus op elke iterasie, want dit sou duidelik die nederlaag van die doel van 'n opsomming van die getalle. Ek sou hou die verandering die waarde terug na nul. En ook, wat is 'n ander meer arcane rede hiervoor is dat dieselfde ontwerp besluit? Ja. 

Publiek: [onhoorbaar]. Spreker 1: Presies. Ek wil dit buite toegang van die lus te op watter lyn? Op 53. En op grond van ons reël van 'n paar lesings gelede veranderlikes scoped, regtig, om die krulhakies wat hulle omring. So as ek binne verklaar nie som van hierdie buitenste krulhakies, Ek kan dit nie gebruik nie in lyn 53. Sit 'n ander manier, as ek verklaar som hier, of selfs binne die Vir lus, kan ek nie toegang tot dit in 53. Die veranderlike sal effektief weg wees. So 'n paar van die redes. Maar laat ons nou terug te gaan en kyk wat gebeur. So Sigma kry genoem. Dit dra by tot 1 plus 2 of 1 plus 2 plus 3, en dan gee die waarde, stoor dit in antwoord, en printf hier is die rede waarom ek sien op die skerm. So dit is wat ons 'n iteratiewe bel benadering, waar iterasie net beteken deur 'n lus. 'N lus vir 'n while lus, 'n doen terwyl lus, net om iets te doen weer en weer en weer. 

Maar Sigma is 'n soort van 'n netjiese funksie in dat ek kon dit anders te implementeer. Wat van hierdie, wat net om te wees gaaf, laat my regtig ontslae te raak van 'n baie afleiding omdat die funksie is regtig eenvoudig. Kom ons Whittle dit af net aan sy vier kern lyne en ontslae te raak van al die kommentaar en krulhakies. Dit is 'n soort van 'n mind-blowing alternatiewe implementering. Alle reg, miskien nie verstommend, maar dit is soort van sexier, alles reg, om te kyk na dit so baie meer saaklik. Met net vier reëls van die kode, Ek moet eers die gesonde verstand tjek. As m minder as of gelyk aan nul, Sigma maak nie sin nie. Dit is net veronderstel om te wees in hierdie geval vir positiewe getalle, so ek gaan net te terugkeer nul arbitrêr sodat ons ten minste sommige sogenaamde basis geval. 

Maar hier is die skoonheid. Die geheel van hierdie idee, en voeg by die getalle van 1 tot N, of m in hierdie geval, kan gedoen word deur die soort van verby die bok. Wel, wat is die som van 1 tot m? Wel, jy weet wat? Dit is dieselfde as die som van m plus die bedrag van 1 tot m minus 1. Wel, jy weet wat? Wat is sigma van m minus 1? Wel, as jy soort volg hierdie logies, dit is dieselfde as m minus 1 plus Sigma van m minus 2. So kan jy soort van just-- dit is soos, as jy net probeer om 'n vriend te irriteer en hulle vra jou 'n vraag, jy soort van reageer met 'n vraag, jy kan soort van hou verby die bok. Maar wat is die sleutel, is dat as jy aanhou maak die vraag kleiner en kleiner, jy nie vra wat is Sigma van n, wat is sigma van n, wat is sigma van n? Jy vra wat is Sigma van N, wat is Sigma van N minus 1, wat is sigma van N minus 2? Uiteindelik jou vraag gaan word wat? Wat is sigma van een of nul, 'n paar baie klein waarde, en so gou as wat jy kry dat jou vriend, jy is nie van plan om te vra dieselfde vraag weer, jy net gaan om te sê, o, dit is nul. Ons klaar speel hierdie soort dom sikliese spel. 

So rekursie is die wet in ontwikkeling van 'n funksie roeping self. Hierdie program toe opgestel en loop, is gaan presies dieselfde manier op te tree, maar wat is die sleutel, is die feit dat binne van 'n funksie genoem Sigma, Daar is 'n reël van die kode waarin Ons noem onsself, wat normaalweg sou sleg wees. Byvoorbeeld, wat as ek die eerste saamgestel, so maak sigma-- maak Sigma 1 ./sigma-1. Positiewe heelgetal is, asseblief, 50 1275. So, wat die funksie blyk te wees, wat gebaseer is op 'n toets, korrek is. Maar wat as ek 'n bietjie gevaarlik en verwyder die sogenaamde basis geval, en net sê, en ek is net die maak dit meer ingewikkeld as wat dit is. Laat ons net bereken die sigma deur m en dan voeg in sigma van m minus een? Wel, wat gaan hier gebeur? Kom ons zoom uit. Kom ons heropstel die program, behalwe dit, heropstel die program, en dan gereed ./sigma-1 inzoomen, Tik positiewe heelgetal asseblief, 50. Hoeveel van julle is bereid om te erken maar om te sien dat? 

OK. So dit kan gebeur vir 'n aantal redes, en eerlik hierdie week ons oor te gee jy meer van hulle. Maar in hierdie geval, probeer agteruit te redeneer wat kan hier gebeur het nie? Segmentering skuld, ons het verlede tyd, verwys na 'n segment van die geheue. Iets sleg gebeur het. Maar wat was dit meganies dat het mis hier as gevolg van my verwydering van daardie sogenaamde basis geval, waar ek teruggekeer van 'n harde-gekodeerde waarde? Wat dink jy het verkeerd geloop? Ja. 

Publiek: [onhoorbaar]. Spreker 1: Ag. Goeie vraag. So het die grootte van die getal dat ek 'n opsomming van het so groot dat dit oortref die grootte van die geheue spasie. Goeie idee, maar nie fundamenteel gaan 'n ongeluk te veroorsaak. Dit kan integer oorloop veroorsaak, waar die stukkies net flip oor en dan fout wat ons 'n baie groot nommer vir soos 'n negatiewe getal, maar wat homself nie sal veroorsaak dat 'n ongeluk. Want aan die einde van die dag 'n int is nog 32 stukkies. Jy gaan nie per ongeluk steel 'n 33 bit. Maar 'n goeie gedagte. Ja. 

Publiek: [onhoorbaar]. Spreker 1: Die metode nooit ophou loop, en inderdaad is dit noem homself weer en weer en weer en weer en weer, en nie een van daardie funksies ooit klaar, want hulle enigste lyn van kode noem hulleself weer en weer en weer. En wat is regtig hier gebeur, en nou is ons kan soort van teken dit picturaal. Laat my gaan oor 'n prentjie vir net 'n oomblik. Dit is 'n foto, wat sal uiteindelik die vlees uit in meer besonderhede, van wat aangaan binnekant van jou rekenaar se geheue. En dit blyk dat op die onderkant van hierdie foto is iets genoem die stapel. Dit is 'n stuk van geheue, 'n stuk van die geheue, dit is net 'n tyd gebruik 'n funksie genoem. Enige tyd wat jy 'n programmeerder, noem 'n funksie, die bedryfstelsel, soos Mac OS, Windows, Linux, gryp 'n klomp van die grepe, miskien 'n paar kilogrepe, miskien n paar megagrepe geheue, gee dit vir jou, en dan kan jy jou funksie gebruik watter veranderlikes wat jy nodig het. En as jy dan bel 'n ander funksie en 'n ander funksie, jy 'n ander deel van die geheue en 'n ander deel van die geheue. 

En inderdaad, as die groen bak van Annenberg verklaar dat die geheue, hier is wat gebeur met die eerste keer as jy bel funksie Sigma. Dit is soos om 'n skinkbord soos hierdie op wat aanvanklik 'n leë stapel. Maar dan as dit skinkbord roep self, om so te praat, roep 'n ander geval van Sigma, wat soos om te vra die bedryfstelsel, ooh, moet 'n bietjie meer geheue, gee my dat. En dan is dit kry opgestapel op bo-op. Maar wat is die sleutel hier is dat die eerste skinkbord is nog steeds daar, omdat hy vir drie maande hierdie tweede skinkbord. Nou intussen, sigma noem Sigma, dit is soos om te vra vir meer geheue. Kry opgestapel op hier. Sigma noem Sigma, dis 'n ander skinkbord wat opgestapel kry hier. En as jy dit doen hou, uiteindelik, soort kaart visuele aan daardie grafiek, wat gaan gebeur met die stapel bak? Dit gaan om die bedrag te oorskry geheue jou rekenaar het. En sodra dit groen skinkbord meer is as die horisontale lyn bo en behalwe stapel dat die woord hoop, wat ons sal terug te kom in die toekoms, dit is 'n slegte ding. Die hoop is 'n ander segment van die geheue, en as jy toelaat dat hierdie bak hoop en hoop op, jy gaan om te oorskry jou eie segment van die geheue, en 'n program is inderdaad gaan om te crash. 

Nou as 'n eenkant, hierdie idee van rekursie, dus kan duidelik lei tot probleme, maar dit is nie noodwendig 'n slegte ding. Omdat oorweeg, nadat alles, how-- en miskien Dit neem 'n paar om gewoond te --how elegante of hoe eenvoudige dat die implementering van Sigma was. En ons gaan nie te gebruik rekursie alles wat baie in CS50, maar in CS51, en regtig 'n klas waar jy data strukture te manipuleer soos bome, of familie bome, wat 'n paar hiërargie, dit is super, super nuttig. Nou, as 'n eenkant, sodat jy as aspirant rekenaar wetenskaplikes vertroud is met 'n paar van Google se binnekant grappies, as jy gaan na Google en jy kyk wat is die definisie van, sê, rekursie, betree. Uh-huh. As 'n eenkant, ek trek 'n paar. Dit was soos 10 minute van uitstel vanoggend. As jy ook Google "skeef" kennisgewing deur kantel jou kop slightly-- en dan hierdie een is miskien mees gruwelike van alle want iemand het spandeer soos hul dag die implementering van hierdie 'n paar jaar ago-- kom. O, wait-- dit is 'n fout. 

So loop op een van die wêreld se grootste webwerwe is hierdie dom bietjie Easter eiers. Hulle verbruik waarskynlik 'n nontrivial aantal reëls van die kode Net sodat ons kan bietjie pret dinge soos dat. Maar ten minste nou jy sommige van die binnekant grappies. 

Nou laat ons neem 'n blik op sommige van die wit lê het ons vertel van die laat, en begin om terug te skil sommige lae tegnies sodat jy werklik verstaan wat is aan die gang en jy kan verstaan sommige van die dreigemente, soos Shellshock, wat het nou begin om ' op die voorpunt van almal se aandag, ten minste in die media. So hier is 'n baie eenvoudige funksie dat die opbrengste niks, nietig. Sy naam is ruil. Dit neem in twee veranderlikes en dit gee niks. Neem in a en b. So 'n vinnige demonstrasie. Ons het hierdie up. Ons kan net sowel 'n bietjie breek hier vir 'n oomblik en het 'n bietjie iets om te drink. As iemand sou nie omgee by my hier vir net 'n oomblik. Hoe gaan jy in die maroen hemp? Kom op. Net die een vandag. Dankie, al is. Alle reg, en ons het kom wat hier? Wat is jou naam? 

SPREKER 4: Laura. 

Spreker 1: Laura. Kom op. So Laura, baie eenvoudige uitdaging vandag. Nice yo te ontmoet. Alle regte. So ons het 'n paar melk hier en ons het 'n paar oranje sap hier en 'n paar koppies wat ons geleen van Annenberg vandag. 

SPREKER 4: geleen het. Spreker 1: En gaan om voort te gaan en gee jou 'n halwe glas van hierdie. Alle regte. En ons sal die helfte van jou 'n glas van die melk. O ja, en net sodat jy kan onthou wat dit was soos, Ek onthou te bring hierdie en vandag. Goed. As jy nie sou omgee, laat ons sien, ons kan sit hulle oor jou eie bril As jy wil. Dit sal die wêreld van Laura se oë. Alle regte. So jou doel te bereik, gegewe twee koppies vloeistof hier, melk en oranje sap, is ruil die twee inhoud, sodat die lemoensap gaan in die melk beker en die melk gaan in die oranje sap beker. 

SPREKER 4: Het ek nog 'n koppie? Spreker 1: Ek is so bly dat jy gevra het, alhoewel dit sou gewees het baie beter footage As jy nie gevra het nie. Maar ja, ons kan u 'n derde beker wat leeg is, natuurlik. Alle regte. So ruil die inhoud daar. Baie mooi. Baie goed. Jy doen dit merkwaardig versigtig. En stap drie. Alle regte. Uitstekend. 'N Groot applous sal goed wees vir Laura wees. Alle regte. Ons het 'n bietjie afskeidsgeskenk vir jou, maar laat my toe om hierdie. Baie dankie. So 'n eenvoudige voorbeeld, al is, om te bewys dat as jy dit doen wil die inhoud te ruil van twee houers, of kom ons noem hulle veranderlikes, jy 'n paar tydelike berging een van die inhoud aan te bied in so dat jy eintlik kan doen om die ruil. So inderdaad, hierdie bron-kode hier in C verteenwoordigend van presies dit. As die lemoensap was 'n en die melk was b, en ons wou die twee te ruil, jy kan iets kreatief te probeer deur die gietende een in die ander, maar dat waarskynlik nie eindig besonder goed. En so het ons gebruik 'n derde koppie, oproep dit TMP, T-M-P deur konvensie, en sit die inhoud van die PB in, dan ruil die een beker, dan sit die PB in die oorspronklike beker, en sodoende bereiking, presies soos Laura het, die ruil. 

So kom ons doen presies dit. Laat my gaan voort en maak tot 'n voorbeeld wat eintlik geen sogenaamde " ruil, "want dit is nie as net gedoen as wat jy dink. So in hierdie program, sien dat Ek gebruik stdio.h, ons ou vriend. Ek het die prototipe vir omruil daar, wat beteken dat die implementering se waarskynlik onder, en laat ons sien wat hierdie belangrikste program gaan vir my om te doen. Ek het eers verklaar int x kry een, en int y kry twee. So dink van daardie as PB en melk, onderskeidelik. En dan het ek net 'n printf sê x is hierdie en y is dit net so kan ek visueel te sien wat aangaan. Toe ek printf beweer dat ek die uitruiling die twee, en dan het ek druk 'n beweer dat hulle verruil, en ek druk x en y weer. So hier in ruil is presies wat Laura het, en presies wat ons gesien het op die skerm 'n oomblik gelede. 

So laat ons gaan voort en wees baie teleurgesteld. Maak nie omruil en loop nie ruil, inzoomen op die uitset hier. Tik x is 1, y is 2, uitruiling verruil. x is nog 1 en y is nog 2. So selfs al is, eerlik, dit lyk presies wil, al is dit meer tegnies, wat Laura het, lyk nie te werk nie. So hoekom is dit? Wel, dit blyk dat wanneer ons skryf 'n program soos hierdie wat beide hoof, uitgelig hier en dan 'n ander funksie, soos ruil, uitgelig hier, wat dit noem, die wêreld lyk 'n bietjie iets soos hierdie bak 'n oomblik gelede. Wanneer belangrikste eerste kry genoem, dit is soos om te vra bedryfstelsel vir 'n bietjie van die geheue vir 'n plaaslike veranderlikes soos x en y wat hoof het, en hulle uiteindelik net daar. Maar as hoof oproepe ruil, en die belangrikste gaan twee argumente, A en B te ruil, lemoensap en melk, dit is nie soos uitreiking van die lemoensap en die melk te Laura. Wat 'n rekenaar nie, is dit verby afskrifte van die oranje sap en afskrifte van die melk te Laura, sodat Wat is uiteindelik binnekant van hierdie skinkbord is die waarde een en twee, of PB en melk, maar daarvan, sodat op hierdie punt in die verhaal, is daar is PB en melk in elk van hierdie bak. Daar is 'n een en 'n twee in elk van hierdie bak, en die ruil-funksie is inderdaad besig. Dit is die uitruiling hulle in van die tweede hoogste skinkbord, maar dat uitruiling het geen impak. En op grond van net 'n paar basiese beginsel wat ons het gepraat oor voor, en wel net 'n paar minute gelede, wat kan verduidelik waarom die verandering A en B binne ruil het geen effek op x en y, selfs al Ek geslaag x en y aan die ruil-funksie. Wat is die sleutel woord hier dat mag simplisties verduidelik? Ek dink ek het dit gehoor hier? Publiek: Return. Spreker 1: Terug? Nie terugkeer nie. Kom ons gaan met 'n ander. Wat is dit? 

Publiek: [onhoorbaar]. 

Spreker 1: OK, so return-- ons kon maak terugkeer werk in die storie, maar daar is 'n nog eenvoudiger verduideliking. Publiek: omvang. Spreker 1: omvang. Ek neem omvang. So omvang, onthou waar ons x en y verklaar. Hulle is binne verklaar van die belangrikste reg hier. A en B het intussen is effektief verklaar binnekant van ruil, nie heeltemal in die krulhakies, maar nog steeds in die algemene gebied van ruil. En so ja, A en B slegs binne hierdie skinkbord bestaan van Annenberg, hierdie tweede deel van die kode. So ons inderdaad die verandering van die kopie, maar dit is nie regtig alles wat nuttig. 

So laat ons neem 'n blik op dit 'n bietjie laer vlak. Ek gaan om terug te gaan na die Bron Gids, en ek gaan na die eerste zoom in hier, en net om te bevestig dat ek in hierdie groter terminale venster, die program is nog steeds gedra soos dit. Veronderstel nou dat hierdie nie opsetlike. Dit is duidelik dat ek wou ruil vir werk, so dit voel soos 'n fout. Nou kan ek begin toevoeging van 'n baie printf se my kode, uit te druk x hier, y oor hier, 'n hier, b hier. Maar eerlik, dit is waarskynlik wat jy gedoen het vir 'n paar weke nou, in kantoorure en by die huis by die werk op psets probeer om foute te vind. Maar jy sien, as jy nog nie het nie, dat die probleem van drie stel jou 'n bevel genoem GDB, waar GDB, GNU debugger, het self 'n hele klomp van die funksies wat kan eintlik Laat ons situasies te verstaan soos hierdie, maar meer dwingend, probleme op te los en vind foute. So ek gaan om dit te doen. In plaas van ./noswap, ek is in plaas gaan GDB ./noswap te voer. Met ander woorde, ek gaan om te hardloop my program nie in Bash, ons nuwe vriend vandag. Ek gaan loop my program noswap binne van hierdie ander program genaamd GDB, wat 'n debugger, wat is 'n program wat ontwerp is om te help Julle mense vind en foute verwyder. So as ek getref Begin hier, daar is 'n gruwelike bedrag van die teks dat jy nooit regtig het om te lees. Dit is in wese 'n afleiding uit die vinnige, wat Ek gaan om te tref Control-L opstaan ​​om die top is daar. Dit is die GDB vinnige. As ek hierdie program wil nou hardloop, as hierdie klein cheat sheet op vandag se skyfie stel, Run is die eerste beveel dat ons bedoel is om te voer. En ek is net gaan om te tik aanloop hier binnekant van GDB, en inderdaad is dit gehardloop my program. Nou is daar 'n paar ekstra uitgange van die skerm soos hierdie, maar dit is GDB om net anale en vertel ons wat aangaan. Jy moet regtig nie hoef te bekommer oor hierdie besonderhede nou. Maar wat is regtig cool oor GDB, as ek dit doen again-- Control-L goedkeuring van die screen-- laat my gaan voor en tik "breek hoof," daardeur, toe ek Tik, die opstel van wat is genoem 'n breek punt noswap.c, lyn 16, en dit is waar GDB uitgepluis my program eintlik is, my funksie eintlik is. Dit sal ons ignoreer vir nou maar dit is die adres in die geheue spesifiek van hierdie funksie. So nou wanneer ek tik hardloop, sien wat is koel hier. My program breek op die lyn wat ek vertel GDB uitvoering te breek op. So ek het nie nou my kode verander, voeg 'n paar printf se, heropstel dit, tik dit verander, voeg 'n paar printf se, behalwe dit, heropstel dit is, loop dit. Ek kan net loop deur my program stap vir stap vir stap op die menslike spoed, nie by Intel-binne soort van spoed. 

So nou sien hierdie lyn hier verskyn, en as ek terug gaan om my program in gedit, sien dat dit is eintlik die heel eerste reël van die kode. Daar is lyn 16 in gedit. Daar is lyn 16 binne GDB, en selfs al hierdie swart en wit koppelvlak is nie naastenby so gebruiker vriendelik, dit beteken dat die lyn 16 is nie uitgevoer nie, maar dit is om te wees. So inderdaad as ek tik druk x, nie printf, net druk x, Ek kry 'n paar valse waarde daar van nul, want x is nog nie geïnisialiseer. So ek gaan na die volgende tik, of, as jy wil fancy wees, net n vir die volgende. Maar toe ek tik die volgende tree, nou sien dit beweeg op lyn 17. So logies, as ek uitgevoer lyn 16 en ek tik nou druk x, Wat moet ek sien? Een. 

En nou is dit weliswaar verwarrend. $ 2 is net 'n fancy manier, as jy later wil verwys na daardie waarde, jy kan sê "dollar teken twee." Dit is soos 'n terug verwysing. Maar vir nou, net ignoreer. Wat interessant is, is wat is op die regterkant van die gelykaanteken. En as ek nou tik die volgende weer en druk y, moet ek sien 2. Ek kan ook nou druk x weer, en eerlik, As ek 'n bietjie verward waar Ek is, kan ek tik lys vir 'n lys en sien net 'n paar konteks rondom die punt wat ek eintlik aan. En nou, ek kan tik volgende, en daar is x 1. Nou tik ek die volgende. O, y is 2. En weer, dit is verwarrend, omdat GDB se uitset word die institutionele met my eie produksie. Maar as jy in gedagte hou, deur skrams heen en weer by jou kode of lê dit uit kant mekaar miskien, sal jy sien wat werklik ek is net versterking deur middel van my program. 

Maar let op wat gebeur volgende, letterlik. Hier is lyn 22. Laat my gaan oor dit, en daardeur beweeg op tot 23, en as ek druk x nou, steeds een. En as ek druk y nou, steeds een. Dit is dus nie 'n nuttige oefening. So laat oordoen dit. Laat my terug te gaan na die top en die tipe weer hardloop. En dit is te sê dat die program dit is wat ontfout het reeds begin, begin van die begin af. Ja, kom ons doen dit weer. En hierdie keer kom ons doen die volgende, volgende, volgende, volgende, volgende, maar nou dinge interessant. Nou wil ek stap in ruil, so ek tik nie volgende. Ek tik stap, en nou sien dit het my na noswap.c line 33 gespring. As ek gaan terug na gedit, wat is lyn 33? Dit is die eerste werklike reël van die kode binnekant van ruil. Wat is lekker, want nou kan ek soort steek rond en kry nuuskierig oor wat aangaan werklik daar. Laat my druk tmp. Whoa. Waarom het tmp het 'n paar gek, valse vullis waarde? Publiek: Dit is nie geïnisialiseer. Spreker 1: Dit is nie geïnisialiseer. En inderdaad, wanneer jy 'n program, jy 'n hele klomp van die geheue is gegee deur die bedryfstelsel nie, maar het nie geïnisialiseer enige waardes, Dus, wat stukkies jy sien hier, selfs al is dit hierdie mal groot negatiewe nommer, beteken net dat dit die oorblyfsels van sommige vorige gebruik van die geheue, selfs al het ek nie myself nodig dit nog nie. So nou is ek gaan om voort te gaan en die tipe volgende, en as ek tik nou druk tmp, Wat moet ek sien? Wat ook al die waarde van 'n was, a is die eerste argument, net soos x was die eerste ding wat geslaag het in, so 'n en x moet dieselfde wees, so druk tmp moet druk my een. 

So, wat jy sal sien in probleem stel drie is 'n handleiding van spesies op GDB, maar besef dat dit is die begin 'n blik op 'n instrument wat eintlik help om probleme op te los soveel meer effektief. Wat ons uiteindelik gaan doen op Woensdag is begin terug te skil 'n paar lae en verwyder 'n paar opleiding wiele. Dat die ding genoem string wat ons gebruik het vir 'n geruime tyd, ons gaan stadig neem dit weg van jou en begin praat oor iets meer esoterisch bekend as char *, maar ons gaan dit lekker om te doen en liggies op die eerste, selfs al wysers, as hulle genoem word, kan 'n paar te doen baie slegte dinge as mishandel, deur te kyk na 'n bietjie claymation uit ons vriend Nick Parlante van Stanford Universiteit, 'n professor in die rekenaar wetenskap wat hierdie voorskou saam van wat hierdie Woensdag te kom. 

[Video speel] Hey, Binky. Wakker. Dit is tyd vir wyser pret. 

-Wat Is dit? Meer inligting oor die riglyne? O, goody! [Einde video speel] Spreker 1: Dit wag vir jou op Woensdag. Ons sal sien dat jy dan. [Video speel] -En nou, diep gedagtes, deur Daven Farnham. 

-Waarom Ons leer C? Hoekom nie A +? 

[Gelag] 

[Einde video speel]