[Prehrávanie hudby] 

SPEAKER 1: Tak jo, to je CS50, a to je začiatok štvrtého týždňa a ako ste možno počuli alebo čítať, bol svet končí. Chystáte sa na celom internete bol znalosti a povedomia chyby v programe, čo je programovací jazyk s názvom Bash. To bolo nádherne značkové ako Shellshock alebo dvere Bash, ale predmety, ako sú tieto neboli neobvyklé. A v skutočnosti, mnoho z nich, aby spomienky Heartbleed, ktoré ste si možno všimli v stlačte znovu tento rok na jar, čo bol podobne docela dramatický. Teraz tí z vás dnes, koľko z vás, aj keď nechápem, čo je to všetko o, počul Shellshock? Dobre, a koľko z vás majú počítače, ktoré sú zraniteľné? OK, mal by tam byť ďaleko, ďaleko viac rúk práve teraz, z dôvodov, ktoré sú vidieť. 

Poďme sa pozrieť na to, čo je sa deje v médiách A potom sa to trochu vysvetliť pre nás technicky. 

SPEAKER 2: Bezpečnostné experti majú varoval, že vážna chyba by mohla asi ovplyvniť stovky milióny svetových internetových užívateľov. Takže čo presne je chyba, že to bolo daboval Shellshock, a čo to robí? No, Shellshock je tiež známy ako Bash chyba, softvér ich využíva. Hackeri používajú vírus skenovanie zraniteľné systémy beží Linux a Unix operačné systémy a infikovať ich. Bash je príkazový riadok shellu. To umožňuje užívateľom vydávať príkazy na spustenie programy a funkcie v softvéri zadaním textu. To je zvyčajne používaný programátorov a by nemala byť otvorená voči okolitému svetu, keď Shellshock zmeny, ktoré. 

No, worringly, niektorí analytici varujú, že môže byť väčšou hrozbou, pretože Shellshock umožňuje kompletné ovládanie infikovaného stroja, vzhľadom k tomu, Heartbleed povolené len hackeri špehovať na počítačoch. Je to tak vážne, že je to bola hodnotená v 10 z 10 k závažnosti podľa vnútroštátnych Databáza zraniteľnosť. 2/3 zo všetkých webových serverov sú rizík, vrátane niektorých počítačoch so systémom Mac. No, uistite sa, že opraviť svoje systémy teraz. Každý hosting webových stránok v chode postihnuté operačné systémy by mali prijať opatrenia čo najskôr. Každý, kto si môže dovoliť to malo vyzerať ich sledovanie a webové aplikácie firewally dávať pozor na prípadné útoky. SPEAKER 3: Najhoršia vec že by sa mohlo stať, je že by niekto napísať kód, ktorý sa automaticky prepne a skenovanie internet a bude mať vplyv na všetkých týchto počítačov. A keď to robia dobre, Najhoršia vec, ktorú mohol urobiť je len odstrániť všetko, alebo zavrel miesta nadol. Takže sme mohli vidieť poškodenie z tohto uhla pohľadu, kde budeme mať škodlivé ľudí ktorí sa len rozhodnúť, že spôsobí katastrofu tým, že systémy, nadol alebo odstránenie súbory, a podobné veci. SPEAKER 2: Niektorí hovoria, že je to jeden z najťažších merať chyby v rokoch, a to môže trvať týždne alebo dokonca mesiacov na určenie jeho konečného vplyvu. 

SPEAKER 1: Takže všetko je to pravda, ale legrační vec je, takmer všetky Užívanie metafor ste práve videli, s výnimkou snáď klávesnicu, nemá nič spoločné s bug vôbec. Servery a drôty a tak ďalej, je to trochu tangenciálne súvisiacich ale v jadre je to vlastne celkom pozná to, čo sa tu deje. V skutočnosti, nechajte ma ísť do naše CS50 spotrebiča. Nechaj ma ísť napred a maximalizovať okno terminálu tu. A vy ste pomocou tohto, alebo vložený verzie tejto zmluvy, v gedit, aby sa písať programy, typ príkazy, a tak ďalej, a to je v skutočnosti, a má už niekoľko týždňov, Bash, B-A-S-H. To je Bourne-again shell, čo je len ozdobný spôsob, ako hovoriť, To je program, ktorý má blikanie rýchle, efektívne, že sedí tam čaká pre vstup pre vás. A je to príkaz riadky, cez ktoré vy ste bola spustená príkazov a nakoniec kompiláciu a spustením programy. 

Ale Bash je tiež programovanie jazyk v nasledujúcom zmysle. Viete, že existujú príkazy, ako je cd a ls aj zvoniť a ďalšie, ale môžete definovať vlastné príkazy od ich zavádzania do Bash. Teraz už nebudeme ísť do skvelého detailu ako Bash programovací jazyk, ale Viete, napríklad, že v súčasnej dobe, tam žiadny príkaz s názvom "Ahoj." Takže to možno nájsť v jeden z týchto balíčkov. Nie je nainštalovaný na mojom počítači. Spýtajte sa na správcu systému. Ale ak chcem tam byť program s názvom "ahoj" v bash alebo na moje výzvy, Môžem skutočne používať syntax, ktorá je celkom ako C. Nie je to úplne rovnaké, ale vyzerá to celkom podobné funkcie, aj keď chýbajú niektoré detaily. Sa zdanlivo nič nedeje, ale teraz keď som napísať "ahoj" , Môžete vytvoriť programu, a to v jazyku C, a to v jazyku Java, nie v inom programovaní jazyk, ale v Bash sám. 

Teraz je tu kľúčové je, že som napísal Meno Chcel som, aby tento nový príkaz, a zátvorky sú tiež symbolický čo je funkcia. Mimochodom, môžete si tiež urobiť srandu veci, a v skutočnosti, a to aj na Mac OS, To je program s názvom Terminal. Je dodávaný vstavaný do kohokoľvek počítač, ktorý má Mac v tejto miestnosti, a môžete robiť podobné veci v Mac OS, ale môžete ísť viac než to. A to je trochu tangenciálny, ale je to celkom sranda. Pripomenul som si dnes ráno, keď myslia si, vďaka, na malú hru som hrával s jedným z CS50 bývalých TFs kedy kedykoľvek by odísť z Jeho klávesnica s jeho obrazovku odomknúť, Ja by som spustiť príkaz ako tohle-- "pozdraviť." A teraz nejaký čas sa vrátil k jeho klávesnice, čo som vyčistil obrazovku a on by si sadnúť, pokúsiť sa urobiť nejakú prácu, vypísať obsah jeho directory-- 

[Prehrávanie zvuku] 

Ahoj. Dobrý deň. 

SPEAKER 1: Takže, v spravodlivosti, to nie je v skutočnosti "ahoj." Bolo to zvyčajne niečo viac podobný že-- [Prehrávanie zvuku] -Beep. SPEAKER 1: začali uznávať takzvané I would-- tak jeho počítač by nadávať na neho, kedykoľvek sa mu vlastne sa posadil na jeho klávesnici. A veľmi rýchlo prišiel na to nenechávať jeho obrazovka odomknutá. Ale to naznačuje, že druh z hlúpe zábavy, ktorá vás môže mať niečo ako Bash. Ale je to trochu viac vážne, aby bolo jasno, než to. A v skutočnosti, to je jeden z najnebezpečnejšie a dlhotrvajúci chyby že naozaj zasiahla svet po celom svete. Táto chyba bola asi pre asi 20 rokov, a budete udrel v niekoľkých okamih jeho relatívna jednoduchosť. 

Tak toto je reprezentatívna príkaz, že ak vlastné Mac, doslova hneď Keď máte otvorené veko, môžete skúsiť písať do toho program s názvom Terminal. Terminál je pod Aplikácia Utilities-- raz, používatelia Windows nemusíte starať o tomto threat-- ale tí z vás s počítačmi Mac môžete zadať to do okna, ako to urobím tu, a ak nechcete písať že do tohto programu Terminál, ako ja budem robiť teraz, keď vidíte slovo "zraniteľný", váš počítač náchylné k vykorisťovaniu. 

