>> [Musikk spilles]
>> SPEAKER 1: Ok, dette er CS50, og dette er begynnelsen av uke fire,
og som du kanskje har hørt eller lese, har verden blitt slutt.
Går alle rundt på internett har vært kunnskap og bevissthet
av en feil i et program, en programmeringsspråk kalt Bash.
Dette har vært fantastisk branded som Shellshock, eller Bash døren,
men artikler som dette har ikke vært uvanlig.
Og faktisk, mange av dem bringe tilbake minner Heartbleed,
som du kanskje har lagt merke til i trykk tilbake denne siste våren, som
var tilsvar ganske dramatisk.
Nå for de av dere her i dag, hvor mange av dere har,
selv om du ikke forstår hva det handler om, hørt om Shellshock?
Greit, og hvor mange av dere har datamaskiner som er sårbare?
OK, bør det være langt, langt flere hender opp akkurat nå, av grunner vi skal se.
>> La oss ta en titt på hva som er pågått i media
og deretter forklare det litt her for oss teknisk.
>> SPEAKER 2: Sikkerhetseksperter har advarte om at en alvorlig feil kunne
være i ferd med å påvirke hundrevis av millioner av verdens nettbrukere.
Så hva er egentlig feilen som har vært kalt Shellshock, og hva gjør det?
Vel, er Shellshock også kjent som Bash bug, programvaren den utnytter.
Hackere bruker viruset til å skanne sårbare systemer som kjører Linux og Unix
operativsystemer og deretter infisere dem.
Bash er et kommandolinje shell.
Dette lar brukere gi kommandoer til å lansere programmer og funksjoner i programvare
ved å skrive inn tekst.
Det er vanligvis brukt av programmerere, og bør ikke være åpen for resten av verden,
om Shellshock endrer dette.
>> Vel, worringly, enkelte analytikere advare det kan være en større trussel,
fordi Shellshock gir full styring av en infisert maskin,
mens Heartbleed bare tillatt hackere å spionere på datamaskiner.
Det er så alvorlig, det er vært vurdert en 10 av 10
for alvorlighetsgraden av National Vulnerability Database.
2/3 av alle webservere er på risiko, inkludert noen Mac-datamaskiner.
Vel, må du lappe systemene nå.
Alle som vertskap for et nettsted som kjører de berørte operativsystemene
bør iverksette tiltak så snart som mulig.
Alle som har råd til det bør se til sin overvåking og web-applikasjon
brannmurer for å se etter eventuelle angrep.
SPEAKER 3: Verste som kan skje er
at noen ville skrive kode som automatisk ville gå og skanne
Internett og vil påvirke alle disse datamaskinene.
Og når de gjør det, vel, det verste de kunne gjøre
er det bare å slette alt, eller stenge nettstedene ned.
Så vi kunne se skader fra dette synspunkt,
der vi ville ha ondsinnede mennesker som bare bestemmer seg for å føre til kaos
ved å bringe systemer ned eller slette filer, og sånt.
SPEAKER 2: Noen sier dette er en av de mest vanskelige å måle
bugs i år, og det kan ta uker eller til og med
måneder for å bestemme dens endelige virkning.
>> SPEAKER 1: Så alt dette er sant, men det morsomme er, nesten alle
av bildene du nettopp så, med unntak av kanskje tastaturet,
har ingenting å gjøre med feilen overhodet.
Servere og ledninger og så videre, Det er liksom tangentially relatert,
men i kjernen er det faktisk ganske kjent hva som skjer her.
Faktisk, la meg gå inn vår CS50 apparatet.
La meg gå videre og maksimere terminalvinduet her.
Og dere har brukt denne, eller den innebygde versjon derav,
i gedit for å skrive programmer, skriver kommandoer, og så videre,
og dette er faktisk, og har vært i flere uker, Bash, B-A-S-H.
Dette er Bourne-Again Shell, som er bare en fancy måte å si,
Dette er et program som har en blinkende rask, effektivt,
som sitter der og venter for innspill for deg.
Og det er kommandoen grensesnitt via hvilke
dere har kjørt kommandoer og slutt å kompilere og deretter kjører
programmer.
>> Men Bash er også et programmer språket i det følgende måte.
Du vet at det finnes kommandoer som cd og ls og også clang og andre,
men du kan definere dine egne kommandoer ved å implementere dem i Bash.
Nå er vi ikke kommer til å gå i stor detalj
som å Bash i programmeringsspråk, men vet, for eksempel, som i øyeblikket,
det er ingen kommando som heter "hei."
Så kan det bli funnet i en av disse pakker.
Det er ikke installert på datamaskinen min.
Spør administratoren.
Men hvis jeg ønsker at det skal være et program kalt "hallo" i Bash eller på min teksten,
Jeg kan faktisk bruke syntaks som er helt som C. Det er ikke helt det samme,
men det ser ganske lik en funksjon, riktignok mangler noen detaljer.
Ingenting ser ut til å skje, men nå hvis jeg skriver "Hei,"
du kan faktisk skrive en program, ikke i C, ikke i Java,
ikke i et annet programmerings språk, men i Bash seg selv.
>> Nå nøkkelen her er at jeg skrev navn jeg ønsket å gi denne nye kommandoen
og parentes er også symbolsk for dette er en funksjon.
Som en side, kan du også gjøre det gøy ting, og faktisk, selv om Mac OS,
Dette er et program som heter Terminal.
Det kommer innebygd i noens datamaskin som har en Mac i dette rommet,
og du kan gjøre lignende ting i Mac OS, men du kan gå mer utover det.
Og dette er litt tangential, men det er like gøy.
Jeg ble minnet om denne morgenen, når du tenker dette gjennom,
av et lite spill jeg pleide å spille med en av CS50 tidligere TFS
hvor som helst han ville gå bort fra hans tastatur med skjermen sin ulåst,
Jeg vil utføre en kommando som dette-- "si hei."
Og nå helst han kom tilbake til sin tastaturet etter at jeg ryddet skjermen
og han ville sitte ned, prøve å gjøre noe arbeid,
vise innholdet i hans directory--
>> [Lydavspilling]
>> -Hallo.
Hei.
>> SPEAKER 1: Så, i rettferdighet, det var faktisk ikke "hei."
Det var som regel noe mer beslektet med at--
[Lydavspilling]
-Beep.
SPEAKER 1: --that jeg would-- så hans datamaskin ville
sverger på ham som helst han faktisk satte seg på hans tastatur.
Og veldig raskt han funnet ut ikke å forlate sin skjerm ulåst.
Men dette tyder slags av dumme gøy at du
kan ha med noe sånt som Bash.
Men det er litt mer alvorlige, for å være sikker på, enn.
Og faktisk, dette er en av de farligste og mest langvarige feil
som virkelig har rammet verden globalt.
Denne feilen har eksistert for noen 20 år,
og du vil bli rammet i løpet av et øyeblikk av sin relative enkelhet.
>> Så dette er en representant befaler at hvis du
eier en Mac, bokstavelig talt akkurat nå når du har din lokket åpent,
du kan prøve å skrive inn i den program kalt Terminal.
Terminal er under Søknader Utilities--
for en gangs skyld, trenger Windows-brukere ikke trenger å bekymre deg for dette spesielle threat--
men de av dere med Mac-maskiner kan skrive dette inn i et vindu som jeg skal gjøre her,
og hvis du skriver at i dette programmet
kalt Terminal, som jeg gjør nå, hvis du ser ordet "sårbare"
datamaskinen er sårbare for utnytting.
>> Nå hva betyr det egentlig?
Og dette er riktignok noen ganske gal syntaks,
men la oss i det minste trekke ut noen av de interessante sider ved.
Så det er noen syntaks som ser litt kjent, i det minste fra C
og programmering mer generelt.
Jeg ser noen parentes, semikolon, klammeparentes, og slikt,
men det viser seg at dette dumme ting her i gult
er egentlig en funksjon som ikke gjør noe.
Tykktarmen del gjøre ingenting, og semikolon betyr slutte å gjøre ingenting.
Så innsiden av disse klammeparentes, det faktum
at jeg har en lik tegnet til venstre, dette
er i hovedsak å opprette en kommando eller en variabel,
heter x, og tilordne den at gul bit av koden der.
Det kan være noe sånt som "echo Hallo "eller" si pip "eller noe
beslektet med det.
Men legg merke til om øynene dine vandre videre til høyre,
det er mer til denne linjen enn bare enden av det semikolon.
"Echo sårbar", og deretter utover at det er enda mer.
En annen semikolon, bash -c :.
>> Så lang historie kort, denne linjen med kode er
tilstrekkelig for overbevisende en datamaskin som er
sårbare for å gjøre noe at du vil den skal gjøre,
fordi det er en bug i Bash der selv om Bash skulle stoppe
lese linjer med kommandoen rett der etter den gule teksten,
for en 20-pluss år gamle bug, Bash har faktisk vært å lese
utover at semikolon og pen mye gjør det den er fortalt.
>> Så hva er implikasjonen av det til slutt?
Jeg sa bare "echo hello" eller "echo sårbar,"
men hva om du gjorde noe faktisk skadelig, som rm-rf *,
som du kanskje ikke noen gang har skrevet før,
og ærlig du sannsynligvis bør ikke for tidlig,
fordi du kan gjøre en mye skade med den.
Hvorfor?
rm gjør hva, selvfølgelig?
Fjerner.
* Betyr hva?
Alle.
Så det er en såkalt wild card, så det betyr
slette alt i gjeldende katalog.
-r skjer til å bety rekursiv, som betyr at hvis hva du sletter
er en katalog, og innsiden av det er andre filer og andre kataloger,
rekursivt dykke inn der og slette alt dette.
Og -f er den verste av dem alle.
Alle vet hva f betyr her?
Force.
Så tvinge midler, selv Hvis dette er en dårlig idé,
gjøre det uten å spørre meg for ytterligere bekreftelse.
Så, vet du, ler vi på dette, men ærlig, jeg sannsynligvis
skriver dette flere ganger en dag, fordi virkeligheten
er det er den raskeste måten å slette en hel haug med ting.
Men selv jeg har gjort noen skade.
>> Men hvis du skulle lure en datamaskin til å definere noen dum variabel
eller funksjon kalt x, men da lure datamaskinen i utføring
utover grensene for det funksjon, utover at semikolon,
du kan faktisk lure en datamaskin til å utføre noe sånt rm-rf
eller e-post-kommandoen eller kommandoen Kopier.
Noe bokstavelig talt kan du gjøre med datamaskin, enten det er å slette filer,
skape filer, spamming noen, angripe noen server eksternt,
hvis du kan uttrykke det med en kommando, du
kan lure en datamaskin til å gjøre det.
>> Nå hva er et eksempel på hvordan du kan gjøre dette?
Vel, det er mye av datamaskiner på internett kjører Bash.
Alle av oss Mac-brukere er blant dem.
Mange Linux-servere er blant dem også, og Unix-servere.
Windows igjen får relativt av kroken
med mindre du har installert spesiell programvare.
Nå er en rekke servere, for eksempel, kjører web-servere,
og faktisk Linux er kanskje det mest populære operativsystemet
å kjøre på datamaskiner på internett som tjenestegjør opp websider.
Nå som vi skal se senere i semesteret, da
du sende en anmodning fra din browser-- Chrome,
Internet Explorer, whatever-- til en ekstern server,
det viser seg at selv om du nettopp har skrevet www.example.com,
Nettleseren din er å sende en melding som er litt mer uforståelige, som dette.
>> Men legg merke til en litt noe rart.
De to første linjene Jeg har aldri sett før,
men de ser ikke spesielt truende.
Men legg merke til hva jeg har stjålet for tredje linje her.
Hvis en dårlig fyr var å sende en melding som dette fra hans eller hennes datamaskin
til en sårbar Mac eller en sårbare Linux server,
det morsomme er at Bash, som enkel liten ledeteksten,
er allestedsnærværende, og er ofte brukt til å hovedsaklig utføre
innholdet i en melding om at den mottar.
Og den logikken, kan du lure en web server, derfor
ved å sende noe sånt User-Agent, som vanligvis
er ment å si navn på nettleseren din.
User-Agent Chrome, User-Agent Internett Explorer, User-Agent Firefox, dette
er bare i nettleseren måte å identifisere seg selv.
Men hvis en bad guy veldig kløktig sier, mm-mm, jeg er
ikke tenkt å fortelle deg hva nettleseren min er,
Jeg i stedet kommer til å sende deg dette kryptisk-ser ting med en rm-rf
* I det, kan du bokstavelig talt lure en sårbare web server på internett
til å utføre akkurat det i der for å slette alle filene.
Og ærlig talt, det er ikke selv de verste av det.
Du kan gjøre noe.
Du kan starte et distribuert denial of service angrep
Hvis du sendte denne meldingen til hele bunter av webservere
og da hadde dem alle ned, for eksempel på Harvard.edu servere,
og du kan sortere på bang pokker ut av dem
av en nettverkstrafikk som var ellers utløses av dette dårlig fyr.
>> Så, lang historie kort, nesten alle i dette rommet som eier en Mac
er utsatt for dette.
The silver lining er at med mindre du er kjører en webserver på den bærbare datamaskinen,
og med mindre du faktisk har konfigurert det å tillate noe som SSH inn i det,
du er faktisk trygg.
Det er sårbare, men det er ingen en prøver å komme inn i den bærbare datamaskinen,
slik at du kan liksom være trygg.
Men Apple vil snart være å oppdatere en løsning på dette.
Verden av Linux har allerede sluppet en rekke feilrettinger for Fedora og Ubuntu
og andre versjoner av Linux, og faktisk hvis du kjører oppdatering 50 i apparatet,
selv det også vil være oppdatert og korrigert.
Men som også har ikke virkelig vært sårbar,
fordi med mindre du har flikket med apparatet
og gjort den bærbare datamaskinen offentlig tilgjengelig på internett, som ikke er
som standard, har du faktisk vært fint fordi
av brannmur og andre teknikker.
>> Men det er et ekstremt eksempel på en feil at vi har levd for for bokstavelig talt 20
år, og hvem vet om noen hele denne tiden har visst om det?
Og faktisk, dette er en av de grunnleggende utfordringene
at vi får se senere i semester om sikkerhet,
er at akkurat som i den virkelige verden, de gode gutta er på ulempe.
For å holde skurkene ut, må vi sørge for at alle dører er låst,
at hvert vindu er sikker, at hvert punkt trer inn i et hjem
er sikkert å holde skurkene ut.
Men hva gjør den slemme må gjøre for å faktisk kompromittere ditt hjem
og stjele fra deg?
Han eller hun må bare finne en ulåst dør, en knust vindu, eller noe
langs disse linjene, og det er den samme i datasikkerhet.
Vi kan skrive millioner av linjer med programmeringskode
og bruke hundrevis eller tusenvis timer prøver å få det riktig,
men hvis du gjør bare én feil i nøyaktighet,
du kan sette hele systemet og faktisk i dette tilfelle hele internett
og verden i fare.
>> Så hvis du har lyst til å lære mer om dette, kan du gå til denne nettadressen her.
Det er ikke behov for handling i kveld med mindre du er
blant dem mer komfortable at har kjørt din egen web
server, i så fall bør du, faktisk, oppdatere programvaren.
>> Og dette også er tittelen på en tale, og nå et papir,
at vi har koblet på Kurset hjemmeside for i dag.
Det var av en fyr heter Ken Thompson, som
var imot en svært berømt award i informatikk,
og han ga denne talen noen år siden, i hovedsak på samme tema.
Spør folk på spørsmålet, bør du virkelig
tillit, til slutt, Programvaren du har fått?
For eksempel har vi alle vært å skrive programmer,
og vi har vært kompilering dem med Clang.
Og til din kunnskap, du har skrevet noen programmer for CS50 hvor det er
en bakdør slags, det er en måte som en dårlig fyr, hvis du kjører programmet,
kunne ta over datamaskinen?
Sannsynligvis ikke, ikke sant?
Mario, og grådige, og Credit.
Disse er alle ganske små programmer.
Du må være ganske dårlig hvis du faktisk
gjort hele datamaskinen sårbar etter å skrive 10 eller 20 linjer med kode,
eller i det minste ikke klar over noen av sikkerhetsrisikoen.
Nå sier jeg at facetiously, men vi kommer til å se i dag
og denne uken er det faktisk virkelig, virkelig lett
å være dårlig, og gjøre selv korte programmer sårbare.
>> Men for nå, minst, skjønner at spørsmålet blir stilt her
handler om Clang i en kompilator.
Hvorfor har vi vært tillitsfulle Clang for de siste to eller tre uker?
Hvem er å si at den som skrev Clang hadde ikke en "hvis" tilstand der
som i hovedsak injisert noen nuller og de i hvert program det kompilerer
som ville la ham eller henne tilgang datamaskinen når du sover
og din laptop lokket er åpent og datamaskinen kjører?
Høyre?
Vi har denne typen ære system rett nå hvor vi stoler på at Clang er legit.
Du stoler på at apparatet er legit.
Du stoler som bokstavelig talt hvert program på din Mac eller PC er troverdig.
Og som denne enkle feil antyder, selv om det ikke er skadelig,
det er absolutt ikke sannsynlig å være tilfelle.
>> Så du bør være redd som faen.
Ærlig talt, det er ingen enkel Løsningen på dette annet
enn en slags samfunnsmessig bevissthet av den økende kompleksiteten
at vi bygger på toppen av våre datasystemer,
og hvor stadig mer sårbare vi kan godt være.
>> Nå med det sagt, Breakout.
Så Breakout er problemet satt tre, og Breakout er et spill fra en svunnen tid
som du kanskje husker, men for oss i oppgavesettet tre,
det tillater oss å ta ting sikkerhetskopiere et hakk
slik at når vi skriver programmer, selv i et terminalvindu som dette,
vi kan faktisk kjøre, til slutt, grafiske programmer ikke
i motsetning til de vi hadde tilgang til i Scratch.
Så dette er de ansattes gjennomføring av Breakout,
som er nettopp dette murstein-breaking spillet, som du flytte padle tilbake
og tilbake, og du treffer ballen mot de fargede klosser opp toppen.
Så dette er å bringe oss slags tilbake til der
vi var i stand til å være svært raskt med Scratch, og nå med C,
implementere vår egen grafiske brukergrensesnitt.
>> Men mer enn det, dette Oppgavesettet representerer den første
der vi gir deg en haug med kode.
Og faktisk, jeg ta eksplisitt hensyn til dette, fordi særlig
for de mindre komfortable, dette oppgavesettet, i hvert fall ved første øyekast,
kommer til å føle seg som vi har tatt det opp et hakk.
Fordi vi har gitt deg, for noen av søke
og sortering problemer i PSet, en haug med kode som vi skrev,
og et par kommentarer si at "å gjøre"
hvor du må fylle ut feltene.
Så ikke så skummelt, men det er første gang
vi levere du kode som du trenger for å først lese, forstå og deretter legge til
og fullføre den.
>> Og deretter med Breakout, vi kommer til å gjøre det samme,
noe som gir deg et par dusin flere linjer kode som, ærlig, gi deg
mye av rammeverket for spillet, men stoppe kort
implementere mursteinene og ballen og padle,
men vi gjennomføre noen andre funksjoner.
Og selv som ved første øyekast, igjen, spesielt hvis mindre komfortable,
kan virke særlig skremmende og du tror det er så mange nye funksjoner
du trenger å vikle hjernen din rundt, og det er sant.
Men husk, det er helt som Scratch.
Odds er du ikke brukte alle Brikkene i Scratch.
Odds er du ikke lyst til å vikle tankene rundt dem alle
fordi alle tok det var en raskt blikk for å forstå, oh,
det er hva jeg kan gjøre med at puslespill brikke.
Og ja, i oppgavesettet 3 spec, vil vi peke deg
på dokumentasjonen som vil introdusere deg til noen nye funksjoner,
og til slutt programmerings konstruerer du bruker.
Betingelser, løkker, variabler og funksjoner
vil være identisk det vi har sett så langt.
>> Så ja, hva vi vil gi du er noen eksempelkode som
kan du opprette et vindu som ser ikke ulikt dette,
og slå den til slutt inn noe helt som dette.
Så dra nytte av CS50, diskutere arbeidstid og mer,
og ta trøst i det faktum at mengden med kode du må skrive
er faktisk ikke så mye.
Den første utfordringen er bare å akklimatisere deg selv til noen kode vi har skrevet.
>> Eventuelle spørsmål om pset3, Shellshock, eller på annen måte?
>> PUBLIKUM: Det virket som gå gjennom med Breakout
at koden er nesten et objekt-orientert stil,
men jeg trodde C var en objektorientert program.
SPEAKER 1: Et utmerket spørsmål.
Så i å se gjennom fordelingskode, koden
vi skrev for pset3, for de som er kjent, det
ser ut som det er en lite objekt-orientert.
Korte svaret er, det er.
Det er en tilnærming til hvordan du kan gjøre objektorientert kode ved hjelp
et språk som C, men det er fortsatt slutt prosessuelle.
Det er ingen metoder inne i variablene, som du ser.
Men det minner om det.
Og vi vil se at funksjonen igjen når vi kommer til PHP og Javascript
mot slutten av semesteret.
Men for nå, tenk på det som et hint om hva som kommer.
Godt spørsmål.
Greit.
Så flette slags var hvordan vi venstre ting forrige gang.
Og flette slags var kult i forstand at den var så mye raskere,
i det minste på grunnlag av flyktige tester vi gjorde i forrige uke, enn for eksempel boble
sortere, utvalg sortere, innsetting slag.
Og hva var godt for er bare hvordan konsist og renslig
du kan uttrykke det.
Og hva gjorde vi si det var en øvre bundet på kjøretiden til flettingen
sortere?
Yeah?
>> PUBLIKUM: n log n?
>> SPEAKER 1: n log n, ikke sant. n log n.
Og vi vil komme tilbake til hva som egentlig betyr eller hvor det kommer fra,
men dette var bedre enn hva driftstid
som vi så for boble valg og innsetting slag?
Så n squared. n squared er større enn dette,
og selv om det ikke er helt opplagt, vet at log n er mindre enn n,
så hvis du gjør n ganger noe mindre enn n,
det kommer til å være mindre enn n squared.
Det er litt av intuisjon der.
Men vi betalte en pris for dette.
Det var raskere, men et tema som startet å dukke opp i forrige uke var dette kompromisset.
Jeg fikk bedre ytelse tid klok, men hva
jeg har å bruke på den andre hånd, for å oppnå det?
>> PUBLIKUM: Minne.
SPEAKER 1: Si det igjen?
PUBLIKUM: Minne.
SPEAKER 1: Memory, eller plass mer generelt.
Og det var ikke super åpenbart med våre mennesker,
men husker at våre frivillige var stepping frem og stepping
tilbake som om det er en rekke her, og som om det er
en andre rekke her at de kunne bruke, fordi vi
trengte et sted å fusjonere de folkene.
Vi kunne ikke bare bytte dem på plass.
Så fusjonere slags innflytelse er mer plass, som
vi trenger ikke med de andre algoritmer,
men oppsiden er at det er mye raskere.
Og ærlig talt, i den virkelige verden plass disse days-- RAM, harddisk space--
er forholdsvis billig, og slik at det er ikke nødvendigvis en dårlig ting.
>> Så la oss ta en rask titt, litt mer metodisk, på hva vi gjorde
og hvorfor vi sa det var n log n.
Så her er de åtte tall og åtte frivillige vi hadde forrige gang.
Og det første som Merge Sorter fortalte oss å gjøre var hva?
PUBLIKUM: Divide i to.
SPEAKER 1: Si det igjen?
PUBLIKUM: Divide i to.
SPEAKER 1: Divide i to, ikke sant.
Dette er veldig minner om telefonboken, av skillet
og erobre mer generelt.
Så vi så på venstre halvdel.
Og så når vi sa, liksom den venstre halvdel av elementene,
hva gjorde vi neste si?
Sortere den venstre halvdelen av den venstre halvparten, som tillater oss å,
etter å dele i to, fokusere på fire og to.
>> Hvordan du sortere en liste nå, i do gul, størrelse to, ved hjelp av Merge Sort?
Vel dele den i to, og sortere den venstre halvdelen.
Og dette var der ting fikk litt dum kort.
Hvordan du sortere til en liste som er av størrelse en, som dette nummer fire her?
Det er sortert.
Du er ferdig.
>> Men så hvordan kan du sortere en liste over størrelse en når det er nummer to?
Vel, samme, men nå hva som var tredje og viktig steg i Merge Sort?
Du måtte fusjonere venstre halvparten, og den høyre halvdel.
Og når vi gjorde det, vi så på fire, har vi sett på to.
Vi bestemte oss for all right, åpenbart to som kommer først,
så vi satte to i sin sted, etterfulgt av fire.
Og nå må du slags spole tilbake, og dette er slags karakteristisk
av en algoritme som Merge Sorter, spole tilbake i minnet.
Hva var neste linje av historien?
Hva bør jeg fokusere på neste?
Den høyre halvdel av venstre halv, som er seks og åtte.
>> Så la meg bare gå gjennom dette uten belaboring punktet for mye.
Seks og åtte, deretter seks er sorteres, er åtte sortert.
Flette dem sammen sånn, og nå det neste store skrittet
er, selvfølgelig, sortere høyre halvdel fra den aller første trinn i denne algoritmen.
Så vi fokusere på ett, tre, sju, fem.
Vi deretter fokusere på venstre halvdel.
Den venstre halvdel av at den høyre halvdel av det, og deretter flette i ett og tre.
Deretter høyre halvdel, deretter til venstre halvdel av den, så den høyre halvdelen av det.
Flette det inn, og nå hva skritt gjenstår?
Flett den store venstre halvdel og den store høyre halvdel, slik at man går ned der,
så to, så tre, så fire, deretter fem, så seks, så sju, deretter åtte.
>> Så nå hvorfor er dette til slutt avslørende, spesielt hvis n og logaritmer flere
vanligvis heller unnslippe deg, i hvert fall i nyere minne?
Vel, merke høyden på denne tingen.
Vi hadde åtte elementer, og vi deles den ved to, to, to.
Så log base to av åtte gir oss tre.
Og tro meg på at hvis litt tåkete på det.
Men log base to av åtte er tre, så vi har gjort tre lag med sammenslåing.
Og når vi slått sammen elementer, hvor mange elementer
fikk vi se på på hver av de radene?
Totalt n, rett?
Fordi å fusjonere den øverste raden, selv om vi gjorde det stykkevis,
vi til slutt rørte hvert tall en gang.
Og i den andre raden, til flette disse listene av størrelse to,
vi måtte ta på hvert element en gang.
Og så her virkelig tydelig i den siste raden,
vi måtte ta på hver av disse elementer samtidig, men bare en gang,
så her ligger altså vår n log n.
>> Og nå bare for å gjøre ting litt mer formell for bare et øyeblikk, hvis du
skulle nå analysere dette på en slags høyere nivå
og prøve å bestemme, godt hvordan kan du gå om å uttrykke
kjøretiden til denne algoritmen bare ved å se på det, og ikke
ved hjelp av en contrived eksempel?
Vel, hvor mye tid vil du si en trinn som dette i gult ville ta,
hvis n <2 tilbake?
Det er en stor O av hva?
Så jeg ser en, så ett trinn, kanskje to skritt fordi det er hvis
og deretter gå tilbake, men det er konstant tid, ikke sant?
Så vi sa O (1), og det er hvordan jeg skal uttrykke dette.
T, bare være gangtid.
n er størrelsen av tilførselen så T (n), bare en fancy måte
si driften tid gitt input av størrelse n
kommer til å være i størrelsesorden av konstant tid, i O (1).
>> Men ellers, hva om dette?
Hvordan vil du uttrykke kjøretid på denne gule linjen?
T av hva?
Du kan slags jukse her og svare på spørsmålet mitt syklisk.
Så hvis kjøretiden i Generelt vi bare si er T (n).
Og nå er du slags elvebåttur her og si, vel, bare sortere venstre halvdel,
og deretter sortere høyre halvdel.
Hvordan kan vi symbolsk representerer kjøretiden til denne gule linjen?
T av hva?
Hva er størrelsen på innspill?
n over to.
Hvorfor kan jeg ikke bare si det?
Og da dette er en annen T (n / 2) og deretter igjen, hvis jeg slå sammen to sorterte halvdeler,
hvor mange elementer skal jeg å måtte røre totalt?
n.
Så jeg kan uttrykke dette, bare for å være snill av fancy,
som kjøretiden generelt.
T (n) er bare kjøretiden T (n / 2), pluss T (n / 2), venstre halvdel og høyre halvdel,
pluss O (n), som sannsynligvis er n skritt, men kanskje, hvis jeg bruker to fingre,
det er dobbelt så mange trinn, men det er lineær.
Det er noen flere skritt det er en faktor av n,
slik at vi kan uttrykke dette som dette.
Og det er her nå vil vi punt til baksiden av våre high school math lærebok
vi er at tilbakefall til slutt ender opp som tilsvarer dette, n ganger log n,
hvis du faktisk gjør ut regnestykket mer formelt.
>> Så det er bare to perspektiver.
En tallmessig med en hardkodet representativt eksempel
ved hjelp av åtte tall, og en mer generell titt på hvordan vi kom dit.
Men hva er egentlig interessant her er, igjen, denne oppfatningen av sykling.
Jeg bruker ikke for løkker.
Jeg er litt definere noe i forhold til seg selv,
ikke bare med denne matematisk funksjon,
men også i form av denne pseudo-kode.
Denne pseudo-kode er rekursiv i at to av sine linjer
er i hovedsak å fortelle det til å gå bruker i seg selv til å løse en mindre
Problemet med mindre størrelse, og deretter igjen og igjen
og igjen før vi spikke det ned til denne såkalte basistilfelle.
>> Så la oss faktisk tegne et mer overbevisende take-away fra dette som følger.
La meg gå inn i gedit og ta en se på noen av dagens kildekode,
spesielt dette eksempelet her.
Sigma 0, som tilsynelatende legger tallene en gjennom n.
Så la oss se hva som er kjent og ukjent her.
Først har vi et par inkluderer, så ikke noe nytt der.
Prototype.
Jeg er litt disig på dette etter noen dager,
men hva gjorde vi si en prototype av en funksjon er?
PUBLIKUM: [uhørlig].
SPEAKER 1: Hva er det?
PUBLIKUM: Vi annonserer det.
SPEAKER 1: Vi lanserer den.
Så du underviser Clang, hey, faktisk ikke implementere dette ennå,
men et sted i denne filen, formodentlig, kommer til å bli en funksjon som heter hva?
Sigma.
Og dette er bare et løfte om at det kommer til å se slik ut.
Det kommer til å ta et heltall som input-- og jeg kan være mer eksplisitt
og si int n --og det er kommer til å returnere en int,
men semikolon midler, mm, jeg skal komme seg rundt å implementere dette litt senere.
Igjen er Clang dum.
Det er bare kommer til å vite hva du forteller det topp til bunn,
så vi må i det minste gi det et hint om hva som kommer.
>> Nå la oss se på hoved her.
La oss bla nedover her og se hva hoved gjør.
Det er ikke så lenge av en funksjon, og faktisk konstruere her er kjent.
Jeg erklærer en variabel n, og deretter Jeg plage brukeren igjen og igjen
for et positivt heltall ved hjelp getInt, og bare gå ut av denne sløyfen
når brukeren har overholdt.
Gjør Mens, har vi brukt til å plage brukeren på den måten.
Nå er dette interessant.
Jeg erklærer en int som heter "svar."
Jeg tilordne den returverdien av en funksjon som heter "sigma".
Jeg vet ikke hva som gjør ennå, men Jeg husker erklære det for et øyeblikk siden.
Og så er jeg passerer i verdi som brukeren har skrevet inn, n,
og da jeg rapportere svaret.
Vel la oss bla tilbake for bare et øyeblikk.
La oss gå videre inn i denne katalogen, gjør sigma 0, og faktisk kjøre dette programmet
og se hva som skjer.
Så hvis jeg går videre og kjøre dette programmet, ./sigma-0,
og jeg skriver i en positiv heltall som to, Sigma,
som den greske symbolet tilsier, er bare kommer til å legge opp alle tallene fra
null på opp til to.
Så 0 pluss 1 pluss 2.
Så dette skal forhåpentligvis gi meg tre.
Det er alt det gjør.
Og på samme måte, hvis jeg kjører dette igjen og jeg gir det nummer tre,
det er tre pluss to, så det er 5, pluss 1 bør gi meg seks.
Og så hvis jeg får virkelig sprø og begynner å skrive i større tall,
det bør gi meg større og større summer.
Så det er alt.
>> Så hva gjør sigma se ut?
Vel, det er ganske grei.
Det er hvordan vi kan ha implementert dette for de siste par ukene.
"Int" kommer til å være returtypen.
Sigma er navnet, og det tar en variabel m i stedet for n.
Jeg skal endre det opp toppen.
Så dette er bare en mental helse sjekk.
Vi vil se hvorfor i et øyeblikk.
Nå erklærer jeg en annen variabel, sum, initialisere den til null.
Da har jeg dette For sløyfe itera, tilsynelatende for klarhet,
fra i = 1 på opp til an = m, som er hva brukeren har skrevet inn, og da jeg
øke summen som dette.
Og deretter returnere summen.
>> Så et par spørsmål.
En, jeg hevder i min kommentar at dette unngår faren for en uendelig løkke.
Hvorfor skulle passerer i et negativt tall indusere, potensielt, en uendelig løkke?
>> PUBLIKUM: Du vil aldri nå moh.
>> SPEAKER 1: nå Aldri moh.
Men m er gått inn, så la oss vurdere et enkelt eksempel.
Hvis m er gått i ved bruker som negativt.
Uavhengig av hoved.
Hoved beskytter oss mot dette også, så jeg er bare
blir virkelig anal med sigma å også sørge for
at innsatsen ikke kan være negativ.
Så hvis m er negativ, noe sånt som negativ en.
Hva kommer til å skje?
Vel, jeg kommer til å blir initialisert til en,
og da er jeg kommer til å være mindre enn eller lik m?
>> Stand by.
Det var-- la oss ikke, la oss nix denne historien.
Jeg fikk ikke stille det spørsmålet, fordi risikoen for at jeg berget
ikke kommer til å skje fordi jeg er alltid kommer være større than-- OK,
Jeg trekker det spørsmålet.
OK.
La oss fokusere bare på denne delen her.
Hvorfor gjorde jeg erklære noen utenfor loopen?
Notice on line 49 Jeg har erklært i innsiden av løkken,
men online 48 jeg har erklærte noen utenfor.
Yeah.
PUBLIKUM: [uhørlig].
SPEAKER 1: Sure.
Så først og fremst jeg absolutt ikke ønsker å erklære og initial sum
til null innvendig sløyfe på hver iterasjon,
fordi dette ville klart beseire den Hensikten med å summere opp tallene.
Jeg ville holde endre verdien tilbake til null.
Og også, hva er en annen mer uforståelige Grunnen til at samme design avgjørelse?
Yeah.
>> PUBLIKUM: [uhørlig].
SPEAKER 1: Nettopp.
Jeg ønsker å få tilgang til det utenfor av sløyfen altfor på hvilken linje?
På 53.
Og basert på vår tommelfingerregel fra et par forelesninger siden,
variabler er scoped, egentlig, til klammeparentes som omfatter dem.
Så hvis jeg ikke erklære sum inne av disse ytre klammeparentes,
Jeg kan ikke bruke den på linje 53.
Sagt på en annen måte, hvis jeg erklærte sum i her, eller selv innenfor
For loop, jeg kunne ikke tilgang til den i 53.
Den variable ville effektivt være borte.
Så et par grunner der.
Men nå la oss gå tilbake og se hva som skjer.
Så sigma blir kalt.
Den legger opp 1 pluss 2, eller 1 pluss 2 pluss 3, og deretter returnerer verdien,
lagrer det i svaret, og printf her er grunnen til at jeg ser på skjermen.
Så dette er hva vi kaller en iterativ tilnærming, hvor iterasjon bare
betyr anvendelse av en løkke.
En for løkke, en while-loop, en gjøre mens loop, bare gjør noe nytt
og igjen og igjen.
>> Men sigma er slag av en ryddig funksjon i at jeg kunne gjennomføre det annerledes.
Hva om dette, noe som bare for å være litt kult,
la meg virkelig bli kvitt av mye distraksjon
fordi denne funksjonen er egentlig ganske enkel.
La oss spikke det ned bare til sine fire kjernelinjer
og bli kvitt all den kommentarer og klammeparentes.
Dette er en slags halsbrekk alternativ implementering.
Ok, kanskje ikke tanke blåser, men det er slags sexy, all right,
å se på dette så mye mer konsist.
Med bare fire linjer med kode, Jeg først har denne tilregnelighet sjekk.
Hvis m er mindre enn eller lik null, gjør sigma ingen mening.
Det er bare ment å være i dette tilfellet for positive tall,
så jeg skal bare returnere null vilkårlig
slik at vi i det minste har noen såkalte basistilfelle.
>> Men her er det fine.
Helheten av denne ideen, og legger til tall fra 1 til n, og m i dette tilfellet
kan gjøres ved slags passerer the buck.
Vel, hva er summen av 1 til m?
Vel, vet du hva?
Det er det samme som summen av m pluss summen av 1 og m minus en.
Vel vet du hva?
Hva er sigma av m minus 1?
Vel, hvis du slags følge dette logisk, er det det samme som m minus 1
pluss sigma av m minus 2.
Så du kan slags just-- dette er som, hvis du er bare
prøver å irritere en venn og de spør deg et spørsmål,
du slags svare med et spørsmål, du kan slags holde passerer the buck.
Men kjernen er at hvis du holder gjør spørsmålet mindre og mindre
og mindre, er du ikke spør hva som er sigma
n, hva er sigma av n, hva er sigma av n?
Du spør hva som er sigma n, hva er sigma
n minus 1, hva er sigma n minus 2?
Til slutt spørsmålet ditt kommer til å bli det?
Hva er sigma av en eller null, noen svært liten verdi,
og så snart du får det, din venn,
du kommer ikke til å spørre det samme spørsmålet igjen,
du bare kommer til å si, oh det er null.
Vi er ferdig med å spille denne typen dum syklisk spill.
>> Så rekursjon er handlingen i programmering av en funksjon som kaller seg.
Dette programmet, når kompilert og kjøre, er kommer til å oppføre seg på akkurat samme måte,
men hva er nøkkelen er at innsiden av en funksjon som heter sigma,
er det en kodelinje hvori vi kaller oss selv,
som normalt ville være dårlig.
For eksempel, hva hvis jeg først utarbeidet denne, så sørg sigma--
gjøre sigma 1 ./sigma-1.
Positivt heltall, vær så snill, 50 1275.
Så hva funksjonen ser ut til å være basert på en test, korrekt.
Men hva hvis jeg får en litt farlig og slette den såkalte base case,
og bare si, vel jeg bare å lage denne mer komplisert enn det er.
La oss bare beregne sigma ved å ta m, og deretter tilsetning
i sigma av m minus en?
Vel, hva kommer til å skje her?
La oss zoome ut.
La oss rekompilere programmet, lagre det, rekompilere programmet,
og deretter klar ./sigma-en zoomer inn, skriv positivt heltall please, 50.
Hvor mange av dere er villig å fess opp til å se det?
>> OK.
Så dette kan skje for en rekke grunner,
og ærlig denne uken vi er i ferd med å gi deg mer av dem.
Men i dette tilfellet, kan du prøve å resonnere bakover
hva kan ha skjedd her?
Segmentering feil, sist vi sa tid, henviser til et segment av minnet.
Noe dårlig skjedde.
Men hva var det mekanisk som gikk galt
her på grunn av fjerning min av det såkalte basis tilfellet
der jeg returnerte hardkodet verdi?
Hva tror du gikk galt?
Yeah.
>> PUBLIKUM: [uhørlig].
SPEAKER 1: Ah.
Godt spørsmål.
Så størrelsen av antallet at jeg var summere opp
ble så stor at det overgikk størrelsen på plass i minnet.
God idé, men ikke fundamentalt kommer til å føre til krasj.
Som kan føre til heltall overløp, hvor de biter bare snu
og da vi feil en virkelig stor nummer for som et negativt tall,
men det i seg selv vil ikke føre til krasj.
Fordi på slutten av dag en int er fortsatt 32 bits.
Du kommer ikke til å uhell stjele en 33. bit.
Men en god tanke.
Yeah.
>> PUBLIKUM: [uhørlig].
SPEAKER 1: Metoden aldri slutter å kjøre,
og faktisk det kaller seg igjen og igjen og igjen og igjen
og igjen, og ingen av disse funksjonene noensinne
føre fordi deres eneste linje av kode kaller seg selv igjen og igjen
og igjen.
Og hva er egentlig skjer her, og nå er vi
kan slags tegne dette billedlig.
La meg gå over til en bilde for bare et øyeblikk.
Dette er et bilde, som vil til slutt kjøttet ut
i mer detalj, av hva som skjer innsiden av datamaskinens minne.
Og det viser seg at på bunnen av dette bildet
er noe som kalles stabelen.
Dette er en del av minne, en mengde RAM,
det er bare brukt noen gang en funksjon kalles.
Hver gang du, en programmerer, kalle en funksjon,
operativsystemet, som Mac OS, Windows eller Linux,
griper en haug av bytes, kanskje en kilobyte, kanskje noen få megabyte
minne, hendene dem til deg, og deretter lar
du kjører din funksjon ved hjelp Uansett variablene du trenger.
Og hvis du da ringe en annen funksjon og en annen funksjon,
du får en annen bit av minne og en annen bit av minne.
>> Og ja, hvis disse grønne skuffer fra Annenberg representerer dette minnet,
her er hva som skjer den første gang du ringer funksjon sigma.
Det er som å sette et brett som dette på hva som er utgangspunktet en tom stabelen.
Men så hvis den skuffen kaller seg, så å si,
ringer en annen forekomst av sigma, det er
som å spørre operativsystemet, ooh, trenger litt mer minne,
gi meg den.
Og så blir det stablet på oppå.
Men det som er nøkkelen her er at den første skuffen er der fortsatt,
fordi han har påberopt seg denne annen skuff.
Nå i mellomtiden, sigma kaller sigma, det er som å be om mer minne.
Blir stablet på over her.
sigma kaller sigma, det er en annen skuffen som blir stablet på her.
Og hvis du fortsetter å gjøre dette, til slutt, hva slags kart denne visuelle
på det kartet, hva som kommer til skje med bunken med skuffer?
Det kommer til å overstige beløpet minne maskinen har.
Og så snart denne grønne skuffen overskrider den horisontale linje
ovenfor stack og over at ordet haugen, som vi vil komme tilbake til i fremtiden,
det er en dårlig ting.
Haugen er en annen segment av minne,
og hvis du lar disse skuffer haug og haug på,
du kommer til å overstige ditt eget segment av minne,
og et program er faktisk kommer til å krasje.
>> Nå som en side, denne ideen av rekursjon derfor
tydelig kan føre til problemer, men det er ikke nødvendigvis en dårlig ting.
Fordi vurdere, etter alt, how-- og kanskje
dette tar litt tid å venne å --how elegant eller hvor enkelt
at gjennomføringen av sigma var.
Og vi kommer til å bruke rekursjon så mye i CS50,
men i CS51, og virkelig noen klasse hvor du manipulere datastrukturer
som trær, eller familietrær, som har noen hierarki,
det er super, super nyttig.
Nå, som en side, slik at du som aspirerende dataforskere
er kjent med noen av Googles inne vitser, hvis du går til Google
og du ser opp hva som er definisjon av, si, rekursjon, inn.
Uh-he.
Som en side, trakk jeg opp noen.
Dette var som 10 minutter av sommel i morges.
Hvis du også Google "skjevt", varsel ved å vippe hodet slightly--
og så dette er kanskje mest fryktelig av alt
siden noen brukt som sin dag å implementere denne
noen år ago-- kommer på.
Oh, det er wait-- en bug.
>> Så kjøres på en av verdens største nettsteder
er disse dumme små påskeegg.
De sannsynligvis forbruke nontrivial antall linjer med kode
akkurat slik at vi kan ha små morsomme ting som det.
Men minst nå får du noen av disse inne vitser.
>> Nå la oss ta en titt på noen av de hvite løgner vi har vært å fortelle i det siste,
og begynner å skrelle tilbake noen lag teknisk
slik at du virkelig forstår hva som har skjedd på
og du kan forstå noen av truslene,
som Shellshock, som har nå begynt å bli
på i forkant av alles oppmerksomhet, i det minste i mediet.
Så her er en veldig enkel funksjon som returnerer ingenting, ugyldig.
Dens navn er swap.
Det tar i to variabler og den returnerer ingenting.
Tar i a og b.
Så en rask demonstrasjon.
Vi tok opp disse.
Vi kan like godt ta litt pause her for bare et øyeblikk
og har noe å drikke.
Hvis noen ikke vil ha noe imot å bli med meg opp her for bare et øyeblikk.
Hva med deg i rødbrun skjorte?
Kom opp.
Bare én dag.
Takk, skjønt.
Greit, og vi har kommer opp hvem her?
Hva heter du?
>> SPEAKER 4: Laura.
>> SPEAKER 1: Laura.
Kom opp.
Så Laura, veldig enkel utfordring i dag.
Hyggelig å møte yo.
Greit.
Så vi har litt melk over her og vi har litt appelsinjuice over her
og noen kopper som vi lånt fra Annenberg i dag.
>> SPEAKER 4: Borrowed.
SPEAKER 1: Og kommer til å gå videre og gi deg et halvt glass av denne.
Greit.
Og vi vil gi deg halv et glass melk.
Oh, og bare slik at du kan huske hva dette var,
Jeg husket å bringe dette opp og på i dag.
Ok.
Hvis du ikke har noe imot det, la oss se, vi kan sette dem over dine egne briller
hvis du vil.
Dette blir verden fra Lauras øyne.
Greit.
Så målet ditt, gitt to kopper flytende her, melk og appelsinjuice,
er bytte de to innholdet slik at appelsinjuice går inn i melkekoppen
og melken går over i appelsinjuice cup.
>> SPEAKER 4: Må jeg få en annen cup?
SPEAKER 1: Jeg er så glad for at du spurte, men det ville ha vært mye bedre opptak
hvis du ikke hadde spurt.
Men ja, kan vi tilby deg en tredje kopp som er tom, selvfølgelig.
Greit.
Så bytte ut innholdet der.
Very nice.
Veldig bra.
Du gjør dette bemerkelsesverdig nøye.
Og trinn tre.
Greit.
Utmerket.
En stor applaus ville være bra for Laura.
Greit.
Vi har en liten avskjedsgave for deg, men la meg ta disse.
Takk så mye.
Så et enkelt eksempel, skjønt, å vise at hvis du gjør
ønsker å bytte ut innholdet av to beholdere,
eller la oss kalle dem variabler, du trenger noen midlertidig lagring
å arrangere et av innholdet i så at du faktisk kan gjøre swap.
Så ja, denne kildekoden her oppe i C er representativ for akkurat det.
Hvis appelsinjuice var en og melken var b, og vi ønsket å bytte de to,
du kan prøve noe kreativt ved å helle en til den andre,
men som sannsynligvis ikke ville ende spesielt godt.
Og så bruker vi en tredje kopp, samtale det tmp, T-M-P av konvensjonen,
og sette innholdet i OJ i det, så bytte en kopp,
deretter sette OJ inn i opprinnelige cup, og dermed
oppnå, akkurat som Laura gjorde, swap.
>> Så la oss gjøre akkurat det.
La meg gå videre og åpne opp et eksempel som er
faktisk kalt "no bytte ", fordi dette ikke er
som rett og slett gjort som du kanskje tror.
Så i dette programmet, legge merke til at Jeg bruker stdio.h, vår gamle venn.
Jeg har prototypen for swap opp der, som
betyr gjennomføringen er trolig ned nedenfor,
og la oss se hva denne hoved Programmet kommer til å gjøre for meg.
Jeg først erklære int x blir en, og int y får to.
Så tenker på dem som OJ og melk, henholdsvis.
Og da jeg bare har en printf si x er dette
og y er dette, så jeg kan visuelt se hva som skjer.
Så jeg har printf hevde at jeg bytte de to,
og da jeg skrive ut en hevder at de er byttet,
og jeg skrive ut x og y igjen.
Så her nede i swap er nøyaktig hva Laura gjorde,
og akkurat det vi så på skjermen et øyeblikk siden.
>> Så la oss gå videre og bli dypt skuffet.
Gjør ingen swap, og kjøre uten swap, zoomer inn på produksjonen her.
Skriv inn x er 1, y er 2, bytte byttet.
x er fortsatt 1, og y er fremdeles 2.
Så selv om, ærlig, dette ser nøyaktig like, om enn mer teknisk,
hva Laura gjorde, ikke synes å fungere.
Så hvorfor er det?
Vel, det viser seg at når vi skrive et program som dette
som har både hoved, uthevet her, og deretter en annen funksjon, som swap,
uthevet her, som det kaller, verden
ser litt noe sånt Disse skuffene et øyeblikk siden.
Når hoved først blir kalt, det er som å spørre operativsystem
for litt minne for eventuelle lokale variabler som x og y som har hoved,
og de ender opp akkurat der.
Men hvis hoved samtaler bytte, og hoved går å bytte to argumenter, a og b,
appelsinjuice og melk, er det ikke som late appelsinjuice og melk
til Laura.
For en datamaskin gjør, er det passerer kopier av appelsinjuice
og kopier av melk til Laura, slik at hva som er i siste instans innsiden av denne skuffen
er verdien en og to, eller OJ og melk, men kopier av disse,
slik at på dette punktet i historien, det
er OJ og melk i hver av disse skuffene.
Det er en en og en to i hver av disse skuffene,
og swap-funksjonen faktisk fungerer.
Det er å bytte dem inne av den nest øverste skuffen,
men at swapping har ingen innvirkning.
Og basert på bare noen grunnleggende prinsipp vi har
snakket om før, og faktisk bare noen få minutter siden, hva
kan forklare hvorfor endring a og b innsiden av swap
har ingen effekt på x og y, selv om Jeg passerte x og y til swap-funksjonen.
Hva er stikkordet her at kanskje éntrådet forklare?
Jeg tror jeg hørte det her?
PUBLIKUM: Return.
SPEAKER 1: Gå tilbake?
Ikke tilbake.
La oss gå med en annen.
Hva er det?
>> PUBLIKUM: [uhørlig].
>> SPEAKER 1: OK, så return-- vi kunne gjøre retur arbeid i historien,
men det er en enda enklere forklaring.
PUBLIKUM: Scope.
SPEAKER 1: Scope.
Jeg tar omfang.
Så omfanget, huske hvor vår x og y deklarert.
De er erklært inne av hoved rett opp her.
a og b, i mellomtiden, er effektivt erklærte
innsiden av swap, ikke helt i klammeparentes, men likevel
i det generelle området av swap.
Og så ja, a og b bare eksisterer innenfor denne skuffen
fra Annenberg, dette andre del av kode.
Så vi faktisk endre kopien, men det er egentlig ikke alle som nyttig.
>> Så la oss ta en titt på dette litt lavere nivå.
Jeg kommer til å gå tilbake til Source Directory,
og jeg kommer til å først zoome inn her, og bare
for å bekrefte at jeg er i dette større terminalvindu,
Programmets fortsatt oppfører seg som det.
Anta nå at dette er ikke tilsiktet.
Klart jeg ville bytte til arbeid, så det føles som en bug.
Nå kunne jeg begynne å legge en Mange printf-tallet til min kode,
skrive ut x over her, y løpet her, en over her, b over her.
Men ærlig talt, det er nok det du har gjort for et par uker
nå, i kontortiden og hjemme når du arbeider
på psets prøver å finne noen bugs.
Men du vil se, hvis du ikke allerede har, det problemet satt tre introduserer deg
til en kommando som heter GDB, hvor GDB, GNU debugger,
har selv en hel haug med funksjoner som faktisk kan
la oss forstå situasjoner som dette, men mer overbevisende,
løse problemer og finne bugs.
Så jeg kommer til å gjøre dette.
I stedet for ./noswap, jeg er i stedet kommer til å kjøre GDB ./noswap.
Med andre ord, jeg kommer til å kjøre min programmet ikke i Bash, vår nye venn
i dag.
Jeg kommer til å kjøre min program noswap inne
av dette andre programmet heter GDB, som er en debugger, som
er et program som er utviklet for å hjelpe dere mennesker finne og fjerne bugs.
Så hvis jeg treffer Kjør her, det er en fryktelig mengde tekst
at du egentlig aldri trenger å lese.
Det er egentlig en distraksjon fra teksten, som
Jeg kommer til å treffe Kontroll-L å komme opp på toppen der.
Dette er GDB prompt.
Hvis jeg ønsker å kjøre dette programmet nå, som denne lille jukselapp på dagens
lysbilde antyder, Run er den første kommandoer som vi mente å innføre.
Og jeg bare kommer til å skrive løpe opp her inne i GDB,
og faktisk det kjørte mitt program.
Nå er det noen ekstra utgangene på skjermen som dette,
men det er GDB bare å være anal og fortelle oss hva som skjer.
Du trenger egentlig ikke å bekymre deg om disse detaljene akkurat nå.
Men hva er egentlig kult om GDB, hvis jeg gjør dette igjen--
Kontroll-L klarner screen-- la meg gå videre og type "bryte viktigste," dermed,
når jeg trykker Enter, sette hva som er kalt en pause punkt på noswap.c,
linje 16, som er der GDB funnet ut mitt program faktisk
er, min funksjon faktisk er.
Dette vil vi se bort for nå men det er adressen
i minnet spesielt for denne funksjonen.
Så nå når jeg skriver kjørt, legge merke til hva som er kult her.
Min program bryter ved linjen I fortalte GDB å stanse henrettelsen på.
Så jeg trenger ikke å nå endre min kode, legge til noen printf-tallet, rekompilere det, reprise
det, endre, legge til noen printf-tallet, lagre det, rekompilere den, kjøre den.
Jeg kan bare gå gjennom mitt program skritt for skritt for skritt ved human hastighet
ikke på Intel-inside slags hastighet.
>> Så nå merker denne linjen vises her, og hvis jeg går tilbake
mitt program i gedit, legge merke til at det faktisk er
den aller første linje med kode.
Det er linje 16 i gedit.
Det er ledningen 16 i GDB, og selv om denne svarte og hvite grensesnitt
er ikke på langt nær så bruker vennlig, betyr dette
at linjen 16 har ikke blitt utført ennå, men det handler om å være.
Så ja hvis jeg skriver print x, ikke printf, bare print x,
Jeg får noen falsk verdi der på null, fordi x er ikke klargjort ennå.
Så jeg kommer til å skrive neste, eller, hvis du ønsker å være fancy, bare n for neste.
Men når jeg skriver dette oppgir nå merker det går videre til linje 17.
Så logisk, hvis jeg har henrettet linje 16 og jeg nå skriver print x,
hva bør jeg se?
One.
>> Og nå er dette riktignok forvirrende.
$ 2 er bare en fancy måte, hvis du ønsker å referere til denne verdien senere,
du kan si "dollar sign to."
Det er som en back referanse.
Men for nå, bare ignorere det.
Det interessante er hva som er på høyre side av likhetstegnet.
Og nå hvis jeg skriver neste gang og print y, skal jeg se 2.
Jeg kan også nå skrive ut x igjen, og ærlig,
hvis jeg får en litt forvirret med hensyn til hvor jeg er, kan jeg skrive liste for liste
og bare se noen sammenheng rundt poenget er jeg faktisk på.
Og nå kan jeg skrive neste, og det x er 1.
Nå skriver jeg neste.
Oh, er y 2.
Og igjen, det er forvirrende, fordi GDB utgang
blir blandes med min egen utgang.
Men hvis du huske på, ved skotter frem og tilbake på koden din
eller legge det ut siden ved side kanskje, vil du
se at egentlig er jeg bare stepping gjennom mitt program.
>> Men legg merke til hva som skjer videre, bokstavelig talt.
Her er linje 22.
La meg gå over den, og dermed går videre til 23, og hvis jeg skriver ut x nå, fortsatt en.
Og hvis jeg skriver ut y nå, fortsatt en.
Så dette er ikke en nyttig øvelse.
Så la oss gjenta dette.
La meg gå tilbake til topp og type løp igjen.
Og det sier programmet som blir feilsøkt
har startet allerede, startet fra begynnelsen.
Ja, la oss gjøre dette igjen.
Og denne gangen la oss gjøre videre, neste, neste, neste, neste,
men nå ting blir interessant.
Nå ønsker jeg å gå inn swap, så jeg ikke skriver neste.
Jeg skriver skritt, og nå merke det har hoppet meg til noswap.c linje 33.
Hvis jeg går tilbake til gedit, hva er linje 33?
Det er den første faktiske kodelinje innsiden av swap.
Som er fint, for nå kan jeg slags rote rundt og få nysgjerrig
om hva som skjer virkelig i det.
La meg skrive tmp.
Whoa.
Hvorfor tmp har noen gal, falsk søppel verdi?
PUBLIKUM: Det har ikke blitt initialisert.
SPEAKER 1: Det har ikke blitt initialisert.
Og ja, når du kjører et program, du får en hel haug med minne
av operativsystemet, men du har ikke initialisert noen verdier,
Så uansett hva biter du er ser her, selv om det er
denne sprø stor negativ nummer, betyr bare
at de er restene fra noen tidligere bruk av RAM,
selv om jeg har ikke meg selv trengte det ennå.
Så nå kommer jeg til å gå videre og type neste, og hvis jeg nå skriver print tmp,
hva bør jeg se?
Når verdien av en var, a er det første argumentet, bare
som x var den første ting blir vedtatt i,
slik at en og x bør være den samme, så ut tmp bør skrive meg en.
>> Så hva du vil se i Oppgavesettet tre er en tutorial av former på GDB,
men innser at dette er begynnelsen av en titt på et verktøy som faktisk vil
hjelpe deg med å løse problemer så mye mer effektivt.
Hva vi er i siste instans kommer til å gjøre på onsdag
er begynner å skrelle tilbake et par lag og fjerne noen trening hjul.
Den tingen kalt streng som vi har brukt på en stund,
vi kommer til å sakte ta det bort fra deg og begynne å snakke om
noe mer esoterisk kjent som char *,
men vi kommer til å gjøre dette hyggelig og forsiktig først, selv om pekere,
som de kalles, kan gjøre noen veldig dårlige ting hvis misbrukt,
ved å se på en liten leireanimasjon fra vår venn Nick Parlante fra Stanford
University, en professor i data vitenskap som satt sammen denne forhåndsvisningen
av hva som kommer denne onsdagen.
>> [VIDEOAVSPILLING]
-Hei, Binky.
Våkn opp.
Det er tid for pekeren moro.
>> Hva er det?
Lær om pekere?
Oh, goody!
[END VIDEOAVSPILLING]
SPEAKER 1: som venter deg på onsdag.
Vi får se deg da.
[VIDEOAVSPILLING]
-Og Nå, dype tanker, av Daven Farnham.
>> Hvorfor lærer vi C?
Hvorfor ikke A +?
>> [Latter]
>> [END VIDEOAVSPILLING]