[Predvajanje glasbe] 

ZVOČNIK 1: V redu, to je CS50, in to je začetek štirih tednu in kot ste lahko slišali ali prebral, je bil svet konča. Gre vse po internetu se je znanje in osveščenost bug v program, programski jezik imenovan Bash. To je bilo čudovito blagovno znamko kot Shellshock ali vrat Bash, vendar predmeti, kot so ti niso bili redki. In v resnici, mnogi od njih prinese nazaj spomine Heartbleed, ki ste morda opazili v pritisnite nazaj to čez pomlad, ki je bilo podobno precej dramatično. Zdaj za tiste, ki ste tu danes, koliko od vas ima, tudi če ne boste razumeli, kaj to je vse o, slišal Shellshock? Vse v redu, in koliko vas računalnike, ki so ranljivi? OK, ne bi smelo biti veliko, veliko več roke do sedaj, iz razlogov, bomo videli. 

Oglejmo si, kaj je se dogaja v medijih in potem to pojasni malo tu za nas tehnično. 

SPEAKER 2: Varnostni strokovnjaki imajo Opozoril je, da bi resna napaka biti na tem, da vplivajo na stotine milijone svetovnih uporabnikov spleta. Torej, kaj točno je hrošč, ki je bil poimenovan Shellshock, in kaj storiti? Torej, je Shellshock znan tudi kot Bash bug, software izkorišča. Hekerji uporabljajo virus skeniranje ranljivi sistemov teče Linux in UNIX operacijske sisteme in jih nato okuži. Bash je ukazni vrstici lupine. To omogoča uporabnikom, vprašanje ukaze za začetek Programi in funkcije v programski opremi ki jih vnesete v besedilo. To je s programerji običajno uporabljajo, in ne bi smeli biti odprti za širši svet, čeprav Shellshock spremeni to. 

No, worringly, nekateri analitiki opozarjajo, da bi lahko bila večja grožnja, ker Shellshock omogoča popoln nadzor okuženem računalniku, ker Heartbleed le dovoljene hekerji za vohunjenje za računalnike. To je tako resna, da je je ocenjeno na 10 od 10 za resnost s strani nacionalnih Ranljivost Database. 2/3 vseh spletnih strežnikov na tveganje, vključno z nekaterimi Mac računalnikov. Torej, poskrbite, da boste obliž svoje sisteme zdaj. Vsakdo, ki gosti spletno stran teče prizadeta operacijski sistemi bi moral ukrepati čim prej. Vsakdo, ki si lahko privoščijo, da je treba iskati na njihovo uporabo za spremljanje in spletni požarni zidovi, da pazi za napade. ZVOČNIK 3: Najhuje da bi se lahko zgodilo, je da bi nekdo napisal kodo, ki bo samodejno zagnal in skeniranje internet in bi vplivala na vsi od teh računalnikov. In ko bodo to storili, dobro, najslabša stvar, ki jo lahko naredite je šele izbrisati vse, ali zapreti mesta navzdol. Tako smo lahko videli škodo iz tega vidika, kjer bi imeli zlonamernih ljudi ki samo odloči, da bo povzročil opustošenje Z uskladitvijo sistemov navzdol ali brisanje datoteke in take stvari. SPEAKER 2: Nekateri pravijo, da je to ena izmed najbolj težko izmeriti hrošči v letih, in to lahko traja tedne ali celo mesecev za določitev končnega učinka. 

ZVOČNIK 1: Torej, vse to je res, vendar Hecno je, skoraj vse od podob, ki ste jo pravkar videl, razen morda tipkovnico, nima nič opraviti z bug whatsoever. Strežniki in žice in tako naprej, to je nekako le bežno povezani, ampak bistvo je pravzaprav zelo seznanjeni, kaj se dogaja tukaj. V bistvu me spustili v naša CS50 aparata. Dovolite mi, da gredo naprej in čim bolj terminal window tukaj. In fantje so bili z uporabo tega ali vdelani njihove različice, v gedit za pisanje programov, vpisovati ukaze, in tako naprej, in to je dejansko, in ima že več tednov, Bash, B-A-S-H. To je Bourne-spet lupini, ki je samo fancy način rekel, to je program, ki ima utripa hitro, učinkovito, da sedi tam čaka za vhod za vas. In to je ukaz linijski vmesnik, prek katerega fantje so bili teče ukaze in končno sestavljanje in nato teče programov. 

Ampak Bash je tudi programiranje jezika v naslednjem smislu. Veste, da obstajajo ukazi, kot so cd in ls in tudi Jek in drugi, vendar pa lahko določite lastne ukaze ki jih za njihovo izvajanje v Bash. Zdaj mi ne bo iti v podrobnosti da Bash programski jezik, ampak vedeti, na primer, da se v trenutku, ni ukaz imenovano "zdravo." Tako je mogoče najti v eden od teh paketov. To ni nameščen na mojem računalniku. Se obrnite na skrbnika. Ampak, če želim, da obstaja program, imenovano "zdravo" v Bash ali na mojem pozivu, Jaz lahko dejansko uporabljajo sintakso, ki je zelo všeč C. To ni čisto enak, ampak izgleda precej podobno funkcijo, čeprav manjka nekaj podrobnosti. Nič ne kaže, da se zgodi, ampak zdaj, če sem tip "zdravo" lahko dejansko napisati Program, ne v C, ne v Java, ne v drugem načrtovanju jezik, ampak v Bash sam. 

Zdaj Ključno je, da sem napisal ime sem si želel, da bi ta novi ukaz, in oklepaji so tudi simbolična saj je to funkcijo. Naj omenim, da lahko to storite tudi zabavno stvari, in v resnici, tudi na Mac OS, To je program, imenovan Terminal. Na voljo je vgrajen v kdorkoli je Računalnik, ki ima Mac v tej sobi, in lahko storite podobne stvari na Mac OS, lahko pa gre za več kot to. In to je malo tangencialna, ampak to je kar zabavno. Sem se spomnil zjutraj, ko je ta razmišljanja, z malo igro sem igral z enim od CS50 nekdanjih TF s katerim koli je hodil od njegova tipkovnica s svojo zaslon odklenjen, Jaz bi izvršitev ukaza kot to-- "pozdravi". In zdaj vsak čas se je vrnil v svojo tipkovnico, ko sem odprl zaslon in bi on sedi, poskusite narediti nekaj dela, Vsebino svojega directory-- 

[AUDIO PREDVAJANJE] 

Zdravo. Pozdravljeni. 

ZVOČNIK 1: Tako je v pravičnosti, ni bilo dejansko "zdravo." Ponavadi je bilo nekaj bolj podobna to-- [AUDIO PREDVAJANJE] -Beep. ZVOČNIK 1: --that I bilo-- tako da bi njegov računalnik Prisegam na njega kadar koli je dejansko sedel na svoji tipkovnici. In zelo hitro je pogruntal da ne zapustijo njegov zaslon odklenjen. Vendar to kaže na neke butasto zabave, ki vas imajo lahko z nekaj podobnega Bash. Ampak to je malo več resno, da ne bo pomote, kot to. In v resnici, to je eden najnevarnejši in dolgotrajne bugs da je res zajela svet v svetovnem merilu. Ta bug je bila približno približno 20 let, in boste udari v samo Trenutek, ki ga njegove relativne preprostosti. 

Torej je ta zastopnik ukaz, da če vas lastnik Mac dobesedno zdaj ko imate svoj pokrov odprt, lahko poskusite tipkanje v to program, imenovan Terminal. Terminal je pod Aplikacije Utilities-- za enkrat, Windows uporabniki ne bi bilo treba skrbeti za to določenem threat-- ampak tisti, ki ste z Maci lahko vnesete to v oknu, kot bom naredil tukaj, in če vam tip da se v ta program imenovan Terminal, kot bom zdaj, če vidite besedo "ranljivi" računalnik izpostavljeni izkoriščanju. 