Teraz čo to vlastne znamená? A to je pravda niektorí dosť šialené syntax, ale poďme aspoň vytiahnuť niektoré zo zaujímavých aspektov. Takže tam je nejaká syntaxe, ktorá vyzerá trochu pozná, aspoň z C a programovanie všeobecne. Vidím nejaké zátvorky, bodkočiarkami, zložené zátvorky, a také, ale ukázalo sa, že tento hlúposť tu v žltej farbe je v podstate funkcia že nerobí nič. Dvojbodka znamená nerobiť nič, a bodkočiarka znamená prestať robiť nič. Takže vnútri nich zložené zátvorky, skutočnosť, že mám rovné prihlásiť sa vľavo, to je v podstate vytvára príkaz, alebo premenná, nazvaný x a priradením tá žltá časť kódu tam. To by mohlo byť niečo ako "echo ahoj "alebo" hovoria pípnutie ", alebo tak niečo podobný tomu. Všimnime si ale, ak vaše oči ďalej putovať na pravej strane, tam je viac k tejto čiare, než len koniec tejto bodkočiarkou. "Echo zraniteľný", a potom Okrem toho je tu ešte viac. Ďalšie bodkočiarka, bash-c:. 

Tak dlhý príbeh krátky, tento riadok kódu je dostatočná pre presvedčivé Počítač, ktorý je citlivé na niečo že chcete to robiť, pretože tam je chyba v Bash, kedy aj keď Bash mal zastaviť čítanie riadkov príkazu vpravo tam po žltej textu, na 20 a navyše rok stará chyba, Bash skutočne čítal po tomto bodkočiarkou a pekná veľa robí to, čo je povedané. 

Takže to, čo je to dôsledok z toho nakoniec? Len som povedal, "echo ahoj" alebo "echo zraniteľné," ale čo keď ste niečo v skutočnosti škodlivý, ako rm -RF * ktoré ste možno nie kedy napísal skôr, a úprimne povedané, pravdepodobne nemali príliš skoro, pretože môžete robiť Mnoho škôd s ním. Prečo? rm čo robí, samozrejme? Odstraňuje. * Znamená čo? Všetko. Takže je to tak-zvané divoká karta, tak to znamená, že zmazať všetko aktuálny adresár. r sa deje tak, že znamená rekurzívne, čo znamená, že ak to, čo ste zmazanie je adresár, a vnútri tam je ďalšie súbory a ďalšie adresáre, rekurzívne ponoriť do ešte a odstrániť všetko. A f je najhoršie zo všetkých. Každý, kto vie, čo f tu znamená? Force. Takže nútiť prostriedky, a to aj či je to dobrý nápad, to bez toho by ma výzva Pre ďalšie potvrdenie. Takže, viete, my smiať , Ale úprimne povedané, asi by som Tento typ viackrát deň, pretože skutočnosti je, že je to najrýchlejší spôsob, ako odstrániť veľa vecí. Ale aj ja som urobil nejakú škodu. 

Ale ak ste boli na trik počítač do definovania nejaké stupídne premenné alebo volanie funkcie x, ale potom podvádzať počítača do realizácie za hranice, ktoré funkcie nad rámec tohto bodkočiarkou, môžete naozaj trik počítač k vykonaniu niečo ako rm -RF alebo príkaz E-mail alebo príkaz Kopírovať. Čokoľvek doslova môžete robiť s počítač, či už je to mazanie súborov, vytváranie súborov, spamy niekoho, útočia na nejaké serveri vzdialene, ak môžete vyjadriť s príkazom, je môže prinútiť počítač, aby robili to. 

Teraz, čo je príklad , Ako by to mohlo robiť? No, je tu veľa počítačov na internet tečúcou Bash. Všetci používatelia, aby sme Mac sú medzi nimi. Mnoho linuxových serverov patrí medzi je tiež, a servery Unix. Windows opäť dostane relatívne vyvesený Ak ste nainštalovali špeciálny softvér. Teraz veľa serverov, pre inštancie, spustiť webové servery, av skutočnosti Linux je možná najobľúbenejší operačný systém aby mohlo bežať na počítačoch na internete ktoré sa servírujú stránky. Teraz, ako uvidíme neskôr, v semestri, kedy odošlite žiadosť Váš browser-- Chrome, Internet Explorer, whatever-- na vzdialenom serveri, Ukazuje sa, že aj keď ste práve zadali www.example.com, Váš prehliadač odoslanie správy to je trochu tajomný, ako je tento. 

Ale všimnite si niečo podivného. Prvé dva riadky Nikdy som nevidel, ale nevyzerajú obzvlášť ohrozujúce. Ale všimnite, čo som ukradol na treťom riadku tu. Ak je zlý človek mal poslať správu takhle zo svojho počítača na zraniteľné Mac alebo zraniteľný server Linux, Legrační je, že Bash, že jednoduchý malý príkazový riadok, je všadeprítomný a je často použitý v podstate vykonať obsah správu, ktorá sa mu venuje. A tým, že logika, môžete trik webový server, preto, zaslaním niečo ako User-Agent, ktorý zvyčajne má hovoriť názov vášho prehliadača. User-Agent Chrome, User-Agent Internet Explorer, User-Agent Firefox, tento je jednoducho váš prehliadač je spôsob stotožňuje. Ale keď zloduch veľmi chytro hovorí, mm-mm, ja som Nie je ti to povedať čo môj prehliadač, Ja namiesto toho bude ti to poslať mystický vyzerajúce vec s rm -RF * V nej môžete doslova trik zraniteľné webový server na internete v prevedení presne, že v tam pre zmazanie všetkých súborov. A úprimne povedané, to nie je aj to najhoršie. Môžete robiť čokoľvek. Dalo by sa začať distribuovanej odmietnutie služby útoku ak si poslal túto správu celé zväzky webových serverov a potom nechal všetky zostúpiť, pre inštancie na serveroch Harvard.edu, a môžete zoradiť Bang sakra z nich o prevádzke na sieti, ktorý bol inak vyvolaná týmto zlý chlap. 

Tak dlhý príbeh krátky, takmer všetci v tejto miestnosti, kto vlastní Mac Je citlivá na to. Dobrou správou je, že ak ste beží webový server na vašom notebooku, a ak ste skutočne nakonfigurovaný to, aby niečo také SSH do toho, ste naozaj v bezpečí. To je zraniteľný, ale nie je kto sa snaží dostať do vášho notebooku, takže môžete trochu istí. Avšak, Apple čoskoro bude aktualizovať opravu to. Svet Linuxu už vydala počet opráv pre Fedora a Ubuntu a ďalšie verzie Linux, a naozaj Ak spustíte aktualizáciu 50 v zariadení, dokonca, že taky bude aktualizovaná a opravená. Že ale príliš nemá naozaj bol zraniteľný, pretože ak ste pohrali sa so spotrebičom a robil váš notebook verejne dostupné na internete, čo nie je V predvolenom nastavení, vy ste v skutočnosti bolo v poriadku, pretože z firewall a ďalších techník. 

Ale je to extrémny príklad chyby že sme žili za doslova 20 rokov, a kto vie, či sa niekto Celú tú dobu sa vie o tom? A v skutočnosti, to je jeden z základné problémy že uvidíme neskôr semester o bezpečnosť, je to, že rovnako ako v reálnom svete, dobrí sú v nevýhode. Ak chcete zachovať zbabelcami von, musíme Uistite sa, že všetky dvere sú zamknuté, že každé okno je bezpečný, že každý bod vstupu do domu je bezpečný, aby zbabelcami von. Ale to, čo robí zlý človek musí to skutočne ohroziť váš domov a kradnúť od vás? On alebo ona jednoducho musí nájsť ten, odomknutý dvere, jeden rozbité okno, alebo tak niečo v tomto smere, a to je To isté sa v oblasti počítačovej bezpečnosti. Môžeme písať milióny riadky programového kódu a utrácať stovky alebo tisíce hodín, sa snaží, aby si to v poriadku, ale ak urobíte len jeden chyba v správnosti, si môžete dať celý systém a skutočne v tomto prípade celý internet a svet v ohrození. 

