[REPRODUCCIÓ DE MÚSICA] 

ALTAVEU 1: Molt bé, això és CS50, i aquest és el començament de la setmana quatre, i com vostè pot haver sentit o llegir, el món ha estat arribant al final. El anar per tot l'internet ha estat el coneixement i la consciència d'un error en un programa, una llenguatge de programació anomenat Bash. Aquest ha estat marcat meravellosament com Shellshock, o la porta Bash, però articles com aquests no han estat infreqüents. I, de fet, molts d'ells porten records posteriors de Heartbleed, que vostè pot haver notat en el comprimir la primavera passada, que ser igualment bastant dramàtic. Ara, per a aquells de vostès aquí avui, quants de vostès tenen, encara que no entén el que és tot sobre, sentit parlar de Shellshock? Molt bé, i quants de vostès tenir equips que són vulnerables? Acceptar, ha d'haver molt, molt més mans fins ara, per raons que veurem. 

Fem una ullada al que estat succeint en els mitjans de comunicació i després explicar-ho una mica aquí per a nosaltres tècnicament. 

ALTAVEU 2: Els experts en seguretat tenen advertit que una greu falla podria estar a punt d'afectar a centenars de milions d'usuaris d'Internet del món. Llavors, què és exactament l'error que ha estat anomenat Shellshock, i el que fa? Bé, Shellshock també es coneix com el Bug Bash, el programari que explota. Els hackers utilitzen virus per escanejar vulnerables sistemes que Linux i Unix sistemes operatius i després infectar ells. Bash és un shell de línia d'ordres. Això permet que els usuaris dels comandos d'edició per llançar programes i característiques en el programari per la introducció de text. S'utilitza normalment pels programadors, i no ha d'estar obert a la resta del món, encara Shellshock canvia això. 

Bé, worringly, alguns analistes adverteixen que podria ser una amenaça més gran, perquè Shellshock permet completa el control d'una màquina infectada, mentre que només es permet Heartbleed hackers per espiar en ordinadors. És tan greu, és ha classificat octubre 1 sobre 10 de la gravetat per la National Base de dades de vulnerabilitats. 2.3 de tots els servidors web estan en risc, incloent alguns ordinadors Mac. Bé, assegureu-vos que apedaçar els seus sistemes ara. Qualsevol que allotjar un lloc web en funcionament els sistemes operatius afectats ha de prendre mesures tan aviat com sigui possible. Qualsevol que pugui permetre ha de mirar a la seva aplicació de monitorització i web tallafocs a tenir en compte qualsevol atac. ALTAVEU 3: El pitjor que podria passar és que algú escriuria codi que aniria automàticament i escanejar internet i afectaria tots aquests equips. I una vegada que ho fan, així, el pitjor que podien fer s'acaba d'esborrar tot, o tancar els llocs de sota. Així que podríem veure el dany des d'aquest punt de vista, on hauríem persones malicioses que acaba de decidir a causar estralls portant sistemes avall o eliminar arxius, i coses com aquestes. ALTAVEU 2: Alguns diuen que aquesta és una de les més difícils de mesurar errors en anys, i que pot portar setmanes o fins i tot mesos per determinar el seu impacte final. 

ALTAVEU 1: Així que tot això és cert, però el curiós és que gairebé tots de les imatges que acabes de veure, excepte potser el teclat, no té res a veure amb l'error absolut. Servidors i filferros i així successivament, És una mena de tangencialment relacionat, però en el fons és en realitat bastant familiaritzat el que està passant aquí. De fet, deixa anar a nostre aparell CS50. Déjame anar per davant i maximitzar la finestra de terminal aquí. I vostès han estat utilitzant aquest, o la versió incorporada de la mateixa, en gedit per escriure programes, escriure ordres, i així successivament, i això és en realitat, i té estat durant setmanes, Bash, B-A-S-H. Aquest és el Bourne-again shell, que és només una forma elegant de dir, aquest és un programa que té un parpelleig ràpid, eficaç, que se senti allà esperant per a l'entrada per a vostè. I és la comanda interfície de línia a través del qual que vostès han estat executant ordres i en última instància, la compilació i després corrent programes. 

Però Bash és també una programació idioma en el següent sentit. Vostè sap que hi ha ordres com cd i ls i també Clang i altres, però vostè pot definir els seus propis comandaments mitjançant la implementació d'ells en Bash. Ara no anem a entrar en gran detall com per colpejar el llenguatge de programació, però Sabem, per exemple, que en aquest moment, no hi ha ordre anomenat "hola." Per tant, es pot trobar a dos paquets. No està instal · lat en el meu equip. Pregunti al seu administrador. Però si jo vull que hi hagi un programa anomenat "hola" en Bash o en el meu ràpida, De fet, puc utilitzar la sintaxi que és absolutament com C. No és exactament el mateix, però es veu bastant similar a un funció, encara que falten alguns detalls. Res sembla succeir, però ara si escric "hola" en realitat es pot escriure una programa, no en C, no en Java, no en una altra programació idioma, però en si Bash. 

Ara la clau aquí és que vaig escriure el nomeno jo volia donar a aquest nou ordre, i els parèntesis són també simbòlic que això sigui una funció. Com acotació al marge, també es pot fer la diversió coses, i de fet, fins i tot en Mac OS, aquest és un programa que es diu Terminal. Ve integrat en qualsevol de equip que té un Mac en aquesta sala, i es poden fer coses similars a Mac OS, però es pot anar més enllà d'això. I això és una mica tangencial, però és bastant divertit. Em vaig recordar d'aquest matí, en pensar en això, d'un petit joc que solia jugar amb un dels ex TFS del CS50 mitjançant el qual qualsevol moment anava a allunyar-se el seu teclat amb la seva pantalla desbloquejat, M'agradaria executar una ordre així- "saludar". I ara ja que tornava al seu teclat després vaig netejar la pantalla i s'asseia, tractar de fer una mica de treball, llistar el contingut del seu directory-- 

[AUDIO REPRODUCCIÓ] 

-Hello. Hola. 

ALTAVEU 1: Així que, per ser justos, que no era en realitat "hola." En general era una cosa més semblant a això-- [AUDIO REPRODUCCIÓ] -Beep. ALTAVEU 1: --que I would-- pel que el seu equip faria juro a ell en qualsevol moment que en realitat va seure al seu teclat. I molt aviat es va descobrir no deixar desbloquejat la seva pantalla. Però això suggereix que l'espècie divertit estúpid que pot tenir amb alguna cosa com Bash. Però és una mica més greu, sens dubte, que això. I de fet, aquest és un dels la majoria dels insectes perillosos i de llarga durada que realment ha colpejat el món global. Aquest error ha estat del voltant durant uns 20 anys, i seràs colpejat en tan sols un moment per la seva relativa simplicitat. 

Així que aquest és un representant digues que si posseir un Mac, literalment, en aquest moment quan vostè té la seva tapa oberta, pots provar a escriure en aquesta programa anomenat Terminal. Terminal està sota Aplicacions Utilities-- per una vegada, els usuaris de Windows no han de preocupar-se per això threat-- particular, però aquells de vostès amb Mac pot escriure això en una finestra com la que vaig a fer aquí, i si escriviu que en aquest programa anomenada Terminal, com faré ara, si vostè veu la paraula "vulnerable" l'equip és vulnerables a l'explotació. 

