[MUSIK SPELA] 

SPEAKER 1: Okej, det här är CS50, och detta är början på vecka fyra, och som ni kanske har hört eller läsa, har världen slutar. Att gå runt på internet har varit kunskap och medvetenhet av ett fel i ett program, en programmeringsspråk som heter Bash. Detta har underbart branded som Shellshock, eller Bash dörren, men artiklar som dessa har inte varit ovanligt. Och faktum är att många av dem kommer med tillbaka minnen av Heartbleed, som ni kanske har märkt i Tryck tillbaka i våras, vilket var likaså tämligen dramatisk. Nu för de av er här idag, hur många av er har, även om du inte förstår vad det handlar om, hört talas om Shellshock? Okej, och hur många av er har datorer som är utsatta? OK, bör det finnas långt, långt fler händer upp just nu, av skäl som vi skall se. 

Låt oss ta en titt på vad som finns pågått i media och sedan förklara det lite för oss här tekniskt. 

TALARE 2: Säkerhetsexperter har varnade för att ett allvarligt fel kunde handla om att påverka hundratals miljoner av världens webbanvändare. Så vad exakt är det bugg som har varit dubbade Shellshock, och vad gör det? Nå, Shock är också känd som den Bash bugg, programvaran det utnyttjar. Hackare använder viruset för att skanna sårbara system som kör Linux och Unix operativsystem och sedan infektera dem. Bash är en kommandorad skal. Detta låter användare fråga kommandon för att starta program och funktioner i programvaran genom att skriva in text. Det är oftast används av programmerare, och bör inte vara öppna mot omvärlden, även om Shellshock ändrar det. 

Tja, worringly, vissa analytiker varna det kan vara ett större hot, eftersom Shellshock tillåter fullständig kontroll över en infekterad maskin, medan Heartbleed endast tillåtet hackare att spionera på datorer. Det är så allvarligt, det är betyg en 10 av 10 för svårighetsgrad av National Sårbarhet Database. 2/3 av alla webbservrar är på risk, inklusive vissa Mac-datorer. Tja, se till att du patch ditt system nu. Den som en webbplats igång de drabbade operativsystem bör vidta åtgärder så snart som möjligt. Den som har råd med det ska se deras övervakning och webbapplikation brandväggar för att hålla utkik efter eventuella attacker. TALARE 3: Värsta som kan hända är att någon skulle skriva kod som automatiskt skulle gå och scanna Internet och skulle påverka alla dessa datorer. Och när de gör det, ja, det värsta de kunde göra är bara att ta bort allt, eller stänga platserna ned. Så vi kunde se skador från denna synpunkt, där vi skulle ha skadliga människor som bara bestämmer sig för att orsaka förödelse genom att bringa system ned eller ta bort filer och sånt. TALARE 2: En del säger att detta är en av de svåraste att mäta buggar i år, och det kan ta veckor eller till och med månader för att bestämma dess slutliga effekten. 

SPEAKER 1: Så allt detta är sant, men det roliga är, nästan alla av bildspråk som du just såg, utom kanske tangentbordet, har ingenting att göra med felet som helst. Servrar och ledningar och så vidare, Det blir liksom tangentiellt relaterade, men kärnan är det faktiskt ganska bekant vad som händer här. Faktum är, låt mig gå in i vår CS50 apparaten. Låt mig gå vidare och maximera terminalfönstret här. Och ni har använt detta, eller den inbäddade versionen i detta, i gedit för att skriva program, skriva in kommandon och så vidare, och detta är faktiskt, och har varit i veckor, Bash, B-A-S-H. Detta är Bourne-again shell, som är bara ett finare sätt att säga, Detta är ett program som har en blinkande prompt, effektivt, som sitter där och väntar för inmatning för dig. Och det är kommandot line interface via vilket ni har varit igång kommandon och slutligen sammanställa och sedan köra program. 

Men våldsamt slag är också en programmerings språk i följande mening. Du vet att det finns kommandon som cd och ls samt klang och andra, men du kan definiera dina egna kommandon genom att implementera dem i Bash. Nu ska vi inte gå till gå in i detalj att Bash programmeringsspråket, men vet till exempel att det för närvarande, det finns inget kommando som heter "Hej." Så det kan hittas i ett av dessa paket. Det är inte installerat på datorn. Fråga administratören. Men om jag vill att det ska finnas ett program kallade "hello" i Bash eller på mitt prompten Jag kan faktiskt använda syntax som är riktigt gillar C. Det är inte riktigt samma sak, men det ser ganska lik en funktion, om än saknas vissa detaljer. Ingenting verkar hända, men nu om jag skriver "Hej," du kan faktiskt skriva ett program, inte i C, inte på Java, inte i en annan programmering språket, men i Bash självt. 

Nu nyckeln här är att jag skrev name Jag ville ge denna nya kommando, och parentes är också en symbol för detta är en funktion. Inom parentes kan man också göra roliga saker, och faktiskt även på Mac OS, detta är ett program som heter Terminal. Den levereras inbyggd i någons dator som har en Mac i det här rummet, och du kan göra liknande saker i Mac OS, men du kan gå mer än så. Och det är lite tangentiell, men det är ganska kul. Jag blev påmind i morse, när man tänker igenom detta, ett litet spel jag brukade spela med en av CS50 forna TF varvid varje gång han skulle gå bort från hans tangentbord med sin skärm olåst, Jag skulle köra ett kommando som här-- "säga hej." Och nu varje gång han kom tillbaka till sin tangentbord efter att jag rensat skärmen och han skulle sitta ner, försöka göra en del arbete, visa innehållet i sin directory-- 

[AUDIO SPELA] 

-Hello. Hej. 

SPEAKER 1: Så, i rättvisans namn, Det var faktiskt inte "Hej." Det var oftast något mer besläktad med att-- [AUDIO SPELA] -Beep. SPEAKER 1: --that jag would-- så hans dator skulle svära på honom varje gång han faktiskt satte sig vid sitt tangentbord. Och mycket snabbt han räknat ut att inte lämna sin skärm olåst. Men detta antyder sorteringen dum kul att du kan ha med något liknande Bash. Men det är lite mer allvarligt, för att vara säker, än så. Och i själva verket är detta ett av de mest farliga och långvariga fel det har verkligen drabbat världen globalt. Detta fel har funnits för cirka 20 år, och du kommer att slås på bara stund av sin relativa enkelhet. 

Så detta är en representativ befaller att om du äger en Mac, bokstavligen just nu när du har din locket öppet, kan du prova att skriva in i det program som heter Terminal. Terminal är under Tillämpningar Utilities-- för en gångs skull, inte Windows-användare inte behöver oroa denna threat-- men de av er med Mac kan skriva detta i ett fönster som jag ska göra här, och om du skriver som i det här programmet heter Terminal, som jag gör nu, Om du ser ordet "sårbar", datorn är sårbara för exploatering. 