Kaj to dejansko pomeni? In to je res nekateri precej noro sintaksa, ampak dajmo vsaj potegnili nekatere zanimive vidike. Torej je nekaj sintakse, ki je videti malo znano, vsaj od C in načrtovanje na splošno. Vidim nekaj oklepajev, podpičja, zavitimi oklepaji, in take, vendar se izkaže, da je to neumna stvar tukaj v rumeno je v bistvu funkcija da ne naredi ničesar. Sredstva debelega črevesa storiti ničesar, in podpičje pomeni stop delam nič. Tako znotraj teh zavitimi oklepaji, dejstvo, da imam enako podpis na levo, to je v bistvu ustvarjanje ukaz, ali spremenljivi imenuje x in ga dodeliti da je rumena malo kode tam. , Da bi lahko nekaj podobnega "echo zdravo "ali" pravijo beep "ali kaj podoben tistemu. Ampak obvestilo, če vaše oči nadalje sprehaja v desno, to še ni na tej liniji kot šele konec tega podpičjem. "Echo ranljivi," in nato tistega, ki obstaja še več. Druga podpičje, bash -c :. 

Tako da skrajšam zgodbo, ta vrstica kode je zadostuje za prepričljiv Računalnik, ki je dovzetni za početje nekaj , da želite to storiti, zato, ker je napaka v Bash, s katerim čeprav je bil Bash naj ustavi branje linije poveljevanja pravice tam po rumeno besedilo, za 20-plus let starega hrošča, Bash je dejansko branje onkraj te podpičjem in lepa še to, kar je povedal. 

Torej, kaj je posledice od tega na koncu? Rekel sem "echo zdravo" ali "echo ranljivi," kaj pa če si kaj dejansko zlonamerno, kot rm -RF *, ki morda ne kdaj tipkal prej, in odkrito verjetno ne bi smeli prehitro, ker lahko narediš Veliko škode z njo. Zakaj? rm za kaj, seveda? Odstrani. * Pomeni kaj? Vse. Torej, to je tako imenovani joker, tako da to pomeni izbrisati vse, kar je v trenutni imenik. r se zgodi, da pomeni rekurzivna, kar pomeni, če kaj ste izbrisali je imenik, in notranjost je je druge datoteke in druge imenike, rekurzivno potopite tam in izbrisati vse to. In -f je najslabša od vseh. Kdo ve, kaj pomeni -f tukaj? Force. Torej prisili sredstva, tudi če je to slaba ideja, to storiti, ne da bi me spodbudilo za nadaljnjo potrditev. Torej, veš, mi smejali to, vendar odkrito povedano, sem verjetno to večkrat vnesete dan, saj realnosti je, da je najhitrejša pot do izbrisati cel kup stvari. Ampak tudi jaz naredil nekaj škode. 

Ampak, če ste bili, da pretenta računalnik v opredelitvi nekaj neumnega spremenljivko ali funkcijo imenovan x, potem pa prelisičijo računalnik v izvršilni preko meja, ki funkcija, poleg tega podpičjem, da bi lahko res trik računalnik v izvršilni nekaj podobnega rm -rf ali ukaz Email ali ukaz Kopiraj. Vse, kar dobesedno lahko storite z računalnik, pa naj gre za brisanje datotek, ustvarjanje datotek, spamming nekoga, napadajo nekaj strežnika na daljavo, če lahko izrazijo z ukazom, si lahko pretentati računalnik v tem. 

Zdaj, kaj je primer kako si lahko to storil? No, tam je veliko računalnikov na internet teče Bash. Vse uporabnike nas Mac so med njimi. Veliko strežnikov Linux so med njih, kot tudi, in strežnikov Unix. Windows spet dobi relativno off kavelj če ste namestili posebna programska oprema. Zdaj veliko strežnikov, za instance, vodenje spletnih strežnikov, in v resnici je Linux morda najbolj priljubljen operacijski sistem da deluje na računalnikih, na internetu da služi up spletne strani. Zdaj, kot bomo videli kasneje v semestru, ko pošljete zahtevo vaš browser-- Chrome, Internet Explorer, whatever-- na oddaljenem strežniku, Izkazalo se je, da je kljub temu, si tipkal www.example.com, Vaš brskalnik sporoča da je malo bolj skrivnostne, kot je ta. 

Opazil Nekaj ​​čudnega. Prvi dve vrstici Še nikoli nisem videl, vendar ne izgledajo še posebej nevarna. Ampak obvestilo, kaj sem ukradel za tretjo linijo tukaj. Če bi bila slab človek, da pošljete sporočilo kot je ta iz svojega računalnika ranljivi Mac ali ranljive Linux strežnik, Hecno je, da Bash, Tako preprosto je malo ukazno vrstico, je vseprisotna in je pogosto vajeni predvsem izvršiti vsebina sporočilo, ki ga prejme. In s to logiko, lahko pretentati spletni strežnik, zato s pošiljanjem nekaj podobnega User-Agent, ki običajno naj bi se reči, Ime vašega brskalnika. User-Agent Chrome, User-Agent Internet Explorer, User-Agent Firefox, ta je samo svojega brskalnika način se prepoznava. Ampak, če je slab človek zelo spretno pravi, mm-mm, sem ne bom ti povedal kaj je moj brskalnik, Jaz sem namesto tega bomo pošiljali ta skrivnosten videz stvar z rm -RF * V njem, lahko dobesedno trik ranljivi spletni strežnik na internetu v izvršilni točno, da je v tam za brisanje vseh datotek. In odkrito povedano, to ni celo najhujše. Lahko narediš karkoli. Začnete lahko razdeli zanikanje napada storitev Če ste poslali to sporočilo cele grozde spletnih strežnikov in nato jih imela vse spustimo, za instance, na Harvard.edu strežnikih, in jih lahko razvrstite po poku vraga iz njih omrežnega prometa, ki je bil s tem slab človek drugače sprožijo. 

Torej, skrajšam zgodbo, skoraj vsi v tej sobi, ki ima v lasti Mac je občutljiva na to. Sončni žarek je, da če ste teče spletni strežnik na vaš prenosnik, in če ste jih dejansko nastavljen to, da bi nekaj podobnega SSH vanjo, ti si dejansko varen. To je občutljiva, vendar ni eden poskuša priti v prenosni računalnik, tako da lahko nekako prepričani. Vendar pa bo Apple kmalu biti posodabljanje določi za to. Svet Linux je že izšla število popravkov za Fedora in Ubuntu in drugih različic Linuxa in dejansko če naletite posodobitev 50 na aparatu, celo, da se bo tudi treba posodobljena in popravljena. Ampak to je preveč, ne Res je ranljiva, ker, če nimate tinkered z napravo in javnosti na vaš prenosnik dostopne na internetu, ki ni privzeto, ki ste jih pravzaprav že v redu, ker za požarni zid in drugih tehnik. 

Ampak to je skrajni primer hrošča da smo živeli za dobesedno 20 let, in kdo ve, če je kdo Ves ta čas je znano o tem? In v resnici, to je eden izmed temeljnih izzivov da bomo videli kasneje v semester o varnosti, je, da tako kot v resničnem svetu, dobri fantje so v slabšem položaju. Če želite, da slabi fantje ven, moramo poskrbite, da se vsa vrata zaklenjena, da je vsako okno varen, da vsaka točka vstopa v dom je varno, da slabi fantje ven. Ampak kaj slab človek moral storiti, da bi dejansko ogrozijo vaš dom in kradejo od vas? On ali ona je samo, da bi našli enega odklenjen vrata, ena broken window, ali kaj v tej smeri, in to je Isto za računalniško varnost. Mi lahko napišete milijone vrstic programske kode in porabili več sto ali tisoč ur, ki skušajo zaslužiti to pravilen, ampak če bi samo enega Napaka v točnosti, lahko postavite celoten sistem in dejansko v tem primeru, je celotna interneta in svet v nevarnosti. 

