[Powered by Google Translate] [Vecka 7]
[David J. Malan - Harvard University]
[Detta är CS50. - CS50.TV]
Okej. Välkommen tillbaka. Detta är CS50, och detta är början av vecka 7.
Ett par små meddelanden:
Pset5 pågår nu, eller snart ska,
och låt mig säga, helt ärligt, denna tenderar att vara bland de mer utmanande
av kursens problemet apparater, så låt mig nämna detta nu
så att denna vecka mer än någonsin att du inte vänta tills, säg, onsdag kväll
eller torsdag kväll att dyka i.
Detta är definitivt en intressant pset. Vi tycker att det är kul.
Om du faktiskt få det helt korrekt och kan då utmana den så kallade Big styrelsen,
har du möjlighet att matcha Hardwood med några av kursens personal
och några av dina klasskamrater.
Vad Big styrelsen är är när du har din stavningskontroll fungerar,
kommer du att kunna gå till cs50.net efter att ha kört ett kommando,
rent väljer in, och sedan den tid och mängden RAM och mer
som du har använt i din implementering kommer att visas här på kursens hemsida.
Du kommer att märka att en massa av dessa folk här listas som personal
eftersom helgen, trodde personalen att det skulle vara kul att försöka överträffa varandra.
Så inser att målet här är inte att vinna i personalen.
Även jag är bara här på nummer 13.
Rent väljer i, men det är en möjlighet att se hur lite RAM
och hur få CPU sekunder kan du använda vis-a-vis några av dina klasskamrater.
>> Och jag ska erkänna att Kevin Michael Schmid,
närvarande nummer 1 position som en av de TF,
Detta är en implementering som vi kallar inte
med tanke på att han använder nästan 0 RAM och nästan 0 sekunder för lastning.
Så vi tar hand om Kevin offline. [Skratt]
Det finns vissa färdigheter som Kevin sätter på prov här.
En av de saker som vi trodde vi skulle göra alltför nu CS50x är en vecka pågår,
och ni är lika mycket en del av detta experiment som dessa studenter.
Vi har frågat dem som en del av pset0, som var på samma sätt att lämna in en Scratch projekt
av intresse för dem - ett spel, en interaktiv konstverk, en animering eller liknande -
en 1 - till 2-minuters video, om de skulle vilja, säga hej till världen och vilka de är faktiskt.
Jag trodde att jag skulle dela med dig bara ett par av de videor som har lämnats hittills
eftersom för oss, på personalen åtminstone det verkligen har varit spännande
och inspirerande att se dessa människor från hela världen - länder över hela världen -
du ställer in, av alla saker, en datavetenskap kurs på Internet,
oavsett om det är för att de vill fortsätta sina studier,
de vill ta sin karriär i en ny riktning,
de vill fylla luckor i sina kunskaper,
så några av samma skäl som ni kanske har varit här.
>> Så jag ger dig en sådan elev här. Du kan höja volymen bara lite.
Här är en av våra studerandes 1-minut inlagor.
Hej, världen. Jag är en student för industriell teknik här i Malaga, Spanien.
Jag är mycket glad över detta online-kurs eftersom jag älskar datavetenskap, jag verkligen,
och jag uppskattar verkligen att jag får utforska den.
Och det faktum att jag kan lära samma alla ni gör
men istället för att vara i Harvard jag i Malaga, hur häftigt är inte det?
Tja, jag är Fernando, och detta är CS50. Se er.
[Skratt] annat klipp som vi särskilt vill, ser du att den här herrn engelska är inte så stark.
Det ser ut som att han hade maskin översatt, så översättningarna själva är lite ofullständig,
men detta var en av våra Favoriter hittills också.
[♪ ♪]
Hej, världen. [Tala på japanska]
[Jag måste hälsa på japanska eftersom min engelska är mycket otillförlitliga.]
[Jag har levererat budskapet till dig från staden Gifu, Japan.]
[Jag kan vara en student för första gången på 20 år, vilket kan ses.]
[Jag är mycket tacksam mot Harvard University som gav mig denna möjlighet och EDX.]
[Golf är en gitarr och min favorit sak igång.] [Skratt]
[♪ ♪]
[Varför tror du jag försökte delta i en cs50x.]
[Harvard University, är det min längtan.]
[Speciellt om jag långt närvaro bodde i Japan.]
[Jag ville prova omedelbart medvetna om förekomsten av en sådan EDX när.]
[Tror du inte att du inte relaterade till ålder lära I.]
[CS50 är min längtan. Mitt namn är Kazu, och detta är CS50.]
[♪ ♪] [applåder och jublande]
En annan favorit vårt var underkastelse hit från någon.
[♪ ♪] [Malan] Google om du inte är bekant med denna meme.
>> Och sedan slutligen ett par andra som fick postat att det kanske vinna bedårande utmärkelsen.
[Studenter] Aww! >> [Malan] Vi får lyssna. Det är kort, så lyssna noga.
[Kvinnlig talare] Vad heter du? >> Louie.
[Kvinnlig talare] Vad är detta? >> [Fnittrar] CS50. [Skratt]
[Malan] Han gjorde två tagningar, dock.
Nu kör vi, det sista.
Mitt namn är Louie, och detta är CS50.
[Skratt] Detta är då CS50x.
Tack till alla er när den följer tillsammans hemma
som har ta del hittills.
Idag avslutar vi vår diskussion om datastrukturer,
åtminstone några av de mest grundläggande,
och sedan fortsätter vi vårt samtal om HTML och webbprogrammering.
I själva verket har vi tillbringat förbi några sju veckor att titta på grunderna i programmering -
algoritmer, datastrukturer och liknande -
och C, som ni kanske har upplevt hittills,
är inte nödvändigtvis den mest tillgängliga språk
som att genomföra några av dessa idéer.
Och så börjar denna vecka och nästa vecka och därefter följande,
vi kommer slutligen kunna övergången från C, som i allmänhet är känd som en ganska låg nivå språk,
till saker högre nivå, bland dem PHP, JavaScript och liknande,
som vi får se utnyttja samma lärdomar som vi har lärt oss under de senaste veckorna,
men du kommer att upptäcka att förklara saker som arrayer och hashtabeller och söka och sortering
blivit så mycket lättare eftersom de språk själva vi börja använda
kommer att bli mer kraftfull.
Men först, en tillämpning av träd.
Det är mycket vanligt i dessa dagar för att behöva komprimera informationen.
I vilket sammanhang skulle du vill komprimera någon form av digital information?
>> Ja. >> [Eleven] När du behöver skicka den via webben.
Ja, när du vill skicka något över webben.
Om du vill ladda ner en stor fil, det är perfekt om någon i andra änden
har komprimerat filen med hjälp av en zip-format eller något liknande
så att du skickar färre bitar än vad som annars skulle överföras.
Så hur komprimera du information?
Det hela handlar om att använda färre bitar än vad som krävs som standard.
Men det är lite av en nyfiken sak eftersom tänker tillbaka på veckor 0 och 1
När vi talade om ASCII och binära och vi pratade om ASCII särskilt
som att använda 8 bitar för att representera bokstäverna i alfabetet
så att bokstaven A representeras av 65, gemener ett är antalet 97,
och hur du representerar 65 eller 97, du använder 7 eller 8 bitar.
Men kruxet är att det finns några bokstäver i det engelska alfabetet
som inte är lika populära som andra.
Z är inte så populärt, Q är inte så populärt, men A och E är super populär.
Och ändå för alla dessa brev, som standard världen använder samma antal bitar, bara 8.
Så skulle det inte ha varit smartare om istället för att använda 8 bitar för varje bokstav,
även de mest sällan används som Q och Z,
tänk om vi använde färre bitar för A och E och S och de mest populära bokstäverna
och används fler bitar för de mindre populära bokstäver,
Tanken är låt oss optimera för det gemensamma målet,
vilket är ett tema i datavetenskap för att försöka optimera vad som kommer att hända de mest
och spendera lite mer tid, lite mer utrymme på de saker som, ja, kan hända
men inte nödvändigtvis lika ofta.
Så låt oss ta ett exempel.
>> Antag att vi vill koda information ganska effektivt.
Du kanske har vuxit upp med vetskapen lite om morsekod,
och oddsen är du inte visste själva koden,
men du kanske kommer ihåg att det är minst denna serie av punkter och streck.
Detta är en ganska effektiv kodning, och märker att de mest populära brev - till exempel e -
använder den kortaste av pip.
Morsekod handlar om beep-beep-beep-beep-beep-beep och hålla toner
antingen för korta tidsperioder eller långa tidsperioder.
E, som betecknas med punkten, är en super kort pip, bara pip, och det skulle innebära E.
Däremot skulle T vara en längre pip, som pip [förlänger ljud]
och som skulle representera T
Men det är fortfarande ganska kort eftersom däremot om man tittar på Z,
att uttrycka Z du skulle gå pip, pip [längre ljud], pip, pip [kortare ljud].
Så det är längre eftersom det är mindre vanligt.
Men gotcha här är att morsekod är lite bristfällig
att det inte är direkt avkodningsbara.
Till exempel antar att du hör på vissa änden av kabeln pip [kort], pip [länge].
Vilket budskap fick jag bara? En punkt och ett streck. Vad representerar det?
[Eleven] A. >> [Malan] Kanske.
Det kan också vara E följt av T.
Med andra ord, morsekod, även om det utnyttjar denna princip att optimera hörnet fallet,
Det lämpar sig inte för omedelbar decodability.
Det är, den människa som hör eller tar emot dessa punkter och streck
måste på något sätt räkna ut där pauserna är mellan bokstäver,
för om du inte vet var dessa pauser är, kan du förväxla A för ET eller vice versa.
>> Så vad kan du göra? I morsekod du kan bara paus mellan varje brev.
Men paus är typ av mot hela poängen med snabba upp saker.
Så vad händer om vi istället kom upp med en kod där det inte fanns denna dålig situation
där E är ett prefix, till exempel av A -
Med andra ord, om vi kunde se till att mönstren fortfarande kort för de populära bokstäverna
lång för de mindre populära bokstäver, men det finns ingen förväxling?
En man vid namn Huffman år sedan uppfann detta system kallas Huffmankodning
som utnyttjar faktiskt en av de datastrukturer som vi har tillbringat lite tid att tala om
den senaste veckan, nämligen träd, binära träd särskilt -
ett binärt träd vilket betyder att det inte har mer än 2 barn.
Den har kanske en vänster barn, kanske en rätt barn, och det är det.
Så antar bara för diskussionens skull att någon vill skicka ett meddelande
som ser ut så här. Det är fullständigt nonsens, men det är sammansatt av As, B, Cs, Ds, och Es.
Och om man räknar faktiskt upp alla som, B, Cs, Ds, och Es
och sedan dividera med det totala antalet bokstäver,
denna lilla diagram här säger att 45% av bokstäverna är Es, 20% är As,
10% B, och så vidare.
Så med andra ord, anta att den citerade strängen där
är bara några meddelande som du vill skicka.
Det råkar vara nonsens bara så vi kan använda så få bokstäver som möjligt,
men det är faktiskt så att E fortfarande den mest populära,
och B och C är den minst populära, åtminstone av dessa 5 bokstäver i alfabetet.
Så hur kan vi gå komma med en kodning,
en binär kodning, ett mönster av 0 och 1 för varje av dessa bokstäver
på ett sådant sätt att E är en kort mönster och kanske B och C är något längre mönster,
igen, tanken är att vi vill använda färre bitar för det mesta
och fler bitar endast en gång på ett tag.
Enligt Huffmankodning kan du skapa en skog av träd.
Det blir liksom en story här som involverar träd och även arbetet med att bygga upp dem.
Låt oss börja.
>> Jag föreslår att du börjar med den här skogen, så att säga, av 5 träd,
var och en är en ganska dum träd.
Trädet består av bara en enda nod, som representeras här av en cirkel.
Så alla dessa saker kan vara en C struktur
och insidan av C-struct kan vara en flottör som representerar frekvensen antalet
och sedan kanske en röding representerar brevet.
Så tänk på dessa noder som bara några gamla C-struct, men för nu, högre nivå.
Detta är en skog av 5 träd, vardera som bara har en enda nod.
Vad Huffman föreslås är att vi börjar att kombinera dessa träd
som har de minsta frekvens räknas till något större träd
genom att ansluta dem med en ny rotnod.
Så bland bokstäverna här, märker att för enkelhetens jag har sorterat dem från vänster till höger,
även om det inte är absolut nödvändigt, och märker att de minsta noderna
är för närvarande 10% och 10%.
Så Huffman föreslog att vi går samman de 2 minsta noder i ett nytt träd
genom att införa en ny förälder nod och sedan ge den föräldern en vänster barn och en höger barn
där B är godtyckligt vänster och C är godtyckligt rätt.
Och sedan Huffman föreslog vidare att låt oss nu bara tänka på vänstra barnet
i ett av dessa träd alltid som representeras av 0
och rätt barnet alltid som representeras av siffran 1.
>> Det spelar ingen roll om du vänder dem så länge du är konsekvent.
Så nu har vi fyra träd i den här skogen.
Och jag säger fyra för nu trädet till vänster -
och det är inte så mycket ett träd i den meningen att det växer på detta sätt,
det är mer som ett släktträd där nu 0,2 är typ av förälder till de två barn -
märker att i den föräldern vi har ritat 0,2.
Vi har lagt frekvensen räknas de två barnen och med tanke på nya noden summan.
Så nu upprepar vi bara denna process.
Hitta de två minsta noderna och sedan gå med dem till ett nytt träd
och sedan upprepa processen ytterligare.
Just nu har vi några kandidater, 20%, 15%, och ytterligare 20%.
I det här fallet måste vi bryta slips. Vi kan göra det godtyckligt.
Vi borde bara göra det konsekvent.
I det här fallet, ska jag gå godtyckligt med en till vänster,
och jag samman nu 20% och 15% för att ge mig en ny förälder som kallas 35%,
vars vänstra barn 0, vars rätt barn är 1, och nu har vi bara tre träd i skogen.
Du kan kanske se vart det är på väg.
Om vi ​​upprepar detta ett par gånger, vi kommer att ha bara en större träd,
alla vars kanter är märkta med 0 och 1.
Låt oss göra det igen.
35% är att trädets rot. 20% och 45%, så vi kommer att slå samman 35% och 20%.
Nu har vi detta träd här. Vi lägger dem tillsammans, vi har 55%.
Nu finns det bara två träd i skogen.
Vi gör detta en sista gång, och förhoppningsvis matematiskt alla frekvenser lägga upp
eftersom de bör eftersom vi beräknas dem från get-go för att lägga till upp till 100%.
Och nu har vi en träd.
Så detta är en Huffmankodning träd.
Det slags tog ett tag att komma dit verbalt, men verkligheten är en for-loop
eller med en rekursiv funktion, kan du bygga denna sak upp ganska snabbt.
Så nu har vi ett nytt nod, och alla dessa inre noder har malloc'd,
förmodligen längs vägen.
Så nu på toppen av detta träd har vi 100%, men nu märker vi en stig
från denna nya store-store-store-morförälder till alla stora-store-store-barnbarn
hela vägen vid botten, till alla bladen.
>> Vad vi ska göra nu är att föreslå att för att representera bokstaven E,
Vi kommer helt enkelt att använda siffran 1. Varför?
För om vi korsar detta träd från den slutliga roten ner till bladet som kallas E,
Vi följer bara en kant, den högra kanten, och det är märkt naturligtvis uppe till höger 1.
Så konsekvenserna här Huffman var att E: s kodning i binär bara skall vara 1.
Och det är jäkligt effektivt. Kan inte riktigt få något mindre än så.
Däremot är en kommer att vara representerade, om du följer logiken,
genom vilket mönster av bitar istället? 01.
Så för att komma till en, börjar vi vid roten och vi går till vänster och sedan går vi rätt,
vilket innebär att vi följde en 0 och sedan en 1.
Så vi skall företräda bokstaven A med mönstret 0 och 1.
Och nu märker vi redan har en egenskap av omedelbar decodability
att vi inte har i morsekod.
Även om båda dessa mönster är ganska kort - E är 1 bit, A 2 bitar -
märker att de inte kan förväxlas ena eller det andra,
för om du ser en 1 det måste vara ett E, om du ser en 0 sedan en 1 Det är uppenbarligen fått vara ett A.
Likaså, vad är D? 001.
Vad är C? 0001.
Och vad är B? 0000.
Och återigen, eftersom alla brev vi bryr oss om är i bladen
och ingen av dem är typ av mellanhänder på vägen från rot till blad,
det finns ingen risk för att conflating 2 bokstäver "olika kodningar
eftersom alla dessa bitmönster är deterministiska.
0000 kommer alltid att vara B.
Det finns ingen nod någonstans mellan att du kan förvirra en bokstav för den andra.
Så vad är innebörden här?
>> Den mest populära brev - i detta fall E - har fått den kortaste kodning,
A har fått nästa kortaste kodning,
och B och C, som vi redan visste från get-go var typ av de minst populära
vid 10% frekvens vardera har de fått den längsta kodning.
Och så vad detta betyder nu är att om du vill skicka ett meddelande som är komprimerad
via Internet eller i ett e-postmeddelande eller liknande,
snarare än att använda vanlig ASCII, kan du skicka ett Huffman kodat meddelande
där om du vill skicka bokstaven E, skickar du bara en enda bit.
Om du vill skicka ett A, skickar du 2 bitar, 01, istället för att skicka 8 bitar
följt av ytterligare 8 bitar följt av ytterligare 8 bitar och så vidare.
Men det finns en gotcha här.
Det är inte tillräckligt att bara bygga detta träd och sedan börja skicka från Alice till Bob
den kortare bitmönster, sträng från ASCII,
eftersom Alice har också informera Bob vad
Om Bob kommer att kunna läsa hennes komprimerade budskap?
[Ohörbart elev svar] >> Vad är det?
[Ohörbart elev svar] >> av vad trädet är.
Eller ännu mer specifikt, vad dessa kodningar är,
särskilt eftersom under denna berättelse vi gjort en bedömning samtal vid ett tillfälle.
Kom ihåg att vi var tvungna att välja godtyckligt mellan de 2 olika 20% noder?
Så det är inte så att Bob, mottagaren, kan bara rekonstruera trädet på sin egen
eftersom han kanske kommer att skapa trädet någonsin så lite annorlunda från Alice.
Heller Bob inte ens vet vad det ursprungliga meddelandet är
eftersom det enda Alice skickar honom, naturligtvis, är den komprimerade budskap.
>> Så fångsten med kompression som detta är att, ja, kan Alice spara en hel del bitar
genom att sända 1 för E och 01 för A och så vidare,
men hon har också informera Bob vad mappningen mellan bokstäver och bitar
eftersom de inte kan tydligt lita på bara ASCII längre om vi inte använder ASCII.
Så hon kan antingen skicka honom trädet på något sätt -
skriva ner det, lagra den som binära data eller något liknande -
eller bara skicka honom en liten lathund, en Excel-fil, som visar avbildningar.
Så effektiviteten i kompressionen förutsätter verkligen att de meddelanden som du skickar
är ganska stora, åtminstone medelstora,
för om du skickar en super kort meddelande,
Om du bara vill skicka meddelandet BAD händer som att vara ett ord som vi kan stava här,
B-A-D, är du förmodligen kommer att använda färre bitar,
men kruxet är om du även måste informera Bob vad trädet är
eller vad dessa kodningar är, du kommer att förmodligen uppväger alla de besparingar
att ha komprimerade saker till att börja med.
Så det kan faktiskt vara så att om du försöker komprimera
även med något som zip eller filformat du kan känna -
ganska små filer, även tomma filer -
ibland dessa filer kan bli större och inte mindre.
Men realistiskt, händer det bara för små filstorlekar,
så det kommer inte att göra en gigabyte filen 2 gigabyte;
vi verkligen pratar byte eller bara en kilobyte par.
>> Vissa program som zip är smart nog att inse att,
"Du kommer att spendera fler bitar komprimera detta."
"Låt mig inte bry komprimera det för dig alls."
Så det här är bara ett sätt och sedan att komprimera textformat.
Vi kunde genomföra något liknande i C.
Till exempel, här är hur vi kan representera en nod i detta träd
där vi har en röding på symbolen, en flytande värde för frekvensen,
och som vi har sett med våra andra datastrukturer, 2 pekare,
1 till vänster barnet, 1 till höger, vilket i båda fallen kan vara NULL,
men om inte, hänvisat till en vänster barn och en höger barn.
Så detta är då Huffmankodning, och det är ett sätt som du kan gå om att komprimera information,
och det är verkligen en av de mest lätt att genomföra
i samband med exempelvis förra veckans datastrukturer,
men ännu mer sofistikerade algoritmer finns
som kan göra ännu mer sofistikerade mutationer av dina data.
Eventuella frågor sedan på träd, träd binära eller komprimering av text?
[Elev] Finns det någon tvetydighet, som om [ohörbart] delas upp i 01,
då 011 vara tvetydig, eller hur?
[Ohörbart] >> Bra fråga. Tvetydighet.
Låt mig sammanfatta genom att hänvisa till den här bilden här.
Eftersom de tecken du komprimerar, representationer,
genom definitionen av denna algoritm alltid förblir bladen,
du aldrig misstag använder samma mönster av bitar för prefixet av flera bokstäver.
Så med andra ord, du är orolig, det låter som, en tvetydighet som uppstår
varigenom 001 kan vara början på B eller början på C eller något liknande.
Men det kan inte vara fallet eftersom märker att alla bokstäver i alfabetet vi kodning
är på bladen.
>> Den tvetydighet kan bara uppstå, såsom i fallet med morsekod,
Om, till exempel, var C någonstans på vägen från roten till B.
[Elev] Rätt. Så i det fallet, säger A har 2 blad. >> Säg A har - Säg det igen.
[Elev] Säg A har 2 blad, F och G, och sedan G - >> Okej. Men det går inte.
En själv inte kunde ha blad F och G eftersom dessa bokstäver F och G
skulle själva vara lämnar någonstans till vänster om B eller rätten av E.
Så per definition, måste de vara löv.
Annars är du precis rätt, vi har inte löst problemet med att morsekod står inför.
Bra fråga. Övriga frågor? Okej.
Denna föreställning om bitar, visar det sig att vi har haft makten hela tiden att vi faktiskt inte har använt
när det gällde att manipulera dessa 0 och 1.
Vi frågade om detta på ett av de tidigaste problemet set:
nämligen hur du går om att konvertera versaler till gemener eller tvärtom?
Eller mer konkret, frågade en av de första psets
hur många bitar behöver du faktiskt vända för att ändra en till gemener en eller tvärtom?
Här är en snabb påminnelse om vad 65 och 97 ser ut i binärt.
Och även om den frågan har typ av bleknat i minnet,
Du kan se igen här att hur många bitar måste vändas
att ändra kapitalet A till gemener en? Bara en.
>> De skiljer sig endast på ett ställe, den tredje biten från vänster.
Medan A har en 010, lite en har 011.
Så på något sätt måste vi bara kunna vända den biten,
och vi kan då dra nytta eller gemener.
Vi har gjort detta tidigare genom att faktiskt använda om villkor
och kontrollera om brevet är mellan kapitalet A och kapital Z,
sedan utgångar som A - a + 26 eller nåt sånt.
Du gjorde förmodligen en aritmetisk ändring av bokstäverna i alfabetet.
Men tänk om vi bara kunde vända det enda bit?
Hur kan du gå om att ta ett byte värde av bitar, så 8 bitar som 01.000.001 och 01.100.001?
Om du hade dessa mönster av bitar, hur kan vi gå om att ändra bara en av dem?
Tänk om vi introducerar i gult här i andra mönster av bitar?
Om jag gör hela gula sträng 0s undantag för en bit som jag vill ändra
och då jag införa en ny aktör som kallas en bitvis operatör -
bitvis i den meningen att den arbetar på enskilda bitar,
inte på en hel bitgrupp eller fyra byte på en gång.
Denna lodrätt streck där i gult tyder på att vad händer om vi tar representationen av kapitalet A
och bitvis ELLER den med den gula bitsekvens?
Med andra ord, tänker tillbaka till vår diskussion om booleska uttryck i Scratch och sedan i C.
>> Att göra en boolesk eller innebär att vara sant, antingen den första måste vara sant
eller den andra saken måste vara sann eller de båda har för att vara sant,
och sedan den resulterande utsignalen är själv sant.
I detta fallet här, vad vi får om vi tar 0 "eller" ed med 0? Falska eller falskt?
Det är fortfarande falskt, så små en är som förväntat.
Tänk om vi istället gör 1 eller 0?
Detta återstår nu 1, men märker vad att hända här.
Om vi ​​börjar med kapital A och vi fortsätter att "eller" dess enskilda bitar som vi gör här,
0 eller den gula en ger oss vad här nere? Det ger oss 1.
I själva verket, antar att vi inte visste vad det versaler versionen av lite en faktiskt var.
Låt oss gå göra detta. Låt mig flytta tillbaka hit.
Låt oss göra det igen. 0 eller 0 ger mig 0.
1 eller 0 ger mig 1.
0 eller 1 ger mig 1.
0 eller 0 ger mig 0. Nästa gång det är 0, nästa är 0, är ​​nästa en 0.
1 eller 0 ger mig 1.
Och så även om vi inte visste i förväg vad gemener en var,
helt enkelt genom "eller" ing A med detta mönster av bitar som vi har presenteras här i gult,
Du kan gemener ett kapital A genom att bläddra den biten.
Vi använde detta uttryck veckor sedan: bläddra lite.
Hur gör du faktiskt göra det programmatiskt?
Du använder vad som allmänt kallas en mask, en sekvens av bitar,
att i detta fall råkar vara så att se ut så här numret här,
och sedan "eller" det tillsammans med den nya C-operatör,
inte | | du använder en enda | och du skulle faktiskt få detta svar här eftersom varför?
Detta är den plats 1s, 2s plats, 4S, 8S, 16s, 32s.
Så det visar sig att om du tar en bokstav A och bitvis ELLER den med heltalet 32,
eftersom heltalet 32, när man tittar på det som bitar, ser ut så här,
som innebär att du kan vända den bit som du verkligen vill.
Och på samma sätt - och vi titta på kod på bara ett ögonblick -
antar att vi vill gå åt andra hållet.
>> Hur går du från gemena en till kapital A? Vilken bit måste förändras?
Det är samma en.
Vi vill ändra på det tredje biten från 1 till 0.
Och hur kan vi gå om att göra detta?
Hur stänger vi av lite? Med vilken mönster av bitar kan vi stänga lite?
Tänk om vi sorterar av invertsocker masken?
Medan tidigare gjorde vi hela gula masken 0s
utom för en bit vi ville vända på,
tänk om denna tid gör vi hela masken 1s förutom den bit som vi vill stänga
och sedan använda det operatör?
Tänk om vi "och" saker? Låt oss ta en titt.
Om vi ​​nu vänder på detta, anta att jag återigen skapa en mask som är allt 1s
med undantag för en bit som jag vill stänga
och sedan snarare än "eller" de vita siffror upp toppen med de gula siffrorna här nere,
Vad händer om jag istället "och" dem tillsammans? Det kallas en bitvis och.
Logiskt sett är det samma sak som ett booleskt och.
Det ger mig 0 och 1 är 0. Så falsk och sant är falskt.
Sann och sant är sant.
Och här är den magiska: sant och falskt är nu falskt, så vi har stängt av den biten.
Och nu resten av historien är något enkelt.
Eftersom resten av masken är 1s, spelar det ingen roll vad siffrorna är i vitt.
När du "och" något med sant, du kommer inte att ändra dess värde.
Om det är sant, kommer det att förbli trogna. Om det var falskt, kommer den att förbli falsk.
>> Men det magiska händer när du tar något som var sant
och du sedan "och" den med falskt.
Detta har effekten att stänga av den biten.
Så lite kryptisk där.
Låt oss verkligen titta på några kod, som faktiskt kan se ännu mer kryptiskt,
men låt oss ta en titt här på tolower.
Om jag tittar på tolower, från kapital A till gemener en,
låt oss se hur vi kan genomföra detta program.
Här är viktigaste, och det är inte ta några kommandoradsargument.
Jag förklarar ett tecken c för det brev som användaren ska skriva i.
Jag använder sedan en bekant göra medan slinga för att bara se till att användaren definitivt ger mig ett kapital A
eller B eller C. .. Z, så de ger mig något mellan A och Z.
Och nu vad gör jag här?
Jag är "eller" ing detta med 0x20, men det är faktiskt samma som -
och vi kommer att återkomma till detta i ett ögonblick - 32.
Så återigen, är 32 detta mönster av bitar här. Varför vet vi det?
Tänk tillbaka till vecka 0.
Detta är den plats 1s, 2s plats, 4S, 8S, 16s, 32S plats.
Så denna gula nummer råkar vara 32.
Jag kan sedan ta en bokstav som röding här bitvis "eller" det med bokstavligen numret 32,
och vad får jag tillbaka? Den gemena versionen av röding.
För en stund sedan, men uttryckte jag detta i en annan bas notation.
Vad har detta för? >> [Elev] Hexadecimal.
[Malan] Detta händer att representera hexadecimalt.
Vi har inte pratat om hexadecimalt så mycket,
men det är faktiskt bekvämt i fall som detta.
>> Även om det ser mer komplex och även om det ser ut som 20 och inte 32,
det visar sig att hexadecimala faktiskt super bekvämt notation
eftersom hexadecimala varje siffran efter 0x - och det betyder ingenting;
detta är bara mänskligt konvention som säger här kommer ett hexadecimalt tal -
vart och ett av dessa siffror, 2 och sedan 0 kan själva representeras
med exakt 4 bitar.
Så om vi gör det, låt mig öppna upp en textredigerare här - konstig Komplettera automatiskt -
om vi gör en liten textredigerare här innebär att antalet 0x20 här är 4 bitar, här ytterligare 4 bitar.
Låt oss göra det längst till höger 4 bitar först.
0 när representerat med 4 bitar är vad? Super lätt. Bara alla 0s.
Så 4 bitar som 0s.
Hur står ni 2? Det var ett tag sedan vi gjorde detta, men det är 0100.
Så detta är den 1s plats, är detta 2s plats, och sedan det spelar ingen roll vad de andra platserna är.
Med andra ord, i hexadecimal du kan säga 0x20,
men om du sedan tänker på vad är 2 och hur det representeras i binär,
vad är 0 och hur det representeras i binär,
svaren på dessa frågor är det och det, respektive.
Så 0x20 råkar representera detta mönster av 8 bitar,
vilket är just den mask som vi ville ha.
Så det här är för tillfället bara en intellektuell övning,
men verkligheten är i kod det oftast vanligare att skriva konstanter som denna
i hexadecimal för då programmeraren kan relativt enkelt,
även om det kräver lite papper och penna, räkna ut vad det mönster av bitar är
eftersom du inte kan bara uttrycka 0 och 1 vanligtvis i koden.
Du kan inte gå 00.010 och så vidare.
>> Du måste välja decimala eller hexadecimala eller oktala eller andra beteckningar.
De flesta människor tenderar att plocka hexadecimala helt enkelt så att varje siffra representerar 4 bitar
och du kan göra detta snabbt matematik.
Och jag vinkar min hand på toupper, vilket är nästan samma, det ser nästan identiska.
Toupper råkar inte använda eller operatören utan den här killen och DF.
Vad representerar df? df? Någon? >> [Elev] 255.
255? Inte 255. Det skulle vara ff.
Vi lämnar det här en som en liten övning.
Men om du går från 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 och vad kommer efter 9?
Vi är typ av ur decimaler, men i hexadecimal vad som kommer efter 9?
[Elev] en. >> Så a, b, c, d..
Du kan räkna ut därifrån vilket mönster av bitar d. faktiskt representerar.
Och om vi gör matten, vi får se till att masken du i slutändan får tillbaka är identisk med denna.
Detta är f, alla 1s, och detta är d. Så df representerar den masken. Okej.
Och slutligen, inte göra saker och ting bra super, super tekniska,
men antar vi ville skriva ett program som gör detta.
Låt mig gå vidare och göra binära, som är ett program i en fil som heter Skrivning.
Och låt mig nu kör binär och ge mig en icke-negativt heltal.
Låt oss börja enkelt och skriv in 0.
Detta är nu ett program som skriver ut ett heltal i binär representation.
Så om jag spelar detta spel igen och skriva in bara 1 skulle jag få en 32-bitars representation av 1.
Om jag gör det igen med 2, ska jag få det.
Om jag gör 7 skulle jag få ett par 1s i slutet och så vidare.
Det visar sig att jag nämner detta eftersom med bitvisa operationer
Du kan faktiskt göra en annan sak också.
Du kan skapa dessa masker dynamiskt.
Ta en titt på detta ett sista exempel där bitvisa operationer.
Här är den första delen av koden, fråga användaren efter ett nummer
och det insisterar på att du ger mig en icke-negativt heltal.
Så det är typ av gamla skolan grejer.
Men här är något som är ganska intressant.
>> Hur gör jag för att skriva ut en rad i binär?
Jag iterera först från vad till vad?
Vad är storleken på en int typiskt, åtminstone i apparaten? >> [Elev] 4.
Det är 4. Så 4 * 8 är 32 till 1 är 31.
Så om jag börjar att räkna från 31, representerar att det visar sig,
bara begreppsmässigt, den 31 bitar eller den högsta ordning lite, vilket är den här killen här,
Detta kommer att vara lite 0.
Så det här är lite 01 ... bit 31.
Så vad är denna kod gör?
Notera detta för slinga, även om det ser kryptisk, är bara iterera från 31 ner till 0. Det var allt.
Så den intressanta delen nu måste i dessa 5 rader här.
Observera att i denna linje jag förklara en variabel som heter mask
att vara konsekvent med vår berättelse dessa gula siffror.
Och vad är detta gör?
Detta är en annan bitvis vi inte sett förut, troligen.
Det är den vänstra shift operatör.
Denna operatör gör detta.
Här är antalet 1, och om du gör jag lämnade skift, vänster shift,
vad tror du som har effekten att göra med att enskilda 1?
Bokstavligen flytta den.
Så om antalet 1 är vad du har till vänster och du börjar med att initiera i till 31,
vad är det göra? Det kommer att ta nummer 1 och flytta den 31 platser här.
Och eftersom det finns uppenbarligen inga andra siffror bakom sig,
de kommer som standard att ersättas med 0s.
Så du börjar med nummer 1, vilket naturligtvis ser ut så här -
och låt mig rita den hit i mitten.
Och sedan när du flytta saker till vänster, går den här killen i huvudsak på detta sätt.
Men så fort du gör det, blir en 0 fyllas i.
Om du flyttar den en andra gång, går det så här och en annan 0 fylls i.
>> Du flytta det igen och sedan en annan 0 fylls i.
Så om du gör det här av 1 << I 31 platser, slut dig att få en mask
som är 32 tecken långt, längst till vänster av vilka en är en 1,
alla övriga som är en 0.
Och det visar sig, som en sidoreplik, flytta ett nummer till vänster så här
också tillfällighet, och ibland bekvämt,
har effekten att göra vad den siffran? >> [Elev] Fördubbling det.
Fördubbling det eftersom varje kolumn - de 1s plats, 2s plats, 4s plats,
8s plats 16s plats - de är alla fördubbling som du går till vänster.
Eller snarare, när du ändrar 1s du kommer att hamna fördubbla värdet av numret.
Du kan sluta göra intressanta omvandlingar av siffror
genom att flytta allt över på detta sätt genom befogenheter 2.
Så hur fungerar det?
Detta ger mig sedan en mask som är allt 0s utom en 1 i exakt den plats som jag vill ha det,
och sedan detta uttryck, som stulits från toupper.c,
är helt enkelt säger ta talet n som användaren skrivit in,
"Och" den med den masken, och vad ska du bli?
Du kommer att få en 1 om det finns en 1 i den maskerade plats,
eller du kommer att få en 0 om det inte finns.
Och så allt det här programmet gör effektivt är att den har en slinga,
och det skapar en mask med en 1 hit, sedan en 1 hit, sedan en 1 hit,
och den använder denna bitvis OCH knep att säga är det en 1 bit i användarens input här?
>> Finns det en 1 bit i användarens input här? Och i så fall bokstavligen ut 1, annars ut 0.
Vi gör detta med Ints bara för att det är därför vi gör 32 bitar i stället för 8,
men vad vi har infört är då denna bitvis AND, denna bitvis OR,
och denna vänster shift operatör, som inte ofta fruktansvärt bra,
men det visar sig att de kan vara.
Faktum är att om du skulle representera något som en rad Booleans
bara för att representera sant eller falskt Anta att du vill hålla koll på huruvida
ett rum fullt av 300 elever är närvarande,
kan du förklara en rad storlek 300 av typ bool så att du får 300 bools,
och du kan ställa in varje till true om någon är här och i annat fall false.
Varför är det representationen i den datastruktur ineffektiv?
Vad är dåligt om utformningen av den datastruktur, en uppsättning av 300 bools?
Vad är en bool, faktiskt, under huven?
Även detta är något som kanske inte känner till.
Det visar sig att det inte finns någon bool.
Kom ihåg att vi sorts skapas som med cs50.h filen,
som i sin tur innehåller standarden bool.
C är typ av dum, men när det kommer till bool.
Den använder 8 bitar för att representera varje bool, vilket är helt slöseri
eftersom det självklart, hur många bitar du behöver för att representera en bool? Bara 1.
Så det visar sig att om du har nu möjlighet med bitvisa operatörer
att manipulera enskilda bitar även i en röding, även i en enda byte,
det visar sig att du kan minska det minne som krävs för att representera något dumt
som att närvaro stylad datastruktur med en faktor 8.
Istället för att använda åtta bitar för att representera sant eller falskt, kan du använda bokstavligen en
genom att använda en enda byte för varje åtta elever i klassen
och växla från 0 till 1 individuella bitar genom att använda dessa typer av lågaktivt trick.
Det är verkligen sätta stopp för energin. Finns det några frågor om bitvisa operationer?
>> Ja. >> [Elev] Finns det en exklusiv eller operatör?
Ja. Det är en exklusiv eller operatör som ser ut så här, ^, morot symbolen,
vilket betyder bara det första eller det andra sak kan vara en 1 för utgången att vara en 1.
Det finns också en inte ~ som gör att du kan invertera en 0 till en 1 eller vice versa samt.
Och det finns också en rätt skift operatör, >>, vilket är motsatsen till den vi såg.
Okej. Låt oss ta saker nu till en högre nivå.
Vi började med att tala om text och sedan komprimera den
och representerar texten med färre antal bitar,
Vi pratade lite om hur vi kan nu börja manipulera saker på en bitvis nivå.
Låt oss zooma nu tillbaka 10.000 fot till representation
av mer komplexa saker som grafik.
Här har vi en tysk flagg, här har vi en av Frankrike.
Dessa kan representeras i filformat du kanske vet - GIF, till exempel.
Om du någonsin sett en bild på webben som slutar på. Gif,
detta är en Graphics Interchange Format.
Dessa två flaggor här sortens lämpar sig för komprimering
för vad kanske uppenbar anledning? >> [Ohörbart elev svar]
Det finns en hel del upprepning, eller hur?
För att skicka Tysklands flagga, tänk på detta som en bild på skärmen
tillbaka i dina Scratch dagar.
Du kanske kommer ihåg att det finns enstaka bildpunkter eller prickar som utgör en bild.
>> Det finns en hel rad av svarta prickar och en annan hel rad av svarta prickar.
Det finns en massa rader av svarta prickar som vi kunde se om vi verkligen har zoomat in,
ungefär som när vi zoomat in på Rob ansikte i Photoshop.
Så snart vi fick djupare och djupare och djupare in i bilden,
du började se pixelering, alla rutor som består hans öga i det fallet.
Samma affär här. Om vi ​​zoomat in ganska lite, skulle du se enskilda punkter.
Nåväl, är denna typ av slöseri bitar.
Om en tredjedel av flaggan är svart och en tredjedel av flaggan är gul och så vidare,
varför kan vi inte komprimera något denna flagga?
Och även den franska flaggan kan komprimeras även om mönstret är lite annorlunda.
Det visar sig GIF filformatet är ett förlustfritt komprimeringsformat,
vilket innebär att du kan ta en bild som den tyska flaggan här,
Du kan kasta bort en massa av sina bitar utan avkall på kvaliteten.
Detta står i motsats till något liknande JPEG,
som de flesta av oss är förmodligen mer bekant.
Facebook bilder och Flickr foton och liknande
är nästan alltid sparas som JPEG när de är uppladdade,
men JPEG är en förstörande - förstörande - format där du kastar bitar
men du kastar också bort kvalitet.
Och så om du komprimera bilder med Photoshop eller ladda upp dem till Facebook
eller ta dem på en riktigt skit telefon,
du vet att bilden börjar bli mycket fläckiga och pixelated,
och det är för att det är som komprimeras av datorn eller telefonen
genom att bokstavligen kasta informationen bort.
Men GIF är fantastiskt att det kan använda färre bitar än det kanske som standard
utan att förlora någon information.
>> Och det gör i huvudsak så som följer.
I stället för butik i en fil som en BMP skulle en RGB trippel för svart, svart, svart, svart,
svart, svart, svart, svart, svart, svart, svart, svart och så vidare,
snarare är GIF kommer att säga, "Black"
och sedan "Upprepa detta 100 gånger", eller något liknande.
"Svart, upprepa detta 100 gånger, svart, upprepa detta 100 gånger ..."
"Gul, upprepa detta 100 gånger."
Och så minns i huvudsak längst till vänster pixel
och sedan kodar något sätt begreppet upprepa denna pixel och om igen.
Så GIF kan sedan komprimera sig utan att förlora någon information.
Men om du skulle gissa, om det är den algoritm som GIF användning,
vilka av dessa flaggor, även om de ser identiska i storlek,
kommer att bli mindre när de sparas på disk som en GIF? >> [Eleven] Tyskland.
Tyskland kommer att bli mindre? Varför?
[Studerande] Eftersom du upprepa det många, många gånger horisontellt
och sedan upprepa en annan tid. >> Exakt.
Eftersom de människor som uppfann GIF bara typ av beslut godtyckligt
att upprepningen ska överföras horisontellt och inte i sidled.
Det finns mycket mer upprepning sidled här i den tyska flaggan än i den franska flaggan.
Så om vi faktiskt öppnar en mapp på min hårddisk som har dessa GIF,
Du kan faktiskt se att den tyska flaggan här är 2 kilobyte och den franska en är 4 kilobyte.
Det råkar vara en tillfällighet att en är dubbelt den andra,
men det är i själva verket så att den franska flaggan är mycket större.
>> Även om vi pratar om här grafik kan samma idéer gäller
inte saker som flaggor, men bilder som är lite mer komplicerat.
Om du tar en bild av ett äpple, säkert finns det en hel del dubbelarbete där,
så vi på något sätt kunde komma ihåg att standard bakgrunden är blå
och inte, som den högra bilden visar,
måste komma ihåg färgen på varje pixel i bilden.
Så vi kan kasta bitar bort det utan att förlora information.
Äpplet ser fortfarande likadant.
I det här exemplet här, kan du se vad som händer i en film.
Dessa representerar gamla skolan film rullar varvid i övre bilden där
du har en RV kör förbi ett hus och ett träd.
Och som van kör förbi från vänster till höger, vad uppenbarligen inte förändras?
Huset kommer inte någonstans, och trädet kommer inte någonstans.
Det enda som rör sig är van i detta fall.
Så som bakgrund Oförändrad antyder, vad du kan göra i filmer
är kasta liknande bara bort information som inte förändras mellan ramar.
Detta är allmänt känt som interframe komprimering
varigenom om denna ram ser nästan identisk med den här,
låt oss inte fundera lagring på hårddisk någon av samma information
på dessa mellanliggande bildrutor, låt oss bara använda nyckelbildrutor då och då
att lagra faktiskt att informationen redundant precis som en liten sanity check.
>> Däremot är ett annat sätt att komprimera video i detta andra och lägre exempel här,
där i stället lagra 30 bilder, varför inte du lagrar bara 15 bildrutor per sekund i stället?
Snarare än filmen typ av flytande vackert, perfekt,
kan det se ut som det stamning lite, lite old school,
men nettoeffekten är att använda mycket färre bitar än vad som annars skulle vara nödvändigt.
Så var lämnar det då oss?
Det var lite av en åt sidan på var annars kan du gå med kompression.
För mer information om detta, ta en klass som CS175 här.
Här är ett annat exempel inom video.
Om biet är det enda röra,
du kan verkligen kasta bort informationen i dessa mitten ramar
eftersom blomman och himlen och lämnar inte förändras.
Men låt oss nu betrakta en sista sak.
Under de närmaste 5 minuter lämnar vi C efter evigt i föreläsning? Ja. Inte i psets, dock.
Senaste berättelse om C och sedan får vi mycket sexig Stuff
där HTML och webb-och woo-hoo. Okej.
Nu kör vi. Det är motivationen.
Det visar sig hela tiden när vi har skrivit program vi kör klang.
Och klang, vi har sagt sedan den första veckan ganska mycket tar källkod
och omvandlar den till objektkod.
Det tar C och omvandlar den till 0 och 1.
Jag har typ av ljugit för dig för några veckor eftersom det inte är riktigt så enkelt är det.
>> Det finns mycket mer som händer under huven när du kör ett program som klang.
I själva verket kan processen att sammanställa ett program verkligen sammanfattas,
som ni kanske minns från Rob video på kompilatorer,
i dessa 4 steg: förbehandling, sammanställa själv, montering och länkning.
Men vi i klassen och de flesta människor i världen sammanfatta typiskt alla dessa steg
som bara "kompilering."
Men om vi börjar med källkod så här, minns det är kanske det enklaste C-program
Vi har skrivit hittills, minns att när sammanställt det hamnar ser ut så här.
Men det finns faktiskt ett mellansteg, och dessa åtgärder är följande.
Först finns det här högst upp i detta och de flesta av våra program,
# Include
Vad ingår # göra för oss?
Det ganska mycket kopior och pastor innehållet i stdio.h i min fil som så varför?
Varför bryr jag mig om innehållet i stdio.h? Vad finns där av intresse?
Printf förklaring, dess prototyp, så att kompilatorn sedan vet vad jag menar
När jag nämner denna funktion printf.
Så steg 1 i sammanställningen är förbehandling, där ett program som klang
eller något hjälpprogram som klang levereras med läser din kod topp till botten,
vänster till höger, och varje gång det ser en # symbol följs av ett sökord som inkluderar,
den utför den operationen, kopiera och klistra in i detta fall stdio.h i filen.
Det är steg 1.
Då har du en mycket större C-fil på grund av den enorma kopiera, klistra in jobb som bara har hänt.
>> Steg 2 nu sammanställer.
Men det visar sig att sammanställa tar källkod som ser ut så här
och omvandlar den till något som ser ut så här,
som för dem som är bekanta heter? >> [Elev] församling. >> Assembler.
Detta är faktiskt något om du tar CS61 du dyka in mer i detalj.
Detta är bara ungefär så nära som du kan komma att skriva 0 och 1 själv
men skriver saker på ett sätt som fortfarande gör åtminstone lite förnuft.
Dessa är maskininstruktioner, och om vi bläddra ner till huvudfunktionen här,
märker att det är denna push-instruktion, flytta instruktion, subtrahera instruktion,
call instruktion, och så vidare.
När du hör att datorn har Intel Inside,
du har en Intel CPU i din Mac eller PC, vad betyder det?
En CPU levereras byggd av företag som Intel förstå vissa instruktioner.
De har ingen aning om vad funktioner som swap är eller huvudsakliga är i sig,
men de vet vad mycket låg nivå instruktioner som addera, subtrahera, trycka,
flytta, ring och så vidare är.
Så när du kompilerar C-kod till assembler,
din mycket användarvänlig utseende kod omvandlas till något som ser ut så här,
som rör sig bokstavligen byte eller 4 byte runt i sådana små enheter i och ut av CPU.
Men till slut, när klang är redo att ta denna representation av ditt program
till 0 och 1, då steget kallas montering händer,
och detta igen alla händer i ett ögonblick när du kör klang.
Vi börjar här, matar den ut en fil som denna, och sedan omvandlar den till dessa 0 och 1.
Och om du vill gå tillbaka någon gång och faktiskt se detta i handling,
Om jag går in hello1.c--detta är en av de allra första programmen som vi tittat på -
Normalt skulle vi sammanställa detta med klang hello1.c och detta skulle ge oss a.out.
Om däremot du istället ge den-S flaggan, vad du får är hello1.s
och du kommer faktiskt se assembler.
>> Jag gör det här för en mycket kort program, men om du går tillbaka till Scramble
eller återvinna eller något program som du har skrivit och bara av nyfikenhet
vill se hur det faktiskt ser ut, vad som faktiskt matas in i processorn,
Du kan använda den-S flaggan med klang.
Men sedan slutligen, det finns fortfarande en gotcha.
Här är de 0 och 1 som representerar min genomförandet av hej, värld.
Men jag använde någon annans funktion i mitt program.
Så även om processen har varit jag tar hej.c,
det blir kompileras till assemblerkod, och sedan blir samman till 0 och 1,
den enda 0 och 1 som matas ut vid denna tidpunkt
är de som följer av min kod.
Men den person som skrev printf, sammanställt de sin kod för 20 år sedan
och det är nu installerad någonstans på apparaten,
så vi har något att slå ihop sina 0 och 1 med min 0 och 1,
och som leder oss till den 4: e och sista steget att sammanställa, så kallad länkning.
Så på vänster sida har vi exakt samma bild som tidigare:
hej.c blir assemblerkod blir 0 och 1.
Men minns att jag använde standard I / O-bibliotek i min kod,
och det innebär någonstans på datorn finns en fil som heter stdio.c
eller åtminstone den kompilerade versionen eftersom detta någon några år sedan
sammanställt stdio.c i assemblerkod och sedan en hel drös av 0 och 1.
Detta är vad som kallas en statisk eller en dynamisk bibliotek.
Det är lite fil sitter någonstans i apparaten.
>> Men slutligen måste jag ta min 0 och 1 samt den personens 0 och 1
och på något sätt koppla ihop dem, kombinera bokstavligen de 0s och 1s
till en enda fil som heter a.out eller hello1 eller vad jag heter mitt program
så att slutresultatet har alla 1: or och 0: or som ska komponera mitt program.
Så hela den här tiden denna termin när du har använt klang
och ännu mer nyligen igång göra för att köra klang,
alla dessa steg har hänt sorts omedelbart men mycket medvetet.
Och så om du fortsätter i datavetenskap, nämligen CS61,
Detta är det lager som du kommer att fortsätta att skala tillbaka utanför där
talar om effektivitet, konsekvenser säkerhet och liknande av dessa lägre nivå detaljer.
Men med det, är vi på väg att lämna C bakom.
Låt oss gå vidare och ta vår 5-minuters paus nu,
och när vi kommer tillbaka: Internet.
Okej. Vi är tillbaka.
Nu börjar vi vår blick inte bara på HTML eftersom, som ni kommer att se,
HTML sig är faktiskt ganska enkelt
men egentligen på webbprogrammering mer allmänt nätverk mer allmänt,
och hur alla dessa tekniker kommer tillsammans
att tillåta oss att skapa mer avancerade program ovanpå Internet
än hittills har vi kunnat under dessa svarta och vita fönster.
Faktum är att vid denna punkt i terminen trots att vi kommer att spendera relativt sett mindre tid
på PHP, HTML, CSS, JavaScript, SQL och mer,
de flesta studenter gör sluta göra de slutliga projekt som är webbaserat
för som du ser, den bakgrund du har nu i C
är mycket för dessa högre nivå språk.
>> Och när du börjar tänka på din slutliga projektet,
som, ungefär som problembild 0, där du uppmuntrades
att göra de flesta något av intresse för dig i Scratch,
den slutgiltiga projektet är din chans att ta din nyfunna kunskap och kunniga med C
eller PHP eller JavaScript eller liknande ut för en spin
och skapa din egen mjukvara för världen att se.
Och till utsäde dig med idéer, vet att du kan gå här, projects.cs50.net.
Varje år, värva vi idéer från lärare och personal och grupper studerande på campus
bara för att lämna in sina idéer för intressanta saker som kan lösas med hjälp av datorer,
använda webbplatser, med hjälp av programvara.
Så om du kämpar för att komma med en idé av dina egna,
med alla medel bläddra igenom de idéer där från detta år och sista.
Det är helt okej att ta itu med ett projekt som har tagits upp tidigare.
Vi har sett många apps för att se status för tvätt på campus,
många apps för att navigera i menyn matsal,
många apps för att navigera i kurskatalogen och liknande.
Och faktiskt, i en framtida föreläsning och i framtida seminarier,
Vi kommer att introducera dig till några allmänt tillgängliga API: er, både kommersiellt tillgängliga
liksom här tillgängligt från CS50 på campus så att du har tillgång till data
och kan sedan göra intressanta saker med det.
Så mer om slutliga projekt i ett par dagar när vi släpper specifikationen,
men nu, vet att du kan arbeta ensam eller med en eller två vänner
på de flesta varje projekt av intresse för dig.
Internet.
Du går vidare och dra ut din bärbara dator, går du till facebook.com för första gången,
inte ha loggat in nyligen, och tryck på Enter. Vad händer egentligen?
>> När du trycker Enter på datorn, ett helt gäng steg
start slags magiskt händer.
Så du här till vänster, webbserver som Facebook är här till höger,
och på något sätt du använder detta språk som kallas HTTP, Hypertext Transfer Protocol.
HTTP är inte ett programmeringsspråk. Det är mer av ett protokoll.
Det är en uppsättning konventioner som webbläsare och webbservrar använda när förbindelse med varandra.
Och vad det innebär är följande.
Ungefär som i den verkliga världen, har vi dessa konventioner
där om du uppfyller vissa människa för första gången, om du inte har något emot humoring mig här,
Jag kanske kommer upp till dig, säg, "Hej, mitt namn är David." >> Hej, David. Mitt namn är Sammy.
"Hej, David. Mitt namn är Sammy."
Så nu har vi precis engagerade i denna typ av fåniga människor protokoll
där jag har inlett protokollet har Sammy svarat,
Vi har skakat hand, och transaktionen är klar.
HTTP är mycket likartad i anden.
När din webbläsare förfrågningar www.facebook.com,
vad din webbläsare verkligen gör är att utvidga sin hand, så att säga,
till servern och det är skickar det ett meddelande.
Och det budskapet är typiskt något som få - vad vill du få? -
få mig hemsidan, som normalt betecknas med ett snedstreck i slutet av en webbadress.
Och bara så du vet vilket språk jag talar, jag webbläsaren ska berätta
att jag talar HTTP version 1,1,
Och även för bra åtgärd, jag ska berätta för er att värden som jag vill hemsidan för
är facebook.com.
Vanligtvis en webbläsare, ovetande dig, människa,
skickar detta meddelande över Internet när du helt enkelt skriva www.facebook.com,
>> Enter, i din webbläsare.
Och vad svarar Facebook med?
Den svarar med något liknande som ser kryptiska detaljer men också mycket mer.
Låt mig gå vidare till Facebooks hemsida här.
Detta är den skärm som de flesta av oss förmodligen aldrig se om du förbli inloggad hela tiden,
men detta är verkligen deras hemsida.
Om vi ​​gör detta i Chrome märker att du kan dra upp dessa små snabbmenyer.
Med hjälp av Chrome, antingen i Mac OS, Windows, Linux, eller liknande,
Om du styr klick eller vänster klick kan du dra vanligtvis upp en meny som ser ut så här,
där några alternativ väntar, är en av dessa View Page Source.
Du kan också vanligtvis få dessa saker genom att gå till Visa-menyn och peta runt.
Till exempel, här under Visa är utvecklare samma sak.
Jag ska gå vidare och titta på View Page Source.
Vad du ser är HTML att Mark har skrivit att representera facebook.com.
Det är en fullständig röra här, men vi får se att detta gör lite mer känsla snart.
Men det finns några mönster här. Låt mig rulla ner till sånt här.
Det är svårt för en människa att läsa, men märker att det finns detta mönster av vinkelparenteser
med sökord som alternativ sökord som värde, några noterade strängar.
Det är där, när du registrerade dig för första gången, anges vad ditt födelseår är.
Det rullgardinsmenyn för födelse år på något sätt kodas här
i detta språk som kallas HTML, HyperText Markup Language.
Med andra ord, när webbläsaren begär en webbsida,
det talar denna konvention kallas HTTP.
Men vad svarar facebook.com på denna begäran med?
>> Den svarar med några av dessa kryptiska meddelanden, som vi ser i ett ögonblick.
Men de flesta av dess svar är i form av HTML, HyperText Markup Language.
Det är den faktiska språk som en webbsida skrivs.
Och vad en webbläsare verkligen är då, vid mottagandet av något som ser ut så här,
läser den uppifrån och ned, från vänster till höger, och varje gång det ser en av dessa vinkelparenteser
följt av ett nyckelord som alternativ visar det sig att märkningsspråk på lämpligt sätt.
I det här fallet skulle det visa en rullgardinsmeny år.
Men återigen, detta är en fullständig röra att titta på.
Detta beror inte på Facebook utvecklare manifesterar 0 för 5 för stil, till exempel.
Detta eftersom de flesta av koden som de skriver är i själva verket skriven vackert,
väl kommenterade, snyggt indragen, och liknande,
men naturligtvis, datorer, webbläsare verkligen inte ge ett dugg
om din kod är väl stil.
Och i själva verket är det helt slöseri att träffa tabbtangenten alla dessa tider
och att sätta kommentarer alla i hela din kod och välja riktigt beskrivande variabelnamn
för om webbläsaren inte bryr, allt du gör i slutet av dagen slösa byte.
>> Så det visar sig vad de flesta webbplatser gör är trots att källkoden för facebook.com,
för cs50.net och alla dessa andra webbplatser på Internet
vanligtvis välskrivet och väl kommenterade och snyggt indragen och liknande,
vanligtvis innan webbplatsen läggs ut på Internet, är koden minified,
varigenom HTML och CSS - något annat vi snart se -
JavaScript-koden kommer vi snart att se komprimeras,
varigenom långa variabelnamn blir X och Y och Z,
och allt detta blanktecken som gör allt ser så läsbar som alla kastas bort,
för om man tänker på det här sättet, får Facebook en miljard sida träffar en dag -
något galet som det - så tänk om en programmerare bara för att vara anal
slå på mellanslag en extra tid bara för att strecksatsen någon kodrad någonsin så mycket mer?
Vad är innebörden om Facebook bevarar att whitespace
i alla byte de skickar tillbaka till människor på Internet?
Att slå mellanslagstangenten när ger dig en extra byte i filen.
Och om en miljard människor går sedan att ladda hemsidan den dagen,
hur mycket mer data har du överförs via Internet?
En gigabyte utan anledning.
Och beviljas för en hel del webbplatser är detta inte en så skalbar fråga,
men för Facebook, för Google, för några av de mest populära webbplatserna
Det finns bra incitament ekonomiskt att göra din kod ser ut som en enda röra
så att du använder så få byte som möjligt förutom att sedan pressas det
med något som zip, som kallas en algoritm gzip,
att webbläsaren gör för dig automatiskt. Men detta är hemskt.
Vi kommer aldrig lära sig något om andra människors hemsidor och hur man designar webbsidor
om vi måste titta på det så här.
>> Så lyckligtvis webbläsare som Chrome och IE och Firefox dessa dagar
vanligtvis kommer med inbyggd utvecklingsverktyg.
Faktum är att om jag går ner hit för att inspektera Element eller om jag går till Visa, utvecklare,
och gå till Utvecklarverktyg uttryckligen,
detta fönster längst ned på min skärm dyker nu upp.
Det är lite skrämmande i början eftersom det finns en hel del obekanta flikar här,
men om jag klickar på Elements hela vägen längst ned till vänster,
Krom är uppenbarligen ganska smart. Den vet hur man ska tolka allt detta kod.
Och så vad Chrome gör det rensar upp alla Facebook HTML.
Även om det inte finns blanksteg där, det finns inte indrag där,
Nu märker att jag kan börja navigera denna webbsida desto mer hierarkiskt.
Det visar sig att varje webbsida skriven på ett språk som kallas HTML5 bör börja med detta,
denna DOCTYPE-deklaration, så att säga: <! DOCTYPE html>
Det är typ av ljus och grå där, men det är den allra första kodrad i den här filen,
och det säger bara webbläsaren, "Hej, här kommer lite HTML5. Här kommer en webbsida."
Den första öppna konsolen utöver det råkar vara här, en öppen konsol HTML-tagg,
och sedan om jag dyka i djupare - dessa pilar är helt meningslös;
de bara för presentation skull, de är faktiskt inte i filen -
märka att insidan av Facebooks HTML-tagg, något som börjar med en öppen konsol
och sedan har ett ord kallas en tagg.
Så inne i HTML-taggen är tydligen ett huvud tagg och en body-taggen.
Inuti huvudet taggen är nu en hel röra för Facebook
eftersom de har en hel del metadata och andra saker för marknadsföring och reklam.
>> Men om vi bläddra ner, ner, ner, ner, låt oss se var den är. Här är det.
Detta är åtminstone något bekant.
Titeln på Facebooks hemsida, om du någonsin tittar i fliken i din namnlisten,
är Välkommen till Facebook - Logga in, Registrera dig eller Läs mer.
Det är vad du skulle se i Chrome namnlist,
och det är hur det representeras i koden.
Om vi ​​struntar i allting annat i huvudet, de flesta av tarmar av en webbsida är i kroppen,
och det visar sig att Facebook kod kommer att se mer komplexa
än de flesta saker vi ska skriva en början bara för att det är byggts upp under årens lopp,
men det finns en hel del script-taggar, JavaScript-kod,
som gör webbplatsen mycket interaktiv:
se statusuppdateringar omedelbart med språk som JavaScript.
Det är något som kallas en div, som är en division av en sida.
Men innan vi kommer till den detaljen, låt oss försöka att zooma ut
och titta på en enklare version av Facebook 1,0, så att säga.
Här är det hej, värld av webbsidor.
Det har att DOCTYPE-deklaration högst upp
som är lite annorlunda från allt annat.
Inget annat vi skriver på en webbsida kommer att börja med <! förutom att raden där
och med undantag för något som kallas kommentarer i HTML.
Men för det mesta, allt på en webbsida öppen konsol, sökord, nära fästet.
>> I det här fallet kan du se den enklaste av webbsidor möjligt.
HTML-taggen innehåller ett huvud-tagg och den innehåller en body-taggen,
men märker att det finns denna föreställning om att starta och stoppa taggar.
Detta är starttaggen för HTML, är detta nära taggen eller sluttagg.
Lägg märke till att de är typ av motsatser i den meningen att den nära taggen eller sluttagg
har slash fram detta inuti sig själv.
Samtidigt finns det en öppen huvud tagg här och en nära huvudet tagg här.
>> Det finns en öppen titel och en nära titel tagg här.
Det faktum att jag har lagt titeln på en rad, helt godtyckligt.
Det såg ut precis som det skulle passa fint på en linje, så jag inte bry slå in ett par gånger.
Under tiden kroppen jag strecksats bara vara aldrig så klart.
Observera att HTML är en ganska dum språk.
Faktum tillbaka i dag innan det fanns WYSIWYG-redigerare
och Microsoft Word där du kan säga, "Gör detta djärva, gör detta kursiv,"
skulle du faktiskt skriver lite kommandon i essäer 20 + år sedan
där du skulle säga, "Börja göra denna text fet. Sluta göra denna text fet."
"Börja göra denna text kursiv stil. Sluta göra denna text kursiv stil."
>> Det är vad HTML eller något Markup Language är.
Denna första taggen säger, "Hej, webbläsare. Här kommer lite HTML."
Nästa taggen säger: "Hej, webbläsare. Här kommer huvudet, huvudet på min hemsida."
"Hej, kommer webbläsaren. Här titeln."
Och sedan över här, "Hej, webbläsare. Det var allt för titeln."
Så detta är hur webbläsare känner inte längre visa fler tecken än hej, värld
i namnlisten.
Samtidigt detta säger: "Det är det för huvudet."
Det säger, "Här kommer kroppen Här är själva kroppen." - Bokstavligen, orden hej, världen.
Och detta säger här: "Det är det för kroppen. Det var allt för HTML."
Så webbläsare är ganska dumt.
De läser bara det här uppifrån och ned, från vänster till höger, och göra precis vad de blir tillsagda att göra.
Låt oss faktiskt göra lite exempel här.
Låt mig öppna upp den enklaste av program på min Mac här, nämligen Textredigerare.
I Windows kan du använda Notepad.exe.
Men detta är allt du behöver för att börja göra webbsidor.
Jag ska gå vidare och bara kopiera och klistra in den här koden i denna fil.
Jag ska gå vidare och spara den på skrivbordet,
och jag kommer att spara som hello.html,
och nu filen heter hello.html.
Här är det på mitt skrivbord.
Låt mig nu gå in i en webbläsare och dra filen i webbläsaren.
Och voila, här är min allra första hemsida.
Observera att titeln på fliken hej, världen enligt rubriktaggen,
och märker att hej, är världens i huvudtexten på min webbsida,
och woo-hoo, jag på Internet.
>> Jag är inte riktigt, rätt, för den här filen är inte på Internet.
Det råkar vara på min lokala hårddisk på just vägen.
Men tanken är densamma. Allt vi behöver nu är en webbserver som att ladda upp den.
Men först ska vi faktiskt införa lite mer komplexitet och lite mer stilisering.
Detta är en enkel, om tråkig, webbsida.
Det visar sig att det finns andra typer av taggar vi kan använda.
Till exempel, här i gult har jag infört 2 nya taggar.
Vi kommer inte att spela mycket med dessa idag, men märker att länken taggen
på något sätt ser annorlunda från allt annat.
Länken Taggen tar så kallade attribut,
och ett attribut är något som förändrar beteendet hos en tagg.
I det här fallet är inte det bästa valet av namn, länk, eftersom det är typ av meningslöst,
men den här länken tagg säger i huvudsak inkludera filen som heter styles.css insidan av min hemsida.
Du kan tänka på detta som analogt med C: s direktivet # include.
Styles.css hänvisar till ett annat språk helt och hållet att vi inte kommer att spela med i dag,
men det är för estetik: teckenstorlekar, färger, stoppning, indrag, marginaler,
och alla den typen av estetik detaljer.
Samtidigt är skripttagg funktionellt likartade,
men i stället inkluderar CSS att språket innehåller den ett annat språk, JavaScript.
Så med andra ord, med dessa 2 taggar jag kommer så småningom att kunna skriva min egen hemsida
men också dra in kod som jag eller någon annan har skrivit
så att vi kan stå på andras axlar, kan vi öva god design,
factoring ut gemensam kod.
Om jag har 10 olika webbsidor, innebär detta att en del av mina estetik
kan vägas ut, ungefär som # include, i en separat fil.
Så vi komma dit.
Men låt oss faktiskt först göra något mer intressant med denna fil.
>> Återigen, detta är bara Textredigeraren. Jag är inte tekniskt på internet ännu, men vi kommer dit.
Jag skulle vilja göra hej, världen lite djärvare än det är.
Så hej, låt oss godtyckligt säga för fet.
Återigen är historien densamma: hej, komma, börja göra denna djärva,
då världen blir tryckt i fetstil, och detta innebär inte vill skriva ut detta i fetstil.
Låt mig gå vidare och spara min fil, gå tillbaka till Chrome, jag zooma in bara så vi kan se det bättre,
och ladda, och du kommer att se att världen är nu i fetstil.
Webben handlar om hyperlänkar, så låt oss gå vidare och göra detta:
Min favorit hemsida är, låt oss säga, youtube.com.
Spara, ladda om. Okej. Det finns ett par problem nu förutom OHYGGLIGHET av webbplatsen.
1, jag är ganska säker på att jag slog in här. Och det gjorde jag.
Jag inte bara trycka Enter, jag också indragen, öva vad vi har predikat om stil,
men min är rätt bredvid värld.
Så varför är det här? Webbläsare gör bara vad du säger till dem att göra.
Jag har inte berättat webbläsaren "Break linjer här. Sätt punkt paus här."
Så webbläsaren spelar det ingen roll om jag slår tillbaka 30 gånger,
det fortfarande kommer att sätta min rätt bredvid värld.
Vad jag verkligen måste göra här är att säga något i stil med , infoga en radbrytning.
>> Och faktiskt är en radbrytning slags konstig sak
eftersom du inte kan verkligen börja flytta till en annan linje, och sedan göra något,
och sedan sluta flytta till en ny rad. Det är typ av en atomär operation.
Du antingen göra det eller inte. Du trycker på Retur eller inte.
Så br är lite av en annan etikett, så jag behöver sortera i både öppna och stänga den
allt på en gång.
Syntaxen för det är det.
Tekniskt sett kan du göra något liknande i vissa versioner av HTML,
men detta är bara dumt eftersom det finns ingen anledning att starta och stoppa något
om du kan istället göra allt på en gång.
Inse att HTML5 inte strikt kräver detta snedstreck,
så kommer du att se läroböcker och onlinematerial som inte har det,
men för bra åtgärd vi öva symmetri som vi har sett hittills.
Detta innebär att etiketten är både öppnas och stängs.
Så nu vill jag spara min fil, gå tillbaka hit.
Okej, så det börjar se bättre ut, förutom på webben jag känner är typ av klickbar,
och ändå youtube här verkar inte leda till någonting.
Det beror även om det ser ut som en länk, vet webbläsaren inte att i sig,
så jag måste tala om för webbläsaren att detta är en länk.
>> Sättet att göra detta är att använda ett ankare tag:
<A href för Hyper referens, som är den gamla skolan sätt att säga en länk,
= "Http://www.youtube.com">
och låt mig flytta till en ny linje bara så det är lite mer lättläst,
och jag ska krympa teckenstorlek.
Jag gjort ännu? Nej, det kommer att bli denna dikotomi.
Denna tagg, ankaret taggen, tar verkligen ett attribut,
som modifierar sitt beteende och värdet av detta attribut är tydligen YouTube URL.
Men märker dikotomin är att bara för att det är den URL som du ska,
det betyder inte det måste vara det ord som du understryker och göra en länk.
Snarare kan det vara något sånt här.
Så jag måste säga sluta göra detta ord en hyperlänk med hjälp av nära ankartaggen.
Notera att jag inte gör det här.
1, skulle detta vara bara ett slöseri med allas tid och det är inte nödvändigt.
>> För att stänga en tagg, nämner du bara namnet på taggen igen.
Du nämner inte något av de attribut.
Så låt oss rädda, gå tillbaka. Okej, voila, nu är det blå och hyperlänkad.
Om jag klickar på den, jag faktiskt gå till YouTube.
Så även om min webbsida är inte på Internet, är det minst HTML,
och om vi låter Internet ikapp, skulle vi hamna faktiskt upp här på youtube.com.
Och jag kan gå tillbaka och här är min hemsida. Men märker detta.
Om du någonsin fått skräppost eller lösenordsfiske,
nu har du möjlighet efter bara fem minuter att göra detsamma.
Vi kan gå hit och göra något liknande www.badguy.com
eller vad det skissartade webbplats är, och sedan kan du säga verifiera ditt PayPal-konto.
[Skratt] Och nu detta kommer att gå till badguy.com, som jag inte tänker klicka på
eftersom jag har ingen aning om var det leder. [Skratt]
>> Men vi har nu möjlighet att faktiskt hamna där.
Så vi egentligen bara börjat skrapa på ytan.
Vi är inte programmering i sig, vi skriver märkspråk.
Men så snart vi spetsa vårt ordförråd i HTML,
Vi ska presentera PHP, en verklig programmeringsspråk
som ger oss möjlighet att generera HTML automatiskt generera CSS automatiskt,
så att vi kan börja på onsdag för att genomföra, säger
vår egen sökmotor och mycket mer.
Men mer om det i ett par dagar. Vi ses då.
>> [CS50.TV]