Nu vad innebär det egentligen? Och det är visserligen några ganska galet syntax, men låt oss åtminstone dra ut några av de intressanta aspekterna. Så det finns en viss syntax som ser lite bekant, åtminstone från C och programmering i allmänhet. Jag ser några parenteser, semikolon, klamrar och sådant, men det visar sig att detta dum sak här i gult är i huvudsak en funktion det gör ingenting. De kolon medel göra ingenting, och semikolon betyder sluta göra någonting. Så insidan av dessa klamrar, det faktum att jag har en lika logga till vänster, detta är i huvudsak att skapa ett kommando, eller en variabel, kallas x, och tilldela det den gula bit kod där. Det kan vara något i stil med "eko Hej "eller" säger pip "eller något besläktad med det. Men märker om dina ögon vandra längre till höger, det finns mer till denna linje än precis i slutet av den semikolon. "Echo sårbar" och sedan utöver att det finns ännu mer. En annan semikolon, våldsamt slag -c :. 

Så lång historia kort, här kodraden är tillräcklig för tvingande en dator som är sårbara för att göra något som du vill att den ska göra, eftersom det finns en bugg i Bash vari även om Bash var tänkt att sluta läser rader av kommandorätt där efter den gula texten, för en 20-plus år gamla bugg, Bash har faktiskt varit läsning utöver detta semikolon och ganska mycket gör vad den blir tillsagd. 

Så vad är innebörden av att i slutändan? Jag sa bara "echo hello" eller "echo sårbara" men vad händer om du gjorde något faktiskt skadligt, liksom rm -rf *, som du kanske inte någonsin skrivit förut, och ärligt talat du förmodligen bör inte för tidigt, eftersom du kan göra en raddaskada med den. Varför? rm gör vad, förstås? Avlägsnar. * Betyder vad? Alla. Så det är en så kallad joker, så innebär det ta bort allt i den aktuella katalogen. -r råkar betyda rekursivt, vilket innebär att om det du tar bort är en katalog, och insidan av det är andra filer och andra kataloger, rekursivt dyka in där och ta bort allt detta. Och f är den värsta av dem alla. Någon som vet vad -f betyder här? Force. Så tvinga sätt, till och med om detta är en dålig idé, göra det utan att fråga mig för ytterligare bekräftelse. Så, ni vet, skrattar vi på detta, men ärligt talat, jag förmodligen skriver detta flera gånger en dag, eftersom verkligheten är det är det snabbaste sättet att bort en hel massa grejer. Men även jag har gjort en del skada. 

Men om du skulle lura en dator till att definiera några dumma variabel eller funktion som kallas x, men sedan lura datorn i verkställande utanför gränserna för det funktion, utöver detta semikolon, du kan verkligen lura en dator till verkställande något liknande rm -rf eller E-post kommandot eller kommandot Kopiera. Allt bokstavligen kan du göra med dator, oavsett om det är att ta bort filer, skapa filer, spam någon, attackera någon server på distans, om du kan uttrycka det med ett kommando, du kan lura en dator till att göra det. 

Nu vad är ett exempel på hur du kan göra detta? Tja, det finns en hel del datorer på internet kör Bash. Alla av oss Mac-användare är bland dem. Många Linux-servrar är bland dem också, och Unix-servrar. Windows igen blir relativt undan om du inte har installerat särskild programvara. Nu har en hel del servrar, för Exempelvis köra webbservrar, och i själva verket Linux är kanske den mest populära operativsystem att köras på datorer på internet som betjänar upp webbsidor. Nu när vi får se senare i terminen, då du skickar en begäran från din browser-- Chrome, Internet Explorer, whatever-- till en fjärrserver, det visar sig att även om du just skrev www.example.com, din webbläsare sänder ett meddelande det är lite mer svårbegripliga, som den här. 

Men märker lite något konstigt. De två första raderna Jag har aldrig sett förut, men de ser inte särskilt hotfullt. Men lägg märke till vad jag har stulit för tredje raden här. Om ett dåligt killen var att skicka ett meddelande så här från sin dator till en sårbar Mac eller sårbara Linux-server, det roliga är att Bash, det enkelt litet kommandotolk är allestädes närvarande och ofta vana vid att i huvudsak genomföra innehållet i en budskap som den tar emot. Och med den logiken kan du lura en webbserver därför genom att skicka något som User-Agent, som vanligtvis är tänkt att säga namn i din webbläsare. User-Agent Chrome, User-Agent Internet Explorer, User-Agent Firefox, detta är bara webbläsarens sätt att identifiera sig. Men om en dålig kille mycket skickligt säger, mm-mm, jag är inte kommer att berätta vad min webbläsare är, Jag stället kommer att skicka dig här kryptiskt utseende sak med rm -rf * I det, kan du bokstavligen lura en sårbar webbserver på Internet till verkställande just det i där för att ta bort alla filer. Och ärligt talat, det är inte även de värsta. Du kan göra vad som helst. Du kan starta en distribuerad överbelastningsattack om du skickade detta meddelande till Hela knippen av webbservrar och sedan hade dem alla ner, för exempel på Harvard.edu servrar, och du kan sortera på bang heck av dem av en nätverkstrafik som var annars utlöses av denna skurk. 

Så lång historia kort, nästan alla i det här rummet som äger en Mac är utsatta för detta. Den guldkant är att om du inte är kör en webbserver på din bärbara dator, och om du inte har faktiskt konfigurerat det att låta något i stil med SSH in i det, du är faktiskt säker. Det är sårbart, men det finns ingen man försöker komma in i din bärbara dator, så du kan sorts vara säker. Men Apple kommer snart att uppdatera en fix för detta. I världen av Linux har redan släppt ett antal korrigeringar för Fedora och Ubuntu och andra versioner av Linux, och faktiskt om du kör uppdateringen 50 i apparaten, även det kommer också att vara uppdateras och korrigeras. Men även detta har inte verkligen varit utsatta, för om du har mixtrar med apparaten och gjort din bärbara dator för allmänheten tillgängliga på Internet, vilket inte är som standard, du har faktiskt varit bra eftersom av brandvägg och andra tekniker. 

Men det är ett extremt exempel på en bugg som vi har bott för bokstavligen 20 år, och vem vet om någon hela denna tid har vetat om det? Och i själva verket är detta en av de grundläggande utmaningarna att vi får se senare i termin om säkerhet, är att precis som i den verkliga världen, de goda är på underläge. För att hålla skurkarna ut, vi måste se till att varje dörr är låst, att alla fönster är säker, att varje punkt träder i ett hem är säkert att hålla skurkarna ut. Men vad gör den onde måste göra för att faktiskt äventyra ditt hem och stjäla från dig? Han eller hon har bara att hitta en olåst dörr, en krossat fönster, eller något i denna riktning, och det är den Samma sak i datasäkerhet. Vi kan skriva miljontals rader programkod och spendera hundratals eller tusentals timmar att försöka få det rätt, men om du gör bara en fel i korrekthet, du kan sätta hela systemet och faktiskt i detta fall hela internet och världen i fara. 

