[Muzikos grojimo] 

SPEAKER 1: Gerai, tai yra CS50, ir tai yra keturios savaitės pradžia, ir kaip jūs galbūt girdėjote arba skaityti, pasaulis buvo nutraukti. Ėjimas visame internete buvo žinias ir supratimą iš programoje, apie klaidą programavimo kalba vadinama bash. Tai buvo nuostabiai firminių kaip Shellshock, arba bash duris, bet tokių straipsnių nebuvo neįprasta. Ir iš tiesų, daugelis iš jų pareikšti sugrąžina Heartbleed, kurį gali pastebėjau, Paspauskite Back praėjusį pavasarį, o buvo panašiai gana dramatiška. Dabar tie iš jūsų čia šiandien, kaip ir daugelis iš jūsų turi, net jei jūs nesuprantate, ką svabiausia, girdėjote Shellshock? Visos teisės, ir kaip daugelis iš jūsų turi kompiuterius, kad yra pažeidžiamos? Gerai, ten turėtų būti daug, daug daugiau rankų iki dabar dėl priežasčių, matysime. 

Leiskite pažvelgti į tai, kas atrodo jau vyksta žiniasklaidoje ir tada paaiškinti, kad tai šiek tiek Čia mums techniškai. 

SPEAKER 2: Saugumo ekspertai turi perspėjo, kad rimtas trūkumas galėtų būti apie paveikti šimtus Milijonai pasaulio interneto vartotojų. Taigi, kas tiksliai yra klaida, kad buvo dubliuotas Shellshock ir ką jis daro? Na, Shellshock taip pat žinomas kaip Bash klaida, programinės įrangos jis naudoja. Piratai naudoti viruso nuskaityti pažeidžiami sistemos veikia Linux ir Unix operacinės sistemos, o tada užkrėsti juos. Bash yra komandų eilutės apvalkalas. Tai leidžia vartotojams klausimas komandas pradėti programos ir funkcijos, kaip programinės įrangos įvesdami tekstą. Tai paprastai naudojama programuotojų ir neturėtų būti atviras visam pasauliui, nors Shellshock keičia tai. 

Na, worringly, kai kurie analitikai įspėja, kad gali būti didesnis pavojus, nes Shellshock leidžia visiškai kontrolė užsikrėtusiu mašina, o Heartbleed leidžiama tik hakeriai šnipinėti kompiuterius. Tai taip rimta, tai buvo įvertinta 10 iš 10 už sunkumą pagal Nacionalinės Luka duomenų bazė. 2/3 visų interneto serverių yra ne rizika, įskaitant kai kuriose "Mac kompiuteriais. Na, įsitikinkite, kad jūs pleistras jūsų sistemos dabar. Kiekvienas talpinimas svetainėje veikia paveiktos operacinės sistemos kaip galima greičiau turėtų imtis veiksmų. Kiekvienas, kuris gali sau leisti ji turėtų atrodyti jų stebėjimo ir interneto taikymo ugniasienės atkreipti dėmesį išpuolių. SPEAKER 3: Blogiausias dalykas kad gali atsitikti yra kad kažkas būtų rašyti kodą, kad automatiškai eiti ir nuskaityti interneto ir turėtų įtakos visų šių kompiuterių. Ir kai jie tai padaryti, taip pat, blogiausias dalykas, jie gali padaryti tiesiog ištrinti viską, arba uždaryti svetaines žemyn. Taigi, mes galime pamatyti žalą iš šiuo požiūriu, kur mes turėtume kenkėjiškų žmonės kurie tiesiog nuspręsti, kad sukelti sumaištį iškeliant sistemas žemyn arba išbraukiant failus ir panašius dalykus. SPEAKER 2: Vieni sako, tai yra viena iš iš labiausiai sunku išmatuoti riktai metų, ir jis gali trukti savaites ar net mėnesių, siekiant nustatyti jos pagrindinis poveikį. 

SPEAKER 1: Taigi visa tai yra tiesa, bet juokingas dalykas yra, beveik visi vaizdais, jums tik pamačiau, išskyrus gal klaviatūroje, neturi nieko bendro su klaida kokia. Serveriai ir laidai ir tt, tai tarsi liestine susiję, bet tuo core tai tikrai gana susipažinę, kas vyksta čia. Tiesą sakant, leiskite man eiti į mūsų CS50 prietaisas. Leiskite man eiti į priekį ir maksimaliai terminalo langą čia. Ir vaikinai buvo naudojant tai, arba įterpti versiją dalį, į gedit, kad rašyti programas, įrašykite komandas, ir taip toliau, ir tai yra iš tikrųjų, ir turi buvo už savaitės, Bash, B-A-S-H. Tai Bornas-vėl lukštais, kuri yra tik išgalvotas būdas pasakyti, tai programa, kuri turi mirksi greitai, efektyviai, kad sėdi ten laukia įvesties jums. Ir tai komanda eilutės sąsaja, per kurią vaikinai buvo paleisti komandas ir galiausiai sudaromas ir tada veikia programos. 

Bet bash pat programavimas kalba tokia prasme. Jūs žinote, kad yra komandų kaip cd ir ls ir žvangėjimas ir kiti, bet jūs galite nustatyti savo komandas juos įgyvendinti per Bash. Dabar mes nesiruošia eiti į labai išsamiai kaip bash programavimo kalbą, bet žinoti, kad, pavyzdžiui, šiuo metu ten ne komanda vadinama "labas". Taigi jis gali būti rasta vienas iš šių paketų. Tai nėra įdiegta mano kompiuteryje. Paklauskite savo administratorių. Bet jei aš ten noriu būti programa vadinamas "labas" ir "Bash arba mano eilutę Aš iš tikrųjų galite naudoti sintaksę, kad tai labai patiko C. Tai ne visai tas pats, bet atrodo gana panašios į funkcija, nors ir trūksta kai kurių detalių. Niekas, atrodo, kad taip atsitiktų, bet dabar, jei aš tipo "labas" jūs iš tikrųjų galite rašyti programa, o ne C, o ne "Java", ne kitoje programavimo kalba, bet pati Bash. 

Dabar svarbiausia čia yra tai, kad aš parašiau pavadinimas aš norėjau duoti šią naują komandą, ir skliaustai taip pat Simboliška tai yra funkcija. Kaip panaikinti, taip pat galite padaryti įdomus dalykai, ir iš tiesų, net ir Mac OS, tai programa, vadinama terminalas. Jis ateina pastatytas į kas s kompiuteris, kuris turi "Mac" šiame kambaryje, ir jūs galite padaryti panašius dalykus Mac OS, bet tu gali eiti daugiau nei, kad. Ir tai yra mažai liestinę, bet tai rūšies įdomus. Man buvo priminta šį rytą, kai galvoju tai per, iš mažai žaidimas aš žaisti su vienu iš CS50 buvusių TFS , pagal kurią bet kuriuo metu jis pėsčiomis nuo jo klaviatūra su jo ekrane atrakintas, Norėčiau įvykdyti komandą kaip this-- "say hello". Ir dabar kiekvieną kartą jis grįžo į savo klaviatūra, kai aš pašalinta ekraną ir jis atsisėsti, pabandyti padaryti tam tikrą darbą, sudaryti sąrašą savo directory-- turinį 

[Garso atkūrimas] 

-Hello. Sveiki. 

SPEAKER 1: Taigi, tiesą sakant, jis iš tikrųjų nebuvo "labas". Tai paprastai būdavo kažkas panašesnė į that-- [Garso atkūrimas] -Beep. SPEAKER 1: --that aš would-- todėl jo kompiuteris būtų prisiekiu į jį bet kuriuo metu, jis iš tikrųjų atsisėdo prie jo klaviatūra. Ir labai greitai jis suprato, nepalikti jo ekranas atrakintas. Tačiau tai rodo, kad rūšiuoti kvailas įdomus, kad jums gali turėti kažką panašaus Bash. Bet tai šiek tiek daugiau rimtas, būti tikri, kad ne. Ir iš tikrųjų, tai yra viena iš pavojingiausių ir ilgalaikę klaidas kad tikrai nukentėjo pasaulį globaliai. Ši klaida buvo maždaug už maždaug 20 metų, ir jums bus kaldinamos tik momentas savo santykinio paprastumo. 

Taigi tai yra atstovas liepk, kad jei jūs savo "Mac", pažodžiui dabar kai jūs turite savo dangtelis atidarytas, galite pabandyti rašyti į tą programa, vadinama terminalas. Terminalas pagal Programos Utilities-- vieną kartą, Windows vartotojai neturi nerimauti šiuo konkrečiu threat-- bet tiems iš jūsų, su "Mac" galite įvesti tai į langą, kaip aš tai padaryti čia ir jei tipo kad į šią programą vadinamas terminalo, kaip aš dabar daryti, jei matote žodį "pažeidžiami" kompiuteris pažeidžiamos naudojimo. 

