>> [MUSIC JOC]
>> SPEAKER 1: Bine, acest lucru este CS50, iar acesta este începutul de patru saptamani,
și cum poate ați auzit sau citit, lumea a fost încheiată.
Mergând tot în jurul pe internet a fost cunoașterea și conștientizarea
de o eroare într-un program, o limbaj de programare numit Bash.
Acest lucru a fost tatuat minunat ca Shellshock, sau ușa Bash,
dar articole ca acestea nu au fost mai puțin frecvente.
De fapt, multe dintre ele aduc amintiri din spate a Heartbleed,
care este posibil să fi observat în apăsați din nou primăvara trecută, care
a fost în mod similar destul de dramatic.
Acum, de cei dintre voi aici astăzi, cât de mulți dintre voi au,
chiar dacă nu înțeleg ce este vorba, a auzit de Shellshock?
Bine, și cât de mulți dintre voi au computere care sunt vulnerabile?
OK, nu ar trebui să fie mult, mult mai multe mâini chiar acum, pentru motive pe care le va vedea.
>> Să aruncăm o privire la ceea ce este se petrece în mass-media
și apoi să explice un pic aici pentru noi punct de vedere tehnic.
>> SPEAKER 2: Experții în securitate au a avertizat că un defect grav ar putea
fie pe cale de a afecta sute de milioane de utilizatori de internet din lume.
Deci, exact ceea ce este bug-ul care a fost numit Shellshock, și ce face?
Ei bine, Shellshock este, de asemenea, cunoscut sub numele de Bash bug, software-ul se exploatează.
Hackerii folosesc virusul pentru a scana vulnerabile sistemele care rulează Linux și Unix
sisteme de operare și apoi le infecta.
Bash este un shell linie de comandă.
Acest lucru permite utilizatorilor aspect comenzi pentru a lansa programe și caracteristici în cadrul software-ului
prin tastarea în text.
Este de obicei folosit de programatori, și nu ar trebui să fie deschis către lume,
deși Shellshock schimba asta.
>> Ei bine, worringly, unii analiști avertizează că ar putea fi o amenințare mai mare,
deoarece Shellshock permite complet controlul asupra unui sistem infectat,
în timp ce Heartbleed permis numai hackeri pentru a spiona pe computere.
Este atât de gravă, că este fost evaluat un 10 din 10
pentru severitate de către National Vulnerabilitate baza de date.
2/3 din toate serverele web sunt la risc, inclusiv unele computere Mac.
Ei bine, asigurați-vă că patch sistemele de acum.
Oricine gazduieste un site web care rulează sistemele de operare afectate
ar trebui să ia măsuri cât mai curând posibil.
Oricine își poate permite ar trebui să arate la cererea lor de monitorizare și web
firewall-uri pentru a privi afară pentru orice atacuri.
SPEAKER 3: Cel mai rău lucru care se poate întâmpla este
că cineva va scrie cod care ar merge în mod automat și scanare
pe internet și ar afecta toate aceste calculatoare.
Și odată ce ei fac asta, bine, cel mai rău lucru pe care ar putea face
este doar șterge totul, sau închide site-urile jos.
Deci, am putea vedea daune din acest punct de vedere,
în cazul în care am avea oameni malware care tocmai a decide de a provoca haos
de sisteme de aducerea în jos sau ștergerea fișiere, și lucruri de genul asta.
SPEAKER 2: Unii spun că aceasta este una dintre cele mai dificile pentru a măsura
bug-uri în ani, și-l poate dura săptămâni sau chiar
luni pentru a determina impactul final.
>> SPEAKER 1: Deci, toate acestea sunt adevărate, dar un lucru amuzant este, aproape toate
de imaginile care tocmai ați văzut, cu excepția, poate, tastatura,
nu are nimic de-a face cu un fel de bug-ul.
Servere și cabluri și așa mai departe, E un fel de tangențial legate,
dar la baza este de fapt destul de familiar ce se întâmplă aici.
De fapt, lasă-mă să intru în aparat noastră CS50.
Lasă-mă să mergeți mai departe și de a maximiza fereastra terminalului aici.
Și voi ați fost folosind acest, sau versiune embedded acestora,
în gedit, în scopul de a scrie programe, tip de comenzi, și așa mai departe,
și aceasta este, de fapt, și are fost de săptămâni, Bash, B-A-S-H.
Aceasta este Bourne-Again Shell, care este doar un mod fantezist de a spune,
acesta este un program care are o clipește rapid, eficient,
că stă acolo de așteptare pentru intrare pentru tine.
Și e comanda linii de interfață prin care
voi au fost difuzate de comenzi și în cele din urmă compilarea și apoi rularea
programe.
>> Dar Bash este, de asemenea, o programare Limba în următorul sens.
Știți că există comenzi, cum ar fi cd și ls și, de asemenea, zăngăni și alții,
dar vă puteți defini propriile comenzi prin punerea în aplicare a acestora în Bash.
Acum, noi nu vom du-te în detaliu
ca pentru a bash limbajul de programare, dar Știu, de exemplu, că în acest moment,
nu exista nici o comandă numit "hello".
Deci, poate fi găsit în unul dintre aceste pachete.
Nu este instalat pe computerul meu.
Întrebați administratorul.
Dar dacă vreau să existe un program de numit "hello" în Bash sau la promptă mea,
Eu pot folosi de fapt sintaxă care este destul ca C. Nu e chiar același lucru,
dar se pare destul de similar cu o funcție, chiar dacă lipsesc unele detalii.
Nimic nu pare să se întâmple, dar acum, dacă am de tip "salut"
puteți scrie de fapt o Programul, nu în C, nu în Java,
nu într-o altă programare limbă, dar în Bash sine.
>> Acum Cheia aici este că am scris nume am vrut să dau această nouă comandă,
și parantezele sunt, de asemenea, simbolic de aceasta fiind o functie.
Ca o paranteza, puteți face, de asemenea, distractiv lucruri, și, de fapt, chiar de pe Mac OS,
acesta este un program numit Terminal.
Ea vine construit în oricui computer care are un Mac în această cameră,
și poți face lucruri similare în Mac OS, dar poti sa te duci mai mult dincolo de asta.
Și acest lucru este un pic tangential, dar e un fel de distracție.
Mi-am amintit în această dimineață, atunci când ne gândim la asta,
de un mic joc am folosit pentru a juca cu unul dintre foștii TFS CS50 lui
prin care în orice moment ar pleca de la Tastatura lui cu ecran său deblocat,
Mi-ar executa o comanda ca asta-- "salut".
Și acum orice moment a venit înapoi la lui tastatură după ce am eliminat pe ecran
și el va sta jos, încercați să faceți ceva de lucru,
lista conținutul directory-- său
>> [Redare audio]
>> Alo.
Buna ziua.
>> SPEAKER 1: Deci, în echitate, nu a fost de fapt "salut".
Acesta a fost, de obicei, ceva mai asemănător cu asta--
[Redare audio]
-Beep.
SPEAKER 1: acea experiență am would-- astfel încât computerul său ar fi
Jur la el orice moment el de fapt așezat la tastatura lui.
Și foarte repede el a dat seama de a nu părăsi ecranul său deblocat.
Dar acest lucru sugerează genul de distracție stupid pe care le
poate avea cu ceva de genul Bash.
Dar e un pic mai mult serios, pentru a fi siguri, decât că.
Și, de fapt, acesta este unul dintre cele mai multe bug-uri periculoase și de lungă durată
care a lovit într-adevăr lumea la nivel global.
Acest bug a fost în jur de 20 de ani,
și veți fi lovit în doar un clipă de simplitatea sa relativă.
>> Deci, acest lucru este un reprezentant poruncește ca, dacă
detin un Mac, literalmente chiar acum atunci când aveți capac deschis,
aveți posibilitatea să încercați să introduceți în care program numit Terminal.
Terminal este sub Aplicații Utilities--
pentru o dată, utilizatorii de Windows nu trebuie să vă faceți griji cu privire la acest threat-- special
dar cei cu Mac-uri posibilitatea să tastați aceasta într-o fereastră ca voi face aici,
și dacă tastați că în acest program
numit Terminal, ca voi face acum, dacă vedeți cuvântul "vulnerabil",
computerul este vulnerabili la exploatare.
>> Acum, ce înseamnă asta de fapt înseamnă?
Și acest lucru este, desigur, unele sintaxa destul de nebun,
dar hai, cel puțin scoate unele dintre aspectele interesante.
Deci, există unele sintaxă care arată un pic familiar, cel puțin de la C
și programarea mai general.
Văd niște paranteze, punct și virgulă, acolade, și astfel,
dar se pare că acest lucru stupid aici în galben
este în esență o funcție care nu face nimic.
Mijloacele de colon face nimic, și punct și virgulă înseamnă nu mai faci nimic.
Deci interiorul acestora acolade, faptul
că am un egal semneze la stânga, acest lucru
este crearea, în esență, o comandă, sau o variabilă,
numita x, și atribuindu-se că pic galben de cod acolo.
Asta ar putea fi ceva de genul "ecou salut "sau" spune beep "sau ceva
asemănător cu asta.
Dar observați dacă ochii tăi umbla mai mult spre dreapta,
e mai mult decât această linie doar la sfârșitul acelui punct și virgulă.
"Echo vulnerabil," și apoi dincolo de faptul că există chiar mai mult.
Un alt punct și virgulă, bash C :.
>> Deci, pe scurt, această linie de cod este
suficient pentru convingatoare un calculator care este
vulnerabile la a face ceva care doriți să-l fac,
pentru că există un bug în Bash, prin care chiar dacă Bash ar fi trebuit să se oprească
linii de lectură de drept comandă acolo după textul galben,
pentru un plus de 20 de ani bug vechi, Bash a fost de fapt de lectură
dincolo de care virgulă și destul de mult a face ceea ce i se spune.
>> Deci, ce este implicarea de care în final?
Am spus doar "echo hello" sau "echo vulnerabil,"
dar ce se întâmplă dacă ai făcut ceva de fapt malware, cum ar fi rm-rf *,
care nu s-ar putea au scris vreodată înainte,
si sincer, probabil, ar trebui să nu prea curând,
pentru ca poti face o mulțime de daune cu ea.
De ce?
rm ceea ce, desigur nu?
Elimină.
* Înseamnă asta?
Toate.
Deci, este un așa-numit wild card, așa că înseamnă
șterge totul în directorul curent.
r se întâmplă să însemne recursiv, ceea ce înseamnă că, dacă ceea ce ștergerea
este un director, și în interiorul acolo este alte fișiere și alte directoare,
recursiv arunca cu capul în acolo și a șterge tot de asta.
Și -f este cel mai rău dintre toate.
Oricine știe ce înseamnă aici f?
Force.
Deci forța mijloace, chiar în cazul în care acest lucru este o idee rea,
fă-o fără să mă ia determinat pentru confirmarea ulterioară.
Deci, știți, am râde de aceasta, dar sincer, eu, probabil,
acest tip de mai multe ori o zi, pentru că realitatea
este că e cel mai rapid mod de a șterge o grămadă de lucruri.
Dar chiar am făcut unele daune.
>> Dar dacă ar fi să păcălească un calculator în definirea unor variabile stupid
sau funcție numită x, dar apoi pacalirea calculatorul în executare
dincolo de limitele pe care funcție, dincolo de faptul că punct și virgulă,
ai putea pacali într-adevăr un calculator în executarea ceva de genul rm-rf
sau comanda e-mail sau comanda Copy.
Orice literalmente se poate face cu calculator, fie că este vorba ștergerea fișierelor,
crearea de fișiere, spam-ul pe cineva, ataca un server de la distanță,
daca se poate exprima cu o comandă,
poate pacali un calculator in a face asta.
>> Acum, ceea ce este un exemplu de cum s-ar putea face acest lucru?
Ei bine, există o mulțime de calculatoare pe Bash rulare internet.
Toți utilizatorii de noi Mac sunt printre ei.
O mulțime de servere Linux sunt printre ele, de asemenea, și servere Unix.
Ferestre devine din nou relativ de pe cârlig
cu excepția cazului în care le-ați instalat software special.
Acum, o mulțime de servere, pentru exemplu, servere web rula,
și, de fapt, Linux este, probabil, cele mai populare sisteme de operare
pentru a rula pe computerele de pe Internet care servesc pagini web.
Acum, așa cum vom vedea mai târziu în semestrul, atunci când
trimiteți o solicitare de la dumneavoastră browser-- Chrome,
Internet Explorer, o fi la un server de la distanță,
se pare că, deși doar ați tastat www.example.com,
Browser-ul dumneavoastră este de a trimite un mesaj că e un pic mai mult arcane, ca aceasta.
>> Dar observați ceva ciudat.
Primele două linii N-am mai văzut până acum,
dar ei nu te uita în special în pericol.
Dar observați ce am furat pentru a treia linie de aici.
În cazul în care un tip rău a fost de a trimite un mesaj ca aceasta din calculatorul lui sau a ei
la un Mac vulnerabil sau un server Linux vulnerabil,
Lucrul amuzant este că Bash, că simplu prompt de mic de comandă,
este omniprezent și este de multe ori utilizat pentru a executa, în esență,
conținutul unui mesaj pe care-l primește.
Și de această logică, puteți truc un server web, prin urmare,
prin trimiterea ceva de genul User-Agent, care, de obicei,
ar trebui să spun Numele browser-ul dumneavoastră.
User-Agent Chrome, User-Agent Internet Explorer, User-Agent Firefox, această
este doar browser-ul dvs. modalitate de a identifica în sine.
Dar dacă un om rău foarte ingenios spune, mm-mm, sunt
Nu o să-ți spun ceea ce browser-ul meu este,
Am în schimb o să vă trimită această lucru criptic aspect cu un rf rm
* În ea, poți păcăli literalmente o server web vulnerabil pe internet
în executarea exact ca în acolo pentru a șterge toate fișierele.
Și sincer, asta nu-i chiar mai rău de ea.
Puteți face nimic.
Ai putea începe un distribuită atac denial of service
dacă te-a trimis acest mesaj pentru buchete întregi de servere web
și apoi a avut-le pe toate coboare, pentru exemplu, pe serverele Harvard.edu,
și se pot sorta a-bang-ului naiba din ele
de un trafic de rețea care a fost în caz contrar declanșat de acest tip rău.
>> Deci, pe scurt, aproape toată lumea în această cameră, care deține un Mac
este vulnerabil la acest lucru.
Linia de argint este ca daca nu esti rulează un server web de pe laptop-ul,
și dacă nu le-ați configurat de fapt , pentru a permite ceva de genul SSH în ea,
tu ești de fapt în siguranță.
Este vulnerabil, dar nu există nici e o încercarea de a obține în laptop-ul,
astfel încât să puteți să fiți un fel de siguri.
Cu toate acestea, Apple va fi în curând fi actualizarea un fix pentru acest lucru.
Lumea de Linux a lansat deja o serie de remedii pentru Fedora și Ubuntu
și alte versiuni de Linux, și într-adevăr dacă aveți o actualizare 50 în aparat,
chiar asta vor fi actualizate și corectate.
Dar asta nu are într-adevăr a fost vulnerabil,
pentru că dacă nu ai tinkered cu aparatul
și a făcut laptop-ul public accesibilă pe internet, care nu este
în mod implicit, ai de fapt, a fost bine pentru că
de firewall și alte tehnici.
>> Dar este un exemplu extrem de un bug pe care le-am trăit de la literalmente 20
ani, și cine știe dacă cineva în tot acest timp a cunoscut despre el?
Și, de fapt, aceasta este una dintre provocările fundamentale
că vom vedea mai târziu, în semestru de securitate,
este că la fel ca în lumea reală, baietii buni sunt la dezavantajul.
Pentru a păstra băieții răi afară, trebuie să asigurați-vă că fiecare ușă este blocat,
că fiecare fereastră este sigur, că fiecare punct de intrare într-o casă
este sigur de a păstra băieții răi.
Dar ceea ce face tipul cel rău trebuie să face pentru a compromite de fapt, casa ta
si fura de la tine?
El sau ea trebuie doar să găsească un deblocat ușă, o fereastră spartă, sau ceva
de-a lungul acestor linii, și este același lucru în securitatea calculatoarelor.
Putem scrie milioane de de linii de cod de programare
și petrece sute sau mii de ore încercând să-l corect,
dar dacă faci doar un singur greșeală în corectitudine,
puteți pune întregul sistem și într-adevăr, în acest caz, întregul internet
și lumea în pericol.
>> Deci, dacă doriți să aflați mai multe despre aceasta, du-te la acest URL aici.
Nu este nevoie de acțiune in seara asta daca nu esti
printre cei mai confortabil care au fost difuzate propria ta web
Server, în cazul în care ar trebui să care, în fapt, actualiza software-ul.
>> Și acest lucru este de asemenea titlul de un discurs, iar acum o hârtie,
pe care le-am legat cu privire la site-ul curs pentru azi.
A fost de un coleg nume Ken Thompson, care
a fost acceptarea unui foarte celebru premiu în informatică,
și le-a dat acest discurs câțiva ani în urmă, în esență, pe aceeași temă.
Solicitarea oameni buni întrebarea, ar trebui într-adevăr
încredere, în cele din urmă, software-ul care le-ați dat?
De exemplu, cu toții avem a fost scris de programe,
și am fost compilarea le cu răsune.
Și pentru cunoștințele dumneavoastră, ați scris programe pentru CS50 cazul în care există
o usa din spate de felul, există o cale că un tip rău, în cazul în care rulează programul,
ar putea prelua computerul dumneavoastră?
Probabil că nu, corect?
Mario, și lacomi, și de credit.
Acestea sunt toate programele destul de mici.
Ar trebui să fie destul de rău dacă tu de fapt
a făcut tot computerul vulnerabil după ce a scris 10 sau 20 de linii de cod,
sau cel puțin nu cunosc unele de implicațiile de securitate.
Acum, eu spun că în glumă, dar vom vedea astăzi
și în această săptămână este de fapt într-adevăr, într-adevăr ușor
să fie rău și să facă chiar programe scurte vulnerabile.
>> Dar pentru moment, cel puțin, seama ca intrebarea care se pune aici
este de aproximativ răsune într-un compilator.
De ce am avut încredere în răsune pentru ultimele două sau trei săptămâni?
Cine poate spune că oricine a scris răsune nu a avut un "dacă" starea acolo
că injectat în esență, niște zerouri și cele în fiecare program compileaza
care ar permite el sau ea acces calculatorului atunci când dormi
și capac laptop este deschis și pe computer se execută?
Corect?
Avem acest tip de drept sistem de onoare acum unde avem încredere că răsune este legal.
Ai încredere că aparatul este legal.
Ai încredere că literalmente fiecare program pe Mac sau PC-ul dvs. este de încredere.
Și, după cum sugerează acest bug simplu, chiar dacă nu este rău intenționat,
că nu este absolut probabil să fie cazul.
>> Deci, ar trebui să fie speriat ca dracu '.
Sincer, nu e nici simplu soluție la această altă
decât un fel de conștientizare a societății de creșterea complexității
că suntem bazându-se pe partea de sus de sistemele noastre informatice,
și cum în ce mai vulnerabilă am putea fi foarte bine.
>> Acum, cu care a spus, Breakout.
Deci, Breakout este problema stabilit trei, și Breakout este un joc de odinioară
pe care le-ar putea aminti, dar pentru noi în problema set de trei,
ne permite să ia lucrurile înapoi la un alt nivel
astfel încât atunci când scriem programe, chiar într-o fereastră terminal de acest fel,
putem rula de fapt, în cele din urmă, programe grafice nu
spre deosebire de cele pe care le au acces la Scratch.
Deci, aceasta este a personalului punerea în aplicare a Breakout,
care este doar acest caramida-rupere joc, care vă deplasați cu zbaturi înapoi
și mai departe, și te-a lovit mingea împotriva acelor cărămizi colorate sus.
Deci, acest lucru ne aduce un fel de înapoi de unde
am reușit să fie foarte rapid cu Scratch, iar acum cu C,
de punere în aplicare propria noastră interfețe grafice.
>> Dar mai mult decât atât, această set problemă reprezintă primul
în care vom da ai o grămadă de cod.
Și, de fapt, eu aduc explicit atenție la acest lucru, deoarece mai ales
pentru cei mai puțin confortabil, acest problema stabilit, cel puțin la prima vedere,
se va simti ca ne-am luat-o la un alt nivel.
Pentru că ne-am dat, pentru unele dintre căutării
și sortarea probleme în PSET, o grămadă de cod pe care am scris,
și o pereche de comentarii care spune "a face",
în cazul în care va trebui să umple golurile.
Deci, nu prea înfricoșător, dar e prima dată
te vom preda cod pe care aveți nevoie pentru a prima citire, să înțeleagă, și apoi se adaugă la
și-l finalizeze.
>> Și apoi cu Breakout, vom face la fel,
oferindu-vă câteva zeci de mai multe linii de cod care, sincer, vă dau
o mulțime de cadrul de joc, dar nu mai scurt
de punere în aplicare cărămizi și mingea și paleta,
dar vom face implementarea unor alte caracteristici.
Și chiar că, la prima vedere, din nou, mai ales în cazul în care mai puțin confortabil,
s-ar putea părea deosebit de descurajatoare și crezi că e atât de multe funcții noi
aveți nevoie să-și încheie mintea ta în jurul, și asta e adevărat.
Dar tineti minte, e destul ca Scratch.
Cote sunt nu ai folosit toate piesele de puzzle din zero.
Șansele sunt că nu-i păsa să-și încheie mintea ta în jurul toate
pentru că tot ce a luat a fost o privire rapidă pentru a înțelege, oh,
asta e ceea ce pot face cu această piesă de puzzle.
Și, într-adevăr, în problema stabilit 3 spec, vă vom punct
la documentația care va vi-l prezint la unele funcții noi,
și în cele din urmă de programare construiește utilizați.
Condiții, mai rapide, variabile și funcții
va fi identic cu ceea ce am văzut până acum.
>> Deci, într-adevăr, ceea ce vom da ce este un cod de probă care
vă permite să creați o fereastră care nu se uită spre deosebire de aceasta,
și în cele din urmă se transforma într- ceva destul de genul asta.
Deci, să profite de CS50, discuta orelor de program și mai mult,
și să ia de confort în faptul că cantitatea de cod ce trebuie să scrie
este, de fapt, nu tot atât de mult.
Prima provocare este doar să se aclimatizeze te la un cod care le-am scris.
>> Orice întrebări cu privire la pset3, Shellshock, sau altfel?
>> Audiența: Se pare ca merge prin cu Breakout
care codul este aproape un stil orientat-obiect,
dar m-am gândit C a fost un program orientat-obiect.
SPEAKER 1: O întrebare excelentă.
Deci, în căutarea prin Codul de distribuție, codul
am scris pentru pset3, pentru cei familiarizați, ea
se pare ca este o puțin orientat-obiect.
Răspunsul scurt este, este.
Este o aproximare a modului în care s-ar putea face cod orientat pe obiect, folosind
un limbaj cum ar fi C, dar este încă în cele din urmă procedural.
Nu există metode interiorul variabilele, după cum veți vedea.
Dar este o reminiscență de asta.
Și vom vedea din nou această caracteristică când vom ajunge la PHP și JavaScript
spre sfârșitul semestrului.
Dar pentru acum, cred că de ea ca un indiciu a ceea ce este de a veni.
Bună întrebare.
În regulă.
Deci fuziona fel a fost cum ne-am lucruri pe care ultima oara.
Și îmbinarea fel a fost rece în sens că a fost atât de mult mai repede,
cel puțin pe baza testelor sumare am făcut săptămâna trecută, decât, să zicem, cu bule
sortare, selecție fel, inserare fel.
Și ceea ce a fost prea curat este doar cum succint și curat
puteți exprima.
Și ce-am spus că a fost un superior legat de timpul de funcționare de îmbinare
sortarea?
Da?
>> Audiența: n log n?
>> SPEAKER 1: n log n, chiar. n log n.
Și ne vom întoarce la ceea ce că înseamnă de fapt sau de unde vine,
dar acest lucru a fost mai bine decât ceea ce timp de funcționare
că am văzut de balon selecție și inserare fel?
Deci, n pătrat. n pătrat este mai mare decât aceasta,
și chiar dacă nu este destul de evident, știu că log n este mai mic decât n,
asa ca daca faci de n ori ceva mai mic decât n,
aceasta va fi mai mică decât n pătrat.
Este un pic de intuiție acolo.
Dar am plătit un preț pentru acest lucru.
Acesta a fost mai rapid, dar o temă care a început să apară săptămâna trecută a fost acest compromis.
Am o performanță mai bună timp înțelept, dar ceea ce
am avut eu să-și petreacă pe de altă parte parte, pentru a atinge acest?
>> Audiența: memorie.
SPEAKER 1: Spune din nou?
Audiența: memorie.
SPEAKER 1: memorie, sau mai mult spațiu în general.
Și nu a fost super evident cu oamenii noștri,
dar reamintească faptul că voluntarii noștri au fost un pas înainte și pas cu pas
înapoi ca și cum nu este o matrice aici, și ca și cum nu există
un al doilea tablou aici că acestea ar putea folosi, pentru că ne-am
undeva necesare pentru a fuziona acei oameni.
Noi nu putea să le schimba în loc.
Deci fuziona levier fel este mai mult spațiu, care
nu am nevoie de alte algoritmi,
dar partea buna este ca e mult mai rapid.
Și sincer, în spațiul lumea reală acestea RAM days--, hard disk spatiu--
este relativ ieftin, și așa că e nu neapărat un lucru rău.
>> Deci, haideți să aruncăm o privire rapidă, un pic mai metodic, la ceea ce am făcut
și de ce am spus că este o n log n.
Deci, aici sunt cele opt numere și opt voluntari am avut ultima dată.
Și primul lucru pe care Merge Sorteaza ne-a spus să fac a fost ce?
Audiența: Divide în două.
SPEAKER 1: Spune din nou?
Audiența: Divide în două.
SPEAKER 1: Divide în două, chiar.
Acest lucru este foarte amintește de cartea de telefon, de divizare
și cuceri mai general.
Așa că ne-am uitat la jumătatea stângă.
Și apoi, o dată am spus, un fel jumătatea stângă a elementelor,
ceea ce am spus în continuare?
Sortarea jumătatea stângă a stânga jumătate, ceea ce ne-a permis sa,
după împărțirea în două, se concentreze pe patru și două.
>> Cum se sorta o listă acum, în galben, de dimensiune doi, folosind Merge Sort?
Ei bine, se împart în două, și sorta jumătatea stângă.
Și acest lucru a fost în cazul în care lucrurile am un pic scurt stupid.
Cum se sorta o listă care este de Dimensiunea unul, ca acest număr de patru aici?
Este sortate.
Ai terminat.
>> Dar atunci cum să sortați o listă de Dimensiunea una, atunci când este numarul doi?
Ei bine, același lucru, dar acum ceea ce a fost al treilea și pas important în Merge Sort?
Trebuia să fuzioneze stânga jumătate și jumătatea din dreapta.
Și odată ce am făcut asta, ne-am uitat la patru, ne-am uitat la două.
Am decis în regulă, în mod evident, doi este pe primul loc,
asa ca am pus două în ei loc, urmat de patru.
Și acum trebuie să fel de înapoi, iar acest lucru este un fel de caracteristică
unui algoritm ca Merge Sortare, înapoi în memorie.
Care a fost următoarea linie de poveste?
Ce ar trebui să se concentreze pe viitor?
Jumătatea din dreapta în stânga jumătate, care este de șase și opt.
>> Deci, permiteți-mi să pas prin acest fără belaboring punctul de prea mult.
Șase și opt, apoi șase este sortate, opt sunt sortate.
Merge-le împreună așa, iar acum urmatorul pas mare
este, desigur, sorta jumătatea din dreapta de la chiar primul pas al acestui algoritm.
Deci, ne vom concentra pe unul, trei, șapte, cinci.
Apoi ne vom concentra pe jumătatea stângă.
Jumătatea stângă a că, jumătatea din dreapta a că, și apoi fuziona într-o singură și trei.
Apoi, jumătatea din dreapta, apoi la stânga pe jumătate de aceasta, atunci jumătatea din dreapta a acesteia.
Merge-l în, și acum ceea ce rămâne pas?
Merge mare jumătatea stângă și Big pe jumătate dreptate, așa că unul se duce acolo,
apoi două, apoi trei, apoi patru, apoi cinci, apoi șase, apoi șapte, apoi opt.
>> Deci, acum, de ce este acest lucru în cele din urmă revelatoare, mai ales în cazul în care n și logaritmi mai mult
în general, prefera să scape, cel puțin din ultimul timp?
Ei bine, observa înălțimea de acest lucru.
Am avut opt ​​elemente, și ne-am împărțit prin două, câte două, câte două.
Deci, jurnal de bază doi de opt ani ne dă trei.
Și crede-mă pe faptul că, dacă un pic neclar pe care.
Dar log baza doi din opt este de trei, așa că am făcut trei straturi de fuziune.
Și când am fuzionat Elemente, cât de multe elemente
ne-am uita la fiecare dintre aceste rânduri?
Un total de n, corect?
Pentru ca să fuzioneze rândul de sus, chiar dacă am făcut-o bucată cu bucată,
ne-am atins în cele din urmă fiecare număr o dată.
Și în al doilea rând, pentru a îmbina aceste liste de dimensiune doi,
am avut de a atinge fiecare element dată.
Și apoi aici într-adevăr în mod clar, în ultimul rând,
am avut de a atinge fiecare dintre cele elemente de dată, dar numai o dată,
deci aici se află, apoi, n log n nostru.
>> Și acum doar pentru a face lucrurile un pic mai formal pentru o clipă, dacă
au fost de a analiza acum acest la un fel de nivel superior
și să încerce să decidă, bine cum s-ar putea merge cu privire la exprimarea
timpul de execuție a acestui algoritm doar uitandu-te la ea și nu
prin utilizarea unui exemplu inventate?
Ei bine, cât de mult timp ai spune un pas ca acest lucru în galben s-ar lua,
dacă n <2 schimb?
Asta-i o O mare de ce?
Deci, eu văd unul, așa un pas, poate două etape, pentru că, dacă
și apoi să se întoarcă, dar este constantă de timp, nu?
Așa că am spus O (1), și care este cum voi exprima acest lucru.
T, fie doar timpul de funcționare.
n este mărimea de intrare, deci T (n), doar un fel de lux
de a spune funcționare Timp de intrare dat de dimensiune n
va fi pe ordinea de timp constant, în O (1).
>> Dar altfel, ce zici de asta?
Cum te-ai exprima Timp de această linie galbenă care rulează?
T de ce?
Puteți fel de ieftin aici și răspunde la întrebarea mea ciclic.
Deci, în cazul în care timpul de execuție în general putem spune doar este T (n).
Și acum un fel de punting aici și zis, bine, sorta doar jumătatea stângă,
și apoi sorta jumătatea din dreapta.
Cum am putea reprezenta simbolic timpul de execuție a acestei linii de culoare galbenă?
T de ce?
Care este mărimea de intrare?
n peste două.
De ce nu am spus asta?
Apoi acesta este un alt T (n / 2) și apoi din nou, dacă am uni două jumătăți sortate,
cât de multe elemente de voi trebui să atingă totală?
n.
Deci, eu pot exprima acest lucru, doar pentru a fi un fel de fantezie,
ca timpul de execuție, în general.
T (n) este doar timpul de execuție a T (n / 2), plus T (n / 2), la stânga pe jumătate și jumătate drept,
plus O (n), care este, probabil n pași, dar poate că, dacă eu sunt, folosind două degete,
este de două ori mai multe pași, dar e liniar.
E un număr de pași care este un factor de n,
așa că s-ar putea exprima acest lucru ca aceasta.
Și acest lucru este în cazul în care acum ne vom punt la din spate a noastră matematica manual de liceu
suntem că recurenta în cele din urmă sfârșește prin a egala acest lucru, n log n ori,
dacă aveți de fapt, nu afară matematica mai mult formal.
>> Deci, asta e doar două perspective.
Unul numeric cu o hard-coded exemplu reprezentativ
folosind opt numere, si o mai mult privire generală la cum am ajuns acolo.
Dar ceea ce este cu adevarat interesant aici este, din nou, această noțiune de ciclism.
Nu folosesc pentru bucle.
Sunt un fel de definire ceva în termeni de sine,
nu numai cu această funcție matematică,
dar, de asemenea, în ceea ce privește acest cod pseudo.
Acest cod pseudo este recursiv în care doi dintre liniile sale
este, în esență, se spune pentru a merge folosi în sine pentru a rezolva o mică
problemă de dimensiuni mai mici, și apoi din nou și din nou
și din nou, până când ne-am Whittle se până la această așa-numitul caz de bază.
>> Deci, haideți să de fapt desena o mai convingătoare ia-departe de această, după cum urmează.
Lasă-mă să intru în gedit și să ia o uita-te la o parte din codul sursă de astăzi,
în special acest exemplu aici.
Sigma 0, care adaugă aparent numerele de la unu la n.
Deci, hai sa vedem ce este familiar și nefamiliare aici.
În primul rând, avem o pereche de include, deci nimic nou acolo.
Prototype.
Sunt un pic neclar pe această după câteva zile,
dar ceea ce am spus-o prototip al unei funcții este?
Audiența: [inaudibil].
SPEAKER 1: Ce-i asta?
Audiența: Am anunța.
SPEAKER 1: Am anunța.
Deci, sunteți de predare răsune, hei, Nu, de fapt punerea în aplicare acest lucru încă,
dar undeva în acest dosar, probabil, va fi o funcție numită ce?
Sigma.
Și aceasta este doar o promisiune care o sa arate asa.
O să iau un număr întreg de input-- și eu pot fi mai explicit
și spune int n --and e O să se întoarcă un int,
dar mijloace punct și virgulă, mm, voi primi în jurul pentru punerea în aplicare a acestei un pic mai târziu.
Din nou, răsune este prost.
Este doar o să știe ce l-ai spune de sus în jos,
asa ca am nevoie de cel puțin da un indiciu a ceea ce este de a veni.
>> Acum, să ne uităm la principal aici.
Să defilați în jos și aici vezi ce principal este de a face.
Nu este atât de mult de o funcție, și de fapt, constructul aici este familiar.
Declar o variabilă n, și apoi Am hartuiti din nou și din nou a utilizatorului
pentru un număr întreg pozitiv folosind getint, și numai ieșirea din această buclă
Odată ce utilizatorul a respectat.
Face în timp, ne-am folosit pentru a hartuiti utilizatorul în acest fel.
Acum, acest lucru este interesant.
Declar un int numit "răspuns".
Am valoarea de returnare atribui de o funcție numită "sigma."
Nu știu ce face inca asta, dar Îmi amintesc ao declara în urmă cu o clipă.
Și apoi voi trece în Valoarea pe care utilizatorul introduce, n,
și apoi m-am raporta răspunsul.
Ei bine, să derulați înapoi pentru doar o clipă.
Să mergem mai departe în acest director, face sigma 0, și a alerga de fapt acest program
și să vedem ce se întâmplă.
Deci, dacă am merge mai departe și a alerga acest program, ./sigma-0,
și eu de tip într-o pozitiv număr întreg cum ar fi două, Sigma,
ca simbol grecesc implică, este doar Va aduna toate numerele de la
zero până la două.
Deci 0 plus 1 plus 2.
Deci, acest lucru ar trebui să sperăm, da-mi 3.
Asta e tot ce face.
Și în mod similar, dacă Eu conduc din nou si eu dau numărul trei,
asta e 3 plus 2, astfel încât este 5, plus 1 ar trebui să-mi dea 6.
Și apoi, dacă ajung într-adevăr nebun și începeți să tastați în număr mai mare,
ar trebui să-mi dea sume mai mari și mai mari.
Deci, asta e tot.
>> Deci, ce se sigma arata?
Ei bine, e destul de simplu.
Este modul în care ne-ar fi pus în aplicare aceasta pentru ultimele două săptămâni.
"Int" va fi tipul de întoarcere.
Sigma este numele, și este nevoie de o m variabilă în loc de n.
Voi schimba asta sus.
Apoi, acesta este doar un cec bun-simț.
Vom vedea de ce într-o clipă.
Acum declara o altă variabilă, sumă, se inițializează cu zero.
Apoi am această buclă iterarea, aparent pentru claritate,
de la i = 1 la până la o = m, care este indiferent de utilizatorul tastat în, și apoi am
incrementarea suma de genul asta.
Și apoi să se întoarcă suma.
>> Deci, o serie de întrebări.
O, eu susțin în comentariul meu că această evită riscul de o buclă infinită.
De ce ar trece într-un număr negativ induce, potențial, o buclă infinită?
>> Audiența: Nu vei ajunge la m.
>> SPEAKER 1: Nu ajunge m.
Dar m este trecut în, Să ia în considerare un exemplu simplu.
Dacă m este trecut în de utilizator ca unul negativ.
Indiferent de principal.
Principala ne protejează de acest prea, așa că eu sunt doar
fiind într-adevăr anal cu sigma pentru a face, de asemenea sigur
că intrarea nu poate fi negativ.
Deci, dacă m este negativ, ceva de genul unul negativ.
Ce se va întâmpla?
Ei bine, i se va se inițializat la unul,
și apoi i se va fi mai mic sau egal cu m?
>> Stand de.
Asta fost-- nu-i lăsăm, hai nix această poveste.
Nu am cerut această întrebare, pentru că riscul pe care am aluzie la
nu se va întâmpla pentru că i se întotdeauna va fi mai mare bine than--,
Am retrage această întrebare.
OK.
Să ne concentrăm doar pe această parte aici.
De ce sa declar ceva în afara buclei?
Aviz pe linia 49 am i declarat în interiorul buclei,
dar on-line 48 am a declarat ceva din afara.
Da.
Audiența: [inaudibil].
SPEAKER 1: Sigur.
Deci, în primul rând eu cu siguranță nu doresc să declare și să inițializa sumă
la zero în interiorul bucla pe fiecare iterație,
deoarece acest lucru ar anula în mod clar Scopul insumarea numerelor.
Mi-ar continua să se schimbe valoarea la zero.
Și, de asemenea, ceea ce este un alt mai multe arcane motiv pentru care aceeași decizie de design?
Da.
>> Audiența: [inaudibil].
SPEAKER 1: Exact.
Vreau să-l acceseze în afara din bucla prea pe ce linie?
Pe 53.
Și se bazează pe regula noastră de degetul mare de la un cuplu de prelegeri în urmă,
variabile cad, într-adevăr, la acolade care le cuprind.
Deci, dacă eu nu declar sumă interior dintre aceste acolade exterioare,
Nu pot folosi în linie 53.
Pune-un alt mod, în cazul în care am declarat Suma aici, sau chiar în cadrul
Pentru bucla, nu am putut accesa în 53.
Variabila va fi eficient plecat.
Deci, un cuplu de motive de acolo.
Dar acum să ne întoarcem și să vedem ce se întâmplă.
Deci, sigma este chemat.
Se adaugă cu 1 plus 2, sau 1 plus 2 plus 3, după care revine la valoarea,
stochează într-un răspuns, și printf aici De aceea, eu văd pe ecran.
Deci, asta este ceea ce vom numi un iterativ abordare, în cazul în care repetare doar
înseamnă a folosi o buclă.
A Pentru buclă, o buclă în timp ce, o face în timp ce buclă, a face ceva din nou
și din nou și din nou.
>> Dar sigma este un fel de funcție curat în că aș putea să o pună în aplicare în mod diferit.
Ce zici de asta, care doar pentru a fi un fel de rece,
Lasă-mă să scap într-adevăr de o mulțime de distracție
deoarece această funcție este într-adevăr destul de simplu.
Să Whittle-l în jos doar la patru linii sale de bază
și de a scăpa de toate comentarii și acolade.
Aceasta este un fel de minte-suflare implementare alternativă.
Bine, poate nu minte-suflare, dar e un fel de sexy, bine,
să se uite la acest atât de mult mai succint.
Cu doar patru linii de cod, Am prima dată această verificare bun-simț.
Dacă m este mai mic sau egal cu la zero, sigma are nici un sens.
Ar trebui doar să fie în acest caz pentru numere pozitive,
așa că am de gând doar să a reveni la zero arbitrar
astfel încât să putem avea cel puțin unii așa-numitul caz de bază.
>> Dar aici e frumusețea.
Totalitatea acestei idei, adăugând numere de la 1 la n, sau m în acest caz,
se poate face prin fel de trecerea dolar.
Ei bine, ceea ce este suma de la 1 la m?
Ei bine, știi ce?
Este la fel ca suma m plus suma de la 1 la m minus 1.
Ei bine, știi ce?
Ce-i sigma de m minus 1?
Ei bine, dacă ai un fel de urma acestui logic, e la fel ca m minus 1
plus sigma de m minus 2.
Astfel încât să puteți fel de doar-- acest lucru este ca, daca esti doar
încercarea de a enerva un prieten și ei vă pun o întrebare,
ai un fel de a răspunde cu o întrebare, puteți fel de păstra trece dolar.
Dar ceea ce este important este că, dacă vă păstrați făcând întrebarea în ce mai mici
și mai mic, tu esti nu cer ceea ce este sigma
de n, ceea ce este sigma de n, ceea ce este sigma de n?
Ceri ce-i sigma de n, ceea ce este sigma
de n minus 1, ceea ce este sigma de n minus 2?
În cele din urmă întrebarea dvs. va deveni ceea ce?
Ce este sigma de unul sau de zero, o anumită valoare foarte mică,
și de îndată ce te că, prietenul tău,
nu sunteți de gând să ceară aceeași întrebare din nou,
esti doar de gând să spun, oh e zero.
Am terminat joaca acest fel de joc ciclic stupid.
>> Deci, recursivitate este actul în programare unei funcții numindu-se.
Acest program, atunci când sunt compilate și a alerga, este O să se comporte exact în același mod,
dar ceea ce este important este că în interiorul de o funcție numită sigma,
există o linie de cod care suntem noi înșine de asteptare,
care ar fi în mod normal de rău.
De exemplu, dacă eu primul compilat acest lucru, asa ca sigma--
face sigma 1 ./sigma-1.
Întreg pozitiv, vă rugăm, 50 1275.
Deci, ceea ce funcția pare să fie, bazat pe un test, corect.
Dar dacă am obține un pic periculos și șterge așa-numitul caz de bază,
și să spunem, ei bine eu sunt doar a face acest lucru mai complicat decât este.
Să calculăm sigma prin luarea m și apoi adăugarea
în sigma de m minus unul?
Ei bine, ce se va întâmpla aici?
Să zoom out.
Să recompilați programul, salvați-l, recompilați programul,
și apoi gata ./sigma-1 zoom in, intra întreg pozitiv, vă rugăm, 50.
Câți dintre voi sunteți dispuși pentru Fess până la văzând că?
>> OK.
Deci, acest lucru se poate întâmpla pentru un număr de motive,
și sincer în această săptămână suntem pe cale de a vă oferi mai multe dintre ele.
Dar, în acest caz, încercați a raționa înapoi
ce s-ar fi întâmplat aici?
Eroare de segmentare, ne-a declarat trecut timp, se referă la un segment de memorie.
Ceva sa întâmplat rău.
Dar ce-a fost mecanic care a mers prost
aici din cauza îndepărtării mele de care așa-numitul cazul de bază,
unde m-am întors o valoare hard-coded?
Ce crezi că a mers prost?
Da.
>> Audiența: [inaudibil].
SPEAKER 1: Ah.
Bună întrebare.
Deci mărimea numărului că am fost insumarea
ajuns atât de mare, încât a depășit mărimea spațiului de memorie.
Bună idee, dar nu fundamental va provoca un accident.
Asta ar putea duce la overflow întreg, în cazul în care biții doar flip peste
și apoi ne-am confundat-o foarte mare număr de ca un număr negativ,
dar care în sine nu va provoca un accident.
Pentru că, la sfârșitul a zi un întreg este încă 32 de biți.
Nu te duci la fura accidental un pic 33.
Dar un gand bun.
Da.
>> Audiența: [inaudibil].
SPEAKER 1: Metoda nu opreste,
și într-adevăr, se solicită din nou și din nou și din nou și din nou
și din nou, și nici unul dintre aceste funcții vreodată
termina pentru că linia lor unic de Codul themself cheamă din nou și din nou
și din nou.
Si ceea ce este cu adevărat întâmplă aici, iar acum ne-am
poate desena un fel de acest pictural.
Lasă-mă să merg pe la un imagine pentru doar o clipă.
Aceasta este o imagine, care va carne în cele din urmă
mai în detaliu, de ce se întâmplă în interiorul memoria computerului.
Și se pare că pe în partea de jos a acestui tablou
este ceva numit stiva.
Aceasta este o bucată de memorie, o bucată de RAM,
asta e doar folosit in orice moment o funcție se numește.
De fiecare dată când, un programator, apela o funcție,
sistemul de operare, cum ar fi Mac OS, Windows, Linux sau,
apucă un buchet de bytes, poate o câteva kilobytes, poate câteva megaocteți
de memorie, ele mâinile pentru tine, și apoi vă permite
aveți o funcție utilizând indiferent de variabile care aveți nevoie.
Și dacă apoi apel altul Funcția și o altă funcție,
te un alt felie de memorie și o altă felie de memorie.
>> Și, într-adevăr, dacă aceste tăvi verzi de la Annenberg reprezintă acea memorie,
aici e ceea ce se întâmplă primul timp te sun funcție sigma.
E ca și cum pune o tavă de genul asta pe ceea ce este inițial o stivă de gol.
Dar, apoi, în cazul în care tava se numește, ca să spunem așa,
de asteptare un alt exemplu de sigma, care este
ca și cum cere sistemul de operare, ooh, au nevoie de un pic mai mult de memorie,
da-mi asta.
Și apoi se îngrămădite pe partea de sus.
Dar ceea ce este esențial aici este că prima tava este încă acolo,
pentru că a invocat această a doua tavă.
Acum între timp, sigma suna sigma, asta e ca cere mai multă memorie.
Se îngrămădite pe aici.
sigma numesc sigma, asta e un alt tavă care se îngrămădite pe aici.
Și dacă tot faci asta, în cele din urmă, un fel de hartă acestei vizual
pentru că grafic, ceea ce va întâmpla cu teancul de tăvi?
Acesta va depăși suma de memorie în care computerul are.
Și, de îndată ce acest lucru tavă verde depășește linia orizontală
de mai sus stivă și mai sus că grămadă cuvânt, care ne vom întoarce în viitor,
că este un lucru rău.
Heap este un alt segment de memorie,
iar dacă ai lăsat aceste tăvi morman morman și pe,
ai de gând să depășească propriul segment de memorie,
și un program este într-adevăr de gând să se prăbușească.
>> Acum, ca o paranteza, aceasta idee de recursie, prin urmare,
poate conduce în mod clar la probleme, dar nu este neapărat un lucru rău.
Pentru că ia în considerare, după toate, cum-- și poate
aceasta ia ceva timp sa folosit la reușești elegant sau cât de simplu
că punerea în aplicare a sigma a fost.
Iar noi nu vom folosi recursivitate tot atât de mult în CS50,
dar în CS51, și într-adevăr orice clasă în cazul în care manipula structuri de date
cum ar fi copaci, sau arbori de familie, care au unele ierarhie,
e super, super util.
Acum, ca o paranteza, astfel încât să ca aspiră oamenii de știință de calculator
sunt familiarizați cu unele de Google glume interior, dacă te duci la Google
și te uiți la ceea ce este definiție de, să zicem, recursivitate, intra.
Aha.
Ca o paranteza, am tras câteva.
Acest lucru a fost ca 10 de minute de amânare în această dimineață.
În cazul în care, de asemenea, Google "strâmb," Notă prin înclinarea capului slightly--
iar apoi acesta este, probabil, cel mai atroce de toate
deoarece cineva a petrecut ca zi de punere în aplicare a acestei
câțiva ani ago-- haide.
Oh, Asteapta-- că e un bug.
>> Deci, care rulează pe unul dintre cele mai mari site-uri din lume
sunt aceste ouă stupide mici de Paști.
Probabil că consuma o număr trivial de linii de cod
doar astfel încât să putem avea mici lucruri amuzante de genul asta.
Dar cel puțin acum te unele dintre aceste glume interior.
>> Acum, haideți să aruncăm o privire la unele dintre cele mai alb se află noi am spus în ultima vreme,
și începe să coaja înapoi mai multe straturi de vedere tehnic
astfel încât să înțelegeți cu adevărat ceea ce se întâmplă
și puteți înțelege unele dintre amenințările,
ca Shellshock, care au început acum să devină
pe prima linie a tuturor atenție, cel puțin în mass-media.
Deci, aici este o funcție foarte simplu care returnează nimic, nul.
Numele său este de swap.
Este nevoie de două variabile și returnează nimic.
Ia într-o și b.
Deci, o demonstrație rapidă.
Am adus astea.
Am putea foarte bine să ia un pic pauză aici pentru un moment
și au un pic de ceva de băut.
În cazul în care cineva nu ar deranja aderarea ma aici pentru doar o clipă.
Cum despre tine în tricoul maro?
Hai sus.
Doar cea de astăzi.
Mulțumesc, totuși.
Bine, și ne-am vine cine aici?
Care e numele tău?
>> SPEAKER 4: Laura.
>> SPEAKER 1: Laura.
Hai sus.
Deci Laura, provocare foarte simplu de azi.
Mă bucur să yo cunosc.
În regulă.
Deci avem niște lapte pe aici și Avem niște suc de portocale pe aici
și unele cupe pe care le împrumutat de la Annenberg astăzi.
>> SPEAKER 4: imprumutat.
SPEAKER 1: Si va merge mai departe și vă va oferi o jumatate de pahar de aceasta.
În regulă.
Și vă vom oferi jumătate un pahar de lapte.
Oh, și doar astfel încât să puteți amintiți-vă cum a fost aceasta ca,
Mi-am amintit de a aduce asta și astăzi.
Bine.
Dacă nu te superi, să vedem, ne-am le pot pune pe propriile ochelari
dacă doriți.
Acest lucru va fi lumea din ochii Laurei.
În regulă.
Deci, obiectivul tău, dat doua cesti de lichid aici, lapte și suc de portocale,
se schimba cele două conținutul, astfel încât suc de portocale merge în ceașcă de lapte
iar laptele intră în cana de suc de portocale.
>> SPEAKER 4: Primesc o ceașcă?
SPEAKER 1: Mă bucur că ați întrebat, deși ar fi fost mult mai bine imagini
dacă nu ai fi întrebat.
Dar da, vă putem oferi un al treilea ceașcă e gol, desigur.
În regulă.
Deci, schimba conținutul acolo.
Foarte frumos.
Foarte bine.
Faci asta remarcabil cu atenție.
Și pasul trei.
În regulă.
Excelent.
O rundă mare de aplauze ar fi bine pentru Laura.
În regulă.
Avem un cadou de despărțire mic pentru tine, dar lasă-mă să iau astea.
Vă mulțumesc foarte mult.
Deci, un exemplu simplu, deși, pentru a demonstra că dacă faci
vreau să schimb conținutul a doua containere,
sau hai sa le numim variabile, aveți nevoie de depozitare temporară
să organizeze una dintre conținutul în așa pe care le puteți face de fapt swap.
Deci, într-adevăr, acest cod sursă de aici până în C este reprezentativ pentru exact acest lucru.
Dacă sucul de portocale fost și laptele a fost b, și ne-am dorit pentru a schimba cele două,
ai putea încerca ceva creativ prin turnarea unul în celălalt,
dar că, probabil, nu ar fi termina deosebit de bine.
Și așa vom folosi o ceașcă treilea, apel ea tmp, T-M-P prin convenție,
și pune conținutul JO în care, atunci schimba-o cana,
apoi pune JO în cupa originală, astfel
realizarea, exact așa cum Laura a făcut, swap.
>> Deci, hai sa facem exact acest lucru.
Lasă-mă să mergeți mai departe și deschide up un exemplu care este
de fapt, numit "nu schimba, "pentru că acest lucru nu este
ca pur si simplu face ca s-ar putea crede.
Deci, în acest program, observăm că Sunt folosind stdio.h, vechiul nostru prieten.
Am prototipul pentru schimb de acolo, care
înseamnă punerea în aplicare a acesteia probabil în jos de mai jos,
și să vedem ce acest principal Programul va face pentru mine.
Declar prima int x devine unul, și int y devine doi.
Deci, cred că de cele de JO și lapte, respectiv.
Și atunci am avea o printf spune x este aceasta
iar y este aceasta, doar așa pot vezi vizual ce se întâmplă.
Apoi am printf susținând că eu sunt schimbarea celor doi,
și apoi am imprima un susțin că acestea sunt schimbate,
și am imprima x și y din nou.
Deci, aici, în schimb este exact ceea ce a făcut Laura,
și exact ceea ce am văzut pe ecran în urmă cu o clipă.
>> Deci, să mergem mai departe și fi crunt dezamăgiți.
Nu fac nici de swap, și a alerga nu de swap, zoom pe ieșirea de aici.
Introduceti x este 1, y este 2, swapping schimbat.
x este încă 1, iar y este încă 2.
Deci, chiar dacă, sincer, acest lucru pare ca exact, deși mai mult de vedere tehnic,
ceea ce a făcut Laura nu părea, la locul de muncă.
Deci, de ce este asta?
Ei bine, se pare că, atunci când vom scrie un program de genul asta
care are atât principal, a subliniat aici, și apoi o altă funcție, cum ar fi swap,
evidențiate aici, care se numește, în lume
arată un pic ceva de genul aceste tăvi în urmă o clipă.
Când principal primul este chemat, e ca și cum cere sistemul de operare
pentru un pic de memorie pentru orice locală variabile cum ar fi x și y, care are principal,
și se sfârșesc aici.
Dar, în cazul în care apelurile principale schimba, și principalul trece de a schimba două argumente, A și B,
suc de portocale și lapte, nu e ca predarea sucul de portocale și lapte
la Laura.
Ce face un calculator, este trece de exemplare ale sucului de portocale
și copii ale laptelui la Laura, astfel încât ceea ce este în cele din urmă în interiorul acestui tavă
este cel de valoare și două, sau JO și lapte, dar copii ale acestora,
astfel încât în ​​acest moment în poveste, acolo
este JO și lapte în fiecare din aceste tăvi.
Există o unul și două în fiecare dintre aceste tăvi,
și funcția de swap este într-adevăr de lucru.
Este le pompare în interiorul de-al doilea cel mai de sus tava,
dar care nu are impact pompare.
Și se bazează pe doar câteva Principiul de bază care le-am
a vorbit despre înainte, și într-adevăr în urmă cu doar câteva minute, ceea ce
s-ar putea explica de ce schimbarea a și b interior de schimb
are nici un efect asupra x și y, chiar dacă Am trecut x și y pentru funcția de swap.
Care este cuvantul cheie aici s-ar putea explica simplist?
Cred că l-am auzit aici?
Audiența: Return.
SPEAKER 1: Înapoi?
Nu se mai întoarcă.
Să mergem cu un altul.
Ce-i asta?
>> Audiența: [inaudibil].
>> SPEAKER 1: OK, deci revenim am putut face munca de întoarcere în poveste,
dar există o explicație mai simplă.
Audiența: Domeniul de aplicare.
SPEAKER 1: Domeniul de aplicare.
Voi lua domeniu.
Deci domeniul de aplicare, amintiți-vă unde x și y noastre declarate.
Ei au declarat în interiorul de principal chiar aici.
A și B, între timp, sunt a declarat în mod eficient
interior de swap, nu destul de în acolade, dar încă
în domeniul general de swap.
Și astfel, într-adevăr, a și b există numai în această tavă
din Annenberg, această a doua bucată de cod.
Deci, vom schimba într-adevăr copia, dar că nu-i chiar atât de util.
>> Deci, haideți să aruncăm o privire la acest nivel un pic mai jos.
Am de gând să mă întorc în directorul sursă,
și am de gând să primul mări aici, și doar
pentru a confirma că sunt în acest fereastră terminal mai mare,
Programul încă se comportă așa.
Să presupunem acum că această nu este intenționată.
În mod clar am vrut să schimb de lucru, asa ca se simte ca un bug.
Acum am putea începe adăugarea unei mulțime de printf lui la codul meu,
imprimarea x pe aici, y peste aici, un peste aici, b aici.
Dar, sincer, asta e, probabil, ceea ce care le-ați făcut pentru câteva săptămâni
acum, în ore de birou și la domiciliu atunci când se lucrează
pe psets încercarea de a găsi unele bug-uri.
Dar veți vedea, dacă nu ați făcut deja, că problema stabilit trei va introduce
la o comandă numită GDB, unde GDB, GNU debugger,
are în sine o grămadă de caracteristici care pot de fapt
să ne înțelegem situații în acest fel, dar mai convingător,
rezolva problemele și pentru a găsi bug-uri.
Așa că am de gând să fac asta.
În loc de ./noswap, eu sunt în schimb va rula GDB ./noswap.
Cu alte cuvinte, am de gând să ruleze meu Programul nu în Bash, noul nostru prieten
astăzi.
Am de gând să ruleze meu Programul noswap interior
din acest alt program numit GDB, care este un program de depanare, care
este un program care este proiectat pentru a ajuta la Voi oamenii găsi și elimina bug-uri.
Deci, dacă am lovit Fugi de aici, nu e o cantitate atroce de text
că nu va trebui într-adevăr să citească.
Este, în esență, o distragere a atenției de prompt, care
Am de gând să lovit de control-L să se ridice la partea de sus acolo.
Aceasta este prompt GDB.
Dacă vreau să rulați acest program acum, ca această foaie de ieftin mic pe azi
diapozitiv sugerează, Run este primul Comenzile pe care le menirea de a introduce.
Și am de gând doar să tastați rula pe aici în interiorul GDB,
și într-adevăr, ea a fugit programul meu.
Acum, există unele suplimentare ieșiri de pe ecran ca aceasta,
dar asta e doar GDB fiind anal și să ne spună ce se întâmplă.
Nu trebuie într-adevăr să vă faceți griji despre aceste detalii chiar acum.
Dar ceea ce este cu adevarat misto despre GDB, dacă am face acest lucru again--
Control-L șterge screen-- lasă-mă să merg înainte și de tip "sparge principal," astfel,
când am lovit Enter, stabilind ce este numit un punct de pauză la noswap.c,
linia 16, care este în cazul GDB a dat seama programul meu de fapt
este, funcția mea este de fapt.
Acest vom ignora pentru acum dar asta e adresa
în memorie în mod special a acestei funcții.
Așa că acum, când am tip alerga, observa ceea ce e bine aici.
Programul meu rupe la linia I a spus GDB pentru a întrerupe executarea la.
Așa că nu trebuie să se schimbe acum codul meu, adăuga unele lui printf, recompilați ea, reluare
l, schimba, adăuga unele lui printf, salvați-l, recompilați-l, l rulați.
Eu pot merge doar prin intermediul programului meu pas cu pas cu pas la viteza uman,
nu la fel Intel-interior de viteză.
>> Deci, observăm acum această linie Apare aici, iar dacă mă duc înapoi
la programul meu in gedit, observă că aceasta este de fapt
prima linie de cod.
Nu e linia 16 in gedit.
Nu e linia 16 în GDB, și chiar deși această interfață alb-negru
nu este aproape la fel de utilizator prietenos, acest lucru înseamnă
că linia 16 nu a fost executată încă, dar este pe cale de a fi.
Deci, într-adevăr, dacă am tip de imprimare x, nu printf, doar de imprimare x,
Am obține o valoare fals acolo de la zero, deoarece x nu a fost inițializat încă.
Așa că am de gând să tastați următor, sau, dacă vrea să fie fantezie, doar N pentru viitor.
Dar când am tip următor intra, acum observați că trece la linia 17.
Deci, logic, dacă l-am executat linia 16 și de tip acum de imprimare x,
ceea ce ar trebui să văd?
One.
>> Iar acum acest lucru este, desigur, confuz.
2 dolari este doar un mod fantezist de, dacă vreau să mă refer la faptul că valoarea mai târziu,
vă pot spune "dolar semneze două."
E ca o referință spate.
Dar pentru acum, doar ignora-l.
Ce este interesant este ceea ce-i pe partea dreaptă a semnului egal.
Și acum, dacă am introduce următorul nou și imprimare y, eu ar trebui sa vedeti 2.
Pot, de asemenea, acum a imprima x din nou, și sincer,
dacă Primesc un pic confuz cu privire la unde sunt, am posibilitatea să tastați lista de lista
și vezi doar câteva context în jurul punctul de fapt sunt la.
Și acum am posibilitatea să tastați următor, și acolo x este 1.
Acum tip următor.
Oh, y este 2.
Și din nou, ea este confuz, deoarece producția GDB lui
este amestecat cu propria mea ieșire.
Dar, dacă vă păstrați în minte, de uitându-se înainte și înapoi la codul
sau de stabilire în parte by-side poate, veți
vedea că într-adevăr sunt doar pas cu pas prin programul meu.
>> Dar observați ce se întâmplă în continuare, la propriu.
Iată linia 22.
Lasă-mă să merg pe ea, se deplasează astfel pe la 23, iar în cazul în care am imprima x acum, încă unul.
Și dacă y imprima acum, încă unul.
Deci, acest lucru nu este un exercițiu util.
Deci, să refaceți acest lucru.
Lasă-mă să mă întorc până la alerga top și de tip nou.
Și spune programului care fiind depanate
a început deja, a pornit de la început.
Da, hai să facem asta din nou.
Și de această dată să facă în continuare, următor, next, next, next,
dar acum lucrurile devin interesante.
Acum vreau să-și intensifice în swap, așa că nu tastați următoarea.
Am de tip pas, iar acum observăm o mi-a sărit în linie noswap.c 33.
Dacă mă întorc la gedit, ceea ce-i linia 33?
Acesta este primul real linie de cod în interiorul de swap.
Ceea ce este frumos, pentru că acum pot fel de poke în jurul și de a lua curios
ca la ceea ce se întâmplă cu adevărat acolo.
Lasă-mă să imprimați tmp.
Uau.
De ce are tmp avea unele nebun, valoare gunoi fals?
Audiența: Nu a fost inițializat.
SPEAKER 1: Nu a fost inițializat.
Și într-adevăr, atunci când executați un program, ai dat o grămadă de memorie
de sistemul de operare, dar tu nu s-au inițializat valori,
deci indiferent de biți esti văd aici, chiar dacă este
acest negativ nebun mare număr, înseamnă doar
că acestea sunt rămășițele de la unele utilizarea anterioară a acelui RAM,
chiar dacă eu nu am am nevoie de el încă.
Așa că acum am de gând să merg mai departe și de tip următor, iar dacă am introduce acum tmp imprimare,
ceea ce ar trebui să văd?
Oricare ar fi valoarea unui fost, o este primul argument, doar
ca x a fost primul lucru fiind trecut în,
așa a și x trebuie să fie aceeași, astfel imprima tmp ar trebui să-mi imprima o.
>> Deci, ceea ce veți vedea în set problemă trei este un tutorial de felul pe GDB,
dar dau seama că acesta este începutul de o privire la un instrument care va de fapt
ajuta să rezolvați problemele mult mai eficient.
Ce suntem în cele din urmă va face miercuri
se începe cu coaja înapoi câteva straturi și scoate niște roți de formare.
Asta șir lucru numit ca ne-am folosit de ceva timp,
vom lua încet că departe de la tine și începe să vorbești despre
ceva mai ezoteric cunoscut ca char *,
dar vom face acest lucru frumos și mai întâi ușor, chiar dacă indicii,
cum se numesc, se poate face ceva lucruri foarte rele, dacă abuzate,
uitandu-se la un mic claymation de la prietenul nostru Nick Parlante de la Stanford
Universitatea, un profesor de la calculator știință care au pus împreună acest preview
de ceea ce va urma această miercuri.
>> [VIDEO PLAYBACK]
Hei, Binky.
Trezește-te.
E timpul pentru distracție pointer.
>> Ce-i asta?
Aflați mai multe despre indicii?
Ce bine!
[END VIDEO PLAYBACK]
SPEAKER 1: Asta va asteapta miercuri.
Ne vedem atunci.
[VIDEO PLAYBACK]
-Si Acum, Deep Gânduri, de Daven Farnham.
>> De ce suntem noi de învățare C?
De ce nu A +?
>> [Râsete]
>> [END VIDEO PLAYBACK]