Så om du vill veta mer om detta, gå till denna URL här. Det finns inget behov av åtgärder ikväll om du inte är bland dem bekvämare att har varit igång en egen web server, i vilket fall du bör, faktiskt, uppdatera programvaran. 

Och även detta är titeln på ett tal, och nu ett papper, att vi har länkat på kursens hemsida i dag. Det var av en kollega vid namn Ken Thompson, som var att acceptera en mycket berömd utmärkelse i datavetenskap, och han gav detta tal några år sedan, huvudsakligen på samma ämne. Begärt folks frågan, bör du verkligen förtroende, slutligen, program du har fått? Till exempel har vi alla skrivit program, och vi har sammanställt dem med klang. Och för din kunskap, du har skrivit något program för CS50 där det finns en bakdörr av slag, finns det en väg att en dålig kille, om att köra ditt program, kan ta över din dator? Antagligen inte, eller hur? Mario och Greedy och kredit. Dessa är alla ganska små program. Du skulle behöva vara ganska dåligt om du verkligen gjorde hela datorn sårbar efter att ha skrivit 10 eller 20 rader kod, eller åtminstone omedvetna om några av de konsekvenser för säkerheten. Nu säger jag det skämt, men vi kommer att se i dag och den här veckan är det faktiskt riktigt, riktigt enkelt att vara dåligt och göra ännu korta program sårbara. 

Men för nu, åtminstone, inser att frågan ställs här är ca klang i en kompilator. Varför har vi litar Clang under de senaste två eller tre veckor? Vem säger att den som skrev Clang hade inte en "om" tillståndet i det som i huvudsak injicerade några nollor och ettor i varje program är samman som skulle låta honom eller henne åtkomst datorn när du sover och din bärbara dator locket är öppet och datorn är igång? Rätt? Vi har denna typ av ära system rätten Nu när vi litar på att Clang är legit. Du litar på att produkten är legit. Du litar på att bokstavligen varje program på din Mac eller PC är pålitlig. Och eftersom denna enkla bugg antyder, även om det inte är skadligt, det är absolut inte sannolikt att vara fallet. 

Så du bör vara rädd som fan. Ärligt talat, det finns ingen enkel lösning på detta andra än ett slags samhällelig medvetenhet av den ökande komplexiteten att vi bygger på toppen i våra datasystem, och hur allt mer sårbara Vi kan mycket väl vara. 

Nu med det sagt, Breakout. Så Breakout är problemet set tre, och Breakout är ett spel från förr att du kanske kommer ihåg, men för oss i problem set tre, Det ger oss möjlighet att ta saker backa upp ett pinnhål så att när vi skriver program, även i ett terminalfönster som denna, vi faktiskt kan köras, i slutändan, grafiska program inte till skillnad från dem som vi hade tillgång till i Scratch. Så detta är personalens genomförande av breakout, vilket är just detta tegel-breaking spel, att du flyttar paddeln tillbaka och tillbaka, och du träffar bollen mot de färgade tegelstenar upp överst. Så det här är att föra oss slags tillbaka till där vi kunde vara mycket snabbt Scratch, och nu med C, genomföra våra egna grafiska användargränssnitt. 

Men mer än så, det här Problemet set är det första där vi ger du en massa kod. Och faktiskt, jag tar explicit uppmärksamhet åt detta, eftersom framför allt för de mindre bekväm, detta problembild, åtminstone vid första anblicken, kommer att känna sig som Vi har tagit upp ett hack. Eftersom vi har gett dig, för en del av sökandet och sorteringsproblem i pset, ett gäng kod som vi skrev, och ett par kommentarer som säger "att göra" där du måste fylla i tomrummen. Så inte alltför skrämmande, men det är första gången vi lämna du kod som du behöver först läsa, förstå och sedan lägga till och slutföra det. 

Och sedan med Breakout, vi kommer att göra samma sak, vilket ger dig ett tiotal fler linjer kod som, ärligt talat, ger dig en hel del av ramverket för spelet men sluta kort genomföra blocken och bollen och paddel, men vi genomför en del andra funktioner. Och även att det vid första anblicken, återigen, särskilt om mindre bekväm, kan tyckas särskilt skrämmande och du att det finns så många nya funktioner du behöver för att linda ditt sinne runt, och det är sant. Men kom ihåg, det är riktigt gillar Scratch. Oddsen är att du inte använder alla pusselbitarna i Scratch. Oddsen är att du inte bryr dig att linda ditt sinne runt dem alla eftersom alla tog det var en snabb blick för att förstå, åh, det är vad jag kan göra med den pusselbit. Och faktiskt, i problembild 3 spec, vi peka dig på den dokumentation som kommer presentera ett antal nya funktioner, och slutligen programmeringen konstruerar du använder. Villkor, loopar, variabler och funktioner kommer att ha samma vad vi har sett hittills. 

Så ja, vad vi ska ge du är en del exempelkod som kan du skapa ett fönster som ser inte olik denna, och i slutändan göra det till något ganska så här. Så dra nytta av CS50, diskutera kontorstid och mer, och ta tröst i det faktum att mängden kod som du måste skriva är faktiskt inte så mycket. Den första utmaningen är bara att vänja själv till en del kod som vi har skrivit. 

Har du frågor om pset3, Shellshock, eller på annat sätt? 

PUBLIK: Det verkade som går igenom med Bryt att koden är nästan en objektorienterad stil, men jag tyckte C var en objektorienterat program. SPEAKER 1: En utmärkt fråga. Så titta igenom distributions kod, koden Vi skrev för pset3, för dem som är bekanta, det ser ut som det är en litet objektorienterat. Kort svar är, det är. Det är en uppskattning av hur ni kan göra objektorienterad kod med ett språk som C, men det är fortfarande ytterst procedur. Det finns inga metoder inuti variablerna, som du ser. Men det påminner om det. Och vi får se den funktionen igen när vi kommer till PHP och JavaScript mot slutet av terminen. Men för nu, se det som en antydan om vad som komma skall. Bra fråga. Okej. Så slå samman sort var hur vi vänster saker förra gången. Och slå samman sort var svalt i meningen att det var så mycket snabbare, åtminstone på grundval av de ytliga tester vi gjorde förra veckan, än, säg, bubbla sortera, urval sort, inser sort. Och vad som var snyggt också är bara hur koncist och snyggt du kan uttrycka det. Och vad gjorde vi säger att det var en övre bundet på speltid för merge sortera? Yeah? 

PUBLIK: n log n? 

SPEAKER 1: n log n, rätt. n log n. Och vi ska återkomma till vad det egentligen betyder eller var det kommer ifrån, men detta var bättre än vad gångtid som vi såg för bubbla urval och inför sort? Så n kvadrat. n squared är större än så här, och även om det inte är uppenbart, vet att log n är mindre än n, så om du gör n gånger något mindre än n, det kommer att vara mindre än n kvadrat. Det är lite av intuition där. Men vi betalade ett pris för detta. Det var snabbare, men ett tema som startade växa fram i förra veckan var denna avvägning. Jag fick bättre prestanda tidsmässigt, men vad jag har att spendera på den andra sidan, för att uppnå det? 

