[Muziek] 

SPEAKER 1: Oke, dit is CS50, en dit is het begin van week vier, en zoals je misschien al gehoord of lezen, is de wereld eindigt. Gaan al rond het internet heeft zijn kennis en bewustzijn van een bug in een programma, een programmeertaal genaamd Bash. Dit is prachtig gebrandmerkt als Shellshock, of de Bash deur, maar artikelen als deze zijn niet ongewoon zijn. En in feite, veel van hen te brengen herinneringen terug van Heartbleed, die je misschien al gemerkt hebt in de Druk afgelopen voorjaar terug, die was ook tamelijk dramatisch. Nu van die van jullie hier vandaag, hoeveel van jullie hebben, zelfs als je niet begrijpt wat draait het allemaal om, gehoord van Shellshock? Oke, en hoe velen van jullie hebben computers die kwetsbaar zijn? OK, er moet veel, veel meer handen tot nu, om redenen die we zullen zien. 

Laten we eens kijken naar wat er is er in de media en leg het dan een beetje hier voor ons technisch. 

SPEAKER 2: Security experts hebben gewaarschuwd dat een ernstige fout kon ongeveer beïnvloeden honderden miljoenen van 's werelds webgebruikers. Dus wat is precies de fout die is geweest nagesynchroniseerde Shellshock, en wat doet het? Nou, Shellshock is ook bekend als de Bash bug, de software die het exploiteert. Hackers gebruiken het virus te scannen kwetsbaar systemen met Linux en Unix besturingssystemen en vervolgens te infecteren. Bash is een command line shell. Dit stelt gebruikers in kwestie commando's te starten programma's en functies in de software door het invoeren van tekst. Het wordt meestal gebruikt door programmeurs, en moet niet open voor de buitenwereld, hoewel Shellshock verandert dat. 

Nou, worringly, sommige analisten waarschuwen het kan een grotere bedreiging te zijn, omdat Shellshock is volledige controle over een besmette machine, terwijl Heartbleed alleen toegestaan hackers bespioneren computers. Het is zo ernstig, het is is beoordeeld op 10 van de 10 voor de ernst van de Nationale Vulnerability Database. 2/3 van alle webservers zijn op risico's, waaronder een aantal Mac-computers. Nou, zorg ervoor dat je patch nu uw systemen. Iedereen het hosten van een website draaiende de getroffen besturingssystemen moet actie zo snel mogelijk te nemen. Iedereen die zich kan veroorloven het eruit moet zien om de monitoring en web-applicatie firewalls om uit te kijken voor eventuele aanslagen. SPEAKER 3: Ergste dat zou kunnen gebeuren is dat iemand code zou schrijven dat zou automatisch gaan scannen het internet en van invloed zou zijn al deze computers. En zodra ze dat goed doen, het ergste wat ze konden doen is gewoon alles te verwijderen, of sluit de sites af. Dus we konden de schade zien vanuit dat oogpunt, waar we kwaadwillende mensen zouden hebben die alleen maar besluiten om ellende te veroorzaken door het brengen van systemen naar beneden of verwijderen bestanden, en dat soort dingen. SPEAKER 2: Sommigen zeggen dat dit een van de meest moeilijk te meten bugs in jaren, en kan weken duren of zelfs maanden de tijd om zijn uiteindelijke effect te bepalen. 

SPEAKER 1: Dus dat is allemaal waar, maar het grappige is, bijna alle van de beelden zag je gewoon, behalve misschien het toetsenbord, heeft niets te maken met de bug dan ook. Servers en draden enzovoort, Het is een soort van zijdelings gerelateerd, maar in de kern is het eigenlijk best bekend wat er aan de hand hier. In feite, laat me gaan in onze CS50 apparaat. Laat me ga je gang en het maximaliseren het terminalvenster hier. En jullie zijn met behulp van deze, of de embedded versie daarvan, in gedit om programma's te schrijven, typen opdrachten, enzovoorts, en dit is eigenlijk, en heeft al weken, Bash, B-A-S-H. Dit is de Bourne-Again Shell, dat is gewoon een mooie manier om te zeggen, Dit is een programma dat is knippert snel, effectief, die zit te wachten voor input voor u. En het is de opdracht line interface via welke jullie hebben gelopen commando's en uiteindelijk samenstellen en dan loopt programma. 

Maar Bash is ook een programmering taal de volgende betekenis. Je weet dat er commando's als cd en ls en ook kletteren en anderen, maar je kunt je eigen commando's te definiëren door de uitvoering ervan in Bash. Nu zijn we niet van plan om gaan in groot detail met betrekking tot de programmeertaal dreun, maar weet bijvoorbeeld dat op het moment, er is geen commando genaamd "hallo." Zodat het kan worden gevonden in een van deze pakketten. Het is niet op mijn computer geïnstalleerd. Vraag uw beheerder. Maar als ik wil dat er een programma worden genaamd "hello" in Bash of bij mij prompt, Ik kan eigenlijk gebruiken syntax dat is heel graag C. Het is niet helemaal hetzelfde, maar het ziet er vergelijkbaar met een functie, zij missen wat details. Niets lijkt te gebeuren, maar nu als ik typ "hello" kan je eigenlijk schrijven programma niet in C, niet in Java, niet in een andere programmeertaal taal, maar in Bash zelf. 

Nu is de sleutel hier is dat ik schreef het noem ik wilde deze nieuwe opdracht te geven, en de haakjes zijn ook symbolisch voor dit een functie is. Even terzijde, kun je ook leuk doen dingen, en in feite, zelfs op Mac OS, Dit is een programma genaamd Terminal. Het komt ingebouwd in iemands computer die een Mac heeft in deze kamer, en je kunt soortgelijke dingen in Mac doen OS, maar je kunt meer dan dat gaan. En dit is een kleine tangentiële, maar het is wel leuk. Ik werd vanmorgen herinnerd, wanneer het denken dit door middel van, van een klein spel dat ik gebruikt om te spelen met een van de voormalige TFs CS50's waarbij elk ogenblik zou hij weglopen zijn toetsenbord met zijn scherm ontgrendeld, Ik zou een commando uit te voeren zoals dit-- "hallo zeggen." En nu elke keer kwam hij terug naar zijn toetsenbord nadat Ik schraapte het scherm en hij zou gaan zitten, proberen om wat werk te doen, een lijst van de inhoud van zijn directory-- 

[AUDIO AFSPELEN] 

-Hallo. Hello. 

SPEAKER 1: Dus, in alle eerlijkheid, het was niet echt "hallo." Het was meestal iets meer verwant aan dat-- [AUDIO AFSPELEN] -Beep. SPEAKER 1: --that Ik would-- zodat zijn computer zou zweren bij hem elke keer als hij daadwerkelijk ging aan zijn toetsenbord. En heel snel bedacht hij geen reactie zijn scherm ontgrendeld. Maar dit suggereert dat de soort van domme plezier dat je kunnen hebben met iets als Bash. Maar het is een beetje meer ernstig, om zeker te zijn, dan dat. En in feite is dit een van de meest gevaarlijke en langdurige bugs dat is echt wereldwijd geraakt de wereld. Deze bug is al ongeveer 20 jaar en u zult worden gevonden in slechts een schip door de relatieve eenvoud. 

Dit is een representatief zeg dan, dat als je het bezit van een Mac, letterlijk op dit moment wanneer u uw deksel open, je kunt proberen te typen in dat programma genaamd Terminal. Terminal is onder Toepassingen Utilities-- voor een keer, niet Windows-gebruikers niet hoeven te zorgen te maken over dit bijzondere threat-- maar die van u met Macs kunt typen dit in een venster zoals ik hier doe, en als je typt dat in dit programma genaamd Terminal, zoals ik nu doe, Als u het woord 'kwetsbaar' uw computer is kwetsbaar voor uitbuiting. 