Ara, què significa en realitat? I això és cert una sintaxi força boig, però anem a almenys derramares alguns dels aspectes interessants. Així que hi ha una sintaxi que es veu una mica familiar, almenys des de C i la programació en general. Veig alguns parèntesis, punt i coma, claus, i tal, però resulta que aquest estupidesa aquí en groc és essencialment una funció això no fa res. Els mitjans de còlon no fan res, i la punt i coma significa deixar de fer res. Així a l'interior d'aquests claus, el fet que tinc una igual signar a l'esquerra, aquesta és essencialment la creació una ordre, o una variable, anomenada x, i assignant-li que poc groga de codi allà. Això podria ser alguna cosa així com "eco hola "o" dir bip "o alguna cosa similar a això. Però fixa't si els seus ulls passejar més a la dreta, hi ha més en aquesta línia de només el final d'aquest punt i coma. "Echo vulnerables", i després més enllà que hi ha encara més. Un altre punt i coma, -c festa:. 

Així que conte llarg, aquesta línia de codi és suficient per a obligar un equip que és vulnerables a fer alguna cosa que vostè vol que faci, perquè hi ha un error en el qual Bash encara Bash havia de deixar de línies de lectura de comandament de la dreta allà després del text groc, per a un 20-plus anys error d'edat, Bash ha estat en realitat la lectura més enllà d'aquest punt i coma i bastant molt fent el que se li diu. 

Quina és la implicació que en última instància? Que acabo de dir "fet hola" o "eco vulnerables" però el que si vostè va fer alguna cosa realment maliciosos, com rm-rf *, que potser no alguna vegada ha escrit abans, i, francament, és probable que no ha de massa aviat, perquè es pot fer una molt de mal amb ella. Per què? rm fa què, és clar? Elimina. * Significa què? Tots. Així que és una crida comodí, pel que significa esborrar tot en el directori actual. -r passa a significar recursiva, que vol dir que si el que estàs esborrant és un directori, i dins d'aquí és altres arxius i altres directoris, recursiva submergir-se en allà i esborrar tot això. I f és el pitjor de tots ells. Algú sap el que significa -f aquí? Força. Així forçar mitjans, fins i tot si això és una mala idea, fer-ho sense mi que va provocar per al seu posterior confirmació. Així que, ja saps, ens riem de això, però, francament, jo probablement escrigui això diverses vegades un dia, perquè la realitat és que és la manera més ràpida de suprimir un munt de coses. Però fins i tot he fet una mica de mal. 

Però si anés a enganyar a un ordinador en definir alguna variable estúpid o funció crida x, però després enganyar l'ordinador que executi més enllà dels límits d'aquesta funció, més enllà d'aquest punt i coma, que de fet podria enganyar a un ordinador en l'execució d'alguna cosa com rm-rf o la comanda Email o l'ordre Copia. Qualsevol cosa, literalment, li pot veure amb el ordinador, si es tracta de l'eliminació d'arxius, la creació d'arxius, enviament de correu brossa a algú, atacant a algun servidor de manera remota, si vostè pot expressar amb una ordre, pot enganyar a un ordinador perquè faci això. 

Ara el que és un exemple de com es pot fer això? Bé, hi ha un munt d'ordinadors al Bash internet en execució. Tots els usuaris de Mac ens estan entre ells. Una gran quantitat de servidors Linux es troben entre ells també, i servidors Unix. Finestres obté de nou relativament fora del ganxo llevat que hi hagi instal · lat programari especial. Ara un munt de servidors, per exemple, per executar servidors web, i de fet Linux és potser el més popular sistema operatiu perquè funcione a ordinadors a Internet que servir les pàgines web. Ara bé, com veurem més endavant en el semestre, quan s'envia una sol licitud de seva browser-- Chrome, Internet Explorer, whatever-- a un servidor remot, resulta que tot i que que acaba d'escriure www.example.com, el teu navegador enviant un missatge això és una mica més arcà, com aquest. 

Però noti alguna cosa estranya. Les dues primeres línies Jo mai he vist abans, però que no es veuen particularment mortal. Però noto el que jo he robat per a la tercera línia d'aquí. Si un intrús fora a enviar un missatge així des del seu ordinador a un Mac o vulnerable servidor Linux vulnerables, el curiós és que Bash, que ràpida mica simple comandament, és omnipresent i és sovint S'usa per executar essencialment el contingut d'un missatge que rep. I per aquesta lògica, es pot enganyar a un servidor web, per tant, enviant una cosa així User-Agent, que en general se suposa que és dir el Nom del teu navegador. User-Agent Crom, User-Agent Internet Explorer, Firefox User-Agent, aquest és només el navegador d' forma d'identificar-se a si mateix. Però si un dels dolents molt intel · ligentment diu, mm-mm, estic No diré el que el meu navegador és, Estic en comptes d'anar a fer-li arribar aquesta El críptic d'aspecte amb un rm-rf * En el mateix, que, literalment, pot enganyar a un servidor web vulnerable a Internet perquè executi exactament això en allà per esborrar tots els arxius. I, francament, això no és fins i tot la pitjor part. Vostè pot fer qualsevol cosa. Vostè podria començar una distribuïda atac de denegació de servei si va enviar aquest missatge a raïms sencers de servidors web i després van tenir tots ells descendeixen, per exemple, en servidors Harvard.edu, i es pot ordenar d'explosió els diables d'ells per un tràfic de xarxa que desencadenada en contra d'aquest noi dolent. 

Per tant, conte llarg, gairebé tots en aquesta sala que és propietari d'un Mac és vulnerable a aquest. El costat positiu és que a menys que siguis executar un servidor web en el seu ordinador portàtil, i, llevat que hi hagi configurat en realitat per permetre que alguna cosa així com SSH en ell, estàs realment segur. És vulnerable, però no és un tractant d'entrar al seu ordinador portàtil, així que vostè pot ordenar d'explicar. No obstant això, Apple aviat ser l'actualització d'una solució per a aquest. El món de Linux ja ha llançat una sèrie de correccions per Fedora i Ubuntu i altres versions de Linux, i de fet si executa l'actualització 50 en l'aparell, encara que això també serà actualitzada i corregida. Però això tampoc té estat realment vulnerable, perquè a menys que vostè té vanament amb l'aparell i va fer el seu portàtil públicament accessibles a Internet, que no és per defecte, que hi hagi en realitat estat bé perquè de tallafocs i altres tècniques. 

Però és un exemple extrem d'un error que hem viscut per per, literalment, 20 anys, i qui sap si algú tot aquest temps s'ha sabut d'ella? I de fet, aquesta és una de els reptes fonamentals que veurem més endavant en el semestre per la seguretat, és que igual que en el món real, els bons són a la desavantatge. Per mantenir els nois dolents, hem de assegurar-se que cada porta està tancada, que cada finestra és segur, que cada punt d'entrada en una llar és segur per mantenir els nois dolents. Però el que fa el dolent de la pel · lícula ha de fer per comprometre realment casa i robar de vostè? Ell o ella només ha de trobar un desbloquejat porta, una finestra trencada o alguna cosa en aquest sentit, i és la el mateix a la seguretat informàtica. Podem escriure a milions de línies de codi de programació i gastar centenars o milers d'hores tractant d'aconseguir correcte, però si ho fan només una error en la correcció, vostè pot posar tot el sistema i de fet, en aquest cas, la totalitat d'internet i el món en risc. 