PUBLIKEN: Minne. SPEAKER 1: Säg igen? PUBLIKEN: Minne. SPEAKER 1: Minne, eller space mer allmänt. Och det var inte super självklart med våra människor, men minns att våra volontärer stega framåt och kliva tillbaka som om det finns en matris här, och som om det inte finns en andra matris här att de kunde använda, eftersom vi behövs någonstans att slå ihop dessa folks. Vi kunde inte bara byta dem på plats. Så sammanfoga sortera hävstångs finns mer utrymme, vilket Vi behövde inte med de andra algoritmerna, men uppåtsidan är att det är mycket snabbare. Och ärligt talat, i den verkliga världen utrymme dessa dagar-- RAM, hårddisk space-- är relativt billigt, och så det är inte nödvändigtvis en dålig sak. 

Så låt oss ta en snabb titt, lite mer metodiskt, på vad vi gjorde och varför vi sa att det låg n log n. Så här är de åtta siffror och åtta volontärer som vi hade förra gången. Och det första som Merge Sortera sa åt oss att göra var det? PUBLIK: Dela i två delar. SPEAKER 1: Säg igen? PUBLIK: Dela i två delar. SPEAKER 1: Dela i två, eller hur. Det påminner mycket om telefonboken, om klyftan och erövra mer allmänt. Så vi tittade på den vänstra halvan. Och sedan när vi sa, sortera den vänstra halvan av elementen, vad gjorde vi nästa säga? Sortera den vänstra halvan av det vänstra hälften, som tillät oss att, efter att dela i två delar, fokusera på fyra och två. 

Hur kan du sortera en lista nu, i gul, storlek två, använder Merge Sort? Tja dela den på mitten, och sortera den vänstra halvan. Och det var där saker fick lite dum kort. Hur kan du sortera en lista som är över storlek ett, som den här nummer fyra här? Den är sorterade. Du är klar. 

Men hur gör du sortera en lista med storlek en när det är nummer två? Jo, samma sak, men nu vad var tredje och viktigt steg i Merge Sort? Du var tvungen att slå ihop vänster halva och den högra halvan. Och när vi gjorde det, vi såg klockan fyra, vi tittade på två. Vi bestämde okej, uppenbarligen två kommer först, så vi satte två i sin ställe, följt av fyra. Och nu måste du sorts spola tillbaka, och detta är typ av egenskap av en algoritm som Merge Sortera, spola tillbaka i minnet. Vad var nästa rad av historien? Vad ska jag fokusera på nästa? Den högra halvan av den vänstra hälften, vilket är sex och åtta. 

Så låt mig bara gå igenom det här utan belaboring poängen för mycket. Sex och åtta, då sex är sorterade åtta sorteras. Slå ihop ihop dem så där, och nu nästa stora steg är, naturligtvis, sortera den högra halvan från det allra första steget i denna algoritm. Så vi fokuserar på en, tre, sju, fem. Vi fokuserar då på den vänstra halvan. Den vänstra halvan av denna, den högra halvan av det, och sedan slå ihop i ett och tre. Då den högra halvan, sedan vänster halva av den, då den högra halvan av den. Slå ihop det, och nu vad steget återstår? Slå ihop den stora vänstra halvan och den stora högra halvan, så man går ner där, sedan två, sedan tre, sedan fyra, sedan fem, sedan sex, sedan sju, sedan åtta. 

Så nu varför är det i slutändan avslöja, särskilt om n och logaritmer mer allmänhet hellre fly dig, åtminstone i de senaste minne? Tja, märker höjden på denna sak. Vi hade åtta delar, och vi delade det med två, med två, med två. Så log bas två av åtta ger oss tre. Och lita på mig, att om lite oklar på det. Men log bas två av åtta är tre, så vi har gjort tre lager av sammanslagning. Och när vi gick samman element, hur många element vi tittar på var och en av dessa rader? Sammanlagt n, eller hur? Eftersom att slå samman den översta raden, även om vi gjorde det bit för bit, vi slutligen rörd varje nummer en gång. Och i den andra raden, till slå ihop dessa listor i storlek två, vi hade att röra varje element gång. Och då här egentligen tydligt i den sista raden, vi hade att röra var och en av dem element en gång, men bara en gång, så här ligger alltså vår n log n. 

Och nu bara för att göra saker lite mer formellt för bara ett ögonblick, om du skulle nu analysera denna vid ett slags högre nivå och försöker bestämma, väl hur kanske du går om att uttrycka speltid för denna algoritm bara genom att titta på det och inte genom användning av en contrived exempel? Nå, hur mycket tid skulle du säga en steg så här i gult skulle ta, Om n <2 retur? Det är en stor o för vad? Så jag ser en, så ett steg, kanske två steg eftersom det är om och sedan återvända, men det är konstant tid, eller hur? Så vi sa O (1), och det är hur jag ska uttrycka detta. T, bara vara gångtid. n är storleken på den ingående, så T (n), bara ett finare sätt att säga driften tiden given ingång storlek n kommer att vara i storleksordningen av konstant tid, i O (1). 

Men annars, hur är det här? Hur skulle du uttrycka gångtid för denna gula linjen? T om vad? Du kan slags fuska här och svara på min fråga cykliskt. Så om drifttid i allmänhet vi bara säga är T (n). Och nu är du typ av punting här och säga, ja, bara sortera den vänstra halvan, och sedan sortera den högra halvan. Hur kan vi symboliskt speltid för denna gula linjen? T om vad? Vad är storleken på ingång? n över två. Varför inte jag bara säga att? Och då är en annan T (n / 2) och sedan igen, om jag slå ihop två sorterade halvor, hur många element kommer jag att behöva röra totalt? n. Så jag kan uttrycka det, bara för att vara typ av infall, som gångtiden i allmänhet. T (n) är bara speltid för T (n / 2), plus T (n / 2), vänster halva och högra halvan, plus O (n), vilket troligen n steg, men kanske, om jag använder två fingrar, Det är dubbelt så många steg, men det är linjärt. Det är en del antal steg det är en faktor n, så vi skulle kunna uttrycka det som det här. Och det är här nu ska vi punt till baksidan av vår gymnasiet matte lärobok vi är att återfall i slutändan hamnar equaling detta, n gånger log n, om du verkligen gör ut matten mer formellt. 

Så det är bara två perspektiv. Ett numeriskt med en hårdkodad representativt exempel med hjälp av åtta siffror och en mer allmän titt på hur vi kom dit. Men det som är verkligt intressant här är, återigen, denna föreställning om cykling. Jag är inte använder för slingor. Jag slags definiera något i termer av sig själv, inte bara med detta matematisk funktion, utan också i fråga om denna pseudo-kod. Denna pseudokod är rekursiv i att två av dess linjer i huvudsak säga till den att gå använder sig för att lösa ett mindre Problemet med mindre storlek, och sedan igen och igen och igen tills vi tälja det ner till det så kallade referensscenariot. 

