>> [Přehrávání hudby]
>> SPEAKER 1: Tak jo, to je CS50, a to je začátek čtvrtého týdne
a jak jste možná slyšeli nebo číst, byl svět končí.
Chystáte se na celém internetu byl znalosti a povědomí
chyby v programu, což je programovací jazyk s názvem Bash.
To bylo nádherně značkové jako Shellshock nebo dveře Bash,
ale předměty, jako jsou tyto nebyly neobvyklé.
A ve skutečnosti, mnoho z nich, aby vzpomínky Heartbleed,
které jste si možná všimli v stiskněte znovu letos na jaře, což
byl podobně docela dramatický.
Teď ti z vás dnes, kolik z vás,
i když nechápu, co je to všechno o, slyšel Shellshock?
Dobře, a kolik z vás mají počítače, které jsou zranitelné?
OK, měl by tam být daleko, daleko více rukou právě teď, z důvodů, které jsou vidět.
>> Pojďme se podívat na to, co je se děje v médiích
A pak se to trochu vysvětlit pro nás technicky.
>> SPEAKER 2: Bezpečnostní experti mají varoval, že vážná chyba by mohla
asi ovlivnit stovky miliony světových internetových uživatelů.
Takže co přesně je chyba, že to bylo daboval Shellshock, a co to dělá?
No, Shellshock je také známý jako Bash chyba, software je využívá.
Hackeři používají virus skenování zranitelné systémy běží Linux a Unix
operační systémy a infikovat je.
Bash je příkazový řádek shellu.
To umožňuje uživatelům vydávat příkazy ke spuštění programy a funkce v softwaru
zadáním textu.
To je obvykle používán programátory a by neměla být otevřena vůči okolnímu světu,
když Shellshock změny, které.
>> No, worringly, někteří analytici varují, že může být větší hrozbou,
protože Shellshock umožňuje kompletní ovládání infikovaného stroje,
vzhledem k tomu, Heartbleed povoleno pouze hackeři špehovat na počítačích.
Je to tak vážné, že je to byla hodnocena v 10 z 10
k závažnosti podle vnitrostátních Databáze zranitelnost.
2/3 ze všech webových serverů jsou rizik, včetně některých počítačích se systémem Mac.
No, ujistěte se, že opravit své systémy nyní.
Každý hosting webových stránek v chodu postižené operační systémy
by měly přijmout opatření co nejdříve.
Každý, kdo si může dovolit to mělo vypadat jejich sledování a webové aplikace
firewally dávat pozor na případné útoky.
SPEAKER 3: Nejhorší věc že by se mohlo stát, je
že by někdo napsat kód, který se automaticky přepne a skenování
internet a bude mít vliv na všech těchto počítačů.
A když to dělají dobře, Nejhorší věc, kterou mohl udělat
je jen odstranit vše, nebo zavřel místa dolů.
Takže jsme mohli vidět poškození z tohoto úhlu pohledu,
kde budeme mít škodlivé lidí kteří se jen rozhodnout, že způsobí katastrofu
tím, že systémy, dolů nebo odstranění soubory, a podobné věci.
SPEAKER 2: Někteří říkají, že je to jeden z nejobtížnějších měřit
chyby v letech, a to může trvat týdny nebo dokonce
měsíců k určení jeho konečného dopadu.
>> SPEAKER 1: Takže všechno je to pravda, ale legrační věc je, téměř všechny
Užívání metafor jste právě viděli, s výjimkou snad klávesnici,
nemá nic společného s bug vůbec.
Servery a dráty a tak dále, je to trochu tangenciálně souvisejících
ale v jádru je to vlastně docela zná to, co se tady děje.
Ve skutečnosti, nechte mě jít do naše CS50 spotřebiče.
Nech mě jít napřed a maximalizovat okno terminálu zde.
A vy jste pomocí tohoto, nebo vložený verze této smlouvy,
v gedit, aby se psát programy, typ příkazy, a tak dále,
a to je ve skutečnosti, a má už několik týdnů, Bash, B-A-S-H.
To je Bourne-again shell, což je jen ozdobný způsob, jak říkat,
To je program, který má blikání rychlé, efektivní,
že sedí tam čeká pro vstup pro vás.
A je to příkaz řádky, přes které
vy jste byla spuštěna příkazů a nakonec kompilaci a spuštěním
programy.
>> Ale Bash je také programování jazyk v následujícím smyslu.
Víte, že existují příkazy, jako je cd a ls i zvonit a další,
ale můžete definovat vlastní příkazy od jejich zavádění do Bash.
Teď už nebudeme jít do skvělého detailu
jako Bash programovací jazyk, ale Víte, například, že v současné době,
tam žádný příkaz s názvem "Ahoj."
Takže to lze nalézt v jeden z těchto balíčků.
Není nainstalován na mém počítači.
Zeptejte se na správce systému.
Ale pokud chci tam být program s názvem "ahoj" v bash nebo na mé výzvy,
Mohu skutečně používat syntaxi, která je docela jako C. Není to úplně stejné,
ale vypadá to docela podobné funkce, i když chybí některé detaily.
Se zdánlivě nic neděje, ale teď když jsem napsat "ahoj"
, můžete vytvořit programu, a to v jazyce C, a to v jazyce Java,
ne v jiném programování jazyk, ale v Bash sám.
>> Nyní je zde klíčové je, že jsem napsal Jméno Chtěl jsem, aby tento nový příkaz,
a závorky jsou také symbolický což je funkce.
Mimochodem, můžete si také udělat legraci věci, a ve skutečnosti, a to i na Mac OS,
To je program s názvem Terminal.
Je dodáván vestavěný do kohokoli počítač, který má Mac v této místnosti,
a můžete dělat podobné věci v Mac OS, ale můžete jít víc než to.
A to je trochu tangenciální, ale je to docela legrace.
Připomněl jsem si dnes ráno, když myslí si, díky,
na malou hru jsem hrával s jedním z CS50 bývalých TFs
kdy kdykoli by odejít z Jeho klávesnice s jeho obrazovku odemknout,
Já bych spustit příkaz jako tohle-- "pozdravit."
A teď nějaký čas se vrátil k jeho klávesnice, co jsem vyčistil obrazovku
a on by si sednout, pokusit se udělat nějakou práci,
vypsat obsah jeho directory--
>> [Přehrávání zvuku]
>> Ahoj.
Dobrý den.
>> SPEAKER 1: Takže, v spravedlnosti, to není ve skutečnosti "ahoj."
Bylo to obvykle něco více podobný že--
[Přehrávání zvuku]
-Beep.
SPEAKER 1: začaly uznávat takzvané I would-- tak jeho počítač by
nadávat na něj, kdykoli se mu vlastně se posadil na jeho klávesnici.
A velmi rychle přišel na to nenechávat jeho obrazovka odemčena.
Ale to naznačuje, že druh z hloupé zábavy, která vás
může mít něco jako Bash.
Ale je to trochu víc vážně, aby bylo jasno, než to.
A ve skutečnosti, to je jeden z nejnebezpečnější a dlouhotrvající chyby
že opravdu zasáhla svět po celém světě.
Tato chyba byla asi pro asi 20 roků,
a budete udeřil v několika okamžik jeho relativní jednoduchost.
>> Tak tohle je reprezentativní příkaz, že pokud
vlastní Mac, doslova hned Když máte otevřené víko,
můžete zkusit psát do toho program s názvem Terminal.
Terminál je pod Aplikace Utilities--
jednou, uživatelé Windows nemusíte starat o tomto threat--
ale ti z vás s počítači Mac můžete zadat to do okna, jako to udělám tady,
a pokud nechcete psát že do tohoto programu
Terminál, jako já budu dělat teď, když vidíte slovo "zranitelný",
váš počítač náchylné k vykořisťování.
>> Teď co to vlastně znamená?
A to je pravda někteří dost šílené syntax,
ale pojďme alespoň vytáhnout některé ze zajímavých aspektů.
Takže tam je nějaká syntaxe, která vypadá trochu zná, alespoň z C
a programování obecně.
Vidím nějaké závorky, středníky, složené závorky, a takové,
ale ukázalo se, že tento hloupost zde ve žluté barvě
je v podstatě funkce že nedělá nic.
Dvojtečka znamená nedělat nic, a středník znamená přestat dělat nic.
Takže uvnitř nich složené závorky, skutečnost,
že mám rovné přihlásit se vlevo, to
je v podstatě vytváří příkaz, nebo proměnná,
nazvaný x a přiřazením ta žlutá část kódu tam.
To by mohlo být něco jako "echo ahoj "nebo" říkají pípnutí ", nebo tak něco
podobný tomu.
Povšimněme si ale, pokud vaše oči dále putovat na pravé straně,
tam je více k této čáře, než jen konec této středníkem.
"Echo zranitelný", a pak Kromě toho je tu ještě víc.
Další středník, bash-c :.
>> Tak dlouhý příběh krátký, tento řádek kódu je
dostatečná pro přesvědčivé Počítač, který je
citlivé na něco že chcete to dělat,
protože tam je chyba v Bash, kdy i když Bash měl zastavit
čtení řádků příkazu vpravo tam po žluté textu,
na 20 a navíc rok stará chyba, Bash skutečně četl
po tomto středníkem a hezká hodně dělá to, co je řečeno.
>> Takže to, co je to důsledek z toho nakonec?
Jen jsem řekl, "echo ahoj" nebo "echo zranitelné,"
ale co když jste něco ve skutečnosti škodlivý, jako rm -rf *
které jste možná ne kdy napsal dříve,
a upřímně řečeno, pravděpodobně neměli příliš brzy,
protože můžete dělat Mnoho škod s ním.
Proč?
rm co dělá, samozřejmě?
Odstraňuje.
* Znamená co?
Vše.
Takže je to tak-zvané divoká karta, tak to znamená, že
smazat vše aktuální adresář.
r se děje tak, že znamená rekurzivní, což znamená, že pokud to, co jste smazání
je adresář, a uvnitř tam je další soubory a další adresáře,
rekurzivně ponořit do ještě a odstranit všechno.
A f je nejhorší ze všech.
Každý, kdo ví, co f zde znamená?
Force.
Takže nutit prostředky, a to i jestli je to dobrý nápad,
to aniž by mě výzva Pro další potvrzení.
Takže, víte, my smát , ale upřímně řečeno, asi bych
Tento typ vícekrát den, protože skutečnosti
je, že je to nejrychlejší způsob, jak odstranit spoustu věcí.
Ale i já jsem udělal nějakou škodu.
>> Ale pokud jste byli na trik počítač do definování nějaké stupidní proměnné
nebo volání funkce x, ale pak podvádět počítače do provádění
za hranice, které funkce nad rámec tohoto středníkem,
můžete opravdu trik počítač k vykonání něco jako rm -rf
nebo příkaz E-mail nebo příkaz Kopírovat.
Cokoliv doslova můžete dělat s počítač, ať už je to mazání souborů,
vytváření souborů, spamy někoho, útočí na nějaké serveru vzdáleně,
pokud můžete vyjádřit s příkazem, je
může přimět počítač, aby dělali to.
>> Teď, co je příklad , jak by to mohlo dělat?
No, je tu spousta počítačů na internet tekoucí Bash.
Všichni uživatelé, abychom Mac jsou mezi nimi.
Mnoho linuxových serverů patří mezi je také, a servery Unix.
Windows opět dostane relativně vyvěšený
Pokud jste nainstalovali speciální software.
Teď hodně serverů, pro instance, spustit webové servery,
a ve skutečnosti Linux je možná nejoblíbenější operační systém
aby mohlo běžet na počítačích na internetu které se servírují stránky.
Nyní, jak uvidíme později, v semestru, kdy
odešlete žádost Váš browser-- Chrome,
Internet Explorer, whatever-- na vzdáleném serveru,
Ukazuje se, že i když jste právě zadali www.example.com,
Váš prohlížeč odeslání zprávy to je trochu tajemný, jako je tento.
>> Ale všimněte si něco podivného.
První dva řádky Nikdy jsem neviděl,
ale nevypadají zvláště ohrožující.
Ale všimněte, co jsem ukradl na třetím řádku zde.
Je-li špatný člověk měl poslat zprávu takhle ze svého počítače
na zranitelné Mac nebo zranitelný server Linux,
Legrační je, že Bash, že jednoduchý malý příkazový řádek,
je všudypřítomný a je často použitý v podstatě provést
obsah zprávu, která se mu věnuje.
A tím, že logika, můžete trik webový server, proto,
zasláním něco jako User-Agent, který obvykle
má říkat název vašeho prohlížeče.
User-Agent Chrome, User-Agent Internet Explorer, User-Agent Firefox, tento
je prostě váš prohlížeč je způsob ztotožňuje.
Ale když padouch velmi chytře říká, mm-mm, já jsem
Není ti to říct co můj prohlížeč,
Já místo toho bude ti to poslat mystický vypadající věc s rm -rf
* V ní můžete doslova trik zranitelné webový server na internetu
v provedení přesně, že v tam pro smazání všech souborů.
A upřímně řečeno, to není i to nejhorší.
Můžete dělat cokoliv.
Dalo by se začít distribuované odmítnutí služby útoku
pokud jsi poslal tuto zprávu celé svazky webových serverů
a pak nechal všechny sestoupit, pro instance na serverech Harvard.edu,
a můžete seřadit Bang sakra z nich
o provozu na síti, který byl jinak vyvolána tímto špatný chlap.
>> Tak dlouhý příběh krátký, téměř všichni v této místnosti, kdo vlastní Mac
Je citlivá na to.
Dobrou zprávou je, že pokud jste běží webový server na vašem notebooku,
a pokud jste skutečně nakonfigurován to, aby něco takového SSH do toho,
jste opravdu v bezpečí.
To je zranitelný, ale není kdo se snaží dostat do vašeho notebooku,
takže můžete trochu jisti.
Nicméně, Apple brzy bude aktualizovat opravu to.
Svět Linuxu již vydala počet oprav pro Fedora a Ubuntu
a další verze Linux, a opravdu Pokud spustíte aktualizaci 50 v zařízení,
dokonce, že taky bude aktualizována a opravena.
Že ale příliš nemá opravdu byl zranitelný,
protože pokud jste pohráli si se spotřebičem
a dělal váš notebook veřejně dostupné na internetu, což není
Ve výchozím nastavení, vy jste ve skutečnosti bylo v pořádku, protože
z firewall a dalších technik.
>> Ale je to extrémní příklad chyby že jsme žili za doslova 20
let, a kdo ví, jestli se někdo Celou tu dobu se ví o tom?
A ve skutečnosti, to je jeden z základní problémy
že uvidíme později semestr o bezpečnost,
je to, že stejně jako v reálném světě, dobří jsou v nevýhodě.
Chcete-li zachovat padouchy ven, musíme Ujistěte se, že všechny dveře jsou zamčené,
že každé okno je bezpečný, že každý bod vstupu do domu
je bezpečný, aby padouchy ven.
Ale to, co dělá špatný člověk musí to skutečně ohrozit váš domov
a krást od vás?
On nebo ona prostě musí najít ten, odemčený dveře, jeden rozbité okno, nebo tak něco
v tomto směru, a to je Totéž se v oblasti počítačové bezpečnosti.
Můžeme psát miliony řádky programového kódu
a utrácet stovky nebo tisíce hodin, se snaží, aby si to v pořádku,
ale pokud uděláte jen jeden chyba ve správnosti,
si můžete dát celý systém a skutečně v tomto případě celý internet
a svět v ohrožení.
>> Takže pokud byste se chtěli dozvědět více o tom, přejděte na následující adresu zde.
Není třeba akci dnes večer, pokud jste
mezi ty klidnější, že Byly běží vlastní web
serveru, v tom případě byste měli, ve skutečnosti, aktualizovat software.
>> I to je název řeč, a nyní papír,
že jsme svázána Webové stránky hřiště je pro dnešek vše.
Bylo by kolegy jmenoval Ken Thompson, který
bylo přijetí velmi slavný Ocenění ve vědě o počítačích,
a dal tuto řeč o několik let Před podstatě na stejné téma.
Žádat lidi otázka, měli byste opravdu
důvěra, nakonec, Software, který jste dostali?
Například, my všichni máme bylo psaní programů,
a my jsme byli sestavování je s Clang.
A své znalosti, jste napsal všechny programy pro CS50 tam, kde je
zadní dveře druhů, existuje způsob, jak že padouch, pokud běží program,
mohl převzít vašem počítači?
Asi ne, že jo?
Mario a Greedy a Credit.
To vše jsou docela malé programy.
Musel byste být dost špatné, pokud jste skutečně
dělal celý počítač zranitelný po napsání 10 nebo 20 řádků kódu,
nebo alespoň vědomi některých bezpečnostních důsledků.
Teď říkám, že bodře, ale budeme vidět dnes
a tento týden je to vlastně opravdu, ale opravdu snadné
být špatný, a aby ještě krátké programy zranitelné.
>> Ale teď, alespoň si uvědomit, že tato otázka je sem pozval
je o Clang v kompilátoru.
Proč jsme se věřit zvonění za poslední dva nebo tři týdny?
Kdo může říci, že ten, kdo psal zvonění neměl "kdyby" podmínku, že
že v podstatě injekčně nějaké nuly a ty do každého programu, sestavuje
že by ho nechal, nebo její přístup počítač, když jsi spal
a vaše víko notebooku je otevřena a počítač se systémem?
Je to tak?
Máme tento druh čest systému práva Nyní, pokud věříme, že Clang je důvěryhodně.
Věříte, že spotřebič je důvěryhodně.
Věříte, že doslova každý program, na počítači Mac nebo PC je důvěryhodný.
A jak tento jednoduchý chyba naznačuje, i když to není škodlivý,
to rozhodně není pravděpodobné, že tomu tak je.
>> Takže byste měli bát jako čert.
Upřímně řečeno, není jednoduché Roztok se tento druhý
než jakési společenské povědomí z rostoucí složitosti
že stavíme na vrcholu našich počítačových systémů,
a jak se stále více zranitelnější bychom mohli být docela dobře.
>> Nyní se, že řekl, Breakout.
Takže Breakout je problém nastavit tři a Breakout je hra z dávných dob
které by vás mohly vyvolat, ale pro nás problém nastavit tři,
to nám umožňuje, aby se věci zpět do zářezu
tak, že když píšeme programy, i v terminálovém okně, jako je tento,
můžeme skutečně spustit, nakonec, grafické programy ne
Na rozdíl od těch, které jsme měli přístup v Scratch.
Tak tohle je na zaměstnance je realizace Breakout,
což je právě tato cihla-lámání hra, že se pohybujete pádlo zpět
a tam, a odpálil míček před těmi barevnými cihlami až nahoře.
Takže to je, že nás trochu zpátky tam, kde
jsme byli schopni se velmi rychle Scratch, a teď s C,
, kterým se provádí vlastní grafická uživatelská rozhraní.
>> Ale víc než to, že tento Problém set představuje první
ve které dáváme Jste banda kódu.
A ve skutečnosti, já uvedu explicitní pozornost na to, protože zejména
Pro ty méně příjemné, to problém nastavit, alespoň na první pohled,
se bude cítit jako udělali jsme ji do zářezu.
Vzhledem k tomu, že jsme vám dal, Pro některé z hledání
a třídění problémy v pset, banda kódu, který jsme napsali,
a pár komentářů které říkají "dělat,"
kde budete muset vyplnit prázdná místa.
Takže ne příliš děsivé, ale je to poprvé,
jsme podal vám kód, který je třeba nejprve přečíst, pochopit a pak se přidají do
a dokončit ji.
>> A pak Breakout, budeme dělat totéž,
která vám několik desítek více linek kódu, který, upřímně řečeno, aby vám
hodně rámce pro hra, ale zastavit před
prováděcích cihly a míč a pádlo,
ale my realizovat některé další funkce.
A dokonce, že na první pohled, znovu, zejména v případě méně pohodlné,
Mohlo by se zdát obzvláště skličující a si myslíte, že je tak mnoho nových funkcí
budete muset zabalit svou mysl kolem, a je to pravda.
Ale mějte na paměti, že je to docela jako Scratch.
Kurz jste nepoužili všechny že kousky skládačky na začátku.
Kurz jste se nestaral zabalit vaše mysl asi všichni
protože vše, co se to Letmý pohled pochopit, oh,
že to, co se dá dělat s tímto kousek puzzle.
A skutečně, v problému nastavení 3 spec, budeme bod,
v dokumentaci, která bude Představujeme Vám některých nových funkcí,
a nakonec programování konstruuje, který používáte.
Podmínky, smyčky, proměnné a funkce
bude stejná jako to, co jsme viděli doposud.
>> Takže opravdu, co dáme vám je nějaký ukázkový kód, který
vám umožní vytvořit okno který vypadá ne na rozdíl od toho
a nakonec přeměnit ji na něco takového, jako toto.
Takže využít CS50, diskutovat úřední hodiny a více,
a útěchu v tom, že množství kódu musíte napsat
ve skutečnosti není tak moc.
Prvním úkolem je jen aklimatizovat sami nějaký kód jsme napsali.
>> Jakékoliv dotazy týkající se pset3, Shellshock, nebo jinak?
>> Diváků: Zdálo se, že prochází s Breakout
že kód je téměř objektově-orientovaný styl,
ale myslím, že C je objektově-orientovaný program.
SPEAKER 1: výborná otázka.
Takže při pohledu přes distribuce kód, kód
jsme napsali pro pset3, Pro ty, kteří znají, ho
Vypadá to, že je to trochu objektově-orientovaný.
Stručná odpověď je, že to je.
Je to přiblížení na to, jak mohli dělat objektově-orientovaný kód pomocí
jazyk C, ale to je ještě nakonec procedurální.
Tam jsou umístěny uvnitř žádné metody proměnné, jak uvidíte.
Ale připomíná to.
A uvidíme, tuto funkci znovu až se dostaneme do PHP a JavaScript
ke konci semestru.
Ale teď, myslím, že na to, jak náznak toho, co je přijde.
Dobrá otázka.
V pořádku.
Takže sloučení trochu bylo, jak jsme se levá věci minule.
A sloučit druh byl cool in pocit, že je to tak mnohem rychlejší,
alespoň na základě zběžné testy jsme dělali minulý týden, než, řekněme, bublina
třídění, výběr třídění, vkládání sort.
A to, co bylo hezké i jen jak stručně a čistě
můžete vyjádřit.
A to, co jsme si řekli, že je to horní vázán na běžící čas sloučení
třídit?
Jo?
>> Diváků: n log n?
>> SPEAKER 1: n log n, vpravo. n log n.
A vrátíme se k tomu, co to ve skutečnosti znamená, nebo kde to pochází,
ale toto bylo lepší než jaké doby chodu
které jsme viděli na bubliny Výběr a vkládání třídit?
Tak n na druhou. n na druhou je větší než to,
A i když to není zcela zřejmé, vím, že log n je menší než n,
takže pokud to n-krát něco menší než n,
že to bude menší než n na druhou.
Je to trochu intuice tam.
Ale my jsme zaplatili cenu za to.
Bylo to rychlejší, ale téma, které začalo objevovat minulý týden byl tento kompromis.
Mám lepší výkon Čas moudrý, ale to, co
jsem musel strávit na straně druhé ruce, aby bylo dosaženo, že?
>> DIVÁKŮ: Memory.
SPEAKER 1: Cože?
DIVÁKŮ: Memory.
SPEAKER 1: Paměti, nebo místo obecně.
A nebylo to výborný zřejmé, s našimi lidmi,
ale připomenout, že naše dobrovolníky byly vykročil vpřed a posílení
zpět, i když tam je pole tady, a jako by to
Druhá pole, které zde by mohly využít, protože jsme
Potřebné někde sloučit ty lidi.
Nemohli jsme jen vyměnit je na místě.
Takže sloučit třídění vliv je prostor, který
nemuseli jsme se další algoritmy,
ale Výhodou je, že je to mnohem rychlejší.
A upřímně řečeno, v reálném světě prostoru Tyto days-- RAM, pevný disk space--
je relativně levné, a tak to je není nutně špatná věc.
>> Takže pojďme se rychle podívat, trochu více metodicky, na to, co jsme udělali
a proč řekl, že je n log n.
Tak tady je osm čísel a Osm dobrovolníků jsme měli minule.
A první věc, která Sloučit Seřadit nám řekl, dělat to, co?
Diváků: Rozdělit na dvě části.
SPEAKER 1: Cože?
Diváků: Rozdělit na dvě části.
SPEAKER 1: Rozdělte na dvě části, vpravo.
To je velmi připomíná telefonní seznam, rozděl
a dobýt obecněji.
Takže jsme se podívali na levé polovině.
A pak jednou jsme si řekli, třídění levá polovina z prvků,
co jsme další říci?
Seřadit levou polovinu vlevo polovina, která nám umožnila,
Po rozdělení na dvě části, zaměřit se na čtyři a dvě.
>> Jak seřadit seznam nyní, žlutá, velikosti dvou, pomocí Merge Sort?
No rozdělit jej na polovinu, a seřadit levou polovinu.
A to bylo místo, kde se věci mám trochu hloupý krátce.
Jak seřadit seznam, který je z velikost jednoho, jako tady toto číslo čtyři?
Je řazeny.
Máte hotovo.
>> Ale jak si seřadit seznam Velikost jednoho, když je to číslo dvě?
No, to samé, ale nyní to, co bylo Třetím a klíčovým krokem při sloučení Seřadit?
Vy jste měli sloučit levé polovina a pravou polovinu.
A jakmile jsme udělali, že jsme se zaměřili ve čtyři jsme se zaměřili na dvě.
Rozhodli jsme se v pořádku, zřejmě dva je na prvním místě,
tak jsme dali dva ve své místo, následuje čtyři.
A teď jste si na trochu vzad, a to je druh charakteristiky
algoritmu, jako je korespondence Třídit vzad v paměti.
Jaký byl další linie příběhu?
Co bych měl zaměřit na další?
Pravá polovina vlevo polovina, což je šest a osm.
>> Takže jen krok přes to bez hašteřit bod příliš mnoho.
Šest a osm, pak šest je řazeny, osm je tříděn.
Spojit je dohromady, jako to, a teď další velký krok
Je, samozřejmě, třídit pravou polovinu z První krok tohoto algoritmu.
Tak jsme se zaměřit na jeden, tři, sedm, pět.
Dále se zaměřujeme na levé polovině.
Levá polovina, že pravá polovina že, a pak sloučit do jedné a tři.
Pak pravou polovinu, potom levé polovině ní, pak pravá polovina z nich.
Sloučit ji, a co teď krok zůstává?
Sloučit velký levé poloviny a velké pravá polovina, takže se jde tam,
pak dvě, pak tři, pak čtyři, pak pět, šest a pak, pak sedm, pak osm.
>> Takže teď, proč se to nakonec odhalí, zejména v případě, n a logaritmy více
obecně spíše útěk vás, alespoň v nedávné paměti?
Dobře si všimněte, výška této věci.
Měli jsme osm prvků, a my jsme dělí ji dvěma, dvěma, dvěma.
Takže log základnu dva z osmi nám dává tři.
A věř mi, že pokud na trochu mlhavé na to.
Ale přihlásit základ dvou z osmi jsou tři, tak jsme udělali tři vrstvy sloučení.
A když jsme sloučili prvky, kolik elementů
se podíváme na na každém z těchto řádků?
Celkem n, ne?
Vzhledem k tomu, sloučit horní řádek, i když jsme to po částech,
nakonec jsme kdysi dotkl každé číslo.
A v druhé řadě, k sloučení těchto seznamů velikosti dvou,
jsme museli jednou dotknout každého prvku.
A pak tu opravdu jasně v poslední řadě,
jsme se museli dotknout každého z nich Prvky jednou, ale jen jednou,
tak zde leží, pak se naše n log n.
>> A teď jen aby se věci trochu více formální jen na chvíli, pokud máte
bylo nyní analyzovat toto na jakési vyšší úrovni
a pokusit se rozhodnout dobře, jak může jít o vyjádření
doba chodu tohoto algoritmu jen při pohledu na něj, a ne
pomocí spiklenecký příklad?
No, kolik času byste řekli krok jako je to v žluté bude trvat,
pokud n <2 návrat?
To je velký O co?
Takže jsem viděl jednoho, tak jeden krok, možná dva kroky, protože je to v případě,
a pak se vrátit, ale je to časová konstanta, ne?
Tak jsme si řekli, O (1), a to jak jsem si to vyjádřit.
T, jen se běh času.
n je velikost vstupu, tak T (n), jen ozdobný způsob, jak
říkat běh čas vzhledem vstup velikosti n
bude na objednávce o konstantním čase, v O (1).
>> Ale jinak, co tohle?
Jak byste vyjádřit doba chodu tohoto žlutou čárou?
T, co?
Můžete trochu podvádět tu a odpověz na mou otázku cyklicky.
Takže v případě, že čas běží v Obecně jen říct, je T (n).
A teď trochu plavit sem říkal, no, prostě tak nějak levou polovinu,
a pak třídit pravou polovinu.
Jak můžeme symbolicky reprezentovat doba chodu tohoto žlutou čárou?
T, co?
Jaká je velikost vstupu?
n po dvou.
Proč jsem jen říct, že?
A pak je další T (n / 2) a pak znovu, když jsem sloučit dva setříděné poloviny,
kolik prvků jdu muset dotknout všech?
n.
Takže můžu vyjádřit to, jen aby se trochu fantazie,
jak čas běží obecně.
T (n) je právě běžící čas T (n / 2), Plus T (n / 2), vlevo polovina a pravou polovinu,
Plus O (n), což je pravděpodobně n kroků, ale možná, když jsem pomocí dvou prstů,
to je dvakrát tolik kroky, ale je to lineární.
Je to nějaký počet kroků To je faktor n,
tak bychom mohli vyjádřit to, protože to.
A to je místo, kde se budeme plavit na zpět na naší střední školy z matematiky učebnici
jsme, že opakování nakonec skončí rovná to, n krát log n,
pokud jste skutečně udělat z matematika více formálně.
>> Tak to je jen dva pohledy.
Jeden s číselně pevně reprezentativního příkladu
pomocí osmi čísel a další Obecně pohled na to, jak jsme se tam dostali.
Ale co je opravdu zajímavé, je opět tento pojem cyklistiky.
Nejsem použitím smyček.
Jsem trochu definování něco ve smyslu sama o sobě,
nejen s tímto matematické funkce,
ale také z hlediska tohoto pseudokódu.
Tento kód pseudo rekurzivní v tom, že dva ze svých linií
je v podstatě říká to go používají se k řešení menší
Problém menší velikosti, a pak znovu a znovu
a znovu, dokud se nám to ořezávat až do této takzvané referenční případ.
>> Takže pojďme se vlastně nakreslit přesvědčivější se-od to takto.
Nech mě jít do gedit a vzít podívejte se na některé z dnešního zdrojového kódu,
zejména tento příklad zde.
Sigma 0, který zřejmě dodává čísla jedna až n.
Takže pojďme se podívat, co je znají a neznámé zde.
Nejprve musíme pár patří, takže nic nového tam.
Prototype.
Jsem trochu zamlžený na to po několika dnech,
ale to, co jsme si řekli Prototyp funkce je?
Diváků: [neslyšitelné].
SPEAKER 1: Co je to?
Diváků: Oznamujeme to.
SPEAKER 1: Oznamujeme to.
Takže jste se učil zvonění, hej, není ve skutečnosti provádění tohoto dosud,
ale někde v tomto souboru, pravděpodobně, se bude funkce volána, co?
Sigma.
A to je jen slib, že bude to vypadat takto.
Bude to trvat celé číslo jako input-- a můžu být konkrétnější
a říkají, int n --a, že je to chystá vrátit int,
ale středník znamená, mm, budu obejít k provádění tohoto o něco později.
Opět platí, že Clang je hloupý.
Je to jen bude vědět, co řeknete, že shora dolů,
takže musíme dát alespoň je to náznak toho, co je přijde.
>> Nyní se podívejme na hlavní zde.
Pojďme se procházet sem a vidět, co hlavní dělá.
Není to tak dlouho, funkce, a ve skutečnosti zde konstrukt je obeznámen.
Prohlašuji, proměnné n, a pak Znovu a znovu jsem se obtěžovat uživatele
pro kladné celé číslo pomocí vezmi_int, a jediný výstup z této smyčky
Jakmile uživatel splnil.
Dělat, když jsme použili k obtěžovat uživatele v tomto smyslu.
Nyní je to zajímavé.
Prohlašuji, int s názvem "odpověď".
I přiřadit je návratová hodnota o funkci nazvanou "sigma".
Já nevím, co to ještě dělá, ale Vzpomínám si, deklarovat ji před chvílí.
A pak jsem kolem v hodnota, kterou uživatel zadal, n,
a pak jsem nahlásit odpověď.
No pojďme se posunout zpět jen na chvíli.
Pojďme dál do tohoto adresáře, aby sigma 0, a ve skutečnosti spustit tento program
a uvidíme, co se stane.
Takže když jsem se do toho pusťte a běh tento program, ./sigma-0,
jsem se a zadejte pozitivní číslo jako dvě, Sigma,
jako řecký symbol znamená, je jen chystá sečíst všechna čísla od
nulu až na dva.
Takže 0 plus 1 plus 2.
Tak by to mělo snad mi dát 3.
To je všechno, co dělá.
A podobně, když jsem spustit tento znovu a dám mu číslo tři,
to je 3 plus 2, tak to je 5 plus 1 by mi šest.
A pak když jsem opravdu blázen a začněte psát ve větších počtech,
to by mi větší a větší částky.
Takže to je všechno.
>> Tak co sigma vypadá?
No, je to docela jednoduché.
To je, jak jsme mohli realizovat to za posledních pár týdnů.
"Int" bude návratový typ.
Sigma je název, a to trvá Proměnná m místo n.
Změním to až nahoře.
Pak je to jen kontrola zdravý rozum.
Uvidíme, proč za chvíli.
Teď Prohlašuji další proměnné, částka, inicializovat na nulu.
Pak jsem to pro smyčce iterace, zřejmě pro přehlednost,
od i = 1 až na an = m, což je co uživatel zadal, a pak jsem
zvýšit částku, jako je tento.
A pak se vrátit částku.
>> Takže pár otázek.
Jednou jsem nárok na můj komentář, že tento zabraňuje riziku nekonečné smyčce.
Proč by předáním záporného čísla vyvolat potenciálně nekonečnou smyčku?
>> Diváků: Nikdy dosáhnout metrů.
>> SPEAKER 1: Nikdy nesahejte m.
Ale m je předán, takže pojďme zvážit jednoduchý příklad.
Pokud m je předán do uživatel jako negativního.
Bez ohledu na to hlavní.
Hlavní nás chrání před to taky, takže jsem jen
je opravdu anal s sigma se také ujistit,
že vstup nemůže být záporná.
Takže, pokud m je záporný, něco negativního.
Co se bude dít?
No, já se chystá inicializaci jednoho,
a pak i bude méně než nebo rovno m?
>> Stand by.
To byl-- pojďme ne, pojďme nix tento příběh.
Neptal jsem se na tuto otázku, protože riziko, že jsem se zmiňovat o
se to nestane, protože i je vždy bude mít větší than-- OK,
I odvolat na tuto otázku.
OK.
Pojďme se zaměřit pouze na tuto část zde.
Proč jste Prohlašuji, některé mimo smyčky?
Oznámení o lince 49 jsem prohlásil i uvnitř smyčky,
ale on-line 48 jsem prohlásil trochu mimo.
Jo.
Diváků: [neslyšitelné].
SPEAKER 1: Jistě.
Takže v první řadě určitě ne chtějí deklarovat a inicializovat částku
na nulový vnitřní smyčky na každé iteraci,
protože by to jasně porazit Účelem sečtením čísel.
Já bych se neustále mění hodnota zpět na nulu.
A také to, co je další více tajemný Důvodem pro téhož rozhodnutí designu?
Jo.
>> Diváků: [neslyšitelné].
SPEAKER 1: Přesně tak.
Chci se k nim dostat ven smyčky příliš na tom, co online?
Na 53.
A podle našeho pravidlo od pár přednášek před,
proměnné jsou rozsahem, opravdu, na složené závorky, které je zahrnují.
Takže pokud nemám deklarovat částku uvnitř z těchto vnějších složených závorkách,
Nemohu použít v souladu 53.
Jinak řečeno, když jsem prohlásil, částka sem, nebo dokonce v
Pro smyčku, mohl bych se dostat ji do 53.
Proměnná by účinně pryč.
Takže pár důvodů tam.
Ale teď se vraťme a uvidíme, co se stane.
Takže sigma volána.
Dodává se 1 plus 2, nebo 1 plus 2 plus 3 a vrátí hodnotu,
ukládá je do odpovědi, a printf zde je důvod, proč jsem viděl na obrazovce.
Tak tohle je to, co nazveme iterační přístup, kde iterace jen
znamená, že pomocí smyčky.
U smyčky, while, dělat, když smyčky, prostě dělat něco znovu
a znovu a znovu.
>> Ale sigma je docela elegantní funkce v že jsem mohl realizovat jinak.
Co o tom, které jen aby se trochu v pohodě,
dovolte mi, abych opravdu zbavit z mnoha rozptýlení
protože tuto funkci je opravdu velmi jednoduché.
Pojďme řezat ho jen svých čtyř hlavních linií
a zbavit se všech připomínky a složené závorky.
To je tak trochu ohromující Alternativní implementace.
Dobře, možná ne ohromující, ale je to trochu svůdnější, v pořádku,
podívat se na to tak mnohem stručněji.
S pouhými čtyřmi řádky kódu, Poprvé jsem tuto kontrolu zdravý rozum.
Je-li m je menší než nebo rovna nula, sigma nemá smysl.
Je to jen má být v v tomto případě pro kladná čísla,
tak jsem jen tak vrátit nulu libovolně
tak, že jsme aspoň některé takzvané referenční případ.
>> Ale tady je to krása.
Celistvost této myšlenky, dodává Čísla od 1 do n, m, nebo v tomto případě,
může být provedeno podle druhu absolvování babku.
No, a co je součet 1 až m?
No, víš co?
Je to stejné jako součet m plus součet 1 až M minus jedna.
Tak víš co?
Co je to sigma z m mínus 1?
No, pokud jste trochu sledovat tento logicky, je to to samé jako M minus 1
navíc sigma M minus dva.
Takže můžete trochu jen-- to je jako, když jste právě
se snaží otravovat přítele a oni vás na něco zeptat,
tak nějak odpovědět na otázku, můžete trochu držet kolem babku.
Ale co je klíčové je, že pokud budete mít takže otázka, menší a menší,
a menší, ty jsi ne se ptát, co je to sigma
n, co je sigma o n, co je sigma n?
Ptáte se, co je sigma n, co je sigma
n minus 1, co je sigma n mínus 2?
Nakonec vaše otázka se stane co?
Co je sigma jednoho nebo nula, některé velmi malé hodnoty,
a jakmile se si, že váš přítel,
nebudete se zeptat opět stejná otázka,
jste jen chtěl říct, oh to je nula.
Skončili jsme hrát tento druh z hloupé cyklické hry.
>> Takže rekurze je akt v programování z funkce volá sama sebe.
Tento program, který při kompilaci a spuštění je bude chovat přesně stejným způsobem,
ale to, co je klíčové je, že uvnitř o funkci nazvanou sigma,
je řádek kódu přičemž Říkáme sami,
které by za normálních okolností bylo špatné.
Například, co nejdříve, pokud I sestavil toto, takže se sigma--
aby sigma 1 ./sigma-1.
Kladné celé číslo, prosím, 50 1275.
Takže to, co je funkce Zdá se, že být, na základě jednoho testu, správné.
Ale co když mám trochu nebezpečné a odstranit takzvanou základní věci,
a jen říct, tak jsem jen dělat to složitější, než to je.
Řekněme, výpočet sigma tím, že m a pak se přidá
v sigma m mínus jedna?
No, a co se bude dít tady?
Pojďme oddálit.
Pojďme překompilovat program, uložit, překompilovat program,
a tedy připraven ./sigma 1 přiblížení, zadejte kladné číslo, prosím, 50.
Kolik z vás je ochotno na Fess až když viděl, že?
>> OK.
Tak tohle se může stát pro celá řada důvodů,
a upřímně řečeno, tento týden jsme o tom, aby vám více z nich.
Ale v tomto případě se pokuste rozum zpět
co by se tu stalo?
Chyba segmentace, řekli jsme poslední čas, označuje segment paměti.
Něco špatného se stalo.
Ale co to bylo mechanicky to pokazilo
zde kvůli mému odstranění této takzvané základní věci,
kde jsem se vrátil pevně hodnotu?
Co si myslíte, že se stalo?
Jo.
>> Diváků: [neslyšitelné].
SPEAKER 1: Ah.
Dobrá otázka.
Takže velikost čísla že jsem se sečtením
byl tak velký, že je překročena velikost paměti.
To je dobrý nápad, ale ne zásadně chystá způsobit pád.
To by mohlo vést k přetečení celého čísla, kde bity jen otočit
a pak jsme se mylně opravdu velký číslo jako záporné číslo,
ale to samo o sobě nezpůsobí pád.
Protože na konci den int je stále 32 bitů.
Vy nebudete náhodně ukrást 33. bit.
Ale dobrá myšlenka.
Jo.
>> Diváků: [neslyšitelné].
SPEAKER 1: Metoda nikdy zastaví,
a opravdu to tak nazývá znovu a znovu a znovu a znovu
a znovu, a nikdo z ty funkce vůbec
dokončit, protože jejich jediným řádku Kód vlastního života volá znovu a znovu
a znovu.
A co je opravdu se tu děje, a teď jsme
může druh čerpat to obrazně.
Nechte mě projít do obraz na chvíli.
To je obraz, který nakonec zhmotnit
podrobněji o tom, co se děje vnitřní paměti vašeho počítače.
A ukázalo se, že na Spodní část tohoto obrázku
je něco, co nazývá zásobník.
To je kus paměti, kus paměti RAM,
to je jen použít kdykoliv funkce se nazývá.
Kdykoliv, programátor, volání funkce,
operační systém, jako je Mac OS, Windows, nebo Linux,
chytne banda bajtů, možná pár kilobajtů, možná pár megabajtů
paměti, předá je pro vás, a pak se nechá
můžete spustit funkci pomocí bez ohledu na proměnné, které potřebujete.
A pokud si pak volat další funkce a další funkce,
dostanete další kus paměti a další plátek paměti.
>> A skutečně, pokud je těchto zelených zásobníků od Annenberg představují, že paměť,
tady je to, co se stane první když budete volat funkci sigma.
Je to jako dávat zásobník takhle na to, co je nejprve prázdný zásobník.
Ale pak když je tento zásobník volá sám, abych tak řekl,
volá další instanci sigma, je to
jako se ptát, operační systém, ooh, potřebují trochu více paměti,
dej mi to.
A pak se to dostane nahromadí na na vrcholu.
Ale to, co je klíčem je, že První zásobník je stále tady,
proto, že použil tento druhý zásobník.
Nyní mezitím sigma sigma volání, To je jako ptát se na více paměti.
Dostane nahromadí na sem.
sigma volat Sigma, to je další zásobník, který se nahromadí na zde.
A pokud budete mít, co děláme, nakonec, druh map tato vizuální
tohoto grafu, co se děje na stane s hromadou misek?
To bude vyšší než výše paměti má váš počítač.
A jakmile ekologickým zásobníku přesahuje vodorovnou čáru
nad komínem a nad to slovo hromady, které se vrátíme v budoucnosti,
to je špatná věc.
Halda je jiný segment paměti,
a pokud si nechat tyto zásobníky hromada a hromada na,
budete překročit vlastní segment paměti,
a program je opravdu chystá k havárii.
>> Nyní jako stranou, tuto myšlenku rekurze, tedy
jasně vést k problémům, ale to není nutně špatná věc.
Vzhledem k tomu, zvážit, po všichni, Jak-- a možná
to trvá nějaký čas zvykat na --how elegantní nebo jak jednoduché
že provádění sigma je.
A my nebudeme používat rekurze tak moc v CS50,
ale v CS51, a opravdu kterákoliv třída kde se manipulovat datové struktury
jako jsou stromy, nebo rodinné stromy, které mají určitou hierarchii,
je to super, super užitečné.
Nyní, stejně jako stranou, aby vás jako začínající počítačoví odborníci
jsou obeznámeni s některými z Google je uvnitř vtipy, pokud jdete na Google
a podívat se, co je definice, řekněme, rekurze, zadejte.
Uh-huh.
Jako stranou, vytáhl jsem pár.
To je jako 10 minut otálení dnes ráno.
Pokud se vám také Google "nakřivo" oznámení nakláněním hlavu slightly--
a tohle je možná těch nejděsivějších ze všech
protože někdo strávil jako jejich den provádění tohoto
několik let ago-- pojď.
Oh, počkej to je chyba.
>> Tak běží na jednom z největší světová stránky
jsou tyto hloupé velikonoční vajíčka.
Pravděpodobně konzumují netriviální počet řádků kódu
jen proto, že můžeme mít malé zábavné věci, jako že.
Ale aspoň teď dostanete některé z těchto uvnitř vtipy.
>> Nyní se pojďme podívat na některé z White Lies jsme říkali pozdní,
a začít loupat zpět některé vrstvy technicky
takže si opravdu pochopit, co se děje
a můžete pochopit, některé z hrozeb,
jako Shellshock, že se nyní začínají být
Na čele každého z nás pozornost, přinejmenším v médiích.
Takže tady je velmi jednoduchá funkce že se vrátí nic neplatné.
Jeho jméno je odkládací.
Trvá dvou proměnných a vrátí nic.
Bere na A a B..
Tak rychle demonstrace.
Vzali jsme to nahoru.
Mohli bychom také vzít trochu zlomit tu jen na chvíli
a mít něco k pití.
Pokud někdo by mi nevadilo spojení me up na chvíli tady.
Jak se o vás v kaštanově hnědé košili?
Pojď nahoru.
Jen jeden dnes.
Děkuji, i když.
Tak jo, a máme přijít, kdo tady?
Jak se jmenujete?
>> SPEAKER 4: Laura.
>> SPEAKER 1: Laura.
Pojď nahoru.
Takže Laura, velmi jednoduchá výzva dnes.
Nice to meet yo.
V pořádku.
Takže máme trochu mléka sem a máme nějaký pomerančový džus sem
a některé poháry, které jsme půjčil si od Annenberg dnes.
>> SPEAKER 4: Půjčil.
SPEAKER 1: A bude pokračovat a dá vám půl sklenice tohoto.
V pořádku.
A my vám dáme poloviny sklenici mléka.
Jo, a jen tak, že můžete vzpomenout, co to bylo, jako,
Vzpomněl jsem si, aby to a dnes.
Dobře.
Pokud vám to nebude vadit, podívejme se, my je dát na své vlastní brýle
jestli chcete.
Bude to svět z Laurových očí.
V pořádku.
Takže váš cíl, vzhledem k tomu dva šálky Zde kapalina, mléko a pomerančový džus,
je prohodit obsah tak, aby se pomerančová šťáva jde do šálku mléka
a jde do mléka pomerančový džus šálek.
>> SPEAKER 4: Dostanu jeden šálek?
SPEAKER 1: Jsem rád, že se ptáš, když bylo by to mnohem lepší záběry
pokud jste se neptal.
Ale ano, můžeme nabídnout třetiny kalich je prázdná, samozřejmě.
V pořádku.
Takže vyměnit obsah tam.
Very nice.
Velmi dobře.
Děláš to pozoruhodně opatrně.
A krok tři.
V pořádku.
Výborně.
Velký potlesk by bylo dobré pro Lauru.
V pořádku.
Máme malý dárek na rozloučenou pro vás, ale dovolte mi, abych to.
Děkuji moc.
Tak jednoduchý příklad, i když, prokázat, že pokud si
Chcete měnit obsah ze dvou nádob,
nebo říkejme jim proměnné, budete potřebovat nějaké dočasné uskladnění
inscenovat jednu z obsahu v rozsahu, v že můžete skutečně udělat swap.
Takže opravdu, tento zdrojový kód zde v C je představitelem přesně to.
V případě, že pomerančový džus byl a mléko Byl b, a my jsme chtěli vyměnit dvě,
můžete zkusit něco kreativního nalitím do sebe,
ale to asi ne konec obzvláště dobře.
A tak jsme se použít třetina šálku, hovor to tmp, T-M-P konvencí,
a dát obsah Věst v tom, že pak vyměnit jeden šálek,
pak dal OJ do Originální pohár, čímž se
dosažení, přesně tak, jak Laura udělala, swap.
>> Takže pojďme dělat přesně to.
Nech mě jít napřed a otevřít up příklad, který je
vlastně říká "ne vyměnit, "protože to není
jak jednoduše udělat, jak byste si mohli myslet.
Takže v rámci tohoto programu, zjistíte, že Já používám stdio.h naše stará známá.
Mám prototyp odkládací prostor tam, což
znamená, že její realizace je asi dole,
a podívejme se, co to hlavní Program bude dělat pro mě.
První Prohlašuji, int x dostane jeden, a int y dostane dva.
Takže myslíte, že z těch, co věstníku a mléka, resp.
A pak jsem se printf říkat x je to
a y je to, jen tak mohu vizuálně vidět, co se děje.
Pak jsem printf tvrdí že jsem přečerpání dva,
a pak jsem vytisknout tvrdí, že to vyměnili,
a já znovu vytisknout x a y.
Takže tady v swap přesně to, co Laura udělala,
a přesně to, co jsme viděli na obrazovka před chvílí.
>> Tak pojďme do toho a bude velice zklamán.
Nenechte výměnu a spustit žádný swap, přiblížení na výstupu zde.
Zadejte x 1, y je 2, swapping prohozeny.
x je stále 1, a y je ještě 2.
Takže i když, upřímně řečeno, to vypadá přesně líbí, i když technicky,
co Laura udělala, nezdálo se, že práce.
Tak proč to je?
No, ukázalo se, že při napíšeme program, jako je tento
která oba hlavní, zdůraznil zde a pak další funkce, jako odkládací prostor,
zde zdůrazněno, které volá, svět
vypadá něco jako Tyto zásobníky před chvílí.
Když hlavní nejprve volána, To je jako ptát se operační systém
o trochu paměti pro jakýkoli místní proměnných, jako je x a y, které má hlavní,
a skončí tady.
Ale pokud hlavní hovory přepínat, a hlavní přechází vyměnit dva argumenty, A a B,
pomerančový džus a mléko, to není jako podal pomerančový džus a mléko
Lauře.
Co dělá počítač, je to předá kopie pomerančového džusu
a kopie mléka Laura, aby se co je nakonec uvnitř tohoto zásobníku
je jedna hodnota, a dva, nebo Úř a mléka, ale jejich kopie,
tak, že v tomto bodě v příběhu, tam
je věst a mléko v každé z těchto zásobníků.
K dispozici je jedna a dvě v každé z těchto zásobníků,
a funkce odkládací skutečně funguje.
Je to vymění je uvnitř z druhé nejvyšší zásobníku,
ale že odkládání nemá žádný vliv.
A na základě jen některé Základním principem máme
mluvil o dříve, a sice před pár minut, co
by mohlo vysvětlit, proč změny a b uvnitř swapu
nemá žádný vliv na x a y, i když Prošel jsem x a y na funkci paměti.
Co je klíčové slovo zde, že může zjednodušeně vysvětlit?
Myslím, že je tady jsem slyšel?
DIVÁKŮ: Return.
SPEAKER 1: Návrat?
Nevrátí.
Pojďme s jedním jiný.
Co je to?
>> Diváků: [neslyšitelné].
>> SPEAKER 1: OK, takže jsme mohli return-- aby zpáteční práce v příběhu,
ale tam je ještě jednodušší vysvětlení.
DIVÁKŮ: Scope.
SPEAKER 1: Rozsah platnosti.
Vezmu rozsahu.
Takže rozsah, si vzpomenout, kde Naše x a y prohlásil.
Jsou deklarované uvnitř z hlavní až tady.
a, b, zatím, jsou fakticky vyhlásil
uvnitř odkládací prostor, ne zcela Složené závorky, ale stále
v obecné části swapu.
A tak skutečně, a ab existují pouze v rámci tohoto zásobníku
z Annenberg, toto Druhý kus kódu.
Takže jsme opravdu mění kopii, ale to není opravdu všechno, že užitečné.
>> Takže pojďme se podívat na to trochu nižší úrovni.
Chystám se vrátit do Source Directory,
a já budu první přiblížit tady, a jen
potvrdit, že jsem v tomto větší okno terminálu,
Program se stále chová takhle.
Předpokládejme nyní, že tento není úmyslné.
Jasně jsem chtěl výměnu na práce, takže je to jako chyba.
Teď jsem mohl začít přidávat hodně printf let na mém kódu,
vytisknout x sem, y po tady, tady, b sem.
Ale upřímně řečeno, to je asi to, co jsi dělal za pár týdnů
Nyní, v úředních hodinách a doma při práci
na psets se snaží najít nějaké chyby.
Ale uvidíte, pokud jste tak již neučinili, že problém nastavit tři vás seznámí
k příkazu názvem GDB, kde GDB, GNU debugger,
má sama spoustu funkce, které mohou ve skutečnosti
abychom pochopili situaci takhle, ale přesvědčivě,
řešit problémy a najít chyby.
Tak jdu na to.
Místo toho, aby ./noswap jsem místo bude běžet GDB ./noswap.
Jinými slovy, budu běžet můj Program není Bash, náš nový přítel
dnes.
Chystám se spustit můj Program noswap uvnitř
tohoto jiného programu s názvem GDB, který je debugger, který
je program, který je navržen tak, aby Vy lidé najít a odstranit chyby.
Takže když jsem narazila Spustit tady, je tu ukrutný množství textu
že opravdu nikdy nebudete muset číst.
Je to v podstatě rozptýlení z příkazového řádku, který
Chystám se udeřit Control-L dostat se na tam nahoře.
To je výzva GDB.
Pokud chci spustit tento program nyní protože tento malý tahák na dnešní
snímek naznačuje, Run je první příkazy, které nám chtěl představit.
A já jsem prostě jít s typem běžet až tady uvnitř GDB,
a opravdu to běžel můj program.
Teď tam je nějaký další výstupy na obrazovku, jako je tato,
ale to je jen GDB je anální a říkat nám, co se děje.
Ty opravdu nemají na starosti o těchto údajů právě teď.
Ale to, co je opravdu v pohodě GDB, je-li to udělat again--
Control-L vymaže screen-- nech mě jít dopředu a typu "break hlavní," tím,
když jsem stiskněte klávesu Enter, nastavení, co je volal zlom v noswap.c,
řádek 16, který je tam, kde GDB přišel můj program ve skutečnosti
je moje funkce je ve skutečnosti.
To budeme ignorovat nyní ale to je adresa
v paměti specificky této funkce.
Takže teď, když typ jsem běžet, Všimněte si, co je v pohodě zde.
Můj program vypukne v řádku I řekl GDB pozastavit výkon na.
Takže nemám teď změnit svůj kód, přidat nějaké printf je, překompilovat to, repríza
to, změnit, přidat nějaké printf je, uložit, překompilovat ho spustit.
Mohu jen projít můj program krok za krokem za krokem při lidskou rychlostí,
ne na Intel-uvnitř druhu rychlosti.
>> Takže teď všimnete tento řádek Zde se zobrazí, a když jsem se vrátit
do mého programu v gedit, Všimněte si, že to je ve skutečnosti
První řádek kódu.
K dispozici je řada 16 v gedit.
K dispozici je řada 16 v GDB, a dokonce i i když tento černý a bílý rozhraní
není zdaleka tak uživatel přátelský, to znamená, že
že linka 16 nebyl vykonán ještě, ale je to o tom, že je.
Takže vlastně když jsem typ tisku x, ne printf, jen print x,
Mám nějakou falešnou hodnotu tam nula, protože x nebyl dosud inicializován.
Takže budu psát dál, nebo, pokud máte Chcete být fantazie, jen n na další.
Ale když jsem typ příští vstoupit, nyní Všimněte si, že se pohybuje na lince 17.
Takže logicky, pokud jsem popraven řádek 16 a teď napište print x,
co bych měl vidět?
One.
>> A teď je to sice matoucí.
2 dolarů je jen ozdobný způsob, pokud máte chcete odkázat na tuto hodnotu vyšší,
můžete říct "dolar podepsat dva."
Je to jako odkaz zpět.
Ale teď, prostě ignorovat.
Co je zajímavé je to, co je vpravo od rovnítka.
A teď když jsem psát další zase a tisk y, měl bych vidět dva.
Mohu nyní také vytisknout x znovu, a upřímně řečeno,
když jsem stále trochu zmatená, tam, kde jsem, mohu psát seznam pro seznam
a prostě vidět nějaký kontext kolem bod Vlastně jsem na.
A teď můžu psát Další, a tam je 1 x.
Teď píšu dál.
Oh, y je 2.
A opět, je to matoucí, protože výstup GDB je
je smíšeny s vlastní výstup.
Ale pokud budete mít na mysli tím, že podíval se tam a zpět na váš kód
nebo kterým ji z boku po boku možná budete
vidět, že ve skutečnosti jsem jen krokování mého programu.
>> Povšimněme si ale, co se bude dít dál, a to doslova.
Tady je linka 22.
Nech mě jít přes něj, čímž se posouvá o na 23, a když jsem vytisknout x teď ještě jeden.
A když jsem vytisknout y teď ještě jeden.
Takže to není vhodné cvičení.
Takže pojďme zopakovat to.
Dovolte mi, abych se vrátit do opět nahoře a typ běh.
A to říká program který je laděn
začala již začal od začátku.
Ano, pojďme to udělat znovu.
A tentokrát pojďme dělat dál, další, další, další, další,
ale teď se věci zajímavé.
Teď chci vstoupit do Swap, takže si nemyslím, psát dál.
Píšu krok, a teď si toho skočil mi do noswap.c lince 33.
Mám-li se vrátit do gedit, co je řádek 33?
To je první skutečný řádek kódu uvnitř swapu.
Což je pěkné, protože teď můžu druh hrabat kolem sebe a dostat zvědavý
o tom, co se děje opravdu tam.
Dovolte mi, abych vytisknout tmp.
Whoa.
Proč tmp mít některé blázen, falešné odpadky hodnota?
Diváků: To nebyl inicializován.
SPEAKER 1: To nebyl inicializován.
A skutečně, při spuštění programu, jste dostal spoustu paměti
operačním systémem, ale nebyly inicializovány žádné hodnoty,
Takže bez ohledu na bity jste viděl sem, i když je to
tento šílený velký negativní číslo, prostě znamená,
že to jsou zbytky z některé předchozí využití této paměti RAM,
i když nemám já ho potřeboval ještě.
Takže teď jdu do toho pusťte a typ další, a když jsem teď psát tiskové tmp,
co bych měl vidět?
Ať už je hodnota byla je první argument, jen
jako X byl první co byly přeneseny do,
tak a x by měla být stejná, tak tisknout tmp by mi vytisknout jeden.
>> Takže to, co uvidíte v problémové sady tři je výukový program svého druhu na GDB,
ale si uvědomit, že toto je začátek z pohledu na nástroj, který bude skutečně
pomoci při řešení problémů tak mnohem efektivněji.
Co jsme nakonec dělat ve středu
se začne loupat o několik vrstev a odstranit některé tréninkové kola.
To, čemu se říká řetězec, který jsme delší dobu používat,
jdeme pomalu brát pryč od vás a začít mluvit o
něco esoterického známý jako char *,
ale budeme to udělat pěkný a nejprve mírně, i když ukazatele,
jak se jim říká, můžete udělat nějaké velmi špatné věci, pokud by byl zneužit,
při pohledu na malou claymation od náš přítel Nick Parlante ze Stanfordu
University, profesor v počítači vědy, který dal dohromady tento náhled
toho, co je přijde tuto středu.
>> [PŘEHRÁVÁNÍ]
Hej, Binky.
Probuď se.
Je čas na ukazatel zábavy.
>> Co je to?
Další informace o ukazateli?
Oh, dobrota!
[END VIDEOPŘEHRÁVÁNÍ]
SPEAKER 1: To na vás čeká ve středu.
Uvidíme se pak.
[PŘEHRÁVÁNÍ]
-A Teď, hluboké myšlenky, od Daven Farnham.
>> Proč se učíme C?
Proč ne +?
>> [SMÍCH]
>> [END VIDEOPŘEHRÁVÁNÍ]