Així que si voleu aprendre més sobre això, aneu a aquesta URL aquí. No hi ha necessitat d'una acció aquesta nit llevat que estigui entre els més còmodes que han estat la gestió de la seva pròpia web servidor, en aquest cas vostè ha, de fet, actualitzar el programari. 

I això també és el títol de un discurs, i ara un paper, que ens hem vinculat a la la pàgina web del curs per avui. Va ser per un company anomenat Ken Thompson, qui va ser l'acceptació d'un molt famós premi en ciències de la computació, i ell va donar aquest discurs alguns anys fa, essencialment sobre el mateix tema. La gent que fa la pregunta, Si realment confiança, en última instància, la programari que t'han donat? Per exemple, tots tenim estat escrivint programes, i hem estat recopilant amb Clang. I al seu coneixement, has escrit qualsevol programa de CS50 on hi ha una porta del darrere de tipus, hi ha una manera que un tipus dolent, si s'executa el programa, podria fer-se càrrec del seu equip? Probablement no, oi? Mario i cobdiciós, i Crèdit. Aquests són tots els programes bastant petits. Vostè hauria de ser bastant malament si en realitat fet tot l'equip sigui vulnerable després d'escriure 10 o 20 línies de codi, o almenys conscient d'alguns de les implicacions de seguretat. Ara dic que en to de burla, però anem a veure avui i aquesta setmana és en realitat molt, molt fàcil a ser dolent i fer encara programes curts vulnerables. 

Però, per ara, almenys, adonar- que la pregunta que es fa aquí està a punt Clang en un compilador. Per què hem estat confiant en Clang durant els últims dos o tres setmanes? Qui pot dir que qui va escriure Clang no tenia un "si" condició en la que hi ha que essencialment s'injecta alguns zeros i els en cada programa es compila això seria deixar que ell o ella l'accés quan l'equip està adormit i la seva tapa del portàtil està obert i l'equip s'executa? ¿Cert? Tenim aquest tipus de sistema d'honor dret ara on confiem que Clang és de fiar. Vostè confia que l'aparell és de fiar. Vostè confia que, literalment, tots els programes al teu Mac o PC és digne de confiança. I com aquest simple error suggereix, encara que no és maliciós, això no és absolutament probable que sigui el cas. 

Així que vostè ha de tenir por com l'infern. Francament, no hi senzill solució a aquest altre que una espècie de consciència social de la complexitat cada vegada més gran que estem construint a la part superior dels nostres sistemes informàtics, i com cada vegada més vulnerables podríem molt bé ser. 

Ara, amb això dit, Breakout. Així Breakout és problema estableix tres, i Breakout és un joc d'abans que es pot recordar, però per a nosaltres en un problema establert tres, que ens permet prendre les coses tornin a un nivell superior de manera que quan estem escrivint programes, fins i tot en una finestra de terminal com aquest, en realitat podem executar, en última instància, no els programes de gràfics a diferència d'aquells que vam tenir en l'accés a les ratllades. Així que aquesta és la dècada dels funcionaris implementació de Breakout, que és precisament aquesta trencar maons joc, que es mou la pala cap enrere endavant i cap enrere, i colpejar la bola contra els maons de colors fins a la part superior. Així que això ens està portant espècie de tornada a on hem estat capaços de ser molt ràpid amb Scratch, i ara amb C, la implementació de la nostra pròpia interfícies gràfiques d'usuari. 

Però més que això, aquest conjunt de problemes representa la primera en la que estem donant que un munt de codi. I, de fet, els porto explícita atenció a això, perquè tot per als menys confortable, aquest problema configurat, almenys a primera vista, es va a sentir com hem portat a un nivell superior. Com que els hem donat, per alguns de la cerca i classificació dels problemes en el conjunt de processadors, un munt de codi que escrivim, i un parell de comentaris que diuen "fer" on vostè ha de omplir els espais en blanc. Així que no massa por, però que és la primera vegada li estem lliurant codi que vostè necessita llegir primer, entendre, i després afegir a i completar-lo. 

I després, amb Breakout, farem el mateix, donant-li unes poques dotzenes més línies de codi que, francament, li donarà una gran part del marc per el joc, però aturar- de l'aplicació dels maons i la pilota i la paleta, però sí implementem algunes altres característiques. I fins i tot que, a primera vista, de nou, especialment si menys còmode, podria semblar especialment difícil i Creus que hi ha tantes noves funcions que necessita per embolicar la seva ment voltant, i això és veritat. Però tingui en compte, és absolutament com esgarrapades. El més probable és que no ha utilitzat totes les peces del trencaclosques en zero. El més probable és que no et importava per embolicar la seva ment al voltant de tots ells perquè tot el que va fer ser un ràpida mirada per comprendre, oh, això és el que puc fer amb aquesta peça del trencaclosques. I de fet, en conjunt de problemes 3 spec, anem a assenyalar que en la documentació que presentar a algunes funcions noves, i en última instància la programació construccions que utilitzi. Condicions, bucles, variables i funcions serà idèntic al el que hem vist fins ara. 

Així que de fet, el que donarem vostè és un codi d'exemple que li permet crear una finestra que no es veu a diferència d'aquest, i en última instància, convertir-lo en alguna cosa com això. Així que pren avantatge d'CS50, discutir hores d'oficina i més, i consolar-se amb el fet que la quantitat de codi que ha d'escriure en realitat no és tant. El primer repte és només per aclimatar vostè mateix a algun codi que hem escrit. 

Qualsevol pregunta sobre pset3, Shellshock, o d'una altra manera? 

AUDIÈNCIA: Semblava que anar a través amb Breakout que el codi és gairebé un estil orientat a objectes, però vaig pensar que era un C programa orientat a objectes. ALTAVEU 1: Una excel · lent pregunta. Així que en mirar a través de la codi de distribució, el codi escrivim per pset3, Per a aquells familiaritzats, es sembla que és un poc orientat a objectes. Resposta curta és, ho és. És una aproximació de com es podria fer codi orientat a objectes utilitzant un llenguatge com C, però és encara en última instància de procediment. No hi ha mètodes dins d' les variables, com veuràs. Però recorda que. I veurem que la funció de nou quan arribem a PHP i JavaScript cap al final del semestre. Però per ara, pensar-hi com una pista del que està per venir. Bona pregunta. Bé. Així merge sort era com coses esquerra última vegada. I fusionar espècie estava fresc a la sentit que era molt més ràpid, almenys sobre la base de les proves superficials que vam fer la setmana passada, que, per exemple, la bombolla espècie, ordenament per selecció, ordenació per inserció. I el que era massa net és només com succinta i netament pots expressar-ho. I el que vam dir que era un superior amb destinació en el temps d'execució de la fusió Ordenar? Sí? 

AUDIÈNCIA: n log n? 