Takže ak by ste sa chceli dozvedieť viac o tom, prejdite na nasledujúcu adresu tu. Netreba akcii dnes večer, ak ste medzi tie pokojnejšie, že Boli beží vlastný web servera, v tom prípade by ste mali, v skutočnosti, aktualizovať softvér. 

Aj to je názov reč, a teraz papier, že sme zviazaná Webové stránky ihrisko je pre dnešok všetko. Bolo by kolegami menoval Ken Thompson, ktorý bolo prijatie veľmi slávny Ocenenie vo vede o počítačoch, a dal túto reč o niekoľko rokov Pred podstate na rovnakú tému. Žiadať ľudí otázka, mali by ste naozaj dôvera, nakoniec, Softvér, ktorý ste dostali? Napríklad, my všetci máme bolo písanie programov, a my sme boli zostavovaní je s Clang. A svoje vedomosti, ste napísal všetky programy pre CS50 tam, kde je zadné dvere druhov, existuje spôsob, ako že zloduch, pokiaľ beží program, mohol prevziať vašom počítači? Asi nie, že jo? Mario a Greedy a Credit. To všetko sú celkom malé programy. Musel by ste byť dosť zlé, ak ste skutočne robil celý počítač zraniteľný po napísaní 10 alebo 20 riadkov kódu, alebo aspoň vedomí niektorých bezpečnostných dôsledkov. Teraz hovorím, že bodro, ale budeme vidieť dnes a tento týždeň je to vlastne naozaj, ale naozaj ľahké byť zlý, a aby ešte krátke programy zraniteľné. 

Ale teraz, aspoň si uvedomiť, že táto otázka je sem pozval je o Clang v kompilátora. Prečo sme sa veriť zvonenie za posledné dva alebo tri týždne? Kto môže povedať, že ten, kto písal zvonenie nemal "keby" podmienku, že že v podstate injekčne nejaké nuly a tie do každého programu, zostavuje že by ho nechal, alebo jej prístup počítač, keď si spal a vaša veko notebooku je otvorená a počítač so systémom? Je to tak? Máme tento druh česť systéme práva Teraz, ak veríme, že Clang je dôveryhodne. Veríte, že spotrebič je dôveryhodne. Veríte, že doslova každý program, na počítači Mac alebo PC je dôveryhodný. A ako tento jednoduchý chyba naznačuje, aj keď to nie je škodlivý, to rozhodne nie je pravdepodobné, že tomu tak je. 

Takže by ste mali báť ako čert. Úprimne povedané, nie je jednoduché Roztok sa tento druhý ako akési spoločenské povedomie z rastúcej zložitosti že staviame na vrchole našich počítačových systémov, a ako sa stále viac zraniteľnejšie by sme mohli byť celkom dobre. 

Teraz sa, že povedal, Breakout. Takže Breakout je problém nastaviť tri a Breakout je hra z dávnych dôb ktoré by vás mohli vyvolať, ale pre nás problém nastaviť tri, to nám umožňuje, aby sa veci späť do zárezu tak, že keď píšeme programy, aj v terminálovom okne, ako je tento, môžeme skutočne spustiť, nakoniec, grafické programy nie Na rozdiel od tých, ktoré sme mali prístup v Scratch. Tak toto je na zamestnanca je realizácia Breakout, čo je práve táto tehla-lámanie hra, že sa pohybujete pádlo späť a tam, a odpálil loptičku pred tými farebnými tehlami až hore. Takže to je, že nás trochu späť tam, kde sme boli schopní sa veľmi rýchlo Scratch, a teraz s C, , Ktorým sa vykonáva vlastné grafické používateľské rozhranie. 

Ale viac než to, že tento Problém set predstavuje prvý v ktorej dávame Ste banda kódu. A v skutočnosti, ja uvediem explicitné pozornosť na to, pretože najmä Pre tých menej príjemné, to problém nastaviť, aspoň na prvý pohľad, sa bude cítiť ako urobili sme ju do zárezu. Vzhľadom k tomu, že sme vám dal, Pre niektoré z hľadania a triedenie problémy v pset, banda kódu, ktorý sme napísali, a pár komentárov ktoré hovoria "robiť," kde budete musieť vyplniť prázdne miesta. Takže nie príliš desivé, ale je to prvýkrát, sme podal vám kód, ktorý je potrebné najprv prečítať, pochopiť a potom sa pridajú do a dokončiť ju. 

A potom Breakout, budeme robiť to isté, ktorá vám niekoľko desiatok viac liniek kódu, ktorý, úprimne povedané, aby vám veľa rámca pre hra, ale zastaviť pred vykonávacích tehly a loptu a pádlo, ale my realizovať niektoré ďalšie funkcie. A dokonca, že na prvý pohľad, znovu, najmä v prípade menej pohodlné, Mohlo by sa zdať obzvlášť skľučujúca a si myslíte, že je tak veľa nových funkcií budete musieť zabaliť svoju myseľ okolo, a je to pravda. Ale majte na pamäti, že je to celkom ako Scratch. Kurz ste nepoužili všetky že kúsky skladačky na začiatku. Kurz ste sa nestaral zabaliť vaša myseľ asi všetci pretože všetko, čo sa to Letmý pohľad pochopiť, oh, že to, čo sa dá robiť s týmto kúsok puzzle. A skutočne, v probléme nastavenie 3 spec, budeme bod, v dokumentácii, ktorá bude Predstavujeme Vám niektorých nových funkcií, a nakoniec programovanie konštruuje, ktorý používate. Podmienky, slučky, premenné a funkcie bude rovnaká ako to, čo sme videli doteraz. 

Takže naozaj, čo dáme vám je nejaký ukážkový kód, ktorý vám umožní vytvoriť okno ktorý vyzerá nie na rozdiel od toho a nakoniec premeniť ju na niečo také, ako toto. Takže využiť CS50, diskutovať úradné hodiny a viac, a útechu v tom, že množstvo kódu musíte napísať v skutočnosti nie je tak moc. Prvou úlohou je len aklimatizovať sami nejaký kód sme napísali. 

Akékoľvek otázky týkajúce sa pset3, Shellshock, alebo inak? 

Divákov: Zdalo sa, že prechádza s Breakout že kód je takmer objektovo-orientovaný štýl, ale myslím, že C je objektovo-orientovaný program. SPEAKER 1: výborná otázka. Takže pri pohľade cez distribúcia kód, kód sme napísali pre pset3, Pre tých, ktorí poznajú, ho Vyzerá to, že je to trochu objektovo-orientovaný. Stručná odpoveď je, že to je. Je to priblíženie na to, ako mohli robiť objektovo-orientovaný kód pomocou jazyk C, ale to je ešte nakoniec procedurálne. Tam sú umiestnené vo vnútri žiadne metódy premenné, ako uvidíte. Ale pripomína to. A uvidíme, túto funkciu znovu až sa dostaneme do PHP a JavaScript ku koncu semestra. Ale teraz, myslím, že na to, ako náznak toho, čo je príde. Dobrá otázka. V poriadku. Takže zlúčenie trochu bolo, ako sme sa ľavá veci minule. A zlúčiť druh bol cool in pocit, že je to tak oveľa rýchlejšie, aspoň na základe zbežnej testy sme robili minulý týždeň, než, povedzme, bublina triedenie, výber triedenie, vkladanie sort. A to, čo bolo pekné i len ako stručne a čisto môžete vyjadriť. A to, čo sme si povedali, že je to horná viazaný na bežiaci čas zlúčenie triediť? Jo? 

Divákov: n log n? 