Nu, wat betekent dat eigenlijk? En dit is weliswaar sommige behoorlijk gek syntax, maar laten we in ieder geval trekken uit aantal interessante aspecten. Dus er is een aantal syntax die lijkt een beetje bekend, tenminste C en het programmeren in het algemeen. Ik zie een aantal haakjes, puntkomma, accolades, en dergelijke, maar het blijkt dat dit stomme ding hier in het geel vooral afhankelijk dat doet niets. De dubbele punt betekent niets doen, en de puntkomma betekent stoppen met niets doen. Dus binnen deze accolades, het feit dat ik een gelijke teken naar links, dit hoofdzaak creëren een commando of een variabele genaamd x, en het toewijzen van het dat gele stukje code daar. Dat zou iets als "echo te zijn hallo "of" zeggen piep "of iets vergelijkbaar met die. Maar let op als je ogen dwalen verder naar rechts, er is meer aan deze lijn dan alleen het einde van die puntkomma. "Echo kwetsbaar," en dan verder dan dat er nog meer. Een andere puntkomma, bash-c :. 

Zo lang verhaal kort, deze regel code is voldoende om dwingende een computer die is kwetsbaar iets te doen dat u wilt doen, omdat er een bug in Bash waarbij hoewel Bash moest stoppen lezen van regels van het commando rechts er na de gele tekst, voor een 20-plus jaar oude bug, Bash is eigenlijk al het lezen verder dan dat puntkomma en mooi veel te doen wat het wordt verteld. 

Dus wat is de implicatie van dat uiteindelijk? Ik zei gewoon "echo hello" of "echo kwetsbaar," maar wat als je iets deed eigenlijk kwaadaardige, zoals rm-rf *, die je misschien niet hebben voordat ooit getypt, en eerlijk gezegd heb je waarschijnlijk moet niet te vroeg, omdat je een kunt doen veel schade mee. Waarom? rm doet wat, natuurlijk? Verwijdert. * Betekent wat? Alle. Het is dus een zogenaamd wild card, dus betekent alles verwijderen de huidige directory. -r gebeurt recursieve te betekenen, wat betekent dat als wat je te verwijderen is een directory, en de binnenkant van daar is andere bestanden en andere mappen, recursief induiken er en dat alles wissen. En f is de ergste van allemaal. Iedereen weet wat -f betekent hier? Kracht. Dus dwingen middelen, zelfs als dit een slecht idee, doe het zonder te vragen mij voor verdere bevestiging. Dus, weet je, we lachen bij dit, maar eerlijk gezegd, ik waarschijnlijk typt u deze meerdere keren een dag, omdat de realiteit is het is de snelste manier om een hele hoop dingen moeten verwijderen. Maar ook heb ik wat schade gedaan. 

Maar als je naar een computer te misleiden in het definiëren van enkele domme variabele of functie genaamd x, maar tricking de computer in te voeren buiten de grenzen van deze functie, dan dat puntkomma, je zou inderdaad kunnen verleiden een computer in iets uitvoeren als rm-rf of de e-mail commando of de opdracht Kopiëren. Even wat letterlijk je kunt doen met de computer, of het nu het verwijderen van bestanden, aanmaken van bestanden, spammen iemand, aanvallende enkele server op afstand, als je het kan uitdrukken met een opdracht, je kan een computer te verleiden tot dat te doen. 

Nu, wat is een voorbeeld van hoe je dit zou kunnen doen? Nou, er is heel veel computers op het internet lopen Bash. Ieder van ons Mac-gebruikers zijn onder hen. Een groot aantal Linux-servers behoren tot ze net zo goed, en Unix servers. Windows opnieuw krijgt relatief de haak tenzij u hebt geïnstalleerd speciale software. Nu veel servers, bijvoorbeeld om webservers, en in feite Linux is misschien wel de meest populaire besturingssysteem te draaien op computers op het internet die zijn waar je van webpagina's. Nu zoals we zullen later zien in het semester, toen u een verzoek uit te sturen uw browser-- Chrome, Internet Explorer, whatever-- naar een externe server, blijkt dat hoewel je net getypt www.example.com, Uw browser is het verzenden van een bericht dat is een beetje meer mysterieuze, zoals deze. 

Maar let een beetje iets vreemds. De eerste twee regels Ik heb nog nooit eerder gezien, maar ze zien er niet uit bijzonder bedreigend. Maar let op wat ik heb gestolen voor de derde regel hier. Als een slechte kerel was om een ​​bericht te sturen als deze uit zijn of haar computer om een ​​kwetsbare Mac of een kwetsbare Linux-server, het grappige is dat Bash, dat eenvoudige kleine opdrachtprompt alomtegenwoordig en is vaak gebruikte in wezen te voeren de inhoud van een boodschap die het ontvangt. En door die logica, kunt u truc een webserver derhalve door iets verzenden als User-Agent, die meestal wordt verondersteld om het te zeggen naam van je browser. User-Agent Chrome, User-Agent Internet Explorer, User-Agent Firefox, dit is gewoon je browser manier om zichzelf te identificeren. Maar als een slechte kerel zeer slim zegt, mm-mm, ik ben niet van plan om u te vertellen wat mijn browser is, Ik ga in plaats daarvan ga je deze sturen cryptisch uitziende ding met een rm-rf * In het, kunt u letterlijk een truc kwetsbare webserver op het internet in het uitvoeren van precies dat in er voor het verwijderen van alle bestanden. En eerlijk gezegd, dat is niet zelfs de ergste. Je kunt alles doen. Je zou kunnen beginnen met een gedistribueerde denial of service-aanval Als u dit bericht verzonden naar hele trossen van webservers en dan hadden ze allemaal afstammen, voor bijvoorbeeld op Harvard.edu servers, en u kunt sorteren van bang heck uit hen een netwerkverkeer dat was anders wordt veroorzaakt door deze slechte kerel. 

Dus, lang verhaal kort, bijna iedereen in deze kamer, die eigenaar is van een Mac is kwetsbaar voor dit. De zilveren voering is dat, tenzij je het runnen van een webserver op uw laptop, en tenzij je hebt eigenlijk geconfigureerd het om iets als SSH toelaten in het, je bent echt veilig. Het is kwetsbaar, maar er is geen men probeert te krijgen in uw laptop, dus je kunt een soort van gerust zijn. Echter, Apple zal binnenkort zijn het bijwerken van een oplossing voor dit. De wereld van Linux heeft al vrijgegeven een aantal fixes voor Fedora en Ubuntu andere versies en Linux, en inderdaad Als u Update 50 draaien in het apparaat, zelfs dat ook wordt geactualiseerd en gecorrigeerd. Dat is ook niet echt kwetsbaar geweest, want als je hebt gesleuteld aan het apparaat en maakte je laptop in het openbaar toegankelijk op het internet, die niet is standaard, je hebt eigenlijk prima omdat geweest van firewalling en andere technieken. 

Maar het is een extreem voorbeeld van een bug dat we hebben geleefd voor letterlijk 20 jaar, en wie als iemand weet al die tijd heeft geweten? En in feite is dit een van de fundamentele uitdagingen dat we later zullen zien in de semester over de veiligheid, is dat net als in de echte wereld, de good guys zijn in het nadeel. Om de slechteriken te houden, moeten we Zorg ervoor dat elke deur is op slot, dat elk raam is veilig, dat elk punt van binnenkomst in een huis veilig is om de slechteriken te houden. Maar wat doet de bad guy te doen om daadwerkelijk een compromis uw huis en stelen van je? Hij of zij heeft gewoon een unlocked vinden deur, een gebroken raam, of iets in die richting, en het is de hetzelfde in computerbeveiliging. We kunnen miljoenen schrijven regels programmeercode en spenderen honderden of duizenden uren proberen om het juist te krijgen, maar als je gewoon een fout in de juistheid, U kunt het hele systeem te zetten en zelfs in dit geval volledig Internet en de wereld in gevaar. 

