[Mūzikas atskaņošanai] 

SPEAKER 1: Nu labi, tas ir CS50, un tas ir sākums ceturto nedēļu, un, kā jūs varētu būt dzirdējuši vai lasīt, pasaule ir beidzas. Going visapkārt internetā ir bijis zināšanas un izpratni no bug kādā programmā, programmēšanas valoda sauc Bash. Tas ir lieliski firmas kā Shellshock, vai Bash durvīm, bet raksti, piemēram, tie nav bijis nekas neparasts. Un patiesībā, daudzi no viņiem dot muguras atmiņas par Heartbleed, kas jums var būt ievērojuši nospiest atpakaļ pagājušā gada pavasarī, kas bija līdzīgi diezgan dramatiska. Tagad no tiem no jums šeit Šodien, cik daudzi no jums ir, pat tad, ja jūs nesaprotat, ko tas viss ir par to dzirdēja Shellshock? Visas tiesības, un cik daudzi no jums ir datori, kas ir neaizsargāti? OK, ir jābūt daudz, daudz vairāk rokas tieši tagad, dēļ mēs redzēsim. 

Pieņemsim to apskatīt to, kas ir nu jau par medijos un tad izskaidrot to mazliet šeit mums tehniski. 

SPEAKER 2: Drošības eksperti ir brīdināja, ka nopietns trūkums varētu būt par ietekmētu simtiem miljoniem pasaules interneta lietotājiem. Tātad, kas īsti ir kļūda, kas ir bijis dublēta Shellshock, un ko tas dara? Nu, Shellshock ir arī pazīstams kā Bash bug, programmatūra, ko tā izmanto. Hakeri izmanto vīrusu, lai skenētu neaizsargāti sistēmas darbojas Linux un Unix operētājsistēmas un tad inficē tos. Bash ir komandrindas čaula. Tas ļauj lietotājiem jautājums komandas uzsākt programmas un pazīmes, kas programmatūru ierakstot tekstu. Tas, ko programmētāji ir parasti izmanto, un nedrīkst būt atvērta plašākai pasaulei, gan Shellshock izmaiņas, kas. 

Nu, worringly, daži analītiķi brīdināt tas varētu būt lielāks drauds, jo Shellshock pieļauj pabeigta kontrole inficētas mašīnas, savukārt Heartbleed tikai atļauts hakeri izspiegot datoriem. Tas ir tik nopietni, ir pienācis tika novērtēts ar 10 no 10 par smagumu, ko valsts Neaizsargātības Database. 2/3 visus tīmekļa serveri ir pie risku, tostarp dažas Mac datoriem. Nu, pārliecinieties, ka jūs plāksteris jūsu sistēmas tagad. Ikviens hosting vietnes darbību cietušās operētājsistēmas būtu jārīkojas, cik drīz vien iespējams. Ikviens, kurš var atļauties tas izskatās to uzraudzības un tīmekļa lietojumprogrammu ugunsmūri, lai piesargies par jebkādiem uzbrukumiem. SPEAKER 3: Sliktākais kas varētu notikt, ir ka kāds varētu rakstīt kodu, kas automātiski iet un skenēt internets un ietekmētu visas šīs datoriem. Un, kad viņi dara, ka, labi, Sliktākais viņi varētu darīt ir tikai izdzēst visu, vai slēgtas vietnes leju. Lai mēs varētu redzēt bojājumus No šī viedokļa raugoties, kur mēs būtu ļaunprātīgu cilvēki kas vienkārši nolemj radīt postījumus , apvienojot sistēmas leju vai dzēšot failus, un lietām, piemēram, ka. SPEAKER 2: Daži saka, tas ir viens no visgrūtāk novērtēt bugs gados, un tas var veikt nedēļas vai pat mēneši, lai noteiktu tās maksimālu ietekmi. 

SPEAKER 1: Tātad tas viss ir taisnība, bet smieklīgi ir tas, gandrīz visi no tēlainības tikko redzēju, izņemot varbūt tastatūras, nav nekāda sakara ar bug whatsoever. Serveri un vadi, un tā tālāk, tas ir sava veida tangenciāls saistīti, bet pamatā tas ir faktiski diezgan pazīstami, kas notiek šeit. Patiesībā, ļaujiet man iedziļināties mūsu CS50 ierīces. Ļaujiet man iet uz priekšu un maksimāli termināla logu šeit. Un jums puiši ir bijis, izmantojot to, vai iegulto versija pantu, in gedit lai rakstīt programmas, tipa komandas, un tā tālāk, un tas ir reāli, un ir bijis nedēļas, Bash, B-A-S-H. Tas ir Bourne-atkal apvalks, kas ir tikai iedomātā veids, kā pateikt, Tas ir programma, kas ir mirgo ātri, efektīvi, ka sēž tur gaida par ieguldījumu jums. Un tas ir komandu līnija saskarne, caur kuru jums puiši ir darboties komandas un galu galā, apkopojot un tad darbojas programmas. 

Bet Bash ir arī programmēšanas valoda šādā nozīmē. Jūs zināt, ka ir komandas, piemēram, cd un ls un arī šķindēt un citi, bet jūs varat noteikt savu komandas īstenojot tos Bash. Tagad mēs nebrauksim iedziļināties sīkumos kā lai Bash programmēšanas valodu, bet zinu, ka, piemēram, brīdī, tur nav komandu sauc "sveiki." Tāpēc to var atrast viens no šiem iepakojumiem. Tas nav uzstādīta uz mana datora. Uzdod savu administratoru. Bet, ja es gribu, lai būtu programma sauc par "hello" in Bash vai manu ātru, Es patiesībā var izmantot sintaksi, kas ir gluži tāpat kā C. Tas nav gluži tas pats, bet tas izskatās diezgan līdzīgs funkcija, lai gan trūkst dažas detaļas. Nekas, šķiet, varētu notikt, bet tagad, ja es tipa "hello," Jūs faktiski var uzrakstīt programma, ne C, ne Java, ne citā programmēšanas valoda, bet Bash pati. 

Tagad galvenais šeit ir tas, ka es uzrakstīju nosaukt es gribēju dot šo jauno komandu, un iekavas ir arī simbolisks tas ir funkcija. Kā malā, jūs varat arī darīt jautri lietas, un patiesībā, pat par Mac OS, šī ir programma, ko sauc Terminal. Tas nāk iebūvēts kāds ir dators, kas ir Mac šajā telpā, un jūs varat darīt līdzīgas lietas Mac OS, bet jūs varat iet vēl tālāk, ka. Un tas ir maz tangenciāla, bet tas ir sava veida jautrību. Šorīt es atcerējos, domājot to cauri, par maz spēle es izmantoti, lai atskaņotu ar vienu no CS50 bijušo TFS turklāt jebkuru reizi viņš ietu prom no viņa tastatūra ar savu ekrānu atslēgts, Es varētu izpildīt komandu tāpat this-- "saka sveiki." Un tagad jebkurā laikā viņš atgriezās pie viņa tastatūra kad es noskaidroti ekrānu un viņš varētu apsēsties, mēģināt darīt kādu darbu, uzskaitīt saturu viņa directory-- 

[AUDIO PLAYBACK] 

-hello. Sveiki. 

SPEAKER 1: Tātad, taisnīgumu, tas faktiski nav "sveiki." Parasti tas bija kaut kas vairāk līdzinās that-- [AUDIO PLAYBACK] -Beep. SPEAKER 1: --that I would-- tāpēc viņa dators būtu zvērēt pie viņa jebkurā laikā viņš faktiski apsēdās pie viņa klaviatūras. Un ļoti ātri viņš sapratu, neatstāt savu ekrāns atbloķēt. Bet tas liek domāt, tāda veida par stulbu jautrības, kas jūs var būt ar kaut ko līdzīgu Bash. Bet tas ir nedaudz vairāk nopietns, lai būtu droši, nekā. Un, patiesībā, tas ir viens no Visbīstamākais un ilgtermiņa ilgstošas ​​bugs , kas ir patiešām hit pasaulē globāli. Šī kļūda ir ap aptuveni 20 gadus, un jums tiks kaltas tikai moments ar savu relatīvo vienkāršību. 

Tātad tas ir reprezentatīvs saki, ja jums pieder Mac, burtiski tagad ja jums ir jūsu vāks atvērts, Jūs varat izmēģināt ierakstot, ka programmu, ko sauc Terminal. Terminālis ir zem Pieteikumi Utilities-- vienreiz, Windows lietotājiem nav jāuztraucas par šo konkrēto threat-- bet tie no jums ar Mac var ierakstīt to vērā logu, piemēram, es darīšu šeit, , un, ja jūs tipa ka šajā programmā sauc Terminal, tāpat kā es darīšu tagad, ja redzat vārdu "neaizsargāti," jūsu dators ir neaizsargāti pret ekspluatāciju. 