SPEAKER 1: n log n, vpravo. n log n. A vrátime sa k tomu, čo to v skutočnosti znamená, alebo kde to pochádza, ale toto bolo lepšie než akej doby chodu ktoré sme videli na bubliny Výber a vkladanie triediť? Tak n na druhú. n na druhú je väčšie ako to, A aj keď to nie je úplne zrejmé, viem, že log n je menšie ako n, takže ak to n-krát niečo menšie ako n, že to bude menšie ako n na druhú. Je to trochu intuície tam. Ale my sme zaplatili cenu za to. Bolo to rýchlejšie, ale téma, ktoré začalo objavovať minulý týždeň bol tento kompromis. Mám lepší výkon Čas múdry, ale to, čo som musel stráviť na strane druhej ruky, aby bolo dosiahnuté, že? 

DIVÁKOV: Memory. SPEAKER 1: Čože? DIVÁKOV: Memory. SPEAKER 1: Pamäte, alebo miesto všeobecne. A nebolo to výborný zrejmé, s našimi ľuďmi, ale pripomenúť, že naša dobrovoľníkmi boli vykročil vpred a posilnenie späť, aj keď tam je pole tu, a ako by to Druhá pole, ktoré tu by mohli využiť, pretože sme Potrebné niekde zlúčiť tých ľudí. Nemohli sme len vymeniť ich na mieste. Takže zlúčiť triedenie vplyv je priestor, ktorý nemuseli sme sa ďalšie algoritmy, ale Výhodou je, že je to oveľa rýchlejšie. A úprimne povedané, v reálnom svete priestore Tieto days-- RAM, pevný disk space-- je relatívne lacné, a tak to je nie je nevyhnutne zlá vec. 

Takže poďme sa rýchlo pozrieť, trochu viac metodicky, na to, čo sme urobili a prečo povedal, že je n log n. Tak tu je osem čísel a Osem dobrovoľníkov sme mali minule. A prvá vec, ktorá Zlúčiť Zoradiť nám povedal, robiť to, čo? Divákov: Rozdeliť na dve časti. SPEAKER 1: Čože? Divákov: Rozdeliť na dve časti. SPEAKER 1: Rozdeľte na dve časti, vpravo. To je veľmi pripomína telefónny zoznam, rozdeľ a dobyť všeobecnejšie. Takže sme sa pozreli na ľavej polovici. A potom raz sme si povedali, triedenie ľavá polovica z prvkov, čo sme ďalšie povedať? Zoradiť ľavú polovicu vľavo polovica, ktorá nám umožnila, Po rozdelení na dve časti, zamerať sa na štyri a dve. 

Ako zoradiť zoznam teraz, žltá, veľkosti dvoch, pomocou Merge Sort? No rozdeliť ho na polovicu, a zoradiť ľavú polovicu. A to bolo miesto, kde sa veci mám trochu hlúpy krátko. Ako zoradiť zoznam, ktorý je z veľkosť jedného, ​​ako tu toto číslo štyri? Je radené. Máte hotovo. 

Ale ako si zoradiť zoznam Veľkosť jedného, ​​keď je to číslo dva? No, to isté, ale teraz to, čo bolo Tretím a kľúčovým krokom pri zlúčení Zoradiť? Vy ste mali zlúčiť ľavej polovica a pravú polovicu. A akonáhle sme urobili, že sme sa zamerali vo štyri sme sa zamerali na dve. Rozhodli sme sa v poriadku, zrejme dva je na prvom mieste, tak sme dali dva vo svojej miesto, nasleduje štyri. A teraz ste si na trochu vzad, a to je druh charakteristiky algoritmu, ako je korešpondencia Triediť vzad v pamäti. Aký bol ďalší línie príbehu? Čo by som mal zamerať na ďalšie? Pravá polovica vľavo polovica, čo je šesť a osem. 

Takže len krok cez to bez hašteriť bod príliš veľa. Šesť a osem, potom šesť je radené, osem je triedený. Spojiť ich dohromady, ako to, a teraz ďalší veľký krok Je, samozrejme, triediť pravú polovicu z Prvý krok tohto algoritmu. Tak sme sa zamerať na jeden, tri, sedem, päť. Ďalej sa zameriavame na ľavej polovici. Ľavá polovica, že pravá polovica že, a potom zlúčiť do jednej a tri. Potom pravú polovicu, potom ľavej polovici nej, potom pravá polovica z nich. Zlúčiť ju, a čo teraz krok zostáva? Zlúčiť veľký ľavej polovice a veľké pravá polovica, takže sa ide tam, potom dve, potom tri, potom štyri, potom päť, šesť a potom, potom sedem, potom osem. 

Takže teraz, prečo sa to nakoniec odhalí, najmä v prípade, n a logaritmy viac všeobecne skôr útek vás, aspoň v nedávnej pamäti? Dobre si všimnite, výška tejto veci. Mali sme osem prvkov, a my sme delí ju dvoma, dvoma, dvoma. Takže log základňu dvaja z ôsmich nám dáva tri. A ver mi, že ak na trochu hmlisté na to. Ale prihlásiť základ dvoch z ôsmich sú tri, tak sme urobili tri vrstvy zlúčenie. A keď sme zlúčili prvky, koľko elementov sa pozrieme na na každom z týchto riadkov? Celkovo n, nie? Vzhľadom k tomu, zlúčiť horný riadok, aj keď sme to po častiach, nakoniec sme kedysi dotkol každé číslo. A v druhom rade, k zlúčenie týchto zoznamov veľkosti dvoch, sme museli raz dotknúť každého prvku. A potom tu naozaj jasne v poslednom rade, sme sa museli dotknúť každého z nich Prvky raz, ale len raz, tak tu leží, potom sa naša n log n. 

A teraz len aby sa veci trochu viac formálne len na chvíľu, ak máte bolo teraz analyzovať toto na akejsi vyššej úrovni a pokúsiť sa rozhodnúť dobre, ako môže ísť o vyjadrenie doba chodu tohto algoritmu len pri pohľade na neho, a nie pomocou sprisahanecké príklad? No, koľko času by ste povedali krok ako je to v žltej bude trvať, ak n <2 návrat? To je veľký O čo? Takže som videl jedného, ​​tak jeden krok, možno dva kroky, pretože je to v prípade, a potom sa vrátiť, ale je to časová konštanta, nie? Tak sme si povedali, O (1), a to ako som si to vyjadriť. T, len sa beh času. n je veľkosť vstupu, tak T (n), len ozdobný spôsob, ako hovoriť beh čas vzhľadom vstup veľkosti n bude na objednávke o konštantnom čase, v O (1). 

Ale inak, čo toto? Ako by ste vyjadriť doba chodu tohto žltou čiarou? T, čo? Môžete trochu podvádzať tú a odpovedz na moju otázku cyklicky. Takže v prípade, že čas beží v Všeobecne len povedať, je T (n). A teraz trochu plaviť sem hovoril, no, proste tak nejako ľavú polovicu, a potom triediť pravú polovicu. Ako môžeme symbolicky reprezentovať doba chodu tohto žltou čiarou? T, čo? Aká je veľkosť vstupu? n po dvoch. Prečo som len povedať, že? A potom je ďalší T (n / 2) a potom znova, keď som zlúčiť dva zotriedené polovice, koľko prvkov idem musieť dotknúť všetkých? n. Takže môžem vyjadriť to, len aby sa trochu fantázie, ako čas beží všeobecne. T (n) je práve bežiaci čas T (n / 2), Plus T (n / 2), vľavo polovica a pravú polovicu, Plus O (n), čo je pravdepodobne n krokov, ale možno, keď som pomocou dvoch prstov, to je dvakrát toľko kroky, ale je to lineárna. Je to nejaký počet krokov To je faktor n, tak by sme mohli vyjadriť to, pretože to. A to je miesto, kde sa budeme plaviť na späť na našej strednej školy z matematiky učebnicu sme, že opakovanie nakoniec skončí rovná to, n krát logn, ak ste skutočne urobiť z matematika viac formálne. 

