[Powered by Google Translate] [Setmana 7] [David J. Malan - Harvard University] [Aquesta és CS50. - CS50.TV] Està bé. Benvingut de nou. Això és CS50, i aquest és el començament de la setmana 7. Un parell d'anuncis petits: Pset5 està ara en progrés, o aviat ho seran, i deixin-me dir-los, sincerament, aquest tendeix a ser un dels més difícils de conjunts de problemes del curs, així que anem a esmentar això ara pel que aquesta setmana més que mai no s'espera fins, diguem, a la nit o dijous a la nit a capbussar Aquest és sens dubte un conjunt de processadors interessant. Creiem que és divertit. Si vostè aconsegueix realment és totalment correcta i després pot impugnar la Borsa de Nova York anomenada, vostè tindrà l'oportunitat d'aparellar enginys amb una part del personal del curs i alguns dels seus companys de classe. Què és la Borsa de Nova York és un cop que el seu corrector ortogràfic de treball, vostè serà capaç d'anar a cs50.net després d'executar una ordre, purament optar a, i llavors la quantitat de temps i la quantitat de RAM i més que ha utilitzat en la seva implementació s'exhibiran aquí a la pàgina d'inici del curs. Es donarà compte que una gran quantitat d'aquestes persones aquí estan llistats com a personal des del cap de setmana, l'equip va pensar que seria divertit per tractar de superar la competència. Així que adonar-se que l'objectiu aquí no és superar els empleats. Fins i tot jo no sóc més que aquí, al número 13. Purament acceptes, però és una oportunitat per veure el poc RAM i què pocs segons de la CPU es pot utilitzar vis-a-vis alguns dels seus companys de classe.
I vaig a admetre que Kevin Michael Schmid, Actualment, al número 1 posició com un dels TF, es tracta d'una aplicació que no és possible trucar atès que ell està usant gairebé 0 RAM i gairebé 0 segons per a la càrrega. Així que anem a tenir cura desconnectat Kevin. [Rialles] Hi ha certes habilitats que Kevin està posant a prova aquí. Una de les coses que pensem que faríem ara és massa CS50x és una setmana en curs, i vostès són una part tan important d'aquest experiment com els estudiants són. Els hem demanat com a part del seu pset0, que era similar en presentar un projecte de Scratch d'interès per a ells - un joc, una peça d'art interactiu, l'animació, o similars - un 1 - vídeo a 2 minuts, si volen, saludant a tothom i que són en realitat. Jo vaig pensar en compartir amb vostès un parell dels vídeos que s'han presentat fins ara perquè per a nosaltres, pel personal almenys, el que realment ha estat emocionant i inspirador veure aquesta gent de tot el món - els països de tot el món - en sintonia, de totes les coses, a un curs d'informàtica a Internet, ja sigui perquè volen continuar els seus estudis, volen prendre la seva carrera en una nova direcció, volen omplir les llacunes del seu propi coneixement, de manera que algunes de les mateixes raons que vostès potser han estat aquí.
Així que li dono un tal estudiant aquí. Podries pujar el volum una mica. Aquí està un 1-minut presentacions dels nostres estudiants. Hola, món. Sóc un estudiant d'enginyeria industrial aquí a Màlaga, Espanya. Estic molt emocionat amb aquest curs perquè m'agrada la informàtica, de veritat, i jo realment estima que em poso a explorar. I el fet que puc aprendre el mateix tot el que vostès fan però en lloc d'estar a Harvard estic a Màlaga, el meravellós és això? Bé, sóc Fernando, i això és CS50. Ens veiem. [Rialles] Un altre clip en particular ens agrada, trobareu que aquest cavaller anglès no és tan forta. Sembla que tenia una traducció automàtica, de manera que les pròpies traduccions són una mica imperfecta, però aquest era un dels nostres favorits fins ara, així. [♪ ♪] Hola, món. [Parlant en japonès] [He de saludar en japonès perquè el meu anglès és menys segurs.] [He lliurat el missatge a vostè de la ciutat de Gifu, Japó.] [I pot ser un estudiant per primera vegada en 20 anys, com es pot veure.] [Estic molt agraït a la Universitat de Harvard, qui em va donar aquesta oportunitat i EDX.] [El golf és una guitarra i dirigint la meva cosa favorita.] [Rialles] [♪ ♪] [Per què creu vostè que jo estava tractant d'assistir a una cs50x.] [Universitat de Harvard, és el meu anhel.] [Especialment si estic presència llunyana vivia al Japó.] [Jo volia provar immediatament conscient de l'existència de tal EDX quan.] [No et sembla el que no és relacionat amb l'edat d'aprenentatge I.] [CS50 és el meu anhel. El meu nom és Kazu, i això és CS50.] [♪ ♪] [aplaudiments] Un altre dels favorits de la nostra era aquesta presentació aquí d'algú. [♪ ♪] [Malan] Google si no està familiaritzat amb aquest meme.
I finalment, un parell d'altres que he publicat que potser guanyar el premi adorable. [Estudiants] Aww! >> [Malan] Haurem d'escoltar. Aquest és curta, així que escolta amb atenció. [Speaker dona] et dius? >> Louie. [Speaker dona] Què és això? >> [Rialles] CS50. [Rialles] [Malan] Ell va fer dues preses, però. Aquí, l'última. El meu nom és Louie, i això és CS50. [Rialles] Aquesta és, doncs, CS50x. Gràcies a tots aquells de vostès mentre segueix a casa que han estat fins ara participar. Avui dia, podem concloure la nostra anàlisi d'estructures de dades, almenys alguns dels més fonamentals, i després continuem la nostra conversa sobre HTML i programació web. De fet, hem passat el passat uns set setmanes buscant en els fonaments de la programació - algorismes, estructures de dades i similars - i C, com vostè pot haver experimentat fins ara, no és necessàriament el més accessible dels idiomes amb el qual posar en pràctica algunes d'aquestes idees. I així comença aquesta setmana i la propera setmana i després el següent, que finalment serà capaç de fer la transició de C, la qual es coneix generalment com un llenguatge de nivell força baix, a les coses de nivell superior, entre ells PHP, JavaScript, i similars, que veurem recórrer a les mateixes lliçons que hem après al llarg de les últimes setmanes, però trobareu que declarar coses com matrius i taules hash i de recerca i ordenació convertit en molt més fàcil perquè les llengües mateixes que començarem a utilitzar es farà més poderós. Però primer, una aplicació d'arbres. És molt comú en aquests dies a haver de comprimir la informació. En quin context es vol comprimir algun tipus d'informació digital?
Si. >> [Estudiant] Quan hagi de enviar-lo a través d'Internet. Sí, quan vostè vol enviar alguna cosa a través d'Internet. Per descarregar un arxiu de grans dimensions, és ideal si algú en l'altre extrem ha comprimit l'arxiu amb un format zip o alguna cosa per l'estil de manera que enviarà menys bits que d'una altra manera podrien ser transmesos. Llavors, com comprimir la informació? Tot es redueix a la utilització d'un menor nombre de bits que es requereixen per defecte. Però això és una mena de cosa curiosa perquè pensi de nou a les setmanes 0 i 1 quan parlem de ASCII i binari i parlem de ASCII en particular com l'ús de 8 bits per representar lletres de l'alfabet de manera que la lletra A es representa per 65, minúscules a és el número 97, i no obstant això representen el 65 o el 97, que està usant 7 o 8 bits. Però el problema és que hi ha algunes lletres en l'alfabet anglès que no són tan populars com altres. Z no és tan popular, Q no és tan popular, però A i E són molt populars. I tot amb totes aquestes cartes, per defecte el món utilitza el mateix nombre de bits, a 8. Llavors, ¿no hauria estat més intel · ligent si en lloc d'utilitzar 8 bits per a cada lletra, fins i tot el més freqüentment utilitzat com Q i Z, I si fem servir menys bits per A i E i S i les lletres més populars i s'utilitza més bits per les lletres menys populars, la idea és optimitzar anem per al cas comú, que és un tema en ciències de la computació de tractar d'optimitzar el que va a passar la major part del i passar una mica de temps més, una mica més d'espai a les coses que, sí, podria succeir però no necessàriament amb la freqüència. Així que anem a prendre un exemple.
Suposem que volem codificar informació bastant eficient. És possible que hagi crescut sense conèixer una mica sobre el codi Morse, i les probabilitats són que vostè no sabia el codi actual, però es pot recordar que és almenys d'aquesta sèrie de punts i ratlles. Es tracta d'una codificació bastant eficients, i l'avís de que la lletra més popular - per exemple, I - utilitza la més curta de xiulets. El codi Morse és tot sobre bip-bip-bip-bip-bip-bip i la celebració dels tons ja sigui per períodes curts de temps o durant llargs períodes de temps. I, com s'indica al punt, és un so súper curt, només xiulet, i que representaria E. Per contra, T seria un xiulet llarg, com un xiulet [perllonga so] i que representaria T. Però això és encara molt curt, ja que, per contra, si ens fixem en Z, per expressar Z anirà beep, beep [més so], beep, beep [so curt]. Així que és més perquè és menys comú. Però et tinc aquí és que el codi Morse és una mica deficient en què no és immediatament decodificable. Per exemple, suposem que vostè sent en algun extrem del cable de senyal sonor [curt], beep [llarg]. Quin missatge Acabo de rebre? Un punt i un guió. Què és el que representa? [Estudiant] A. >> [Malan] Pot ser. També podria ser I seguit de T. En altres paraules, el codi Morse, encara s'aprofita aquest principi d'optimitzar el cas de la cantonada, que no es presta a la capacitat de descodificació immediata. És a dir, l'ésser humà que està escoltant o rebre aquests punts i ratlles ha de trobar alguna manera d'on són els salts entre lletres, perquè si vostè no sap on són els salts, pot confondre A per ET o viceversa.
Llavors, què podria fer? En codi Morse només podria fer una pausa entre cadascuna de les lletres. Però és una espècie de pausa en contra de tota la qüestió d'accelerar les coses. I si en comptes d'això es va acostar amb un codi en el qual no va ser aquesta mala situació on E és un prefix, per exemple, d'A - en altres paraules, si poguéssim assegurar que els patrons són encara curt per les lletres populars temps perquè les cartes menys populars, però no hi ha confusió possible? Un home amb el nom de Huffman anys va inventar aquest pla denominat codificació de Huffman que realment aprofita una de les estructures de dades que hem passat una mica de temps parlant de La setmana passada, la dels arbres, els arbres binaris en concret - un significat arbre binari que no té més de 2 nens. Té potser un fill esquerre, potser un fill dret, i això és tot. Així que suposo que pel simple fet de la discussió que algú vol enviar un missatge que són aquestes. És una tonteria però està compost d'As, Bs, Cs, Ds, i ES. I si realment explicar tot això de la As, Bs, Cs, Ds, i Es i es divideix pel nombre total de cartes, aquesta petita carta aquí diu que el 45% de les cartes són És, el 20% són As, 10% b, i així successivament. En altres paraules, se suposa que la cadena esmentada allà és només un missatge que voleu enviar. Li passa a ser una ximpleria, així que podeu emprar com poques cartes com sigui possible, però és de fet el cas que E segueix sent el més popular, i B i C són les menys populars, com a mínim una d'aquestes 5 lletres de l'alfabet. Llavors, com fem per trobar una codificació, una codificació binària, un patró de 0 i 1 per a cadascuna d'aquestes cartes de manera que E és un patró curt i potser B i C són lleugerament més llargues patrons, de nou, la idea és que volem utilitzar menys bits major part del temps i més bits només de tant en tant. D'acord amb la codificació Huffman, pot crear un bosc d'arbres. Hi ha una espècie d'una història aquí que suposa arbres i també el procés de construcció cap amunt. Anem a començar.
Proposo que s'inicia amb aquest bosc, per dir-ho, de 5 arbres, cadascun dels quals és un arbre bastant estúpid. L'arbre està composta de només un únic node, representat aquí per un cercle. Així que cadascuna d'aquestes coses pot ser una estructura C ia l'interior de l'estructura C podria ser un flotador que representa el recompte de freqüència i després potser un char que representa la lletra. Així que pensa en aquests nodes com qualsevol vella estructura C, però, per ara, un nivell més alt. Es tracta d'un bosc de 5 arbres, cadascun dels quals només tenen un sol node. Què Huffman proposta és que comencem a combinar aquests arbres que tenen els més petits té freqüència en els arbres una mica més gran mitjançant la connexió amb un node arrel. Així que entre les cartes aquí, noti que per comoditat he ordenats d'esquerra a dreta, encara que això no és estrictament necessari i s'adona que els més petits nodes Actualment el 10% i el 10%. Així Huffman va proposar que fusionar aquests dos petits nodes en un arbre nou mitjançant la introducció d'un nou node primari i després fer aquest pare un fill esquerre i un fill dret on B és arbitràriament l'esquerra i C és arbitràriament la dreta. I després Huffman va proposar a més que anem ara només pensa en el fill esquerre en un d'aquests arbres sempre com està representat per 0 i el fill dret sempre com està representada pel número 1.
No importa si vostè donar-los la volta, sempre que vostè és consistent. Així que ara tenim quatre arbres en aquest bosc. I dic quatre, perquè ara l'arbre de l'esquerra - i no és tant un arbre en el sentit que creix d'aquesta manera, és més com un arbre genealògic on ara el 0.2 és una mena de pare dels dos nens - compte que en aquest pare que hem dibuixat 0.2. Hem afegit els comptes de la freqüència dels dos nens i donat el nou node a la suma total. Així que ara, simplement repetiu aquest procés. Troba els dos nodes més petits i després unir-los en un nou arbre i repeteixi el procés. En aquest moment tenim uns quants candidats, el 20%, 15%, i un altre 20%. En aquest cas, hem de trencar l'empat. Podem fer-ho de forma arbitrària. Hauríem fer-ho de forma coherent. En aquest cas, arbitràriament a anar amb l'altre a l'esquerra, i ara fusionar el 20% i el 15% de donar-me un nou pare va trucar un 35%, el fill esquerre és 0, el dret és un nen, i ara tenim només tres arbres al bosc. Vostè potser pugui veure on va això. Si repetim això un parell de vegades més, tindrem un sol arbre més gran, tots de les vores estan etiquetats amb 0s i 1s. Anem a fer-ho de nou. 35% és l'arrel d'aquest arbre. 20% i 45%, així que anem a fusionar el 35% i 20%. Ara tenim aquest arbre aquí. Afegim els que junts, tenim un 55%. Ara només hi ha dos arbres al bosc. Ho fem un cop final, i espero que matemàticament totes les freqüències es sumen perquè ja es computaran des del primer moment per sumar 100%. I ara tenim un arbre. Així que aquest és un arbre de Huffman. En certa manera es va prendre un temps per arribar-hi verbalment, però la realitat és amb un bucle for o amb una funció recursiva, vostè podria construir aquesta cosa bastant ràpid. Així que ara tenim un nou node, i tots aquests nodes interiors han estat malloc'd, presumiblement, al llarg del camí. Així que ara a la part superior d'aquest arbre que tenim 100%, però noto ara tenim un camí d'aquesta nova tatara-tatara-tatara-avi de tots els tatara-tatara-tatara-néts tot el camí a la part inferior, per tots els fulls.
Què farem ara és proposar que per representar la lletra E, ens limitarem a utilitzar el número 1. Per què? Perquè si travessem aquest arbre des de l'arrel fins a l'última fulla coneguda com E, seguim un sol vora, la vora dreta, i això ha marcat, és clar, a la part superior dreta 1. Així que la implicació aquí per Huffman va ser que codifica la E en binari només serà l'1. I això és molt molt eficient. No es pot realment aconseguir qualsevol menor que això. Per contra, A es representarà, si se segueix la lògica, per què patró de bits en el seu lloc? 01. Així que per arribar a A, comencem a l'arrel i es va a l'esquerra i després a la dreta, el que significa que seguim a 0 i després 1 a. Així que representarà la lletra A amb el patró de 0 i 1. I ara noti que ja tenim una propietat de descodificació immediata que no teníem en codi Morse. Tot i que aquests dos patrons són bastant curt - E és de 1 bit, 2 bits A és - compte que no pot ser confós un o l'altre, perquè si vostè veu un 1 que ha de ser una E, si vostè veu un 0, un 1 és òbviament ha d'haver una A. De la mateixa manera, quin és D? 001. Què és C? 0001. I què és B? 0000. I de nou, perquè totes les cartes que ens interessen són les fulles i cap d'ells són una espècie d'intermediaris en el camí de l'arrel a les fulles, no hi ha risc de combinar codificacions 2 lletres els diferents perquè tots aquests patrons de bits són deterministes. 0000 serà sempre B. No hi ha cap node en algun punt intermedi que podria confondre a una lletra per a l'altre. Llavors, ¿quina és la implicació en aquesta llista?
La carta més popular - en aquest cas E - ha aconseguit la codificació més curta, A ha aconseguit la codificació més curta següent, i B i C, que ja sabia des del primer moment classe eren dels menys populars el 10% de freqüència cadascuna, que han aconseguit el major codificació. I així, el que això significa és que si vol enviar un missatge que es comprimeix a través d'Internet o en un correu electrònic o similar, en lloc d'utilitzar ASCII estàndard, pot enviar un missatge codificat Huffman Que si vol enviar la lletra E, que acaba d'enviar un sol bit. Si voleu enviar una A, envia 2 bits, 01, en lloc d'enviar 8 bits seguit d'altres 8 bits seguides per altres 8 bits i així successivament. Però hi ha un Gotcha aquí. No n'hi ha prou per a la construcció d'aquest arbre i després començar a enviar la Alice a Bob el patró poc més curt, una cadena ASCII, perquè Alícia també ha d'informar del que Bob Bob si serà capaç de llegir el seu missatge comprimit? [Resposta dels estudiants inaudible] >> Què és això? [Resposta dels estudiants inaudible] >> De quin arbre és. O més específicament, quines són aquestes codificacions són, sobretot perquè durant aquesta història hem fet una crida a judici en un punt. Recordeu que vam haver recollir arbitràriament entre els dos nodes diferents de 20%? Així que no és el cas que Bob, el receptor, només pot reconstruir l'arbre pel seu compte perquè potser crearà l'arbre molt lleugerament diferent a Alice. D'altra banda, Bob ni tan sols sap el que el missatge original és perquè l'única Alice li està enviant, és clar, és el missatge comprimit.
Així que la captura amb la compressió d'aquest tipus és que, sí, Alice pot estalviar un munt de bits mitjançant l'enviament d'1 per E i 01 per A i així successivament, però ella també ha d'informar Bob el que la cartografia és entre les lletres i els bits perquè clarament no pot dependre només de ASCII més si no estem usant ASCII. Així que ella li pot enviar l'arbre d'alguna manera - escriviu, deseu-lo com dades binaris o alguna cosa així - o simplement li enviarem un full de trucs poc, un arxiu d'Excel, que mostra les assignacions. Així que l'eficàcia de la compressió realment assumeix que els missatges que està enviant són bastant grans, si més no de grandària mitjana, perquè si vostè està enviant un missatge curt super, si el que desitja és enviar el missatge BAD, que passa a ser una paraula que pot significar aquí, B-A-D, vostè està probablement va a utilitzar menys bits, però el problema és si vostè també ha d'informar a Bob el que l'arbre és o quines són aquestes codificacions són, vostè va a pesar més que probable que tots els estalvis de tenir les coses comprimides, per començar. Així que en realitat pot passar que si s'intenta comprimir fins i tot amb una mena formats ZIP o arxiu que estigui familiaritzat amb - arxius molt petits, fins i tot arxius buits - de vegades aquests arxius poden aconseguir més gran i més petit no. Però en realitat, això passa només per mides d'arxiu petits, pel que no va a fer un arxiu de 2 gigabytes gigabyte ser; realment estem parlant bytes o només uns kilobytes de parella.
Alguns programes com zip són prou intel · ligents per adonar-se que, "Vas a gastar més bits de compressió això". "No deixis que em molesta comprimir per a vostè en tot." Així que això és només una manera de comprimir llavors format de text. Es podria implementar alguna cosa com això en C. Per exemple, aquí està la manera com podria representar un node d'aquest arbre on tindrem una xerrada per al símbol, un valor flotant per la freqüència, i com hem vist amb els nostres altres estructures de dades, 2 punters, 1 per al fill esquerre, 1 a la dreta, qualsevol dels quals pot ser NULL, però si no, es refereix a un fill esquerre i un fill dret. Així que aquesta és, doncs, la codificació de Huffman, i és una forma en què vostè pot anar sobre la compressió de la informació, i és sens dubte un dels més fàcils d'implementar en el context de, per exemple, estructures de dades de la setmana passada, encara fins i tot els algoritmes més sofisticats existeixen que poden fer mutacions encara més sofisticats de les dades. Qualsevol pregunta llavors sobre els arbres, arbres binaris, o la compressió de text? [Estudiant] Hi ha alguna ambigüitat, com si es divideix [inaudible] en 01, 011 llavors seria ambigu, no? [Inaudible] >> Bona pregunta. L'ambigüitat. Vaig a resumir en referir a aquest quadre aquí. A causa que els caràcters que s'estan comprimint, les representacions de, per definició d'aquest algorisme sempre romanen les fulles, vostè mai va a voler utilitzar el mateix patró de bits per al prefix de lletres múltiples. En altres paraules, vostè està preocupat, que sona, una ambigüitat que sorgeixi 001 per el que podria ser el començament de B o l'inici de C o alguna cosa així. Però això no pot ser així, perquè noti que totes les lletres de l'alfabet que estem codificació es troben a les fulles.
L'ambigüitat només pot sorgir, com en el cas del codi Morse, si, per exemple, C estava en algun lloc al llarg de la ruta des de l'arrel a B. [Estudiant] Dret. Així que en aquest cas, per exemple A té 2 fulles. >> Say A té - Digues-ho de nou. [Estudiant] Say A té dues fulles, F i G, i després G - >> bé. Però no puc. A si mateix no podria tenir fulles F i G perquè aquestes lletres F i G serien ells mateixos deixa en algun lloc a l'esquerra de B o el dret dels E. Així, per definició, han de ser fulles. En cas contrari, vostè està exactament correcte, no hem resolt el problema que enfronta el codi Morse. Bona pregunta. Altres preguntes? Està bé. Aquesta noció de bits, resulta que hem tingut al llarg de tot el poder que en realitat no hem utilitzat a l'hora de manipular aquests 0s i 1s. Li preguntem sobre això en un dels conjunts més primerencs de problemes: a saber, com vostè va sobre la conversió de majúscules a minúscules o viceversa? O, més concretament, un d'aquests conjunts de processadors primera pregunta quantitat de bits que és el que realment ha de donar la volta per canviar a minúscules una A o viceversa? Heus aquí un breu recordatori de cle 65 i 97 semblen en binari. I fins i tot si aquesta qüestió s'ha esvaït en espècie de la seva memòria, es pot veure de nou aquí que la quantitat de bits de donar la volta per canviar majúscula a minúscula una? Només una.
Només es diferencien en una sola ubicació, el tercer bit de l'esquerra. Mentre que A té un 010, una mica té un 011. Llavors, d'alguna manera, hem de ser capaços de donar la volta només aquest trosset, i llavors podem capitalitzar o minúscules. Hem fet això en el passat utilitzant de manera efectiva si les condicions i comprovar si la carta és entre el capital A i Z capital, llavors com sortides A - a + 26 o alguna cosa així. Probablement va fer un canvi aritmètic de les lletres de l'alfabet. Però, i si poguéssim donar la volta que sol bit? Com vostè va sobre la pena prendre un byte de bits, de manera que 8 bits 01000001 i 01100001 igual? Si tingués aquests patrons de bits, com podem fer per canviar només un d'ells? Què passa si introduïm en groc aquí aquesta altre patró de bits? Si faig les 0s sencers groc cadena excepte per al bit que vull canviar i després introduir un nou operador conegut com a operador bit a bit - bit a bit en el sentit que opera a bits individuals, no en un byte complet o quatre bytes d'una vegada. Aquesta barra vertical hi ha en groc suggereix que el que si es té la representació de la majúscula i OR bit a bit amb la seqüència de bits de color groc? En altres paraules, pensa de nou a la discussió de les expressions booleanes en Scratch i després en C.
Fent un booleà o vol dir que per ser veritat, ja sigui la primera cosa que ha de ser veritat o la segona cosa que ha de ser cert o tots dos han de ser veritat, i després la sortida resultant si és cert. En aquest cas aquí, què obtenim si prenem 0 "o" ed amb 0? Fals o fals? Encara és fals, de manera que la minúscula segueix sent com s'esperava. I si en comptes d'això fer 1 o 0? Això ara roman en 1, però adonar-se del que passarà aquí. Si comencem amb majúscula i seguim "o" els bits individuals com estem fent aquí, 0 o el groc ens dóna el que aquí baix? Això ens dóna 1. De fet, suposo que no sabia el que la versió en majúscules d'una mica en realitat. Anem a fer això. Permetin-me passar això de nou per aquí. Farem això de nou. 0 o 0 em dóna 0. 1 o 0 em fa 1. 0 o 1 em dóna 1. 0 o 0 em dóna 0. El següent és 0, el següent és 0, el següent és 0. 1 o 0 em fa 1. I així, encara que no sabia per endavant el que era una minúscula, simplement per "o" ing A amb aquest patró de bits que hem presentat aquí en groc, pot minúscules A majúscula en llançar aquesta part. Es va utilitzar aquesta expressió setmanes enrere: prémer una mica. Com es pot realment fer això mitjançant programació? S'utilitza el que normalment es coneix com màscara, una seqüència de bits, que en aquest cas que passa a tenir aquest número aquí, i llavors "o" juntament amb aquest nou operador C, no | |, s'utilitza un únic | i que en realitat tindria aquesta resposta aquí, perquè per què? Aquest és el lloc 1s, 2s lloc, 16s 4s, 8s, 32s. Així que resulta que si vostè pren una lletra majúscula A i O-lògic amb el sencer 32, perquè el sencer 32, quan es miri en forma de bits, es veu així, que significa que pot capgirar el poc que realment voleu. I de la mateixa manera - i anem a veure el codi en un moment - suposem que volem anar en una altra direcció.
Com es passa de majúscula a capital per A? Que poc cal canviar? És el mateix. Volem canviar aquest tercer bit des d'un 1 a 0. I com podem anar fent això? Com ens desviem una mica? Amb quina patró de bits podríem apagar una mica? Què passaria si una espècie d'invertir la màscara? Mentre que abans, hem fet tot el 0s màscara groga excepte per al bit que volíem per encendre, I si aquesta vegada, fem el 1s màscara sencera a excepció de la part que es vol desactivar i aleshores utilitzar el que operador? Què passaria si "i" les coses? Anem a fer una ullada. Si ara la volta a això, suposem que de nou puc crear una màscara que és tot 1s excepte pel poc un que desitja desactivar i llavors en lloc de "o" els números blancs sobre de la tapa amb els números grocs aquí baix, I si en lloc de "i" ells junts? Es diu bit a bit i. Lògicament, és la mateixa cosa que un booleà i. Això em dóna 0 i 1 és 0. Així fals i la veritat és fals. És cert i veritable és veritable. I aquí està la màgia: vertader i fals és fals ara, així que hem apagat que poc. I ara la resta de la història és una cosa senzilla. Com que la resta de la màscara és d'1 s, no importa el que els nombres estan en blanc. Quan vostè "i" una mica de veritat, vostè no canviarà el seu valor. Si bé és cert, seguirà sent cert. Si era fals, seguirà sent fals.
Però la màgia succeeix quan es pren alguna cosa que era cert i després "i" amb falsa. Això té l'efecte de desactivar aquest bit. Així que una mica críptic allà. Anem a veure en realitat una mica de codi, que en realitat podria ser encara més críptic, però anem a fer una ullada aquí a tolower. Si miro tolower, en passar de majúscula a minúscula a, veurem com podem implementar aquest programa. Això és important, i no està prenent cap argument de línia d'ordres. Estic declarant un caràcter c en la carta que l'usuari va a escriure polz Després utilitzo un acord familiaritzat bucle while per fer només assegurar-se que l'usuari definitivament em dóna una A majúscula B o C. .. Z, de manera que em dóna alguna cosa entre A i Z. I ara, què faig jo aquí? Jo sóc "o" ing això amb 0x20, però que en realitat és el mateix que - i tornarem a això en un moment - 32. Així que de nou, 32 és el patró de bits d'aquí. Per què sabem això? Pensi vostè en la setmana 0. Aquest és el lloc 1s, 2s lloc, 4s, 8s, 16s, 32s lloc. Així que aquest nombre groc passa a ser 32. Continuació, preneu una carta com la xerrada aquí, bit a bit "o" és literalment amb el número 32, i què és el que jo torni? La versió en minúscules que char. Fa un moment, però, em va expressar això en una notació de base diferent. Què representa això? >> [Estudiant] Hexadecimal. [Malan] Això li passa a representar hexadecimal. No hem parlat de hexadecimal gairebé res, però en realitat és convenient en casos com aquest.
Tot i que sembla més complex i encara que sembla que 20 i no 32, resulta que en realitat és la notació hexadecimal súper còmode perquè en hexadecimal cada dígit després del 0x - i això no vol dir res; això és només convenció humana que diu aquí ve un nombre hexadecimal - cada un d'aquests dígits, el 2 i després el 0, es pot representar amb exactament 4 bits. Així que si fem això, permetin-me obrir un editor de text aquí - estrany Autocomplete - si fem un editor de text poc aquí, el nombre 0x20 vol dir aquí és de 4 bits, aquí hi ha altres 4 bits. Farem els 4 bits més a la dreta en primer lloc. 0 quan es representa amb 4 bits és el que? Super fàcil. Així tots 0s. Així que 4 bits com a 0. Com es pot representar 2? Ha estat un temps des que vaig fer això, però és 0100. Així que aquest és el lloc 1s, aquest és el lloc 2s, i llavors no importa el que els altres llocs són. En altres paraules, en hexadecimal es podria dir 0x20, però si després pensar en el que és el 2 i com es representen en binari, Quin és el 0 i com es representa en binari, les respostes a aquestes preguntes són això i allò altre, respectivament. Així succeeix 0x20 per representar aquest patró de 8 bits, que és precisament la màscara que volíem. Així que això és de moment només un exercici intel · lectual, però la realitat és que en el codi és generalment més comú escriure constants com aquesta en hexadecimal perquè llavors el programador pot fàcilment relativament, fins i tot si es requereix una mica de paper i un llapis, esbrinar el que el patró de bits és perquè un no pot expressar 0s i 1s normalment en el codi. No pots anar a 00010 i així successivament.
Has de triar les notacions decimal o hexadecimal o octal o d'un altre tipus. La majoria de la gent tendeix a escollir hexadecimal simplement perquè cada dígit representa 4 bits i vostè pot fer aquest càlcul ràpid. I vaig a agitar la mà en ToUpper, que és gairebé el mateix, es veu gairebé idèntic. ToUpper passa a utilitzar l'operador o no, sinó més bé aquest tipus i df. Què df representa? df? Algú? >> [Estudiant] 255. 255? No 255. Això seria ff. Deixarem aquest com una mica d'exercici. Però si vostè va de 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 i després el que ve després de les 9? Estem una mica fora de dígits decimals, però en hexadecimal què ve després de 9? [Estudiant] a. Així >> a, b, c, d. Vostè pot calcular a partir d'aquí quin patró de bits d en realitat representa. I si fem els càlculs, veurem que la màscara s'arriba a l'esquena és idèntica a aquesta. Això és f, tots els 1, i això és d. Així df representa aquesta màscara. Està bé. I finalment, per no fer les coses de so super, super tècnic, però suposem que volem escriure un programa que fa això. Deixin-me seguir endavant i fer binària, que és un programa en un arxiu anomenat binary.c. I ara m'ho dius a mi córrer binari i em dóna un nombre enter no negatiu. Comencem fàcil i escriviu 0. Això ara és un programa que imprimeix un enter en la seva representació binària. Així que si puc jugar a aquest joc de nou i escriure en només 1, necessiteu aconseguir una representació de 32-bit de 1. Si ho faig de nou amb 2, m'entenc. Si ho faig 7, que hauria obtenir una 1s pocs al final i així successivament. Resulta que jo esmento perquè amb operacions a nivell de bits en realitat es pot fer una cosa així. Podeu crear aquestes màscares de forma dinàmica. Fes un cop d'ull a aquest exemple una final que involucri operacions bit a bit. Aquí està la primera part del codi, sol · licitar a l'usuari un nombre, i s'insisteix que vostè em dóna un enter no negatiu. Així que és una mena de coses de la vella escola. Però aquí hi ha una cosa que és bastant interessant.
Com puc imprimir un nombre en binari? Per primera iteració de què a què? Quina és la mida d'un int típicament, almenys en l'aparell? >> [Estudiant] 4. És 4. Així que 4 * 8 és 32 - 1 és 31. Així que si jo estic començant a comptar a partir del 31, que representa, és, només conceptualment, el bit 31 o el bit d'ordre més alt, que és aquest noi per aquí, mentre que això serà de 0 bits. Així que aquest és el bit 01 ... bit 31. Llavors, què està fent aquest codi? Vegeu aquest bucle for, encara que sembla críptica, és simplement iterar des del 31-0. Això és tot. Així que la part interessant ara ha d'estar en aquestes 5 línies aquí. Noteu que en aquesta línia estic declarant una variable anomenada màscara per ser coherent amb la nostra història d'aquests números grocs. I llavors, què fa això? Aquest és un altre operador de bits que no hem vist abans, el més probable. És l'operador de desplaçament a l'esquerra. Aquest operador fa això. Aquí hi ha el número 1, i si ho fas em vaig anar torn, desviació a l'esquerra, Què pensa vostè que té l'efecte de fer a aquesta persona 1? Literalment canviant de nou. Així que si el nombre 1 és el que té a l'esquerra i comença inicialitzant i al 31, el que farem? Va a prendre aquest número 1 i canviar 31 places per aquí. I perquè òbviament hi ha cap altre dígit darrere d'ell, els que per defecte seran reemplaçats per 0. Pel que comenci amb el número 1, que per descomptat té aquest aspecte - i m'ho dius a mi dir aquí al centre. I després, a mesura que canvien les coses a l'esquerra, aquest home essencialment va d'aquesta manera. Però tan aviat com ho fa, un 0 s'omple polz Si el canvien per segona vegada, va d'un costat a un altre 0 s'omple polz
Vostè ho canviï de nou i després un altre 0 s'omple polz Així que si vostè fa aquesta cosa d'1 << i 31 places, s'arriba a una màscara que és 32 caràcters de longitud, més a l'esquerra de la qual és un 1, tota la resta dels quals són un 0. I resulta que, en un apart, canviant un nombre a l'esquerra com aquest també per casualitat, i de vegades convenient, té l'efecte de fer el que a aquest nombre? >> [Estudiant] duplicar. Duplicar perquè cadascuna de les columnes - el lloc 1s, 2s lloc, lloc 4s, Lloc 8s, 16s lloc - són tots duplicació a mesura que avança cap a l'esquerra. O més aviat, en canviar el 1s vas a acabar duplicant el valor del nombre. Vostè pot acabar sobre de fer transformacions interessants de dígits sobretot en canviar d'aquesta manera per potències de 2. Llavors, com funciona això? Això llavors em dóna una màscara que és de tots 0s a excepció d'una en una, precisament el lloc on ho vol, i llavors aquesta expressió, que és robat de toupper.c, diu simplement prendre el nombre n que l'usuari va escriure, "I que" amb aquesta màscara, i el que vas a aconseguir? Vostè va a obtenir un 1 si hi ha un 1 en aquest lloc emmascarat, o vostè va a obtenir un 0 si no ho és. I així tot el programa de manera efectiva és que té un bucle, i crea una màscara amb un 1 per aquí, després un 1 per aquí, després un 1 per aquí, i utilitza aquest truc AND bit a bit a dir és que hi ha un bit 1 a la entrada de l'usuari en aquesta llista?
Hi ha un bit 1 a la entrada de l'usuari aquí? I si és així, literalment imprimir 1, en cas contrari imprimir 0. Estem fent això amb INT només perquè és per això que estem fent 32 bits en lloc de 8, però el que hem introduït és aquest AND bit a bit, bit a bit OR això, i aquest operador de desplaçament a l'esquerra, que no solen ser terriblement útil, però resulta que pot ser. De fet, si vostè anés a representar alguna cosa així com un conjunt de valors booleans només per representar veritables o falses, suposi que vol fer un seguiment de si és o no una habitació plena de 300 estudiants és present, pot declarar una matriu de mida 300 de tipus bool perquè vostè obtingui 300 Bools, i es pot configurar per a cada cert si algú aquí i false en cas contrari. Per què és que la representació en aquesta estructura de dades ineficient? Què hi ha de dolent en el disseny d'aquesta estructura de dades, una matriu de 300 Bools? Què és un bool, de fet, sota la caputxa? Això, també, és una cosa que no pot ser conegut. Resulta que no hi ha bool. Recordi que tipus de creat que amb l'arxiu cs50.h, que s'inclou de sèrie bool. C és una mica ximple, però, quan es tracta de bool. S'utilitza 8 bits per representar cada bool, que és totalment antieconòmic perquè, òbviament, quants bits es necessita per representar un bool? A només 1. Així que resulta que si vostè ara té la capacitat dels operadors a nivell de bits per manipular bits individuals, fins i tot en un char, fins i tot en un sol byte, resulta que podria reduir la memòria necessària per representar alguna cosa estúpid com l'estructura de les dades d'assistència llaurat per un factor de 8. En comptes d'usar vuit bits per representar veritables o falses, que, literalment, podria utilitzar un mitjançant l'ús d'un sol byte per cada vuit alumnes de la classe i alternar 0-1 els bits individuals utilitzant aquest tipus de baix nivell trucs. Això realment posar fi a l'energia. Hi ha alguna pregunta sobre les operacions a nivell de bits?
Si. >> [Estudiant] Hi ha un operador exclusiu o? Sí Hi ha un operador exclusiu o que són aquestes, ^, el símbol de la pastanaga, el que significa que només és el primer o el segon pot ser un 1 perquè la sortida sigui un 1. També hi ha un no, ~, el que li permetrà invertir un 0 a un 1 o viceversa, així. I també hi ha un operador de desplaçament a la dreta, >>, que és el contrari de la que vam veure. Està bé. Anem a prendre les coses ara a un nivell més alt. Comencem parlant de text i després comprimir i que representa el text amb un nombre menor de bits; parlem una mica sobre com podem començar a manipular les coses a un nivell de bit a bit. Anem ara amplia fins a 10.000 peus a la representació de les coses més complexes, com gràfics. Aquí tenim una bandera d'Alemanya, aquí tenim un de França. Aquests poden ser representats en formats d'arxiu que pot saber - GIF, per exemple. Si alguna vegada has vist una imatge en la web que acaba en. Gif, Aquest és un format d'intercanvi de gràfics. Aquestes dues banderes espècie d'aquí es presten a la compressió per la qual cosa potser òbvia raó? >> [Resposta dels estudiants inaudible] Hi ha un munt de repetició, no? Per enviar bandera d'Alemanya, pensa en això com una imatge a la pantalla En l'època de la seva Scratch. Vostè recordarà que hi ha píxels individuals o punts que componen una imatge.
Hi ha tota una fila de punts negres i un altre conjunt de files de punts negres. Hi ha un munt de files de punts negres que podríem veure si realment el zoom, tant com quan el zoom a la cara de Rob en Photoshop. Així que vam arribar més i més i més profund en la imatge, que va començar a veure la pixelació, tots els quadrats que componen l'ull en aquest cas. El mateix passa aquí. Si el zoom una mica, veurà punts individuals. Bé, això és una mica un malbaratament de bits. Si un terç de la bandera és de color negre i un terç de la bandera és de color groc i així successivament, ¿Per què no podem comprimir d'alguna manera aquesta bandera? I fins i tot la bandera francesa pot ser comprimit tot i que el patró és una mica diferent. Resulta que el format de fitxer GIF és un format de compressió sense pèrdua, el que significa que vostè pot prendre una imatge com la bandera alemanya aquí, vostè pot tirar molt dels seus bits sense sacrificar la qualitat. Això està en contrast amb alguna cosa com JPEG, amb la qual la majoria de nosaltres som probablement més familiar. Fotos de Facebook i Flickr fotos i similars gairebé sempre es guarden com arxius JPEG quan estan carregats, però és una pèrdua JPEG - format mitjançant el qual vostè es desfaci de bits - amb pèrdues però també tir de qualitat. I així, si comprimeix les fotos amb Photoshop o pujar-les a Facebook o portar-los a un telèfon realment horrible, vostè sap que la imatge comença a ser molt desiguals i pixelat, i això és perquè està sent comprimit per l'ordinador o per telèfon per, literalment, llençar informació de distància. Però GIF és sorprenent, ja que pot utilitzar menys bits del que podria per defecte sense perdre cap informació.
I és essencialment ho fa de la manera següent. En lloc d'emmagatzemar en un arxiu com un arxiu BMP faria un triple RGB per al negre, negre, negre, negre, negre, negre, negre, negre, negre, negre, negre, negre i així successivament, més aviat, el format GIF es dirà, "Negre" i després, "Repetiu això 100 vegades", o alguna cosa per l'estil. "Negre, repetir això 100 vegades, negre, repetir això 100 vegades ..." "Groc, repetir això 100 vegades." I així ho recorda, essencialment, el píxel més a l'esquerra i després codifica d'alguna manera la noció de repetir aquest píxel i una altra. Així GIFs llavors poden comprimir sense perdre cap informació. Però si hagués de endevinar, si aquest és l'algorisme que GIFS ús, que d'aquests indicadors, tot i que són idèntiques en grandària, serà menor quan es guarda al disc com un GIF? >> [Estudiant] Alemanya. Alemanya serà més petit? Per què? [Estudiant] Perquè t'ho repeteixen moltes, moltes vegades horitzontalment i després repetir en una altra ocasió. >> Exactament. Perquè la gent que va inventar GIF només tipus de arbitràriament decidir que la repetició serà aprofitat horitzontal i lateralment no. No hi ha repetició molt més lateralment aquí al pavelló alemany de la bandera francesa. Així que si realment obrir una carpeta en el meu disc dur que té aquests GIFs, en realitat es pot veure que la bandera alemanya aquí és de 2 kilobytes i el francès és de 4 kilobytes. Li passa a ser una coincidència que un és el doble de l'altra, però és de fet el cas que la bandera francesa és molt més gran.
Tot i que estem parlant aquí sobre els gràfics, les mateixes idees poden aplicar-se a no coses com banderes sinó imatges que són una mica més complexes. Si es pren una fotografia d'una poma, segur que hi ha un munt de duplicació allà, per la qual cosa d'alguna manera podria recordar que el fons predeterminat és blau i no, com la imatge de la dreta indica, Cal recordar que el color de cada píxel en la imatge. Així que podem tirar trossos de distància sense perdre informació. La poma segueix semblant el mateix. En aquest exemple aquí, pot veure el que passa en una pel · lícula. Aquests representen la vella escola rotllos de pel · lícula pel que en la imatge de dalt hi ha Té una conducció RV passat una casa i un arbre. I com que van condueix més enllà d'esquerra a dreta, el que, evidentment, no està canviant? La casa no va enlloc, i l'arbre no va enlloc. L'únic que es mou és la furgoneta en aquest cas. Així com a fons Sense canvis indica, el que pot fer en les pel · lícules és igualment just rebutjar la informació que no canvia entre fotogrames. Això es coneix generalment com la compressió intertrama pel que si aquesta estructura es veu gairebé idèntic a aquest, no cal preocupar emmagatzematge en disc de la informació idèntica en aquests quadres intermedis, utilitzarem fotogrames clau només de tant en tant que en realitat emmagatzemar aquesta informació redundant així com una mica de seny comprovar.
Per contra, un altre enfocament per a la compressió de vídeo és en aquest exemple i segona més baixa aquí, on en lloc d'emmagatzemar 30 imatges, per què no acaba d'emmagatzemar 15 imatges per segon al seu lloc? Més que el tipus de pel · lícula que flueix molt bé, perfectament, pot ser que sembli que està quequejant una mica, una mica de la vella escola, però l'efecte net serà utilitzar bits d'un nombre molt menor del que podria ser necessària. Llavors, on ens deixa això llavors? Això va ser una mica d'un costat a un altre on es pot anar amb la compressió. Per saber més sobre això, prengui una classe com CS175 aquí. Hi ha un altre exemple en vídeo. Si l'abella és l'única cosa en moviment, realment es pot rebutjar la informació en els quadres mitjans perquè la flor i el cel i les fulles no estan canviant. Però considerarem ara una última cosa. En els propers 5 minuts, deixar enrere per sempre C a classe? Sí No en els conjunts de processadors, però. Darrera història sobre C i després arribem a coses molt sexy participació d'HTML i Web i woo Hoo. Està bé. Aquí anem. Aquesta és la motivació. Resulta que tot aquest temps en què hem estat escrivint programes que s'executen Clang. I Clang, hem dit des de la primera setmana més o menys, té el codi font i el converteix en un codi objecte. Es triga C i la converteix en 0 i 1. He mena d'estat mentint durant unes setmanes, ja que no és tan simple com això.
Hi ha moltes més coses sota de la caputxa quan s'executa un programa com Clang. De fet, el procés de compilació d'un programa realment pot ser resumida, Com es pot recordar de vídeo de Rob en compiladors, en aquests 4 passos: pre-processament, elaboració pròpia, el muntatge i la vinculació. Però a la classe i la majoria de les persones en el món sovint resumir tots aquests passos simplement com "compilar". Però si comencem amb el codi font d'aquest tipus, record aquest és potser el programa més simple C que hem escrit fins ara, recordem que quan es compila acaba semblant-se a això. Però en realitat hi ha un pas intermedi, i els passos són els següents. En primer lloc hi ha una cosa a la part superior d'aquesta i la majoria dels nostres programes, # Include Què és # include fer per nosaltres? És més o menys còpies i enganxa el contingut del fitxer stdio.h en mi per que per què? Per què es preocupen pel contingut de stdio.h? Què hi ha aquí d'interès? Printf la declaració, el seu prototip, de manera que el compilador sap a què em refereixo quan esmento aquesta funció printf. Així que el pas 1 a la compilació és pre-processament, de manera que un programa com Clang o algun programa d'ajuda que ve amb Clang llegeix el codi de dalt a baix, esquerra a dreta, i cada vegada que veu un símbol # seguit d'una paraula clau com include, realitza aquesta operació, copiar i enganxar en aquest cas stdio.h en el seu arxiu. Aquest és el pas 1. Llavors vostè té una molt més gran arxiu de C a causa de la gran còpia, enganxa treball que acaba de passar.
2 Pas ara està compilant. Però resulta que porta compilar el codi font que es veu així i es converteix en alguna cosa que són aquestes, que per a aquells que estan familiaritzats es diu? >> [Estudiant] Assemblea. Idioma >> Assemblea. Això és realment una cosa si es pren CS61 podràs submergir-te en en més detall. Això és el més proper que es pot arribar a escriure 0s i 1s vostè mateix però escriure les coses de tal manera que encara fa almenys una mica de sentit. Aquestes són les instruccions de la màquina, i si desplaceu-vos cap avall a la funció principal aquí, compte que existeix aquesta instrucció d'inserció, mogui la instrucció, restar instrucció, trucar a la instrucció, i així successivament. Quan vostè sent que l'equip té Intel a l'interior, vostè té una CPU Intel en el seu Mac o PC, què significa això? Una CPU ve integrat per empreses com Intel entendre certes instruccions. No tenen idea del que són les funcions com ara el canvi o principal estan per se, però sé molt baix nivell instruccions com sumar, restar, empènyer, moure, cridar, i així successivament són. Així que quan es compila codi C a llenguatge assemblador, la seva molt fàcil d'usar amb aspecte de codis es converteix en alguna cosa que són aquestes, que literalment es mou bytes o 4 bytes al voltant d'aquestes petites unitats d'entrada i sortida de la CPU. Però finalment, quan Clang està disposada a assumir aquesta representació del seu programa en 0 i 1, llavors el pas s'anomena muntatge succeeix, i aquesta vegada tot succeeix en un tres i no res quan s'executa Clang. Comencem aquí, envia un arxiu com aquest, i després el converteix a aquests 0s i 1s. I si vol tornar en algun moment i en realitat veure això en acció, si vaig a hello1.c--aquest és un dels primers programes que vam veure - normalment volem compilar aquest amb hello1.c Clang i això ens donaria a.out. Si per contra en el seu lloc donar-li l'opció-S, el que s'obté és hello1.s i que realment va a veure el llenguatge assemblador.
Estic fent això per un programa molt curt, però si tornes per Scramble o Recuperar o qualsevol programa que vostè ha escrit i només per curiositat volen veure el que realment sembla, el que en realitat s'alimenta a la CPU, pot usar aquest comandament-S amb Clang. Però llavors, finalment, encara hi ha un Gotcha. Aquests són el 0 i 1 que representa la meva implementació de hola, món. Però he utilitzat d'una altra persona en funció del meu programa. Així que, encara que el procés ha estat tom hello.c, que es compila en codi assemblador, i després s'ensamblen en 0s i 1s, l'únic 0s i 1s que es generen en aquest punt en el temps són les que resulten del meu codi. Però la persona que va escriure printf, que compileu el codi fa 20 anys i està ara instal · lat en algun lloc en l'aparell, per la qual cosa d'alguna manera ha de combinar els seus 0s i 1s amb la meva 0s i 1s, i que ens porta a la quarta i última etapa de compilació, coneguda com la vinculació. Així que a la banda esquerra tenim la mateixa imatge exacta com abans: hello.c es converteix en codi assemblador converteix en 0s i 1s. Però recordem que he utilitzat l'estàndard d'E / S de la biblioteca en el meu codi, i això vol dir que en algun lloc en l'equip hi ha un arxiu anomenat stdio.c o almenys la versió compilada dels mateixos perquè algú fa alguns anys compilat stdio.c en codi assemblador i després un munt de 0s i 1s. Això és el que es coneix com estàtica o una biblioteca dinàmica. És algun arxiu que seu en algun lloc de l'aparell.
Però, finalment, he de portar al meu 0s i 1s i aquesta persona 0s i 1s i d'alguna manera ells s'uneixen, literalment combinar els 0s i 1s en un sol arxiu anomenat a.out o hello1 o el que vaig trucar al meu programa de manera que el resultat final té tots els 1s i 0s que ha componen meu programa. Així que tot aquest temps aquest semestre quan vostè ha estat utilitzant Clang i més recentment d'executar make per executar Clang, tots aquests passos s'han anat succeint una mena d'instantània però molt deliberadament. I així, si continua en ciències de la computació, és a dir, CS61, aquesta és la capa que vostè continuarà pelar fora d'allà parla d'eficiència, implicacions de seguretat, i similars d'aquests detalls de nivell inferior. Però amb això, estem a punt de deixar enrere C. Seguirem endavant i prendre el nostre fill de 5 minuts de descans ara, i quan tornem: la Internet. Està bé. Estem de tornada. Ara comencem la nostra mirada no només en HTML, ja que, com es veurà, HTML en si mateix és realment molt simple però realment en la programació web en general, la creació de xarxes en general, i com totes aquestes tecnologies s'uneixen que ens permeti crear programes molt més sofisticades sobre l'Internet que fins ara hem pogut en aquestes finestres en blanc i negre. De fet, en aquest punt en el semestre tot i que passarà un temps relativament menys en PHP, HTML, CSS, JavaScript, SQL i més, majoria dels estudiants acaben fent treballs finals que són basat en la web perquè, com es veurà, el fons que ara tenim en C és molt aplicable a aquests llenguatges d'alt nivell.
I a mesura que comences a pensar en el seu projecte final, que, igual que 0 Sèrie de problemes, on es va encoratjar per fer gairebé qualsevol cosa del seu interès en Scratch, El projecte final és la teva oportunitat de prendre el seu nou coneixement i comprensió amb C o PHP o JavaScript o similar per fer un tomb i crear el seu propi tros de programari perquè el món vegi. I a les llavors que amb idees, saber que pots anar aquí, projects.cs50.net. Cada any, sol · licitar idees dels professors i el personal i grups d'estudiants al campus només perquè presentin les seves idees per a coses interessants que podrien ser resolts utilitzant ordinadors, ús de llocs web, utilitzant el programari. Així que si vostè està lluitant per arribar a una idea pròpia, per tots els mitjans desplaçar-se a través de les idees allà des d'aquest any i el passat. Està perfectament bé per fer front a un projecte que ha estat abordat abans. Hem vist moltes de les aplicacions per veure l'estat de bugaderia al campus, moltes de les aplicacions per navegar pel menú del menjador, moltes de les aplicacions de la navegació pel catàleg de cursos i similars. I, en efecte, en una conferència futur i en futurs seminaris, que li donarà a conèixer algunes API a disposició del públic, tant comercialment disponible així com aquí CS50 disponible al planter perquè tingui accés a les dades i llavors pot fer coses interessants amb ell. Així que més sobre els projectes finals en pocs dies quan deixem anar el plec de condicions, però per ara, saber que es pot treballar sol o amb un o dos amics en la majoria de qualsevol projecte del seu interès. La Internet. Veu i treu el seu portàtil, vostè va a facebook.com, per primera vegada, no haver registrat recentment, i premeu Enter. Què passa exactament?
Quan es prem Enter en l'equip, un munt de passos iniciar una qüestió de màgia passa. Així que aquí, al servidor d'esquerra, web com Facebook està aquí a la dreta, i d'alguna manera està utilitzant aquest llenguatge anomenat HTTP, Hypertext Transfer Protocol. HTTP no és un llenguatge de programació. És més aviat un protocol. Es tracta d'un conjunt de convencions que els navegadors web i servidors web utilitzen quan comuniquen entre si. I el que això significa és el següent. Igual que en el món real, tenim aquestes convencions on si compleix algun humà per primera vegada, si no et fa res em seguia el corrent aquí, Jo aniria de tu, diuen: "Hola, em dic David." >> Hola, David. El meu nom és Sammy. "Hola, David. Meu nom és Sammy". Així que ara que hem participat en aquest tipus de protocol humà ximple on he iniciat el protocol, Sammy ha respost, ens hem donat la mà, i la transacció s'ha completat. HTTP és molt similar en esperit. Quan el seu navegador sol · licita web www.facebook.com, el que tu navegador està fent realment està estenent la seva mà, per dir-ho, al servidor i està enviant un missatge. I aquest missatge és típicament una cosa com usar-lo - Què vols aconseguir? - me la pàgina d'inici, que normalment s'indica per una sola barra en l'extrem d'un URL. I perquè ho sàpigues quin idioma estic parlant, el navegador et vaig a comptar que estic parlant versió HTTP 1.1, I també per si de cas, et diré que el host que vull que la pàgina d'inici de és facebook.com. Normalment, un navegador web, sense el coneixement de tu, l'ésser humà, li envia aquest missatge a través d'Internet en les que simplement escriure www.facebook.com,
Retorn al seu navegador. I què significa respondre a Facebook? Respon amb alguns detalls críptics d'aspecte similar, però també molt més. Deixa anar endavant a la pàgina principal de Facebook aquí. Aquesta és la pantalla que la majoria de nosaltres probablement mai vegi si romandre connectat tot el temps, però això és de fet la seva pàgina d'inici. Si fem això en Chrome, observi que vostè pot aixecar aquests menús contextuals petits. Amb Chrome, ja sigui en Mac OS, Windows, Linux, o similar, Si controles clic o clic amb el botó esquerre, normalment pot aixecar un menú que té aquest aspecte, on algunes opcions esperen, un dels quals és d'origen Vista de pàgina. També pot obtenir normalment a aquestes coses per anar al menú Veure i ensumant. Per exemple, aquí a Veure, Developer és la mateixa cosa. Vaig a seguir endavant i mirar a la font Vista de pàgina. El que veuràs és el codi HTML que Marc ha escrit per a representar facebook.com. És un desastre complet aquí, però anem a veure que això té sentit una mica més en poc temps. Però hi ha algunes pautes aquí. Permetin-me desplaceu-vos cap avall per coses com aquesta. Això és difícil per a un ésser humà de llegir, però nota que hi ha aquest patró de parèntesi angulars amb paraules clau com a opció, paraules clau com a valor, algunes cadenes entre cometes. Aquí és on, quan es va registrar per primera vegada, s'especifica quina és el seu any de naixement és. Aquest menú desplegable d'anys de naixement és quelcom no codificat aquí en aquest llenguatge anomenat HTML, HyperText Markup Language. En altres paraules, quan el navegador sol · licita una pàgina web, parla aquesta convenció anomenat HTTP. Però, què facebook.com respondre a aquesta petició amb?
Respon amb alguns d'aquests missatges críptics, com veurem en un moment. Però la major part de la seva resposta està en la forma d'HTML, HyperText Markup Language. Aquest és el veritable llenguatge en què està escrit d'una pàgina web. I el que un navegador web realment és, llavors, a la recepció d'una cosa que són aquestes, llegeix de dalt a baix, d'esquerra a dreta, i cada vegada que el veu un d'aquests parèntesis angulars seguit d'una paraula clau com a opció, es mostra que el llenguatge de marcat de la manera apropiada. En aquest cas, es podria visualitzar un menú desplegable d'anys. Però de nou, això és un complet desastre a la vista. Això no és perquè els desenvolupadors de Facebook 0 per manifestar 5 per estil, per exemple. Això és perquè la major part del codi que s'escriu és, de fet, molt ben escrit, ben documentat, amb una sagnia bé, i similars, però les màquines de cursos, ordinadors, navegadors realment no els importa un rave si el codi està bé llaurada. I, de fet, és totalment antieconòmic per colpejar la tecla de tabulació totes aquestes vegades i posar tots els comentaris a través del seu codi i de triar els noms de variables descriptius realment perquè si el navegador no li importa, tot el que estem fent al final del dia és perdre bytes.
Així que resulta que la majoria dels llocs web és fer tot i que el codi font per facebook.com, per cs50.net i tots aquests altres llocs web a Internet són ben escrit i ben documentat i ben sagnats i similars, en general abans que el lloc web es col · loca a Internet, el codi es minified, de manera que el HTML i el CSS - una mica més que aviat ho veurem - el codi JavaScript aviat veurem es comprimeix, de manera que els noms llargs de variable d'esdevenir X i Y i Z, i tots els que els espais en blanc que fa que tot sembli tan llegible és tot tirat, perquè si es pensa en això d'aquesta manera, Facebook té una pàgina de mil milions de visites al dia - una cosa així de boig - per la qual cosa si un programador per estar anal prem la barra espaiadora una vegada extra només per sagnar alguna línia de codi cada vegada molt més? Quina és la implicació que si Facebook conserva espais en blanc en tots els bytes que s'envien a la gent a Internet? Colpejar la barra espaiadora una vegada que es dóna un byte al vostre arxiu. I si mil milions de persones després de descarregar la pàgina principal d'aquest dia, quant més dades ha transmès a través d'Internet? Un gigabyte per cap bona raó. I concedeix, per un munt de llocs web que no és un tema tan escalable, però per Facebook, per Google, per alguns dels llocs web més populars hi ha gran incentiu econòmic perquè el seu codi semblar un embolic per tal que vostè està utilitzant com pocs bytes com sigui possible, a més de llavors comprimir utilitzen una part com zip, un algoritme anomenat gzip, que el navegador fa de forma automàtica. Però això és horrible. Mai anem a aprendre qualsevol cosa sobre els llocs web d'altres persones i com dissenyar pàgines web si hem de veure-ho així.
Així que, afortunadament, navegadors com Chrome i l'IE i Firefox en aquests dies normalment vénen amb eines de desenvolupament integrades. De fet, si vaig per aquí a Inspeccionar Element o si vaig a veure, Developer, i vagi a Eines de Desenvolupament de manera explícita, aquesta finestra a la part inferior de la meva pantalla ara apareix. És una mica intimidatori al principi, perquè hi ha un munt de fitxes desconeguts aquí, però si faig clic a Elements de tot el camí a la part inferior esquerra, Chrome és, òbviament, molt intel · ligent. Sap com interpretar tot aquest codi. I el que fa és que Chrome es neteja tot l'HTML de Facebook. Tot i que no hi ha espais en blanc allà, no hi ha sagnia allà, ara adonar que jo pugui començar a navegar per aquesta pàgina web encara més jeràrquica. Resulta que totes les pàgines web escrites en un llenguatge anomenat HTML 5 ha de començar amb això, aquesta declaració DOCTYPE, per dir-ho així: És una mica de llum i de color gris allà, però aquesta és la primera línia de codi a l'arxiu, i que li diu al navegador, "Hey, aquí ve una mica d'HTML5. Aquí ve una pàgina web." El primer tram obert més enllà que passa a ser això, un claudàtor obert tag HTML, i després, si em capbusso en el més profund - aquestes fletxes són completament sense sentit; no són més que per l'amor de presentació, ells no estan realment a l'arxiu - compte que dins de l'etiqueta HTML de Facebook, alguna cosa que comença amb un claudàtor obert i després té una paraula es denomina una etiqueta. Així que dins de l'etiqueta HTML és aparentment una etiqueta del cap i un cos de l'etiqueta. Dins de l'etiqueta del cap ara és un embolic per Facebook perquè tenen una gran quantitat de metadades i altres coses per a la comercialització i la publicitat.
Però si es desplaça cap avall, avall, avall, avall, veurem on és. Aquí està. Aquesta és almenys alguna cosa familiar. El títol de la pàgina principal de Facebook, si mai punxi a la pestanya a la barra de títol, és Benvingut a Facebook - Entrar, Registreu-vos o més. Això és el que es veu a la barra de títol de Chrome, i això és el que està representat en el codi. Si deixem de banda tota la resta al cap, la major part de les entranyes d'una pàgina web es troben al cos, i resulta que el codi de Facebook s'assemblarà més complex que la majoria de les coses que anem a escriure inicialment només perquè s'ha construït al llarg dels anys, però hi ha un munt d'etiquetes de script, el codi JavaScript, que fa que el lloc web molt interactiva: veure les actualitzacions d'estat de forma instantània utilitzant llenguatges com Javascript. Hi ha una cosa que es diu un div, que és una divisió d'una pàgina. Però abans d'arribar a aquest detall, anem a tractar d'allunyar i veure una versió més simple de Facebook 1.0, per dir-ho. Aquí està el hola món, de les pàgines web. Té aquesta declaració DOCTYPE a la part superior que és una mica diferent de tota la resta. Res més que escriure en una pàgina web començarà amb per negreta. Un cop més, la història és la mateixa: hello, coma, començar a fer aquesta audaç, llavors el món s'imprimeix en negreta, i això significa deixar d'imprimir això en negreta. Deixin-me seguir endavant i salvar el meu arxiu, torni a Chrome, vaig a fer un zoom només perquè puguem veure millor, i tornar a carregar, i veuràs que el món es troba ara en negreta. La xarxa és sobre els hipervincles, així que seguirem endavant i fer això: meu lloc favorit és, diguem, youtube.com. Guardar, carregar. Bé. Hi ha un parell de problemes ara, a més de la lletjor de la web. 1, estic bastant segur que premeu Enter aquí. I ho vaig fer. No bé Enter, també sagnat, practicar el que hem estat predicant sobre l'estil, però el meu està just al costat del món. Per què és això? Els navegadors només fer el que els diuen que facin. No li he dit el navegador ", les línies de ruptura aquí. Inseriu el paràgraf trencar aquí." Així que el navegador, no importa si li pego Retorn 30 vegades, encara posarà al costat del meu món. El que realment cal fer aquí és dir alguna cosa com
, inseriu un salt de línia.
I en realitat, un salt de línia és una espècie de cosa rara perquè no es pot començar a moure a una altra línia, i després fer alguna cosa, i després deixar de moure a una nova línia. És una espècie d'una operació atòmica. O ho fan o no. Vostè prem Intro o no. Així br és una mica d'una etiqueta diferent, de manera que he de ordenar de tots dos oberts i tancament tot d'una vegada. La sintaxi que és aquesta. Tècnicament, es podria fer alguna cosa com això en algunes versions d'HTML, però això és una estupidesa, perquè no hi ha raó per iniciar i aturar una mica si en el seu lloc pot fer tot alhora. Adonar-se que HTML5 no és estrictament necessari que aquesta barra, pel que veurà els llibres de text i recursos en línia que no la tenen, però per si de cas anem a practicar la simetria que hem vist fins ara. Això significa que l'etiqueta és alhora obert i tancat. Així que ara anem a salvar el meu arxiu, torneu aquí. Bé, pel que està començant a veure millor, a excepció de la web que sé és una mena de clic, i, no obstant això youtube aquí no semblen conduir a res. Això és perquè tot i que es veu com un enllaç, el navegador no sap que per se, així que he de dir-li al navegador que es tracta d'un enllaç.
La manera de fer això és utilitzar una etiqueta d'ancoratge: i em va deixar passar això a una nova línia just pel que és una mica més llegible, i vaig a reduir la mida de font. Estic fet encara? No No serà aquesta dicotomia. Aquesta etiqueta, l'etiqueta d'àncora, en efecte, tenir un atribut, que modifica el seu comportament, i el valor d'aquest atribut és aparentment URL de YouTube. Però cal notar la dicotomia és que només perquè aquesta és la URL que va a, això no vol dir que ha de ser la paraula que està subratllat i fer un enllaç. Més aviat, que pot ser alguna cosa com això. Així que he de dir aquesta paraula deixa de fer un hipervincle mitjançant l'etiqueta d'àncora prop. Noteu que no estic fent això. 1, això només seria una pèrdua de temps per a tots i no cal.
Per tancar una etiqueta, només s'esmenta el nom de l'etiqueta de nou. No esmenta cap dels atributs. Així que anem a salvar això, anar cap enrere. Bé, llest, ara és blau i amb hipervincles. Si fa clic, em fa realment anar a YouTube. Així que, encara que la meva pàgina web no està a Internet, és almenys HTML, i si deixem que l'Internet a posar-se al dia, que en realitat acabaria aquí, a youtube.com. I puc tornar enrere i aquesta és la meva pàgina web. Però fixa't en això. Si alguna vegada has rebut spam o un atac de phishing, Ara vostè té la capacitat després de només cinc minuts per fer el mateix. Podem anar-hi i fer alguna cosa com www.badguy.com o el que el lloc web és incompleta, i llavors es pot dir verificar el teu compte PayPal. [Rialles] I ara això anirà a badguy.com, que no vaig a fer clic a perquè no tinc ni idea d'on condueix. [Rialles]
Però ara tenim la capacitat per posar fi realment allà. Així que realment estem començant a esgarrapar la superfície. No estem programació en si, que estem escrivint llenguatge de marques. Però tan bon punt es completen nostre vocabulari en HTML, introduirem PHP, un llenguatge de programació real que ens permetrà generar automàticament codi HTML, CSS generar de forma automàtica, perquè puguem començar dimecres per posar en pràctica, per exemple, nostre propi motor de cerca i molt més. Però més sobre això en un parell de dies. Ens veiem llavors.
[CS50.TV]