ALTAVEU 1: n log n, dret. n log n. I anem a tornar al que realment significa o d'on ve, però això era millor que el que el temps de funcionament que vam veure durant la bombolla selecció i ordenació per inserció? Així que n al quadrat. n al quadrat és més gran que això, i encara que no és prou obvi, sap que log n és menor que n, així que si vostè ho fa n vegades una mica menor que n, que serà menor que n al quadrat. És una mica d'intuïció allà. Però paguem un preu per això. Era més ràpid, però un tema que va començar emergeixi la setmana passada era aquest sacrifici. Tinc un millor rendiment pel que fa a temps, però el que Per què he de passar per un altre part, amb la finalitat d'aconseguir això? 

AUDIÈNCIA: Memòria. ALTAVEU 1: Digues-ho de nou? AUDIÈNCIA: Memòria. ALTAVEU 1: Memòria, o l'espai de forma més general. I no era súper òbvia amb els nostres éssers humans, però recordar que els nostres voluntaris van anar donant un pas endavant i pas a pas cap enrere com si hi ha una matriu aquí, i com si hi una segona matriu que aquí que podrien utilitzar, perquè ens algun lloc necessària per fusionar aquestes persones. No podíem canviar al seu lloc. Així fusionar espècie de palanquejament és més espai, la qual cosa que no era necessari amb els altres algoritmes, però l'avantatge és que és molt més ràpid. I, francament, a l'espai del món real aquests RAM dies--, disc dur espai-- és relativament barat, i pel que és no és necessàriament una cosa dolenta. 

Així que anem a fer una ullada ràpida, una mica més metòdicament, en el que vam fer i per què vam dir que va ser n log n. Així que aquí hi ha els vuit nombres i la vuit voluntaris que tenien l'última vegada. I el primer que Merge Ordenar ens va dir que fer era què? AUDIÈNCIA: Divideix en dues. ALTAVEU 1: Digues-ho de nou? AUDIÈNCIA: Divideix en dues. ALTAVEU 1: Dividir en dos, dreta. Això recorda molt a la guia telefònica, de divisió i conquerir de manera més general. Així que busquem en la meitat esquerra. I llavors un cop vam dir, una espècie la meitat esquerra dels elements, ¿Què vam fer juntament diem? Ordenar la meitat esquerra de l'esquerra la meitat, la qual cosa ens va permetre, després de dividir en dos, centrar en quatre-dos. 

Com ordenar una llista ara, en groc, de mida 2, utilitzant Combinar Ordenar? Bé dividir per la meitat, i ordenar la meitat esquerra. I aquest era el lloc on les coses es va posar una mica breument estúpid. Com ordenar una llista que és de mida d'un, com aquest número quatre en aquesta llista? Està ordenada. Ha acabat. 

Però llavors, ¿com ordenar una llista de mida d'un quan és el número dos? Bé, el mateix, però ara el que va ser la tercer i el pas clau en Merge Ordenar? Calia combinar l'esquerra la meitat i la meitat dreta. I una vegada que ho vam fer, ens vam mirar a les quatre, ens fixem en dos. Decidim bé, òbviament ha dos que passi primer, així que vam posar dos al seu lloc, seguit per quatre. I ara has de tipus de rebobinat, i això és una espècie de característica d'un algorisme com Merge Ordena, rebobinar en la memòria. Quina va ser la següent línia de la història? Què hauria d'estar centrat en el proper? La meitat dreta de l'esquerra mitjana, que és de sis-vuit. 

Així que permetin-me simplement un pas a través d'aquesta sense picar el punt massa. Sis i vuit, a continuació, sis és ordenats, vuit s'ordena. Combinar junts d'aquesta manera, i ara el proper gran pas està, per descomptat, ordenar la meitat dreta des el primer pas d'aquest algorisme. Així que ens centrem en un, tres, set, cinc. Després ens centrem en la meitat esquerra. La meitat esquerra que, la meitat dreta això i, a continuació, es fonen en un i tres. Llavors la meitat dreta, després a l'esquerra la meitat d'ell, llavors la meitat dreta de la mateixa. Combinar en, i ara el que queda pas? Combinar la gran meitat esquerra i la gran meitat dreta, de manera que un es posa allà, després dos, després tres, després quatre, després cinc, després sis, després set, després vuit. 

Així que ara per què s'està revelant en última instància, especialment si n i logaritmes més en general, més aviat escapar, almenys en els últims temps? Bé, fixa't en l'altura d'aquesta cosa. Vam tenir vuit elements, i ens dividit per dos, per dos, per dos. Així que la base ingressi dues de les vuit ens dóna 3. I confia en mi que si una mica nebulós sobre això. Però el registre de base de dos de vuit és tres, pel que hem fet tres capes de fusió. I quan ens fusionem elements, el nombre d'elements ens veiem en cadascuna de les files? Un total de n, oi? A causa de la fusió de la fila superior, tot i que ho vam fer a poc a poc, que en última instància, toquem cada número una vegada. I a la segona fila, a fusionar aquestes llistes de mida 2, vam haver de tocar cada element una vegada. I llavors aquí realment clarament a l'última fila, vam haver de tocar cada un dels elements d'una vegada, però només una vegada, així que en aquest document es troba, llavors, el nostre n log n. 

I ara només per fer les coses una mica més formal per a un moment, si estaven ara a analitzar aquest en una mena de major nivell i tractar de decidir, així com podries anar en expressar el temps d'execució d'aquest algorisme només mirant a ella i no utilitzant un exemple artificiós? Bé, quant de temps li diries a pas com aquest en groc prendria, si n <2 volta? Aquesta és una gran O de què? Així que jo estic veient un, així que un pas, potser dos passos perquè és si i després tornar, però és constant de temps, oi? Així que vam dir O (1), i això és com vaig a expressar això. T, acaba de ser temps d'execució. n és la mida de l'entrada, així que T (n), només una forma elegant de dir el funcionament temps d'entrada donat de grandària n serà de l'ordre de constant de temps, a O (1). 

Però d'altra banda, ¿què passa amb això? Com expressar la moment d'aquesta línia groga corrent? T ¿de què? Pot tipus de trampes aquí i respondre a la meva pregunta de forma cíclica. Així que si el temps de funcionament en en general ens limitem a dir és T (n). I ara vostè està mena de batea aquí i dient, bé, només ordenar la meitat esquerra, i després ordenar la meitat dreta. Com podríem representar simbòlicament el temps d'execució d'aquesta línia groga? T ¿de què? Quina és la mida de l'entrada? n més de dos. Per què no m'acaba de dir això? I llavors aquest és un altre T (n / 2) i després de nou, si puc combinar dues meitats ordenades, quants elements vaig a haver de tocar total de? n. Així que puc expressar això, només per ser una mica de fantasia, com el temps de funcionament en general. T (n) és el temps de durada de T (n / 2), més de T (n / 2), la meitat esquerra i la meitat dreta, a més d'O (n), que és probablement n passos, però potser, si estic fent servir dos dits, que és el doble que passos, però és lineal. És cert nombre de passos això és un factor de n, pel que podríem expressar això com aquesta. I aquí és on ara anem a Punt a la part posterior del nostre llibre de text de matemàtiques de l'escola secundària estem que la recurrència en última instància acaba igualant això, n log n vegades, si vostè fa realment fora els càlculs de manera més formal. 