Tagad, ko tas patiesībā nozīmē? Un tas ir, protams, daži diezgan traks sintakse, bet pieņemsim vismaz izvilkt daži no interesantākajiem aspektiem. Tātad tur ir daži sintakse, kas izskatās maz pazīstami, vismaz no C un programmēšana kopumā. Es redzu dažas iekavas, semikoliem, cirtaini bikšturi, un tādi, bet izrādās, ka šis stulba lieta šeit dzeltenā krāsā būtībā funkcija kas neko nedara. Kols līdzekļi nedarīt neko, un semikols nozīmē pārtraukt darīt neko. Tātad iekšpusē no tiem cirtaini bikšturi, fakts ka man ir vienāda pierakstīties pa kreisi, šis būtībā radot komanda, vai mainīgais, sauc x, un piešķirot to ka dzeltenā mazliet koda tur. Tas varētu būt kaut kas līdzīgs "echo sveiki "vai" saka pīkstiens "vai kaut ko līdzīgs, ka. Bet paziņojums, ja jūsu acīm klīst tālāk pa labi, tur ir vairāk, lai šo līniju nekā tikai beigās šī semikolu. "Atbalss neaizsargāti," un tad tālāk, ka tur ir vēl vairāk. Vēl viens semikols, bash -c :. 

Tik garš stāsts īss, šī līnija kods ir pietiekams pārliecinoši dators, kas ir neaizsargāti darīt kaut ko ka jūs vēlaties to darīt, jo tur ir kļūda Bash kuru kaut Bash bija paredzēts, lai apturētu lasīšana līnijas komandu tiesībām tur pēc dzeltenā teksta, uz 20 plus gadus veco bug, Bash ir faktiski lasījums pēc šī semikolu un diezgan daudz darīt to, ko tā ir teicis. 

Tātad, kāda ir saistība no tā galu galā? Es tikai teicu "echo hello" vai "echo neaizsargāti," bet, kas notiks, ja jūs kaut ko faktiski ļaunprātīgu, tāpat rm -RF *, kas jūs nevarēsiet kādreiz ievadījis pirms, un atklāti jūs, iespējams, vajadzētu ne pārāk ātri, tāpēc, ka jūs varat darīt kaitējumu ar to daudz. Kāpēc? rm nav ko, protams? Noņem. * Nozīmē ko? Viss. Tātad, tas ir tā sauktais wild card, tāpēc tas nozīmē, dzēst visu, kas pašreizējā direktorijā. r notiek nozīmē rekursīvs kas nozīmē, ja tas, ko jūs esat svītrojot ir direktoriju, un iekšā tur ir citi faili un citas direktorijas, rekursīvi nirt tur un izdzēst visu, kas. Un -F ir sliktākais no viņiem visiem. Ikviens zina, ko -f nozīmē šeit? Force. Tātad piespiest līdzekļus, pat ja tā ir slikta ideja, izdarīt bez pamudinot mani tālākai apstiprināšanai. Tātad, jūs zināt, mēs pasmieties , bet godīgi sakot, es, iespējams, ierakstiet šo vairākas reizes dienā, jo realitātes tas ir ātrākais veids, kā dzēst visu ķekars sīkumi. Bet pat es esmu darījis kādu kaitējumu. 

Bet, ja tu būtu, lai triks datoru definēšanas kādu stulbu mainīgais vai funkciju sauc x, bet tad tricking datoru izpildes ārpus robežām, kas funkcija, pēc minētā semikolu, jūs tiešām varētu triks datoru stājas izpildot kaut ko līdzīgu rm -RF vai e-pasta komandu vai Copy komandu. Jebkas burtiski jūs varat darīt ar datoru, vai tas ir izdzēšot failus, radot failus, surogātklikšķus kāds, uzbrukt kādu serveri attālināti, ja jūs varat izteikt to ar komandu, tu var triks datoru darām. 

Tagad to, kas ir piemērs kā jūs varētu darīt? Nu, tur ir daudz datoru par interneta braukšanas Bash. Visi mūs Mac lietotājiem ir starp tiem. Linux serveru daudz ir vieni tos kā labi, un Unix serveriem. Logi atkal izpaužas salīdzinoši off āķa ja jūs uzinstalēju speciāla programmatūra. Tagad daudz serveriem, par Piemēram, palaist web serveri, un patiesībā Linux ir iespējams populārākā operētājsistēma palaist uz datoriem internetā , kas kalpo līdz pat interneta lapas. Tagad, kā mēs redzēsim vēlāk semestrī, kad jūs nosūtītu pieprasījumu no Jūsu browser-- Chrome, Internet Explorer, whatever-- ar attālo serveri, izrādās, ka pat tad, ja Jūs tikko ierakstījāt www.example.com, pārlūkprogramma nosūtot īsziņu kas ir nedaudz vairāk mistisks, kā šis. 

Bet paziņojums mazliet kaut ko dīvainu. Pirmās divas rindas Es nekad neesmu redzējis, bet tie neizskatās Īpaši bīstamas. Bet paziņojums, ko es esmu nozagts par trešajā rindā šeit. Ja slikts puisis bija, lai nosūtītu ziņu piemēram, tas no viņa vai viņas datoru pie neaizsargātas Mac vai a neaizsargāti Linux serveru, smieklīgi ir tas, ka Bash, ka vienkārši nedaudz komandrindas, ir visuresošs, un bieži pieraduši būtībā izpildīt saturs ziņa, ka tā saņem. Un ar šo loģiku, jūs varat triks web serveri, tāpēc, nosūtot kaut ko līdzīgu User-Agent, kas parasti vajadzētu teikt nosaukt jūsu pārlūkprogrammā. User-Agent Chrome, User-Agent Internet Explorer, User-Agent Firefox, šis ir tikai jūsu pārlūkprogramma s veids, kā identificēt sevi. Bet, ja slikts puisis ļoti gudri saka, mm-mm, es esmu nav dodas uz jums kāds ir mans pārlūks ir, Es esmu tā vietā gatavojas nosūtīt jums šo mistisks izskata lieta ar rm -RF * Tajā, jūs varat burtiski triks neaizsargāti web serveri internetā uz izpildes tieši ka tur izdzēšot visus failus. Un, atklāti sakot, tas nav pat sliktākais no tā. Jūs varat darīt jebko. Jūs varētu sākt izplatīts pakalpojumu atteikšanas uzbrukums ja jūs nosūtīja šo ziņu veselus ķekarus tīmekļa serveriem un tad bija viņiem visiem nolaisties, lai Piemēram, uz Harvard.edu serveriem, un jūs varat kārtot no sprādziena heck no tiem ar tīkla satiksmi, kas bija citādi izraisīja šo slikts puisis. 

Tātad, garš stāsts īss, gandrīz ikviens šajā telpā, kam pieder Mac ir neaizsargāti pret šo. Sudraba maliņa ir, ka, ja tu esi darbojas web serveri uz jūsu klēpjdators, un, ja jūs esat faktiski konfigurēts tā, lai ļautu kaut ko līdzīgu SSH tajā, jūs faktiski droši. Tas ir neaizsargāti, bet tur nav viens mēģina nokļūt jūsu klēpjdators, lai jūs varētu veida drošs. Tomēr Apple drīz būt atjaunināt noteikt par to. Linux pasaule jau ir atbrīvota vairāki labojumi, lai Fedora un Ubuntu un citas versijas Linux, un patiešām Ja jūs vadāt atjauninājumu 50 ierīcē, pat, ka arī būs papildināta un koriģēta. Bet tas arī ir ne tiešām bijuši neaizsargāti, jo, ja vien jūs esat tinkered ar ierīci un dara savu klēpjdatoru publiski pieejama internetā, kas nav pēc noklusējuma, jūs esat tiešām ir labi, jo no firewalling un citām metodēm. 

Bet tas ir ekstrēms piemērs bug ka mēs esam dzīvojuši uz burtiski 20 gadiem, un kas zina, ja kāds visu šo laiku ir zināms par to? Un faktiski, tas ir viens no fundamentālās problēmas ka mēs redzēsim vēlāk semestris par drošību, ir tas, ka tāpat kā reālajā pasaulē, labie puiši ir pie nelabvēlīgā situācijā. Lai saglabātu slikti puiši, mums ir pārliecinieties, ka katrs durvis ir aizslēgtas, ka katrs logs ir droša, ka katrs punkts stāšanās mājās ir droša, lai saglabātu slikti puiši out. Bet ko dara slikts puisis ir darīt, lai reāli apdraudēt jūsu mājās un nozagt no jums? Viņš vai viņa vienkārši ir atrast vienu atbloķēt durvis, viena salauzta logu, vai kaut pa šo līniju, un tas ir Tas pats ar datoru drošību. Mēs varam rakstīt miljoniem rindiņas programmēšanas kodu un tērēt simtiem vai tūkstošiem stundu cenšas iegūt to pareizi, bet, ja jūs veicat tikai vienu kļūda pareizību, varat ievietot visu sistēmu un patiešām šajā gadījumā visa internets un pasaules riskam. 

