>> [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 o leer, el mundo ha estado llegando a su fin.
El ir por todo el internet ha sido el conocimiento y la conciencia
de un error en un programa, una lenguaje de programación llamado Bash.
Este ha sido marcado maravillosamente como Shellshock, o la puerta Bash,
pero artículos como estos no han sido infrecuentes.
Y, de hecho, muchos de ellos traen recuerdos posteriores de Heartbleed,
que usted puede haber notado en el comprimir 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 que es todo sobre, oído hablar de Shellshock?
Muy bien, y ¿cuántos de ustedes tener equipos que son vulnerables?
Aceptar, debe haber mucho, mucho más manos hasta ahora, por razones que veremos.
>> Echemos un vistazo a lo que estado sucediendo en los medios de comunicación
y luego explicarlo un poco aquí para nosotros técnicamente.
>> ALTAVOZ 2: Los expertos en seguridad tienen advertido que una grave falla podría
estar a punto de afectar a cientos de millones de usuarios de Internet del mundo.
Entonces, ¿qué es exactamente el error que ha sido apodado Shellshock, y lo que hace?
Bueno, Shellshock también se conoce como el Bug Bash, el software que explota.
Los hackers utilizan virus para escanear vulnerables sistemas 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 lanzar programas y características en el software
por la introducción de texto.
Se utiliza normalmente por los programadores, y no debe estar abierto al resto del mundo,
aunque Shellshock cambia eso.
>> Bueno, worringly, algunos analistas advierten que podría ser una amenaza mayor,
porque Shellshock permite completa el control de una máquina infectada,
mientras que sólo se permite Heartbleed hackers para espiar en computadoras.
Es tan grave, es ha clasificado un 10 sobre 10
de la gravedad por la National Base de datos de vulnerabilidades.
2.3 de todos los servidores web están en riesgo, incluyendo algunos ordenadores Mac.
Bueno, asegúrese de que parchear sus sistemas ahora.
Cualquiera que alojar un sitio web en funcionamiento los sistemas operativos afectados
debe tomar medidas tan pronto como sea posible.
Cualquiera que pueda permitírselo debe mirar a su aplicación de monitoreo y web
firewalls a tener en cuenta cualquier ataque.
ALTAVOZ 3: Lo peor que podría pasar es
que alguien escribiría código que iría automáticamente y escanear
internet y afectaría todos 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ño desde ese punto de vista,
donde tendríamos personas maliciosas que acaba de decidir a causar estragos
trayendo sistemas abajo o eliminar archivos, y cosas como esas.
ALTAVOZ 2: Algunos dicen que esta es una de las más difíciles de medir
errores en años, y que puede 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 con el error absoluto.
Servidores y alambres y así sucesivamente, Es una especie de tangencialmente relacionado,
pero en el fondo es en realidad bastante familiarizado lo que está pasando aquí.
De hecho, déjame ir a nuestro aparato CS50.
Déjame ir por delante y maximizar la 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 tiene sido 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 un parpadeo rápido, eficaz,
que se sienta allí esperando para la entrada para usted.
Y es el comando interfaz de línea a través del cual
que ustedes han estado ejecutando comandos y en última instancia, la compilación y luego corriendo
programas.
>> Pero Bash es también una programación idioma en el siguiente sentido.
Usted sabe que hay comandos como cd y ls y también clang y otros,
pero usted puede definir sus propios comandos mediante la implementación de ellos en Bash.
Ahora no vamos a entrar en gran detalle
como para golpear el lenguaje de programación, pero Sabemos, por ejemplo, que en este momento,
no hay comando llamado "hola."
Por lo tanto, se puede encontrar en uno de estos paquetes.
No está instalado en mi equipo.
Pregunte a su administrador.
Pero si yo quiero que haya un programa llamado "hola" en Bash o en mi pronta,
De hecho, puedo utilizar la sintaxis que es absolutamente como C. No es exactamente lo mismo,
pero se ve bastante similar a un función, aunque faltan algunos detalles.
Nada parece suceder, pero ahora si escribo "hola"
en realidad se puede escribir una programa, no en C, no en Java,
no en otra programación idioma, pero en sí Bash.
>> Ahora la clave aquí es que escribí el nombro yo quería dar a este nuevo comando,
y los paréntesis son también simbólico de que esto sea una función.
Como acotación al margen, también se puede hacer la diversión cosas, y de hecho, incluso en Mac OS,
este es un programa que se llama Terminal.
Viene integrado en cualquiera de equipo que tiene un Mac en esta sala,
y se pueden hacer cosas similares en Mac OS, 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 jugar con uno de los ex TFS del CS50
mediante el cual cualquier momento iba a alejarse de su teclado con su pantalla desbloqueado,
Me gustaría ejecutar un comando así- "saludar".
Y ahora toda vez que volvía a su teclado 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 algo má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 realidad se sentó a su teclado.
Y muy pronto se descubrió no dejar desbloqueado su pantalla.
Pero esto sugiere que la especie divertido estúpido que
puede tener con algo como Bash.
Pero es un poco más grave, sin duda, que eso.
Y de hecho, este es uno de los la mayoría de los insectos peligrosos y de larga duración
que realmente ha golpeado el mundo global.
Este error ha sido de alrededor durante unos 20 años,
y serás golpeado en tan sólo un momento por su relativa simplicidad.
>> Así que este es un representante di que si
poseer un Mac, literalmente, en este momento cuando usted tiene su tapa abierta,
puedes probar a escribir en esa programa llamado Terminal.
Terminal está bajo Aplicaciones Utilities--
por una vez, los usuarios de Windows no tienen que preocuparse por esto threat-- particular,
pero aquellos de ustedes con Macs puede escribir esto en una ventana como la que voy a hacer aquí,
y si usted escribe que en este programa
llamada Terminal, como voy a hacer ahora, si usted ve la palabra "vulnerable"
el equipo es vulnerables a la explotación.
>> Ahora, ¿qué significa en realidad?
Y esto es cierto una sintaxis bastante loco,
pero vamos a por lo menos derramares algunos de los aspectos interesantes.
Así que hay una sintaxis que se ve un 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 este estupidez aquí en amarillo
es esencialmente una función eso no hace nada.
Los medios de colon no hacen nada, y la punto y coma significa dejar de hacer nada.
Así en el interior de estos llaves, el hecho de
que tengo una igual firmar a la izquierda, esta
es esencialmente la creación un comando, o una variable,
llamada x, y asignándole que poco amarilla de código allí.
Eso podría ser algo así como "eco hola "o" decir bip "o algo
similar a eso.
Pero fíjate si sus ojos pasear más a la derecha,
hay más en esta línea de sólo el final de ese punto y coma.
"Echo vulnerables", y luego má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 obligar un equipo que es
vulnerables a hacer algo que usted quiere que haga,
porque hay un error en el cual Bash aunque Bash debía dejar de
líneas de lectura de comando de la derecha allí 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 bastante mucho haciendo lo que se le dice.
>> ¿Cuál es la implicación de que en última instancia?
Que acabo de decir "echo hola" o "eco vulnerables"
pero lo que si usted hizo algo realmente maliciosos, como rm-rf *,
que tal vez no alguna vez ha escrito antes,
y, francamente, es probable que no debe demasiado pronto,
porque se puede hacer una mucho daño con ella.
¿Por qué?
rm hace qué, por supuesto?
Elimina.
* Significa qué?
Todos.
Así que es una llamada comodín, por lo que significa
borrar todo en el 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, incluso si esto es una mala idea,
hacerlo sin mí que provocó para su posterior confirmación.
Así que, ya sabes, nos reímos de esto, pero, francamente, yo probablemente
escriba esto varias veces un día, porque la realidad
es que es la manera más rápida de eliminar un montón de cosas.
Pero incluso he hecho un poco de daño.
>> Pero si usted fuera a engañar a un ordenador en definir alguna variable estúpido
o función llama x, pero luego engañar a la computadora que ejecute
más allá de los límites de esa función, más allá de ese punto y coma,
que de hecho podría engañar a un ordenador en la ejecución de algo como rm-rf
o el comando Email o el comando Copiar.
Cualquier cosa, literalmente, le puede ver con el ordenador, 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 expresarlo con un comando,
puede engañar a una computadora para que haga eso.
>> Ahora lo que es un ejemplo de cómo se puede hacer esto?
Bueno, hay un montón de ordenadores en el Bash internet en ejecución.
Todos los usuarios de Mac nos están entre ellos.
Una gran cantidad de servidores Linux se encuentran entre ellos también, y servidores Unix.
Ventanas obtiene de nuevo relativamente fuera del gancho
a menos que haya instalado software especial.
Ahora un montón de servidores, para ejemplo, para ejecutar servidores web,
y de hecho Linux es quizás el más popular sistema operativo
para ejecutarse en ordenadores en Internet que se servir las páginas web.
Ahora bien, como veremos más adelante en el semestre, cuando
se envía una solicitud de su browser-- Chrome,
Internet Explorer, whatever-- a un servidor remoto,
resulta que a pesar de que que acaba de escribir www.example.com,
su navegador está enviando un mensaje eso es un poco más arcano, como éste.
>> Pero note algo extraño.
Las dos primeras líneas Yo nunca he visto antes,
pero que no se ven particularmente mortal.
Pero noto lo que yo he robado para la tercera línea de aquí.
Si un intruso fuera a enviar un mensaje así desde su ordenador
a un Mac o un vulnerable servidor Linux vulnerables,
lo curioso es que Bash, que pronta poco simple comando,
es omnipresente y es a menudo Se usa para ejecutar esencialmente
el contenido de un mensaje que recibe.
Y por esa lógica, se puede engañar a un servidor web, por lo tanto,
enviando algo así User-Agent, que por lo general
se supone que es decir lo Nombre de tu navegador.
User-Agent Cromo, User-Agent Internet Explorer, Firefox User-Agent, este
es sólo el navegador de forma de identificar a sí mismo.
Pero si uno de los malos muy inteligentemente dice, mm-mm, estoy
No voy a decir lo que mi navegador es,
Estoy en vez de ir a hacerle llegar esta Lo críptico de aspecto con un rm-rf
* En el mismo, que, literalmente, puede engañar a un servidor web vulnerable en Internet
para que ejecute exactamente eso en allí para borrar todos los archivos.
Y, francamente, eso no es incluso la peor parte.
Usted puede hacer cualquier cosa.
Usted podría comenzar una distribuida ataque de denegación de servicio
si envió este mensaje a racimos enteros de servidores web
y luego tuvieron todos ellos descienden, por ejemplo, en servidores Harvard.edu,
y se puede ordenar de explosión los diablos de ellos
por un tráfico de red que se desencadenada en contrario de este chico malo.
>> Por lo tanto, cuento largo, casi todos en esta sala que es dueño de un Mac
es vulnerable a este.
El lado positivo es que a menos que seas ejecutar un servidor web en su computadora portátil,
y, a menos que haya configurado en realidad para permitir que algo así como SSH en él,
estás realmente seguro.
Es vulnerable, pero no es uno tratando de entrar en su computadora portátil,
así que usted puede ordenar de contar.
Sin embargo, Apple pronto ser la actualización de una solución para este.
El mundo de Linux ya ha lanzado una serie de correcciones para Fedora y Ubuntu
y otras versiones de Linux, y de hecho si ejecuta la actualización 50 en el aparato,
aunque eso también será actualizada y corregida.
Pero eso tampoco tiene sido realmente vulnerable,
porque a menos que usted tiene vanamente con el aparato
e hizo su portátil públicamente accesibles en Internet, que no es
por defecto, que haya en realidad estado bien porque
de cortafuegos y otras técnicas.
>> Pero es un ejemplo extremo de un error que hemos vivido para para, literalmente, 20
años, y quién sabe si alguien todo este tiempo se ha sabido de ella?
Y de hecho, esta es una de los retos fundamentales
que veremos más adelante en el semestre 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 que asegurarse de que cada puerta está cerrada,
que cada ventana es seguro, que cada 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 que hacer para comprometer realmente su casa
y robar de usted?
Él o ella sólo tiene que encontrar uno desbloqueado puerta, una ventana rota o algo
en ese sentido, y es la lo mismo en la seguridad informática.
Podemos escribir a millones de líneas de código de programación
y gastar cientos o miles de horas tratando de conseguirlo correcto,
pero si lo hacen sólo una error en la corrección,
usted puede poner todo el sistema y de hecho, en este caso, la totalidad de internet
y el mundo en riesgo.
>> Así que si desea aprender más sobre esto, vaya a esta URL aquí.
No hay necesidad de una acción esta noche a menos que esté
entre los más cómodos que han 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 de un discurso, y ahora un papel,
que nos hemos vinculado en la la página web del curso para hoy.
Fue por un compañero llamado Ken Thompson, quien
fue la aceptación de un muy famoso premio en ciencias de la computación,
y él dio este discurso algunos años hace, esencialmente sobre el mismo tema.
La gente que hace la pregunta, Si usted realmente
confianza, en última instancia, la software que te han dado?
Por ejemplo, todos tenemos estado escribiendo programas,
y hemos estado recopilando con Clang.
Y a su conocimiento, ¿has escrito cualquier programa de CS50 donde hay
una puerta trasera de tipo, hay una manera que 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 bastante mal si en realidad
hecho todo el equipo sea vulnerable después de escribir 10 o 20 líneas de código,
o al menos consciente de algunos de las implicaciones de seguridad.
Ahora digo que en tono de burla, pero vamos a ver hoy
y esta semana es en realidad muy, muy fácil
a ser malo y hacer aún programas cortos vulnerables.
>> Pero, por ahora, al menos, darse cuenta que la pregunta que se hace aquí
está a punto Clang en un compilador.
¿Por qué hemos estado confiando en Clang durante los últimos dos o tres semanas?
¿Quién puede decir que quien escribió Clang no tenía un "si" condición en la que hay
que esencialmente se inyecta algunos ceros y los en cada programa se compila
eso sería dejar que él o ella el acceso cuando el equipo está dormido
y su tapa del portátil está abierto y el equipo se ejecuta?
¿Cierto?
Tenemos este tipo de sistema de honor derecho ahora 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 programas en tu Mac o PC es digno de confianza.
Y como este simple error sugiere, incluso si no es malicioso,
eso no es absolutamente probable que sea el caso.
>> Así que usted debe tener miedo como el infierno.
Francamente, no hay sencillo solución a este otro
que una especie de conciencia social de la complejidad cada vez mayor
que estamos construyendo en la parte superior de nuestros sistemas informáticos,
y cómo cada vez más vulnerables podríamos muy bien ser.
>> Ahora, con esto dicho, Breakout.
Así Breakout es problema establece tres, y Breakout es un juego de antaño
que se puede recordar, pero para nosotros en un problema establecido tres,
que nos permite tomar las 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 tuvimos en el acceso a los arañazos.
Así que esta es la década de los funcionarios implementación de Breakout,
que es precisamente esta romper ladrillos juego, que se mueve la pala hacia atrás
adelante y hacia atrás, y golpear la bola contra los ladrillos de colores hasta la parte superior.
Así que esto nos está trayendo especie de vuelta a donde
hemos sido capaces de ser muy rápido con Scratch, y ahora con C,
la implementación de nuestra propia interfaces gráficas de usuario.
>> Pero más que eso, este conjunto de problemas representa la primera
en la que estamos dando que un montón de código.
Y, de hecho, les traigo explícita atención a esto, porque todo
para los menos confortable, este problema configurado, al menos a primera vista,
se va a sentir como hemos 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 comentarios que dicen "hacer"
donde usted tiene que llenar los espacios en blanco.
Así que no demasiado miedo, pero que es la primera vez
le estamos entregando código que usted necesita leer 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íneas de código que, francamente, le dará
una gran parte del marco para el juego, pero detenerse
de la aplicación de los ladrillos y 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 y Crees que hay tantas nuevas funciones
que necesita para envolver su mente alrededor, y eso es verdad.
Pero tenga en cuenta, es absolutamente como arañazos.
Lo más probable es que no ha utilizado todas las piezas del rompecabezas en cero.
Lo más probable es que no te importaba para envolver su mente alrededor de todos ellos
porque todo lo que hizo fue un rápida mirada para comprender, oh,
eso es lo que puedo hacer con esa pieza del rompecabezas.
Y de hecho, en conjunto de problemas 3 spec, vamos a señalar que
en la documentación que presentarles a algunas funciones nuevas,
y en última instancia la programación construcciones que utilice.
Condiciones, bucles, variables y funciones
será idéntico al lo que hemos visto hasta el momento.
>> Así que de hecho, lo que vamos a dar usted es un código de ejemplo que
le permite crear una ventana que no se ve a diferencia de este,
y en última instancia, convertirlo en algo como esto.
Así que toma ventaja de CS50, discutir horas de oficina y más,
y consolarse con el hecho de que la cantidad de código que tiene que escribir
en realidad no es tanto.
El primer reto es sólo para aclimatarse usted mismo a algún código que hemos escrito.
>> Cualquier pregunta sobre pset3, Shellshock, o de otra manera?
>> AUDIENCIA: Parecía que ir a través con Breakout
que el código es casi un estilo orientado a objetos,
pero pensé que era un C programa orientado a objetos.
ALTAVOZ 1: Una excelente pregunta.
Así que en mirar a través de la código de distribución, el código
escribimos para pset3, Para aquellos familiarizados, se
parece que es un poco orientado a objetos.
Respuesta corta es, lo es.
Es una aproximación de cómo se podría hacer código orientado a objetos utilizando
un lenguaje como C, pero es todavía en última instancia de procedimiento.
No hay métodos dentro de las variables, como verás.
Pero recuerda que.
Y veremos que la función de nuevo cuando lleguemos a PHP y JavaScript
hacia el final del semestre.
Pero por ahora, pensar en ella como una pista de lo que está por venir.
Buena pregunta.
Bien.
Así merge sort era cómo cosas izquierda última vez.
Y fusionar especie estaba fresco en la sentido de que era mucho más rápido,
al menos sobre la base de las pruebas superficiales que 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ólo cómo sucinta y limpiamente
puedes expresarlo.
Y lo que dijimos que era un superior con 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 que realmente significa o de dónde viene,
pero esto era mejor que lo que el tiempo de funcionamiento
que vimos durante la burbuja selección y ordenación por inserción?
Así que n al cuadrado. n al cuadrado es 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 veces algo 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 rendimiento en cuanto a tiempo, pero lo que
Por qué tengo que pasar por otro parte, con el fin de lograr eso?
>> AUDIENCIA: Memoria.
ALTAVOZ 1: Dilo de nuevo?
AUDIENCIA: Memoria.
ALTAVOZ 1: Memoria, o el espacio de forma más general.
Y no era súper obvia con nuestros seres humanos,
pero recordar que nuestros voluntarios fueron dando un paso adelante y paso a paso
hacia atrás como si hay una matriz aquí, 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 apalancamiento es más espacio, lo cual
que no era necesario con los 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 es no es necesariamente algo malo.
>> Así que vamos a echar un vistazo rápido, un poco má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 la ocho voluntarios que tenían la última vez.
Y lo primero que Merge Ordenar 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 a la 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 especie la mitad izquierda de los elementos,
¿qué hicimos junto decimos?
Ordenar la mitad izquierda de la izquierda la mitad, lo que nos permitió,
después de dividir en dos, centrarse en cuatro y dos.
>> ¿Cómo ordenar una lista ahora, en amarillo, de tamaño dos, utilizando Combinar Ordenar?
Bueno dividir por la mitad, y ordenar la mitad izquierda.
Y este era el lugar donde las cosas se puso un poco brevemente estúpido.
¿Cómo ordenar una lista que es de tamaño de uno, como este número cuatro en esta lista?
Está ordenada.
Ha terminado.
>> Pero entonces, ¿cómo ordenar una lista de tamaño de uno cuando es el número dos?
Bueno, lo mismo, pero ahora lo que fue la tercero y el paso clave en Merge Ordenar?
Había que combinar la izquierda la mitad y la mitad derecha.
Y una vez que lo hicimos, nos miramos a las cuatro, nos fijamos en dos.
Decidimos bien, obviamente dos que ocurra primero,
así que pusimos dos en su lugar, seguido por cuatro.
Y ahora tienes que tipo de rebobinado, y esto es una especie de característica
de un algoritmo como Merge Ordena, 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 izquierda media, que es de seis y ocho.
>> Así que permítanme simplemente un paso a través de esta sin machacar el punto demasiado.
Seis y ocho, a continuación, seis es ordenados, ocho se ordena.
Combinar juntos de esa manera, y ahora el próximo gran paso
está, por supuesto, ordenar la mitad derecha desde el 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 de eso y, a continuación, se funden en uno y tres.
Entonces la mitad derecha, luego a la izquierda la mitad de él, entonces la mitad derecha de la misma.
Combinar en, y ahora lo que queda paso?
Combinar la gran mitad izquierda y la gran mitad derecha, por lo que uno se pone allí,
luego dos, luego tres, luego cuatro, luego cinco, 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 nos dividido 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 si un 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 fusionamos elementos, 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, a fusionar dichas listas de tamaño dos,
tuvimos que tocar cada elemento una vez.
Y entonces aquí realmente claramente en la última fila,
tuvimos que tocar cada uno de los elementos 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 poco más formal para un momento, si
estaban ahora a analizar este en una especie de mayor nivel
y tratar de decidir, así cómo podrías ir al expresar
el tiempo de ejecución de este algoritmo sólo mirando a ella y no
utilizando un ejemplo artificioso?
Bueno, ¿cuánto tiempo le dirías a paso 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 es constante de tiempo, ¿verdad?
Así que dijimos O (1), y eso es có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 funcionamiento tiempo de entrada dado de tamaño n
va a ser del orden de constante de tiempo, en O (1).
>> Pero por lo demás, ¿qué pasa con esto?
¿Cómo expresar la momento de esta línea amarilla corriendo?
T ¿de qué?
Puede tipo de trampas aquí y responder a mi pregunta de forma cíclica.
Así que si el tiempo de funcionamiento en en general nos limitamos a decir es T (n).
Y ahora usted está especie de batea aquí y diciendo, bueno, sólo ordenar la mitad izquierda,
y luego ordenar la mitad derecha.
¿Cómo podríamos representar simbólicamente el 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 luego de nuevo, si puedo combinar dos mitades ordenadas,
cuántos elementos voy a 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 que pasos, pero es lineal.
Es cierto número de pasos eso es un factor de n,
por lo que podríamos expresar esto como esta.
Y aquí es donde ahora vamos a Punt a la parte posterior de nuestro libro de texto de matemáticas de la escuela secundaria
estamos que la recurrencia en última instancia termina igualando esto, n log n veces,
si usted hace realmente fuera los cálculos de manera más formal.
>> Así que eso es sólo dos puntos de vista.
Una numéricamente con un duro con código de ejemplo representativo
con ocho números y una más vistazo 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ón algo en términos de sí mismo,
no sólo con esta función matemática,
sino también en términos de este pseudo código.
Esta pseudo código es recursiva en que dos de sus líneas
está esencialmente diciendo que se vaya utilice 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 hacia a este llamado caso base.
>> Así que vamos a dibujar una realidad más convincente para llevar de la siguiente manera.
Déjame ir en gedit y tomo un ver algunas de código fuente actual,
en particular, este ejemplo aquí.
Sigma 0, que aparentemente añade los números del uno al n.
Así que vamos a ver lo que es familiar y desconocido aquí.
En primer lugar tenemos un par de incluye, así que nada nuevo.
Prototype.
Estoy un poco confusa en esto después de pocos días,
pero lo dijimos una prototipo 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 que que va a tener este aspecto.
Va a tomar un entero como Entrada-- y puedo ser más explícito
y decir int n --y es va a devolver un int,
pero medio punto y coma, mm, voy a llegar alrededor de a la implementación de este un poco más tarde.
Una vez más, Clang es tonto.
Sólo va a saber lo que le dices que arriba a abajo,
así que tenemos que dar por lo menos es un indicio de lo que está por venir.
>> Ahora echemos un vistazo a principal aquí.
Vamos a desplazarse hasta aquí y ver lo principal está haciendo.
No es que a largo de una función, y de hecho, el constructo aquí es familiar.
Declaro una variable n, y luego Me 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 para molestar al usuario de esa manera.
Ahora esto es interesante.
Declaro un int llamada "respuesta".
Asigno que el valor de retorno de una función llamada "sigma".
No sé lo que eso hace todavía, pero Me acuerdo que declara que hace un momento.
Y entonces yo estoy pasando en el valor que el usuario escribió en, n,
y luego informo la respuesta.
Bueno, vamos a retroceder sólo por un momento.
Vamos a seguir adelante en este directorio, hacen sigma 0, y en realidad ejecutar este programa
y ver qué pasa.
Así que si sigo adelante y correr este programa, ./sigma-0,
y escribo en un positivo entero como dos, Sigma,
como el símbolo griego lo indica, es sólo va 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 mensaje y le doy el número tres,
eso es 3 más 2, por lo que es 5, más 1 me debería dar 6.
Y luego, si me pongo muy loco y empieza a escribir en números más grandes,
me debería dar sumas 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 implementado esto para el último par de semanas.
"Int" va a ser el tipo de retorno.
Sigma es el nombre, y se necesita una 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 For iteración, al parecer, para mayor claridad,
desde i = 1 hasta en un = m, que es cualquiera 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 esta evita el riesgo de un bucle infinito.
¿Por qué habría de pasar en un número negativo inducir, potencialmente, un bucle infinito?
>> AUDIENCIA: Usted nunca llegará a m.
>> ALTAVOZ 1: Nunca llegar m.
Pero m se pasa, así que vamos a considerar un ejemplo sencillo.
Si m se pasa por el usuario como uno negativo.
Independientemente de principal.
Principal nos protege de esto también, así que estoy solo
siendo muy anal con sigma 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 a que éste se inicia a uno,
y luego me va a ser menos de o igual a m?
>> Colocarse.
Eso fue-- no vamos, vamos a Nix esta historia.
Yo no pedí esa pregunta, porque el riesgo de que aludo
no va a suceder porque i es siempre 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 algunos fuera del bucle?
Aviso sobre la línea 49 no tengo i declarada dentro del bucle,
pero en línea 48 que he declarado algunos de fuera.
Sí.
AUDIENCIA: [inaudible].
ALTAVOZ 1: Seguro.
Así que, ante todo, yo desde luego no lo hago querer declarar e inicializar suma
a cero en el interior de la bucle en cada iteración,
porque esto iría en contra de la claridad propósito de resumir los números.
Me gustaría mantener el cambio el valor a cero.
Y también, lo que es otra más arcana razón de esa misma decisión de diseño?
Sí.
>> AUDIENCIA: [inaudible].
ALTAVOZ 1: Exactamente.
Quiero acceder a ella fuera del bucle demasiado en qué línea?
En 53.
Y en base a nuestra regla de oro desde hace un par de conferencias,
variables que están en el ámbito, de verdad, a la llaves que ellos abarcan.
Así que si no declaro suma dentro de 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 volver y ver qué pasa.
Así sigma se llama.
Se suma 1 más 2 o 1 más 2 má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 iterativo enfoque, donde iteración sólo
significa usar un bucle.
Un bucle For, un bucle while, un Do While bucle, simplemente hacer algo nuevo
y una y otra vez.
>> Pero sigma es una especie de función ordenada en que podría poner en práctica de manera diferente.
¿Qué pasa con esto, que sólo para ser una especie de fresco,
permítanme realmente deshago de una gran cantidad de distracción
porque esta función es realmente muy simple.
Vamos a reducir gradualmente hacia abajo apenas a sus cuatro líneas básicas
y deshacerse de toda la comentarios y llaves.
Esta es una especie de alucinante implementació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 a cero, sigma no tiene sentido.
Sólo se supone que es en este caso para los números positivos,
así que sólo voy a devolver cero arbitrariamente
de manera que al menos tenemos algunos llamado caso base.
>> Pero aquí está la belleza.
La totalidad de esta idea, añadiendo la nú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 m má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 de ló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 amigo y 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 mantiene haciendo la pregunta más y más pequeña
y más pequeño, usted es no pedir lo que es sigma
de n, lo que es de sigma n, lo que es sigma de n?
Le estás preguntando cuál es sigma de n, lo que es sigma
n de menos 1, lo que es de sigma n menos 2?
Eventualmente su pregunta va a ser qué?
¿Qué es la sigma de uno o cero, un valor muy pequeño,
y tan pronto como se conseguir que, a su amigo,
usted no va a pedir la misma pregunta de nuevo,
sólo vamos a decir, oh es cero.
Hemos terminado de jugar este tipo de juego cíclico estúpido.
>> Así que la recursividad es el acto en la programación de una función que se hace llamar.
Este programa, cuando se compila y ejecuta, es va a comportarse de la misma manera,
pero lo que es clave es que en el interior de una función llamada sigma,
hay una línea de código en el que que llamamos nosotros mismos,
que normalmente sería malo.
Por ejemplo, ¿qué pasa si yo primero compilado esta, así que sigma--
hacer sigma 1 ./sigma-1.
Entero positivo, por favor, 50 1275.
Así que lo que la función parece ser, basado en una prueba, correcta.
Pero lo que si me da un poco peligroso y eliminar el llamado caso base,
y acabo de decir, bueno, yo sólo estoy haciendo esto más complicado de lo que es.
Vamos a computar el sigma tomando 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 dispuestos a confesar a ver eso?
>> Okay.
Así que esto puede suceder por una serie de razones,
y, francamente, esta semana estamos a punto de darle más de ellos.
Pero en este caso, intente para razonar hacia atrás
lo que podría haber sucedido aquí?
Fallo de segmentación, dijimos última tiempo, se refiere a un segmento de memoria.
Algo malo ha pasado.
Pero ¿qué era mecánicamente que salió mal
aquí debido a mi retirada de 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úmero que estaba resumiendo
puso tan grande que supera el tamaño del espacio de memoria.
Buena idea, pero no fundamentalmente va a causar un accidente.
Eso podría causar desbordamiento de enteros, donde los bits sólo voltean
y luego confundimos una muy grande número como por un número negativo,
pero que en sí no va a causar un accidente.
Debido a que al final de la día un int es todavía 32 bits.
Usted no va a robar accidentalmente un poco 33a.
Pero un buen pensamiento.
Sí.
>> AUDIENCIA: [inaudible].
ALTAVOZ 1: El método nunca deja de correr,
y he aquí que se llama de nuevo y una y otra vez y otra vez
y otra vez, y ninguno de esas funciones cada vez
terminar porque su única línea de código si misma llama una y otra vez
y otra vez.
Y lo que es realmente pasando aquí, y ahora nos
puede dibujar este tipo de ilustraciones.
Déjame ir a un foto por un momento.
Esta es una imagen, que eventualmente dar cuerpo a
con más detalle, de lo que está pasando dentro de la memoria del equipo.
Y resulta que en la parte inferior de esta imagen
es algo que se llama la pila.
Se trata de un trozo de memoria, un trozo de memoria RAM,
eso es sólo utilizan cualquier momento una función es llamada.
Cada vez que, un programador, llamar a una función,
el sistema operativo, como Mac OS, Windows, o Linux,
agarra un puñado de bytes, tal vez un pocos kilobytes, tal vez pocos megabytes
de la memoria, los entrega a usted y, a continuación, le permite
ejecuta su función utilizando lo variables que usted necesita.
Y si luego llamar a otro la función y la otra función,
le da otra rebanada de memoria y otra rebanada de memoria.
>> Y de hecho, si estas bandejas verdes de Annenberg representar esa memoria,
esto es lo que sucede el primer vez que se llame a la función sigma.
Es como poner una bandeja como ésta en lo que es inicialmente una pila vacía.
Pero entonces, si esa bandeja llama a sí mismo, por así decirlo,
llamar a otra instancia de 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 que la 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 otra bandeja que consigue apilados en aquí.
Y si sigues haciendo esto, finalmente, una especie de mapa de esta visual
a esa carta, lo que va a ocurrir con la pila de bandejas?
Se va a exceder la cantidad de memoria el equipo tiene.
Y tan pronto como esta bandeja verde excede 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 diferente segmento de la memoria,
y si dejas que estos bandejas de pila y pila en,
usted va a superar su propio segmento de la memoria,
y un programa está de hecho va a estrellar.
>> Ahora como un aparte, esta idea de la recursión, por lo tanto,
puede conducir a problemas claramente, pero no es necesariamente una mala cosa.
Debido a considerar, después de todo, y tal vez cómo--
esto toma algún tiempo acostumbrarse a --¿Cómo elegante o lo simple
que la aplicación de sigma fue.
Y no vamos a utilizar recursividad casi nada en CS50,
pero en CS51, y realmente cualquier clase donde 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 usted como aspirantes a científicos de la computación
están familiarizados con algunos de Google de bromas internas, si usted va a Google
y usted mira para arriba lo que es la definición de, por ejemplo, la recursividad, escriba.
Uh-huh.
Como acotación al margen, me detuve unos pocos.
Esto fue como de 10 minutos de la dilación de esta mañana.
Si también Google "torcida" aviso inclinando la cabeza slightly--
y entonces éste es quizás más atroz de todos
ya que alguien pasó como su 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 los mayores sitios web del mundo
son estos estúpidos pequeños huevos de Pascua.
Probablemente consumen una número no trivial de líneas de código
sólo para que podamos tener pequeñas cosas divertidas como esas.
Pero por lo menos ahora usted consigue algunas de esas bromas.
>> Ahora echemos un vistazo a algunos de los blanco se encuentra que hemos estado diciendo en los últimos tiempos,
y empezar a pelar algunas capas técnicamente
de modo que usted realmente entiende lo que ha estado pasando
y se puede entender algunas de las amenazas,
como Shellshock, que Ahora han comenzado a convertirse en
en la vanguardia de todo el mundo de atención, al menos en los medios de comunicación.
Así que aquí es una función muy simple que devuelve nada, el vacío.
Su nombre es de intercambio.
Se necesita en dos variables y no devuelve nada.
Toma en ay b.
Así que una demostración rápida.
Trajimos estos.
Puede ser que también tome un poco romper aquí por un momento
y tener un poco de algo para beber.
Si a alguien no le importaría unirse me 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 tenemos viene 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í y tenemos un poco de jugo de naranja por aquí
y algunas tazas que nos tomado de Annenberg hoy.
>> ALTAVOZ 4: Borrowed.
ALTAVOZ 1: Y va a seguir adelante y le dará la mitad de un vaso de esto.
Bien.
Y le daremos la mitad un vaso de leche.
Ah, y para que pueda recuerde cómo era esto,
Me acordé de traer esto y en la actualidad.
Bueno.
Si no te importa, vamos a ver, nos puede 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 de líquido aquí, leche y zumo de naranja,
se intercambie los dos contenidos de forma que el jugo de naranja va a la taza de leche
y la leche entra en la taza de jugo de naranja.
>> ALTAVOZ 4: ¿Tengo otra taza?
ALTAVOZ 1: Estoy tan bueno que lo preguntas, aunque habría sido mucho mejor material de archivo
si no hubieras preguntado.
Pero sí, podemos ofrecerle una tercera vaso 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 aplauso sería bueno para Laura.
Bien.
Tenemos un pequeño regalo de despedida para usted, pero quiero aprovechar estos.
Muchas gracias.
Así, un ejemplo sencillo, sin embargo, para demostrar que si lo hace
querer cambiar el contenido de dos contenedores,
o vamos a llamarlos las variables, necesitas algo de almacenamiento temporal
para organizar uno de los contenidos en la que en realidad se puede hacer el canje.
Así que de hecho, el código fuente aquí en C es representante de exactamente eso.
Si el zumo de naranja era una y la leche era b, y queríamos cambiar los dos,
usted podría intentar algo creativo mediante el vertido de una en la otra,
pero que probablemente no lo haría terminar particularmente bien.
Y por lo que utilizar una taza tercera, llamada que tmp, T-M-P por convención,
y poner el contenido del DO en que, a continuación, intercambiar una taza,
a continuación, poner la DO en el taza original, de ese modo
lograr, exactamente como se Laura hizo, el canje.
>> Así que vamos a hacer exactamente eso.
Déjame ir adelante y abrir hasta un ejemplo de que es
llama en realidad "no cambiar, "porque esto no es
como un simple hecho como usted podría pensar.
Así que en este programa, observe que Estoy usando stdio.h, nuestro viejo amigo.
Tengo el prototipo para swap ahí arriba, que
significa la aplicación de probablemente por debajo,
y vamos a ver lo que este principal programa va a hacer por mí.
La primera vez que declaro int x se uno, y int y consigue dos.
Así que pensar en aquellos como DO y leche, respectivamente.
Y entonces yo sólo tengo un printf diciendo x es esta
e y es esto, para que yo pueda ver visualmente lo que está pasando.
Luego he printf reclamando que estoy intercambiando los dos,
y luego imprimo un afirman que están intercambiados,
y yo imprimo x e y otra vez.
Así que aquí en intercambio es exactamente lo que hizo Laura,
y es exactamente lo que vimos en la pantalla hace un momento.
>> Así que vamos a seguir adelante y muy 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 parece exactamente igual, aunque de forma más técnica,
Laura lo hizo, no parece funcionar.
Entonces ¿por qué es eso?
Bueno, resulta que cuando escribimos un programa como este
que tiene tanto principal, puesto de relieve aquí, y luego otra función, como canje,
resaltado aquí, lo cual que llama, el mundo
se ve un poco de algo como estas 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 de variables como x e y que tiene principal,
y terminan ahí.
Pero si las llamadas principales de intercambio, y principal pasa a intercambiar dos argumentos, a y b,
jugo de naranja y la leche, que no es como entregándole el jugo de naranja y la leche
a Laura.
¿Qué hace una computadora, ¿es pasa copias del zumo de naranja
y copias de la leche a Laura, por lo que lo que es en última instancia dentro de esta bandeja
es el valor de uno y dos, o DO y leche, pero las copias de los mismos,
de manera que en este punto en la historia, hay
es DO y la leche en cada una de estas bandejas.
Hay un uno y un dos en cada una de estas bandejas,
y la función de intercambio es de hecho trabajando.
Les está intercambiando el interior de la segunda bandeja superior,
pero que el intercambio no tiene impacto.
Y en base a algunas principio básico que hemos
hablado antes, y de hecho Hace tan sólo unos minutos, lo que
podría explicar por qué el cambio a y b en el interior de canje
no tiene efecto en x e y, aunque Pasé x e y para la función de intercambio.
¿Cuál es la palabra clave aquí que podrí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ónde nuestra xey declarados.
Están declaran dentro de principal hasta aquí.
A y B, por su parte, están declarado efectivamente
dentro de swap, no del todo en las llaves, pero todavía
en el área general de swap.
Y así de hecho, a y b sólo existen dentro de esta bandeja
de Annenberg, este segundo trozo de código.
Así que estamos de hecho el cambio de la copia, pero eso no es realmente tan útil.
>> Así que echemos un vistazo a este nivel un poco más bajo.
Voy a volver a El directorio de origen,
y yo voy a primero zoom aquí, y sólo
para confirmar que estoy en esta ventana de terminal más grande,
el programa todavía se está comportando así.
Supongamos ahora que este no es intencional.
Claramente quería intercambio para trabajo, así que se siente como un bicho.
Ahora podía empezar a añadir un mucha printf de a mi código,
imprimir x aquí, y sobre aquí, una aquí, b por aquí.
Pero, francamente, eso es probablemente lo que que has estado haciendo durante un par de semanas
ahora, en horario de oficina y 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 de características que realmente puede
vamos a entender situaciones como éste, pero más convincente,
resolver problemas y encontrar errores.
Así que voy a hacer esto.
En lugar de ./noswap, estoy en su lugar va a correr GDB ./noswap.
En otras palabras, voy a dirigir mi programa no en Bash, nuestro nuevo amigo
hoy en día.
Voy a llevar mi programa noswap interior
de este otro programa llamado GDB, que es un depurador, que
es un programa que está diseñado para ayudar a que los seres humanos encontrar y eliminar errores.
Así que si golpeo Ejecute aquí, hay una cantidad atroz de texto
que realmente no tiene que leer.
Básicamente se trata de una distracción desde el símbolo, que
Voy a golpear Control-L levantarse 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 primera Los comandos que nos referíamos a introducir.
Y yo sólo voy a escribir correr hasta aquí dentro de GDB,
y de hecho funcionó mi programa.
Ahora hay un poco de adicional salidas de la pantalla como esta,
pero eso es sólo estar GDB anal y nos dice lo que está pasando.
Usted realmente no tiene que preocuparse sobre estos detalles ahora mismo.
Pero lo que es realmente bueno de GDB, si hago esto nuevo--
Control-L despeja el screen-- me dejes ir por delante y el tipo "romper principal", por lo tanto,
cuando pulso Enter, estableciendo lo que es llamado un punto de quiebre en noswap.c,
línea 16, que es donde GDB descubierto mi programa de realidad
Es decir, mi función es en realidad.
Esta ignoraremos por ahora pero 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 I dicho 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 programa paso a paso a paso a la velocidad humana,
no en Intel-inside tipo de velocidad.
>> Así que ahora cuenta esta línea aparece 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 incluso aunque esta interfaz blanco y negro
no es tan de usuario amable, esto significa
esa línea 16 no se ha ejecutado aún, pero está a punto de ser.
Así que de hecho, si escribo de impresión x, 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, si quiero ser presuntuoso, N para el próximo.
Pero cuando introduzco siguiente entro, ahora cuenta se pasa a la línea 17.
Así que, lógicamente, si he ejecutado lí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, si desee 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 hay a la derecha del signo igual.
Y ahora si escribo la próxima vez y de impresión y, debo ver 2.
También puedo ahora imprimir x de nuevo, y, francamente,
si me estoy poniendo un poco confundido en cuanto a donde estoy, puedo tipo de lista para la lista
y sólo ver un poco de contexto alrededor El punto que estoy realmente en.
Y ahora puedo escribir siguiente, 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, por mirando hacia atrás y hacia adelante en su código
o por el que se fuera del lado a lado tal vez, usted
veo que en realidad sólo soy pasando 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í el a 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 la superior y tipo de ejecución de nuevo.
Y está diciendo que el programa que 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 en intercambio, así que no me escriba a continuación.
Escribo paso, y ahora notarlo me ha saltado a la línea noswap.c 33.
Si vuelvo a gedit, lo que es la línea 33?
Esa es la primera real línea de código dentro de swap.
Lo cual es bueno, porque ahora puedo tipo 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, pero no han inicializado ningún valor,
así que lo que los bits que eres viendo aquí, aunque es
este gran negativo loco número, sólo significa
que esos son los restos de cierto uso anterior de que la memoria RAM,
aunque yo no tengo yo lo necesitaba todavía.
Así que ahora voy a seguir adelante y tipo siguiente, 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 primera Lo 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 problemas tres es un tutorial de clases en GDB,
pero se dan cuenta de que este es el comienzo de un vistazo a una herramienta que lo hará realidad
ayudarle a resolver problemas de manera mucho más eficaz.
Lo que estamos en última instancia vamos a hacer el miércoles
se comenzará a pelar unas pocas capas y eliminar algunas ruedas de entrenamiento.
Esa cadena cosa llamada que que hemos utilizado durante algún tiempo,
vamos a tomar poco a poco de que fuera de usted y empezar a hablar de
algo más esotéricamente conocido como char *,
pero vamos a hacerlo bien y suavemente al principio, a pesar de que los punteros,
como se les llama, se puede hacer un poco de cosas muy malas si se abusa,
mirando un poco de animación con plastilina nuestro amigo Nick Parlante de Stanford
Universidad, profesor en la computadora la 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]