>> [Musik spiller]
>> SPEAKER 1: Okay, det er CS50, og dette er begyndelsen af ​​uge fire,
og som du måske har hørt eller læse, har verden slutter.
Går alle rundt på internettet har været viden og bevidsthed
af en fejl i et program, en programmeringssprog kaldet Bash.
Det har været vidunderligt mærkevarer som Shellshock eller Bash døren,
men artikler som disse har ikke været ualmindeligt.
Og i virkeligheden, mange af dem bringe tilbage minderne om Heartbleed,
som du måske har bemærket i trykke tilbage denne sidste forår, som
var ligeledes temmelig dramatisk.
Nu er de af jer her i dag, hvor mange af jer har,
selv hvis du ikke forstår, hvad det hele handler om, hørt om Shellshock?
Okay, og hvor mange af jer har computere, som er sårbare?
OK, bør der være langt, langt flere hænder op lige nu, vi grunde skal se.
>> Lad os tage et kig på, hvad der er stået på i medierne
og derefter forklare det lidt her for os teknisk.
>> SPEAKER 2: Sikkerhed eksperter har advarede om, at en alvorlig fejl kunne
være ved at påvirke hundredvis af millioner af verdens internetbrugere.
Så hvad er den fejl, der har været eftersynkroniseret Shellshock, og hvad gør den?
Nå, er Shellshock også kendt som Bash bug, den software, der udnytter.
Hackere bruger virus til at scanne sårbar systemer, der kører Linux og Unix
operativsystemer og derefter inficere dem.
Bash er en kommandolinje shell.
Dette lader brugerne sende kommandoer til at lancere programmer og funktioner i softwaren
ved at skrive i teksten.
Det er typisk bruges af programmører, og bør ikke være åben over for den øvrige verden,
selvom Shellshock ændrer det.
>> Nå, worringly, nogle analytikere advare det kunne være en større trussel,
fordi Shellshock tillader fuldstændig kontrol over en inficeret maskine,
hvorimod Heartbleed kun tilladt hackere til at spionere på computere.
Det er så alvorligt, det er blevet klassificeret en 10 ud af 10
til sværhedsgraden af ​​National Sårbarhed Database.
2/3 af alle web-servere er i risiko, herunder nogle Mac-computere.
Nå, skal du sørge lappe dine systemer nu.
Enhver vært for et websted kørende de berørte operativsystemer
bør træffe foranstaltninger så hurtigt som muligt.
Enhver, der har råd til det skal se til deres ansøgning overvågning og web
firewalls til at se ud for eventuelle angreb.
SPEAKER 3: Værste der kan ske, er
at nogen ville skrive kode, automatisk ville gå og scanne
internettet og ville påvirke alle disse computere.
Og når de gør det, ja, det værste de kunne gøre
er bare slette alt, eller lukke de steder ned.
Så kunne vi se skade fra det synspunkt,
hvor vi ville have ondsindede personer der bare beslutte at skabe kaos
ved at bringe systemer ned eller slette filer, og ting som.
SPEAKER 2: Nogle siger, dette er en af de mest vanskelige at måle
bugs i år, og det kan tage uger eller endda
måneder til at bestemme dens endelige effekt.
>> SPEAKER 1: Så alt dette er sandt, men det sjove er, at næsten alle
af billedsprog, du lige har set, bortset fra måske tastaturet,
har intet at gøre med overhovedet bug.
Servere og ledninger og så videre, Det er lidt tangentielt relateret,
men kernen er det faktisk temmelig velkendt, hvad der foregår her.
Faktisk, lad mig gå ind vores CS50 apparatet.
Lad mig gå videre og maksimere terminalvinduet her.
Og gutter har brugt denne, eller den integrerede version heraf,
i Gedit med henblik på at skrive programmer, indtaste kommandoer og så videre,
og dette er faktisk, og har været i ugevis, Bash, B-A-S-H.
Dette er Bourne-igen shell, der er bare en fancy måde at sige,
dette er et program, der har en blinker hurtig, effektiv,
der sidder der venter for input til dig.
Og det er den kommando line interface, via hvilken
gutter har kørt kommandoer og i sidste ende at kompilere og derefter køre
programmer.
>> Men Bash er også et programmeringssprog sprog i følgende forstand.
Du ved, at der er kommandoer som cd og ls, og også clang og andre,
men du kan definere dine egne kommandoer ved at gennemføre dem i Bash.
Nu er vi ikke kommer til at gå i detaljer
at Bash programmeringssprog, men ved for eksempel, at i det øjeblik,
der er ingen kommando kaldet "hej."
Så det kan findes i en af ​​disse pakker.
Det er ikke installeret på min computer.
Spørg din administrator.
Men hvis jeg ønsker, at der skal være et program kaldet "hej" i bash eller på min prompt,
Jeg kan faktisk bruge syntaks, der er helt ligesom C. Det er ikke helt det samme,
men det ser temmelig ligner en funktion, omend mangler nogle detaljer.
Intet synes at ske, men nu, hvis jeg skriver "hej"
du kan faktisk skrive en programmet, ikke i C, ikke i Java,
ikke i et andet programmeringssprog sprog, men i Bash selv.
>> Nu centrale her er, at jeg skrev navn, jeg ønskede at give denne nye kommando,
og parentes er også symbolsk for dette er en funktion.
Som en sidebemærkning, kan du også gøre det sjovt ting, og i virkeligheden, selv på Mac OS
dette er et program kaldet Terminal.
Det kommer indbygget i nogens computer, der har en Mac i dette rum,
og du kan gøre lignende ting i Mac OS, men du kan gå mere end det.
Og det er lidt tangential, men det er lidt sjovt.
Jeg blev mindet i morges, når tænker dette igennem,
af et lille spil jeg plejede at spille med en af ​​CS50 tidligere TF'er
hvorved helst, han ville gå væk fra hans tastatur med sin skærm ulåst,
Jeg vil udføre en kommando ligesom denne-- "sige hej."
Og nu helst han kom tilbage til sin tastatur efter jeg ryddet skærmen
og han ville sidde ned, forsøge at gøre noget arbejde,
vise indholdet af hans directory--
>> [Audio Playback]
>> Hallo.
Hej.
>> SPEAKER 1: Så i retfærdighed, Det var faktisk ikke "Hej."
Det var normalt noget mere beslægtet med at--
[Audio Playback]
-Beep.
SPEAKER 1: --that jeg would-- så sin computer ville
sværger på ham som helst, han faktisk satte sig ved hans tastatur.
Og meget hurtigt han regnet ud ikke at forlade sin skærm ulåst.
Men dette tyder slags dumme sjov, som du
kan have med noget som Bash.
Men det er lidt mere alvorlige, at være sikker på, end det.
Og i virkeligheden, det er en af ​​de farligste og mest langvarige bugs
der virkelig har ramt verden globalt.
Denne fejl har været omkring for omkring 20 år,
og du vil blive ramt i blot et øjeblik af dens relative enkelhed.
>> Så dette er en repræsentant befaler, at hvis du
ejer en Mac, bogstaveligt talt lige nu når du har din låget åbent,
du kan prøve at skrive ind i det program kaldet Terminal.
Terminal er under Ansøgninger Utilities--
for en gangs skyld, behøver Windows-brugere ikke behøver at bekymre sig om denne særlige threat--
men dem af jer med Mac-computere kan skrive dette ind i et vindue som jeg vil gøre her,
og hvis du skriver at i dette program
kaldet Terminal, ligesom jeg vil gøre nu, hvis du ser ordet "sårbar"
din computer er sårbare over for udnyttelse.
>> Nu hvad betyder det egentlig?
Og det er ganske vist nogle temmelig vanvittigt syntaks,
men lad os i det mindste trække ud nogle af de interessante aspekter.
Så der er nogle syntaks, der ser lidt bekendt, i det mindste fra C
og programmering mere generelt.
Jeg ser nogle parenteser, semikolon, krøllede parenteser, og sådan,
men det viser sig, at dette dumme ting her i gult
er i det væsentlige en funktion det gør ingenting.
Tyktarmen midler gøre ingenting, og det semikolon betyder stoppe med at gøre ingenting.
Så indersiden af ​​disse krøllede parenteser, det faktum,
at jeg har en lige underskrive til venstre, dette
er hovedsagelig at skabe en kommando, eller en variabel,
kaldet x, og tildele den den gule smule kode der.
Det kunne være noget lignende "ekko hej "eller" siger bip "eller noget
beslægtet med.
Men bemærk hvis dine øjne vandre længere til højre,
der er mere til denne linje end bare slutningen af ​​denne semikolon.
"Echo sårbar" og derefter ud over at der er endnu mere.
Andet semikolon, bash -c :.
>> Så lang historie kort, denne linje kode er
tilstrækkelig til overbevisende en computer, der er
sårbare over for at gøre noget at du vil have det at gøre,
fordi der er en fejl i Bash hvorved selvom Bash skulle stoppe
læsning kommandoveje ret der efter den gule tekst,
for en 20-plus år gamle fejl, Bash har faktisk været at læse
ud over dette semikolon og temmelig meget at gøre, hvad det er fortalt.
>> Så hvad er konsekvenserne af denne i sidste ende?
Jeg sagde bare "echo hej" eller "ekko sårbare,"
men hvad nu hvis du gjorde noget faktisk ondsindet, ligesom rm -rf *
som du måske ikke nogensinde har skrevet før,
og helt ærligt du sandsynligvis bør ikke for tidligt,
fordi du kan gøre en masse skade med den.
Hvorfor?
rm gør hvad, selvfølgelig?
Fjerner.
* Betyder hvad?
Alle.
Så det er en såkaldt wild card, så det betyder
slette alt i den aktuelle mappe.
r sker forstås rekursiv hvilket betyder, hvis det, du sletter
er en mappe, og inde i der er andre filer og andre mapper,
rekursivt dykke ned der og slette alt dette.
Og -f er den værste af dem alle.
Enhver ved, hvad -f betyder her?
Kraft.
Så tvinge midler, selv hvis det er en dårlig idé,
gøre det uden at spørge mig for yderligere bekræftelse.
Så, du ved, vi griner dette, men helt ærligt, jeg sandsynligvis
skriver dette flere gange, en dag, fordi virkeligheden
er det er den hurtigste måde at slette en hel masse ting.
Men selv jeg har gjort nogle skader.
>> Men hvis du var til at narre en computer i fastlæggelsen nogle dumme variabel
eller funktion kaldet x, men derefter narre computeren i fuldbyrdelsesstaten
ud over grænserne for at funktion ud over at semikolon,
du kunne faktisk narre en computer til udførelse af noget som rm -rf
eller e-mail-kommandoen eller kommandoen Kopier.
Alt bogstaveligt du kan gøre med den computer, uanset om det er at slette filer,
oprette filer, spamming nogen, angribe nogle server eksternt,
hvis du kan udtrykke det med en kommando, du
kan narre en computer, til at gøre det.
>> Nu, hvad der er et eksempel på hvordan du kan gøre dette?
Tja, der er en masse computere på internettet kører Bash.
Alle os Mac-brugere er blandt dem.
En masse af Linux-servere er blandt dem så godt, og Unix-servere.
Windows får igen relativt off the hook
medmindre du har installeret speciel software.
Nu er en masse servere for Eksempelvis køre webservere,
og i virkeligheden Linux er måske den mest populære operativsystem
til at køre på computere på internettet der tjener op websider.
Nu da vi vil se senere i semestret, når
du sende en anmodning fra Deres browser-- Chrome,
Internet Explorer whatever-- til en ekstern server,
det viser sig, at selvom du lige har skrevet www.example.com,
din browser sender en besked , der er lidt mere mystisk, som denne.
>> Men bemærk lidt noget mærkeligt.
De første to linier Jeg har aldrig set før,
men de ser ikke særlig truende.
Men mærke til, hvad jeg har stjålet for tredje linje her.
Hvis en slem fyr var at sende en besked som denne fra hans eller hendes computer
til en sårbar Mac eller en sårbar Linux server,
det sjove er, at Bash, at simpel lille kommandoprompt
er allestedsnærværende og er ofte brugt til i det væsentlige at udføre
indholdet af en budskab, som det modtager.
Og ved denne logik, kan du narre en web-server, derfor,
ved at sende noget lignende User-Agent, som normalt
formodes at sige Navn på din browser.
User-Agent Chrome, User-Agent Internet Explorer, User-Agent Firefox, dette
er bare din browser måde at identificere sig selv.
Men hvis en slem fyr meget behændigt siger, mm mm, er jeg
vil ikke fortælle dig hvad min browser er,
Jeg stedet vil sende dig dette kryptisk udseende ting med en rm -rf
* I det, kan du bogstaveligt talt narre en sårbar webserver på internettet
i udførelsen af ​​netop dette i der for at slette alle filerne.
Og helt ærligt, det er ikke selv den værste af det.
Du kan gøre noget.
Du kunne starte en distribueret denial of service angreb
Hvis du har sendt denne besked til hele klaser af webservere
og derefter havde dem alle ned for eksempel på Harvard.edu servere
og du kan sortere bang dælen ud af dem
af en netværkstrafik, der var ellers udløst af denne dårlige fyr.
>> Så lang historie kort, næsten alle i dette rum, der ejer en Mac
er sårbare over for denne.
Sølv foring er, at medmindre du er kører en webserver på din bærbare computer,
og medmindre du rent faktisk har konfigureret den til at tillade noget SSH ind i det,
du er faktisk sikker.
Det er sårbare, men der er ingen ene forsøger at komme ind i din bærbare computer,
så du kan slags forvisset.
Dog vil Apple snart være at opdatere en rettelse til dette.
En verden af ​​Linux har allerede udgivet en række rettelser til Fedora og Ubuntu
og andre versioner af Linux, og faktisk hvis du kører update 50 i apparatet,
selv der vil også være opdateret og korrigeret.
Men det er også ikke har rigtig været sårbare,
fordi medmindre du har puslede med apparatet
og lavet din bærbare offentligt tilgængelige på internettet, hvilket ikke er
som standard, har du faktisk været fint, fordi
af firewall og andre teknikker.
>> Men det er et ekstremt eksempel på en fejl at vi har levet for bogstaveligt 20
år, og hvem ved, hvis nogen al denne tid har kendt til det?
Og i virkeligheden, det er en af de fundamentale udfordringer
at vi vil se senere i semester om sikkerhed,
er, at ligesom i den virkelige verden, de gode fyre er på den ulempe.
For at holde de slemme fyre ud, er vi nødt til at sørge for, at alle døre er låst,
at hvert vindue er sikkert, at hvert punkt indrejse i et hjem
er sikkert at holde de slemme fyre ud.
Men hvad betyder den dårlige fyr er nødt til at gøre til rent faktisk at kompromittere dit hjem
og stjæle fra dig?
Han eller hun bare har at finde en ulåst dør, en brudt vindue, eller noget
langs disse linjer, og det er den samme ting i computersikkerhed.
Vi kan skrive millioner af linjer programkode
og bruge hundredvis eller tusindvis af timer forsøger at få det rigtige,
men hvis du laver bare en fejl i korrekthed,
du kan sætte hele systemet og faktisk i dette tilfælde hele internettet
og verden i fare.
>> Så hvis du gerne vil vide mere om dette, skal du gå til denne URL her.
Der er ikke behov for handling i aften, medmindre du er
blandt dem mere komfortable at har kørt din egen hjemmeside
server, i hvilket tilfælde du bør, i virkeligheden, opdatere din software.
>> Og det er også titlen på en tale, og nu et papir,
at vi har linket på kursets hjemmeside for dag.
Det var af en kollega opkaldt Ken Thompson, der
var at acceptere en meget berømt award i datalogi,
og han gav denne tale nogle år siden, hovedsagelig på samme emne.
Beder folk spørgsmålet, bør du virkelig
tillid i sidste ende software, du har fået?
For eksempel, vi alle har været at skrive programmer,
og vi har kompilere dem med Dunk.
Og til din viden, du har skrevet eventuelle programmer for CS50, hvor der er
en bagdør slags, er der en vej at en slem fyr, hvis der kører dit program,
kunne overtage din computer?
Sandsynligvis ikke, vel?
Mario, og grådige, og Credit.
Disse er alle temmelig små programmer.
Du er nødt til at være temmelig dårligt, hvis du rent faktisk
gjort hele din computer sårbar efter at skrive 10 eller 20 linjer kode,
eller mindst uvidende om nogle af de sikkerhedsmæssige konsekvenser.
Nu siger jeg, at facetiously, men vi kommer til at se i dag
og i denne uge er det faktisk virkelig, virkelig nemt
at være dårligt og gøre endnu korte programmer sårbare.
>> Men for nu, i det mindste indse at spørgsmålet bliver stillet her
er omkring Clang i en compiler.
Hvorfor har vi tillidsfuldt Dunk i de sidste to eller tre uger?
Hvem er at sige, at den, der skrev Dunk havde ikke en "hvis" betingelse derinde
at stort injiceres nogle nuller og dem ind i ethvert program kompileres
der ville lade ham eller hende adgang din computer, når du sover
og din laptop låg er åbent og din computer kører?
Right?
Vi har denne form for ære system ret nu hvor vi har tillid til, at Dunk er legit.
Du har tillid til, at apparatet er legit.
Du har tillid til, at bogstaveligt talt hver program på din Mac eller pc er troværdig.
Og da denne enkle fejl antyder, selv om det ikke er skadeligt,
Det er absolut ikke sandsynligvis vil være tilfældet.
>> Så du skal være bange som helvede.
Helt ærligt, der er ingen enkel anden løsning på dette
end en slags samfundsmæssig bevidsthed af den stigende kompleksitet
at vi bygger oven af vores edb-systemer,
og hvor mere sårbar Vi kan meget vel være.
>> Nu med det sagt, Breakout.
Så Breakout er problemet indstille tre, og Breakout er et spil fra gårsdagens
at du måske husker, men for os i problemet indstille tre,
det giver os mulighed for at tage tingene tilbage op et hak
så når vi skriver programmer, selv i et Terminal vindue som dette,
vi kan faktisk køre, i sidste ende, grafiske programmer, som ikke
i modsætning til dem, vi havde adgang til i Scratch.
Så dette er personalets gennemførelse af Breakout,
der er netop denne mursten-breaking spil, at du flytter din padle tilbage
og tilbage, og du rammer bolden mod de farvede klodser op øverst.
Så dette bringer os slags tilbage til hvor
Vi var i stand til meget hurtigt at være med Scratch, og nu med C,
implementere vores egen grafiske brugergrænseflader.
>> Men mere end det, det problem sæt repræsenterer den første
hvor vi giver dig en masse kode.
Og i virkeligheden, jeg bringe eksplicit opmærksom på dette, fordi især
for de mindre komfortabel, dette problem indstillet, i hvert fald ved første øjekast,
kommer til at føle sig som vi har taget det op et hak.
Fordi vi har givet dig, for nogle af søgningen
og sortering problemer i pset, en masse kode, som vi skrev,
og et par bemærkninger at sige "at gøre,"
hvor du er nødt til at udfylde de tomme felter.
Så ikke alt for skræmmende, men det er første gang
vi afleverer dig kode, som du har brug for at først læse, forstå og derefter tilføje til
og fuldføre den.
>> Og derefter med Breakout, vi kommer til at gøre det samme,
giver dig et par dusin flere linier kode, som helt ærligt, giver dig
en masse af rammerne for spillet, men stopper kort
gennemføre de mursten og bolden og pagaj,
men vi gennemføre nogle andre funktioner.
Og selv som ved første øjekast, igen, især hvis mindre behagelig,
kan virke særligt skræmmende og du tror, ​​der er så mange nye funktioner
du nødt til at pakke dit sind rundt, og det er sandt.
Men husk, det er helt ligesom Scratch.
Odds er du ikke bruge alle puslespilsbrikker i bunden.
Odds er du ikke pleje at ombryde dit sind omkring dem alle
fordi alle tog det var en hurtigt blik til at forstå, åh,
det er, hvad jeg kan gøre med denne brik.
Og ja, i problem sæt 3 spec, vil vi pege dig
på den dokumentation, der vil introducere dig til nogle nye funktioner,
og i sidste ende programmering konstruerer du bruger.
Betingelser, loops, variable og funktioner
vil være identisk med hvad vi har set hidtil.
>> Så ja, hvad vi vil give du er nogle eksempler på kode, der
Her kan du oprette et vindue der ser ikke ulig det,
og i sidste ende gøre det til noget helt ligesom dette.
Så drage fordel af CS50, diskutere kontortid og mere,
og tage trøst i det faktum, at mængden af ​​kode du skal skrive
er faktisk ikke så meget.
Den første udfordring er bare at akklimatisere dig selv til noget kode, vi har skrevet.
>> Eventuelle spørgsmål om pset3, Shellshock, eller på anden måde?
>> PUBLIKUM: Det virkede som går igennem med Breakout
at koden er næsten et objekt-orienteret stil,
men jeg troede AC var en objektorienteret program.
SPEAKER 1: En fremragende spørgsmål.
Så kigge gennem fordeling kode, koden
skrev vi til pset3, For dem bekendt, er det
ligner det er en lille objekt-orienteret.
Korte svar er, det er.
Det er en tilnærmelse af, hvordan du kan gøre objektorienteret kode ved hjælp
et sprog som C, men det er stadig i sidste ende proceduremæssige.
Der er ingen metoder inde i de variabler, som du kan se.
Men det minder om det.
Og vi vil se, at funktionen igen når vi kommer til PHP og JavaScript
mod slutningen af ​​semesteret.
Men for nu, så tænk på det som en antydning af, hvad der er at komme.
Godt spørgsmål.
Okay.
Så fusionere slags var, hvordan vi venstre ting sidste gang.
Og flette slags var cool i forstand, at det var så meget hurtigere,
mindst baseret på overfladisk test vi gjorde i sidste uge, end fx boble
sortere, udvælgelse sortere, indsættelse slags.
Og hvad var sirlige også er bare hvordan kortfattet og rent
du kan udtrykke det.
Og hvad gjorde vi sige, det var en øvre bundet på køretiden for merge
sortere?
Ja?
>> PUBLIKUM: n log n?
>> SPEAKER 1: n log n, til højre. n log n.
Og vi vil komme tilbage til, hvad det egentlig betyder, eller hvor der kommer fra,
men dette var bedre end hvad køretid
som vi oplevede for boble udvælgelse og indsættelse slags?
Så n potens. n kvadreret er større end dette,
og selvom det ikke er helt indlysende, ved, at log n er mindre end n,
så hvis du gør n gange noget mindre end n,
det kommer til at være mindre end n potens.
Det er lidt af intuition der.
Men vi betalte en pris for dette.
Det var hurtigere, men et tema, der startede at dukke op i sidste uge var denne afvejning.
Jeg fik bedre ydeevne tidsmæssigt, men hvad
jeg er nødt til at bruge på den anden hånd, for at opnå det?
>> Publikum: Hukommelse.
SPEAKER 1: Sig det igen?
Publikum: Hukommelse.
SPEAKER 1: Hukommelse, eller plads mere generelt.
Og det var ikke super indlysende med vores mennesker,
men minder om, at vores frivillige stepping frem og træde
tilbage, som om der er et array her, og som om der er
en anden gruppe her at de kunne bruge, fordi vi
tiltrængt sted at fusionere disse folk.
Vi kunne ikke bare bytte dem på plads.
Så fusionere slags gearing er mere plads, hvilket
vi behøvede ikke med de andre algoritmer,
men opadrettede er, at det er meget hurtigere.
Og helt ærligt, i den virkelige verden plads disse days-- ram, harddisk space--
er relativt billige, og så det er ikke nødvendigvis en dårlig ting.
>> Så lad os tage et hurtigt kig, lidt mere metodisk, hvad vi gjorde
og hvorfor vi sagde, at det var n log n.
Så her er de otte numre, og det otte frivillige, vi havde sidste gang.
Og den første ting, Merge Sorter fortalte os at gøre, var hvad?
Publikum: Opdel i to.
SPEAKER 1: Sig det igen?
Publikum: Opdel i to.
SPEAKER 1: Opdel i to, til højre.
Dette er meget minder om telefonbogen, i kløft
og erobre mere generelt.
Så vi kiggede på den venstre halvdel.
Og så når vi sagde, sortere den venstre halvdel af elementerne,
hvad gjorde vi næste sige?
Sortere den venstre halvdel af den venstre halvdelen, hvilket tillod os at,
efter deling i to, fokusere på fire og to.
>> Hvordan du sortere en liste nu, i gul, størrelse to, ved hjælp Flet Sort?
Nå opdele det på midten, og sortere den venstre halvdel.
Og det var, hvor tingene fik lidt dum kortvarigt.
Hvordan du sortere en liste, der er af Størrelse One, som dette nummer fire her?
Det er ordnet.
Du er færdig.
>> Men hvordan kan du sortere en liste over Størrelse One når det er nummer to?
Nå, samme ting, men nu hvad var tredje og afgørende skridt i Merge Sortér?
Du havde at fusionere venstre halvdelen og højre halvdel.
Og når vi gjorde det, vi kiggede på fire, vi kiggede på to.
Vi besluttede okay, naturligvis to kommer først,
så vi sætte to i sin sted, efterfulgt af fire.
Og nu er du nødt til at slags spole tilbage, og dette er slags karakteristiske
af en algoritme som Merge Sorter, spole tilbage i hukommelsen.
Hvad var den næste linje af historien?
Hvad skal jeg fokusere på næste?
Den højre halvdel af den venstre halvdelen, hvilket er seks og otte.
>> Så lad mig bare gå gennem denne uden belaboring punktet for meget.
Seks og otte, så seks er sorteret, otte er sorteret.
Flet dem sammen på den måde, og nu er den næste store skridt
er naturligvis sortere højre halvdel fra det allerførste skridt i denne algoritme.
Så vi fokuserer på en, tre, syv, fem.
Vi derefter fokusere på den venstre halvdel.
Den venstre halvdel af det, den højre halvdel af det, og derefter flette i én og tre.
Så den højre halvdel, derefter til venstre halvdel af det, så den højre halvdel af det.
Flet det i, og hvad nu skridt tilbage?
Flet den store venstre halvdel og den store højre halvdel, så man går dernede,
derefter to, så tre, så fire, så fem, så seks og derefter syv, derefter otte.
>> Så nu, hvorfor er dette i sidste ende afslører, især hvis n og logaritmer mere
generelt hellere slippe dig, i hvert fald i nyere tid?
Nå, mærke højden af ​​denne ting.
Vi havde otte elementer, og vi delte det med to, og to, med to.
Så log basis to af otte giver os tre.
Og tro mig på, at hvis lidt diset på det.
Men log basis to af otte er tre, så vi har gjort tre lag af sammenlægning.
Og da vi fusionerede elementer, hvor mange elementer
vi se på på hver af disse rækker?
I alt n, right?
Fordi at fusionere den øverste række, selvom vi gjorde det stykkevis,
vi rørt i sidste ende hvert nummer en gang.
Og i anden række, at flette disse lister af størrelse to,
vi var nødt til at røre hvert element én gang.
Og så virkelig her tydeligt i den sidste række,
vi var nødt til at røre ved hver af disse elementer én gang, men kun én gang,
så heri ligger, så vores n log n.
>> Og nu bare for at gøre tingene lidt mere formelle for bare et øjeblik, hvis du
skulle nu analysere dette ved en slags højere niveau
og forsøge at beslutte, godt, hvordan kan du gå om at udtrykke
køretiden for denne algoritme bare ved at kigge på det og ikke
ved hjælp af en kunstig eksempel?
Nå, hvor meget tid ville du sige en træde som denne i gul ville tage,
hvis n <2 gengæld?
Det er en stor O i hvad?
Så jeg ser en, så et skridt, måske to trin, fordi det er hvis
og derefter vende tilbage, men det er konstant tid, ikke?
Så vi sagde O (1), og det er hvordan jeg skal udtrykke dette.
T, bare være køretid.
n er størrelsen af ​​input, så T (n), bare en fancy måde
sige drift tid givet input af størrelse n
vil være af størrelsesordenen konstant tid, i O (1).
>> Men ellers, hvad med det her?
Hvordan vil du beskrive køretid for denne gule linje?
T i hvad?
Du kan slags snyde her og besvare mit spørgsmål cyklisk.
Så hvis køretiden i Generelt siger vi bare er T (n).
Og nu er du slags punting her og sige, godt, bare sortere den venstre halvdel,
og derefter sortere den højre halvdel.
Hvordan kan vi symbolsk køretiden for denne gule linje?
T i hvad?
Hvad er størrelsen af ​​input?
n over to.
Hvorfor kan jeg ikke bare sige det?
Og så er det en anden T (n / 2) og derefter igen, hvis jeg flette to sorterede halvdele,
hvor mange elementer skal jeg hen nødt til at røre ved alt?
n.
Så jeg kan udtrykke dette, bare for at være slags fancy,
som køretiden i almindelighed.
T (n) er blot køretiden for T (n / 2), plus T (n / 2), venstre halvdel og højre halvdel,
plus O (n), som er sandsynligvis n trin, men måske, hvis jeg bruger to fingre,
det er dobbelt så mange trin, men det er lineær.
Det er nogle antal trin det er en faktor af n,
så vi kan udtrykke dette som dette.
Og det er her, vi nu vil punt til bagsiden af ​​vores high school math lærebog
vi er at tilbagefald i sidste ende ender svarende dette n gange log n,
hvis du rent faktisk gør ud math mere formelt.
>> Så det er kun to perspektiver.
En numerisk med en hard-kodet repræsentativt eksempel
hjælp otte numre, og en mere generel kig på, hvordan vi fik der.
Men hvad der er virkelig interessant her er, igen, denne forestilling om cykling.
Jeg bruger ikke efter sløjfer.
Jeg er lidt at definere noget i form af sig selv,
ikke kun med denne matematisk funktion,
men også i form af denne pseudo kode.
Denne pseudokode er rekursive i, at to af dens linjer
hovedsagelig fortæller det til at gå benytte sig at løse et mindre
Problemet med mindre størrelse, og derefter igen og igen
og igen, indtil vi skære det ned til denne såkaldte base case.
>> Så lad os faktisk tegne en mere overbevisende take-away fra det som følger.
Lad mig gå ind i gedit og tage en se på nogle af dagens kildekode,
især dette eksempel her.
Sigma 0, hvilket tilsyneladende tilføjer numrene en gennem n.
Så lad os se, hvad der er velkendt og ukendte her.
Først har vi et par omfatter, så intet nyt der.
Prototype.
Jeg er lidt diset på dette efter få dage,
men hvad gjorde vi sige en prototype af en funktion er?
Publikum: [uhørligt].
SPEAKER 1: Hvad er det?
PUBLIKUM: Vi annoncere det.
SPEAKER 1: Vi offentliggør det.
Så du underviser Dunk, hey, faktisk ikke at gennemføre dette endnu,
men et eller andet sted i denne fil, formodentlig vil være en funktion kaldet hvad?
Sigma.
Og dette er blot et løfte om, at det kommer til at se sådan ud.
Det kommer til at tage et heltal som input-- og jeg kan være mere eksplicit
og sige int n DET-- det er vil returnere en int,
men semikolon midler, mm, jeg får rundt at gennemføre dette lidt senere.
Igen Clang er stum.
Det er kun kommer til at vide, hvad du fortælle det top til bund,
så vi er nødt til i det mindste give det en antydning af, hvad der er at komme.
>> Lad os nu se på vigtigste her.
Lad os rulle ned her og se hvad main gør.
Det er ikke så længe for en funktion, og faktisk konstruktionen her er velkendte.
Jeg erklærer en variabel n, og derefter Jeg plager brugeren igen og igen
til et positivt heltal ved hjælp getInt, og kun udgang ud af denne løkke
når brugeren har opfyldt.
Gør Mens vi har brugt til forpeste brugeren på den måde.
Nu er det interessant.
Jeg erklærer en int kaldet "svar".
Jeg tildeler det returværdien af en funktion kaldet "sigma".
Jeg ved ikke, hvad der gør endnu, men Jeg husker at erklære det for et øjeblik siden.
Og så jeg passerer i værdi, som brugeren har indtastet, n,
og så skal jeg rapportere svaret.
Jamen så lad os rulle tilbage for bare et øjeblik.
Lad os gå videre ind i denne mappe, gør sigma 0, og faktisk køre dette program
og se hvad der sker.
Så hvis jeg gå videre og køre dette program ./sigma-0,
og jeg skriver i en positiv heltal som to, Sigma,
som den græske symbol antyder, er bare kommer til at tilføje op alle de tal fra
nul på op til to.
Så 0 plus 1 plus 2.
Så dette vil forhåbentlig give mig 3.
Det er alt den gør.
Og på samme måde, hvis jeg køre dette igen og jeg give det et nummer tre,
der er 3 plus 2, så det er 5 plus 1 skulle give mig 6.
Og så hvis jeg får virkelig skøre og begynde at skrive i større tal,
det bør give mig større og større beløb.
Så det er alt.
>> Så hvad betyder sigma se ud?
Tja, det er temmelig ligetil.
Det er, hvordan vi kunne have gennemført dette for de sidste par uger.
"Int" kommer til at være en tilbagevenden type.
Sigma er navnet, og det tager en variabel m i stedet for n.
Jeg vil ændre det op toppen.
Så er dette blot en tilregnelighed check.
Vi vil se, hvorfor i et øjeblik.
Nu Jeg erklærer en anden variabel, sum, initialisere den til nul.
Så jeg har denne For-løkke iteration, tilsyneladende for klarhed,
fra i = 1 på op til = m, hvilket er hvad brugeren har skrevet i, og så er jeg
øg beløb som denne.
Og derefter returnere beløb.
>> Så et par spørgsmål.
En, jeg hævder i min kommentar, at dette undgår risikoen for en uendelig løkke.
Hvorfor skulle passere i et negativt tal fremkalde potentielt en uendelig løkke?
>> Publikum: Du vil aldrig nå meter.
>> SPEAKER 1: Aldrig nå m.
Men m er gået i, så lad os Overvej et simpelt eksempel.
Hvis m er gået ind af brugeren som negativ.
Uanset main.
Vigtigste beskytter os mod dette også, så jeg er bare
bliver virkelig anal med sigma også sikre
at input ikke kan være negativ.
Så hvis m er negativ, noget som negativ.
Hvad kommer til at ske?
Nå, jeg går til bliver initialiseret til en,
og så er jeg kommer til at være mindre end eller lig med m?
>> Standby.
Det var-- lad os ikke, lad os nix denne historie.
Jeg spurgte ikke, at spørgsmål, fordi risikoen for, at jeg hentyder til
kommer ikke til at ske, fordi jeg er altid vil være større than-- OK,
Jeg trække det spørgsmål.
OK.
Lad os kun fokusere på denne del her.
Hvorfor gjorde jeg erklære nogle uden for loop?
Meddelelse om linje 49 Jeg har erklæret i indersiden af ​​løkken,
men online 48 Jeg har erklæret nogle uden.
Ja.
Publikum: [uhørligt].
SPEAKER 1: Selvfølgelig.
Så først og fremmest jeg bestemt ikke ønsker at erklære og initialisere sum
til nul inde i løkke på hver iteration
fordi dette klart vil besejre Formålet opsummering tallene.
Jeg ville holde skiftende værdien tilbage til nul.
Og også, hvad er en anden mere mystisk Grunden til det samme design beslutning?
Ja.
>> Publikum: [uhørligt].
SPEAKER 1: Præcis.
Jeg vil have adgang til det udenfor af løkken også på hvilken linje?
Den 53.
Og baseret på vores tommelfingerregel fra et par forelæsninger siden,
variabler virkefelt, virkelig, til krøllede parenteser, der omfatter dem.
Så hvis jeg ikke erklære sum inde af disse ydre krøllede parenteser,
Jeg kan ikke bruge det på linje 53.
Sagt på en anden måde, hvis jeg erklærede sum i her, eller endog inden for
For-løkke, kunne jeg ikke få adgang til det i 53.
Den variable vil reelt være væk.
Så et par grunde der.
Men lad os nu gå tilbage og se hvad der sker.
Så sigma bliver kaldt.
Det tilføjer op 1 plus 2 eller 1 plus 2 plus 3 og derefter returnerer værdien,
gemmer det i svar, og printf her er derfor, jeg ser på skærmen.
Så dette er hvad vi vil kalde en iterativ tilgang, hvor iteration bare
: anvendelse af en løkke.
En for-løkke, en while-løkke, en skal mens loop, bare gør noget igen
og igen og igen.
>> Men Sigma er sådan en pæn funktion i at jeg kunne gennemføre det anderledes.
Hvad med dette, hvilket bare for at være lidt cool,
lad mig virkelig slippe af en masse distraktion
fordi denne funktion er faktisk ganske enkel.
Lad os skære det ned lige til sine fire centrale linjer
og slippe af med alle de kommentarer og krøllede parenteser.
Det er lidt af en mind-blowing alternativ implementering.
Okay, måske ikke mind-blowing, men det er lidt mere sexet, okay,
at se på dette så meget mere kortfattet.
Med blot fire linjer kode, Jeg først har denne tilregnelighed check.
Hvis m er mindre end eller lig med nul, Sigma giver ingen mening.
Det er kun meningen at være i dette tilfældet for positive tal,
så jeg bare til returnere nul vilkårligt
så vi i det mindste have nogle såkaldt base case.
>> Men her er det skønhed.
Hele denne idé, tilføjer den tal fra 1 til n eller m i denne sag,
kan gøres ved slags lade sorteper.
Nå, hvad er summen af ​​1 til m?
Tja, ved du hvad?
Det er det samme som summen af ​​m plus summen af ​​1 m minus 1.
Jamen ved du hvad?
Hvad er sigma af m minus 1?
Tja, hvis du slags følge denne logisk, det er det samme som m minus 1
plus sigma af m minus 2.
Så du kan slags bare-- dette er ligesom, hvis du bare
forsøger at irritere en ven og de beder dig et spørgsmål,
du slags reagere med et spørgsmål, du kan slags holde passerer sorteper.
Men hvad er afgørende, er, at hvis du holder at spørgsmålet mindre og mindre
og mindre, er du ikke spørge, hvad der er sigma
af n, hvad er sigma af n, hvad er sigma af n?
Du spørger, hvad er sigma af n, hvad er sigma
af n minus 1, hvad er sigma af n minus 2?
Til sidst dit spørgsmål kommer til at blive, hvad?
Hvad er sigma af en eller nul, et meget lille værdi,
og så snart du få det, din ven,
du ikke kommer til at spørge det samme spørgsmål igen,
du vil bare sige, åh, det er nul.
Vi er færdig med at spille denne slags dumme cykliske spil.
>> Så rekursion er den handling i programmeringen for en funktion kalder sig.
Dette program, der udarbejdes og løbe, er kommer til at opføre sig på nøjagtig samme måde,
men hvad er nøglen er, at inde af en funktion kaldet sigma
der er en linje af kode, hvor Vi kalder os selv,
som normalt ville være dårligt.
For eksempel, hvad nu hvis jeg først kompileret dette, så gør sigma--
at sigma 1 ./sigma-1.
Positivt heltal, please, 50 1275.
Så hvad funktionen synes at være baseret på en test korrekt.
Men hvad nu hvis jeg får en lidt farlig og slette den såkaldte base case,
og bare sige, godt jeg bare gøre dette mere kompliceret, end det er.
Lad os bare beregne sigma ved at tage m, og derefter tilsætte
i sigma af m minus en?
Nå, hvad der kommer til at ske her?
Lad os zoome ud.
Lad os kompilere programmet, gemme det, rekompilere programmet
og derefter klar ./sigma-1 zoome ind, indtaste positivt heltal venligst, 50.
Hvor mange af jer er villige at Fess op til at se det?
>> OK.
Så dette kan ske for en række årsager,
og helt ærligt i denne uge er vi ved at give dig flere af dem.
Men i dette tilfælde, så prøv at ræsonnere baglæns
hvad der kunne være sket her?
Segmenteringsfejl, vi sagde sidste tid, henviser til et segment af hukommelse.
Noget slemt er sket.
Men hvad var det mekanisk, der gik galt
her på grund af min udsendelse af denne såkaldte base case,
hvor jeg vendte tilbage en hard-kodet værdi?
Hvad tror du der gik galt?
Ja.
>> Publikum: [uhørligt].
SPEAKER 1: Ah.
Godt spørgsmål.
Så størrelsen af ​​det antal at jeg var opsummering
fik så store, at det overskred størrelsen af ​​den hukommelse.
God idé, men ikke fundamentalt kommer til at forårsage et nedbrud.
Det kan forårsage heltalsoverløb, hvor de bits bare vendes
og så vi forveksler en virkelig stor nummer som et negativt tal,
men at selv ikke vil forårsage et styrt.
Fordi i slutningen af dag en int er stadig 32 bit.
Du kommer ikke til uheld stjæle en 33. bit.
Men en god tanke.
Ja.
>> Publikum: [uhørligt].
SPEAKER 1: Metoden aldrig stoppet,
og ja det kalder sig igen og igen og igen og igen
og igen, og ingen af disse funktioner nogensinde
færdig, fordi deres eneste linje af kode kalder sig selv igen og igen
og igen.
Og hvad der er virkelig sker her, og nu har vi
kan slags tegne dette billedligt.
Lad mig gå over til en billede for bare et øjeblik.
Dette er et billede, der i sidste ende vil konkretisere
mere detaljeret, hvad der foregår på indersiden af ​​din computers hukommelse.
Og det viser sig, at der på bunden af ​​dette billede
er noget, der hedder stakken.
Dette er et stykke hukommelse, en luns af RAM,
der er bare brugt nogen tid en funktion kaldes.
Hver gang du, en programmør, kalde en funktion,
operativsystemet, ligesom Mac OS, Windows eller Linux,
griber en flok bytes, måske en kilobytes, måske få megabyte
hukommelse, hænder dem til dig, og derefter lader
du kører din funktion ved hjælp uanset variabler, du har brug for.
Og hvis du så kalde en anden funktion og en anden funktion,
du får en anden skive hukommelse og en anden skive hukommelse.
>> Og ja, hvis disse grønne bakker fra Annenberg repræsenterer den hukommelse,
her er hvad der sker den første gang du kalder funktionen sigma.
Det er ligesom at sætte en bakke som denne på hvad der er i første omgang en tom stak.
Men derefter, hvis denne bakke kalder sig selv, så at sige,
ringer til en anden instans Sigma, der er
som at bede operativsystemet, ooh, har brug for lidt mere hukommelse,
Giv mig den.
Og så det bliver stablet på på toppen.
Men hvad er nøglen her, er, at den første bakke er der stadig,
fordi han påberåbt sig denne anden bakke.
Nu mellemtiden sigma kalder sigma det er ligesom at bede om mere hukommelse.
Gets stablet på herovre.
sigma kalder sigma, det er en anden bakke, der bliver stablet på her.
Og hvis du bliver ved med at gøre dette, i sidste ende, at slags kort denne visuelle
for det pågældende kort, hvad der kommer til ske med stablen af ​​bakker?
Det kommer til at overstige det beløb, hukommelse din computer har.
Og så snart denne grønne bakke overstiger den vandrette linje
over stakken og over ordet dynge, som vi vil vende tilbage til i fremtiden,
det er en dårlig ting.
Den bunke er en anden segment af hukommelse,
og hvis du lader disse bakker bunke og bunke på,
du kommer til at overskride dit eget segment af hukommelse,
og et program er faktisk kommer til at gå ned.
>> Nu som en sidebemærkning, denne idé rekursion derfor
kan tydeligt føre til problemer, men det er ikke nødvendigvis en dårlig ting.
Fordi overveje, efter alt hvordan-- og måske
det tager lidt tid at vænne til-hvor elegant eller hvordan enkle
at gennemførelsen af ​​sigma var.
Og vi kommer ikke til at bruge rekursion så meget i CS50,
men i CS51, og virkelig enhver klasse hvor du manipulerer datastrukturer
som træer, eller stamtræer, at have en vis hierarki
det er super, super nyttige.
Nu, som en sidebemærkning, så du som håbefulde dataloger
er bekendt med nogle af Googles interne jokes, hvis du går til Google
og du ser op, hvad er det definition af, siger, rekursion, indtast.
Uh-huh.
Som en sidebemærkning, jeg trak op et par stykker.
Dette var ligesom 10 minutter af tøven i morges.
Hvis du også Google "skævt", bekendtgørelse ved at vippe dit hoved slightly--
og så denne ene er måske mest grusomme af alle
da en person brugt ligesom deres dag gennemførelse af denne
nogle år ago-- komme videre.
Åh, wait-- det er en fejl.
>> Så kører på en af ​​de verdens største hjemmesider
er disse dumme små påskeæg.
De forbruger sandsynligvis en nontrivial antal linjer kode
bare så vi kan få lidt sjov ting.
Men i det mindste nu får du nogle af disse inde vittigheder.
>> Lad os nu tage et kig på nogle af de White Lies vi har fortalt for sent,
og begynde at skrælle tilbage nogle lag teknisk
så du virkelig forstår hvad der er foregået på
og du kan forstå nogle af de trusler,
Ligesom Shellshock, at er nu begyndt at blive
på forkant med alles vægt, i det mindste i medierne.
Så her er en meget simpel funktion der returnerer ingenting, ugyldige.
Dens navn er swap.
Det tager i to variabler og det returnerer ingenting.
Tager i a og b.
Så en hurtig demonstration.
Vi bragte dem op.
Vi kan lige så godt tage lidt pause her for et øjeblik
og har lidt noget at drikke.
Hvis nogen ikke har noget imod at tilslutte mig op her for et øjeblik.
Hvad med dig i rødbrun skjorte?
Kom op.
Blot én dag.
Tak, selv om.
Okay, og vi har kommer op der her?
Hvad er dit navn?
>> SPEAKER 4: Laura.
>> SPEAKER 1: Laura.
Kom op.
Så Laura, meget enkel udfordring i dag.
Rart at møde yo.
Okay.
Så vi har nogle mælk herover og vi har nogle appelsinsaft herovre
og nogle kopper, vi lånt fra Annenberg dag.
>> SPEAKER 4: Lånt.
SPEAKER 1: Og kommer til at gå videre og give dig et halvt glas dette.
Okay.
Og vi vil give dig halvdelen et glas mælk.
Åh, og bare så du kan huske, hvad det var ligesom,
Jeg huskede at bringe dette op og på i dag.
Okay.
Hvis du ikke har noget imod, lad os se, vi kan sætte dem over dine egne briller
hvis du vil.
Dette vil være den verden fra Lauras øjne.
Okay.
Så dit mål, da to kopper flydende her, mælk og appelsinjuice,
er bytte de to indholdet, så det appelsinjuice går i mælken kop
og mælken går i appelsinsaft kop.
>> SPEAKER 4: Får jeg en kop?
SPEAKER 1: Jeg er så glad for du spurgte, selv om det ville have været meget bedre optagelser
hvis du ikke havde spurgt.
Men ja, kan vi tilbyde dig en tredje kop, der er tom, selvfølgelig.
Okay.
Så bytte indholdet der.
Very nice.
Meget godt.
Du gør dette bemærkelsesværdigt omhyggeligt.
Og trin tre.
Okay.
Fremragende.
Et stort bifald ville være godt for Laura.
Okay.
Vi har en lille afskedsgave for dig, men lad mig tage dem.
Tak så meget.
Så et simpelt eksempel, selv om, at vise, at hvis du gør
vil bytte indholdet af to containere,
eller lad os kalde dem variabler, du har brug for nogle midlertidige opbevaring
at iscenesætte et af indholdet i så at du rent faktisk kan gøre swappen.
Så ja, denne kildekode op her i C er repræsentativt for netop dette.
Hvis appelsinsaft var og mælken var B, og vi ønskede at bytte de to,
du kunne prøve noget kreativt ved at hælde en i den anden,
men det sandsynligvis ikke ville ende særlig godt.
Og så bruger vi en tredje kop, opkald det tmp, T-M-P af konventionen,
og sætte indholdet af EFT i det, så bytte en kop,
derefter sætte EFT i oprindelige kop, hvorved
nå, præcis som Laura gjorde, swappen.
>> Så lad os gøre netop dette.
Lad mig gå videre og åbne op et eksempel, der er
faktisk kaldt "nej swap ", fordi det ikke er
som blot gjort, som du måske tror.
Så i dette program, bemærk at Jeg bruger stdio.h, vores gamle ven.
Jeg har prototypen til swap deroppe, som
betyder dens gennemførelse er sandsynligvis ned nedenfor,
og lad os se hvad denne hoved Programmet kommer til at gøre for mig.
Jeg først erklære int x får en, og int y får to.
Så tænk på dem som EFT og mælk, hhv.
Og så er jeg bare have en printf siger x er dette
og y er det, bare så jeg kan visuelt se, hvad der foregår.
Så jeg har printf hævder at jeg bytte de to,
og så vil jeg udskrive en hævder, at de er byttet,
og jeg udskrive x og y igen.
Så hernede i swap er præcis, hvad Laura gjorde,
og præcis hvad vi så på skærmen et øjeblik siden.
>> Så lad os gå videre og blive hårdt skuffet.
Gør nogen swap, og køre nogen swap, zoomer ind på outputtet her.
Indtast x er 1, y er 2, bytte byttes.
x er stadig 1, og y er stadig 2.
Så selvom ærligt, det ser præcis gerne, omend mere teknisk,
hvad Laura gjorde, ikke synes at arbejde.
Så hvorfor er det?
Tja, det viser sig, at når vi skriver et program som dette
der har både hoved, fremhævet her, og derefter en anden funktion, ligesom swap,
fremhævet her, som det opfordrer verden
ser lidt noget lignende disse bakker et øjeblik siden.
Når vigtigste først bliver kaldt, det er som at spørge styresystem
for lidt hukommelse til enhver lokal variabler som x og y som vigtigste har,
og de ender dér.
Men hvis de vigtigste opkald bytte, og de vigtigste passerer at bytte to argumenter, a og b,
appelsinjuice og mælk, det er ikke som rakte appelsinsaft og mælk
Laura.
Hvad en computer gør, er det passerer kopier af appelsinsaft
og kopier af mælken til Laura, så der hvad der er i sidste ende inde i denne bakke
er værdien et og to eller EFT og mælk, men kopier heraf,
således at der på dette punkt i historien, der
er EFT og mælk i hver af disse bakker.
Der er en en og en to i hver af disse bakker,
og swap-funktionen er faktisk fungerer.
Det er at bytte dem inde af det andet øverste bakke,
men at swapping har ingen indvirkning.
Og baseret på blot nogle grundlæggende princip, vi har
talte om før, og faktisk blot et par minutter siden, hvad
kan forklare, hvorfor skiftende a og b indersiden af ​​swap
har ingen effekt på x og y, selv om Jeg passerede x og y til swap-funktionen.
Hvad er nøgleordet her, at måske simplistisk forklare?
Jeg tror, ​​jeg hørte det her?
Publikum: Retur.
SPEAKER 1: Return?
Ikke vende tilbage.
Lad os gå med en anden.
Hvad er det?
>> Publikum: [uhørligt].
>> SPEAKER 1: OK, så return-- vi kunne gøre tilbagevenden arbejde i historien,
men der er en endnu enklere forklaring.
Publikum: Scope.
SPEAKER 1: Scope.
Jeg tager rækkevidde.
Så rækkevidde, huske, hvor vores x og y er erklæret.
De er erklæret inde af de vigtigste lige heroppe.
a og b, i mellemtiden, er effektivt erklæret
indersiden af ​​swap, ikke helt i de krøllede parenteser, men stadig
i det generelle område af swap.
Og så ja, a og b kun eksistere inden denne bakke
fra Annenberg dette anden luns af kode.
Så vi er faktisk at ændre kopien, men det er ikke virkelig alt, nyttige.
>> Så lad os tage et kig på denne lidt lavere niveau.
Jeg har tænkt mig at gå tilbage til Source Directory,
og jeg har tænkt mig at først zoome ind her, og bare
at bekræfte, at jeg er i dette større terminal vindue,
Programmets stadig opfører sig sådan.
Antag nu, at dette er ikke tilsigtet.
Klart jeg ville swap til arbejde, så det føles som en fejl.
Nu kunne jeg begynde at tilføje en masse printf er til min kode,
udskrivning ud x herovre, iy over her, en herovre, B herovre.
Men helt ærligt, det er hvad sandsynligvis du har gjort for et par uger
nu, i kontortiden og hjemme, når du arbejder
på psets forsøger at finde nogle bugs.
Men du vil se, hvis du ikke allerede har, dette problem indstille tre introducerer dig
til en kommando kaldet GDB, hvor GDB, GNU debugger,
har selv en hel masse funktioner, der kan faktisk
lad os forstå situationer som dette, men mere overbevisende,
løse problemer og finde fejl.
Så jeg har tænkt mig at gøre dette.
I stedet for ./noswap, jeg er i stedet kommer til at køre GDB ./noswap.
Med andre ord, vil jeg køre min programmet ikke i bash, vores nye ven
dag.
Jeg har tænkt mig at køre min program noswap inde
af dette andet program kaldet GDB, hvilket er en debugger, som
er et program, der er designet til at hjælpe I mennesker finde og fjerne fejl.
Så hvis jeg ramte Køre her, der er en grusom mængde tekst
at du virkelig aldrig nødt til at læse.
Det er hovedsagelig en distraktion fra prompt, som
Jeg har tænkt mig at ramme Ctrl-L at komme op på toppen er der.
Dette er GDB-prompten.
Hvis jeg ønsker at køre dette program nu, da denne lille snyde ark på dagens
dias antyder, Run er den første kommandoer, vi betød at indføre.
Og jeg bare at skrive køre op her inde i GDB,
og ja det kørte mit program.
Nu er der nogle ekstra udgange af skærmen som dette,
men det er GDB blot er anal og fortæller os, hvad der foregår.
Du behøver ikke virkelig nødt til at bekymre sig om disse oplysninger lige nu.
Men hvad er virkelig cool om GDB, hvis jeg gør det igen--
Ctrl-L rydder screen-- lade mig gå fremad og type "bryde hoved," derved,
når jeg trykker på Enter, indstilling, hvad der er kaldet en pause punkt noswap.c,
linie 16, hvilket er hvor GDB regnet ud mit program faktisk
er min funktion faktisk er.
Dette vil vi ignorere for nu men det er den adresse
i hukommelsen specifikt om denne funktion.
Så nu når jeg skriver løbe, mærke til, hvad der er køligt her.
Mit program bryder på den linje, jeg fortalte GDB at holde pause udførelse på.
Så jeg behøver ikke at nu ændre min kode, tilføje nogle printf s, rekompilere det, skal du køre
det, ændre, tilføje nogle printf s, gemme det, rekompilere det, køre den.
Jeg kan bare gå gennem mit program trin for trin for trin ved menneskelig hastighed,
ikke på Intel-inside slags hastighed.
>> Så nu mærke til denne linje vises her, og hvis jeg gå tilbage
til mit program i gedit, bemærke, at det er faktisk
den allerførste linje kode.
Der er linie 16 i gedit.
Der er linie 16 i GDB, og selv selv om denne sorte og hvide grænseflade
er ikke nær så bruger børn, betyder dette
denne linje 16 er ikke udført endnu, men det handler om at være.
Så ja, hvis jeg skriver print x, ikke printf, bare tryk x,
Jeg får nogle falske værdi der på nul, da x ikke er blevet initialiseret endnu.
Så jeg har tænkt mig at skrive næste, eller, hvis du ønsker at være fancy, bare n Til næste.
Men når jeg skriver næste komme ind, nu bemærke det går videre til linie 17.
Så logisk, hvis jeg har henrettet linie 16 og jeg nu skriver print x,
hvad skal jeg se?
One.
>> Og nu er det ganske vist forvirrende.
$ 2 er bare en fancy måde, hvis du ønsker at henvise til denne værdi senere,
du kan sige "dollartegn to."
Det er ligesom en back reference.
Men for nu, bare ignorere det.
Det interessante er, hvad der er på højre side af lighedstegnet.
Og nu, hvis jeg skriver næste gang og udskrive y, skal jeg se 2.
Jeg kan nu også udskrive x igen, og helt ærligt,
hvis jeg får lidt forvirret med hensyn til hvor jeg er, kan jeg skrive liste for liste
og bare se nogle sammenhæng omkring det punkt er jeg faktisk på.
Og nu kan jeg skrive næste, og der x er 1.
Nu skriver jeg næste.
Åh, y er 2.
Og igen, det er forvirrende, fordi GDB produktion
bliver blandet med min egen produktion.
Men hvis du huske på, ved kigger frem og tilbage på din kode
eller om det ud side side måske, vil du
se, at jeg virkelig er bare stepping gennem mit program.
>> Men mærke til, hvad der sker næste, bogstaveligt talt.
Her er linie 22.
Lad mig gå over det, og derved bevæger sig på til 23, og hvis jeg udskriver x nu, stadig en.
Og hvis jeg udskrive y nu, stadig en.
Så dette er ikke en nyttig øvelse.
Så lad os gentage denne.
Lad mig gå tilbage op til top og type køre igen.
Og det siger programmet der bliver fejlrettet
er allerede begyndt, startede fra begyndelsen.
Ja, lad os gøre det igen.
Og denne gang lad os gøre næste, næste, næste, næste, næste,
men nu tingene bliver interessante.
Nu vil jeg træde ind swap, så kan jeg ikke skrive det næste.
Jeg skriver skridt, og nu mærke til det har sprunget mig til noswap.c linje 33.
Hvis jeg går tilbage til gedit, hvad er linje 33?
Det er den første egentlige linje kode inde i swap.
Hvilket er rart, fordi jeg nu kan slags poke rundt og få nysgerrige
om, hvad der foregår i sandhed derinde.
Lad mig udskrive tmp.
Whoa.
Hvorfor tmp har nogle skøre, fup skrald værdi?
PUBLIKUM: Det er ikke blevet initialiseret.
SPEAKER 1: Det er ikke blevet initialiseret.
Og ja, når du kører et program, du er givet en hel bunke af hukommelse
af operativsystemet, men du har ikke initialiseret nogle værdier,
så uanset bit du se her, selvom det er
denne vanvittige stor negativ nummer, betyder bare,
at det er de rester fra nogle tidligere brug af denne RAM,
selvom jeg har ikke selv havde brug for det endnu.
Så nu har jeg tænkt mig at gå videre og typen næste, og hvis jeg nu skriver print tmp
hvad skal jeg se?
Uanset værdien af ​​en var a er det første argument, bare
Ligesom x var den første ting bliver vedtaget i,
så en og x skal være den samme, så udskrive TMP bør udskrive mig en.
>> Så hvad du vil se i problem sæt tre er en tutorial slags på GDB,
men indse, at dette er begyndelsen af et kig på et værktøj, der vil faktisk
hjælpe dig med at løse problemer så meget mere effektivt.
Hvad vi er i sidste ende kommer til at gøre på onsdag
er begynde at skrælle et par lag og fjerne nogle støttehjul.
Denne ting kaldet streng, vi har brugt i nogen tid,
vi vil langsomt tage det væk fra dig og begynde at tale om
noget mere esoterisk kendt som char *,
men vi vil gøre dette nice og først svagt, selvom pegepinde,
som de kaldes, kan gøre nogle meget dårlige ting hvis de misbruges,
ved at se på en lille claymation fra vores ven Nick Parlante fra Stanford
University, professor i computer videnskab, der tilsammen denne forhåndsvisning
af, hvad der er at komme denne onsdag.
>> [VIDEOAFSPILNING]
Hey, Binky.
Vågn op.
Det er tid til pointer sjov.
>> Hvad er det?
Lær om pointers?
Åh, goody!
[END VIDEO PLAYBACK]
SPEAKER 1: der venter dig på onsdag.
Vi vil se dig derefter.
[VIDEOAFSPILNING]
-Og Nu, dybe tanker, af Daven Farnham.
>> Hvorfor lærer vi C?
Hvorfor ikke A +?
>> [Latter]
>> [END VIDEO PLAYBACK]