Tātad, ja jūs vēlaties uzzināt vairāk par to, dodieties uz šo URL šeit. Nav nepieciešama rīcība šovakar, ja jūs esat starp tiem ērtāk, ka ir rādīt savu web serveri, tādā gadījumā jums vajadzētu, Patiesībā, atjaunināt savu programmatūru. 

Un tas arī ir nosaukums runas, un tagad papīrs, ka mēs esam saistīti uz Protams Mājas šodien. Tas bija ko puisis nosaukts Ken Thompson, kurš bija pieņemt ļoti slavens balva datorzinātnēs, un viņš sniedza šo runu dažus gadus Pirms, pēc būtības par šo pašu tēmu. Jautā folks jautājums, jums būtu patiešām uzticība, galu galā, programmatūru, jūs esat bijusi? Piemēram, mums visiem ir bijis rakstot programmas, un mēs esam bijuši apkopojot tos ar šķindēt. Un, lai jūsu zināšanas, jūs esat uzrakstījis jebkādas programmas CS50 kur tur ir sētas durvīm par veidu, tur ir veids, kā kas slikts puisis, ja darbojas savu programmu, varētu pārņemt jūsu datorā? Droši vien nav, vai ne? Mario, un mantkārīgs, un kredīts. Tie visi ir diezgan mazas programmas. Jūs ir diezgan slikti, ja jūs faktiski izgatavots jūsu visu datoru neaizsargāti pēc rakstīšanas 10 vai 20 koda rindiņas, vai vismaz neapzinās daži Drošības ietekmi. Tagad es saku, ka facetiously, bet mēs ejam, lai redzētu šodien un šonedēļ tas faktiski ļoti, ļoti viegli būt slikti un padarīt vēl īsās programmas neaizsargātiem. 

Bet tagad, vismaz, saprotam ka jautājums tiek lūgts šeit ir par šķindēt ar kompilatoru. Kāpēc mēs esam bijuši uzticoties šķindēt pēdējo divu vai trīs nedēļu laikā? Kurš ir teikt, ka tas, kurš rakstīja šķindēt nebija "ja" nosacījums, kas tur ka būtībā injicēts dažas nullītes un tiem, uz katrai programmai tas apkopo kas varētu ļaut viņam vai viņai piekļuve datoru, kad tu esi aizmidzis un jūsu klēpjdators vāks ir atvērts un jūsu dators darbojas? Tiesības? Mums ir šāda veida gods sistēmas tiesības Tagad, ja mēs ticam, ka šķindēt ir legit. Jūs uzticaties, ka ierīce ir legit. Jūs uzticaties, ka burtiski katrs programma uz jūsu Mac vai PC ir uzticams. Un kā šo vienkāršo bug liecina, pat ja tā nav ļaunprātīga, tas absolūti nav varētu būt gadījums. 

Lai jūs būtu bail kā elle. Atklāti sakot, tur nav vienkāršs risinājums šai otrai kā sava veida sabiedrības informētības pieaugošo sarežģītību ka mēs esam pamatojoties uz augšu mūsu datorsistēmu, un cik novājināšanos mēs varētu ļoti labi būt. 

Tagad ar to teica, Breakout. Tātad Breakout ir problēma noteikt trīs, un Breakout ir spēle no vakardienas ka jūs varētu atgādināt, bet par mums problēmu noteikts trīs, tas ļauj mums veikt lietas dublēt robs tā, ka tad, kad mēs rakstām programmas, pat termināļa logā, piemēram, tas, mēs faktiski var palaist, galu galā, grafiskās programmas ne atšķirībā no tiem, mums bija piekļuve ar nulles. Tātad šis ir personāla s īstenošana Breakout, kas ir tikai šī ķieģeļu sadalīšana spēle, ka jūs pārvietot savu bradāt atpakaļ un tālāk, un jūs hit bumbu pret tiem, krāsainu ķieģeļu augšu augšas. Tātad šis ir celt mums kārtot atpakaļ, kur mēs varējām būt ļoti ātri ar nulles, un tagad ar C, Īstenojot mūsu pašu grafiskās lietotāju saskarnes. 

Taču vairāk nekā to, ka šis problēma kopa reprezentē pirmo kurā mēs dodam jums ķekars kodu. Un patiesībā, nesu skaidra uzmanību uz to, jo īpaši tiem mazāk apmierināti, tas problēma noteikti, vismaz no pirmā acu uzmetiena, gatavojas justies kā mēs esam veikuši to uz augšu iecirtums. Tāpēc, ka mēs esam dota jums, dažiem no meklēšanas un šķirošanas problēmas PSET, ķekars kodu, mēs rakstīja, un pāris komentāri ka saka "to darīt," kur jums ir aizpildīt tukšās vietas. Tāpēc ne pārāk atbaidošs, bet tā ir pirmā reize mēs nodotu jums kodu, kas jums ir nepieciešams, lai vispirms izlasīt, saprast, un tad pievienot un pabeigt to. 

Un tad ar Breakout, mēs esam gatavojas darīt to pašu, sniedzot jums daži desmiti vairāk līniju kods, kas, atklāti sakot, sniegt jums daudz no regulējuma spēle, bet apstāties īsi īstenot ķieģeļu un bumbu un bradāt, bet mēs ieviest dažas citas funkcijas. Un pat, ka pēc pirmā acu uzmetiena, atkal, it īpaši, ja mazāk apmierināti, varētu šķist īpaši biedējošu un Jūs domājat, ka tur ir tik daudz jaunas funkcijas Jums ir nepieciešams, lai wrap savas domas apkārt, un tā ir taisnība. Bet paturiet prātā, tas ir gluži tāpat kā nulles. Izredzes ir jums nav izmantot visas puzzle gabaliņus nulles. Izredzes ir jums nav vienalga, lai wrap jūsu prāts ap viņiem visiem jo viss, kas bija bija ātrs skatiens lai saprastu, ak, ka tas, ko es varu darīt ar šo mīklu gabalu. Un tiešām, jo ​​problēma noteikti 3 spec, mēs norādīt Jums pie dokumentiem, kas būs jūs iepazīstināt ar dažām jaunām funkcijām, un galu galā programmēšana konstrukcijas lietojat. Nosacījumi, cilpas, mainīgie, un funkcijas būs identisks tas, ko mēs esam redzējuši līdz šim. 

Tik tiešām, ko mēs sniegsim Jums ir kāda parauga kods, kas ļauj jums izveidot logu kas izskatās nav atšķirībā šo, un galu galā pārvērst to kaut kas gluži kā šis. Tātad izmantot CS50, apspriest biroja stundas un vairāk, un būt apmierināts ar to, šajā daudzums kodu, jums ir rakstīt ir faktiski nav tik daudz. Pirmais uzdevums ir tikai aklimatizēties sev kādu kodu, mēs esam rakstīts. 

Visus jautājumus par pset3, Shellshock, vai kā citādi? 

AUDITORIJA: Likās iet cauri ar Breakout ka kods ir gandrīz objektorientētā style, bet es domāju, C biju objektorientētā programmu. SPEAKER 1: lielisks jautājums. Tātad skatoties caur izplatīšana kods, kods mēs rakstījām par pset3, tiem iepazinušies, to Izskatās, ka tas ir maz objektorientētā. Īsā atbilde ir, tā ir. Tas ir tuvināšanu, kā jūs varētu darīt objektorientētā kodu, izmantojot valodas, piemēram, C, bet tas ir tomēr galu galā procesuālo. Nav metodes iekšpusē mainīgos lielumus, kā jūs redzēsiet. Bet tas atgādina, ka. Un mēs redzam, ka funkciju atkal kad mēs nokļūt PHP un JavaScript uz beigām semestra. Bet tagad, domā par to, kā mājienu par to, kas ir nākt. Labs jautājums. Viss labi. Tātad apvienot kārtošanas bija, kā mēs kreisās lietas pēdējo reizi. Un apvienot kārtot bija vēss sajūta, ka tas bija tik daudz ātrāk, vismaz pamatojoties uz virspusējas testu mēs darījām pagājušajā nedēļā, nekā, teiksim, burbuli kārtot, atlase šķirot, ievietošanas kārtošanas. Un kāda bija veikls arī ir tikai cik īsi un tīri Jūs varat izteikt to. Un ko mēs sakām, tas bija augšējo saistošs par braukšanas laiku sapludināšanu šķirot? Yeah? 

AUDITORIJA: n log n? 

SPEAKER 1: n log n, labi. n log n. Un mēs būsim atpakaļ uz to, ka patiesībā nozīmē vai ja kas nāk no, bet tas bija labāk kā kādā darba laika ka mēs redzējām par burbuli atlase un ievietošanas kārtošanas? Tātad n brusas. n kvadrātā ir lielāks nekā tas, un pat tad, ja tas nav gluži skaidrs, zināms, ka log n ir mazāks nekā n, tāpēc, ja jūs n reizes kaut kas mazāks nekā n, tas būs mazāks nekā n brusas. Tas ir mazliet intuīciju tur. Bet mēs maksā cenu par to. Tas bija ātrāks, bet tēma, kas sākās parādīties pagājušajā nedēļā bija šī Tradeoff. Man labāku sniegumu laika ziņā, bet ko nebija man tērēt otras roku, lai panāktu, ka? 