Dus als je wilt om meer te leren over dit, ga dan naar deze URL hier. Er is geen noodzaak voor actie vanavond tenzij je onder hen meer comfortabel dat zijn het runnen van uw eigen web- server, in welk geval u zou mogen, in feite, update uw software. 

En dit is ook de titel van een toespraak, en nu een papier, dat we hebben gekoppeld aan de website cursus voor vandaag. Het was door een collega genaamd Ken Thompson, die was het aanvaarden van een zeer bekende onderscheiding in de informatica, en hij gaf deze toespraak een aantal jaren geleden, in wezen op hetzelfde onderwerp. Vragen mensen de vraag, moet je echt vertrouwen, uiteindelijk, de software die u hebt gekregen? Bijvoorbeeld, we hebben allemaal het schrijven van programma's, en we hebben het samenstellen ze met Clang. En om je kennis, je hebt geschreven alle programma's voor CS50 waar er een achterdeur van soorten, is een weg dat een slechte kerel, als het runnen van uw programma, over uw computer zou kunnen nemen? Waarschijnlijk niet, toch? Mario en Gulzig, en Credit. Dit zijn allemaal vrij kleine programma's. Je zou mooi zijn slecht als je eigenlijk maakte je hele computer kwetsbaar na het schrijven van 10 of 20 regels code, of althans niet bewust van enige van de gevolgen voor de beveiliging. Nu zeg ik dat schertsend, maar we gaan vandaag zien en deze week is het eigenlijk echt, echt makkelijk slecht te zijn en zelfs korte programma's kwetsbaar. 

Maar voor nu, op zijn minst, realiseren dat de vraag hier wordt gevraagd ongeveer Clang in een compiler. Waarom hebben wij vertrouwen Clang voor de afgelopen twee of drie weken? Wie zegt dat wie schreef Clang niet over een "als" toestand er dat hoofdzakelijk geïnjecteerde sommige nullen en die in elk programma compileert dat zou laten hem of haar de toegang uw computer wanneer u slaapt en uw laptop deksel open en uw computer aanstaat? Rechts? Wij hebben dit soort van eer systeem recht nu waar we vertrouwen erop dat Clang is legit. U erop vertrouwen dat het apparaat is legit. Je vertrouwt dat letterlijk elk programma op uw Mac of pc is betrouwbaar. En als deze eenvoudige bug doet vermoeden, zelfs als het niet kwaadaardig is, dat is absoluut niet waarschijnlijk het geval. 

Dus moet je bang als de hel zijn. Eerlijk gezegd, er is geen eenvoudige oplossing die andere dan een soort van maatschappelijke bewustwording de toenemende complexiteit dat we bouwen op de top van onze computersystemen, en hoe steeds kwetsbaarder we kunnen heel goed zijn. 

Nu met dat gezegd, Breakout. Dus Breakout is probleem set drie, en Breakout is een spel van weleer dat je nog wel herinneren, maar voor ons in probleem set drie, Het stelt ons in staat om te nemen dingen back-up een inkeping zodat wanneer we schrijven programma's, zelfs in een Terminal-venster als dit, kunnen we eigenlijk lopen, uiteindelijk, grafische programma's niet in tegenstelling tot die we hadden toegang tot in Scratch. Dus dit is het personeel uitvoering van Breakout, dat is alleen deze baksteen-brekende spel, dat je je peddel terug te gaan en weer, en je de bal raakt tegen die gekleurde stenen boven. Dus dit brengt ons soort terug naar waar We konden heel snel met Scratch, en nu met C, de uitvoering van onze eigen grafische gebruikersinterfaces. 

Maar meer dan dat, deze probleem set is de eerste waarin we geven u een bos van code. En in feite, ik breng expliciete aandacht, want vooral voor degenen die minder comfortabel, dit probleem stellen, althans op het eerste gezicht, gaat om het gevoel dat we hebben het gemaakt tot een inkeping. Omdat we je hebben gegeven, voor sommige zoekterm en sorteren problemen in de PSET, een bos van code die we schreven, en een paar reacties die zeggen "te doen," waar je de lege plekken op te vullen. Dus niet te eng, maar het is de eerste keer wij overhandigen u code die je nodig hebt om eerst te lezen, te begrijpen en vervolgens toe te voegen aan en vul het in. 

En dan met Breakout, we gaan om hetzelfde te doen, waardoor u een paar dozijn meer lijnen van de code die, eerlijk gezegd, geef je veel van het kader voor het spel, maar stoppen met korte van de uitvoering van de bakstenen en de bal en de peddel, maar we voeren een aantal andere functies. En zelfs dat op het eerste gezicht, weer, vooral als minder comfortabel, lijkt vooral ontmoedigend en je denkt dat er zoveel nieuwe functies je nodig hebt om je geest te wikkelen rond, en dat is waar. Maar houd in gedachten, het is heel graag Scratch. Kans groot dat u niet al te gebruiken de puzzelstukjes in Scratch. Kans groot dat u niet de zorg in te pakken je geest om ze allemaal omdat al duurde het was een snelle blik om te begrijpen, oh, dat is wat ik kan doen met dat puzzelstukje. En inderdaad, in het probleem te stellen 3 spec, zullen wij u wijzen op de documentatie die zal u kennismaken met een aantal nieuwe functies, en uiteindelijk de programmering construeert u gebruikt. Condities, loops, variabelen en functies identiek zal zijn wat we tot nu toe hebben gezien. 

Dus inderdaad, wat we zullen geven u is wat voorbeeldcode die Hiermee kunt u een venster te maken dat ziet er niet veel anders dan deze, en uiteindelijk om te zetten in iets heel graag dit. Dus profiteren van de CS50, bespreken kantooruren en meer, en gerustgesteld dat de hoeveelheid code die je hebt om te schrijven is eigenlijk niet zo heel veel. De eerste uitdaging is juist om te acclimatiseren uzelf op een code die we hebben geschreven. 

Heeft u vragen over pset3, Shellshock, of anderszins? 

Publiek: Het leek gaan door met Breakout dat de code is bijna een object-georiënteerde stijl, maar ik dacht dat C was een object-georiënteerd programma. SPEAKER 1: Een goede vraag. Dus op zoek via de distributie code, de code we schreven voor pset3, voor degenen die bekend zijn, is het ziet eruit alsof het een weinig objectgeoriënteerde. Korte antwoord is, het is. Het is een benadering van de manier waarop u misschien objectgeoriënteerde code doen met behulp van een taal zoals C, maar het is uiteindelijk toch procedureel. Er zijn geen methoden binnenin de variabelen, zoals u zult zien. Maar het doet denken aan dat. En we zullen die functie weer te zien als we in PHP en JavaScript tegen het einde van het semester. Maar voor nu, denk aan het als een hint van wat er komen gaat. Goede vraag. Oke. Dus samenvoegen soort was hoe we linkse dingen laatste tijd. En samenvoegen soort was koel in de zin dat het zo veel sneller, ten minste op basis van het vluchtig testen we hebben vorige week, dan, zeg, bel soort, selectie sorteren, insertion sort. En wat was te netjes is gewoon hoe bondig en netjes je kunt het uit te drukken. En wat hebben we zeggen het was een bovenste gebonden aan de looptijd van de merge sorteren? Yeah? 

PUBLIEK: n log n? 

