[Powered by Google Translate] [Week 7] [David J. Malan - Harvard Universiteit] [Hierdie is CS50. - CS50.TV] Alles reg. Welkom terug. Dit is CS50, en dit is die begin van die week 7. 'N paar van die min aankondiging: Pset5 is nou aan die gang is, of so spoedig moontlik sal wees, En laat ek sê, eerlik te wees, dit is geneig om te wees onder die meer uitdagende van die kursus se probleem stelle, so laat my noem dit nou sodat hierdie week ooit meer as jy wag nie tot, sê, Woensdag nag of Donderdag nag te duik. Dit is beslis 'n interessante pset. Ons dink dit is pret. As jy eintlik kry dit ten volle korrek en kan dan daag die sogenaamde Big Raad, jy het 'n geleentheid om verstand te pas met 'n paar van die kursus se personeel en 'n paar van jou klasmaats. Wat Die Groot Raad is, is wanneer jy jou speltoetser werk, jy sal in staat wees om te gaan na die uitvoer van 'n opdrag te cs50.net, suiwer kies in, en dan die bedrag van die tyd en die bedrag van RAM en meer wat jy gebruik het in jou implementering sal hier uitgestal word op die kursus se tuisblad. Jy sal sien dat 'n hele klomp van hierdie mense hier is gelys as personeel sedert die naweek, die personeel het gedink dit sou pret om te probeer om mekaar te oortref. So besef dat die doel hier is nie om die personeel te oortref. Selfs ek is net hier op nommer 13. Suiwer kies in, maar dit is 'n geleentheid om te sien hoe min RAM en hoe min CPU sekondes wat jy kan gebruik om vis-a-vis paar van jou klasmaats. En ek sal erken dat Kevin Michael SchmidtEndLink, tans in die nommer 1 posisie as een van die TFS, dit is 'n implementering wat ons noem nie moontlik gegee dat hy byna 0 RAM en byna 0 sekondes gebruik vir die laai. So ons sal sorg van Kevin regte pad. [Lag] Daar is sekere vaardighede wat Kevin is om die toets hier. Een van die dinge wat ons gedink het ons wil doen is ook nou CS50x is 'n week aan die gang, en julle is net soveel 'n deel van hierdie eksperiment as die studente. Ons het hulle gevra as deel van hul pset0, wat insgelyks 'n Scratch projek in te dien van belang is vir hulle - 'n spel, 'n interaktiewe stuk van kuns, 'n animasie, of iets dergeliks - 'n 1 - 2-minute video, indien hulle wil, sê hallo vir die wêreld en wat hulle werklik is. Ek het gedink ek wil dit deel met julle net 'n paar van die video's wat tot dusver voorgelê want vir ons is, ten minste op die personeel, is dit regtig is opwindende en inspirerende hierdie mense van oor die hele wêreld om te sien - lande oor die hele wêreld - transaksies in, van alle dinge, 'n rekenaar wetenskap op die Internet, of is dit omdat hulle wil hul eie studies voort te sit, hulle wil hê om hul loopbane te neem in 'n nuwe rigting, hulle wil hê om in te vul gapings in hul eie kennis, so 'n paar van die dieselfde redes dat julle miskien hier. So ek gee jou 'n sodanige student hier. Jy kan die volume te verhoog net 'n bietjie. Hier is een van ons studente se 1-minuut voorleggings. Hello, world. Ek is 'n student van die industriële ingenieurswese hier in Malaga, Spanje. Ek is opgewonde oor hierdie aanlyn kursus, want ek is lief vir rekenaar wetenskap, Ek het regtig nie, en Ek het werklik waardeer dat ek kry om dit te verken. En die feit dat ek dieselfde al julle ouens doen, kan leer maar in plaas van in Harvard Ek is in Malaga, hoe ontsagwekkend is dit nie? Wel, ek is Fernando, en dit is CS50. Sien julle ouens. [Lag] Nog 'n clip wat ons veral hou, sal jy vind dat hierdie man se Engels nie so sterk is nie. Dit lyk asof hy dit in die masjien vertaal, sodat die vertalings self is 'n bietjie onvolmaakte, maar dit was een van ons gunstelinge so ver as goed. [♪ ♪] Hello, world. [Praat in Japannees] [Ek het om te groet in Japannees, want my Engels is baie onbetroubaar.] [Ek gee die boodskap aan jou uit die stad van Gifu, Japan.] [Ek kan 'n student vir die eerste keer in 20 jaar, soos gesien kan word.] [Ek is baie dankbaar aan die Universiteit van Harvard wat aan my gegee het hierdie geleentheid en EDX.] [Golf is 'n kitaar en my gunsteling ding aan die gang.] [Lag] [♪ ♪] [Waarom dink jy ek het probeer 'n cs50x by te woon.] [Universiteit van Harvard, dit is my verlange.] [Veral as ek ver teenwoordigheid in Japan gewoon het.] [Ek wil om te probeer om onmiddellik bewus van die bestaan ​​van sodanige EDX toe.] [Dink jy nie sodat jy nie met betrekking tot die ouderdom van leer I.] [Cs50 is my verlange. My naam is Kazu, en dit is cs50.] [♪ ♪] [applous en juig] Nog 'n gunsteling van ons was hierdie voorlegging hier van iemand. [♪ ♪] [Malan] Google dit as jy onbekend is met hierdie meme. En dan laastens, 'n paar van die ander wat het gepos dat dit dalk die pragtige toekenning wen. [Studente] Aww! >> [Malan] Ons sal hê om te luister. Dit is kort, so nou luister. [Vroulike spreker] Wat is jou naam? >> Louie. [Vroulike spreker] Wat is dit? >> [Giggel] CS50. [Lag] [Malan] Hy het twee neem, al is. Hier gaan ons, die laaste. My naam is Louie, en dit is CS50. [Lag] Dit is dan CS50x. Dankie aan almal van dié van julle, terwyl die volgende saam by die huis wat tot dusver deelname. Vandag, ons sluit ons bespreking van die data strukture, ten minste sommige van die mees fundamentele, en dan sal ons voortgaan om ons gesprek oor HTML en web ontwikkeling. Inderdaad, het ons het die afgelope sowat sewe weke op soek na die grondbeginsels van programmering - algoritmes, data strukture, en dies meer - en C, as jy tot dusver ervaar het, is nie noodwendig die mees toeganklike van tale waarmee sommige van daardie idees te implementeer. En so het die begin van hierdie week en volgende week en dan die volgende, ons sal uiteindelik in staat wees om die oorgang van C, wat algemeen bekend staan ​​as 'n redelik lae-vlak taal, aan dinge hoër vlak, onder hulle PHP, JavaScript, en dies meer, wat ons sal sien trek op dieselfde lesse wat ons geleer het oor die afgelope paar weke, maar jy sal vind dat die dinge verkondig soos skikkings en hash tabelle en soek-en sorteer soveel makliker geword omdat die tale self sal ons begin met behulp van sal meer kragtige. Maar eers, 'n aansoek van die bome. Dit is baie algemeen hierdie dae nodig om inligting te compress. In watter konteks wil jy 'n soort van digitale inligting te compress? Ja. >> [Student] Wanneer jy nodig het om dit te stuur oor die web. Ja, wanneer jy iets oor die web te stuur. As jy wil 'n groot lêer te laai, dit is ideaal as iemand aan die ander kant saamgepers om die lêer met behulp van 'n zip-formaat of iets soos dit sodat jy die stuur van minder stukkies as wat dit andersins oorgedra word. So hoe compress jy inligting? Dit kom alles neer op die gebruik van minder stukkies as by verstek word vereis. Maar dit is 'n soort van 'n snaakse ding, want dink terug aan weke 0 en 1 toe het ons gepraat oor ASCII-en binêre en het ons gepraat oor ASCII in die besonder met behulp van 8 stukkies letters van die alfabet te stel sodat die letter A word verteenwoordig deur 65 kleinletter a is die getal 97, en hoe jy die 65 of 97, 7 of 8 bisse gebruik. Maar die vangs is dat daar is 'n paar briewe in die Engelse alfabet wat is nie so gewild soos die ander. Z is nie alles wat gewild, Q is nie al wat gewild, maar A en E is super gewild. En tog vir almal van hierdie briewe, by verstek die wêreld maak gebruik van die dieselfde aantal bisse, net 8. So sou dit nie gewees het nie slimmer as in plaas van die gebruik van 8 bisse vir elke brief, selfs die mees selde gebruik word soos Q en Z, wat as ons gebruik minder stukkies vir A en E en S en die mees gewilde letters en gebruik meer stukkies vir die minder gewilde letters, die idee laat se optimaliseer vir die algemene geval, wat is 'n tema in die rekenaar wetenskap probeer om te optimaliseer wat gaan die meeste om te gebeur en spandeer 'n bietjie meer tyd, 'n bietjie meer ruimte op die dinge wat, ja, kan gebeur maar nie noodwendig so dikwels. So laat ons neem 'n voorbeeld. Veronderstel dat ons meer inligting wil ontvang redelik doeltreffend enkodeer. Jy kan grootgeword het wetende dat 'n bietjie iets oor Morse kode, en die kans is jy nie weet wat die werklike kode, maar jy kan onthou dat dit is ten minste hierdie reeks van kolletjies en strepies. Dit is 'n redelik doeltreffende kodering, en kennis dat die mees gewilde letter - byvoorbeeld, E - gebruik die kortste van biep. Morsekode is al oor die biep-biep-biep-biep-biep-biep en hou van die toon hetsy vir kort periodes van tyd of lang periodes van tyd. E, soos aangedui deur die kolletjie, is 'n super kort biep, net biep, en dit sou verteenwoordig E. In teenstelling hiermee, sal T 'n lang beep, soos beep [verleng klank, en dit sou verteenwoordig T. Maar dit is nog redelik kort, want, in teenstelling, as jy kyk na Z, Z te druk sou jy biep, biep [meer gesonde], biep, biep [korter klank] gaan. So dit is meer, want dit is minder algemeen. Maar die Gotcha hier is dat Morsekode is 'n bietjie gebrekkig in die sin dat dit is nie dadelik Deco Deer. Byvoorbeeld, veronderstel dat jy hoor op 'n paar einde van die draad beep [short], biep [lank]. Watter boodskap het ek net ontvang? 'N punt en 'n streep. Wat nie dat verteenwoordig? [Student] A. >> [Malan] Miskien. Dit kan ook wees E gevolg deur T. Met ander woorde, Morsekode, maar dit maak gebruik van hierdie beginsel van die optimalisering van die hoek geval, dit leen hom nie tot onmiddellike decodability. Dit is die mens wat dit hoor, of die ontvangs van hierdie kolletjies en strepies om een ​​of ander manier uit te vind waar die breek is tussen letters, want as jy nie weet waar daardie pouses is, kan jy dalk verwar A vir ET of vice versa. So, wat kan jy doen? In Morsekode kan jy net breek tussen elk van die letters. Maar pousering is soort teenvoeter vir die hele punt van die bespoediging dinge. So, wat as plaas ons vorendag gekom met 'n kode, waar daar was nie hierdie slegte situasie waar E 'n voorvoegsel, byvoorbeeld, van 'n - met ander woorde, as ons seker kan maak dat die patrone is nog steeds kort vir die gewilde letters lank vir die minder gewilde letters, maar daar is geen moontlike verwarring? 'N man met die naam van Huffman jaar gelede uitgevind hierdie skema, genoem Huffman kodering wat maak eintlik een van die data strukture wat ons het 'n bietjie tyd spandeer praat die afgelope week, wat van bome, binêre bome spesifiek - 'n binêre boom wat beteken dat dit nie meer as 2 kinders. Dit het miskien 'n linker kind, miskien 'n regte kind, en dit is dit. So veronderstel net ter wille van die bespreking wat iemand wil hê om 'n boodskap te stuur wat lyk soos hierdie. Dit is 'n volledige nonsens maar dit saamgestel van As, Bs, Cs, Ds, en Es. En as jy eintlik tel tot al van die AS, BS, Cs, Ds, en Es en dan verdeel deur die totale getal van die briewe, hierdie klein grafiek hier sê dat 45% van die briewe Es is, 20% is soos, 10% Bs, en so meer. So met ander woorde, aanvaar dat die aangehaalde string daar is net 'n boodskap wat jy wil stuur. Dit gebeur te wees nonsens net sodat ons dit kan gebruik as 'n paar briewe as moontlik, maar dit is wel die geval is dat E steeds die mees gewilde, en B en C is die ongewildste, ten minste van hierdie 5 letters van die alfabet. So hoe kan ons gaan om te kom met 'n kodering, 'n binêre-kodering, 'n patroon van 0'e en 1s vir elk van hierdie briewe in so 'n manier dat die E is 'n kort patroon en miskien B en C is effens langer patrone, weer, die idee is dat ons wil gebruik minder stukkies die meeste van die tyd en nog baie meer stukkies slegs een keer in 'n rukkie. Volgens Huffman kodering, kan jy 'n bos van die bome. Daar is 'n soort van 'n storie lyn wat behels die bome en ook die proses van die bou van hulle. Kom ons begin. Ek stel voor dat jy begin met die bos, om so te praat, 5 bome, elkeen wat 'n redelik dom boom. Die boom is saamgestel uit net 'n enkele nodus, soos verteenwoordig deur 'n sirkel. So elkeen van hierdie dinge kan 'n C struct en binnekant van die C struct kan 'n float wat die frekwensie tel en dan miskien 'n char wat die brief. Van hierdie nodes so te dink as net 'n ou C struct, maar vir nou, 'n hoër vlak. Dit is 'n bos van 5 bome, elk van wat slegs 'n enkele nodus. Wat Huffman voorgestelde is dat ons begin om die bome te kombineer wat die kleinste frekwensie tellings in effens groter bome deur die koppeling van hulle met 'n nuwe wortel node. So tussen die letters hier opmerk dat ek vir gerief hulle het gesorteer van links na regs, alhoewel dit is nie streng noodsaaklik is, en kennis dat die kleinste nodes is tans 10% en 10%. So Huffman het voorgestel dat ons saamsmelt daardie 2 kleinste nodes in 'n nuwe boom deur die bekendstelling van 'n nuwe ouer node en dan gee dat die ouer 'n linker kind en 'n regte kind waar B arbitrêr is die linker-en C is arbitrêr die reg. En dan Huffman het verder voorgestel dat laat ons net nou dink van die linker kind in een van hierdie bome altyd soos verteenwoordig deur 0 en die regte kind altyd soos verteenwoordig deur die aantal 1. Dit maak nie saak as jy flip hulle so lank as wat jy konsekwent. So nou het ons vier bome in die bos. En ek sê vier, want nou is die boom aan die linkerkant - en dit is nie soseer 'n boom in die sin dat dit groei op hierdie manier, dit is meer soos 'n stamboom waar nou die 0,2 is 'n soort van die ouer van die twee kinders - opmerk dat ons in daardie ouer 0,2 het getrek. Ons het bygevoeg die frekwensie tellings van die twee kinders en gegee die nuwe node die totale bedrag. So nou het ons net hierdie proses herhaal. Vind die twee kleinste nodes en dan saam met hulle in 'n nuwe boom en dan herhaal die proses verder. Reg nou is ons het 'n paar kandidate, 20%, 15%, en die ander 20%. In hierdie geval, ons het die staking te breek. Ons kan dit doen arbitrêr. Ons moet maar net doen dit konsekwent. In hierdie geval, sal ek na willekeur gaan met die een op die linkerkant, en ek nou saamsmelt om die 20% en 15% te gee vir my 'n nuwe ouer 35% genoem, wie se linker kind is 0, wie se regterhand kind is 1, en nou het ons net drie bome in die bos. Jy kan dalk sien waar dit gaan. As ons herhaal 'n paar keer gaan ons net een groot boom te hê, almal wie se rande is gemerk met 0'e en 1s. Kom ons doen dit weer. 35% is dat die boom se wortel. 20% en 45%, sodat ons die 35% en 20% gaan om saam te smelt. Nou het ons hierdie boom hier. Ons voeg diegene saam, ons het 55%. Nou is daar net twee bome in die bos. Ons doen dit een laaste keer, en hopelik wiskundig al die frekwensies optel want hulle moet ons sedert bereken hulle van die get-go te voeg tot 100%. En nou het ons 'n boom. So, dit is 'n Huffman kodering boom. Dit soort van 'n rukkie geneem om daar te kom mondelings, maar die realiteit is met 'n lus of met 'n rekursiewe funksie, kan jy hierdie ding tot redelik vinnig bou. So nou het ons 'n nuwe node, en al van hierdie innerlike nodes is malloc'd, vermoedelik langs die pad. So nou by die top van die boom wat ons het 100% nie, maar kyk nou het ons 'n pad van hierdie nuwe groot-groot-groot-grootouer op alle van die groot-groot-groot-kleinkinders al die pad aan die onderkant, aan al die blare. Wat gaan ons nou doen, is stel voor dat ten einde die letter E voor te stel, ons sal net gebruik maak van die aantal 1. Hoekom? Want as ons deurkruis die boom van die finale wortel af aan die blaar bekend as E, ons volg net die een kant, die regter rand, en dit is natuurlik gemerk regs bo 1. So was die implikasie hier vir Huffman dat E die kodering in binêre regverdige sal wees 1. En dit is pretty damn doeltreffende. Kan nie regtig kry nie kleiner as dié. Daarenteen, is 'n lopende om verteenwoordig te word, as jy die logika volg, watter patroon van stukkies plaas? 01. So te kry om 'n, ons begin by die wortel en ons gaan links en dan gaan ons reg, wat beteken dat ons het gevolg op 'n 0 en dan 'n 1. So sal ons verteenwoordig die letter A met die patroon 0 en 1. En nou sien ons reeds 'n eiendom van onmiddellike decodability dat ons nie in Morsekode. Selfs al het beide van hierdie patrone is redelik kort - E is 1 bietjie, A 2 stukkies - agterkom dat hulle kan nie die een of die ander verwar word, want as jy sien 'n 1 dit het 'n E, as jy sien 'n 0 toe 'n 1 Dit is natuurlik het 'n A. Net so, wat is D? 001. Wat is C? 0001. En wat is B? 0000. En weer, omdat al die briewe wat ons omgee is op die blare en nie een van hulle is soort van middelmanne in die pad van wortel blaar, daar is geen risiko van conflating 2 letters verskillende coderingen omdat al die van hierdie bietjie patrone is deterministiese. 0000 sal altyd B. Daar is geen node iewers tussen wat jy dalk een brief vir die ander verwar. So, wat is die implikasie hier? Die mees gewilde letter - in hierdie geval E - gekry het die kortste kodering, A gekry het die volgende kortste kodering, en B en C, wat ons reeds geweet van die get-go was soort van die minste populêre frekwensie van 10% elk, het hulle die langste kodering gekry. En wat beteken dit nou is, is dat as jy wil om 'n boodskap te stuur wat saamgepers oor die internet of in 'n e-pos of iets dergeliks, eerder as die gebruik van standaard ASCII, kan jy stuur 'n gekodeerde boodskap Huffman waardeur as jy wil die letter E te stuur, stuur net 'n bietjie. As jy wil 'n A te stuur, jy stuur 2 stukkies, 01, in plaas van die stuur van 8 bisse gevolg deur 'n ander 8 stukkies gevolg deur nog 8 stukkies en so meer. Maar daar is 'n Gotcha hier. Dit is nie voldoende om net te konstrueer hierdie boom, en dan begin die stuur van Alice te Bob die korter bispatroon, string van ASCII, omdat Alice het ook Bob in te lig van wat as Bob gaan in staat wees om haar saamgeperste boodskap te lees? [Onhoorbaar student reaksie] >> Wat is dit? [Onhoorbaar student reaksie] >> van wat die boom is. Of selfs meer spesifiek, wat die enkoderings is, veral omdat in hierdie storie het ons 'n oordeel oproep op 'n punt. Onthou wat ons gehad het om na willekeur te kies tussen die 2 verskillende 20% nodes? So dit is nie die geval dat Bob, die ontvanger, kan net rekonstrueer die boom op sy eie want miskien het hy die boom sal ooit so iets verskillend van Alice skep. Daarbenewens het Bob nie eens weet wat die oorspronklike boodskap is omdat die enigste ding Alice stuur hom, natuurlik, is die saamgeperste boodskap. So het die vangs met kompressie soos hierdie is dat, ja, kan Alice 'n hele klomp van die stukkies red deur die stuur van 1 vir E en 01 vir A en so meer, maar sy het ook Bob in te lig wat die kartering tussen letters en stukkies want hulle kan duidelik nie staatmaak op net ASCII meer as ons nie die gebruik van ASCII. Sodat sy kan hom stuur die boom op een of ander manier - skryf dit neer, stoor dit as binêre data of iets soos dit - of stuur hom net 'n bietjie cheat sheet, 'n Excel-lêer, wat die afbeeldings. So het die doeltreffendheid van kompressie neem regtig dat die boodskappe wat jy stuur is redelik groot, ten minste medium-grootte, want as jy die stuur van 'n super kort boodskap, as jy net wil stuur die boodskap sleg, wat gebeur met 'n woord wat ons hier kan spel, B-A-D, jy waarskynlik gaan minder stukkies te gebruik, maar die vangs is, as jy ook 'n Bob in te lig wat die boom is of wat daardie enkoderings is, gaan jy waarskynlik swaarder as al die besparing met saamgeperste dinge om mee te begin. , Sodat dit kan die geval wees dat as jy probeer om die comprimeren selfs met iets soos zip of lêer formate jy dalk vertroud wees met - redelik klein lêers, selfs leë lêers - soms die lêers kan kry groter en nie kleiner. Maar realisties, dit gebeur net vir klein lêer groottes, so dit is nie van plan om 'n GB-lêer 2 GB; ons regtig praat bytes of net 'n paar kilogrepe. Sommige programme soos ZIP is slim genoeg om te besef dat, "Jy gaan meer stukkies comprimeren hierdie te spandeer." "Laat my nie pla comprimeren dit vir jou op alle." So dit is net een manier om van die comprimeren van die teks formaat. Ons kan iets soos hierdie te implementeer in C. Byvoorbeeld, hier is hoe ons kan 'n node verteenwoordig in hierdie boom waar ons 'n kar vir die simbool, 'n drywende waarde vir die frekwensie, en soos ons gesien het met ons ander datastrukture, 2 pointers, 1 aan die linkerkant kind, 1 aan die regterkant, een van wat kan wees NULL, maar indien nie, dit verwys na 'n links kind en 'n regte kind. So, dit is dan Huffman kodering, en dit is een manier wat jy kan gaan oor die comprimeren van inligting, en dit is beslis een van die mees maklik om te implementeer in die konteks van, sê, verlede week se data strukture, alhoewel selfs meer gesofistikeerde algoritmes bestaan wat selfs meer gesofistikeerd mutasies van jou data kan doen. Enige vrae en dan op bome, binêre bome, of kompressie van die teks? [Student] Is daar 'n dubbelsinnigheid, soos as [onhoorbaar] verdeel in 01, dan 011 sou wees dubbelsinnig, reg? [Onhoorbaar] >> Goeie vraag. Dubbelsinnigheid. Laat my opsomming te maak deur te verwys na hierdie foto hier. Omdat die karakters wat jy comprimeren, die vertoë van deur die omskrywing van hierdie algoritme altyd die blare, jy per ongeluk nooit gebruik maak van die dieselfde patroon van bisse vir die voorvoegsel van verskeie briewe. So in ander woorde, jy is bekommerd oor, dit klink soos, 'n dubbelsinnigheid wat voortspruit waardeur 001 kan die begin van B of die begin van C of iets soos dit. Maar dit kan nie die geval wees nie, want kennis dat al die letters van die alfabet ons kodering is op die blare. Die dubbelsinnigheid kan slegs ontstaan, soos in die geval van Morsekode, Indien, byvoorbeeld, C was iewers langs die pad vanaf die wortel tot B. [Student] Reg. Dus, in daardie geval, sê A het 2 blare. >> Sê 'n - Sê dit weer. [Student] Sê A het 2 blare, F en G, en dan G - >> Goed. Maar dit kan nie. A kon self nie die blare F en G omdat daardie briewe F en G sal hulle laat iewers aan die linkerkant van B of die reg van E. So per definisie, moet hulle blare. Andersins, jy is presies reg, het ons nie die probleem opgelos dat Morsekode gesigte. Goeie vraag. Ander vrae? Alles reg. Hierdie idee van bisse, dit blyk ons ​​het krag almal saam dat ons eintlik nog nie gebruik wanneer dit kom by hierdie 0'e en 1s te manipuleer. Ons het gevra oor dit op een van die vroegste probleem stelle: naamlik, hoe gaan jy oor die omskakeling van hoofletters na onderkas of andersom? Of, meer konkreet, een van daardie eerste psets gevra hoeveel stukkies jy het eintlik ten einde 'n A of andersom verander na onderkas om te draai? Hier is 'n vinnige herinnering van wat 65 en 97 kyk soos in binêre. En selfs as daardie vraag het soort van vervaag in jou geheue, jy kan weer sien hier dat Hoeveel bisse moet word omgekeer kapitaal te verander om 'n onderkas? Net een. Hulle verskil net in een plek, die derde bietjie van die linkerkant. AANGESIEN A het 'n 010, min 'n het 'n 011. So een of ander manier, moet ons net in staat wees om daardie bietjie om te draai, en dan kan ons hoofletters of kleinletters. Ons het dit gedoen in die verlede deur eintlik die gebruik van voorwaardes en te keur indien die brief is tussen kapitaal en kapitaal Z, dan uitsette soos 'n - a + 26 of iets soos dit. Jy het waarskynlik 'n rekenkundige verandering aan die letters van die alfabet. Maar wat as ons kon net flip dat die enkele bietjie? Hoe kon jy gaan oor die neem van een byte se waarde van stukkies, so 8 bisse soos 01.000.001 en 01.100.001? As jy het daardie patrone bisse, hoe kan ons gaan oor die verandering van net een van hulle? Wat gebeur as ons voer in geel hier ander patroon van bisse? As ek die hele geel string 0s behalwe vir die een stukkie wat ek wil om te verander en dan het ek 'n nuwe operateur bekend as 'n bis-operateur - bis in die sin dat dit werk op 'n individuele stukkies, nie op 'n hele byte of vier grepe alles op een slag nie. Hierdie vertikale bar daar in geel dui daarop dat wat as ons die voorstelling van kapitaal A bis of dit met die geel volgorde van stukkies? Met ander woorde, dink terug aan ons bespreking van Boole-uitdrukkings in Scratch en dan in C. Doen 'n Boolese of beteken dat waar te wees, óf die eerste ding om waar te wees of die tweede ding om waar te wees of hulle albei het om waar te wees, en dan die gevolglike uitset is waar. In hierdie geval hier, wat ons kry as ons 0 "of" ed met 0? Vals of onwaar? Dit is nog steeds vals is, sodat die kleinletter 'n bly soos verwag. Wat gebeur as in plaas ons doen 1 of 0? Dit bly nou 1, maar agterkom wat hier gebeur is. As ons begin met 'n hoofletter A en ons voortgaan om te "of" sy individuele stukkies as ons hier doen, 0 of die geel een gee vir ons wat hier onder? Dit gee ons 1. Om die waarheid te sê, dink ons ​​het nie geweet wat die hoofletters weergawe van min eintlik 'n was. Kom ons gaan doen dit. Laat my beweeg dit terug hier. Kom ons doen dit weer. 0 of 0 gee my 0. 1 of 0 gee my 1. 0 of 1 gee my 1. 0 of 0 gee my 0. Die volgende een is 0, die volgende een is 0, die volgende een is 0. 1 of 0 gee my 1. En so selfs al het ons nie vooraf weet wat kleinletter a was, deur eenvoudig "of" 'n met hierdie patroon van bisse wat ons hier het in geel, jy kan 'n kapitaal onderkas deur daarby daardie bietjie. Ons gebruik hierdie uitdrukking weke gelede: 'n bietjie daarby. Hoe doen jy eintlik dat programmaties? Jy gebruik wat algemeen bekend as 'n masker, 'n reeks van bisse, dat in hierdie geval gebeur net so om te lyk soos hierdie getal hier, en dan moet jy "of" dit saam met behulp van hierdie nuwe C-operateur, nie | |, jy gebruik 'n enkele | en jy sou eintlik hierdie antwoord hier want hoekom? Dit is die 1s, 2s plek, 4s, 8s, 16s, 32s. So dit blyk dat as jy 'n hoofletter A en bis of dit met die heelgetal 32, omdat die heelgetal 32, as jy kyk na dit as stukkies, so lyk, wat beteken dat jy kan die bietjie wat jy eintlik wil flip. En insgelyks - en ons sal kyk na die kode in net 'n oomblik - Gestel ons wil die ander rigting te gaan. Hoe gaan jy uit kleinletter 'n hoofletter A? Watter bietjie moet verander? Dit is dieselfde een. Ons wil hê dat die derde bietjie te verander van 'n 1 na 'n 0. En hoe kan ons te werk gaan om dit te doen? Hoe draai ons 'n bietjie af? Met watter patroon van bisse kan ons 'n bietjie af? Wat gebeur as ons sorteer invert die masker? AANGESIEN dit voor, ons het die hele geel masker 0'e behalwe vir die een stukkie wat ons wou om te draai op, wat as hierdie tyd, maak ons ​​die hele masker 1s, behalwe vir die bietjie wat ons wil afskakel en dan gebruik wat operateur? Wat gebeur as ons "en" dinge? Kom ons neem 'n blik. As ons nou Flip, veronderstel dat ek weer 'n masker wat is al 1s behalwe vir die een stukkie wat ek wil om te draai af en dan eerder as "of" die wit getalle tot bo met die geel nommers hier onder, wat as ek plaas "en" hulle saam? Dit is bekend as 'n bis. Logies, dit is dieselfde ding as 'n Boole-en. Dit gee my 0 & 1 is 0. So vals en ware is vals. Waar en waar is, is waar. En hier is die magic: ware en valse nou vals is, so ons het daardie bietjie afgeskakel. En nou die res van die storie is ietwat eenvoudig. Omdat die res van die masker is 1s, dit maak nie saak wat die getalle in wit. Wanneer jy "en" iets met die ware, jy nie gaan om die waarde daarvan te verander. As dit waar is, sal dit bly waar. As dit vals was, bly dit vals. Maar die magie gebeur wanneer jy iets wat was waar en jy dan "en" dit met vals. Dit het die effek van die draai af dat die bietjie. So 'n bietjie kripties. Kom ons eintlik kyk na 'n paar kode, wat werklik kan kyk nog meer kriptiese, maar laat ons neem 'n blik hier by tolower. As ek kyk by die tolower, gaan van kapitaal 'n 'n onderkas, laat ons sien hoe ons hierdie program te implementeer. Hier is die hoof, en dit is nie die neem van 'n command-line argumente. Ek verklaar 'n karakter c vir die brief wat die gebruiker gaan te tik. Ek gebruik dan 'n bekende te doen terwyl lus te maak net seker dat die gebruiker beslis gee my 'n hoofletter A of B of C. .. Z, so hulle gee my iets tussen A en Z. En nou, wat doen ek hier? Ek is "of" ing met 0x20, maar dit is eintlik dieselfde as - en ons kom terug na hierdie in 'n oomblik - 32. So weer, 32 is hierdie patroon bisse hier. Waarom weet ons dit? Net terug dink aan week 0. Dit is die 1s, 2s plek, 4s, 8s, 16s, 32s plek. So, dit geel aantal gebeur om te wees 32. Ek kan dan 'n brief soos die char hier, bis "of" dit met letterlik die getal 32, en wat kry ek terug? Die kleinletter weergawe van daardie char. 'N oomblik gelede, maar ek het hierdie in 'n ander basis notasie. Wat het dit voor? >> [Student] heksadesimaal. [Malan] Dit gebeur heksadesimaal te verteenwoordig. Ons het nie gepraat oor heksadesimale al dat daar nog baie, maar dit is eintlik handig in gevalle soos hierdie. Selfs al is dit lyk meer komplekse en hoewel dit lyk soos 20 en nie 32, dit blyk dat heksadesimaal eintlik is super gerieflike notasie want in heksadesimaal elke syfer na die 0x - en dit beteken niks nie; dit is net menslike konvensie wat sê hier kom 'n heksadesimale getal - elk van hierdie syfers, die 2 en dan die 0, kan hulle verteenwoordig word met presies 4 stukkies. So as ons dit doen, laat my oop te stel hier 'n teks editor - weird outovoltooiing - as ons dit doen hier 'n bietjie teks editor, beteken hier die aantal 0x20 4 bisse, hier is 'n ander 4 stukkies. Kom ons doen eers die regterkantste 4 stukkies. 0 wanneer verteenwoordig met 4 stukkies is wat? Super maklik. Net al 0'e. So 4 bisse as 0S. Hoe stel jy 2? Dit was 'n rukkie sedert ons het dit gedoen, maar dit is 0100. So, dit is die 1s plek, dit is die 2s plek, en dan is dit maak nie saak wat die ander plekke is. Met ander woorde, in heksadesimaal jy dalk sê 0x20, maar as jy dan dink oor wat is die 2 en hoe word dit in binêre verteenwoordig, wat is die 0 en hoe word dit in binêre verteenwoordig, die antwoorde op hierdie vrae is dit en dit, onderskeidelik. So gebeur 0x20 hierdie patroon van 8 bisse te stel, wat is presies die masker wat ons wou. So, dit is vir die oomblik net 'n intellektuele oefening, maar die realiteit is in die kode is dit tipies is meer algemeen konstantes soos hierdie te skryf in heksadesimaal, want dan kan die programmeerder relatief maklik, selfs indien dit vereis van sommige papier en potlood, uit te vind wat daardie patroon van die stukkies is want jy kan nie net druk 0'e en 1s tipies in die kode. Jy kan nie 00.010 en so meer. Jy het desimale of hexadecimale of oktale of ander notasies te kies. Die meeste mense is geneig om heksadesimaal eenvoudig so dat elke syfer 4 stukkies te kies en wat jy kan doen hierdie vinnige wiskunde. En Ek sal my hand beweeg op toupper, wat is byna dieselfde, dit lyk byna identies. Toupper gebeur nie of operateur, maar eerder hierdie man en df te gebruik. Wat df verteenwoordig? df? Iemand? >> [Student] 255. 255? Nie 255. Dit sou wees ff. Ons sal hierdie een laat as 'n bietjie oefening. Maar as jy gaan van 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 en dan wat kom na 9? Ons is soort van uit desimale syfers, maar in heksadesimaal wat kom na 9? [Student] a. >> So 'n, b, c, d. Jy kan uitvind van daar af watter patroon van stukkies d eintlik verteenwoordig. En as ons doen die wiskunde, sal ons sien dat die masker wat jy uiteindelik kry terug is identies aan hierdie een. Dit is f, alle 1s, en dit is d. So df daardie masker. Alles reg. En laastens, nie om dinge te laat klink super, super tegniese, maar veronderstel ons wou om 'n program te skryf wat dit doen. Laat my voort te gaan en maak binêre, wat is 'n program in 'n lêer genaamd binary.c. En nou, laat ek hardloop binêre en gee my 'n nie-negatiewe heelgetal. Kom ons begin maklik en tipe in 0. Dit is nou 'n program wat druk uit 'n heelgetal in sy binêre voorstelling. So as ek speel die spel weer en tik in net 1, moet ek 'n 32-bis voorstelling van 1. As ek dit doen weer met 2, moet ek kry. As ek dit doen 7, moet ek 'n paar 1s kry aan die einde en so meer. Dit blyk uit Ek noem dit omdat met bis-bedrywighede jy kan eintlik 'n ander ding doen as goed. Jy kan hierdie maskers dinamies. Neem 'n blik op hierdie een laaste voorbeeld wat bis-bedrywighede. Hier is die eerste deel van die kode, lei die gebruiker vir 'n aantal en dit dring daarop aan dat jy gee my 'n nie-negatiewe heelgetal. So dit is 'n soort van die ou skool stuff. Maar hier is iets wat interessant is soort. Hoe gaan ek oor die druk van 'n nommer in die binêre? Ek die eerste keer itereer van wat na wat? Wat is die grootte van 'n int tipies, ten minste in die toestel? >> [Student] 4. Dit is 4. So 4 * 8 32 - 1 is 31. So as ek begin te tel uit 31, wat verteenwoordig, dit blyk, net konseptueel, die 31ste bietjie of die hoogste orde bietjie, wat is hierdie man hier, terwyl dit gaan bietjie 0. So dit is bietjie 01 ... bietjie 31. So, wat is hierdie kode te doen? Let op hierdie lus, selfs al lyk dit kripties, net iterating van 31 af na 0. Dit is dit. Dus is die interessante deel moet nou in hierdie 5 lyne hier. Let daarop dat in hierdie lyn het ek 'n veranderlike genoem masker is verklaar te wees in ooreenstemming met ons storie van hierdie geel getalle. En dan wat is om dit te doen? Dit is 'n ander bis operateur het ons nie gesien het nie, waarskynlik. Dit is die linker verskuiwing operateur. Hierdie operateur doen dit. Hier is die getal 1, en as jy dit doen Ek het verskuiwing, links skuif, wat dink jy wat die effek van doen dat individuele 1? Letterlik skuif dit oor. Dus, as die nommer 1 is wat jy aan die linkerkant en jy begin deur die inisialisering i 31, wat dit gaan doen? Dit gaan hierdie nommer 1 te neem en skuif dit 31 plekke hier. En omdat daar natuurlik geen ander syfers agter dit, dié sal by verstek vervang word met 0s. So jy sal begin met die getal 1, wat natuurlik lyk soos hierdie - en laat my trek dit oor hier in die middel. En dan as jy dinge skuif na links, hierdie man gaan in wese op hierdie manier. Maar so gou as jy dit doen, kry 'n 0 gevul. As jy skuif dit 'n tweede keer, gaan dit op hierdie manier en 'n ander 0 kry gevul. Jy skuif dit weer en dan nog 'n 0 kry gevul. So as jy hierdie ding van 1 << i 31 plekke, jy eindig met 'n masker wat is 32 karakters lank, die linker een van die wat is 'n 1, almal van die res van wat is 'n 0. En dit blyk uit, as 'n eenkant, die verskuiwing van 'n nommer aan die linkerkant soos hierdie ook toevallig, en soms gerieflik, het die effek van doen wat aan daardie getal? >> [Student] Verdubbeling. Verdubbeling dit omdat elk van die kolomme - die 1s, 2s plek, 4s plek, 8s, 16s plek - they're al die verdubbeling as jy links gaan. Of eerder, wanneer jy skuif die 1s jy gaan aan die einde die verdubbeling van die waarde van die getal. Jy kan beland doen interessante transformasies van syfers deur die verskuiwing van alles op hierdie wyse deur die magte van 2. So hoe werk dit? Dit gee dan vir my 'n masker wat alle 0'e, behalwe vir 'n 1 in presies die plek waar ek dit wil hê, en dan hierdie uitdrukking, wat van toupper.c gesteel word, is eenvoudig sê die getal n dat die gebruiker ingetik in, "En" dit met daardie masker, en wat is jy gaan om te kry? Jy gaan 'n 1 te kry as daar 'n 1 in daardie gemaskerde plek, of jy gaan 'n 0 te kry as daar is nie. En so het al hierdie program is effektief dit het 'n lus, en dit skep 'n masker met 'n 1 hier, dan 'n 1 hier, dan 'n 1 hier, en gebruik dit hierdie bis EN truuk om te sê, is daar 'n 1 bietjie in die gebruiker se insette hier? Is daar 'n 1 bietjie in die gebruiker se insette hier? En indien wel, letterlik druk 1, anders druk 0. Ons is om dit te doen met ints net omdat dit is die rede waarom ons doen 32 bisse in plaas van 8, maar wat het ons dan ingestel is hierdie bis EN, hierdie bis of, en hierdie links verskuiwing operateur, wat nie dikwels vreeslik nuttig, maar dit blyk dat hulle kan wees. In werklikheid, as jy iets soos 'n boolse skikking te verteenwoordig net waar of vals voor te stel, veronderstel jy wil om tred te hou van of 'n kamer vol van 300 studente teenwoordig is, jy kan 'n verskeidenheid van grootte 300 van die tipe Bool verklaar sodat jy 300 bools, en jy kan elkeen na waar as iemand hier is en valse anders. Hoekom is dit verteenwoordiging in daardie data struktuur ondoeltreffend? Wat is sleg oor die ontwerp van daardie data struktuur, 'n verskeidenheid van 300 bools? Wat is 'n Bool, in werklikheid, onder die enjinkap? Hierdie, ook, is iets wat dalk nie vertroud wees. Dit blyk uit daar is geen Bool. Onthou ons soort van geskep dat met die cs50.h lêer, wat self sluit standaard Bool. C is 'n soort van dom, maar, wanneer dit kom by Bool. Dit maak gebruik van 8 stukkies elke Bool te stel, wat is heeltemal verkwistende want natuurlik, hoeveel stukkies wat jy nodig het 'n Bool te stel? Net 1. So dit blyk dat as jy het nou die vermoë om met bis-operateurs individuele stukkies selfs in 'n kar, selfs in 'n enkele greep te manipuleer, dit blyk dat jy kan die geheue wat nodig is om iets dom te stel verminder soos dat die bywoning styl data struktuur deur 'n faktor van 8. In plaas van die gebruik van agt bisse waar of vals voor te stel, kan jy letterlik gebruik maak van een deur gebruik te maak van 'n enkele greep vir elke agt studente in die klas en Reguliere van 0 tot 1 individuele stukkies deur die gebruik van hierdie soort van lae-vlak truuks. Wat werklik 'n einde aan die energie. Is daar enige vrae oor bis bedrywighede? Ja. >> [Student] Is daar 'n eksklusiewe of operateur? Ja. Daar is 'n eksklusiewe of operateur wat lyk soos hierdie, ^, die wortel simbool, wat beteken dat slegs die eerste ding of die tweede ding kan 'n 1 vir die uitset na 'n 1. Daar is ook 'n nie ~, wat sal toelaat dat jy 'n 0 na 'n 1 of andersom sowel omkeer. En daar is ook 'n regter shift-operateur, >>, wat is die teenoorgestelde van die een wat ons gesien het. Alles reg. Kom ons neem dinge nou na 'n hoër vlak. Ons het begin deur te praat oor die teks en dan dit te comprimeren en wat die teks met minder aantal bisse; ons gesels 'n bietjie oor hoe ons kan nou begin manipuleer dinge op 'n bis-vlak. Kom ons kyk nou zoom back-up 10.000 voete op verteenwoordiging van meer komplekse dinge soos grafika. Hier het ons het 'n vlag van Duitsland, hier het ons een van Frankryk. Dit kan voorgestel word in lêer formate wat jy kan weet - GIFs, byvoorbeeld. As jy nog ooit gesien het 'n beeld op die web wat eindig in. Gif, dit is 'n Graphics Interchange Format. Hierdie twee vlae hier soort van hulself leen tot die kompressie vir wat dalk voor die hand liggende rede? >> [Onhoorbaar student reaksie] Daar is 'n baie van die herhaling, reg? Ten einde Duitsland se vlag te stuur, dink aan dit as 'n beeld op die skerm terug in jou Scratch dae. Jy kan onthou dat daar is individuele pixels of kolletjies wat 'n beeld. Daar is 'n hele ry swart kolletjies en nog 'n hele ry van swart kolletjies. Daar is 'n klomp van die rye swart kolle wat ons kan sien of ons werklik vergrote in, graag wanneer ons ingezoomd op Rob se gesig in Photoshop. So gou as ons het dieper en dieper en dieper in die beeld, jy begin sien die pixelation, al die blokkies wat sy oog in daardie geval saamgestel. Dieselfde deal hier. As ons vergrote in nogal 'n bietjie, sou jy sien individuele kolle. Wel, dit is soort van 'n vermorsing van stukkies. As 1/3 van die vlag is swart en 1/3 van die vlag is geel en so meer, Daarom kan ons nie op een of ander manier compress hierdie vlag? En selfs die Franse vlag kan saamgepers word, selfs al is die patroon is 'n bietjie anders. Dit blyk uit die GIF-lêer formaat is 'n lossless kompressie-formaat, wat beteken dat jy kan 'n beeld soos die Duitse vlag hier, jy kan 'n klomp van sy stukkies weggooi sonder om afbreuk te kwaliteit. Dit is in teenstelling met iets soos JPEG, waarmee die meeste van ons is waarskynlik meer bekend. Facebook foto's en Flickr foto's en dies meer is byna altyd gestoor as JPEG wanneer hulle opgelaai, maar JPEG is 'n lossy lossy - waardeur jy weggooi stukkies maar jy moet ook weggooi gehalte. En so, as jy compress foto's met Photoshop of oplaai na Facebook of neem hulle op 'n baie crappy telefoon, jy weet dat die prentjie begin om te kry baie vuil en pixelated, en dit is omdat dit is wat saamgepers deur die rekenaar of selfoon deur letterlik gooi inligting weg. Maar GIF is ongelooflik dat dit minder stukkies kan gebruik as wat dit kan by verstek sonder om enige inligting te verloor. En dit nie in wese soos volg. Eerder as om die winkel in 'n lêer soos 'n BMP sou 'n RGB triple vir swart, swart, swart, swart, swart, swart, swart, swart, swart, swart, swart, swart en so meer, eerder die GIF-formaat gaan om te sê, "Swart," en dan, "Herhaal hierdie 100 keer," of iets soos dit. "Swart, herhaal hierdie 100 keer, swart, herhaal hierdie 100 keer ..." "Geel, hierdie 100 keer herhaal." En so is dit onthou, in wese, die linker pixel en kodeer dan die een of ander manier die idee van die weer en weer herhaal dat pixel. So GIFs kan compress hulle dan sonder om enige inligting te verloor. Maar as jy het om te raai, as dit die algoritme wat gifs gebruik, wat van hierdie vlae, selfs al is hulle lyk identies in grootte, gaan om te wees kleiner as op die skyf gestoor as 'n GIF? >> [Student] Duitsland. Duitsland gaan om kleiner te wees? Hoekom? [Student] Omdat jy dit herhaal baie, baie keer horisontaal en dan moet jy ander tyd herhaal. >> Presies. Omdat die mense wat GIF uitgevind net soort van arbitrêr besluit dat die herhaling horisontaal en nie lateraal aged. Daar is 'n baie meer herhaling lateraal hier in die Duitse vlag as in die Franse vlag. So as ons eintlik 'n gids op my harde skyf, wat het hierdie GIFs, jy kan eintlik sien dat die Duitse vlag hier is 2 kilogrepe en die Franse is 4 kilogrepe. Dit gebeur as 'n toevalligheid dat 'n mens twee keer die ander, maar dit is in werklikheid die geval dat die Franse vlag is veel groter. Selfs al is ons hier praat oor die graphics, kan dieselfde idees van toepassing op nie dinge soos vlae maar beelde wat 'n bietjie meer kompleks. As jy 'n foto van 'n appel, voorwaar, daar is 'n baie van duplisering, sodat ons kan op een of ander manier te onthou dat die standaard agtergrond is blou en nie, soos die regterkantste foto aandui, die kleur van elke enkele pixel in hierdie prentjie om te onthou. Sodat ons kan gooi stukkies weg daar sonder om inligting te verloor. Die appel lyk nog net dieselfde. Hier in hierdie voorbeeld, kan jy sien wat gebeur in 'n film. Hierdie ou-skool film rolle waardeur in die boonste prent daar verteenwoordig jy het 'n RV ry verby 'n huis en 'n boom. En as dié van verby ry van links na regs, wat natuurlik nie om te verander? Die huis is nie iewers heen gaan, en die boom is nie iewers heen gaan. Die enigste ding wat beweeg is die van in hierdie geval. So as agtergrond Onveranderd suggereer, wat jy kan doen in films is insgelyks net weggooi inligting wat nie verander tussen rame. Dit is algemeen bekend as interframe kompressie waardeur as dit raam lyk byna identies is aan hierdie een, laat ons nie die moeite stoor op skyf van enige van die identiese inligting op hierdie intermediêre rame, laat se enigste sleutel rame gebruik een keer in 'n rukkie wat eintlik dat inligting kere net so 'n bietjie gesonde verstand gaan stoor. In teenstelling, 'n ander benadering te comprimeren video is in hierdie tweede en laer voorbeeld hier, waar eerder as winkel 30 rame, hoekom doen jy nie net 15 rame per sekonde stoor plaas? Eerder as om die fliek soort van vloeiende pragtig, perfek, is dit dalk lyk dit hakkel 'n bietjie, 'n bietjie ou skool, maar die netto effek sal veel minder stukkies as wat dit andersins nodig wees om te gebruik. So waar dit laat ons dan? Dit was 'n bietjie van 'n eenkant waar anders kan jy gaan met kompressie. Vir meer inligting op daardie, neem 'n klas soos CS175 hier. Hier is nog 'n voorbeeld in die video. As die bye is die enigste ding wat beweeg, jy kan regtig weggooi inligting in daardie middelste rame omdat die blom en die lug en blare is nie besig om te verander. Maar laat ons nou een laaste ding wat oorweeg. In die volgende 5 minute het ons verlaat C agter vir ewig in die lesing? Ja. Nie in die psets, though. Laaste storie oor C en dan kry ons 'n baie sexy stuff met HTML en Web-en woo-hoo. Alles reg. Hier gaan ons. Dit is die motivering. Dit blyk uit al hierdie tyd wanneer ons programme loop ons kletteren skryf. En klang, ons het gesê sedert die eerste week pretty much, bronkode en dit omskakel in object code. Dit neem C en dit omskakel in 0'e en 1s. Ek het soort van lieg vir jou vir 'n paar weke, want dit is nie heeltemal so eenvoudig soos dit. Daar is 'n baie meer onder die enjinkap aangaan wanneer jy 'n program soos kletteren. In feite, kan werklik die proses van die opstel van 'n program opgesom word, as jy kan onthou van Rob se video op samestellers, in hierdie 4 stappe: pre-verwerking, samestelling self, vervaardiging, en koppel. Maar ons in die klas en die meeste mense in die wêreld tipies n opsomming van al hierdie stappe as net "die opstel van." Maar as ons begin met die bron kode soos hierdie, onthou dit is miskien die eenvoudigste C program ons het tot dusver geskryf is, onthou dat wanneer saamgestel dit eindig op soek soos hierdie. Maar daar is eintlik 'n intermediêre stap, en daardie stappe is soos volg. Eerstens is daar is hierdie ding op die top van hierdie en die meeste van ons programme, # Include Wat beteken # sluit vir ons doen? Dit pretty much kopieer en plak die inhoud van stdio.h in my lêer sodat hoekom? Waarom gee ek nie oor die inhoud van stdio.h? Wat is daar van belang? Printf se verklaring, sy prototipe, sodat die vertaler dan weet wat ek bedoel wanneer ek noem hierdie funksie printf. So stap 1 in die opstel van pre-verwerking, waardeur 'n program soos kletteren of 'n helper program wat kletteren kom met lees jou kode van bo na onder, links na regs, en 'n tyd wat dit 'n # simbool sien, gevolg deur 'n sleutelwoord soos sluit, dit voer dat die operasie, kopieer en plak in hierdie geval stdio.h in jou lêer. Dit is stap 1. Dan het jy 'n veel groter C-lêer as gevolg van die groot kopieer, plak werk wat nou net gebeur het. Stap 2 is besig om nou. Maar dit blyk uit die samestelling van bron-kode wat lyk soos hierdie en draai dit in iets wat lyk soos hierdie, wat vir diegene wat vertroud is genoem? >> [Student] Vergadering. >> Assembly language. Dit is eintlik iets as jy CS61 jy in duik in meer detail. Dit is net omtrent so naby as wat jy kan kry tot die skryf van 0'e en 1s jouself maar die skryf van dinge in so 'n manier wat nog ten minste 'n bietjie sin maak. Hierdie masjien instruksies, en as ons scroll af na die hooffunksie hier, agterkom dat daar is dit push onderrig, beweeg onderrig, aftrek onderrig, noem onderrig, en so meer. Wanneer jy hoor dat jou rekenaar Intel Inside, jy het 'n Intel CPU in jou Mac of PC, wat beteken dit? 'N CPU kom wat gebou is deur maatskappye soos Intel sekere instruksies te verstaan. Hulle het geen idee watter funksies soos swap is of die hoof is per se, maar hulle weet wat baie lae-vlak instruksies soos, trek, stoot, beweeg, te roep, en so meer. So wanneer jy stel C-kode in saamsteltaal, jou baie gebruikers vriendelik-looking kode omgeskakel word in iets wat lyk soos hierdie, wat beweeg letterlik bytes of 4 bytes om in so 'n klein eenhede in en uit van die SVE. Maar uiteindelik, wanneer kletteren is gereed om hierdie voorstelling van jou program te neem in 0'e en 1s, dan is die stap met die naam byeenkoms gebeur, en dit gebeur weer almal in die knip van 'n oog toe hardloop kletteren. Ons hier begin, is dit uitgange 'n lêer soos hierdie, en dit dan moet dit omskakel na hierdie 0'e en 1s. En as jy wil om terug te gaan op 'n sekere punt en eintlik dit in aksie te sien, as ek kom in hello1.c-dit is een van die eerste programme wat ons kyk na - normaalweg sou ons stel dit met kletteren hello1.c en dit sou gee ons a.out. As jy daarenteen gee dit plaas-S vlag, wat kry jy hello1.s en jy sal sien die saamsteltaal. Ek doen dit vir 'n baie kort program, maar as jy terug te gaan vir Scramble of verhaal of enige program wat jy geskryf het en net uit nuuskierigheid wil om te sien wat dit werklik lyk, wat is eintlik gevoed word in die SVE, jy kan dat-S vlag gebruik met kletteren. Maar dan laastens, daar is nog steeds een Gotcha. Hier is die 0'e en 1s dat my implementering van Hello, world. Maar ek iemand anders se funksie in my program gebruik. Dus, selfs al is die proses was ek hello.c, kry dit saamgestel in vergadering-kode, en dan is dit kry vergader in 0'e en 1s, die enigste 0'e en 1s wat op hierdie punt in die tyd outputted is die een wat die gevolg is van my kode. Maar die persoon wat geskryf het printf, het hulle hul kode 20 jaar gelede saamgestel en dit is nou geïnstalleer iewers op die toestel, sodat ons die een of ander manier het sy of haar 0'e en 1s om saam te smelt met my 0'e en 1s, en dit bring ons by die 4de en finale stap van die opstel, bekend as koppel. So op die linkerkant ons het presies dieselfde beeld as voorheen: word hello.c vergadering kode 0e en 1e. Maar onthou dat ek gebruik die standaard I / O biblioteek in my kode, en dit beteken dat daar iewers op die rekenaar is 'n lêer genaamd stdio.c of ten minste die saamgestelde weergawe daarvan omdat iemand n paar jaar gelede saamgestel stdio.c in gemeente-kode en dan 'n hele klomp van 0'e en 1s. Dit is wat bekend staan ​​as 'n statiese of 'n dinamiese biblioteek nie. Dit is 'n paar lêer sit iewers in die toestel. Maar laastens, ek het my 0'e en 1s te neem en daardie persoon se 0'e en 1s en op een of ander manier verbind hulle saam, letterlik kombineer dié 0e en 1e in 'n enkele lêer genaamd a.out of hello1 of wat ookal ek het my program sodat die eind resultaat van die 1s en 0s wat my program saamstel. So het al die tyd hierdie semester wanneer jy kletteren al met behulp van en selfs meer onlangs loop ten einde kletteren te voer, al hierdie stappe het gebeur soort oombliklik maar baie doelbewus. En so, as jy nog steeds in rekenaarwetenskap, naamlik CS61, dit is die laag wat jy sal voortgaan om te skil af is daar praat oor die doeltreffendheid, veiligheid implikasies, en die wil van hierdie laer vlak besonderhede. Maar met wat ons oor C agterlaat. Kom ons gaan voort en neem ons 5-minute breek nou, en wanneer ons terug kom: die Internet. Alles reg. Ons is terug. Nou het ons begin om ons kyk nie net op HTML, want soos u sal sien, HTML self is eintlik redelik eenvoudig maar eintlik meer in die algemeen op die web programmering, netwerke meer in die algemeen, en hoe al hierdie tegnologie bymekaar kom ons in staat stel om baie meer gesofistikeerde programme te skep bo-op die Internet as tot dusver het ons in staat was om in hierdie swart en wit vensters. Inderdaad, selfs al is op hierdie punt in die semester sal ons relatief minder tyd spandeer op PHP, HTML, CSS, JavaScript, SQL en nog baie meer, die meeste studente doen einde finale projekte wat is web-gebaseerde want soos jy sien, die agtergrond wat jy nou in C is baie van toepassing op hierdie hoër vlak tale. En as jy begin dink oor jou finale projek, wat baie soos Problem Set 0, waar jy is aangemoedig die meeste enigiets van belang te doen om jou Scratch die finale projek is jou geleentheid om jou nuutgevonde kennis en vaardig te neem met C of PHP of JavaScript of die wil uit vir 'n spin en die skep van jou eie stukkie van die sagteware vir die wêreld te sien. En aan die saad wat jy met idees, weet dat jy hier kan die hoof, projects.cs50.net. Elke jaar het ons idees in te win van die fakulteit en personeel en studente groepe op die kampus net hulle idees in te dien vir die interessante dinge wat opgelos kan word deur gebruik te maak van rekenaars, die gebruik van webwerwe, die gebruik van sagteware. So as jy sukkel om te kom met 'n idee van jou eie, deur al beteken blaai deur die idees van hierdie jaar en verlede. Dit is heeltemal in orde om 'n projek aan te pak wat voorheen aangepak. Ons het gesien hoe baie apps vir die sien van die status van wasgoed op die kampus, baie apps om die eetsaal menu te opgevolg, baie apps vir die opgevolg deur die kursus katalogus en dies meer. En inderdaad, in 'n toekomstige lesing en in toekomstige seminare, ons sal jou bekendstel aan die publiek beskikbaar API's, beide kommersieel beskikbaar sowel as hier beskikbaar by CS50 op die kampus, sodat jy toegang tot inligting en kan dan interessante dinge doen met dit. Sodat meer in 'n paar dae op die finale projekte wanneer ons die vrylating van die spesifikasie, maar vir nou is, weet dat jy solo kan werk of met een of twee vriende op die meeste 'n projek van belang is vir jou. Die Internet. Jy gaan voort en trek uit jou laptop, gaan jy na facebook.com vir die eerste keer, nie aangemeld is onlangs, en druk Enter. Wat gebeur presies? As jy op jou rekenaar druk Enter, 'n hele klomp van die stappe Begin soort mettertyd gebeur. So jy hier aan die linkerkant, web bediener soos Facebook is hier aan die regterkant, en op een of ander manier is jy met behulp van hierdie taal genoem HTTP, HyperText Transfer Protocol. HTTP is nie 'n programmeertaal. Dit is meer van 'n protokol. Dit is 'n stel van die konvensies wat web blaaiers en webservers gebruik wanneer intercommunicating. En wat dit beteken, is soos volg. Graag in die werklike wêreld, ons het hierdie konvensies waar as jy n mens vir die eerste keer ontmoet, as jy nie omgee nie humoring my hier, Ek kan kom aan jou, sê: "Hallo, my naam is Dawid." >> Hi, David. My naam is Sammy. "Hi, David. My naam is Sammy." So nou het ons net wat betrokke is in hierdie soort van dom menslike protokol waar ek die protokol het begin, het Sammy gereageer, ons hande geskud het, en die transaksie voltooi is. HTTP is baie soortgelyk in die gees. Wanneer jou webblaaier versoeke www.facebook.com, wat jou browser is regtig doen die uitbreiding van sy hand, om so te praat, op die bediener en dit stuur 'n boodskap. En dat die boodskap is gewoonlik iets kry - wat wil jy te kry? kry my die tuisblad, wat gewoonlik aangedui deur 'n enkele streep aan die einde van 'n URL. En net sodat jy weet watter taal ek praat, ek is die leser gaan om jou te vertel dat ek praat HTTP weergawe 1.1, En ook vir 'n goeie maatreël, ek gaan om jou te vertel dat die leër te ontmoet wat ek wil die home page van is facebook.com. Tipies, 'n webblaaier, unbeknownst aan julle, die mens, stuur hierdie boodskap oor die internet as jy net www.facebook.com tik, Tik in jou browser. En wat beteken Facebook reageer met? Dit reageer met 'n soortgelyke soek kriptiese besonderhede, maar ook veel meer. Laat my voort te gaan na Facebook se home page hier. Dit is die skerm wat die meeste van ons waarskynlik nooit sien as jy bly aangeteken in al van die tyd, maar dit is inderdaad hulle tuisblad. As ons dit doen in Chrome, agterkom dat jy kan trek hierdie klein konteks kieslyste. Met Chrome, hetsy op Mac OS, Windows, Linux, of iets dergeliks, As jy kliek of links kliek beheer, kan jy gewoonlik trek 'n spyskaart wat lyk soos hierdie, waar 'n paar opsies wag, waarvan een is View Page Source. Jy kan gewoonlik ook van hierdie dinge deur te gaan na die kieslys en skeer rond. Byvoorbeeld, hier onder View Ontwikkelaars is dieselfde ding. Ek gaan om voort te gaan en kyk na View Page Source. Wat jy sien, is die HTML-kode wat Mark het geskryf facebook.com te verteenwoordig. Dit is 'n volledige gemors hier, maar ons sal sien dat dit 'n bietjie meer sin maak voor lank. Maar daar is 'n paar patrone hier. Laat my scroll af na dinge soos hierdie. Dit is moeilik vir 'n mens om te lees, maar sien dat daar is hierdie patroon van reghoekige hakies met sleutelwoorde soos opsie, sleutelwoorde soos waarde, sommige aangehaal snare. Dit is waar, wanneer jy ingeteken het vir die heel eerste keer gespesifiseer wat jou geboorte jaar is. Dit drop-down menu van geboorte jaar word een of ander manier hier geïnkripteer in hierdie taal genoem HTML, HyperText Markup Language. Met ander woorde, wanneer jou blaaier 'n webblad versoek, dit praat hierdie Konvensie genoem HTTP. Maar wat beteken facebook.com aan daardie versoek reageer? Dit reageer met 'n paar van hierdie kriptiese boodskappe, soos ons sal sien in 'n oomblik. Maar die meeste van sy antwoord is in die vorm van HTML, HyperText Markup Language. Dit is die taal waarin 'n web bladsy is geskryf. En wat 'n webblaaier nie regtig dan, by ontvangs van iets wat lyk soos hierdie, lees dit van bo na onder, links na regs, en enige tyd dit sien een van hierdie reghoekige hakies gevolg deur 'n sleutelwoord soos opsie, dit toon dat die opmaak taal op die gepaste manier. In hierdie geval, sou dit vertoon 'n drop-down menu jare. Maar weer, dit is 'n volledige gemors om na te kyk. Dit is nie omdat Facebook ontwikkelaars manifesteer 0 vir 5 styl, byvoorbeeld. Dit is omdat die meeste van die kode wat hulle skryf is, in werklikheid, geskryf pragtig, goed gedraai, mooi ingekeep, en dies meer, maar natuurlik masjiene, rekenaars, blaaiers gee regtig nie 'n damn of jou kode is 'n goed-styl. En in die feit, dit is heeltemal verkwistende om die Tab-sleutel te druk al die tye en kommentaar te plaas regdeur jou kode en regtig beskrywende veranderlike name te kies want as die leser nie sorg nie, is al wat jy doen aan die einde van die dag mors grepe. So dit blyk uit wat die meeste webtuistes selfs al is die bron-kode vir facebook.com vir cs50.net en al hierdie ander webwerwe op die Internet word gewoonlik goed geskryf en goed gedraai en mooi ingekeep en dies meer, gewoonlik voor die aangesig van die webwerf is op die Internet, is die kode minified, waardeur die HTML en die CSS - iets anders sal ons gou sien - die JavaScript-kode wat ons sal gou sien saamgepers word, waardeur lang veranderlike name word X en Y en Z, en almal van daardie spasie wat maak alles lyk so leesbare is al weggegooi, want as jy dink oor dit op hierdie manier, Facebook kry 'n miljard bladsy treffers 'n dag - iets gek soos dit - so wat as 'n programmeerder te wees anale druk die space bar 'n ekstra tyd net om te streepje n reël van die kode ooit soveel meer? Wat is die implikasie as Facebook bewaar dat witspasie in al die grepe stuur hulle terug na die mense op die internet? Slaan die spasie balk gee wanneer jy 'n ekstra greep in jou lêer. En as 'n miljard mense, dan gaan die tuisblad daardie dag aflaai hoeveel meer inligting het jy oor die internet versend word? 'N giga byte vir geen goeie rede. Toegeken, vir 'n baie websites is dit nie so 'n skaal aanvaarde kwessie, maar vir Facebook, Google, vir 'n paar van die gewildste webwerwe daar is 'n groot aansporing finansieel te maak om jou kode te kyk soos 'n gemors sodat jy gebruik so min as moontlik bytes benewens dan dit te comprimeren met iets soos zip, 'n algoritme genaamd gzip, dat die leser nie outomaties vir jou. Maar dit is verskriklik. Ons sal nooit iets leer oor ander mense se websites en hoe om webbladsye te ontwerp as ons het om te kyk na dit soos hierdie. So gelukkig blaaiers soos Chrome en Internet Explorer en Firefox hierdie dae tipies kom met ingeboude ontwikkelaar gereedskap. In werklikheid, as ek neerdaal hier Element of indien te inspekteer, ek gaan na View, ontwikkelaar, en gaan na Developer Tools uitdruklik, hierdie venster aan die onderkant van my skerm verskyn nou. Dit is 'n bietjie intimiderend op die eerste, want daar is 'n baie onbekende tabs hier, maar as ek op Elements al die pad aan die onderkant links, Chrome is natuurlik redelik slim. Dit weet hoe om al hierdie kode te interpreteer. En so wat Chrome doen is dit skoon al van Facebook se HTML. Selfs al is daar nie spasie, daar is nie inkeping daar, nou sien dat ek kan begin om hierdie webblad aan al die meer hiërargies navigeer. Dit blyk dat elke webblad geskryf in 'n taal, die sogenaamde HTML5 moet begin met hierdie, hierdie DOCTYPE verklaring, om so te praat: Dit is soort van lig en grys daar, maar dit is die heel eerste lyn van die kode in die lêer, en wat vertel net die leser, "Hey, hier kom 'n paar HTML5 Hier kom 'n web bladsy." Die eerste oop bracket buite wat gebeur met hierdie ding, 'n oop bracket HTML tag, en dan as ek duik in dieper - hierdie pyle is heeltemal betekenisloos; hulle is net vir die aanbieding se onthalwe, hulle is nie eintlik in die lêer - let dat die binnekant van Facebook se HTML tag, enigiets wat begin met 'n oop bracket en dan het 'n woord is bekend as 'n tag. Dus, binne die HTML-tag is blykbaar 'n kop tag en 'n liggaam tag. Binnekant van die kop tag is nou 'n hele gemors by Facebook want hulle het 'n baie van metadata en ander dinge vir bemarking en advertensies. Maar as ons scroll down, down, down, down, laat ons sien waar dit is. Hier is dit. Hierdie een is ten minste 'n bietjie bekend is. Die titel van Facebook se tuisblad, as jy ooit kyk in die blad in jou titel bar, Welkom by Facebook - Log In Sign Up of Meer inligting. Dit is wat jy wil sien in Chrome se titel bar, en dit is hoe dit is verteenwoordig in die kode. As ons ignoreer alles anders in die kop, die meeste van die ingewande van 'n web bladsy is in die liggaam, en dit blyk dat Facebook se kode is gaan om te kyk meer komplekse as die meeste dinge sal ons aanvanklik skryf net omdat dit oor die jare opgebou is, maar daar is 'n hele klomp van die script tags, JavaScript kode, wat maak die webwerf baie interaktiewe: status updates onmiddellik die gebruik van tale soos JavaScript sien. Daar is iets genoem 'n div, wat is 'n afdeling van 'n bladsy. Maar voordat ons by daardie detail, laat ons probeer om uit te zoomen en kyk na 'n eenvoudiger weergawe van Facebook 1,0, om so te praat. Hier is die hello, wêreld van die web bladsye. Dit het dat die DOCTYPE verklaring by die heel boonste wat is 'n bietjie verskillend van alles anders. Niks anders wat ons skryf in 'n web bladsy gaan om te begin met vir vet. Weereens, die storie is dieselfde: hello, komma, begin met die maak van hierdie moedige, toenmalige wêreld kry in vetdruk, en dit beteken stop druk dit in vetdruk. Laat my voort te gaan en red my lêer, gaan terug na Chrome, sal ek zoom in net sodat ons dit beter kan sien, en herlaai, en jy sal sien dat die wêreld nou is in vetdruk. Die Web is al oor die hiperskakels, so laat ons gaan voort en doen dit: my gunsteling webwerf is, laat ons sê, youtube.com. Red, herlaai. Okay. Daar is 'n paar probleme nou behalwe die afzichtelijk van die webwerf. 1, Ek is redelik seker ek druk Enter hier. En ek het. Ek het nie net druk Enter, het ek ook ingekeep, praktiserende wat ons preek oor styl, maar my is reg langs aan die wêreld. So hoekom is dit? Browsers net doen wat jy vir hulle sê om te doen. Ek het nie vertel die leser, "Break lyne hier Voeg paragraaf hier breek." Sodat die leser, dit maak nie saak as ek Opbrengs 30 keer getref het, dit is nog steeds gaan my reg langs aan die wêreld sit. Wat ek regtig het om hier te doen, is iets soos sê
, voeg 'n lyn breek. En eintlik, 'n lyn breek is 'n soort van 'n vreemde ding want jy kan nie regtig begin beweeg na 'n ander lyn, dan doen iets, en dan ophou beweeg na 'n nuwe reël. Dit is soort van 'n atoom operasie. Jy doen nie, of jy doen nie. Jy druk Enter of jy doen nie. So br is 'n bietjie van 'n ander tag, en so het ek nodig het om te sorteer van beide oop en dit sluit almal gelyktydig. Die sintaksis vir wat is dit. Tegnies, kan jy iets soos hierdie te doen in sommige weergawes van HTML, maar dit is net dom, want daar is geen rede om te begin en stop om iets as jy nie kan plaas en doen dit alles in 'n keer. Besef dat HTML5 streng nie vereis dat hierdie streep, sodat jy sal sien handboeke en aanlyn hulpbronne wat dit nie het nie, maar vir 'n goeie maatreël laat oefen die simmetrie wat ons het tot dusver gesien. Dit beteken dat die merker is beide geopen en gesluit. So nou, laat my my lêer red, gaan terug hier. Okay, so dit is beter begin lyk, behalwe die web wat ek ken is 'n soort van klikbare, en nog youtube hier lyk nie te lei tot enigiets. Dit is omdat, selfs al is dit lyk soos 'n skakel, die leser nie weet dat per se, so ek moet die leser om te sê dat dit is 'n skakel. Die manier om dit te doen, is om 'n anker te gebruik tag: en laat my skuif dit na 'n nuwe lyn net so dit is 'n bietjie meer leesbare, en ek sal die font grootte krimp. Ek gedoen nie? Nee, daar is gaan hierdie digotomie wees. Hierdie tag, die anker tag, inderdaad 'n kenmerk, wat verander sy gedrag, en die waarde van die kenmerk is blykbaar YouTube se URL. Maar let op die digotomie is dat net omdat dit is die URL wat jy gaan, dit beteken nie dat wat aan die woord wat jy onderstreep en maak 'n skakel te wees. Inteendeel, kan dit iets soos hierdie. So ek het om te sê ophou om hierdie woord 'n hyperlink deur gebruik te maak van die beslote anker tag. Sien ek is nie om dit te doen. 1, sal dit net 'n vermorsing van almal se tyd en dit is nie nodig nie. 'N merker te sluit, jy noem net die naam van die tag weer. Jy noem nie enige van die eienskappe. So laat red, gaan terug. Okay, voila, nou dit is blou en hyperlink. As ek dit kliek, Ek het eintlik gaan na YouTube. Dus, selfs al is my web bladsy is nie op die internet, dit is ten minste HTML, en as ons laat die Internet inhaal, ons sou eintlik eindig hier by youtube.com. En ek kan terug gaan en hier is my web bladsy. Maar let. As jy al ooit spam of 'n phishing-aanval gekry het, nou het jy die vermoë om ná net vyf minute om dieselfde te doen. Ons kan hier gaan en iets te doen soos www.badguy.com of wat ookal die oppervlakkig webwerf is, en dan kan jy sê jou PayPal-rekening te verifieer. [Lag] En nou dit gaan om te gaan na badguy.com, wat ek nie van plan om op te klik want ek het geen idee waar dit lei. [Lag] Maar nou het ons die vermoë om werklik daar beland. So ons is eintlik maar net die begin van die oppervlak te krap. Ons is nie die programmering per se, ons skryf opmaak taal. Maar sodra ons om uit ons woordeskat in HTML, ons sal stel PHP, 'n werklike programmeertaal wat ons sal toelaat HTML outomaties genereer, genereer CSS outomaties, sodat ons kan begin op Woensdag te implementeer, sê, ons eie search engine en nog baie meer. Maar meer oor wat in 'n paar dae. Ons sien julle dan. [CS50.TV]