Dabar ką tai iš tikrųjų reiškia? Ir tai yra tiesa keletas gana kvailai sintaksė, bet tegul bent atkreipti dėmesį kai įdomių aspektų. Taigi, čia yra keletas sintaksė, kuri atrodo mažai pažįstamas, bent iš C ir programavimo apskritai. Matau keletą skliausteliuose, kabliataškiais, garbanotas petnešos, ir tokia, bet it turns out, kad šis kvailas dalykas čia geltonai esmės yra funkcija kad nieko nedaro. Dvitaškis priemonė nieko, ir kabliataškis tai nustoti daryti nieko. Taigi viduje iš jų garbanotieji petnešų, tai kad turiu lygūs pasirašyti į kairę, tai yra iš esmės sukurti komandą, ar kintamasis, vadinamas x ir ją skiriant kad geltona šiek tiek kodo ten. Tai galėtų būti kažkas panašaus į "aidas labas "arba" pasakyti pyptelėjimas "ar kažkas panašus į tai. Tačiau pastebėti, jei jūsų akyse Brody toliau į dešinę, yra daugiau į šią eilutę, nei tik tos kabliataškiu pabaigoje. "Echo pažeidžiamas", ir tada išskyrus tas, kurios ten net daugiau. Kitas kabliataškis, bash-c :. 

Taigi ilga istorija trumpa, šis kodas linija pakanka įtikinamų kompiuteris tai pažeidžiami darai kažką kad jūs norite daryti, nes ten yra bash, kuriuo klaidą nors bash turėjo sustoti skaito linijos komandų dešinėje ten po geltoną tekstą, už 20-plius metų senumo klaidų, Bash tikrųjų buvo skaityti po šios kabliataškiu ir gana daug daryti tai, ką jis pasakė. 

Taigi, kas yra potekstė iš kurios galiausiai? Aš ką tik pasakė "Echo labas" arba "echo pažeidžiami" bet ką daryti, jei jums padarė kažką iš tikrųjų kenksminga, kaip rm-rf *, kuri galbūt ne kada nors įvedėte anksčiau, ir atvirai tikriausiai neturėtų pernelyg greitai, nes jūs galite padaryti daug žalos su juo. Kodėl? rm ką daro, žinoma? Pašalina. * Reiškia ką? Viskas. Taigi, tai vadinamasis laukinių kortelė, todėl tai reiškia, ištrinti viską einamojo katalogo. r atsitinka reiškia rekursinis Tai reiškia, jei tai, ką jūs ištrinti yra katalogas, o viduje ten yra kitų failų ir kitų katalogų, rekursyviai pasinerti į ten ir i ¹ trinti visus, kad. Ir -f yra blogiausias iš jų visų. Kiekvienas žino, ką reiškia -f čia? Pajėgų. Taigi priversti priemones, net jei tai yra bloga idėja, padaryti be raginimo man tolesniam patvirtinimo. Taigi, jūs žinote, mes juoktis tai, tačiau atvirai kalbant, aš tikriausiai įrašykite šiuos kelis kartus dieną, nes realybės tai yra greičiausias būdas ištrinti visa krūva daiktų. Bet net ir aš padariau tam tikrą žalą. 

Bet jei jūs buvote apgauti kompiuterį į apibrėžiant kai kvailas kintamasis ar funkcija vadinama x, bet tada tracking kompiuterį į vykdančiosios už tos ribos funkcija, ir po tos kabliataškiu, jūs iš tiesų gali apgauti kompiuterį į vykdančiosios kažką panašaus rm-rf ar Parašyk komanda arba Kopijuoti komanda. Viskas tiesiog galite padaryti su kompiuteris, ar jis šalinti failus, kurti failus, šiukšlės nors, puola šiek serverį nuotoliniu būdu, jei jūs galite išreikšti tai su komanda, jūs gali apgauti kompiuterį į tai, kad. 

Dabar, kas yra pavyzdys kaip jūs galite tai padaryti? Na, yra Kompiuterių daug nuo interneto tekančiu Bash. Visi mus "Mac" vartotojams yra tarp jų. Linux serverių aikštelė yra tarp jiems taip pat, ir Unix serverių. Langai vėl gauna santykinai nuo kabliuko nebent jūs įdiegėte speciali programinė įranga. Dabar serverių daug, už pavyzdžiui, paleisti žiniatinklio serverių, ir tai Linux yra galbūt Populiariausias operacinė sistema paleisti kompiuteriuose internete kad tarnauja tinklalapius. Dabar, kaip matysime vėliau semestrą, kai galite atsiųsti iš prašymą Jūsų browser-- Chrome "Internet Explorer", whatever-- į nuotolinio serverio, paaiškėja, kad, nors jūs tiesiog atspausdinti www.example.com, Jūsų naršyklė siunčia pranešimą tai šiek tiek daugiau paslaptingų, kaip šis. 

Bet pastebiu truputį kažką keisto. Pirmos dvi eilutės Aš niekada nemačiau anksčiau, bet jie nežiūri ypač pavojinga. Tačiau pastebėti, ką aš pavogtas trečią eilutę čia. Jei blogas vaikinas buvo išsiųsti žinutę kaip tai iš savo kompiuterio pažeidžiamai Mac arba pažeidžiami Linux serverio, Įdomiausia tai, kad bash, paprasta mažai komandų eilutę, yra visur ir dažnai Naudoti iš esmės vykdyti Į turinį pranešimą, kad ji gauna. Ir ta logika, jūs galite apgauti interneto serverį, todėl, siunčiant kažką panašaus Vartotojo agentas, kuris paprastai Manoma, kad pasakyti pavadinti savo naršyklėje. Vartotojo agentas Chrome Vartotojo agentas interneto Explorer "," Vartotojo agentas "Firefox", tai yra tik jūsų naršyklės būdas identifikuoti save. Bet jei blogas vaikinas labai protingai sako, mm mm, aš nesiruošia papasakoti ką mano naršyklė, Aš vietoj ketina siųsti jums tai paslaptingas atrodantis dalykas su rm-rf * Į jį, galite tiesiog apgauti pažeidžiama interneto serverį internete į vykdančiosios tiksliai, kad ten išbraukiant visus failus. Ir tiesą sakant, tai ne net blogiausia. Jūs galite padaryti bet ką. Galite pradėti platinamas denial of service atakos jei siunčiamas šį pranešimą sveiki kekių interneto serverių ir tada turėjo juos visus nusileisti, už pavyzdžiui, ant Harvard.edu serverių, ir jūs galite rūšiuoti ir sprogimo iš jų gi pagal tinklo srautą, kad buvo kitaip sukėlė šio blogiukas. 

Taigi, ilga istorija trumpa, beveik visi šiame kambaryje, kuris valdo "Mac" yra pažeidžiami tai. Sidabro pamušalas yra tai, kad, jei esate veikia interneto serverį į savo kompiuterį, ir jei jūs iš tikrųjų sukonfigūruota tai, kad būtų galima kažką panašaus SSH į jį, jūs iš tikrųjų saugus. Tai yra pažeidžiamos, tačiau nėra vienas bando patekti į savo kompiuterį, todėl jūs galite rūšiuoti tikri. Tačiau "Apple" netrukus būti atnaujinti dėl šios pataisos. Linux pasaulyje jau išleista pataisymai Fedora ir Ubuntu skaičius ir kiti "Linux" versijas, ir iš tiesų jei paleisti naujinimą 50 į prietaisą, net, kad taip pat bus būti atnaujinti ir pataisyti. Bet tai taip pat turi ne tikrai buvo pažeidžiamos, nes, jei jūs tinkered su prietaisu , ir padarė savo nešiojamas viešai prieinami internete, kuri yra ne pagal nutylėjimą, Jūs tikrųjų buvo gerai, nes iš užkardos ir kitais metodais. 

Bet tai kraštutinis pavyzdys klaidą kad mes gyveno už pažodžiui 20 metų, ir kas žino, jei kas nors visą šį laiką buvo žinoma apie tai? Ir iš tikrųjų, tai yra viena iš pagrindinės problemos kad matysime vėliau semestras apie saugumą, yra tai, kad kaip ir realiame pasaulyje, geri vaikinai yra ne trūkumas. Norėdami, kad blogi vaikinai, mes turime įsitikinkite, kad kiekvienas durų yra užrakintas, kad kiekvienas langas yra saugi, kad kiekvienas įvažiavimo į namus yra saugus išlaikyti blogi vaikinai iš. Bet ką daro blogas vaikinas turi padaryti, kad iš tikrųjų pakenkti jūsų namuose ir pavogti iš jūsų? Jis arba ji tiesiog turi rasti vieną atrakinta durys, vienas neveikia langas, ar kažkas palei tas linijas, ir tai Tas pats dalykas kompiuterinį saugumą. Mes galime parašyti milijonus linijos programavimo kodą ir išleisti šimtus ar net tūkstančius valandų bando gauti tai teisinga, bet jei jums padaryti tik vieną klaida teisingumą, galite įdėti visą sistemą ir Iš tiesų šiuo atveju visa internete ir pasaulis pavojus. 