Torej, če želite izvedeti več o tem, pojdite na ta URL tukaj. Ni potrebe za ukrepanje Nocoj, če ste med tistimi, ki bolj udobno, da so tekmovanje v teku svoj spletu strežnik, v tem primeru bi smeli, v resnici, posodobite programsko opremo. 

In tudi to je naslov govor, in zdaj papir, da smo povezani na Spletna stran seveda za danes. Bilo ga je kolega imenom Ken Thompson, ki je je sprejemala zelo znan nagrada na področju računalništva, in on je dal ta govor nekaj let nazaj, v bistvu na to isto temo. Sprašuje ljudje vprašanje, bi bilo res zaupanje, na koncu, programsko opremo, ki ste jih dobila? Na primer, vsi imamo je pisanje programov, in smo bili sestavljanje jim z Jek. In s svojim znanjem, ki ste jih napisal vseh programov za CS50, kjer obstaja zadnja vrata z menoj, tam je pot da je slab človek, če teče svoj program, lahko prevzame računalniku? Verjetno ne, kajne? Mario in požrešen, in Credit. Vse to so zelo majhne programe. Morali bi biti precej slabo, če vas dejansko je ves vaš računalnik ranljiv po pisanju 10 ali 20 vrstic kode, ali vsaj ne poznajo nekaterih posledic varnosti. Zdaj pravijo, da facetiously, ampak bomo videli danes in ta teden je dejansko Res, zelo enostavno da je slabo in da celo kratki programi ranljivi. 

Ampak za zdaj, vsaj zavedaš da se vprašanje sem vprašal Gre Jek v prevajalnik. Zato smo bili zaupamo Jek v zadnjih dveh ali treh tednih? Kdo pravi, da kdor je napisal Jek ni imela "če" stanje v tam da v bistvu vbrizga nekaj ničel in tisti, v vsakem programu se pripravlja da bi pustil ali njen dostop vaš računalnik, ko spiš in vaš prenosnik pokrov je odprt in je vaš računalnik teče? Prav? Imamo to vrsto čast sistema pravice Zdaj, ko smo prepričani, da je Jek zakonit. Zaupate, da je aparat zakonit. Zaupate, da dobesedno vsak program, na vašem Mac ali PC, je vreden zaupanja. In to preprosto bug kaže, tudi če to ni zlonamerno, to je absolutno ne verjetno, da bo tako. 

Torej bi morali biti strah kot hudič. Odkrito povedano, ni preprosta Rešitev tega drugo kot neke družbene zavesti naraščajoče kompleksnosti da gradimo na vrh naših računalniških sistemov, in kako bolj ranljiva smo lahko zelo dobro. 

Zdaj s tem je dejal, Breakout. Torej Breakout je problem določiti tri, in Breakout je igra od minulih dni da boste morda spomnite, vendar za nas problem določiti tri, to nam omogoča, da sprejmejo Stvari back up zarezo tako da, ko pišemo programe, celo v Terminal oknu, kot je ta, bomo lahko dejansko vozijo, na koncu, grafični programi niso za razliko od tistih, ki jih je imel Dostop v nič. Torej, to je za zaposlene je Izvajanje Breakout, ki je le ta brick-breaking Igra, ki jo premikanje vaših veslo nazaj in tja, in si udaril žogo zoper te barve opeke up vrhu. Torej, to je nam prinaša nekako nazaj, kjer smo lahko zelo hitro z nič, zdaj pa s C, izvajanje lastne grafični uporabniški vmesniki. 

Še več, ta Problem sklop predstavlja prvi , v kateri smo kar ti kup kode. In v resnici, sem prinesel izrecno pozornost, ker zlasti za tiste manj udoben, to problem določiti, vsaj na prvi pogled, se dogaja, da se počutim kot smo jo prevzeli zarezo. Saj smo vam ga je dal, za nekatere iskanju in reševanju problemov v pset, kup kode, ki jih je napisal, in nekaj pripomb ki pravijo "narediti" , kjer boste morali izpolniti obrazec. Tako da ne preveč strašljivo, vendar to je prvič smo vam izroči kodo, ki jo potrebujete za najprej prebrati, razumeti, in nato dodamo in jo izpolnite. 

In nato z Breakout, bomo storili enako, vam daje nekaj deset več vrstic kode, odkrito povedano, daj, da ti Veliko okvira za Igra vendar stop short izvajanja opeke in krogla in veslo, ampak bomo izvedli nekatere druge funkcije. In tudi, da je na prvi pogled, še enkrat, še posebej, če je manj udoben, Morda se zdi še posebej zastrašujoče in misliš, da je tako veliko novih funkcij morate zaviti vaš um okoli, in to je res. Toda ne pozabite, to je zelo všeč nič. Kvota se niste uporabili vse kosov sestavljanke v nič. Verjetnost, da vam ni mar za zavijanje vaš um okoli vse od njih ker vse to je bilo hiter pogled razumeti, oh, to je tisto, kar lahko naredim s tem puzzle kos. In res, v problem nastaviti 3 spec, vam bomo točko V dokumentaciji, ki bodo vam predstavil nekaj novih funkcij, in na koncu programskega konstruira uporabljate. Pogojev, zank, spremenljivke in funkcije bo enaka kar smo videli doslej. 

Torej res, kaj bomo dal si je nekaj vzorčno kodo, ki vam omogoča, da ustvarite okno da ne izgleda za razliko od tega, in ga na koncu spremeni v nekaj povsem tako. Torej izkoristite CS50, razpravljali o uradnih ur in več, in vseeno zadovoljen z dejstvom, da je znesek kodo morate pisati pravzaprav sploh ni tako veliko. Prvi izziv je samo aklimatizirati sami do neke kode, ki smo jih napisali. 

Vsa vprašanja v zvezi pset3, Shellshock, ali kako drugače? 

OBČINSTVO: Zdelo se je, kot preživlja z Breakout da koda je skoraj objektno usmerjen slog, vendar sem mislil, C je objektno programa. ZVOČNIK 1: Odlično vprašanje. Torej, v pogledu skozi distribucijo kode, koda smo pisali za pset3, za tiste, ki poznajo, ga Izgleda, da je malo objektno usmerjen. Kratek odgovor je, da je. To je približek, kako si lahko storite objektno usmerjen kodo pomočjo jezik kot C, vendar je še vedno na koncu postopkovno. Ni metode notranji del spremenljivke, kot boste videli. Ampak to spominja na to. In bomo spet videli, da funkcijo ko pridemo v PHP in JavaScript proti koncu semestra. Ampak za zdaj, pomislite, da je namig o tem, kaj je, da pridejo. Dobro vprašanje. V redu. Torej zlivanjem je bilo, kako smo leva stvari zadnjič. In zlivanjem je kul občutek, da je bilo tako veliko hitreje, temelji vsaj na Letimičan testov smo prejšnji teden, kot, recimo, mehurček sort, izbor sort, vstavljanje sort. In kaj je bil čeden preveč je le kako jedrnato in čisto ga lahko izrazi. In tisto, kar smo rekli, da je zgornja vezan na čas spajanja teče razvrstiti? Ja? 

OBČINSTVO: n log n? 