Tak to je len dva pohľady. Jeden s číselne pevne reprezentatívneho príkladu pomocou ôsmich čísel a ďalšie Všeobecne pohľad na to, ako sme sa tam dostali. Ale čo je naozaj zaujímavé, je opäť tento pojem cyklistiky. Nejsem použitím slučiek. Som trochu definovanie niečo v zmysle sama o sebe, nielen s týmto matematické funkcie, ale aj z hľadiska tohto pseudokódu. Tento kód pseudo rekurzívne v tom, že dva zo svojich línií je v podstate hovorí to go používajú sa k riešeniu menšie Problém menšej veľkosti, a potom znova a znova a znovu, kým sa nám to orezávať až do tejto takzvanej referenčnej prípad. 

Takže poďme sa vlastne nakresliť presvedčivejšia sa-od to takto. Nechaj ma ísť do gedit a vziať pozrite sa na niektoré z dnešného zdrojového kódu, najmä tento príklad tu. Sigma 0, ktorý zrejme dodáva čísla jedna až n. Takže poďme sa pozrieť, čo ich poznajú a neznáme tu. Najprv musíme pár patrí, takže nič nové tam. Prototype. Som trochu zahmlený na to po niekoľkých dňoch, ale to, čo sme si povedali Prototyp funkcie je? Divákov: [nepočuteľné]. SPEAKER 1: Čo je to? Divákov: Oznamujeme to. SPEAKER 1: Oznamujeme to. Takže ste sa učil zvonenie, hej, nie je v skutočnosti vykonávaniu tohto doteraz, ale niekde v tomto súbore, pravdepodobne, sa bude funkcia volaná, čo? Sigma. A to je len sľub, že bude to vyzerať takto. Bude to trvať celé číslo ako input-- a môžem byť konkrétnejší a hovoria, int n --a, že je to chystá vrátiť int, ale bodkočiarka znamená, mm, budem obísť na vykonávanie tohto o niečo neskôr. Opäť platí, že Clang je hlúpy. Je to len bude vedieť, čo poviete, že zhora nadol, takže musíme dať aspoň je to náznak toho, čo je príde. 

Teraz sa pozrime na hlavné tu. Poďme sa prechádzať sem a vidieť, čo hlavné robí. Nie je to tak dlho, funkcie, a v skutočnosti tu konštrukt je oboznámený. Prehlasujem, premenné n, a potom Znovu a znovu som sa obťažovať užívateľa pre kladné celé číslo pomocou vezmi_int, a jediný výstup z tejto slučky Akonáhle užívateľ splnil. Robiť, keď sme použili na obťažovať užívateľa v tomto zmysle. Teraz je to zaujímavé. Prehlasujem, int s názvom "odpoveď". Aj priradiť je návratová hodnota o funkciu nazvanú "sigma". Ja neviem, čo to ešte robí, ale Spomínam si, deklarovať ju pred chvíľou. A potom som okolo v hodnota, ktorú užívateľ zadal, n, a potom som nahlásiť odpoveď. No poďme sa posunúť späť len na chvíľu. Poďme ďalej do tohto adresára, aby sigma 0, a v skutočnosti spustiť tento program a uvidíme, čo sa stane. Takže keď som sa do toho pustite a beh tento program, ./sigma-0, som sa a zadajte pozitívny číslo ako dve, Sigma, ako grécky symbol znamená, je len chystá sčítať všetky čísla od nulu až na dva. Takže 0 plus 1 plus 2. Tak by to malo snáď mi dať 3. To je všetko, čo robí. A podobne, keď som spustiť tento znova a dám mu číslo tri, to je 3 plus 2, tak to je 5 plus 1 by mi šesť. A potom keď som naozaj blázon a začnite písať vo väčších počtoch, to by mi väčšie a väčšie sumy. Takže to je všetko. 

Tak co sigma vyzerá? No, je to celkom jednoduché. To je, ako sme mohli realizovať to za posledných pár týždňov. "Int" bude návratový typ. Sigma je názov, a to trvá Premenná m namiesto n. Zmením to až hore. Potom je to len kontrola zdravý rozum. Uvidíme, prečo za chvíľu. Teraz Prehlasujem ďalšie premenné, suma, inicializovať na nulu. Potom som to pre sláčiky iterácie, zrejme pre prehľadnosť, od i = 1 až na an = m, čo je čo užívateľ zadal, a potom som zvýšiť sumu, ako je tento. A potom sa vrátiť čiastku. 

Takže pár otázok. Raz som nárok na môj komentár, že tento zabraňuje riziku nekonečnej slučke. Prečo by odovzdaním záporného čísla vyvolať potenciálne nekonečnú slučku? 

Divákov: Nikdy dosiahnuť metrov. 

SPEAKER 1: Nikdy nesiahajte m. Ale m je odovzdaný, takže poďme zvážiť jednoduchý príklad. Ak m je odovzdaný do užívateľ ako negatívneho. Bez ohľadu na to hlavné. Hlavné nás chráni pred to taky, takže som len je naozaj anal s sigma sa tiež uistiť, že vstup nemôže byť záporná. Takže, ak m je záporný, niečo negatívne. Čo sa bude diať? No, ja sa chystá inicializáciu jedného, a potom aj bude menej ako alebo rovné m? 

Stand by. To byl-- poďme nie, poďme nix tento príbeh. Nepýtal som sa na túto otázku, pretože riziko, že som sa zmieňovať o sa to nestane, pretože aj je vždy bude mať väčší than-- OK, Aj odvolať na túto otázku. OK. Poďme sa zamerať len na túto časť tu. Prečo ste Prehlasujem, niektoré mimo slučky? Oznámenie o linke 49 som vyhlásil aj vnútri slučky, ale on-line 48 som vyhlásil trochu mimo. Jo. Divákov: [nepočuteľné]. SPEAKER 1: Iste. Takže v prvom rade určite nie chcú deklarovať a inicializovať čiastku na nulový vnútorný slučky na každej iterácii, pretože by to jasne poraziť Účelom sčítaním čísel. Ja by som sa neustále mení hodnota späť na nulu. A tiež to, čo je ďalšie viac tajomný Dôvodom pre toho istého rozhodnutia dizajnu? Jo. 

Divákov: [nepočuteľné]. SPEAKER 1: Presne tak. Chcem sa k nim dostať von slučky príliš na tom, čo online? Na 53. A podľa nášho pravidlo od pár prednášok pred, premenné sú rozsahom, naozaj, na zložené zátvorky, ktoré ich zahŕňajú. Takže ak nemám deklarovať sumu vnútri z týchto vonkajších zložených zátvorkách, Nemôžem použiť v súlade 53. Inak povedané, keď som vyhlásil, suma sem, alebo dokonca v Pre slučku, mohol by som sa dostať ju do 53. Premenná by účinne preč. Takže pár dôvodov tam. Ale teraz sa vráťme a uvidíme, čo sa stane. Takže sigma volaná. Dodáva sa 1 plus 2, alebo 1 plus 2 plus 3 a vráti hodnotu, ukladá ich do odpovede, a printf tu je dôvod, prečo som videl na obrazovke. Tak toto je to, čo nazveme iteračné prístup, kde iterácie len znamená, že pomocou slučky. U slučky, while, robiť, keď slučky, proste robiť niečo znova a znovu a znovu. 

Ale sigma je celkom elegantný funkcie v že som mohol realizovať inak. Čo o tom, ktoré len aby sa trochu v pohode, dovoľte mi, aby som naozaj zbaviť z mnohých rozptýlenie pretože túto funkciu je naozaj veľmi jednoduché. Poďme rezať ho len svojich štyroch hlavných línií a zbaviť sa všetkých pripomienky a zložené zátvorky. To je tak trochu ohromujúce Alternatívne implementácie. Dobre, možno nie ohromujúce, ale je to trochu zvodnejšie, v poriadku, pozrieť sa na to tak oveľa stručnejšie. S iba štyrmi riadky kódu, Prvýkrát som túto kontrolu zdravý rozum. Ak m je menšie ako alebo rovná nula, sigma nemá zmysel. Je to len má byť v v tomto prípade pre kladné čísla, tak som len tak vrátiť nulu ľubovoľne tak, že sme aspoň niektoré takzvané referenčný prípad. 