Taigi, jei norite sužinoti daugiau apie tai, eiti į šį URL čia. Nėra būtinybė imtis veiksmų vakarą, nebent esate tarp tų, patogiau, kad jau veikia savo interneto serverio, tokiu atveju jums reikia, Tiesą sakant, atnaujinti savo įrangą. 

Ir tai taip pat yra pavadinimas kalbos, o dabar popierius, kad mes susiję su Kursas tinklapyje šiandien. Tai buvo pagal kolegos pavadintas Ken Thompson, kuris buvo priimti labai garsus apdovanojimas kompiuterių mokslo, ir jis davė šią kalbą keletą metų Prieš esmės tą pačią temą. Klausia žmonės klausimas, turėtų tikrai pasitikėjimas, galiausiai, programinė įranga, kurią buvote? Pavyzdžiui, mes visi turime buvo raštu programas, ir mes pildė juos su Zaszczękać. Ir su savo žiniomis, jūs raštu kokių nors CS50 programos, kur yra atgal durų rūšių, yra būdas kad blogas vaikinas, jei veikia savo programą, galėtų perimti kompiuterio? Tikriausiai ne, tiesa? Mario ir gobšus, ir kredito. Tai yra visi gana mažos programos. Jūs turite būti gana blogai, jei jums iš tikrųjų padarė visa jūsų kompiuteris pažeidžiamas po to rašyti 10 ar 20 eilučių kodo, arba bent jau nežino, kai poveikio saugumui. Dabar aš sakau, kad Krotochwilnie, bet mes ketiname pamatyti šiandien ir šią savaitę tai tikrai tikrai, tikrai lengva būti blogai ir padaryti dar trumpos programos pažeidžiami. 

Bet dabar, bent jau suvokti, kad klausimas yra čia paprašė apie Zaszczękać į kompiliatorių. Kodėl mes buvo pasitikėti Zaszczękać per pastaruosius dvejus ar tris savaites? Kas yra pasakyti, kad tas, kas rašė Zaszczękać neturėjo "jei" sąlygą yra kad iš esmės švirkščiamas keletą nulių ir tie, kurie į kiekvieną programą ji rengia kad leistų jam ar jai prieiga kompiuteris, kai esate miega ir jūsų nešiojamas dangtis yra atidarytas ir jūsų kompiuteris veikia? Teisė? Mes turime šį garbė sistemos richtige dabar, kur mes tikimės, kad Zaszczękać yra teisėtas. Jūs pasitikite, kad prietaisas yra teisėtas. Jūs pasitikite, kad tiesiog kiekviena programa jūsų Mac arba PC yra patikimas. Ir kaip tai paprasta klaidą rodo, net jei ji nėra kenksminga, tai visiškai ne gali būti atvejis. 

Taigi, jūs turėtumėte bijoti, kaip pragaras. Atvirai kalbant, nėra paprasta sprendimas tai kita nei visuomenės sąmoningumo ugdymas rūšiuoti didėjančio sudėtingumo kad mes statyti ant mūsų kompiuterines sistemas, ir kaip vis labiau pažeidžiama mes galime labai gerai būti. 

Dabar su tai sakė, Breakout. Taigi Breakout yra problema nustatyti tris, ir Breakout žaidimas iš pasekėjai kad jūs galite prisiminti, bet mums problemą nustatyti trys, jis leidžia mums imtis dalykų atsargines žingsniu taip, kad kai mes rašome programas, net terminalo langą, kaip šis, mes iš tikrųjų gali paleisti, galiausiai, grafiniai programos ne kitaip nei mes turėjome prieiga prie į nulio. Taigi tai yra štabo įgyvendinimas Breakout, kuri yra tik tai plytų laužymas žaidimas, kad jūs judėti savo irklas atgal ir atgal, ir jūs Hit kamuolys prieš tuos spalvotų plytų iki viršaus. Taigi, tai yra pareikšti mus rūšiuoti atgal, iš kur mes galėjome būti labai greitai su nulio, o dabar su C, įgyvendinti mūsų grafinės vartotojo sąsajos. 

Tačiau daugiau nei, kad tai problema rinkinys yra pirmasis kurioje mes teikiame Jūs kodo krūva. Ir iš tiesų, aš suteikti aiškų dėmesį į tai, nes ypač tiems mažiau patogūs, tai , problema nustatyti bent jau iš pirmo žvilgsnio, ketina jaustis kaip mes atlikome jį vienu žingsniu. Kadangi mes davė jums, dėl kai kurių paieškos ir rūšiavimas problemas pset, kodo, kad mes rašė krūva, ir pastabų pora kad pasakyti "padaryti" kur jūs turite užpildyti ruošiniai. Taigi ne per baisu, bet tai pirmas kartas mes atiduodami jums kodą, kad jums reikia pirmiausia perskaityti, suprasti, ir tada pridėti prie ir užbaigti jį. 

Ir tada su Breakout, mes ketiname daryti tą patį, suteikdama jums keletą dešimčių daugiau eilučių kodo, kad, tiesą sakant, suteiks jums Struktūros aikštelė žaidimas, bet sustoti įgyvendinimo plytas ir kamuolys ir irklas, bet mes įgyvendinti kai kurių kitų funkcijų. Ir net, kad iš pirmo žvilgsnio, vėlgi, ypač jei mažiau patogūs, gali atrodyti ypač nelengvas ir manote, kad tiek daug naujų funkcijų jums reikia wrap savo mintis aplink, ir tai tiesa. Tačiau turėkite galvoje, kad tai labai patiko nulio. Šansų yra tu negali naudoti visus dėlionės gabaliukai nulio. Šansų yra tu nerūpi, į kuriuos vyniojami jūsų protas aplink juos visus nes visa tai vyko, buvo pirmo žvilgsnio suprasti, oi, kad tai, ką aš galiu padaryti, su tuo galvosūkį gabalas. Ir iš tiesų, problema nustatyti 3 spec, mes jums atkreipti ne dokumentacijoje, kuri bus supažindinti jus su kai kurių naujų funkcijų, ir galiausiai programavimas konstruoja jūs naudojate. Sąlygos, ratai, kintamieji, ir funkcijos bus identiškas tai, ką mes matėme iki šiol. 

Taigi iš tiesų, ką mes suteiksime Jums yra tam tikra imties kodas, leidžia jums sukurti langą kad atrodo ne kitaip tai, ir galiausiai ją paversti kažkas labai panašaus į tai. Taigi pasinaudoti CS50, aptarti darbo valandomis, ir daugiau, ir džiaukis tai, kad kodo suma jums reikia parašyti iš tikrųjų viskas ne tai, kad daug. Pirmasis uždavinys yra tiesiog Aklimatizuojama sau tam tikras kodas, mes parašiau. 

Bet kokie pset3 klausimai, Shellshock, ar kitaip? 

PUBLIKA: Atrodė išgyvena su Breakout kad kodas yra beveik Objektinis stiliaus, bet aš maniau, C buvo Objektinis programa. SPEAKER 1: puikus klausimas. Taigi žvelgdami pro paskirstymo kodas, kodas mes rašė pset3, tiems pažįstamas, jį atrodo, kad jis mažai Objektinis. Trumpas atsakymas yra, tai yra. Tai kaip jums suderinimas gali padaryti Objektinis kodą, naudodamas kaip C kalba, tačiau tai vis vien galiausiai procesinis. Viduje nėra jokių metodų kintamieji, kaip pamatysite. Bet tai primena, kad. Ir mes matome, kad funkcija vėl kai mes gauti PHP ir JavaScript link pabaigos semestrą. Bet dabar, manau, apie tai, kaip kas yra užuomina į priekį. Geras klausimas. Viskas gerai. Taigi Merge sort buvo, kaip mes left dalykai paskutinį kartą. Ir sujungti tarsi buvo vėsu jausmas, kad tai buvo taip daug greičiau, bent grindžiamas greitomis bandymų mes padarėme praeitą savaitę, nei, tarkim, burbulas Rūšiuoti atranka rikiuoti, įterpimo rūšiuoti. Ir tai, kas buvo tvarkingas yra tik kaip trumpai ir švariai galite išreikšti. Ir ką mes pasakyti, kad tai buvo viršutinis laikytis ant bėgimo metu susilieja rūšiuoti? Taip? 

PUBLIKA: n log n? 

SPEAKER 1: n log n, teisinga. n log n. Ir mes grįžti į tai, kas, kad iš tikrųjų reiškia arba kai kuri ateina iš, bet tai buvo geriau nei bėgimo metu kad mes pamačiau burbulas parinkimas ir įterpimo rūšiuoti? Taigi n kvadratu. n kvadratu yra didesnis nei šis, ir net jei tai nėra akivaizdu, žinau, kad žurnalas n yra mažesnis nei n, Taigi, jei jūs n kartų kažkas mažesnis nei n, ji bus mažesnė nei n kvadratu. Tai intuicijos tiek ten. Bet mes sumokėjo kainą už tai. Jis buvo greitesnis, bet tema, kuri pradėjo ryškėti praėjusią savaitę buvo toks kompromisas. Gavau geresnį rezultatą laikas išmintingas, bet ką aš turiu išleisti kitą ranka, kad būtų pasiekti? 