Så låt oss faktiskt dra en mer övertygande take-away från detta enligt följande. Låt mig gå in i gedit och ta en titta på några av dagens källkod, särskilt exemplet här. Sigma 0, som tydligen tillför siffrorna ett till n. Så låt oss se vad som är välbekant och obekanta här. Först har vi ett par innehåller, så inget nytt där. Prototype. Jag är lite oklar på detta efter några dagar, men vad gjorde vi säger en prototyp av en funktion är? PUBLIK: [ohörbart]. SPEAKER 1: Vad är det? PUBLIK: Vi tillkännager det. SPEAKER 1: Vi tillkännage det. Så du undervisar Clang, hej, faktiskt genomföra detta ännu, men någonstans i den här filen, förmodligen, kommer att en funktion som kallas vad? Sigma. Och detta är bara ett löfte som det kommer att se ut så här. Det kommer att ta ett heltal som input-- och jag kan bli tydligare och säga int n --and det är kommer att returnera en int, men semikolonmedel, mm, jag ska komma runt att genomföra detta lite senare. Återigen är Clang dum. Det kommer bara att veta vad du berättar det uppifrån och ned, så vi måste åtminstone ge det en antydan om vad som komma skall. 

Låt oss nu titta på huvud här. Låt oss bläddra ner här och se vad huvud gör. Det är inte så länge för en funktion, och i själva konstruktionen här är bekant. Jag deklarerar en variabel n, och sedan Jag tjata användaren och om igen för ett positivt heltal med hjälp getInt, och endast utträde ur denna slinga när användaren har uppfyllt. Gör Samtidigt har vi använt för att pester användaren på detta sätt. Nu är detta intressant. Jag förklarar en int som heter "svar." Jag tilldelar den returvärdet av en funktion som kallas "sigma". Jag vet inte vad det gör ännu, men Jag minns att förklara det för en stund sedan. Och då jag passerar i värde som användaren har skrivit in, n, och sedan rapporterar jag svaret. Bra låt oss rulla tillbaka för bara ett ögonblick. Låt oss gå vidare i den här katalogen, gör sigma 0, och faktiskt köra programmet och se vad som händer. Så om jag går vidare och kör detta program ./sigma-0, och jag skriver på ett positivt heltal som två, Sigma, som den grekiska symbolen antyder, är bara kommer att lägga upp alla nummer från noll på upp till två. Så 0 plus 1 plus 2. Så detta ska förhoppningsvis ge mig 3. Det är allt den gör. Och på samma sätt, om jag kör detta igen och jag ger det till nummer tre, det är 3 plus 2, så det är 5 plus 1 borde ge mig 6. Och sedan om jag blir riktigt galen och att skriva i större siffror, Det borde ge mig större och större summor. Så det är allt. 

Så vad gör sigma ut? Tja, det är ganska enkelt. Det är så vi kan ha genomfört detta för de senaste veckorna. "Int" kommer att vara den typ avkastning. Sigma är namnet, och det tar en variabel m istället för n. Jag ska ändra på det där uppe. Då är detta bara en sanity check. Vi får se varför i ett ögonblick. Nu förklarar jag en annan variabel, summa, initiera den till noll. Sedan har jag här För loop iteration, uppenbarligen för tydlighet, från i = 1 på upp till en = m, vilket är vad användaren skrivit in, och sedan jag öka summan så här. Och sedan tillbaka summan. 

Så ett par frågor. Ett, jag hävdar i min kommentar att detta undviker risken för en oändlig slinga. Varför skulle passera på ett negativt tal framkalla, eventuellt, en oändlig loop? 

PUBLIK: Du kommer aldrig att nå m. 

SPEAKER 1: når aldrig m. Men m förs in, så låt oss överväga ett enkelt exempel. Om m föres in av användaren som negativ en. Oavsett viktigaste. Huvud skyddar oss från detta också, så jag är bara vara riktigt anal med sigma att också se till att ingången inte kan vara negativ. Så om m är negativ, något negativt. Vad kommer att hända? Tja, jag går till få initialiseras till ett, och sedan jag kommer att bli mindre än eller lika med m? 

Avvakta. Det var-- låt oss inte, låt oss nix denna historia. Jag ville inte ställa den frågan, eftersom risken att jag syftar på kommer inte att hända eftersom jag är alltid kommer vara större than-- OK, Jag återkalla den frågan. OK. Låt oss bara fokusera på denna del här. Varför fick jag förklarar en del utsidan av slingan? Kallelse på rad 49 Jag har förklarats i insidan av slingan, men på nätet 48 Jag har förklarade några utanför. Yeah. PUBLIK: [ohörbart]. SPEAKER 1: Visst. Så först och främst gör jag verkligen inte vill deklarera och initiera summan till noll insidan av slinga på varje iteration, eftersom detta uppenbarligen skulle besegra Syftet summera siffrorna. Jag skulle hålla ändra värdet till noll. Och dessutom, vad är en annan, mer svårbegripliga Anledningen till samma beslut design? Yeah. 

PUBLIK: [ohörbart]. SPEAKER 1: Exakt. Jag vill komma åt det utanför av slingan också på vilken linje? Den 53. Och på grundval av vår tumregel från ett par föreläsningar sedan, variabler scoped, egentligen, till klamrar som omfattar dem. Så om jag inte deklarerar summan inne av dessa yttre klammerparenteser, Jag kan inte använda den i linje 53. Med andra ord, om jag förklarade summan in här, eller till och med inom För loop, kunde jag inte komma åt den i 53. Variabeln skulle i praktiken vara borta. Så ett par anledningar där. Men nu ska vi gå tillbaka och se vad som händer. Så sigma anropas. Den lägger upp 1 plus 2 eller 1 plus 2 plus 3, och sedan returnerar värdet, lagras det i svaret, och printf här är därför jag ser på skärmen. Så det här är vad vi kallar en iterativ tillvägagångssätt, där iteration bara att använda en loop. A För loop, en while-slinga, en Do While loop, bara göra något nytt och igen och igen. 

Men sigma är lite av en snygg funktion i att jag kunde genomföra det på olika sätt. Vad sägs om detta, vilket bara för att vara typ av cool, låt mig verkligen bli av en massa distraktion eftersom denna funktion är egentligen ganska enkel. Låt oss skära ner det bara till dess fyra grundlinjer och bli av med alla de kommentarer och klammerparenteser. Detta är lite av en otrolig alternativ implementering. Okej, kanske inte otrolig, men det är lite sexigare, okej, att titta på detta så mycket mer koncist. Med bara fyra rader kod, Jag har först denna sanity check. Om m är mindre än eller lika med noll, gör sigma ingen mening. Det har bara tänkt att vara i det här fallet för positiva tal, så jag ska bara retur noll godtyckligt så att vi åtminstone har vissa sk basfall. 