SPEAKER 1: n log n, rechts. n log n. En we terug naar wat die komen werkelijk betekent of waar die vandaan komt, maar dit was beter dan looptijd die we zagen voor de bubble selectie en insertion sort? Zo n kwadraat. n kwadraat is groter dan dit, en ook al is het niet helemaal duidelijk, weten dat log n kleiner is dan n, dus als je n keer iets kleiner dan n, het gaat om minder dan n kwadraat zijn. Het is een beetje van intuïtie daar. Maar we betaalden een prijs voor. Het was sneller, maar een thema dat begon vorige week naar voren was deze afweging. Ik heb betere prestaties tijd verstandig, maar wat had ik moeten besteden aan de andere de hand, om te bereiken dat? 

PUBLIEK: Memory. SPEAKER 1: Zeg nog eens? PUBLIEK: Memory. SPEAKER 1: Geheugen, of ruimte meer in het algemeen. En het was niet super duidelijk onze mensen, maar herinneren dat onze vrijwilligers werden naar voren stapt en intensivering terug alsof er een scala hier en alsof er een tweede array hier dat ze kunnen gebruiken, omdat we broodnodige ergens naar die mensen samen te voegen. We konden niet alleen ruilen hen op zijn plaats. Dus samenvoegen soort hefboomwerking meer ruimte, die we niet nodig met de andere algoritmen, maar het voordeel is dat het veel sneller. En eerlijk gezegd, in de echte wereld de ruimte deze dagen-- RAM, een harde schijf ruimtebesparing is relatief goedkoop en dus dat niet per se een slechte zaak. 

Dus laten we eens een snelle blik, een beetje meer methodisch, naar wat we deden en waarom we vonden het een n log n. Dus hier zijn de acht nummers en de acht vrijwilligers hadden we de vorige keer. En het eerste wat samenvoegen Sorteer vertelde ons te doen was wat? PUBLIEK: Verdeel in twee. SPEAKER 1: Zeg nog eens? PUBLIEK: Verdeel in twee. SPEAKER 1: Verdeel in twee, rechts. Dit doet sterk denken aan het telefoonboek van de kloof en verover meer in het algemeen. Dus hebben we gekeken naar de linker helft. En toen we eenmaal gezegd, een soort de linkerhelft van de elementen, wat hebben we volgende zeggen? Sorteer de linkerhelft van de linker de helft, wat ons toeliet om, Na verdelen in twee, focus op vier en twee. 

Hoe maak je nu een lijst te sorteren, in geel, van de grootte van twee, met behulp van Merge Sort? Goed verdeel het in tweeën, en sorteren van de linker helft. En dit was waar dingen kreeg een beetje dom kort. Hoe maak je een lijst die is van afstand maat one, als dit nummer vier hier? Het is opgelost. U bent klaar. 

Maar hoe maak je een lijst van de gekozen afstand maat one wanneer het de nummer twee? Nou, hetzelfde, maar nu wat was de derde en de belangrijkste stap in het Merge Sort? Je moest naar links samenvoegen de helft en de rechter helft. En als we dat deden, keken we bij vier, hebben we gekeken naar twee. We besloten al goed, uiteraard twee staat voorop, dus hebben we twee in haar plaats, gevolgd door vier. En nu moet je soort terugspoelen, en dit is een soort van karakteristieke van een algoritme zoals Merge Sorteren, terugspoelen in het geheugen. Wat was de volgende regel van het verhaal? Wat moet ik richten op de volgende stap? De rechterhelft van de linker de helft, dat is zes en acht. 

Dus laat me gewoon stap door dit zonder belaboring het punt te veel. Zes en acht, dan zes is gesorteerd acht wordt gesorteerd. Meng ze samen als dat, en nu is de volgende grote stap is natuurlijk, sorteren de rechterhelft van de eerste stap van dit algoritme. Dus richten we ons op een, drie, zeven, vijf. We hebben toen gericht op de linker helft. De linkerhelft van dat de rechterhelft van dat, en vervolgens samen te voegen in een en drie. Dan is de rechter helft, dan is de helft naar links ervan, dan is de rechter helft van het. Samenvoegen in, en wat nu stap blijft? Voeg de grote linker helft en de grote rechter helft, dus men gaat daar beneden, dan twee, dan drie, dan vier, dan vijf dan zes, dan zeven, dan acht. 

Dus nu waarom is dit uiteindelijk het openbaren, vooral als n en logaritmen meer algemeen vrij ontsnappen u, althans in de recente geschiedenis? Nou, let op de hoogte van deze zaak. We hadden acht elementen, en we gedeeld door twee, twee, twee. Dus log basis van twee van de acht geeft ons drie. En geloof me op dat als een beetje vaag over dat. Maar log basis twee van de acht is drie, dus we hebben drie lagen samenvoegen gedaan. En als we gefuseerd elementen, hoeveel elementen hebben we naar op elk van die rijen? Een totaal van n, toch? Omdat aan de bovenste rij samenvoegen, ook al deden we het stukje bij beetje, we uiteindelijk raakte elk nummer een keer. En in de tweede rij, naar samenvoegen die lijsten van de grootte van twee, we moesten elk element een keer aanraken. En dan is hier echt duidelijk in de laatste rij, We moesten elk van die raken elementen eenmaal, maar slechts eenmaal, dus hierin ligt dan onze n log n. 

En nu alleen maar om dingen een beetje te maken meer formele voor slechts een moment, als je waren om dit nu te analyseren een soort hogere en proberen om te beslissen, hoe goed zou je gaan over het uiten van de looptijd van dit algoritme gewoon door er naar te kijken en niet met behulp van een gekunsteld voorbeeld? Nou, hoeveel tijd zou je zeggen een stap als dit in het geel zou nemen, als n <2 terug? Dat is een grote O van wat? Dus ik ben het zien van een, dus een stap, misschien twee stappen, want het is als en dan terug te keren, maar het is constante tijd, toch? Dus we zeiden O (1), en dat is hoe ik dit zal uiten. T, gewoon looptijd. n is de grootte van de ingang, dus T (n), gewoon een mooie manier zeggen de running tijd bepaalde input van grootte n gaat worden in de orde van constante tijd, in O (1). 

Maar voor de rest, hoe zit dit? Hoe zou u drukken de looptijd van deze gele lijn? T van wat? U kunt soort cheat hier en antwoord op mijn vraag cyclisch. Als de looptijd in algemeen zijn we gewoon zeggen is T (n). En nu bent u soort hier punteren en zeggen, nou ja, gewoon afstand de linker helft, en vervolgens sorteert de rechter helft. Hoe kunnen we symbolisch vertegenwoordigen de looptijd van deze gele lijn? T van wat? Wat is de grootte van de input? n meer dan twee. Waarom heb ik niet gewoon zeggen dat? En dan is dit nog een T (n / 2) en vervolgens nogmaals, als ik het samenvoegen van twee gesorteerde helften, hoeveel elementen ga ik moeten raken totaal? n. Dus ik kan dit uit te drukken, gewoon soort van fancy, als de lopende tijd in het algemeen. T (n) is gewoon de looptijd van T (n / 2), plus T (n / 2), linkerhelft en rechterhelft, plus O (n), die waarschijnlijk n trappen, maar misschien, als ik met twee vingers, het is twee keer zoveel stappen, maar het is lineair. Het is een aantal stappen dat is een factor van n, dus we kunnen dit uit te drukken als deze. En dit is waar nu zullen we punter naar de achterkant van onze middelbare school mathhandboek we zijn dat herhaling uiteindelijk eindigt gelijk dit, n keer log n, als je eigenlijk doen uit de wiskunde meer formeel. 

Dus dat is gewoon twee perspectieven. Een numeriek met een hard-coded representatief voorbeeld behulp van acht cijfers en een algemene kijk op hoe we daar aankwamen. Maar wat echt interessant hier is, nogmaals, dit begrip van het wielrennen. Ik maak geen gebruik van loops. Ik ben soort van het definiëren van iets wat op zich niet alleen met dit wiskundige functie, maar ook in termen van deze pseudo-code. Deze pseudo-code is recursieve dat twee van de lijnen is in wezen het vertellen om te gaan Gebruik zelf een kleinere oplossen probleem van kleinere omvang, en vervolgens weer en weer, totdat we whittle het neer op deze zogenaamde basisscenario. 

