CS50 2014 - Semaine 4

>> [REPRODUCCIÓN DE MÚSICA] >> ALTAVOZ 1: Muy bien, esto es CS50,y este es el comienzo de la semana cuatro, y como usted puede haber oído oleer, el mundo ha estado llegando a su fin. El ir por todo el internetha sido el conocimiento y la conciencia de un error en un programa, unalenguaje de programación llamado Bash. Este ha sido marcado maravillosamentecomo Shellshock, o la puerta Bash, pero artículos como estosno han sido infrecuentes. Y, de hecho, muchos de ellos traenrecuerdos posteriores de Heartbleed, que usted puede haber notado en elcomprimir la primavera pasada, que fue igualmente bastante dramático. Ahora, por aquellos de ustedes aquíhoy, ¿cuántos de ustedes tienen, incluso si usted no entiende lo quees todo sobre, oído hablar de Shellshock? Muy bien, y ¿cuántos de ustedestener equipos que son vulnerables? Aceptar, debe haber mucho, mucho más manoshasta ahora, por razones que veremos. >> Echemos un vistazo a lo queestado sucediendo en los medios de comunicación y luego explicarlo un pocoaquí para nosotros técnicamente. >> ALTAVOZ 2: Los expertos en seguridad tienenadvertido que una grave falla podría estar a punto de afectar a cientos demillones de usuarios de Internet del mundo. Entonces, ¿qué es exactamente el error que ha sidoapodado Shellshock, y lo que hace? Bueno, Shellshock también se conoce como elBug Bash, el software que explota. Los hackers utilizan virus para escanear vulnerablessistemas que ejecutan Linux y Unix sistemas operativos y luego infectar a ellos. Bash es un shell de línea de comandos. Esto permite que los usuarios de los comandos de edición para lanzarprogramas y características en el software por la introducción de texto. Se utiliza normalmente por los programadores, yno debe estar abierto al resto del mundo, aunque Shellshock cambia eso. >> Bueno, worringly, algunos analistasadvierten que podría ser una amenaza mayor, porque Shellshock permite completael control de una máquina infectada, mientras que sólo se permite Heartbleedhackers para espiar en computadoras. Es tan grave, esha clasificado un 10 sobre 10 de la gravedad por la NationalBase de datos de vulnerabilidades. 2.3 de todos los servidores web están enriesgo, incluyendo algunos ordenadores Mac. Bueno, asegúrese de queparchear sus sistemas ahora. Cualquiera que alojar un sitio web en funcionamientolos sistemas operativos afectados debe tomar medidas tan pronto como sea posible. Cualquiera que pueda permitírselo debe mirara su aplicación de monitoreo y web firewalls a tener en cuenta cualquier ataque. ALTAVOZ 3: Lo peorque podría pasar es que alguien escribiría código queiría automáticamente y escanear internet y afectaríatodos estos equipos. Y una vez que lo hacen, así,lo peor que podían hacer se acaba de borrar todo,o cerrar los sitios de abajo. Así que podríamos ver el dañodesde ese punto de vista, donde tendríamos personas maliciosasque acaba de decidir a causar estragos trayendo sistemas abajo o eliminararchivos, y cosas como esas. ALTAVOZ 2: Algunos dicen que esta es unade las más difíciles de medir errores en años, y quepuede llevar semanas o incluso meses para determinar su impacto final. >> ALTAVOZ 1: Así que todo eso es cierto,pero lo curioso es que casi todos de las imágenes que acabas de ver,excepto quizás el teclado, no tiene nada que ver conel error absoluto. Servidores y alambres y así sucesivamente,Es una especie de tangencialmente relacionado, pero en el fondo es en realidad bastantefamiliarizado lo que está pasando aquí. De hecho, déjame ir anuestro aparato CS50. Déjame ir por delante y maximizarla ventana de terminal aquí. Y ustedes han estado utilizando este,o la versión incorporada de la misma, en gedit para escribir programas,escribir comandos, y así sucesivamente, y esto es en realidad, y tienesido durante semanas, Bash, B-A-S-H. Este es el Bourne-again shell,que es sólo una forma elegante de decir, este es un programa que tiene unparpadeo rápido, eficaz, que se sienta allí esperandopara la entrada para usted. Y es el comandointerfaz de línea a través del cual que ustedes han estado ejecutando comandos yen última instancia, la compilación y luego corriendo programas. >> Pero Bash es también una programaciónidioma en el siguiente sentido. Usted sabe que hay comandos comocd y ls y también clang y otros, pero usted puede definir sus propios comandosmediante la implementación de ellos en Bash. Ahora no vamos aentrar en gran detalle como para golpear el lenguaje de programación, peroSabemos, por ejemplo, que en este momento, no hay comando llamado "hola." Por lo tanto, se puede encontrar enuno de estos paquetes. No está instalado en mi equipo. Pregunte a su administrador. Pero si yo quiero que haya un programallamado "hola" en Bash o en mi pronta, De hecho, puedo utilizar la sintaxis que esabsolutamente como C. No es exactamente lo mismo, pero se ve bastante similar a unfunción, aunque faltan algunos detalles. Nada parece suceder,pero ahora si escribo "hola" en realidad se puede escribir unaprograma, no en C, no en Java, no en otra programaciónidioma, pero en sí Bash. >> Ahora la clave aquí es que escribí elnombro yo quería dar a este nuevo comando, y los paréntesis son tambiénsimbólico de que esto sea una función. Como acotación al margen, también se puede hacer la diversióncosas, y de hecho, incluso en Mac OS, este es un programa que se llama Terminal. Viene integrado en cualquiera deequipo que tiene un Mac en esta sala, y se pueden hacer cosas similares en MacOS, pero se puede ir más allá de eso. Y esto es un poco tangencial,pero es bastante divertido. Me acordé de esta mañana,al pensar en esto, de un pequeño juego que solía jugarcon uno de los ex TFS del CS50 mediante el cual cualquier momento iba a alejarse desu teclado con su pantalla desbloqueado, Me gustaría ejecutar un comandoasí- "saludar". Y ahora toda vez que volvía a suteclado después limpié la pantalla y se sentaba,tratar de hacer un poco de trabajo, listar el contenido de su directory-- >> [AUDIO REPRODUCCIÓN] >> -Hello. Hola. >> ALTAVOZ 1: Así que, para ser justos,que no era en realidad "hola." Por lo general era algomás parecido a eso-- [AUDIO REPRODUCCIÓN] -Beep. ALTAVOZ 1: --que I would--por lo que su equipo haría juro a él en cualquier momento que en realidadse sentó a su teclado. Y muy pronto se descubrióno dejar desbloqueado su pantalla. Pero esto sugiere que la especiedivertido estúpido que puede tener con algo como Bash. Pero es un poco másgrave, sin duda, que eso. Y de hecho, este es uno de losla mayoría de los insectos peligrosos y de larga duración que realmente ha golpeado el mundo global. Este error ha sido de alrededordurante unos 20 años, y serás golpeado en tan sólo unmomento por su relativa simplicidad. >> Así que este es un representantedi que si poseer un Mac, literalmente, en este momentocuando usted tiene su tapa abierta, puedes probar a escribir en esaprograma llamado Terminal. Terminal está bajoAplicaciones Utilities-- por una vez, los usuarios de Windows no tienen quepreocuparse por esto threat-- particular, pero aquellos de ustedes con Macs puede escribiresto en una ventana como la que voy a hacer aquí, y si usted escribeque en este programa llamada Terminal, como voy a hacer ahora,si usted ve la palabra "vulnerable" el equipo esvulnerables a la explotación. >> Ahora, ¿qué significa en realidad? Y esto es ciertouna sintaxis bastante loco, pero vamos a por lo menos derramaresalgunos de los aspectos interesantes. Así que hay una sintaxis que se veun poco familiar, al menos desde C y la programación en general. Veo algunos paréntesis,punto y coma, llaves, y tal, pero resulta que esteestupidez aquí en amarillo es esencialmente una funcióneso no hace nada. Los medios de colon no hacen nada, y lapunto y coma significa dejar de hacer nada. Así en el interior de estosllaves, el hecho de que tengo una igualfirmar a la izquierda, esta es esencialmente la creaciónun comando, o una variable, llamada x, y asignándoleque poco amarilla de código allí. Eso podría ser algo así como "ecohola "o" decir bip "o algo similar a eso. Pero fíjate si sus ojospasear más a la derecha, hay más en esta línea desólo el final de ese punto y coma. "Echo vulnerables", y luegomás allá de que hay aún más. Otro punto y coma, -c fiesta :. >> Así que cuento largo,esta línea de código es suficiente para obligarun equipo que es vulnerables a hacer algoque usted quiere que haga, porque hay un error en el cual Bashaunque Bash debía dejar de líneas de lectura de comando de la derechaallí después del texto amarillo, para un 20-plus años bug de edad,Bash ha sido en realidad la lectura más allá de ese punto y coma y bastantemucho haciendo lo que se le dice. >> ¿Cuál es la implicaciónde que en última instancia? Que acabo de decir "echo hola"o "eco vulnerables" pero lo que si usted hizo algorealmente maliciosos, como rm-rf *, que tal vez noalguna vez ha escrito antes, y, francamente, es probable queno debe demasiado pronto, porque se puede hacer unamucho daño con ella. ¿Por qué? rm hace qué, por supuesto? Elimina. * Significa qué? Todos. Así que es una llamadacomodín, por lo que significa borrar todo enel directorio actual. -r pasa a significar recursiva,que quiere decir que si lo que estás borrando es un directorio, y dentro de ahíes otros archivos y otros directorios, recursiva sumergirse en allíy borrar todo eso. Y f es el peor de todos ellos. Alguien sabe lo que significa -f aquí? Fuerza. Así forzar medios, inclusosi esto es una mala idea, hacerlo sin mí que provocópara su posterior confirmación. Así que, ya sabes, nos reímos deesto, pero, francamente, yo probablemente escriba esto varias vecesun día, porque la realidad es que es la manera más rápida deeliminar un montón de cosas. Pero incluso he hecho un poco de daño. >> Pero si usted fuera a engañar a un ordenadoren definir alguna variable estúpido o función llama x, pero luegoengañar a la computadora que ejecute más allá de los límites de esafunción, más allá de ese punto y coma, que de hecho podría engañar a un ordenadoren la ejecución de algo como rm-rf o el comando Emailo el comando Copiar. Cualquier cosa, literalmente, le puede ver con elordenador, si se trata de la eliminación de archivos, la creación de archivos, envío de correo basura a alguien,atacando a algún servidor de forma remota, si usted puede expresarlocon un comando, puede engañar a una computadora para que haga eso. >> Ahora lo que es un ejemplo decómo se puede hacer esto? Bueno, hay un montón de ordenadoresen el Bash internet en ejecución. Todos los usuarios de Mac nos están entre ellos. Una gran cantidad de servidores Linux se encuentran entreellos también, y servidores Unix. Ventanas obtiene de nuevorelativamente fuera del gancho a menos que haya instaladosoftware especial. Ahora un montón de servidores, paraejemplo, para ejecutar servidores web, y de hecho Linux es quizás elmás popular sistema operativo para ejecutarse en ordenadores en Internetque se servir las páginas web. Ahora bien, como veremos más adelanteen el semestre, cuando se envía una solicitud desu browser-- Chrome, Internet Explorer, whatever--a un servidor remoto, resulta que a pesar de queque acaba de escribir www.example.com, su navegador está enviando un mensajeeso es un poco más arcano, como éste. >> Pero note algo extraño. Las dos primeras líneasYo nunca he visto antes, pero que no se venparticularmente mortal. Pero noto lo que yo he robadopara la tercera línea de aquí. Si un intruso fuera a enviar un mensajeasí desde su ordenador a un Mac o un vulnerableservidor Linux vulnerables, lo curioso es que Bash,que pronta poco simple comando, es omnipresente y es a menudoSe usa para ejecutar esencialmente el contenido de unmensaje que recibe. Y por esa lógica, se puedeengañar a un servidor web, por lo tanto, enviando algo asíUser-Agent, que por lo general se supone que es decir loNombre de tu navegador. User-Agent Cromo, User-Agent InternetExplorer, Firefox User-Agent, este es sólo el navegador deforma de identificar a sí mismo. Pero si uno de los malos muyinteligentemente dice, mm-mm, estoy No voy a decirlo que mi navegador es, Estoy en vez de ir a hacerle llegar estaLo críptico de aspecto con un rm-rf * En el mismo, que, literalmente, puede engañar a unservidor web vulnerable en Internet para que ejecute exactamente eso enallí para borrar todos los archivos. Y, francamente, eso no esincluso la peor parte. Usted puede hacer cualquier cosa. Usted podría comenzar una distribuidaataque de denegación de servicio si envió este mensaje aracimos enteros de servidores web y luego tuvieron todos ellos descienden, porejemplo, en servidores Harvard.edu, y se puede ordenar de explosiónlos diablos de ellos por un tráfico de red que sedesencadenada en contrario de este chico malo. >> Por lo tanto, cuento largo, casitodos en esta sala que es dueño de un Mac es vulnerable a este. El lado positivo es que a menos que seasejecutar un servidor web en su computadora portátil, y, a menos que haya configurado en realidadpara permitir que algo así como SSH en él, estás realmente seguro. Es vulnerable, pero no esuno tratando de entrar en su computadora portátil, así que usted puede ordenar de contar. Sin embargo, Apple prontoser la actualización de una solución para este. El mundo de Linux ya ha lanzadouna serie de correcciones para Fedora y Ubuntu y otras versiones de Linux, y de hechosi ejecuta la actualización 50 en el aparato, aunque eso también seráactualizada y corregida. Pero eso tampoco tienesido realmente vulnerable, porque a menos que usted tienevanamente con el aparato e hizo su portátil públicamenteaccesibles en Internet, que no es por defecto, que hayaen realidad estado bien porque de cortafuegos y otras técnicas. >> Pero es un ejemplo extremo de un errorque hemos vivido para para, literalmente, 20 años, y quién sabe si alguientodo este tiempo se ha sabido de ella? Y de hecho, esta es una delos retos fundamentales que veremos más adelante en elsemestre por la seguridad, es que al igual que en el mundo real,los buenos están en la desventaja. Para mantener a los chicos malos, tenemos queasegurarse de que cada puerta está cerrada, que cada ventana es seguro, quecada punto de entrada en un hogar es seguro para mantener a los chicos malos. Pero lo que hace el malo de la película tiene quehacer para comprometer realmente su casa y robar de usted? Él o ella sólo tiene que encontrar uno desbloqueadopuerta, una ventana rota o algo en ese sentido, y es lalo mismo en la seguridad informática. Podemos escribir a millones delíneas de código de programación y gastar cientos o milesde horas tratando de conseguirlo correcto, pero si lo hacen sólo unaerror en la corrección, usted puede poner todo el sistema yde hecho, en este caso, la totalidad de internet y el mundo en riesgo. >> Así que si desea aprender mássobre esto, vaya a esta URL aquí. No hay necesidad de una acciónesta noche a menos que esté entre los más cómodos quehan sido la gestión de su propia web servidor, en cuyo caso usted debe,de hecho, actualizar el software. >> Y esto también es el título deun discurso, y ahora un papel, que nos hemos vinculado en lala página web del curso para hoy. Fue por un compañerollamado Ken Thompson, quien fue la aceptación de un muy famosopremio en ciencias de la computación, y él dio este discurso algunos añoshace, esencialmente sobre el mismo tema. La gente que hace la pregunta,Si usted realmente confianza, en última instancia, lasoftware que te han dado? Por ejemplo, todos tenemosestado escribiendo programas, y hemos estado recopilandocon Clang. Y a su conocimiento, ¿has escritocualquier programa de CS50 donde hay una puerta trasera de tipo, hay una maneraque un tipo malo, si se ejecuta el programa, podría hacerse cargo de su equipo? Probablemente no, ¿verdad? Mario y codicioso, y Crédito. Estos son todos los programas bastante pequeños. Usted tendría que ser bastantemal si en realidad hecho todo el equipo sea vulnerabledespués de escribir 10 o 20 líneas de código, o al menos consciente de algunosde las implicaciones de seguridad. Ahora digo que en tono de burla,pero vamos a ver hoy y esta semana es en realidadmuy, muy fácil a ser malo y hacer aúnprogramas cortos vulnerables. >> Pero, por ahora, al menos, darse cuentaque la pregunta que se hace aquí está a punto Clang en un compilador. ¿Por qué hemos estado confiando en Clangdurante los últimos dos o tres semanas? ¿Quién puede decir que quien escribió Clangno tenía un "si" condición en la que hay que esencialmente se inyecta algunos cerosy los en cada programa se compila eso sería dejar que él o ella el accesocuando el equipo está dormido y su tapa del portátil está abiertoy el equipo se ejecuta? ¿Cierto? Tenemos este tipo de sistema de honor derechoahora donde confiamos en que Clang es de fiar. Usted confía en que el aparato es de fiar. Usted confía en que, literalmente, todos los programasen tu Mac o PC es digno de confianza. Y como este simple error sugiere,incluso si no es malicioso, eso no es absolutamenteprobable que sea el caso. >> Así que usted debe tener miedo como el infierno. Francamente, no hay sencillosolución a este otro que una especie de conciencia socialde la complejidad cada vez mayor que estamos construyendo en la parte superiorde nuestros sistemas informáticos, y cómo cada vez más vulnerablespodríamos muy bien ser. >> Ahora, con esto dicho, Breakout. Así Breakout es problema establece tres, yBreakout es un juego de antaño que se puede recordar, peropara nosotros en un problema establecido tres, que nos permite tomarlas cosas vuelvan a un nivel superior de manera que cuando estamos escribiendo programas,incluso en una ventana de terminal como este, en realidad podemos ejecutar, en última instancia,no los programas de gráficos a diferencia de aquellos que tuvimosen el acceso a los arañazos. Así que esta es la década de los funcionariosimplementación de Breakout, que es precisamente esta romper ladrillosjuego, que se mueve la pala hacia atrás adelante y hacia atrás, y golpear la bolacontra los ladrillos de colores hasta la parte superior. Así que esto nos está trayendoespecie de vuelta a donde hemos sido capaces de ser muy rápidocon Scratch, y ahora con C, la implementación de nuestra propiainterfaces gráficas de usuario. >> Pero más que eso, esteconjunto de problemas representa la primera en la que estamos dandoque un montón de código. Y, de hecho, les traigo explícitaatención a esto, porque todo para los menos confortable, esteproblema configurado, al menos a primera vista, se va a sentir comohemos llevado a un nivel superior. Debido a que les hemos dado,para algunos de la búsqueda y clasificación de los problemas en el conjunto de procesadores,un montón de código que escribimos, y un par de comentariosque dicen "hacer" donde usted tiene que llenar los espacios en blanco. Así que no demasiado miedo, peroque es la primera vez le estamos entregando código que usted necesitaleer primero, entender, y luego añadir a y completarlo. >> Y luego, con Breakout,vamos a hacer lo mismo, dándole unas pocas docenas más líneasde código que, francamente, le dará una gran parte del marco parael juego, pero detenerse de la aplicación de los ladrillosy la pelota y la paleta, pero sí implementamos algunas otras características. E incluso que, a primera vista, de nuevo,especialmente si menos cómodo, podría parecer especialmente difícil yCrees que hay tantas nuevas funciones que necesita para envolver su mentealrededor, y eso es verdad. Pero tenga en cuenta, esabsolutamente como arañazos. Lo más probable es que no ha utilizado todaslas piezas del rompecabezas en cero. Lo más probable es que no te importaba para envolversu mente alrededor de todos ellos porque todo lo que hizo fue unrápida mirada para comprender, oh, eso es lo que puedo hacercon esa pieza del rompecabezas. Y de hecho, en conjunto de problemas3 spec, vamos a señalar que en la documentación quepresentarles a algunas funciones nuevas, y en última instancia la programaciónconstrucciones que utilice. Condiciones, bucles,variables y funciones será idéntico allo que hemos visto hasta el momento. >> Así que de hecho, lo que vamos a darusted es un código de ejemplo que le permite crear una ventanaque no se ve a diferencia de este, y en última instancia, convertirlo enalgo como esto. Así que toma ventaja de CS50,discutir horas de oficina y más, y consolarse con el hecho de quela cantidad de código que tiene que escribir en realidad no es tanto. El primer reto es sólo para aclimatarseusted mismo a algún código que hemos escrito. >> Cualquier pregunta sobre pset3,Shellshock, o de otra manera? >> AUDIENCIA: Parecía queir a través con Breakout que el código es casiun estilo orientado a objetos, pero pensé que era un Cprograma orientado a objetos. ALTAVOZ 1: Una excelente pregunta. Así que en mirar a través de lacódigo de distribución, el código escribimos para pset3,Para aquellos familiarizados, se parece que es unpoco orientado a objetos. Respuesta corta es, lo es. Es una aproximación de cómo sepodría hacer código orientado a objetos utilizando un lenguaje como C, pero estodavía en última instancia de procedimiento. No hay métodos dentro delas variables, como verás. Pero recuerda que. Y veremos que la función de nuevocuando lleguemos a PHP y JavaScript hacia el final del semestre. Pero por ahora, pensar en ella comouna pista de lo que está por venir. Buena pregunta. Bien. Así merge sort era cómocosas izquierda última vez. Y fusionar especie estaba fresco en lasentido de que era mucho más rápido, al menos sobre la base de las pruebas superficialesque hicimos la semana pasada, que, por ejemplo, la burbuja especie, ordenamiento por selección, ordenación por inserción. Y lo que era demasiado limpio es sólocómo sucinta y limpiamente puedes expresarlo. Y lo que dijimos que era un superiorcon destino en el tiempo de ejecución de la fusión ordenar? ¿Sí? >> AUDIENCIA: n log n? >> ALTAVOZ 1: n log n, derecho. n log n. Y vamos a volver a lo querealmente significa o de dónde viene, pero esto era mejorque lo que el tiempo de funcionamiento que vimos durante la burbujaselección y ordenación por inserción? Así que n al cuadrado. n al cuadradoes más grande que esto, e incluso si no es bastante obvio,sabe que log n es menor que n, así que si usted lo hace n vecesalgo menor que n, que va a ser menor que n al cuadrado. Es un poco de intuición allí. Pero pagamos un precio por ello. Era más rápido, pero un tema que comenzóemerja la semana pasada era este sacrificio. Tengo un mejor rendimientoen cuanto a tiempo, pero lo que Por qué tengo que pasar por otroparte, con el fin de lograr eso? >> AUDIENCIA: Memoria. ALTAVOZ 1: Dilo de nuevo? AUDIENCIA: Memoria. ALTAVOZ 1: Memoria, oel espacio de forma más general. Y no era súperobvia con nuestros seres humanos, pero recordar que nuestros voluntariosfueron dando un paso adelante y paso a paso hacia atrás como si hay una matrizaquí, y como si hay una segunda matriz que aquíque podrían utilizar, porque nos algún lugar necesaria para fusionar esas personas. No podíamos cambiar en su lugar. Así fusionar especie de apalancamientoes más espacio, lo cual que no era necesario conlos otros algoritmos, pero la ventaja es que es mucho más rápido. Y, francamente, en el espacio del mundo realéstos RAM días--, disco duro espacio-- es relativamente barato, y por lo que esno es necesariamente algo malo. >> Así que vamos a echar un vistazo rápido, un pocomás metódicamente, en lo que hicimos y por qué dijimos que fue n log n. Así que aquí están los ocho números y laocho voluntarios que tenían la última vez. Y lo primero que MergeOrdenar nos dijo que hacer era qué? AUDIENCIA: Divide en dos. ALTAVOZ 1: Dilo de nuevo? AUDIENCIA: Divide en dos. ALTAVOZ 1: Dividir en dos, derecha. Esto recuerda mucho ala guía telefónica, de división y conquistar de manera más general. Así que buscamos en la mitad izquierda. Y entonces una vez dijimos, una especiela mitad izquierda de los elementos, ¿qué hicimos junto decimos? Ordenar la mitad izquierda de la izquierdala mitad, lo que nos permitió, después de dividir en dos,centrarse en cuatro y dos. >> ¿Cómo ordenar una lista ahora, enamarillo, de tamaño dos, utilizando Combinar Ordenar? Bueno dividir por la mitad,y ordenar la mitad izquierda. Y este era el lugar donde las cosasse puso un poco brevemente estúpido. ¿Cómo ordenar una lista que es detamaño de uno, como este número cuatro en esta lista? Está ordenada. Ha terminado. >> Pero entonces, ¿cómo ordenar una lista detamaño de uno cuando es el número dos? Bueno, lo mismo, pero ahora lo que fue latercero y el paso clave en Merge Ordenar? Había que combinar la izquierdala mitad y la mitad derecha. Y una vez que lo hicimos, nos miramosa las cuatro, nos fijamos en dos. Decidimos bien,obviamente dos que ocurra primero, así que pusimos dos en sulugar, seguido por cuatro. Y ahora tienes que tipo de rebobinado,y esto es una especie de característica de un algoritmo como MergeOrdena, rebobinar en la memoria. ¿Cuál fue la siguiente línea de la historia? ¿Qué debería estar centrado en el próximo? La mitad derecha de la izquierdamedia, que es de seis y ocho. >> Así que permítanme simplemente un paso a través de estasin machacar el punto demasiado. Seis y ocho, a continuación, seis esordenados, ocho se ordena. Combinar juntos de esa manera,y ahora el próximo gran paso está, por supuesto, ordenar la mitad derecha desdeel primer paso de este algoritmo. Así que nos centramos en uno, tres, siete, cinco. Luego nos centramos en la mitad izquierda. La mitad izquierda de que, la mitad derecha deeso y, a continuación, se funden en uno y tres. Entonces la mitad derecha, luego a la izquierda la mitadde él, entonces la mitad derecha de la misma. Combinar en, y ahora lo que queda paso? Combinar la gran mitad izquierda y la granmitad derecha, por lo que uno se pone allí, luego dos, luego tres, luego cuatro, luegocinco, luego seis, luego siete, luego ocho. >> Así que ahora por qué se esta revelando en última instancia,especialmente si n y logaritmos más en general, más bien escapar,al menos en los últimos tiempos? Bueno, fíjate en la altura de esta cosa. Tuvimos ocho elementos, y nosdividido por dos, por dos, por dos. Así que la base ingrese dos de las ocho nos da tres. Y confía en mí en que siun poco nebuloso sobre eso. Pero el registro de base de dos de ocho es tres,por lo que hemos hecho tres capas de fusión. Y cuando nos fusionamoselementos, el número de elementos nos vemos en cada una de las filas? Un total de n, ¿verdad? Debido a la fusión de la fila superior,a pesar de que lo hicimos poco a poco, que en última instancia, tocamos cada número una vez. Y en la segunda fila, afusionar dichas listas de tamaño dos, tuvimos que tocar cada elemento una vez. Y entonces aquí realmenteclaramente en la última fila, tuvimos que tocar cada uno de loselementos de una vez, pero sólo una vez, así que en este documento se encuentra, entonces, nuestro n log n. >> Y ahora sólo para hacer las cosas un pocomás formal para un momento, si estaban ahora a analizar esteen una especie de mayor nivel y tratar de decidir, así cómopodrías ir al expresar el tiempo de ejecución de este algoritmosólo mirando a ella y no utilizando un ejemplo artificioso? Bueno, ¿cuánto tiempo le dirías apaso como éste en amarillo tomaría, si n <2 vuelta? Esa es una gran O de qué? Así que yo estoy viendo uno, así que un paso,tal vez dos pasos porque es si y luego regresar, pero esconstante de tiempo, ¿verdad? Así que dijimos O (1), y eso escómo voy a expresar esto. T, acaba de ser tiempo de ejecución. n es el tamaño de la entrada,así que T (n), sólo una forma elegante de decir el funcionamientotiempo de entrada dado de tamaño n va a ser del ordende constante de tiempo, en O (1). >> Pero por lo demás, ¿qué pasa con esto? ¿Cómo expresar lamomento de esta línea amarilla corriendo? T ¿de qué? Puede tipo de trampas aquí yresponder a mi pregunta de forma cíclica. Así que si el tiempo de funcionamiento enen general nos limitamos a decir es T (n). Y ahora usted está especie de batea aquí ydiciendo, bueno, sólo ordenar la mitad izquierda, y luego ordenar la mitad derecha. ¿Cómo podríamos representar simbólicamenteel tiempo de ejecución de esta línea amarilla? T ¿de qué? ¿Cuál es el tamaño de la entrada? n más de dos. ¿Por qué no me acaba de decir eso? Y entonces este es otro T (n / 2) y luegode nuevo, si puedo combinar dos mitades ordenadas, cuántos elementos voya tener que tocar total de? n. Así que puedo expresar esto,sólo para ser un poco de fantasía, como el tiempo de funcionamiento en general. T (n) es el tiempo de duración de T (n / 2),además de T (n / 2), la mitad izquierda y la mitad derecha, además de O (n), que es probablemente n pasos,pero tal vez, si estoy usando dos dedos, que es el doble quepasos, pero es lineal. Es cierto número de pasoseso es un factor de n, por lo que podríamos expresar esto como esta. Y aquí es donde ahora vamos a Punt a laparte posterior de nuestro libro de texto de matemáticas de la escuela secundaria estamos que la recurrencia en última instanciatermina igualando esto, n log n veces, si usted hace realmente fueralos cálculos de manera más formal. >> Así que eso es sólo dos puntos de vista. Una numéricamente con unduro con código de ejemplo representativo con ocho números y una másvistazo general a la forma en que llegamos allí. Pero lo que es realmente interesante aquíes, de nuevo, esta noción de ciclismo. No estoy usando para bucles. Soy una especie de definiciónalgo en términos de sí mismo, no sólo con estafunción matemática, sino también en términos de este pseudo código. Esta pseudo código es recursivaen que dos de sus líneas está esencialmente diciendo que se vayautilice a sí mismo para resolver un menor problema de tamaño más pequeño,y luego otra vez y otra vez y otra vez hasta que reducir gradualmente haciaa este llamado caso base. >> Así que vamos a dibujar una realidad más convincentepara llevar de la siguiente manera. Déjame ir en gedit y tomo unver algunas de código fuente actual, en particular, este ejemplo aquí. Sigma 0, que aparentemente añadelos números del uno al n. Así que vamos a ver lo que es familiary desconocido aquí. En primer lugar tenemos un par deincluye, así que nada nuevo. Prototype. Estoy un poco confusa enesto después de pocos días, pero lo dijimos unaprototipo de una función es? AUDIENCIA: [inaudible]. ALTAVOZ 1: ¿Qué es eso? AUDIENCIA: Anunciamos ella. ALTAVOZ 1: Anunciamos ella. Así que usted está enseñando Clang, hey,no la aplicación real de esto todavía, pero en algún lugar de este archivo, presumiblemente,va a ser una función llamada qué? Sigma. Y esto es sólo una promesa queque va a tener este aspecto. Va a tomar un entero comoEntrada-- y puedo ser más explícito y decir int n --y esva a devolver un int, pero medio punto y coma, mm, voy a llegar alrededor dea la implementación de este un poco más tarde. Una vez más, Clang es tonto. Sólo va a saber lo quele dices que arriba a abajo, así que tenemos que dar por lo menoses un indicio de lo que está por venir. >> Ahora echemos un vistazo a principal aquí. Vamos a desplazarse hasta aquí yver lo principal está haciendo. No es que a largo de una función, yde hecho, el constructo aquí es familiar. Declaro una variable n, y luegoMe molestan al usuario una y otra vez para un entero positivo utilizando getInt,y única salida de este bucle una vez que el usuario ha cumplido. Do While, que hemos utilizado paramolestar al usuario de esa manera. Ahora esto es interesante. Declaro un int llamada "respuesta". Asigno que el valor de retornode una función llamada "sigma". No sé lo que eso hace todavía, peroMe acuerdo que declara que hace un momento. Y entonces yo estoy pasando en elvalor que el usuario escribió en, n, y luego informo la respuesta. Bueno, vamos a retrocedersólo por un momento. Vamos a seguir adelante en este directorio, hacensigma 0, y en realidad ejecutar este programa y ver qué pasa. Así que si sigo adelante y correreste programa, ./sigma-0, y escribo en un positivoentero como dos, Sigma, como el símbolo griego lo indica, es sólova a sumar todos los números del cero en un máximo de dos. Así 0 más 1 más 2. Así que espero que este debe darme 3. Eso es todo lo que está haciendo. Y del mismo modo, si se me acaba el mensajey le doy el número tres, eso es 3 más 2, por lo que es5, más 1 me debería dar 6. Y luego, si me pongo muy loco yempieza a escribir en números más grandes, me debería darsumas cada vez más grandes. Así que eso es todo. >> Entonces, ¿qué sigma parece? Bueno, es bastante sencillo. Es la forma en que podríamos haber implementadoesto para el último par de semanas. "Int" va a ser el tipo de retorno. Sigma es el nombre, y se necesitauna variable m en lugar de n. Cambiaré que encima de la tapa. Entonces esto es sólo una prueba de cordura. Veremos por qué en un momento. Ahora declaro otra variable,suma, inicializar a cero. Entonces tengo este bucle Foriteración, al parecer, para mayor claridad, desde i = 1 hasta en un = m, que escualquiera que sea el usuario escribió en, y luego me incrementar la suma de esta manera. Y a continuación, devolver la suma. >> Así que un par de preguntas. Uno, me dicen en mi comentario de que estaevita el riesgo de un bucle infinito. ¿Por qué habría de pasar en un número negativoinducir, potencialmente, un bucle infinito? >> AUDIENCIA: Usted nunca llegará a m. >> ALTAVOZ 1: Nunca llegar m. Pero m se pasa, así que vamos aconsiderar un ejemplo sencillo. Si m se pasa por elusuario como uno negativo. Independientemente de principal. Principal nos protege deesto también, así que estoy solo siendo muy anal consigma también cerciorarse que la entrada no puede ser negativo. Así que si m es negativo,algo así como una cosa negativa. ¿Qué va a pasar? Bueno, va aque éste se inicia a uno, y luego me va a sermenos de o igual a m? >> Colocarse. Eso fue-- no vamos,vamos a Nix esta historia. Yo no pedí esa pregunta, porqueel riesgo de que aludo no va a suceder porque i essiempre va ser mayor Aceptar que--, Me retracto de que se trate. Okay. Vamos a centrarnos sólo en esta parte aquí. ¿Por qué me declaro algunosfuera del bucle? Aviso sobre la línea 49 no tengoi declarada dentro del bucle, pero en línea 48 que hedeclarado algunos de fuera. Sí. AUDIENCIA: [inaudible]. ALTAVOZ 1: Seguro. Así que, ante todo, yo desde luego no lo hagoquerer declarar e inicializar suma a cero en el interior de labucle en cada iteración, porque esto iría en contra de la claridadpropósito de resumir los números. Me gustaría mantener el cambioel valor a cero. Y también, lo que es otra más arcanarazón de esa misma decisión de diseño? Sí. >> AUDIENCIA: [inaudible]. ALTAVOZ 1: Exactamente. Quiero acceder a ella fueradel bucle demasiado en qué línea? En 53. Y en base a nuestra regla de orodesde hace un par de conferencias, variables que están en el ámbito, de verdad, a lallaves que ellos abarcan. Así que si no declaro suma dentrode estas llaves exteriores, Yo no lo puedo usar en la línea 53. Dicho de otra manera, si yo declarésuma aquí, o incluso dentro de la Para bucle, no podía acceder a él en el 53. La variable efectivamente se habría ido. Así que un par de razones allí. Pero ahora vamos a volvery ver qué pasa. Así sigma se llama. Se suma 1 más 2 o 1 más 2más 3, y luego devuelve el valor, almacena en respuesta, y printf aquíes por lo que estoy viendo en la pantalla. Así que esto es lo que vamos a llamar a un proceso iterativoenfoque, donde iteración sólo significa usar un bucle. Un bucle For, un bucle while, un Do Whilebucle, simplemente hacer algo nuevo y una y otra vez. >> Pero sigma es una especie de función ordenada enque podría poner en práctica de manera diferente. ¿Qué pasa con esto, quesólo para ser una especie de fresco, permítanme realmente deshagode una gran cantidad de distracción porque esta funciónes realmente muy simple. Vamos a reducir gradualmente hacia abajo apenasa sus cuatro líneas básicas y deshacerse de toda lacomentarios y llaves. Esta es una especie de alucinanteimplementación alternativa. Está bien, tal vez no alucinante,pero es un poco más sexy, de acuerdo, ver esta mucho más sucinta. Con sólo cuatro líneas de código,La primera vez que tengo esta prueba de cordura. Si m es menor que o igual acero, sigma no tiene sentido. Sólo se supone que es eneste caso para los números positivos, así que sólo voy adevolver cero arbitrariamente de manera que al menos tenemosalgunos llamado caso base. >> Pero aquí está la belleza. La totalidad de esta idea, añadiendo lanúmeros del 1 al n, m, o en este caso, se puede hacer por la clase de pasar la pelota. Bueno, ¿cuál es la suma de 1 a m? Bueno, ¿sabes qué? Es lo mismo que la suma de mmás la suma de 1 m de menos 1. Pues ¿sabes qué? ¿Qué hay de sigma m menos 1? Bueno, si usted sigue este tipo delógicamente, es el mismo que m menos 1 además de sigma m menos 2. Así que usted puede tipo de solo--esto es como, si eres tratando de molestar a un amigoy te hacen una pregunta, que clase de responder con una pregunta,usted puede tipo de mantener escurrir el bulto. Pero lo que es clave es que si se mantienehaciendo la pregunta más y más pequeña y más pequeño, usted esno pedir lo que es sigma de n, lo que es de sigman, lo que es sigma de n? Le estás preguntando cuál essigma de n, lo que es sigma n de menos 1, lo que es de sigma n menos 2? Eventualmente su preguntava a ser qué? ¿Qué es la sigma de uno ocero, un valor muy pequeño, y tan pronto como seconseguir que, a su amigo, usted no va a pedirla misma pregunta de nuevo, sólo vamos a decir, oh es cero. Hemos terminado de jugar este tipode juego cíclico estúpido. >> Así que la recursividad es el acto en la programaciónde una función que se hace llamar. Este programa, cuando se compila y ejecuta, esva a comportarse de la misma manera, pero lo que es clave es que en el interiorde una función llamada sigma, hay una línea de código en el queque llamamos nosotros mismos, que normalmente sería malo. Por ejemplo, ¿qué pasa si yo primerocompilado esta, así que sigma-- hacer sigma 1 ./sigma-1. Entero positivo, por favor, 50 1275. Así que lo que la función pareceser, basado en una prueba, correcta. Pero lo que si me da un poco peligrosoy eliminar el llamado caso base, y acabo de decir, bueno, yo sólo estoy haciendoesto más complicado de lo que es. Vamos a computar el sigmatomando m y después añadiendo en sigma de m menos uno? Bueno, ¿qué va a pasar aquí? Vamos a alejar. Vamos a volver a compilar el programa,guardarlo, volver a compilar el programa, y entonces listo ./sigma-1 el zoom,introducir entero positivo favor, 50. ¿Cuántos de ustedes están dispuestosa confesar a ver eso? >> Okay. Así que esto puede suceder poruna serie de razones, y, francamente, esta semana estamosa punto de darle más de ellos. Pero en este caso, intentepara razonar hacia atrás lo que podría haber sucedido aquí? Fallo de segmentación, dijimos últimatiempo, se refiere a un segmento de memoria. Algo malo ha pasado. Pero ¿qué eramecánicamente que salió mal aquí debido a mi retiradade que el llamado caso base, donde volví un valor codificado? ¿Qué crees que salió mal? Sí. >> AUDIENCIA: [inaudible]. ALTAVOZ 1: Ah. Buena pregunta. Así que el tamaño del númeroque estaba resumiendo puso tan grande que superael tamaño del espacio de memoria. Buena idea, pero no fundamentalmenteva a causar un accidente. Eso podría causar desbordamiento de enteros,donde los bits sólo voltean y luego confundimos una muy grandenúmero como por un número negativo, pero que en sí no va a causar un accidente. Debido a que al final de ladía un int es todavía 32 bits. Usted no va arobar accidentalmente un poco 33a. Pero un buen pensamiento. Sí. >> AUDIENCIA: [inaudible]. ALTAVOZ 1: El métodonunca deja de correr, y he aquí que se llama de nuevoy una y otra vez y otra vez y otra vez, y ninguno deesas funciones cada vez terminar porque su única línea decódigo si misma llama una y otra vez y otra vez. Y lo que es realmentepasando aquí, y ahora nos puede dibujar este tipo de ilustraciones. Déjame ir a unfoto por un momento. Esta es una imagen, queeventualmente dar cuerpo a con más detalle, de lo que está pasandodentro de la memoria del equipo. Y resulta que enla parte inferior de esta imagen es algo que se llama la pila. Se trata de un trozo dememoria, un trozo de memoria RAM, eso es sólo utilizan cualquier momentouna función es llamada. Cada vez que, un programador,llamar a una función, el sistema operativo, comoMac OS, Windows, o Linux, agarra un puñado de bytes, tal vez unpocos kilobytes, tal vez pocos megabytes de la memoria, los entregaa usted y, a continuación, le permite ejecuta su función utilizandolo variables que usted necesita. Y si luego llamar a otrola función y la otra función, le da otra rebanada de memoriay otra rebanada de memoria. >> Y de hecho, si estas bandejas verdesde Annenberg representar esa memoria, esto es lo que sucede el primervez que se llame a la función sigma. Es como poner una bandeja como éstaen lo que es inicialmente una pila vacía. Pero entonces, si esa bandejallama a sí mismo, por así decirlo, llamar a otra instanciade sigma, eso es como preguntar el sistema operativo,ooh, necesitará un poco más de memoria, dame eso. Y entonces se apilan en la parte superior. Pero lo que es clave aquí es quela primera bandeja está todavía allí, porque él invocó esta segunda bandeja. Ahora mientras tanto, sigma llaman sigma,eso es como pedir más memoria. Obtiene apilados por aquí. sigma llamar sigma, esa es otrabandeja que consigue apilados en aquí. Y si sigues haciendo esto,finalmente, una especie de mapa de esta visual a esa carta, lo que va aocurrir con la pila de bandejas? Se va a exceder la cantidadde memoria el equipo tiene. Y tan pronto como esta bandeja verdeexcede la línea horizontal por encima de la pila y por encima de esa palabra montón,que vamos a volver en el futuro, eso es una mala cosa. El montón es una diferentesegmento de la memoria, y si dejas que estosbandejas de pila y pila en, usted va a superarsu propio segmento de la memoria, y un programa está de hecho va a estrellar. >> Ahora como un aparte, esta ideade la recursión, por lo tanto, puede conducir a problemas claramente, perono es necesariamente una mala cosa. Debido a considerar, después detodo, y tal vez cómo-- esto toma algún tiempo acostumbrarsea --¿Cómo elegante o lo simple que la aplicación de sigma fue. Y no vamos a utilizarrecursividad casi nada en CS50, pero en CS51, y realmente cualquier clasedonde se manipulan estructuras de datos como árboles o árboles de la familia,que tienen cierta jerarquía, es super, super útil. Ahora, como un aparte, de modo que ustedcomo aspirantes a científicos de la computación están familiarizados con algunos de Google debromas internas, si usted va a Google y usted mira para arriba lo que es ladefinición de, por ejemplo, la recursividad, escriba. Uh-huh. Como acotación al margen, me detuve unos pocos. Esto fue como de 10 minutos dela dilación de esta mañana. Si también Google "torcida" avisoinclinando la cabeza slightly-- y entonces éste es quizásmás atroz de todos ya que alguien pasó comosu día de la aplicación de esta algunos años ago-- vamos. Oh, espera-- eso es un error. >> Así que se ejecuta en uno de losmayores sitios web del mundo son estos estúpidos pequeños huevos de Pascua. Probablemente consumen unanúmero no trivial de líneas de código sólo para que podamos tenerpequeñas cosas divertidas como esas. Pero por lo menos ahora usted consiguealgunas de esas bromas. >> Ahora echemos un vistazo a algunos de losblanco se encuentra que hemos estado diciendo en los últimos tiempos, y empezar a pelaralgunas capas técnicamente de modo que usted realmente entiendelo que ha estado pasando y se puede entenderalgunas de las amenazas, como Shellshock, queAhora han comenzado a convertirse en en la vanguardia de todo el mundo deatención, al menos en los medios de comunicación. Así que aquí es una función muy simpleque devuelve nada, el vacío. Su nombre es de intercambio. Se necesita en dos variablesy no devuelve nada. Toma en ay b. Así que una demostración rápida. Trajimos estos. Puede ser que también tome un pocoromper aquí por un momento y tener un poco de algo para beber. Si a alguien no le importaría unirseme hasta aquí por un momento. ¿Qué tal si en la camisa marrón? Vamos arriba. Sólo la de hoy. Gracias, sin embargo. Muy bien, y tenemosviene que aquí? Cuál es tu nombre? >> ALTAVOZ 4: Laura. >> ALTAVOZ 1: Laura. Vamos arriba. Así que Laura, muy simple desafío de hoy. Encantado de conocerte yo. Bien. Así que tenemos un poco de leche aquí ytenemos un poco de jugo de naranja por aquí y algunas tazas que nostomado de Annenberg hoy. >> ALTAVOZ 4: Borrowed. ALTAVOZ 1: Y va a seguir adelantey le dará la mitad de un vaso de esto. Bien. Y le daremos la mitadun vaso de leche. Ah, y para que puedarecuerde cómo era esto, Me acordé de traeresto y en la actualidad. Bueno. Si no te importa, vamos a ver, nospuede ponerlos en sus propias gafas si quieres. Este va a ser el mundo desde los ojos de Laura. Bien. Así que su objetivo, le dieron dos tazas delíquido aquí, leche y zumo de naranja, se intercambie los dos contenidos de forma que eljugo de naranja va a la taza de leche y la leche entra enla taza de jugo de naranja. >> ALTAVOZ 4: ¿Tengo otra taza? ALTAVOZ 1: Estoy tan bueno que lo preguntas, aunquehabría sido mucho mejor material de archivo si no hubieras preguntado. Pero sí, podemos ofrecerle una terceravaso que está vacía, por supuesto. Bien. Así que cambiar el contenido allí. Muy agradable. Muy buena. Estás haciendo esto muy cuidadosamente. Y el tercer paso. Bien. Excelente. Un gran aplausosería bueno para Laura. Bien. Tenemos un pequeño regalo de despedidapara usted, pero quiero aprovechar estos. Muchas gracias. Así, un ejemplo sencillo, sin embargo,para demostrar que si lo hace querer cambiar el contenidode dos contenedores, o vamos a llamarlos las variables,necesitas algo de almacenamiento temporal para organizar uno de los contenidos en laque en realidad se puede hacer el canje. Así que de hecho, el código fuente aquí enC es representante de exactamente eso. Si el zumo de naranja era una y la lecheera b, y queríamos cambiar los dos, usted podría intentar algo creativomediante el vertido de una en la otra, pero que probablemente no lo haríaterminar particularmente bien. Y por lo que utilizar una taza tercera, llamadaque tmp, T-M-P por convención, y poner el contenido delDO en que, a continuación, intercambiar una taza, a continuación, poner la DO en eltaza original, de ese modo lograr, exactamente como seLaura hizo, el canje. >> Así que vamos a hacer exactamente eso. Déjame ir adelante y abrirhasta un ejemplo de que es llama en realidad "nocambiar, "porque esto no es como un simple hecho como usted podría pensar. Así que en este programa, observe queEstoy usando stdio.h, nuestro viejo amigo. Tengo el prototipopara swap ahí arriba, que significa la aplicación deprobablemente por debajo, y vamos a ver lo que este principalprograma va a hacer por mí. La primera vez que declaro int x seuno, y int y consigue dos. Así que pensar en aquellos como DOy leche, respectivamente. Y entonces yo sólo tengo unprintf diciendo x es esta e y es esto, para que yo puedaver visualmente lo que está pasando. Luego he printf reclamandoque estoy intercambiando los dos, y luego imprimo unafirman que están intercambiados, y yo imprimo x e y otra vez. Así que aquí en intercambio esexactamente lo que hizo Laura, y es exactamente lo que vimos enla pantalla hace un momento. >> Así que vamos a seguir adelante ymuy decepcionado. No nos swap, y ejecutar sin swap,hacer zoom sobre la salida de aquí. Ingrese x es 1, y es 2, intercambiando intercambiado. x es todavía 1, e y es todavía 2. Así que, aunque, francamente, esto pareceexactamente igual, aunque de forma más técnica, Laura lo hizo, no parece funcionar. Entonces ¿por qué es eso? Bueno, resulta que cuandoescribimos un programa como este que tiene tanto principal, puesto de relieve aquí,y luego otra función, como canje, resaltado aquí, lo cualque llama, el mundo se ve un poco de algo comoestas bandejas hace un momento. Cuando principal primero se vuelve a llamar,eso es como preguntarle sistema operativo para un poco de memoria para cualquier local devariables como x e y que tiene principal, y terminan ahí. Pero si las llamadas principales de intercambio, y principalpasa a intercambiar dos argumentos, a y b, jugo de naranja y la leche, que no es comoentregándole el jugo de naranja y la leche a Laura. ¿Qué hace una computadora, ¿espasa copias del zumo de naranja y copias de la leche a Laura, por lo quelo que es en última instancia dentro de esta bandeja es el valor de uno y dos, o DOy leche, pero las copias de los mismos, de manera que en este puntoen la historia, hay es DO y la leche en cada una de estas bandejas. Hay un uno y un dosen cada una de estas bandejas, y la función de intercambio es de hecho trabajando. Les está intercambiando el interiorde la segunda bandeja superior, pero que el intercambio no tiene impacto. Y en base a algunasprincipio básico que hemos hablado antes, y de hechoHace tan sólo unos minutos, lo que podría explicar por qué el cambioa y b en el interior de canje no tiene efecto en x e y, aunquePasé x e y para la función de intercambio. ¿Cuál es la palabra clave aquí quepodría explicar de manera simplista? Creo que he oído aquí? AUDIENCIA: Retorno. ALTAVOZ 1: Regreso? No volver. Vamos a ir con otra. Qué es eso? >> AUDIENCIA: [inaudible]. >> ALTAVOZ 1: OK, así que pudimos return--hacer que el trabajo de retorno en la historia, pero hay una explicación aún más simple. AUDIENCIA: Ámbito de aplicación. ALTAVOZ 1: Ámbito de aplicación. Tomaré alcance. Así alcance, recordar dóndenuestra xey declarados. Están declaran dentrode principal hasta aquí. A y B, por su parte, estándeclarado efectivamente dentro de swap, no del todo enlas llaves, pero todavía en el área general de swap. Y así de hecho, a y bsólo existen dentro de esta bandeja de Annenberg, estesegundo trozo de código. Así que estamos de hecho el cambio de la copia, peroeso no es realmente tan útil. >> Así que echemos un vistazo aeste nivel un poco más bajo. Voy a volver aEl directorio de origen, y yo voy a primerozoom aquí, y sólo para confirmar que estoy en estaventana de terminal más grande, el programa todavía se está comportando así. Supongamos ahora que esteno es intencional. Claramente quería intercambio paratrabajo, así que se siente como un bicho. Ahora podía empezar a añadir unmucha printf de a mi código, imprimir x aquí, y sobreaquí, una aquí, b por aquí. Pero, francamente, eso es probablemente lo queque has estado haciendo durante un par de semanas ahora, en horario de oficinay en la casa cuando se trabaja en conjuntos de procesadores tratando de encontrar algunos errores. Pero vas a ver, si no lo ha hecho,ese problema se establecieron tres que introduce a un comando llamado GDB,donde GDB, GNU debugger, tiene en sí un montón decaracterísticas que realmente puede vamos a entender situacionescomo éste, pero más convincente, resolver problemas y encontrar errores. Así que voy a hacer esto. En lugar de ./noswap, estoy en su lugarva a correr GDB ./noswap. En otras palabras, voy a dirigir miprograma no en Bash, nuestro nuevo amigo hoy en día. Voy a llevar miprograma noswap interior de este otro programa llamadoGDB, que es un depurador, que es un programa que está diseñado para ayudar aque los seres humanos encontrar y eliminar errores. Así que si golpeo Ejecute aquí, hayuna cantidad atroz de texto que realmente no tiene que leer. Básicamente se trata de una distraccióndesde el símbolo, que Voy a golpear Control-Llevantarse en la parte superior existe. Este es el símbolo del BGF. Si quiero ejecutar este programa ahora,como esta pequeña hoja de trucos en la actualidad de diapositiva sugiere, Run es la primeraLos comandos que nos referíamos a introducir. Y yo sólo voy a escribircorrer hasta aquí dentro de GDB, y de hecho funcionó mi programa. Ahora hay un poco de adicionalsalidas de la pantalla como esta, pero eso es sólo estar GDB analy nos dice lo que está pasando. Usted realmente no tiene que preocuparsesobre estos detalles ahora mismo. Pero lo que es realmente bueno deGDB, si hago esto nuevo-- Control-L despeja el screen-- me dejes irpor delante y el tipo "romper principal", por lo tanto, cuando pulso Enter, estableciendo lo que esllamado un punto de quiebre en noswap.c, línea 16, que es donde GDBdescubierto mi programa de realidad Es decir, mi función es en realidad. Esta ignoraremos por ahorapero esa es la dirección de específicamente en la memoria de esta función. Así que ahora cuando me escriba Ejecutar,notar lo que está bien aquí. Mi programa se rompe en la línea Idicho GDB para detener la ejecución en. Así que no tengo que cambiar ahora mi código,añadir algunos de printf, recompilar, vuelva a ejecutar ella, cambiar, añadir algunos de printf,guardarlo, compilarlo, ejecutarlo. Yo sólo puedo caminar a través de mi programapaso a paso a paso a la velocidad humana, no en Intel-inside tipo de velocidad. >> Así que ahora cuenta esta líneaaparece aquí, y si vuelvo a mi programa en gedit,cuenta de que esto es en realidad la primera línea de código. Hay línea 16 en gedit. Hay línea 16 dentro del BGF, e inclusoaunque esta interfaz blanco y negro no es tan de usuarioamable, esto significa esa línea 16 no se ha ejecutadoaún, pero está a punto de ser. Así que de hecho, si escribo de impresiónx, no printf, sólo print x, Me sale algún valor falso no de cero,porque x no se ha inicializado todavía. Así que voy a escribir a continuación, o, siquiero ser presuntuoso, N para el próximo. Pero cuando introduzco siguiente entro, ahoracuenta se pasa a la línea 17. Así que, lógicamente, si he ejecutadolínea 16 y ahora escribo print x, ¿qué debo ver? Una. >> Y ahora esto es ciertamente confuso. $ 2 es sólo una forma elegante de, sidesee hacer referencia a ese valor más adelante, se puede decir "signo de dólar dos." Es como una referencia hacia atrás. Pero por ahora, simplemente lo ignoran. Lo interesante es lo que haya la derecha del signo igual. Y ahora si escribo la próxima vezy de impresión y, debo ver 2. También puedo ahora imprimirx de nuevo, y, francamente, si me estoy poniendo un poco confundido en cuanto adonde estoy, puedo tipo de lista para la lista y sólo ver un poco de contexto alrededorEl punto que estoy realmente en. Y ahora puedo escribirsiguiente, y no es x 1. Ahora escribo siguiente. Oh, y es 2. Y de nuevo, es confuso,porque la producción del BGF está siendo mezclado con mi propia producción. Pero si se tiene en cuenta, pormirando hacia atrás y hacia adelante en su código o por el que se fuera del ladoa lado tal vez, usted veo que en realidad sólo soypasando a través de mi programa. >> Pero darse cuenta de lo que sucede a continuación, literalmente. Aquí está la línea 22. Déjame ir sobre él, moviendo así ela 23, y si imprimo x ahora, sigue siendo uno. Y si imprimo y ahora, sigue siendo uno. Así que esto no es un ejercicio útil. Así que vamos a rehacer este. Permítanme volver a lasuperior y tipo de ejecución de nuevo. Y está diciendo que el programaque está siendo depurado ha comenzado ya,comenzado desde el principio. Sí, vamos a hacer esto de nuevo. Y esta vez vamos a hacerlo la próxima,siguiente, siguiente, siguiente, siguiente, pero ahora las cosas se ponen interesantes. Ahora quiero entrar enintercambio, así que no me escriba a continuación. Escribo paso, y ahora notarlome ha saltado a la línea noswap.c 33. Si vuelvo a gedit, lo que es la línea 33? Esa es la primera reallínea de código dentro de swap. Lo cual es bueno, porque ahora puedotipo de hurgar y sentir curiosidad en cuanto a lo que está pasando realmente en ese país. Permítanme imprimo tmp. Whoa. ¿Por qué tmp tiene alguna, el valor de la basura falsa loco? AUDIENCIA: No se ha inicializado. ALTAVOZ 1: No se ha inicializado. Y de hecho, cuando se ejecuta un programa,te dan un montón de memoria por el sistema operativo, perono han inicializado ningún valor, así que lo que los bits que eresviendo aquí, aunque es este gran negativo loconúmero, sólo significa que esos son los restos decierto uso anterior de que la memoria RAM, aunque yo no tengoyo lo necesitaba todavía. Así que ahora voy a seguir adelante y tiposiguiente, y si ahora escribo tmp de impresión, ¿qué debo ver? Cualquiera que sea el valor de una era,a es el primer argumento, sólo como x fue la primeraLo que se pasa en, por lo que una y X debe ser el mismo,así imprimir tmp me debe imprimir una. >> Así que lo que usted verá en el conjunto de problemastres es un tutorial de clases en GDB, pero se dan cuenta de que este es el comienzode un vistazo a una herramienta que lo hará realidad ayudarle a resolver problemasde manera mucho más eficaz. Lo que estamos en última instanciavamos a hacer el miércoles se comenzará a pelar unas pocas capasy eliminar algunas ruedas de entrenamiento. Esa cadena cosa llamada queque hemos utilizado durante algún tiempo, vamos a tomar poco a poco de que fuerade usted y empezar a hablar de algo más esotéricamenteconocido como char *, pero vamos a hacerlo bien ysuavemente al principio, a pesar de que los punteros, como se les llama, se puede hacer un poco decosas muy malas si se abusa, mirando un poco de animación con plastilinanuestro amigo Nick Parlante de Stanford Universidad, profesor en la computadorala ciencia que armó esta vista previa de lo que está por venir este miércoles. >> [REPRODUCCIÓN DE VÍDEO] Oye, Binky. Despertarse. Es tiempo para la diversión puntero. >> ¿Qué es eso? Aprenda acerca de los punteros? Qué bien! [FIN REPRODUCCIÓN DE VÍDEO] ALTAVOZ 1: Que le espera el miércoles. Nos vemos entonces. [REPRODUCCIÓN DE VÍDEO] -Y Ahora, pensamientos profundos,por Daven Farnham. >> Por qué estamos aprendiendo C? ¿Por qué no A +? >> [Risas] >> [FIN REPRODUCCIÓN DE VÍDEO]