AUDITORIJA: Memory. SPEAKER 1: Say atkal? AUDITORIJA: Memory. SPEAKER 1: atmiņas, vai telpu kopumā. Un tas nebija super skaidrs, ar saviem cilvēkiem, bet atgādināt, ka mūsu brīvprātīgajiem Tika Izsakot un pastiprināšanu atpakaļ, it kā tur ir masīvs šeit, un it kā tur ir otrs masīvs šeit, ka viņi varētu izmantot, jo mēs ļoti nepieciešamo kaut kur apvienot šos ļaudīm. Mēs varētu ne tikai mijmaiņas tos vietā. Tātad apvienot kārtošanas sviras ir vairāk vietas, kas mums nav nepieciešams ar citi algoritmi, bet otrādi ir, ka tas ir daudz ātrāks. Un godīgi sakot, reālajā pasaulē telpā šie days-- RAM, cietais disks space-- ir salīdzinoši lēts, un tā tas ir nebūt nav slikti. 

Tātad, pieņemsim veikt ātri apskatīt, nedaudz vairāk metodiski, ko mēs darījām un kāpēc mums teica, ka tas bija n log n. Tātad, šeit ir astoņi numuri un Astoņi brīvprātīgie mums bija pēdējo reizi. Un pirmā lieta, ka sapludināšana Kārtot teica mums darīt bija ko? AUDITORIJA: Divide divās. SPEAKER 1: Say atkal? AUDITORIJA: Divide divās. SPEAKER 1: Divide divās daļās, pa labi. Tas ir ļoti atgādina tālruņu grāmata, par plaisu un iekarot kopumā. Tātad mēs paskatījās kreisajā pusē. Un tad, kad mēs teicām, kārtot kreiso pusi no elementiem, Ko mēs esam blakus teikt? Kārtot kreiso pusi pa kreisi puse, kas ļāva mums, pēc tam sadalot divās, koncentrēties uz četriem un diviem. 

Kā jūs kārtot sarakstu tagad, dzeltens, izmēru divām, izmantojot sapludināšana Šķirot? Nu sadalīt to pusi, un kārtot kreiso pusi. Un tas bija, kad lietas ieguvuši mazliet stulba īsumā. Kā jūs kārtotu sarakstu, kas ir par lielums viens, piemēram, šo numuru četri šeit? Tas ir sakārtoti. Jūs esat darīts. 

Bet tad kā jūs kārtot sarakstu izmērs viens, kad tas ir numur divi? Nu, tas pats, bet tagad to, kas bija Trešais un galvenais solis Merge Atlasīt? Jums bija apvienot kreisi pusi un labo pusi. Un, kad mēs darījām, ka mēs skatījāmies četros, mēs paskatījās diviem. Mēs nolēmām, visas tiesības, acīmredzot divi ir pirmajā vietā, tāpēc mēs liekam divas savā vietu, kam seko četri. Un tagad jums ir sava veida attīt atpakaļ, un tas ir sava veida īpašība no algoritma, piemēram sapludināšana Kārtot, attīt atmiņā. Kāds bija nākamais rindā ir stāsts? Kas man būtu koncentrēties uz nākamo? Labo pusi kreisi puse, Kurš ir seši un astoņi. 

Tātad, ļaujiet man tikai soli caur šo bez belaboring punktu pārāk daudz. Seši un astoņi, tad seši ir sakārtoti, astoņi ir sakārtots. Apvienot tos kopā, piemēram, ka, un tagad nākamais lielais solis ir, protams, sakārtot pareizo pusi no pats pirmais solis šīs algoritms. Tātad, mēs koncentrējamies uz vienu, trīs, septiņi, pieci. Mēs pēc tam koncentrēties uz kreisajā pusē. Kreisā puse, ka tiesības puse ka, un pēc tam apvienot vienā un trīs. Tad labajā pusē, tad kreisajā pusē no tā, tad tiesības puse no tā. Apvienot to, un tagad ko solis paliek? Apvienot lielo kreiso pusi un liels labajā pusē, tāpēc viens iet uz leju tur, tad divas, tad trīs, pēc tam četri, tad piecu, sešu tam, tad septiņu, astoņu tam. 

Tāpēc tagad kāpēc tas galu galā atklāj, it īpaši, ja n un logaritmi vairāk parasti drīzāk aizbēgt jums, vismaz pēdējos atmiņā? Nu, paziņojums augstumu šī lieta. Mums bija astoņi elementus, un mēs dala to ar divi ar divi, ar divi. Tātad log bāzes divi no astoņiem dod mums trīs. Un ticiet man, ka, ja mazliet miglaini par to. Bet log bāze divi no astoņiem ir trīs, tāpēc mēs esam darījuši trīs slāņu apvienošana. Un, kad mēs apvienojām elementi, cik daudzi elementi tomēr mēs skatāmies uz katru no šīm rindām? Kopumā n, vai ne? Jo apvienot augšējā rindā, pat ja mēs to darīja pa daļām, mēs galu galā pieskārās katru numuru vienu reizi. Un otrajā rindā, lai apvienot šos sarakstus izmēra divu, mums bija pieskarties katru elementu reizi. Un tad šeit tiešām skaidri pēdējā rindā, mums nācās pieskarties viens no tiem elementi vienu reizi, bet tikai vienu reizi, tāpēc šeit slēpjas, tad, mūsu n log n. 

Un tagad tikai, lai padarītu lietas nedaudz vairāk formāls tikai brīdi, ja jums bija tagad analizēt šo pie sava veida augstākā līmenī un mēģināt izlemt, labi, kā jūs varētu iet par paužot darbības laiks šo algoritmu tikai, skatoties uz to, un nav izmantojot samākslotu piemēru? Nu, cik daudz laika jūs teiktu soli, piemēram, tas ir dzeltenā krāsā varētu veikt, ja n <2 atgriešanās? Tas ir liels O, ko? Tāpēc es esmu redzēt vienu, tāpēc vienu soli, varbūt divus soļus, jo tas ir, ja un pēc tam atgriezties, bet tas ir nemainīgs laiks, vai ne? Tātad, mēs minētā O (1), un ka ir kā es ņemšu izteikt to. T, vienkārši darba laika. n ir lielums ievadi, tāpēc T (n), tikai iedomātā veids , sakot vadīšanu laiks dots ievadi lieluma n būs par kārtību pastāvīga laikā, O (1). 

Bet citādi, ko par šo? Kā jūs izteikt darbības laiks šo dzelteno līniju? T, ko? Jūs varat veida apkrāptu šeit un atbildēt uz manu jautājumu cikliski. Tātad, ja darba laiks Kopumā mēs vienkārši teikt, ir T (n). Un tagad jūs esat veida punting šeit un sakot, labi, vienkārši kārtot kreiso pusi, un pēc tam kārtot labo pusi. Kā varētu mēs simboliski pārstāvēt darbības laiks šīs dzelteno līniju? T, ko? Kas izmērs ieejas? n vairāk nekā divi. Kāpēc es tikai saku, ka? Un tad tas ir vēl viens T (n / 2) un pēc tam atkal, ja es apvienot divas sakārtotās pusītes, cik elementi man iet ir pieskarties pavisam? n. Tāpēc es varu izteikt to, tikai, lai būtu sava veida iedomātā, kā darbojas laiku kopumā. T (n) ir tikai darbības laiks T (n / 2), plus T (n / 2), pa kreisi pusi un labo pusi, plus O (n), kas, iespējams, ir n soļi, bet varbūt, ja es esmu, izmantojot divus pirkstus, tas ir divreiz vairāk soļi, bet tas ir lineāra. Tas ir daži no soļiem skaits tas faktors n, lai mēs varētu izteikt to kā šī. Un tas ir, ja tagad mēs punt uz atpakaļ mūsu vidusskolas matemātikas mācību grāmata mēs esam, ka atkārtošanās galu galā nonāks līdzinoties to, n reizes log n, ja jūs faktiski darīt out math vairāk formāli. 

Tā ka ir tikai divas perspektīvas. Viens skaitliski ar iekodēts raksturīgu piemēru izmantojot astoņus numurus, un vairāk Kopumā izskatās, kā mēs saņēmām tur. Bet to, kas ir patiešām interesanti šeit ir, atkal, šis jēdziens riteņbraukšana. Es neesmu, izmantojot cilpas. Es esmu veida definēšanas kaut ziņā pats par sevi, ne tikai ar šo matemātiska funkcija, bet arī attiecībā pret šo pseido kodu. Tas pseido kods ir rekursīvs ka divi tās līnijas būtībā stāstīt to, lai iet izmantot sevi, lai atrisinātu mazāku problēma mazāka izmēra, un tad atkal un atkal un atkal, līdz mēs drāzt to uz leju, lai tā sauktās gadījumu. 