Dus laten we eigenlijk trek een meer dwingende take-away van deze als volgt. Laat me gaan in gedit en neem een kijken naar een aantal van de huidige broncode, in het bijzonder dit voorbeeld hier. Sigma 0, die blijkbaar toevoegt de nummers een tot en met n. Dus laten we eens kijken wat er bekend en onbekende hier. Eerst hebben we een paar omvat, dus niets nieuws. Prototype. Ik ben een beetje vaag op dit na een paar dagen, maar wat hebben we zeggen een prototype van een functie is? PUBLIEK: [onverstaanbaar]. SPEAKER 1: Wat is dat? PUBLIEK: We kondigen het. SPEAKER 1: We kondigen het. Dus u geeft Clang, hey, dit eigenlijk niet de uitvoering nog, maar ergens in dit bestand, vermoedelijk, zal worden een functie genaamd wat? Sigma. En dit is slechts een belofte dat het gaat er als volgt uitzien. Het gaat om een ​​geheel getal te nemen als input-- en ik kan meer expliciet worden en zeggen: int n --en het is gaan naar een int terug te keren, maar puntkomma middelen, mm, ik zal rond te krijgen om de uitvoering van dit een beetje later. Nogmaals, Clang is dom. Het is alleen maar om te weten wat u vertellen boven naar beneden, dus we moeten in ieder geval geven het een hint van wat er komen gaat. 

Laten we nu eens kijken naar de belangrijkste hier. Laten scroll hier naar beneden en zien wat de belangrijkste aan het doen is. Het is niet zo lang van een functie, en in feite het construct hier bekend. Ik verklaar een variabele n, en dan Ik steeds weer lastig vallen van de gebruiker voor een positief geheel getal met behulp getInt, en enige uitgang uit deze lus zodra de gebruiker heeft voldaan. Do While, hebben we gebruikt om te pesten de gebruiker op die manier. Nu is dit interessant. Ik verklaar een int genaamd "antwoord." Ik wijs het de return waarde van een functie genaamd "sigma". Ik weet niet wat dat nog doet, maar Ik herinner me verklaren het even geleden. En dan ga ik langs bij de waarde die de gebruiker heeft ingevoerd in, n, en vervolgens verslag ik het antwoord. Nou laten we terugbladeren voor slechts een moment. Laten we verder gaan in deze map, maken sigma 0, en eigenlijk dit programma uit te voeren en zie wat er gebeurt. Dus als ik ga je gang en rennen dit programma ./sigma-0, en ik typ in een positieve integer als twee, Sigma, als het Griekse symbool aangeeft, is slechts naar alle nummers optellen nul tot twee. Dus 0 plus 1 plus 2. Dus dit moet hopelijk geef me 3. Dat is alles wat het doet. En op dezelfde manier, als ik weer lopen deze en ik geef het de nummer drie, dat is 3 plus 2, dus dat is 5, plus 1 moet mij geven 6. En dan als ik echt gek en Typ in grote aantallen, het zou mij groter en groter sommen. Dus dat is alles. 

Dus wat doet sigma eruit? Nou, het is vrij eenvoudig. Het is hoe we zouden kunnen hebben geïmplementeerd dit voor de afgelopen paar weken. "Int" gaat naar de return type zijn. Sigma is de naam, en het duurt een variabele m in plaats van n. Ik zal boven veranderen up. Dan is dit gewoon een sanity check. We zullen zien waarom in een moment. Nu verklaar ik een andere variabele, sum, initialiseren op nul. Dan heb ik deze For-lus iteratie, blijkbaar voor de duidelijkheid, van i = 1 op tot een = m, welke wat de gebruiker heeft ingevoerd in, en dan heb ik verhoog de som als deze. En dan terug de som. 

Dus een paar vragen. One, eis ik in mijn reactie dat dit vermijdt risico van een oneindige lus. Waarom zou passeren in een negatief getal veroorzaken, wat kan een oneindige lus? 

PUBLIEK: Je zult nooit m bereiken. 

SPEAKER 1: Reik nooit m. Maar m wordt doorgegeven in, dus laten we een eenvoudig voorbeeld beschouwen. Als m wordt gevoerd door de gebruiker als negatieve. Ongeacht het belangrijkste. Belangrijkste beschermt ons tegen dit ook, dus ik ben gewoon het zijn echt anale met sigma om er ook voor zorgen dat de input niet kan negatief zijn. Als m is negatief, iets als negatieve. Wat gaat er gebeuren? Nou, ik zal geïnitialiseerd om een, en vervolgens ik zal worden minder dan of gelijk aan m? 

Stand-by. Dat was-- laten we niet, laten we nix dit verhaal. Ik heb niet gevraagd die vraag, omdat het risico dat ik een verwijzing naar gaat niet gebeuren omdat i altijd zal groter zijn than-- OK, Ik intrekken die vraag. OK. Laten we ons alleen richten op dit deel hier. Waarom heb ik verklaren wat buiten de lus? Notice on line 49 Ik heb i verklaarde binnenkant van de lus, maar online 48 Ik heb verklaarde een aantal buiten. Yeah. PUBLIEK: [onverstaanbaar]. SPEAKER 1: Zeker. Dus in de eerste plaats doe ik zeker niet willen verklaren en initialiseren som nul binnen de lus op elke iteratie, omdat dit duidelijk zou de nederlaag van de doel van een opsomming van de nummers. Ik zou blijven veranderen de waarde weer op nul. En ook, wat is een andere, meer arcane reden voor hetzelfde ontwerp beslissing? Yeah. 

PUBLIEK: [onverstaanbaar]. SPEAKER 1: Precies. Ik wil het buiten toegang van de lus te op welke lijn? Op 53. En op basis van onze vuistregel van een paar colleges geleden, variabelen worden scoped, echt, om de accolades die ze omvatten. Dus als ik geen som binnenkant verklaren van deze uiterlijke accolades, Ik kan het niet gebruiken in lijn 53. Anders gezegd, als ik verklaard som in hier, of zelfs binnen de Lus, kon ik niet tot het in 53. De variabele zou effectief worden gegaan. Dus een paar redenen daar. Maar laten we nu eens terug te gaan en zie wat er gebeurt. Dus sigma wordt aangeroepen. Het voegt up 1 en 2, of 1 plus 2 plus 3, en dan geeft de waarde, slaat deze op in antwoord, en printf hier Daarom zie ik op het scherm. Dus dit is wat we een iteratief zullen noemen aanpak, waarbij iteratie net betekent het gebruik van een lus. Een For-lus, een While-lus, een Do Terwijl lus, net weer iets te doen en opnieuw en opnieuw. 

Maar sigma is een soort van een nette functie in dat ik kon het anders uit te voeren. Hoe zit het met deze, die gewoon wel cool zijn, laat me echt te ontdoen van veel afleiding omdat deze functie is eigenlijk heel simpel. Laten Whittle het neer net om de vier kern-lijnen en zich te ontdoen van alle commentaar en accolades. Dit is een soort van een mind-blowing alternatieve implementatie. Oke, misschien niet erg-blowing, maar het is een beetje sexier, oke, om te kijken naar deze zo veel beknopter. Met slechts vier regels code, Ik heb eerst dit sanity check. Als m kleiner is dan of gelijk aan nul, sigma heeft geen zin. Het is alleen de bedoeling om in dit geval voor positieve getallen, dus ik ga gewoon nul willekeurig terug zodat we in ieder geval hebben sommige zogenaamde basisscenario. 