ZVOČNIK 1: n log n, desno. n log n. In se bomo vrnili na tisto, ki v resnici pomeni, ali če ta prihaja, ampak to je bilo bolje kot tisto, kar teče čas da smo videli za bubble Izbor in vstavljanje nekako? Torej n kvadrat. n kvadrat je večji od tega, in tudi če to ni očitno, vedo, da je log n manjši od n, tako da, če vam n-krat nekaj manjša od n, da se dogaja, da je manj kot n kvadrat. To je malo intuicije tam. Vendar smo plačali ceno za to. Bil je hitrejši, vendar pa tema, ki se je začela pojavljati prejšnji teden je bil ta kompromis. Imam boljšo zmogljivost čas pametno, ampak kaj sem moral porabiti za druge roko, da bi to dosegli? 

OBČINSTVO: Memory. ZVOČNIK 1: Ponovi? OBČINSTVO: Memory. ZVOČNIK 1: Memory, ali prostor bolj na splošno. In ni bilo super Očitno z našimi ljudmi, vendar pa opozarjajo, da naši prostovoljci so stopam naprej in poglobitvi nazaj, kot da obstaja niz tu, kot da bi tam Drugi niz tukaj, da ki bi jih lahko uporabili, ker smo potrebnejši nekam, da se združijo te ljudje. Mi samo ne bi jih lahko zamenjali v mestu. Torej zlivanjem vzvod je več prostora, ki nam ni bilo treba z drugi algoritmi, ampak glavo je, da je veliko hitreje. In odkrito povedano, v resničnem svetu prostor ti days-- RAM, trdi disk space-- je relativno poceni, in da je ni nujno slaba stvar. 

Torej, kaj je na hitro pogledamo, malo bolj metodično, na kar smo storili in zakaj smo rekli, da je bil n log n. Torej, tukaj so osem številk in Osem prostovoljcev smo imeli zadnjič. In prva stvar, ki Merge Razvrsti nam je povedal, da je naredil kaj? OBČINSTVO: Razdelimo na dva dela. ZVOČNIK 1: Ponovi? OBČINSTVO: Razdelimo na dva dela. ZVOČNIK 1: razdelite na dva dela, prav. To je zelo spominja na telefonski imenik, od razkoraka in osvojiti bolj na splošno. Tako smo pogledal na levi polovici. In potem, ko smo rekli, neke leva polovica elementov, kaj bomo naslednjič rečem? Razvrstimo levi polovici levi polovico, kar nam je omogočilo, da se, potem delimo na dva dela, osredotočiti na štiri in dve. 

Kako si uredite seznam zdaj, rumene barve, velikosti dveh, z uporabo zlivanjem? No, ga razdelite na pol, ter razvrstite levo polovico. In to je bilo, kje se stvari imam malo neumno kratko. Kako ste razvrstiti seznam, ki je od velikost ena, kot je ta številka štiri tukaj? To je urejeno. Ste končali. 

Ampak potem kako razvrstiti seznam velikost ena, ko je številka dve? No, isto stvar, ampak zdaj, kar je bilo Tretji in najpomembnejši korak v zlivanjem? Ste morali združiti levico polovico in desno polovico. In ko smo naredili, da smo pogledali ob štirih, mi pogledal dva. Odločili smo se, vse v redu, Očitno sta na prvem mestu, zato smo poslali dva v svojem mesto, sledijo štiri. In zdaj moraš nekako nazaj, in to je nekako značilno algoritma kot Merge Sort, previjanje nazaj v spomin. Kaj je naslednja vrstica zgodbe? Kaj naj se osredotoča na naslednje? Desna polovica levega in pol, ki je šest let in osem. 

Torej, povej mi samo korak skozi to brez belaboring točko preveč. Šest in osem, nato pa je šest razporejene, osem je razvrščen. Jih združiti skupaj, kot da je in zdaj naslednji velik korak je, seveda, razvrščanje desno polovico od Zelo prvi korak tega algoritma. Tako smo se osredotočili na eno, tri, sedem, pet. Nato smo se osredotočili na levi polovici. Leva polovica da pravica polovica da, in nato združiti v eno in tri. Nato desno polovico, nato levo polovico nje, nato desno polovico njega. Združiti, v, in kaj zdaj korak naprej? Združiti velik levo polovico in velika desna polovica, tako da eden gre dol, Nato dva, nato tri, nato štiri, nato pet, nato pa šest, nato sedem, nato osem. 

Torej, zdaj, zakaj je to končno razkril, še posebej, če je n in logaritmi več splošno precej vas pobegniti, vsaj v zadnjih pomnilnik? No, opazil, da se višina te stvari. Imeli smo osem elementov, in je deljeno z dva, z dvema, po dva. Torej, se prijavite bazo dva od osmih nam daje tri. In verjemi mi, da če malo motna o tem. Vendar se prijavite baza dve od osmih je tri, Tako smo naredili tri plasti združevanja. In ko smo se združili elementi, koliko elementov pa gledamo na vsaki od teh vrstic? Skupno n, kajne? Ker je, da se združijo v zgornji vrstici, čeprav smo to storili po kosih, smo na koncu dotaknili vsak številko enkrat. In v drugi vrsti, da spajanje teh seznamov velikosti dveh, smo imeli na dotik vsak element enkrat. In potem sem res jasno v zadnji vrsti, smo se morali dotakniti vsakega od tistih, elementi enkrat, vendar le enkrat, tako da tu leži, potem je naša n log n. 

In sedaj, samo da se stvari malo Bolj formalno le za trenutek, če vas so bili do zdaj analizirati to na nekakšni višji ravni in poskušajo odločiti, kako dobro lahko greste o izražanju Čas tega algoritem teče samo jih je videti na njej in ne z uporabo izmišljen primer? No, koliko časa bi rekli, korak, kot je ta v rumeni bi potrebovali, če je n <2 donos? To je velik O česa? Torej, vidim eno, tako en korak, morda dva koraka, ker je, če in se nato vrne, vendar je konstanten čas, kajne? Tako smo omenjeni O (1), in da je kako bom to izraziti. T, bodi čas teče. n je velikost vhoda, Tako T (n), samo fancy način rekel teka čas, saj vnos velikosti n se bo o vrstnem redu konstantno časa, v O (1). 

Sicer pa, kaj pa je to? Kako bi se ti izrazi teče čas to rumeno črto? T česa? Lahko nekako goljufija tukaj in odgovor na moje vprašanje ciklično. Torej, če je čas teče splošno smo pravkar rekel, je T (n). In zdaj ste nekako čolnarjenje tu in rekel, dobro, nekako levo polovico, nato pa razvrstite desno polovico. Kako bi mi simbolično predstavljajo Čas teče to rumeno črto? T česa? Kakšna je velikost vhoda? n preko dveh. Zakaj ne rečem, da je? In potem to je en T (n / 2) in nato še enkrat, če sem se združita dve razvrstite po polovici, koliko elementi bom da imajo na dotik skupno? n. Tako da sem lahko to izraziti, samo da bi nekako fancy, kot čas, ki teče na splošno. T (n), je le čas T (n / 2), ki teče, plus T (n / 2), levo polovico in desno polovico, skupaj O (n), ki je verjetno n korakov, ampak mogoče, če sem z dvema prstoma, to je dvakrat toliko koraki, vendar je linearna. To je nekaj več korakov da je faktor n, tako da bi to lahko izrazi kot to. In to je, če zdaj bomo punt na nazaj naše visoke šole matematičnem učbeniku smo, da ponovitve na koncu konča višini to, n-krat log n, če ste dejansko storiti math bolj formalno. 

Torej, to je le dve perspektive. Ena številčno z hard-kodirane reprezentativnem vzorcu uporabo osem številk, in še več splošno pogledamo, kako smo prišli tja. Ampak kaj je res zanimivo tukaj je, še enkrat, ta pojem od kolesarjenja. Jaz ne uporablja za zanke. Sem nekako opredeljevanju nekaj v smislu sebi Ne samo s tem Matematična funkcija, ampak tudi v smislu tega psevdo kode. To pseudo koda je rekurzivna v tej dveh njegovih vodov v bistvu je povedal, da gredo se uporabi za reševanje manjših problem manjše velikosti, in nato znova in spet, dokler ne bomo Zmanjšati je do tega tako imenovanega osnovnega postopka. 