Ale tu je to krása. Celistvosť tejto myšlienky, dodáva Čísla od 1 po n, m, alebo v tomto prípade, môže byť vykonané podľa druhu absolvovanie babku. No, a čo je súčet 1 až m? No, vieš čo? Je to rovnaké ako súčet m plus súčet 1 až M mínus jedna. Tak vieš čo? Čo je to sigma z m mínus 1? No, ak ste trochu sledovať tento logicky, je to to isté ako M mínus 1 navyše sigma M mínus dva. Takže môžete trochu len-- to je ako, keď ste práve sa snažia otravovať priateľa a oni vás na niečo spýtať, tak nejako odpovedať na otázku, môžete trochu držať okolo babku. Ale čo je kľúčové je, že ak budete mať takže otázka, menšie a menšie, a menšie, ty si nie sa pýtať, čo je to sigma n, čo je sigma o n, čo je sigma n? Pýtate sa, čo je sigma n, čo je sigma n mínus 1, čo je sigma n mínus 2? Nakoniec vaša otázka sa stane čo? Čo je sigma jedného alebo nula, niektoré veľmi malé hodnoty, a akonáhle sa si, že váš priateľ, nebudete sa opýtať opäť rovnaká otázka, ste len chcel povedať, oh to je nula. Skončili sme hrať tento druh z hlúpe cyklické hry. 

Takže rekurzia je akt v programovaní z funkcie volá sama seba. Tento program, ktorý pri kompilácii a spustenie je bude správať presne rovnakým spôsobom, ale to, čo je kľúčové je, že vo vnútri o funkciu nazvanú sigma, je riadok kódu pričom Hovoríme sami, ktoré by za normálnych okolností bolo zlé. Napríklad, čo najskôr, ak I zostavil toto, takže sa sigma-- aby sigma 1 ./sigma-1. Kladné celé číslo, prosím, 50 1275. Takže to, čo je funkcia Zdá sa, že byť, na základe jedného testu, správne. Ale čo keď mám trochu nebezpečné a odstrániť takzvanú základné veci, a len povedať, tak som len robiť to zložitejšie, než to je. Povedzme, výpočet sigma tým, že m a potom sa pridá v sigma m mínus jedna? No, a čo sa bude diať tu? Poďme oddialiť. Poďme prekompilovať program, uložiť, prekompilovať program, a teda pripravený ./sigma 1 priblíženia, zadajte kladné číslo, prosím, 50. Koľko z vás je ochotných na Fess až keď videl, že? 

OK. Tak toto sa môže stať pre celý rad dôvodov, a úprimne povedané, tento týždeň sme o tom, aby vám viac z nich. Ale v tomto prípade sa pokúste rozum späť čo by sa tu stalo? Chyba segmentácie, povedali sme posledný čas, označuje segment pamäte. Niečo zlé sa stalo. Ale čo to bolo mechanicky to pokazilo tu kvôli môjmu odstráneniu tejto takzvanej základné veci, kde som sa vrátil pevne hodnotu? Čo si myslíte, že sa stalo? Jo. 

Divákov: [nepočuteľné]. SPEAKER 1: Ah. Dobrá otázka. Takže veľkosť čísla že som sa sčítaním bol tak veľký, že je prekročená veľkosť pamäte. To je dobrý nápad, ale nie zásadne chystá spôsobiť pád. To by mohlo viesť k pretečeniu celého čísla, kde bity len otočiť a potom sme sa mylne naozaj veľký číslo ako záporné číslo, ale to samo o sebe nespôsobí pád. Pretože na konci deň int je stále 32 bitov. Vy nebudete náhodne ukradnúť 33. bit. Ale dobrá myšlienka. Jo. 

Divákov: [nepočuteľné]. SPEAKER 1: Metóda nikdy zastaví, a naozaj to tak nazýva znova a znova a znova a znova a znova, a nikto z tie funkcie vôbec dokončiť, pretože ich jediným riadku Kód vlastného života volá znova a znova a znovu. A čo je naozaj sa tu deje, a teraz sme môže druh čerpať to obrazne. Nechajte ma prejsť do obraz na chvíľu. To je obraz, ktorý nakoniec zhmotniť podrobnejšie o tom, čo sa deje vnútornej pamäte vášho počítača. A ukázalo sa, že na Spodná časť tohto obrázku je niečo, čo nazýva zásobník. To je kus pamäti, kus pamäte RAM, to je len použiť kedykoľvek funkcia sa nazýva. Kedykoľvek, programátor, volanie funkcie, operačný systém, ako je Mac OS, Windows, alebo Linux, chytí banda bajtov, možno pár kilobajtov, možno pár megabajtov pamäti, odovzdá ich pre vás, a potom sa nechá môžete spustiť funkciu pomocou bez ohľadu na premenné, ktoré potrebujete. A ak si potom volať ďalšie funkcie a ďalšie funkcie, dostanete ďalší kus pamäte a ďalšie plátok pamäti. 

A skutočne, ak je týchto zelených zásobníkov od Annenberg predstavujú, že pamäť, tu je to, čo sa stane prvou keď budete volať funkciu sigma. Je to ako dávať zásobník takhle na to, čo je najprv prázdny zásobník. Ale potom keď je tento zásobník volá sám, aby som tak povedal, volá ďalšiu inštanciu sigma, je to ako sa pýtať, operačný systém, ooh, potrebujú trochu viac pamäte, daj mi to. A potom sa to dostane nahromadí na na vrchole. Ale to, čo je kľúčom je, že Prvý zásobník je stále tu, preto, že použil tento druhý zásobník. Teraz medzitým sigma sigma volanie, To je ako pýtať sa na viac pamäte. Dostane nahromadí na sem. sigma volať Sigma, to je ďalšia zásobník, ktorý sa nahromadí na tu. A ak budete mať, čo robíme, nakoniec, druh máp táto vizuálna tohto grafu, čo sa deje na stane s hromadou misiek? To bude vyššia ako výška pamäte má váš počítač. A akonáhle ekologickým zásobníka presahuje vodorovnú čiaru nad komínom a nad to slovo hromady, ktoré sa vrátime v budúcnosti, to je zlá vec. Halda je iný segment pamäte, a keď si nechať tieto zásobníky hromada a hromada na, budete prekročiť vlastný segment pamäte, a program je naozaj chystá k havárii. 

Teraz ako stranou, túto myšlienku rekurzia, teda jasne viesť k problémom, ale to nie je nevyhnutne zlá vec. Vzhľadom k tomu, zvážiť, po všetci, Jak-- a možno to trvá nejaký čas zvykať na --how elegantné alebo ako jednoduché že vykonávanie sigma je. A my nebudeme používať rekurzia tak moc v CS50, ale v CS51, a naozaj ktorákoľvek trieda kde sa manipulovať dátové štruktúry ako sú stromy, alebo rodinné stromy, ktoré majú určitú hierarchiu, je to super, super užitočné. Teraz, rovnako ako stranou, aby vás ako začínajúci počítačoví experti sú oboznámení s niektorými z Google je vnútri vtipy, ak idete na Google a pozrieť sa, čo je definície, povedzme, rekurzia, zadajte. Uh-huh. Ako stranou, vytiahol som pár. To je ako 10 minút otáľania dnes ráno. Ak sa vám tiež Google "nakrivo" oznámenia nakláňaním hlavu slightly-- a toto je možná tých najdesivejších zo všetkých pretože niekto strávil ako ich deň vykonávanie tohto niekoľko rokov ago-- poď. Oh, počkaj to je chyba. 

Tak beží na jednom z najväčšia svetová stránky sú tieto hlúpe veľkonočné vajíčka. Pravdepodobne konzumujú netriviálne počet riadkov kódu len preto, že môžeme mať malé zábavné veci, ako že. Ale aspon teraz dostanete niektoré z týchto vnútri vtipy. 

