>> [MUZIKO Ludante]
>> SPEAKER 1: Bone, tiu estas CS50, kaj ĉi tiu estas la komenco de la semajno kvar,
kaj kiel vi auxdis aux legi, la mondo estis fini.
Irante tra la tuta interreto estis scio kaj konscio
de cimo en la programo, oni programlingvo nomas Bash.
Ĉi tio estis mirinde branded kiel Shellshock aux Bash pordo,
sed artikoloj kiel tiuj ne estis malofta.
Kaj fakte, multaj el ili alkonduku reen memorojn de Heartbleed,
kiun eble vi rimarkis en la premi reen pasinta printempo, kiuj
Estis simile sufiĉe drama.
Nun el la de vi ĉi tie hodiaŭ, kiom vi havas,
eĉ se vi ne komprenas, kion ĝi estas ĉiuj proksimume, auxdis Shellshock?
Bone, kaj kiel multaj el vi havi komputiloj kiuj estas vundeblaj?
OK, tie devus esti for, for pli manoj ĝis nun, pro kialoj ni vidos.
>> Ni rigardu kio estas estis okazanta en la amaskomunikiloj
kaj tiam klarigos iom tie ni teknike.
>> SPEAKER 2: Sekureco spertuloj havas avertis ke grava difekto povis
proksimume tuŝi centoj da milionojn de la mondo retejo uzantoj.
Do kio precize estas la bug kiu jam nomita Shellshock, kaj kion ĝi faras?
Nu, Shellshock estas konata ankaŭ kiel la Bash cimon, la softvaro ĝi eksplodas.
Hackers uzu la viruso skani vundebla sistemoj kurante Linukso kaj Unikso
mastrumaj sistemoj kaj tiam infekti ilin.
Bash estas komandlinio konko.
Tiu ebligas al la uzantoj temo ordonas ĵeti programoj kaj funkcioj ene programaro
tajpante en teksto.
Ĝi estas tipe uzita por programistoj, kaj ne devus esti malfermita al la ekstera mondo,
kvankam Shellshock ŝanĝas tion.
>> Nu, worringly, iuj analizistoj averti eblis pli granda minaco,
ĉar Shellshock permesas kompletan kontrolo de infektita maŝino,
dum Heartbleed nur permesita hackers spioni komputiloj.
Ĝi estas tiel grava, ĝi estas estis rankumita 10 el 10
por severidad de la Nacia Vundebleco Database.
2/3 de ĉiuj retserviloj estas je riskon, inkludante iuj komputiloj Mac.
Nu, certigu vin fliki vian sistemoj nun.
Ĉiu retprovizanton retejo kurado la tuŝitaj mastrumaj sistemoj
prenu agon kiel eble plej baldaŭ.
Ĉiu kiu povas permesi devus serĉi iliaj monitoreo kaj apliko retejo
firewalls al elsercxu por ajna atakoj.
SPEAKER 3: Worst afero ke povus okazi estas
ke iu skribus kodon estus aŭtomate iri skani
interreto kaj tuŝus ĉiuj el tiuj komputiloj.
Kaj unufoje ili faru tion, nu, la plej malbona afero ili povis fari
Estas simple forviŝi ĉion, aŭ fermitaj lokoj suben.
Do ni povis vidi damaĝon de tiu vidpunkto,
kie ni havas malican homoj kiu ĵus decidas kaŭzi detruojn
disvastigante sistemoj malsupren aŭ viŝante dosierojn, kaj aĵoj tiel.
SPEAKER 2: Kelkaj diras estas de la plej malfacila de mezuri
bugs en jaroj, kaj ĝi povas preni semajnojn aŭ eĉ
monatoj por determini lian fina efiko.
>> SPEAKER 1: Do ĉiuj kiuj estas veraj, sed la amuza afero estas, preskaŭ ĉiuj
el la pentrajxoj vi ĵus vidis, krom eble la klavaro,
havas nenion komunan kun la cimon ajn.
Serviloj kaj dratoj ks, ĝi estas ia tangencialmente rilatigitaj,
sed la kerno estas vere bela familiara kio okazas tie.
Fakte, mi iros en nia CS50 aparaton.
Lasu min kaj maksimumigi la terminala fenestro tie.
Kaj vi uloj estis uzanta ĉi, aŭ enigita versio gxiajn
en gedit por verki programojn, tajpi komandojn, ks,
kaj cxi tiu estas vere, kaj havas estis por semajnojn, Bash, B-Al-S-H.
Tiu estas la Bourne-denove shell, kio estas nur fantazio maniero diri,
tiu estas programo kiu havas palpebrumante prompto, efektive,
kiu sidas tie atendante por enigo por vi.
Kaj ĝi estas la ordono linio interfacon tra kio
vi uloj estis kurante ordonojn kaj finfine kompilante kaj tiam kurante
programoj.
>> Sed Bash estas ankaŭ programado lingvo en la sekvaj senco.
Vi scias, ke tie estas komandojn kiel cd kaj ls kaj ankaŭ tin kaj aliaj,
sed vi povas difini vian propran komandoj implementando ilin en Bash.
Nun ni ne tuj iru en granda detalo
kiel al bash la programlingvo, sed scias, ekzemple, ke en la momento,
ne estas komando nomis "saluton."
Do ĝi povas esti trovita en unu el tiuj pakoj.
Ĝi ne estas instalita en mia komputilo.
Sciigu administranton.
Sed se mi volas tie esti programo nomata "saluton" en Bash aŭ mia prompto,
Mi povas reale uzi sintakson tio tute kiel C. Ĝi estas ne tute la sama,
sed ĝi aspektas bela simila al funkcio, kvankam mankas kelkaj detaloj.
Nenio ŝajnas okazi, sed nun se mi tajpas "saluton"
Vi povas fakte skribi programo, ne en C, ne en Java,
ne en alia programado lingvo, sed en Bash mem.
>> Nun la ŝlosilo tie estas ke mi skribis la nomumi mi volis doni ĉi nova komando,
kaj la krampoj estas ankaŭ simbolaj de tiu estante funkcio.
Kiel flanken, vi ankaŭ povas fari amuzan tion, kaj fakte, ecx en Mac OS,
tio estas programo nomata Terminal.
Ĝi venas konstruita en nenies komputilo kiu havas Mac en tiu ĉambro,
kaj vi povas fari similajn aĵojn en Mac VIN, sed vi povas iri pli tie de tio.
Kaj tio estas iom tuŝa, sed estas speco de amuzo.
Mi rememoris hodiaŭ matene, Kiam pensante ĉi tra,
de malgranda ludo Mi kutimis ludi kun unu el CS50 eksa TFS
per ajna momento li iros for de sia klavaro kun lia ekrano malŝlosis,
Mi devus ekzekuti comandos kiel this-- "diri saluton."
Kaj nun iu tempo li revenis al sia klavaro post mi liberigis la ekrano
kaj li sidigxos, provu fari iun laboron,
listigi la enhavon de sia directory--
>> [AUDIO Playback]
>> -Hello.
Saluton.
>> SPEAKER 1: Do, juste ĝi ne estis fakte "saluton."
Ĝi estis kutime io pli parenca al that--
[AUDIO Playback]
-Beep.
SPEAKER 1: --kiu mi would-- tial lia komputilo farus
ĵuri lin ajna momento li reale sidiĝis ĉe lia klavaro.
Kaj tre rapide li eltrovis ne lasi sian ekranon malŝlosita.
Sed tio sugestas la varo stulta amuza ke vi
povas havi kun iu kiel Bash.
Sed estas iom pli serioza, certe, pli ol tio.
Kaj fakte, ĉi tiu estas unu el la plej danĝera kaj longe daŭra cimoj
kiu vere batis la mondo tutmonde.
Ĉi cimon estis ĉirkaŭe por kelkaj 20 jaroj,
kaj vi estos batita en nur momento de lia relativa simpleco.
>> Do tiu estas reprezentanto ordonas ke se vi
posedi Mac, laŭvorte nun kiam vi havas vian kovrilon malfermita,
Vi povas provi tajpado en tiun programo nomita stacio.
Terminal estas sub Aplikoj Utilities--
por fojo, Windows uzantoj ne devas maltrankviligi tiu aparta threat--
sed tiuj de vi kun Macs povas tajpi jeonon al fenestro kiel mi faras ĉi tie,
kaj se vi tajpas ke en tiu programo
nomita stacio, kiel mi nun faras, se vi vidos la vorton "vundebla"
via komputilo vundeblaj al ekspluato.
>> Nun kion signifas ke vere signifas?
Kaj tio estas rekoni kelkaj belaj freneza sintakso,
sed ni almenaŭ elingigos kelkaj el la interesaj aspektoj.
Do tie estas kelkaj sintaksaj kiuj aspektas iom familiara, almenaŭ de C
kaj programado pli ĝenerale.
Mi vidas iun krampoj, punktokomojn, frizita krampoj, kaj tia,
sed rezultu ke tiu malsaĝa afero tie en flava
Estas esence funkcio kiu faras nenion.
La dupunkto signifas nenion fari, kaj la punktokomo signifas ĉesi fari nenion.
Do ene de tiuj frizita krampoj, la fakto
ke mi havas egalan subskribi al la maldekstra, tiu
Estas esence kreas ordono, aŭ variablo,
nomata x kaj atribuante ĝin ke flava iom da kodo tie.
Tio povus esti io kiel "eĥo saluton "aŭ" diri pepi "aŭ io
parenca al tio.
Sed rimarki se viaj okuloj vagadi pli dekstren,
ekzistas pli al ĉi tiu linio da nur la fino de tiu punktokomo.
"Eĥo vundebla," kaj poste trans ke ekzistas eĉ pli.
Alia punktokomo, bash -c :.
>> Do longan rakonton, tiu linio de kodo
sufiĉa por konvinka komputila tio
vundeblaj al faranta ion ke vi volas fari,
ĉar tie estas cimo en Bash per kvankam Bash estis supozita por haltigi
legi liniojn de komando dekstra tie post la flavan tekston
por 20-plus jara cimon, Bash efektive estis legado
preter tiu punktokomo kaj bela multe faris kion oni diris.
>> Do kio estas la implikaĵo el kiuj fine?
Mi ĵus diris "eĥo saluton" aŭ "eĥon vundebla"
sed kio se vi faris ion vere malica, kiel rm -rf *,
kion vi ne fariĝu neniam tajpis antaŭe,
kaj sincere vi probable por ne tro frue,
ĉar vi povas fari multan damaĝon kun ĝi.
Kial?
rm faras kion, kompreneble?
Forigas.
* Signifas kion?
Ĉiuj.
Do ĝi estas tiel nomata ĵokero, do signifas
forviŝi ĉion en la aktuala dosierujo.
-r okazas al signifi rekursie, kio signifas, se kion vi viŝante
estas dosierujo, kaj ene de tie Estas aliaj dosieroj kaj aliaj dosierujoj,
rekursie plonĝi en tie kaj forviŝi ĉiujn tion.
Kaj -f estas la plej malbona el ĉiuj.
Ĉiu scias kion -f signifas ĉi tie?
Forto.
Do devigi rimedoj, eĉ se tio estas malbona ideo,
faru ĝin sen instigante min por plua konfirmo.
Do, sciu, ni ridi tiu, sed sincere, mi probable
tajpi ĉi multnombraj fojoj tago, ĉar la realo
Estas ĝi estas la plej rapida maniero forviŝi tutan faskon da aĵoj.
Sed eĉ mi faris iun damaĝon.
>> Sed se vi estus trompi komputilo en difinanta kelkaj stultaj variablo
aŭ funkcio nomita x, sed tiam trompante la komputilo en ekzekutinte
trans la limoj de tiu funkcio, preter tiu punktokomo,
Vi povus ja trompi komputilo en ekzekuti iun kiel rm -rf
aŭ Retpoŝto komando aŭ Kopii komando.
Io laŭvorte povas fari kun la komputilo, ĉu ĝi estas viŝante dosieroj
krei dosierojn, spamming iu, ataki iun servilon remotamente,
se vi povas esprimi kun komando, vi
povas trompi komputilo en fari tion.
>> Nun kio estas ekzemplo de kiel vi povus fari tion?
Nu, tie estas multe da komputiloj en interreto kurado Bash.
Ĉiuj el ni Mac uzantoj estas inter ili.
Multa Linukso serviloj estas inter ilin tiel, kaj Unikso-serviloj.
Vindozo denove ricevas relative for de la hoko
se vi instalis speciala programaro.
Nun multajn servilojn, por Ekzemple, kuri retserviloj,
kaj fakte Linukso estas eble la plej popularaj mastruma sistemo
kuri sur komputiloj en interreto kiuj servas supren retpaĝoj.
Nun ni vidos poste en la semestro, kiam
Sendinte peto de via browser-- Chrome,
Interreto Explorer, whatever-- al fora servilo,
Ĝi rezultas ke eĉ kvankam vi ĵus tajpis www.example.com,
via retumilo sendas mesaĝon ke estas iom pli arcano, kiel tiu.
>> Sed rimarki iom io stranga.
La unuaj du linioj Mi neniam vidis antaŭe,
sed ili ne rigardas aparte minaca.
Sed rimarki kion mi ŝtelita por la tria linio tie.
Se malbona ulo estis por sendi mesaĝon kiel tiu de lia aŭ ŝia komputilo
al vundeblaj Mac aŭ vundeblaj Linukso servilo
la amuza afero estas ke Bash, ke simplaj iom komando prompto,
estas ĉiea kaj estas ofte uzita por esence ekzekuti
la enhavo de mesaĝo kiun ĝi ricevas.
Kaj per tiu logiko, oni povas trompi reta servilo, do
sendante iun kiel Uzanto-Agento, kiu kutimas
supozas diri la nomo de via retumilo.
Uzanto-Agento Chrome, Uzanto-Agento Interreto Esploristo, Uzanto-Agento Firefox, tiu
estas nur via foliumilo vojo de identigi.
Sed se malbona ulo tre lerte diras mm-mm, mi
Ne tuj diros kion mia foliumilo,
Mi anstataŭ tuj sendos al vi tiun kamufla aspekto aferon kun rm -rf
* En ĝin, vi povas laŭvorte trompi oni vundeblaj retservilo en interreto
en ekzekuti ĝuste ke en tie por viŝi ĉiujn dosierojn.
Kaj sincere, tio ne eĉ la plej malbonan de ĝi.
Vi povas fari nenion.
Vi povus komenci distribuita neado de servo atako
Se vi sendis tiun mesaĝon al tutaj aroj da ttt-serviloj
kaj tiam havis ilin cxiujn malsupreniros, por Ekzemple, sur Harvard.edu serviloj,
kaj vi povas ordigi de bang la heck ekstere de ili
por reto trafiko kiu estis alie ekkaŭzita de ĉi malbona ulo.
>> Do, longan rakonton mallonga, preskaŭ ĉiuj en tiu ĉambro, kiu posedas Mac
estas vundeblaj al tiu.
La arĝenta tegaĵo estas ke se vi estas kurante retejo servilo en via portebla,
kaj se vi efektive agordita ĝi permesi iu kiel SSH en ĝin,
vi estas vere sekura.
Ĝi estas vundebla, sed ne estas oni provas eniri en via portebla,
tial vi povas ia trankvila.
Tamen, Apple volas frue estos ĝisdatiganta oni riparas por tio.
La mondo de Linukso jam liberigita kelkaj korektoj por Fedora kaj Ubuntu
kaj aliaj versioj de Linukso, kaj ja Se vi kuras ĝisdatigon 50 en la aparato,
eĉ ke tro estos ĝisdatigita kaj korektita.
Sed ankaŭ ne havas vere estis vundebla,
ĉar se vi havas tinkered kun la aparato
kaj vian tekkomputilon publike alireblaj en la interreto, kiu estas ne
implicite, vi havas fakte estis delikata ĉar
de firewalling kaj aliaj teknikoj.
>> Sed estas ekstrema ekzemplo de cimon ke ni vivis por laŭvorte 20
jaroj, kaj kiu scias se iu ĉiu ĉi tiu tempo sciis pri ĝi?
Kaj fakte, ĉi tiu estas unu el la fundamentaj defioj
ke ni vidos poste en la semestro pri sekureco,
estas ke ĝuste kiel en la reala mondo, la bonuloj estas je la malavantaĝo.
Por teni la maliculojn el ni devas certiĝu ke ĉiu pordo estas ŝlosita,
ke ĉiu fenestro estas sekura, ke ĉiu punkto de eniro en hejmo
estas sekura por gardi la maliculojn eksteren.
Sed kion faras la malbona ulo devas faru por fakte kompromisi via hejmo
kaj ŝteli de vi?
Li aŭ ŝi simple devas trovi unu malŝlosita pordon, unu rompitan fenestron, aŭ io
kune tiujn liniojn, kaj ĝi estas la samon en komputila sekureco.
Ni povas skribi milionojn da linioj de programado kodo
kaj elspezi centojn aŭ milojn de horojn klopodante akiri ĝin ĝentila,
sed se vi faros nur unu eraro en praveco,
vi povas meti la tutan sistemon kaj ja en tiu kazo, la tuta interreto
kaj mondo en risko.
>> Do se vi ŝatus lerni pli pri tio, iru al tiu URL tie.
Ne estas bezono por ago tonight krom se vi
inter tiuj pli komforta ol estis kurante via propra retejo
servilo, en kiu kazo vi devus, fakte, ĝisdatigi vian programaron.
>> Kaj ĉi tiu estas ankaŭ la titolo de paroladon, kaj nun papero,
ke ni ligita sur la Certe la retejo hodiaŭ.
Ĝi estis de ulo nomiĝas Ken Thompson, kiu
estis akceptante tre fama premio en komputiko,
kaj li donis al tiu parolado iuj jaroj monatoj, fundamente sur tiu sama temo.
Demandante ulojn la demando, devus vere
kuratoreco, finfine, la programaro vi estis donita?
Ekzemple, ni ĉiuj havas estis skribante programoj,
kaj ni iris kompilante ilin tin.
Kaj al via scio, vi skribis ajna programoj por CS50 kie ekzistas
malantaŭa pordo de varoj, tie estas vojo ke malbona ulo, se kuranta vian programon,
povus transpreni via komputilo?
Probable ne, ĉu ne?
Mario kaj avida, kaj Kredito.
Tiuj estas ĉiuj belaj malgrandaj programoj.
Vi devus esti bela malbona se vi reale
faris vian tutan komputilon vundebla post skribi 10 aŭ 20 linioj de kodo,
aŭ almenaŭ ne konis iun de la sekureco implikaĵoj.
Nun mi diros ke facetiously, sed ni tuj vidos hodiaŭ
kaj ĉi tiu semajno estas reale vere, vere facila
esti malbonaj kaj fari eĉ mallongajn programojn vundebla.
>> Sed nuntempe, almenaŭ, realigi ke la demando petas tien
Estas proksimume tin en tradukilo.
Kial ni estis konfidita tin Dum la pasintaj du aŭ tri semajnoj?
Kiu estas diri ke kiu skribis tin ne havi "se" kondiĉo en tie
ke esence injektis iuj nuloj kaj karaj en ĉiu programo kompilas
kiu lasus lin aŭ ŝin aliron via komputilo kiam vi estas dormanta
kaj via tekkomputilo kovrilo estas malferma kaj via komputilo kuras?
Ĝuste?
Ni havas tian honoron sistemo dekstra nun, kie ni esperas ke tin Estas legit.
Vi esperas, ke la aparato estas legit.
Vi esperas ke laŭvorte ĉiu programo sur via Mac aŭ PC estas fidinda.
Kaj kiel tiu simpla cimon sugestas, eĉ se ĝi ne estas malicaj,
tio tute ne verŝajna esti la kazo.
>> Do vi devus esti timigita kiel infero.
Sincere, ne estas simpla solvon al tiu alia
ol speco de socia konscio la kreskanta komplekseco
ke ni konstruas sur supro de niaj komputiloj,
kaj kiom pli vundebla ni povus tre bone esti.
>> Nun kun kiu diris, Breakout.
Do Breakout estas problemo starigis tri, kaj Breakout estas ludo de pasintaj tempoj
ke vi eble memoras, sed por ni en problemo starigis tri,
ĝi permesas preni aferojn asist muesca
tiel ke kiam ni skribas programojn, eĉ en Terminal fenestro ŝatas ĉi,
ni povas reale funkcii, finfine, grafika programoj ne
kontraste kun tiuj ni devis aliro al en Scratch.
Do tio estas la taĉmento efektivigo de Breakout,
kio estas ĝuste tiu briko-rompado ludo, ke vi movas vian paddle reen
kaj reen, kaj vi batas la pilkon kontraŭ tiuj koloraj brikoj ĝis supro.
Do tiu elkondukis nin ia reen al kie
Ni povis esti tre rapide kun Scratch, kaj nun kun C,
efektivigo nia propra grafikaj interfacoj.
>> Sed pli ol tio, tiu problemo aro reprezentas la unuan
kiun ni donas vi aron de kodo.
Kaj fakte mi venigas eksplicita atenton al tio, ĉar speciale
por tiuj malpli komforta, tiu problemo aro, almenaŭ unuavide,
tuj sentas ni prenis ĝin muesca.
Ĉar ni donas al vi, por iuj de la serĉo
kaj ordigi problemojn en la pset, faskon de kodo kiu ni skribis,
kaj paro da komentoj kiuj diras "fari"
kie vi devas plenigi la spacojn.
Do ne tro timigas, sed ĝi estas la unua fojo
ni disdonado vi kodo, ke vi bezonas unue legi, kompreni, kaj poste aldoni al
kaj kompletigi ĝin.
>> Kaj tiam kun Breakout, ni tuj faras lin sama,
doni vin kelkaj dekduo pli linioj de kodo kiu, sincere, donu vin
multe de la enkadrigi la ludo sed halti mallonga
aplikado de la brikoj kaj la pilko kaj la remilon,
sed ni planas iujn aliajn funkciojn.
Kaj eĉ tio unuavide, denove, speciale se malpli komfortaj,
eble ŝajnas aparte fortimiga kaj Vi kredas, ke estas tiom multaj novaj funkcioj
vi bezonas envolver vian menson ĉirkaŭe, kaj tio estas vera.
Sed teni en menso, estas tute kiel Scratch.
Odds estas, ke vi ne uzu ĉiuj la puzlo pecoj en Scratch.
Odds estas vi ne zorgas envolver via menso ĉirkaŭ ĉiu el ili
ĉar ĉiuj ŝin kaptis estis rapida rigardo kompreni, ho,
tio kion mi povos fari kun tiu puzlo peco.
Kaj efektive, en problemo starigis 3 spec, ni atentigi vin
en la dokumentado kiu volas enkondukos vin al iuj novaj funkcioj,
kaj finfine la programado Konstruas vi uzas.
Kondiĉoj, loops, variabloj kaj funkcioj
estos identa al kion ni vidis ĝis nun.
>> Do ja, kion ni donos Vi estas kelkaj specimenaj kodon
lasas vin krei fenestro kiuj aspektas ne kontraste tio,
kaj finfine igi ĝin iu sufiĉe ŝatas ĉi.
Do utiligi CS50, diskuti oficejo horoj kaj pli,
kaj preni komforton en la fakto, ke la kvanto de kodo vi devas skribi
fakte ne ĉiuj kiuj multe.
La unua defio estas simple alklimatigi preni iom da kodo ni skribis.
>> Demandojn sur pset3, Shellshock, aŭ alie?
>> Publiko: Ĝi aspektis iri tra kun Breakout
ke la kodo estas preskaŭ objekteman stilo,
sed mi pensis C estis objektema programo.
SPEAKER 1: Bonega demando.
Do rigardante tra la dissendo kodo, la kodo
ni skribis por pset3, por tiuj familiaraj, ĝi
aspektas kiel ĝi estas iom objektema.
Mallonga respondo estas, estas.
Estas alproksimiĝo de kiel vi plenumadu objektema kodo uzanta
lingvo kiel C, sed estas ankoraŭ finfine procedural.
Ne estas metodoj ene de la variabloj, kiel vi vidos.
Sed estas rememorado de tiu.
Kaj ni vidos ke trajto denove Kiam ni atingos PHP kaj Javascript
al la fino de la semestro.
Sed nuntempe, rigardante ĝin kiel aludo de kio estas por veni.
Bona demando.
Bone.
Do kunfandi varo estis kiel ni maldekstra tion lastan fojon.
Kaj Kunfandi varo estis cool en la senco ke ĝi estis tiel rapida,
almenaŭ bazita sur la supraĵa testoj Ni faris pasintsemajne, ol, ekzemple, bobelo
varon, selektado speco, inserción varo.
Kaj kio estis neta tro estas nur kiom konciza kaj pure
oni povas esprimi ĝin.
Kaj kion ni diru estis supra ligis sur la rula tempo de merge
ordigi?
Yeah?
>> Publiko: n log n?
>> SPEAKER 1: n log n, dekstre. n log n.
Kaj ni revenos al kio vere signifas aŭ kie tiu devenas,
sed tio estis bona ol kion rultempo
ke ni vidis por bobelo selektado kaj inserción speco?
Do n kvadratoj. n kvadratoj estas pli granda ol tiu,
kaj eĉ se ĝi ne estas sufiĉe preterlasas, scias ke log n estas pli malgranda ol n,
do se vi faros n fojoj iu pli malgranda ol n,
tio okazas al esti malpli ol n kvadratoj.
Estas iom de intuicio tie.
Sed ni pagas prezon por tio.
Ĝi estis pli rapida, sed temo kiu komencis ŝpruci pasintsemajne estis ĉi tradeoff.
Mi havas pli bonan rendimenton tempo saĝa, sed kion
ĉu mi devas pasigi en la alia mano, por atingi tion?
>> Publiko: Memoro.
SPEAKER 1: Diru denove?
Publiko: Memoro.
SPEAKER 1: Memoro aux spaco pli ĝenerale.
Kaj ne estis súper evidenta kun niaj homoj,
sed memoras ke niaj volontuloj estis tretante antaŭen kaj tretante
reen kvazaŭ ekzistas tabelo tie, kaj kvazaŭ ekzistas
dua tabelo tie ili povus uzi, ĉar ni
bezonataj someplace kunfandi tiujn ulojn.
Ni ne povis simple interŝanĝu ilin en lokon.
Do kunfandi speco influon estas pli spaco, kiu
Ni ne bezonos kun la aliaj algoritmoj,
sed la upside estas kiu estas multe pli rapida.
Kaj sincere, en la reala mondo spaco tiuj days-- RAM, malmola disko space--
estas relative malmultekosta, kaj tial tio ne nepre estas malbona afero.
>> Do ni preni rapidan rigardon, iom pli metode, kion ni faris
kaj kial ni diris, ke ĝi n log n.
Do jen la ok numerojn kaj la ok volontuloj ni havis lastan fojon.
Kaj la unua afero, kiun Kunfandi Ordigi sciigis al ni fari estis kio?
Publiko: Akvodislimo en du.
SPEAKER 1: Diru denove?
Publiko: Akvodislimo en du.
SPEAKER 1: Akvodislimo en du, dekstre.
Tiu estas tre memoras la telefono libro, de divido
kaj konkeri pli ĝenerale.
Do ni rigardis la maldekstra duono.
Kaj tiam unufoje ni diris, varo maldekstre duono de la elementoj,
kion ni apud diri?
Ordigi la maldekstra duono de la maldekstra duono, kiuj ebligis al ni,
post dividi en du, enfokusigi sur kvar kaj du.
>> Kiel vi ordigi liston nun, en flava, de grandeco du, uzante Kunfandi varo?
Nu dividi ĝin en duono, kaj ordigi la maldekstra duono.
Kaj tio estis kie aferoj akiris iom stulta mallonge.
Kiel vi ordigi liston tio de grandeco oni, kiel tiu numero kvar tie?
Ĝi estas ordigitaj.
Vi faris.
>> Sed tiam kial vi ordigi listo grandeco kiam ĝi estas la numero du?
Nu, tion saman, sed nun kia estis la tria kaj la ŝlosilo paŝo en Merge Sort?
Vi devis kunfandi la maldekstra duono kaj la dekstran duonon.
Kaj iam ni faris tion, ni rigardis ĉe kvar, ni rigardis du.
Ni decidis bone, evidente du venas unue,
do ni metas du en lia loko, sekvita per kvar.
Kaj nun vi devas ia malantaŭenigi, kaj tio estas ia karakteriza
de algoritmo kiel Merge Ordigi, malantaŭenigi en memoro.
Kio estis la sekvanta linio de la historio?
Kion mi devas centri en la proksima?
La dekstran duonon de la maldekstra duono, Kiu estas ses kaj ok.
>> Do lasu min simple paŝo tra tiu sen belaboring la punkto tro multe.
Ses kaj ok, tiam ses estas ordo, ok estas ordigitaj.
Kunfandi ilin kune kiel tiu, kaj nun la sekva granda paŝo
Estas, kompreneble, ordigi la dekstran duonon de La unua paŝo de ĉi tiu algoritmo.
Do ni enfokusigi unu, tri, sep, kvin.
Ni tiam koncentri sur la maldekstra duono.
La maldekstra duono de tio, la dekstra duono de tiu, kaj tiam kunfandi en unu kaj tri.
Tiam la dekstra duono, tiam lasis la duonon de ĝi, tiam la dekstra duono de ĝi.
Kunfandi ĝin, kaj nun kio paŝo restas?
Kunfandi la granda maldekstra duono kaj la granda dekstran duonon, do oni iras malsupren tie,
poste du, poste tri, kvar, tiam kvin, tiam ses, tiam sep, tiam ok.
>> Do nun kial tio finfine malkaŝante, speciale se n kaj logaritmoj pli
Ĝenerale anstataŭ eskapi al vi, almenaŭ en la lastaj memoro?
Nu, rimarki la alteco de ĉi tiu afero.
Ni havis ok eroj, kaj ni dividis du, por du, por du.
Do ensaluti bazo du el ok donas al ni tri.
Kaj fidi min ke se iom malprecizaj sur tio.
Sed ensaluti bazo du el ok estas tri, tial ni faris tri tavoloj de kuniĝo.
Kaj kiam ni kuniĝis elementoj, kiom da elementoj
ni rigardas sur ĉiu el tiuj vicoj?
Entute n, ĉu ne?
Ĉar kunfandi la supro vico, kvankam ni faris piecemeal,
ni finfine tuŝis ĉiun numeron unufoje.
Kaj en la dua vico, al kunfandi tiujn listojn de grandeco du,
Ni devis tuŝi ĉiun elementon unufoje.
Kaj tiam tie vere klare en la lasta vico,
Ni devis tuŝi ĉiun el tiuj elementoj unufoje, sed nur unufoje,
tiel ene difinitaj kuŝas do nia n log n.
>> Kaj nun simple fari tion iom pli formala por nur momenton, se vi
estis nun analizi tiu ĉe ia alta nivelo
kaj provi decidi, bone kiel eble vi iru kaj esprimu
la rula tempo de ĉi tiu algoritmo nur rigardi ŝin kaj ne
uzante elpensita ekzemplo?
Nu, kiom da tempo vi dirus al paŝo kiel ĉi flava prenus,
se n <2 reveno?
Tio estas granda O de kio?
Do mi vidas unu, do unu paŝon, eble du paŝoj ĉar ĝi estas kvazaŭ
kaj tiam reveni, sed ĝi konstanta tempo, ĉu ne?
Do ni diris O (1), kaj tio estas kiom mi esprimas ĉi.
T, simple estu rultempo.
n estas la amplekso de la enigo, tiel T (n), nur ornama metodo
diri la kurado tempo donita enigo de grandeco n
tuj estos de la ordo de konstanta tempo, en O (1).
>> Sed se ne, kio pri tio?
Kiel vi esprimas la rula tempo de ĉi flava linio?
T de kio?
Vi povas ia cheat tie kaj respondi mian demandon cikle.
Do se la rula tempo Ĝenerale ni nur diros estas T (n).
Kaj nun vi ia punting tie kaj dirante, nu, simple ordigi la maldekstra duono,
kaj tiam ordigi la dekstran duonon.
Kiel povus ni simbole reprezenti la rula tempo de ĉi flava linio?
T de kio?
Kio estas la grandeco de la eniro?
n super du.
Kial mi ne simple diri tion?
Kaj tiam tiu estas alia T (n / 2) kaj poste denove, se mi kunfandi du ordigitaj duonoj,
kiom eroj mi tuj devos tuŝi entute?
n.
Do mi povas esprimi tion, nur estu ia kaprico,
kiel la rultempo ĝenerale.
T (n) estas simple la rula tempo de T (n / 2), plus T (n / 2), maldekstra duono kaj dekstran duonon,
plus O (n), kio verŝajne n paŝoj, sed eble, se mi uzas du fingroj,
ĝi estas duoble pli multaj paŝojn, sed estas lineara.
Estas kelkaj nombro de paŝoj ke estas faktoro de n,
do ni povus esprimi ĉi tiel ĉi.
Kaj ĉi tiu estas kie nun ni Punt al la dorso de nia mezlernejo math lernolibro
ni ke ripetiĝo finfine finu egalanta ĉi, n fojojn log n,
se vi efektive faras el la matematiko pli formale.
>> Do tio estas nur du vidpunktoj.
Unu numere per hard-coded reprezenta ekzemplo
uzante ok ciferoj, kaj pli ĝenerala rigardi kiel ni atingis tien.
Sed kio estas vere interesa tie estas, denove, tiu nocio de biciklado.
Mi ne uzas por bukloj.
Mi speco de difinanta io en terminoj de sin,
ne nur kun tiu matematika funkcio,
sed ankaŭ en terminoj de tiu pseŭdo kodo.
Tiu pseŭdo kodo estas rikura en kiu du de liaj linioj
Estas esence rakontante iri uzi mem solvi malgranda
problemo de malgranda grandeco, kaj tiam denove kaj denove
kaj denove ĝis ni Whittle ĝi al tiu tiel nomata baza kazo.
>> Do ni vere desegni pli konvinka prenu-for de ĉi jene.
Lasu min iri en gedit kaj preni rigardu kelkajn el la hodiaŭaj fontkodon,
precipe tiu ekzemplo tie.
Sigma 0, kiu ŝajne ĝi aldonas la nombroj unu tra n.
Do ni vidu kio estas familiara kaj nekonataj tie.
Unue ni havas paron de inkluzivas, do nenio nova tie.
Prototipo.
Mi estas iomete malprecizaj en tio post kelkaj tagoj,
sed kion ni diras al prototipo de funkcio estas?
Publiko: [inaudible].
SPEAKER 1: Kio estas tio?
Publiko: Ni anoncas ĝin.
SPEAKER 1: Ni anoncas ĝin.
Do vi instruas tin, he, fakte ne implementar ĉi tamen,
sed ie en tiu dosiero, supozeble, tuj estos funkcio nomita kio?
Sigma.
Kaj tio estas nur promeso ke ĝi tuj aspekti ĉi.
Ĝi tuj prenos entjero kiel input-- kaj mi povas esti pli eksplicita
kaj diru int n --and estas tuj revenos al int,
sed punktokomo signifas, mm, mi povos al implementar ĉi iom poste.
Denove, tin estas muta.
Ĝi estas nur tuj scii kion vi diris gxin supre sube,
tial ni bezonas almenaŭ donu ĝi aludo de kio estas por veni.
>> Nun ni rigardu ĉefa tie.
Ni rulumu malsupren tie kaj vidu kia ĉefa faras.
Ĝi ne estas tiel longa de funkcio, kaj fakte la konstruo tie estas familiara.
Mi deklaras variablon n, kaj tiam Mi Pester la uzanto multfoje
por pozitiva entjero uzanta getInt, kaj nur eliron el tiu buklo
Tuj la uzanto obeis.
Ĉu Dum, ni kutimi Pester la uzanto en tiu vojo.
Nun tio estas interesa.
Mi deklari int nomita "respondo".
Mi atribuas lin la reveno valoro de funkcio nomita "sigmo".
Mi ne scias kion tiu faras ankoraŭ, sed Mi memoras deklarante ĝin antaŭ momento.
Kaj tiam mi pasante en la valoro kiun la uzanto tajpas en, n,
kaj tiam mi raportos al la respondo.
Nu ni rulumu reen por nur momento.
Ni iru antaŭen en tiu dosierujo, fari sigma 0, kaj fakte kuri ĉi programo
kaj vidu kio okazas.
Do, se mi iru antaŭen kaj kuri tiu programo, ./sigma-0,
kaj mi tajpas en pozitiva entjero kiel du, Sigma,
kiel la greka simbolo implicas, estas nur tuj aldonos ĉiujn numerojn de
nulo je ĝis du.
Do 0 plus 1 plus 2.
Do tiu devus espereble donos al mi 3.
Tio estas ĉio tio faras.
Kaj simile, se mi kuros ĉi denove kaj Mi donos al ĝi la numero tri,
tio estas 3 plus 2, tiel ke estas 5, plus 1 donu al mi 6.
Kaj tiam se Mi vere freneza kaj ektajpu en grandaj nombroj,
devus doni min pli kaj pli sumoj.
Do jen ĉio.
>> Do kion signifas sigma aspektas?
Nu, estas sufiĉe simpla.
Ĝi estas kiel ni povus esti implementado tio dum la lastaj semajnoj.
"Int" tuj estos la reveno tipo.
Sigma estas la nomo, kaj ĝi prenas ŝanĝiĝema m anstataŭ n.
Mi ŝanĝu tion ĝis supro.
Tiam ĉi tio estas nur la prudento ĉeko.
Ni vidos kial en momento.
Nun mi rakontos alian variablo, sumo, pravalorizi ĝin al nulo.
Tiam mi havas Por maŝo ripetanta, ŝajne por klareco,
de i = 1 sur supren al = m, kio estas ajn la uzanto tajpas en, kaj tiam mi
pliigo sumo kiel ĉi.
Kaj tiam reveni sumo.
>> Do kelkaj demandoj.
Unu, mi asertas en mia komento, ke tiu evitas risko de senfina buklo.
Kial pasante en negativa nombro indukti, potenciale, senfina ciklo?
>> Publiko: Vi neniam atingos m.
>> SPEAKER 1: Neniam atingi m.
Sed m ​​estas pasita en, do ni konsideri simplan ekzemplon.
Se m estas pasita tra la uzanto kiel negativa.
Sendepende de ĉefa.
Ĉefa protektas nin de tiu tro, do mi simple
estante vere anal kun sigma ankaŭ certigi
ke la enigo ne povas esti negativa.
Do se m estas negativa, iu kiel negativa.
Kio okazos?
Nu, mi tuj get inicializado al unu,
kaj tiam mi tuj estos malpli ol aŭ egala al m?
>> Staras.
Tio was-- ni ne, ni Nix tiu rakonto.
Mi ne demandis tiun demandon, ĉar la riskon ke mi aludante
ne tuj okazos ĉar mi estas ĉiam tuj estos granda than-- OK,
Mi desdicen tiu demando.
OK.
Ni enfokusigi nur en tiu parto tie.
Kial mi deklaras iun ekster la buklo?
Avizo en linio 49 Mi havas deklaris i interne de la buklo,
sed linio 48 Mi havas deklaris iun ekstere.
Yeah.
Publiko: [inaudible].
SPEAKER 1: Certe.
Do unuavice mi certe ne deziras deklari kaj pravalorizi sum
nulon ene de la buklo sur ĉiu ripeto,
ĉar tio klare venki la celo de resumante la numerojn.
Mi devus teni ŝanĝanta la valoro reen al nulo.
Kaj ankaŭ, kio estas alia pli arcano kialo por tiu sama dezajno decido?
Yeah.
>> Publiko: [inaudible].
SPEAKER 1: Ekzakte.
Mi volas konsenti li ekstere de la buklo tro sur kio linio?
On 53.
Kaj bazita sur nia regulo de thumb el paro de prelegoj monato,
variabloj scoped, vere, al la frizita krampoj kiuj ampleksas ilin.
Do, se mi ne rakontos sumo interne el tiuj eksteraj frizita krampoj,
Mi ne povas uzi ĝin en linio 53.
Alivorte, se mi deklaras sumo en ĉi tie, aŭ eĉ ene de la
Por buklo, mi ne povis aliri ĝin en 53.
La variablo devus efike foriru.
Do kelkaj kialoj.
Sed nun ni iru reen kaj vidu kio okazas.
Do sigma prenas vokis.
Ĝi adicias supren 1 plus 2 aŭ 1 plus 2 plus 3, kaj tiam redonas la valoron,
stokas ĝin en respondo, kaj printf tie Tial mi vidas sur la ekrano.
Do jen kion ni nomas ripeta alproksimiĝo, kie ripeto simple
signifas uzante buklo.
A Por buklo, momenton buklo, oni Do Dum buklo, simple fari ion denove
kaj denove kaj denove.
>> Sed sigma estas speco de neta funkcio en ke mi povus funkciigi ĝin malsame.
Kio pri tio, kion nur esti speco de cool,
lasu min vere forigi de multaj distro
ĉar tiu funkcio estas vere sufiĉe simpla.
Ni Whittle ĝin simple gxiaj kvar kerno linioj
kaj forigi ĉiujn komentoj kaj frizita krampoj.
Tiu estas speco de menso-blovita Alternativa efektivigo.
Bone, eble ne gravas-blovas, sed estas speco de sexier, bone,
rigardi ĉi tiel pli konciza.
Kun nur kvar linioj de kodo, Mi unue havas tiun prudento ĉeko.
Se m estas malpli ol aŭ egala al nulo, sigma faras neniun senson.
Ĝi nur supozis esti en tiu kazo por pozitivaj nombroj,
do mi simple tuj reveni nulo arbitre
tiel ke ni almenaŭ havas iuj tn baza kazo.
>> Sed jen la beleco.
La tuteco de tiu ideo, aldoni la nombroj de 1 al n, aŭ m tiukaze
povas esti farita de ia pasante la cervo.
Nu, kio estas la sumo de 1 al m?
Nu, vi scias pri kio?
Ĝi estas la sama kiel la sumo de m plus la sumo de 1 al m minus 1.
Bone vi scias kion?
Kio sigma m minus 1?
Nu, se vi speco de sekvi ĉi logike, ĝi estas la sama kiel m minus 1
plus sigma m minus 2.
Do vi povas ia just-- tio estas kiel, se vi nur
provas tedi amikon kaj ili demandos vin demandon,
Vi ia respondas per demando: Vi povas ia teni pasante la cervo.
Sed kio estas ŝlosilo estas ke se vi observos fari la demandon pli kaj pli
kaj pli malgrandaj, vi estas Ne demandi kio estas sigmo
n, kio estas sigmo de n, kio estas sigma n?
Vi demandas kion estas sigma n, kio estas sigmo
de n minus 1, kio estas sigma n minus 2?
Eventuale vian demandon tuj fariĝi kio?
Kio estas sigmo de unu aŭ nulo, iuj tre malgranda valoro,
kaj kiam vi bonstata, via amiko,
vi ne tuj petos La sama demando denove,
vi nur volis diri, oh estas nulo.
Ni faritaj ludi ĉi speco stulta ciklaj ludo.
>> Do rekursio estas la akto en programado de funkcio nomante mem.
Tiu programo, kiam kompilis kaj kuri, estas tuj kondutos precize la sama maniero,
sed kio estas ŝlosilo estas ke interne de funkcio nomita sigma,
estas linio de kodo, kien ni vokas nin,
kiu estus normale esti malbona.
Ekzemple, kio se mi unue kompilis ĉi, do fari sigma--
fari sigma 1 ./sigma-1.
Pozitiva entjero, bonvolu, 50 1275.
Do kio estas la funkcio ŝajnas esti, bazita sur unu provo, korekta.
Sed kio se mi alvenas iom danĝera kaj forviŝi la tn baza kazo,
kaj simple diru, bone mi simple farante tiu pli komplika ol ĝi.
Ni nur komputi la sigma prenante m kaj tiam aldonante
en sigma m minus unu?
Nu, kio okazos tie?
Ni malzomi.
Ni recompilar la programo, savi gxin recompilar la programo,
kaj tiam preta ./sigma-1 zoom in, eniri pozitiva entjero bonvolu, 50.
Kiel multaj el vi pretas al Fess ĝis vidante ke?
>> OK.
Do tio povas okazi pro kelkaj kialoj,
kaj sincere tiu semajno ni pri doni al vi pli da ili.
Sed en ĉi tiu kazo, provi rezoni malantaŭen
kio eble okazis tie?
Segmentación kulpo, ni diris lastan tempo raportas al segmento de memoro.
Io malbona okazis.
Sed kio estis mekanike kiuj iris malbone
tie pro mia forigo de tiu tn baza kazo,
kie mi revenis malmola-kodita valoron?
Kion vi pensas eliris malbone?
Yeah.
>> Publiko: [inaudible].
SPEAKER 1: Ha.
Bona demando.
Do la grandeco de la nombro ke mi resumante
akiris tiom granda ke ĝi superis La grandeco de la memoro spaco.
Bona ideo, sed ne fundamente tuj provokos kraŝo.
Tio povus kaŭzi entjero overflow, kie la bitojn nur klaki super
kaj tiam ni miskomprenas vere granda nombro por kiel negativa nombro,
sed tio mem ne kaŭzos kraŝo.
Ĉar ĉe la fino de la tagon int ankoraŭ 32 bitoj.
Vi ne tuj hazarde ŝtelis 33 bitoj.
Sed bona penso.
Yeah.
>> Publiko: [inaudible].
SPEAKER 1: La metodo neniam ĉesas kurante,
kaj ja nomas sin denove kaj denove kaj denove kaj denove
kaj denove, kaj neniu el tiuj funkcioj iam
fini ĉar ilia plando linio kodo nomas themself denove kaj denove
kaj denove.
Kaj kio estas vere okazas tie, kaj nun ni
povas speco de desegni ĉi pictóricamente.
Permesu al mi iri al bildo por nur momento.
Jen estas bildo, kiu eventuale karnon el
pli detale, kio okazas ene de via komputila memoro.
Kaj ĝi rezultas ke en la fundo de ĉi tiu bildo
Estas io nomata la stako.
Jen peco de memoro, eron de memoro RAM,
Tio estas nur uzita ajn funkcio estas nomita.
Ajna tempo vi, programisto, nomas funkcio,
la mastruma sistemo, kiel Mac OS, Vindozo, aŭ Linukson,
kroĉas faskon da bajtoj, eble kelkaj kilobajtoj, eble malmultaj megabajtoj
de memoro, manoj ili al vi, kaj tiam lasas
vi kuros viaj funkcio uzante ajn variablojn vi bezonos.
Kaj se vi tiam nomita alia funkcio kaj alia funkcio,
vi havos alian tranĉaĵo de memoro kaj alia peco de memoro.
>> Kaj efektive, se tiuj verdaj pletoj el Annenberg reprezenti tiu memoro,
jen kio okazas la unua tempo vi nomas funkcio sigma.
Estas kiel meti pleto ŝatas ĉi sur kio estas komence malplenan pilo.
Sed tiam, se tiu pleto nomas sin, por tiel diri,
nomante alia petskribo de sigma, tio
kiel peti la mastruma sistemo, Ooh, bezonas iom pli da memoro,
donu al mi.
Kaj tiam ĝi ricevas amasiĝis sur la supro.
Sed kio estas ŝlosilo tie estas ke la unua pleto estas ankoraŭ tie,
ĉar li alvokebla tiu dua pleto.
Nun dume, sigma nomas sigma, tio estas kiel peti pli memoro.
Gets amasiĝis sur tien.
sigma nomas sigma, jen alian pleto kiu prenas amasiĝis tie.
Kaj se vi dauxre faras tion, eventuale, speco de mapo ĉi vida
por ke letero, kio tuj okazi kun la pilo de pletoj?
Tuj superos la kvanton de memoro de via komputilo havas.
Kaj tuj kiam ĉi verda pleto superas la horizontala linio
supre stako kaj supre vorto amason, kiun ni revenos al la estonteco,
ke estas malbona afero.
La havaĵo estas malsamaj Segmento de memoro,
kaj se vi lasu tiujn pletoj amaso kaj amaso sur,
vi tuj superos via propra segmento de memoro,
kaj programo estas ja tuj frakasos.
>> Nun kiel flanken, tiu ideo de rikuro, do
povas klare kondukas al problemoj, sed ĝi ne estas nepre malbona.
Pro konsideri, post ĉiuj, how-- kaj eble
tio prenas iom kutimante al --how eleganta aŭ kiel simpla
ke efektivigo de sigma estis.
Kaj ni ne tuj uzos rekursio ĉiuj kiuj multe en CS50,
sed en CS51, kaj vere ajna klaso kie vi manipuli datumstrukturoj
kiel arboj aux familio arboj, kiuj havas iun hierarkio,
ĝi estas super, super utila.
Nun, kiel flanken, por ke vi kiel aspirante komputilo sciencistoj
estas familiara kun kelkaj Google ene ŝercoj, se vi iras al Google
kaj vin serĉi kio estas la difino de, ekzemple, rekursio, eniru.
Uh-huh.
Kiel flanken, mi tiris supren kelkajn.
Tio estis kiel 10 minutoj prokrastado ĉimatene.
Se vi ankaŭ Google "Askew," avizo Movante via kapo slightly--
kaj tiam ĉi tiu estas eble plej terura el ĉiuj
ekde iu eluzita kiel ilia tago implementando ĉi
kelkaj jaroj ago-- venu.
Ho, wait-- tio cimon.
>> Do kurante en unu el la mondaj plej grandaj retejoj
Estas tiuj stultaj iom Pasko ovojn.
Ili probable konsumi netriviala nombro da linioj de kodo
nur por ke ni povu havi iom amuza aferojn tiel.
Sed almenaŭ nun vi ricevos kelkaj el tiuj ene ŝercoj.
>> Nun ni rigardu kelkajn el la blanka kuŝas ni estis rakontante antaunelonge,
kaj komencu de senŝeligi reen iuj tavoloj teknike
por ke vi vere komprenas kio daŭras
kaj vi povas kompreni kelkaj el la minacoj,
kiel Shellshock, ke jxus komencis fariĝi
sur la antauxa flanko de ĉies atenton, almenaŭ en la amaskomunikiloj.
Do ĉi tie estas tre simpla funkcio kiu redonas nenion malplenon.
Lia nomo estas swap.
Ĝi prenas en du variabloj kaj tio rezultigas nenion.
Portas en kaj b.
Tiel rapida pruvo.
Ni alportis tiujn supren.
Ni povus tiel preni iom rompi ĉi tie dum nur momento
kaj havas iom ion por trinki.
Se iu ne gravas kunigi min tie dum nur momento.
Kion pri vi en la maroon ĉemizo?
Venu supren.
Apenaŭ unu hodiaŭ.
Dankon, tamen.
Bone, kaj ni havas venanta supre kiuj tie?
Kio estas via nomo?
>> SPEAKER 4: Laura.
>> SPEAKER 1: Laura.
Venu supren.
Do Laura, tre simpla defio hodiaŭ.
Agrable renkonti yo.
Bone.
Do ni havas lakton tien kaj ni havos iun oranĝsuko tien
kaj kelkaj tasoj ke ni pruntita de Annenberg hodiaŭ.
>> SPEAKER 4: Borrowed.
SPEAKER 1: Kaj tuj antaŭeniri kaj donu al vi duonon glason ĉi.
Bone.
Kaj ni donos al vi la duonon glason da lakto.
Ho, kaj ĝuste tial, ke vi povas memoru kio tio estis kiel,
Mi memoris alporti ĉi tien kaj en hodiaŭ.
Okay.
Se vi ne gravas, vidu, ni povas meti ilin sur vian propran pokaloj
se vi volas.
Tiu estos la mondo de Laura okuloj.
Bone.
Do via celo, donita du tasojn likva tie, lakto kaj oranĝa suko,
estas interŝanĝi la du enhavo tiel ke la oranĝa suko iras en la lakto taso
kaj la lakto iras en la oranĝa suko taso.
>> SPEAKER 4: Do mi akiri alian tason?
SPEAKER 1: Mi tiom ĝojas vin demandis, kvankam estus estinta multe pli bildoj
Se vi ne demandis.
Sed jes, ni povas oferti al vi trian taso tio malplena, kompreneble.
Bone.
Do interŝanĝu la enhavo tie.
Tre agrabla.
Tre bona.
Vi faras ĉi rimarkinde zorgeme.
Kaj paŝo tri.
Bone.
Bonega.
Granda ĉirkaŭvojon de aplaŭdoj estus bona por Laura.
Bone.
Ni havas iom adiaŭa donaco por vi, sed lasu min fari tiujn.
Dankon tiom.
Tiel simpla ekzemplo, kvankam, pruvi ke se vi faras
volas interŝanĝi la enhavon du ujoj,
aŭ ni nomas ilin variabloj, vi bezonas iun provizora stokado
enscenigi unu el la enhavoj en tia ke vi efektive povas fari la interŝanĝa.
Do ja, ĉi fontkodon supren tie en C estas reprezentanto de ĝuste tiu.
Se la oranĝa suko estis kaj la lakto Estis b, kaj ni volis interŝanĝi la du,
Vi povus provi ion krea verŝante unu en la alian,
sed tio probable ne estus fini aparte bone.
Kaj tial ni uzas trian tason, alvoko ĝi tmp, T-M-P per konvencio,
kaj metis la enhavon de la OJ en tio, tiam interŝanĝas taso,
tiam meti la OJ en la originalaj taso, tiamaniere
sukcesante, ĝuste kiel Laura faris, la interŝanĝo.
>> Do ni faru ĝuste tion.
Lasu min kaj malfermu supren ekzemplo tio
fakte nomita "neniu interŝanĝi, "ĉar tiu ne estas
kiel simple faris kiel vi eble opinias.
Do en tiu programo, rimarki ke Mi uzas stdio.h, nia malnova amiko.
Mi havas la prototipo por swap tie supre, kio
signifas lia implementación La verŝajne malsupre
kaj ni vidos, kio estas tiu ĉefa programo tuj faros por mi.
Mi unue deklari int x prenas unu kaj int y ricevas du.
Do pensu pri tiuj kiel OJ kaj lakto, respektive.
Kaj tiam mi simple havas printf dirante x estas tiu
kaj y estas tio, ĝuste tiel mi povas vide vidi kio okazas.
Tiam mi printf asertante ke mi interŝanĝi la du,
kaj tiam mi presi a pretendi ke ili estas interŝanĝitaj,
kaj mi presi x kaj y denove.
Do ĉi tie en interŝanĝa estas ĝuste kio Laura faris,
kaj ĝuste kion ni vidis en la ekrano antaŭ momento.
>> Do ni iru antaŭen kaj esti ege decepcionados.
Ne faru swap, kaj kuri neniun swap, zoom en sur la eligo tie.
Entajpu x 1, y 2, interŝanĝante interŝanĝitaj.
x estas ankoraŭ 1 kaj y estas ankoraŭ 2.
Do kvankam, sincere, tio aspektas akurate ŝatas, kvankam pli teknike,
kio Laura faris, ne ŝajnas funkcii.
Do kial estas tiel?
Nu, ĝi rezultas ke kiam ni skribos programon kiel tiu
kiu du ĉefaj, reliefigis tie, kaj tiam alian funkcion, kiel swap,
reliefigis tie, kiuj flamo, la mondo
aspektas iom ion kiel tiuj pletoj antaŭ momento.
Kiam ĉefa unue prenas vokis, ke estas kvazaŭ demandante mastruma sistemo
por iom de memoro por ajna loka variabloj kiel x kaj y ke ĉefa havas,
kaj ili finas dekstre tie.
Sed se ĉefa alvokoj interŝanĝi, kaj ĉefa sekvinbero por interŝanĝi du argumentoj, a kaj b,
oranĝa suko kaj lakto, ĝi ne ŝatas disdonado la oranĝa suko kaj lakto
Laura.
Kio komputilo faras, estas sekvinbero kopiojn de la oranĝa suko
kaj kopioj de la lakto al Laura, tiel ke kio estas finfine ene de tiu pleto
estas la valoro unu kaj du aux OJ kaj lakto, sed kopioj gxiajn
tiel ke ĉe ĉi tiu punkto en la rakonto, tie
Estas OJ kaj lakto en ĉiu de ĉi tiuj pletoj.
Tie estas unu kaj du en ĉiu de ĉi tiuj pletoj,
kaj la interŝanĝa funkcio estas ja funkcias.
Ĝi interŝanĝante ilin interne de la dua plejsupra pleto,
sed ke interŝanĝante havas neniun efikon.
Kaj bazita sur nur kelkaj baza principo ni
parolis antaŭe, kaj ja nur kelkaj minutoj, kio
povus klarigi kial ŝanĝi a kaj b ene de swap
havas nenian efikon sur x kaj y, kvankam Mi pasis x kaj y por la interŝanĝa funkcio.
Kio estas la ŝlosila vorto tie eble simplistically klarigi?
Mi kredas ke mi aŭdis ĝin ĉi tie?
Publiko: Reveno.
SPEAKER 1: Reiru?
Ne revenos.
Ni iru kun unu alia.
Kio estas tio?
>> Publiko: [inaudible].
>> SPEAKER 1: OK, do return-- ni povis fari revenon verkon en la rakonto,
sed estas eĉ pli simpla klarigo.
Publiko: Medio.
SPEAKER 1: Medio.
Mi prenos medion.
Do medion, memoras kie niaj x kaj y deklaris.
Ili deklaris interne de ĉefa tuj ĉi tie.
a kaj b, dume, estas efektive deklaris
ene de swap, ne tute en la frizita krampoj sed ankoraŭ
en la ĝenerala areo de swap.
Kaj tiel efektive, kaj b nur ekzistas ene de ĉi pleto
el Annenberg, tiu duan eron de kodo.
Do ni ja ŝanĝas la kopio, sed tio ne estas vere ĉiuj ke helpa.
>> Do ni rigardu tio iom malalta nivelo.
Mi tuj iros returne en La Source Dosierujo,
kaj mi tuj unue zomi tie, kaj nur
konfirmi ke mi estas en tiu granda fina fenestro,
La programo estas ankoraŭ kondutas tiel.
Supozu nun ke tiu ne estas intenca.
Klare mi volis swap al laboron, do ĝi sentas kiel cimon.
Nun mi povis komenci aldonante multan printf estas mia kodo,
presi ekstere x tien, y super ĉi tie, ĉi tie, b super tie.
Sed sincere, tio verŝajne vi estis faranta por paro de semajnoj
nun, en oficejo horoj Hejme kiam laborante
sur psets provas trovi iujn cimojn.
Sed vi vidos, se vi ne jam, ke problemo starigis tri enkondukas vin
ordono nomita GDB, kie GDB, erarserĉilo GNU,
havas mem tutan faskon da karakterizaj kiu povas reale
Ni komprenu situacioj kiel tiu, sed pli compellingly,
solvi problemojn kaj trovi cimojn.
Do mi tuj faros.
Anstataŭ ./noswap, mi anstataŭe tuj kuri GDB ./noswap.
En aliaj vortoj, mi tuj ekkuros mia programo ne en Bash, nia nova amiko
hodiaŭ.
Mi tuj kuros mia programo noswap interne
de tiu alia programo nomita GDB, kiu estas erarserĉilo, kiu
estas programo kiu estas desegnita por helpi vi homoj trovi kaj forigi cimojn.
Do se mi batis Run tie, estas atroz kvanto de teksto
ke vi vere neniam devas legi.
Ĝi estas esence distro el la prompto, kiu
Mi tuj batis Kontrolo-L ellitiĝi je la pinto.
Tiu estas la GDB prompto.
Se mi volas kuri ĉi programo nun, kiel tiu malgranda lertaĵoj tukon sur hodiaŭa
slide sugestas, Run estas la unua ordonas, ke ni intencis enkonduki.
Kaj mi simple tuj tajpi kuri tien ene de GDB,
kaj ja ĝi kuris mia programo.
Nun tie estas kelkaj pliaj eliroj de la ekrano kiel tiu,
sed tio GDB nur esti anal kaj diri al ni, kio okazas.
Vi ne vere devi maltrankviligi pri tiuj detaloj nun.
Sed kio estas vere malvarmeta pri GDB, se mi tion again--
Kontrolo-L demetas la screen-- lasu min iri antaŭen kaj tipon "rompi ĉefa," tio,
kiam mi batis Enter, fiksante kio estas nomata ripozon punkto je noswap.c,
linio 16, kiu estas kie GDB eltrovis mian programon reale
estas, mia funkcio estas.
Ĉi ni ignoras nun sed jen la adreso
memore specife de tiu funkcio.
Do nun, kiam mi tajpas kuri, rimarki kio estas malvarma tie.
Mia programo rompas la linion mi sciigis GDB paŭzi ekzekuto ĉe.
Do mi ne devas nun ŝanĝas mian kodon, aldoni iun printf'S recompilar ĝin, rerun
tio, ŝanĝi, aldoni iujn printf'S savi gxin recompilar ĝin, ruli ĝin.
Mi povas apenaŭ marŝi tra mia programo paŝon post paŝo por paŝo en homaj rapido,
ne Intel-ene speco de rapido.
>> Do nun rimarki tiu linio aperas tie, kaj se mi reirus
al mia programo en gedit, rimarki, ke estas reale
la unua linio de kodo.
Ekzistas linio 16 en gedit.
Ekzistas linio 16 ene GDB, kaj eĉ kvankam tiu nigra kaj blanka interfaco
ne estas preskaŭ tiel uzanto amika, tio signifas
tiu linio 16 ne estis ekzekutita ankoraŭ, sed ĝi temas pri esti.
Do ja se mi tajpas print x, ne printf, nur presita x,
Mi alvenas iun blufa valoro tie de nulo, ĉar x ne inicializado ankoraŭ.
Do mi tuj tajpi sekva, aux, se vi volas esti fantazio, simple n por proksima.
Sed kiam mi tajpas proksima eniras, nun rimarki movas sur linio 17.
Do logike, se mi ekzekutita linio 16 kaj mi nun tajpas print x,
kion mi vidas?
Unu.
>> Kaj nun jen estas rekoni konfuza.
$ 2 estas nur ornama metodo, se vi volas aludi al tiu valoro poste,
vi povas diri "dolaro subskribi du."
Estas kvazaŭ reen referenco.
Sed nuntempe, nur ignoras ĝin.
Kio estas interesa estas kio estas dekstre de la egala signo.
Kaj nun se mi tajpas apud denove kaj presita y mi devus vidi 2.
Mi povas ankaŭ nun presi x denove, kaj sincere,
se mi ricevas iom konfuzita kiel al kie Mi estas, mi povas tajpi listo por lerta
kaj simple vidi iujn kuntekston ĉirkaŭ la punkto mi efektive ĉe.
Kaj nun mi povas tajpi proksima, kaj tie x estas 1.
Nun mi tajpas proksima.
Ho, y estas 2.
Kaj cetere, estas malklara, ĉar GDB eligo
estas commingled kun miaj propraj eligo.
Sed se vi rememoru, per ekrigardante reen en via kodo
aŭ metinte ĝin flanko ĉe flanko eble, vi
vidi ke vere mi estas nur tretante tra mia programo.
>> Sed rimarki kion okazas poste, laŭvorte.
Jen linio 22.
Permesu al mi iri ĝin, per tio movante sur 23 kaj se mi presi x Nun ankoraŭ unu.
Kaj se mi presas y nun ankoraŭ unu.
Do tio ne estas utila ekzerco.
Do ni refari tion.
Lasu min reiri al la supro kaj tipon run denove.
Kaj ĝin dirante la programon ke tio esti elpurigita
komencis jam, komenciĝis ekde la komenco.
Jes, ni faru tion denove.
Kaj ĉi tiu fojo ni fari, proksima, sekvanta, sekva, sekvanta,
sed nun la aĵoj interesa.
Nun mi volas treti en swap, do mi ne tajpas proksima.
Mi tajpas paŝo, kaj nun rimarki saltis al mi noswap.c linio 33.
Se mi iros al gedit, kio estas linio 33?
Tio estas la unua reala linio de kodo ene de swap.
Kio estas agrabla, ĉar nun mi povas ia poke ĉirkaŭ kaj akiri scivola
pri kio okazas vere en tie.
Lasu min presi tmp.
Halt.
Kial tmp havi iun freneza, blufa rubo valoron?
Publikon: ĝi ne estis inicializado.
SPEAKER 1: ĝi ne estis inicializado.
Kaj efektive, kiam vi kuros programo, vi donas tutan faskon da memoro
de la mastruma sistemo, sed vi ne inicializado ajn valoroj
tiel ajn bitojn vi vidante tie, eĉ se ĝi estas
ĉi freneza granda negativa nombron, simple signifas
ke tiuj estas la restaĵoj de iu antaŭa uzado de tiu RAM,
kvankam mi ne mi bezonis ankoraŭ.
Do nun mi tuj iros antaŭen kaj tipon sekvanta, kaj se mi nun tajpas print tmp,
kion mi vidas?
Sendepende de la valoro de estis, a estas la unua argumento, nur
kiel x estis la unua afero aprobotaj en,
tial a kaj x devus esti la sama, tiel presi tmp devus presi mi unu.
>> Do, kion vi vidos en problemo aro tri estas lernilo de varoj en GDB,
sed rimarkas ke tiu estas la komenco el rigardu ilon kiu volas reale
helpi vin solvi problemoj tiom pli efike.
Kio ni estas finfine faros merkrede
estas komenci senŝeligi reen kelkaj tavoloj kaj forigi iujn trejnado radoj.
Ke afero nomata ŝnuro ke ni uzis por iu tempo,
Ni tuj malrapide oferportos for de vi kaj komencu paroli pri
ion pli esotéricamente konata kiel char *,
sed ni tuj faros ĉi bela kaj milde ĉe unua, kvankam punteros,
kiam ili estas nomitaj, povas fari iu tre malbonaj aĵoj se trouzita,
rigardante iom Claymation de nia amiko Noĉjo Parlante de Stanford
Universitato, instruisto en komputilo scienco kiu kunmetis ĉi antaŭvido
de kio estas por veni ĉi merkredo.
>> [VIDEO Playback]
-Hey, Binky.
Vekiĝi.
Estas tempo por montrilo amuza.
>> -Kio Estas tio?
Lernu pri punteros?
Ho, Goody!
[FINO VIDEO Playback]
SPEAKER 1: Tio atendas vin merkredon.
Ni vidos vin poste.
[VIDEO Playback]
-Kaj Nun Deep Pensoj, per Daven Farnham.
>> -Why Ni lernas C?
Kial ne A +?
>> [Ridado]
>> [FINO VIDEO Playback]