PUBLIKA: Atmintis. SPEAKER 1: Pasakykite naujo? PUBLIKA: Atmintis. SPEAKER 1: Atmintis, arba erdvė apskritai. Ir tai buvo ne super Akivaizdu, su mūsų žmonėmis, bet prisiminti, kad mūsų savanoriai buvo gerinimo pirmyn ir gerinimo atgal kaip nors ten masyvas čia, ir kaip nors ten Antrasis masyvas čia jie gali naudoti, nes mes reikalingos Kažkur sujungti tuos žmonės. Mes galime ne tik apsikeitimo juos vietoje. Taigi sujungti rikiuoti sverto yra daugiau erdvės, kuri mes nereikėjo su kiti algoritmai, bet aukštyn kojom yra tai, kad daug greičiau. Ir tiesą sakant, ir realiame pasaulyje vietos tai days-- RAM, kietojo disko space-- yra gana pigus, ir taip, kad tai nebūtinai blogas dalykas. 

Taigi leiskite priimti greitai pažvelgti, mažai daugiau metodiškai, ką mes padarėme, ir kodėl mes sakė, kad tai buvo n log n. Taigi, čia yra aštuoni numeriai ir Aštuoni savanoriai mes turėjome paskutinį kartą. Ir pirmas dalykas, kad suliejimas Rūšiuoti liepė mums padaryti, buvo, ką? PUBLIKA: Padalinkite į dvi. SPEAKER 1: Pasakykite naujo? PUBLIKA: Padalinkite į dvi. SPEAKER 1: Padalinkite į dvi, tiesa. Tai labai primena telefonų knyga, iš atskirties ir užkariauti apskritai. Taigi, mes pažvelgė į kairėje pusėje. Ir tada, kai mes pasakėme, tarsi kairė pusė elementų, ką gi mes šalia pasakyti? Rūšiuoti kairėje pusėje, kairėje pusė, kuri leido mums, po dalijant į dvi dalis, sutelkti dėmesį į keturių ir dviejų. 

Kaip jūs rūšiuoti sąrašą dabar, geltonos spalvos, dydžio du, naudojant Sujungti Rūšiuoti? Na padalinti per pusę, ir rūšiuoti kairįjį pusę. Ir tai buvo, kur viskas turiu šiek tiek kvailas trumpai. Kaip jūs rūšiuoti sąrašą, kad yra iš dydis vienas, kaip šį numerį keturių čia? Tai rūšiuojami. Jūs baigsite. 

Bet tada, kaip jūs perrikiuoti sąrašą dydis vienas, kai jis numeris du? Na, tas pats, bet dabar, kas buvo Trečias ir svarbiausias žingsnis Merge Rūšiuoti? Jūs turėjo sujungti į kairę pusę ir į dešinę pusę. Ir kai mes padarėme, mes pažvelgė ne keturių, mes pažvelgė dviejų. Mes nusprendėme visą teisę, Akivaizdu, du ateina pirma, todėl mes įdėti du jos vieta, o po keturių. Ir dabar jūs turite natūra atgal, ir tai yra tarsi charakteristika iš kurio, kaip suliejimo algoritmus Rūšiuoti, atsukti atmintyje. Koks buvo kitas linija istorija? Ką turėčiau būti dėmesio toliau? Teisė pusė kairėje pusę, Kuris yra šeši aštuoni. 

Taigi leiskite man tiesiog žingsnis per šį be belaboring tašką per daug. Šešių ir aštuonių, tada šešių yra rūšiuojami, aštuonių rūšiuojamos. Sujungti juos kartu, kaip kad, o dabar kitas didelis žingsnis yra, žinoma, rūšiuoti tinkamą pusę nuo Pirmasis žingsnis šio algoritmo. Taigi, mes sutelkti dėmesį į vieną, trys, septyni, penki. Tada sutelkti dėmesį į kairėje pusėje. Kairė pusė, kad teisė pusė kad ir tada sujungti į vieną ir trijų. Tada dešiniuoju pusę, tada į kairę pusę jo, tada į dešinę pusę jo. Sujungti jį, o dabar kas žingsnis lieka? Sujungti didelis kairėje pusėje ir didelis Teisė pusė, todėl vienas eina ten, tada du, tada tris, tada keturių, tada penkis, tada šešis, tada septynių, tada aštuoni. 

Taigi, dabar kodėl tai galiausiai atskleidžia, ypač jei n ir logaritmai daugiau apskritai, o pabėgti jums, bent jau pastaraisiais atminties? Na, pastebėsite, šis dalykas aukštį. Mes turėjome aštuonis elementus, ir mes padalintas iš dviejų, iš dviejų, iš dviejų. Taigi prisijunkite bazę du aštuonių suteikia mums tris. Ir pasitikėk manimi, kad jei tiek miglotas, kad. Bet prisijungti bazė du aštuonių yra trys, taip mes padarėme tris sluoksnius sujungti. Ir kai mes susijungė elementai, kaip daug elementų Ar mes pažvelgti į kiekvieną iš šių eilučių? N visų, tiesa? Kadangi sujungti viršutinėje eilutėje, nors mes tai padarėme dalimis, mes galiausiai palietė kiekvieną numerį kartą. Ir antroje eilėje, prie sujungti šiuos sąrašus dydžio dviejų, mes turėjome paliesti kiekvieną elementą vieną kartą. Ir tada čia tikrai aiškiai paskutinėje eilėje, mes turėjome paliesti kiekvieną iš tų elementai iš karto, bet tik vieną kartą, taip čia yra, tuomet mūsų n log n. 

O dabar tik, kad viskas šiek tiek daugiau formalus tik už akimirką, jei jums buvo dabar analizuoti tai esant aukštesnio lygio rūšiuoti ir pabandyti ir nuspręsti, kaip gali tu apie išreikšdami važiavimo laikas iš šio algoritmo tiesiog žiūri į jį, o ne naudojant nenatūralu pavyzdį? Na, kiek laiko jūs pasakytumėte žingsnis, kaip tai geltonai užtruktų, jei n <2 grąža? Štai didelis O ką? Taigi, aš matau vieną, todėl vienas žingsnis, gal du žingsniai, nes jis, jei ir tada grįžti, bet tai pastovus laikas, tiesa? Sakome O (1), ir kad kaip aš išreikšti tai. T, tiesiog bėgančio laiko. n yra nuo įėjimo dydis, taip T (n), tik išgalvotas būdas sakydamas judamasis laikas skiriamas indėlis dydžio n bus ant tam pastovaus metu, O (1). 

Bet kitaip, ką apie tai? Kaip jums išreikšti veikia laiko šio geltona linija? T ką? Galite rūšies apgauti čia ir atsakyti į mano klausimą cikliškai. Taigi, jei veikimo laikas Apskritai mes tiesiog pasakyti yra T (n). Ir dabar jūs rūšies punting čia ir sakydamas, gerai, tiesiog surūšiuoti kairiąją pusę, ir tada rūšiuoti tinkamą pusę. Kaip gali mes simboliškai atstovauti važiavimo laikas iš šio geltona linija? T ką? Kas iš įėjimo dydis? n virš dviejų. Kodėl ne aš tiesiog pasakyti, kad? Ir tai yra dar vienas T (n / 2) ir tada vėl, jei aš sujungti du atrinktas puses, kiek elementų I am going turi liesti iš viso? n. Taigi aš galiu išreikšti tai, tiesiog turi būti natūra išgalvotas, kaip veikia laiko apskritai. T (n) yra tik važiavimo laikas T (n / 2), plius T (n / 2), į kairę pusę ir dešinę pusę, plius O (n), kuris yra turbūt n žingsnių, bet gal, jei aš naudoju du pirštus, tai du kartus daugiau priemonių, tačiau tai tiesinis. Tai kai žingsnių skaičius tai n faktorius, taip mes galime išreikšti tai, kaip šis. Ir tai, kai dabar mes punt į atgal mūsų aukštosios mokyklos matematikos vadovėlio mes, kad pasikartos galiausiai baigiasi lygu tai, n kartų log n, jei jūs iš tikrųjų daryti iš matematikos daugiau formaliai. 

Štai tik du perspektyvas. Vienas programinio su sunkiai koduojami tipinį pavyzdį naudojant aštuonių skaitmenų ir daugiau Apskritai atrodo, kaip mes turime ten. Bet kas tikrai įdomu čia yra, vėlgi, tai dviračiu sąvoka. Aš naudoju už kilpos. Aš rūšies apibrėžimo kažkas požiūriu savaime, ne tik tai matematinė funkcija, bet taip pat, kalbant apie šios pseudo kodą. Tai pseudo kodas yra grįžtamojo tuo, kad dvi jos linijų iš esmės pasakoja jį eiti naudoti pati spręsti mažesnis problema yra mažesnės, ir vėl ir vėl ir vėl, kol mes drožti ją iki šio vadinamojo bazinio atveju. 

