[Powered by Google Translate] [Semana 7] [David J. Malan - Harvard University] [Esta es CS50. - CS50.TV] Está bien. Bienvenido de nuevo. Esto es CS50, y este es el comienzo de la semana 7. Un par de anuncios pequeños: Pset5 está ahora en progreso, o pronto lo serán, y déjenme decirles, sinceramente, este tiende a ser uno de los más difíciles de conjuntos de problemas del curso, así que vamos a mencionar esto ahora por lo que esta semana más que nunca no se espera hasta, digamos, la noche del miércoles o jueves por la noche a zambullirse Este es sin duda un conjunto de procesadores interesante. Creemos que es divertido. Si usted consigue realmente es totalmente correcta y luego puede impugnar la Bolsa de Nueva York llamada, usted tendrá la oportunidad de emparejar ingenios con una parte del personal del curso y algunos de sus compañeros de clase. ¿Qué es la Bolsa de Nueva York es una vez que su corrector ortográfico de trabajo, usted será capaz de ir a cs50.net después de ejecutar un comando, puramente optar en, y entonces la cantidad de tiempo y la cantidad de RAM y más que ha utilizado en su implementación se exhibirán aquí en la página de inicio del curso. Se dará cuenta de que una gran cantidad de estas personas aquí están listados como personal desde el fin de semana, el equipo pensó que sería divertido para tratar de superarse unos a otros. Así que darse cuenta de que el objetivo aquí no es superar a los empleados. Incluso yo no soy más que aquí, en el número 13. Puramente aceptas, pero es una oportunidad para ver lo poco RAM y qué pocos segundos de la CPU se puede utilizar vis-a-vis algunos de sus compañeros de clase.
Y voy a admitir que Kevin Michael Schmid, Actualmente, en el número 1 posición como uno de los TF, se trata de una aplicación que no es posible llamar dado que él está usando casi 0 RAM y casi 0 segundos para la carga. Así que vamos a cuidar desconectado Kevin. [Risas] Hay ciertas habilidades que Kevin está poniendo a prueba aquí. Una de las cosas que pensamos que haríamos ahora es demasiado CS50x es una semana en curso, y ustedes son una parte tan importante de este experimento como los estudiantes son. Les hemos pedido como parte de su pset0, que era similar al presentar un proyecto de Scratch de interés para ellos - un juego, una pieza de arte interactivo, la animación, o similares - un 1 - vídeo a 2 minutos, si quieren, saludando a todo el mundo y que son en realidad. Yo pensé en compartir con ustedes un par de los videos que se han presentado hasta el momento porque para nosotros, por el personal por lo menos, lo que realmente ha sido emocionante y inspirador ver a esta gente de todo el mundo - los países de todo el mundo - en sintonía, de todas las cosas, a un curso de informática en Internet, ya sea porque desean continuar sus estudios, quieren tomar su carrera en una nueva dirección, quieren llenar las lagunas de su propio conocimiento, por lo que algunas de las mismas razones que ustedes tal vez han estado aquí.
Así que le doy un tal estudiante aquí. Podrías subir el volumen un poco. Aquí está uno de 1-minuto presentaciones de nuestros estudiantes. ¡Hola, mundo. Soy un estudiante de ingeniería industrial aquí en Málaga, España. Estoy muy emocionado con este curso porque me gusta la informática, de verdad, y yo realmente aprecio que me pongo a explorarlo. Y el hecho de que puedo aprender lo mismo todo lo que ustedes hacen pero en lugar de estar en Harvard estoy en Málaga, lo maravilloso es eso? Bueno, soy Fernando, y esto es CS50. Nos vemos. [Risas] Otro clip en particular nos gusta, usted encontrará que este caballero Inglés no es tan fuerte. Parece que tenía una traducción automática, por lo que las propias traducciones son un poco imperfecta, pero este era uno de nuestros favoritos hasta ahora, así. [♪ ♪] ¡Hola, mundo. [Hablando en japonés] [Tengo que saludar en japonés porque mi Inglés es muy poco fiable.] [He entregado el mensaje a usted de la ciudad de Gifu, Japón.] [I puede ser un estudiante por primera vez en 20 años, como se puede ver.] [Estoy muy agradecido a la Universidad de Harvard, quien me dio esta oportunidad y EDX.] [El golf es una guitarra y dirigiendo mi cosa favorita.] [Risas] [♪ ♪] [¿Por qué cree usted que yo estaba tratando de asistir a una cs50x.] [Universidad de Harvard, es mi anhelo.] [Especialmente si estoy presencia lejana vivía en Japón.] [Yo quería probar inmediatamente consciente de la existencia de tal EDX cuándo.] [¿No te parece lo que no es relacionado con la edad de aprendizaje I.] [CS50 es mi anhelo. Mi nombre es Kazu, y esto es CS50.] [♪ ♪] [aplausos y vítores] Otro de los favoritos de nuestra era esta presentación aquí de alguien. [♪ ♪] [Malan] Google si no está familiarizado con este meme.
Y por último, un par de otros que he publicado que tal vez ganar el premio adorable. [Estudiantes] Aww! >> [Malan] Vamos a tener que escuchar. Este es corta, así que escucha con atención. [Speaker mujer] ¿Cuál es tu nombre? >> Louie. [Speaker mujer] ¿Qué es esto? >> [Risas] CS50. [Risas] [Malan] Él hizo dos tomas, sin embargo. Aquí vamos, la última. Mi nombre es Louie, y esto es CS50. [Risas] Esta es, pues, CS50x. ¡Gracias a todos aquellos de ustedes mientras sigue en casa que han sido hasta ahora participar. Hoy en día, podemos concluir nuestro análisis de estructuras de datos, al menos algunos de los más fundamentales, y luego continuamos nuestra conversación sobre HTML y programación web. De hecho, hemos pasado el pasado unos siete semanas buscando en los fundamentos de la programación - algoritmos, estructuras de datos y similares - y C, como usted puede haber experimentado hasta el momento, no es necesariamente el más accesible de los idiomas con el que poner en práctica algunas de esas ideas. Y así comienza esta semana y la próxima semana y luego el siguiente, que finalmente será capaz de hacer la transición de C, la cual se conoce generalmente como un lenguaje de nivel bastante bajo, a las cosas de nivel superior, entre ellos PHP, JavaScript, y similares, que veremos recurrir a las mismas lecciones que hemos aprendido a lo largo de las últimas semanas, pero usted encontrará que declarar cosas como matrices y tablas hash y de búsqueda y ordenación convertido en mucho más fácil porque las lenguas mismas que vamos a empezar a utilizar se hará más poderoso. Pero primero, una aplicación de árboles. Es muy común en estos días a tener que comprimir la información. ¿En qué contexto se desea comprimir algún tipo de información digital?
Si. >> [Estudiante] Cuando tenga que enviarlo a través de Internet. Sí, cuando usted desea enviar algo a través de Internet. Si desea descargar un archivo de gran tamaño, es ideal si alguien en el otro extremo ha comprimido el archivo con un formato zip o algo por el estilo de modo que va a enviar menos bits que de otro modo podrían ser transmitidos. Entonces, ¿cómo comprimir la información? Todo se reduce a la utilización de un menor número de bits que se requieren de forma predeterminada. Pero esto es una especie de cosa curiosa porque piense de nuevo a las semanas 0 y 1 cuando hablamos de ASCII y binario y hablamos de ASCII en particular como el uso de 8 bits para representar letras del alfabeto de modo que la letra A se representa por 65, minúsculas a es el número 97, y sin embargo representan el 65 o el 97, que está usando 7 u 8 bits. Pero el problema es que hay algunas letras en el alfabeto Inglés que no son tan populares como otros. Z no es tan popular, Q no es tan popular, pero A y E son muy populares. Y aun con todas estas cartas, por defecto el mundo utiliza el mismo número de bits, a 8. Entonces, ¿no hubiera sido más inteligente si en lugar de utilizar 8 bits para cada letra, incluso el más frecuentemente utilizado como Q y Z, ¿Y si usamos menos bits para A y E y S y las letras más populares y se utiliza más bits para las letras menos populares, la idea es optimizar vamos para el caso común, que es un tema en ciencias de la computación de tratar de optimizar lo que va a pasar la mayor parte del y pasar un poco de tiempo más, un poco más de espacio en las cosas que, sí, podría suceder pero no necesariamente con la frecuencia. Así que vamos a tomar un ejemplo.
Supongamos que queremos codificar información bastante eficiente. Es posible que haya crecido sin conocer un poco sobre el código Morse, y las probabilidades son que usted no sabía el código actual, pero se puede recordar que es por lo menos de esta serie de puntos y rayas. Se trata de una codificación bastante eficientes, y el aviso de que la letra más popular - por ejemplo, E - utiliza la más corta de pitidos. El código Morse es todo acerca de bip-bip-bip-bip-bip-bip y la celebración de los tonos ya sea por períodos cortos de tiempo o durante largos períodos de tiempo. E, como se indica en el punto, es un sonido súper corto, sólo pitido, y que representaría E. Por el contrario, T sería un pitido largo, como un pitido [prolonga sonido] y que representaría T. Pero eso es todavía muy corto, ya que, por el contrario, si nos fijamos en Z, para expresar Z va a ir beep, beep [más sonido], beep, beep [sonido corto]. Así que es más porque es menos común. Pero te tengo aquí es que el código Morse es un poco deficiente en que no es inmediatamente decodificable. Por ejemplo, supongamos que usted oye en algún extremo del cable de señal sonora [corto], beep [largo]. ¿Qué mensaje Acabo de recibir? Un punto y un guión. ¿Qué es lo que representa? [Estudiante] A. >> [Malan] Puede ser. También podría ser E seguido de T. En otras palabras, el código Morse, aunque se aprovecha este principio de optimizar el caso de la esquina, que no se presta a la capacidad de decodificación inmediata. Es decir, el ser humano que está escuchando o recibir estos puntos y rayas tiene que encontrar alguna manera de dónde están los saltos entre letras, porque si usted no sabe dónde están los saltos, puede confundir A para ET o viceversa.
Entonces, ¿qué podría hacer? En código Morse sólo podría hacer una pausa entre cada una de las letras. Pero es una especie de pausa en contra de toda la cuestión de acelerar las cosas. ¿Y si en vez de eso se acercó con un código en el que no fue esta mala situación donde E es un prefijo, por ejemplo, de A - en otras palabras, si pudiéramos asegurar que los patrones son todavía corto para las letras populares tiempo para que las cartas menos populares, pero no hay confusión posible? Un hombre con el nombre de Huffman años inventó este plan denominado codificación de Huffman que realmente aprovecha una de las estructuras de datos que hemos pasado un poco de tiempo hablando de La semana pasada, la de los árboles, los árboles binarios en concreto - un significado árbol binario que no tiene más de 2 niños. Tiene tal vez un hijo izquierdo, tal vez un hijo derecho, y eso es todo. Así que supongo que por el simple hecho de la discusión que alguien quiere enviar un mensaje que se parece a esto. Es una tontería pero está compuesto de As, Bs, Cs, Ds, y ES. Y si realmente contar todo lo de la As, Bs, Cs, Ds, y Es y se divide por el número total de cartas, esta pequeña carta aquí dice que el 45% de las cartas son Es, el 20% son As, 10% B, y así sucesivamente. En otras palabras, se supone que la cadena citada allí es sólo un mensaje que desea enviar. Le pasa a ser una tontería, así que puede utilizar como pocas cartas como sea posible, pero es de hecho el caso de que E sigue siendo el más popular, y B y C son las menos populares, por lo menos una de estas 5 letras del alfabeto. Entonces, ¿cómo hacemos para dar con una codificación, una codificación binaria, un patrón de 0 y 1 para cada una de estas cartas de tal manera que E es un patrón corto y tal vez B y C son ligeramente más largas patrones, de nuevo, la idea es que queremos utilizar menos bits mayor parte del tiempo y más bits sólo de vez en cuando. De acuerdo con la codificación Huffman, puede crear un bosque de árboles. Hay una especie de una historia aquí que supone árboles y también el proceso de construcción para arriba. Vamos a comenzar.
Propongo que se inicia con este bosque, por así decirlo, de 5 árboles, cada uno de los cuales es un árbol bastante estúpido. El árbol está compuesta de sólo un único nodo, representado aquí por un círculo. Así que cada una de estas cosas puede ser una estructura C y en el interior de la estructura C podría ser un flotador que representa el conteo de frecuencia y luego tal vez un char que representa la letra. Así que piensa en estos nodos como cualquier vieja estructura C, pero, por ahora, un nivel más alto. Se trata de un bosque de 5 árboles, cada uno de los que sólo tienen un solo nodo. ¿Qué Huffman propuesta es que empezamos a combinar esos árboles que tienen los más pequeños cuenta con frecuencia en los árboles un poco más grande mediante la conexión con un nodo raíz. Así que entre las cartas aquí, note que por comodidad he ordenados de izquierda a derecha, aunque esto no es estrictamente necesario, y observe que los más pequeños nodos Actualmente el 10% y el 10%. Así Huffman propuso que fusionar esos dos pequeños nodos en un árbol nuevo mediante la introducción de un nuevo nodo primario y luego dar ese padre un hijo izquierdo y un hijo derecho donde B es arbitrariamente la izquierda y C es arbitrariamente la derecha. Y luego Huffman propuso además que vamos ahora sólo piensa en el hijo izquierdo en uno de estos árboles siempre como está representado por 0 y el hijo derecho siempre como está representada por el número 1.
No importa si usted darles la vuelta, siempre y cuando usted es consistente. Así que ahora tenemos cuatro árboles en este bosque. Y digo cuatro, porque ahora el árbol de la izquierda - y no es tanto un árbol en el sentido de que crece de esta manera, es más como un árbol genealógico donde ahora el 0.2 es una especie de padre de los dos niños - cuenta de que en ese padre que hemos dibujado 0.2. Hemos añadido las cuentas de la frecuencia de los dos niños y dado el nuevo nodo a la suma total. Así que ahora sólo tiene que repetir este proceso. Encuentra los dos nodos más pequeños y luego unirlos en un nuevo árbol y repita el proceso. En este momento tenemos unos cuantos candidatos, el 20%, 15%, y otro 20%. En este caso, tenemos que romper el empate. Podemos hacerlo de forma arbitraria. Deberíamos hacerlo de forma coherente. En este caso, arbitrariamente a ir con el otro a la izquierda, y ahora fusionar el 20% y el 15% de darme un nuevo padre llamó un 35%, cuyo hijo izquierdo es 0, cuyo derecho es un niño, y ahora tenemos sólo tres árboles en el bosque. Usted tal vez pueda ver dónde va esto. Si repetimos esto un par de veces más, vamos a tener un solo árbol más grande, todos de cuyos bordes están etiquetados con 0s y 1s. Vamos a hacerlo de nuevo. 35% es la raíz de ese árbol. 20% y 45%, así que vamos a fusionar el 35% y 20%. Ahora tenemos este árbol aquí. Añadimos los que juntos, tenemos un 55%. Ahora sólo hay dos árboles en el bosque. Lo hacemos una vez final, y espero que matemáticamente todas las frecuencias se suman porque ya se les computa desde el primer momento para sumar 100%. Y ahora tenemos un árbol. Así que este es un árbol de Huffman. En cierto modo se tomó un tiempo para llegar allí verbalmente, pero la realidad es con un bucle for o con una función recursiva, usted podría construir esta cosa bastante rápido. Así que ahora tenemos un nuevo nodo, y todos estos nodos interiores han sido malloc'd, presumiblemente, a lo largo del camino. Así que ahora en la parte superior de este árbol que tenemos 100%, pero noto ahora tenemos un camino de esta nueva tatara-tatara-tatara-abuelo de todos los tatara-tatara-tatara-nietos todo el camino en la parte inferior, para todas las hojas.
¿Qué vamos a hacer ahora es proponer que para representar la letra E, nos limitaremos a utilizar el número 1. ¿Por qué? Porque si atravesamos este árbol desde la raíz hasta la última hoja conocida como E, seguimos un solo borde, el borde derecho, y eso ha marcado, por supuesto, en la parte superior derecha 1. Así que la implicación aquí para Huffman fue que codifica la E en binario sólo será el 1. Y eso es muy muy eficiente. No se puede realmente conseguir cualquier menor que eso. Por el contrario, A se va a representar, si se sigue la lógica, por qué patrón de bits en su lugar? 01. Así que para llegar a A, empezamos en la raíz y se va a la izquierda y luego a la derecha, lo que significa que seguimos a 0 y luego 1 a. Así que representará la letra A con el patrón de 0 y 1. Y ahora note que ya tenemos una propiedad de decodificación inmediata que no teníamos en código Morse. A pesar de que estos dos patrones son bastante corto - E es de 1 bit, 2 bits A es - cuenta de que no puede ser confundido uno o el otro, porque si usted ve un 1 que tiene que ser una E, si usted ve un 0, un 1 es obviamente tiene que haber una A. Del mismo modo, ¿cuál es D? 001. ¿Qué es C? 0001. ¿Y qué es B? 0000. Y de nuevo, porque todas las cartas que nos interesan son las hojas y ninguno de ellos son una especie de intermediarios en el camino de la raíz a las hojas, no hay riesgo de combinar codificaciones 2 letras los diferentes porque todos estos patrones de bits son deterministas. 0000 será siempre B. No hay ningún nodo en algún punto intermedio que podría confundir a una letra para el otro. Entonces, ¿cuál es la implicación en esta lista?
La carta más popular - en este caso E - ha conseguido la codificación más corta, A ha conseguido la codificación más corta siguiente, y B y C, que ya sabía desde el primer momento clase eran de los menos populares el 10% de frecuencia cada una, que han conseguido el mayor codificación. Y así, lo que esto significa es que si usted desea enviar un mensaje que se comprime a través de Internet o en un correo electrónico o similar, en lugar de utilizar ASCII estándar, puede enviar un mensaje codificado Huffman Que si usted desea enviar la letra E, que acaba de enviar un solo bit. Si desea enviar una A, envía 2 bits, 01, en lugar de enviar 8 bits seguido de otros 8 bits seguidas por otras 8 bits y así sucesivamente. Pero hay un gotcha aquí. No es suficiente sólo para la construcción de este árbol y luego iniciar el envío de Alice a Bob el patrón poco más corto, una cadena en ASCII, porque Alicia también tiene que informar de lo que Bob Bob si va a ser capaz de leer su mensaje comprimido? [Respuesta de los estudiantes inaudible] >> ¿Qué es eso? [Respuesta de los estudiantes inaudible] >> ¿De qué árbol es. O más específicamente, cuáles son esas codificaciones son, sobre todo porque durante esta historia hemos hecho un llamado a juicio en un punto. Recuerde que tuvimos que recoger arbitrariamente entre los dos nodos diferentes de 20%? Así que no es el caso de que Bob, el receptor, sólo puede reconstruir el árbol por su cuenta porque a lo mejor va a crear el árbol muy ligeramente diferente a Alice. Por otra parte, Bob ni siquiera sabe lo que el mensaje original es porque lo único Alice le está enviando, por supuesto, es el mensaje comprimido.
Así que la captura con la compresión de este tipo es que, sí, Alice puede ahorrar un montón de bits mediante el envío de 1 para E y 01 para A y así sucesivamente, pero ella también tiene que informar a Bob lo que la cartografía es entre las letras y los bits porque claramente no puede depender sólo de ASCII más si no estamos usando ASCII. Así que ella le puede enviar el árbol de alguna manera - escríbalo, guárdelo como datos binarios o algo así - o simplemente le enviaremos una hoja de trucos poco, un archivo de Excel, que muestra las asignaciones. Así que la eficacia de la compresión realmente asume que los mensajes que está enviando son bastante grandes, por lo menos de tamaño mediano, porque si usted está enviando un mensaje corto super, si lo que desea es enviar el mensaje BAD, que pasa a ser una palabra que puede significar aquí, B-A-D, usted está probablemente va a utilizar menos bits, pero el problema es si usted también tiene que informar a Bob lo que el árbol es o cuáles son esas codificaciones son, usted va a pesar más que probable que todos los ahorros de tener las cosas comprimidas, para empezar. Así que en realidad puede ser el caso que si se intenta comprimir incluso con algo así como formatos ZIP o archivo que esté familiarizado con - archivos muy pequeños, incluso archivos vacíos - a veces esos archivos pueden conseguir más grande y más pequeño no. Pero en realidad, esto sucede solamente para tamaños de archivo pequeños, por lo que no va a hacer un archivo de 2 gigabytes gigabyte ser; realmente estamos hablando bytes o sólo unos kilobytes de pareja.
Algunos programas como zip son lo suficientemente inteligentes para darse cuenta de que, "Vas a gastar más bits de compresión esto". "No dejes que me molesta comprimirlo para usted en todo." Así que esto es sólo una manera de comprimir entonces formato de texto. Se podría implementar algo como esto en C. Por ejemplo, aquí está la forma en que podría representar un nodo de este árbol donde tendremos una charla para el símbolo, un valor flotante para la frecuencia, y como hemos visto con nuestros otras estructuras de datos, 2 punteros, 1 para el hijo izquierdo, 1 a la derecha, cualquiera de los cuales puede ser NULL, pero si no, se refiere a un hijo izquierdo y un hijo derecho. Así que esta es, pues, la codificación de Huffman, y es una forma en que usted puede ir sobre la compresión de la información, y es sin duda uno de los más fáciles de implementar en el contexto de, por ejemplo, estructuras de datos de la semana pasada, aunque incluso los algoritmos más sofisticados existen que pueden hacer mutaciones aún más sofisticados de los datos. Cualquier pregunta entonces sobre los árboles, árboles binarios, o la compresión de texto? [Estudiante] ¿Hay alguna ambigüedad, como si se divide [inaudible] en 01, 011 entonces sería ambiguo, ¿no? [Inaudible] >> Buena pregunta. La ambigüedad. Voy a resumir al referirse a este cuadro aquí. Debido a que los caracteres que se están comprimiendo, las representaciones de, por definición de este algoritmo siempre permanecen las hojas, usted nunca va a querer utilizar el mismo patrón de bits para el prefijo de letras múltiples. En otras palabras, usted está preocupado, que suena, una ambigüedad que surja 001 por el que podría ser el comienzo de B o el inicio de C o algo así. Pero eso no puede ser así, porque note que todas las letras del alfabeto que estamos codificación se encuentran en las hojas.
La ambigüedad sólo puede surgir, como en el caso del código Morse, si, por ejemplo, C estaba en algún lugar a lo largo de la ruta desde la raíz a B. [Estudiante] Derecho. Así que en ese caso, por ejemplo A tiene 2 hojas. >> Say A tiene - Dilo de nuevo. [Estudiante] Say A tiene dos hojas, F y G, y luego G - >> bien. Pero no puedo. A sí mismo no podría tener hojas F y G porque esas letras F y G serían ellos mismos deja en algún lugar a la izquierda de B o el derecho de los E. Así, por definición, deben ser hojas. De lo contrario, usted está exactamente correcto, no hemos resuelto el problema que enfrenta el código Morse. Buena pregunta. Otras preguntas? Está bien. Esta noción de bits, resulta que hemos tenido a lo largo de todo el poder que en realidad no hemos utilizado a la hora de manipular estos 0s y 1s. Le preguntamos acerca de esto en uno de los conjuntos más tempranos de problemas: a saber, ¿cómo usted va sobre la conversión de mayúsculas a minúsculas o viceversa? O, más concretamente, uno de esos conjuntos de procesadores primera pregunta cantidad de bits que es lo que realmente tiene que dar la vuelta para cambiar a minúsculas una A o viceversa? He aquí un breve recordatorio de lo 65 y 97 parecen en binario. E incluso si esa cuestión ha desvanecido en especie de su memoria, se puede ver de nuevo aquí que la cantidad de bits que dar la vuelta para cambiar mayúscula a minúscula una? Sólo una.
Sólo se diferencian en una sola ubicación, el tercer bit de la izquierda. Mientras que A tiene un 010, un poco tiene un 011. Entonces, de alguna manera, tenemos que ser capaces de dar la vuelta sólo ese pedacito, y entonces podemos capitalizar o minúsculas. Hemos hecho esto en el pasado utilizando de forma efectiva si las condiciones y comprobar si la carta es entre el capital A y Z capital, entonces como salidas A - a + 26 o algo así. Probablemente hizo un cambio aritmético de las letras del alfabeto. Pero ¿y si pudiéramos dar la vuelta que solo bit? ¿Cómo usted va sobre la pena tomar un byte de bits, por lo que 8 bits 01000001 y 01100001 igual? Si tuviera esos patrones de bits, ¿cómo podemos hacer para cambiar sólo uno de ellos? ¿Qué ocurre si introducimos en amarillo aquí esta otro patrón de bits? Si hago las 0s enteros amarillo cadena excepto para el bit que quiero cambiar y luego introducir un nuevo operador conocido como operador bit a bit - bit a bit en el sentido de que opera en bits individuales, no en un byte completo o cuatro bytes de una vez. Esta barra vertical hay en amarillo sugiere que lo que si se tiene la representación de la mayúscula y OR bit a bit con la secuencia de bits de color amarillo? En otras palabras, piensa de nuevo a la discusión de las expresiones booleanas en Scratch y luego en C.
Haciendo un booleano o quiere decir que para ser verdad, ya sea la primera cosa que tiene que ser verdad o la segunda cosa que tiene que ser cierto o ambos tienen que ser verdad, y luego la salida resultante sí es cierto. En este caso aquí, ¿qué obtenemos si tomamos 0 "o" ed con 0? Falso o falso? Todavía es falso, por lo que la minúscula sigue siendo como se esperaba. ¿Y si en vez de eso hacer 1 o 0? Esto ahora permanece en 1, pero darse cuenta de lo que va a pasar aquí. Si empezamos con mayúscula y seguimos "o" los bits individuales como estamos haciendo aquí, 0 o el amarillo nos da lo que aquí abajo? Esto nos da 1. De hecho, supongo que no sabía lo que la versión en mayúsculas de un poco en realidad. Vamos a hacer esto. Permítanme pasar esto de nuevo por aquí. Vamos a hacer esto de nuevo. 0 o 0 me da 0. 1 ó 0 me da 1. 0 o 1 me da 1. 0 o 0 me da 0. El siguiente es 0, el siguiente es 0, el siguiente es 0. 1 ó 0 me da 1. Y así, aunque no sabía de antemano lo que era una minúscula, simplemente por "o" ing A con este patrón de bits que hemos presentado aquí en amarillo, puede minúsculas A mayúscula al lanzar esa parte. Se utilizó esta expresión semanas atrás: apretar un poco. ¿Cómo se puede realmente hacer eso mediante programación? Se utiliza lo que generalmente se llama una máscara, una secuencia de bits, que en este caso que pasa a tener este número aquí, y entonces "o" junto con este nuevo operador C, no | |, se utiliza un único | y que en realidad tendría esta respuesta aquí, porque ¿por qué? Este es el lugar 1s, 2s lugar, 16s 4s, 8s, 32s. Así que resulta que si usted toma una letra mayúscula A y O-lógico con el entero 32, porque el entero 32, cuando se mire en forma de bits, se ve así, que significa que usted puede darle la vuelta al poco de que usted realmente desea. Y del mismo modo - y vamos a ver el código en un momento - supongamos que queremos ir en otra dirección.
¿Cómo se pasa de minúsculas a capital para A? Qué poco hay que cambiar? Es el mismo. Queremos cambiar ese tercer bit desde un 1 a 0. Y ¿cómo podemos ir haciendo esto? ¿Cómo nos desviamos un poco? ¿Con qué patrón de bits podríamos apagar un poco? ¿Qué pasaría si una especie de invertir la máscara? Mientras que antes, hemos hecho todo el 0s máscara amarilla excepto para el bit que queríamos para encender, ¿Y si esta vez, hacemos el 1s máscara entera a excepción de la parte que se desea desactivar y luego usar lo que operador? ¿Qué pasaría si "y" las cosas? Vamos a echar un vistazo. Si ahora la vuelta a esto, supongamos que de nuevo puedo crear una máscara que es todo 1s excepto por el poco uno que desea desactivar y entonces en lugar de "o" los números blancos encima de la tapa con los números amarillos aquí abajo, ¿Y si en lugar de "y" ellos juntos? Se llama bit a bit y. Lógicamente, es la misma cosa que un booleano y. Esto me da 0 y 1 es 0. Así falso y lo verdadero es falso. Es cierto y verdadero es verdadero. Y aquí está la magia: Verdadero y falso es falso ahora, así que hemos apagado que poco. Y ahora el resto de la historia es algo sencillo. Debido a que el resto de la máscara es de 1 s, no importa lo que los números están en blanco. Cuando usted "y" algo de verdad, usted no va a cambiar su valor. Si bien es cierto, seguirá siendo cierto. Si era falso, seguirá siendo falso.
Pero la magia sucede cuando se toma algo que era cierto y luego "y" con falsa. Esto tiene el efecto de desactivar ese bit. Así que un poco críptico allí. Vamos a ver en realidad algo de código, que en realidad podría ser aún más críptico, pero vamos a echar un vistazo aquí a tolower. Si miro a tolower, al pasar de mayúscula a minúscula a, vamos a ver cómo podemos implementar este programa. Esto es importante, y no está tomando ningún argumento de línea de comandos. Estoy declarando un carácter c en la carta que el usuario va a escribir pulg Luego utilizo un do familiarizado bucle while para hacer sólo asegurarse de que el usuario definitivamente me da una A mayúscula B o C. .. Z, por lo que me da algo entre A y Z. Y ahora, ¿qué hago yo aquí? Yo soy "o" ing esto con 0x20, pero que en realidad es el mismo que - y volveremos a ello en un momento - 32. Así que de nuevo, 32 es el patrón de bits de aquí. ¿Por qué sabemos esto? Piense usted en la semana 0. Este es el lugar 1s, 2s lugar, 4s, 8s, 16s, 32s lugar. Así que este número amarillo pasa a ser 32. Luego puede tomar una carta como la charla aquí, bit a bit "o" es literalmente con el número 32, y ¿qué es lo que yo vuelva? La versión en minúsculas de que char. Hace un momento, sin embargo, me expresó esto en una notación de base diferente. ¿Qué representa esto? >> [Estudiante] Hexadecimal. [Malan] Esto le pasa a representar hexadecimal. No hemos hablado de hexadecimal casi nada, pero en realidad es conveniente en casos como este.
A pesar de que parece más complejo y aunque parece que 20 y no 32, resulta que en realidad es la notación hexadecimal súper cómodo porque en hexadecimal cada dígito después del 0x - y esto no significa nada; esto es sólo convención humana que dice aquí viene un número hexadecimal - cada uno de estos dígitos, el 2 y luego el 0, se puede representar con exactamente 4 bits. Así que si hacemos esto, permítanme abrir un editor de texto aquí - extraño autocomplete - si hacemos un editor de texto poco aquí, el número 0x20 quiere decir aquí es de 4 bits, aquí hay otros 4 bits. Vamos a hacer los 4 bits más a la derecha en primer lugar. 0 cuando se representa con 4 bits es lo que? Super fácil. Así todos 0s. Así que 4 bits como 0. ¿Cómo se puede representar 2? Ha sido un tiempo desde que hice esto, pero es 0100. Así que este es el lugar 1s, este es el lugar 2s, y entonces no importa lo que los otros lugares son. En otras palabras, en hexadecimal se podría decir 0x20, pero si luego pensar en lo que es el 2 y cómo se representan en binario, ¿cuál es el 0 y como se representa en binario, las respuestas a estas preguntas son esto y lo otro, respectivamente. Así sucede 0x20 para representar este patrón de 8 bits, que es precisamente la máscara que queríamos. Así que esto es por el momento sólo un ejercicio intelectual, pero la realidad es que en el código es generalmente más común escribir constantes como esta en hexadecimal porque entonces el programador puede fácilmente relativamente, incluso si se requiere un poco de papel y un lápiz, averiguar lo que el patrón de bits es porque uno no puede expresar 0s y 1s normalmente en el código. No puedes ir a 00010 y así sucesivamente.
Tienes que elegir las notaciones decimal o hexadecimal u octal o de otro tipo. La mayoría de la gente tiende a escoger hexadecimal simplemente para que cada dígito representa 4 bits y usted puede hacer este cálculo rápido. Y voy a agitar la mano en toupper, que es casi lo mismo, se ve casi idéntico. ToUpper pasa a utilizar el operador o no, sino más bien este tipo y df. ¿Qué df representa? df? ¿Alguien? >> [Estudiante] 255. 255? No 255. Eso sería ff. Vamos a dejar este como un poco de ejercicio. Pero si usted va de 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 y luego lo que viene después de las 9? Estamos un poco fuera de dígitos decimales, pero en hexadecimal qué viene después de 9? [Estudiante] a. Así >> a, b, c, d. Usted puede calcular a partir de ahí qué patrón de bits d en realidad representa. Y si hacemos los cálculos, veremos que la máscara se llega a la espalda es idéntica a ésta. Esto es f, todos los 1, y esto es d. Así df representa esa máscara. Está bien. Y por último, para no hacer las cosas de sonido super, super técnico, pero supongamos que queremos escribir un programa que hace esto. Déjenme seguir adelante y hacer binaria, que es un programa en un archivo llamado binary.c. Y ahora déjame correr binario y me da un número entero no negativo. Empecemos fácil y escriba 0. Esto ahora es un programa que imprime un entero en su representación binaria. Así que si puedo jugar a este juego de nuevo y escribir en sólo 1, que debería obtener una representación de 32-bit de 1. Si lo hago de nuevo con 2, me entiendo. Si lo hago 7, que debería obtener una 1s pocos al final y así sucesivamente. Resulta que yo menciono porque con operaciones a nivel de bits en realidad se puede hacer una cosa así. Puede crear estas máscaras de forma dinámica. Echa un vistazo a este ejemplo una final que involucre operaciones bit a bit. Aquí está la primera parte del código, solicitar al usuario un número, y se insiste en que usted me da un entero no negativo. Así que es una especie de cosas de la vieja escuela. Pero aquí hay algo que es bastante interesante.
¿Cómo hago para imprimir un número en binario? Por primera iteración de qué a qué? ¿Cuál es el tamaño de un int típicamente, al menos en el aparato? >> [Estudiante] 4. Es 4. Así que 4 * 8 es 32 - 1 es 31. Así que si yo estoy empezando a contar a partir del 31, que representa, resulta, sólo conceptualmente, el bit 31 o el bit de orden más alto, que es este chico por aquí, mientras que esto va a ser de 0 bits. Así que este es el bit 01 ... bit 31. Entonces, ¿qué está haciendo este código? Observe este bucle for, aunque parece críptica, es simplemente iterar desde el 31 hasta 0. Eso es todo. Así que la parte interesante ahora debe estar en estas 5 líneas aquí. Nótese que en esta línea estoy declarando una variable llamada máscara para ser coherente con nuestra historia de estos números amarillos. Y entonces, ¿qué hace esto? Este es otro operador de bits que no hemos visto antes, lo más probable. Es el operador de desplazamiento a la izquierda. Este operador hace esto. Aquí está el número 1, y si lo haces me fui turno, desviación a la izquierda, ¿qué piensa usted que tiene el efecto de hacer a esa persona 1? Literalmente cambiando otra vez. Así que si el número 1 es lo que tiene a la izquierda y comienza inicializando i al 31, lo que vamos a hacer? Va a tomar este número 1 y cambiarlo 31 plazas por aquí. Y porque obviamente hay ningún otro dígito detrás de él, los que por defecto serán reemplazados por 0. Por lo que usted comience con el número 1, que por supuesto tiene este aspecto - y déjame llamar aquí en el centro. Y luego, a medida que cambian las cosas a la izquierda, este hombre esencialmente va de esta manera. Pero tan pronto como lo hace, un 0 se llena pulg Si lo cambian por segunda vez, va de un lado a otro 0 se llena pulg
Usted lo cambie de nuevo y luego otro 0 se llena pulg Así que si usted hace esta cosa de 1 << i 31 plazas, se llega a una máscara que es 32 caracteres de longitud, más a la izquierda de la que es un 1, todo el resto de los cuales son un 0. Y resulta que, en un aparte, cambiando un número a la izquierda como éste también por casualidad, ya veces conveniente, tiene el efecto de hacer lo que a ese número? >> [Estudiante] duplicarlo. Duplicar porque cada una de las columnas - el lugar 1s, 2s lugar, lugar 4s, Lugar 8s, 16s lugar - son todos duplicación a medida que avanza hacia la izquierda. O más bien, al cambiar el 1s vas a terminar duplicando el valor del número. Usted puede terminar encima de hacer transformaciones interesantes de dígitos sobre todo al cambiar de esta manera por potencias de 2. Entonces, ¿cómo funciona esto? Esto entonces me da una máscara que es de todos 0s a excepción de una en una, precisamente el lugar en el que lo quiere, y entonces esta expresión, que es robado de toupper.c, está diciendo simplemente tomar el número n de que el usuario escribió, "Y que" con esa máscara, y lo que vas a conseguir? Usted va a obtener un 1 si hay un 1 en ese lugar enmascarado, o usted va a obtener un 0 si no lo es. Y así todo el programa de manera efectiva es que tiene un bucle, y crea una máscara con un 1 por aquí, luego un 1 por aquí, luego un 1 por aquí, y utiliza este truco AND bit a bit a decir es que hay un bit 1 en la entrada del usuario en esta lista?
¿Hay un bit 1 en la entrada del usuario aquí? Y si es así, literalmente imprimir 1, de lo contrario imprimir 0. Estamos haciendo esto con ints sólo porque es por eso que estamos haciendo 32 bits en lugar de 8, pero lo que hemos introducido es éste AND bit a bit, bit a bit OR esto, y este operador de desplazamiento a la izquierda, que no suelen ser terriblemente útil, pero resulta que puede ser. De hecho, si usted fuera a representar algo así como un conjunto de valores booleanos sólo para representar verdaderas o falsas, suponga que desea hacer un seguimiento de si es o no una habitación llena de 300 estudiantes está presente, puede declarar una matriz de tamaño 300 de tipo bool para que usted obtenga 300 Bools, y se puede configurar para cada cierto si alguien está aquí y false en caso contrario. ¿Por qué es que la representación en esa estructura de datos ineficiente? ¿Qué hay de malo en el diseño de esa estructura de datos, una matriz de 300 Bools? ¿Qué es un bool, de hecho, debajo de la capucha? Esto, también, es algo que no puede ser conocido. Resulta que no hay bool. Recuerde que tipo de creado que con el archivo cs50.h, que se incluye de serie bool. C es un poco tonto, sin embargo, cuando se trata de bool. Se utiliza 8 bits para representar cada bool, que es totalmente antieconómico porque, obviamente, ¿cuántos bits se necesita para representar un bool? A sólo 1. Así que resulta que si usted ahora tiene la capacidad de los operadores a nivel de bits para manipular bits individuales, incluso en un char, incluso en un solo byte, resulta que podría reducir la memoria necesaria para representar algo estúpido como la estructura de los datos de asistencia labrado por un factor de 8. En vez de usar ocho bits para representar verdaderas o falsas, que, literalmente, podría utilizar un mediante el uso de un solo byte por cada ocho alumnos de la clase y alternar 0 a 1 los bits individuales utilizando este tipo de bajo nivel trucos. Eso realmente poner fin a la energía. ¿Hay alguna pregunta acerca de las operaciones a nivel de bits?
Si. >> [Estudiante] ¿Existe un operador exclusivo o? Sí. Hay un operador exclusivo o que se parece a esto, ^, el símbolo de la zanahoria, lo que significa que sólo es lo primero o lo segundo puede ser un 1 para que la salida sea un 1. También hay un no, ~, lo que le permitirá invertir un 0 a un 1 o viceversa, así. Y también hay un operador de desplazamiento a la derecha, >>, que es lo contrario de la que vimos. Está bien. Vamos a tomar las cosas ahora a un nivel más alto. Empezamos hablando de texto y luego comprimir y que representa el texto con un número menor de bits; hablamos un poco acerca de cómo podemos empezar a manipular las cosas a un nivel de bit a bit. Vamos ahora amplía hasta 10.000 pies a la representación de las cosas más complejas, como gráficos. Aquí tenemos una bandera de Alemania, aquí tenemos uno de Francia. Estos pueden ser representados en formatos de archivo que puede saber - GIF, por ejemplo. Si alguna vez has visto una imagen en la Web que termina en. Gif, Este es un formato de intercambio de gráficos. Estas dos banderas especie de aquí se prestan a la compresión por lo que tal vez obvia razón? >> [Respuesta de los estudiantes inaudible] Hay un montón de repetición, ¿no? Para enviar bandera de Alemania, piensa en esto como una imagen en la pantalla En la época de su Scratch. Usted recordará que hay píxeles individuales o puntos que componen una imagen.
Hay toda una fila de puntos negros y otro conjunto de filas de puntos negros. Hay un montón de filas de puntos negros que podríamos ver si realmente el zoom, tanto como cuando el zoom en la cara de Rob en Photoshop. Tan pronto como llegamos más y más y más profundo en la imagen, que comenzó a ver la pixelación, todos los cuadrados que componen el ojo en ese caso. Lo mismo pasa aquí. Si el zoom un poco, verá puntos individuales. Bueno, esto es un poco un desperdicio de bits. Si un tercio de la bandera es de color negro y un tercio de la bandera es de color amarillo y así sucesivamente, ¿por qué no podemos comprimir de alguna manera esta bandera? E incluso la bandera francesa puede ser comprimido a pesar de que el patrón es un poco diferente. Resulta que el formato de archivo GIF es un formato de compresión sin pérdida, lo que significa que usted puede tomar una imagen como la bandera alemana aquí, usted puede tirar mucho de sus bits sin sacrificar la calidad. Esto está en contraste con algo como JPEG, con la que la mayoría de nosotros somos probablemente más familiar. Fotos de Facebook y Flickr fotos y similares casi siempre se guardan como archivos JPEG cuando están cargados, pero es una pérdida JPEG - formato mediante el cual usted se deshaga de bits - con pérdidas pero también tiro de calidad. Y así, si comprime las fotos con Photoshop o subirlas a Facebook o llevarlos a un teléfono realmente horrible, usted sabe que la imagen empieza a ser muy desiguales y pixelado, y eso es porque está siendo comprimido por el ordenador o por teléfono por, literalmente, tirar información de distancia. Pero GIF es sorprendente, ya que puede utilizar menos bits de lo que podría por defecto sin perder ninguna información.
Y es esencialmente lo hace como sigue. En lugar de almacenar en un archivo como un archivo BMP haría un triple RGB para el negro, negro, negro, negro, negro, negro, negro, negro, negro, negro, negro, negro y así sucesivamente, más bien, el formato GIF se va a decir, "Negro" y luego, "Repita esto 100 veces", o algo por el estilo. "Negro, repetir esto 100 veces, negro, repetir esto 100 veces ..." "Amarillo, repetir esto 100 veces." Y así lo recuerda, esencialmente, el píxel más a la izquierda y luego codifica de alguna manera la noción de repetir ese píxel y otra vez. Así GIFs entonces pueden comprimir sin perder ninguna información. Pero si tuviera que adivinar, si ese es el algoritmo que GIFS uso, que de estos indicadores, a pesar de que son idénticas en tamaño, va a ser menor cuando se guarda en el disco como un GIF? >> [Estudiante] Alemania. Alemania va a ser más pequeño? ¿Por qué? [Estudiante] Porque te lo repiten muchas, muchas veces horizontalmente y luego repetir en otra ocasión. >> Exactamente. Porque la gente que inventó GIF sólo tipo de arbitrariamente decidió que la repetición será aprovechado horizontal y lateralmente no. No hay repetición mucho más lateralmente aquí en el pabellón alemán de la bandera francesa. Así que si realmente abrir una carpeta en mi disco duro que tiene estos GIFs, en realidad se puede ver que la bandera alemana aquí es de 2 kilobytes y el francés es de 4 kilobytes. Le pasa a ser una coincidencia que uno es el doble de la otra, pero es de hecho el caso de que la bandera francesa es mucho más grande.
A pesar de que estamos hablando aquí acerca de los gráficos, las mismas ideas pueden aplicarse a no cosas como banderas sino imágenes que son un poco más complejas. Si se toma una fotografía de una manzana, seguro que hay un montón de duplicación allí, por lo que de alguna manera podría recordar que el fondo predeterminado es azul y no, como la imagen de la derecha indica, Hay que recordar que el color de cada píxel en la imagen. Así que podemos tirar trozos de distancia sin perder información. La manzana sigue pareciendo lo mismo. En este ejemplo aquí, puede ver lo que sucede en una película. Estos representan la vieja escuela rollos de película por lo que en la imagen de arriba hay Tiene una conducción RV pasado una casa y un árbol. Y como que van conduce más allá de izquierda a derecha, lo que, evidentemente, no está cambiando? La casa no va a ninguna parte, y el árbol no va a ninguna parte. Lo único que se mueve es la furgoneta en este caso. Así como fondo Sin cambios indica, lo que puede hacer en las películas es igualmente justo desechar la información que no cambia entre fotogramas. Esto se conoce generalmente como la compresión intertrama por lo que si esta estructura se ve casi idéntico a éste, no hay que preocuparse almacenamiento en disco de la información idéntica en estos cuadros intermedios, vamos a utilizar fotogramas clave sólo de vez en cuando que en realidad almacenar esa información redundante así como un poco de cordura comprobar.
Por el contrario, otro enfoque para la compresión de vídeo es en este ejemplo y segunda más baja aquí, donde en lugar de almacenar 30 imágenes, ¿por qué no acaba de almacenar 15 imágenes por segundo en su lugar? Más que el tipo de película que fluye muy bien, perfectamente, puede ser que parezca que está tartamudeando un poco, un poco de la vieja escuela, pero el efecto neto será utilizar bits de un número mucho menor de lo que podría ser necesaria. Entonces, ¿dónde nos deja esto entonces? Eso fue un poco de un lado a otro donde se puede ir con la compresión. Para saber más sobre eso, tome una clase como CS175 aquí. Aquí hay otro ejemplo en video. Si la abeja es la única cosa en movimiento, realmente se puede desechar la información en los cuadros medios porque la flor y el cielo y las hojas no están cambiando. Pero vamos a considerar ahora una última cosa. En los próximos 5 minutos, dejar atrás para siempre C en clase? Sí. No en los conjuntos de procesadores, sin embargo. Última historia sobre C y luego llegamos a cosas muy sexy participación de HTML y Web y woo hoo. Está bien. Aquí vamos. Esa es la motivación. Resulta que todo este tiempo en que hemos estado escribiendo programas que se ejecutan Clang. Y Clang, hemos dicho desde la primera semana más o menos, tiene el código fuente y lo convierte en un código objeto. Se tarda C y la convierte en 0 y 1. He especie de estado mintiendo durante unas semanas, ya que no es tan simple como eso.
Hay muchas más cosas debajo de la capucha cuando se ejecuta un programa como Clang. De hecho, el proceso de compilación de un programa realmente puede ser resumida, Como se puede recordar de vídeo de Rob en compiladores, en estos 4 pasos: pre-procesamiento, elaboración propia, el montaje y la vinculación. Pero en la clase y la mayoría de las personas en el mundo típicamente resumir todos estos pasos simplemente como "compilar". Pero si empezamos con el código fuente de este tipo, recuerdo este es quizás el programa más simple C que hemos escrito hasta ahora, recordemos que cuando se compila termina pareciéndose a esto. Pero en realidad hay un paso intermedio, y los pasos son los siguientes. En primer lugar hay una cosa en la parte superior de esta y la mayoría de nuestros programas, # Include ¿Qué es # include hacer por nosotros? Es más o menos copias y pega el contenido del archivo stdio.h en mi para que ¿por qué? ¿Por qué se preocupan por el contenido de stdio.h? ¿Qué hay ahí de interés? Printf la declaración, su prototipo, por lo que el compilador sabe a qué me refiero cuando menciono esta función printf. Así que el paso 1 en la compilación es pre-procesamiento, por lo que un programa como Clang o algún programa de ayuda que viene con Clang lee el código de arriba a abajo, izquierda a derecha, y cada vez que ve un símbolo # seguido de una palabra clave como include, realiza esta operación, copiar y pegar en este caso stdio.h en su archivo. Ese es el paso 1. Entonces usted tiene una mucho más grande archivo de C debido a la gran copia, pega trabajo que acaba de pasar.
2 Paso ahora está compilando. Pero resulta que lleva compilar el código fuente que se ve así y se convierte en algo que se parece a esto, que para aquellos que están familiarizados se llama? >> [Estudiante] Asamblea. Idioma >> Asamblea. Esto es realmente algo si se toma CS61 podrás sumergirte en en más detalle. Esto es lo más cercano que se puede llegar a escribir 0s y 1s usted mismo pero escribir las cosas de tal manera que aun hace por lo menos un poco de sentido. Estas son las instrucciones de la máquina, y si desplácese hacia abajo a la función principal aquí, cuenta de que existe esta instrucción de inserción, mueva la instrucción, restar instrucción, llamar a la instrucción, y así sucesivamente. Cuando usted oye que el equipo tiene Intel en el interior, usted tiene una CPU Intel en su Mac o PC, ¿qué significa eso? Una CPU viene integrado por empresas como Intel entender ciertas instrucciones. No tienen idea de lo que son las funciones tales como el canje o principal están per se, pero sé lo muy bajo nivel instrucciones como sumar, restar, empujar, moverse, llamar, y así sucesivamente son. Así que cuando se compila código C en lenguaje ensamblador, su muy fácil de usar con aspecto de códigos se convierte en algo que se parece a esto, que literalmente se mueve bytes o 4 bytes en torno a estas pequeñas unidades de entrada y salida de la CPU. Pero finalmente, cuando Clang está dispuesta a asumir esta representación de su programa en 0 y 1, entonces el paso se llama montaje sucede, y esta vez todo sucede en un abrir y cerrar de ojos cuando se ejecuta Clang. Empezamos aquí, envía un archivo como este, y luego lo convierte a estos 0s y 1s. Y si quiere volver en algún momento y en realidad ver esto en acción, si voy a hello1.c--este es uno de los primeros programas que vimos - normalmente queremos compilar este con hello1.c Clang y esto nos daría a.out. Si por el contrario en su lugar darle la opción-S, lo que se obtiene es hello1.s y que realmente va a ver el lenguaje ensamblador.
Estoy haciendo esto por un programa muy corto, pero si vuelves por Scramble o Recuperar o cualquier programa que usted ha escrito y sólo por curiosidad quieren ver lo que realmente parece, lo que en realidad se alimenta a la CPU, puede utilizar esa opción-S con Clang. Pero entonces, por último, todavía hay un gotcha. Éstos son el 0 y 1 que representa mi implementación de hola, mundo. Pero he utilizado de otra persona en función de mi programa. Así que, aunque el proceso ha sido tomo hello.c, que se compila en código ensamblador, y luego se ensamblan en 0s y 1s, el único 0s y 1s que se generan en este punto en el tiempo son las que resultan de mi código. Pero la persona que escribió printf, que compila su código hace 20 años y está ahora instalado en algún lugar en el aparato, por lo que de alguna manera tiene que combinar sus 0s y 1s con mi 0s y 1s, y que nos lleva a la cuarta y última etapa de compilación, conocida como la vinculación. Así que en el lado izquierdo tenemos la misma imagen exacta como antes: hello.c se convierte en código ensamblador convierte en 0s y 1s. Pero recordemos que he utilizado el estándar de E / S de la biblioteca en mi código, y eso significa que en algún lugar en el equipo hay un archivo llamado stdio.c o por lo menos la versión compilada de los mismos porque alguien hace algunos años compilado stdio.c en código ensamblador y luego un montón de 0s y 1s. Esto es lo que se conoce como estática o una biblioteca dinámica. Es algún archivo que se sienta en algún lugar del aparato.
Pero, por último, tengo que llevar a mi 0s y 1s y esa persona 0s y 1s y de alguna manera ellos se unen, literalmente combinar los 0s y 1s en un solo archivo llamado a.out o hello1 o lo que llamé a mi programa de modo que el resultado final tiene todos los 1s y 0s que debe componen mi programa. Así que todo este tiempo este semestre cuando usted ha estado usando Clang y más recientemente de ejecutar make para ejecutar Clang, todos estos pasos se han ido sucediendo una especie de instantánea pero muy deliberadamente. Y así, si continúa en ciencias de la computación, es decir, CS61, esta es la capa que usted continuará pelar fuera de allí habla de eficiencia, implicaciones de seguridad, y similares de estos detalles de nivel inferior. Pero con eso, estamos a punto de dejar atrás C. Vamos a seguir adelante y tomar nuestro hijo de 5 minutos de descanso ahora, y cuando volvamos: la Internet. Está bien. Estamos de vuelta. Ahora comenzamos nuestra mirada no sólo en HTML, ya que, como se verá, HTML en sí mismo es realmente muy simple pero realmente en la programación web en general, la creación de redes en general, y cómo todas estas tecnologías se unen que nos permita crear programas mucho más sofisticadas sobre el Internet que hasta ahora hemos podido en estas ventanas en blanco y negro. De hecho, en este punto en el semestre a pesar de que pasará un tiempo relativamente menos en PHP, HTML, CSS, JavaScript, SQL y más, mayoría de los estudiantes terminan haciendo trabajos finales que son basado en la web porque, como se verá, el fondo que ahora tenemos en C es muy aplicable a estos lenguajes de alto nivel.
Y a medida que empiezas a pensar en su proyecto final, que, al igual que 0 Serie de problemas, donde se alentó para hacer casi cualquier cosa de su interés en Scratch, El proyecto final es tu oportunidad de tomar su nuevo conocimiento y comprensión con C o PHP o JavaScript o similar para dar una vuelta y crear su propio pedazo de software para que el mundo vea. Y a las semillas que con ideas, saber que puedes ir aquí, projects.cs50.net. Cada año, solicitar ideas de los profesores y el personal y grupos de estudiantes en el campus sólo para que presenten sus ideas para cosas interesantes que podrían ser resueltos utilizando las computadoras, uso de sitios web, utilizando el software. Así que si usted está luchando para llegar a una idea propia, por todos los medios desplazarse a través de las ideas allí desde este año y el pasado. Está perfectamente bien para hacer frente a un proyecto que ha sido abordado antes. Hemos visto muchas de las aplicaciones para ver el estado de lavandería en el campus, muchas de las aplicaciones para navegar por el menú del comedor, muchas de las aplicaciones de la navegación por el catálogo de cursos y similares. Y, en efecto, en una conferencia futuro y en futuros seminarios, que le dará a conocer algunas API a disposición del público, tanto comercialmente disponible así como aquí CS50 disponible en el plantel para que tenga acceso a los datos y entonces puede hacer cosas interesantes con él. Así que más sobre los proyectos finales en pocos días cuando soltamos el pliego de condiciones, pero por ahora, saber que se puede trabajar solo o con uno o dos amigos en la mayoría de cualquier proyecto de su interés. La Internet. Ve y saca su laptop, usted va a facebook.com, por primera vez, no haber registrado recientemente, y pulse Enter. ¿Qué pasa exactamente?
Cuando se pulsa Enter en el equipo, un montón de pasos iniciar una especie de magia sucede. Así que aquí, en el servidor de izquierda, web como Facebook está aquí a la derecha, y de alguna manera está utilizando este lenguaje llamado HTTP, Hypertext Transfer Protocol. HTTP no es un lenguaje de programación. Es más bien un protocolo. Se trata de un conjunto de convenciones que los navegadores web y servidores web utilizan cuando comunican entre sí. Y lo que esto significa es lo siguiente. Al igual que en el mundo real, tenemos estas convenciones donde si cumple algún humano por primera vez, si no te importa me seguía la corriente aquí, Yo iría de ti, dicen: "Hola, mi nombre es David." >> Hola, David. Mi nombre es Sammy. "Hola, David. Mi nombre es Sammy". Así que ahora que hemos participado en este tipo de protocolo humano tonto donde he iniciado el protocolo, Sammy ha respondido, nos hemos dado la mano, y la transacción se ha completado. HTTP es muy similar en espíritu. Cuando su navegador solicita web www.facebook.com, lo que tu navegador está haciendo realmente está extendiendo su mano, por así decirlo, al servidor y está enviando un mensaje. Y ese mensaje es típicamente algo como usarlo - ¿Qué quieres conseguir? - me la página de inicio, que normalmente se indica por una sola barra en el extremo de un URL. Y para que lo sepas qué idioma estoy hablando, el navegador te voy a contar que estoy hablando versión HTTP 1.1, Y también por si acaso, voy a decirte que el host que quiero que la página de inicio de es facebook.com. Normalmente, un navegador web, sin el conocimiento de ti, el ser humano, le envía este mensaje a través de Internet en las que simplemente escribir www.facebook.com,
Intro en su navegador. ¿Y qué significa responder con Facebook? Responde con algunos detalles crípticos de aspecto similar, pero también mucho más. Déjame ir adelante a la página principal de Facebook aquí. Esta es la pantalla que la mayoría de nosotros probablemente nunca vea si permanecer conectado todo el tiempo, pero esto es de hecho su página de inicio. Si hacemos esto en Chrome, observe que usted puede levantar estos menús contextuales pequeños. Con Chrome, ya sea en Mac OS, Windows, Linux, o similar, Si controlas clic o clic con el botón izquierdo, normalmente puede levantar un menú que tiene este aspecto, donde algunas opciones esperan, uno de los cuales es de origen Vista de página. También puede obtener normalmente a estas cosas por ir al menú Ver y husmeando. Por ejemplo, aquí en Ver, Developer es la misma cosa. Voy a seguir adelante y mirar en la fuente Vista de página. Lo que vas a ver es el código HTML que Marcos ha escrito para representar facebook.com. Es un desastre completo aquí, pero vamos a ver que esto tiene sentido un poco más en poco tiempo. Pero hay algunas pautas aquí. Permítanme desplácese hacia abajo para cosas como esta. Esto es difícil para un ser humano de leer, pero nota que hay este patrón de paréntesis angulares con palabras clave como opción, palabras claves como valor, algunas cadenas entre comillas. Aquí es donde, cuando se registró por vez primera, se especifica cuál es su año de nacimiento es. Ese menú desplegable de años de nacimiento es de alguna manera codificado aquí en este lenguaje llamado HTML, HyperText Markup Language. En otras palabras, cuando el navegador solicita una página web, habla esta convención llamado HTTP. Pero, ¿qué facebook.com responder a esa petición con?
Responde con algunos de estos mensajes crípticos, como veremos en un momento. Pero la mayor parte de su respuesta está en la forma de HTML, HyperText Markup Language. Ese es el verdadero lenguaje en que está escrito de una página web. Y lo que un navegador web realmente es, entonces, a la recepción de algo que se parece a esto, lee de arriba a abajo, de izquierda a derecha, y cada vez que lo ve uno de estos paréntesis angulares seguido de una palabra clave como opción, se muestra que el lenguaje de marcado de la manera apropiada. En este caso, se podría visualizar un menú desplegable de años. Pero de nuevo, esto es un completo desastre a la vista. Esto no es porque los desarrolladores de Facebook 0 para manifestar 5 por estilo, por ejemplo. Esto se debe a que la mayor parte del código que se escribe es, de hecho, muy bien escrito, bien documentado, con una sangría bien, y similares, pero las máquinas de cursos, ordenadores, navegadores realmente no les importa un bledo si el código está bien labrada. Y, de hecho, es totalmente antieconómico para golpear la tecla de tabulación todas esas veces y poner todos los comentarios a través de su código y de elegir los nombres de variables descriptivos realmente porque si el navegador no le importa, todo lo que estamos haciendo al final del día es perder bytes.
Así que resulta que la mayoría de los sitios web es hacer a pesar de que el código fuente para facebook.com, para cs50.net y todos estos otros sitios web en Internet son bien escrito y bien documentado y bien sangrados y similares, por lo general antes de que el sitio web se coloca en la Internet, el código se minified, por lo que el HTML y el CSS - algo más que pronto lo veremos - el código JavaScript pronto veremos se comprime, por lo que los nombres largos de variable de convertirse en X e Y y Z, y todos los que los espacios en blanco que hace que todo parezca tan legible es todo tirado, porque si se piensa en ello de esta manera, Facebook tiene una página de mil millones de visitas al día - algo así de loco - por lo que si un programador para estar anal pulsa la barra espaciadora una vez extra sólo para sangrar alguna línea de código cada vez mucho más? ¿Cuál es la implicación de que si Facebook conserva espacios en blanco en todos los bytes que se envían a la gente en Internet? Golpear la barra espaciadora una vez que se da un byte extra en su archivo. Y si mil millones de personas luego proceder a descargar la página principal de ese día, cuánto más datos ha transmitido a través de Internet? Un gigabyte por ninguna buena razón. Y concede, por un montón de sitios web que no es un tema tan escalable, pero para Facebook, para Google, por algunos de los sitios web más populares hay gran incentivo económico para que su código parecer un lío a fin de que usted está utilizando como pocos bytes como sea posible, además de entonces comprimir usando algo como zip, un algoritmo llamado gzip, que el navegador hace de forma automática. Pero esto es horrible. Nunca vamos a aprender cualquier cosa sobre los sitios web de otras personas y cómo diseñar páginas web si tenemos que verlo así.
Así que, afortunadamente, navegadores como Chrome y el IE y Firefox en estos días normalmente vienen con herramientas de desarrollo integradas. De hecho, si voy por aquí a Inspeccionar Elemento o si voy a ver, Developer, y vaya a Herramientas de Desarrollo de manera explícita, esta ventana en la parte inferior de mi pantalla ahora aparece. Es un poco intimidante al principio, porque hay un montón de fichas desconocidos aquí, pero si hago clic en Elementos de todo el camino en la parte inferior izquierda, Chrome es, obviamente, muy inteligente. Sabe cómo interpretar todo este código. Y lo que hace es que Chrome se limpia todo el HTML de Facebook. A pesar de que no hay espacios en blanco allí, no hay sangría allí, ahora cuenta de que yo pueda empezar a navegar por esta página web aún más jerárquica. Resulta que todas las páginas web escritas en un lenguaje llamado HTML 5 debe comenzar con esto, esta declaración DOCTYPE, por decirlo así: Es un poco de luz y de color gris allí, pero esa es la primera línea de código en el archivo, y que le dice al navegador, "Hey, aquí viene un poco de HTML5. Aquí viene una página web." El primer tramo abierto más allá que pasa a ser esto, un corchete abierto tag HTML, y luego, si me zambullo en el más profundo - estas flechas son completamente sin sentido; no son más que por el amor de presentación, ellos no están realmente en el archivo - cuenta que dentro de la etiqueta HTML de Facebook, algo que comienza con un corchete abierto y luego tiene una palabra se denomina una etiqueta. Así que dentro de la etiqueta HTML es aparentemente una etiqueta de la cabeza y un cuerpo de la etiqueta. Dentro de la etiqueta de la cabeza ahora es un lío para Facebook porque tienen una gran cantidad de metadatos y otras cosas para la comercialización y la publicidad.
Pero si se desplaza hacia abajo, abajo, abajo, abajo, vamos a ver dónde está. Aquí está. Ésta es al menos algo familiar. El título de la página principal de Facebook, si alguna vez pinche en la pestaña en la barra de título, es Bienvenido a Facebook - Entrar, Registrarse o más. Eso es lo que se ve en la barra de título de Chrome, y eso es lo que está representado en el código. Si dejamos de lado todo lo demás en la cabeza, la mayor parte de las entrañas de una página web se encuentran en el cuerpo, y resulta que el código de Facebook se va a parecer más complejo que la mayoría de las cosas que vamos a escribir inicialmente sólo porque se ha construido a lo largo de los años, pero hay un montón de etiquetas de script, el código JavaScript, que hace que el sitio web muy interactiva: ver las actualizaciones de estado de forma instantánea utilizando lenguajes como JavaScript. Hay algo que se llama un div, que es una división de una página. Pero antes de llegar a ese detalle, vamos a tratar de alejar y ver una versión más simple de Facebook 1.0, por así decirlo. Aquí está el hola mundo, de las páginas web. Tiene esa declaración DOCTYPE en la parte superior que es un poco diferente de todo lo demás. Nada más que escribir en una página web va a empezar con para negrita. Una vez más, la historia es la misma: hello, coma, comenzar a hacer esta audaz, entonces el mundo se imprime en negrita, y esto significa dejar de imprimir esto en negrita. Déjenme seguir adelante y salvar a mi archivo, vuelva a Chrome, voy a hacer un zoom sólo para que podamos ver mejor, y volver a cargar, y verás que el mundo se encuentra ahora en negrita. La red es acerca de los hipervínculos, así que vamos a seguir adelante y hacer esto: mi sitio favorito es, digamos, youtube.com. Guardar, cargar. Bien. Hay un par de problemas ahora, además de la fealdad de la web. 1, estoy bastante seguro de que pulse Enter aquí. Y lo hice. No sólo pulsar Enter, también sangrado, practicar lo que hemos estado predicando sobre el estilo, pero mi está justo al lado del mundo. ¿Por qué es esto? Los navegadores sólo hacer lo que les dicen que hagan. No le he dicho el navegador ", las líneas de ruptura aquí. Inserte el párrafo romper aquí." Así que el navegador, no importa si le pego Retorno 30 veces, todavía va a poner al lado de mi mundo. Lo que realmente hay que hacer aquí es decir algo como
, inserte un salto de línea.
Y en realidad, un salto de línea es una especie de cosa rara porque no se puede empezar a mover a otra línea, y luego hacer algo, y luego dejar de moverse a una nueva línea. Es una especie de una operación atómica. O lo hacen o no. Usted pulsa Intro o no. Así br es un poco de una etiqueta diferente, por lo que tengo que ordenar de ambos abiertos y cierre todo de una vez. La sintaxis de que es esta. Técnicamente, se podría hacer algo como esto en algunas versiones de HTML, pero esto es una estupidez, porque no hay razón para iniciar y detener algo si en su lugar puede hacer todo a la vez. Darse cuenta de que HTML5 no es estrictamente necesario que esta barra, por lo que verá los libros de texto y recursos en línea que no la tienen, pero por si acaso vamos a practicar la simetría que hemos visto hasta el momento. Esto significa que la etiqueta es a la vez abierto y cerrado. Así que ahora vamos a salvar a mi archivo, vuelva aquí. Bueno, por lo que está empezando a verse mejor, a excepción de la Web que sé es una especie de clic, y, sin embargo youtube aquí no parecen conducir a nada. Eso es porque a pesar de que se ve como un enlace, el navegador no sabe que per se, así que tengo que decirle al navegador que se trata de un enlace.
La manera de hacer esto es utilizar una etiqueta de anclaje: y me dejó pasar esto a una nueva línea justo por lo que es un poco más legible, y voy a reducir el tamaño de fuente. Estoy hecho todavía? No. No va a ser esta dicotomía. Esta etiqueta, la etiqueta de ancla, en efecto, tener un atributo, que modifica su comportamiento, y el valor de ese atributo es aparentemente URL de YouTube. Pero nótese la dicotomía es que sólo porque esa es la URL que va a, eso no quiere decir que tiene que ser la palabra que está subrayado y hacer un enlace. Más bien, que puede ser algo como esto. Así que tengo que decir esta palabra deja de hacer un hipervínculo mediante la etiqueta de ancla cerca. Nótese que no estoy haciendo esto. 1, esto sólo sería una pérdida de tiempo para todos y no es necesario.
Para cerrar una etiqueta, sólo se menciona el nombre de la etiqueta de nuevo. Usted no menciona ninguno de los atributos. Así que vamos a salvar eso, ir hacia atrás. Bueno, listo, ahora es azul y con hipervínculos. Si hace clic en él, me hace realmente ir a YouTube. Así que, aunque mi página web no está en Internet, es por lo menos HTML, y si dejamos que el Internet a ponerse al día, que en realidad terminaría aquí, en youtube.com. Y puedo volver atrás y esta es mi página web. Pero fíjate en esto. Si alguna vez has recibido spam o un ataque de phishing, Ahora usted tiene la capacidad después de sólo cinco minutos para hacer lo mismo. Podemos ir allí y hacer algo como www.badguy.com o lo que el sitio web es incompleta, y entonces se puede decir verificar tu cuenta PayPal. [Risas] Y ahora esto va a ir a badguy.com, que no voy a hacer clic en porque no tengo ni idea de dónde conduce. [Risas]
Pero ahora tenemos la capacidad para poner fin realmente allí. Así que realmente estamos empezando a arañar la superficie. No estamos programación en sí, que estamos escribiendo lenguaje de marcas. Pero tan pronto como se completan nuestro vocabulario en HTML, vamos a introducir PHP, un lenguaje de programación real que nos permitirá generar automáticamente código HTML, CSS generar de forma automática, para que podamos comenzar el miércoles para poner en práctica, por ejemplo, nuestro propio motor de búsqueda y mucho más. Pero más sobre esto en un par de días. Nos vemos entonces.
[CS50.TV]