Tātad pieņemsim faktiski izdarīt vairāk pārliecinoši take-prom no tā, kā šādi. Ļaujiet man iet uz gedit un veikt apskatīt dažus no šodienas pirmkodu, īpaši šis piemērs šeit. Sigma 0, kas acīmredzot piebilst skaitļi viens caur n. Tātad, pieņemsim redzēt, kas ir pazīstams un svešs šeit. Vispirms mums ir pāris ietver, tāpēc nekas jauns tur. Prototips. Es esmu mazliet miglaina par tas pēc dažām dienām, bet ko gan mēs sakām prototips funkcija ir? AUDITORIJA: [nedzirdama]. SPEAKER 1: Kas tas tāds? AUDITORIJA: Mēs paziņojam to. SPEAKER 1: Mēs paziņojam to. Tātad jums ir mācību šķindēt, hey, faktiski neīsteno to vēl, bet kaut kur šo failu, iespējams, tiks funkciju sauc ko? Sigma. Un tas ir tikai solījums, ka tas notiek, lai izskatās šādi. Tā gatavojas veikt veselu skaitli kā input-- un es varu būt skaidrāk un teikt int n --and tas ir gatavojas atgriezties int, bet semikolu līdzekļiem, mm, es nopirkšu apkārt īstenot šo nedaudz vēlāk. Atkal, šķindēt ir mēms. Tas ir tikai gatavojas zināt, ko Jums pateikt to no augšas uz leju, tāpēc mums ir nepieciešams, lai vismaz dotu tas mājienu par to, kas ir nākt. 

Tagad aplūkosim galvenais šeit. Pieņemsim ritiniet uz leju šeit un redzētu, kas galvenais dara. Tas nav, ka ilgi par funkciju, un faktiski būvēt šeit ir pazīstams. Es apliecinu mainīgu n, un pēc tam Es apgrūtināt lietotāju atkal un atkal pozitīvai skaitlim izmantojot getInt, un vienīgā izeja no šīs cilpas pēc tam, kad lietotājs ir izpildījis. Vai gan mēs esam izmantojuši, lai apgrūtināt lietotājam šādā veidā. Tagad tas ir interesanti. Es apliecinu int sauc par "atbilde." Es piešķirt tā atgriešanās vērtību par funkciju sauc "sigma". Es nezinu, ko tas dara, tomēr Es atceros, atzīstot to pirms brīža. Un tad es esmu, kas iet vērtība, lietotājs ierakstījāt, n, un tad es ziņot atbildi. Nu pieņemsim ritināt atpakaļ tikai brīdi. Iesim uz priekšu šajā direktorijā, veikt sigma 0, un faktiski palaist šo programmu un redzēt, kas notiek. Tātad, ja man iet uz priekšu un palaist šī programma, ./sigma-0, un es ierakstiet pozitīvs skaitlis, piemēram, diviem, Sigma, kā Grieķijas simbols nozīmē, ir tikai gatavojas saskaitīt visus numurus no nulle par līdz pat diviem. Tātad 0 plus 1 plus 2. Tātad tas būtu cerams man 3. Tas ir viss, tas dara. Un tāpat, ja es palaist vēlreiz un es arī tā numuru trīs, tas ir 3 plus 2, tā ka ir 5, plus 1 vajadzētu dot man 6. Un tad, ja man patiešām traks un sākt rakstīt lielākiem skaitļiem, tam vajadzētu dot man lielākas un lielākas summas. Tātad tas arī viss. 

Tātad, ko tas sigma izskatās? Nu, tas ir diezgan vienkārši. Tas, kā mēs varētu būt jāīsteno tas par pēdējo pāris nedēļu laikā. "Int" būs atgriešanās tips. Sigma ir vārds, un tas aizņem mainīgais m, nevis n. Es mainīt ka ​​līdz top. Tad tas ir tikai veselība pārbaudītu. Mēs redzēsim, kāpēc brīdi. Tagad es apliecinu citu mainīgo, summa, inicializēt to līdz nullei. Tad man ir tas For cilpa atkārtojot, acīmredzot skaidrības labad, no i = 1 gada līdz = M, kas ir kāds lietotājs drukāti, un tad es pieauguma, piemēram, šo summu. Un pēc tam atgriezties summu. 

Tātad pāris jautājumi. Viens, es varu pieprasīt savā komentārā, ka šis novērš risku bezgalīgu cilpu. Kāpēc būtu iet ar negatīvu skaitli izraisīt, iespējams, bezgalīgu cilpu? 

AUDITORIJA: Jūs nekad sasniegt m. 

SPEAKER 1: Nekad sasniegt m. Bet m ir pieņemts, tāpēc pieņemsim apsvērt vienkāršu piemēru. Ja m ir pieņemts ar lietotāju par negatīvu vienu. Neatkarīgi no galvenā. Galvenais pasargā mūs no šo pārāk, tāpēc es esmu tikai ir tiešām anālais ar sigma arī pārliecināties ka ieejas nevar būt negatīvs. Tātad, ja m ir negatīvs, kaut kā negatīvai. Kas notiks? Nu, es gatavojas get inicializēts ar vienu, un tad es būs ir mazāks par vai vienāds ar m? 

Stāvēt. Ka was-- pieņemsim nav, pieņemsim uzmanies šo stāstu. Es neprasīju šo jautājumu, jo risks, ka es esmu atsaucoties uz nav gatavojas notikt, jo man ir vienmēr būs jābūt lielākam than-- OK, Es ievilkt šo jautājumu. OK. Pieņemsim koncentrēties tikai uz šo daļu šeit. Kāpēc es apliecinu, daži ārpus cilpa? Paziņojums on line 49 Esmu deklarēta i iekšpusē cilpas, bet online 48 es esmu deklarēja aptuveni ārpuses. Jā. AUDITORIJA: [nedzirdama]. SPEAKER 1: Protams. Tātad vispirms un galvenokārt es, protams, nav vēlas deklarēt un sāktu summa līdz nulles iekšpusē cilpa katrā atkārtojuma, jo tas nepārprotami sakaut mērķis summējot numurus. Es varētu saglabāt mainās vērtību atpakaļ uz nulli. Un arī, kas ir vēl vairāk mistisks iemesls šī paša dizaina lēmumu? Jā. 

AUDITORIJA: [nedzirdama]. SPEAKER 1: Tieši tā. Es gribu, lai piekļūtu to ārā cilpa pārāk uz kāda līnijas? Gada 53. Un, pamatojoties uz mūsu īkšķa no pāris lekcijas atpakaļ, mainīgie ir scoped, tiešām, lai cirtaini bikšturi, kas aptver tos. Tātad, ja man nav apliecinu summu iekšā Šo ārējo cirtaini bikšturi, Es nevaru to izmantot 53 rindā. Citiem vārdiem sakot, ja es deklarēta summa šeit, vai pat Cilpa, es nevarēju piekļūt to 53. Mainīgais efektīvi pagājis. Tātad pāris iemesli tur. Bet tagad iesim atpakaļ un redzēt, kas notiek. Tā sigma izpaužas sauc. Tā piebilst, līdz 1 plus 2, vai 1 plus 2 plus 3, un pēc tam atgriež vērtību, noglabā atbildi, un printf šeit ir iemesls, kāpēc es esmu redzēt uz ekrāna. Tātad, tas ir tas, ko mēs saucam iteratīvs pieeja, kur atkārtojuma vienkārši nozīmē, izmantojot cilpu. Par cilpa, kamēr cilpa, Do Kaut cilpa, tikai darot kaut ko atkal un atkal un atkal. 

Bet sigma ir sava veida veikls funkciju , ka es varētu īstenot atšķirīgi. Kas par to, kas tikai, lai būtu sava veida atdzist, ļaujiet man tiešām atbrīvoties par daudz uzmanību jo šīs funkcijas patiešām ir diezgan vienkārši. Pieņemsim drāzt to uz leju vienkārši tās četrām galvenajām līnijām un atbrīvoties no visiem komentārus un cirtaini bikšturi. Tas ir sava veida prāta-putu alternatīva īstenošanu. Nu labi, varbūt ne prātā-putu, bet tas ir sava veida sexier, visas tiesības, apskatīt šo tik daudz kodolīgi. Ar tikai četras rindiņas kodu, Man vispirms ir šis veselība pārbaudītu. Ja m ir mazāks par vai vienāds ar nulle, sigma nav jēgas. Tas ir tikai vajadzēja būt šis gadījums pozitīviem skaitļiem, tāpēc es esmu tikai gatavojas atgriezties nulli patvaļīgi tāpēc, ka mums vismaz ir daži tā saukto bāzes gadījums. 

