1 00:00:00,000 --> 00:00:12,040 >> [MUSIK SPELA] 2 00:00:12,040 --> 00:00:16,460 >> SPEAKER 1: Okej, det här är CS50, och detta är början på vecka fyra, 3 00:00:16,460 --> 00:00:20,420 och som ni kanske har hört eller läsa, har världen slutar. 4 00:00:20,420 --> 00:00:23,520 Att gå runt på internet har varit kunskap och medvetenhet 5 00:00:23,520 --> 00:00:27,100 av ett fel i ett program, en programmeringsspråk som heter Bash. 6 00:00:27,100 --> 00:00:32,729 Detta har underbart branded som Shellshock, eller Bash dörren, 7 00:00:32,729 --> 00:00:35,485 men artiklar som dessa har inte varit ovanligt. 8 00:00:35,485 --> 00:00:38,807 Och faktum är att många av dem kommer med tillbaka minnen av Heartbleed, 9 00:00:38,807 --> 00:00:41,640 som ni kanske har märkt i Tryck tillbaka i våras, vilket 10 00:00:41,640 --> 00:00:43,980 var likaså tämligen dramatisk. 11 00:00:43,980 --> 00:00:47,110 Nu för de av er här idag, hur många av er har, 12 00:00:47,110 --> 00:00:50,330 även om du inte förstår vad det handlar om, hört talas om Shellshock? 13 00:00:50,330 --> 00:00:51,370 14 00:00:51,370 --> 00:00:54,245 Okej, och hur många av er har datorer som är utsatta? 15 00:00:54,245 --> 00:00:55,680 16 00:00:55,680 --> 00:01:00,250 OK, bör det finnas långt, långt fler händer upp just nu, av skäl som vi skall se. 17 00:01:00,250 --> 00:01:02,580 >> Låt oss ta en titt på vad som finns pågått i media 18 00:01:02,580 --> 00:01:05,304 och sedan förklara det lite för oss här tekniskt. 19 00:01:05,304 --> 00:01:07,670 20 00:01:07,670 --> 00:01:11,250 >> TALARE 2: Säkerhetsexperter har varnade för att ett allvarligt fel kunde 21 00:01:11,250 --> 00:01:15,650 handla om att påverka hundratals miljoner av världens webbanvändare. 22 00:01:15,650 --> 00:01:20,600 Så vad exakt är det bugg som har varit dubbade Shellshock, och vad gör det? 23 00:01:20,600 --> 00:01:23,720 24 00:01:23,720 --> 00:01:28,910 Nå, Shock är också känd som den Bash bugg, programvaran det utnyttjar. 25 00:01:28,910 --> 00:01:33,230 Hackare använder viruset för att skanna sårbara system som kör Linux och Unix 26 00:01:33,230 --> 00:01:36,300 operativsystem och sedan infektera dem. 27 00:01:36,300 --> 00:01:38,730 Bash är en kommandorad skal. 28 00:01:38,730 --> 00:01:43,460 Detta låter användare fråga kommandon för att starta program och funktioner i programvaran 29 00:01:43,460 --> 00:01:45,250 genom att skriva in text. 30 00:01:45,250 --> 00:01:49,980 Det är oftast används av programmerare, och bör inte vara öppna mot omvärlden, 31 00:01:49,980 --> 00:01:51,590 även om Shellshock ändrar det. 32 00:01:51,590 --> 00:01:54,160 33 00:01:54,160 --> 00:01:57,910 >> Tja, worringly, vissa analytiker varna det kan vara ett större hot, 34 00:01:57,910 --> 00:02:01,580 eftersom Shellshock tillåter fullständig kontroll över en infekterad maskin, 35 00:02:01,580 --> 00:02:06,030 medan Heartbleed endast tillåtet hackare att spionera på datorer. 36 00:02:06,030 --> 00:02:09,130 Det är så allvarligt, det är betyg en 10 av 10 37 00:02:09,130 --> 00:02:11,900 för svårighetsgrad av National Sårbarhet Database. 38 00:02:11,900 --> 00:02:15,530 39 00:02:15,530 --> 00:02:20,015 2/3 av alla webbservrar är på risk, inklusive vissa Mac-datorer. 40 00:02:20,015 --> 00:02:22,760 41 00:02:22,760 --> 00:02:25,600 Tja, se till att du patch ditt system nu. 42 00:02:25,600 --> 00:02:29,330 Den som en webbplats igång de drabbade operativsystem 43 00:02:29,330 --> 00:02:31,800 bör vidta åtgärder så snart som möjligt. 44 00:02:31,800 --> 00:02:35,390 Den som har råd med det ska se deras övervakning och webbapplikation 45 00:02:35,390 --> 00:02:37,355 brandväggar för att hålla utkik efter eventuella attacker. 46 00:02:37,355 --> 00:02:39,979 47 00:02:39,979 --> 00:02:41,770 TALARE 3: Värsta som kan hända är 48 00:02:41,770 --> 00:02:45,080 att någon skulle skriva kod som automatiskt skulle gå och scanna 49 00:02:45,080 --> 00:02:48,280 Internet och skulle påverka alla dessa datorer. 50 00:02:48,280 --> 00:02:50,710 Och när de gör det, ja, det värsta de kunde göra 51 00:02:50,710 --> 00:02:53,300 är bara att ta bort allt, eller stänga platserna ned. 52 00:02:53,300 --> 00:02:55,360 Så vi kunde se skador från denna synpunkt, 53 00:02:55,360 --> 00:02:58,300 där vi skulle ha skadliga människor som bara bestämmer sig för att orsaka förödelse 54 00:02:58,300 --> 00:03:02,534 genom att bringa system ned eller ta bort filer och sånt. 55 00:03:02,534 --> 00:03:05,200 TALARE 2: En del säger att detta är en av de svåraste att mäta 56 00:03:05,200 --> 00:03:08,080 buggar i år, och det kan ta veckor eller till och med 57 00:03:08,080 --> 00:03:10,820 månader för att bestämma dess slutliga effekten. 58 00:03:10,820 --> 00:03:12,180 59 00:03:12,180 --> 00:03:15,560 >> SPEAKER 1: Så allt detta är sant, men det roliga är, nästan alla 60 00:03:15,560 --> 00:03:18,330 av bildspråk som du just såg, utom kanske tangentbordet, 61 00:03:18,330 --> 00:03:20,930 har ingenting att göra med felet som helst. 62 00:03:20,930 --> 00:03:23,960 Servrar och ledningar och så vidare, Det blir liksom tangentiellt relaterade, 63 00:03:23,960 --> 00:03:27,410 men kärnan är det faktiskt ganska bekant vad som händer här. 64 00:03:27,410 --> 00:03:30,050 Faktum är, låt mig gå in i vår CS50 apparaten. 65 00:03:30,050 --> 00:03:32,910 Låt mig gå vidare och maximera terminalfönstret här. 66 00:03:32,910 --> 00:03:36,020 Och ni har använt detta, eller den inbäddade versionen i detta, 67 00:03:36,020 --> 00:03:39,460 i gedit för att skriva program, skriva in kommandon och så vidare, 68 00:03:39,460 --> 00:03:43,690 och detta är faktiskt, och har varit i veckor, Bash, B-A-S-H. 69 00:03:43,690 --> 00:03:46,890 Detta är Bourne-again shell, som är bara ett finare sätt att säga, 70 00:03:46,890 --> 00:03:50,220 Detta är ett program som har en blinkande prompt, effektivt, 71 00:03:50,220 --> 00:03:51,970 som sitter där och väntar för inmatning för dig. 72 00:03:51,970 --> 00:03:53,920 Och det är kommandot line interface via vilket 73 00:03:53,920 --> 00:03:57,650 ni har varit igång kommandon och slutligen sammanställa och sedan köra 74 00:03:57,650 --> 00:03:58,400 program. 75 00:03:58,400 --> 00:04:01,320 >> Men våldsamt slag är också en programmerings språk i följande mening. 76 00:04:01,320 --> 00:04:05,460 Du vet att det finns kommandon som cd och ls samt klang och andra, 77 00:04:05,460 --> 00:04:09,580 men du kan definiera dina egna kommandon genom att implementera dem i Bash. 78 00:04:09,580 --> 00:04:11,420 Nu ska vi inte gå till gå in i detalj 79 00:04:11,420 --> 00:04:16,089 att Bash programmeringsspråket, men vet till exempel att det för närvarande, 80 00:04:16,089 --> 00:04:17,607 det finns inget kommando som heter "Hej." 81 00:04:17,607 --> 00:04:19,440 Så det kan hittas i ett av dessa paket. 82 00:04:19,440 --> 00:04:20,856 Det är inte installerat på datorn. 83 00:04:20,856 --> 00:04:21,870 Fråga administratören. 84 00:04:21,870 --> 00:04:26,030 Men om jag vill att det ska finnas ett program kallade "hello" i Bash eller på mitt prompten 85 00:04:26,030 --> 00:04:30,810 Jag kan faktiskt använda syntax som är riktigt gillar C. Det är inte riktigt samma sak, 86 00:04:30,810 --> 00:04:35,020 men det ser ganska lik en funktion, om än saknas vissa detaljer. 87 00:04:35,020 --> 00:04:38,090 Ingenting verkar hända, men nu om jag skriver "Hej," 88 00:04:38,090 --> 00:04:40,960 du kan faktiskt skriva ett program, inte i C, inte på Java, 89 00:04:40,960 --> 00:04:44,280 inte i en annan programmering språket, men i Bash självt. 90 00:04:44,280 --> 00:04:47,630 >> Nu nyckeln här är att jag skrev name Jag ville ge denna nya kommando, 91 00:04:47,630 --> 00:04:50,820 och parentes är också en symbol för detta är en funktion. 92 00:04:50,820 --> 00:04:54,010 Inom parentes kan man också göra roliga saker, och faktiskt även på Mac OS, 93 00:04:54,010 --> 00:04:55,620 detta är ett program som heter Terminal. 94 00:04:55,620 --> 00:04:58,800 Den levereras inbyggd i någons dator som har en Mac i det här rummet, 95 00:04:58,800 --> 00:05:03,640 och du kan göra liknande saker i Mac OS, men du kan gå mer än så. 96 00:05:03,640 --> 00:05:07,110 Och det är lite tangentiell, men det är ganska kul. 97 00:05:07,110 --> 00:05:09,715 Jag blev påmind i morse, när man tänker igenom detta, 98 00:05:09,715 --> 00:05:13,279 ett litet spel jag brukade spela med en av CS50 forna TF 99 00:05:13,279 --> 00:05:16,570 varvid varje gång han skulle gå bort från hans tangentbord med sin skärm olåst, 100 00:05:16,570 --> 00:05:23,611 Jag skulle köra ett kommando som här-- "säga hej." 101 00:05:23,611 --> 00:05:26,610 Och nu varje gång han kom tillbaka till sin tangentbord efter att jag rensat skärmen 102 00:05:26,610 --> 00:05:27,985 och han skulle sitta ner, försöka göra en del arbete, 103 00:05:27,985 --> 00:05:29,250 visa innehållet i sin directory-- 104 00:05:29,250 --> 00:05:29,510 >> [AUDIO SPELA] 105 00:05:29,510 --> 00:05:30,010 >> -Hello. 106 00:05:30,010 --> 00:05:31,621 107 00:05:31,621 --> 00:05:32,120 Hej. 108 00:05:32,120 --> 00:05:35,030 >> SPEAKER 1: Så, i rättvisans namn, Det var faktiskt inte "Hej." 109 00:05:35,030 --> 00:05:36,894 Det var oftast något mer besläktad med att-- 110 00:05:36,894 --> 00:05:37,560 [AUDIO SPELA] 111 00:05:37,560 --> 00:05:37,750 -Beep. 112 00:05:37,750 --> 00:05:39,320 SPEAKER 1: --that jag would-- så hans dator skulle 113 00:05:39,320 --> 00:05:42,170 svära på honom varje gång han faktiskt satte sig vid sitt tangentbord. 114 00:05:42,170 --> 00:05:46,265 Och mycket snabbt han räknat ut att inte lämna sin skärm olåst. 115 00:05:46,265 --> 00:05:48,730 Men detta antyder sorteringen dum kul att du 116 00:05:48,730 --> 00:05:50,210 kan ha med något liknande Bash. 117 00:05:50,210 --> 00:05:52,770 Men det är lite mer allvarligt, för att vara säker, än så. 118 00:05:52,770 --> 00:05:57,235 Och i själva verket är detta ett av de mest farliga och långvariga fel 119 00:05:57,235 --> 00:05:58,860 det har verkligen drabbat världen globalt. 120 00:05:58,860 --> 00:06:02,060 Detta fel har funnits för cirka 20 år, 121 00:06:02,060 --> 00:06:05,780 och du kommer att slås på bara stund av sin relativa enkelhet. 122 00:06:05,780 --> 00:06:07,990 >> Så detta är en representativ befaller att om du 123 00:06:07,990 --> 00:06:10,448 äger en Mac, bokstavligen just nu när du har din locket öppet, 124 00:06:10,448 --> 00:06:12,940 kan du prova att skriva in i det program som heter Terminal. 125 00:06:12,940 --> 00:06:15,410 Terminal är under Tillämpningar Utilities-- 126 00:06:15,410 --> 00:06:18,790 för en gångs skull, inte Windows-användare inte behöver oroa denna threat-- 127 00:06:18,790 --> 00:06:22,310 men de av er med Mac kan skriva detta i ett fönster som jag ska göra här, 128 00:06:22,310 --> 00:06:24,210 och om du skriver som i det här programmet 129 00:06:24,210 --> 00:06:28,830 heter Terminal, som jag gör nu, Om du ser ordet "sårbar", 130 00:06:28,830 --> 00:06:32,200 datorn är sårbara för exploatering. 131 00:06:32,200 --> 00:06:33,850 >> Nu vad innebär det egentligen? 132 00:06:33,850 --> 00:06:35,870 Och det är visserligen några ganska galet syntax, 133 00:06:35,870 --> 00:06:39,050 men låt oss åtminstone dra ut några av de intressanta aspekterna. 134 00:06:39,050 --> 00:06:42,567 Så det finns en viss syntax som ser lite bekant, åtminstone från C 135 00:06:42,567 --> 00:06:43,950 och programmering i allmänhet. 136 00:06:43,950 --> 00:06:47,550 Jag ser några parenteser, semikolon, klamrar och sådant, 137 00:06:47,550 --> 00:06:50,820 men det visar sig att detta dum sak här i gult 138 00:06:50,820 --> 00:06:53,580 är i huvudsak en funktion det gör ingenting. 139 00:06:53,580 --> 00:06:57,840 De kolon medel göra ingenting, och semikolon betyder sluta göra någonting. 140 00:06:57,840 --> 00:07:00,250 Så insidan av dessa klamrar, det faktum 141 00:07:00,250 --> 00:07:02,440 att jag har en lika logga till vänster, detta 142 00:07:02,440 --> 00:07:05,500 är i huvudsak att skapa ett kommando, eller en variabel, 143 00:07:05,500 --> 00:07:09,520 kallas x, och tilldela det den gula bit kod där. 144 00:07:09,520 --> 00:07:14,040 Det kan vara något i stil med "eko Hej "eller" säger pip "eller något 145 00:07:14,040 --> 00:07:15,120 besläktad med det. 146 00:07:15,120 --> 00:07:17,780 Men märker om dina ögon vandra längre till höger, 147 00:07:17,780 --> 00:07:22,150 det finns mer till denna linje än precis i slutet av den semikolon. 148 00:07:22,150 --> 00:07:25,160 "Echo sårbar" och sedan utöver att det finns ännu mer. 149 00:07:25,160 --> 00:07:26,530 En annan semikolon, våldsamt slag -c :. 150 00:07:26,530 --> 00:07:28,120 151 00:07:28,120 --> 00:07:34,050 >> Så lång historia kort, här kodraden är 152 00:07:34,050 --> 00:07:36,660 tillräcklig för tvingande en dator som är 153 00:07:36,660 --> 00:07:39,830 sårbara för att göra något som du vill att den ska göra, 154 00:07:39,830 --> 00:07:44,290 eftersom det finns en bugg i Bash vari även om Bash var tänkt att sluta 155 00:07:44,290 --> 00:07:48,980 läser rader av kommandorätt där efter den gula texten, 156 00:07:48,980 --> 00:07:52,520 för en 20-plus år gamla bugg, Bash har faktiskt varit läsning 157 00:07:52,520 --> 00:07:56,780 utöver detta semikolon och ganska mycket gör vad den blir tillsagd. 158 00:07:56,780 --> 00:07:59,070 >> Så vad är innebörden av att i slutändan? 159 00:07:59,070 --> 00:08:01,340 Jag sa bara "echo hello" eller "echo sårbara" 160 00:08:01,340 --> 00:08:05,449 men vad händer om du gjorde något faktiskt skadligt, liksom rm -rf *, 161 00:08:05,449 --> 00:08:07,240 som du kanske inte någonsin skrivit förut, 162 00:08:07,240 --> 00:08:08,920 och ärligt talat du förmodligen bör inte för tidigt, 163 00:08:08,920 --> 00:08:10,700 eftersom du kan göra en raddaskada med den. 164 00:08:10,700 --> 00:08:11,210 Varför? 165 00:08:11,210 --> 00:08:12,990 rm gör vad, förstås? 166 00:08:12,990 --> 00:08:14,270 Avlägsnar. 167 00:08:14,270 --> 00:08:15,930 * Betyder vad? 168 00:08:15,930 --> 00:08:16,430 Alla. 169 00:08:16,430 --> 00:08:18,180 Så det är en så kallad joker, så innebär det 170 00:08:18,180 --> 00:08:20,410 ta bort allt i den aktuella katalogen. 171 00:08:20,410 --> 00:08:23,379 -r råkar betyda rekursivt, vilket innebär att om det du tar bort 172 00:08:23,379 --> 00:08:26,420 är en katalog, och insidan av det är andra filer och andra kataloger, 173 00:08:26,420 --> 00:08:28,950 rekursivt dyka in där och ta bort allt detta. 174 00:08:28,950 --> 00:08:31,040 Och f är den värsta av dem alla. 175 00:08:31,040 --> 00:08:32,580 Någon som vet vad -f betyder här? 176 00:08:32,580 --> 00:08:33,690 177 00:08:33,690 --> 00:08:34,360 Force. 178 00:08:34,360 --> 00:08:37,830 Så tvinga sätt, till och med om detta är en dålig idé, 179 00:08:37,830 --> 00:08:40,939 göra det utan att fråga mig för ytterligare bekräftelse. 180 00:08:40,939 --> 00:08:43,230 Så, ni vet, skrattar vi på detta, men ärligt talat, jag förmodligen 181 00:08:43,230 --> 00:08:44,972 skriver detta flera gånger en dag, eftersom verkligheten 182 00:08:44,972 --> 00:08:47,210 är det är det snabbaste sättet att bort en hel massa grejer. 183 00:08:47,210 --> 00:08:48,590 Men även jag har gjort en del skada. 184 00:08:48,590 --> 00:08:53,100 >> Men om du skulle lura en dator till att definiera några dumma variabel 185 00:08:53,100 --> 00:08:56,810 eller funktion som kallas x, men sedan lura datorn i verkställande 186 00:08:56,810 --> 00:09:00,030 utanför gränserna för det funktion, utöver detta semikolon, 187 00:09:00,030 --> 00:09:04,430 du kan verkligen lura en dator till verkställande något liknande rm -rf 188 00:09:04,430 --> 00:09:07,810 eller E-post kommandot eller kommandot Kopiera. 189 00:09:07,810 --> 00:09:11,400 Allt bokstavligen kan du göra med dator, oavsett om det är att ta bort filer, 190 00:09:11,400 --> 00:09:15,350 skapa filer, spam någon, attackera någon server på distans, 191 00:09:15,350 --> 00:09:17,190 om du kan uttrycka det med ett kommando, du 192 00:09:17,190 --> 00:09:19,120 kan lura en dator till att göra det. 193 00:09:19,120 --> 00:09:21,510 >> Nu vad är ett exempel på hur du kan göra detta? 194 00:09:21,510 --> 00:09:24,300 Tja, det finns en hel del datorer på internet kör Bash. 195 00:09:24,300 --> 00:09:26,390 Alla av oss Mac-användare är bland dem. 196 00:09:26,390 --> 00:09:30,390 Många Linux-servrar är bland dem också, och Unix-servrar. 197 00:09:30,390 --> 00:09:32,630 Windows igen blir relativt undan 198 00:09:32,630 --> 00:09:34,590 om du inte har installerat särskild programvara. 199 00:09:34,590 --> 00:09:37,130 Nu har en hel del servrar, för Exempelvis köra webbservrar, 200 00:09:37,130 --> 00:09:39,840 och i själva verket Linux är kanske den mest populära operativsystem 201 00:09:39,840 --> 00:09:43,060 att köras på datorer på internet som betjänar upp webbsidor. 202 00:09:43,060 --> 00:09:44,910 Nu när vi får se senare i terminen, då 203 00:09:44,910 --> 00:09:48,470 du skickar en begäran från din browser-- Chrome, 204 00:09:48,470 --> 00:09:50,790 Internet Explorer, whatever-- till en fjärrserver, 205 00:09:50,790 --> 00:09:53,730 det visar sig att även om du just skrev www.example.com, 206 00:09:53,730 --> 00:09:59,590 din webbläsare sänder ett meddelande det är lite mer svårbegripliga, som den här. 207 00:09:59,590 --> 00:10:01,239 >> Men märker lite något konstigt. 208 00:10:01,239 --> 00:10:03,030 De två första raderna Jag har aldrig sett förut, 209 00:10:03,030 --> 00:10:04,904 men de ser inte särskilt hotfullt. 210 00:10:04,904 --> 00:10:08,030 Men lägg märke till vad jag har stulit för tredje raden här. 211 00:10:08,030 --> 00:10:13,390 Om ett dåligt killen var att skicka ett meddelande så här från sin dator 212 00:10:13,390 --> 00:10:17,270 till en sårbar Mac eller sårbara Linux-server, 213 00:10:17,270 --> 00:10:21,580 det roliga är att Bash, det enkelt litet kommandotolk 214 00:10:21,580 --> 00:10:27,450 är allestädes närvarande och ofta vana vid att i huvudsak genomföra 215 00:10:27,450 --> 00:10:30,020 innehållet i en budskap som den tar emot. 216 00:10:30,020 --> 00:10:33,490 Och med den logiken kan du lura en webbserver därför 217 00:10:33,490 --> 00:10:36,370 genom att skicka något som User-Agent, som vanligtvis 218 00:10:36,370 --> 00:10:38,300 är tänkt att säga namn i din webbläsare. 219 00:10:38,300 --> 00:10:42,420 User-Agent Chrome, User-Agent Internet Explorer, User-Agent Firefox, detta 220 00:10:42,420 --> 00:10:44,590 är bara webbläsarens sätt att identifiera sig. 221 00:10:44,590 --> 00:10:46,605 Men om en dålig kille mycket skickligt säger, mm-mm, jag är 222 00:10:46,605 --> 00:10:47,930 inte kommer att berätta vad min webbläsare är, 223 00:10:47,930 --> 00:10:50,888 Jag stället kommer att skicka dig här kryptiskt utseende sak med rm -rf 224 00:10:50,888 --> 00:10:55,840 * I det, kan du bokstavligen lura en sårbar webbserver på Internet 225 00:10:55,840 --> 00:10:59,055 till verkställande just det i där för att ta bort alla filer. 226 00:10:59,055 --> 00:11:00,930 Och ärligt talat, det är inte även de värsta. 227 00:11:00,930 --> 00:11:01,763 Du kan göra vad som helst. 228 00:11:01,763 --> 00:11:04,480 Du kan starta en distribuerad överbelastningsattack 229 00:11:04,480 --> 00:11:07,030 om du skickade detta meddelande till Hela knippen av webbservrar 230 00:11:07,030 --> 00:11:10,256 och sedan hade dem alla ner, för exempel på Harvard.edu servrar, 231 00:11:10,256 --> 00:11:12,130 och du kan sortera på bang heck av dem 232 00:11:12,130 --> 00:11:15,490 av en nätverkstrafik som var annars utlöses av denna skurk. 233 00:11:15,490 --> 00:11:18,760 >> Så lång historia kort, nästan alla i det här rummet som äger en Mac 234 00:11:18,760 --> 00:11:20,240 är utsatta för detta. 235 00:11:20,240 --> 00:11:24,100 Den guldkant är att om du inte är kör en webbserver på din bärbara dator, 236 00:11:24,100 --> 00:11:27,780 och om du inte har faktiskt konfigurerat det att låta något i stil med SSH in i det, 237 00:11:27,780 --> 00:11:28,670 du är faktiskt säker. 238 00:11:28,670 --> 00:11:31,710 Det är sårbart, men det finns ingen man försöker komma in i din bärbara dator, 239 00:11:31,710 --> 00:11:33,290 så du kan sorts vara säker. 240 00:11:33,290 --> 00:11:36,210 Men Apple kommer snart att uppdatera en fix för detta. 241 00:11:36,210 --> 00:11:39,660 I världen av Linux har redan släppt ett antal korrigeringar för Fedora och Ubuntu 242 00:11:39,660 --> 00:11:43,790 och andra versioner av Linux, och faktiskt om du kör uppdateringen 50 i apparaten, 243 00:11:43,790 --> 00:11:45,930 även det kommer också att vara uppdateras och korrigeras. 244 00:11:45,930 --> 00:11:47,764 Men även detta har inte verkligen varit utsatta, 245 00:11:47,764 --> 00:11:49,804 för om du har mixtrar med apparaten 246 00:11:49,804 --> 00:11:52,770 och gjort din bärbara dator för allmänheten tillgängliga på Internet, vilket inte är 247 00:11:52,770 --> 00:11:54,910 som standard, du har faktiskt varit bra eftersom 248 00:11:54,910 --> 00:11:56,890 av brandvägg och andra tekniker. 249 00:11:56,890 --> 00:12:01,000 >> Men det är ett extremt exempel på en bugg som vi har bott för bokstavligen 20 250 00:12:01,000 --> 00:12:04,050 år, och vem vet om någon hela denna tid har vetat om det? 251 00:12:04,050 --> 00:12:06,300 Och i själva verket är detta en av de grundläggande utmaningarna 252 00:12:06,300 --> 00:12:08,690 att vi får se senare i termin om säkerhet, 253 00:12:08,690 --> 00:12:13,020 är att precis som i den verkliga världen, de goda är på underläge. 254 00:12:13,020 --> 00:12:16,500 För att hålla skurkarna ut, vi måste se till att varje dörr är låst, 255 00:12:16,500 --> 00:12:20,340 att alla fönster är säker, att varje punkt träder i ett hem 256 00:12:20,340 --> 00:12:21,980 är säkert att hålla skurkarna ut. 257 00:12:21,980 --> 00:12:26,870 Men vad gör den onde måste göra för att faktiskt äventyra ditt hem 258 00:12:26,870 --> 00:12:28,200 och stjäla från dig? 259 00:12:28,200 --> 00:12:32,574 Han eller hon har bara att hitta en olåst dörr, en krossat fönster, eller något 260 00:12:32,574 --> 00:12:35,240 i denna riktning, och det är den Samma sak i datasäkerhet. 261 00:12:35,240 --> 00:12:37,660 Vi kan skriva miljontals rader programkod 262 00:12:37,660 --> 00:12:40,570 och spendera hundratals eller tusentals timmar att försöka få det rätt, 263 00:12:40,570 --> 00:12:43,370 men om du gör bara en fel i korrekthet, 264 00:12:43,370 --> 00:12:47,030 du kan sätta hela systemet och faktiskt i detta fall hela internet 265 00:12:47,030 --> 00:12:48,660 och världen i fara. 266 00:12:48,660 --> 00:12:51,950 >> Så om du vill veta mer om detta, gå till denna URL här. 267 00:12:51,950 --> 00:12:54,450 Det finns inget behov av åtgärder ikväll om du inte är 268 00:12:54,450 --> 00:12:57,116 bland dem bekvämare att har varit igång en egen web 269 00:12:57,116 --> 00:12:59,810 server, i vilket fall du bör, faktiskt, uppdatera programvaran. 270 00:12:59,810 --> 00:13:03,244 >> Och även detta är titeln på ett tal, och nu ett papper, 271 00:13:03,244 --> 00:13:05,410 att vi har länkat på kursens hemsida i dag. 272 00:13:05,410 --> 00:13:07,600 Det var av en kollega vid namn Ken Thompson, som 273 00:13:07,600 --> 00:13:10,120 var att acceptera en mycket berömd utmärkelse i datavetenskap, 274 00:13:10,120 --> 00:13:13,495 och han gav detta tal några år sedan, huvudsakligen på samma ämne. 275 00:13:13,495 --> 00:13:18,250 276 00:13:18,250 --> 00:13:20,520 Begärt folks frågan, bör du verkligen 277 00:13:20,520 --> 00:13:23,480 förtroende, slutligen, program du har fått? 278 00:13:23,480 --> 00:13:26,100 Till exempel har vi alla skrivit program, 279 00:13:26,100 --> 00:13:27,820 och vi har sammanställt dem med klang. 280 00:13:27,820 --> 00:13:31,830 Och för din kunskap, du har skrivit något program för CS50 där det finns 281 00:13:31,830 --> 00:13:35,310 en bakdörr av slag, finns det en väg att en dålig kille, om att köra ditt program, 282 00:13:35,310 --> 00:13:37,410 kan ta över din dator? 283 00:13:37,410 --> 00:13:38,310 Antagligen inte, eller hur? 284 00:13:38,310 --> 00:13:40,180 Mario och Greedy och kredit. 285 00:13:40,180 --> 00:13:41,680 Dessa är alla ganska små program. 286 00:13:41,680 --> 00:13:43,910 Du skulle behöva vara ganska dåligt om du verkligen 287 00:13:43,910 --> 00:13:47,310 gjorde hela datorn sårbar efter att ha skrivit 10 eller 20 rader kod, 288 00:13:47,310 --> 00:13:49,690 eller åtminstone omedvetna om några av de konsekvenser för säkerheten. 289 00:13:49,690 --> 00:13:52,023 Nu säger jag det skämt, men vi kommer att se i dag 290 00:13:52,023 --> 00:13:54,600 och den här veckan är det faktiskt riktigt, riktigt enkelt 291 00:13:54,600 --> 00:13:57,980 att vara dåligt och göra ännu korta program sårbara. 292 00:13:57,980 --> 00:14:02,880 >> Men för nu, åtminstone, inser att frågan ställs här 293 00:14:02,880 --> 00:14:04,850 är ca klang i en kompilator. 294 00:14:04,850 --> 00:14:08,360 Varför har vi litar Clang under de senaste två eller tre veckor? 295 00:14:08,360 --> 00:14:12,650 Vem säger att den som skrev Clang hade inte en "om" tillståndet i det 296 00:14:12,650 --> 00:14:17,680 som i huvudsak injicerade några nollor och ettor i varje program är samman 297 00:14:17,680 --> 00:14:21,180 som skulle låta honom eller henne åtkomst datorn när du sover 298 00:14:21,180 --> 00:14:23,580 och din bärbara dator locket är öppet och datorn är igång? 299 00:14:23,580 --> 00:14:24,080 Rätt? 300 00:14:24,080 --> 00:14:28,350 Vi har denna typ av ära system rätten Nu när vi litar på att Clang är legit. 301 00:14:28,350 --> 00:14:30,000 Du litar på att produkten är legit. 302 00:14:30,000 --> 00:14:34,430 Du litar på att bokstavligen varje program på din Mac eller PC är pålitlig. 303 00:14:34,430 --> 00:14:37,510 Och eftersom denna enkla bugg antyder, även om det inte är skadligt, 304 00:14:37,510 --> 00:14:40,580 det är absolut inte sannolikt att vara fallet. 305 00:14:40,580 --> 00:14:42,350 >> Så du bör vara rädd som fan. 306 00:14:42,350 --> 00:14:45,560 Ärligt talat, det finns ingen enkel lösning på detta andra 307 00:14:45,560 --> 00:14:48,185 än ett slags samhällelig medvetenhet av den ökande komplexiteten 308 00:14:48,185 --> 00:14:50,310 att vi bygger på toppen i våra datasystem, 309 00:14:50,310 --> 00:14:53,740 och hur allt mer sårbara Vi kan mycket väl vara. 310 00:14:53,740 --> 00:14:55,570 >> Nu med det sagt, Breakout. 311 00:14:55,570 --> 00:14:59,889 Så Breakout är problemet set tre, och Breakout är ett spel från förr 312 00:14:59,889 --> 00:15:02,180 att du kanske kommer ihåg, men för oss i problem set tre, 313 00:15:02,180 --> 00:15:04,450 Det ger oss möjlighet att ta saker backa upp ett pinnhål 314 00:15:04,450 --> 00:15:08,880 så att när vi skriver program, även i ett terminalfönster som denna, 315 00:15:08,880 --> 00:15:14,670 vi faktiskt kan köras, i slutändan, grafiska program inte 316 00:15:14,670 --> 00:15:17,800 till skillnad från dem som vi hade tillgång till i Scratch. 317 00:15:17,800 --> 00:15:20,910 Så detta är personalens genomförande av breakout, 318 00:15:20,910 --> 00:15:23,930 vilket är just detta tegel-breaking spel, att du flyttar paddeln tillbaka 319 00:15:23,930 --> 00:15:27,590 och tillbaka, och du träffar bollen mot de färgade tegelstenar upp överst. 320 00:15:27,590 --> 00:15:30,020 Så det här är att föra oss slags tillbaka till där 321 00:15:30,020 --> 00:15:33,180 vi kunde vara mycket snabbt Scratch, och nu med C, 322 00:15:33,180 --> 00:15:35,800 genomföra våra egna grafiska användargränssnitt. 323 00:15:35,800 --> 00:15:38,960 >> Men mer än så, det här Problemet set är det första 324 00:15:38,960 --> 00:15:41,000 där vi ger du en massa kod. 325 00:15:41,000 --> 00:15:43,940 Och faktiskt, jag tar explicit uppmärksamhet åt detta, eftersom framför allt 326 00:15:43,940 --> 00:15:47,090 för de mindre bekväm, detta problembild, åtminstone vid första anblicken, 327 00:15:47,090 --> 00:15:49,170 kommer att känna sig som Vi har tagit upp ett hack. 328 00:15:49,170 --> 00:15:51,540 Eftersom vi har gett dig, för en del av sökandet 329 00:15:51,540 --> 00:15:54,930 och sorteringsproblem i pset, ett gäng kod som vi skrev, 330 00:15:54,930 --> 00:15:56,680 och ett par kommentarer som säger "att göra" 331 00:15:56,680 --> 00:15:58,221 där du måste fylla i tomrummen. 332 00:15:58,221 --> 00:16:00,020 Så inte alltför skrämmande, men det är första gången 333 00:16:00,020 --> 00:16:03,370 vi lämna du kod som du behöver först läsa, förstå och sedan lägga till 334 00:16:03,370 --> 00:16:04,290 och slutföra det. 335 00:16:04,290 --> 00:16:05,940 >> Och sedan med Breakout, vi kommer att göra samma sak, 336 00:16:05,940 --> 00:16:08,740 vilket ger dig ett tiotal fler linjer kod som, ärligt talat, ger dig 337 00:16:08,740 --> 00:16:11,490 en hel del av ramverket för spelet men sluta kort 338 00:16:11,490 --> 00:16:14,304 genomföra blocken och bollen och paddel, 339 00:16:14,304 --> 00:16:15,970 men vi genomför en del andra funktioner. 340 00:16:15,970 --> 00:16:18,280 Och även att det vid första anblicken, återigen, särskilt om mindre bekväm, 341 00:16:18,280 --> 00:16:21,480 kan tyckas särskilt skrämmande och du att det finns så många nya funktioner 342 00:16:21,480 --> 00:16:24,070 du behöver för att linda ditt sinne runt, och det är sant. 343 00:16:24,070 --> 00:16:26,281 Men kom ihåg, det är riktigt gillar Scratch. 344 00:16:26,281 --> 00:16:28,780 Oddsen är att du inte använder alla pusselbitarna i Scratch. 345 00:16:28,780 --> 00:16:31,120 Oddsen är att du inte bryr dig att linda ditt sinne runt dem alla 346 00:16:31,120 --> 00:16:33,617 eftersom alla tog det var en snabb blick för att förstå, åh, 347 00:16:33,617 --> 00:16:35,450 det är vad jag kan göra med den pusselbit. 348 00:16:35,450 --> 00:16:38,260 Och faktiskt, i problembild 3 spec, vi peka dig 349 00:16:38,260 --> 00:16:41,370 på den dokumentation som kommer presentera ett antal nya funktioner, 350 00:16:41,370 --> 00:16:43,570 och slutligen programmeringen konstruerar du använder. 351 00:16:43,570 --> 00:16:47,610 Villkor, loopar, variabler och funktioner 352 00:16:47,610 --> 00:16:50,720 kommer att ha samma vad vi har sett hittills. 353 00:16:50,720 --> 00:16:53,560 >> Så ja, vad vi ska ge du är en del exempelkod som 354 00:16:53,560 --> 00:16:56,110 kan du skapa ett fönster som ser inte olik denna, 355 00:16:56,110 --> 00:16:59,540 och i slutändan göra det till något ganska så här. 356 00:16:59,540 --> 00:17:02,250 Så dra nytta av CS50, diskutera kontorstid och mer, 357 00:17:02,250 --> 00:17:05,290 och ta tröst i det faktum att mängden kod som du måste skriva 358 00:17:05,290 --> 00:17:06,760 är faktiskt inte så mycket. 359 00:17:06,760 --> 00:17:10,359 Den första utmaningen är bara att vänja själv till en del kod som vi har skrivit. 360 00:17:10,359 --> 00:17:11,450 361 00:17:11,450 --> 00:17:15,810 >> Har du frågor om pset3, Shellshock, eller på annat sätt? 362 00:17:15,810 --> 00:17:19,226 >> PUBLIK: Det verkade som går igenom med Bryt 363 00:17:19,226 --> 00:17:22,154 att koden är nästan en objektorienterad stil, 364 00:17:22,154 --> 00:17:24,675 men jag tyckte C var en objektorienterat program. 365 00:17:24,675 --> 00:17:26,050 SPEAKER 1: En utmärkt fråga. 366 00:17:26,050 --> 00:17:28,258 Så titta igenom distributions kod, koden 367 00:17:28,258 --> 00:17:30,180 Vi skrev för pset3, för dem som är bekanta, det 368 00:17:30,180 --> 00:17:32,230 ser ut som det är en litet objektorienterat. 369 00:17:32,230 --> 00:17:33,800 Kort svar är, det är. 370 00:17:33,800 --> 00:17:38,130 Det är en uppskattning av hur ni kan göra objektorienterad kod med 371 00:17:38,130 --> 00:17:41,850 ett språk som C, men det är fortfarande ytterst procedur. 372 00:17:41,850 --> 00:17:44,900 Det finns inga metoder inuti variablerna, som du ser. 373 00:17:44,900 --> 00:17:46,180 Men det påminner om det. 374 00:17:46,180 --> 00:17:48,780 Och vi får se den funktionen igen när vi kommer till PHP och JavaScript 375 00:17:48,780 --> 00:17:49,946 mot slutet av terminen. 376 00:17:49,946 --> 00:17:53,667 Men för nu, se det som en antydan om vad som komma skall. 377 00:17:53,667 --> 00:17:54,250 Bra fråga. 378 00:17:54,250 --> 00:17:56,051 379 00:17:56,051 --> 00:17:56,550 Okej. 380 00:17:56,550 --> 00:17:59,730 Så slå samman sort var hur vi vänster saker förra gången. 381 00:17:59,730 --> 00:18:03,250 Och slå samman sort var svalt i meningen att det var så mycket snabbare, 382 00:18:03,250 --> 00:18:07,100 åtminstone på grundval av de ytliga tester vi gjorde förra veckan, än, säg, bubbla 383 00:18:07,100 --> 00:18:08,710 sortera, urval sort, inser sort. 384 00:18:08,710 --> 00:18:11,780 Och vad som var snyggt också är bara hur koncist och snyggt 385 00:18:11,780 --> 00:18:12,810 du kan uttrycka det. 386 00:18:12,810 --> 00:18:15,840 Och vad gjorde vi säger att det var en övre bundet på speltid för merge 387 00:18:15,840 --> 00:18:16,340 sortera? 388 00:18:16,340 --> 00:18:17,633 389 00:18:17,633 --> 00:18:18,495 Yeah? 390 00:18:18,495 --> 00:18:19,360 >> PUBLIK: n log n? 391 00:18:19,360 --> 00:18:20,819 >> SPEAKER 1: n log n, rätt. n log n. 392 00:18:20,819 --> 00:18:23,776 Och vi ska återkomma till vad det egentligen betyder eller var det kommer ifrån, 393 00:18:23,776 --> 00:18:25,570 men detta var bättre än vad gångtid 394 00:18:25,570 --> 00:18:28,440 som vi såg för bubbla urval och inför sort? 395 00:18:28,440 --> 00:18:30,610 Så n kvadrat. n squared är större än så här, 396 00:18:30,610 --> 00:18:34,650 och även om det inte är uppenbart, vet att log n är mindre än n, 397 00:18:34,650 --> 00:18:36,910 så om du gör n gånger något mindre än n, 398 00:18:36,910 --> 00:18:38,680 det kommer att vara mindre än n kvadrat. 399 00:18:38,680 --> 00:18:40,130 Det är lite av intuition där. 400 00:18:40,130 --> 00:18:42,190 Men vi betalade ett pris för detta. 401 00:18:42,190 --> 00:18:47,000 Det var snabbare, men ett tema som startade växa fram i förra veckan var denna avvägning. 402 00:18:47,000 --> 00:18:49,804 Jag fick bättre prestanda tidsmässigt, men vad 403 00:18:49,804 --> 00:18:52,470 jag har att spendera på den andra sidan, för att uppnå det? 404 00:18:52,470 --> 00:18:53,591 >> PUBLIKEN: Minne. 405 00:18:53,591 --> 00:18:54,465 SPEAKER 1: Säg igen? 406 00:18:54,465 --> 00:18:55,173 PUBLIKEN: Minne. 407 00:18:55,173 --> 00:18:57,040 SPEAKER 1: Minne, eller space mer allmänt. 408 00:18:57,040 --> 00:18:59,040 Och det var inte super självklart med våra människor, 409 00:18:59,040 --> 00:19:02,240 men minns att våra volontärer stega framåt och kliva 410 00:19:02,240 --> 00:19:04,780 tillbaka som om det finns en matris här, och som om det inte finns 411 00:19:04,780 --> 00:19:07,130 en andra matris här att de kunde använda, eftersom vi 412 00:19:07,130 --> 00:19:09,080 behövs någonstans att slå ihop dessa folks. 413 00:19:09,080 --> 00:19:11,480 Vi kunde inte bara byta dem på plats. 414 00:19:11,480 --> 00:19:13,800 Så sammanfoga sortera hävstångs finns mer utrymme, vilket 415 00:19:13,800 --> 00:19:15,620 Vi behövde inte med de andra algoritmerna, 416 00:19:15,620 --> 00:19:17,410 men uppåtsidan är att det är mycket snabbare. 417 00:19:17,410 --> 00:19:20,780 Och ärligt talat, i den verkliga världen utrymme dessa dagar-- RAM, hårddisk space-- 418 00:19:20,780 --> 00:19:25,030 är relativt billigt, och så det är inte nödvändigtvis en dålig sak. 419 00:19:25,030 --> 00:19:28,320 >> Så låt oss ta en snabb titt, lite mer metodiskt, på vad vi gjorde 420 00:19:28,320 --> 00:19:30,220 och varför vi sa att det låg n log n. 421 00:19:30,220 --> 00:19:33,260 Så här är de åtta siffror och åtta volontärer som vi hade förra gången. 422 00:19:33,260 --> 00:19:35,718 Och det första som Merge Sortera sa åt oss att göra var det? 423 00:19:35,718 --> 00:19:37,010 424 00:19:37,010 --> 00:19:38,010 PUBLIK: Dela i två delar. 425 00:19:38,010 --> 00:19:38,663 SPEAKER 1: Säg igen? 426 00:19:38,663 --> 00:19:39,650 PUBLIK: Dela i två delar. 427 00:19:39,650 --> 00:19:40,610 SPEAKER 1: Dela i två, eller hur. 428 00:19:40,610 --> 00:19:42,818 Det påminner mycket om telefonboken, om klyftan 429 00:19:42,818 --> 00:19:44,220 och erövra mer allmänt. 430 00:19:44,220 --> 00:19:45,640 Så vi tittade på den vänstra halvan. 431 00:19:45,640 --> 00:19:48,700 Och sedan när vi sa, sortera den vänstra halvan av elementen, 432 00:19:48,700 --> 00:19:49,690 vad gjorde vi nästa säga? 433 00:19:49,690 --> 00:19:51,210 434 00:19:51,210 --> 00:19:54,860 Sortera den vänstra halvan av det vänstra hälften, som tillät oss att, 435 00:19:54,860 --> 00:19:57,570 efter att dela i två delar, fokusera på fyra och två. 436 00:19:57,570 --> 00:20:01,280 >> Hur kan du sortera en lista nu, i gul, storlek två, använder Merge Sort? 437 00:20:01,280 --> 00:20:02,330 438 00:20:02,330 --> 00:20:04,580 Tja dela den på mitten, och sortera den vänstra halvan. 439 00:20:04,580 --> 00:20:07,100 Och det var där saker fick lite dum kort. 440 00:20:07,100 --> 00:20:10,720 Hur kan du sortera en lista som är över storlek ett, som den här nummer fyra här? 441 00:20:10,720 --> 00:20:12,330 442 00:20:12,330 --> 00:20:13,210 Den är sorterade. 443 00:20:13,210 --> 00:20:14,200 Du är klar. 444 00:20:14,200 --> 00:20:17,300 >> Men hur gör du sortera en lista med storlek en när det är nummer två? 445 00:20:17,300 --> 00:20:21,640 Jo, samma sak, men nu vad var tredje och viktigt steg i Merge Sort? 446 00:20:21,640 --> 00:20:24,020 Du var tvungen att slå ihop vänster halva och den högra halvan. 447 00:20:24,020 --> 00:20:26,580 Och när vi gjorde det, vi såg klockan fyra, vi tittade på två. 448 00:20:26,580 --> 00:20:28,750 Vi bestämde okej, uppenbarligen två kommer först, 449 00:20:28,750 --> 00:20:31,840 så vi satte två i sin ställe, följt av fyra. 450 00:20:31,840 --> 00:20:35,010 Och nu måste du sorts spola tillbaka, och detta är typ av egenskap 451 00:20:35,010 --> 00:20:37,570 av en algoritm som Merge Sortera, spola tillbaka i minnet. 452 00:20:37,570 --> 00:20:40,240 Vad var nästa rad av historien? 453 00:20:40,240 --> 00:20:41,780 Vad ska jag fokusera på nästa? 454 00:20:41,780 --> 00:20:43,110 455 00:20:43,110 --> 00:20:47,350 Den högra halvan av den vänstra hälften, vilket är sex och åtta. 456 00:20:47,350 --> 00:20:50,320 >> Så låt mig bara gå igenom det här utan belaboring poängen för mycket. 457 00:20:50,320 --> 00:20:53,330 Sex och åtta, då sex är sorterade åtta sorteras. 458 00:20:53,330 --> 00:20:57,190 Slå ihop ihop dem så där, och nu nästa stora steg 459 00:20:57,190 --> 00:21:00,990 är, naturligtvis, sortera den högra halvan från det allra första steget i denna algoritm. 460 00:21:00,990 --> 00:21:02,870 Så vi fokuserar på en, tre, sju, fem. 461 00:21:02,870 --> 00:21:04,540 Vi fokuserar då på den vänstra halvan. 462 00:21:04,540 --> 00:21:09,400 Den vänstra halvan av denna, den högra halvan av det, och sedan slå ihop i ett och tre. 463 00:21:09,400 --> 00:21:13,100 Då den högra halvan, sedan vänster halva av den, då den högra halvan av den. 464 00:21:13,100 --> 00:21:15,985 Slå ihop det, och nu vad steget återstår? 465 00:21:15,985 --> 00:21:18,040 466 00:21:18,040 --> 00:21:22,460 Slå ihop den stora vänstra halvan och den stora högra halvan, så man går ner där, 467 00:21:22,460 --> 00:21:27,330 sedan två, sedan tre, sedan fyra, sedan fem, sedan sex, sedan sju, sedan åtta. 468 00:21:27,330 --> 00:21:31,990 >> Så nu varför är det i slutändan avslöja, särskilt om n och logaritmer mer 469 00:21:31,990 --> 00:21:35,487 allmänhet hellre fly dig, åtminstone i de senaste minne? 470 00:21:35,487 --> 00:21:37,070 Tja, märker höjden på denna sak. 471 00:21:37,070 --> 00:21:41,230 Vi hade åtta delar, och vi delade det med två, med två, med två. 472 00:21:41,230 --> 00:21:44,590 Så log bas två av åtta ger oss tre. 473 00:21:44,590 --> 00:21:45,640 474 00:21:45,640 --> 00:21:48,540 Och lita på mig, att om lite oklar på det. 475 00:21:48,540 --> 00:21:54,710 Men log bas två av åtta är tre, så vi har gjort tre lager av sammanslagning. 476 00:21:54,710 --> 00:21:57,170 Och när vi gick samman element, hur många element 477 00:21:57,170 --> 00:21:58,950 vi tittar på var och en av dessa rader? 478 00:21:58,950 --> 00:22:00,212 479 00:22:00,212 --> 00:22:01,437 Sammanlagt n, eller hur? 480 00:22:01,437 --> 00:22:04,020 Eftersom att slå samman den översta raden, även om vi gjorde det bit för bit, 481 00:22:04,020 --> 00:22:05,990 vi slutligen rörd varje nummer en gång. 482 00:22:05,990 --> 00:22:09,054 Och i den andra raden, till slå ihop dessa listor i storlek två, 483 00:22:09,054 --> 00:22:10,470 vi hade att röra varje element gång. 484 00:22:10,470 --> 00:22:12,690 Och då här egentligen tydligt i den sista raden, 485 00:22:12,690 --> 00:22:15,430 vi hade att röra var och en av dem element en gång, men bara en gång, 486 00:22:15,430 --> 00:22:18,400 så här ligger alltså vår n log n. 487 00:22:18,400 --> 00:22:21,780 >> Och nu bara för att göra saker lite mer formellt för bara ett ögonblick, om du 488 00:22:21,780 --> 00:22:24,260 skulle nu analysera denna vid ett slags högre nivå 489 00:22:24,260 --> 00:22:28,340 och försöker bestämma, väl hur kanske du går om att uttrycka 490 00:22:28,340 --> 00:22:31,780 speltid för denna algoritm bara genom att titta på det och inte 491 00:22:31,780 --> 00:22:33,590 genom användning av en contrived exempel? 492 00:22:33,590 --> 00:22:36,590 Nå, hur mycket tid skulle du säga en steg så här i gult skulle ta, 493 00:22:36,590 --> 00:22:37,173 Om n <2 retur? 494 00:22:37,173 --> 00:22:38,840 495 00:22:38,840 --> 00:22:39,830 Det är en stor o för vad? 496 00:22:39,830 --> 00:22:41,450 497 00:22:41,450 --> 00:22:44,540 Så jag ser en, så ett steg, kanske två steg eftersom det är om 498 00:22:44,540 --> 00:22:47,110 och sedan återvända, men det är konstant tid, eller hur? 499 00:22:47,110 --> 00:22:49,960 Så vi sa O (1), och det är hur jag ska uttrycka detta. 500 00:22:49,960 --> 00:22:51,480 T, bara vara gångtid. 501 00:22:51,480 --> 00:22:54,150 n är storleken på den ingående, så T (n), bara ett finare sätt 502 00:22:54,150 --> 00:22:56,330 att säga driften tiden given ingång storlek n 503 00:22:56,330 --> 00:23:00,220 kommer att vara i storleksordningen av konstant tid, i O (1). 504 00:23:00,220 --> 00:23:01,970 >> Men annars, hur är det här? 505 00:23:01,970 --> 00:23:05,660 Hur skulle du uttrycka gångtid för denna gula linjen? 506 00:23:05,660 --> 00:23:06,250 T om vad? 507 00:23:06,250 --> 00:23:09,440 508 00:23:09,440 --> 00:23:12,665 Du kan slags fuska här och svara på min fråga cykliskt. 509 00:23:12,665 --> 00:23:14,770 510 00:23:14,770 --> 00:23:17,900 Så om drifttid i allmänhet vi bara säga är T (n). 511 00:23:17,900 --> 00:23:18,950 512 00:23:18,950 --> 00:23:22,490 Och nu är du typ av punting här och säga, ja, bara sortera den vänstra halvan, 513 00:23:22,490 --> 00:23:23,920 och sedan sortera den högra halvan. 514 00:23:23,920 --> 00:23:27,520 Hur kan vi symboliskt speltid för denna gula linjen? 515 00:23:27,520 --> 00:23:28,020 T om vad? 516 00:23:28,020 --> 00:23:29,360 Vad är storleken på ingång? 517 00:23:29,360 --> 00:23:30,510 518 00:23:30,510 --> 00:23:31,057 n över två. 519 00:23:31,057 --> 00:23:32,140 Varför inte jag bara säga att? 520 00:23:32,140 --> 00:23:36,449 Och då är en annan T (n / 2) och sedan igen, om jag slå ihop två sorterade halvor, 521 00:23:36,449 --> 00:23:38,615 hur många element kommer jag att behöva röra totalt? 522 00:23:38,615 --> 00:23:39,780 523 00:23:39,780 --> 00:23:40,320 n. 524 00:23:40,320 --> 00:23:42,790 Så jag kan uttrycka det, bara för att vara typ av infall, 525 00:23:42,790 --> 00:23:44,430 som gångtiden i allmänhet. 526 00:23:44,430 --> 00:23:51,140 T (n) är bara speltid för T (n / 2), plus T (n / 2), vänster halva och högra halvan, 527 00:23:51,140 --> 00:23:55,360 plus O (n), vilket troligen n steg, men kanske, om jag använder två fingrar, 528 00:23:55,360 --> 00:23:57,960 Det är dubbelt så många steg, men det är linjärt. 529 00:23:57,960 --> 00:24:00,440 Det är en del antal steg det är en faktor n, 530 00:24:00,440 --> 00:24:02,270 så vi skulle kunna uttrycka det som det här. 531 00:24:02,270 --> 00:24:05,550 Och det är här nu ska vi punt till baksidan av vår gymnasiet matte lärobok 532 00:24:05,550 --> 00:24:10,290 vi är att återfall i slutändan hamnar equaling detta, n gånger log n, 533 00:24:10,290 --> 00:24:12,530 om du verkligen gör ut matten mer formellt. 534 00:24:12,530 --> 00:24:13,950 >> Så det är bara två perspektiv. 535 00:24:13,950 --> 00:24:17,500 Ett numeriskt med en hårdkodad representativt exempel 536 00:24:17,500 --> 00:24:21,140 med hjälp av åtta siffror och en mer allmän titt på hur vi kom dit. 537 00:24:21,140 --> 00:24:25,670 Men det som är verkligt intressant här är, återigen, denna föreställning om cykling. 538 00:24:25,670 --> 00:24:26,900 Jag är inte använder för slingor. 539 00:24:26,900 --> 00:24:29,860 Jag slags definiera något i termer av sig själv, 540 00:24:29,860 --> 00:24:31,950 inte bara med detta matematisk funktion, 541 00:24:31,950 --> 00:24:34,860 utan också i fråga om denna pseudo-kod. 542 00:24:34,860 --> 00:24:38,260 Denna pseudokod är rekursiv i att två av dess linjer 543 00:24:38,260 --> 00:24:42,310 i huvudsak säga till den att gå använder sig för att lösa ett mindre 544 00:24:42,310 --> 00:24:45,400 Problemet med mindre storlek, och sedan igen och igen 545 00:24:45,400 --> 00:24:48,820 och igen tills vi tälja det ner till det så kallade referensscenariot. 546 00:24:48,820 --> 00:24:52,810 >> Så låt oss faktiskt dra en mer övertygande take-away från detta enligt följande. 547 00:24:52,810 --> 00:24:58,420 Låt mig gå in i gedit och ta en titta på några av dagens källkod, 548 00:24:58,420 --> 00:24:59,930 särskilt exemplet här. 549 00:24:59,930 --> 00:25:03,709 Sigma 0, som tydligen tillför siffrorna ett till n. 550 00:25:03,709 --> 00:25:05,750 Så låt oss se vad som är välbekant och obekanta här. 551 00:25:05,750 --> 00:25:08,690 Först har vi ett par innehåller, så inget nytt där. 552 00:25:08,690 --> 00:25:09,190 Prototype. 553 00:25:09,190 --> 00:25:11,370 Jag är lite oklar på detta efter några dagar, 554 00:25:11,370 --> 00:25:13,790 men vad gjorde vi säger en prototyp av en funktion är? 555 00:25:13,790 --> 00:25:15,099 556 00:25:15,099 --> 00:25:16,015 PUBLIK: [ohörbart]. 557 00:25:16,015 --> 00:25:16,905 SPEAKER 1: Vad är det? 558 00:25:16,905 --> 00:25:17,800 PUBLIK: Vi tillkännager det. 559 00:25:17,800 --> 00:25:18,883 SPEAKER 1: Vi tillkännage det. 560 00:25:18,883 --> 00:25:22,290 Så du undervisar Clang, hej, faktiskt genomföra detta ännu, 561 00:25:22,290 --> 00:25:25,740 men någonstans i den här filen, förmodligen, kommer att en funktion som kallas vad? 562 00:25:25,740 --> 00:25:26,930 563 00:25:26,930 --> 00:25:27,540 Sigma. 564 00:25:27,540 --> 00:25:30,540 Och detta är bara ett löfte som det kommer att se ut så här. 565 00:25:30,540 --> 00:25:33,720 Det kommer att ta ett heltal som input-- och jag kan bli tydligare 566 00:25:33,720 --> 00:25:36,570 och säga int n --and det är kommer att returnera en int, 567 00:25:36,570 --> 00:25:39,900 men semikolonmedel, mm, jag ska komma runt att genomföra detta lite senare. 568 00:25:39,900 --> 00:25:40,989 Återigen är Clang dum. 569 00:25:40,989 --> 00:25:43,280 Det kommer bara att veta vad du berättar det uppifrån och ned, 570 00:25:43,280 --> 00:25:45,765 så vi måste åtminstone ge det en antydan om vad som komma skall. 571 00:25:45,765 --> 00:25:47,330 >> Låt oss nu titta på huvud här. 572 00:25:47,330 --> 00:25:50,040 Låt oss bläddra ner här och se vad huvud gör. 573 00:25:50,040 --> 00:25:53,780 Det är inte så länge för en funktion, och i själva konstruktionen här är bekant. 574 00:25:53,780 --> 00:25:57,590 Jag deklarerar en variabel n, och sedan Jag tjata användaren och om igen 575 00:25:57,590 --> 00:26:01,880 för ett positivt heltal med hjälp getInt, och endast utträde ur denna slinga 576 00:26:01,880 --> 00:26:03,280 när användaren har uppfyllt. 577 00:26:03,280 --> 00:26:05,670 Gör Samtidigt har vi använt för att pester användaren på detta sätt. 578 00:26:05,670 --> 00:26:06,670 Nu är detta intressant. 579 00:26:06,670 --> 00:26:08,510 Jag förklarar en int som heter "svar." 580 00:26:08,510 --> 00:26:11,420 Jag tilldelar den returvärdet av en funktion som kallas "sigma". 581 00:26:11,420 --> 00:26:15,200 Jag vet inte vad det gör ännu, men Jag minns att förklara det för en stund sedan. 582 00:26:15,200 --> 00:26:18,310 Och då jag passerar i värde som användaren har skrivit in, n, 583 00:26:18,310 --> 00:26:20,420 och sedan rapporterar jag svaret. 584 00:26:20,420 --> 00:26:22,260 Bra låt oss rulla tillbaka för bara ett ögonblick. 585 00:26:22,260 --> 00:26:28,620 Låt oss gå vidare i den här katalogen, gör sigma 0, och faktiskt köra programmet 586 00:26:28,620 --> 00:26:30,490 och se vad som händer. 587 00:26:30,490 --> 00:26:35,930 Så om jag går vidare och kör detta program ./sigma-0, 588 00:26:35,930 --> 00:26:40,139 och jag skriver på ett positivt heltal som två, Sigma, 589 00:26:40,139 --> 00:26:43,180 som den grekiska symbolen antyder, är bara kommer att lägga upp alla nummer från 590 00:26:43,180 --> 00:26:44,320 noll på upp till två. 591 00:26:44,320 --> 00:26:46,560 Så 0 plus 1 plus 2. 592 00:26:46,560 --> 00:26:48,830 Så detta ska förhoppningsvis ge mig 3. 593 00:26:48,830 --> 00:26:49,750 Det är allt den gör. 594 00:26:49,750 --> 00:26:52,690 Och på samma sätt, om jag kör detta igen och jag ger det till nummer tre, 595 00:26:52,690 --> 00:26:56,721 det är 3 plus 2, så det är 5 plus 1 borde ge mig 6. 596 00:26:56,721 --> 00:26:59,470 Och sedan om jag blir riktigt galen och att skriva i större siffror, 597 00:26:59,470 --> 00:27:01,290 Det borde ge mig större och större summor. 598 00:27:01,290 --> 00:27:02,250 Så det är allt. 599 00:27:02,250 --> 00:27:04,010 >> Så vad gör sigma ut? 600 00:27:04,010 --> 00:27:05,430 Tja, det är ganska enkelt. 601 00:27:05,430 --> 00:27:08,940 Det är så vi kan ha genomfört detta för de senaste veckorna. 602 00:27:08,940 --> 00:27:11,120 "Int" kommer att vara den typ avkastning. 603 00:27:11,120 --> 00:27:14,330 Sigma är namnet, och det tar en variabel m istället för n. 604 00:27:14,330 --> 00:27:15,940 Jag ska ändra på det där uppe. 605 00:27:15,940 --> 00:27:17,340 Då är detta bara en sanity check. 606 00:27:17,340 --> 00:27:18,430 607 00:27:18,430 --> 00:27:19,950 Vi får se varför i ett ögonblick. 608 00:27:19,950 --> 00:27:24,220 Nu förklarar jag en annan variabel, summa, initiera den till noll. 609 00:27:24,220 --> 00:27:28,140 Sedan har jag här För loop iteration, uppenbarligen för tydlighet, 610 00:27:28,140 --> 00:27:33,810 från i = 1 på upp till en = m, vilket är vad användaren skrivit in, och sedan jag 611 00:27:33,810 --> 00:27:35,690 öka summan så här. 612 00:27:35,690 --> 00:27:37,360 Och sedan tillbaka summan. 613 00:27:37,360 --> 00:27:38,440 >> Så ett par frågor. 614 00:27:38,440 --> 00:27:42,370 Ett, jag hävdar i min kommentar att detta undviker risken för en oändlig slinga. 615 00:27:42,370 --> 00:27:45,620 Varför skulle passera på ett negativt tal framkalla, eventuellt, en oändlig loop? 616 00:27:45,620 --> 00:27:49,396 617 00:27:49,396 --> 00:27:51,290 >> PUBLIK: Du kommer aldrig att nå m. 618 00:27:51,290 --> 00:27:52,880 >> SPEAKER 1: når aldrig m. 619 00:27:52,880 --> 00:27:55,880 Men m förs in, så låt oss överväga ett enkelt exempel. 620 00:27:55,880 --> 00:27:58,510 Om m föres in av användaren som negativ en. 621 00:27:58,510 --> 00:28:00,059 Oavsett viktigaste. 622 00:28:00,059 --> 00:28:01,850 Huvud skyddar oss från detta också, så jag är bara 623 00:28:01,850 --> 00:28:04,680 vara riktigt anal med sigma att också se till 624 00:28:04,680 --> 00:28:06,540 att ingången inte kan vara negativ. 625 00:28:06,540 --> 00:28:10,130 Så om m är negativ, något negativt. 626 00:28:10,130 --> 00:28:11,930 Vad kommer att hända? 627 00:28:11,930 --> 00:28:14,390 Tja, jag går till få initialiseras till ett, 628 00:28:14,390 --> 00:28:19,060 och sedan jag kommer att bli mindre än eller lika med m? 629 00:28:19,060 --> 00:28:24,130 630 00:28:24,130 --> 00:28:24,765 >> Avvakta. 631 00:28:24,765 --> 00:28:26,930 632 00:28:26,930 --> 00:28:29,370 Det var-- låt oss inte, låt oss nix denna historia. 633 00:28:29,370 --> 00:28:32,780 Jag ville inte ställa den frågan, eftersom risken att jag syftar på 634 00:28:32,780 --> 00:28:38,360 kommer inte att hända eftersom jag är alltid kommer vara större than-- OK, 635 00:28:38,360 --> 00:28:39,871 Jag återkalla den frågan. 636 00:28:39,871 --> 00:28:40,370 OK. 637 00:28:40,370 --> 00:28:42,030 Låt oss bara fokusera på denna del här. 638 00:28:42,030 --> 00:28:44,210 639 00:28:44,210 --> 00:28:48,830 Varför fick jag förklarar en del utsidan av slingan? 640 00:28:48,830 --> 00:28:52,010 Kallelse på rad 49 Jag har förklarats i insidan av slingan, 641 00:28:52,010 --> 00:28:54,950 men på nätet 48 Jag har förklarade några utanför. 642 00:28:54,950 --> 00:28:55,695 Yeah. 643 00:28:55,695 --> 00:28:56,611 PUBLIK: [ohörbart]. 644 00:28:56,611 --> 00:28:58,734 645 00:28:58,734 --> 00:28:59,400 SPEAKER 1: Visst. 646 00:28:59,400 --> 00:29:03,360 Så först och främst gör jag verkligen inte vill deklarera och initiera summan 647 00:29:03,360 --> 00:29:06,130 till noll insidan av slinga på varje iteration, 648 00:29:06,130 --> 00:29:09,370 eftersom detta uppenbarligen skulle besegra Syftet summera siffrorna. 649 00:29:09,370 --> 00:29:11,770 Jag skulle hålla ändra värdet till noll. 650 00:29:11,770 --> 00:29:17,992 Och dessutom, vad är en annan, mer svårbegripliga Anledningen till samma beslut design? 651 00:29:17,992 --> 00:29:18,954 Yeah. 652 00:29:18,954 --> 00:29:20,279 >> PUBLIK: [ohörbart]. 653 00:29:20,279 --> 00:29:21,070 SPEAKER 1: Exakt. 654 00:29:21,070 --> 00:29:24,060 Jag vill komma åt det utanför av slingan också på vilken linje? 655 00:29:24,060 --> 00:29:25,390 656 00:29:25,390 --> 00:29:26,400 Den 53. 657 00:29:26,400 --> 00:29:29,910 Och på grundval av vår tumregel från ett par föreläsningar sedan, 658 00:29:29,910 --> 00:29:33,680 variabler scoped, egentligen, till klamrar som omfattar dem. 659 00:29:33,680 --> 00:29:38,190 Så om jag inte deklarerar summan inne av dessa yttre klammerparenteser, 660 00:29:38,190 --> 00:29:40,250 Jag kan inte använda den i linje 53. 661 00:29:40,250 --> 00:29:43,160 Med andra ord, om jag förklarade summan in här, eller till och med inom 662 00:29:43,160 --> 00:29:45,410 För loop, kunde jag inte komma åt den i 53. 663 00:29:45,410 --> 00:29:47,150 Variabeln skulle i praktiken vara borta. 664 00:29:47,150 --> 00:29:48,579 Så ett par anledningar där. 665 00:29:48,579 --> 00:29:50,370 Men nu ska vi gå tillbaka och se vad som händer. 666 00:29:50,370 --> 00:29:51,730 Så sigma anropas. 667 00:29:51,730 --> 00:29:55,640 Den lägger upp 1 plus 2 eller 1 plus 2 plus 3, och sedan returnerar värdet, 668 00:29:55,640 --> 00:29:59,660 lagras det i svaret, och printf här är därför jag ser på skärmen. 669 00:29:59,660 --> 00:30:03,079 Så det här är vad vi kallar en iterativ tillvägagångssätt, där iteration bara 670 00:30:03,079 --> 00:30:03,870 att använda en loop. 671 00:30:03,870 --> 00:30:06,900 A För loop, en while-slinga, en Do While loop, bara göra något nytt 672 00:30:06,900 --> 00:30:08,380 och igen och igen. 673 00:30:08,380 --> 00:30:13,505 >> Men sigma är lite av en snygg funktion i att jag kunde genomföra det på olika sätt. 674 00:30:13,505 --> 00:30:14,620 675 00:30:14,620 --> 00:30:19,120 Vad sägs om detta, vilket bara för att vara typ av cool, 676 00:30:19,120 --> 00:30:21,880 låt mig verkligen bli av en massa distraktion 677 00:30:21,880 --> 00:30:24,380 eftersom denna funktion är egentligen ganska enkel. 678 00:30:24,380 --> 00:30:27,780 Låt oss skära ner det bara till dess fyra grundlinjer 679 00:30:27,780 --> 00:30:30,410 och bli av med alla de kommentarer och klammerparenteser. 680 00:30:30,410 --> 00:30:34,334 Detta är lite av en otrolig alternativ implementering. 681 00:30:34,334 --> 00:30:37,250 Okej, kanske inte otrolig, men det är lite sexigare, okej, 682 00:30:37,250 --> 00:30:39,920 att titta på detta så mycket mer koncist. 683 00:30:39,920 --> 00:30:43,120 Med bara fyra rader kod, Jag har först denna sanity check. 684 00:30:43,120 --> 00:30:45,732 Om m är mindre än eller lika med noll, gör sigma ingen mening. 685 00:30:45,732 --> 00:30:48,190 Det har bara tänkt att vara i det här fallet för positiva tal, 686 00:30:48,190 --> 00:30:50,340 så jag ska bara retur noll godtyckligt 687 00:30:50,340 --> 00:30:53,210 så att vi åtminstone har vissa sk basfall. 688 00:30:53,210 --> 00:30:54,430 >> Men här är det fina. 689 00:30:54,430 --> 00:30:59,930 Helheten av denna idé, att lägga till nummer från 1 till n, eller m i det här fallet, 690 00:30:59,930 --> 00:31:02,630 kan göras genom slags vältra över ansvaret. 691 00:31:02,630 --> 00:31:04,947 Nå, vad är summan av 1 och m? 692 00:31:04,947 --> 00:31:05,780 Tja, vet du vad? 693 00:31:05,780 --> 00:31:11,949 Det är samma som summan av m plus ett belopp på 1 till m minus 1. 694 00:31:11,949 --> 00:31:12,740 Tja du vet vad? 695 00:31:12,740 --> 00:31:13,940 Vad är sigma av m minus 1? 696 00:31:13,940 --> 00:31:17,860 Tja, om du typ av följa den här logiskt, det är samma som m minus 1 697 00:31:17,860 --> 00:31:21,415 plus sigma m minus 2. 698 00:31:21,415 --> 00:31:22,480 699 00:31:22,480 --> 00:31:26,012 Så kan du typ av bara-- det är som om du är bara 700 00:31:26,012 --> 00:31:28,220 försöker reta en vän och de frågar dig en fråga, 701 00:31:28,220 --> 00:31:31,344 du slags svara med en fråga, du kan typ av hålla vältra över ansvaret. 702 00:31:31,344 --> 00:31:34,560 Men vad är nyckeln är att om du håller göra frågan mindre och mindre 703 00:31:34,560 --> 00:31:36,910 och mindre, du är frågar inte vad som är sigma 704 00:31:36,910 --> 00:31:39,116 n, vad är sigma av n, vad är sigma n? 705 00:31:39,116 --> 00:31:40,990 Du frågar vad som är sigma n, vad är sigma 706 00:31:40,990 --> 00:31:42,839 n minus 1, vad är sigma n minus 2? 707 00:31:42,839 --> 00:31:44,880 Så småningom din fråga kommer att bli vad? 708 00:31:44,880 --> 00:31:50,250 Vad är sigma av en eller noll, några mycket litet värde, 709 00:31:50,250 --> 00:31:52,220 och så fort du få det, din vän, 710 00:31:52,220 --> 00:31:54,350 du kommer inte att fråga samma fråga igen, 711 00:31:54,350 --> 00:31:55,975 du bara kommer att säga, åh det är noll. 712 00:31:55,975 --> 00:31:58,490 Vi är klar att spela den här sortens dumma cyklisk spel. 713 00:31:58,490 --> 00:32:02,950 >> Så rekursion är handlingen i programmering av en funktion som kallar sig. 714 00:32:02,950 --> 00:32:06,630 Detta program, när de sammanställs och kör, är kommer att bete sig exakt samma sätt, 715 00:32:06,630 --> 00:32:09,620 men vad är viktigaste är att inuti av en funktion som kallas sigma, 716 00:32:09,620 --> 00:32:13,150 det finns en kodrad där Vi kallar oss själva, 717 00:32:13,150 --> 00:32:14,980 som normalt skulle vara dåligt. 718 00:32:14,980 --> 00:32:21,160 Till exempel, vad händer om jag först sammanställt denna, så gör sigma-- 719 00:32:21,160 --> 00:32:22,710 göra sigma 1 ./sigma-1. 720 00:32:22,710 --> 00:32:25,050 721 00:32:25,050 --> 00:32:27,690 Positivt heltal, snälla, 50 1275. 722 00:32:27,690 --> 00:32:30,810 Så vad funktionen verkar vara, baserat på ett test, korrekt. 723 00:32:30,810 --> 00:32:34,917 Men vad händer om jag får lite farligt och ta bort det så kallade basfallet, 724 00:32:34,917 --> 00:32:37,750 och bara säga, ja jag bara göra detta mer komplicerat än det är. 725 00:32:37,750 --> 00:32:42,450 Låt oss bara beräkna sigma genom att m och sedan lägga 726 00:32:42,450 --> 00:32:44,564 i sigma m minus ett? 727 00:32:44,564 --> 00:32:45,980 Nå, vad kommer att hända här? 728 00:32:45,980 --> 00:32:47,140 Låt oss zooma ut. 729 00:32:47,140 --> 00:32:52,920 Låt oss kompilera om programmet, spara den, kompilera programmet, 730 00:32:52,920 --> 00:33:00,450 och sedan redo ./sigma-1 zoomar in, ange positivt heltal snälla, 50. 731 00:33:00,450 --> 00:33:02,180 732 00:33:02,180 --> 00:33:04,430 Hur många av er är villig att fess upp till att se det? 733 00:33:04,430 --> 00:33:04,950 >> OK. 734 00:33:04,950 --> 00:33:06,690 Så det här kan hända för ett antal skäl, 735 00:33:06,690 --> 00:33:09,148 och ärligt talat den här veckan är vi på väg att ge dig mer av dem. 736 00:33:09,148 --> 00:33:11,780 Men i detta fall, försök resonera bakåt 737 00:33:11,780 --> 00:33:14,430 Vad kan ha hänt här? 738 00:33:14,430 --> 00:33:17,400 Segmente fel, sa vi senast tid, hänvisar till ett segment av minnet. 739 00:33:17,400 --> 00:33:18,690 Något dåligt hänt. 740 00:33:18,690 --> 00:33:21,550 Men vad var det mekaniskt som gick snett 741 00:33:21,550 --> 00:33:25,000 här på grund av min avlägsna av att så kallade basfallet, 742 00:33:25,000 --> 00:33:26,870 där jag returnhårdkodad värde? 743 00:33:26,870 --> 00:33:28,970 744 00:33:28,970 --> 00:33:30,460 Vad tror du gick fel? 745 00:33:30,460 --> 00:33:31,219 Yeah. 746 00:33:31,219 --> 00:33:32,135 >> PUBLIK: [ohörbart]. 747 00:33:32,135 --> 00:33:36,387 748 00:33:36,387 --> 00:33:36,970 SPEAKER 1: Ah. 749 00:33:36,970 --> 00:33:37,550 Bra fråga. 750 00:33:37,550 --> 00:33:39,508 Så storleken på antalet att jag summera 751 00:33:39,508 --> 00:33:41,920 blev så stor att den överskred storleken på det minnesutrymme. 752 00:33:41,920 --> 00:33:44,640 Bra idé, men inte i grunden kommer att orsaka en krasch. 753 00:33:44,640 --> 00:33:48,230 Det kan orsaka heltalsspill, där bitarna flip drygt 754 00:33:48,230 --> 00:33:51,760 och sedan vi miste en riktigt stor nummer för som ett negativt tal, 755 00:33:51,760 --> 00:33:53,260 men att inte själv kommer att orsaka en krasch. 756 00:33:53,260 --> 00:33:55,509 Eftersom vid slutet av den dag en int är fortfarande 32 bitar. 757 00:33:55,509 --> 00:33:57,640 Du ska inte misstag stjäla en 33: e bit. 758 00:33:57,640 --> 00:33:58,431 Men en bra tanke. 759 00:33:58,431 --> 00:33:58,984 Yeah. 760 00:33:58,984 --> 00:33:59,900 >> PUBLIK: [ohörbart]. 761 00:33:59,900 --> 00:34:00,551 762 00:34:00,551 --> 00:34:02,300 TALARE 1: Metoden aldrig stannar, 763 00:34:02,300 --> 00:34:06,658 och faktiskt den kallar sig igen och igen och igen och igen 764 00:34:06,658 --> 00:34:08,449 och igen, och ingen av dessa funktioner någonsin 765 00:34:08,449 --> 00:34:13,310 avsluta eftersom deras enda rad av kod anropar sig själv om och om igen 766 00:34:13,310 --> 00:34:14,219 och igen. 767 00:34:14,219 --> 00:34:16,080 Och vad är egentligen händer här och nu vi 768 00:34:16,080 --> 00:34:18,100 kan typ av dra denna bildmässigt. 769 00:34:18,100 --> 00:34:20,899 Låt mig gå över till ett Bilden för bara ett ögonblick. 770 00:34:20,899 --> 00:34:22,940 Detta är en bild, som kommer så småningom att bygga ut 771 00:34:22,940 --> 00:34:26,336 mer detaljerat, om vad som händer insidan av datorns minne. 772 00:34:26,336 --> 00:34:28,460 Och det visar sig att den längst ner på denna bilden 773 00:34:28,460 --> 00:34:29,709 är något som kallas stacken. 774 00:34:29,709 --> 00:34:31,920 Detta är en bit av minne, en bit av RAM, 775 00:34:31,920 --> 00:34:33,920 det är bara användas när som helst en funktion anropas. 776 00:34:33,920 --> 00:34:36,239 Varje gång du, en programmerare, anropa en funktion, 777 00:34:36,239 --> 00:34:38,860 operativsystemet, liksom Mac OS, Windows eller Linux, 778 00:34:38,860 --> 00:34:41,920 griper ett gäng byte, kanske en få kilobyte, kanske några megabyte 779 00:34:41,920 --> 00:34:44,590 minne, händer dem till dig, och sedan låter 780 00:34:44,590 --> 00:34:47,650 du kör din funktion med hjälp av oavsett variabler som du behöver. 781 00:34:47,650 --> 00:34:50,699 Och om du sedan ringa en annan funktion och en annan funktion, 782 00:34:50,699 --> 00:34:53,590 du får en annan bit av minnet och en annan del av minnet. 783 00:34:53,590 --> 00:34:57,090 >> Och faktiskt, om dessa gröna brickor från Annenberg representerar detta minne, 784 00:34:57,090 --> 00:34:59,870 Här är vad som händer den första gång du ringer funktionen sigma. 785 00:34:59,870 --> 00:35:04,510 Det är som att sätta en bricka som denna på vad som är initialt en tom stack. 786 00:35:04,510 --> 00:35:07,142 Men sedan om det facket kallar sig, så att säga, 787 00:35:07,142 --> 00:35:08,850 ringer en annan instans av sigma, det är 788 00:35:08,850 --> 00:35:11,640 som att be operativsystemet, ooh, behöver lite mer minne, 789 00:35:11,640 --> 00:35:12,520 ge mig den. 790 00:35:12,520 --> 00:35:14,840 Och då blir staplade ovanpå. 791 00:35:14,840 --> 00:35:18,030 Men vad är nyckeln här är att det första facket är fortfarande där, 792 00:35:18,030 --> 00:35:20,620 eftersom han åberopat denna andra fack. 793 00:35:20,620 --> 00:35:23,500 Nu under tiden, sigma call sigma, det är som att be om mer minne. 794 00:35:23,500 --> 00:35:25,830 Får staplade på här. 795 00:35:25,830 --> 00:35:29,350 sigma kallar sigma, det är en annan fack som får staplas på här. 796 00:35:29,350 --> 00:35:32,942 Och om du fortsätter att göra detta, småningom, typ av kart denna visuella 797 00:35:32,942 --> 00:35:35,525 till att kartlägga, vad som kommer att hända med stapeln av brickor? 798 00:35:35,525 --> 00:35:37,480 799 00:35:37,480 --> 00:35:41,160 Det kommer att överstiga det belopp som minne datorn har. 800 00:35:41,160 --> 00:35:45,790 Och så snart som denna gröna fack överstiger den horisontella linjen 801 00:35:45,790 --> 00:35:49,410 ovanför stacken och över det ordet hög, vilket vi ska återkomma till i framtiden, 802 00:35:49,410 --> 00:35:50,410 det är en dålig sak. 803 00:35:50,410 --> 00:35:52,810 Högen är en annan segment av minne, 804 00:35:52,810 --> 00:35:55,190 och om du låter dem brickor lugg och lugg på, 805 00:35:55,190 --> 00:35:57,800 du kommer att överskrida din egen del av minnet, 806 00:35:57,800 --> 00:36:00,420 och ett program verkligen kommer att krascha. 807 00:36:00,420 --> 00:36:02,930 >> Nu som en sidoreplik, denna idé av rekursion därför 808 00:36:02,930 --> 00:36:06,500 kan helt klart leda till problem, men det är inte nödvändigtvis en dålig sak. 809 00:36:06,500 --> 00:36:08,840 Därför anser, efter att ha allt how-- och kanske 810 00:36:08,840 --> 00:36:11,700 detta tar lite tid att vänja att --how eleganta eller hur enkelt 811 00:36:11,700 --> 00:36:14,890 att genomförandet av sigma var. 812 00:36:14,890 --> 00:36:17,440 Och vi kommer inte att använda rekursion så mycket i CS50, 813 00:36:17,440 --> 00:36:20,780 men i CS51, och verkligen någon klass där du manipulera datastrukturer 814 00:36:20,780 --> 00:36:23,640 som träd eller släktträd, att ha en viss hierarki, 815 00:36:23,640 --> 00:36:26,000 det är super, super bra. 816 00:36:26,000 --> 00:36:29,750 Nu, som en sidoreplik, så att du som blivande datavetare 817 00:36:29,750 --> 00:36:33,180 är bekant med några av Googles interna skämt, om du går till Google 818 00:36:33,180 --> 00:36:36,345 och du tittar upp vad som är definition av, säg, rekursion skriver. 819 00:36:36,345 --> 00:36:40,208 820 00:36:40,208 --> 00:36:41,110 Uh-huh. 821 00:36:41,110 --> 00:36:42,670 Som en sidoreplik, drog jag upp några. 822 00:36:42,670 --> 00:36:45,470 Det var som 10 minuter av förhalning morse. 823 00:36:45,470 --> 00:36:52,890 Om du dessutom Google "snett", meddelande genom att luta huvudet slightly-- 824 00:36:52,890 --> 00:36:55,120 och sedan den här är kanske mest avskyvärda av alla 825 00:36:55,120 --> 00:36:57,286 eftersom någon använt som deras dag att genomföra detta 826 00:36:57,286 --> 00:36:59,880 några år ago-- kom igen. 827 00:36:59,880 --> 00:37:01,140 828 00:37:01,140 --> 00:37:04,540 Åh, wait-- det är en bugg. 829 00:37:04,540 --> 00:37:08,410 830 00:37:08,410 --> 00:37:11,410 >> Så som körs på en av de världens största webbplatser 831 00:37:11,410 --> 00:37:13,510 är dessa dumma små påskägg. 832 00:37:13,510 --> 00:37:16,690 De konsumerar förmodligen en nontrivial antal rader kod 833 00:37:16,690 --> 00:37:19,280 bara så att vi kan ha lite roliga saker. 834 00:37:19,280 --> 00:37:22,140 Men åtminstone nu får du vissa av dessa interna skämt. 835 00:37:22,140 --> 00:37:28,330 >> Nu ska vi ta en titt på några av de vit ligger vi har sagt för sent, 836 00:37:28,330 --> 00:37:30,707 och börja att skala tillbaka några lager tekniskt 837 00:37:30,707 --> 00:37:32,790 så att du verkligen förstår Vad har hänt 838 00:37:32,790 --> 00:37:34,860 och du kan förstå några av de hot, 839 00:37:34,860 --> 00:37:38,060 liknande Shock, att har nu börjat bli 840 00:37:38,060 --> 00:37:41,110 i framkant av allas uppmärksamhet, åtminstone i media. 841 00:37:41,110 --> 00:37:45,810 Så här är en mycket enkel funktion som returnerar ingenting, ogiltiga. 842 00:37:45,810 --> 00:37:46,790 Dess namn är swap. 843 00:37:46,790 --> 00:37:50,880 Det tar i två variabler och den återvänder ingenting. 844 00:37:50,880 --> 00:37:52,260 Tar i a och b. 845 00:37:52,260 --> 00:37:53,337 Så en snabb demonstration. 846 00:37:53,337 --> 00:37:54,170 Vi tog upp dessa. 847 00:37:54,170 --> 00:37:56,100 Vi kan lika gärna ta lite bryta här bara ett ögonblick 848 00:37:56,100 --> 00:37:57,250 och ha lite något att dricka. 849 00:37:57,250 --> 00:38:00,120 Om någon inte skulle ha något emot att gå mig för en stund här. 850 00:38:00,120 --> 00:38:01,830 Du då i rödbrunt skjorta? 851 00:38:01,830 --> 00:38:02,335 Kom upp. 852 00:38:02,335 --> 00:38:04,060 853 00:38:04,060 --> 00:38:05,260 Bara en i dag. 854 00:38:05,260 --> 00:38:06,251 Tack, dock. 855 00:38:06,251 --> 00:38:08,000 Okej, och vi har kommer upp vem här? 856 00:38:08,000 --> 00:38:08,660 Vad heter du? 857 00:38:08,660 --> 00:38:09,360 >> TALARE 4: Laura. 858 00:38:09,360 --> 00:38:09,740 >> SPEAKER 1: Laura. 859 00:38:09,740 --> 00:38:10,370 Kom upp. 860 00:38:10,370 --> 00:38:11,460 861 00:38:11,460 --> 00:38:13,850 Så Laura, mycket enkel utmaning i dag. 862 00:38:13,850 --> 00:38:14,704 863 00:38:14,704 --> 00:38:15,370 Trevligt att träffas yo. 864 00:38:15,370 --> 00:38:16,410 865 00:38:16,410 --> 00:38:16,910 Okej. 866 00:38:16,910 --> 00:38:21,179 Så vi har lite mjölk hit och Vi har lite apelsinjuice hit 867 00:38:21,179 --> 00:38:23,345 och några koppar som vi lånat från Annenberg idag. 868 00:38:23,345 --> 00:38:24,178 >> SPEAKER 4: Lånad. 869 00:38:24,178 --> 00:38:27,240 SPEAKER 1: Och kommer att gå vidare och ge dig ett halvt glas här. 870 00:38:27,240 --> 00:38:28,250 871 00:38:28,250 --> 00:38:28,800 Okej. 872 00:38:28,800 --> 00:38:30,750 Och vi ger dig hälften ett glas mjölk. 873 00:38:30,750 --> 00:38:31,905 874 00:38:31,905 --> 00:38:35,890 Åh, och bara så att du kan ihåg vad det var, 875 00:38:35,890 --> 00:38:38,860 Jag kom ihåg att ta med upp detta och i dag. 876 00:38:38,860 --> 00:38:42,030 877 00:38:42,030 --> 00:38:42,530 Okej. 878 00:38:42,530 --> 00:38:45,470 Om du inte skulle ha något emot, låt oss se, vi kan sätta dem över dina glasögon 879 00:38:45,470 --> 00:38:46,560 om du vill. 880 00:38:46,560 --> 00:38:48,710 Detta är alltså den världen från Lauras ögon. 881 00:38:48,710 --> 00:38:49,210 Okej. 882 00:38:49,210 --> 00:38:53,820 Så ditt mål, med tanke på två koppar flytande här, mjölk och apelsinjuice, 883 00:38:53,820 --> 00:38:58,370 är byta de två innehåll, så att apelsinjuice går in i mjölk kopp 884 00:38:58,370 --> 00:39:00,710 och mjölken går in apelsinjuicen koppen. 885 00:39:00,710 --> 00:39:02,359 >> SPEAKER 4: Får jag en kopp? 886 00:39:02,359 --> 00:39:05,650 SPEAKER 1: Jag är så glad att du frågade, men det skulle ha varit mycket bättre tagningar 887 00:39:05,650 --> 00:39:06,710 om du inte hade bett. 888 00:39:06,710 --> 00:39:10,620 Men ja, kan vi erbjuda dig en tredje cup som är tomt, förstås. 889 00:39:10,620 --> 00:39:11,120 Okej. 890 00:39:11,120 --> 00:39:12,300 Så byta innehållet där. 891 00:39:12,300 --> 00:39:16,100 892 00:39:16,100 --> 00:39:17,050 Mycket trevligt. 893 00:39:17,050 --> 00:39:20,390 894 00:39:20,390 --> 00:39:21,305 Mycket bra. 895 00:39:21,305 --> 00:39:23,121 896 00:39:23,121 --> 00:39:24,745 Du gör detta anmärkningsvärt noga. 897 00:39:24,745 --> 00:39:26,970 898 00:39:26,970 --> 00:39:28,655 Och steg tre. 899 00:39:28,655 --> 00:39:30,390 900 00:39:30,390 --> 00:39:31,350 Okej. 901 00:39:31,350 --> 00:39:31,930 Utmärkt. 902 00:39:31,930 --> 00:39:33,930 En stor applåd skulle vara bra för Laura. 903 00:39:33,930 --> 00:39:36,500 904 00:39:36,500 --> 00:39:37,000 Okej. 905 00:39:37,000 --> 00:39:40,790 Vi har en liten avskedsgåva för dig, men låt mig ta dessa. 906 00:39:40,790 --> 00:39:42,620 Tack så mycket. 907 00:39:42,620 --> 00:39:46,170 Så ett enkelt exempel, fast, att visa att om du gör 908 00:39:46,170 --> 00:39:48,300 vill byta innehållet av två behållare, 909 00:39:48,300 --> 00:39:52,360 eller låt oss kalla dem variabler, du behöver lite tillfällig lagring 910 00:39:52,360 --> 00:39:56,710 att arrangera en av innehållet i den att du faktiskt kan göra swappen. 911 00:39:56,710 --> 00:40:01,790 Så ja, denna källkod här uppe i C är representativt för just detta. 912 00:40:01,790 --> 00:40:06,340 Om apelsinjuice var en och mjölken var b, och vi ville byta de två, 913 00:40:06,340 --> 00:40:08,990 du kan försöka något kreativt genom att hälla en in i den andra, 914 00:40:08,990 --> 00:40:11,031 men som förmodligen inte skulle sluta särskilt väl. 915 00:40:11,031 --> 00:40:15,260 Och så använder vi en tredje kopp, samtal Det tmp, T-M-P av konvention, 916 00:40:15,260 --> 00:40:19,370 och sätta innehållet i EGT i det, sedan byta en kopp, 917 00:40:19,370 --> 00:40:22,610 sedan lägga EGT i original cup, och därigenom 918 00:40:22,610 --> 00:40:25,320 uppnå, precis som Laura gjorde, swap. 919 00:40:25,320 --> 00:40:26,850 >> Så låt oss göra just det. 920 00:40:26,850 --> 00:40:30,110 Låt mig gå vidare och öppna upp ett exempel som är 921 00:40:30,110 --> 00:40:32,720 faktiskt kallas "no swap ", eftersom detta inte är 922 00:40:32,720 --> 00:40:36,180 så enkelt gjort som man kan tro. 923 00:40:36,180 --> 00:40:41,190 Så i det här programmet, märker att Jag använder stdio.h, vår gamle vän. 924 00:40:41,190 --> 00:40:43,130 Jag har prototypen för swap där uppe, vilket 925 00:40:43,130 --> 00:40:45,450 innebär att dess genomförande är troligen nere, 926 00:40:45,450 --> 00:40:48,050 och låt oss se vad denna huvud Programmet kommer att göra för mig. 927 00:40:48,050 --> 00:40:52,020 Jag förklarar först int x blir en, och int y blir två. 928 00:40:52,020 --> 00:40:54,930 Så tänk på dem som EGT och mjölk, respektive. 929 00:40:54,930 --> 00:40:57,100 Och då har jag bara en printf säga x är detta 930 00:40:57,100 --> 00:41:00,120 och y är det, bara så jag kan visuellt se vad som händer. 931 00:41:00,120 --> 00:41:03,810 Då har jag printf hävdar att jag byter de två, 932 00:41:03,810 --> 00:41:07,100 och då jag skriver ut en hävdar att de är bytt, 933 00:41:07,100 --> 00:41:09,300 och jag skriver ut x och y igen. 934 00:41:09,300 --> 00:41:13,010 Så här nere i swap är exakt vad Laura gjorde, 935 00:41:13,010 --> 00:41:16,240 och exakt vad vi såg på skärmen för en stund sedan. 936 00:41:16,240 --> 00:41:19,380 >> Så låt oss gå vidare och bli mycket besvikna. 937 00:41:19,380 --> 00:41:24,690 Gör inga swap, och kör ingen swap, zoomar in på utgången här. 938 00:41:24,690 --> 00:41:28,320 Ange x är 1, y är 2, byta växlats. 939 00:41:28,320 --> 00:41:32,700 x är fortfarande 1, och y är fortfarande 2. 940 00:41:32,700 --> 00:41:37,630 Så även om, ärligt talat, det här ser precis som, om än mer tekniskt, 941 00:41:37,630 --> 00:41:40,730 vad Laura gjorde, inte verkar fungera. 942 00:41:40,730 --> 00:41:42,130 Så varför är det? 943 00:41:42,130 --> 00:41:46,630 Tja, det visar sig att när vi skriver ett program som detta 944 00:41:46,630 --> 00:41:51,590 som har både huvud, markerad här, och sedan en annan funktion, som swap, 945 00:41:51,590 --> 00:41:54,230 markerad här, som den kallar, världens 946 00:41:54,230 --> 00:41:57,030 ser lite något liknande dessa brickor en stund sedan. 947 00:41:57,030 --> 00:42:00,440 När huvud först anropas, det är som att be operativsystem 948 00:42:00,440 --> 00:42:04,030 för lite minne för alla lokala variabler som x och y som huvud har, 949 00:42:04,030 --> 00:42:05,660 och de hamnar där. 950 00:42:05,660 --> 00:42:10,920 Men om huvud samtal byta, och huvud passerar att byta två argument, a och b, 951 00:42:10,920 --> 00:42:16,410 apelsinjuice och mjölk, det är inte som lämna apelsinjuice och mjölk 952 00:42:16,410 --> 00:42:17,500 till Laura. 953 00:42:17,500 --> 00:42:21,300 Vad en dator gör, är det passerar kopior av apelsinjuice 954 00:42:21,300 --> 00:42:27,110 och kopior av mjölken till Laura, så att vad är slutligen inne i detta fack 955 00:42:27,110 --> 00:42:32,510 är värdet en och två, eller EGT och mjölk, men kopior av dessa, 956 00:42:32,510 --> 00:42:34,790 så att på denna punkt i berättelsen, det 957 00:42:34,790 --> 00:42:36,930 är EGT och mjölk i var och en av dessa brickor. 958 00:42:36,930 --> 00:42:39,260 Det är en en och en två i var och en av dessa brickor, 959 00:42:39,260 --> 00:42:41,720 och växlingsfunktionen är verkligen fungerar. 960 00:42:41,720 --> 00:42:46,090 Den byta dem inuti av den andra översta facket, 961 00:42:46,090 --> 00:42:48,147 men att byta inte har någon inverkan. 962 00:42:48,147 --> 00:42:49,980 Och baserat på bara några grundläggande princip vi har 963 00:42:49,980 --> 00:42:52,970 talat om tidigare, och faktiskt bara några minuter sedan, vad 964 00:42:52,970 --> 00:42:58,770 kan förklara varför ändra a och b insida swap 965 00:42:58,770 --> 00:43:05,560 har ingen effekt på x och y, även om Jag passerade x och y på växlingsfunktionen. 966 00:43:05,560 --> 00:43:08,750 Vad är nyckelordet här att kan förenklat förklara? 967 00:43:08,750 --> 00:43:11,250 968 00:43:11,250 --> 00:43:12,627 Jag tror att jag hört det här? 969 00:43:12,627 --> 00:43:13,335 PUBLIKEN: Return. 970 00:43:13,335 --> 00:43:14,085 SPEAKER 1: Return? 971 00:43:14,085 --> 00:43:14,590 Inte tillbaka. 972 00:43:14,590 --> 00:43:15,895 Låt oss med en annan. 973 00:43:15,895 --> 00:43:16,395 Vad är det? 974 00:43:16,395 --> 00:43:17,080 >> PUBLIK: [ohörbart]. 975 00:43:17,080 --> 00:43:20,000 >> SPEAKER 1: OK, så return-- vi kunde göra retur arbete i berättelsen, 976 00:43:20,000 --> 00:43:21,914 men det finns en ännu enklare förklaring. 977 00:43:21,914 --> 00:43:22,580 PUBLIKEN: Scope. 978 00:43:22,580 --> 00:43:23,288 SPEAKER 1: Räckvidd. 979 00:43:23,288 --> 00:43:24,300 Jag tar utrymme. 980 00:43:24,300 --> 00:43:27,290 Så omfattning, kom ihåg var vår x och y deklareras. 981 00:43:27,290 --> 00:43:30,840 De deklarerade inuti Huvud rätt upp här. 982 00:43:30,840 --> 00:43:33,200 a och b, under tiden, är effektivt förklarats 983 00:43:33,200 --> 00:43:35,930 insidan av swap, inte riktigt i klammerparentes men ändå 984 00:43:35,930 --> 00:43:37,690 i det allmänna området för swap. 985 00:43:37,690 --> 00:43:40,560 Och så faktiskt, a och b existerar endast inom detta fack 986 00:43:40,560 --> 00:43:44,850 från Annenberg, detta andra bit av kod. 987 00:43:44,850 --> 00:43:49,500 Så vi verkligen ändra kopian, men det är egentligen inte så bra. 988 00:43:49,500 --> 00:43:52,190 >> Så låt oss ta en titt på detta lite lägre nivå. 989 00:43:52,190 --> 00:43:55,430 Jag kommer att gå tillbaka till Source Directory, 990 00:43:55,430 --> 00:43:58,330 och jag ska först zooma in här, och bara 991 00:43:58,330 --> 00:44:02,290 för att bekräfta att jag är i det här större fönster terminal, 992 00:44:02,290 --> 00:44:04,430 programmet fortfarande beter sig som det. 993 00:44:04,430 --> 00:44:06,840 Antag nu att detta inte avsiktligt. 994 00:44:06,840 --> 00:44:10,090 Klart jag ville swap till arbete, så det känns som en bugg. 995 00:44:10,090 --> 00:44:12,780 Nu kunde jag börja lägga en massa printf ter till min kod, 996 00:44:12,780 --> 00:44:16,010 skriva ut x hit, y över Här, en hit, b hit. 997 00:44:16,010 --> 00:44:18,220 Men ärligt talat, det är nog det som du har gjort i ett par veckor 998 00:44:18,220 --> 00:44:20,190 nu, i kontorstid och hemma vid arbete 999 00:44:20,190 --> 00:44:22,150 på psets försöker hitta några buggar. 1000 00:44:22,150 --> 00:44:25,560 Men ser du, om du inte redan har, det problemet satt tre introducerar dig 1001 00:44:25,560 --> 00:44:31,630 till ett kommando som heter GDB, där GDB, GNU debugger, 1002 00:44:31,630 --> 00:44:34,040 har själv en massa funktioner som faktiskt kan 1003 00:44:34,040 --> 00:44:38,160 låt oss förstå situationer så här, men mer tvingande, 1004 00:44:38,160 --> 00:44:39,940 lösa problem och hitta buggar. 1005 00:44:39,940 --> 00:44:40,940 Så jag ska göra det här. 1006 00:44:40,940 --> 00:44:44,770 Istället för ./noswap, jag är i stället kommer att köra GDB ./noswap. 1007 00:44:44,770 --> 00:44:47,410 1008 00:44:47,410 --> 00:44:51,200 Med andra ord kommer jag att köra min programmet inte i Bash, vår nya vän 1009 00:44:51,200 --> 00:44:51,850 idag. 1010 00:44:51,850 --> 00:44:53,970 Jag kommer att köra min Programmet noswap inuti 1011 00:44:53,970 --> 00:44:56,900 i denna andra program som heter GDB, vilket är en avlusare, vilket 1012 00:44:56,900 --> 00:45:01,035 är ett program som är utformat för att hjälpa Ni människor hitta och ta bort buggar. 1013 00:45:01,035 --> 00:45:03,410 Så om jag slog Kör hit, det finns ett förfärligt mycket text 1014 00:45:03,410 --> 00:45:04,868 att du verkligen aldrig behöver läsa. 1015 00:45:04,868 --> 00:45:07,290 Det är i huvudsak en distraktion från prompten, vilket 1016 00:45:07,290 --> 00:45:10,030 Jag ska träffa Kontroll-L att gå upp på toppen där. 1017 00:45:10,030 --> 00:45:11,800 Detta är den GDB prompten. 1018 00:45:11,800 --> 00:45:15,550 Om jag vill köra det här programmet nu, eftersom denna lilla lathund på dagens 1019 00:45:15,550 --> 00:45:21,860 slide antyder Run är det första kommandon som vi tänkt att införa. 1020 00:45:21,860 --> 00:45:25,150 Och jag ska bara skriva köra upp här inne i GDB, 1021 00:45:25,150 --> 00:45:26,811 och faktiskt det körde mitt program. 1022 00:45:26,811 --> 00:45:29,310 Nu finns det vissa ytterligare utgångarna på skärmen så här, 1023 00:45:29,310 --> 00:45:31,910 men det är GDB bara vara anal och berätta vad som händer. 1024 00:45:31,910 --> 00:45:34,451 Du behöver verkligen inte oroa dig om dessa detaljer just nu. 1025 00:45:34,451 --> 00:45:36,890 Men vad är riktigt coolt om GDB, om jag gör det här igen-- 1026 00:45:36,890 --> 00:45:42,100 Kontroll-L rensar screen-- låta mig gå framåt och typ "break", och därigenom, 1027 00:45:42,100 --> 00:45:45,743 när jag slog in, sätta vad är kallas en brytpunkt vid noswap.c, 1028 00:45:45,743 --> 00:45:51,270 linje 16, som är där GDB räknat ut mitt program faktiskt 1029 00:45:51,270 --> 00:45:53,070 är, faktiskt är min funktion. 1030 00:45:53,070 --> 00:45:55,070 Detta ska vi ignorera för nu men det är adressen 1031 00:45:55,070 --> 00:45:57,310 minnet specifikt av denna funktion. 1032 00:45:57,310 --> 00:46:00,240 Så nu när jag typ springa, märker vad är hett här. 1033 00:46:00,240 --> 00:46:05,650 Min programmet bryter på den linje som jag berättade GDB att pausa exekvering på. 1034 00:46:05,650 --> 00:46:09,850 Så jag behöver inte nu ändra min kod, lägga till några printf s, kompilera det, repris 1035 00:46:09,850 --> 00:46:13,300 den, ändra, lägga till några printf s, spara den, kompilera det, kör den. 1036 00:46:13,300 --> 00:46:18,100 Jag kan bara gå igenom mitt program steg för steg för steg till mänsklig hastighet, 1037 00:46:18,100 --> 00:46:20,880 inte på Intel-inside typ av hastighet. 1038 00:46:20,880 --> 00:46:24,580 >> Så nu märker denna linje visas här, och om jag går tillbaka 1039 00:46:24,580 --> 00:46:27,800 till mitt program i gedit, märker att det faktiskt är 1040 00:46:27,800 --> 00:46:29,280 den allra första rad kod. 1041 00:46:29,280 --> 00:46:31,240 Det finns linje 16 i gedit. 1042 00:46:31,240 --> 00:46:34,610 Det finns linje 16 i GDB, och till och med även om detta svartvita gränssnitt 1043 00:46:34,610 --> 00:46:37,760 är inte alls lika användar vänlig, innebär detta 1044 00:46:37,760 --> 00:46:41,680 att linjen 16 har inte utförts ännu, men det är på väg att bli. 1045 00:46:41,680 --> 00:46:46,220 Så ja, om jag skriver print x, inte printf, bara skriva ut x, 1046 00:46:46,220 --> 00:46:50,730 Jag får några falska värde där noll, eftersom x har inte initierats ännu. 1047 00:46:50,730 --> 00:46:54,760 Så jag ska skriva härnäst, eller om du vill vara snygga, bara n för nästa. 1048 00:46:54,760 --> 00:46:59,090 Men när jag skriver nästa komma in, nu märker det går vidare till linje 17. 1049 00:46:59,090 --> 00:47:02,840 Så logiskt, om jag har verk linje 16 och jag nu skriver print x, 1050 00:47:02,840 --> 00:47:03,640 vad ska jag se? 1051 00:47:03,640 --> 00:47:04,970 1052 00:47:04,970 --> 00:47:05,520 One. 1053 00:47:05,520 --> 00:47:07,820 >> Och nu detta är visserligen förvirrande. 1054 00:47:07,820 --> 00:47:11,260 $ 2 är bara ett finare sätt att, om man vill hänvisa till det värdet senare, 1055 00:47:11,260 --> 00:47:12,510 du kan säga "dollar sign två." 1056 00:47:12,510 --> 00:47:13,480 Det är som en back referens. 1057 00:47:13,480 --> 00:47:14,570 Men för nu, bara ignorera det. 1058 00:47:14,570 --> 00:47:17,070 Det intressanta är vad som är till höger om likhetstecknet. 1059 00:47:17,070 --> 00:47:21,000 Och nu om jag skriver nästa gång och skriv ut y, ska jag se 2. 1060 00:47:21,000 --> 00:47:23,870 Jag kan nu också skriva ut x igen, och ärligt talat, 1061 00:47:23,870 --> 00:47:27,130 om jag börjar bli lite förvirrad där jag är, kan jag skriva lista för listan 1062 00:47:27,130 --> 00:47:30,590 och bara se något sammanhang runt punkten är jag faktiskt på. 1063 00:47:30,590 --> 00:47:35,180 Och nu kan jag skriva nästa, och där x är 1. 1064 00:47:35,180 --> 00:47:36,300 Nu skriver jag nästa. 1065 00:47:36,300 --> 00:47:37,710 Åh, y 2. 1066 00:47:37,710 --> 00:47:40,750 Och återigen, det är förvirrande, eftersom GDB produktion 1067 00:47:40,750 --> 00:47:43,044 håller på att blandas med min egen utgång. 1068 00:47:43,044 --> 00:47:45,710 Men om du kom ihåg, genom blick och tillbaka på din kod 1069 00:47:45,710 --> 00:47:47,740 eller lägga ut den sidan vid sida kanske, du ska 1070 00:47:47,740 --> 00:47:51,020 se att egentligen är jag bara stega igenom mitt program. 1071 00:47:51,020 --> 00:47:54,620 >> Men lägg märke till vad som händer sedan, bokstavligen. 1072 00:47:54,620 --> 00:47:56,380 Här är linje 22. 1073 00:47:56,380 --> 00:48:01,315 Låt mig gå över den, och därmed går vidare till 23, och om jag skriver ut x nu, fortfarande en. 1074 00:48:01,315 --> 00:48:03,890 Och om jag skriver ut y nu, fortfarande en. 1075 00:48:03,890 --> 00:48:05,820 Så det här är inte en nyttig övning. 1076 00:48:05,820 --> 00:48:07,450 Så låt oss göra om det här. 1077 00:48:07,450 --> 00:48:10,069 Låt mig gå tillbaka till topp och typ springa igen. 1078 00:48:10,069 --> 00:48:12,110 Och den säger att programmet som är som debuggade 1079 00:48:12,110 --> 00:48:14,109 har startat redan, startade från början. 1080 00:48:14,109 --> 00:48:15,420 Ja, låt oss göra det här igen. 1081 00:48:15,420 --> 00:48:22,000 Och den här gången ska vi göra härnäst, nästa, nästa, nästa, nästa, 1082 00:48:22,000 --> 00:48:24,180 men nu det blir intressant. 1083 00:48:24,180 --> 00:48:27,760 Nu vill jag kliva in swap, så jag skriver inte nästa. 1084 00:48:27,760 --> 00:48:34,380 Jag skriver steg, och nu märker det har hoppat mig till noswap.c linje 33. 1085 00:48:34,380 --> 00:48:37,240 Om jag går tillbaka till gedit, vad är linje 33? 1086 00:48:37,240 --> 00:48:40,500 Det är den första egentliga kodrad inuti swap. 1087 00:48:40,500 --> 00:48:44,150 Vilket är trevligt, för nu kan jag typ av rota runt och få nyfikna 1088 00:48:44,150 --> 00:48:46,052 om vad som händer riktigt där. 1089 00:48:46,052 --> 00:48:46,760 Låt mig skriva tmp. 1090 00:48:46,760 --> 00:48:47,770 1091 00:48:47,770 --> 00:48:48,800 Oj. 1092 00:48:48,800 --> 00:48:51,438 Varför måste tmp har någon galet, bogus sopor värde? 1093 00:48:51,438 --> 00:48:54,579 1094 00:48:54,579 --> 00:48:56,120 PUBLIK: Det har inte initierats. 1095 00:48:56,120 --> 00:48:57,150 SPEAKER 1: Det har inte initierats. 1096 00:48:57,150 --> 00:49:00,270 Och faktiskt, när du kör ett program, du får en hel massa minne 1097 00:49:00,270 --> 00:49:03,392 av operativsystemet, men du har inte initierats några värden, 1098 00:49:03,392 --> 00:49:05,600 så vad bitar du är ser här, även om det är 1099 00:49:05,600 --> 00:49:07,770 denna galna stora negativa nummer, betyder bara 1100 00:49:07,770 --> 00:49:10,750 att de är resterna från någon tidigare användning av detta RAM, 1101 00:49:10,750 --> 00:49:13,050 även om jag inte har jag själv behövde det ännu. 1102 00:49:13,050 --> 00:49:17,086 Så nu ska jag gå vidare och typ Nästa, och om jag nu skriver print tmp, 1103 00:49:17,086 --> 00:49:17,835 vad ska jag se? 1104 00:49:17,835 --> 00:49:19,570 1105 00:49:19,570 --> 00:49:23,360 Oavsett värdet av en var, a är det första argumentet, precis 1106 00:49:23,360 --> 00:49:25,550 som x var den första sak som gått in, 1107 00:49:25,550 --> 00:49:30,450 så en och x bör vara samma, så ut tmp ska skriva ut mig en. 1108 00:49:30,450 --> 00:49:36,360 >> Så vad du ser i problem set tre är en handledning av slag på GDB, 1109 00:49:36,360 --> 00:49:40,020 men inser att detta är början en titt på ett verktyg som faktiskt kommer att 1110 00:49:40,020 --> 00:49:42,774 hjälpa dig att lösa problem så mycket mer effektivt. 1111 00:49:42,774 --> 00:49:44,690 Vad vi är i slutändan ska göra på onsdag 1112 00:49:44,690 --> 00:49:48,180 är att börja skära ner några lager och ta bort några stödhjul. 1113 00:49:48,180 --> 00:49:50,496 Det där kallas sträng som vi har använt under en tid, 1114 00:49:50,496 --> 00:49:53,370 vi ska sakta ta det ifrån från dig och börja prata om 1115 00:49:53,370 --> 00:49:55,725 något mer esoteriskt känd som char *, 1116 00:49:55,725 --> 00:49:59,550 men vi ska göra det här trevliga och försiktigt vid första, trots pekare, 1117 00:49:59,550 --> 00:50:02,730 som de kallas, kan göra en del mycket dåliga saker om övergrepp, 1118 00:50:02,730 --> 00:50:06,040 genom att titta på en liten claymation från vår vän Nick Parlante från Stanford 1119 00:50:06,040 --> 00:50:09,670 Universitet, professor i dator vetenskap som satt ihop den här förhandsvisningen 1120 00:50:09,670 --> 00:50:11,075 om vad som komma skall på onsdag. 1121 00:50:11,075 --> 00:50:12,196 1122 00:50:12,196 --> 00:50:13,400 >> [VIDEOAVSPELNING] 1123 00:50:13,400 --> 00:50:13,900 Hej, Binky. 1124 00:50:13,900 --> 00:50:14,930 1125 00:50:14,930 --> 00:50:15,780 Vakna. 1126 00:50:15,780 --> 00:50:17,240 Det är dags för pekaren kul. 1127 00:50:17,240 --> 00:50:18,260 1128 00:50:18,260 --> 00:50:19,350 >> Vad är det? 1129 00:50:19,350 --> 00:50:21,150 Lär dig mer om pekare? 1130 00:50:21,150 --> 00:50:22,050 Åh, goody! 1131 00:50:22,050 --> 00:50:22,897 1132 00:50:22,897 --> 00:50:23,730 [END VIDEOAVSPELNING] 1133 00:50:23,730 --> 00:50:25,396 SPEAKER 1: Det väntar på onsdag. 1134 00:50:25,396 --> 00:50:26,440 Vi ses då. 1135 00:50:26,440 --> 00:50:27,106 [VIDEOAVSPELNING] 1136 00:50:27,106 --> 00:50:30,420 -Och Nu, djupa tankar, genom Daven Farnham. 1137 00:50:30,420 --> 00:50:33,980 1138 00:50:33,980 --> 00:50:35,900 >> Varför lär vi oss C? 1139 00:50:35,900 --> 00:50:36,785 Varför inte A +? 1140 00:50:36,785 --> 00:50:38,550 1141 00:50:38,550 --> 00:50:40,910 >> [LAUGHTER] 1142 00:50:40,910 --> 00:50:42,160 >> [END VIDEOAVSPELNING]