[Powered by Google Translate] [Uge 7] [David J. Malan - Harvard University] [Dette er CS50. - CS50.TV] Ok. Velkommen tilbage. Dette er CS50, og dette er begyndelsen af ​​uge 7. Et par små meddelelser: Pset5 er nu i gang, eller snart skal være, og lad mig sige, helt ærligt, er dette en tendens til at være blandt de mere udfordrende af kursets problem sæt, så lad mig nævne det nu således at denne uge mere end nogensinde du ikke vente, siger, onsdag aften eller torsdag aften at dykke i. Dette er absolut en interessant Pset. Vi synes, det er sjovt. Hvis du rent faktisk får det fuldt korrekt og kan derefter udfordre den såkaldte Big Board, har du mulighed for at matche kræfter med nogle af kursets personale og nogle af dine klassekammerater. Hvad The Big Board er er når du har din stavekontrol arbejde, vil du være i stand til at gå til cs50.net efter kører en kommando, rent tilmelde, og derefter mængden af ​​tid og mængden af ​​RAM og mere at du har brugt i din implementering vil blive udstillet her på kursets hjemmeside. Du vil opdage, at en hel masse af disse folk her er opført som personale da i løbet af weekenden, troede personalet, det ville være sjovt at prøve at overgå hinanden. Så indse, at målet her ikke er at overgå de ansatte. Selv er jeg kun her på nummer 13. Rent tilmelde, men det er en mulighed for at se hvor lidt RAM og hvor få CPU sekunder kan du bruge vis-a-vis nogle af dine klassekammerater. Og jeg vil indrømme, at Kevin Michael Schmid, i øjeblikket nummer 1 position som en af ​​de TF'er, dette er en implementering, som vi ikke kalde mulig idet han bruger næsten 0 RAM og næsten 0 sekunder til ilægning. Så vi tager os af Kevin offline. [Latter] Der er visse færdigheder, som Kevin er ved at lægge til testen her. En af de ting, vi troede, vi ville gøre alt for nu CS50x er en uge i gang, og du fyre er lige så meget en del af dette eksperiment som de studerende er. Vi har bedt dem som en del af deres pset0, hvilket var ligeledes at indsende en Scratch projekt af interesse for dem - et spil, en interaktiv kunstværk, en animation eller lignende - en 1 - til 2-minutters video, hvis de gerne vil, siger hej til verden og hvem de egentlig er. Jeg tænkte jeg ville dele med jer bare et par af de videoer, der er blevet fremlagt hidtil fordi for os, om de ansatte i det mindste, det har virkelig været spændende og inspirerende at se disse folk fra hele verden - lande over hele verden - tuning i, af alle ting, til en computer science kursus på internettet, uanset om det er fordi de ønsker at fortsætte deres egne undersøgelser, de ønsker at tage deres karriere i en ny retning, de ønsker at udfylde huller i deres egen viden, så nogle af de samme grunde, som du fyre måske har været her. Så jeg giver dig en sådan elev her. Du kan hæve lydstyrken bare en lille smule. Her er en af ​​vores elevers 1-minut indlæg. Hej, verden. Jeg er en elev af industriel ingeniørvirksomhed her i Malaga, Spanien. Jeg er begejstret for dette online kursus, fordi jeg elsker datalogi, det gør jeg virkelig, og jeg virkelig værdsætter, at jeg får at udforske det. Og det faktum, at jeg kan lære det samme alle jer fyre men i stedet for at være i Harvard Jeg er i Malaga, er hvordan awesome det? Tja, jeg er Fernando, og det er CS50. Se jer. [Latter] En anden klip vi godt kan lide, vil du opdage, at denne gentleman-engelsk ikke er så stærk. Det ser ud som om han havde det maskine oversat, så oversættelserne selv er en smule ufuldkommen, men det var en af ​​vores favoritter hidtil så godt. [♪ ♪] Hej, verden. [Taler i japansk] [Jeg er nødt til at hilse på japansk, fordi mit engelsk er meget upålidelige.] [Jeg har leveret budskabet til dig fra byen Gifu, Japan.] [Jeg kan være en elev for første gang i 20 år, som det kan ses.] [Jeg er meget taknemmelig for Harvard University, der gav mig denne mulighed og EDX.] [Golf er en guitar og min yndlings ting kører.] [Latter] [♪ ♪] [Hvorfor tror du, jeg prøvede at deltage i et cs50x.] [Harvard University, det er min længsel.] [Især hvis jeg er fjernt tilstedeværelse boede i Japan.] [Jeg ønskede at forsøge straks klar over eksistensen af ​​en sådan EDX hvornår.] [Tror du ikke, så du behøver ikke relateret til alder af læring I.] [CS50 er min længsel. Mit navn er Kazu, og dette er CS50.] [♪ ♪] [bifald og råber] En anden favorit vores var dette anbringende her fra nogen. [♪ ♪] [Malan] Google det, hvis du ikke er fortrolig med denne meme. Og så endelig et par andre, der fik bogført at måske vinde yndig pris. [Studerende] Aww! >> [Malan] Vi bliver nødt til at lytte. Det er kort, så lyt nøje. [Kvindelig taler] Hvad er dit navn? >> Louie. [Kvindelig taler] Hvad er det? >> [Fniser] CS50. [Latter] [Malan] Han gjorde to tager, selv om. Her går vi, det sidste. Mit navn er Louie, og dette er CS50. [Latter] Dette er så CS50x. Tak til alle dem af jer, mens du følger langs derhjemme der har tage del hidtil. I dag, vi afslutter vores diskussion af datastrukturer, i det mindste nogle af de mest grundlæggende, og så fortsætter vi vores samtale om HTML og webprogrammering. Faktisk har vi brugt de sidste ca syv uger at se på de grundlæggende principper for programmering - algoritmer, datastrukturer og lignende - og C, som du måske har oplevet hidtil, er ikke nødvendigvis den mest tilgængelige af sprog med til at gennemføre nogle af disse ideer. Og så begynder i denne uge og i næste uge og derefter den følgende, vi vil endelig være i stand til at skifte fra C, hvilket er almindeligt kendt som et ret lavt niveau sprog, til ting højere niveau, blandt dem PHP, JavaScript og lignende, som vi vil se trække på de samme erfaringer, som vi har lært i løbet af de sidste par uger, men du vil opdage, at erklære ting som arrays og hash-tabeller og søgning og sortering blevet så meget lettere, fordi de sprog, selv vi vil begynde at bruge vil blive mere kraftfuld. Men først en ansøgning af træer. Det er meget almindeligt i disse dage at nødt til at komprimere oplysninger. I hvilken sammenhæng ville du ønsker at komprimere en slags digital information? Yeah. >> [Studerende] Når du har brug for at sende det via internettet. Ja, når du ønsker at sende noget via internettet. Hvis du ønsker at downloade en stor fil, er det ideelt, hvis nogen på den anden ende har komprimeret filen ved hjælp af en zip-format eller noget i den retning så du sender færre bits end man ellers skal sendes. Så hvordan kan du komprimere information? Det hele kan koges ned til at bruge færre bits end der kræves som standard. Men det er sådan en underlig ting, fordi tænke tilbage på uge 0 og 1 når vi talte om ASCII og binære og vi talte om ASCII især som bruger 8 bit til at repræsentere bogstaver i alfabetet således at bogstavet A er repræsenteret ved 65, små bogstaver a er antallet 97, og dog du repræsenterer 65 eller 97, du bruger 7 eller 8 bit. Men fangsten er, at der er nogle bogstaver i det engelske alfabet der er ikke så populære som andre. Z er ikke så populær, Q er ikke så populær, men A og E er super populære. Og dog for alle disse breve, som standard verden bruger det samme antal bit, kun 8. Så ville det ikke have været smartere, hvis stedet for at bruge 8 bit for hvert bogstav, selv de mest hyppigt anvendes som Q og Z, hvad nu hvis vi brugte færre bits for A og E og S og de mest populære bogstaver og bruges flere bits for de mindre populære bogstaver, Ideen er lad os optimere for den fælles sag, der er et tema i datalogi for at forsøge at optimere, hvad der kommer til at ske mest og tilbringe lidt mere tid, lidt mere plads på de ting,, yeah, kunne ske men ikke nødvendigvis så tit. Så lad os tage et eksempel. Antag, at vi ønsker at indkode information temmelig effektivt. Du har måske vokset op uden at kende lidt om Morse kode, og odds er du ikke vidste den konkrete kode men du kan huske, at det er mindst denne serie af prikker og streger. Dette er en ret effektiv kodning, og bemærk, at de mest populære bogstav - for eksempel, E - bruger den korteste af bip-lyde. Morse kode handler om bip-bip-bip-bip-bip-bip og holde toner enten i korte tidsrum eller længere perioder. E, som angivet af prik, er en super kort bip, bare bip, og det ville repræsentere E. Derimod vil T være en længere bip, ligesom bip [forlænger lyd], og der ville repræsentere T. Men det er stadig temmelig kort, fordi derimod hvis man ser på Z, at udtrykke Z du ville gå bip, bip [længere lyd], bip, bip [kortere lyd]. Så det er længere, fordi det er mindre udbredt. Men gotcha her er, at morsekode er en smule fejlbehæftet i, at det ikke umiddelbart kan dekodes. For eksempel antage, at du hører om nogle ende af tråden bip [kort], bip [lang]. Hvilket budskab har jeg bare modtage? En prik og en streg. Hvad betyder det for? [Studerende] A. >> [Malan] Måske. Det kunne også være E efterfulgt af T. Med andre ord morsekode, selvom det udnytter dette princip at optimere hjørnet tilfældet, det egner sig ikke til øjeblikkelig decodability. Det vil sige, mennesket, der hører eller modtagelsen af ​​disse prikker og streger har en eller anden måde finde ud af hvor pauserne er mellem bogstaver, fordi hvis du ikke ved, hvor disse pauser er, kan du forvirre A til ET eller omvendt. Så hvad kan du gøre? I morsekode du bare kunne pause mellem hver af bogstaverne. Men pause er slags modstrid med hele pointen med at fremskynde tingene op. Så hvad nu hvis vi i stedet kom op med en kode, hvor der ikke var denne dårlig situation hvor E er et præfiks for eksempel af A - med andre ord, hvis vi kunne sørge for, at de mønstre stadig er kort for de populære breve længes efter de mindre populære bogstaver, men der er ingen mulig forvirring? En mand ved navn Huffman år siden opfandt denne ordning kaldet Huffman kodning der rent faktisk udnytter en af ​​de datastrukturer vi har brugt lidt tid på at tale om denne sidste uge, nemlig træer, binære træer specifikt - et binært træ betyder, at det ikke har nogen mere end 2 børn. Det har måske en venstre barn, måske en ret barn, og det er det. Så formoder bare af hensyn til diskussion, at nogen ønsker at sende en besked der ser sådan ud. Det er komplet nonsens, men det er sammensat af As, Bs, Cs, Ds og Es. Og hvis du rent faktisk tælle op alle de As, Bs, Cs, Ds og Es og derefter dividere med det samlede antal bogstaver, denne lille diagram her siger, at 45% af brevene er Es, 20% er As, 10% B, og så videre. Så med andre ord antage, at den citerede streng der er blot nogle meddelelse, du vil sende. Det sker for at være nonsens bare så vi kan bruge så få bogstaver som muligt, men det er faktisk sådan, at E er fortsat det mest populære, og B og C er den mindst populære i det mindste af disse 5 bogstaver i alfabetet. Så hvordan kan vi gå om at komme op med en kodning, en binær kodning, et mønster af 0'er og 1-taller for hver af disse breve på en sådan måde, at E er en kort mønster og måske B og C er lidt længere mønstre, igen, Ideen er, at vi ønsker at bruge færre bits meste af tiden og flere bits kun én gang i et stykke tid. Ifølge Huffman kodning, kan du oprette en skov af træer. Der er en slags historie linje her, der involverer træer og også processen med at opbygge dem op. Lad os begynde. Jeg foreslår, at du starter med denne skov, så at sige, af 5 træer, som hver især er en temmelig dum træ. Træet består af blot en enkelt knude, som repræsenteret ved en cirkel. Så hver af disse ting kan være en C struct og indersiden af ​​C struct kan være en flyder, der repræsenterer hyppigheden og så måske en char repræsenterer brevet. Så tænk på disse knudepunkter som bare noget gammelt C struct, men for nu, højere niveau. Dette er en skov af 5 træer, hver af hvem kun har en enkelt node. Hvad Huffman foreslåede er, at vi begynder at kombinere de træer der har de mindste frekvens tæller i lidt større træer ved at forbinde dem med en ny rod node. Så blandt de breve her, at for nemheds jeg har sorteret dem fra venstre mod højre, selv om det ikke er strengt nødvendigt, og bemærk, at de mindste knudepunkter er i øjeblikket 10% og 10%. Så Huffman foreslog, at vi flette de 2 mindste knudepunkter i et nyt træ ved at indføre en ny forælder node og derefter give den pågældende forælder en venstre barn og en højre barn hvor B er vilkårligt venstre og C er vilkårligt højre. Og så Huffman desuden foreslået, at lad os nu bare tænke på den venstre barn i et af disse træer altid som værende repræsenteret ved 0 og den rigtige barn altid som at være repræsenteret med tallet 1. Det betyder ikke noget, hvis du vende dem, så længe du er konsekvent. Så nu har vi fire træer i denne skov. Og jeg siger fire, fordi nu træet på venstre - og det er ikke så meget et træ i den forstand, at det vokser på denne måde, det er mere som et stamtræ, hvor nu 0,2 er en slags moderselskab for de to børn - bemærke, at i denne forælder vi har trukket 0,2. Vi har tilføjet de frekvensbånd tællinger af de to børn og givet den nye node den samlede sum. Så nu er vi bare gentage denne proces. Find de to mindste noder og derefter slutte sig til dem i et nyt træ og derefter gentage processen yderligere. Lige nu har vi et par kandidater, 20%, 15% og yderligere 20%. I dette tilfælde er vi nødt til at bryde uafgjort. Vi kan gøre det vilkårligt. Vi skal bare gøre det konsekvent. I dette tilfælde vil jeg vilkårligt gå med den til venstre, og jeg nu fusionere de 20% og 15% for at give mig en ny forælder kaldet 35%, hvis venstre barn er 0, hvis ret barn er 1, og nu har vi kun tre træer i skoven. Du kan måske se, hvor dette foregår. Hvis vi gentager dette et par gange mere, vi vil have bare en større træ, hvor alle kanter er mærket med 0'er og 1'ere. Lad os gøre det igen. 35% er, at træets rod. 20% og 45%, så vi vil fusionere de 35% og 20%. Nu har vi dette træ her. Vi tilføje dem sammen, har vi 55%. Nu er der kun to træer i skoven. Vi gør dette en sidste gang, og forhåbentlig matematisk alle frekvenser tilføje op fordi de siden skulle vi beregnet dem fra get-go at tilføje op til 100%. Og nu har vi et træ. Så dette er en Huffman-kodning træ. Det slags tog lang tid at få der verbalt, men virkeligheden er med en for-løkke eller med en rekursiv funktion, kan du bygge denne ting op temmelig hurtigt. Så nu har vi en ny knude, og alle disse indre knudepunkter er blevet malloc'd, formodentlig undervejs. Så nu i toppen af ​​dette træ har vi 100%, men nu ser vi, har en sti fra denne nye tip-tip-oldeforældre til alle de tip-tip-oldebørn helt i bunden, til alle bladene. Hvad vi vil gøre nu, er foreslå, at for at repræsentere bogstavet E, Vi vil blot bruge nummer 1. Hvorfor? For hvis vi krydser dette træ fra den endelige rod ned til bladet er kendt som E, vi følger blot den ene kant, højre kant, og der er mærket selvfølgelig øverst til højre 1. Så antydes her for Huffman var, at E er kodning i binær bare skal være 1. Og det er pretty damn effektiv. Kan ikke rigtig få noget mindre end det. Derimod er en going at blive repræsenteret, hvis du følger den logik, ved hvilken mønster af bit i stedet? 01. Så for at komme til A, vi starter ved roden, og vi går til venstre og så går vi til højre, hvilket betyder, at vi fulgte en 0 og derefter en 1. Så vi repræsenterer bogstavet A med mønsteret 0 og 1. Og nu ser vi allerede har en egenskab af øjeblikkelig decodability at vi ikke havde i morsekode. Selv om begge disse mønstre er temmelig korte - E er 1 bit, A er 2 bits - bemærket, at de ikke kan forveksles ene eller den anden, fordi hvis du ser en 1 det har fået til at være en E, hvis du ser et 0 så en 1 det er selvfølgelig nødt til at være et A. Ligeledes, hvad er D? 001. Hvad er C? 0001. Og hvad er B? 0000. Og igen, fordi alle de breve, vi holder af, er på bladene og ingen af ​​dem er slags mellemmænd i vejen fra rod til blad, der er ingen risiko for conflating 2 bogstaver 'forskellige kodninger idet alle disse bitmønstre er deterministisk. 0000 vil altid være B. Der er ingen knude et sted i mellem, at du kan forvirre et bogstav for den anden. Så hvad er konsekvenserne her? Den mest populære bogstav - i dette tilfælde E - har fået den korteste kodning, A har fået den næste korteste kodning, og B og C, som vi allerede vidste fra get-go var slags den mindst populære ved 10% frekvens hver, har de fået den længste kodning. Og så hvad det betyder nu, er, at hvis du ønsker at sende en besked, der er komprimeret over internettet eller i en e-mail eller lignende, snarere end at bruge standard ASCII, kan du sende et Huffman kodet meddelelse hvorved hvis du ønsker at sende brevet E, du sender bare en enkelt bit. Hvis du ønsker at sende en A, kan du sende 2 bit, 01, i stedet for at sende 8 bit efterfulgt af yderligere 8 bit efterfulgt af en anden 8 bits og så videre. Men der er en gotcha her. Det er ikke nok bare at konstruere dette træ, og derefter begynde at sende fra Alice til Bob den kortere bit mønster, snor fra ASCII, fordi Alice også underrette Bob, hvad hvis Bob vil være i stand til at læse hendes komprimerede besked? [Uhørlig student svar] >> Hvad er det? [Uhørlig student svar] >> Af hvad træet er. Eller endnu mere specifikt, hvad disse kodninger er, især da i løbet af denne historie har vi lavet en dom opkald på et tidspunkt. Husk, at vi var nødt til at plukke vilkårligt mellem de 2 forskellige 20% noder? Så det er ikke sådan, at Bob, modtageren, kan bare rekonstruere træet på sin egen fordi han måske vil skabe træet nogensinde så lidt forskelligt fra Alice. I øvrigt har Bob ikke engang ved, hvad den oprindelige meddelelse er fordi det eneste Alice sender ham, er selvfølgelig den komprimerede indlæg. Så fangsten med komprimering som dette er, at ja, kan Alice spare en hel masse bits ved at sende 1 for E og 01 for A og så videre, men hun har også til at informere Bob hvad kortlægning er mellem bogstaver og bits fordi de ikke kan klart påberåbe sig bare ASCII længere, hvis vi ikke bruger ASCII. Så hun kan enten sende ham træet eller anden måde - skrive det ned, gemme det som binære data eller noget i den retning - eller bare sende ham en lille snyde ark, en Excel-fil, der viser de kortlægninger. Så effektiviteten af ​​kompression virkelig antager, at de meddelelser, du sender er temmelig store, mindst mellemstore, fordi hvis du sender en super kort besked, hvis du blot ønsker at sende meddelelsen BAD, der sker for at være et ord, vi kan stave her, B-A-D, er du sandsynligvis kommer til at bruge færre bits, men fangsten er, hvis du også nødt til at informere Bob hvad træet er eller hvad disse kodninger er, er du nødt til sandsynligvis opveje alle de besparelser at have komprimerede ting at begynde med. Så det kan faktisk være sådan, at hvis du prøver at komprimere selv med noget lignende lynlås eller filformater, du kan være bekendt med - temmelig små filer, selv tomme filer - undertiden disse filer kan få større og ikke mindre. Men realistisk set, det sker kun for små filstørrelser, så det kommer ikke til at lave en gigabyte fil være 2 GB; vi virkelig taler bytes eller blot et par kilobyte. Nogle programmer som zip er smart nok til at indse, at "Du kommer til at tilbringe flere bits komprimere dette." "Lad mig ikke gider at komprimere den for dig på alle." Så dette er blot én måde derefter at komprimere tekst format. Vi kunne gennemføre noget som dette i C. For eksempel er her, hvordan man kan udgøre et knudepunkt i dette træ hvor vi har en char for symbolet, en flydende værdi for den frekvens, og som vi har set med vore andre datastrukturer, 2 pegepinde, 1 til venstre barn, 1 til højre, som begge kan være nul, men hvis ikke, det henviser til en venstre barn og en højre barn. Så, det er Huffman-kodning, og det er en måde at du kan gå om at komprimere information, og det er helt sikkert en af ​​de mest let at implementere i forbindelse med, siger, sidste uges datastrukturer, men endnu mere sofistikerede algoritmer findes der kan gøre endnu mere sofistikerede mutationer af dine data. Eventuelle spørgsmål derefter på træer, binære træer eller komprimering af tekst? [Studerende] Er der nogen tvetydighed, ligesom hvis [uhørligt] opdelt i 01, så 011 ville være tvetydig, right? [Uhørlig] >> Godt spørgsmål. Tvetydighed. Lad mig opsummere ved at henvise til dette billede her. Fordi de tegn, du komprimere, de repræsentationer, ved definitionen af ​​denne algoritme altid forbliver bladene, du aldrig ved et uheld bruge det samme mønster af bits for præfikset af flere breve. Så med andre ord, du er bekymret, det lyder som, en tvetydighed opstår hvorved 001 kunne være starten på B eller starten på C eller noget lignende. Men det kan ikke være tilfældet, fordi bekendtgørelsen, at alle bogstaverne i alfabetet, vi koder er på bladene. Flertydigheden kan kun opstå, som det er tilfældet med Morse-koden, hvis for eksempel, var C et eller andet sted langs stien fra roden til B. [Studerende] Right. Så i dette tilfælde, siger A har 2 blade. >> Sig A har - Sig det igen. [Studerende] Sig A har 2 blade, F og G, og derefter G - >> Okay. Men det kan man ikke. En selv kunne ikke have blade F og G, fordi disse skrivelser F og G i sig selv være overlader et sted til venstre for B eller retten til E. Så ved definition, skal de være blade. Ellers er du helt rigtige, har vi ikke løst det problem, at Morse kode står over for. Godt spørgsmål. Andre spørgsmål? Ok. Denne opfattelse af bits, viser det sig, vi har haft magten hele tiden, at vi har faktisk ikke brugt når det kom til at manipulere disse 0'er og 1'ere. Vi spurgte om dette på en af ​​de tidligste problem sæt: nemlig, hvordan kan du gå om at konvertere store til små bogstaver eller omvendt? Eller mere konkret, en af ​​de første psets spurgte hvor mange bits du faktisk nødt til at vende for at ændre A til små bogstaver et eller vice versa? Her er en hurtig påmindelse om, hvad 65 og 97 ser ud i binær. Og selv hvis dette spørgsmål har slags falmet i din hukommelse, du kan se igen her, at hvor mange bits der skal vendes at ændre kapital A til små bogstaver a? Blot én. De adskiller sig kun på ét sted, den tredje bit fra venstre. Hvorimod A har en 010, lille en har en 011. Så en eller anden måde skal vi bare være i stand til at vende den smule, og vi kan så udnytte eller små bogstaver. Vi har gjort dette i fortiden ved faktisk at bruge, hvis forholdene og kontrol, hvis brevet er mellem kapital A og kapital Z, så udgange som A - a + 26 eller sådan noget. Du har sikkert gjorde et aritmetisk ændring af bogstaverne i alfabetet. Men hvad nu hvis vi bare kunne vende det enkelt bit? Hvordan kunne du gå om at tage én byte værd af bits, så 8 bit ligesom 01.000.001 og 01.100.001? Hvis du havde disse mønstre af bits, hvordan kan vi gå om at ændre bare en af ​​dem? Hvad hvis vi indfører i gult her til andet mønster af bits? Hvis jeg gør hele gule string 0'er bortset fra den smule, jeg ønsker at ændre og så vil jeg introducere en ny operatør kendt som en bitvis operatør - bitvise i den forstand, at den fungerer på enkelte bits, ikke på en hel byte eller fire bytes på én gang. Denne lodrette streg der i gul antyder, at det, hvis vi tager repræsentationen af ​​kapital A og bitvist OR den med den gule sekvens af bits? Med andre ord tilbage tænke på vores diskussion af boolske udtryk i Scratch og derefter i C. Gør en boolesk eller betyder, at for at være sandt, enten den første ting er at være sandt eller den anden ting er at være sandt, eller de begge har til at være sandt, og derefter blev den resulterende output er selv sandt. I dette tilfælde her, hvad vi får, hvis vi tager 0 "eller" ed med 0? Urigtige eller falsk? Det er stadig forkert, så det lille en fortsat som forventet. Hvad hvis vi i stedet gøre 1 eller 0? Det er nu op 1, men bemærk, hvad der er ved at ske her. Hvis vi starter med stort A, og vi fortsætter med at "eller" de enkelte bits, som vi laver her, 0 eller den gule giver os, hvad hernede? Det giver os 1. Faktisk formoder, at vi ikke vidste, hvad det store version af lidt et faktisk var. Lad os gå gøre dette. Lad mig flytte det tilbage herovre. Lad os gøre det igen. 0 eller 0 giver mig 0. 1 eller 0 giver mig 1. 0 eller 1 giver mig 1. 0 eller 0 giver mig 0. Det næste er 0, den næste er 0, den næste er 0. 1 eller 0 giver mig 1. Og så selv om vi ikke vidste på forhånd, hvad små bogstaver et var, blot ved "eller" ing A med dette mønster af bits, som vi har præsenteret her i gult, du kan småbogstaver en kapital A ved at vende den smule. Vi brugte dette udtryk uger siden: flippe en smule. Hvordan kan du faktisk gøre det programmatisk? Du bruger hvad der generelt kaldes en maske, en sekvens af bits, at i dette tilfælde bare så sker for at ligne dette nummer her, og så skal du "eller" det sammen med denne nye C-operatør, ikke | |, du bruger en enkelt | og du vil faktisk få dette svar her, fordi hvorfor? Dette er det 1s sted, 2s sted, 4S, 8S, 16s, 32s. Så viser det sig, at hvis du tager et stort bogstav A og bitvise ELLER det med tal 32, fordi det tal 32, når man ser på det som bits ser sådan ud, det betyder at du kan vende bit at du rent faktisk ønsker. Og på samme måde - og vi vil se på koden på bare et øjeblik - formoder vi ønsker at gå den anden vej. Hvordan kan du gå fra små en til kapital A? Hvilken bit skal ændres? Det er den samme. Vi ønsker at ændre dette tredje bit fra en 1 til en 0. Og hvordan kan vi gå om at gøre dette? Hvordan får vi slukker en smule? Med hvilken mønster af bits kunne vi slukke en smule? Hvad hvis vi sorterer af invertsukker masken? Hvor der før gjorde vi det hele gule maske 0'er undtagen for én bit vi ønskede at tænde, hvad nu hvis denne gang gør vi det hele maske 1s undtagen for lidt, at vi ønsker at slukke og derefter bruge hvilken operatør? Hvad hvis vi "og" ting? Lad os tage et kig. Hvis vi nu vende til dette, formoder, at jeg igen oprette en maske, der er alt 1s bortset fra den smule, jeg vil slå og derefter snarere end "eller" de hvide tal op øverst med de gule tal hernede, hvad nu hvis jeg i stedet "og" dem sammen? Det kaldes en bitvise og. Logisk set er det samme som en Boolesk og. Dette giver mig 0 & 1 er 0. Så falsk og sandt, er falsk. True og sandt, er sandt. Og her er det magiske: sandt og falsk er nu forkert, så vi har slukket den smule. Og nu resten af ​​historien er noget ligetil. Da resten af ​​masken er 1s, er det ligegyldigt, hvad tallene er i hvid. Når du "og" noget med sand, er du ikke kommer til at ændre værdien. Hvis det er sandt, vil det fortsat være sandt. Hvis det var falsk, vil den forblive falsk. Men magien opstår, når du tager noget, der var sandt og du derefter "og" det med falsk. Dette har den virkning at slukke denne bit. Så lidt kryptisk dér. Lad os faktisk se på noget kode, der kan faktisk se endnu mere kryptisk, men lad os tage et kig her på tolower. Hvis jeg ser på tolower, der går fra kapital A til små bogstaver a, lad os se, hvordan vi kan gennemføre dette program. Her er vigtigste, og det er ikke at tage nogen kommandolinjeargumenter. Jeg erklære et tegn c for det brev, som brugeren kommer til at skrive i. Jeg så bruge en velkendt do while-løkke blot at sørge for, at brugeren absolut giver mig et stort A eller B eller C. .. Z, så de giver mig noget mellem A og Z. Og nu, hvad laver jeg her? Jeg "eller" ING dette med 0x20, men det er faktisk det samme som - og vi vil vende tilbage til dette om et øjeblik - 32. Så igen, 32 er dette mønster af bits her. Hvorfor ved vi det? Bare tænk tilbage til uge 0. Dette er det 1s sted, 2s sted, 4S, 8S, 16s, 32s sted. Så denne gule tal sker for at være 32. Jeg kan derefter tage et brev som den char her, bitvis "eller" det med bogstaveligt nummer 32, og hvad får jeg tilbage? Den lille version af denne char. For et øjeblik siden, selv om, jeg gav udtryk for dette i en anden base notation. Hvad har det repræsenterer? >> [Studerende] Hexadecimal. [Malan] Dette sker for at repræsentere hexadecimal. Vi har ikke talt om hexadecimal så meget, men det er faktisk praktisk i sager som denne. Selvom det ser mere kompliceret og selvom det ser ud som 20 og ikke 32, Det viser sig, at hexadecimal er faktisk super praktisk notation fordi i hexadecimal hver ciffer efter 0x - og det betyder ikke noget; dette er blot menneskelig konvention, der siger her kommer et hexadecimalt tal - hver af disse cifre, 2 og derefter i 0, kan selv være repræsenteret med præcis 4 bits. Så hvis vi gør det, så lad mig åbne en teksteditor her - weird autofuldførelse - hvis vi gør en lille tekst editor her er antallet 0x20 betyder her er 4 bits, her er en anden 4 bits. Lad os gøre det yderst til højre 4 bit først. 0 når repræsenteret med 4 bits er hvad? Super let. Bare 0'er. Så 4 bit som 0'er. Hvordan kan du repræsenterer 2? Det er et stykke tid siden, vi gjorde dette, men det er 0100. Så dette er det 1s sted, er det 2s sted, og så er det ligegyldigt, hvad de andre steder er. Med andre ord, du i hexadecimal kan sige 0x20, men hvis du så tænke på, hvad er de 2 og hvordan er det repræsenteret i binær, hvad er 0, og hvordan er det repræsenteret i binær, svarene på disse spørgsmål er det og det, hhv. Så 0x20 sker for at repræsentere dette mønster på 8 bits, hvilket netop er maske, som vi ønskede. Så det er i øjeblikket blot en intellektuel øvelse, men virkeligheden er i kode, det er typisk mere almindeligt at skrive konstanter som denne i hexadecimal fordi så programmøren kan relativt nemt, selv om det kræver en vis papir og blyant, finde ud af hvad dette mønster af bits er fordi du ikke bare kan udtrykke 0'er og 1-taller typisk i kode. Du kan ikke gå 00.010 og så videre. Du er nødt til at vælge decimaler eller hexadecimal eller oktal eller andre notationer. De fleste mennesker har en tendens til at plukke hexadecimal simpelthen så hvert ciffer repræsenterer 4 bit og du kan gøre dette hurtigt math. Og jeg vil vinke min hånd på toupper, hvilket er næsten det samme, det ser næsten identiske. Toupper sker ikke at anvende eller operatøren, men snarere denne fyr og df. Hvad betyder df repræsenterer? df? Anyone? >> [Studerende] 255. 255? Ikke 255. Det ville være ff. Vi vil forlade denne ene som en lille øvelse. Men hvis du går fra 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 og derefter hvad der kommer efter 9? Vi er slags ud af decimaler, men i hexadecimal hvad der kommer efter 9? [Studerende] a. >> Så a, b, c, d. Du kan regne ud derfra hvad mønster af bits d faktisk repræsenterer. Og hvis vi gør det math, vil vi se, at den maske, du ender med at komme tilbage er identisk med denne. Dette er f, 1-taller, og det er d. Så df repræsenterer den maske. Ok. Og endelig ikke at gøre tingene lyd super, super teknisk, men formoder, at vi ønskede at skrive et program, der gør dette. Lad mig gå videre og gøre binær, som er et program i en fil kaldet binary.c. Og lad mig køre binære og give mig et ikke-negativt heltal. Lad os starte let og skrive 0. Dette er nu et program, der udskriver et heltal i sin binær repræsentation. Så hvis jeg spiller dette spil igen og skrive på bare 1, bør jeg få en 32-bit repræsentation af 1. Hvis jeg gør det igen med 2, bør jeg få det. Hvis jeg gør 7, bør jeg få et par 1s i slutningen og så videre. Det viser sig, jeg nævner dette, fordi med bitvise operationer du kan faktisk gøre en anden ting så godt. Du kan oprette disse masker dynamisk. Tag et kig på denne ene sidste eksempel involverer bitvise operationer. Her er den første del af koden, bede brugeren om et tal, og det insisterer på, at du giver mig et ikke-negativt heltal. Så det er slags gamle skole ting. Men her er noget, der er lidt interessant. Hvordan går jeg om udskrivning af et nummer i binær? Jeg først iterere fra hvad til hvad? Hvad er størrelsen af ​​en int typisk i det mindste i apparatet? >> [Studerende] 4. Det er 4. Så 4 * 8 er 32 - 1 er 31. Så hvis jeg begynder at tælle fra 31, der repræsenterer, viser det sig, bare begrebsmæssigt, det 31. bit eller den højeste orden bit, hvilket er denne fyr herovre, dette vil være bit 0. Så dette er bit 01 ... bit 31. Så hvad er denne kode gør? Bemærk dette for-løkke, selvom det ser kryptisk, er bare iteration fra 31 ned til 0. Det er det. Så det interessante del nu skal være i disse 5 linier her. Bemærk, at i denne linje, jeg erklære en variabel kaldet maske at være i overensstemmelse med vores historie om disse gule numre. Og hvad er dette gør? Dette er en anden bitvis operatør har vi ikke set før, mest sandsynlige. Det er den venstre shift operatør. Denne operator gør dette. Her er nummer 1, og hvis du gør jeg forlod skift, venstre skift, hvad tror du, der har den virkning at gøre den pågældende person 1? Bogstaveligt talt flytte det over. Så hvis nummer 1 er, hvad du har på venstre og du starter med at initialisere i til 31, hvad der er at gøre? Det kommer til at tage dette nummer 1 og flytte det 31 pladser herovre. Og fordi der er naturligvis ingen andre cifre bag det, de vil som standard blive erstattet med 0'er. Så du vil starte ud med nummer 1, hvilket naturligvis ligner dette - og lad mig trække det over her i midten. Og derefter som du skifter tingene til venstre, denne fyr hovedsageligt går på denne måde. Men så snart du gør det, bliver et 0 udfyldt Hvis du skifter det en anden gang, det går på denne måde, og en anden 0 bliver fyldt i. Du flytter det igen og derefter en anden 0 bliver fyldt i. Så hvis du gør denne ting på 1 << I 31 steder, du ender med at få en maske der er 32 karakterer, den yderste venstre ene er et 1, hele resten af ​​dem er et 0. Og det viser sig, som en sidebemærkning, at flytte et nummer til venstre på denne måde også tilfældigt og undertiden bekvemt, har den virkning, at gøre hvad til dette nummer? >> [Studerende] Fordobling det. Fordobling det, fordi hver af søjlerne - det 1s sted, 2s sted, 4s sted, 8s sted, 16s sted - de er alle fordobling som du går til venstre. Eller rettere, når du flytter 1s du vil ende med at fordoble værdien af ​​nummeret. Du kan ende med at gøre interessante transformationer af cifre ved at flytte alt over på denne måde ved potenser af 2. Så hvordan fungerer det? Dette giver så mig en maske, der er 0'er undtagen for en 1 i netop det sted, jeg vil have det, og så dette udtryk, som er stjålet fra toupper.c, er simpelthen at sige tage antallet n at brugeren indtaster, "Og" det med den maske, og hvad vil du få? Du kommer til at få en 1, hvis der er et 1 i denne maskerede sted, eller du kommer til at få et 0, hvis der ikke er. Og så alt dette program er effektivt, er det har en løkke, og det skaber en maske med en 1 herovre, så en 1 herovre, så en 1 herovre, og det bruger denne bitvise OG trick at sige, er der en 1 bit i brugerens input her? Er der en 1 bit i brugerens input her? Og hvis ja, udskrive bogstaveligt 1, ellers udskrives 0. Vi gør dette med int'er bare fordi det er derfor, vi laver 32 bit i stedet for 8, men hvad vi har introduceret så er det bitvise OG, denne bitvis OR, og denne venstre skift operatør, som ikke ofte frygtelig nyttige, men det viser sig at de kan være. I virkeligheden, hvis du skulle repræsentere noget som en vifte af Booleans bare for at repræsentere sandt eller falsk, antage, at du ønskede at holde styr på, om eller ej et rum fuld af 300 studerende er til stede, du kunne erklære en vifte af størrelsen 300 af typen bool, så du får 300 bools, og du kan indstille hver til sand, hvis nogen er her og falsk ellers. Hvorfor er det repræsentation i denne datastruktur ineffektiv? Hvad er dårligt om udformningen af ​​denne datastruktur, en vifte af 300 bools? Hvad er en bool, faktisk under hætten? Også dette er noget, der måske ikke være bekendt. Det viser sig, der ikke er bool. Husk vi slags skabt, med den cs50.h fil, som selv indeholder standard bool. C er en slags dum, selv om, når det kommer til bool. Den bruger 8 bit til at repræsentere hver bool, som er helt uøkonomisk fordi selvfølgelig, hvor mange bits du har brug for at repræsentere en bool? Bare 1. Så viser det sig, at hvis du har nu mulighed for med bitvise operatører at manipulere de enkelte bits selv i en char, selv i en enkelt byte, det viser sig, du kunne reducere den hukommelse, der kræves for at repræsentere noget dumt sådan deltagelse stylet datastruktur med en faktor på 8. I stedet for at bruge otte bits til at repræsentere sandt eller falsk, kan du bogstaveligt talt bruge en ved hjælp af en enkelt byte for hver otte elever i klassen og skifte fra 0 til 1 individuelle bits ved hjælp af disse former for lavt niveau tricks. Det er virkelig sat en stopper for energien. Er der nogen spørgsmål om bitvise operationer? Yeah. >> [Studerende] Er der en eksklusiv eller operatør? Ja. Der er en eksklusiv eller operatør, der ligner denne, ^, gulerod symbol, hvilket betyder, at kun den første ting eller den anden ting kan være en 1 til den produktion, at være en 1. Der er også en ikke, ~, som vil tillade dig at invertere en 0 til en 1 eller vice versa samt. Og der er også en ret skift operatør, >>, hvilket er det modsatte af det, vi så. Ok. Lad os tage tingene nu til et højere niveau. Vi startede med at tale om tekst og derefter komprimere det og repræsenterer teksten med færre antal bits; Vi snakkede lidt om, hvordan vi kan nu begynde at manipulere tingene på en bitvis niveau. Lad os nu ind igen op 10.000 fod til repræsentation af mere komplekse ting som grafik. Her har vi en tysk flag, her har vi en af ​​Frankrig. Disse kan være repræsenteret i filformater, du måske kender - GIF'er, for eksempel. Hvis du nogensinde har set et billede på nettet, som ender med. Gif, dette er en Graphics Interchange Format. Disse to flag her slags egner sig til kompression for hvad måske indlysende grund? >> [Uhørlig student svar] Der er en del gentagelser, right? For at sende Tysklands flag, så tænk på dette som et billede på skærmen tilbage i dine Scratch dage. Du husker muligvis, at der er enkelte pixel eller punkter, der udgør et billede. Der er en hel række af sorte prikker og en anden hel række af sorte prikker. Der er en masse af rækker af sorte prikker, som vi kunne se, om vi virkelig er zoomet ind, meget gerne, når vi zoomet ind på Rob ansigt i Photoshop. Så snart vi fik dybere og dybere og dybere ind i billedet, De begyndte at se pixelering, alle de firkanter, der består hans øje i denne sag. Samme deal her. Hvis vi zoomede ind ganske lidt, ville du se de enkelte prikker. Nå, det er sådan et spild af bits. Hvis en tredjedel af flag er sort, og en tredjedel af flag er gul og så videre, hvorfor kan vi ikke en eller anden måde komprimere dette flag? Og selv det franske flag kan komprimeres selvom mønsteret er en lille smule anderledes. Det viser sig, GIF-filformatet er et tabsfrit komprimeringsformat, hvilket betyder, at du kan tage et billede som det tyske flag her, du kan smide en masse af sine bits uden kompromis med kvaliteten. Dette er i modsætning til noget som JPEG, med de fleste af os er nok mere kendt. Facebook fotos og Flickr-billeder og lignende er næsten altid gemt som JPEG, når de er uploadet, men JPEG-billeder er en lossy - lossy - format, hvor du kan smide bits men du også smide kvalitet. Og så hvis du komprimere billeder med Photoshop eller uploade dem til Facebook eller tage dem på en virkelig crappy telefon, du ved, at billedet begynder at blive meget klattet og pixeleret, og det er fordi det bliver komprimeret af den computer eller telefon ved bogstaveligt at smide information væk. Men GIF er forbløffende i, at det kan bruge færre bits end det måske som standard uden at miste nogen oplysninger. Og det væsentlige gør det som følger. Snarere end butikken i en fil som en BMP ville en RGB tredobbelt for sort, sort, sort, sort, sort, sort, sort, sort, sort, sort, sort, sort og så videre, snarere er GIF-format vil sige, "Black" og derefter, "Gentag dette 100 gange," eller noget lignende. "Black, gentage dette 100 gange, sort, gentage dette 100 gange ..." "Yellow, gentage dette 100 gange." Og sådan husker det væsentlige den venstre pixel og derefter koder eller anden måde ideen om at gentage, at pixel igen og igen. Så GIF kan derefter komprimere sig selv uden at miste nogen oplysninger. Men hvis du var nødt til at gætte, hvis det er den algoritme, gifs brug, hvilke af disse flag, selvom de ser identiske i størrelse, vil være mindre, når de gemmes på harddisken, som et GIF? >> [Studerende] Tyskland. Tyskland bliver mindre? Hvorfor? [Studerende] Fordi du gentager det mange, mange gange vandret og så skal du gentage en anden gang. >> Præcis. Fordi de mennesker, der opfandt GIF bare lidt vilkårligt besluttet at gentagelsen skal understøttes horisontalt og ikke sideværts. Der er meget mere gentagelse lateralt her i det tyske flag end i den franske flag. Så hvis vi rent faktisk åbner en mappe på min harddisk, der har disse GIF, du kan faktisk se, at det tyske flag her er 2 kilobyte og den franske er 4 kilobytes. Det sker for at være en tilfældighed, at man er to gange den anden, men det er faktisk sådan, at den franske flag er meget større. Selvom vi taler her om grafik, kan de samme ideer for ikke ting som flag, men billeder, der er lidt mere kompliceret. Hvis du tager et billede af et æble, så mon der ikke er en masse dobbeltarbejde der, så vi kunne eller anden måde huske, at standard baggrunden er blå og ikke, som det højre billede antyder, skal huske farven på hver enkelt pixel i dette billede. Så vi kan smide bits væk der uden at miste information. Æblet ser stadig bare det samme. I dette eksempel her, kan du se, hvad der sker i en film. Disse repræsenterer old-school filmspoler hvorved i det øverste billede der du har en RV kørsel forbi et hus og et træ. Og som van kører forbi fra venstre til højre, hvad naturligvis ikke ændre? Huset er ikke går nogen steder, og træet er ikke går nogen steder. Det eneste, der bevæger er van i denne sag. Så som Background Uændret antyder, hvad du kan gøre i film er ligeledes bare smide oplysninger, der ikke ændre sig i mellem rammer. Dette er almindeligt kendt som interframe komprimering idet såfremt denne ramme ser næsten identisk med denne, lad os ikke gider lagring på disk nogen af ​​de samme oplysninger på disse mellemliggende frames, lad os kun bruge klippunkter en gang imellem der rent faktisk gemmer disse oplysninger redundant bare som en lille tilregnelighed check. Derimod er en anden metode til komprimering af video i denne anden og lavere eksempel her, hvor stedet butik 30 billeder, hvorfor du ikke bare gemme 15 billeder i sekundet i stedet? Snarere end filmen slags flyder smukt, perfekt, det kan se ud som det er stammen en lille smule, lidt gamle skole, men nettoeffekten vil være at bruge langt færre bits end ellers ville være nødvendigt. Så hvor kommer denne derefter forlade os? Det var lidt af en sidebemærkning om, hvor du ellers kan gå med kompression. For mere om dette, tage en klasse som CS175 her. Her er et andet eksempel på video. Hvis bi er det eneste bevægelse, du kan virkelig smide oplysninger i disse midterste frames fordi blomsten og himmel og blade ikke ændrer sig. Men lad os nu overveje en sidste ting. I de næste 5 minutter vi forlader C bag evigt i forelæsning? Ja. Ikke i psets, selvom. Sidste historie om C og så kommer vi til meget sexet ting involverer HTML og web-og woo-hoo. Ok. Her går vi. Det er motivationen. Det viser sig, al denne tid, hvor vi har skrevet programmer, vi kører Dunk. Og Dunk, vi har sagt, siden den første uge temmelig meget, tager kildekode og omdanner den til objekt kode. Det tager C og omdanner den til 0'er og 1'ere. Jeg har slags løjet for dig for et par uger, fordi det ikke er helt så simpelt er det. Der er meget mere foregår under kølerhjelmen, når du kører et program som Dunk. Faktisk kan processen med at udarbejde et program virkelig kan sammenfattes, som du måske husker fra Robs video på compilere, ind i disse 4 trin: forbehandling, kompilere selv, samling, og sammenkædning. Men vi i klassen, og de fleste mennesker i verden typisk sammenfatte alle disse trin som bare "kompilering". Men hvis vi starter med kildekode som denne, huske dette er måske den enkleste C-programmet vi har skrevet hidtil, huske at når kompileret det ender med at ligne dette. Men der er faktisk et mellemliggende skridt, og disse skridt er som følger. Først er der denne ting på toppen af ​​dette og de fleste af vores programmer, # Include Hvad betyder # include gøre for os? Det temmelig meget kopier og Indsætter indholdet af stdio.h ind i min fil, så hvorfor? Hvorfor bryder jeg mig om indholdet af stdio.h? Hvad er der derinde af interesse? Printf erklæring, dets prototype, så compileren så ved hvad jeg mener når jeg nævner denne funktion printf. Så trin 1 under udarbejdelse, er forbehandling, hvorved et program som Dunk eller nogle helper program, der Dunk kommer med læser din kode top til bund, venstre mod højre, og når som helst det ser en # symbol efterfulgt af et søgeord som omfatter, det udfører denne operation, kopiere og indsætte i dette tilfælde stdio.h ind i din fil. Det er trin 1. Så har du en meget større C-fil på grund af den enorme kopiere, indsætte job, der er bare sket. Trin 2 nu kompilering. Men det viser sig kompilere tager kilde kode, der ser sådan her ud og forvandler det til noget, der ligner denne, som for dem, der kender hedder? >> [Studerende] forsamling. >> Assembly sprog. Dette er faktisk noget, hvis du tager CS61 du dykke ned i flere detaljer. Det er omtrent lige så tæt som du kan komme til at skrive 0'er og 1'ere selv men skrive tingene på en sådan måde, at der stadig gør mindst en lille smule fornuft. Disse er maskininstruktioner, og hvis vi rulle ned til den vigtigste funktion her, bemærke, at der er denne push-instruktion, flytte undervisning, trække instruktion, call instruktion og så videre. Når du hører, at din computer har Intel indeni, du har en Intel CPU i din Mac eller pc, hvad betyder det? En CPU kommer bygget af selskaber som Intel forståelse visse instruktioner. De har ingen idé om, hvad funktioner som swap er eller hoved, er per se, men de ved, hvad meget lavt niveau instruktioner som lægge sammen, trække, skubbe, flytte, ring, og så videre er. Så når du kompilerer C kode i assembler, Deres meget brugervenlig udseende kode omdannes til noget, der ligner denne, der bogstaveligt talt bevæger byte eller 4 byte rundt i så små enheder i og ud af CPU'en. Men til sidst, når Dunk er klar til at tage denne repræsentation af dit program i 0'er og 1-taller, så trinnet kaldet samling sker, og dette igen hele sker i løbet af et øjeblik, når du kører Dunk. Vi starter her, det udlæser en fil som dette, og så er det konverterer det til disse 0'er og 1'ere. Og hvis du vil gå tilbage på et tidspunkt og faktisk se det i aktion, hvis jeg går ind i hello1.c--dette er et af de allerførste programmer vi kiggede på - normalt ville vi kompilere dette med Dunk hello1.c og dette ville give os a.out. Hvis derimod du i stedet give det-S flag, hvad du får, er hello1.s og du vil faktisk se assembler. Jeg gør dette for en meget kort program, men hvis du går tilbage til Scramble eller Recover eller ethvert program, du har skrevet, og lige ud af nysgerrighed ønsker at se, hvad det egentlig ser ud, hvad der rent faktisk bliver ført ind i CPU, kan du bruge det-S flag med Dunk. Men så endelig, er der stadig en Gotcha. Her er de 0'er og 1-taller, der repræsenterer min implementering af hej, verden. Men jeg brugte en andens funktion i mit program. Så selvom processen har været Jeg tager hello.c, det bliver samlet i montage kode og derefter det bliver samlet i 0'er og 1-taller, det eneste 0'er og 1-taller, der udsendes på nuværende tidspunkt er dem, der skyldes min kode. Men den person, der skrev printf, de kompileret deres kode for 20 år siden og det er nu installeret et eller andet sted på apparatet, så vi på en måde nødt til at fusionere hans eller hendes 0'er og 1-taller med min 0'er og 1'ere, og det bringer os til den 4. og sidste trin i kompilering, kendt som forbinder. Så på den venstre side har vi præcis samme billede som før: hello.c bliver forsamling kode bliver 0'er og 1'ere. Men husker, at jeg brugte den standard I / O-bibliotek i min kode, og det betyder et eller andet sted på computeren er der en fil kaldet stdio.c eller i det mindste den kompilerede udgave, fordi nogen nogle år siden kompileret stdio.c i montage kode og derefter en hel masse 0'er og 1'ere. Dette er, hvad der er kendt som en statisk eller en dynamisk bibliotek. Det er nogle fil sidder et eller andet sted i apparatet. Men endelig, jeg er nødt til at tage min 0'er og 1-taller, og den pågældende persons 0'er og 1'ere og på en måde linke dem sammen, bogstaveligt kombinere de 0'er og 1'ere i en enkelt fil kaldet a.out eller hello1 eller hvad jeg kaldte mit program således at det endelige resultat har alle de 1s og 0'erne, der skal komponere mit program. Så al den tid dette semester, hvor du har brugt Dunk og endnu mere for nyligt kørende gøre for at køre Dunk, alle disse trin er sket slags øjeblikkeligt, men meget bevidst. Og så hvis du fortsætter i datalogi, nemlig CS61, dette er det lag, som du vil fortsætte med at skrælle tilbage off der taler om effektivitet, sikkerhedsmæssige konsekvenser og lignende af disse lavere niveauer detaljer. Men med det, er vi ved at forlade C bagefter. Lad os gå videre og tage vores 5-minutters pause nu, og når vi kommer tilbage: Internettet. Ok. Vi er tilbage. Nu begynder vi vores udseende ikke bare på HTML, for som du vil se, HTML selv er faktisk temmelig simpel men virkelig ved webprogrammering mere generelt, networking mere generelt, og hvordan alle disse teknologier mødes at tillade os at skabe langt mere sofistikerede programmer oven på Internettet end hidtil har vi været i stand til i disse sorte og hvide vinduer. Faktisk på dette tidspunkt i det semester, selvom vi bruger relativt mindre tid på PHP, HTML, CSS, JavaScript, SQL og mere, de fleste studerende ender med at gøre de endelige projekter, der er web-baseret fordi, som du vil se, baggrunden du nu har i C er meget for disse højere niveau sprog. Og når du begynder at tænke over dit afsluttende projekt, der, ligesom Problem Set 0, du hvor blev opfordret at gøre de fleste noget af interesse for dig i Scratch, det endelige projekt er din mulighed for at tage din nyfundne viden og kyndige med C eller PHP eller JavaScript eller lignende ud for et spin og skabe din helt egen stykke software for verden at se. Og til frø dig med ideer, ved, at du kan gå her, projects.cs50.net. Hvert år har vi hverve ideer fra fakulteter og personale og grupper af studerende på campus bare for at indsende deres ideer til interessante ting, der kunne løses ved hjælp af computere, brug af websteder, ved hjælp af software. Så hvis du kæmper for at komme op med en idé om din egen, med alle midler rulle gennem de ideer der fra i år og sidste. Det er helt okay at tackle et projekt, der er blevet løst før. Vi har set mange apps for at se status for vasketøj på campus, mange apps til navigation i spisesal menuen mange apps til navigation i Kursuskataloget og lignende. Og ja, i en kommende foredrag og i fremtidige seminarer, vi vil introducere dig til nogle offentligt tilgængelige API'er, både kommercielt tilgængelige såvel som her fås fra CS50 på campus, så du har adgang til data og kan derefter gøre interessante ting med det. Så mere om afgangsprojekter i et par dage, når vi slipper specifikationen, men for nu, ved, at du kan arbejde solo eller med en eller to venner på de fleste helst projekt af interesse for dig. Internettet. Du gå videre og trække sig ud din bærbare computer, skal du gå til facebook.com for første gang, ikke har logget på for nylig, og tryk på Enter. Hvad der præcist sker? Når du trykker på Enter på din computer, en hel bunke af trin begynde slags magisk sker. Så du her til venstre, web server som Facebook er her til højre, og på en måde du bruger dette sprog kaldet HTTP, Hypertext Transfer Protocol. HTTP er ikke et programmeringssprog. Det er mere af en protokol. Det er et sæt af konventioner, som webbrowsere og webservere bruger, når indbyrdes forbundne. Og hvad det betyder er som følger. Meget gerne i den virkelige verden, har vi disse konventioner hvor, hvis du møde nogle mennesker for første gang, hvis du ikke har noget imod humoring mig her, Jeg kan komme op til dig, siger: "Hej, mit navn er David." >> Hej, David. Mit navn er Sammy. "Hej, David. Mit navn er Sammy." Så nu har vi netop involveret i denne form for fjollet menneskelig protokol hvor jeg har indledt protokollen, har Sammy reageret, vi har rystet hænder, og transaktionen er gennemført. HTTP er meget ens i ånden. Når din web browser anmoder www.facebook.com, hvad din browser er virkelig gør, er at udvide sin hånd, så at sige, til serveren, og det er at sende det en meddelelse. Og det budskab er typisk noget som få - hvad gør du ønsker at få? - få mig hjemmesiden, som typisk betegnes med en enkelt skråstreg i slutningen af ​​en webadresse. Og bare så du ved, hvad sprog jeg taler, jeg browseren vil fortælle dig at jeg taler HTTP version 1,1, Og også for god foranstaltning, vil jeg fortælle dig, at værten, at jeg ønsker hjemmesiden for er facebook.com. Typisk en webbrowser, ukendt for dig, det menneskelige, sender dette budskab via internettet, når du blot skrive www.facebook.com, At indgå i din browser. Og hvad betyder Facebook reagere med? Den reagerer med nogle lignende udseende kryptiske detaljer, men også meget mere. Lad mig gå videre til Facebook hjemmeside her. Dette er skærmen som de fleste af os sandsynligvis aldrig se, hvis du forblive logget ind hele tiden, men dette er faktisk deres hjemmeside. Hvis vi gør det i Chrome, bemærke, at du kan trække op disse små kontekstmenuer. Ved hjælp af Chrome, uanset om Mac OS, Windows, Linux eller lignende, hvis du styre klik eller venstre klik, kan du typisk trække op en menu, der ser sådan ud, hvor et par muligheder afvente, hvoraf den ene er View Page Source. Du kan også typisk komme til disse ting ved at gå til menuen Vis og rode rundt. For eksempel, her under Vis Developer er det samme. Jeg har tænkt mig at gå videre og se på View Page Source. Hvad du ser, er den HTML, som Mark har skrevet at repræsentere facebook.com. Det er en komplet rod her, men vi vil se, at det gør lidt mere mening inden længe. Men der er nogle mønstre her. Lad mig scroll ned til ting som dette. Det er svært for et menneske at læse, men bemærker, at der er dette mønster af vinklede beslag med nøgleord som option, søgeord som værdi, nogle citerede strenge. Det er her, da du tilmeldte dig for allerførste gang, specificeret, hvad dit fødselsår er. Denne drop-down menu med årgange eller anden måde er kodet her på dette sprog kaldet HTML, HyperText Markup Language. Med andre ord, når din browser anmoder om en webside det taler denne konvention kaldet HTTP. Men hvad betyder facebook.com svaret på denne opfordring med? Den reagerer med nogle af disse kryptiske beskeder, som vi vil se i et øjeblik. Men de fleste af dens reaktion er i form af HTML, HyperText Markup Language. Det er den faktiske sprog, som en webside er skrevet. Og hvad en webbrowser virkelig så er, ved modtagelsen af ​​noget, der ligner denne, læser det top til bund, venstre til højre, og når som helst det ser en af ​​disse vinklede beslag efterfulgt af et søgeord som option, viser, at kodesprog på passende måde. I dette tilfælde ville det vise en drop-down menu år. Men igen, dette er en komplet rod at se på. Det er ikke fordi Facebook udviklere manifestere 0 for 5 for stil, for eksempel. Dette er fordi de fleste af den kode, de skriver, er i virkeligheden skrevet smukt, kommenteret, pænt indrykket, og lignende, men selvfølgelig maskiner, computere, browsere virkelig ikke en døjt om din kode er godt stylet. Og i virkeligheden er det fuldstændig spild at ramme tabulatortasten alle de gange og til at sætte kommentarer alle i hele din kode og til at vælge virkelig beskrivende variabelnavne fordi hvis browseren er ligeglad, alt hvad du laver i slutningen af ​​dagen spilde bytes. Så viser det sig, hvad de fleste hjemmesider gør, er, selv om kildekoden til facebook.com, for cs50.net og alle disse andre hjemmesider på internettet typisk velskrevet og godt kommenteret og pænt indrykket og lignende, typisk før hjemmesiden er sat på internettet, er koden minified, hvorved HTML og CSS - noget andet, vi vil snart se - JavaScript-kode, vi snart får at se er komprimeret, hvorved lange variabelnavne bliver X-og Y og Z, og alt dette blanke, der gør alting ser så læsbar er alle smidt væk, fordi hvis du tænker over det på denne måde, Facebook får en milliard side hits om dagen - noget vanvittigt sådan - og hvad så hvis en programmør bare for at være anal tryk på mellemrumstasten en ekstra gang bare for at indrykke nogle kodelinje nogensinde så meget mere? Hvad er konsekvenserne, hvis Facebook bevarer at whitespace i alle de bytes, de sender tilbage til folk på internettet? Rammer den plads bar engang giver dig en ekstra byte i din fil. Og hvis en milliard mennesker derefter gå til at downloade hjemmesiden den dag, hvor meget mere data har du sendes over internettet? En gigabyte uden god grund. Og indrømmet, for en masse hjemmesider dette er ikke sådan en skalerbar emne, men for Facebook, Google, for nogle af de mest populære hjemmesider Der er stort incitament økonomisk for at gøre din kode til at ligne en rod så at du bruger så få bytes som muligt udover derefter komprimere det bruge noget lignende lynlås, en algoritme kaldet gzip, at browseren gør for dig automatisk. Men det er forfærdelige. Vi vil aldrig lære noget om andre folks hjemmesider og hvordan man designer websider hvis vi er nødt til at se på det på denne måde. Så heldigvis, browsere som Chrome og IE og Firefox disse dage typisk kommer med indbygget udviklerværktøjer. Faktisk, jeg hvis jeg går ned her til Inspect Element, eller hvis gå til Vis, Developer og gå til Developer Tools eksplicit, dette vindue nederst på min skærm nu popper op. Det er lidt skræmmende i starten, fordi der er en masse ukendte faner her, men hvis jeg klikker på Elements hele vejen nederst til venstre, Chrome er naturligvis temmelig smart. Den ved, hvordan man skal fortolke alt dette kodeks. Og så hvad Chrome gør, er det renser op alle Facebooks HTML. Selv om der ikke er whitespace der, der er ikke indrykning der, nu mærke til, at jeg kan begynde at navigere denne webside desto mere hierarkisk. Det viser sig, at hver webside skrevet i et sprog, der kaldes HTML5 bør begynde med dette, denne DOCTYPE erklæring, så at sige: Det er slags lys og grå der, men det er den allerførste linje kode i denne fil, og at kun fortæller browseren, "Hey, her kommer nogle HTML5. Her kommer en webside." Den første åbne beslag ud over hvad der sker for at være den ting, en åben konsol HTML-tag, og derefter, hvis jeg dykke dybere - disse pile er helt meningsløs; de er bare for præsentation skyld, er de faktisk ikke i filen - bemærke, at indersiden af ​​Facebooks HTML-kode, noget, der starter med en åben konsol og derefter har et ord kaldes en tag. Så inde i HTML-tag er tilsyneladende et hoved-tag og et organ tag. Inde i hovedet tag nu er en hel rod for Facebook fordi de har en masse metadata og andre ting til markedsføring og reklame. Men hvis vi rulle ned, ned, ned, ned, lad os se hvor det er. Her er det. Denne her er i det mindste lidt fortrolig. Titlen på Facebook hjemmeside, hvis du nogensinde ser i fanen i din titel bar, er Velkommen til Facebook - log ind, tilmeld dig eller få mere. Det er, hvad du vil se i Chrome titellinje, og det er, hvordan det er repræsenteret i kode. Hvis vi ignorerer alt andet i hovedet, de fleste af tarme af en webside er i kroppen, og det viser sig, at Facebooks kodeks kommer til at se mere kompleks end de fleste ting, vi vil skrive i første omgang bare fordi det er blevet bygget op gennem årene, men der er en hel masse scripttags, JavaScript-kode, der gør hjemmesiden meget interaktiv: se statusopdateringer øjeblikkeligt ved hjælp af sprog som JavaScript. Der er noget, der hedder en div, som er en division af en side. Men før vi kommer til at detalje, lad os prøve at zoome ud og se på en enklere version af Facebook 1,0, så at sige. Her er det hej, verden af ​​websider. Det har at DOCTYPE erklæring øverst som er lidt anderledes end alt andet. Intet andet, vi skriver på en webside kommer til at starte med for fed. Igen, historien er den samme: hej, komma, begynde at gøre denne dristige, så verden bliver fremhævet med fed skrift, og det betyder stoppe udskrivning dette med fed skrift. Lad mig gå videre og redde min fil, skal du gå tilbage til Chrome, vil jeg zoome ind bare så vi kan se det bedre, og genindlæs, og du vil se, at verden er nu med fed skrift. Web handler om hyperlinks, så lad os gå videre og gøre dette: min favorit hjemmeside er, lad os sige, youtube.com. Gem, genindlæse. Okay. Der er et par problemer nu udover hæslighed af hjemmesiden. 1, jeg er temmelig sikker på, jeg trykker på Enter her. Og jeg gjorde. Jeg ikke kun ramt Enter, jeg også indrykket, praktiserende hvad vi har prædiket om stil, men min er lige ved siden af ​​verden. Så hvorfor er dette? Browsere kun gøre, hvad du fortæller dem at gøre. Jeg har ikke fortalt browseren, "Break linjer her. Indsæt afsnit pause her." Så browseren, betyder det ikke noget, hvis jeg ramte Return 30 gange, det er stadig kommer til at sætte min højre ud for verden. Hvad jeg virkelig nødt til at gøre her, er at sige noget
, indsætter et linjeskift. Og faktisk et linjeskift er lidt af en underlig ting fordi du ikke kan virkelig begynde at flytte til en anden linje, så gør noget, og derefter stoppe flytter til en ny linje. Det er sådan en atomar operation. Du enten gøre det, eller du ikke. Du ramte Enter eller du ikke. Så br er en lille smule af et andet mærke, og så jeg er nødt til at sortere i både åbne og lukke det på én gang. Syntaksen for det er det. Teknisk set kan man gøre sådan noget i nogle versioner af HTML, men det er bare dumt, fordi der er ingen grund til at starte og stoppe noget hvis man i stedet kan gøre det hele på én gang. Indser, at HTML5 ikke strengt nødvendigt denne skråstreg, så vil du se lærebøger og online ressourcer, der ikke har det, men for god foranstaltning lad os øve symmetri, som vi har set hidtil. Dette betyder, at mærket er både åbnes og lukkes. Så nu lad mig gemme min fil, gå tilbage her. Okay, så det er begyndt at se bedre ud, undtagen nettet jeg kender er lidt klikbare, og alligevel youtube her synes ikke at føre til noget. Det er fordi selvom det ligner et link, er browseren ikke vide, at i sig selv, så jeg er nødt til at fortælle browseren, at dette er et link. Måden at gøre dette på er at bruge et anker tag: og lad mig flytte dette til en ny linje bare så det er lidt lettere at læse, og jeg vil skrumpe skriftstørrelsen. Er jeg færdig? Nej, der kommer til at være denne tvedeling. Dette tag, anker tag, faktisk tage en attribut, som ændrer sin opførsel, og værdien af ​​denne attribut er tilsyneladende YouTubes URL. Men bemærk dikotomi er, at bare fordi det er den webadresse, du vil, det betyder ikke, det må være det ord, du understregning og gøre et link. Tværtimod kan der være noget som dette. Så jeg er nødt til at sige stoppe med at lave dette ord et hyperlink ved hjælp af den tætte anker tag. Bemærk jeg ikke gøre dette. 1, ville dette blot være spild af alles tid og det er ikke nødvendigt. For at lukke et tag, du kun nævne navnet på mærket igen. Du behøver ikke nævne nogen af ​​de attributter. Så lad os gemme det, gå tilbage. Okay, voila, nu er det blå og hyperlinks. Hvis jeg klikker på det, jeg rent faktisk gør gå til YouTube. Så selvom min webside ikke er på internettet, er det mindst HTML, og hvis vi lader Internet indhente, ville vi rent faktisk ender her på youtube.com. Og jeg kan gå tilbage og her er min webside. Men læg mærke til dette. Hvis du nogensinde har fået spam eller et phishing-angreb, Nu har du mulighed for efter blot fem minutter at gøre det samme. Vi kan gå her og gøre noget lignende www.badguy.com eller hvad det sketchy hjemmeside er, og så kan du sige bekræfte din PayPal-konto. [Latter] Og nu dette kommer til at gå til badguy.com, som jeg har ikke tænkt mig at klikke på fordi jeg har ingen idé om, hvor det fører hen. [Latter] Men vi har nu evnen til rent faktisk ender der. Så vi er virkelig lige begyndt at ridse overfladen. Vi er ikke programmering som sådan, vi er ved at skrive kodesprog. Men så snart vi afrunde vores ordforråd i HTML, introducerer vi PHP, et virkeligt programmeringssprog der vil give os mulighed for at generere HTML automatisk generere CSS automatisk, så vi kan begynde på onsdag til at gennemføre, siger, vores egen søgemaskine og mere. Men mere om det i et par dage. Vi vil se dig dengang. [CS50.TV]