Teraz sa poďme pozrieť na niektoré z White Lies sme hovorili neskoré, a začať lúpať späť niektoré vrstvy technicky takže si naozaj pochopiť, čo sa deje a môžete pochopiť, niektoré z hrozieb, ako Shellshock, že sa teraz začínajú byť Na čele každého z nás pozornosť, prinajmenšom v médiách. Takže tu je veľmi jednoduchá funkcia že sa vráti nič neplatné. Jeho meno je odkladacia. Trvá dvoch premenných a vráti nič. Berie na A a B .. Tak rýchlo demonštrácie. Vzali sme to hore. Mohli by sme tiež vziať trochu zlomiť tu len na chvíľu a mať niečo na pitie. Ak niekto by mi nevadilo spojenie me up na chvíľu tu. Ako sa o vás v gaštanovo hnedej košeli? Poď hore. Len jeden dnes. Ďakujem, aj keď. Tak jo, a máme prísť, kto tu? Ako sa voláte? 

SPEAKER 4: Laura. 

SPEAKER 1: Laura. Poď hore. Takže Laura, veľmi jednoduchá výzva dnes. Nice to meet yo. V poriadku. Takže máme trochu mlieka sem a máme nejaký pomarančový džús sem a niektoré poháre, ktoré sme požičal si od Annenberg dnes. 

SPEAKER 4: Požičal. SPEAKER 1: A bude pokračovať a dá vám pol pohára tohto. V poriadku. A my vám dáme polovice pohár mlieka. Jo, a len tak, že môžete spomenúť, čo to bolo, ako, Spomenul som si, aby to a dnes. Dobre. Ak vám to nebude vadiť, pozrime sa, my je dať na svoje vlastné okuliare ak chcete. Bude to svet z Laurových očí. V poriadku. Takže váš cieľ, vzhľadom k tomu dva šálky Tu kvapalina, mlieko a pomarančový džús, je prehodiť obsah tak, aby sa pomarančová šťava ide do šálky mlieka a ide do mlieka pomarančový džús šálka. 

SPEAKER 4: Dostanem jedna šálka? SPEAKER 1: Som rád, že sa pýtaš, keď bolo by to oveľa lepšie zábery ak ste sa nepýtal. Ale áno, môžeme ponúknuť tretiny kalich je prázdna, samozrejme. V poriadku. Takže vymeniť obsah tam. Very nice. Veľmi dobre. Robíš to pozoruhodne opatrne. A krok tri. V poriadku. Výborne. Veľký potlesk by bolo dobré pre Lauru. V poriadku. Máme malý darček na rozlúčku pre vás, ale dovoľte mi, aby som to. Ďakujem moc. Tak jednoduchý príklad, aj keď, dokázať, že ak si Chcete meniť obsah z dvoch nádob, alebo hovorme im premenné, budete potrebovať nejaké dočasné uskladnenie inscenovať jednu z obsahu v rozsahu, v že môžete skutočne urobiť swap. Takže naozaj, tento zdrojový kód tu v C je predstaviteľom presne to. V prípade, že pomarančový džús bol a mlieko Bol b, a my sme chceli vymeniť dve, môžete skúsiť niečo kreatívneho naliatím do seba, ale to asi nie koniec obzvlášť dobre. A tak sme sa použiť tretina šálky, hovor to tmp, T-M-P konvencií, a dať obsah EÚ v tom, že potom vymeniť jednu šálku, potom dal OJ do Originálny pohár, čím sa dosiahnutie, presne tak, ako Laura urobila, swap. 

Takže poďme robiť presne to. Nechaj ma ísť napred a otvoriť up príklad, ktorý je vlastne hovorí "nie vymeniť, "pretože to nie je ako jednoducho urobiť, ako by ste si mohli myslieť. Takže v rámci tohto programu, zistíte, že Ja používam stdio.h naša stará známa. Mám prototyp odkladací priestor tam, čo znamená, že jej realizácia je asi dole, a pozrime sa, čo to hlavné Program bude robiť pre mňa. Prvý Prehlasujem, int x dostane jeden, a int y dostane dva. Takže myslíte, že z tých, čo vestníku a mlieka, resp. A potom som sa printf hovoriť x je to a y je to, len tak môžem vizuálne vidieť, čo sa deje. Potom som printf tvrdí že som prečerpanie dva, a potom som vytlačiť tvrdia, že to vymenili, a ja znovu vytlačiť x a y. Takže tu v swap presne to, čo Laura urobila, a presne to, čo sme videli na obrazovka pred chvíľou. 

Tak poďme do toho a bude veľmi sklamaný. Nenechajte výmenu a spustiť žiadny swap, priblíženie na výstupe tu. Zadajte x 1, y je 2, swapping prehodené. x je stále 1, a y je ešte 2. Takže aj keď, úprimne povedané, to vyzerá presne páči, aj keď technicky, čo Laura urobila, nezdalo sa, že práca. Tak prečo to je? No, ukázalo sa, že pri napíšeme program, ako je tento ktorá oba hlavné, zdôraznil tu a potom ďalšie funkcie, ako odkladací priestor, tu zdôraznené, ktoré volá, svet vyzerá niečo ako Tieto zásobníky pred chvíľou. Keď hlavný najprv volaná, To je ako pýtať sa operačný systém o trochu pamäte pre akýkoľvek miestny premenných, ako je x a y, ktoré má hlavné, a skončí tady. Ale ak hlavná hovory prepínať, a hlavné prechádza vymeniť dva argumenty, A a B, pomarančový džús a mlieko, to nie je ako podal pomarančový džús a mlieko Laure. Čo robí počítač, je to odovzdá kópie pomarančového džúsu a kópie mlieka Laura, aby sa čo je nakoniec vnútri tohto zásobníka je jedna hodnota, a dva, alebo Ú a mlieka, ale ich kópie, tak, že v tomto bode v príbehu, tam je EÚ a mlieko v každej z týchto zásobníkov. K dispozícii je jedna a dve v každej z týchto zásobníkov, a funkcie odkladacie skutočne funguje. Je to vymení je vnútri z druhej najvyššej zásobníka, ale že odkladanie nemá žiadny vplyv. A na základe len niektoré Základným princípom máme hovoril o skôr, a síce pred pár minút, čo by mohlo vysvetliť, prečo zmeny a b vnútri swapu nemá žiadny vplyv na x a y, aj keď Prešiel som x a y na funkciu pamäti. Čo je kľúčové slovo tu, že môže zjednodušene vysvetliť? Myslím, že je tu som počul? DIVÁKOV: Return. SPEAKER 1: Návrat? Nevráti. Poďme s jedným iný. Čo je to? 

Divákov: [nepočuteľné]. 

SPEAKER 1: OK, takže sme mohli return-- aby spiatočnej práca v príbehu, ale tam je ešte jednoduchšie vysvetlenie. DIVÁKOV: Scope. SPEAKER 1: Rozsah platnosti. Vezmem rozsahu. Takže rozsah, si spomenúť, kde Naše x a y vyhlásil. Sú deklarované vnútri z hlavnej až tu. a, b, zatiaľ, sú fakticky vyhlásil vnútri odkladací priestor, nie celkom Zložené zátvorky, ale stále vo všeobecnej časti swapu. A tak skutočne, a ab existujú len v rámci tohto zásobníka z Annenberg, toto Druhý kus kódu. Takže sme naozaj mení kópiu, ale to nie je naozaj všetko, že užitočné. 