Taigi leiskite tikrųjų atkreipti patrauklesnės išsinešti iš šio taip. Leiskite man eiti į gedit ir imtis pažvelgti į kai kuriuos šiandienos kodo, visų pirma šis pavyzdys čia. Sigma 0, kuris, matyt, prideda numerius viena per n. Taigi pažiūrėkime, kas žino ir susipažinę čia. Pirmiausia mes turime pora apima, todėl nieko naujo ten. Prototipas. Aš šiek tiek miglotas ant tai po kelių dienų, bet ką gi mes sakome prototipas funkcija yra? PUBLIKA: [nesigirdi]. SPEAKER 1: Kas tai? PUBLIKA: Mes apie tai pranešti. SPEAKER 1: Mes apie tai pranešti. Taigi jūs mokote Zaszczękać, ei, nėra faktiškai įgyvendinti šį dar, bet kažkur šį failą, matyt, ketina būti funkcija vadinamas ką? Sigma. Ir tai tik pažadas, kad jis ketina atrodyti taip. Ji ketina imtis sveikasis skaičius, kaip input-- ir aš galiu būti aiškiau ir pasakyti int n --and tai ketina grįžti int, bet kabliataškiais priemonė, mm, aš gausiu aplink įgyvendinti tai šiek tiek vėliau. Vėlgi, Zaszczękać yra kvailas. Tai tik ketina žinoti, ką pasakyti, kad iš viršaus į apačią, todėl mes turime bent duoti tai, kas yra užuomina į priekį. 

Dabar pažvelkime pagrindinė čia. Leiskite slinkti žemyn čia ir pamatyti, kas pagrindinis daro. Tai nereiškia, kad seniai apie funkciją ir iš tikrųjų konstruktas čia yra susipažinę. Aš pareiškiu, kintama n, o tada Aš kvaršinti vartotojui vėl ir vėl teigiamo sveikojo skaičiaus, naudojant getInt, ir tik išeiti iš šio ciklo kai vartotojas įvykdė. Padaryti, o mes jau naudojamas kvaršinti, kad toje būdu vartotoją. Dabar tai yra įdomu. Aš pareiškiu, int, pavadintą "Atsakymas". Aš priskirti tai gražinama reikšmė iš funkcijos vadinamos "Sigma". Aš nežinau, kas tai daro dar, bet Prisimenu skelbiantis jį prieš akimirką. Ir tada aš einančios vertė, kad vartotojas turi įvesti, n, ir tada aš pranešti atsakymą. Na tegul pereikite atgal už truputi. Vykime į priekį į šį katalogą, kad sigma 0, ir iš tikrųjų paleisti šią programą ir pamatyti, kas atsitiks. Taigi, jei aš einu į priekį ir paleisti ši programa, ./sigma-0, ir aš tipo teigiamas sveikas kaip dviejų, Sigma, kaip graikų simbolis reiškia, yra tik ketiname pridėti visus numerius iš nulio iki dviejų. Taigi 0 ir 1 plius 2. Taigi tai turėtų tikiuosi man 3. Štai visa tai daro. Ir panašiai, jei aš paleisti tai vėl ir aš suteikti jai numerį tris, tai 3 plius 2, todėl tai 5, plius 1 turėtų duoti man 6. Ir tada, jei aš galiu gauti tikrai pamišę ir pradėkite rašyti didesnių skaičių, ji turėtų duoti man vis didesnę sumos. Taigi, kad viskas. 

Taigi, ką sigma atrodo? Na, tai gana paprasta. Tai, kaip mes galime įdiegė tai per pastaruosius porą savaičių. "Int" bus grąžinti tipas. Sigma vardas, ir jis trunka kintamasis m vietoj n. Aš pakeisti, kad iki viršaus. Tada tai tik normalumas patikrinti. Pamatysime, kodėl per vieną akimirką. Dabar aš pareiškiu kitą kintamąjį, suma, inicijuoti jį iki nulio. Tada aš turiu tai už linijos Iteracja, matyt dėl ​​aiškumo, nuo i = 1 "iki = M, kuris yra kokia vartotojas įvedėte, ir tada aš prieaugio panašaus sumą. Ir tada grąžinti sumą. 

Taigi klausimų pora. Vienas iš jų, galiu reikalauti mano pastabą, kad tai išvengiama pavojaus begalinis ciklas. Kodėl einančios neigiamas skaičius sukelti potencialiai begalinis ciklas? 

PUBLIKA: Jūs niekada nepasieks m. 

SPEAKER 1: Niekada nekiškite m. Bet m, praėjo, tad mano paprastą pavyzdį. Jei m yra priimtas pagal vartotojas kaip neigiamas. Nepriklausomai nuo to, pagrindinis. Pagrindinis apsaugo mus nuo tai per daug, todėl aš tiesiog yra tikrai analinis su sigma taip pat įsitikinkite, kad įėjimas negali būti neigiamas. Taigi, jei m yra neigiamas, kažkas panašaus neigiamas. Kas nutiks? Na, aš ketina gauti inicializuoti į vieną, ir tada aš bus mažesnis arba lygus m? 

Budėjimo. Tai was-- tegul ne, tegul nix šią istoriją. Aš neprašiau, kad klausimą, nes rizika, kad aš užsimindamas nesiruošia atsitikti, nes i visada bus didesnis than-- Gerai, Galiu atšaukti šį klausimą. Gerai. Leiskite sutelkti dėmesį tik į šios dalies čia. Kodėl aš pareiškiu, kai ne kilpą? Pranešimas on line 49 aš paskelbta i viduje kilpos, bet internete 48 aš deklaravo apie išorę. Taip. PUBLIKA: [nesigirdi]. SPEAKER 1: Žinoma. Taigi, pirmiausia ir svarbiausia aš tikrai ne noriu paskelbti ir inicijuoti sumą nulinės vidų kilpa ant kiekvieno pakartojimo, nes tai aiškiai nugalėti tikslas susumavus numerius. Norėčiau nuolat keičiasi vertė grįžti į nulinę padėtį. Ir taip pat, kas dar labiau neaiškus priežastis, dėl tos pačios dizaino sprendimą? Taip. 

PUBLIKA: [nesigirdi]. SPEAKER 1: Būtent. Noriu prisijungti prie jos ribų kilpos per daug apie tai, kas atitinka? Dėl 53. Ir remiantis mūsų nykščio taisykle iš paskaitų prieš porą kintamieji yra scoped, tikrai, kad garbanotas petnešos, apimantys juos. Taigi, jei aš neturiu paskelbti viduje sumą Šių išorinių klamrami, Aš negaliu naudoti pagal 53. Kitaip tariant, jei aš paskelbė suma čia arba net Dėl kilpa, aš negalėjau pasiekti jį 53. Kintamasis būtų veiksmingai dingo. Taigi priežasčių ten pora. Bet dabar grįžkime ir pamatyti, kas atsitiks. Taigi sigma iškviečiamas. Ji priduria, iki 1 pridėjus 2 ar 1 pridėjus 2 plius 3, o tada grąžina reikšmę, parduotuvės jį atsakymo, printf čia Štai kodėl aš matau ekrane. Taigi, tai yra tai, ką mes vadiname kartotinis požiūris, kur iteracija tik tai naudojant kilpą. Dėl kilpa, kad ciklas while, Do Nors kilpa, tiesiog daro kažką naujo ir vėl ir vėl. 

Bet Sigma rūšies tvarkingas funkcija kad galėčiau ją įgyvendinti kitaip. Ką apie tai, kuris tiesiog, kad būtų tipo kietas, leiskite man tikrai atsikratyti iš išsiblaškymas daug nes šią funkciją yra tikrai gana paprasta. Leiskite drožinėti jį tiesiog jos keturių pagrindinių linijų ir atsikratyti visų Savo pastabas ir garbanotieji petnešų. Tai rūšies proto-pučia alternatyvus įgyvendinimas. Gerai, gal ir ne proto-pučia, bet tai tipo seksualesnis, visos teisės, pažvelgti į tai, kad daug trumpai. Su vos keturių eilučių kodo, Aš pirmą kartą turi šią normalumas patikrinti. Jei m yra mažesnis arba lygus nulis, sigma neturi prasmės. Tai tik turėtų būti šiuo atveju teigiamų skaičių, todėl aš tik ketina grįžti prie nulio savavališkai taip, kad mes bent jau kai vadinamasis bazinį scenarijų. 