Així que això és només dos punts de vista. Una numèricament amb un dur amb codi d'exemple representatiu amb vuit números i una més cop d'ull general a la forma en què vam arribar allà. Però el que és realment interessant aquí és, de nou, aquesta noció de ciclisme. No estic fent servir per bucles. Sóc una mena de definició alguna cosa en termes de si mateix, no només amb aquesta funció matemàtica, sinó també en termes d'aquest pseudo codi. Aquesta pseudo codi és recursiva en què dos de les seves línies està essencialment dient que es vagi utilitzi a si mateix per resoldre un menor problema de mida més petita, i després una altra vegada i una altra i una altra vegada fins que reduir gradualment cap a aquest anomenat cas base. 

Així que anem a dibuixar una realitat més convincent per portar de la següent manera. Déjame anar a gedit i prenc un veure algunes de codi font actual, en particular, aquest exemple aquí. Sigma 0, que aparentment afegeix els números de l'u al n. Així que anem a veure el que és familiar i desconegut aquí. En primer lloc tenim un parell de inclou, així que res de nou. Prototype. Estic una mica confusa en això després de pocs dies, però ho vam dir 1 prototip d'una funció és? AUDIÈNCIA: [inaudible]. ALTAVEU 1: Què és això? AUDIÈNCIA: Anunciem ella. ALTAVEU 1: Anunciem ella. Així que vostè està ensenyant Clang, hey, no l'aplicació real d'això encara, però en algun lloc d'aquest arxiu, presumiblement, serà una funció anomenada què? Sigma. I això és només una promesa que que tindrà aquest aspecte. Va a prendre un sencer com Entrada-- i puc ser més explícit i dir int n --i és va a tornar un int, però mig punt i coma, mm, arribaré al voltant de a la implementació d'aquest una mica més tard. Una vegada més, Clang és tonto. Només va a saber el que li dius que a dalt a baix, així que hem de donar almenys és un indici del que està per venir. 

Ara donem una ullada a principal aquí. Anem a desplaçar-se fins aquí i veure el principal està fent. No és que a llarg d'una funció, i de fet, el constructe aquí és familiar. Declaro una variable n, i després Em molesten a l'usuari una vegada i una altra per a un enter positiu utilitzant getInt, i única sortida d'aquest bucle una vegada que l'usuari ha complert. Do While, que hem utilitzat per molestar a l'usuari d'aquesta manera. Ara això és interessant. Declaro 1 int anomenada "resposta". Assigno que el valor de retorn d'una funció anomenada "sigma". No sé el que això fa encara, però Recordo que declara que fa un moment. I llavors jo estic passant al valor que l'usuari va escriure en, n, i després informe la resposta. Bé, anem a retrocedir només per un moment. Seguirem endavant en aquest directori, fan sigma 0, i en realitat executar aquest programa i veure què passa. Així que si segueixo endavant i córrer aquest programa, ./sigma-0, i escric en un positiu sencer com dos, Sigma, com el símbol grec ho indica, és només va a sumar tots els números de l' zero en un màxim de dos. Així 0 més 1 més 2. Així que espero que aquest ha donar-me 3. Això és tot el que està fent. I de la mateixa manera, si se m'acaba el missatge i li dono el número tres, això és 3 més 2, pel que és 5, més 1 em hauria de donar juny. I després, si em poso molt boig i comença a escriure en nombres més grans, em hauria de donar sumes cada vegada més grans. Així que això és tot. 

Llavors, què sigma sembla? Bé, és bastant senzill. És la forma en què podríem haver implementat això per a l'últim parell de setmanes. "Int" serà el tipus de retorn. Sigma és el nom, i es necessita una variable m en lloc de n. Canviaré que a sobre de la tapa. Llavors això és només una prova de seny. Veurem per què en un moment. Ara declaro altra variable, suma, inicialitzar a zero. Llavors tinc aquest bucle For iteració, pel que sembla, per a major claredat, des de i = 1 fins a en un = m, que és qualsevol que sigui l'usuari va escriure en, i després em incrementar la suma d'aquesta manera. I a continuació, tornar la suma. 

Així que un parell de preguntes. Un, em diuen al meu comentari que aquesta evita el risc d'un bucle infinit. Per què hauria de passar en un nombre negatiu induir, potencialment, un bucle infinit? 

AUDIÈNCIA: Vostè mai arribarà a m. 

ALTAVEU 1: Mai arribar m. Però m es passa, així que anem a considerar un exemple senzill. Si m es passa pel usuari com un negatiu. Independentment de principal. Principal ens protegeix de això també, així que estic sol sent molt anal amb sigma també assegurar- que l'entrada no pot ser negatiu. Així que si m és negatiu, una mena de cosa negativa. ¿Què passarà? Bé, va a que aquest s'inicia a un, i després em serà menys d'o igual a m? 

Col·locar. Això fue-- no anem, anem a Nix aquesta història. Jo no vaig demanar aquesta pregunta, perquè el risc que al·ludeixo no passarà perquè i és sempre va ser major Acceptar què--, Em retracte de què es tracti. Okay. Anem a centrar-nos només en aquesta part aquí. Per què em declaro alguns fora del bucle? Avís sobre la línia 49 no tinc i declarada dins del bucle, però en línia 48 que he declarat alguns de fora. Sí. AUDIÈNCIA: [inaudible]. ALTAVEU 1: Segur. Així que, abans de res, jo per descomptat no ho faig voler declarar i inicialitzar suma a zero a l'interior de la bucle en cada iteració, perquè això aniria en contra de la claredat propòsit de resumir els números. M'agradaria mantenir el canvi el valor a zero. I també, el que és una altra més arcana raó d'aquesta mateixa decisió de disseny? Sí. 

AUDIÈNCIA: [inaudible]. ALTAVEU 1: Exactament. Vull accedir-hi fora del bucle massa en quina línia? En 53. I sobre la base de la nostra regla d'or des de fa un parell de conferències, variables que estan en l'àmbit, de veritat, a la claus que ells abasten. Així que si no declaro suma dins d'aquestes claus exteriors, Jo no ho puc fer servir en la línia 53. Dit d'una altra manera, si jo vaig declarar suma aquí, o fins i tot dins la Per bucle, no podia accedir-hi en el 53. La variable efectivament s'hauria anat. Així que un parell de raons allà. Però ara anem a tornar i veure què passa. Així sigma es diu. Se suma 1 més 2 o 1 més 2 més 3, i després retorna el valor, emmagatzema en resposta, i printf aquí és pel que estic veient a la pantalla. Així que això és el que anem a trucar a un procés iteratiu enfocament, on iteració només significa utilitzar un bucle. Un bucle For, un bucle while, un Do While bucle, simplement fer alguna cosa nova i una i altra vegada. 

Però sigma és una espècie de funció ordenada en que podria posar en pràctica de manera diferent. Què passa amb això, que només per ser una mena de fresc, permetin-me realment desfaig d'una gran quantitat de distracció perquè aquesta funció és realment molt simple. Anem a reduir gradualment cap avall just els seus quatre línies bàsiques i desfer-se de tota la comentaris i claus. Aquesta és una espècie de lucinant implementació alternativa. Està bé, potser no lucinant, però és una mica més sexy, d'acord, veure aquesta molt més succinta. Amb només quatre línies de codi, La primera vegada que tinc aquesta prova de seny. Si m és menor que o igual a zero, sigma no té sentit. Només se suposa que és en aquest cas per als nombres positius, així que només vaig a tornar zero arbitràriament de manera que almenys tenim alguns anomenat cas base. 