Bet šeit ir skaistums. Šīs idejas veselums, piebilstot skaitļi no 1 līdz n, m un šajā gadījumā var izdarīt veida iet buks. Nu, kas ir summa, no 1 līdz m? Nu, jūs zināt, ko? Tas ir tāds pats, kā no m summu plus summa no 1 līdz m mīnus 1. Nu jūs zināt, ko? Kas ir sigma no m mīnus 1? Nu, ja jūs veida sekot šim loģiski, tas ir tāds pats kā m mīnus 1 plus sigma no m mīnus 2. Tātad jūs varat veida just-- tas ir tāpat kā, ja jūs vienkārši mēģina traucēt draugu un viņi uzdot jums jautājumu, jūs veida atbildēt ar jautājumu, Jūs varat veida glabāt iet buks. Bet to, kas ir galvenais ir tas, ka, ja jūs paturiet padarot jautājums mazākas un mazākas un mazākas, tu esi Neprasot, kas ir sigma n, kas ir sigma of n, kas ir sigma n? Tu jautā, kas ir sigma n, kas ir sigma no n mīnus 1, kas ir sigma n mīnus 2? Galu galā jūsu jautājums gatavojas kļūt par ko? Kas ir sigma vienu vai nulle, daži ir ļoti maza vērtība, un tiklīdz jūs iegūt, ka, jūsu draugs, jums nav gatavojas lūgt pats jautājums atkal, jūs tikai gatavojas teikt, ak tas ir nulle. Mēs pabeidzis spēlējot šāda veida par stulbu ciklisko spēli. 

Tātad rekursijas ir akts programmēšanā par funkciju zvana pati. Šī programma, kad tie ir apkopoti un palaist, ir gatavojas izturēties tieši tāpat, bet to, kas ir galvenais ir tas, ka iekšā no funkciju, ko sauc sigma, ir līnija kods, kas atšķiras ar to mēs esam aicinot sevi, kas parasti ir slikti. Piemēram, kas notiks, ja es pirmo reizi apkopoti šo, lai padarītu sigma-- padarīt sigma 1 ./sigma-1. Pozitīvs skaitlis, lūdzu, 50 1275. Tātad, kāda funkcija, šķiet, būt, pamatojoties uz vienu testu, pareizu. Bet ko tad man nedaudz bīstama un izdzēst tā saukto bāzes lietu, un tikai teikt, arī es esmu tikai padarot šis sarežģītāka, nekā tas ir. Pieņemsim tikai aprēķināt sigma veicot m, un pēc tam pievienojot in sigma no m mīnus viena? Nu, to, kas notiks šeit? Pieņemsim attālinātu. Pieņemsim recompile programmu, saglabājiet to, recompile programmu, un gatavs ./sigma-1 attālināt, ievadiet pozitīvs vesels skaitlis, lūdzu, 50. Cik daudzi no jums ir gatavi lai fess līdz redzēt, ka? 

OK. Tātad tas var notikt vairāki iemesli, un atklāti šonedēļ mēs esam par to, lai dotu jums vairāk no viņiem. Bet šajā gadījumā, mēģiniet spriest atpakaļ kas varētu būt noticis šeit? Segmentāciju vaina, mēs pēdējo reizi teica laiks, attiecas uz segmentu atmiņas. Kaut kas slikts noticis. Bet kas tas bija mehāniski, kas gāja greizi šeit, jo mana izņemšanas šīs tā sauktās bāzes gadījumā, kur es atpakaļ grūti kodēta vērtība? Ko jūs domājat, kas nogāja greizi? Jā. 

AUDITORIJA: [nedzirdama]. SPEAKER 1: Ah. Labs jautājums. Tātad lielumu skaitu ka man bija summējot got tik liels, ka tas pārsniedzis lielums atmiņas vietas. Laba ideja, bet nav būtiski gatavojas izraisīt avāriju. Tas varētu radīt veselu pārplūst, kur biti tikai uzsist pa un tad mēs kļūda tiešām liels numurs kā negatīvu skaitli, bet, kas pats par sevi nevar izraisīt avāriju. Jo beigās diena int joprojām ir 32 biti. Jūs neesat gatavojas nejauši nozagt 33. mazliet. Bet laba doma. Jā. 

AUDITORIJA: [nedzirdama]. SPEAKER 1: metode nekad pārstāj darboties, un tas patiešām prasa sevi atkal un atkal un atkal un atkal un atkal, un neviens no šīs funkcijas ever pabeigt, jo to vienīgais līniju kods aicina themself atkal un atkal un atkal. Un to, kas īsti notiek šeit, un tagad mēs var veida izdarīt to gleznieciski. Ļaujiet man iet vairāk nekā uz attēlu tikai brīdi. Tas ir attēls, kas galu galā konkretizētu sīkāk, par to, kas notiek iekšpusē datora atmiņā. Un izrādās, ka dibens šo attēlu ir kaut kas ko sauc kaudze. Tas ir rieciens atmiņas, rieciens RAM, kas ir tikai izmanto jebkurā laikā funkciju sauc. Jebkurā laikā jūs, programmētājs, zvanu funkciju, operētājsistēmu, piemēram, Mac OS, Windows, vai Linux, grabs ķekars baitu, varbūt daži kilobaiti, varbūt daži megabaiti atmiņas, rokas viņiem jums, un pēc tam ļauj jūs vadāt savu funkciju, izmantojot neatkarīgi mainīgie jums nepieciešams. Un, ja jūs pēc tam zvanīt vēl funkcija un citas funkcijas, jums vēl šķēle atmiņas un vēl šķēle atmiņas. 

Un tiešām, ja šie zaļo paplātes no Annenberg pārstāvēt šo atmiņu, Lūk, kas notiek pirmo reizi reizi, kad zvanu funkciju sigma. Tas ir tāpat kā liekot paplāti kā šis par to, kas sākotnēji tukša kaudze. Bet tad, ja kas paplāte sevi dēvē, tā sakot, zvanot citu instanci no sigma, kas ir piemēram, lūdzot operētājsistēmu, ooh, vajag mazliet vairāk atmiņas, dod man to. Un tad tā izpaužas piled uz augšu. Bet kas ir galvenais šeit ir tas, ka Pirmais paplāte joprojām pastāv, tāpēc, ka viņš atsaucās šo otro tekni. Tagad tikmēr, sigma zvaniet sigma, tas ir tāpat lūdzot vairāk atmiņas. Izpaužas sakrauj uz vairāk nekā šeit. sigma zvanīt sigma, tas ir cits paplāte, kas izpaužas sakrauj šeit. Un, ja jūs paturiet darot, beidzot, sava veida karti šo vizuālo šai diagrammas, kas dodas uz notikt ar kaudze paplātes? Tā gatavojas pārsniegt summu atmiņas jūsu dators ir. Un tiklīdz šo zaļo paplāte pārsniedz horizontālo līniju virs skursteņa un virs šī vārdu kaudze, ko mēs atgriezties nākotnē, , ka ir slikti. Kaudze ir atšķirīgs segments atmiņas, un, ja jūs dariet šos paplātes pāļu un pāļu tālāk, jūs gatavojas pārsniegt savu segments atmiņas, un programma ir patiešām gatavojas crash. 

Tagad, kā malā, šo ideju no recursion, tādēļ, var skaidri radīt problēmas, bet tas nebūt nav slikti. Jo uzskatu, pēc viss, how-- un varbūt tas ņem daži kļūst izmantoti līdz --how elegants vai kā vienkāršs ka īstenošana sigma bija. Un mēs nebrauksim, lai izmantotu rekursijas viss, kas daudz CS50, bet CS51, un tiešām nekādu klase kur jums manipulēt datu struktūras piemēram, koki, vai ģimenes koku, ka ir kāda hierarhija, tas ir super, super noderīga. Tagad, kā malā, tā, ka jums kā topošajiem datorzinātnieku ir pazīstami ar kādu no Google iekšpusē joki, ja jūs doties uz Google un paskatās uz augšu, kas ir definīcija, teiksim, rekursijas, ievadiet. Uh-huh. Kā malā, es velk uz augšu maz. Tas bija, piemēram, 10 minūšu laikā vilcināšanās šorīt. Ja jums ir arī Google "šķībi," paziņojums , paceļot galvu slightly-- un tad tas viens ir iespējams visnežēlīgākajiem no visiem jo kāds pavadīja patīk viņu diena īstenojot šo dažus gadus ago-- come on. Ak, wait-- tas ir bug. 

Tātad darbojas uz vienu no pasaules lielākais mājas lapas šie stulba maz Lieldienu olas. Viņi, iespējams, patērē netriviāls skaits koda rindiņas tikai tāpēc, ka mēs varētu būt maz jautras lietas, piemēram, ka. Bet vismaz tagad jums daži no šiem iekšā jokiem. 