Torej, kaj je dejansko pripraviti bolj prepričljivi sprejme proč od tega, kot sledi. Naj grem v gedit in se pogled na nekatere današnje izvorne kode, predvsem ta primer tukaj. Sigma 0, ki je očitno dodaja številke od ena do n. Pa poglejmo, kaj se pozna in ne poznajo tukaj. Najprej smo imeli nekaj vključuje, tako da nič novega ni. Prototip. Sem malo motna o ta po nekaj dneh, ampak tisto, kar smo rekli Prototip funkcije je? OBČINSTVO: [neslišno]. ZVOČNIK 1: Kaj je to? OBČINSTVO: Mi ga razglasi. ZVOČNIK 1: Mi ga razglasi. Torej si se učil Jek, hej, dejansko ne izvaja to še ni, ampak nekje v tej datoteki, verjetno, se dogaja, da se funkcija imenuje, kaj? Sigma. In to je samo obljuba, da to bo izgledala takole. To bo trajalo celo kot input-- in sem lahko bolj eksplicitno in pravijo, int n --and je vrača int, vendar podpičjem sredstva, mm, bom dobil okoli za izvajanje tega malo kasneje. Again, Jek je neumno. To je le, da bo vedel, kaj ti je povedal, od zgoraj navzdol, zato moramo vsaj dati je namig o tem, kaj je, da pridejo. 

Zdaj pa si oglejmo glavne tukaj. Pojdimo se pomaknite dol in videli, kaj glavna počne. To ni tako dolgo, funkcije, in Dejansko je konstrukt tukaj pozna. Izjavljam spremenljivo n, nato pa Sem znova in znova nadlegovanja uporabnika Za pozitivno celo število z uporabo getInt, in le izhod iz te zanke potem ko je izpolnil uporabnik. Storijo, ko smo uporabili za nadlegovanja uporabnika na ta način. Zdaj je to zanimivo. Izjavljam, int imenovano "odgovor". Sem, da vrne vrednost dodeliti funkcije, imenovano "sigma". Ne vem, kaj to počne še ni, vendar Spomnim se ga razglasi pred nekaj trenutki. In potem sem mimo v vrednost, ki jo uporabnik vtipka, n, in potem sem poročala odgovor. No dajmo se pomaknete nazaj le za trenutek. Pojdimo v ta imenik, bo sigma 0, in dejansko vodijo ta program in glej kaj se zgodi. Torej, če grem naprej in rok ta program, ./sigma-0, in sem tip v pozitivni celo kot dva, Sigma, kot trdi grška simbol, je le bodo sešteti vse številke od nič za do dve. Torej 0 plus 1 plus 2. Torej, to naj mi upamo dati 3. To je vse, kar počne. In podobno, če sem to spet teči in sem dal to številko tri, to je 3 plus 2, tako da je 5, plus 1 naj bi mi dal 6. In potem, če dobim res noro in začnite pisati v večjih številkah, to naj bi mi večje in večje vsote. Torej, to je vse. 

Torej, kaj sigma izgledal? No, to je precej preprosta. Pomembno je, kako lahko smo izvajali To za zadnjih nekaj tednov. "Int", se bo vrsta donos. Sigma je ime, in to traja spremenljivka m namesto n. Bom spremeniti up top. Potem je to samo pregled sanity. Bomo videli, zakaj v tem trenutku. Zdaj Izjavljam drugo spremenljivko, Vsota, inicializacijo nič. Nato sem imel to za zanko ponavljanjem, očitno zaradi jasnosti od i = 1 na do = m, ki je karkoli uporabnik vtipka, potem pa sem prirastek vsoto, kot je ta. In se nato vrne vsoto. 

Torej nekaj vprašanj. Ena, Trdim v mojem komentarju te ta izognemo tveganju neskončne zanke. Zakaj bi prenos negativno število povzroči, potencialno neskončno zanko? 

OBČINSTVO: Nikoli ne boste dosegli m. 

ZVOČNIK 1: Nikoli ne posegajte m. Toda m sprejet, tako da je menijo, preprost primer. Če je m sprejet z uporabnik kot negativnega. Ne glede na glavni. Glavna nas varuje pred tudi to, da sem pravkar pa res anal z sigma, da poskrbite, da vnos ne more biti negativna. Torej, če m je negativen, nekaj takega kot negativnega. Kaj se bo zgodilo? No, jaz se bom se inicializirana enem, in potem sem se bo manj kot ali enako m? 

Stati. To je bilo-- naj ne, dajmo Nix to zgodbo. Nisem vprašal to vprašanje, ker Tveganje, da sem namigoval, da se ne bo zgodilo, ker je i vedno bo večja than-- OK, I navije na to vprašanje. OK. Osredotočimo se le na ta del tukaj. Zakaj sem se razglasi nekatere zunaj zanke? Obvestilo o liniji 49 imam deklarirano i znotraj zanke, ampak na spletu 48 imam razglašena za nekaj zunaj. Ja. OBČINSTVO: [neslišno]. ZVOČNIK 1: Sure. Torej, v prvi vrsti prav gotovo ne želeli opredeliti in inicializacijo vsoto nič notranjosti zanke na vsaki ponovitvi ker bi bilo to jasno poraz Namen seštejemo številke. Jaz bi kar naprej spreminjati Vrednost nazaj na nič. In tudi, kaj je še ena več Skrivnosten Razlog za to isto odločbo oblikovanja? Ja. 

OBČINSTVO: [neslišno]. ZVOČNIK 1: Točno tako. Želim, da je dostopna zunaj zanke preveč na kakšni poti? Na 53. In na podlagi našega pravilo palca od nekaj predavanj nazaj, spremenljivke so scoped, res, da zavitimi oklepaji, ki jih obsegajo. Torej, če ne razglasi vsoto znotraj teh zunanjih zavitimi oklepaji, Ne morem uporabljati v skladu 53. Povedano drugače, če bi razglasila Vsota tukaj, ali celo v Zanke, nisem mogel dostopati ga v 53. Spremenljivka bo dejansko odšla. Torej nekaj razlogov tam. Toda zdaj se vrnimo in glej kaj se zgodi. Torej dobi sigma klical. Dodaja up 1 plus 2 ali 1 plus 2 plus 3, in nato vrne vrednost, V njej so zbrani v odgovoru, in printf tukaj Zato vidim na zaslonu. Torej, to je tisto, kar bom poklical ponavljajoč Pristop, kjer je ponovitev samo pomeni z zanko. Za zanke while zanko, storijo, ko zanka, samo spet delaš nekaj in znova in znova. 

Ampak sigma je nekako čeden funkcije v da sem lahko različno izvajajo. Kaj praviš na to, kar samo da bi nekako kul, Naj se res znebili z veliko odvračanja ker te funkcije je zelo preprosta. Pojdimo Zmanjšati dol samo na njegovih štirih temeljnih črt in se znebite vseh Pripombe in zavite oklepaje. To je nekako osupljivo alternativa izvajanje. V redu, morda ne moti, piha, ampak to je nekako seksi, vse v redu, da pogled na to toliko bolj jedrnato. Samo s štirimi vrsticami kode, Najprej moram to preverjanje prištevnosti. Če m je manjša ali enaka nič, sigma nima smisla. To naj bi bilo samo v V tem primeru za pozitivna števila, tako da sem le, da bo vrne nič samovoljno tako da ima vsaj nekateri tako imenovani osnovni primera. 