Però aquí hi ha la bellesa. La totalitat d'aquesta idea, afegint la números de l'1 al n, m, o en aquest cas, es pot fer per la classe de passar la pilota. Bé, quina és la suma d'1 a m? Bé, saps què? És el mateix que la suma de m més la suma d'1 m d'almenys 1. Doncs saps què? Què hi ha de sigma m almenys 1? Bé, si segueix aquest tipus de lògicament, és el mateix que m almenys 1 a més de sigma m almenys 2. Així que vostè pot tipus de sol-- això és com, si ets tractant de molestar a un amic i et fan una pregunta, que classe de respondre amb una pregunta, vostè pot tipus de mantenir fugir d'estudi. Però el que és clau és que si es manté fent la pregunta més i més petita i més petit, vostè és no demanar el que és sigma de n, el que és de sigma n, el que és sigma de n? Li estàs preguntant quin és sigma de n, el que és sigma n de menys 1, el que és de sigma n almenys 2? Eventualment la seva pregunta serà què? Què és la sigma d'un o zero, un valor molt petit, i tan aviat com es aconseguir que, al seu amic, no va a demanar la mateixa pregunta de nou, només direm, oh és zero. Hem acabat de jugar aquest tipus de joc cíclic estúpid. 

Així que la recursivitat és l'acte en la programació d'una funció que es fa dir. Aquest programa, quan es compila i s'executa, és es comportarà de la mateixa manera, però el que és clau és que a l'interior d'una funció anomenada sigma, hi ha una línia de codi en el qual que anomenem nosaltres mateixos, que normalment seria dolent. Per exemple, què passa si jo primer compilat aquesta, així que sigma-- fer sigma 1 ./sigma-1. Enter positiu, si us plau, 50 1275. Així que el que la funció sembla ser, basat en una prova, correcta. Però el que si em fa una mica perillós i eliminar l'anomenat cas base, i acabo de dir, bé, jo només estic fent això més complicat del que és. Anem a computar el sigma prenent m i després afegint en sigma de m menys un? Bé, què passarà aquí? Anem a allunyar. Anem a tornar a compilar el programa, guardar, tornar a compilar el programa, i llavors llest ./sigma-1 el zoom, introduir enter positiu favor, 50. Quants de vostès estan disposats a confessar a veure això? 

Okay. Així que això pot succeir per una sèrie de raons, i, francament, aquesta setmana estem a punt de donar-li més d'ells. Però en aquest cas, proveu per raonar cap enrere el que podria haver passat aquí? Decisió de segmentació, vam dir última temps, es refereix a un segment de memòria. Una cosa dolent ha passat. Però què era mecànicament que va sortir malament aquí per la meva retirada que l'anomenat cas base, on vaig tornar un valor codificat? Què creus que va sortir malament? Sí. 

AUDIÈNCIA: [inaudible]. ALTAVEU 1: Ah. Bona pregunta. Així que la mida del nombre que estava resumint posar tan gran que supera la mida de l'espai de memòria. Bona idea, però no fonamentalment causarà un accident. Això podria causar desbordament de sencers, on els bits només voltegen i després confonem 1 molt gran nombre com per un nombre negatiu, però que en si no va a causar un accident. Com que al final de l' dia 1 int és encara 32 bits. No va a robar accidentalment una mica 33a. Però un bon pensament. Sí. 

AUDIÈNCIA: [inaudible]. ALTAVEU 1: El mètode mai deixa de córrer, i vet aquí que es diu de nou i una i altra vegada i una altra i una altra vegada, i cap d' aquestes funcions cada vegada acabar perquè la seva única línia d' codi si mateixa diu una i una altra vegada i una altra vegada. I el que és realment passant aquí, i ara ens pot dibuixar aquest tipus d'il • lustracions. Déjame anar a un foto per un moment. Aquesta és una imatge, que eventualment donar cos a amb més detall, del que està passant dins de la memòria de l'equip. I resulta que en la part inferior d'aquesta imatge és una cosa que es diu la pila. Es tracta d'un tros de memòria, un tros de memòria RAM, això és només utilitzen qualsevol moment una funció és cridada. Cada vegada que, un programador, cridar a una funció, el sistema operatiu, com Mac OS, Windows, o Linux, agafa un grapat de bytes, potser un pocs kilobytes, potser pocs megabytes de la memòria, els lliura a vostè i, a continuació, li permet executa la seva funció utilitzant el variables que vostè necessita. I si després trucar a un altre la funció i l'altra funció, li dóna una altra llesca de memòria i una altra llesca de memòria. 

I de fet, si aquestes safates verds de Annenberg representar aquesta memòria, això és el que passa el primer vegada que es cridi a la funció sigma. És com posar una safata com aquesta en el que és inicialment una pila buida. Però llavors, si aquesta safata diu a si mateix, per així dir-ho, trucar a una altra instància de sigma, això és com preguntar el sistema operatiu, ooh, necessitarà una mica més de memòria, dóna'm això. I llavors s'apilen en la part superior. Però el que és clau aquí és que la primera safata està encara allà, perquè ell va invocar aquesta segona safata. Ara mentrestant, sigma diuen sigma, això és com demanar més memòria. Obté apilats per aquí. sigma cridar sigma, aquesta és una altra safata que aconsegueix apilats a aquí. I si segueixes fent això, finalment, una mena de mapa d'aquesta visual a aquesta carta, el que va a ocórrer amb la pila de safates? Es va a excedir la quantitat de memòria l'equip té. I tan aviat com aquesta safata verda excedeix la línia horitzontal per sobre de la pila i per sobre d'aquesta paraula munt, que anem a tornar en el futur, això és una mala cosa. El munt és una diferent segment de la memòria, i si deixes que aquests safates de pila i pila en, vostè va a superar el seu propi segment de la memòria, i un programa està de fet va a estavellar. 

Ara com un part, aquesta idea de la recursió, per tant, pot conduir a problemes clarament, però no és necessàriament una mala cosa. A causa de considerar, després d' tot, i potser com-- això pren algun temps acostumar- a --¿Com elegant o el simple que l'aplicació de sigma va ser. I no utilitzarem recursivitat gairebé res en CS50, però en CS51, i realment qualsevol classe on es manipulen estructures de dades com arbres o arbres de la família, que tenen certa jerarquia, és super, super útil. Ara, com un a part, de manera que vostè com a aspirants a científics de la computació estan familiaritzats amb alguns de Google bromes internes, si vostè va a Google i vostè mira cap amunt el que és la definició de, per exemple, la recursivitat, escriviu. Uh-huh. Com acotació al marge, em vaig aturar uns pocs. Això va ser com de 10 minuts de la dilació d'aquest matí. Si també Google "torta" avís inclinant el cap slightly-- i llavors aquest és potser més atroç de tots ja que algú va passar com el seu dia de l'aplicació d'aquesta alguns anys ago-- anem. Oh, espera-- això és un error. 

Així que s'executa en un dels majors llocs web del món són aquests estúpids petits ous de Pasqua. Probablement consumeixen una nombre no trivial de línies de codi només perquè puguem tenir petites coses divertides com aquestes. Però almenys ara vostè aconsegueix algunes d'aquestes bromes. 