Bet čia grožis. Šios idėjos visuma, pridedant numeriai nuo 1 iki n, arba M, šiuo atveju, galima padaryti rūšies artimųjų spardytis. Na, kas yra 1 suma m? Na, žinote, ką? Tai tas pats kaip m sumai plius 1 suma m minus 1. Na žinote, ką? Kas sigma M minus 1? Na, jei jūs rūšies sekti tai logiškai, tai tas pats, kaip m minus 1 plius sigma M minus 2. Taigi jūs galite rūšies just-- tai kaip, jei jūs tiesiog bando erzinti draugui ir jie užduoti jums klausimą, Jūs rūšies atsakyti klausimą, galite rūšies išlaikyti artimųjų spardytis. Bet kas svarbiausia yra, kad jei jūs nuolat priėmimo klausimas mažesni ir mažesni ir mažesnis, esate neprašo kas sigma n, tai, kas iš Sigma n, tai, kas sigma n? Jūs esate klausia, kas yra sigma n, kas sigma n atėmus 1, kas sigma n minus 2? Galų gale jūsų klausimas taps, ką? Kas yra sigma vieną ar nuliui, kai labai mažas vertė, ir kuo greičiau, kaip jūs gauti, kad jūsų draugas, esate nesiruošia prašyti tą patį klausimą vėl, jūs tiesiog ketinate pasakyti, oi tai nulis. Mes baigsite žaisti šį rūšiuoti kvailas ciklinio žaidimą. 

Taigi rekursija yra programavimo aktas iš funkcijos pasivadinusi. Ši programa, kai surinkti ir paleisti, yra ketina elgtis lygiai taip pat, bet kas svarbiausia yra, kad viduje iš funkcijos vadinamas sigma, yra kodo, kur linija mes skambina patys, , kuris paprastai turėtų būti blogai. Pavyzdžiui, ką daryti, jei aš pirmą kartą sudarytas šis, todėl įsitikinkite, sigma-- padaryti sigma 1 ./sigma-1. Teigiamas sveikasis skaičius, prašome 50 1275. Taigi, ką funkcija atrodo būti, remiantis vieno bandymo teisinga. Bet kas, jei aš galiu gauti šiek tiek pavojinga ir ištrinti vadinamąjį pagrindą, ir tiesiog pasakyti, gerai, aš tiesiog padaryti tai sudėtingesnis, nei ji yra. Tegul tik apskaičiuoti sigma atsižvelgiant m ir tada pridedant į sigma M minus vienas? Na, kas nutiks čia? Leiskite nutolinti. Leiskite perkompiliuoti programą, išsaugokite jį, perkompiliuoti programą, ir tada pasiruošę ./sigma-1 priartinimo, įvesti teigiamą sveikąjį skaičių prašome, 50. Kaip daugelis iš jūsų yra pasirengę į prisipažinti iki matydamas, kad? 

Gerai. Taigi, tai gali atsitikti dėl iš priežasčių, ir atvirai šią savaitę mes apie suteikti jums daugiau iš jų. Tačiau šiuo atveju, pabandykite samprotauti atgal ką galėjo čia nutiko? Segmentavimas kaltė, mes sakėme, paskutinis laikas, reiškia atminties segmentą. Kažkas blogai atsitiko. Bet kas jį buvo mechaniškai, kad nuėjo kreivai čia, nes mano pašalinimo tos vadinamosios bazinės atveju, kur aš grįžo sunkiai koduojami vertę? Ką manote nutiko? Taip. 

PUBLIKA: [nesigirdi]. SPEAKER 1: Ak. Geras klausimas. Taigi į numerį dydžio kad buvau sudėjus gavo tokia didelė, kad ji viršijo iš atminties dydis. Gera mintis, bet ne iš esmės ketina sukelti avariją. Tai gali sukelti sveikasis perpildyti, kur bitai tiesiog apversti ir tada mes klaida tikrai didelis skaičius kaip neigiamas skaičius, bet kad pats nesukels gedimo. Kadangi pasibaigus pabaigos dieną int dar 32 bitai. Jūs esate nesiruošia netyčia pavogti 33-bitų. Bet gera mintis. Taip. 

PUBLIKA: [nesigirdi]. SPEAKER 1: būdas niekada sustoja, ir iš tikrųjų vadina save vėl ir vėl ir vėl ir vėl ir vėl, ir nė vienas iš šios funkcijos ever baigti, nes jų vienintelis linija kodas ragina save programą vėl ir vėl ir vėl. Ir kas iš tikrųjų vyksta čia ir dabar gali rūšies atkreipia į tai pavaizduotomis piktogramo-. Leiskite pereiti prie vaizdas tik už akimirką. Tai vaizdas, kad ilgainiui sukonkretinti išsamiau apie tai, kas vyksta viduje kompiuterio atmintyje. Ir it turns out, kad Šio paveikslėlio apačioje yra kažkas vadinamas kamino. Tai luitas atmintis, RAM riekė, kad tiesiog naudojamas bet kuriuo metu, funkcija yra vadinama. Bet koks laikas jums, programuotojas, skambinti funkciją, operacinė sistema, kaip "Mac OS", "Windows" arba "Linux", griebtuvai baitų krūva, gal Keletas kilobaitų, o gal keletas megabaitų atminties, rankas juos jums, ir tada leidžia paleisti savo funkciją naudojant kokia kintamieji jums reikia. Ir jei tada skambinti kitam funkcija ir kita funkcija, jūs gaunate kitą atminties gabaliuką ir kitas atminties riekė. 

Ir iš tiesų, jei šių "žaliųjų padėklai iš Annenberg, tą atmintį, Štai kas atsitinka pirmą kartą laikas jums paskambinti funkcija sigma. Tai, kaip uždėti plokštelę, kaip tai apie tai, kas iš pradžių tuščia kamino. Bet tada, jei tas dėklas vadina save, taip sakant, paskambinę kitą atvejį Sigma, tai tarsi klausia operacinę sistemą, ooh, reikia šiek tiek daugiau atminties, duok man tą. Ir tada jis bus kraunamos ant ant viršaus. Bet kas svarbiausias čia yra tai, kad Pirmasis dėklas yra vis dar ten, nes jis rėmėsi antrąjį dėklą. Dabar tuo tarpu, sigma skambinti sigma, kad lyg prašydama daugiau atminties. Paimama kraunamos ant čia. sigma skambinti sigma, tai jau kita dėklas, kad gauna kraunamos čia. Ir jei jūs nuolat tai daryti, galiausiai, tipo map tai vaizdo tos diagramos, tai, kas vyksta atsitikti su dėklų kamino? Ji ketina viršyti sumos, atminties jūsų kompiuteris turi. Ir kuo greičiau šios žaliosios dėklą viršija horizontalią liniją virš kamino ir virš to žodžio krūvą, kurios mes grįžti į ateitį, tai yra blogas dalykas. Akmenų krūva yra skirtingi segmentas atminties, ir, jei leisite juos padėklai krūva ir krūva ant, jūs ketinate viršyti jūsų pačių segmentas atminties, ir programa iš tiesų vyksta į avariją. 

Dabar, kaip panaikinti, šią idėją Rekursija, todėl gali aiškiai sukelti problemų, tačiau tai nebūtinai yra blogas dalykas. Nes mano po visi, how-- o gal tai užtrunka šiek tiek priprasti į --how elegantiškas arba kaip paprasta kad sigma įgyvendinimas buvo. Ir mes neketiname naudoti rekursija visi, kad daug CS50, bet CS51, ir tikrai bet kurios klasės kur manipuliuoti duomenų struktūros kaip medžių, ar šeimos medžių, kurie turi tam tikrą hierarchiją, tai super, super naudingas. Dabar, kaip panaikinti, kad jums kaip trokštantis kompiuterių mokslininkai yra susipažinę su kai kuriais iš "Google" viduje anekdotai, jei jūs einate į "Google" ir jums surasti tai, kas yra apibrėžimas, tarkim, rekursija, įveskite. Aha. Kaip žemę, aš iškedentas iki nedaugelis. Tai buvo, pavyzdžiui, 10 minučių atidėliojimas šį rytą. Jei jūs taip pat "Google" pakreiptai "pranešimas pakreipiant galvą slightly-- ir tada šis vienas yra galbūt Patys žvėriškiausių visi nes kažkas praleido kaip jų dieną įgyvendinant šį keletą metų ago-- ateiti. Oi, wait-- tai klaida. 

Taigi veikia ant vieno Didžiausi pasaulio svetainės šie kvaili mažai Velykų kiaušiniai. Jie tikriausiai vartoja nontrivial skaičius eilučių kodo tik todėl, kad mes galime turėti mažai įdomus dalykų, pavyzdžiui, kad. Bet bent jau dabar jūs gaunate kai kurie iš šių viduje anekdotai. 