Tagad pieņemsim apskatīt dažas balta slēpjas mēs esam stāsta par vēlu, un sāk lobīties atpakaļ daži slāņi tehniski tā, ka jūs patiešām saprotat kas ir bijis notiek un jūs varat saprast daži no draudiem, tāpat Shellshock, ka tagad sāka kļūt priekšplānā ikvienam s uzmanību, vismaz medijos. Tātad, šeit ir ļoti vienkārša funkcija kas atgriež neko, par spēkā neesošu. Tās nosaukums ir swap. Tas aizņem divas mainīgajiem un tas atgriež neko. Stājas in a un b. Tik ātri demonstrācija. Mēs celta šiem augšu. Mēs varētu arī nedaudz pārtraukums šeit tikai brīdi un ir nedaudz kaut ko dzert. Ja kāds nebūtu prāta savieno me up šeit tikai brīdi. Kā par jums ir sarkanbrūns krekls? Nāciet uz augšu. Tikai vienu šodien. Paldies, though. Visas tiesības, un mums ir nāk uz augšu, kas šeit? Kāds ir tavs vārds? 

SPEAKER 4: Laura. 

SPEAKER 1: Laura. Nāciet uz augšu. Tātad Laura, ļoti vienkāršs uzdevums šodien. Prieks iepazīties yo. Viss labi. Tātad mums ir dažas piena nekā šeit un mums ir dažas apelsīnu sulas pār šeit un dažas tases, ka mēs aizgūts no Annenberg šodien. 

SPEAKER 4: Borrowed. SPEAKER 1: Un gatavojas iet uz priekšu un jums pusglāzi šo. Viss labi. Un mēs jums pusi glāze piena. Ak, un tikai tāpēc, ka jūs varat atcerēties, kas tas bija, piemēram, Atcerējos, lai šo augšu un šodien. Labi. Ja jūs neiebilstat, redzēsim, mēs varat viņus pār savām brillēm ja vēlaties. Tas būs pasaulē no Lauras acīm. Viss labi. Tātad jūsu mērķis, ņemot vērā divas tases šķidrums šeit, piens un apelsīnu sulu, ir apmainīt divus saturu tā, ka apelsīnu sula tērēta piena kauss un piena tērēta apelsīnu sulas glāze. 

SPEAKER 4: Vai es varu saņemt vēl vienu tasi? SPEAKER 1: Es esmu tik priecīgs jums jautāja, lai gan tas būtu bijis daudz labāk kadrus ja jūs nebūtu lūgusi. Bet jā, mēs varam piedāvāt jums trešā kauss, kas ir tukša, protams. Viss labi. Tātad swap saturu tur. Ļoti jauki. Ļoti labs. Jūs darāt to ļoti uzmanīgi. Un soli trīs. Viss labi. Excellent. Liels kārta aplausi būtu labi Lauru. Viss labi. Mums ir maz atvadīšanās dāvanu jums, bet ļaujiet man izmantot šos. Thank you so much. Tik vienkāršs piemērs, lai gan, , lai pierādītu, ka, ja jūs vēlas apmainīt saturu divu konteineru vai sauksim tos mainīgos, jums ir nepieciešams zināms pagaidu uzglabāšanu uz kādu no satura iestudē tik ka jūs faktiski var darīt swap. Tik tiešām, tas pirmkodu up šeit C tiek uzrādīts tieši tā. Ja apelsīnu sula bija un piens bija b, un mēs vēlējāmies, lai mijmaiņas divas, jūs varētu mēģināt kaut ko radošu , uzlejot viens uz otra, bet tas, iespējams, nebūtu galu īpaši labi. Un tāpēc mēs izmantojam trešo kauss, zvanu tā tmp, T-M-P pēc vienošanās, un nodot saturu OJ jo, tad swap vienu tasi, tad ielieciet OV stājas oriģināls kauss, tādējādi sasniegšanā, tieši tā, kā Laura darīja, mijmaiņas. 

Tāpēc pieņemsim darīt tieši to. Ļaujiet man iet uz priekšu un atvērt up piemēru, kas ir faktiski sauc par "nē swap ", jo tas nav kā vienkārši izdarīt, kā jūs varētu domāt. Tātad šajā programmā, ievērosiet, ka Es esmu, izmantojot stdio.h, mūsu vecais draugs. Man ir prototipu par mijmaiņas tur augšā, kas nozīmē, ka tā īstenošana ir iespējams zemāk, un redzēsim, ko tas galvenais Programma gatavojas darīt man. Es pirmo reizi apliecinu int x izpaužas viens, un int y izpaužas divi. Tāpēc domāju, ka no tiem, kā OV un pienu, attiecīgi. Un tad es vienkārši ir printf sakot x tas ir un y ir tas, tikai tāpēc es varu vizuāli redzēt, kas notiek. Tad man ir printf apgalvojot , ka es esmu pārnešana divas, un tad es izdrukāt apgalvo, ka viņi samainīti, un es izdrukāt x un y vēlreiz. Tātad, noteikti šeit mijmaiņa tieši to, ko Laura darīja, un tieši to, ko mēs redzējām ekrāns pirms brīža. 

Tāpēc iesim uz priekšu un būt ļoti vīlušies. Marka nav swap, un palaist bez swap, uzklikšķinot uz produkciju šeit. Ievadiet x ir 1, y 2, pārnešana nomainīju. x joprojām ir 1, un Y ir vēl 2. Tātad, pat ja, godīgi sakot, tas izskatās tieši tāpat, lai gan vairāk tehniski, ko Laura darīja, nešķita strādāt. Tātad, kāpēc ir tā, ka? Nu, izrādās, ka tad, kad mēs uzrakstīt programmu, kā šis , kas ir gan galvenais, uzsvēra šeit, un tad vēl funkcijas, piemēram, swap, uzsvēra šeit, kas tā aicina, pasaule izskatās nedaudz kaut kas līdzīgs šie paplātes brīdi atpakaļ. Kad galvenais pirmkārt izpaužas sauc, tas ir, piemēram, lūdzot operētājsistēmu mazliet atmiņas par jebkuru vietējo mainīgie, piemēram, x un y, ka galvenais ir, un viņi galu galā turpat. Bet, ja galvenie zvani swap, un galvenais iet apmainīt divus argumentus, A un B, apelsīnu sulu un pienu, tas nepatīk nododot apelsīnu sulu un pienu līdz Laura. Kas dators dara, ir tā, iet kopijas apelsīnu sulas un kopijas pienu Laura, tāpēc, ka kas ir galu galā iekšā šīs paplātes ir vērtība viens un divi vai OV un piena, bet kopijas, tā, ka šajā brīdī stāsts, tur ir OV un pienu katrā no šīm paplātes. Tur ir viens un divi katrā no šiem paplātes, un mijmaiņas funkcija patiešām strādā. Tas pārnešana tās iekšpusē Otrās augšējais paplātes, bet pārnešana neietekmē. Un, pamatojoties uz tikai daži pamatprincips mēs esam runāja par pirms, un patiešām tikai pirms dažām minūtēm, kas varētu izskaidrot, kāpēc mainās a un b iekšpusē noņemamo nav nekādas ietekmes uz x un y, kaut gan Es pagājis X un Y, lai mijmaiņas funkciju. Kas ir atslēgas vārds šeit, ka varētu vienkāršoti izskaidrot? Es domāju, ka es dzirdēju to šeit? AUDITORIJA: Return. SPEAKER 1: Return? Neatgriežas. Iesim ar vienu citu. Kas tas ir? 

AUDITORIJA: [nedzirdama]. 

SPEAKER 1: Labi, tāpēc return-- mēs varētu padarīt atgriešanās darbu stāsts, bet tur pat vienkāršāka izskaidrojums. AUDITORIJA: joma. SPEAKER 1: joma. Es ņemšu jomu. Tā joma, atcerēties, kur Mūsu x un y deklarētas. Viņi paziņoja, iekšpusē Galveno labi šeit. a un b, tikmēr, ir efektīvi deklarēta iekšpusē mijmaiņas, nav gluži cirtaini bikšturi, bet joprojām vispārējā jomā mijmaiņas. Un tik tiešām, un b pastāvēt tikai šajā paplātes no Annenberg šis otrais rieciens kodu. Tātad, mēs esam patiešām mainās kopiju, bet tas nav īsti viss, kas noderīga. 