Ara donem una ullada a alguns dels blanc es troba que hem estat dient en els últims temps, i començar a pelar algunes capes tècnicament de manera que vostè realment entén el que ha estat passant i es pot entendre algunes de les amenaces, com Shellshock, que Ara han començat a convertir-se en a l'avantguarda de tot el món de atenció, almenys en els mitjans de comunicació. Així que aquí és una funció molt simple que retorna res, el buit. El seu nom és d'intercanvi. Es necessita en dues variables i no torna res. Presa en ai b. Així que una demostració ràpida. Vam portar aquests. Pot ser que també prengui una mica trencar aquí per un moment i tenir una mica d'alguna cosa per beure. Si a algú no li importaria unir-se em fins aquí per un moment. Què tal si a la camisa marró? Anem amunt. Només la d'avui. Gràcies, però. Molt bé, i tenim ve que aquí? Quin és el teu nom? 

ALTAVEU 4: Laura. 

ALTAVEU 1: Laura. Anem amunt. Així que la Laura, molt simple desafiament d'avui. Encantat de conèixer jo. Bé. Així que tenim una mica de llet aquí i tenim una mica de suc de taronja per aquí i algunes tasses que ens pres d'Annenberg avui. 

ALTAVEU 4: Borrowed. ALTAVEU 1: I seguirà endavant i li donarà la meitat d'un got d'això. Bé. I li donarem la meitat un got de llet. Ah, i perquè pugui recordi com era això, Vaig recordar de portar això i en l'actualitat. Bé. Si no t'importa, anem a veure, ens pot posar-los en les seves pròpies ulleres si vols. Aquest serà el món des dels ulls de Laura. Bé. Així que el seu objectiu, li van donar dues tasses de líquid aquí, llet i suc de taronja, s'intercanviï els dos continguts de manera que el suc de taronja va a la tassa de llet i la llet entra en la tassa de suc de taronja. 

ALTAVEU 4: Tinc una altra tassa? ALTAVEU 1: Estic tan bo que ho preguntes, encara que hauria estat molt millor material d'arxiu si no haguessis preguntat. Però sí, podem oferir-li una tercera got que està buida, és clar. Bé. Així que canviar el contingut allà. Molt agradable. Molt bona. Estàs fent això amb molta cura. I el tercer pas. Bé. Excel · lent. Un gran aplaudiment seria bo per a Laura. Bé. Tenim un petit regal de comiat per a vostè, però vull aprofitar aquests. Moltes gràcies. Així, un exemple senzill, però, per demostrar que si ho fa voler canviar el contingut de dos contenidors, o anem a anomenar les variables, necessites una mica d'emmagatzematge temporal per organitzar un dels continguts en la que en realitat es pot fer el canvi. Així que de fet, el codi font aquí a C és representant d'exactament això. Si el suc de taronja era una i la llet era b, i volíem canviar els dos, vostè podria intentar alguna cosa creativa mitjançant l'abocament d'una a l'altra, però que probablement no ho faria acabar particularment bé. I pel que utilitzar una tassa tercera, anomenada que tmp, T-M-P per convenció, i posar el contingut del DO que, a continuació, intercanviar una tassa, a continuació, posar la DO en el tassa original, d'aquesta manera aconseguir, exactament com Laura va fer, el bescanvi. 

Així que farem exactament això. Déjame anar endavant i obrir fins a un exemple que és diu en realitat "no canviar, "perquè això no és com un simple fet com vostè podria pensar. Així que en aquest programa, observi que Estic usant stdio.h, el nostre vell amic. Tinc el prototip per swap allà dalt, que significa l'aplicació de probablement per sota, i anem a veure el que aquest principal programa farà per mi. La primera vegada que declaro int x un, i int i aconsegueix dues. Així que pensar en aquells com DO i llet, respectivament. I llavors jo només tinc un printf dient x és aquesta i i és això, perquè jo pugui veure visualment el que està passant. Després he printf reclamant que estic intercanviant els dos, i després imprimeixo 1 afirmen que estan intercanviats, i jo imprimeixo x i i una altra. Així que aquí a intercanvi és exactament el que va fer Laura, i és exactament el que vam veure en la pantalla fa un moment. 

Així que seguirem endavant i molt decebut. No ens swap, i executar sense swap, fer zoom sobre la sortida d'aquí. Introduïu x és 1, i és 2, intercanviant intercanviat. x és encara 1, i i és encara 2. Així que, encara que, francament, això sembla exactament igual, encara que de forma més tècnica, Laura ho va fer, no sembla funcionar. Llavors per què és això? Bé, resulta que quan escrivim un programa com aquest que té tant principal, lloc de relleu aquí, i després una altra funció, a canvi, ressaltat aquí, la qual cosa que crida, el món es veu una mica d'alguna cosa com aquestes safates fa un moment. Quan principal primer es torna a cridar, això és com preguntar sistema operatiu per una mica de memòria per a qualsevol local de variables com x i i que té principal, i acaben aquí. Però si les trucades principals d'intercanvi, i principal passa a intercanviar dos arguments, a i b, suc de taronja i la llet, que no és com lliurant-li el suc de taronja i la llet a Laura. Què fa un ordinador, és passa còpies del suc de taronja i còpies de la llet a Laura, pel que el que és en última instància dins d'aquesta safata és el valor d'un i dos, o DO i llet, però les còpies dels mateixos, de manera que en aquest punt en la història, hi ha és DO i la llet en cadascuna d'aquestes safates. Hi ha un ui un dos en cadascuna d'aquestes safates, i la funció d'intercanvi és de fet treballant. Els està intercanviant l'interior de la segona safata superior, però que l'intercanvi no té impacte. I basant-se algunes principi bàsic que hem parlat abans, i de fet Fa tan sols uns minuts, el que podria explicar per què el canvi a i b a l'interior de bescanvi no té efecte en x i y, encara que Vaig passar x i i per a la funció d'intercanvi. Quina és la paraula clau aquí que podria explicar de manera simplista? Crec que he sentit aquí? AUDIÈNCIA: Retorn. ALTAVEU 1: Retorn? No tornar. Anirem amb una altra. Què és això? 

AUDIÈNCIA: [inaudible]. 

ALTAVEU 1: OK, així que vam poder return-- fer que el treball de retorn en la història, però hi ha una explicació encara més simple. AUDIÈNCIA: Àmbit d'aplicació. ALTAVEU 1: Àmbit d'aplicació. Prendré abast. Així abast, recordar on nostra xiy declarats. Estan declaren dins de principal fins aquí. A i B, per la seva banda, estan declarat efectivament dins de swap, no del tot a les claus, però encara en l'àrea general de swap. I així de fet, a i b només existeixen dins d'aquesta safata d'Annenberg, aquest segon tros de codi. Així que estem de fet el canvi de la còpia, però això no és realment tan útil. 