Ampak tukaj je lepota. Celota te ideje, dodajanje številke od 1 do n, ali m je v tem primeru, je mogoče storiti z vrsto prelaganje. No, kaj je vsota 1 do m? No, veš kaj? To je enako kot vsota m plus vsota 1 do m minus 1. No, veš kaj? Kaj je sigma od m minus 1? No, če ste nekako slediti tem Logično, to je isto kot m minus 1 plus sigma iz m minus 2. Tako da lahko nekako samo-- to je kot, če ste pravkar poskuša nagajati prijatelju in jih nekaj vprašam, si nekako odzvati z vprašanjem, lahko nekako obdržati prelaganje. Toda kaj je ključnega pomena je, da če boste obdržali tako vprašanje manjši in manjši in manjši, ste Ne sprašujem, kaj je sigma n, kaj je sigma od n, kaj je sigma n? Vi sprašujete, kaj je sigma n, kaj je sigma n minus 1, kaj je sigma n minus 2? Sčasoma vaše vprašanje bo postal kaj? Kaj je sigma ene ali nič, zelo majhne vrednosti, in takoj, ko vas dobili, da svojega prijatelja, ne boste vprašati spet isto vprašanje, greš samo reči, oh to je nič. Mi smo se več igral te vrste butasto cikličnega igri. 

Torej rekurzija je dejanje pri načrtovanju funkcije, kliče sama. Ta program, ko se zbirajo in vodijo, je dogaja, da se obnašajo natanko enako, toda kaj je ključnega pomena je, da se v notranjosti funkcije, se imenuje sigma, je vrstica kode čemer smo sebe kliče, , ki bi običajno bilo slabo. Na primer, kaj če sem prvič zbrati to, zato poskrbite sigma-- da sigma 1 ./sigma-1. Pozitivno celo število, prosim, 50 1275. Torej, kaj funkcija izgleda biti, ki temelji na enem testu, pravilno. Toda kaj, če dobim malo nevarno in brišete tako imenovano osnovno zadevo, in samo reči, tudi jaz sem samo izdelavo to bolj zapleteno, kot je. Reciva izračun sigma ob m in nato dodajanjem v sigma m minus ena? No, kaj se bo zgodilo tukaj? Pojdimo pomanjšati. Pojdimo prevedite program, ga shranite, prevedite program, in nato pripravljen ./sigma-1 povečave, vnesite pozitivno celo prosim, 50. Koliko ste pripravljeni da priznaj, da vidim, da je? 

OK. Torej, to se lahko zgodi pri več razlogov, in odkrito ta teden smo o tem, da bi vam več od njih. Toda v tem primeru poskusite nazaj k razumu kaj bi se lahko zgodilo tukaj? Segmentacija napaka, smo rekli zadnje čas, se nanaša na segment pomnilnika. Nekaj ​​slabega se je zgodilo. Toda, kaj je bilo mehansko, ki je šel po zlu sem zaradi moje odstranitve navedene tako imenovanega osnovnega primeru kjer sem se vrnil trdi kodirana vrednost? Kaj misliš, da je šlo narobe? Ja. 

OBČINSTVO: [neslišno]. ZVOČNIK 1: Ah. Dobro vprašanje. Torej velikosti števila da sem povzel imaš tako velika, da je presegla velikost pomnilniškega prostora. Dobra ideja, vendar ne bistveno dogaja, da povzroči nesrečo. To lahko povzroči integer overflow, kjer bitov samo obrnila in potem bomo zamenjali res velik številka, kot pa z negativnim predznakom, vendar to samo po sebi ne bo povzročilo nesrečo. Ker na koncu dan int je še vedno 32 bitov. Saj ne bo naključju ukrade 33. bit. Ampak dobra misel. Ja. 

OBČINSTVO: [neslišno]. ZVOČNIK 1: Postopek nikoli ne neha teči, in res je sama ponovno poziva in znova in znova in znova in spet, in nobeden od te naloge doslej dokončati, ker njihov edini vrstici koda themself znova poziva in znova. In kaj je res dogaja tukaj in zdaj lahko nekako pripraviti to slikovno. Naj grem več na slika za trenutek. To je slika, ki bo sčasoma izpopolnili podrobneje, kaj se dogaja znotraj pomnilnika računalnika. In izkazalo se je, da je na dno te slike je nekaj, kar se imenuje sveženj. To je kos pomnilnika, kos RAM, to je samo uporablja kadarkoli Funkcija se imenuje. Vsak čas si, programer, pokličete funkcijo, operacijski sistem, kot Mac OS, Windows ali Linux, zagrabi kup bajtov, morda nekaj kilobajtov, morda nekaj megabajtov pomnilnika, ki jih roke za vas, in nato omogoča zaženete svojo funkcijo z ne glede na spremenljivke, kar potrebujete. In če potem pokličete drugo Funkcija in drugo funkcijo, boste dobili še en košček spomina in drugo rezino pomnilnika. 

In res, če teh zelenih pladnje od Annenberg predstavljajo tisti spomin, tukaj je, kaj se zgodi prvi Čas pokličete funkcijo sigma. To je kot dajanje pladenj takole o tem, kaj je na začetku prazna snop. Ampak potem če je pladenj se poziva, da se tako izrazim, kliče en primerek Sigma, ki je kot bi od operacijskega sistema, ooh, potrebujejo malo več pomnilnika, daj mi to. In potem postane to zloži na na vrhu. Toda kaj je ključ v tem, da Prvi pladenj je še vedno tam, ker je sklicevala na to drugo pladenj. Zdaj medtem, sigma pokličite sigma, , ki je, kot zahtevajo več pomnilnika. Gets nakopičena sem. sigma sigma klic, da je druga pladenj, ki dobi nakopičil tukaj. In če boste obdržali to delaš, na koncu, vrsta map ta vizualna v tem grafikonu, kaj se dogaja, da zgodi s skladovnice pladnjev? To se dogaja, da presega zneska pomnilnika ima računalnik. In takoj, ko je to zeleno pladenj nad vodoravno linijo zgoraj dimnika nad to besedo kup, kateri se bomo vrnili v prihodnosti, da je slaba stvar. Kup je drugačna segment pomnilnika, in če ste kaj ti pladnji pile in pile na, boš presega svoj segment pomnilnika, in program je dejansko šlo za nesrečo. 

Zdaj kot praha, to idejo rekurzijska, zato lahko nedvomno povzroči težave, vendar to ni nujno slaba stvar. Ker menijo, po Vse, kako-- in morda to traja nekaj pridobivanje vajeni da --how elegantno ali kako preprosta da izvajanje sigma je. In ne bomo uporabljati rekurzija vse, da je veliko v CS50, ampak v CS51, in res vsaka razred kje ste manipulirati podatkovne strukture kot so drevesa ali družinskih dreves, da imajo nekaj hierarhijo, to je super, super uporabna. Zdaj, kot prahi, da vas kot ambicioznimi računalniške znanstvenike so seznanjeni z nekaterimi od Googla znotraj šale, če greš na Google in pogledate, kaj je opredelitev, recimo, rekurzija, vnesite. Uh-huh. Naj omenim, da sem potegnil nekaj. To je kot 10 minut odlašanje danes zjutraj. Če vas tudi Google "poševno" obvestilo z nagibanjem glave slightly-- in potem ta je morda najbolj odvratne vseh ker je nekdo preživel kot njihov dan izvajanju tega nekaj let ago-- pridi. Oh, wait-- da je bug. 

Torej teče na enem Največje spletne strani svetu so ti neumni velikonočna jajca. Verjetno porabijo enostavna, število vrstic kode samo zato, da bomo lahko imeli malo zabavnih stvari, kot je ta. Ampak vsaj zdaj dobiš nekatere od teh znotraj šale. 