Dabar galime pažvelgti į kai kuriuos iš balta yra, mes jau pasakojo vėlai, ir pradėti žievelės atgal kai sluoksniai techniškai taip, kad jūs tikrai suprasti, tai, kas jau vyksta ir jūs galite suprasti, kai grėsmių, kaip Shellshock, kad jau pradėjo tapti nuo kiekvieno priešakyje dėmesio, bent jau žiniasklaidoje. Taigi čia yra labai paprasta funkcija kad grįžta nieko, tuščia. Jo vardas yra apsikeitimo. Tai trunka dviejų kintamųjų ir jis grįžta nieko. Mano A ir B. Taigi greitai demonstravimas. Mes atnešė tai iki. Mes taip pat galėtų imtis šiek tiek pertrauka čia truputi ir turi mažai ką gerti. Jei kas nors ne tai prisijungti man iki čia tik akimirką. Kaip apie jus į kaštoninės marškinėliai? Nagi iki. Tiesiog vienas šiandien. Ačiū, nors. Visos teisės, ir mes turime artėja, kas čia? Koks tavo vardas? 

SPEAKER 4: Laura. 

SPEAKER 1: Laura. Nagi iki. Taigi Laura labai paprasta iššūkis šiandien. Nice to meet yo. Viskas gerai. Taigi, mes turime šiek tiek pieno čia ir mes turime šiek tiek apelsinų sulčių per čia ir kai puodeliai, kad mes pasiskolino iš Annenberg šiandien. 

SPEAKER 4: Pasiskolinti. SPEAKER 1: Ir ketinate eiti į priekį ir duoti jums pusę tai stiklo. Viskas gerai. Ir mes suteiksime jums pusę pieno stiklo. Oh, ir tik todėl, kad jūs galite prisiminti, kas tai buvo, pavyzdžiui, Prisiminiau pareikšti tai aukštyn ir šiandien. Gerai. Jei ne tai, pažiūrėkime, mes galite įdėti juos savo akinius jei norite. Tai bus pasaulis iš Laura akis. Viskas gerai. Taigi jūsų tikslas, atsižvelgiant į du puodeliai skystis čia, pieno ir apelsinų sulčių, yra sukeisti dvi turinį taip, kad apelsinų sultys eina į pieno puodelį ir pieno eina į apelsinų sultys puodelis. 

SPEAKER 4: Ar gausiu kitą puodelį? SPEAKER 1: Aš taip džiaugiuosi, prašėte, nors tai būtų buvę daug geriau filmuota medžiaga jei nebuvo prašoma. Bet taip, mes galime Jums pasiūlyti trečiosios puodelis tai tuščia, žinoma. Viskas gerai. Taigi apsikeitimo turinį ten. Labai gražus. Labai gerai. Jūs darote tai nepaprastai atsargiai. Ir trijų etapų. Viskas gerai. Puikus. Didelis audringi plojimai būtų gerai, Laura. Viskas gerai. Mes turime mažai atsisveikinimo dovaną už jus, bet leiskite man pasinaudoti jų. Labai ačiū. Taigi paprastas pavyzdys, nors, įrodyti, kad, jei jūs norite sukeisti turinį iš dviejų talpyklių, arba tegul pavadinkime juos kintamieji, jums reikia šiek tiek laikino saugojimo į vieną iš turinio etape tiek kad jūs iš tikrųjų galite padaryti swap. Taigi iš tiesų, tai kodo iki čia C yra atstovas būtent tai. Jei apelsinų sultys buvo ir pienas buvo b ir norėjome apsikeitimo du, galite pabandyti kažką kūrybinį pilant viena į kitą, bet tikriausiai nebūtų pabaigą ypač gerai. Ir todėl mes naudojame trečią taurę, skambutį tai tmp, T-M-P pagal susitarimą, ir įdėti turinį OL tuo, kad, tada sukeisti vieną puodelį, tada įdėti OL į originalus puodelis, taip pasiekti, tiksliai taip, kaip Laura padarė, apsikeitimo sandorio. 

Taigi darykime būtent tai. Leiskite man eiti į priekį ir atidaryti iki Pavyzdžiui ŠTAI iš tikrųjų vadinama "ne apsikeitimo ", nes tai nėra kaip tik padaryti, kaip jūs manote. Taigi šioje programoje, pastebėsite, kad Aš naudoju stdio.h, mūsų senas draugas. Turiu prototipas už apsikeitimo sandorio ten, kuris tai jo įgyvendinimas s tikriausiai žemyn toliau, ir pažiūrėkime, ką šis pagrindinis Programa ketina tai padaryti už mane. Aš pirmą kartą paskelbti int x gauna vienas, ir int y gauna du. Taigi manau, tie, kaip leidinyje ir pienas, atitinkamai. Ir tada aš tiesiog printf sakydamas x tai ir y tai, tik tiek galiu vizualiai pamatyti, kas vyksta. Tada aš printf teigdamas kad aš Swapping du, ir tada aš atsispausdinti teigia, kad jie pavertė, ir aš atsispausdinti x ir y dar kartą. Taigi žemyn čia apsikeitimo sandoris ką Laura padarė, ir ką matėme ekranas prieš akimirką. 

Taigi eikime į priekį ir skaudžiai nusivilti. Make no apsikeitimo ir paleisti jokio swap, padidindami produkcijos čia. Įveskite x 1, y 2, Swapping pavertė. x yra dar 1, ir y yra dar 2. Taigi, nors, tiesą sakant, tai atrodo tiksliai norite, nors techniškai, ką Laura padarė, neatrodė, kad dirbti. Taigi, kodėl taip yra? Na, paaiškėja, kad kai mes rašome, kaip ši programa , kuri turi tiek pagrindinė, pabrėžė čia ir tada kita funkcija, kaip apsikeitimo sandorių, pabrėžė čia, o ji ragina, pasaulis atrodo šiek tiek kažką panašaus šie padėklai prieš akimirką. Kai pagrindinis pirmas iškviečiamas, tai tarsi klausia operacinę sistemą už atminties tiek dėl bet vietos kintamieji, pavyzdžiui, x ir y, kad pagrindinis turi, ir jie galų gale teisus ten. Tačiau, jeigu pagrindinis skambučių apsikeitimo ir pagrindinis eina sukeisti du argumentus, A ir B, apelsinų sultys ir pienas, tai nepatinka atiduodami apelsinų sultis ir pieną Laura. Ką kompiuteris daro, tai eina kopijas apelsinų sulčių ir kopijos Laura pieno, kad kas galiausiai viduje šio dėklo yra vertė vieno ir dviejų arba OL ir pieno, tačiau jų kopijos, kad šiuo metu į istoriją, ten yra OL ir pieno kiekvienoje iš šių dėklų. Yra vienas ir du kiekviena iš šių dėklų, ir apsikeitimo funkcija iš tiesų dirba. Tai Swapping juos viduje Antros viršutinį dėklą bet Swapping neturi įtakos. Ir remiantis tik keletas pagrindinis principas, mes kalbėjo apie prieš, ir iš tiesų vos kelios minutės prieš ką gali paaiškinti, kodėl keičiasi a ir b viduje apsikeitimo sandorio neturi įtakos x ir y poveikį, nors Aš išlaikė x ir y apsikeitimo funkcija. Kas pagrindinis žodis čia gali supaprastintai paaiškinti? Manau, aš girdėjau, kad čia? PUBLIKA: Grįžti. SPEAKER 1: Grįžti? Ne sugrįžti. Vykime su vienu kitu. Kas tai? 

PUBLIKA: [nesigirdi]. 

SPEAKER 1: Gerai, kad return-- galėtume padaryti grąžinimo darbą istoriją, bet ten net paprastesnis paaiškinimas. PUBLIKA: Taikymo sritis. SPEAKER 1 Taikymo sritis. Imsiu apimtį. Taigi apimtis, prisiminti, kur Mūsų x ir y deklaruoti. Jie pareiškė, viduje iš pagrindinės teisė čia. a ir b, tuo tarpu, yra efektyviai paskelbė viduje apsikeitimo sandorio, ne visai į garbanotas petnešos, tačiau vis dar bendrojo ploto apsikeitimo sandorio. Ir taip iš tikrųjų, ir b egzistuoja tik per šį dėklą iš Annenberg, tai antra riekė kodą. Taigi mes iš tiesų keičiasi kopiją, tačiau tai tikrai ne visi, kad naudinga. 