Així que donem una ullada a aquest nivell una mica més baix. Vaig a tornar a El directori d'origen, i jo vaig a primer zoom aquí, i només per confirmar que estic en aquesta finestra de terminal més gran, el programa encara s'està comportant així. Suposem ara que aquest no és intencional. Clarament volia intercanvi per treball, així que se sent com una bestiola. Ara podia començar a afegir un molta printf d'al meu codi, imprimir x aquí, i sobre aquí, un aquí, b per aquí. Però, francament, això és probablement el que que has estat fent durant un parell de setmanes ara, en horari d'oficina ia la casa quan es treballa en conjunts de processadors tractant de trobar alguns errors. Però vas a veure, si no ho ha fet, aquest problema es van establir tres que introdueix a una ordre anomenat GDB, on GDB, GNU debugger, té en si un munt de característiques que realment pot anem a entendre situacions com aquest, però més convincent, resoldre problemes i trobar errors. Així que vaig a fer això. En lloc de ./noswap, estic al seu lloc va a córrer GDB ./noswap. En altres paraules, vaig a dirigir la meva programa no en Bash, el nostre nou amic avui en dia. Vaig a portar el meu programa noswap interior d'aquest altre programa anomenat GDB, que és un depurador, que és un programa que està dissenyat per ajudar a que els éssers humans trobar i eliminar errors. Així que si copejo Executeu aquí, hi ha una quantitat atroç de text que realment no ha de llegir. Bàsicament es tracta d'una distracció des del símbol, que Vaig a colpejar Control-L aixecar-se en la part superior existeix. Aquest és el símbol del BGF. Si vull executar aquest programa ara, com aquesta petita full de trucs en l'actualitat de diapositiva suggereix, Run és la primera Les comandes que ens referíem a introduir. I jo només vaig a escriure córrer fins aquí dins de GDB, i de fet va funcionar meu programa. Ara hi ha una mica de addicional sortides de la pantalla com aquesta, però això és només estar GDB anal i ens diu el que està passant. Segur que no ha de preocupar sobre aquests detalls ara mateix. Però el que és realment bo d' GDB, si faig això nou-- Control-L refusa el screen-- em deixis anar per davant i el tipus "trencar principal", per tant, quan pols Enter, establint el que és anomenat un punt d'inflexió en noswap.c, línia 16, que és on GDB descobert el meu programa de realitat És a dir, la meva funció és en realitat. Aquesta ignorarem per ara però aquesta és l'adreça d' específicament en la memòria d'aquesta funció. Així que ara quan em escrigui Executar, notar el que està bé aquí. El meu programa es trenca en la línia I dit GDB per aturar l'execució en. Així que no he de canviar ara el meu codi, afegir alguns printf, recompilar, torneu a executar ella, canviar, afegir alguns printf, guardar, compilar, executar-lo. Jo només puc caminar a través del meu programa pas a pas a pas a la velocitat humana, no en Intel-inside tipus de velocitat. 

Així que ara compta aquesta línia apareix aquí, i si torno al meu programa a gedit, adonar que això és en realitat la primera línia de codi. Hi línia 16 a gedit. Hi línia 16 dins del BGF, i fins i tot encara que aquesta interfície blanc i negre no és tan d'usuari amable, això significa aquesta línia 16 no s'ha executat encara, però està a punt de ser. Així que de fet, si escric d'impressió x, no printf, només print x, Em surt algun valor fals no de zero, perquè x no s'ha inicialitzat encara. Així que vaig a escriure a continuació, o, si vull ser presumptuós, N per al proper. Però quan introdueixo següent entro, ara compte es passa a la línia 17. Així que, lògicament, si he executat línia 16 i ara escric print x, ¿Què he de veure? Una. 

I ara això és certament confús. $ 2 és només una forma elegant de, si vulgui fer referència a aquest valor més endavant, es pot dir "signe de dòlar 2." És com una referència cap enrere. Però per ara, simplement ho ignoren. L'interessant és el que hi ha a la dreta del signe igual. I ara si escric la propera vegada i d'impressió i, he de veure 2. També puc ara imprimir x de nou, i, francament, si m'estic posant una mica confós pel que fa a on sóc, puc tipus de llista per a la llista i només veure una mica de context al voltant El punt que estic realment en. I ara puc escriure següent, i no és x 1. Ara escric següent. Oh, i és 2. I de nou, és confús, perquè la producció del BGF està sent barrejat amb la meva pròpia producció. Però si es té en compte, per mirant cap enrere i cap endavant en el seu codi o pel qual es fora del costat al costat potser, vostè veig que en realitat només sóc passant a través del meu programa. 

Però adonar-se del que passa a continuació, literalment. Aquí hi ha la línia 22. Déjame anar sobre ell, movent així el a 23, i si imprimeixo x ara, segueix sent un. I si imprimeixo i ara, segueix sent un. Així que això no és un exercici útil. Així que anem a refer aquest. Permetin-me tornar a la superior i tipus d'execució de nou. I està dient que el programa que està sent depurat ha començat ja, començat des del principi. Sí, farem això de nou. I aquesta vegada ho farem la propera, següent, següent, següent, següent, però ara les coses es posen interessants. Ara vull entrar en intercanvi, així que no em escrigui a continuació. Escric pas, i ara notar m'ha saltat a la línia noswap.c 33. Si torno a gedit, el que és la línia 33? Aquesta és la primera real línia de codi dins de swap. La qual cosa és bo, perquè ara puc tipus de furgar i sentir curiositat pel que fa al que està passant realment en aquest país. Permetin-me imprimeixo tmp. Whoa. Per què tmp té alguna , El valor de les escombraries falsa boig? AUDIÈNCIA: No s'ha inicialitzat. ALTAVEU 1: No s'ha inicialitzat. I de fet, quan s'executa un programa, et donen un munt de memòria pel sistema operatiu, però no han inicialitzat cap valor, així que el que els bits que ets veient aquí, tot i que és aquest gran negatiu boig nombre, només significa que aquests són les restes de cert ús anterior que la memòria RAM, encara que jo no tinc jo ho necessitava encara. Així que ara vaig a seguir endavant i tipus següent, i si ara escric tmp d'impressió, ¿Què he de veure? Qualsevol que sigui el valor d'una era, a és el primer argument, només com x ser la primera El que es passa a, de manera que una i X ha de ser el mateix, així imprimir tmp em deu imprimir un. 

Així que el que vostè veurà en el conjunt de problemes 3 és un tutorial de classes en GDB, però s'adonen que aquest és el començament d'un cop d'ull a una eina que ho farà realitat ajudar a resoldre problemes de manera molt més eficaç. El que estem en última instància farem el dimecres es començarà a pelar unes poques capes i eliminar algunes rodes d'entrenament. Aquesta cadena cosa crida que que hem utilitzat durant algun temps, anem a prendre a poc a poc que fos de vostè i començar a parlar de una mica més esotèricament conegut com char *, però ho farem bé i suaument al principi, tot i que els punters, com se'ls anomena, es pot fer una mica de coses molt dolentes si s'abusa, mirant una mica d'animació amb plastilina nostre amic Nick Parlant de Stanford Universitat, professor a l'ordinador la ciència que va armar aquesta vista prèvia del que està per venir aquest dimecres. 

[REPRODUCCIÓ DE VÍDEO] Escolta, Binky. Despertar. És temps per a la diversió punter. 

Què és això? Aprendre sobre els punters? Que bé! [FI REPRODUCCIÓ DE VÍDEO] ALTAVEU 1: Que l'espera el dimecres. Ens veiem llavors. [REPRODUCCIÓ DE VÍDEO] -I Ara, pensaments profunds, per Daven Farnham. 

Per què estem aprenent C? Per què no A +? 

[Rialles] 

[FI REPRODUCCIÓ DE VÍDEO]