Zdaj pa si oglejte nekaj White Lies smo bili sporoči prepozno, in začnite lupiti nazaj nekateri sloji tehnično tako, da boste resnično razumeli Kaj se je dogajalo in boste razumeli nekaj groženj, kot Shellshock, da sedaj začeli postanejo na čelu vsakogar pozornosti, vsaj v medijih. Torej, tukaj je zelo preprosta funkcija da vrne nič, nična. Njeno ime je swap. To traja v dveh spremenljivk in se vrne ničesar. Traja v a in b. Torej hitra predstavitev. Te smo odraščali. Mi lahko traja tudi malo prekinil sem za trenutek in še nekaj malega za popit. Če nekdo ne bi motilo pridružil me tukaj samo za trenutek. Kaj pa ti v maroon majico? Pridi gor. Samo eno danes. Vseeno hvala. Vse v redu, in imamo Prihaja kdo tu? Kako ti je ime? 

SPEAKER 4: Laura. 

ZVOČNIK 1: Laura. Pridi gor. Torej Laura, zelo preprost izziv danes. Lepo, da yo spoznati. V redu. Torej imamo nekaj mleka sem in imamo nekaj pomarančnega soka tukaj in nekaj skodelic, ki smo danes sposodil od Annenberg. 

SPEAKER 4: Sposodil. ZVOČNIK 1: In šel naprej in vam pol kozarca to. V redu. In vam bom dal polovico kozarec mleka. Oh, in samo zato, da si lahko se spomnite, kaj je to bilo všeč, Spomnil sem se, da bi to gor in danes. Ok. Če ne bi motilo, da vidimo, smo jim lahko dal preko svojih očal če hočeš. To bo svet iz oči Laura. V redu. Torej je vaš cilj, saj dve skodelici tekočina tukaj, mleko in pomarančni sok, je zamenjal dve vsebine, tako da pomarančni sok, ki gre v skodelico mleka in mleko gre v skodelice pomarančnega soka. 

SPEAKER 4: Ali dobim še eno skodelico? ZVOČNIK 1: Vesela sem, da si vprašal, čeprav da bi bilo veliko bolje posnetki če ne bi vprašal. Ampak ja, vam lahko ponudimo tretja cup, ki je prazna, seveda. V redu. Torej zamenjali vsebino tam. Zelo lepo. Zelo dobro. Počneš to izredno previdno. In korak tri. V redu. Odlično. Velik aplavz bi bilo dobro za Lauro. V redu. Imamo malo poslovilno darilo za vas, vendar naj vzamem te. Najlepša hvala. Tako preprost primer, čeprav, dokazati, da če vam želijo, da bi zamenjali vsebino dveh posodah, ali pa jih pokličete spremenljivke, boste potrebovali nekaj začasnega skladiščenja na odru enega vsebine v tako da lahko dejansko narediti swap. Torej res, ta izvorna koda tukaj v C je predstavnik točno to. Če je bil pomarančni sok in mleko je b, in smo želeli, da bi zamenjali dva, Lahko poskusite nekaj ustvarjalnega z ležanjem ena v drugo, vendar to verjetno ne bi konča zlasti dobro. In tako smo uporabili tretji kozarec, klic je tmp, T-M-P po dogovoru in dal vsebino UL s tem, nato zamenjali eno skodelico, potem dal v UL originalni pokal, s čimer doseganje, točno tako, kot Laura storil, swap. 

Torej, kaj je naredil točno to. Dovolite mi, da gredo naprej in odprite up primer, ki je pravzaprav imenuje "no swap ", ker to ni kot enostavno narediti, kot si morda mislite. Torej, v tem programu, opazili, da Jaz sem z uporabo stdio.h, naš stari prijatelj. Imam prototip za swap tam gor, ki pomeni njegovo izvajanje je verjetno dol, in da vidimo, kaj je to glavni Program bo storil zame. Najprej sem razglasila int x dobi ena, in int y dobi dva. Torej, mislim tiste kot UL in mleko, oz. In potem sem samo še printf rekel x je to in y, je to samo zato, da sem lahko vizualno videli, kaj se dogaja. Potem sem printf trdijo da sem zamenjavo dveh, in potem sem izpisal trdijo, da si zamenjal, in sem spet izpisal x in y. Torej, tukaj v swap je točno tisto, Laura storil, in točno to, kar smo videli na zaslon pred nekaj trenutki. 

Torej, gremo naprej in biti boleče razočaran. Da ne bo zamenjave, in zagnati nobene zamenjave, povečanjem proizvodnje tukaj. Vnesite x 1, y 2, zamenjavam zamenjala. x je vedno 1, in y je vedno 2. Torej, čeprav, odkrito povedano, to izgleda ravno všeč, čeprav bolj tehnično, kaj Laura storil, ni videti, da deluje. Torej, zakaj je to? No, izkazalo se je, da se pri smo napisali program, kot je to da se je tako glavni, poudaril sem, in nato drugo funkcijo, kot zamenjave, poudarjeno tukaj, ki Zato poziva, svet Izgleda malo nekaj podobnega Ti pladnji trenutek nazaj. Ko glavni prvi dobi imenuje, To je, kot bi od operacijskega sistema za malo pomnilnika za vsak lokalni spremenljivke, kot sta x in y, ki ima glavno, in končajo tam. Ampak, če je glavna zahteva zamenjali, in glavni mine, da bi zamenjali dva argumenta, A in B, pomarančni sok in mleko, to ni všeč odnesete pomarančni sok in mleko z Lauro. Kaj računalnik počne, je to, prehaja kopije pomarančnega soka in kopije mleka Laura, tako da kar je v končni fazi v notranjosti tega pladnja je ena vrednost in dva ali UL in njihovi mleko, ampak kopije, tako da na tej točki v zgodbi, pa je UL in mleko v vsakem od teh pladnjev. Obstaja ena in dva V vsaki od teh pladnjev, in funkcija swap je res deluje. To je njihovo zamenjavo znotraj v drugem najvišjem predalu, ampak da je zamenjevanje nima vpliva. In na podlagi le nekaj Osnovno načelo, ki smo jih že prej govorili, in dejansko le nekaj minut nazaj, kaj lahko pojasni, zakaj spreminjanje in b notranjosti zamenjave nima vpliva na x in y, čeprav Opravil sem X in Y s funkcijo zamenjave. Kaj je ključna beseda pri tem, da Morda poenostavljeno razložiti? Mislim, da sem ga slišal sem? OBČINSTVO: Return. ZVOČNIK 1: Vrnitev? Ne vrne. Pojdimo z eno drugo. Kaj je to? 

OBČINSTVO: [neslišno]. 

ZVOČNIK 1: OK, tako da smo lahko return-- da povratno delo v zgodbi, vendar pa še enostavnejša razlaga. OBČINSTVO: Področje. ZVOČNIK 1: Področje uporabe. Bom obseg. Torej področje, se spomnite, kjer naš x in y razglašena. Oni so razglašena v notranjosti za glavni tukaj gor. a in b, medtem, so dejansko razglasila notranjost zamenjave, ni čisto v Zaviti oklepaji, vendar še vedno V splošnem področju zamenjave. In res, in b obstajajo le v tem predalu iz Annenberg, to Drugi kos kode. Tako da smo res spreminja kopijo, vendar to ni res vse, da pomaga. 