Maar hier is het mooie. Het geheel van dit idee, het toevoegen van de getallen van 1 tot n, en m in casu kan worden gedaan door het soort van passeren van de bok. Nou, wat is de som van 1 tot en met m? Nou, weet je wat? Het is dezelfde als de som van m plus de som van 1 tot m minus 1. Nou weet je wat? Wat is sigma van m min 1? Nou, als je soort van deze te volgen logisch, het is hetzelfde als m minus 1 plus sigma van m minus 2. Dus je kan soort alleen-- dit is als, als je gewoon proberen om een ​​vriend te ergeren en ze je een vraag stellen, je soort antwoorden met een vraag, kun je soort te houden passeren van de bok. Maar wat is de belangrijkste is dat als je blijft waardoor de vraag kleiner en kleiner, je bent niet vragen wat is sigma n, wat is sigma van n, wat is sigma van n? Je vraagt ​​wat er sigma van n, wat is sigma van n minus 1, wat is sigma van n min 2? Uiteindelijk uw vraag wat gaat worden? Wat sigma van een of nul, een zeer kleine waarde, en zodra je krijgen dat je vriend, je bent niet van plan om te vragen dezelfde vraag weer, je bent gewoon gaat zeggen, oh het is nul. We zijn klaar met het spelen van dit soort domme cyclische spel. 

Dus recursie is de handeling in de programmering van een functie oproepen zelf. Dit programma worden opgesteld en beheerd, is gaat gedragen precies dezelfde manier maar wat is de belangrijkste is dat de binnenkant van een functie genaamd sigma, er is een regel code, waarin we onszelf noemen, die normaal zou zijn slecht. Bijvoorbeeld, wat als ik voor het eerst Dit samengesteld, dus zorg sigma-- maken sigma 1 ./sigma-1. Positief geheel getal, dan kunt u, 50 1275. Wat de functie lijkt zijn, op basis van een test, correct. Maar wat als ik een beetje gevaarlijk en de zogenaamde base case verwijderen, en gewoon zeggen, nou ik ben gewoon het maken van dit ingewikkelder dan het is. Laten we berekenen de sigma door middel m en vervolgens toevoegen in sigma m van minus een? Nou ja, wat gaat hier gebeuren? Laten we uitzoomen. Laten we opnieuw compileren van het programma, opslaan, opnieuw compileren van het programma, en dan klaar ./sigma-1 in te zoomen, voer positief geheel getal neem, 50. Hoeveel van jullie zijn bereid te bekennen om te zien dat? 

OK. Dus kan dit gebeuren voor een aantal redenen, en eerlijk gezegd deze week zijn we over om u meer van hen geven. Maar in dit geval, probeer dan achteruit redeneren wat zou hier zijn gebeurd? Segmentatie fout, we zei vorige Hiermee wordt bedoeld dat een segment van het geheugen. Iets ergs gebeurd. Maar wat was het mechanisch dat mis ging hier vanwege mijn verwijdering van die zogenaamde base case, waar ik terug een hard-coded waarde? Wat denk je dat er mis ging? Yeah. 

PUBLIEK: [onverstaanbaar]. SPEAKER 1: Ah. Goede vraag. Dus de omvang van het aantal dat ik een opsomming van werd zo groot dat het overtrof de grootte van het geheugen. Goed idee, maar niet fundamenteel gaan naar een crash veroorzaken. Dat zou integer overflow veroorzaken, waar de bits gewoon omdraaien en dan verwarren we een echt grote nummer voor als een negatief getal, maar die zelf niet leiden tot een crash. Want aan het eind van de dag een int is nog steeds 32 bits. Je gaat niet naar ongeluk stelen een 33 bit. Maar een goede gedachte. Yeah. 

PUBLIEK: [onverstaanbaar]. SPEAKER 1: De methode nooit stopt, en inderdaad hij zich opnieuw oproepen en opnieuw en opnieuw en opnieuw en weer, en geen van deze functies ooit afronden omdat hun enige lijn van code roept zichzelf opnieuw en opnieuw en weer. En wat is echt hier gebeurt, en nu zijn we kan soort trekken dit picturaal. Laat me gaan naar een foto voor slechts een moment. Dit is een beeld, dat zal uiteindelijk invulling in meer detail, van wat er gaande is binnenkant van het geheugen van uw computer. En het blijkt dat op de onderkant van deze foto is iets genaamd de stapel. Dit is een stuk van geheugen, een brok van RAM, dat is gewoon ieder moment gebruikt een functie wordt aangeroepen. Elke keer dat je een programmeur, noemen een functie, het besturingssysteem, zoals Mac OS, Windows of Linux, grijpt een stelletje bytes, misschien een paar kilobytes, misschien enkele megabytes van het geheugen, geeft ze aan u, en dan laat u uw functie uitgevoerd met behulp van wat variabelen die je nodig hebt. En als je dan nog bellen functie en andere functie, u een ander stukje van het geheugen krijgen en een segment van het geheugen. 

En inderdaad, indien deze groene trays uit Annenberg representeren dat het geheugen, hier is wat er gebeurt de eerste keer dat je belt functie sigma. Het is als het zetten van een bak als deze op wat in eerste instantie een lege stack. Maar dan, als die lade noemt zich, om zo te zeggen, bellen naar een andere instantie Sigma, dat als het vragen van het besturingssysteem, ooh, hebben behoefte aan een beetje meer geheugen, Geef me dat. En dan wordt het opgestapeld op bovenop. Maar wat is de belangrijkste hier is dat de eerste lade is er nog steeds, omdat hij aangeroepen deze tweede lade. Nu ondertussen sigma bel sigma, dat is hetzelfde als vragen voor meer geheugen. Wordt opgestapeld op hier. sigma sigma noemen, dat is een ander lade die hier wordt opgestapeld op. En als je blijft dit doen, uiteindelijk, soort kaart deze visuele om die kaart, wat er gaat gebeuren met de stapel bakken? Het gaat om het bedrag niet te boven van het geheugen van uw computer. En zodra deze groene bak boven de horizontale lijn boven stack en vooral dat woord hoop, waar we op terug zal komen in de toekomst, dat is een slechte zaak. De hoop is een ander segment van het geheugen, en als je deze laat trays stapel en stapel op, je gaat overtreffen zelf segment van het geheugen, en een programma wordt inderdaad gaat crashen. 

Nu nog even terzijde, dit idee recursie derhalve Duidelijk leiden tot problemen, maar het is niet noodzakelijk een slechte zaak. Omdat overwegen, na alle, how-- en misschien Dit is wel even wennen om --hoe elegant of hoe eenvoudig dat de uitvoering van sigma was. En we gaan niet te gebruiken recursie al te veel in CS50, maar in CS51, en echt elke klasse waar je data structuren te manipuleren zoals bomen, of stambomen, dat wat hiërarchie het is super, super handig. Nu, als een terzijde, zodat u als aspirant-informatici vertrouwd zijn met een aantal van Google's inside jokes, als je naar Google en je kijkt wat er de definitie van, zeg, recursie, in te voeren. Uh-huh. Even terzijde, ik trok een paar. Dit was net 10 minuten van uitstelgedrag vanmorgen. Als u ook Google "scheef", bericht door het kantelen van je hoofd slightly-- en dan deze is misschien wel afschuwelijkste van alle omdat iemand doorgebracht als hun dag de uitvoering van dit enkele jaren ago-- branden. Oh, wait-- dat is een bug. 

Dus lopen op een van de grootste websites ter wereld zijn die stomme kleine paaseieren. Ze consumeren waarschijnlijk triviale aantal regels code gewoon zo dat we kunnen hebben kleine leuke dingen als dat. Maar in ieder geval nu je krijgt sommige van die inside jokes. 