Men här är det fina. Helheten av denna idé, att lägga till nummer från 1 till n, eller m i det här fallet, kan göras genom slags vältra över ansvaret. Nå, vad är summan av 1 och m? Tja, vet du vad? Det är samma som summan av m plus ett belopp på 1 till m minus 1. Tja du vet vad? Vad är sigma av m minus 1? Tja, om du typ av följa den här logiskt, det är samma som m minus 1 plus sigma m minus 2. Så kan du typ av bara-- det är som om du är bara försöker reta en vän och de frågar dig en fråga, du slags svara med en fråga, du kan typ av hålla vältra över ansvaret. Men vad är nyckeln är att om du håller göra frågan mindre och mindre och mindre, du är frågar inte vad som är sigma n, vad är sigma av n, vad är sigma n? Du frågar vad som är sigma n, vad är sigma n minus 1, vad är sigma n minus 2? Så småningom din fråga kommer att bli vad? Vad är sigma av en eller noll, några mycket litet värde, och så fort du få det, din vän, du kommer inte att fråga samma fråga igen, du bara kommer att säga, åh det är noll. Vi är klar att spela den här sortens dumma cyklisk spel. 

Så rekursion är handlingen i programmering av en funktion som kallar sig. Detta program, när de sammanställs och kör, är kommer att bete sig exakt samma sätt, men vad är viktigaste är att inuti av en funktion som kallas sigma, det finns en kodrad där Vi kallar oss själva, som normalt skulle vara dåligt. Till exempel, vad händer om jag först sammanställt denna, så gör sigma-- göra sigma 1 ./sigma-1. Positivt heltal, snälla, 50 1275. Så vad funktionen verkar vara, baserat på ett test, korrekt. Men vad händer om jag får lite farligt och ta bort det så kallade basfallet, och bara säga, ja jag bara göra detta mer komplicerat än det är. Låt oss bara beräkna sigma genom att m och sedan lägga i sigma m minus ett? Nå, vad kommer att hända här? Låt oss zooma ut. Låt oss kompilera om programmet, spara den, kompilera programmet, och sedan redo ./sigma-1 zoomar in, ange positivt heltal snälla, 50. Hur många av er är villig att fess upp till att se det? 

OK. Så det här kan hända för ett antal skäl, och ärligt talat den här veckan är vi på väg att ge dig mer av dem. Men i detta fall, försök resonera bakåt Vad kan ha hänt här? Segmente fel, sa vi senast tid, hänvisar till ett segment av minnet. Något dåligt hänt. Men vad var det mekaniskt som gick snett här på grund av min avlägsna av att så kallade basfallet, där jag returnhårdkodad värde? Vad tror du gick fel? Yeah. 

PUBLIK: [ohörbart]. SPEAKER 1: Ah. Bra fråga. Så storleken på antalet att jag summera blev så stor att den överskred storleken på det minnesutrymme. Bra idé, men inte i grunden kommer att orsaka en krasch. Det kan orsaka heltalsspill, där bitarna flip drygt och sedan vi miste en riktigt stor nummer för som ett negativt tal, men att inte själv kommer att orsaka en krasch. Eftersom vid slutet av den dag en int är fortfarande 32 bitar. Du ska inte misstag stjäla en 33: e bit. Men en bra tanke. Yeah. 

PUBLIK: [ohörbart]. TALARE 1: Metoden aldrig stannar, och faktiskt den kallar sig igen och igen och igen och igen och igen, och ingen av dessa funktioner någonsin avsluta eftersom deras enda rad av kod anropar sig själv om och om igen och igen. Och vad är egentligen händer här och nu vi kan typ av dra denna bildmässigt. Låt mig gå över till ett Bilden för bara ett ögonblick. Detta är en bild, som kommer så småningom att bygga ut mer detaljerat, om vad som händer insidan av datorns minne. Och det visar sig att den längst ner på denna bilden är något som kallas stacken. Detta är en bit av minne, en bit av RAM, det är bara användas när som helst en funktion anropas. Varje gång du, en programmerare, anropa en funktion, operativsystemet, liksom Mac OS, Windows eller Linux, griper ett gäng byte, kanske en få kilobyte, kanske några megabyte minne, händer dem till dig, och sedan låter du kör din funktion med hjälp av oavsett variabler som du behöver. Och om du sedan ringa en annan funktion och en annan funktion, du får en annan bit av minnet och en annan del av minnet. 

Och faktiskt, om dessa gröna brickor från Annenberg representerar detta minne, Här är vad som händer den första gång du ringer funktionen sigma. Det är som att sätta en bricka som denna på vad som är initialt en tom stack. Men sedan om det facket kallar sig, så att säga, ringer en annan instans av sigma, det är som att be operativsystemet, ooh, behöver lite mer minne, ge mig den. Och då blir staplade ovanpå. Men vad är nyckeln här är att det första facket är fortfarande där, eftersom han åberopat denna andra fack. Nu under tiden, sigma call sigma, det är som att be om mer minne. Får staplade på här. sigma kallar sigma, det är en annan fack som får staplas på här. Och om du fortsätter att göra detta, småningom, typ av kart denna visuella till att kartlägga, vad som kommer att hända med stapeln av brickor? Det kommer att överstiga det belopp som minne datorn har. Och så snart som denna gröna fack överstiger den horisontella linjen ovanför stacken och över det ordet hög, vilket vi ska återkomma till i framtiden, det är en dålig sak. Högen är en annan segment av minne, och om du låter dem brickor lugg och lugg på, du kommer att överskrida din egen del av minnet, och ett program verkligen kommer att krascha. 

Nu som en sidoreplik, denna idé av rekursion därför kan helt klart leda till problem, men det är inte nödvändigtvis en dålig sak. Därför anser, efter att ha allt how-- och kanske detta tar lite tid att vänja att --how eleganta eller hur enkelt att genomförandet av sigma var. Och vi kommer inte att använda rekursion så mycket i CS50, men i CS51, och verkligen någon klass där du manipulera datastrukturer som träd eller släktträd, att ha en viss hierarki, det är super, super bra. Nu, som en sidoreplik, så att du som blivande datavetare är bekant med några av Googles interna skämt, om du går till Google och du tittar upp vad som är definition av, säg, rekursion skriver. Uh-huh. Som en sidoreplik, drog jag upp några. Det var som 10 minuter av förhalning morse. Om du dessutom Google "snett", meddelande genom att luta huvudet slightly-- och sedan den här är kanske mest avskyvärda av alla eftersom någon använt som deras dag att genomföra detta några år ago-- kom igen. Åh, wait-- det är en bugg. 

Så som körs på en av de världens största webbplatser är dessa dumma små påskägg. De konsumerar förmodligen en nontrivial antal rader kod bara så att vi kan ha lite roliga saker. Men åtminstone nu får du vissa av dessa interna skämt. 