Tātad, pieņemsim to apskatīt Tas nedaudz zemākā līmenī. Es iešu atpakaļ Source Directory, un es esmu gatavojas vispirms tuvinātu šeit, un tikai , lai apstiprinātu, ka es esmu šajā lielāks termināla logu, Programma joprojām uzvedas tāpat. Pieņemsim tagad, ka šis nav apzināta. Skaidri es gribēju swap uz darbs, tāpēc tas jūtas kā bug. Tagad es varētu sākt pievienot no printf gados uz manu kodu daudz, izdrukāšana x vairāk nekā šeit, y vairāk šeit, nekā šeit, b nekā šeit. Bet atklāti sakot, tas ir iespējams, ko jums ir darīt uz pāris nedēļām tagad, darba laikā un mājās, strādājot par psets cenšas atrast dažas kļūdas. Bet jūs redzēsiet, ja jums vēl nav, ka problēma noteikti trīs iepazīstina jūs ar komandu sauc GDB, kur GDB, GNU atkļūdotājs ir pati visu ķekars iezīmes, kas faktiski var ļaujiet mums saprast situācijas , piemēram, tas, bet vairāk pārliecinoši, risināt problēmas un atrast kļūdas. Tāpēc es esmu gatavojas darīt. Tā vietā, lai ./noswap, es esmu tā vietā gatavojas palaist GDB ./noswap. Citiem vārdiem sakot, es esmu gatavojas palaist manu programma nav Bash, mūsu jaunais draugs šodien. Es esmu gatavojas palaist manu Programma noswap iekšā Šīs citu programmu, ko sauc GDB, kas ir atkļūdotājs, kas ir programma, kas ir izstrādāta, lai palīdzētu jūs cilvēkus atrast un noņemt kļūdas. Tātad, ja es hit Run šeit, tur ir zvērīgās teksta apjoms kas jums patiešām nekad nav lasīt. Tas ir būtībā izklaidēšanās no uzvednes, kas Es esmu gatavojas hit Control-L piecelties augšpusē tur. Tas ir GDB ātri. Ja es gribu, lai palaistu šo programmu tagad, kā šo maz apkrāptu lapas par šodienas slide liecina, Run ir pirmais komandas, kas mums domāts, lai ieviestu. Un es esmu tikai gatavojas rakstīt palaist šeit iekšpusē GDB, un tas patiešām bija mana programma. Tagad tur ir dažas papildu produkciju kā šis ekrāns, bet tas ir GDB vienkārši ir anālais un stāsta mums to, kas notiek. Jums nav īsti jāuztraucas par šīm detaļām tieši tagad. Bet to, kas ir patiešām atdzist par GDB, ja es to izdarītu again-- Control-L notīra screen-- ļaujiet man iet priekšu un tips "break galvenais," tādējādi, kad es hit Enter, nosakot, kas ir sauc lūzuma punkts pie noswap.c, line 16, kas ir, ja GDB sapratu, mana programma faktiski ir, mana funkcija patiesībā ir. Tas mēs ignorēt tagad bet tas ir adrese atmiņā īpaši šīs funkcijas. Tāpēc tagad, kad es tipa palaist, paziņojums, kas ir cool šeit. Mana programma pārtraukumiem pie līnijas I teicis GDB lai apturētu izpildi at. Tāpēc man nav tagad mainīt savu kodu, pievienot dažas printf s, recompile to, atkārto tas, mainīt, pievienot dažas printf s, saglabājiet to, recompile to, palaist to. Es varu vienkārši pastaigāties pa manu programmu soli pa solim pa solim pie cilvēka ātrumu, nevis Intel iekšpusē veida ātrumu. 

Tātad tagad paziņojums šo līniju parādās šeit, un, ja es dodos atpakaļ uz manu programmu gedit, ievēroju, ka tas ir faktiski ļoti pirmajā rindā kodu. Tur ir 16 līnija gedit. Tur ir 16 līnijas ietvaros GDB, un pat lai gan šī melnā un baltā interfeiss nav gandrīz kā lietotājam draudzīgi, tas nozīmē ka līnija 16 nav ticis izpildīts vēl, bet tas ir par to, lai būtu. Tik tiešām, ja es tipa print x, ne printf, tikai drukāt x, Man dabūt viltus vērtību tur nulle, jo x vēl nav inicializēts. Tāpēc es esmu gatavojas rakstīt nākamo, vai arī, ja jums vēlas būt iedomātā, tikai n uz nākamo. Bet, kad es tipa nākamais ieiet, tagad pamanāt, ka tas pārceļas uz līnijas 17. Tātad loģiski, ja es esmu izpildīts 16 līnijas, un es tagad tipa drukas x, ko man vajadzētu redzēt? One. 

Un tagad tas ir, protams, mulsinoši. 2 $ ir tikai iedomātā veids, ja jums vēlas atsaukties uz šo vērtību vēlāk, Jūs varat teikt, "dolāra paraksta divi." Tas ir tāpat kā atpakaļ atsauces. Bet tagad, vienkārši ignorēt to. Kas ir interesanti ir tas, kas ir labajā pusē vienādības zīmi. Un tagad, ja es tipa nākamais atkal un drukas y, man vajadzētu redzēt 2. Es varu tagad arī izdrukāt x atkal, un godīgi sakot, ja es saņemu nedaudz apmulsis par to, kur es esmu, es varu ierakstīt sarakstu sarakstu un tikai redzēt kādu kontekstu ap Es punkts esmu faktiski ir. Un tagad es varu ierakstīt nākamais, un tur x ir 1. Tagad es tipa nākamo. Ak, y ir 2. Un atkal, tas ir mulsinoši, jo GDB produkcijas tiek sajaukti ar savu produkciju. Bet, ja jūs paturiet prātā, ko glancing un atpakaļ uz savu kodu vai ar ko to ārā pusē blakus varbūt, jūs redzēt, ka tiešām es esmu tikai pastiprināšanu caur manu programmu. 

Bet paziņojums, kas notiek tālāk, burtiski. Lūk line 22. Ļaujiet man iet pār to, tādējādi pārejot 23, un, ja es izdrukāt x tagad, joprojām ir viena. Un, ja es izdrukāt y tagad, joprojām ir viena. Tātad tas nav interesants. Tātad pieņemsim pārtaisīt to. Ļaujiet man iet atpakaļ uz augšu top un tips palaist vēlreiz. Un tas ir saprotams programmu , kas ir tiek debugged jau ir sākusies, sākās no sākuma. Jā, pieņemsim darīt atkal. Un šoreiz pieņemsim darīt tālāk, nākamais, nākamais, nākamais, nākamais, bet tagad lietas iegūt interesantu. Tagad es gribu, lai soli swap, tāpēc man nav rakstīt nākamo. Es tipa soli, un tagad pamanīt ir pieaudzis man noswap.c līnija 33. Ja es dodos atpakaļ uz gedit, kas ir 33 līnijas? Tas ir pirmais faktiskais līnija koda iekšpusē swap. Kas ir jauki, jo tagad es varu veida kule apkārt un saņemt ziņkārīgs par to, kas notiek patiesi tur. Ļaujiet man drukāt tmp. Paga. Kāpēc TMP ir daži traks, viltus atkritumu vērtība? AUDITORIJA: Tas nav inicializēts. SPEAKER 1: Tas nav inicializēts. Un tiešām, palaižot programmu, jūs esat dota visu ķekars atmiņas operētājsistēma, bet jūs nav inicializēts nekādas vērtības, lai kāds bits tu esi redzēt šeit, pat ja tas ir šo crazy liels negatīvs numurs, tikai nozīmē, ka tie ir paliekas no daži iepriekšējā izmantošana šajā RAM, lai gan man nav pats nepieciešams to vēl. Tāpēc tagad es esmu gatavojas iet uz priekšu un tips nākamais, un, ja es tagad tipa drukas tmp, ko man vajadzētu redzēt? Neatkarīgi vērtība bija ir pirmais arguments, vienkārši tāpat x bija pirmais lieta tiek pieņemts, tik un x ir jābūt vienādam, lai drukātu tmp jāizdrukā man vienu. 

Tātad, ko jūs redzēsiet problēmu komplektā trīs ir apmācība par veidu par GDB, bet saprast, ka tas ir sākums no apskatīt rīks, kas būs faktiski palīdzēs jums atrisināt problēmas tik daudz efektīvāk. Ko mēs esam galu galā darīsim trešdien ir sāk lobīties atpakaļ dažus slāņus un noņemt dažus mācību riteņiem. Ka lieta, ko sauc virkne, kas mēs esam izmanto kādu laiku, mēs ejam lēni pieņemt, ka prom no jums un sākt runāt par kaut ko vairāk esoterically pazīstams kā char *, bet mēs esam gatavojas darīt jauka un Vispirms uzmanīgi, lai gan norādes, kā viņi sauc, var izdarīt dažus ļoti sliktas lietas, ja ļaunprātīgi, , apskatot nedaudz Claymation no mūsu draugs Nick Parlante no Stenfordas Universitātes profesors datorā zinātne, kas salikti kopā šo priekšskatījumu par to, kas ir nākt šo trešdien. 

[Video atskaņošana] Hei, Binky. Mosties. Ir pienācis laiks, lai šautriņu jautri. 

-Ko Tas tāds? Uzziniet par norādes? Ak, našķis! [END VIDEO PLAYBACK] SPEAKER 1: Tas gaida tevi trešdien. Redzēsim jums tad. [Video atskaņošana] -Un Tagad, Deep Domas, ko Daven Farnham. 

-Kāpēc mēs mācīties C? Kāpēc ne +? 

[Smiekli] 

[END VIDEO PLAYBACK]