[Muziciranja] Zvučnik 1: U redu, ovo je CS50, i to je početak četiri tjedna, i kao što ste možda čuli ili pročitati, svijet je završio. Ide sve oko interneta ima bio znanja i svijesti buga u program, programski jezik zove bash. To je čudesno je označen kao što je potres mozga, ili Bash vrata, ali članci poput ovih nisu bili rijetkost. A u stvari, mnogi od njih donijeti sjećanja na Heartbleed, što ste možda primijetili u pritisnite vratio prošlog proljeća, koje bio sličan prilično dramatična. Sada od one od vas ovdje Danas, koliko vas ima, čak i ako ne razumiju što to je sve o, čuli za potres mozga? U redu, i koliko vas je imaju računala koja su ranjiva? U redu, ne bi trebalo biti daleko, daleko više ruku do sada, iz razloga što ćemo vidjeti. Uzmimo pogled na ono što je traje u medijima a zatim objasniti malo Ovdje nam je tehnički. ZVUČNIK 2: Sigurnosni stručnjaci imaju upozorio da je ozbiljan propust može biti oko utjecati na stotine milijuni svjetskih korisnika weba. Dakle, točno ono što je bug koji je bio nazvan potres mozga, a što učiniti? Dakle, kontuzija također poznat kao Bash bug, softver se iskorištava. Hakeri koriste virus skeniranje ranjiva Sustavi za trčanje Linux i Unix operacijskim sustavima, a zatim ih zaraziti. Bash je ljuska naredbenog retka. To omogućuje korisnicima pitanje naredbe za pokretanje programi i značajke unutar softvera upisivanjem u tekstu. To obično se koristi od strane programera, a Ne bi trebao biti otvoren za širu svijetu, iako je potres mozga mijenja to. Pa, worringly, neki analitičari upozoravaju da bi mogla biti veća prijetnja, zbog kontuzija omogućuje potpuni kontrolu nad zaraženim računalima, dok Heartbleed dopušteno samo hakeri da izvidi na računalima. To je tako ozbiljna, da je ocijenjeno je 10 od 10 za ozbiljnost od strane Nacionalnog Ranjivost baze. 2/3 svih web poslužitelja su na rizik, uključujući i neke Mac računala. Pa, pobrinite se da krpa svoje sustave sada. Svatko hosting web stranice trčanje pogođenim operacijski sustavi treba poduzeti što je prije moguće. Svatko tko može priuštiti to treba izgledati za njihovo praćenje i web aplikacija firewall paziti na bilo napada. Zvučnik 3: Najgora stvar da bi se moglo dogoditi je da bi netko napisati kod koji će automatski otići i skeniranje Internet i da će utjecati na svim tim računalima. I kad su to učiniti, dobro, Najgore što se može učiniti je samo izbrisati sve, ili zatvorio web stranice prema dolje. Tako smo mogli vidjeti štetu od te točke gledišta, gdje bi Zlobnici koji je upravo odluče izazvati pustoš dovođenjem sustava dolje ili brisanje datoteke, i takve stvari. ZVUČNIK 2: Neki kažu da je ovo jedan od najtežih za mjerenje bube u godinama, i to može potrajati tjednima ili čak mjeseci kako bi se utvrdilo konačan učinak. Zvučnik 1: Dakle, sve je to istina, ali smiješno je, gotovo sve od slika koje ste upravo vidjeli, osim možda na tipkovnici, nema nikakve veze s Bug god. Serveri i žice i tako dalje, To je vrsta tangencijalno povezano, ali u srži je zapravo prilično upoznati ono što se ovdje događa. U stvari, pustite me u Naš CS50 aparata. Dopustite mi ići naprijed i povećali Terminal prozor ovdje. A ti dečki su pomoću toga, ili ugrađen verziju istog, u gedit kako pisati programe, upišite naredbe, i tako dalje, , a to je zapravo, i ima bio tjednima, Bash, B-A-S-H. To je Bourne-opet ljuska, koji je samo fancy način govoreći, To je program koji ima treperi brz, učinkovit, koji sjedi tamo čeka za ulaz za vas. I to je naredba linija sučelje preko kojega ti dečki su trčanje naredbe i konačnici sastavljanje i onda trčanje programi. No, bash je i programiranje jezik u sljedećem smislu. Vi znate da postoje naredbe poput CD i LS i zveket i drugi, ali možete definirati svoje vlastite naredbe tako da ih provodi u Bash. Sada mi ne idemo u ići u pojedinosti kao da Bash programski jezik, ali Znam, primjerice, da je u ovom trenutku, ne postoji naredba zove "Zdravo." Dakle, može se naći u jedan od ovih paketa. To nije instaliran na mom računalu. Pitajte administratora. No, ako želim da postoji program pod nazivom "Hello" u Bash ili na moj redak Ja zapravo mogu koristiti sintaksu da je kao što je prilično C. To nije sasvim isti, ali to izgleda prilično slično funkcija, iako nedostaju neke pojedinosti. Ništa se čini da se dogodi, ali sada, ako sam tip "Hello" zapravo možete pisati Program, a ne u C, a ne u Javi, ne u nekom drugom programu jezik, ali u Bash sama. Sada ključ ovdje je da sam pisao imenovati Htio sam dati ovu novu naredbu, a zagrade su također simboliku jer je to funkcija. Kao na stranu, također možete napraviti zabavu stvari, i zapravo, čak i na Mac OS, To je program koji se zove terminal. Ona dolazi s ugrađenim u bilo tko je računalo koje ima Mac u ovoj sobi, , a možete napraviti slične stvari u Mac OS, ali možete ići još dalje od toga. A to je malo tangencijalno, ali to je neka vrsta zabave. Toga sam se sjetio jutros, kada razmišljam o ovome, od malo igra sam se igrala s jednim od CS50 bivših TFS pri čemu svaki put kad bi otići od njegova tipkovnica s njegovom ekranu otključana, Ja bih izvršiti naredbu kao ovo-- "pozdraviti". I sada svaki put kad bi se vratio na njegov tipkovnice nakon što sam očistio ekran i on će sjesti, pokušati napraviti neki posao, popis sadržaj svojoj directory-- [Audio reprodukcije] Halo. Pozdrav. Zvučnik 1: Dakle, u pravednosti, to zapravo nije "zdravo". To je obično nešto više srodan to-- [Audio reprodukcije] -Beep. Zvučnik 1: --that sam would-- tako da bi njegovo računalo Kunem se u njega u bilo koje vrijeme je on zapravo sjeo za tipkovnicu. I vrlo brzo je shvatio Ne napustiti njegov zaslon otključan. No, to ukazuje na neku vrstu glupo zabave koja vas Možete imati nešto poput Bash. Ali to je malo više ozbiljno, kako bi bili sigurni, od toga. A u stvari, to je jedan od najopasniji i dugotrajan bugova da stvarno je hit u svijetu na globalnoj razini. Ovaj bug je oko za 20-ak godina a vi ćete biti pogođen u samo Trenutak po relativne jednostavnosti. Dakle, to je predstavnik zapovijedam da ako vas posjedujete Mac, doslovno odmah kada imate svoj poklopac otvoren, možete pokušati upisivanjem u to Program se zove terminal. Terminal je pod Prijave Utilities-- jednom, Windows korisnici ne moraju brinuti o ovom konkretnom threat-- ali one od vas s Macove možete upisati ovo u prozor kao da ću napraviti ovdje, i ako ne upišete da se u tom programu zove terminal, kao što ću učiniti sada, ako vidite riječ "ranjiva", računalo ranjivi. Sada, što to zapravo znači? A to je, doduše, neki prilično ludo sintakse, ali neka je barem izvući neke od zanimljivih aspekata. Dakle, postoji neki sintaksa koja izgleda Malo poznati, barem iz C i programiranja općenito. Vidim neke zagrade, zarezom, kovrčava aparatića, i kao što, ali ispada da je ova glupa stvar ovdje u žutom u biti funkciju da ne radi ništa. Debelog crijeva znači ne raditi ništa, a zarez znači prestati raditi ništa. Dakle, unutar tih vitičastim zagradama, činjenica da imam jednaka prijavite se lijevo, to je u biti stvaranje naredbe, ili promjenjiva, zove x, i to dodjeljivanje da je žuta malo koda postoji. To bi moglo biti nešto poput "jeke Halo "ili" kažu piskutavi "ili tako nešto slično tome. No primijetite li svojim očima lutati dalje na desno, ima još na toj liniji od samo kraj tog zarezom. "Echo ranjiva", a zatim izvan toga postoji još više. Još jedan zarez, bash -c :. Dakle, ne duljimo, Ova linija koda dovoljno za uvjerljiv Računalo koje je ranjiva na radiš nešto da li želite to učiniti, jer postoji bug u Bash pri čemu iako bash je trebao zaustaviti čitanje linijom zapovijedanja prava tamo nakon žutog teksta, za 20-plus godina star bug, Bash je zapravo bio čitanje Iznad toga zarezom i prilično koliko radiš ono što je rekla. Dakle, što je implikacija od toga u konačnici? Samo sam rekao "odjek Hello" ili "echo ranjiva" No, što ako ste učinili nešto zapravo zlonamjerni, kao što su rm-rf *, koje možda nećete ikada upisali prije, i iskreno vjerojatno ne treba prerano, jer možete napraviti Puno štete s njom. Zašto? RM što radi, naravno? Uklanja. * Znači što? Sve. Dakle, to je tzv wild card, tako da to znači izbrisati sve što je u trenutna imenik. r se događa da znači rekurzivna, što znači ako je ono što brisanja je katalog, i iznutra postoji je druga slika i druge direktorije, rekurzivno zaroniti u tu i izbrisati sve to. I f je najgora od svih. Zna li itko što znači f ovdje? Sila. Dakle prisiliti sredstva, čak i ako je to loša ideja, to učiniti bez mene pitajući za daljnju potvrdu. Pa, znate, mi se smijati to, ali iskreno, ja vjerojatno upišite ovaj više puta dan, jer je stvarnost je da je najbrži način da se izbrisali hrpu stvari. No, čak sam učinio neke štete. Ali, ako ste bili na trik računala u definiranju neke glupe varijablu ili funkcija zove x, ali onda tjeranjem računalo u izvršavanju izvan granica koje funkcija, iza tog zarezom, vi doista mogao izigrati računalo u izvršavanju nešto kao rm-rf ili e-naredba ili Kopiraj naredbe. Sve doslovce možete učiniti s računalo, bilo da je brisanje datoteka, kreiranje datoteke, spam nekoga, napadaju neki server na daljinu, ako ga može izraziti s naredbom, što može izigrati računalo na taj događaj. Sad, što je primjer kako ste mogli to učiniti? Pa, ima puno računala na Internetu trčanje Bash. Svi od nas korisnike Mac računala su među njima. Puno Linux poslužitelja su među ih, kao i Unix poslužitelja. Prozori opet dobiva Relativno izvući iz nevolje osim ako ste instalirali poseban softver. Sada puno poslužitelja, za instanca, izvode web poslužitelji, i zapravo Linux je možda najpopularniji operativni sustav za rad na računalima na internetu koji su služeći se web stranice. Sada kao što ćemo kasnije vidjeti u semestru, kada šaljete zahtjev Vaš browser-- Chrome, Internet Explorer, whatever-- na udaljenom poslužitelju, ispada da iako ste upravo upisali www.example.com, Vaš preglednik šalje poruku to je malo više kompliciranih, kao što je ovaj. Ali primijetiti malo nešto čudno. Prve dvije linije Nikad prije nisam vidio, ali oni ne izgledaju Posebno opasne. Ali primijetiti ono što sam ukrao za treću liniju ovdje. Ako negativac su poslati poruku kao što je ovaj iz svog računala ranjivoj Mac ili ranjiva Linux poslužitelj, Smiješno je da bash, tako jednostavno malo naredbenog retka, je sveprisutan i često je naviknuti na osnovi izvršiti Sadržaj Poruka koja se prima. I po toj logici, možete trik web poslužitelj, dakle, slanjem nešto slično Korisnički agent, koji se obično je trebao reći naziv web pregledniku. Korisnički agent Chrome, User-agent internetu Explorer, User-agent Firefox, ovo je samo vaš preglednik a način poistovjećujući. Ali ako negativac vrlo pametno kaže, mm-mm, ja sam Ne ide ti reći ono što je moj preglednik, Ja sam umjesto toga će vam poslati ovo zagonetna izgleda stvar s rm-rf * U njemu, možete doslovno trik ranjivi web poslužitelj na internetu u izvršavanju točno da je u tu za brisanje svih datoteka. I iskreno, to nije čak i najgore od njega. To možete učiniti ništa. Ti bi mogao početi distribuirati denial of service napada ako je poslao ovu poruku cijeli trsovi web poslužitelja a zatim ih je sve spustiti, za primjer, na Harvard.edu poslužiteljima, , a možete sortirati od prasak pakao iz njih strane mrežnog prometa koji je bio inače pokreću ove negativca. Dakle, ne duljimo, gotovo svatko u ovoj sobi koji posjeduje Mac je osjetljiva na to. Srebro podstava je da ako nisi pokrenut web poslužitelj na prijenosnom računalu, i ako ste zapravo konfiguriran to dopustiti nešto poput SSH u nju, ti si zapravo sigurna. To je ranjiva, ali nema jedan težak da biste dobili u svoj laptop, tako da možete na neki način biti sigurni. Međutim, Apple će uskoro biti ažuriranje popraviti za to. Svijet Linux je već pušten broj grešaka za Fedora i Ubuntu i druge verzije Linux, i doista ako naiđete ažuriranje 50 u aparatu, čak i da previše će biti obnovljeno i ispraviti. No, da previše nije Stvarno je ranjiva, jer ako ste tinkered s aparatom i napravio svoj laptop javno dostupni na internetu, što nije po defaultu, ste zapravo bilo u redu, jer od firewall i drugim tehnikama. No, to je ekstremni primjer bug da smo živjeli za doslovno 20 godine, a tko zna, ako je netko sve ovo vrijeme nije znao o tome? A u stvari, to je jedan od temeljni izazovi kako ćemo vidjeti kasnije u semestar o sigurnosti, je, baš kao u stvarnom svijetu, dobri dečki su u nepovoljnom položaju. Da bi negativci van, moramo pobrinite se da svaka vrata zaključana, da je svaki prozor je siguran, da svaka točka ulaska u dom je siguran da bi negativci van. No, što se negativac moraju učiniti da se zapravo kompromis svoj dom i kradu od vas? On ili ona jednostavno mora naći jedan otključan vrata, jedan razbijeni prozor, ili tako nešto u tom smjeru, a to je Ista stvar u računalnoj sigurnosti. Možemo pisati milijune linija programskog koda i potrošiti stotine ili tisuće sati pokušavaju dobiti to ispraviti, ali ako bi samo jedan pogreška u ispravnost, možete staviti cijeli sustav i Doista, u ovom slučaju, cijeli internet i svijet u opasnosti. Dakle, ako želite saznati više o tome, ići na ovaj URL ovdje. Nema potrebe za akciju Večeras, osim ako ste među onima ugodnije da su pokretanje vlastitog weba poslužitelja, u kojem slučaju bi trebali, u stvari, ažurirajte softver. I ovo je naslov govor, a sada papira, da smo povezani na Naravno stranice je za danas. To je za momka zove Ken Thompson, koji je je prihvaćanje vrlo poznati Nagrada u računalnoj znanosti, i on je dao ovaj govor nekoliko godina Prije, u biti na ovoj istoj temi. Pitajući ljudi pitanje, trebali ste stvarno povjerenja, u konačnici, Softver koji ste dobili? Na primjer, svi mi imamo pisanje programa, a mi smo bili sastavljanja ih s jeka. I na svom znanju, što ste napisali svi programi za CS50 gdje postoji stražnja vrata sorti, postoji način da je loš čovjek, ako se izvodi svoj program, mogla preuzeti svoje računalo? Vjerojatno ne, zar ne? Mario, i pohlepni, i Credit. Sve su to prilično mali programi. Morao bi biti prilično loše ako vas zapravo je cijelo računalo ranjivim Nakon pisanja 10 ili 20 linija koda, ili barem svjesni nekih sigurnosnih implikacija. Sada sam reći da u šali, ali ćemo vidjeti danas a ovaj tjedan je zapravo jako, jako jednostavno kako bi bilo loše i napraviti još kratki programi ranjivi. Ali za sada, barem, shvatite da je pitanje pitao ovdje je oko jeka u prevodilac. Zašto smo bili vjerujući Zveket za posljednje dvije ili tri tjedna? Tko kaže da onaj tko je napisao Zveket nisu imali "ako" stanje u tu da je u biti ubrizgava neke nule i one u svakom programu se sastavlja da bi neka ili njezin pristup vaše računalo kada ste spavali i vaš laptop poklopac otvoren i vaše računalo radi? Zar ne? Imamo ovu vrstu prava čast sustava Sada, gdje vjerujemo da Zveket je čitljiv. Vi vjerujete da je aparat čitljiv. Vi vjerujete da je doslovno svaki program na vašem Mac ili PC je pouzdan. I kao što je ova jednostavna bug sugerira, čak i ako to nije zlonamjerno, to je apsolutno ne vjerojatno da će biti slučaj. Tako da bi trebao biti uplašen kao pakao. Iskreno, ne postoji jednostavan rješenje za taj drugi nego neka vrsta društvene svijesti sve veće složenosti da smo zgrada na vrhu od naših računalnih sustava, i kako sve više ranjiva možemo biti jako dobro. Sada s tim, rekao je, bijeg. Dakle, bijeg je problema postaviti tri, a Bijeg je igra od prošle da biste mogli sjetiti, ali za nas u problemu postaviti tri, što nam omogućuje da se stvari vratiti na višu razinu tako da kad smo pisanje programa, čak iu prozor terminala kao što je ovaj, mi zapravo može raditi, u konačnici, grafički programi ne za razliku od onih koje smo imali pristup u nule. Dakle, ovo je osoblja Provedba bijeg, što je upravo to cigla-razbijanje igra, da li premjestiti svoje veslo natrag i naprijed, a vi udariti loptu protiv onih boje cigle do vrha. Dakle, ovo je nas dovodi vrsta natrag do mjesta gdje bili smo u mogućnosti da se vrlo brzo s nule, a sada sa C, provedbu vlastitih grafičko korisničko sučelje. No, više od toga, to Problem skup prvi u kojima dajemo vi hrpa koda. A u stvari, sam donijeti eksplicitno pozornost na to, jer je posebno za one manje udobno, ovo Problem postaviti, barem na prvi pogled, će se osjećati kao mi smo ga uzeti gore zarezati. Zato smo vam dao, za neke pretraživanja i sortiranje probleme u pset, hrpa koda koji smo pisali, i par komentara da kažu "učiniti" u kojoj morate ispuniti praznine. Dakle, ne previše zastrašujuće, ali to je prvi put mi smo ti predaje kod koji trebate Prvi čitati, razumjeti, a zatim dodati i završiti ga. I onda sa bijeg, ćemo učiniti isto, dajući vam nekoliko desetaka više linija koda koji, iskreno rečeno, daju ti Puno okvira za igra, ali stajemo provedbenih cigle i loptu i veslo, ali mi provesti neke druge značajke. A čak i da je na prvi pogled, opet, pogotovo ako je manje ugodno, može činiti osobito zastrašujuće i misliš da ima mnogo novih funkcija morate wrap your mind okolo, i to je istina. No, imajte na umu, da je prilično poput nule. Izgledi su da ne koriste sve slagalice u nule. Tečajevi su vam nije stalo da zamotate vaš um oko svih njih jer sve što je bilo Brzi pogled shvatiti, oh, to je ono što ja mogu učiniti s tim puzzle komad. I doista, u problemu postaviti 3 spec, mi ćemo vas uputiti na dokumentaciji koja će Vas upoznati s nekim novim funkcijama, i na kraju programiranje konstruira koristite. Uvjeti, petlje, varijable i funkcije biti jednake ono što smo do sada vidjeli. Pa zaista, ono što ćemo dati što je neki uzorak koda koji Omogućuje stvaranje prozora da ne gleda razliku od toga, i na kraju se to pretvorilo u nešto sasvim kao što je ovaj. Dakle iskoristiti CS50, raspravljati radno vrijeme i više, i uzeti utjehu u činjenici da količina koda morate pisati zapravo nije sve toliko. Prvi izazov je samo da se vrati sebi da nekog koda smo pismeni. Bilo kakva pitanja o pset3, Potres mozga, ili na neki drugi način? PUBLIKA: Činilo se kao ide kroz s bijeg da je kod gotovo objektno-orijentirani stil, ali mislio sam C je objektno-orijentirane programa. Zvučnik 1: izvrsno pitanje. Tako je u potrazi kroz distribucija broj, broj smo napisali za pset3, za one koji poznaju, to Izgleda kao da je Malo objektno-orijentirane. Kratak odgovor je, to je. To je aproksimacija kako ste moglo učiniti objektno-orijentirane kod pomoću jezik poput C, ali je Još uvijek u konačnici proceduralne. Ne postoje metode unutrašnjost varijable, kao što ćete vidjeti. No to podsjeća na to. I vidjet ćemo taj lik opet kad dođemo na PHP i JavaScript prema kraju semestra. Ali za sada, mislim da je to što je nagovještaj onoga što će doći. Dobro pitanje. U redu. Dakle spajaju svojevrsni je kako smo lijevi stvari zadnji put. I spajanje svojevrsni je cool u Osjećaj da je toliko brži, barem na temelju povrsan testovima smo učinili prošli tjedan, nego, recimo, mjehura sortiranje, odabir sortirati, umetanje vrst. A što je bio uredan previše je samo Kako jezgrovito i čisto možete ga izraziti. A ono što smo rekli da je gornja vezan na trčanje vrijeme spajanja sortirati? Da? PUBLIKA: n log n? Zvučnik 1: n log n, zar ne. n log n. A mi ćemo se vratiti na ono što zapravo znači i gdje da dolazi, ali ovo je bio bolji od onoga vremena rada kako smo vidjeli za mjehur odabir i umetanje neka vrsta? Dakle, n kvadrat. n na kvadrat je veći od toga, pa čak i ako to nije sasvim očito, Znam da je dnevnik je n manji od n, pa ako ne n puta nešto manji od n, to će biti manji od n na kvadrat. To je malo intuicije postoji. No platili smo cijenu za to. To je bio brži, ali tema koje je započeo rađati prošlog tjedna bio je to tradeoff. Dobio sam bolju izvedbu Vrijeme mudar, ali ono što nisam ja moram potrošiti na druge ruka, kako to postići? PUBLIKA: memorije. Zvučnik 1: Molim? PUBLIKA: memorije. Zvučnik 1: Memorija, ili prostor općenito. I to ne bilo super Očito s našim ljudima, ali podsjećaju da naši volonteri su iskoraku i intenziviranju natrag kao da postoji niz ovdje, i kao da postoji Drugi niz se ovdje su mogli koristiti, jer mi Potrebna negdje spojiti te ljude. Nismo mogli samo ih zamijeniti na mjestu. Dakle, spajanje sortiranja poluge više prostora, što nismo trebali s drugih algoritama, ali naopako je da je puno brže. I iskreno, u stvarnom svijetu prostoru to days-- RAM-a, tvrdi disk space-- je relativno jeftino, a da je nije nužno loša stvar. Tako ćemo uzeti brzi pogled, malo više sustavno, na ono što smo učinili i zašto mi je rekao da je n log n. Dakle, ovdje su osam brojeva i Osam volonteri imali smo zadnji put. A prva stvar koja Spoji Sortiranje nam je rekao da to bilo što? PUBLIKA: Podijeliti na dva dijela. Zvučnik 1: Molim? PUBLIKA: Podijeliti na dva dijela. Zvučnik 1: Podijeliti na dva dijela, u pravu. To je vrlo podsjeća telefonski imenik, od podjele i osvojiti više općenito. Tako smo gledali na lijevoj polovici. I onda kada smo rekli, neka vrsta lijeva polovica elemenata, Što smo naprijed rekli? Sortirati lijevu polovicu lijevo pola, što nam je omogućilo da se, nakon podjele na dva dijela, usredotočiti na četiri i dva. Kako sortirati popis sada, u žuta, veličine dva, pomoću Spoji Sortiraj? Pa ga podijelite na dva dijela, i sortiranje lijevu polovicu. I to je bilo mjesto gdje se stvari dobio malo glupo kratko. Kako sortirati popis koji je od jedna veličina, kao što je ovaj broj četiri ovdje? To je riješeno. Ti si učinio. Ali kako onda ste sortirati popis Veličina jedan kada je broj dva? Pa, ista stvar, ali sada ono što je bio treći i ključan korak u Merge Sortiraj? Imali ste spojiti lijevu pola i desna polovica. A kad smo to učinili, mi izgledao u četiri sata, gledali smo dva. Odlučili smo sve u redu, Očito dva na prvom mjestu, pa smo stavili dva u mjesto, a slijede četiri. A sada morate vrsta unatrag, i to je neka vrsta obilježje algoritma poput pisma Sortiranje, natrag u memoriju. Koji je sljedeći redak ove priče? Što bih trebao biti usredotočen na sljedeće? Pravo polovica lijevo pola, što je šest i osam. Pa neka mi samo korak kroz ovo bez belaboring točku previše. Šest i osam, a zatim je šest razvrstani, osam sortira. Spoji ih zajedno kao što je to, i sad sljedeći veliki korak je, naravno, sortiranje desnu polovicu od Prvi korak ovog algoritma. Tako ćemo se usredotočiti na jedan, tri, sedam, pet. Tada smo se fokusirati na lijevoj polovici. Lijeva polovica da, u pravu polovica da, a zatim spojiti u jedan i tri. Zatim pravo na pola, a zatim napustio pola nje, a zatim pravo na pola od toga. Spoji ga na, i što sad korak dalje? Spoji veliki lijevu polovicu i velika Pravo na pola, pa se ide dolje, zatim dva, zatim tri, pa četiri, a zatim pet, a zatim šest, zatim sedam, zatim osam. Tako sada zašto je to u konačnici otkriva, pogotovo ako n i logaritmi više općenito, a ti pobjegne, barem u posljednje vrijeme? Pa, primijetit visinu ovu stvar. Imali smo osam elemenata, a mi to podijeli s dva, s dva, s dva. Dakle, prijavite baze dvoje osam daje nam tri. I vjerujte mi na to, ako malo maglovit na tome. No, prijavite baze dvoje osam je tri, tako da smo učinili tri sloja spajanjem. A kad smo spojili elementi, kako mnogi elementi nije gledamo na svakom od tih redaka? Ukupno n, zar ne? Zbog spojiti gornji red, iako smo to učinili parče, smo u konačnici dotaknuo svaki broj jednom. I u drugom redu, na spojiti te popise veličine dva, smo morali dotaknuti svaki element jednom. I onda ovdje stvarno jasno u zadnjem redu, smo morali dotaknuti svaki od onih Elementi jednom, ali samo jednom, pa ovdje leži, dakle, naša n log n. A sada samo da bi stvari malo više formalno samo na trenutak, ako vas su se sada analizirati ovo na svojevrstan višoj razini i pokušati odlučiti, te kako možda da se o izražavanju vrijeme rada ovog algoritma samo gledanjem u njega, a ne pomoću neprirodan primjer? Pa, koliko vremena će vam reći korak kao što je ovaj u žutom će potrajati, Ako je n <2 povratak? To je veliki O čega? Dakle, vidim jedan, pa jedan korak, možda dva koraka, jer to je, ako a zatim se vratiti, ali to je konstantna vremena, zar ne? Tako smo, rekao je O (1), a to je kako ću se izraziti. T, samo se prikazivati ​​vrijeme. n je veličina ulaza, pa T (n), samo fancy način govoreći prikazivati Vrijeme dao unos veličine n će biti na red konstantnog vremena u O (1). Ali inače, što je ovo? Kako bi vam izraziti vrijeme rada ove žute crte? T čega? Možete vrsta varati i ovdje odgovoriti na moje pitanje ciklički. Dakle, ako se radi put u Općenito možemo samo reći da je T (n). I sada ste vrsta punting ovdje i govoreći, dobro, samo sortirati lijevu polovicu, a zatim sortirati desnu polovicu. Kako bismo mogli simbolično predstavljaju vrijeme rada ove žute crte? T čega? Što je veličina ulaz? n više od dva. Zašto ne bih samo reći da? A onda je to još jedan T (n / 2), a zatim opet, ako sam spojiti dvije polovice razvrstane, Koliko elementi ću imati na dodir ukupno? n. Dakle, ja mogu izraziti, samo da bude neka vrsta fancy, kao trčanje vremena općenito. T (n) je samo vrijeme rada T (n / 2), plus T (n / 2), lijeva polovica i desnu polovicu, plus O (n), što je vjerojatno n koraka, ali možda, ako sam pomoću dva prsta, to je dvostruko više koraci, ali to je linearno. To je neki broj koraka to je faktor n, pa možemo izraziti kao ovaj. I ovo je mjesto gdje sada ćemo čamac za natrag naše matematiku u srednjoj školi udžbenika smo da recidiva u konačnici završi izjednačavanje to, n puta log n, Ako ste zapravo učiniti izvan Matematika više formalno. Dakle, to je samo dvije perspektive. Jedan brojčano s hard-kodirane reprezentativni primjer pomoću osam brojeva i više Općenito pogledati kako smo došli tamo. No, ono što je stvarno zanimljivo ovdje je, opet, taj pojam biciklizam. Ja ne koriste za petlje. Ja sam vrsta definiranja nešto u smislu sama po sebi, ne samo s tim matematička funkcija, ali iu smislu ove pseudo koda. Ova pseudo kod je rekurzivna U tom dvojicom svojih linija je u biti to govori da ide se koristiti za rješavanje manji Problem manjih dimenzija, i onda opet i opet i opet sve dok ga strugati do tog tzv osnovnom scenariju. Tako ćemo doista privući više uvjerljiv potrajati-daleko od toga kako slijedi. Pusti me u gedit i uzeti Pogledajmo neke od današnjeg izvornog koda, osobito ovaj primjer ovdje. Sigma 0, što je očito, dodaje brojeva od jedan do n. Pa da vidimo što je poznato i upoznati ovdje. Prvo imamo nekoliko uključuje, tako da ništa novo. Prototip. Ja sam malo maglovita na to nakon nekoliko dana, No, ono što smo rekli prototip funkcija je? PUBLIKA: [nečujan]. Zvučnik 1: Što je to? PUBLIKA: Mi ga objaviti. Zvučnik 1: Mi ga objaviti. Tako da uče zveket, hej, Nije zapravo provedbi ovaj još, ali negdje u ovoj datoteci, vjerojatno, koja će se funkcija zove ono? Sigma. A to je samo obećanje da to će izgledati ovako. To će potrajati cijeli broj kao input-- i ja mogu biti jasniji i reći int n --and je će se vratiti int, ali-zarezom sredstva, mm, ja ću doći oko za provedbu toga malo kasnije. Opet, jeka je glupa. To je jedini će znati što što reći vrha do dna, tako da ćemo morati barem dati to nagovještaj onoga što će doći. Sada pogledajmo glavna ovdje. Idemo dođite ovamo i vidjeti što glavna radi. Nije to toliko dugo u funkciji, a zapravo konstrukt ovdje je poznato. Izjavljujem varijablu n, a zatim I opet sam gnjaviti korisnika za pozitivni cijeli pomoću getInt, i jedini izlaz iz ove petlje nakon što je korisnik postupio. Učiniti dok smo se koristi za dosađivati ​​korisniku na taj način. Sada je to zanimljivo. Izjavljujem int pod nazivom "odgovor". Ja to povratna vrijednost dodijeliti od ovisnosti pod nazivom "Sigma". Ne znam što to čini još uvijek, ali Sjećam ga progla trenutak prije. A onda sam u prolazu Vrijednost koju korisnik upisali u, n, a onda sam se prijaviti odgovor. Pa ajmo dođite natrag samo na trenutak. Idemo naprijed u ovaj imenik, napravite Sigma 0, a zapravo pokrenuti ovaj program i vidjeti što se događa. Dakle, ako sam ići naprijed i pokrenuti Ovaj program, ./sigma-0, i ja upisati pozitivno cijeli broj kao dva, Sigma, kao grčki simbol podrazumijeva, samo je će se zbrojiti sve brojeve iz usredotočiti na do dva. Dakle, 0 plus 1 plus 2. Dakle, ovo nadamo se treba dati mi 3. To je sve što radi. A na sličan način, ako sam pokrenuti ovaj opet i ja da je to broj tri, to je 3 plus 2, tako da je 5 plus 1 treba mi dati 6. A onda, ako sam se stvarno luda i početi upisivati ​​u većim brojevima, to mi treba dati veće i veće svote. Dakle, to je sve. Pa što ne Sigma izgledati? Pa, to je prilično jednostavan. To je kako smo mogli provoditi ovo za posljednjih nekoliko tjedana. "Int" će biti povratni tip. Sigma je ime, i to traje varijabla m umjesto n. Ja ću to promijeniti do vrha. Onda je ovo samo provjera razum. Vidjet ćemo zašto je u ovom trenutku. Sada izjavljujem drugi varijablu, suma, inicijalizirati ga na nulu. Onda sam to za petlju iterating, očito zbog jasnoće, od i = 1 na do an = m, što je sve što korisnik upisali u, a onda sam povećajte iznos kao što je ovaj. A onda se vratiti svotu. Dakle, par pitanja. Jedan od njih, ja tvrdim u mom komentaru da to izbjegava rizik od beskonačnu petlju. Zašto bi prolazi u negativnom broj izazivati, potencijalno, beskonačnu petlju? PUBLIKA: Nikad nećeš doći metara. Zvučnik 1: Nikad do m. No, m je donesen u, pa neka je razmotriti jednostavan primjer. Ako m je donesen u po korisnik kao negativan. Bez obzira na glavni. Glavni nas štiti od ovo previše, pa sam samo što stvarno analni s Sigma je također kako bi bili sigurni da ulaz ne može biti negativan. Dakle, ako m je negativna, nešto kao negativan. Što će se dogoditi? Pa, ja se ide na se inicijalno jednom, a onda sam je idući u biti manji ili jednak m? Stand by. To was-- Nemojmo, ajmo Nix ovu priču. Nisam pitao to pitanje, jer Rizik da sam aludirao na se neće dogoditi, jer sam je Uvijek će biti veća than-- redu, Ja uvući to pitanje. U redu. Idemo se fokusirati samo na ovaj dio ovdje. Zašto sam proglasiti neki izvan petlje? Obavijest o liniji 49 Imam proglasio ja unutar petlje, ali on-line 48 Imam proglasio neki izvana. Da. PUBLIKA: [nečujan]. Zvučnik 1: Svakako. Dakle, prije svega ja sigurno ne želite objaviti i inicijalizirati iznos nuli unutrašnjost petlje na svakoj iteraciji, jer bi to jasno poraz Svrha sumiranje brojeva. Ja bih stalno mijenja Vrijednost vratiti na nulu. I također, što je još jedan više kompliciranih Razlog za taj isti dizajn odluke? Da. PUBLIKA: [nečujan]. Zvučnik 1: Točno. Želim mu pristupiti izvana petlje previše o tome što liniji? Na 53. I na temelju naše pravilo od prije par predavanja, varijable scoped, zapravo, da se kovrčava aparatić koji ih obuhvaćaju. Dakle, ako ja ne proglasi iznos unutar od ovih vanjskih vitičastim zagradama, Ne mogu ga koristiti u skladu 53. Drugim riječima, ako sam proglasio suma u ovdje, ili čak i unutar Za petlje, nisam mogao pristupiti u 53. Varijabla bi učinkovito nestati. Dakle, nekoliko razloga tamo. Ali sada idemo natrag i vidjeti što se događa. Dakle Sigma dobiva zove. Ona dodaje do 1 plus 2 ili 1 plus 2 plus 3, a zatim vraća vrijednost, pohranjuje ga u odgovoru, i printf ovdje Zato vidim na ekranu. Dakle, to je ono što ćemo nazvati iterativni pristup, gdje iteracija samo znači pomoću petlje. Za petlje, while petlji učiniti dok petlja, upravo radi nešto opet i opet i opet. Ali Sigma je vrsta uredan funkcije u da sam mogao provesti drugačije. Što je to, što samo da bude vrsta cool, neka mi stvarno riješiti od puno distrakcija jer ove funkcije je stvarno vrlo jednostavan. Idemo strugati ga dolje samo na četiri osnovne linije i riješiti sve komentari i vitičastim zagradama. To je neka vrsta nevjerojatnih alternativa implementacija. Dobro, možda ne smeta puhanje, ali to je vrsta seksi, u redu, gledati na to tako mnogo više jezgrovito. Sa samo četiri linija koda, Prvi put sam se ovaj duševne ček. Ako m je manji od ili jednak nula, Sigma nema smisla. To je samo trebao biti u ovaj slučaj za pozitivne brojeve, pa ja sam samo idući u povratak na nulu samovoljno tako da mi barem imamo Neki tzv osnovni scenarij. No, ovdje je ljepota. Cjelokupnost ove ideje, dodavši Brojevi od 1 do n, m ili u ovom slučaju, se može učiniti vrstom prolazi mužjak. Pa, što je suma od 1 do m? Pa, znate što? To je isto kao zbroj m plus suma od 1 do m minus 1. Pa znaš što? Što je sigma od minus 1 m? Pa, ako ste vrsta slijediti ovaj logično, to je isto kao m minus 1 plus Sigma m minus 2. Dakle, možete vrsta samo-- to je kao, ako si samo pokušavate ljutiti prijatelja i oni vam postaviti jedno pitanje, ste vrsta odgovoriti na pitanje, možete vrsta zadržati prolazi mužjak. No, ono što je ključno je da ako bi se čineći pitanje manji i manji i manja, ti si ne pita što je sigma n, što je sigma od nje, što je Sigma n? Pitaš što je Sigma n, što je sigma n minus 1, što je Sigma n minus 2? Na kraju vaše pitanje će postati ono? Što je sigma jednog ili nula, neke vrlo male vrijednosti, i čim vas dobiti taj, tvoj prijatelj, nećete pitati isto pitanje opet, ste samo reći, oh to je nula. Gotovi smo igrati ovu vrstu glupo cikličkog igre. Dakle rekurzija je čin u programiranju od funkcija koja sebe. Ovaj program, kada je sastavljen i trčanje, je će se ponašati na isti način, No, ono što je ključno je da unutar od funkcija zove Sigma, postoji linija koda pri čemu mi smo sami zovete, koji bi normalno biti loše. Na primjer, što ako sam prvi put sastavio ovo, pa bi sigma-- bi Sigma 1 ./sigma-1. Pozitivan broj, molimo, 50 1275. Dakle, ono što je funkcija, čini se se, na temelju jednog testa, ispravan. No, što ako sam se malo opasno i brisanje tzv osnovni scenarij, i samo reći, ali ja sam samo to da to složeniji nego što jest. Ajmo izračunati SIGMA uzimanjem m, a zatim dodao u sigma od m minus jedan? Pa, što će se dogoditi? Idemo udaljavanje. Idemo rekompilirati programa, spremiti, kompilirati program, a zatim spremni ./sigma-1 uvećanjem, upišite pozitivni cijeli molimo, 50. Kako mnogi od vas su spremni do uživajte u onome što vidim da? U redu. Dakle, to se može dogoditi za nekoliko razloga, a iskreno ovaj tjedan smo o da vam dati više od njih. No, u tom slučaju, pokušajte razumu unatrag Što bi se dogodilo ovdje? Segmentacija kriv, rekli smo prošli vrijeme, odnosi se na segment memorije. Nešto loše se dogodilo. No, ono što ga je mehanički da ode po zlu ovdje zbog moje uklanjanje tog tzv osnovnom scenariju, gdje sam se vratio hard-kodirane vrijednosti? Što mislite je pošlo po zlu? Da. PUBLIKA: [nečujan]. Zvučnik 1: Ah. Dobro pitanje. Dakle veličini broja da sam saželo Ima toliko velika da je premašen veličina memorije. Dobra ideja, ali nije bitno će izazvati sudar. To bi moglo izazvati cijeli preljev, gdje su bitovi samo flip preko i onda smo pogrešno stvarno velika broj za kao negativni broj, ali to samo po sebi neće izazvati sudar. Jer na kraju Dan int još 32 bita. Ti nećeš slučajno ukrasti 33. malo. No, dobra misao. Da. PUBLIKA: [nečujan]. Zvučnik 1: Metoda nikada ne zaustavi, i doista se ponovno poziva i opet i opet i opet i opet, i nitko od ta funkcija ikad završiti jer je njihov jedini redak Kod uvijek iznova poziva themself i opet. A ono što je stvarno događa ovdje, a sada smo Možete vrsta draw to slikovito. Pustite me na to Slika samo na trenutak. To je slika, da na kraju će meso iz detaljnije, onoga što se događa unutar memorije računala. I ispada da se na dnu ove slike nešto što se zove stog. To je komad memorije, komad RAM-a, to je samo koristiti u bilo koje vrijeme Funkcija se zove. Svaki put kada, programer, pozvati funkciju, operativnog sustava, kao što su Mac OS, Windows ili Linux, zgrabi hrpa bitova, možda Nekoliko kilobajta, možda i nekoliko megabajta memorije, ruke im za vas, a onda vam pokrenete svoj funkcije pomoću sve što vam je potrebno varijabli. A ako onda pozvati drugu Funkcija i još jedna funkcija, li dobiti još jednu krišku memorije i još jedna kriška memorije. I doista, ako ovim zelenim ladicama iz Annenberg predstavlja tu uspomenu, Evo što se događa prvi koje vrijeme, na funkciju sigma. To je poput stavljanja ladicu ovako na ono što je u početku prazna stog. Ali onda, ako je ladica se poziva, da se tako izrazim, pozivanje drugi primjer Sigma, to je kao da pitate operativni sustav, Ooh, treba malo više memorije, Daj mi to. I onda to dobiva nagomilan na na vrhu. No, ono što je ovdje ključno je da Prva ladica je još uvijek tamo, jer je pozivati ​​ovu drugu ladicu. Sada je u međuvremenu, Sigma nazvati sigma, to je kao da pitate za više memorije. Dobiva nagomilan na ovamo. Sigma nazvati Sigma, to je druga pladanj koji se gomilali ovdje. A ako Ponavljajte taj, na kraju, vrsta map ovaj vizualni na toj ljestvici, što će se dogoditi s hrpom ladica? To će premašiti iznos memorije vaše računalo ima. I čim je ovaj zeleni ladice prelazi vodoravnu liniju stog gore i gore tu riječ hrpi, što ćemo se vratiti u budućnosti, to je loša stvar. Gomila je drugačija segment memorije, i ako neka to kade gomila i gomila na, ti ćeš prelaziti svoj segment memorije, i Program doista ide na sudar. Sada kao na stranu, ove ideje od rekurzije, dakle, jasno može dovesti do problema, ali to ne mora nužno biti loša stvar. Zato razmislite, nakon sve, how-- a možda to uzima neke koristi dobivanje da --how elegantan ili kako jednostavan da provedba sigma je. I nećemo koristiti rekurzija sve što je mnogo u CS50, ali u CS51, i stvarno bilo klase gdje se manipulirati strukture podataka poput stabala, ili obiteljskih stabala, da imaju neku hijerarhiju, to je super, super korisna. Sada, kao što je na stranu, tako da vas kao želja računalnih znanstvenika su upoznati s nekim od Google-a unutar šale, ako idete na Google a vi pogledati ono što je definicija, recimo, rekurzija, ući. Aha. Kao na stranu, sam se zaustavio nekoliko. To je kao da 10 minuta odugovlačenje jutros. Ako ste i Google "iskosa", obavijest naginjanjem glavu slightly-- a onda ovo je možda najokrutniji od svih jer je netko proveo kao njihov dan provedbe ovog nekoliko godina ago-- hajde. Oh, wait-- da je bug. Dakle, radi na jednom od Najveći svjetski web stranice su ovi glupi pisanica. Oni vjerojatno konzumirati svaki bitan broj linija koda samo tako da možemo imati malo zabave takve stvari. Ali barem sada ste dobili Neki od onih unutar viceva. Sada ćemo pogledati neke od White Lies smo se govori u posljednje vrijeme, i početi guliti natrag neki slojevi tehnički tako da stvarno razumiju Što se događa i možete razumjeti Neke od prijetnji, kao što je potres mozga, da sada su počeli da postanu na čelu svačijeg pažnje, barem u medijima. Dakle, ovdje je vrlo jednostavna funkcija koji vraća ništa, praznina. Njegovo ime je zamjena. To traje dvije nepoznanice i to vraća ništa. Uzeti u A i B. Tako brzo demonstracija. Donijeli smo ove gore. Mi možda i uzeti malo razbiti tu samo na trenutak i imaju nešto za popiti. Ako se netko ne bi smetalo pridružio ja ovdje samo na trenutak gore. Kako je s vama u kesten majicu? Dođi gore. Samo jedan danas. Hvala ti, ipak. U redu, a imamo dolazi tko ovdje? Koje je tvoje ime? Zvučnik 4: Laura. Zvučnik 1: Laura. Dođi gore. Tako je Laura, vrlo jednostavan izazov danas. Lijepo je jo susret. U redu. Dakle, imamo malo mlijeka ovamo i imamo neke sok od naranče ovamo i neke čaše koje smo posudio od Annenberg danas. Zvučnik 4: Posudio. Zvučnik 1: I ići dalje i dati vam pola čaše to. U redu. A mi ćemo vam dati pola Čaša mlijeka. Oh, i jednostavno, tako da možete sjetiti što je to bilo, Sjetio sam se kako bi ovo gore i na danas. Ok. Ako ti ne bi smetalo, da vidimo, mi Možete ih staviti preko vaših naočala ako želiš. To će biti svijet iz Laurinim očima. U redu. Dakle, vaš cilj, dao dvije šalice Tekućina ovdje, mlijeko i sok od naranče, se zamijeniti dva sadržaja, tako da Sok od naranče ide u šalici mlijeka a mlijeko ide u Sok od naranče čaša. Zvučnik 4: Hoću li dobiti još jednu šalicu? Zvučnik 1: Drago mi je što ste pitali, iako to bi bilo puno bolje snimke ako nije pitao. Ali da, možemo vam ponuditi i treći Šalica koja je prazna, naravno. U redu. Dakle, mijenjati sadržaj postoji. Vrlo lijepo. Vrlo dobro. Vi ste to radili iznimno pažljivo. I treći korak. U redu. Izvrsno. Veliki pljesak bilo bi dobro za Lauru. U redu. Imamo mali oproštajni dar za vas, ali neka mi se to. Hvala ti puno. Tako jednostavan primjer, premda, pokazati da ako to ne učinite želite mijenjati sadržaj od dva kontejnera, ili nazovimo ih varijabli, Trebate li privremeno skladištenje na pozornici jednog od sadržaja u tako da zapravo možete napraviti swap. Dakle, doista, to izvorni kod ovdje u C prikazuje upravo to. Ako je sok od naranče i mlijeko Bio b, a mi htjeli zamijeniti dvije, možete pokušati nešto kreativno izlijevanjem jedna u drugu, ali to vjerojatno ne bi završiti osobito dobro. I tako mi koristimo treću čašu, poziv to tmp, T-M-P dogovorno i staviti sadržaj SL u to, onda zamijeniti jednu šalicu, zatim staviti u OJ Izvorni šalice, čime postizanje, točno onako kako Laura je, swap. Tako ćemo učiniti upravo to. Dopustite mi ići naprijed i otvoriti do primjer koji je zapravo se zove "ne zamijeniti, "jer to nije što je jednostavno učinio kao što možda mislite. Tako je u ovom programu, primijetiti da Ja sam koristeći stdio.h, naš stari prijatelj. Imam prototip za zamjenu tamo gore, što znači njegova primjena je Vjerojatno dolje, pa da vidimo što je to glavna Program će raditi za mene. Prvi put sam proglasiti int x dobiva jedan, a int y dobiva dva. Dakle, mislite o onima što SL i mlijeko, respektivno. I onda sam samo printf rekavši x je ovo i y je to, samo tako mogu vizualno vidjeti što se događa. Onda sam printf tvrdeći da sam zamjene dva, a onda sam se ispisati tvrde da su oni zamijenili, i ja opet ispisati X i Y. Dakle, ovdje je u swap upravo ono što je Laura, i upravo ono što smo vidjeli na Zaslon trenutak prije. Dakle, idemo naprijed i biti krajnje razočaran. Da ne bude zamjenu, i pokrenuti nikakvu zamjenu, zumiranje u na izlazu ovdje. Ulaz je x 1, y je 2, zamjene zamijenili. x je uvijek 1, a y je još 2. Dakle, iako, iskreno govoreći, ovo izgleda baš sviđa, iako više tehnički, što Laura učinio, nije se činilo da rade. Pa zašto je to tako? Pa, ispada da kad pišemo program kao što je to koji je i glavni, istaknuo ovdje, a zatim još jedna funkcija, kao što su izmjene u radu, istaknuta ovdje, koji ona naziva, svijet izgleda malo nešto slično ove ladice trenutak prije. Kada je glavni prvi dobiva zove, to je kao da pitate operativni sustav za malo memorije za bilo lokalno varijable kao što su xiy da glavna ima, i završe tamo gore. No, ako je glavni pozivi mijenjati, a glavna prolazi da zamijene dva argumenta, A i B, Sok od naranče i mlijeko, to nije kao predaje sok od naranče i mlijeko Lauri. Ono što računalo radi, to je prolazi kopije soka od naranče i kopije mlijeka Lauri, tako da što je u konačnici unutar ove ladice vrijednost je jedan i dva, ili OJ i njihovi mlijeka, ali primjeraka, tako da se u tom trenutku u priči, postoji je SL i mlijeko u svakoj od tih ladica. Ima jedan i dva U svakom od ovih ladica, i funkcija zamjena doista radi. To ih zamjene unutar na drugi najviši ladicu, ali da zamjene nema utjecaja. I na temelju samo neki Osnovni princip mi smo govorio o prije, i doista Prije samo nekoliko minuta, što moglo objasniti zašto mijenjaju ib unutar swapa nema učinka na X i Y, iako Prošao sam X i Y na funkciji zamjenu. Što je ključna riječ ovdje da možda pojednostavljeno objasniti? Mislim da je to čuo sam ovdje? PUBLIKA: Povratak. Zvučnik 1: Povratak? Ne vrate. Idemo s jednim drugim. Što je to? PUBLIKA: [nečujan]. Zvučnik 1: U redu, tako da smo mogli return-- bi povratnu rad u priči, ali tu je još jednostavnije objašnjenje. PUBLIKA: Opseg. Zvučnik 1: Opseg. Uzet ću opseg. Dakle, opseg, sjetiti gdje Naš xiy proglasio. Oni proglasio unutar od Glavni pravu ovdje. i b, u međuvremenu, su učinkovito proglasio unutar swapa, ne sasvim u Kovrčava aparatić, ali još uvijek u općem području swapa. I tako je doista, i b postoje samo u ovoj ladici iz Annenberg, ovo Drugi komad koda. Dakle, mi doista Mijenjamo kopirati, ali to nije stvarno sve što je korisno. Tako ćemo pogledati ovo malo niža razina. Ja ću se vratiti u Izvor imenik, i ja ću prvi povećavanje ovdje, i samo potvrditi da sam u to veći terminal prozor, Program je još uvijek ponaša kao da je. Pretpostavimo sada da je ovaj nije namjerno. Jasno sam htjela zamjenu za radovi, tako da se osjeća kao kukac. Sada sam mogao početi dodavanjem Puno printf-a na moj broj, ispis x ovamo, y tijekom ovdje, ovamo, b ovamo. Ali iskreno, to je vjerojatno ono što što ste radili za par tjedana Sada, u radno vrijeme i kod kuće kada radite na psets pokušavaju naći neke greške. No, vidjet ćete, ako već niste, da je problem postaviti tri uvodi vas na naredbe zove GDB, gdje GDB, GNU debugger, je sama cijela hrpa značajke koje mogu zapravo neka nas razumjeti situacije kao što je ovaj, ali je još uvjerljivo, rješavati probleme i pronaći greške. Tako da ću to učiniti. Umjesto ./noswap, ja sam umjesto će pokrenuti GDB ./noswap. Drugim riječima, ja ću pokrenuti moje Program ne Bash, naš novi prijatelj danas. Idem na trčanje moj Program noswap unutar ovog drugog programa pod nazivom GDB, što je za pronalaženje pogrešaka, što je program koji je osmišljen kako bi pomogao Vi ljudi pronaći i ukloniti greške. Dakle, ako sam pogodio Run ovdje, tu krvoločan količina teksta da stvarno nikada ne morate čitati. To je u biti distrakcija od redak, koji Ja ću pogoditi Control-L ustati na vrhu tamo. To je GDB brz. Ako želim pokrenuti ovaj program, kao ovo mangupirati se plahta na današnjem slide sugerira, Run je prvi zapovijeda da smo trebali uvesti. I Samo ću upisati trčanje ovdje unutar GDB, i doista je vodio moj program. Sada postoji neka dodatna izlazi na zaslonu kao što je ovaj, ali to je samo bio GDB analni i reći nam što se događa. Vi stvarno ne morate brinuti o tim detaljima sada. No, ono što je stvarno cool o GDB, ako sam to učiniti again-- Kontrola-L briše screen-- me pusti naprijed i tipa "slomiti glavna", čime se, kad sam udario Enter, postavljanje što je pod nazivom Point Break na noswap.c, Linija 16, što je, gdje GDB shvatio moj program zapravo je, moja je funkcija zapravo je. To ćemo zanemariti za sada ali to je adresa u spomen posebno ove funkcije. Dakle, sada kada sam tip trčanje, primijetiti ono što je cool ovdje. Moj program razbija na liniji I. Rekao GDB za pauzu na izvršenje. Dakle, ne moram se sada promijeniti moj broj, dodati neke printf-a, kompilirati ga, ponoviti da, promijeniti, dodati neke printf-a, spremiti, kompilirati ga, pokrenite ga. Ja samo mogu prošetati kroz moj program korak po korak po korak u ljudskoj brzini, Nije na Intel-unutar vrste brzine. Tako sada primjetiti ovu liniju pojavljuje ovdje, a ako se vratim mom programu u gedit, primijetiti da je to zapravo Prva linija koda. Tu je linija 16 u gedit. Tu je linija 16 u GDB, pa čak i iako je ovaj crno-bijeli sučelje nije gotovo kao korisnika prijateljski, to znači da linija 16 nije izvršena , no riječ je o biti. Pa doista, ako sam tip ispis x, ne printf, samo za ispis x, Ja dobiti neke lažne vrijednosti postoji od nule, jer x još nije ponište. Tako da ću upisati sljedeći, ili, ako vas želim biti fancy, samo n za sljedeći. Ali kad sam Sljedećih ući, sada primijetiti da prelazi na liniji 17. Pa logično, ako sam pogubljen Linija 16, a ja sada upisati ispisa x, Što bih trebao vidjeti? Jedan. I sada je to doduše zbunjujuće. 2 dolara je samo fancy način, ako vas žele da se odnosi na tu vrijednost naknadno, možete reći: "Dolar potpisati dva." To je kao back referencu. No, za sada, samo ga ignorirati. Ono što je zanimljivo je što je na desnoj strani znaka jednakosti. I sad kad bih upisati sljedeći opet i ispis y, ja bi trebao vidjeti 2. Ja sada mogu ispisivati x opet, i iskreno, ako sam uzimajući malo zbunjeni o tome gdje sam ja, ja mogu upisati popis za popis i samo vidjeti neke kontekst cijelog točka Ja sam zapravo u. I sad ja mogu upisati Sljedeći, i tu je x 1. Sada sam upisati sljedeći. Oh, y je 2. I opet, to je zbunjujuće, jer GDB je izlaz se međusobno pomiješane s mojim vlastitim izlazom. Ali, ako imate na umu, tako Bacimo li pogled unatrag i naprijed na kodu ili polaganja stranu po strani možda, vi ćete vidim da je stvarno samo sam korak kroz moj program. Ali primijetiti ono što će se sljedeće dogoditi, doslovno. Evo linija 22. Pusti me preko nje, čime se kreće na do 23, a ako ja ispisati x sada, još uvijek jedan. A ako sam y ispisati sada, još uvijek jedan. Dakle, ovo nije korisna vježba. Tako ćemo ponoviti ovo. Pustite me da se vratim do Najbolje i tip ponovno pokrenuti. I to govori program da je se debugged počela je već, počeo od početka. Da, učinimo to opet. I ovaj put ćemo učiniti, sljedeći, sljedeći, sljedeći, sljedeći, ali sada se stvari zanimljive. Sada želim da stupim u swap, pa ne upisati sljedeći. I tip korak, a sada ga primjetiti mi je skočio na noswap.c liniji 33. Ako sam se vratiti u gedit, što je linija 33? To je prva stvarna linija koda unutar swapa. Što je lijepo, jer sada mogu vrsta džaku okolo i dobiti znatiželjan o tome što se događa doista tamo. Dopustite mi ispisati tmp. Opa. Zašto tmp imaju neke luda, lažna vrijednost smeća? PUBLIKA: To nije ponište. Zvučnik 1: To nije ponište. I doista, kada pokrenete program, ti si dao hrpu memorije od strane operativnog sustava, ali su nije pokrenut niti vrijednosti, kako god bita ste vidim ovdje, iako je to ovom ludom veliki negativni broj, samo znači da su to ostaci iz Neki prethodni korištenje tog RAM-a, iako nisam Osobno ga je potrebno još. Dakle, sada ću ići naprijed i tip Sljedeći, a ako ja sada upisati ispisa tmp, Što bih trebao vidjeti? Bez obzira na vrijednost bila je prvi argument, samo X kao što je prvi stvar bude donesen u, tako i X bi trebao biti isti, tako ispisati tmp treba ispisati mi jednu. Dakle, ono što ćete vidjeti u problemu setu tri je udžbenik sorti na GDB, ali shvatite da je ovo početak od pogled na alat koji će zapravo vam pomoći u rješavanju problema toliko mnogo učinkovitije. Ono što smo u konačnici će učiniti u srijedu se početi guliti natrag nekoliko slojeva i ukloniti neki trening kotača. Ta stvar se zove niz koji smo se koristi za neko vrijeme, idemo polako oduzeti od vas i početi govoriti o nešto više ezoterički poznat kao char *, ali ćemo učiniti ovaj lijepi i Na početku nježno, iako pokazivače, kako ih nazivaju, može napraviti neki vrlo loše stvari, ako zlostavljani, gledajući malo claymation iz naš prijatelj Nick Parlante Stanford Sveučilište, profesor na računalu znanost koji su stavili zajedno ovaj pregled od onoga što će doći u srijedu. [Video reprodukciju] Hej, Binky. Probudite se. To je vrijeme za zabavu kazaljke. Što je to? Saznajte više o pokazivače? Oh, slatkiši! [END video reprodukciju] Zvučnik 1: To vas čeka u srijedu. Vidimo se onda. [Video reprodukciju] -I Sada, Deep Misli, po Daven Farnham. Zašto su mi učenje C? Zašto ne +? [Smijeh] [END video reprodukciju]