Nu ska vi ta en titt på några av de vit ligger vi har sagt för sent, och börja att skala tillbaka några lager tekniskt så att du verkligen förstår Vad har hänt och du kan förstå några av de hot, liknande Shock, att har nu börjat bli i framkant av allas uppmärksamhet, åtminstone i media. Så här är en mycket enkel funktion som returnerar ingenting, ogiltiga. Dess namn är swap. Det tar i två variabler och den återvänder ingenting. Tar i a och b. Så en snabb demonstration. Vi tog upp dessa. Vi kan lika gärna ta lite bryta här bara ett ögonblick och ha lite något att dricka. Om någon inte skulle ha något emot att gå mig för en stund här. Du då i rödbrunt skjorta? Kom upp. Bara en i dag. Tack, dock. Okej, och vi har kommer upp vem här? Vad heter du? 

TALARE 4: Laura. 

SPEAKER 1: Laura. Kom upp. Så Laura, mycket enkel utmaning i dag. Trevligt att träffas yo. Okej. Så vi har lite mjölk hit och Vi har lite apelsinjuice hit och några koppar som vi lånat från Annenberg idag. 

SPEAKER 4: Lånad. SPEAKER 1: Och kommer att gå vidare och ge dig ett halvt glas här. Okej. Och vi ger dig hälften ett glas mjölk. Åh, och bara så att du kan ihåg vad det var, Jag kom ihåg att ta med upp detta och i dag. Okej. Om du inte skulle ha något emot, låt oss se, vi kan sätta dem över dina glasögon om du vill. Detta är alltså den världen från Lauras ögon. Okej. Så ditt mål, med tanke på två koppar flytande här, mjölk och apelsinjuice, är byta de två innehåll, så att apelsinjuice går in i mjölk kopp och mjölken går in apelsinjuicen koppen. 

SPEAKER 4: Får jag en kopp? SPEAKER 1: Jag är så glad att du frågade, men det skulle ha varit mycket bättre tagningar om du inte hade bett. Men ja, kan vi erbjuda dig en tredje cup som är tomt, förstås. Okej. Så byta innehållet där. Mycket trevligt. Mycket bra. Du gör detta anmärkningsvärt noga. Och steg tre. Okej. Utmärkt. En stor applåd skulle vara bra för Laura. Okej. Vi har en liten avskedsgåva för dig, men låt mig ta dessa. Tack så mycket. Så ett enkelt exempel, fast, att visa att om du gör vill byta innehållet av två behållare, eller låt oss kalla dem variabler, du behöver lite tillfällig lagring att arrangera en av innehållet i den att du faktiskt kan göra swappen. Så ja, denna källkod här uppe i C är representativt för just detta. Om apelsinjuice var en och mjölken var b, och vi ville byta de två, du kan försöka något kreativt genom att hälla en in i den andra, men som förmodligen inte skulle sluta särskilt väl. Och så använder vi en tredje kopp, samtal Det tmp, T-M-P av konvention, och sätta innehållet i EGT i det, sedan byta en kopp, sedan lägga EGT i original cup, och därigenom uppnå, precis som Laura gjorde, swap. 

Så låt oss göra just det. Låt mig gå vidare och öppna upp ett exempel som är faktiskt kallas "no swap ", eftersom detta inte är så enkelt gjort som man kan tro. Så i det här programmet, märker att Jag använder stdio.h, vår gamle vän. Jag har prototypen för swap där uppe, vilket innebär att dess genomförande är troligen nere, och låt oss se vad denna huvud Programmet kommer att göra för mig. Jag förklarar först int x blir en, och int y blir två. Så tänk på dem som EGT och mjölk, respektive. Och då har jag bara en printf säga x är detta och y är det, bara så jag kan visuellt se vad som händer. Då har jag printf hävdar att jag byter de två, och då jag skriver ut en hävdar att de är bytt, och jag skriver ut x och y igen. Så här nere i swap är exakt vad Laura gjorde, och exakt vad vi såg på skärmen för en stund sedan. 

Så låt oss gå vidare och bli mycket besvikna. Gör inga swap, och kör ingen swap, zoomar in på utgången här. Ange x är 1, y är 2, byta växlats. x är fortfarande 1, och y är fortfarande 2. Så även om, ärligt talat, det här ser precis som, om än mer tekniskt, vad Laura gjorde, inte verkar fungera. Så varför är det? Tja, det visar sig att när vi skriver ett program som detta som har både huvud, markerad här, och sedan en annan funktion, som swap, markerad här, som den kallar, världens ser lite något liknande dessa brickor en stund sedan. När huvud först anropas, det är som att be operativsystem för lite minne för alla lokala variabler som x och y som huvud har, och de hamnar där. Men om huvud samtal byta, och huvud passerar att byta två argument, a och b, apelsinjuice och mjölk, det är inte som lämna apelsinjuice och mjölk till Laura. Vad en dator gör, är det passerar kopior av apelsinjuice och kopior av mjölken till Laura, så att vad är slutligen inne i detta fack är värdet en och två, eller EGT och mjölk, men kopior av dessa, så att på denna punkt i berättelsen, det är EGT och mjölk i var och en av dessa brickor. Det är en en och en två i var och en av dessa brickor, och växlingsfunktionen är verkligen fungerar. Den byta dem inuti av den andra översta facket, men att byta inte har någon inverkan. Och baserat på bara några grundläggande princip vi har talat om tidigare, och faktiskt bara några minuter sedan, vad kan förklara varför ändra a och b insida swap har ingen effekt på x och y, även om Jag passerade x och y på växlingsfunktionen. Vad är nyckelordet här att kan förenklat förklara? Jag tror att jag hört det här? PUBLIKEN: Return. SPEAKER 1: Return? Inte tillbaka. Låt oss med en annan. Vad är det? 

PUBLIK: [ohörbart]. 

SPEAKER 1: OK, så return-- vi kunde göra retur arbete i berättelsen, men det finns en ännu enklare förklaring. PUBLIKEN: Scope. SPEAKER 1: Räckvidd. Jag tar utrymme. Så omfattning, kom ihåg var vår x och y deklareras. De deklarerade inuti Huvud rätt upp här. a och b, under tiden, är effektivt förklarats insidan av swap, inte riktigt i klammerparentes men ändå i det allmänna området för swap. Och så faktiskt, a och b existerar endast inom detta fack från Annenberg, detta andra bit av kod. Så vi verkligen ändra kopian, men det är egentligen inte så bra. 

