[Powered by Google Translate] [Week 7] [David J. Malan - Harvard University] [Dit is CS50. - CS50.TV] Oke. Welkom terug. Dit is CS50, en dit is het begin van week 7. Een paar kleine aankondigingen: Pset5 is nu aan de gang, of binnenkort zal, en laat ik zeggen, eerlijk gezegd, is dit de neiging om als een van de meer uitdagende van het probleem van de cursus sets, dus laat me noemen dit nu zodat deze week meer dan ooit je niet wachten tot, laten we zeggen, woensdagavond of donderdagavond te duiken inch Dit is zeker een interessante PSET. We denken dat het is leuk. Als je daadwerkelijk krijgt het volledig correct is en kan dan tegen de zogenaamde Big Board, heb je een kans om verstand overeenkomen met een aantal van het personeel van de cursus en een aantal van je klasgenoten. Wat The Big Board is is als je eenmaal je spellingcontrole werken hebben, je zult in staat zijn om te cs50.net te gaan na het uitvoeren van een opdracht, zuiver kiezen, en dan de tijd en de hoeveelheid RAM en die u hebt gebruikt in uw toepassing worden hier tentoongesteld op de homepage van de cursus pagina. U zult merken dat een hele hoop van deze mensen hier zijn opgenomen als personeelskosten omdat in het weekend, het personeel dacht dat het leuk zou zijn om te proberen elkaar te overtreffen. Dus beseffen dat het doel hier niet is te overtreffen het personeel. Zelfs ik ben alleen hier op nummer 13. Puur opt-in, maar het is een kans om te zien hoe weinig RAM-geheugen en hoe weinig CPU seconden kunt u gebruik maken van vis-a-vis een aantal van je klasgenoten. En ik geef toe dat Kevin Michael Schmid, momenteel nummer 1 positie als een van de TFS, Dit is een implementatie die wij noemen niet mogelijk gezien het feit dat hij bijna 0 RAM-geheugen en bijna 0 seconden met voor het laden. Dus we zullen zorgen voor Kevin offline. [Gelach] Er zijn bepaalde vaardigheden die Kevin zet hier op de proef. Een van de dingen die we dachten dat we zouden doen, is nu ook CS50x is een week aan de gang, en jullie zijn net zo goed een onderdeel van dit experiment als die studenten zijn. We hebben hen gevraagd als onderdeel van hun pset0, die eveneens was om een ​​Scratch project in te dienen voor hen van belang - een spel, een interactief kunstwerk, een animatie en dergelijke - een 1 - tot 2-minuten durende video, als ze willen, zeggen hallo tegen de wereld en wie ze in werkelijkheid zijn. Ik dacht dat ik met u delen een paar van de video's die zijn tot nu toe ingediende want voor ons, op het personeel in ieder geval, het is echt spannend geweest en inspirerend om deze mensen te zien uit de hele wereld - landen over de hele wereld - afstemmen, van alle dingen, naar een informatica cursus over het internet, of het nu is omdat ze willen hun eigen studie voort te zetten, ze willen hun carrière te nemen in een nieuwe richting, ze willen vullen hiaten in hun eigen kennis, zodat een aantal van dezelfde redenen dat jullie misschien hier zijn geweest. Dus ik geef je een dergelijke student hier. Je kon het volume te verhogen gewoon een beetje. Hier is een van 1-minuut onze student inzendingen. Hallo, wereld. Ik ben een student van industrieel ingenieur hier in Malaga, Spanje. Ik ben enthousiast over deze online cursus, omdat ik hou van de informatica, echt waar, en ik echt waarderen dat ik om het te verkennen. En het feit dat ik hetzelfde kan jullie allemaal doen leren maar in plaats van in Harvard Ik ben in Malaga, hoe geweldig is dat? Nou, ik ben Fernando, en dit is CS50. Ik zie jullie. [Gelach] Een andere clip die we vooral willen, je zult zien dat deze gentleman's Engels niet zo sterk is. Het lijkt erop dat hij het had machine vertaalde, zodat de vertalingen zelf zijn een beetje onvolmaakt, maar dit was een van onze favorieten tot nu toe ook. [♪ ♪] Hallo, wereld. [Spreken in het Japans] [Ik moet begroeten in het Japans, want mijn Engels is zeer onbetrouwbaar.] [Ik heb de boodschap aan u van de stad Gifu, Japan.] [I kan een student voor de eerste keer in 20 jaar, zoals te zien.] [Ik ben erg dankbaar voor de universiteit van Harvard, die gaf me deze kans en EDX.] [Golf is een gitaar en mijn favoriete ding draait.] [Gelach] [♪ ♪] [Waarom denk je dat ik probeerde een cs50x bij te wonen.] [Harvard University, het is mijn verlangen.] [Vooral als ik ver aanwezigheid in Japan gewoond.] [Ik wilde proberen onmiddellijk bewust van het bestaan ​​van dergelijke EDX wanneer.] [Denk je niet dat, zodat je niet in verband met de leeftijd van het leren I.] [CS50 is mijn verlangen. Mijn naam is Kazu, en dit is CS50.] [♪ ♪] [applaus en gejuich] Een andere favoriet van ons was dit middel hier van iemand. [♪ ♪] [Malan] Google als je niet bekend bent met deze meme. En dan tot slot, een paar anderen die werd gepost dat misschien de schattige award te winnen. [Studenten] Aww! >> [Malan] We zullen moeten luisteren. Dit is kort, zo nauw luisteren. [Vrouwelijke spreker] Wat is je naam? >> Louie. [Vrouwelijke spreker] Wat is dit? >> [Giechelt] CS50. [Gelach] [Malan] Hij heeft twee takes, dat wel. Daar gaan we, de laatste. Mijn naam is Louie, en dit is CS50. [Gelach] Dit is dan CS50x. Hartelijk dank aan al diegenen onder u, terwijl na langs thuis die zijn tot nu toe deel te nemen. Vandaag hebben we sluiten onze bespreking van data structuren, ten minste enkele van de meest fundamentele en dan gaan we verder met onze discussie over HTML en web programmeren. Inderdaad, we hebben doorgebracht de afgelopen paar zeven weken te kijken naar de fundamenten van de programmering - algoritmen, datastructuren en dergelijke - en C, zoals u wellicht tot nu toe hebben ervaren, is niet noodzakelijkerwijs de meest toegankelijke van de talen waarmee sommige van deze ideeën te implementeren. En zo begint deze week en volgende week en dan de volgende, zullen we uiteindelijk in staat om de overgang te zijn van C, die over het algemeen bekend staat als een vrij low-level taal, om dingen hoger niveau, waaronder PHP, JavaScript, en dergelijke, die we zullen zien een beroep doen op dezelfde lessen die we hebben geleerd van de afgelopen paar weken, maar je zult zien dat te verklaren dingen zoals arrays en hash tabellen en zoeken en sorteren worden zo veel makkelijker omdat de talen zelf beginnen we met behulp van zal worden krachtiger. Maar eerst, een toepassing van bomen. Het is zeer vaak deze dagen nodig hebben om informatie te comprimeren. In welke context zou je willen een soort van digitale informatie te comprimeren? Ja. >> [Student] Wanneer u het te verzenden via het web. Ja, als je iets wilt sturen via het web. Als u een groot bestand te downloaden, is het ideaal als iemand aan de andere kant heeft gecomprimeerd dat bestand met behulp van een zip-formaat of iets dergelijks zodat u verzendt minder bits dan anders worden overgedragen. Dus hoe ga je comprimeren informatie? Het komt allemaal neer op met minder bits dan vereist is volgens standaard. Maar dit is een soort van een merkwaardig ding, want denk terug aan week 0 en 1 toen we spraken over ASCII-en binaire en we hadden het over ASCII in het bijzonder als het gebruik van 8 bits om letters van het alfabet vertegenwoordigen zodat de letter A wordt vertegenwoordigd door 65 kleine letter a is het nummer 97, en hoe u vertegenwoordigt de 65 of 97, je bent 7 of 8 bits gebruikt. Maar de vangst is dat er een aantal letters in het Engels alfabet die niet zo populair als andere. Z is niet zo populair, Q is niet zo populair, maar A en E zijn super populair. En toch voor al deze brieven, standaard de wereld maakt gebruik van hetzelfde aantal bits, slechts 8. Dus zou het niet geweest zijn slimmer als in plaats van het gebruik van 8 bits voor elke letter, zelfs de meest zelden gebruikt als Q en Z, wat als we minder bits gebruikt voor A en E en S en de meest populaire letters en meer bits gebruikt voor de minder populaire letters, het idee is laten we optimaliseren voor de gemeenschappelijke zaak, dat is een thema in de informatica van het proberen te optimaliseren wat er gaat gebeuren de meest en breng een beetje meer tijd, een beetje meer ruimte op de dingen die, ja, er zou kunnen gebeuren maar niet per se zo vaak. Dus laten we eens een voorbeeld. Stel dat we willen informatie te coderen redelijk efficiënt. Je zou zijn opgegroeid een beetje iets over Morse code, en de kans is dat je niet de eigenlijke code te kennen, maar je zou herinneren dat het in ieder geval deze reeks van punten en strepen. Dit is een vrij efficiënte codering, en merk op dat de meest populaire brief - bijvoorbeeld, E - maakt gebruik van de kortste van de pieptonen. Morse code is alles over piep-piep-piep-piep-piep-piep en houden tonen zowel korte tijd of lange tijd. E, zoals aangegeven door de stip, is een super korte pieptoon, alleen piep, en dat zou vertegenwoordigen E. Daarentegen zou T een langere piep, piep, zoals [verlengt geluid], en dat zou vertegenwoordigen T. Maar dat is nog steeds vrij kort omdat, in tegenstelling, als je kijkt naar Z, tot Z drukken zou je piep, piep [meer geluid], piep, piep [kortere geluid] te gaan. Dus het is meer omdat het minder vaak voor. Maar de gotcha hier is dat Morse code is een beetje gebrekkig in dat het niet meteen decodeerbaar. Bijvoorbeeld, stel dat je hoort op sommige uiteinde van de draad piep [korte], piep [lang]. Welke boodschap heb ik net ontvangen? Een punt en een streepje. Wat betekent dat voor? [Student] A. >> [Malan] Misschien. Het kan ook E gevolgd door T. Met andere woorden, Morse code, maar het maakt gebruik van dit principe optimale hoek zaak Het leent zich niet tot onmiddellijke decodability. Dat wil zeggen, de mens die hoort of het ontvangen van deze punten en strepen moet een of andere manier erachter te komen waar de pauzes zijn tussen letters, want als je niet weet waar die pauzes zijn, kun je verwarren A voor ET of vice versa. Dus wat zou je doen? In Morse code kon je gewoon pauze tussen elk van de letters. Maar pauzeren is een soort van strijd met het hele punt van versnellen dingen. Dus wat als we in plaats daarvan kwam met een code waar er was niet deze slechte situatie waarbij E een prefix, bijvoorbeeld van A - met andere woorden, als we ervoor zorgen dat de patronen nog kort zijn voor de populaire letters lang voor de minder populaire letters, maar er is geen verwarring mogelijk is? Een man met de naam van de Huffman jaar geleden uitgevonden deze actie onder de naam Huffman-codering dat maakt gebruik eigenlijk een van de gegevensstructuren die we hebben doorgebracht een beetje tijd aan het praten over de afgelopen week, die van bomen, binaire bomen met name - een binaire boom betekent dat het niet meer dan 2 kinderen. Het heeft misschien een linker kind, misschien een goede kind terug, en dat is het. Dus stel alleen maar omwille van de discussie dat iemand wil sturen een bericht dat ziet er zo uit. Het is complete onzin, maar het is samengesteld uit As, B, C's, D's, en Es. En als je echt tellen alle van de As, B, C's, D's, en Es en vervolgens delen door het totale aantal letters, deze kleine grafiek hier zegt dat 45% van de brieven Es zijn, 20% As, 10% B, enzovoort. Met andere woorden, aan dat de string, daar is slechts enkele bericht dat u wilt verzenden. Het gebeurt te zijn onzin zodat we kunnen gebruiken als een paar letters mogelijk, maar het is inderdaad zo dat E blijft de meest populaire, en B en C het minst populair, althans van deze 5 letters van het alfabet. Dus hoe kunnen we gaan over het bedenken van een codering, een binaire codering, een patroon van 0 en 1 voor elk van deze letters zodanig dat E een kort model en misschien B en C zijn iets langer patronen nogmaals, het idee is dat we willen gebruiken minder bits meeste van de tijd en meer bits slechts af en toe. Volgens Huffman codering, kunt u een bos van bomen. Er is een soort van een verhaallijn hier die inhoudt dat bomen en ook het proces van het bouwen van ze op. Laten we beginnen. Ik stel voor dat je begint met dit bos, om zo te zeggen van 5 bomen, die elk een behoorlijk stom boom. De boom bestaat uit slechts een knooppunt, zoals hier weergegeven door een cirkel. Dus elk van deze dingen zou een C struct zijn en in de C struct kan een vlotter die de frequentie telling en dan misschien een char die de brief. Dus denk van deze knooppunten als zomaar een C struct, maar voor nu, hoger niveau. Dit is een bos van 5 bomen, elk van die alleen een enkel knooppunt. Wat Huffman voorgestelde is dat we beginnen met die bomen te combineren dat de kleinste frequentie telt hebben in iets grotere bomen door ze te verbinden met een nieuwe root node. Dus onder de letters hier, merken dat voor het gemak heb ik ze gesorteerd van links naar rechts, maar dat is niet strikt noodzakelijk, en merk op dat de kleinste knooppunten momenteel 10% en 10%. Dus Huffman Wij stellen u voor de 2 kleinste knooppunten samen te voegen tot een nieuwe boom door de invoering van een nieuwe bovenliggende node en geef die ouder een linker kind en een rechter kind waarbij B willekeurig de linker en C willekeurig rechts. En dan Huffman verder voorgesteld dat laten we maar denken nu aan de linker kind in een van deze bomen altijd zo worden voorgesteld door 0 en het rechter kind altijd zo worden weergegeven door het getal 1. Het maakt niet uit of je spiegelen ze zo lang als je consequent bent. Dus nu hebben we vier bomen in dit bos. En ik zeg vier, omdat nu de boom aan de linker - en het is niet zozeer een boom in de zin dat het op deze manier groeit, het is meer als een stamboom waar nu de 0,2 is een soort van de ouder van de twee kinderen - merken dat in die ouder we 0,2 getekend. We hebben toegevoegd de frequentie graven van de twee kinderen en de nieuwe knooppunt de totale som. Dus nu we dit proces herhalen. Zoek de twee kleinste knooppunten en ze vervolgens samen te voegen tot een nieuwe boom en herhaal het proces verder. Op dit moment hebben we een paar kandidaten, 20%, 15%, en nog eens 20%. In dit geval moeten we de winnaar te bepalen. We kunnen het willekeurig. We moeten gewoon consequent doen. In dit geval, zal ik willekeurig gaan met de een aan de linkerkant, en ik nu samen te voegen de 20% en de 15% om mij een nieuwe ouder genaamd 35%, waarvan de linkerborst kind is 0, wiens recht kind is 1, en nu hebben we slechts drie bomen in het bos. Je kunt misschien wel zien waar dit naartoe gaat. Als we herhalen dit nog een paar keer, we gaan maar een grotere boom hebben, waarvan alle randen zijn voorzien van 0s en 1s. Laten we het nog een keer doen. 35% is dat de boom wortel. 20% en 45%, dus we gaan naar de 35% en 20% samen te voegen. Nu hebben we deze boom hier. We voegen deze samen, we hebben 55%. Nu is er maar twee bomen in het bos. We doen dit nog een laatste keer, en hopelijk wiskundig alle frequenties optellen omdat ze moeten omdat we berekend ze uit de get-go optellen tot 100%. En nu hebben we een boom. Dit is dus een Huffman codering boom. Het soort duurde een tijdje om daar mondeling te komen, maar de realiteit is met een for-lus of met een recursieve functie, kunt u bouwen dit ding vrij snel. Dus nu hebben we een nieuw knooppunt, en al deze interne knopen zijn malloc'd, vermoedelijk, langs de weg. Nu de top van de boom we 100%, maar nu zien we een pad van deze nieuwe over-over-overgrootouders om alle groot-groot-groot-kleinkinderen helemaal onderaan aan alle bladeren. Wat we nu doen is voor te stellen dat om de letter E te vertegenwoordigen, zullen we gewoon gebruik maken van het getal 1. Waarom? Want als we deze boom naar beneden doorkruisen van de laatste wortel naar het blad bekend als E, volgen we slechts een kant, de rechterkant, en dat is het label natuurlijk bovenaan rechts 1. De implicatie hier voor Huffman was dat E's coderen in binaire gewoon gelijk aan 1. En dat is verdomd efficiënt. Ik kan niet echt veel kleiner dan dat. Daarentegen wordt een zal worden vertegenwoordigd, als je de logica, door welk patroon van bits in plaats daarvan? 01. Dus om naar A, we beginnen bij de wortel en gaan we links en dan gaan we rechts, wat betekent dat we volgden een 0 en dan een 1. Dus vertegenwoordigt de letter A met het patroon 0 en 1. En nu merken dat we al een eigenschap van onmiddellijke decodability hebben dat we niet in Morse-code. Hoewel beide van deze patronen zijn vrij kort - E is 1 bit, A is 2 bits - merken dat ze niet kunnen een of het ander worden verward, want als je een 1 het moet een E zijn, als je een 0, dan een 1 het duidelijk moet toch een A. zijn Ook, wat is d? 001. Wat C? 0001. En wat is B? 0000. En nogmaals, omdat alle brieven die we de zorg over zijn op de bladeren en geen van hen zijn soort tussenpersonen in het pad van wortel tot blad, er is geen gevaar voor elkaar gehaald 2 letters 'verschillende coderingen omdat al deze bitpatronen zijn deterministisch. 0000 zal altijd B. Er is geen knooppunt ergens tussen dat je misschien een letter voor de andere te verwarren. Dus wat is de implicatie hier? De meest populaire letter - in dit geval E - heeft gekregen van de kortste codering A heeft gekregen van de volgende kortste codering, en B en C, die we al kenden van de get-go waren zo vriendelijk van de minst populaire Bij 10% frequentie elk zijn ze weer de langste codering. En dus wat dit betekent nu is dat als je een bericht wilt dat is gecomprimeerd versturen via het internet of in een e-mail of iets dergelijks, in plaats van met behulp van standaard ASCII, kunt u een Huffman gecodeerde boodschap waarbij als je wilt de letter E te sturen, stuurt u gewoon een enkele bit. Als u wilt een A te sturen, stuurt u 2 bits, 01, in plaats van het verzenden van 8 bits gevolgd door een 8 bits gevolgd door een 8 bits enzovoort. Maar er is een gotcha hier. Het is niet voldoende om alleen te bouwen deze boom en dan het verzenden van Alice naar Bob te beginnen de kortere bitpatroon, een string van ASCII, want Alice heeft ook aan Bob op de hoogte van wat Als Bob gaat worden staat zijn om haar gecomprimeerde bericht te lezen? [Onverstaanbaar student reactie] >> Wat is dat? [Onverstaanbaar student reactie] >> Van wat de boom is. Of nog specifieker, wat die coderingen zijn, vooral omdat tijdens dit verhaal hebben we een beslissing te nemen op een punt. Vergeet niet dat we moesten willekeurig kiezen tussen de 2 verschillende 20% nodes? Dus het is niet zo dat Bob, de ontvanger, kan het gewoon reconstrueren de boom op zijn eigen want misschien is hij creëert de boom ooit zo iets anders dan Alice. Bovendien is Bob niet eens wat het oorspronkelijke bericht is omdat het enige wat Alice stuurt hem uiteraard de gecomprimeerde boodschap. Dus de vangst met compressie als dit is dat, ja, kan Alice besparen een hele hoop stukjes door het sturen 1 voor E en 01 voor A enzovoort, maar ze moet ook Bob informeren wat de mapping is tussen letters en bits omdat ze niet duidelijk rekenen op net ASCII meer als we niet met behulp van ASCII. Dus ze kan sturen hem de boom een ​​of andere manier - schrijf het op, bewaar het als binaire gegevens of iets dergelijks - of stuur hem een ​​beetje spiekbriefje, een Excel-bestand, dat de toewijzingen toont. Dus de effectiviteit van compressie neemt echt dat de berichten die u verzendt zijn vrij groot, in ieder geval middelgrote, want als je het verzenden van een super kort bericht, als je gewoon wilt om het bericht te verzenden BAD, die toevallig ook een woord dat we hier te spellen, B-A-D, ben je waarschijnlijk gaat minder bits te gebruiken, maar de vangst is als je ook nog Bob informeren wat de boom is of wat die coderingen zijn, zul je waarschijnlijk opwegen tegen alle van de besparingen van het hebben van gecomprimeerde dingen om mee te beginnen. Dus het kan eigenlijk zo zijn dat als je probeert te comprimeren zelfs met iets als zip of bestandsformaten u misschien wel vertrouwd met - vrij kleine bestanden, zelfs lege bestanden - soms zijn die bestanden kunnen groter en niet kleiner. Maar realistisch, dat gebeurt alleen voor kleine bestandsgrootte, dus het is niet van plan om een ​​gigabyte bestand zijn 2 gigabyte; we echt praten bytes of slechts een paar kilobytes. Sommige programma's zoals zip zijn slim genoeg om dat te realiseren, "Je gaat meer bits comprimeren deze door te brengen." "Laat me niet de moeite het te comprimeren voor u allen." Dus dit is gewoon een manier dan comprimeren tekstformaat. We konden implementeren iets als dit in C. Zo, hier is hoe we een knooppunt te vertegenwoordigen in deze boom waar we een char voor het symbool, een zwevende waarde voor de frequentie, en zoals we hebben gezien met onze andere datastructuren, 2 pointers, 1 links kind 1 rechts, die beide kunnen worden NULL, maar zo niet, het verwijst naar een linker kind en een rechter kind. Dus dit is dan Huffman codering, en het is een manier waarop je kunt gaan over het comprimeren van informatie, en het is zeker een van de meest eenvoudig te implementeren in het kader van bijvoorbeeld de gegevens van vorige week structuren, hoewel zelfs meer verfijnde algoritmen bestaan dat kan nog meer verfijnde mutaties van uw gegevens. Hebt u vragen dan aan de bomen, binaire bomen of compressie van tekst? [Student] Is er enige onduidelijkheid, alsof [onverstaanbaar] gesplitst in 01, dan 011 zou zijn dubbelzinnig, toch? [Onverstaanbaar] >> Goede vraag. Dubbelzinnigheid. Laat ik samenvatten door te verwijzen naar deze foto hier. Omdat de tekens die u comprimeert, de voorstellingen van, per definitie van dit algoritme altijd de bladeren, je zult nooit per ongeluk gebruiken hetzelfde patroon van bits voor het voorvoegsel van meerdere letters. Dus met andere woorden, je bent bezorgd over, het klinkt als een dubbelzinnigheid die voortvloeien waarbij 001 kan de start van B of begin C of iets dergelijks. Maar dat kan niet het geval zijn, omdat merken dat alle letters van het alfabet dat we coderen zijn op de bladeren. De dubbelzinnigheid kan alleen ontstaan ​​bij Morse code, Als bijvoorbeeld C was ergens langs het pad van de wortel naar B. [Student] Juist. Dus in dat geval bijvoorbeeld A heeft twee bladeren. >> Say A heeft - Zeg dat nog eens. [Student] Say A heeft 2 bladeren, F en G, en dan G - >> Oke. Maar het kan niet. Een zelf kon niet hebben vanwege hun blad F en G omdat die brieven F en G zouden zelf laat ergens links van B of rechts van E. Dus per definitie, moeten deze bladeren. Anders ben je precies goed, we hebben niet het probleem opgelost dat Morse code wordt geconfronteerd. Goede vraag. Andere vragen? Oke. Dit begrip van bits, het blijkt dat we hebben gehad kracht de hele tijd dat we niet hebben daadwerkelijk wordt gebruikt als het ging om het manipuleren van deze 0s en 1s. We hebben gevraagd om dit op een van de vroegste probleem sets: namelijk je hoe gaan over het omzetten van hoofdletters naar kleine letters of vice versa? Of, meer concreet, een van die eerste psets gevraagd hoeveel bits heb je eigenlijk over moet halen om een ​​wijziging in een of vice versa kleine letters? Hier is een snelle herinnering aan wat 65 en 97 lijken in binaire. En zelfs als die vraag is soort van vage in uw geheugen, kun je hier weer te zien dat hoeveel bits moeten worden omgedraaid om kapitaal te veranderen A naar een kleine letter? Eentje maar. Ze verschillen alleen in een locatie, de derde bit van links. Overwegende A heeft een 010, wat een heeft een 011. Dus een of andere manier moeten we gewoon in staat zijn om dat beetje omdraaien, en we kunnen dan profiteren of kleine letters. We hebben dit gedaan in het verleden door feitelijk gebruik als de omstandigheden en te controleren of de brief is tussen kapitaal A en kapitaal Z, Vervolgens uitgangen zoals A - een + 26 of iets dergelijks. Je hebt waarschijnlijk wel een rekenkundige wijziging van de letters van het alfabet. Maar wat als we gewoon omdraaien, dat enkele bit? Hoe kon je gaan over het nemen van een byte ter waarde van bits, dus 8 bits als 01000001 en 01100001? Als je had die patronen van bits, kunnen we wat gaan over het veranderen van slechts een van hen? Wat als we hier introduceren in het geel die andere patroon van bits? Als ik de hele geel koord 0s, behalve voor degene beetje dat ik wil veranderen en dan introduceer ik een nieuwe exploitant bekend als een logische bewerking - bitsgewijs in die zin dat op een individuele bits, niet op een hele byte of vier bytes tegelijk. Deze verticale balk daar in geel geeft aan, dat als we de vertegenwoordiging van het kapitaal A en bitwise OR dan met het gele opeenvolging van bits? Met andere woorden, denk terug aan onze bespreking van Booleaanse uitdrukkingen in Scratch en vervolgens in C. Het doen van een Booleaanse of betekent dat dat waar is, ofwel de eerste ding heeft om waar te zijn of de tweede ding heeft om waar te zijn of ze hebben allebei om waar te zijn, en de resulterende output zelf waar. In dit geval hier, we wat krijgen als we 0 "of" ed met 0? Valse of niet waar? Het is nog steeds vals, dus de kleine letters a blijft zoals verwacht. Wat als we in plaats daarvan 1 of 0 te doen? Dit blijft nu 1, maar let op wat er gaat hier gebeuren. Als we beginnen met hoofdletter A en we blijven "of" de individuele bits als we hier doen, 0 of de gele geeft ons wat hier beneden? Dit geeft ons 1. In feite, denk dat we niet weten wat de hoofdletters versie van weinig eigenlijk een was. Laten we gaan dit doen. Laat me dit terug te gaan hier. Laten we dit weer. 0 of 0 geeft me 0. 1 of 0 geeft me 1. 0 of 1 geeft me 1. 0 of 0 geeft me 0. Het volgende is 0, de volgende is 0, de volgende is 0. 1 of 0 geeft me 1. En dus zelfs als we niet weten van tevoren wat kleine letter a was, gewoon door "of" ing A met dit patroon van bits die we hier hebben gepresenteerd in het geel, kunt u kleine letters een hoofdletter A door het opgooien van dat beetje. We gebruikten deze uitdrukking weken geleden: het opgooien van een beetje. Hoe doe je dat eigenlijk doen programmatisch? U wat algemeen een masker, een reeks bits genoemd, in dit geval toevallig hier uitzien nummer en dan moet je 'of' het samen met deze nieuwe C-operator, niet | |, gebruikt u een | en je zou eigenlijk hier dit antwoord want waarom krijgen? Dit is de 1s plaats, 2s plaats, 4s, 8s, 16s, 32s. Dus het blijkt dat als je een hoofdletter A en bitwise OR met de integer 32, omdat het gehele getal 32, als je kijkt naar het als bits, ziet er als volgt, dat betekent dat je kunt bladeren het beetje dat je eigenlijk wilt. En evenzo - en we zullen op code er in slechts een moment - stel dat we willen de andere richting te gaan. Hoe ga je van kleine letters a tot en met hoofdletter A? Welke beetje moet veranderen? Het is dezelfde. We willen dat derde bit veranderen van een 1 op 0. En hoe kunnen we dat doen? Hoe zetten we een beetje af? Met welk patroon van bits kunnen we weer een beetje af? Wat als we sorteren van invertsuiker het masker? Waar voorheen, hebben we de hele gele masker 0s behalve degene bit we wilden zetten, wat als deze keer, maken we het hele masker 1s met uitzondering van het beetje dat we willen uitschakelen en gebruik vervolgens wat operator? Wat als wij "en" dingen? Laten we eens een kijkje nemen. Als we nu spiegelen aan deze, stel dat ik weer een masker dat is alles 1s creëren behalve voor de een bit die ik wil uitschakelen en dan in plaats van "of" de witte getallen tot top met de gele nummers hier beneden, wat als ik in plaats daarvan "en" hen samen? Het heet een bitwise en. Logisch, het is hetzelfde als een Boolean-en. Dit geeft me 0 & 1 is 0. Dus vals en waar is onwaar. Waar en waar is waar. En hier is de magie: Ware en valse is nu vals, dus we hebben uitgezet dat beetje. En nu is de rest van het verhaal is enigszins eenvoudig. Omdat de rest van het masker 1s, maakt het niet uit welke nummers in wit. Wanneer u "en" iets met echte, je niet gaat om de waarde te veranderen. Als het waar is, blijft waar. Als het vals was, blijft deze valse. Maar de magie gebeurt er als je iets dat waar was en je dan "en" het met vals. Dit heeft het effect van het uitschakelen van dat bit. Dus een beetje cryptisch daar. Laten we eigenlijk kijken naar een aantal code, die eigenlijk zou er nog meer cryptische, maar laten we een kijkje nemen hier bij tolower. Als ik kijk naar tolower, gaande van het kapitaal A naar een kleine letters, laten we eens kijken hoe we dit programma uit te voeren. Hier is de belangrijkste, en het is niet het nemen van command-line argumenten. Ik verklaar een teken c voor de brief die de gebruiker gaat typen inch Ik gebruik dan een vertrouwde do while lus om gewoon ervoor zorgen dat de gebruiker zeker geeft me een hoofdletter A of B of C. .. Z, dus ze geven me iets tussen A en Z. En nu, wat doe ik hier? Ik ben "of" ing dit met 0x20, maar dat is eigenlijk hetzelfde als - en we zullen terugkeren naar dit in een moment - 32. Dus nogmaals, 32 is dit patroon van bits hier. Hoe weten we dat? Denk eens terug aan week 0. Dit is de 1s plaats, 2s plaats, 4s, 8s, 16s, 32s plaats. Dus dit geel nummer toevallig 32. Ik kan dan hier nemen een brief als de char, bitsgewijze "of" met letterlijk de nummer 32, en wat krijg ik terug? De kleine versie van die char. Een moment geleden, hoewel, ik drukte dit in een ander basisstation notatie. Wat heeft dit voor? >> [Student] Hexadecimaal. [Malan] Dit gebeurt te vertegenwoordigen hexadecimaal. We hebben nog niet gesproken over hexadecimale zo heel veel, maar het is eigenlijk handig in gevallen als deze. Ook al ziet het er meer complexe en hoewel het lijkt erop dat de 20 en niet 32, het blijkt dat hexadecimale eigenlijk is super handig notatie want in hexadecimale elk cijfer achter de 0x - en dit betekent niets; dit is gewoon de menselijke conventie die zegt dat hier komt een hexadecimaal getal - elk van deze cijfers de 2 en de 0 kan zelf worden vertegenwoordigd met precies 4 bits. Dus als we dit doen, laat me open te stellen hier een tekst-editor - raar autocomplete - als we een beetje teksteditor hier, het aantal 0x20 betekent hier is 4 bits, hier is nog een 4 bits. Laten we het meest rechtse 4 bits eerst. 0 wanneer vertegenwoordigd met 4 bits is wat? Super makkelijk. Gewoon alle 0s. Dus 4 bits als 0s. Hoe Vertegenwoordigt u 2? Het is alweer een tijdje geleden dat we dit deden, maar het is 0100. Dus dit is de 1s plaats, dit is de 2s plaats, en dan maakt het niet uit wat de andere plaatsen zijn. Met andere woorden, in hexadecimale zou je kunnen zeggen 0x20, maar als je dan na te denken over wat er de 2 en hoe wordt het vertegenwoordigd in binaire, wat is de 0 en hoe wordt het vertegenwoordigd in binaire, de antwoorden op deze vragen zijn dit en dit, respectievelijk. Dus 0x20 gebeurt te vertegenwoordigen dit patroon van 8 bits, dat is precies het masker dat we wilden. Dit is dus voor het moment alleen maar een intellectuele oefening, maar de realiteit is in de code het typisch is vaker te schrijven constanten als dit in hexadecimale omdat dan de programmeur kan relatief gemakkelijk zelfs als het vereist enige papier en potlood, erachter te komen wat dat patroon van bits is want je kunt niet zomaar meestal uiten 0s en 1s in code. Je kunt niet naar 00010, enzovoort. Je moet decimaal of hexadecimaal of octaal of andere notaties kiezen. De meeste mensen hebben de neiging om hexadecimale halen gewoon zo dat elk getal 4 bits vertegenwoordigt en u kunt dit doen snel wiskunde. En ik zal zwaaien mijn hand op toupper, die bijna hetzelfde is, het ziet er bijna identiek. Toupper gebeurt er met het gebruik niet de of operator, maar deze man en df. Wat betekent df voor? df? Iedereen? >> [Student] 255. 255? Niet 255. Dat zou ff. We laten dit als een kleine oefening. Maar als je van 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 en wat er na 9? We zijn soort uit decimale cijfers, maar in hexadecimale wat komt er na 9? [Student] een. Dus >> a, b, c, d. U kunt daar uit welk patroon van bits d daadwerkelijk vertegenwoordigt. En als we dat doen de wiskunde, zullen we zien dat het masker je uiteindelijk krijgt terug is identiek aan deze. Dit is f, alle 1s, en is d. Dus df vertegenwoordigt dat masker. Oke. En tot slot, om geen dingen geluid super, super technisch, maar stel dat we wilden een programma dat dit doet schrijven. Laat me gaan en maak binaire, dat is een programma in een bestand met de naam binary.c. En nu laat ik lopen binaire en geef me een niet-negatief geheel getal. Laten we beginnen makkelijk en typ 0. Dit is nu een programma dat drukt een geheel getal in het binaire representatie. Dus als ik speel dit spel opnieuw en typ in slechts 1, moet ik een 32-bits representatie van 1. Als ik dit doe opnieuw met 2, moet ik dat. Als ik dat doe 7, moet ik een paar 1s te krijgen aan het eind enzovoort. Het blijkt dat ik dit te vermelden, want met bitwise operaties je kunt eigenlijk doen een ander ding ook. U kunt dynamisch te maken van deze maskers. Neem een ​​kijkje op deze laatste voorbeeld waarbij bitwise operaties. Hier is het eerste deel van de code, wordt de gebruiker gevraagd een nummer, en het dringt erop aan dat u mij een niet-negatief geheel getal. Dus dat is een soort van oude school spullen. Maar hier is iets dat is interessant. Hoe ga ik over het afdrukken van een aantal in binaire? Ik voor het eerst herhalen van wat naar wat? Wat is de grootte van een int algemeen, althans in het apparaat? >> [Student] 4. Het is 4. Dus 4 * 8 is 32 - 1 is 31. Dus als ik begin te tellen vanaf 31, dat staat, zo blijkt, net conceptueel, de 31e bit of de hoogste orde bit, wat is deze man hier, overwegende dat dit gaat worden bit 0. Dus dit is wat 01 ... bit 31. Dus wat is deze code aan het doen? Let op deze for-lus, ook al is het cryptisch lijkt, is gewoon itereren van 31 tot 0. Dat is het. Dus het interessante deel nu moet in deze 5 regels hier. Merk op dat in deze lijn ben ik een variabele genaamd masker te verklaren overeenstemming te zijn met ons verhaal van deze gele nummers. En wat dit doet? Dit is een andere logische bewerking we niet eerder gezien, het meest waarschijnlijk. Het is de linker shift operator. Deze operator doet dit. Hier is het nummer 1, en als je dat doet i left shift, verschuiving naar links, wat denk je dat heeft het effect van het doen van aan die persoon 1? Letterlijk verschuiven het over. Dus als de nummer 1 is wat je hebt aan de linkerkant en je begint met het initialiseren van i tot 31, wat is dat dan doen? Het gaat om dit nummer 1 te nemen en het verschuiven 31 plaatsen hier. En omdat er kennelijk geen andere cijfers achter de rug, die zal standaard worden vervangen door 0s. Dus je zult beginnen met het cijfer 1, die natuurlijk ziet er zo uit - en laat mij trekken hier meer dan in het centrum. En dan als je dingen naar links, deze man gaat in wezen op deze manier. Maar zodra je dat doet, krijgt een 0 ingevuld inch Als u verschuift het een tweede keer, het gaat op deze manier en een andere 0 wordt gevuld inch Je verschuiven het weer en dan nog een 0 wordt gevuld inch Dus als je dit ding van 1 << i 31 plaatsen, je uiteindelijk krijgt een masker dat is 32 tekens, de meest linkse waarvan een 1, alle overige die een 0. En het blijkt, als een terzijde, de verschuiving van een nummer aan de linkerkant als deze ook toevallig, en soms handig, heeft het effect van te doen wat naar dat nummer? >> [Student] Verdubbeling van het. Verdubbeling omdat elk van de kolommen - de 1s plaats, 2s plaats, 4s plaats, 8s plaats, 16s plaats - ze zijn allemaal verdubbeling als je gaat naar links. Of beter gezegd, als je de 1s verschuift je gaat uiteindelijk een verdubbeling van de waarde van het getal. U kunt uiteindelijk doen interessante transformaties van cijfers door het verschuiven van alles over op deze manier door machten van 2. Dus hoe werkt dit? Dit geeft me dan een masker dat is alles 0s met uitzondering van een 1 op precies de plaats waar ik wil, en dan deze uitdrukking, die is gestolen van toupper.c, is gewoon te zeggen neem het getal n dat de gebruiker heeft ingevoerd in, "En" het met dat masker, en wat ga je krijgen? Je gaat een 1 te krijgen als er een 1 in die gemaskerde locatie, of je gaat naar een 0 te krijgen als er niet. En alzo zal geheel van dit programma verleent effectief is het een lus, en creëert een masker met een hier vervolgens een 1 hier dan een 1 hier, en maakt gebruik van deze bitwise AND truc om te zeggen is er een 1 bit in input van de gebruiker hier? Is er een 1 bit in de input van de gebruiker hier? En zo ja, letterlijk af te drukken 1, anders af te drukken 0. We doen dit met ints, alleen maar omdat dat is waarom we het doen bent 32 bits in plaats van 8, maar wat we hebben vervolgens geïntroduceerd is dit bitwise AND, deze bitwise OR, en dit naar links verplaatsen gebruikt, die niet vaak erg nuttig, maar het blijkt dat ze kan zijn. In feite, als je naar iets als een array van Booleans vertegenwoordigen gewoon te vertegenwoordigen waar of onwaar, stel dat je wilde om bij te houden van al dan niet een kamer vol met 300 studenten aanwezig is, je zou kunnen verklaren een array van grootte 300 van type bool, zodat je 300 bools, en kunt u elke op true als iemand hier en anders false. Waarom is dat vertegenwoordiging op dit datastructuur inefficiënt? Wat is er slecht over het ontwerp van deze gegevens structuur, een reeks van 300 bools? Wat een bool in feite onder de motorkap? Ook dit is iets dat niet kan worden vertrouwd. Het blijkt dat er geen bool. Denk eraan dat we soort van gemaakt dat met de cs50.h bestand, die zelf ook standaard bool. C is een beetje dom, hoewel, als het gaat om bool. Het gebruikt 8 bits te vertegenwoordigen elk bool, dat volledig verspilling want uiteraard moet je hoeveel bits je nodig hebt om een ​​bool vertegenwoordigen? Slechts 1. Dus het blijkt dat als je nu de mogelijkheid met bitwise operators individuele bits even in een char, zelfs in een byte manipuleren, het blijkt dat je zou kunnen verminderen het geheugen nodig is om iets stoms te vertegenwoordigen zo vormgegeven aanwezigheid gegevensstructuur met een factor 8. In plaats van acht bits op true of false vertegenwoordigen, kon je letterlijk gebruik maken van een met behulp van een enkele byte voor elke acht leerlingen in de klas en schakelen 0-1 individuele bits door dit soort lage tricks. Dat is echt een einde maken aan de energie. Zijn er nog vragen over bitwise operaties? Ja. >> [Student] Is er een exclusieve of operator? Ja. Er is een exclusieve of operator die er zo uitziet, ^, de wortel symbool, wat betekent dat alleen de eerste ding of het tweede ding kan een 1 voor de uitgang om een ​​1. Er is ook een niet ~, waardoor u 0 naar 1 of vice versa en omkeren. En er is ook een rechtse shift operator, >>, dat is het tegenovergestelde van degene die we zagen. Oke. Laten we nu dingen naar een hoger niveau. We zijn begonnen met praten over de tekst en vervolgens te comprimeren en die de tekst met minder aantallen bits; spraken we een beetje over hoe we kunnen nu beginnen te manipuleren dingen op een bitwise niveau. Laten we nu van Z weer 10.000 voet naar vertegenwoordiging van meer complexe zaken als graphics. Hier hebben we een vlag van Duitsland hebben, hier hebben we een van Frankrijk. Deze kunnen worden vertegenwoordigd in bestandsformaten u wellicht weet - GIF, bijvoorbeeld. Als je ooit hebt gezien een afbeelding op het web die eindigt op. Gif, Dit is een Graphics Interchange Format. Deze twee vlaggen hier soort van lenen zich voor compressie voor wat misschien voor de hand liggende reden? >> [Onverstaanbaar student reactie] Er is veel herhaling, toch? Met het oog op de Duitse vlag te sturen, denk aan dit als een beeld op het scherm terug in uw Scratch dagen. Je zou kunnen herinneren dat er afzonderlijke pixels of puntjes bevatten die een beeld samen te stellen. Er is een hele rij van zwarte stippen en een andere hele rij van zwarte stippen. Er is een heleboel rijen zwarte stippen dat we konden zien of we echt ingezoomd, veel als toen we ingezoomd op het gezicht van Rob in Photoshop. Zodra we dieper en dieper en dieper in het beeld, je begon het zien van de pixelation, alle van de vierkantjes die zijn oog gecomponeerd in dat geval. Zelfde deal hier. Als we ingezoomd nogal wat, zou je zien afzonderlijke punten. Nou, dit is een soort van een verspilling van bits. Indien een derde van de vlag is zwart en een derde van de vlag is geel enzovoort, waarom kunnen we een of andere manier comprimeren deze vlag? En zelfs de Franse vlag kunnen worden gecomprimeerd, hoewel het patroon is een beetje anders. Het blijkt dat de GIF-bestandsindeling is een gecomprimeerde lossless format wat betekent dat u een beeld zoals de Duitse vlag hier te nemen, kun je een heleboel weggooien van de stukjes, zonder concessies aan de kwaliteit. Dit in tegenstelling tot iets als JPEG, waarmee de meeste van ons zijn waarschijnlijk meer vertrouwd. Facebook-foto's en Flickr foto's en dergelijke zijn bijna altijd opgeslagen als JPEG-bestanden als ze geüpload, maar JPEG is een lossy - lossy - formaat waarbij je hoeft weg te gooien stukjes maar je hebt ook weggooien kwaliteit. En dus als je comprimeren van foto's met Photoshop of upload ze naar Facebook of neem ze op een echt crappy telefoon, je weet dat het beeld begint te worden zeer vlekkerig en korrelig, en dat komt omdat het wordt gecomprimeerd door de computer of telefoon door letterlijk gooien informatie weg. Maar GIF is verbazingwekkend in dat het kan minder bits gebruiken dan het misschien standaard zonder informatie te verliezen. En doet wezen dat als volgt. In plaats van op te slaan in een bestand als een BMP zou een RGB-triple voor zwart, zwart, zwart, zwart, zwart, zwart, zwart, zwart, zwart, zwart, zwart, zwart, enzovoort, veeleer is het GIF-formaat gaan zeggen, "Black", en dan, "Herhaal dit 100 keer," of iets dergelijks. "Zwart, herhaal dit 100 keer, zwart, herhaal dit 100 keer ..." "Yellow, herhaal dit 100 keer." En zo herinnert, in wezen, de meest linkse pixel en dan codeert een of andere manier het idee van het herhalen van die pixel opnieuw en opnieuw. Dus GIF kan dan comprimeren zelf, zonder enige informatie te verliezen. Maar als je moest raden, als dat het algoritme dat gifs gebruik, welke van deze vlaggen, hoewel ze grootte identiek lijken, zal kleiner zijn wanneer ze worden opgeslagen op de harde schijf als een GIF? >> [Student] Duitsland. Duitsland zal kleiner? Waarom? [Student] Omdat je het te herhalen vele, vele malen horizontaal en dan herhaal je nog een keer. >> Precies. Omdat de mensen die het bedacht GIF gewoon een soort van willekeurig gekozen dat de herhaling zal horizontaal en niet zijdelings worden benut. Er is veel meer herhaling lateraal hier in de Duitse vlag dan in de Franse vlag. Dus als we daadwerkelijk openen van een map op mijn harde schijf dat deze GIF heeft, kun je eigenlijk zien dat de Duitse vlag hier is 2 kilobytes en de Franse een is 4 kilobytes. Het is nu eenmaal een toeval dat een is twee keer de andere, maar het is in feite het geval dat de Franse vlag is veel groter. Hoewel we hebben het hier over graphics, kan dezelfde ideeën van toepassing zijn op niet dingen zoals vlaggen, maar beelden die een beetje ingewikkelder. Als u een foto van een appel, dus er is een hoop dubbel werk daar, dus we konden een of andere manier vergeten dat de standaard achtergrond blauw is en niet, zoals het rechterbeeld suggereert moet de kleur van elke pixel in deze afbeelding herinneren. Dus we kunnen weggooien stukjes er zonder informatie te verliezen. De appel ziet er nog steeds precies hetzelfde. In dit voorbeeld hier, kunt u zien wat er gebeurt in een film. Deze vertegenwoordigen old-school filmspoelen, waarbij in de bovenste afbeelding is er heb je een camper rijden langs een huis en een boom. En als die van verleden rijdt van links naar rechts, wat natuurlijk niet veranderen? Het huis is nergens heen, en de boom gaat nergens heen. Het enige dat beweegt is de bestelwagen in dit geval. Dus als achtergrond Ongewijzigd suggereert u, wat kan doen in films wordt op dezelfde wijze gewoon weggooien informatie die niet verandert in tussen de frames. Dit is algemeen bekend als interframecompressie waarbij indien dit frame ziet er bijna identiek is aan deze, Laten we niet de moeite te slaan op de harde schijf van een van de identieke informatie op deze tussenliggende frames, laten we slechts keyframes een keer gebruiken in de zoveel tijd die daadwerkelijk op te slaan die informatie redundant net als een klein geestelijke gezondheid te controleren. Daarentegen andere benadering voor het comprimeren van video in deze tweede en lagere voorbeeld, waar in plaats van te slaan 30 frames, waarom ga je niet gewoon in plaats bewaren 15 beelden per seconde? In plaats van de film soort van stromende prachtig, perfect, Het zou kunnen kijken alsof het stotteren een beetje, een beetje oude school, maar het netto effect zal zijn veel minder bits dan anders noodzakelijk gebruiken. Dus waar komt dit dan voor ons? Dat was een beetje een terzijde van waar anders kun je gaan met compressie. Voor meer informatie over deze, neem dan een klasse als CS175 hier. Hier is een ander voorbeeld binnen video. Als de bijen is het enige bewegende, je kunt echt weggooien informatie in die midden frames omdat de bloem en de hemel en de bladeren zijn niet veranderen. Maar laten we nu nog een ding te overwegen. In de volgende 5 minuten laten we C achter voor altijd in college? Ja. Niet in de psets, dat wel. Laatste verhaal over C en dan krijgen we een zeer sexy stuff met betrekking tot HTML en web-en woo-hoo. Oke. Daar gaan we. Dat is de motivatie. Het blijkt al die tijd dat we hebben programma's lopen we Clang schrijven. En Clang, we hebben gezegd sinds de eerste week vrij veel, neemt broncode en zet deze om in object code. Het duurt C en zet het om in 0s en 1s. Ik heb soort van tegen je gelogen voor een paar weken, want het is niet zo simpel als dat. Er is veel meer aan de hand onder de kap wanneer u een programma als Clang. In feite, kan het proces van het samenstellen van een programma echt worden samengevat, zoals je misschien herinnert uit video Rob's op compilers, in deze 4 stappen: pre-processing, compileren zelf, montage, en het koppelen van. Maar we in de klas en de meeste mensen in de wereld doorgaans samen te vatten al deze stappen als gewoon "samenstellen." Maar als we beginnen met broncode als dit, herinneren is dit misschien wel de eenvoudigste C-programma we hebben tot nu toe geschreven, herinneren dat toen gecompileerd het eindigt uitziet. Maar er is eigenlijk een tussenstap, en deze stappen zijn als volgt. Eerst is er dit ding aan de top van deze en de meeste van onze programma's, # Include Wat doet # er zijn voor ons? Het vrij veel kopieert en plakt de inhoud van stdio.h in mijn bestand, zodat waarom? Waarom moet ik de zorg over de inhoud van stdio.h? Wat is daar van belang? Printf verklaring, het prototype, zodat de compiler weet dan wat ik bedoel toen ik deze functie printf noemen. Dus stap 1 bij het samenstellen van is pre-processing, waarbij een programma als Clang of een helper programma dat Clang wordt geleverd met leest uw code boven naar beneden, van links naar rechts, en elke keer dat hij ziet een # symbool, gevolgd door een zoekwoord als omvatten, voert die operatie, kopiëren en plakken in dit geval stdio.h in uw bestand. Dat is stap 1. Dan heb je een veel grotere C-bestand als gevolg van de enorme kopiëren, plakken job die net is gebeurd. Stap 2 is nu het compileren. Maar het blijkt compileren duurt source code die er als volgt uitziet en verandert het in iets dat er zo uitziet, die voor degenen die bekend zijn wordt genoemd? >> [Student] Vergadering. >> Assembler. Dit is eigenlijk iets wat als je CS61 je in duiken in meer detail. Dit is ongeveer net zo dicht als je kunt krijgen aan het schrijven van 0s en 1s jezelf maar het schrijven van dingen op een zodanige wijze dat maakt nog steeds op zijn minst een beetje zin. Dit zijn machine-instructies, en als we naar beneden scrollen naar de belangrijkste functie hier, merken dat er deze push instructie, bewegen instructie, aftrekken instructie, bel instructie, enzovoort. Als je hoort dat uw computer Intel inside heeft, heb je een Intel CPU in je Mac of pc, wat betekent dat? Een CPU is ingebouwd door bedrijven als Intel begrijpen van bepaalde instructies. Ze hebben geen idee wat functies zoals swap zijn of belangrijkste zijn per se, maar ze weten wel wat een zeer laag niveau instructies zoals het optellen, aftrekken, duwen, verplaatsen, te bellen, enzovoort zijn. Dus als je C-code compileren naar assembleertaal, uw zeer gebruiksvriendelijk uitziende code wordt omgezet in iets dat er zo uitziet, die beweegt letterlijk bytes of 4 bytes in deze in kleine eenheden in en uit de CPU. Maar uiteindelijk, als Clang is klaar om deze voorstelling van uw programma te nemen in 0 en 1, vervolgens de stap genoemd montage gebeurt en dit weer allemaal gebeurt in het knipperen van een oog bij het uitvoeren van Clang. We beginnen hier, het systeem voert een bestand als deze, en dan zet het om in deze 0s en 1s. En als je wilt om terug te gaan op een bepaald punt en eigenlijk is dit in actie te zien, Als ik in hello1.c--dit is een van de eerste programma's die we bekeken - Normaal gesproken zouden we samen te stellen dit met Clang hello1.c en dit zou ons a.out. Indien daarentegen u in plaats daarvan geven de vlag-S, wat je krijgt is hello1.s en je zult echt zien de assembler. Ik doe dit voor een zeer korte programma, maar als je terug voor Scramble of herstellen of een programma dat u hebt geschreven en gewoon uit nieuwsgierigheid willen zien hoe het er daadwerkelijk uitziet, wat er daadwerkelijk wordt ingevoerd in de CPU, kunt u dat-S vlag met Clang. Maar dan ten slotte, is er nog steeds een gotcha. Hier zijn de 0s en 1s dat mijn uitvoering van hello, wereld vertegenwoordigen. Maar ik gebruikte een ander functie in mijn programma. Dus ook al is het proces is neem ik hello.c, het wordt gecompileerd in assembly code, en dan wordt geassembleerd in 0s en 1s, de enige 0s en 1s die uitgevoerd op dit punt in de tijd zijn degenen die resulteren uit mijn code. Maar de persoon die schreef printf stelden ze hun code 20 jaar geleden en het is nu ergens geïnstalleerd op het apparaat, dus we een of andere manier hebben om zijn of haar 0s en 1s samen te voegen met mijn 0s en 1s, en dat brengt ons bij de 4e en laatste stap van het samenstellen, die bekend staat als het koppelen. Dus op de linker kant hebben we exact hetzelfde beeld als voorheen: hello.c wordt assembly code wordt 0s en 1s. Maar herinneren dat ik de standaard I / O library gebruikt in mijn code, en dat betekent dat ergens op de computer is er een bestand met de naam stdio.c althans de gecompileerde versie daarvan omdat iemand enkele jaren geleden stdio.c gecompileerd in assembly code en dan een hele hoop van 0s en 1s. Dit is wat bekend staat als een statische of een dynamische bibliotheek. Het is een bestand zit ergens in het apparaat. Maar ten slotte, ik moet mijn 0s en 1s te nemen en die persoon 0s en 1s en een of andere manier verbinden ze samen, letterlijk combineren deze 0s en 1s in een bestand genaamd a.out of hello1 of wat dan ook belde ik mijn programma zodat het eindresultaat heeft alle 1s en 0s dat mijn programma samen te stellen. Dus al die tijd dit semester als je al Clang met behulp van en nog meer recent uitgevoerde maken om Clang lopen, al deze stappen zijn er soort van direct, maar zeer bewust. En dus als je verder in de informatica, namelijk CS61, dit is de laag die je verder te schillen terug uit er praten over efficiency, gevolgen voor de beveiliging, en dergelijke van deze lagere niveau details. Maar daarmee zijn we op het punt om achter te laten C. Laten we verder gaan en nu nemen onze 5-minuten pauze, en als we terug te komen: het internet. Oke. We zijn weer terug. Nu beginnen we onze blik niet alleen op HTML, omdat, zoals u zult zien, HTML zelf is eigenlijk vrij eenvoudig maar echt op web programmeren meer in het algemeen, netwerken meer in het algemeen, en hoe al deze technologieën samenkomen zodat we veel meer geavanceerde programma's te maken boven op het internet dan tot nu toe hebben we in staat geweest om in deze zwart-wit ramen. Inderdaad, op dit punt in het semester ook al zullen we besteden relatief minder tijd op PHP, HTML, CSS, JavaScript, SQL en meer, de meeste studenten doen uiteindelijk doet laatste projecten die zijn web-based want zoals u zult zien, de achtergrond heb je nu in C is zeer van toepassing op deze hogere talen. En als je begint te denken over je afstudeerproject, die, net als Problem Set 0, waar u werden aangemoedigd voor de meeste iets van belang doen om u in Scratch, het laatste project is uw kans om uw pas ontdekte kennis en savvy te nemen met C of PHP of JavaScript of het uit als voor een spin en maak je eigen stukje software voor de wereld om te zien. En om zaadje dat je met ideeën, weet dat je hier kunt hoofd, projects.cs50.net. Elk jaar hebben we vragen ideeën van docenten en personeel en groepen studenten op de campus alleen maar om hun ideeën in te dienen voor interessante dingen die kunnen worden opgelost met behulp van computers, met behulp van websites, met behulp van software. Dus als je moeite hebt om te komen met een idee van uw eigen, met alle middelen om door de ideeën er van dit jaar en de laatste. Het is prima om een ​​project dat al eerder is aangepakt aan te pakken. We hebben gezien veel apps voor het zien van de status van wasgoed op de campus, veel apps voor het navigeren de eetzaal menu, veel apps voor het navigeren in de studiegids en dergelijke. En inderdaad, in een toekomst lezing en in de toekomst seminars, wij u kennismaken met een aantal publiek beschikbare API's, zowel in de handel verkrijgbare alsook hier verkrijgbaar bij CS50 op de campus, zodat u toegang tot de gegevens en kan dan doen interessante dingen mee. Dus meer over de definitieve projecten in een paar dagen als we de specificaties vrij te geven, maar voor nu, weet dat je kunt solo werken of met een of twee vrienden op de meeste elk project voor u van belang. The Internet. Ga je gang en trek je laptop, ga je naar facebook.com voor de eerste keer, niet hebben aangemeld voor kort en druk op Enter. Wat gebeurt er precies? Wanneer u op Enter hit op uw computer, een hele hoop stappen begint soort van magische wijze gebeurt. Dus u hier aan de linkerkant, webserver zoals Facebook is hier aan de rechterkant, en een of andere manier u gebruikt deze taal genaamd HTTP, Hypertext Transfer Protocol. HTTP is geen programmeertaal. Het is meer van een protocol. Het is een set van conventies die webbrowsers en webservers gebruiken bij interne verbinding tussen. En wat dit betekent is als volgt. Heel erg zoals in de echte wereld, hebben we deze verdragen waar als je voldoen aan een aantal menselijke voor de eerste keer, als je het niet erg humoring me hier, Ik zou naar je toe komen en zeggen: "Hallo, mijn naam is David." >> Hoi, David. Mijn naam is Sammy. "Hallo, David. Mijn naam is Sammy." Dus nu we net bezig met dit soort domme menselijke protocol waar ik het protocol werd opgezet, heeft Sammy gereageerd, We hebben handen geschud, en de transactie is voltooid. HTTP is zeer vergelijkbaar in de geest. Als uw web browser vraagt ​​www.facebook.com, wat uw browser is eigenlijk doet is de uitbreiding van haar hand, om zo te zeggen, naar de server en het is te sturen een bericht. En die boodschap is meestal iets als word - wat wil je krijgen? - Begrijp me de home page, die doorgaans wordt aangeduid met een enkele schuine streep aan het einde van een URL. En net zodat je weet welke taal ik spreek, ben ik de browser zal u vertellen dat ik spreek HTTP versie 1.1, En ook voor een goede maatregel, ik ga u vertellen dat de host die ik wil dat de home page van is facebook.com. Typisch, een webbrowser, buiten het medeweten van u, de mens, stuurt dit bericht via het Internet wanneer u typt www.facebook.com, Voer, in uw browser. En wat betekent Facebook reageren met? Het reageert met een aantal soortgelijke uitziende cryptische gegevens, maar ook nog veel meer. Laat me verder gaan hier naar huis Facebook pagina. Dit is het scherm dat de meeste van ons waarschijnlijk nooit zien als je ingelogd blijven de hele tijd, maar dit is inderdaad hun home page. Als we dit doen in Chrome, merk je dat je kunt trekken van deze kleine context menu's. Met behulp van Chrome, of op Mac OS, Windows, Linux, of iets dergelijks, Als u Controle klikken of links te klikken, kunt u meestal trek een menu dat er zo uitziet, waar een paar opties af te wachten, waarvan er een is van View Page Source. U kunt ook meestal krijgen om deze dingen door te gaan naar het menu Beeld en rondneuzen. Bijvoorbeeld, hier onder View, Developer is hetzelfde. Ik ga om verder te gaan en op View Page Source kijken. Wat je ziet is de HTML die Mark heeft geschreven aan facebook.com vertegenwoordigen. Het is een complete puinhoop hier, maar we zullen zien dat dit een beetje meer zin heeft het duurde niet lang. Maar er zijn sommige patronen hier. Laat me Scroll naar beneden voor dit soort dingen. Dit is moeilijk voor een mens om te lezen, maar merkt dat er dit patroon van haakjes met zoekwoorden als optie, zoekwoorden, zoals waarde, sommige aanhalingstekens. Dit is waar, toen u zich aanmeldde voor de allereerste keer, aangegeven wat uw geboortejaar is. Dat drop-down menu van geboorte jaar een of andere manier hier gecodeerd in deze taal genaamd HTML, HyperText Markup Language. Met andere woorden, wanneer uw browser een webpagina aanvraagt, het spreekt deze conventie genaamd HTTP. Maar wat betekent facebook.com reageren op dat verzoek? Het reageert met sommige van deze cryptische boodschappen, zoals we zullen zien in een moment. Maar de meeste van haar reactie in de vorm van HTML, HyperText Markup Language. Dat is de werkelijke taal waarin een webpagina is geschreven. En wat een webbrowser is echt dan is, na ontvangst van iets dat er zo uitziet, leest het van boven naar beneden, van links naar rechts, en elke keer dat hij ziet een van deze haakjes gevolgd door een zoekwoord als optie, geeft dat opmaaktaal op de juiste manier. In dit geval toont het een drop-down menu jaren. Maar nogmaals, dit is een grote puinhoop om naar te kijken. Dit is niet omdat Facebook ontwikkelaars manifesteren 0 voor 5 voor stijl, bijvoorbeeld. Dit is omdat de meeste van de code die ze schrijven, in feite, prachtig geschreven, goed commentaar, mooi ingesprongen, en dergelijke, maar natuurlijk machines, computers, browsers echt niet schelen of uw code is goed ingericht. En in feite, het is volledig verspilling van de tab-toets raken al die keren en om een ​​reactie te plaatsen door heel uw code in en om echt beschrijvende variabele namen te kiezen want als de browser maakt het niet uit, alles wat je aan het doen bent op het einde van de dag verspillen bytes. Zo blijkt wat de meeste websites doen is ook al is de broncode voor facebook.com, voor cs50.net en al die andere websites op het internet zijn meestal goed geschreven en goed commentaar en mooi ingesprongen en dergelijke, meestal voordat de website wordt geplaatst op het internet, wordt de code minified, waarbij de HTML en de CSS - iets anders zullen we snel zien - de JavaScript-code zullen we binnenkort wordt gecomprimeerd, waarbij lange variabelenamen worden X en Y en Z, en dat alles witruimte dat maakt alles ziet er zo leesbaar is allemaal weggegooid, want als je erover nadenkt deze manier, Facebook krijgt een miljard page hits per dag - iets geks als dat - dus wat als een programmeur alleen maar om anale druk op de spatiebalk een extra tijd alleen maar laten inspringen enkele regel code nog zo veel meer? Wat is de implicatie als Facebook behoudt dat witruimte in alle bytes ze terug te sturen naar mensen op het internet? Het raken van de spatiebalk een keer geeft u een extra byte in uw bestand. En als een miljard mensen ga dan naar de home pagina te downloaden die dag, hoeveel meer gegevens heb je via het internet? Een gigabyte zonder goede reden. En verleend, voor veel websites is dit niet zo'n probleem schaalbaar, maar voor Facebook, voor Google, voor een aantal van de meest populaire websites er is grote stimulans financieel om uw code ziet eruit als een puinhoop zodat u met zo weinig bytes mogelijk in aanvulling op dan het te comprimeren met behulp van iets als zip, een algoritme genaamd gzip, dat de browser voor je doet automatisch. Maar dit is verschrikkelijk. We zullen nooit iets leren over andere mensen websites en hoe je webpagina's te ontwerpen als we ernaar uitzien. Dus gelukkig, browsers zoals Chrome en IE en Firefox deze dagen meestal geleverd met ingebouwde ontwikkeltools. In feite, als ik naar beneden gaan hier naar Element of als Inspecteer ik ga naar Beeld, Developer, en expliciet naar Developer Tools, dit venster aan de onderkant van mijn scherm verschijnt nu. Het is een beetje intimiderend op het eerste, want er is een heleboel onbekende tabs hier, maar als ik klik op elementen helemaal links onderaan, Chrome is natuurlijk behoorlijk slim. Het weet hoe te interpreteren van deze code. En dus wat Chrome doet is het reinigt alle HTML van Facebook. Ook al is er geen witruimte is er, er is niet inspringen daar, nu merk dat ik kan beginnen met deze webpagina navigeren des te meer hiërarchisch. Het blijkt dat elke webpagina geschreven in een taal genaamd HTML5 moet beginnen met deze, deze DOCTYPE-declaratie, bij wijze van spreken: Het is een soort van licht en grijze daar, maar dat is de allereerste regel van de code in dit bestand, en dat vertelt alleen de browser, "He, hier enkele HTML5 komt. Hier komt een webpagina." De eerste open beugel voorbij dat toevallig dit ding, een open beugel HTML-tag, en dan als ik duiken in dieper - deze pijlen zijn volledig zinloos; ze gewoon omwille presentatie, ze zijn niet echt in dossier - merken dat de binnenkant van HTML-tag van Facebook, iets dat begint met een open beugel en heeft een woord wordt een tag. Dus in de HTML-tag is blijkbaar een hoofd-tag en een body-tag. Binnenkant van het hoofd tag is nu een puinhoop voor Facebook omdat ze een veel metadata en andere dingen voor marketing en reclame. Maar als we naar beneden scrollen, omlaag, omlaag, omlaag, laten we eens kijken waar het is. Hier is. Dit is ten minste enigszins vertrouwd. De titel van thuis Facebook pagina, als je ooit kijken in het tabblad in uw titel bar, is Welcome to Facebook - Log In, Aanmelden of meer informatie. Dat is wat je zou zien in de titel van Chrome bar, en dat is hoe het is vertegenwoordigd in de code. Als we negeren al het andere in het hoofd, het grootste deel van de ingewanden van een webpagina zijn in het lichaam, en het blijkt dat Facebook de code er uit gaat zien meer complexe dan de meeste dingen die we in eerste instantie schrijven, alleen maar omdat het is opgebouwd door de jaren heen, maar er is een heleboel script tags, JavaScript-code, dat maakt de website zeer interactief: het zien van status updates direct met behulp van talen zoals JavaScript. Er is zoiets als een div, dat is een divisie van een pagina. Maar voordat we dat detail, laten we proberen om uit te zoomen en kijken naar een eenvoudiger versie van Facebook 1.0, bij wijze van spreken. Hier is de hello, wereld van de webpagina's. Het heeft dat DOCTYPE-declaratie op de top dat is een beetje anders dan al het andere. Niets anders schrijven we in een webpagina gaat om te beginnen met zeggen voor vet. Nogmaals, het verhaal is hetzelfde: hello, komma, beginnen met het maken van dit vet, Vervolgens wereld wordt vetgedrukt, en dit betekent meer wilt afdrukken deze in het vet. Laat me ga je gang en sla mijn dossier, ga terug naar Chrome, zal ik inzoomen zodat we kunnen zien het beter, en herladen, en je zult zien dat wereld is nu in het vet. Het web is alles over hyperlinks, dus laten we verder gaan en doe je dit: mijn favoriete website is, laten we zeggen, youtube.com. Opslaan, herladen. Oke. Er zijn een paar problemen nu naast de afzichtelijkheid van de website. 1, ik ben er vrij zeker van dat ik geraakt Voer hier. En dat deed ik. Ik heb niet alleen druk op Enter, ik ook ingesprongen, het beoefenen van wat we hebben gepredikt over stijl, maar mijn ligt direct naast wereld. Dus waarom is dit? Browsers alleen doen wat je ze vertelt te doen. Ik heb nog niet verteld de browser, "Break lijnen hier. Steek paragraaf hier te breken." Dus de browser, maakt het niet uit of ik druk op Return 30 keer, het is nog steeds om mijn recht te zetten naast wereld. Wat ik echt moet doen, is iets als zeggen
, voegt u een regeleinde. En eigenlijk, een regeleinde is een soort van raar ding want je kunt niet echt in beweging naar een andere regel dan iets doen, en dan stoppen met bewegen om een ​​nieuwe regel. Het is een soort van een atomaire operatie. Je doet het of je doet het niet. Je druk op Enter of je doet het niet. Dus br is een beetje van een andere tag, en dus ik moet sorteren van zowel open en te sluiten tegelijk. De syntaxis voor dat is dit. Technisch gezien kun je zoiets als dit doen in sommige versies van HTML, maar dit is gewoon dom omdat er geen reden om te starten en te stoppen iets als je in plaats daarvan het allemaal in een keer. Realiseer je dat HTML5 niet strikt dit niet slash vereisen, dus je ziet studieboeken en online bronnen die niet beschikken over het, maar laten we voor een goede maatregel de praktijk van de symmetrie die we tot nu toe gezien. Dit betekent dat de tag zowel geopend en gesloten. Dus nu laat ik bewaar mijn bestand, hier terug. Oke, dus het begint er beter uitzien, met uitzondering van het web Ik weet dat is een soort van aanklikbaar, en toch youtube hier lijkt niet te leiden tot niets. Dat komt omdat, hoewel het lijkt op een link, wordt de browser niet dat per se, dus ik moet de browser te vertellen dat dit is een link. De manier om dit te doen is het gebruik van een anker tag: en laat me dit verplaatsen naar een nieuwe lijn net dus het is een beetje beter leesbaar, en ik zal krimpen de lettergrootte. Ben ik al klaar? Nee, er gaat deze tweedeling te zijn. Deze tag, het anker tag, inderdaad neemt een attribuut, die wijzigt haar gedrag, en de waarde van dit attribuut is blijkbaar van YouTube URL. Maar let op de tweedeling is dat alleen maar omdat dat is de URL die je gaat, dat wil niet zeggen dat is toch wel het woord dat je onderstrepen en het maken van een link. Integendeel, kan dat iets als dit. Dus ik moet zeggen het maken van dit woord een hyperlink met behulp van de nauwe ankertag stoppen. Merk op dat ik doe dit niet. 1, zou dit gewoon een verspilling van ieders tijd en het is niet nodig. Om een ​​tag te sluiten, kunt u pas weer vermelding van de naam van de tag. U hoeft geen melding van een van de attributen. Dus laten we met dien verstande dat, ga terug. Oke, voila, nu is het blauw en hyperlinks. Als ik erop klik, ik eigenlijk wel naar YouTube. Dus ook al mijn web pagina is niet op het internet, is het op zijn minst HTML, en als we het internet halen, zouden we eigenlijk hier belanden op youtube.com. En ik kan terug te gaan en hier is mijn webpagina. Maar merken. Als je ooit hebt gekregen spam of een phishing-aanval, nu heb je de mogelijkheid al na vijf minuten om hetzelfde te doen. We kunnen hier te gaan en iets doen als www.badguy.com of wat dan ook de schetsmatige website is, en dan kun je zeggen: Controleer uw PayPal-rekening. [Gelach] En nu dit gaat naar badguy.com, die ik ben niet van plan om te klikken op want ik heb geen idee waar dat toe leidt. [Gelach] Maar we hebben nu de mogelijkheid om daadwerkelijk daar terecht. Dus we zijn echt net beginnen te krassen op het oppervlak. We zijn niet het programmeren op zich, we schrijven bent opmaaktaal. Maar zodra we rond onze woordenschat in HTML, introduceren we PHP, een echte programmeertaal die ons in staat om automatisch HTML, automatisch genereren van CSS, zodat we kunnen beginnen op woensdag te implementeren, te zeggen, onze eigen zoekmachine en nog veel meer. Maar meer daarover in een paar dagen. We zien je dan. [CS50.TV]