Taigi leiskite pažvelgti tai šiek tiek žemesnio lygio. Aš ruošiuosi grįžti į Šaltinis katalogas, ir aš ruošiuosi pirmas priartinti čia, ir tik patvirtinti, kad aš tai didesnis terminalo langą, programa vis dar elgiasi kaip kad. Tarkime dabar, kad tai nėra tyčinis. Aišku aš norėjau apsikeitimo su darbas, todėl ji jaučiasi klaidą. Dabar galėčiau pradėti pridedant daug printf aisiais į mano kodas, spausdinti x per čia, y per čia per čia, b čia. Bet tiesą sakant, tai tikriausiai ką jūs veikėte už poros savaičių dabar, po darbo valandų ir namuose, kai darbo ant psets bando rasti kai kurių klaidų. Bet pamatysite, jeigu jūs dar neturite, kad problema nustatyti trijų supažindina jus į komandą, vadinama GDB, kur GDB, GNU Debugger, turi sau visa krūva funkcijos, kurios gali iš tikrųjų leiskite mums suprasti situacijas kaip tai, bet daugiau įtikinamai, spręsti problemas ir rasti klaidas. Taigi, aš ruošiuosi tai padaryti. Vietoj ./noswap, aš vietoj ketina paleisti GDB ./noswap. Kitaip tariant, aš paleisti mano programa ne Bash, mūsų naujas draugas šiandien. Aš ruošiuosi paleisti mano programa noswap viduje Šio kita programa, vadinama GDB, kuris yra debuggerem, kuris yra programa, kuri sukurta siekiant padėti Jūs žmogus nuolatos surasti ir pašalinti klaidas. Taigi, jei aš paspauskite Paleisti čia, ten žiaurią suma teksto kad jūs tikrai niekada skaityti. Tai iš esmės išsiblaškymas iš eilutę, kuri Aš ruošiuosi nukentėjo Control-L keltis ten viršuje. Tai GDB eilutę. Jei aš noriu paleisti šią programą dabar kaip tai mažai apgauti lapo šiandien Pristatymas rodo, Vykdyti yra pirmasis komandas, kad mes skirtas pristatyti. Ir aš tik ketina įvesti paleisti čia viduje GDB, ir iš tikrųjų tai vyko mano programą. Dabar yra keletas papildomų išėjimai panašaus ekrane, bet tai GDB tiesiog yra analinis ir mums, kas vyksta. Jūs neturite iš tikrųjų turi nerimauti apie tokias detales dabar. Bet kas tikrai cool apie GDB, jei aš tai padaryti again-- Valdymo L išvalo screen-- leiskite man eiti į priekį ir įveskite "pertrauka Pagrindinis" taip, kai aš paspauskite "Enter", kuriame kas vadinama pertrauka taškas noswap.c, linija 16, kur yra GDB išsiaiškino, mano programa iš tikrųjų yra, mano funkcija yra iš tikrųjų. Tai mes ignoruoti dabar bet tai adresas atmintyje specialiai šiai funkcijai. Taigi dabar, kai aš tipo paleisti, pastebėsite, kas yra kietas čia. Mano programa sugenda prie linijos I sakė GDB pristabdyti vykdymą ne. Taigi, aš neturiu dabar pakeisti savo kodą, pridėti keletą printf aisiais, perkompiliuoti jį Rerun jis, keisti, pridėti šiek tiek printf aisiais, išsaugokite jį, perkompiliuoti jį, paleiskite jį. Galiu tiesiog vaikščioti per mano programą žingsnis po žingsnio prie žmogaus greičiu po žingsnio, ne "Intel" viduje rūšies greičiu. 

Taigi dabar pastebėti šią eilutę pasirodo čia, o jei aš einu atgal mano programos gedit, pastebėsite, kad tai yra iš tikrųjų labai pirmoji eilutė kodą. Yra linija 16 ir gedit. Yra linija 16 per GDB, ir net nors šiuo juoda ir balta sąsaja nėra beveik kaip naudotojas draugiškas, tai reiškia, kad linija 16 nebuvo įvykdytas dar, bet ji yra apie būti. Taigi iš tiesų, jei aš tipo spausdinti x, o ne printf, tiesiog spausdinti x, Aš kažkiek netikrą vertę yra nulinė, nes x nebuvo inicijuotas dar. Taigi, aš ruošiuosi rašyti toliau, ar, jei jūs nori būti išgalvotas, tik N šalia. Bet kai aš tipo šalia atvykti, dabar pastebėsite, kad jis pereina į linijos 17. Taigi logiška, kad jei aš įvykdytas 16 linija, ir aš dabar tipo spausdinimo x, ką turėčiau pamatyti? Vienas. 

Ir dabar tai yra tiesa paini. 2 $ yra tik išgalvotas būdas, jei Jums noriu kreiptis į tos vertės vėliau, galite pasakyti "doleris pasirašyti du." Tai lyg nugaros nuoroda. Bet dabar, tiesiog jį ignoruoti. Kas įdomu yra tai, kas remiantis lygybės ženklą dešinėje. Ir dabar, jei aš tipo sekantis vėl ir spausdinti y, turėčiau pamatyti 2. Aš taip pat dabar gali spausdinti x ir vėl atvirai, jei aš gaunu šiek tiek supainioti, kur aš esu, aš galiu įvesti sąrašą sąraše ir tik pamatyti tikrą kontekstą aplink Aš tikiu, vieta tikrai ne. Ir dabar galiu tipo šalia, ir x yra 1. Dabar aš tipo šalia. O, y 2. Ir vėl, tai yra painu, nes GDB produkcijos yra maišomos su savo produkcija. Bet jei reikia nepamiršti, kurias žvelgdamas pirmyn ir atgal savo kodą arba d jį pusę iki pusės galbūt, jūs matyti, kad iš tikrųjų aš tiesiog gerinimo per mano programą. 

Tačiau pastebėti, kas vyksta šalia, pažodžiui. Štai linija 22. Leiskite man eiti per jį, taip pereinant iki 23, ir jei aš spausdinti x dabar dar vienas. Ir jei aš spausdinti y dabar, dar vienas. Taigi, tai nėra naudinga naudotis. Taigi leiskite pakartoti tai. Leiskite grįžti iki viršuje ir tipas paleisti vėl. Ir tai suprantama programa kad manimi yra debugged jau prasidėjo, prasidėjo iš pradžių. Taip, tegul tai padaryti dar kartą. Ir šį kartą tegul daryti toliau, Kitas, šalia, šalia, šalia, bet dabar viskas pasidaro įdomu. Dabar aš noriu dėti į apsikeitimo, todėl aš ne tipo šalia. Aš tipo žingsnį, ir dabar pastebėti šoktelėjo mane noswap.c linija 33. Jei aš einu atgal į gedit, kas 33 linija? Štai pirmasis faktinis linija kodo viduje apsikeitimo sandorio. Kuris yra gražus, nes dabar galiu rūšies baksnoti aplink ir gauti įdomu kaip į tai, kas vyksta iš tikrųjų ten. Leiskite spausdinti tmp. Oho. Kodėl tmp turi keletą kvailai, fiktyvus šiukšlių vertė? PUBLIKA: Tai nebuvo inicializuoti. SPEAKER 1: Tai nebuvo inicializuoti. Ir iš tiesų, kai paleidžiate programą, jums suteikta visa krūva atminties operacinės sistemos, bet jūs nebuvo inicializuoti jokių vertybių, taip kokia bitai jūs matau čia, nors tai šio crazy didelis neigiamas skaičius, tiesiog reiškia, kad jie yra iš liekanos kai praėjusią naudojimas tos RAM, nors aš ne aš reikėjo dar. Taigi, dabar aš ruošiuosi eiti į priekį ir tipas šalia, ir jei aš dabar tipo spausdinimo tmp, ką turėčiau pamatyti? Nepriklausomai buvo vertė, yra pirmasis argumentas, tiesiog kaip x buvo pirmasis dalykas yra priimtas, taip ir x turėtų būti tas pats, taip spausdinti tmp turi atspausdinti man vieną. 

Taigi, ką jūs pamatysite, problemą, trijų yra nekaip apie GDB pamoka, bet suprantu, kad tai yra pradžia iš ne įrankis atrodo, kad iš tikrųjų padėti jums išspręsti problemas, tiek daug efektyviau. Ką mes galiausiai ketinate daryti trečiadienį yra pradėti žievelės atgal keletą sluoksnių ir pašalinti kai kuriuos mokymo ratus. Tai dalykas, vadinamas eilutė, mes naudojamas tam tikrą laiką, mes ketiname lėtai imtis, kad toli iš jūsų ir pradėti kalbėti apie kažkas daugiau esoterically žinomas kaip char *, bet mes ketiname padaryti šį gražus ir iš pradžių atsargiai, nors rodyklės, kaip jie vadinami, galite padaryti kai kuriuos labai blogi dalykai, jei piktnaudžiaujama, žiūrėdamas į mažą Claymation nuo mūsų draugas Nikas Parlante iš Stanfordo Universitetas, kompiuteryje profesorius mokslas, kuris kartu sudėjus šį peržiūros kas turi ateiti šį trečiadienį. 

[VIDEO PLAYBACK] Ei, Binky. Pabuskite. Atėjo laikas rodykle įdomus. 

-Kas Kad? Sužinokite daugiau apie rodykles? Oi, geruolis! [END VIDEO PLAYBACK] SPEAKER 1: Tai jūsų laukia trečiadienį. Pamatysime jums tada. [VIDEO PLAYBACK] -Ir Dabar Deep Thoughts, iki Daven Farnham. 

-Kodėl mes mokytis C? Kodėl gi ne +? 

[Juokas] 

[END VIDEO PLAYBACK]