Takže poďme sa pozrieť na to trochu nižšej úrovni. Chystám sa vrátiť do Source Directory, a ja budem prvý priblížiť tu, a len potvrdiť, že som v tomto väčšie okno terminálu, Program sa stále chová takto. Predpokladajme teraz, že tento nie je úmyselné. Jasne som chcel výmenu na práce, takže je to ako chyba. Teraz som mohol začať pridávať veľa printf rokov na mojom kódu, vytlačiť x sem, y po tu, tu, b sem. Ale úprimne povedané, to je asi to, čo si robil za pár týždňov Teraz, v úradných hodinách a doma pri práci na psets sa snažia nájsť nejaké chyby. Ale uvidíte, ak ste tak už neurobili, že problém nastaviť tri vás zoznámi k príkazu názvom GDB, kde GDB, GNU debugger, má sama veľa funkcie, ktoré môžu v skutočnosti aby sme pochopili situáciu takto, ale presvedčivo, riešiť problémy a nájsť chyby. Tak idem na to. Namiesto toho, aby ./noswap som miesto bude bežať GDB ./noswap. Inými slovami, budem bežať môj Program nie je Bash, náš nový priateľ dnes. Chystám sa spustiť môj Program noswap vnútri tohto iného programu s názvom GDB, ktorý je debugger, ktorý je program, ktorý je navrhnutý tak, aby Vy ľudia nájsť a odstrániť chyby. Takže keď som narazila Spustiť tu, je tu ukrutný množstvo textu že naozaj nikdy nebudete musieť čítať. Je to v podstate rozptýlenie z príkazového riadku, ktorý Chystám sa udrieť Control-L dostať sa na tam hore. To je výzva GDB. Ak chcem spustiť tento program teraz pretože tento malý ťahák na dnešné snímka naznačuje, Run je prvá príkazy, ktoré nám chcel predstaviť. A ja som jednoducho ísť s typom bežať až tu vnútri GDB, a naozaj to bežal môj program. Teraz tam je nejaký ďalší výstupy na obrazovku, ako je táto, ale to je len GDB je análny a hovoriť nám, čo sa deje. Tie naozaj nemajú na starosti o týchto údajov práve teraz. Ale to, čo je naozaj v pohode GDB, ak je to urobiť again-- Control-L vymaže screen-- nechaj ma ísť dopredu a typu "break hlavné," tým, keď som stlačte klávesu Enter, nastavenie, čo je volal zlom v noswap.c, riadok 16, ktorý je tam, kde GDB prišiel môj program v skutočnosti je moja funkcia je v skutočnosti. To budeme ignorovať teraz ale to je adresa v pamäti špecificky tejto funkcie. Takže teraz, keď typ som bežať, Všimnite si, čo je v pohode tu. Môj program vypukne v riadku I povedal GDB pozastaviť výkon na. Takže nemám teraz zmeniť svoj kód, pridať nejaké printf je, prekompilovať to, repríza to, zmeniť, pridať nejaké printf je, uložiť, prekompilovať ho spustiť. Môžem len prejsť môj program krok za krokom za krokom pri ľudskou rýchlosťou, nie na Intel-vnútri druhu rýchlosti. 

Takže teraz všimnete tento riadok Tu sa zobrazí, a keď som sa vrátiť do môjho programu v gedit, Všimnite si, že to je v skutočnosti Prvý riadok kódu. K dispozícii je rad 16 v gedit. K dispozícii je rad 16 v GDB, a dokonca aj aj keď tento čierny a biely rozhrania nie je zďaleka tak užívateľ priateľský, to znamená, že že linka 16 nebol vykonaný ešte, ale je to o tom, že je. Takže vlastne keď som typ tlače x, nie printf, len print x, Mám nejakú falošnú hodnotu tam nula, pretože x nebol doteraz inicializovaný. Takže budem písať ďalej, alebo, ak máte Chcete byť fantázie, len n na ďalšie. Ale keď som typ budúci vstúpiť, teraz Všimnite si, že sa pohybuje na linke 17. Takže logicky, ak som popravený riadok 16 a teraz napíšte print x, čo by som mal vidieť? One. 

A teraz je to síce mätúce. 2 dolárov je len ozdobný spôsob, ak máte chcete odkázať na túto hodnotu vyššiu, môžete povedať "dolár podpísať dva." Je to ako odkaz späť. Ale teraz, jednoducho ignorovať. Čo je zaujímavé je to, čo je vpravo od rovnítka. A teraz keď som písať ďalší zase a tlač y, mal by som vidieť dva. Môžem teraz tiež vytlačiť x znova, a úprimne povedané, keď som stále trochu zmätená, tam, kde som, môžem písať zoznam pre zoznam a jednoducho vidieť nejaký kontext okolo bod Vlastne som na. A teraz môžem písať Ďalšie, a tam je 1 x. Teraz píšem ďalej. Oh, y je 2. A opäť, je to mätúce, pretože výstup GDB je je pomiešané s vlastnou výstup. Ale ak budete mať na mysli tým, že pozrel sa tam a späť na váš kód alebo ktorým ju z boku po boku možno budete vidieť, že v skutočnosti som len krokovanie môjho programu. 

Všimnime si ale, čo sa bude diať ďalej, a to doslova. Tu je linka 22. Nechaj ma ísť cez neho, čím sa posúva o na 23, a keď som vytlačiť x teraz ešte jeden. A keď som vytlačiť y teraz ešte jeden. Takže to nie je vhodné cvičenie. Takže poďme zopakovať to. Dovoľte mi, aby som sa vrátiť do opäť hore a typ beh. A to hovorí program ktorý je ladený začala už začal od začiatku. Áno, poďme to urobiť znova. A tentoraz poďme robiť ďalej, ďalšie, ďalšie, ďalšie, ďalšie, ale teraz sa veci zaujímavé. Teraz chcem vstúpiť do Swap, takže si nemyslím, písať ďalej. Píšem krok, a teraz si toho skočil mi do noswap.c linke 33. Ak sa mám vrátiť do gedit, čo je riadok 33? To je prvý skutočný riadok kódu vnútri swapu. Čo je pekné, pretože teraz môžem druh hrabať okolo seba a dostať zvedavý o tom, čo sa deje naozaj tam. Dovoľte mi, aby som vytlačiť tmp. Whoa. Prečo tmp mať niektoré blázon, falošné odpadky hodnota? Divákov: To nebol inicializovaný. SPEAKER 1: To nebol inicializovaný. A skutočne, pri spustení programu, ste dostal veľa pamäte operačným systémom, ale neboli inicializované žiadne hodnoty, Takže bez ohľadu na bity ste videl sem, aj keď je to tento šialený veľký negatívny číslo, jednoducho znamená, že to sú zvyšky z niektoré predchádzajúce využitie tejto pamäte RAM, aj keď nemám ja ho potreboval ešte. Takže teraz idem do toho pustite a typ ďalšie, a keď som teraz písať tlačové tmp, čo by som mal vidieť? Či už je hodnota bola je prvý argument, len ako X bol prvý čo boli prenesené do, tak a x by mala byť rovnaká, tak tlačiť tmp by mi vytlačiť jeden. 

Takže to, čo uvidíte v problémovej sady tri je výukový program svojho druhu na GDB, ale si uvedomiť, že toto je začiatok z pohľadu na nástroj, ktorý bude skutočne pomôcť pri riešení problémov tak oveľa efektívnejšie. Čo sme nakoniec robiť v stredu sa začne lúpať o niekoľko vrstiev a odstrániť niektoré tréningové kolesá. To, čomu sa hovorí reťazec, ktorý sme dlhšiu dobu používať, ideme pomaly brať preč od vás a začať hovoriť o niečo ezoterického známy ako char *, ale budeme to urobiť pekný a najprv mierne, aj keď ukazovatele, ako sa im hovorí, môžete urobiť nejaké veľmi zlé veci, ak by bol zneužitý, pri pohľade na malú claymation od náš priateľ Nick Parlante zo Stanforde University, profesor v počítači vedy, ktorý dal dohromady tento náhľad toho, čo je príde túto stredu. 

[PREHRÁVANIE] Hej, Binky. Prebuď sa. Je čas na ukazovateľ zábavy. 

Čo je to? Ďalšie informácie o ukazovateli? Oh, dobrota! [END Videoprehrávanie] SPEAKER 1: To na vás čaká v stredu. Uvidíme sa potom. [PREHRÁVANIE] -A Teraz, hlboké myšlienky, od Daven Farnham. 

Prečo sa učíme C? Prečo nie +? 

[SMIECH] 

[END Videoprehrávanie]