Laten we nu eens een kijkje nemen op een aantal van de White Lies we al te vertellen van een te late, en beginnen afpellen sommige lagen technisch zodat je echt begrijpt wat is er aan de hand en je kunt begrijpen een aantal van de bedreigingen, zoals Shellshock, dat zijn nu begonnen te worden op de voorgrond van ieders aandacht, althans in de media. Dus hier is een erg eenvoudige functie die terugkeert niets, leegte. Zijn naam is swap. Het duurt in twee variabelen en het geeft niets. Neemt in a en b. Dus een korte demo. We brachten deze up. We kunnen net zo goed een beetje breek hier maar voor een moment en hebben een beetje iets te drinken. Als iemand het niet erg mee me hier voor slechts een moment. Hoe zit je in de kastanjebruin shirt? Kom maar naar boven. Gewoon de een vandaag. Dank je wel, dat wel. Oke, en we hebben komen die hier? Wat is je naam? 

SPEAKER 4: Laura. 

SPEAKER 1: Laura. Kom maar naar boven. Dus Laura, zeer eenvoudige uitdaging vandaag. Leuk om yo te ontmoeten. Oke. Dus we hebben wat melk hier en we hebben een aantal sinaasappelsap hier en een aantal koppen dat we geleend van Annenberg vandaag. 

SPEAKER 4: Borrowed. SPEAKER 1: En gaan om verder te gaan en geven u een half glas van dit. Oke. En wij sturen u de helft geven een glas van de melk. Oh, en het gewoon zo dat je kunt herinneren wat dit was, Ik herinnerde me te brengen dit op en op vandaag. Oke. Als je het niet erg, laten we eens kijken, we kunt ze over je eigen bril als je wilt. Dit zal de wereld vanuit de ogen van Laura zijn. Oke. Dus je doel, gegeven twee kopjes vloeibare hier, melk en jus d'orange, is wisselen de twee inhoud, zodat de sinaasappelsap gaat in de melk cup en de melk gaat in het sinaasappelsap cup. 

SPEAKER 4: Krijg ik nog een kopje? SPEAKER 1: Ik ben zo blij dat je vroeg, dat wel het zou veel beter materiaal zijn geweest als je het niet had gevraagd. Maar ja, we kunnen u een derde te bieden kopje dat is natuurlijk leeg. Oke. Zo wisselen de inhoud daar. Erg leuk. Zeer goed. Je doet dit opvallend voorzichtig. En stap drie. Oke. Excellent. Een groot applaus zou goed zijn voor Laura zijn. Oke. We hebben een klein afscheidscadeau voor u, maar laat ik deze nemen. Dank je wel. Dus een simpel voorbeeld, maar, om aan te tonen dat als je dat doet willen de inhoud te wisselen van twee containers, of laten we noemen hen variabelen, u een aantal tijdelijke opslag nodig een van de inhoud fase in zo dat je eigenlijk kan doen de swap. Dus inderdaad, deze bron code hier in C representatief is precies dat. Als het sinaasappelsap was een en de melk was b, en we wilden wisselen van de twee, je zou iets creatiefs te proberen door gieten in elkaar, maar dat zou waarschijnlijk niet end bijzonder goed. En dus hebben we een derde beker, call gebruiken het tmp, T-M-P volgens afspraak, en doe de inhoud van het PB in dat, dan is ruilen een kopje, zet dan de PB in de originele beker, waardoor bereiken, precies zoals Laura deed, de swap. 

Dus laten we het doen precies dat. Laat me gaan en openen van een voorbeeld dat eigenlijk heet "geen wisselen, "want dit is niet zo eenvoudig gedaan als je zou denken. Dus in dit programma, merken dat Ik gebruik stdio.h, onze oude vriend. Ik heb het prototype voor swap daarboven, die betekent dat de uitvoering van waarschijnlijk beneden, en laten we zien wat deze belangrijkste programma gaat doen voor mij. Ik voor het eerst verklaar int x krijgt een, en int y krijgt twee. Dus denk aan die als PB en melk, respectievelijk. En dan heb ik gewoon een printf zeggen x is dit en y is dit, zodat ik kan visueel te zien wat er gaande is. Dan heb ik printf claimen dat ik het omwisselen van de twee, en vervolgens afdrukken ik uit een beweren dat ze verwisseld, en print ik x en y weer. Dus hier in swap is precies wat Laura deed, en precies wat we zagen op het scherm een ​​moment geleden. 

Dus laten we verder gaan en erg teleurgesteld. Maak geen swap, en lopen geen swap, inzoomen op de output hier. Voer x is 1, y 2, swapping verwisseld. x is nog 1 en y is momenteel nog 2. Dus hoewel, eerlijk gezegd, dit ziet er precies willen, zij het meer technisch, wat Laura deed, leek niet te werken. Dus waarom is dat? Nou, het blijkt dat wanneer we schrijven een programma als dit dat is zowel de belangrijkste, benadrukt hier, en dan een andere functie, zoals swap, hier uitgelicht, die roept hij, de wereld ziet er een beetje iets als deze laden een moment geleden. Als belangrijkste eerste wordt genoemd, dat is hetzelfde als vragen besturingssysteem voor een beetje van het geheugen voor elke lokale variabelen zoals x en y die de belangrijkste is, en ze eindigen daar. Maar als belangrijkste gesprekken wisselen, en de belangrijkste gaat om twee argumenten, a en b wisselen, jus d'orange en melk, het is niet alsof het overhandigen van het sinaasappelsap en de melk Laura. Wat een computer doet, is het passeert exemplaren van het jus d'orange en kopieën van de melk aan Laura, zodat wat is uiteindelijk de binnenkant van deze lade is de waarde een en twee, of PB en melk, maar kopieën daarvan, zodat op dit punt in het verhaal, is er is PB en melk in elk van deze schalen. Er is een een en een twee in elk van deze trays, en de swap-functie is inderdaad werkt. Het is binnenin ruilt ze van de tweede bovenste lade, maar dat swapping heeft geen invloed. En op basis van slechts enkele basisprincipe we hebben gesproken over vroeger, en inderdaad slechts een paar minuten geleden, wat zou kunnen verklaren waarom het veranderen a en b binnenkant van swap heeft geen effect op x en y, hoewel Ik passeerde x en y om de swap-functie. Wat is hier het sleutelwoord dat misschien simplistisch uit te leggen? Ik denk dat ik hoorde het hier? PUBLIEK: Return. SPEAKER 1: Return? Niet meer terug. Laten we gaan met een andere. Wat is dat? 

PUBLIEK: [onverstaanbaar]. 

SPEAKER 1: OK, dus return-- we konden maken rendement werk in het verhaal, maar er is een nog eenvoudiger verklaring. PUBLIEK: Scope. SPEAKER 1: Scope. Ik zal strekking te nemen. Dus scope, herinneren waar onze x en y aangegeven. Ze zijn binnen verklaard van de belangrijkste hier naar boven. a en b, ondertussen zijn effectief verklaard binnenkant van de swap, niet helemaal in de accolades maar nog steeds in de algemene ruimte van de swap. En inderdaad, a en b bestaan ​​alleen op deze lade van Annenberg, deze tweede stuk code. Dus we inderdaad het veranderen van de kopie, maar dat is helemaal niet zo behulpzaam. 