Så låt oss ta en titt på detta lite lägre nivå. Jag kommer att gå tillbaka till Source Directory, och jag ska först zooma in här, och bara för att bekräfta att jag är i det här större fönster terminal, programmet fortfarande beter sig som det. Antag nu att detta inte avsiktligt. Klart jag ville swap till arbete, så det känns som en bugg. Nu kunde jag börja lägga en massa printf ter till min kod, skriva ut x hit, y över Här, en hit, b hit. Men ärligt talat, det är nog det som du har gjort i ett par veckor nu, i kontorstid och hemma vid arbete på psets försöker hitta några buggar. Men ser du, om du inte redan har, det problemet satt tre introducerar dig till ett kommando som heter GDB, där GDB, GNU debugger, har själv en massa funktioner som faktiskt kan låt oss förstå situationer så här, men mer tvingande, lösa problem och hitta buggar. Så jag ska göra det här. Istället för ./noswap, jag är i stället kommer att köra GDB ./noswap. Med andra ord kommer jag att köra min programmet inte i Bash, vår nya vän idag. Jag kommer att köra min Programmet noswap inuti i denna andra program som heter GDB, vilket är en avlusare, vilket är ett program som är utformat för att hjälpa Ni människor hitta och ta bort buggar. Så om jag slog Kör hit, det finns ett förfärligt mycket text att du verkligen aldrig behöver läsa. Det är i huvudsak en distraktion från prompten, vilket Jag ska träffa Kontroll-L att gå upp på toppen där. Detta är den GDB prompten. Om jag vill köra det här programmet nu, eftersom denna lilla lathund på dagens slide antyder Run är det första kommandon som vi tänkt att införa. Och jag ska bara skriva köra upp här inne i GDB, och faktiskt det körde mitt program. Nu finns det vissa ytterligare utgångarna på skärmen så här, men det är GDB bara vara anal och berätta vad som händer. Du behöver verkligen inte oroa dig om dessa detaljer just nu. Men vad är riktigt coolt om GDB, om jag gör det här igen-- Kontroll-L rensar screen-- låta mig gå framåt och typ "break", och därigenom, när jag slog in, sätta vad är kallas en brytpunkt vid noswap.c, linje 16, som är där GDB räknat ut mitt program faktiskt är, faktiskt är min funktion. Detta ska vi ignorera för nu men det är adressen minnet specifikt av denna funktion. Så nu när jag typ springa, märker vad är hett här. Min programmet bryter på den linje som jag berättade GDB att pausa exekvering på. Så jag behöver inte nu ändra min kod, lägga till några printf s, kompilera det, repris den, ändra, lägga till några printf s, spara den, kompilera det, kör den. Jag kan bara gå igenom mitt program steg för steg för steg till mänsklig hastighet, inte på Intel-inside typ av hastighet. 

Så nu märker denna linje visas här, och om jag går tillbaka till mitt program i gedit, märker att det faktiskt är den allra första rad kod. Det finns linje 16 i gedit. Det finns linje 16 i GDB, och till och med även om detta svartvita gränssnitt är inte alls lika användar vänlig, innebär detta att linjen 16 har inte utförts ännu, men det är på väg att bli. Så ja, om jag skriver print x, inte printf, bara skriva ut x, Jag får några falska värde där noll, eftersom x har inte initierats ännu. Så jag ska skriva härnäst, eller om du vill vara snygga, bara n för nästa. Men när jag skriver nästa komma in, nu märker det går vidare till linje 17. Så logiskt, om jag har verk linje 16 och jag nu skriver print x, vad ska jag se? One. 

Och nu detta är visserligen förvirrande. $ 2 är bara ett finare sätt att, om man vill hänvisa till det värdet senare, du kan säga "dollar sign två." Det är som en back referens. Men för nu, bara ignorera det. Det intressanta är vad som är till höger om likhetstecknet. Och nu om jag skriver nästa gång och skriv ut y, ska jag se 2. Jag kan nu också skriva ut x igen, och ärligt talat, om jag börjar bli lite förvirrad där jag är, kan jag skriva lista för listan och bara se något sammanhang runt punkten är jag faktiskt på. Och nu kan jag skriva nästa, och där x är 1. Nu skriver jag nästa. Åh, y 2. Och återigen, det är förvirrande, eftersom GDB produktion håller på att blandas med min egen utgång. Men om du kom ihåg, genom blick och tillbaka på din kod eller lägga ut den sidan vid sida kanske, du ska se att egentligen är jag bara stega igenom mitt program. 

Men lägg märke till vad som händer sedan, bokstavligen. Här är linje 22. Låt mig gå över den, och därmed går vidare till 23, och om jag skriver ut x nu, fortfarande en. Och om jag skriver ut y nu, fortfarande en. Så det här är inte en nyttig övning. Så låt oss göra om det här. Låt mig gå tillbaka till topp och typ springa igen. Och den säger att programmet som är som debuggade har startat redan, startade från början. Ja, låt oss göra det här igen. Och den här gången ska vi göra härnäst, nästa, nästa, nästa, nästa, men nu det blir intressant. Nu vill jag kliva in swap, så jag skriver inte nästa. Jag skriver steg, och nu märker det har hoppat mig till noswap.c linje 33. Om jag går tillbaka till gedit, vad är linje 33? Det är den första egentliga kodrad inuti swap. Vilket är trevligt, för nu kan jag typ av rota runt och få nyfikna om vad som händer riktigt där. Låt mig skriva tmp. Oj. Varför måste tmp har någon galet, bogus sopor värde? PUBLIK: Det har inte initierats. SPEAKER 1: Det har inte initierats. Och faktiskt, när du kör ett program, du får en hel massa minne av operativsystemet, men du har inte initierats några värden, så vad bitar du är ser här, även om det är denna galna stora negativa nummer, betyder bara att de är resterna från någon tidigare användning av detta RAM, även om jag inte har jag själv behövde det ännu. Så nu ska jag gå vidare och typ Nästa, och om jag nu skriver print tmp, vad ska jag se? Oavsett värdet av en var, a är det första argumentet, precis som x var den första sak som gått in, så en och x bör vara samma, så ut tmp ska skriva ut mig en. 

Så vad du ser i problem set tre är en handledning av slag på GDB, men inser att detta är början en titt på ett verktyg som faktiskt kommer att hjälpa dig att lösa problem så mycket mer effektivt. Vad vi är i slutändan ska göra på onsdag är att börja skära ner några lager och ta bort några stödhjul. Det där kallas sträng som vi har använt under en tid, vi ska sakta ta det ifrån från dig och börja prata om något mer esoteriskt känd som char *, men vi ska göra det här trevliga och försiktigt vid första, trots pekare, som de kallas, kan göra en del mycket dåliga saker om övergrepp, genom att titta på en liten claymation från vår vän Nick Parlante från Stanford Universitet, professor i dator vetenskap som satt ihop den här förhandsvisningen om vad som komma skall på onsdag. 

[VIDEOAVSPELNING] Hej, Binky. Vakna. Det är dags för pekaren kul. 

Vad är det? Lär dig mer om pekare? Åh, goody! [END VIDEOAVSPELNING] SPEAKER 1: Det väntar på onsdag. Vi ses då. [VIDEOAVSPELNING] -Och Nu, djupa tankar, genom Daven Farnham. 

Varför lär vi oss C? Varför inte A +? 

[LAUGHTER] 

[END VIDEOAVSPELNING]