Torej si oglejte to malo nižje ravni. Jaz grem nazaj v Source Directory, in bom najprej povečate tukaj, in samo Za potrditev, da sem v tem Večje okno terminala, Program se še vedno obnašajo, kot da je. Recimo, da zdaj, ko je to ni namerna. Jasno sem si želel zamenjave za dela, tako da se počuti kot hrošča. Zdaj lahko začnete z dodajanjem Veliko printf, da mojo kodo, tiskanje x tukaj, y nad tukaj, tukaj, b tukaj. Vendar odkrito povedano, to je verjetno kaj ste delali za nekaj tednov Zdaj, v uradnih urah in doma pri delu na psets poskušajo najti nekaj hroščev. Ampak boste videli, če tega še niste storili, da je problem določiti tri vam predstavi na ukaz imenovano GDB, kjer GDB, GNU razhroščevalnik, si je cel kup funkcije, ki lahko dejansko nam razumeti situacije kot je ta, ampak bolj očarljivo, reševanju problemov in iskanju hroščev. Zato bom to naredil. Namesto da ./noswap, sem namesto tekoč teči GDB ./noswap. Z drugimi besedami, grem teči moj Program ne Bash, naš novi prijatelj danes. Jaz grem teči moj Program noswap notranjosti tega drugega programa, imenovanega GDB, ki je iskalnik napak, ki je program, ki je zasnovan tako, da pomaga ste se pri ljudeh najti in odstraniti hroščev. Torej, če sem udaril Run tukaj, tam je odvratne količino besedila da res ne bo treba brati. To je v bistvu moteča na poziv, ki Bom udaril Control-L vstati na vrhu tam. To je GDB poziv. Če želim zagnati ta program zdaj, kot je to malo goljufija stanja na današnji slide kaže, Run je prva ukaze, ki smo mislili, da uvedejo. In jaz bom samo, da tip teči tu notranjosti GDB, in res je tekel svoj program. Zdaj je na voljo nekaj dodatnih izhodov zaslona, ​​kot je ta, ampak to je GDB le da analni in nam povedal, kaj se dogaja. Saj ni res treba skrbeti o teh podrobnosti. Ampak kaj je res kul GDB, če naredim to again-- Control-L počisti screen-- pusti me naprej in tip "prekinil glavno," s tem, ko sem pritisnite tipko Enter, ki določa, kaj je imenuje prelomna točka pri noswap.c, linija 16, ki je, če GDB pogruntal moj program dejansko je moja funkcija dejansko je. To bomo prezreti za zdaj ampak to je naslov v spomin posebej to funkcijo. Torej, zdaj, ko sem teči s tipom, opazili, kaj je kul tukaj. Moj program razbije v vrstici I povedal GDB za pavzo usmrtitev na. Tako da mi ne bi bilo treba zdaj spremeniti svojo kodo, dodati nekaj printf-jev, ga prevesti, ponovitev ga spremenite, dodate nekaj printf-jev, ga shranite, jo prevedem, ga zaženite. Jaz lahko samo sprehod skozi mojega programa korak po korak za korakom na človeško hitrostjo, ne na Intel-znotraj vrste hitrosti. 

Torej sedaj opazil to linijo Tu se pojavi, in če grem nazaj na moj program v gedit, opazili, da je to dejansko Zelo prvi vrstici kode. Tam je linija 16 v gedit. Tam je postavka 16 v GDB in celo čeprav je ta črno-beli vmesnik še zdaleč ni tako uporabnika prijazen, to pomeni da linija 16 še ni bil izvršen še ni, vendar je na tem, da bo. Torej res, če sem tip print x, ne printf, le print x, Dobim lažne vrednost je nič, ker x še ni bila inicializirana. Tako da bom naslednji tip, ali pa, če vas želijo biti fancy, samo N za dostavo. Toda, ko sem s tipom naslednji vstop, zdaj opazite, da se preseli na liniji 17. Torej je logično, če sem usmrčen linija 16 in sem zdaj tip tiskanja x, kaj naj jaz vidim? One. 

In zdaj je to res zmedeno. $ 2 samo fancy način, če vas želite sklicevati na to vrednost kasneje, lahko rečeš "dolar podpiše dva." To je kot referenco nazaj. Ampak za zdaj, le ignorirajo. Zanimivo je to, kar je na desni strani enačaja. In zdaj, če sem tip zraven še enkrat in tiskanje y, moram videti 2. Jaz lahko zdaj tudi natisnete x še enkrat, in odkrito povedano, če sem že malo zmeden, kje sem, sem lahko vnesete seznam za seznam in sem videl samo nekaj konteksta okrog točka, da sem dejansko na. In zdaj sem lahko vnesete Naslednji, in tam je x 1. Zdaj sem tip zraven. Oh, y 2. In spet, da je zmedeno, ker proizvodnja GDB je se pomešati s svojo močjo. Ampak, če si v mislih, ki jih Že pogled nazaj in naprej po kodi ali o iz strani s strani morda boste vidim, da res sem samo odskočna preko mojega programa. 

Ampak obvestilo, kaj se bo zgodilo, dobesedno. Tukaj je linija 22. Naj grem po njem, s čimer se gibljejo na do 23, in če sem natisniti x zdaj, še ena. In če sem natisniti y zdaj, še ena. Torej to ni koristno vaja. Torej, kaj je to ponoviti. Naj grem nazaj do spet top in vrsta rok. In to govori program da se je debugged se je že začelo, začel od začetka. Ja, dajmo to storiti še enkrat. In tokrat naredimo naslednji, naslednji, naslednji, naslednji, naslednji, zdaj pa stvari postanejo zanimive. Sedaj želim stopiti v swap, tako da jaz ne tip zraven. Sem tip korak, zdaj ga opazili me je skočil na noswap.c linijo 33. Če grem nazaj v gedit, kaj je linija 33? To je prvi dejanski vrstica kode znotraj zamenjave. Kar je lepo, ker zdaj ne morem nekako suniti okrog in dobili radovedni o tem, kaj se dogaja zares tam. Dovolite mi, da natisnete tmp. Vau. Zakaj tmp imajo nekateri noro, lažne smeti vrednost? OBČINSTVO: To ni bil inicializiran. ZVOČNIK 1: To ni bil inicializiran. In res, ko zaženete program, ste dali cel kup pomnilnika z operacijskim sistemom, vendar si ni inicializirana nobenih vrednosti, tako da karkoli bits ste vidim tukaj, čeprav je to noro velik negativen številka, pomeni le, da so to ostanki iz nekatere prejšnje uporabe tega RAM-a, čeprav nisem Sam ga še potrebno. Torej, zdaj bom, da gredo naprej in tip naslednji, in če jaz zdaj tip tiskanja tmp, kaj naj jaz vidim? Zaradi je vrednost, je prvi argument, samo kot x je prva stvar, ki se prenesejo v, tako, x mora biti enaka, zato je treba natisniti tmp mi natisnete eno. 

Torej, kaj boste videli na problem niz tri je tutorial z menoj na GDB, vendar je spoznala, da je to začetek z pogledom na orodje, ki bo dejansko vam pomagajo rešiti težave toliko bolj učinkovito. Kaj bomo na koncu storili v sredo je začela lupiti nazaj nekaj plasti in odstranite nekaj koles usposabljanja. Ta stvar se imenuje niz, ki smo nekaj časa uporabljali, bomo počasi vzeti od vas in začeli govoriti o nekaj več ezoterično znan kot char *, vendar bomo storili to lepo in sprva počasi, čeprav kazalci, kot oni poklical, lahko storite nekaj Zelo slabe stvari, če zlorabljene jih gledaš malo claymation od naš prijatelj Nick Parlante iz Stanforda University, profesor na računalniku znanost, ki skupaj predogleda o tem, kaj je, da pridejo na to sreda. 

[VIDEO PREDVAJANJE] Hej, Binky. Zbudi. To je čas za zabavo kazalca. 

Kaj je to? Spoznajte kazalci? Oh, Goody! [END VIDEO PREDVAJANJE] ZVOČNIK 1: To vas čaka v sredo. Se vidimo potem. [VIDEO PREDVAJANJE] In zdaj, Deep Thoughts, z Daven Farnham. 

Zakaj se učimo C? Zakaj pa ne +? 

[Smeh] 

[END VIDEO PREDVAJANJE]