Dus laten we eens een kijkje nemen op deze iets lager niveau. Ik ga om terug te gaan naar de Source Directory, en ik ga eerst opnieuw in hier, en net om te bevestigen dat ik in deze groter terminal venster, het programma is nog steeds gedragen als dat. Stel nu dat deze is geen opzet. Het is duidelijk dat ik wilde swap aan werk, dus het voelt als een bug. Nu kon ik beginnen met het toevoegen van een Veel printf om mijn code, printen x hier, y dan hier, een meer dan hier, b dan hier. Maar eerlijk gezegd, dat is waarschijnlijk wat je hebt gedaan voor een paar weken nu, in het kantoor uren en thuis bij het werken Op psets proberen om wat bugs te vinden. Maar je zult zien, als je dat nog niet hebt, dat probleem set drie introduceert u een commando genaamd GDB, waar GDB, GNU debugger, heeft zelf een hele hoop functies die daadwerkelijk kan laat ons situaties begrijpen als dit, maar meer meeslepend, problemen op te lossen en vinden van bugs. Dus ik ga dit doen. In plaats van ./noswap, ik ben in plaats gaat GDB ./noswap lopen. Met andere woorden, ik ga lopen mijn programma niet in Bash, onze nieuwe vriend vandaag. Ik ga lopen mijn programma noswap binnenkant van deze andere programma genaamd GDB, een debugger die is een programma dat is ontworpen om te helpen Jullie mensen te vinden en te verwijderen bugs. Dus als ik hit Run hier, er is een gruwelijke hoeveelheid tekst dat je echt nooit meer te lezen. Het is in wezen een afleiding vanaf de prompt, waar Ik ga naar Control-L hit om op te staan ​​aan de top daar. Dit is de GDB prompt. Als ik wil dit programma draaien nu, als deze kleine spiekbriefje op vandaag slide suggereert, Run is de eerste beveelt dat we bedoeld om te introduceren. En ik ga gewoon om te typen aanloop hier binnenkant van GDB, en inderdaad het liep mijn programma. Nu is er een aantal extra uitgangen van het scherm als dit, maar dat is GDB gewoon anale en vertel ons wat er aan de hand. Je hoeft niet echt zorgen te maken over deze gegevens op dit moment. Maar wat is echt cool over GDB, als ik dit again-- Controle-L wist de screen-- laat me gaan gang en het type "break belangrijkste," aldus, als ik druk op Enter, het instellen van wat is riep een breekpunt bij noswap.c, lijn 16, waar GDB bedacht mijn programma eigenlijk is, mijn functie eigenlijk is. Dit zullen we negeren voor nu maar dat is het adres in geheugen dat speciaal van deze functie. Dus als ik nu typ Uitvoeren, merken wat is cool hier. Mijn programma breekt op de lijn I vertelde GDB om uitvoering te pauzeren bij. Dus ik hoef niet te veranderen nu mijn code, voeg wat printf's, opnieuw compileren, herhaling het, veranderen, voeg wat printf's, opslaan, opnieuw compileren, voer het uit. Ik kan gewoon lopen via mijn programma stap voor stap voor stap menselijke snelheid, niet op Intel-inside soort snelheid. 

Dus nu zien deze lijn verschijnt hier, en als ik terug te gaan om mijn programma in gedit, merken dat dat eigenlijk de eerste regel van de code. Er is lijn 16 in gedit. Er is lijn 16 binnen GDB, en zelfs hoewel dit zwart-wit-interface is lang niet zo gebruiksvriendelijk vriendelijke, betekent dit dat leiding 16 niet werd uitgevoerd nog niet, maar het is over te zijn. Dus inderdaad, als ik het type afdruk x, niet printf, alleen printen x, Ik krijg een aantal nep waarde er van nul, omdat x is nog niet geïnitialiseerd. Dus ik ga volgende te typen, of, als u wenst te worden fancy, gewoon n voor de volgende. Maar toen ik het type naast gaan, nu merkt het op gaat om lijn 17. Dus logisch, als ik heb uitgevoerd lijn 16 en ik nu typ druk x, wat moet ik zien? Een. 

En nu is dit weliswaar verwarrend. $ 2 is gewoon een mooie manier om, als je later wilt verwijzen naar die waarde, je kunt zeggen "dollarteken twee." Het is als een terugverwijzing. Maar voor nu, gewoon negeren. Wat interessant is, is wat er aan de rechterkant van het gelijkteken. En nu als ik volgende weer typen en af ​​te drukken y, moet ik zie 2. Ik kan nu ook afdrukken x weer, en eerlijk gezegd, als ik word een beetje in de war over waar ik ben, kan ik de lijst voor de lijst typt en gewoon zien wat context rond het punt dat ik ben eigenlijk op. En nu ik kan typen next, en er is x 1. Typ nu ik volgende. Oh, y 2. En nogmaals, het is verwarrend, omdat de uitgang GDB's wordt vermengd met mijn eigen vermogen. Maar als je in het achterhoofd te houden, door blik heen en weer op uw code of buiten het leggen het kant elkaar misschien, zult u zie dat echt ik ben gewoon het doorlopen van mijn programma. 

Maar let op wat er daarna gebeurt, letterlijk. Hier is lijn 22. Laat me gaan er overheen, waardoor bewegen op tot 23, en als ik afdrukken x nu, nog een. En als ik afdrukken y nu, nog een. Dit is geen nuttige oefening. Dus laten we dit opnieuw te doen. Laat me terug te gaan naar de top en het type run weer. En het is te zeggen dat de programma dat is waarin fouten worden opgespoord is al begonnen, gestart vanaf het begin. Ja, laten we dit opnieuw doen. En deze keer laten we het nu doen, next, next, next, next, maar nu dingen interessant. Nu wil ik de stap naar swap, dus ik typ niet naast. Ik typ stap, en nu merken heeft mij sprong naar noswap.c lijn 33. Als ik terug naar gedit, wat is lijn 33? Dat is de eerste werkelijke regel code binnenkant van swap. Dat is leuk, want nu kan ik soort rondneuzen en nieuwsgierig over wat er gaande is echt daar. Laat me printen tmp. Whoa. Waarom heeft tmp hebben een aantal gek, nep garbage waarde? Publiek: Het is niet geïnitialiseerd. SPEAKER 1: Het is niet geïnitialiseerd. En inderdaad, als je een programma uit te voeren, je krijgt een hele hoop geheugen door het besturingssysteem, maar u hebben geen waarden geïnitialiseerd, dus wat stukjes je bent hier te zien, ook al is het deze gekke grote negatieve nummer, betekent alleen dat dat zijn de overblijfselen van aantal eerdere gebruik van die RAM, ook al heb ik niet mezelf nog nodig had. Dus nu ga ik verder en het type te gaan naast, en als ik nu typ druk tmp wat moet ik zien? Ongeacht de waarde van een was, a is het eerste argument, net als x is de eerste ding wordt doorgegeven in, zodat een en x moet hetzelfde zijn, dus afdrukken tmp moet me nog een af ​​te drukken. 

Dus wat zie je in probleem set drie is een tutorial van soorten op GDB, maar beseffen dat dit het begin is van een blik op een instrument dat daadwerkelijk zal u te helpen problemen op te lossen dus veel effectiever. Wat we uiteindelijk gaan doen op woensdag is beginnen te schillen terug een paar lagen en verwijder enkele zijwieltjes. Dat ding heet string die we hebben gebruikt voor enige tijd, we gaan langzaam dat weg te nemen van u en beginnen te praten over iets meer esoterisch bekend als char *, maar we gaan deze mooie doen en eerst zachtjes terwijl pointers, als ze worden opgeroepen, kunnen sommige doen zeer slechte dingen als misbruikt, door te kijken naar een beetje claymation uit onze vriend Nick Parlante van Stanford Universiteit, een professor in de computer wetenschap die samen dit voorbeeld zetten van wat er deze woensdag komen. 

[VIDEO AFSPELEN] He, Binky. Wakker worden. Het is tijd voor pointer plezier. 

Wat is dat? Meer informatie over pointers? Oh, goody! [END VIDEO AFSPELEN] SPEAKER 1: Dat wacht u op woensdag. We zullen je dan zien. [VIDEO AFSPELEN] -En Nu, Deep Thoughts, door Daven Farnham. 

Waarom leren we C? Waarom niet A +? 

[Lachen] 

[END VIDEO AFSPELEN]