DAVID MALAN: Velkommen tilbage, alle. Så i går, vil du huske, at vi fokuseret på disse emner her. Så vi havde fire overordnede topics-- privatlivets fred, sikkerhed og samfund; internetteknologier; skyen; og i sidste ende, webudvikling. Havde nogen har båndbredde eller tidspunktet at se lidt John Oliver aftes? Det er faktisk temmelig morsomt, hvis ikke en smule skræmmende. Eventuelle spørgsmål om noget vi gjorde i går? Eventuelle præciseringer? Eventuelle spørgsmål, som du ønsker at gøre sikre, at vi rører på i dag i en eller anden form? Så ren tavle. 

Så hvad er på dagsordenen for i dag? Så jeg troede, vi ville begynde i dag med et kig på, hvad der er generelt kendt som beregningsmæssige thinking-- på risikoen for oversimplificerer, tænker som en computer, måske tænke som en ingeniør, og forsøger at begynde at organisere dine tanker eller til at give dig en bedre fornemmelse af hvad der er involveret i faktisk kommanderende en computer til at gøre noget ved hjælp af programmering. Og vi vil holde det på en smuk højt niveau, temmelig meget engelsk, men prøv at bruge af fortrolig eksempler at formalisere hvordan du ville gå om at løse problemer. 

Og vi vil revidere nogle CS emner, ligesom abstraktion, som kom op et par gange i går, algoritmer og derefter repræsentation. Og det er, hvor vi vil begynde dag på bare et øjeblik. Så vil vi tage et kig på programmering. Vi tager et kig på nogle grundlæggende konstruktioner som du kan være bekendt og måske endda finde helt intuitivt. 

Vi ser, i virkeligheden, ved en prøveprogrammering miljø, der er meget tilgængelige, meget legesyg, og faktisk målrettet for aldre 12 og op. Vi vil bruge et par minutter der og derefter tage tingene til et lavere niveau og faktisk tale om nogle af algoritmer og datastrukturer, så at sige, at programmører bruger typisk at løse problemer langt flere effektivt end du måske kunne undvære dem helt. Så efter frokost, vil vi tage et kig på teknologi stakke, som er lige en fancy måde at sige samlinger af teknologier at du kan bruge til løse et problem. Og vi vil tale om alfabetet suppe af sprog, der findes today-- Java og Python og C ++ og PHP og Ruby og alle mulige andre ting. 

Vi vil tage et kig kortvarigt ved design mønstre. Programmører, over tid, har vedtaget metoder har tendens til at hjælpe dem løse problemer lettere. Når du begynder at se dig selv at skrive den samme slags kode igen og igen, folk formalisere disse gentagelser og tilskrive navne til dem og derefter bruge dem, og fremme dem i sidste ende. Og vi vil snakke lidt om mobile strategier, gerne, hvad vil det sige at faktisk lave en mobil app eller et mobilt website. Gør du det til Android? Gør du det til iOS? Har du gøre det for dem begge? Og hvad er de afvejninger? Og så endelig, vil vi tage et kig web programmering, som er en samlebetegnelse virkelig beskriver enhver tid du skriver software, der er betød at køre på nettet, enten på telefoner eller desktops eller laptops. Vi vil tage et kort kig på databaser og design deri, hvis blot fordi næsten enhver interessant web-baseret program disse dage har en slags database. Ellers ville det bare være statisk indhold. Og en database tillader dig at foretage ændringer over tid, uanset om dig selv eller fra brugere. Og vi vil overveje, hvordan du ville gå om at designe denne database og den slags jargon der kan komme op i en ingeniør drøftelse på en hvid bord når faktisk at gennemføre en app for første gang. 

Vi taler kort om API'er, nyttige tjenester som du kan bruge til at stå på skuldrene af andre, uanset om virksomhederne eller enkeltpersoner, og løse dit egne problemer hurtigere. Og så vil vi fuske måske lidt med JavaScript, et programmeringssprog, der bruges både i browsere disse dage, men også i servere. Og måske vil vi gense, tiden tillader det, nogle af hands-on web ting, vi gjorde i går og integrere de to sammen før vi udsætte. 

Så med at-- hvad er ahead-- er der noget der mangler, at du vil gerne sikre, at vi indsætter og komme ind på på et tidspunkt. Hvis det er fjedre til at tænke på, bringe det op inden længe. Men hvorfor skal vi ikke begynde med en se på beregningsmæssige tænkning. 

Og lad mig foreslå, at beregningsmæssige tænkning er, igen, slags det høje niveau beskrivelse af hvad en datalog kan gøre. Og ja, lad os starte med tre ingredienser, kan gå ind beregningsmæssige tænkning. Dette er blot en måde at beskrive det. Vi kunne sikkert definere dette i en række forskellige måder. 

Men lad mig foreslå, af hensyn til i dag, at verdens problemer, alle verdens problemer, når kontaktet af en datalog kunne ses som hvad vi får call indgange, der brug for at få tilført i, hvad vi vil kalde algoritmer, som derefter afkaster udgange. Med andre ord, hele verden for problemløsning I krav kan destilleres i disse tre ingredienser. Så hvad mener jeg med input? Indgange er lige, hvad du er afleveres for at løse. 

For eksempel, her er en gammel skole problem. Hvis jeg har en telefonbog her og Jeg ønsker at se noget i det, dette er mit input. Jeg har 1.000 eller deromkring sider i en telefonbog. Det er input til mit problem. Og jeg ønsker at finde noget ligesom Mike Smith, så en ven hvis navn og nummer er forhåbentlig i denne adressebog. 

Dette er før de dage af celle telefoner, så jeg kan ikke bare søge efter det. Så jeg er nødt til at gøre det gamle skole og faktisk søgning disse indgange til nogle svar. Og svaret er bare at blive kaldt output. Så input er telefonbogen. Algoritmen er uanset sæt skridt, jeg bruger til at finde Mike Smith. Og output er, forhåbentlig, Mike Smiths telefonnummer. Og dette så ville være lige repræsenterer de fleste problemer til med du er handed indgange og ønsker at producere udgange. 

Så før vi betragter processen hvorved vi kan løse dette problem, finde Mike Smith og noget i den stil, lad os overveje den første og de last-- ind- og udgange. Fysisk, selvfølgelig, input her er en hel masse papir limet sammen i form af en telefonbog. Men computere, af course-- laptops og stationære computere og endda telefoner disse days-- de er elektroniske anordninger. 

Og i slutningen af ​​dagen, hvad er den eneste input til en computer? Tja, det er noget ligesom denne strømkablet her. Jeg sætte det ind i væggen, og Jeg får en strøm af elektroner, som tillader mig at køre maskinen. Eller måske disse elektroner er skabt ved hjælp af mit batteri. Men i slutningen af ​​dagen, det er det eneste går ind i min bærbare computer. Og så meget interessant ting er i sidste ende kommer ud, også ved hjælp af printeren eller skærmen eller audially eller lignende. 

Så hvis alt vi har som vores grundlæggende input til en computer er elektricitet, så bare elektroner går ind og eller ud, og så hvordan kan vi bruge denne indgang til rent faktisk at repræsentere oplysninger? Med andre ord, hvordan får vi fra en simpel strøm af elektricitet at repræsentere faktiske tal eller faktiske bogstaver eller faktiske billeder på skærmen eller faktiske film eller e-mails eller vilkårligt blandt disse højere niveau koncepter, hvis du vil, at der på den slutningen af ​​dagen eller anden måde skal oplagres i dette elektronisk mekanisk anordning ved hjælp af kun de simple ingredients-- elektroner kommer ind og ud? 

Så det lader til, at, I den simpleste form, den eneste form for stater Jeg har i min verden, så at speak-- betingelser i min verden-er enten Jeg har elektroner flyder, elektricitet flyder, eller jeg gør not-- så videre, off. Og lad os formalisere og slukkes, som en datalog kan, med kun 1 og 0. Lad os bare beskrive nogle vilkårlige men konsistent nummer til det. 1 betyder på, 0 betyder slukket. Eller du kan også se det som sande midler på og falske midler. Du kunne også gøre sort og hvid eller rød og blå. Du skal bare to deskriptorer. Og et dataloger ville generelt bare bruge 0 og 1. 

Så hvis det er tilfældet, min eneste alfabet er bestående af 0 og 1'er, hvordan kunne jeg muligvis komme til at udjævne antallet 2 i en computer, endsige tallet 3 eller et bogstav i alfabetet eller et billede eller en film? Hvordan vi slags bootstrap os fra dette grundprincip af 0'er og 1'ere og faktisk repræsentere noget mere interessant? 

Nå, lad os sætte dette spørgsmål på hold for et øjeblik og overveje noget forhåbentlig velkendt, selvom du ikke har virkelig tænkt over det i detaljer i 10, 20, 30, 40, 50 flere år. Det er hvad? Hvordan ville du udtale det? Ikke et trick spørgsmål. En række, men hvad er det? 1, 2, 3 eller 123. Og jeg kunne godt lide, hvordan du sagde 1, 2, 3, fordi det er en måde at få det vist. 1, 2, 3, er det en sekvens af tre symboler. Det er billeder, som vi nu har ord for. Og hvis du slags læst dem alle sammen, en typisk menneske på engelsk ville sige 123. Og det er en slags højere niveau koncept, føles som et rimeligt stort antal. 

Men hvordan kom vi derhen? Nå, kan det være et stykke tid siden du har tænkt over det på denne måde, men tilbage i min dag, jeg slags lært dette som en klumme, 10'erne kolonne, og de 100 kolonne. Så som Lakisa siger, det er 1, 2, 3, men det er også 123. Men hvordan kommer vi fra førstnævnte til sidstnævnte? 

Nå, ville du typisk gør i 100 klumme, jeg har en 1. Så det er ligesom at sige 100 gange 1. Og så i 10 klumme, jeg har to. Så det er ligesom at sige 10 gange 2. I en klumme, jeg har tre. Så det er ligesom at sige 1 gange 3. 

Og hvis jeg tilføjer disse ting sammen, det, selvfølgelig, er 100 plus 10 plus 3. Og åh, det er derfor jeg får denne højere begrebet 123. Det er bare grundlæggende matematik, hvorved disse symboler har vægte til dem, hvis du vil PLACEHOLDER eller kolonneværdier. Og når jeg formere alt ud, jeg får dette nummer. 

Så hvor mange af jer ved, hvordan man taler binary-- 0'er og 1's-- som en computer? OK, perfekt, ingen, eller ingen af ​​jer tror, ​​du gør. Men jeg vil hævde dig faktisk kender dette allerede. Vi skal bare slags nappe vores mentale model en lille smule. Men processen er nøjagtig den samme. 

Lad mig forlade denne ene deroppe og i stedet trække det ned et øjeblik. I en verden af ​​computere, vi har kun 0'er og 1'er. Og så det, der er vil ændre er hvad? Tja, i min menneskelige verden, den decimal systemet lukkes betydning 10, Jeg har, hvor mange cifre på min rådighed? 10, ikke? 0 til 9, selvfølgelig. 

Og det er derfor, vi har den 10 plads og 100 sted. Hvor er det fra? Nå, det er 10 til potensen af ​​0. Det er 10 til potensen af ​​1, 10 til potensen af ​​2, og så videre. Du skal bare holde multiplicere dine kolonner med 10, starter ud med kun 1 i yderste højre en her. 

Så i verden af computere, hvis du kun har binary-- bi betydning 2-- eller 0 og 1'er, vi bare virkelig brug for at ændre bunden af ​​denne matematik. Så med andre ord, nu vil vi bare har en klumme og til-- hvor er det going-- 2 klumme, de 4 klumme, og måske ud. Hvorfor det? Nå, det er 2 0-th magt. Dette er 2 til 1. Dette er 2 til 2, og så videre. 

Så mens her, vi har 1, 10 s, 100 s, 1000 s, 10.000 s, 100.000 s, 1 millioner, og så videre, her vi har 1, 2, 4, 8, 16, 32, 64. Du skal bare holde gange med 2, i stedet for at holde multiplikation med 10. Så nu, hvis målet på hånd er at repræsentere tal kun bruger 0'er og 1-taller, Lad os overveje, hvordan vi kommer derhen. 

Dette er naturligvis, er mønsteret 0 0 0, men hvad nummer begrebsmæssigt betyder det repræsenterer? Nå, 4 gange 0 plus 2 gange 0 plus 1 gange 0, lad os tilføje dem sammen. 4 gange 0 er naturligvis, 0, plus 2 gange 0 er, selvfølgelig, 0 plus 1 gange 0 er naturligvis, 0. Så ah, det repræsenterer nummer vi mennesker kender som 0. 

Nå, nu, lad os meget hurtigt hurtigt fremad. Hvis jeg i stedet ikke repræsenterer 0 0 0, men lad os gøre en 0 1, der kunne være, hvordan Lakisa, tidligere, ville bare udtale det 1 0 1. Men nu, hvordan kan vi tage det til den højere nivellere nummer vi mennesker kunne vide? Så hvad er dette tal? Det er 5, antallet, vi kender som 5. 

Tja, hvorfor er det? Tja, vi kan virkelig slags gå igennem det metodisk 4 gange 1, 2 gange 0, 1 gange 1. Tilføj dem sammen, så dette er 4 plus 0 plus 1. Og det er, ja, fem. Så det bliver lidt kedelig nu gør det aritmetiske igen og igen. Men processen er nøjagtig den samme. 

Det eneste, der har ændret sig i vores verden er, at vores kolonner er 1, 2, 4, 8, 16, og så videre, i stedet for 1, 10, 100, 1.000. Og det er kun fordi vores alfabet har skrumpet fra 0 til 9 til bare fra 0 til 1. 

Så som en lille quiz her, ville hvordan du repræsenterer antallet 7 i binær? 0? Nå, 0, betyder, at du 0 0 0? Sig det igen, Karina. Perfektionere. Hvorfor det? Det er effektivt 4 plus 2 plus 1. Så godt. 

Hvordan vi repræsenterer lidt another-- hvad nummer 2? Tæt på, men baglæns. Så hvad er det? Er 4 plus 1, så det er 5 igen. 

Så what's-- Undskyld, Karina? 0 1 0. 0 1 0 ville være 2, fordi igen, selv hvis det slags ikke springe ud på dig, bare gøre det math. 4 gange 0, 0, 2 gange 1 er 2, 1 gange 0 er 0. Så dette er det nummer, vi kender som to. 

Hvad med nummer 8? Hm? God. Så vi slags brug for en anden pladsholder. Vi har brug for en 0 0 0. Og det er rigtigt af vores slags af gamle skole decimal system. Hvordan repræsenterer antallet 1000? 

Nå, ville du synes at være slags i en hård plet, Hvis bede dig om at repræsentere antallet 1.000, fordi selv hvis du giver dig selv som 9 af disse, 9 af disse, 0 af disse, hvilket er det største antal, du har, har du ikke helt få til 1000. Så hvis du 1000, du bare brug for en anden position, så du kan gøre 1 0 0 0, ergo antallet 1.000. 

Så nu, lad os kort denne slags konceptuelle diskussion tilbage til hardware, hvor igen, input var blot denne lille strømkabel, elektricitet kommer ind og flyder ud. Og så for at for at kortlægges herfra til der, ja, hvad har vi virkelig brug for? Nå, kan du tænke på at være inde i en computer, en hel masse pærer, hvis du vil. De er virkelig kaldes transistorer. Og transistorer er blot skifter kan enten være tændt eller slukket. Så du kan tænke på en transistor, der er på tillader elektricitet at flyde og en transistor, der er slukket at stoppe elektricitet i at strømme. Og i stedet tage løbet lysene her, hvorfor jeg ikke gør den slags af ny skole stil. Så det kan være en 1, en lommelygte være på, kun knap selv. Og dette kan være en 0, og nu er det væk. 

Så ved hjælp af denne fysiske enhed, jeg kan nu repræsentere det binære system. Jeg skal bare have to stater. Det er ligegyldigt, hvad farve det er, eller hvad det er. Alt, der betyder noget, er, at jeg har en stat på og en anden stat fra. Så ved hjælp af min telefon her, hvordan gør jeg repræsenterer antallet vi kender som 0? Eller sagt ækvivalent, hvad nummer jeg repræsenterer nu? 0, da enheden er slukket. 

Og hvis jeg gør dette? Og nu, hvordan gør jeg repræsenterer antallet 2? Kan jeg låne din telefon her, som vi gjorde i går? Så lad os se, så hvis jeg ønsker at repræsentere tallet 2, er dette nummer 2? Ingen. Hvilket nummer er jeg ved et uheld repræsenterer her? Dette er faktisk nummer tre. 

Så hvilken en ønsker jeg at slukke? Den sorte telefon eller-- godt, hvis they're-- sort telefon eller den hvide telefon? Den hvide telefon. Så hvis jeg slå dette fra, og vi line det op herovre, vi har en 1 i 2 sted og et 0 i 1 sted. Og så er jeg nu repræsenterer nummer 2. Og dette, selvfølgelig, ville være antallet 3, for nu begge disse lys er på. 

Og jeg vil stoppe her, men det er indlysende hvis jeg ønsker at repræsentere nummer 4 eller 8 eller højere, Jeg har tænkt mig at brug for flere telefoner. Men det er alt, der foregår. Så hvis du nogensinde har hørt, at indersiden af ​​en-- tak du-- computer er millioner af transistorer, der er bare millioner af bittesmå switche. Og de er ikke lys pærer, der tændes og slukkes, men de enten tillader elektricitet at flyde et eller andet sted, eller stoppe det. Og så der er dine to states-- til eller fra, til eller fra. 

Så vi synes nu at have denne evne at repræsentere denne koncept, vi gerne i selve hardwaren. Men alt, hvad vi har nu, er evnen til at repræsentere tal ville synes. Så hvordan kan vi gå om repræsentere bogstaver i alfabetet, som føles som den næste slags funktion, du ønsker at føje til en moderne computer når du har tal? 

Og ja, hvis du tænker over IT, historisk, computere blev indført virkelig at tjene som regnemaskiner numerisk. Men selvfølgelig, disse dag, de gør meget mere. Selv når de starter op, du typisk se et eller flere ord. Så hvordan kan du repræsenterer ord, hvis alt du har, er, igen, elektricitet ved udgangen af dag, eller ækvivalent 0 og 1'er? 

Ja. Ja, jeg mener, vi slags gjorde denne i går i en eller anden form, hvor på et tidspunkt, Jeg tror, ​​jeg vilkårligt sagt, at hvis vi ønsker at repræsentere bogstavet A, kunne vi bare kalde det en 1. Det var i forbindelse med kryptografi, hvor vi bare brug en slags kode, en slags kortlægning. 

Så måske en vil være repræsenteret som en 1, og B vil være repræsenteret som en 2, og Z er repræsenteret som en 26, for eksempel. Og så er den eneste undtagelse er, at hvis jeg kommer til at indkode breve i mine e-mails eller i mine tekstbeskeder som tal, du alle nødt til at acceptere at bruge samme sæt af konventioner. Og ja, verden har gjort præcis det. 

Der er et system i verden kaldet ASCII, American Standard Til udveksling af information, der er simpelthen en beslutning nogle år siden, at menneskene gjort, at besluttet, at A kommer til at svare til, ikke 1, 2 og 26, og så forth-- det er en lidt different-- men 65, 66, 67. Og jeg vil hente en diagram på blot et øjeblik. Men det er vilkårlig. Men det gør ikke noget at det er vilkårlig. Verden har bare være konsekvent. 

Nu, mere for nylig, der er noget mere avanceret kaldet Unicode, fordi verdens slags realiserede, efter at opfinde computere, at der er mere end godt 256 symboler i verden at vi måske ønsker at repræsentere, især når du indfører Asiatiske sprog og andre symbologies der har brug for mere udtryksfuldhed end du kan passe ind i den tidligste version af denne kode, som blev kaldt ASCII. Så Unicode faktisk tillader dig at bruge mere 0'er og 2. Især du holder høre bytes ord i samfundet og endda kun i går. Og en byte er hvad igen? 

Hvad er en byte? Det er kun 8 bit. Så hvad betyder det egentlig? Tja, det betyder, tidligere, da vi var taler om binær og jeg var ved hjælp af vilkårligt tre bit da vi var taler om binary-- det en plads, de 2 plads, og de fire er sted-- godt, en byte betyder blot, at du taler ikke i enheder af tre, men fire, fem, seks, syv otte, som giver os 8 plads, 16 s, 32 s, 64 s, og 128 s. 

Med andre ord, en smule ikke alle at nyttig en måleenhed, fordi det er ligesom en lille smule oplysning, til eller fra. Så for nogle år siden, verden lige besluttet det er lidt mere bekvemt at tale i form af bytes, otte ting ad gangen. Og så derfor blev født begrebet en byte. Og så har vi otte bits her. 

Og det viser sig, også for lignende årsager, besluttede verden år siden, at repræsentere en ASCII brev, du kommer til at bruge enheder af 8 bit. Så selvom du ikke gør brug for, at mange, du er altid vil bruge 8 bit til repræsenterer et bogstav i alfabetet. Og dette er praktisk, fordi så hvis du modtager en besked, der har en 0 0 0 1 1 1 1 0 efterfulgt af yderligere 1 1 1 0 1 0 0 1, så hvis du modtager 16 bits, verdens kan bare antage, at den første 8 er et bogstav og den anden 8 er et andet brev. 

Er ligegyldigt, hvor mange der er. Det betyder bare, at vi er alle konsekvent når vi fortolker disse bits. Og dette var bare tilfældigt. Det betyder noget, men det gjorde jeg ikke virkelig tænke over, hvad det betyder. 

Så det er en lille hvid løgn. Oprindeligt ASCII faktisk bruges kun 7 bit. Og den ottende bit er kaldet udvidet ASCII. Men pointen er, i sidste ende, det samme. Verden generelt standardiseret på 8 bit. 

Så dette synes at være en smule begrænsende, fordi jeg kun kan repræsenterer kapital A, kapital B gennem kapital Z. Men faktisk ikke, hvis jeg går at-- der er en masse ressourcer online, for eksempel, asciitable.com, dette kommer til at være lidt overvældende i starten. Men jeg vil påpege hvad der er vigtigt her. 

Det bare sker for at være-- og jeg vil walk-- lad os se, om jeg gå over her. Her er, i decimal kolonne, antallet 65. Og på den højre kolonne brev karakter, Chr, er bogstavet A. Og du kan ignorere, for nu, alt i midten. Dette er hexadecimal, oktal, og en HTML-kode. Til dette websted er bare forsøger at kaste en masse oplysninger på dig på en gang. Men alt, hvad vi interesserer os er decimal søjle, og søjlen karakter. 

Så ved denne logik, hvad der er det nummer, verden har besluttet repræsenterer et lille a? Ja, 97. Og bare for at forvirre potentielt svagt, hvad nummer har verden besluttet ville repræsentere nummer 1? Ret, fordi we-- 49, forekommer her, ned i bunden til venstre. 

Nu, hvad mener jeg med det? Så det viser sig, at i edb-systemer, der generelt en grundlæggende forskel mellem et tal og et tegn. En række er det, vi lærte vokser op, når Vi var super unge i folkeskolen. Det er ting, du tæller med. Men en karakter er blot en form, en glyph, så at sige, på skærmen. 

Nu, mennesker vi slags se noget, der ligner dette. Og vi siger, åh, der er nummer to. Men nej, det er bare et symbol, der ser ligesom det, vi kender som nummer to. Og så er der denne grundlæggende forskel mellem de faktiske tal og tegn. Dette er et tal. Men generelt, i forbindelse med en computer, Hvis du i stedet se noget som dette quoted-- og du ikke altid nødt til at se det citerede, men af ​​hensyn til discussion-- hvis du ser anførselstegn omkring nummeret, dette er nu et tegn. Så denne nummer 2 nedenunder hætten indersiden af ​​en computer ville være repræsenteret med et mønster af bits, der repræsenterer antallet 50 i henhold til diagrammet online. 

Men hvis en computer bare ser dette, dette ville være repræsenteret med mønster af bit 0 0 0 0 0 0 1 0. Betragtninger, denne karakter ville faktisk være repræsenteret as-- og nu, Jeg fik at tænke lidt harder-- så dette karakter vil være repræsenteret med 0 0 1-- hvad har jeg brug for her? 0 0 1 1 0 0 1 0. Hvordan klarede jeg gøre det? Nå det er det nummer 50, hvis du formere det ud ved hjælp af disse kolonner, dette er nummer 2, og så det er derfor, der er denne dikotomi. 

Og dette er blot en teaser nu for funktioner der eksisterer i programmeringssprog at vi vil komme ind på kort senere i dag. I programmeringssprog, du har generelt men ikke altid, tingene kalde forskellige datatyper. Med andre ord, en programmer-- når han eller hun skriver, en programmør får at afgøre, hvad format til at lagre sine data. Du kan enten gemme data som rå tal, ligesom nummer to. Eller du kan gemme dem som strenge, eller sekvenser af tegn at du generelt ville udtrykke med citater i dit programmeringssprog. 

Du kan have tingene called-- Jeg forsimpler og kalde dem real numbers-- så tal, ikke er heltal, såsom antallet 2, men tal gerne 4.56. Så reelle tal kan også har decimaler, så det er en anden fundamental stykke data i en computer. Og så kan du endda have andre datatyper stadig. Så det er bare en teaser virkelig for den enkleste af design beslutninger at en programmør kunne gøre under emhætten. 

Så nogen spørgsmål endnu? Så lad os prøve at gøre dette lidt mere reel. Denne hardware er ikke så meget længere bruges. Men de fleste alle i dette rum sandsynligvis voksede op med og stadig bruger harddiske på en måde. 

Selv om de fleste af vores bærbare computere ikke længere har enheder, der opererer på denne måde, i stedet laptops i dag generelt har solid state-drev uden bevægelige dele. Og der har tendens til at være dyrere, desværre, men en lille smule hurtigere og en-- godt, ofte, meget hurtigere, som er en af ​​årsagerne. Og også det ikke så meget varme. Det kan være mindre, så det er generelt en netto positiv. 

Men det giver os mulighed for at kortlægge en lidt mere konkret hvad vi taler om i 0'er og 1 niveau nu til en fysisk enhed. Det er én ting for mig at tale omkring 0 og 1'er i form af min telefon eller abstrakt i form af kontakterne til og fra. Men hvad med harddiske? I din bærbare, hvis du har en ældre en, eller i din stationære computer, eller i hvert fald i servere i dag, hvor du har harddiske, der har en terabyte af plads, 4 terabyte af plads, godt hvad betyder det? 

En harddisk med 1 terabyte plads midler der er 1 billion bytes inde i det på en måde, eller ækvivalent 8 billioner bit indeni. 1 terabyte ville være 8 terabit eller 1 billion bit, som betyder, at hvis du har en hård drev, har du en eller anden måde eller andre en billion 0'er og 1'er inde i den. Og hvis vi bare tage et kig på en vilkårlig billede af en harddisk repræsentant, dette er hvad en hård drev kan typisk ud indeni. 

Det også er lidt ligesom en gammel grammofon afspiller men generelt med flere poster inde, så at speak-- multiple fade, som de kaldes, metal cirkulære diske, og så lidt læsehoved, meget som en gammel pladespiller. Og at læsehoved bevæger sig frem og frem og på en måde læser bits. Og hvad der er på disse fade, selv selvom vi mennesker ikke kan se dem, enten i virkeligheden eller i dette billede, der er bittesmå magnetiske partikler. Og selv hvis du har lange glemt, hvordan elektricitet fungerer, en magnetisk partikel der er opladet generelt har en nordlige ende og en syd end-- så nord og syd. Og så verden bare besluttede for nogen tid siden at hvis en magnetisk protokol væsentlige er justeret sådan, nord-syd, lad os kalde det en 1. Hvis det er i stedet syd-nord, lad os bare kalde det en 0. Og så hvis du har på din rådighed en billion lillebitte magnetisk particles-- og forhåbentlig, hardware opfindsomhed i For at vende dem omkring som du ser fit-- hvis du vil repræsentere en hel masse 0'er, du bare brug for 8 magnetiske partikler alt på linie som denne. Og hvis du ønsker at repræsentere otte 1'ere, du bare brug for 8 magnetiske partikler aligned ryg mod ryg mod ryg på denne måde. 

Hvad mener jeg med det magnetiske partikler? Helt ærligt, alle disse år senere, ting, der stadig kommer efter min mening er denne fyr, hvis du voksede op med denne ting. Dette er en little-- for dem unfamiliar-- en lille barndommen legetøj, har denne hårløse mand her der har alle disse lillebitte sort magnetiske partikler, der kommer med det. Og ved hjælp af den røde pind, som er blot en magnet, du kan slags give ham et overskæg eller øjenbryn eller hår eller noget på ham. Så i virkeligheden, hvis vi ind i for eksempel dette er den slags spil du kan spille med Wooly Willy. 

Og dette er kun at sige, disse er meget større magnetiske partikler end er faktisk på en harddisk, og langt færre magnetiske partikler. Men lad os faktisk se så hvis du har bittesmå magnetiske partikler i en harddisk, hvordan kan du faktisk bruge dem til at repræsentere data. 

[VIDEO PLAYBACK] 

-Den Harddisk er, hvor din pc butikker fleste af sine permanente data. For at gøre dette, at data rejser fra RAM langs med software-signaler, der fortæller harddisk hvordan man opbevarer disse data. Harddisken kredsløb oversætte dem signaler til spændingsvariationer. Disse, til gengæld styrer harddiskens bevæger parts-- nogle af de få bevægelige dele tilbage i den moderne computer. 

Nogle af de signaler styrer en motor, der spinder metal-belagte plader. Dine data er faktisk lagret på disse fade. Andre signaler flytte læse / skrive hoveder at læse eller skrive data på pladerne. Denne maskine er så præcis at et menneskehår kunne ikke selv passere mellem hovederne og spinning fade. Men det hele fungerer på forrygende hastigheder. [END AFSPIL] Og du kan se på hale slutningen af ​​videoen, Der er generelt flere plader. Og så læser hoved er ikke bare at læse toppen. Det er lidt ligesom tre eller fire eller flere læsehoveder at flytte som dette, læsning data samtidigt. 

Så der er en masse kompleksitet og sortering af timing der er involveret i en harddisk. Og de ting er spinning virkelig darn hurtigt, så der er en masse kompleksitet. Men lad os zoome ind lidt dybere og se, hvor er disse magnetiske partikler og hvordan vi får på dem. 

[VIDEO PLAYBACK] 

-Lad Os se på, hvad vi lige set i slowmotion. Når en kort elektrisk impuls sendes til læse / skrive hoved, det vender på en lille elektromagnetisk for en brøkdel af et sekund. Magneten skaber en felt, som ændrer polariteten af ​​en lille, lille del af metalpartiklerne som frakke hver fad overflade. Et mønster række disse små ladede områder på disken repræsenterer en enkelt bit af data i binære talsystem bruges af computere. 

Nu, hvis strømmen er sendt en vej gennem læse / skrive hoved, området er polariseret i en retning. Hvis den aktuelle sendes i den modsatte retning, polariseringen er vendt. Hvordan får man data fra harddisken? Bare vende processen. Så det er partiklerne på disk, der får den nuværende i læse / skrive hoved bevægelse. Sammensæt millioner af disse magnetiseret segmenter, og du har fået en fil. 

Nu kan stykker af en enkelt fil være spredt over et drevets fade, lidt ligesom det rod af papirer på dit skrivebord. Så en speciel ekstra fil holder styr på, hvor alt er. Må ikke du ønsker du havde noget i den stil? 

[END AFSPIL] 

Så bliver hentydet til der, måske, er dette emne fra i går af sletning. Når du sletter en fil, går vi sagde at en computer faktisk gør hvad, når du trækker noget til Papirkurven eller trash bin? Det glemmer bare det. Men 0'er og 1-taller, de magnetiske partikler at ligne rød og blå ting her, eller min arm her, er der stadig på harddisken. 

Og så findes der software-- Norton Utilities og Yesteryear og andre mere moderne software-- der bare vil scanne en hel harddisk søger på alle disse 0'er og 1'er, fordi det viser sig, at de fleste fil formater-- Word-dokumenter, Excel-filer, billeder, video files-- alle har visse mønstre, der er fælles blandt dem. Hver videofil måske være af en anden video, men de første adskillige bits er som regel de samme. Eller de sidste mange bits er som regel de samme. 

Og så med stor sandsynlighed, du kan søge efter disse mønstre. Og selv hvis filen er blevet glemt, du kan sige med stor sandsynlighed, men det ligner et Word-dokument, lader gendanne den og un-glemme det, hvis du vil. Og så er, hvordan du kan gendanne data, der enten har været et uheld slettet eller slettes eller bevidst slettet for uanset formål. 

Derimod sikker sletning gør hvad i forbindelse med et billede som dette? Præcis, gør dem alle tilfældigt. Så det slags flytter nogle af dem ned, nogle af dem op, efterlader nogle af dem uændret, og generelt gør tilfældig støj ud af det, eller bare måske gør alle dem 0'er eller dem alle 1 s. Og at også kan generelt krat dine data væk. 

Så lad os nu vende tilbage til spørgsmålet af beregningsmæssige tænkning, hvorved vi har formlen indgange. Og algoritmer giver du udgange i sidste ende. Vi fokuserer nu på input og udgange, for nu, jeg krav vi har en måde repræsenterer indgange og udgange. Vi bare vil bruge binær. 

Og uanset hvad vi ønsker at repræsentere dag, uanset om det er et tal eller et bogstav eller tusindvis heraf i en telefonbog eller billeder eller film, i slutningen af dagen, det hele er 0'er og 1'er. Og jeg hævder, at selv om dette er en super simpel verden med kun 0'er og 1 s, kan vi bygge os selv op. Og vi har set et eksempel på at med bogstaver hidtil. 

Så lad os nu fokusere på dette midterste ingrediens, en algoritme. Og lad os vende tilbage til dette eksempel på Mike Smith. Så i dette telefonbog, som ganske vist, vi bruger ikke så meget længere, der er et problem, der skal løses. Vi ønsker at finde en som Mike Smith. 

Og hvad kunne jeg gøre for at finde Mike? Tja, jeg kunne bare åbne op denne bog, starte på den første side, og indse, åh, jeg er i et afsnit. Mike er der ikke. Jeg har brug for S sektion for Smith. Så bare holde dreje én side ad gangen. Lad mig foregive, at det er alt hvide sider og ikke gule sider, fordi vi kommer ikke til at finde Mike i de gule sider alligevel. Men jeg er i de hvide sider. Og nu er jeg i afsnittet B. Jeg har stadig ikke fundet ham. Så jeg holde vender en side ad gangen. 

Dette er en algoritme. Det er et sæt af instruktioner for at løse nogle problemer. Med andre ord, se på side, hvis Mike er ikke på det, vende side, og gentagelser igen og igen og igen, ideelt ser ned som du gør det. Så er denne algoritme, denne proces, korrekt? 

Undskyld. Nej, jeg hører nogle nos. OK, men det is-- yeah, det er helt sikkert kedelig. Ligesom, vi vil være her hele dagen, hvis jeg holde udkig efter Mike ved denne hastighed. Men lad mig hævder det er korrekt. Det er dumt, men det er korrekt. 

I slutningen af ​​dagen, længe det måske tage, jeg vil finde Mike hvis han er derinde og jeg betaler opmærksomhed. Og jeg til sidst nå sit side. Og hvis jeg får for langt, hvis Jeg kommer til T-sektion, så kan jeg lidt optimere og bare sige, hm, alle gjort. Jeg behøver ikke engang at spilde tid går til Z s. Men dette er en meget lineær tilgang, hvis du vil, en meget slags venstre mod højre tilgang, en lige linje. Og dens korrekte men langsomt. 

Så jeg husker fra folkeskolen, sortere af en optimering fra en første grader, hvor jeg lærte at tælle ikke af dem, men ved twos-- så 2, 4, 6. Det er A, meget sværere at gør, men i teorien, er det faster-- 8, 10, 12, 14, og så videre. Hvad med at algoritme? Er det mere effektivt? Er det hurtigere? 

PUBLIKUM: Det er effektiv. 

DAVID MALAN: Ja, så det er def-- det er bogstaveligt dobbelt så hurtigt, antager jeg ikke får udløst op med mine fingre. Det er dobbelt så hurtigt, fordi Jeg vender gennem to sider på én gang i stedet for en, men det er potentielt i korrekt, fordi hvorfor? 

PUBLIKUM: Du springe nogle. DAVID MALAN: Right, hvad hvis Mike sker skal sandwiched-- måske når jeg er senere i telefonbogen, Mike sker for at være indlagt mellem disse to sider, og jeg bare blindt springe over det. Så vi har brug for lidt rettelse der. Når jeg ramte T-sektion, jeg kan ikke bare trygt sige, vi ikke finde Mike Smith. Jeg sandsynligvis nødt til at dobbelt tilbage. Eller i virkeligheden, når jeg når nogen opkaldt S-N, i stedet for S-M for Smith, straks, jeg kunne fordoble tilbage, fordi han måske var på den foregående side. 

Men jeg behøver ikke at dobbelt tilbage langt. I teorien, hvis jeg gør det på det rigtige tid, jeg bare gå tilbage en side. Så det er kun at tilsætte et ekstra trin. Så jeg har gået dobbelt så hurtigt, men det kostede mig en ekstra side. Men der føles som en nettogevinst. 

Men det er ikke, hvordan de fleste mennesker i dette rum ville løse dette problem. Hvad ville en typisk person måske en nogle år siden gør, at finde Mike Smith? Ja, ikke finde Mike. Hvad skal jeg gøre? Så få lidt tættere, men jeg gør know-- hvad der er sandt om en telefonbog? PUBLIKUM: Det er sekventiel. DAVID MALAN: Det er sekventiel. Det er alfabetisk. Og så hvis jeg er i M sektion, Mike er helt klart til højre, Jeg kan bogstaveligt talt rive problemet i half-- det er som regel lettere end at-- tåre problemet i halve og smide det væk, så nu har jeg et problem, der er ikke længere 1000 Og den slags, der var hårdt, fordi jeg tror jeg faktisk tore telefonbogen denne ikke time-- 1.000 sider, men 500. 

Så problemet er bogstaveligt halvt så stor. Og det er temmelig overbevisende, fordi med mine tidligere algoritmer, udgave 1 og 2, jeg kun gøre problemet én side mindre, to sider mindre på et tidspunkt. Betragtninger nu, jeg gjorde det 500 sider mindre alle på én gang. 

OK, så nu foreslår Karim at jeg går til højre halvdel. Så jeg har tænkt mig at gå nogenlunde til midten, give eller tage. Og hvis jeg gjorde det matematisk, Jeg kunne gå lige til midten. Og nu, jeg er klar, åh, Jeg er i T-sektion. Jeg faktisk gik for vidt. 

Men jeg kan, igen, rive problem i halve, smide det væk. Og mine bytes ikke så stor. Det er kun, hvad, 256 sider eller 250 sider, give eller tage lige nu. Men det er stadig langt mere end en side eller to sider. 

Og så nu, jeg går omtrent til midten. Åh, jeg gik ikke helt langt nok nu. Så jeg gentager, gentag, gentag, gentage, indtil jeg forhåbentlig efterladt med kun én side. 

Så der inviterer spørgsmålet, hvis jeg startede med omkring 1000 sider, hvor mange skridt tog det mig med version 1 af min algoritme? Tja, hvis Mike er i S sektion, i værste fald, det er temmelig tæt på slutningen af ​​alfabetet. Så hvis telefonbogen har 1.000 sider, Jeg finder Mike inden 1.000 sider, give eller tage. Måske er det ligesom 800 eller deromkring, men det er temmelig tæt på 1.000. 

Betragtninger, i den anden algoritme, hvor mange side vender maksimalt kunne jeg kræver at finde Mike Smith? Der er 1.000 sider, men jeg er gør dem to ad gangen. Right, så max ligesom 500ish, fordi hvis jeg går igennem hele telefonbogen, på hvilket tidspunkt, kan jeg stoppe. Men jeg kan barbere et par af bare stopper ved T-sektion. Men det er i værste fald 500 sider. 

Så hvor mange gange kan jeg opdele en 1,00o-side telefonbog i halve igen og igen og igen-- fra 1.000 til 500 til 250 til 125? Hvor lang tid før jeg ramte en side? Ja, det er omkring 10. Afhængigt af afrunding og sådan, det er omkring 10 sider i alt behov for at blive vendt eller telefonbøger skal rives. 

Så det er temmelig stærk. Vi startede med en 1.000-siders problem i alle disse tre historier. Men i den første algoritme, det tog mig, værste fald, 1000 side vender sig for at finde Mike. Anden algoritme, 500 sider for at finde Mike. Tredje algoritme, til 10 sider finde Mike. Og det er endnu mere kraftfuld når du tror om sortering af en modsat scenario. Antag, at telefonen selskab næste år måske fusionerer to byer sammen, og telefonbogen er pludselig denne tykke, i stedet for dette, der, så 2.000 sider i stedet for 1000. Nå, min første algoritme søger Mike Smith i en 2000-siders telefonbog, værre tilfælde, det vil tage hvor mange side vender næste år? 

Telefonbog er 2.000 sider, so-- godt, ikke mere en. Hvis telefonbogen er dobbelt så tyk i den første algoritme, første algoritme, 2000, ikke? I værste fald, Mike er virkelig tæt på afslutningen af ​​bogen, så det er 2.000 sider sving. Anden algoritme går af toere, ligesom 1.000 sider. 

Men hvad med i min tredje og seneste algoritme? Hvis telefonen selskab fordobler antal sider fra 1000 til 2000, hvor mange flere gange behøver jeg rive den bog i halvdelen at finde Mike? 

PUBLIKUM: Bare en. 

DAVID MALAN: Bare en mere, fordi med en side tåre, Jeg kan bogstaveligt talt opdele og erobre, om man vil, dette problem i halve taking en massiv bid af det. Og så dette er et eksempel på effektivitet og velsagtens en algoritme med, som vi alle er slags intuitivt bekendt. Men det er lige så korrekt som mine andre algoritmer med denne tweak for den anden algoritme, men det er så meget mere effektiv. 

Og i virkeligheden, hvad en computer videnskabsmand, eller til gengæld en programmør, ville typisk gøre, når du skriver kode er at forsøge at finde ud af, okay, jeg vil ikke have min Programmet bare at være korrekt, Jeg vil også det at være effektiv og løse problemer godt. Forestil dig i den virkelige verden i dag, ligesom Google indekserer, søgninger ligesom milliarder af sider, tænk hvis de anvendes den første algoritme til at finde katte blandt en milliard Og den slags ser på den første side i deres database, den anden, den tredje, bare at kigge for en kat, på udkig efter en kat. Det er temmelig darn langsom det synes. De kunne i stedet bruge noget kaldet binær søgning, som er ingen coincidence-- bi betyder to, vi holde dividere noget i to, i half-- de kunne bruge binær søgning og måske finde katte endnu hurtigere, eller hvad det er, du søger efter. 

Og helt ærligt, er der endnu mere avanceret algoritmer at gøre meget mere end blot dividere ting i halve for at finde oplysninger hurtigt. Og vi vil snakke lidt om dem efter frokost i dag. Så lad mig bare prøve at repræsentere dette. Vi behøver ikke at gå ind i enhver matematik eller faktiske tal. Vi kan tale om dette i det abstrakte. 

Men lad mig bare foreslå, hvis du havde en diskussion nu med ingeniørerne foreslå denne algoritme og du forsøger at gøre en beregnet beslutning, fordi måske den ingeniør siger til dig, du hvad, jeg kan gennemføre en lineær søgning i som to minutter. Så nemt. Binær søgning er ikke så fancy, men det vil tage mig ligesom 10 minutter, så 5 gange så lang. 

Der er en handel her, selv i form for at beslutte, hvad software til at skrive. Skriver du enklere algoritme, der vil bare tage dig to minutter? Eller har du bruge mere tid, 10 minutter, skrive mere avanceret algoritme? Hvordan afgør den slags spørgsmål? Eller du kunne gøre det lidt mere virkeligt. Jeg fortæller min chef det kommer til at tage mig ene uge eller 10 uger at gennemføre software på denne måde, hvordan kan du beslutte, hvilke algoritme til grønt lys? Karim? 

PUBLIKUM: Publikum, jeg gætte. 

DAVID MALAN: Publikum. Hvad mener du med publikum? 

PUBLIKUM: Hvis det går skal anvendes af brugerne der [uhørligt] af brugere [uhørligt]. Men hvis det er noget, du er bare gør for dig selv at lette et problem, [Uhørligt] hurtigere. DAVID MALAN: Ja, det er hurtigt og beskidt er en god måde at beskrive det. Faktisk, hvis du er beskriver meget af min tid i Grad skole, hvor ofte gange, Jeg skrev dårlig kode bevidst so-- mindste, det er sådan jeg rationaliseres it-- bevidst så, fordi selvom jeg skrev koden der var forholdsvis langsom til at udføre, Jeg var i stand til at skrive selve koden temmelig hurtige, udgifter kun få minutter eller timer ikke dage. Og det viste sig, jeg lejlighedsvis behov for at sove. Så selv om min kode kræves 8 timer at køre, godt det er fint, Jeg vil bare gå på vågeblus, mens den kører. 

Så på det tidspunkt, jeg troede, det var meget klog, selvom jeg tilsyneladende arbejdet meget langsomt gennem min PhD. Men det modsatte af det er at hvis jeg skulle skrive software for andre mennesker, der betød mere end mig, godt, have dem vente 8 timer til komme tilbage deres søgeresultater er ikke alt, overbevisende. Og så bruge mere tid op foran for at skrive software der er mere effektiv, mere ligesom vores tredje algoritme, formentlig gavner brugerne over tid. Så det er virkelig afhængig løbet tid, hvordan disse omkostninger tilføje op. Hvis du vil skrive software for at bruge det én gang, sandsynligvis lige så godt gøre hurtig og beskidt, som man siger. Bare smide det sammen. Det er kode, embarrasses dig, det er så slemt, men det får jobbet gjort korrekt, selvom det ikke er effektivt. Omvendt du bruger mere tid om noget, får det lige højre. Og derefter afskrives over tid, at upfront omkostninger af tid er nok værd, hvis du holder optimering for den fælles sag. 

Og ja, det er et tema i programmering, eller datalogi mere generelt, forsøger at optimere ikke for den ualmindelige tilfælde men de fælles case-- hvad operation kommer til at ske igen og igen? Hvis du vil have milliarder af brugere, der søger på dit websted, bør du nok bruge de ekstra uger op foran skrive bedre software, således at alle dine brugere gavn. Lad os nu prøve at fange dette til en lidt billedligt, men ikke så meget numerisk. 

Så her er bare en gammel skole diagram. Og lad mig sige, at dette er tid. Og det er ligegyldigt hvad-- faktisk, nej, ikke tid. Lad os sætte det på den anden akse. Lad os sige, at dette er den tid, og dette er størrelsen af ​​problemet. 

Og en datalog kan generelt ringe dette blot n. n er som vores gå til variabel, hvor n er et tal, n nummer, og det er den antal uanset indgange du har. Så i dette tilfælde er n antallet af sider. Så det kunne være 1000 i tilfældet, vi lige fortalt. 

Så tiden kan være enhver måleenhed. Måske, det er anden. Måske, det er dag. Måske, det er ligesom side sving. Betyder ikke noget. Uanset hvad du ønsker at tælle i, at vil være tid eller koste tilsvarende. 

Så med det allerførste algoritme, hvis jeg f.eks havde en 1000-siders telefonbog, Jeg har tænkt mig at tegne en prik der, fordi hvis det er 1.000 sider, tog det omtrent 1000 side vender, give eller tage. Og så hvis jeg havde en 2000-side telefonbog, og jeg har tænkt mig at tegne en anden dot her, fordi det for 2.000 sider, det er ligesom 2.000 sekunder eller side vender eller hvad. Og så når jeg sagde tidligere, er det slags et lineært forhold, det var bevidst, fordi jeg ønskede senere on-- ret nu-- at tegne en streg. Det er lidt af en lige line forhold. Hældningen er 1/1, hvis du vil. 

I mellemtiden er den anden algoritme sagde, hvis du har fået 1.000 sider og du brugte den anden algoritme, hvor jeg talte med 2 s, dreje to sider ad gangen, skal jeg tegne en prik under eller over min oprindelige prik? 

PUBLIKUM: Under. 

DAVID MALAN: Nedenfor, for som vi har set, det tager mindre tid, halvt så meget tid. Så dot bør være halvt så højt som den anden. Og samme deal herovre, denne prik skal nok være nogenlunde der. Og så min anden algoritme, på samme måde, har en lineær sammenhæng med tiden. Og vi kan trække det som sådan. 

Så nu, den tredje og sidste algoritme er lidt sværere at trække. Men intuitivt, hvis jeg har fået 1000 sider med min tredje algoritme, Det bør kun tage mig som 10 trin. Og hvis jeg har fået 2.000 sider med min tredje algoritme, det skal tage mig ikke 10 trin, men 11, bare en mere. Så vi kun knap kommer til at se dette. 

Og det viser sig, hvis Jeg zoome ind på dette, er jeg vil overdrive for effekt, formen af ​​denne linje, i sidste ende, er ikke en lige line-- fordi, ja hvis det var, det ville se mere som others-- det er faktisk en buet linje at hvis vi zoomer ind, går til at se meget mere som denne. Det-- godt, OK, ignorere denne del. Det var min pen går af vinkel. Det er en buet linie, der altid er stigende, altid, altid, altid stigende, men kun lige knap. 

Og så over tid, har du en forhold, der er mere som dette. Det ser næsten lige. Men det er stadig så langsomt stigende. Men for næsten alle punkter langs din x-aksen, vandret akse, Det er lavere end de andre linjer. 

Så det kunne være en sammenhæng n, hvor hvis du har n-sider, tager dig n sekunder. Dette kan være et forhold n / 2. Du har n-sider, det tager du n / 2 sekunder, halvt så mange. Og dette er en logaritmisk forhold, der hvis du husker, log basis 2 af n fanger denne form for vækst, så at sige. Så dette er den slags hellig gral blandt de tre af disse her, fordi det er bare så meget mere effektiv, men velsagtens mere komplekse at implementere. Nogen spørgsmål? 

Jamen så lad mig gøre det, så lad mig åbne en tekst vindue bare så vi kan forsøge at formalisere noget her. Så lad mig gå videre nu, og gennemføre denne algoritme til at finde Mike Smith i kode, hvis du vil, pseudokode kode. Jeg har ikke tænkt mig at bruge Java eller C ++. Jeg skal bare bruge slags Engelsk-lignende syntaks, som vi ville principielt gør pseudokode kode. Her har jeg et tomt vindue. Og jeg siger trin 1 i den meget første algoritme er afhente telefonbog. Trin 2 er åben bog for første side. Trin 3 vil være se på side for Mike Smith. Hvis på side, kalder Mike. ellers turn side og gå til trin 3. Udført, lad os sige. 

Og så det er ikke helt perfekt, som vi vil se i et øjeblik. Men lad os overveje, hvad begreber, jeg har introduceret her. Så trin 1 og 2 og 3 er temmelig meget verber. De er udsagn, actions-- gøre dette. Og så i en programmering sprog, ville vi generelt kalde dem erklæringer eller funktioner eller procedurer, kalde dem en række ting. Men de er bare actions-- gøre dette. 

Trin 4 er fundamentalt anderledes, fordi det er slags stille et spørgsmål. Det siger vi er slags på en gaffel i vejen. Hvis Mike er på siden, så ring ham, så drej til venstre, hvis du vil. Og hvis ikke, gå tilbage til nogle andre page-- eller rettere, undskyld, gå tilbage til et andet trin, der inducerer en slags looping konstrukt. Og vi gør det igen og igen og igen. 

Og faktisk, ved du hvad? Ja. ellers hvis i slutningen af ​​bogen stop. Så vi har brug for sådan en tredje tilstand, fordi du kan ikke holde dreje siden annoncen nauseum, fordi i sidste ende, vil jeg ramte slutningen af ​​bogen. Og en fejl i et program kan være ikke foregribe dette scenario. Og så vil jeg bare indset, åh, vent et minut, jeg har brug for en tredje scenarie. Hvis jeg er ude af sider, jeg bør virkelig bare stoppe. Ellers er det udefineret. Hvad vil der ske, hvis jeg holder siger vende siden og gå tilbage, Dette er, når computere fryse eller nedbrud, når du rammer nogle uforudsete situation som. 

Nu, hvad Mike Smiths tredje algorithm-- afhente telefonbogen, åben bog at first-- til nej, ikke første side denne gang, at middle-- åh, ja, det havde være den anden algoritme. Lad os bare springe til den tredje. 

PUBLIKUM: Åh, jeg er ked af. 

DAVID MALAN: Det er fint. Lad os bare springe til third-- åbne til midten og nu ser for Mike Smith. hvis på side, kalder Mike. Og hvad gør vi ønsker at sige her? ellers hvad? Vi kan udtrykke dette i en række forskellige måder. Der er ingen rigtige svar. OK, hvis ikke igen, men vi er nødt til være-- OK, vi ønsker at dele i to, men ønsker vi at gå til venstre eller gå til højre? Hvordan kan vi udtrykke, at begrebet? Tja, i Mikes tilfælde, ja, det er fair. Men OK, så det er faktisk en god pointe. Det er fint. Vi vil holde gå med denne logik. Så-- 

PUBLIKUM: Mindre end halvdelen. DAVID MALAN: Ja. Så andet, hvis side er, vil vi sige, mindre end Smith, til venstre for Smith, then-- lad os se, er dette vil komplicere? andet, hvis side kommer før Smith, tåre i halve, smider hvoraf halvdelen? 

PUBLIKUM: Jeg troede der var [uhørligt]. 

DAVID MALAN: jeg hører begge svar. 

PUBLIKUM: Venstre. DAVID MALAN: OK, kaste væk venstre halvdel, som Lakisa sagde tidligere, den venstre halvdelen, så jeg slags bare ønsker at gå at-- jeg gå til højre. Eller ækvivalent, og jeg lavede en lille lidt af et rod af starten her, Jeg ønsker effektivt at gå til trin 2 igen, hvor åbne for middle-- eller open-- yeah, lad os bare sige, sider til midten. Og det løser det. Det er ikke længere en bog. Det er bare halvdelen af ​​en bog, så åbne sider til midten. 

else-- var der næsten. Trin 6, andet, hvis side kommer efter Smith, rive i halve, smider højre halvdel, derefter gå til trin 2. ellers holde op, en fjerde scenario, hvis vi har ingen sider tilbage at vende. Så vi kunne rense det op. Og vi bør rense det op. Dette er meget pseudokode kode, hvis du vil, meget højt niveau beskrivelse. Men det betyder generelt fange ideen. 

Og igen, i dette scenario, vi har begrebet en tilstand, en filial, en gaffel i vejen, hvilket gør en decision-- hvis dette, gå på denne måde, ellers hvis, gå på denne måde, ellers hvis, går den vej. Og dette er en meget almindelig programmeringsteknik at afgøre, hvilken retning at gå, så at sige. Og vi har også en slags af looping struktur, hvor vi laver noget igen og igen. 

Nu viser det sig, meget som i dette eksempel, bliver super præcis er vigtig. Men vi har også set noget at vi holder kalde abstraktion. Hvad betyder det at afhente telefonbog? Vi er bare lidt at tage for givet i dette rum at der har nogle semantisk mening. Alle os bare lidt ved, åh, godt, afhente telefonbogen. Hvad betyder det egentlig? Nå, der virkelig betyder udvide hånd, læne over, udvide fingre, knibe bog mellem fingrene, stå op, træk hånd mod dig. Og vi kunne være virkelig pedantiske om dette, virkelig bliver super præcis om, hvad jeg gør. Men alle disse skridt kollektivt er hvad det betyder at afhente en telefonbog. 

Og så tidligere, da jeg sagde, hver af disse to første udsagn kan opfattes som en fortsætte eller en funktion, virkelig det repræsenterer, hvad vi holde kalde en abstraktion. Det er ligesom et højt niveau konceptuel beskrivelse af et problem, faktisk involverer et par skridt. Og så dette, også er en tilbagevendende emne i programmering, hvorved jeg kunne skrive et program hjælp syntaks ligesom denne-- pick_up_phone_book (). Og så syntaktisk, jeg er vil stjæle noget fra de fleste programmeringssprog. 

Nu, trin 1 ser endnu mere som en funktion, som programmør ville kalde det. Det ligner kode, at nogen har givet et navn til og givet til mig at bruge somehow-- i andre ord, hvad den linje, jeg har fremhævet repræsenterer funktionalitet, der måske Jeg vidste ikke engang gennemføre mig selv. Nogen ældre, klogere end mig allerede regnet ud hvordan du udtrykker begrebet af optagning en telefonbog. Og det er ligesom de fem trin jeg lige raslede off, off toppen af ​​mit hoved. 

Men han eller hun allerede gennemført dette, gav disse flere trin et navn, pick_up_phone_book. Og parentesen er lige hvad de fleste programmører gøre i slutningen af ​​udsagn som dette. Jeg nu kan stå på hans eller hendes skuldre og aldrig igen, tænke over, hvad det betyder at hente en telefonbog. Jeg kan bare sige, afhente telefonbogen. Og det er præcis, hvad alle af os mennesker gjorde her. 

Da vi var sandsynligvis en år gamle, 2 år, nogen havde at lære os, hvad det betød at afhente en telefonbog. Og lige siden da, vi har abstraheret væk fra dem meget uinteressant mekaniske trin. Og vi bare have en intuitiv forståelse af hvad det betyder at afhente en telefonbog. 

Og du kan ekstrapolere nu til mere kompliceret things-- konstruere en bygning. Ligesom, at nogle mennesker, der faktisk har betydning. Til entreprenører, arkitekter, der har nogle betydning. Og de ville vide hvad de skal gøre, hvis Jeg sagde, gå opføre en bygning. 

Men de fleste af os i rummet ikke kunne beskæftige sig med at abstraktionsniveau. Du er nødt til at fortælle os gerne gå få skovlen og gå få betonen og søm træstykkerne sammen, og hvad der ellers er involveret i opbygningen af ​​en bygning. Og det er, fordi vi ikke har endnu blevet programmeret til at forstå hvad det betyder at opføre en bygning. Vi har ikke den abstraktion. Vi har ikke denne funktionalitet. 

Og så, hvad du vil se i programmeringssprog i almindelighed især mere moderne sprog, ligesom Java, PHP, Ruby, og Python, de er meget mere moden end ældre sprog, ligesom C og C ++ og endnu andre. Og så de kommer med mere funktionalitet indbygget. Mere kode er blevet skrevet af folk i fortiden at vi nu kan ringe eller indkalde eller bruge, da jeg antyde på dette fremhævede linje her. Og så selvom vi ikke taler om programmeringssprog per se, bare pseudokode kode, alle af ideer er stadig i den diskussion. Og det viser sig præcision er super vigtigt, som er abstraktion. Og lad os prøve at kommunikere, at som følger. 

Jeg ved et uheld kunne have ødelagt dette ved at blinke et dias på skærmen for tidligt. Men lad mig bede om en modig frivillig, hvis du ikke har noget imod at komme op. Du ville være foran kamera, hvis du er OK med det. Ville nogen gerne komme op og give instruktioner til dine kolleger her? Bare nødt til at komme herover og stå over her og sige nogle ord. 

Victoria smiler mest og undgå mine øjne mest. Ville du være villig til at komme videre op? OKAY. Og hvis alle andre på din sæder kunne tage ud et stykke papir skrot, hvis du vil. Foret papir er fint. Kom rundt på denne måde. Eller nogle af det papir, du fik i går, bare noget blankt ark af papir, hvis du kunne. Og hvis du ikke har nogen, bare spørge din nabo, hvis du kunne. 

Så for øjeblikket, for dette eksempel, Victoria kommer til at spille rollen som en programmør, en ingeniør, som skal programmere jer alle, som computerne, til at gøre noget. Og vi vil se, hvad antagelser du beslutter at gøre. Vi vil se, hvordan præcist hun vælger at være. Og hvis denne demonstration går pædagogisk godt, masser af fejl vil blive foretaget, at vi så vil bruge at som en mulighed for diskussion. Men udfordringen for du skal være at undgå disse fejl, være en god programmør. Og så udfordringen ved hånden, hvis du ville kunne lide at gå over her, er foran Victoria på skærmen her-- og forhåbentlig ingen af ​​jer huske dette, når jeg flashed på skærmen. Og ikke vende rundt på alle, fordi der er en anden skærm i dette rum at jeg kan slukke. Så du skal ikke vende rundt. 

Foran Victoria er, at samme skrig. Og hendes job er nu at fortælle dig alt på dit stykke papir, hvad at tegne. Og vi vil se, er baseret på verbale instruktioner alene, computerkode, om man vil, hvordan præcis dine tegninger are-- dine implementeringer er. Giver mening? 

PUBLIKUM: Ja. DAVID MALAN: OK, udføre. 

PUBLIKUM: Tegn en firkant. 

[LATTER] 

DAVID MALAN: Og nej spørgsmål kan blive bedt om. Kan kun gøre, hvad du får at vide. Åh, og hvis du har nutidens dias åbne i en fane, skal du ikke se på din fane. OKAY? 

PUBLIKUM: OK, tegne en cirkel. En slope-- kan jeg sige hældning? DAVID MALAN: Op til dig. PUBLIKUM: En skråning. Og en trekant. 

DAVID MALAN: Okay. Og blive her for et øjeblik. Og jeg har tænkt mig at komme rundt om et øjeblik. Og ingen grund til at sætte jeres navne på det. Lad mig komme rundt og samle dine tegninger, hvis du ikke har noget imod at rive dem ud. 

Her er hvad vi fik tilbage. Jeg vil projicere den på skærmen. Jeg ser en firkant, en cirkel, en skråning, og en trekant. Så det var et svar der. Og let's-- hovsa. Tak. Her er en anden sortiment, og en bag det. 

Så de alle synes at fange ånden. Tak. Der er en anden, og her er en anden. Hældningen fortolkning er en lidt anderledes, lidt krumme. Og det tætteste, enten på grund af vidunderlige specificitet, som du har beskrevet, eller måske du slags så det før, det er faktisk hvad Victoria var faktisk beskriver. 

Men nu, dem af jer der fik det ikke helt rigtigt, lad os tilbyde nogle indvendinger her. Så Victoria først sagde tegne et kvadrat. Og nu, kan vi antage af hensyn til dag at alle kender hvordan man tegner en firkant. Men det er ikke helt klart, ikke? Hvor ellers kan du få tegnet en firkant, eller hvor kan være nogle af de uklarheder her til computer? PUBLIKUM: Placering og størrelse. DAVID MALAN: Beliggenhed, right? Alle jer havde et papir på nogle form, generelt rektangler, men lidt forskellige størrelser. Men du sikkert kunne have trukket, hvis du ønsker, en kæmpe firkantet, måske en lille firkant. Måske var det roteres. Jeg tror ikke, vi så, at. Men det kunne have været mere diamant ligesom men stadig ikke desto mindre, matematisk en firkant. Så det var velsagtens tvetydig. 

Så sagde hun, tegne en cirkel. Nogle af jer har draget den ved siden af det, hvilket ikke er urimeligt, fordi mennesker tendens til at tænke eller læse højre til venstre på de fleste sprog, så ikke en dårlig gæt. Men denne cirkel kan have været inde på pladsen, kunne have været omkring firkantet, kunne have været et andet sted på arket, så velsagtens tvetydig. 

Slope kunne have været måske tage de fleste friheder verbalt med, hvad det betyder. Og nogle af jer fortolket det som en bølgelinien eller en lige linje eller lignende. Og så trekant, også kunne have blevet orienteret i en række forskellige måder. Så kort, selv med noget, du blik og du er ligesom, wow, så enkel, et barn kunne tegne dette, vel ikke virkelig, medmindre du er super, super overbevisende og fortælle computeren præcis, hvad de skal gøre. Så hvis vi kunne, hvis du har et andet ark af papir, lad os prøve dette endnu en gang. Og jeg har tænkt mig at give Victoria én andet eksempel på skærmen her. Og igen, ikke vende rundt og ser ikke på dine dias. Og jeg vil give hende et øjeblik at tænke over, hvordan til at beskrive dette. Lad dem ikke se frygten i øjnene. 

[LATTER] 

Og igen, denne gang gearing nogle af disse grillbarer og forsøge at få næsten alle mindst det rigtige svar. 

PUBLIKUM: OK, tage en stykke papir, se i midten af ​​det stykke papir. I midten af ​​det stykke af papir, tegne en terning. 

[LATTER] DAVID MALAN: Hvad har vi lært? Vi var så tæt på. OK, gentag hvis du kunne, for alle. 

PUBLIKUM: I midten af ​​den stykke papir, trækker en genstand, som ligner en terning. 

DAVID MALAN: OK, det er alt hvad du kommer til at arbejde med. Tillad mig at være analytisk og ikke så meget kritisk, men for at gøre kravet at Victoria afgjort ser ud til at tænke i meget højt niveau abstraktioner, som er ikke urimeligt. Fordi ellers ville vi alle være temmelig dårligt fungerende, hvis vi skulle være lige så præcis med alt, hvad vi gør i verden. 

Men at sige gå til middle-- I troede vi var på sådan en god track der, ligesom gå til meget midterste på siden, og derefter tegne en terning. Så hun tænker i abstraktioner, fordi hun stadig ser hvad der er på skærmen som faktisk en terning. Men der er så mange muligheder for fortolkning der. Og i virkeligheden, der er så mange andre måder, du kan udtrykke at, som jeg vil foreslå i et øjeblik. Så her har vi en inkarnation af den picture-- whoops-- én inkarnation af billedet, så en lille tre dimensionalitet til det, hvilket er rart. 

Her er en anden, hvor du har den samme, selvom det er lidt af en åben kube. Nogle folk tog det lidt mere flad, todimensionel. Og det er fint. Så der, faktisk i midten af ​​papiret. Denne ene jeg tror du vil lignende, for hvis vi går her, dette er, hvad hun beskrev. Så nu, lad mig foreslå hvordan ellers vi kan beskrive denne situation. 

Tilbage i dag, en af ​​de mest mere almindelige måder at lære programmering var at skrive kode, skriver linjer af instruktioner, at kontrolleret lidt skildpadde på skærmen. Logo og andre varianter af denne var navnet på sproget. Og skildpadden levede i en verden. 

Så formoder denne rektangulære pladsen er hans verden. Og du ville starte med assuming-- I ikke rigtig ved hvordan man tegner skildpadde, så lad os gøre det sådan her. Og så han har en shell og så måske nogle fødder. Så har du måske denne lille tegn på skærmen. 

Og formålet med dette programmeringssprog var at tvinge skildpadden at gå op, ned, venstre, højre og til at sætte hans pen ned eller afhente sin pen op, så han kunne faktisk tegne på skærmen i denne meget flad rektangulær verden. Så hvor jeg tænkte du måske være at gå, og hvor du skal overveje dykning ned til mentalt når der beskriver instruktioner mere generelt Jeg vil hævde, sættes din pen ned i middle-- og vi vil slippe af med den skildpadde, fordi jeg kan ikke rigtig holde tegning ham meget godt. 

Og nu, hvor ellers kunne Jeg siger tegne en terning? Nå, vi kunne sige noget som uafgjort en diagonal linje nordøst, for eksempel, eller i en 45 graders vinkel opad. Og der kunne have fået mig her. Og jeg er temmelig langt fra en terning. Men nu, kunne jeg sige noget lignende dreje 90 grader til venstre og trække en linje af samme længde nordvest. Og jeg kunne fortsætte med lignende retninger. Og det kommer ikke til at være let. Og helt ærligt, vi sandsynligvis ville har været her i fem minutter. Men måske vi ville have fået til noget, der ved udgangen af ​​dag, ender med at blive en terning, men vi dykkede inde i denne abstraktion at gøre det på sådan en lav niveau, du ikke kan virkelig se, hvad du laver, indtil hele ting er faktisk der på siden. Og så dette er et generelt princip, igen, af programming-- denne idé af abstraktion. Det er så vidunderligt kraftfuld, fordi igen, hun netop sagde, tegne en terning, som alle os temmelig meget ville grok meget hurtigt. Vi ville bare forstå, OK, tegne en terning. Vi kan ikke vide orienteringen, så vi kunne være lidt mere præcis, men vi kan generelt billede eller ved, hvad en terning er. Og det er nyttigt, fordi hvis hver gang du satte sig som programmør på tastaturet til at skrive kode, hvis du skulle tænke på sådan et lavt niveau, ingen af ​​os nogensinde ville få noget gjort. Og helt sikkert, ingen af ​​os ville nyde processen med at skrive kode. Det ville være som at skrive i 0'er og 1'er, som ærligt talt var ikke så længe siden mennesker blev skrive kode i 0'er og 1'er. Og vi kom meget hurtigt op med disse højere niveau languages-- C ++ og Java og andre. 

Så lad os prøve en gang til bare for at flip bordene, så vi alle har mulighed for at tænke i stedet på samme måde. Kunne vi få en mere frivillig denne tid til at komme op til tavlen og tegne, ikke recitere? Ja, OK. Ben, kom op. Og, Ben, i dette tilfælde, når du står over for bestyrelsen, ikke ser til venstre, ser ikke rigtigt. Kun gøre, hvad jeres kolleger her fortælle dig. Og for alle andre i værelse, du nu er programmør. Han er computeren. Og det billede jeg har valgt her på forhånd er denne ene her. De er bare-- de tænker af en sjov vittighed er alt. 

Så ville der nogen gerne frivilligt den første instruktion eller erklæring om, at skulle kommando Bens pen? Og vi vil gøre det kollektivt, måske en instruktion fra hver person. Undskyld? 

PUBLIKUM: Tegn en cirkel. DAVID MALAN: Tegn en cirkel er den første, jeg hørte. 

PUBLIKUM: Op top. 

DAVID MALAN: Op top. OK, vi kan lade dig slette, fortryde. Og nu, en anden. Dan, du ville være rare tilbyder den næste instruktion? 

PUBLIKUM: Sure, tegne centrum af bunden af ​​cirklen, med en small-- lidt lille mellemrum fra det, tegne en lige linie ned til tre fjerdedele af vejen ned bestyrelsen en lille vinkel til venstre. 

DAVID MALAN: God. 

PUBLIKUM: Let vinkel. 

DAVID MALAN: Fortryd, ctrl-Z. OKAY. Andrew, du ønsker at tilbyde op næste instruktion? 

PUBLIKUM: Selvfølgelig. Fra bunden af ​​denne linje, en yderligere mindre angle-- whoops-- måske omkring en tredjedel af længden [uhørligt], lille vinkel nedad og gerne en tredjedel af længden af ​​[uhørlig]. Så ja, fra dette punkt, tegne en linje en tredje af længden af ​​den tidligere linje længere mod venstre. 

DAVID MALAN: At OK? Lige linje, det er OK? OK, Olivier, du ønsker at tilbyde op den næste? 

PUBLIKUM: [uhørligt] fra bunden af ​​cirklen, [uhørlig]. Tegn på højre side af [uhørligt] centimeter. 

[LATTER] 

DAVID MALAN: Jeg tror, ​​du kommer til at nødt til at konvertere det er inches her. 

PUBLIKUM: Stop. 

[LATTER] 

DAVID MALAN: OK. [? Ara,?] Du ønsker at tilbyde op den næste? 

PUBLIKUM: Tegn en [uhørligt] den øvre [uhørligt] det samme. [Uhørligt] cirkel, tegne til [Uhørligt] og tegne [uhørligt]. 

DAVID MALAN: OK, ikke mere fortryde. Lad os gøre en eller to flere instruktioner. Chris, du ønsker at tilbyde en? 

PUBLIKUM: Nederst af cirkelen [uhørlig] trække en lige linje slopping nedad til venstre [uhørligt]. 

DAVID MALAN: OK. Andrew? Vi did-- Karim? 

PUBLIKUM: Begyndende fra højre linje, enden af ​​den venstre linie, bunden, du kommer til at gå lige omkring den samme længde som denne linje du er på, tegning til højre [uhørligt]. [Uhørligt] grader, så [uhørligt] grader på højre side. 

DAVID MALAN: Okay. Lad os holde pause. Må ikke vende rundt endnu. Lad os holde pause, og lad os se prøve en anden forsøg før vi afsløre for Ben hvad han har tegning. Kan du shuffle Ben til den right-- eller faktisk, nej, lad os bare give dig andet bord, endnu bedre. Så skulle nogen nu gerne at tage mere af den fremgangsmåde at Victoria tog tidligere, hvor vi taler i en højere abstraktionsniveau og på bare en sætning eller to beskrive Ben hvad at tegne uden komme ind ukrudt, så at sige, på dette et lavere niveau? Victoria. [LATTER] PUBLIKUM: Tegn en figur af walking mand. Og hans ben og arme nødt til at være den højre side. 

DAVID MALAN: OK, det er alt, du får. Okay. Hvorfor skal vi ikke afsløre for Ben, hvad han gjorde. Så en runde af bifald. Det var den sværeste måske. 

Så selv om vi taler i temmelig dumme vilkår om bare at tegne billeder, forhåbentlig du kan virkelig sætte pris på graden af udtryksfuldhed, der måtte være nødvendige for at fortælle en computer, hvad de skal gøre. Og i virkeligheden, det faktum, at Ben var i stand til at trække dette så hurtigt er slags bevis på at bruge en sprog, måske et højere niveau version af engelsk, der tillader ham at bare bruge ord, eller høre ord fra Victoria, der tillader ham disse abstractions-- bare trække en figur til fods til right-- den slags har nogle semantisk mening til det, der ikke er næsten lige så indlysende, når du bare siger, sætte pennen ned, tegne til højre, trækker til venstre. 

Og så dette, også er meget almindelig i programmering. Dette ville siges at være som en meget lavt niveau sprog, programmering i 0'er og 1'er, hvis du vil. Og det ville være et højere niveau programmeringssprog i Java, eller sådan noget. Lidt af en forsimpling, men det er det lidt ligesom følelsesmæssige følelsen af, at du føler, når ved hjælp af en slags ting eller en anden. Lidt af frustration her af behovet for en sådan præcision, men muligheden at være lidt løsere med fortolkningen her. Men selvfølgelig, bugs kan opstå som følge heraf. 

Hvis du gerne vil på home-- vi vil ikke gøre denne ene i class-- men hvis du gerne vil bringe kampen, Jeg troede, vi ville dykke ned i dette. Så hvis du gerne vil spille dette spil med dine andre væsentlige eller børn eller lignende, du kunne nyde det så godt. 

Så lad os gå videre og se på en sidste ting her for beregningsmæssige tænkning. Og det bringer os til John Oliver, ikke for klippet du måske har set i aftes, men til en noget nyligt nummer. For et par måneder tilbage, Volkswagen tog ganske lidt af flak hvad grunden, hvis du kender? Hvad har de komme i problemer for? 

Ja, så emissions-- de forsøgte at slå emissioner tests med væsentlige at have deres biler forurener miljøet mindre når deres biler blev testet og forurene miljøet mere når bilerne ikke blev testet. Og hvad er mere og mere interessant i verden, som du kan have udledes fra diskussioner af like-- hvad er det-- CarPlay, Apples software til biler og det faktum, at mange af os i stigende grad har touch-skærme i vores biler, der er en skræmmende mængde af software i folks biler i dag, som ærligt åbner en hel dåse orm, når det kommer til sikkerhed og fysisk risiko. Men for i dag, lad os fokusere på netop, hvad der er involveret skriftligt software som kunne have gamed systemet. 

For definitionen af problem, for dem bekendt, lad os tage et kig på John Oliver. Og for dem bekendt med problemet, lad os se på det i en sjov linse via John Oliver så godt. Så lad mig slå spille på dette, jeg tror, ​​tre-minutters introduktion. For pokker. [VIDEO PLAYBACK] -Cars-- DAVID MALAN: Det er klart, på YouTube, it's-- - --the smarteste tegn i de Fast and Furious film. I denne uge, tyske bilproducent Volkswagen befandt sig midt i en skandale af potentielt kriminelle proportioner. 

-Volkswagen Er forfriskende for milliarder i bøder, mulige strafferetlige anklager for sine ledere, som selskabet undskylder til rigning 11 millioner biler til hjælpe det slå emissionsprøvninger. 

-Certain Diesel modeller designet med sofistikeret software, brugt oplysninger, herunder positionen af rattet og køretøj hastighed, for at bestemme bilen var under afprøvning emissioner. Under denne omstændighed, at motoren ville reducere giftige emissioner. Men bilen blev rigget til bypass at når det blev kørt. Emissionerne steg 10 til 40 gange over acceptable EPA niveauer. 

Wow, 10 til 40 gange større end EPA tillader. Det er det værste Volkswagen har nogensinde gjort, er noget du måske sige, hvis du havde aldrig hørt om Anden Verdenskrig. Men måske det sikreste tegn på, hvor meget besvær Volkswagen er i, er, at folk på meget top har trådt ned. Den administrerende direktør fratrådte onsdag efter travlt med at gøre skade kontrol, siger han var uendeligt ked af det, som lød store indtil det viste sig han var kun 10% sorry men havde rigget munden kunstigt øger sin sorriness. Og i mellemtiden, Volkswagen USA chef havde en undskyldning for hans egen. 

-Lad Os være klar over dette, vores virksomhed var uærlig. Og i mine tyske ord, vi har fuldstændig skruet op. 

-Ja, Men helt skruet op er ikke tyske værker. Og det tyske sprog har mange smukke sætninger til at beskrive situationer, ligesom denne, såsom [TYSK], hvilket betyder groft, sorg, der kommer fra business-relaterede løgne, eller [TYSK], som oversætter som shaming dem far involverer skyer af benzin. Det er en smuk sprog. Det bare sejler ud tungen. Og ved den måde, mens at menneskets undskyldning kan have lydt oprigtig, det er værd at bemærke, at han talte på en officiel lancering fest for 2016 Volkswagen Passat, hvilket betyder, at om kort tid efter at sige undskyld, sagde han dette. 

-Tak Meget for at komme. Nyd aftenen. Op næste er Lenny Kravitz. 

[MUSIK AFSPILLER] 

-OK, OK, slutter dit undskyldning med op næste Lenny Kravitz ikke skrige ædru anger. Det skriger, spurgte vi Bon Jovi, og han sagde nej. Volkswagens mærke har blevet alvorligt beskadiget. Og helt ærligt, deres nye annonce kampagne er ikke ligefrem hjælper. 

- [TYSK], ville vi hos Volkswagen gerne at undskylde for at bedrage dig vores biler. 

[END AFSPIL] DAVID MALAN: Så det var en rundkørsel måde of-- sorry-- dette var en rundkørsel måde indføre et grundlæggende problem i software, som er, at du brug for at detektere visse betingelser. Og så spørgsmålet ved hånden her er, hvordan gør en bil potentielt som implementeret i software af disse programmører, opdage, at det faktisk er at blive testet? Så for at være super klar, hvad de gjorde var, i miljøer, hvor programmørerne regnede bilen var ved at blive testet, de på en måde gjort bilen udleder færre emissioner, færre emissioner, så mindre giftige dampe og sådan. Men når det er normalt kørsel på vej, Det ville bare udlede så meget forurening, som det ønskede. 

Så hvordan kunne vi skrive pseudokode for denne algoritme? Hvordan kunne vi skrive pseudokode for software, der kører i bilen? Jeg mener, i en nøddeskal, det koger ned til noget som dette. hvis der testes, udleder mindre. ellers udleder mere. Men det er lidt for højt niveau, ikke? 

Lad os prøve at dykke i, hvad dette indvinding af at blive testet midler. Med andre ord, selvom du ikke ved noget om biler, hvilken slags spørgsmål kunne man spørge, for at afgøre, om du bliver testet, hvis du er bilen? Hvilke egenskaber kan være stede, hvis en bil er ved at blive testet? 

PUBLIKUM: Test udstyr. 

DAVID MALAN: Test udstyr. Så hvis testudstyr i nærheden, så udleder mindre. Så jeg kunne forestille mig at gennemføre at med en slags kameraer eller påvisning hvad der foregår omkring dig. Og lad mig foreslå, at bare føles for kompliceret til faktisk har ekstra hardware netop til dette formål. 

PUBLIKUM: Hvis du er i park, hvis din hætte er åben. 

DAVID MALAN: I parken eller hætte åben, så det er godt. 

PUBLIKUM: Og bil kørende. 

DAVID MALAN: Så det er lidt mere concrete-- og bil kørende. Så det ville være sammenfaldet af en nogle forskellige betingelser, hvis du vil. Så hvis bilen er i parken, og selv selv om dette er en meget mekanisk ting typisk, jeg kunne forestille skrive software, især fordi der er ofte et lys der i disse dage, Jeg kunne forestille mig at der er software, der kan forespørge Shifter eller hvad ikke, er du i parken, er du i drevet, er du i bakgear. Og jeg kan komme tilbage en besvare det er enten ja eller nej til den slags spørgsmål. 

Og så kunne jeg også nok svare et spørgsmål som, er hætten åben. Måske er der en slags sensor at enten giver mig tilbage en 1 eller 0, sandt eller falsk, motorhjelmen er åben. Og så bil kørende, kunne jeg afsløre at en eller anden måde via hvilken mekanisme? Ligesom, bilen kører, jeg kunne registrere, at det er på, kunne jeg opdage en eller anden måde at bilen er i bevægelse? 

MÃ¥lgruppe: RPM'er. 

DAVID MALAN: Ja, så der er altid, at nål, fortæller dig, hvor mange omdrejninger i minut hjulene oplever. Og så kunne jeg se på det. Og hvis det ikke er 0, som sandsynligvis betyder, at bilen er i bevægelse. Men vi er nødt til at være en lidt forsigtige der, because-- lad os forenkle denne-- hvis vi bare sagde, hvis bilen kører, Vi ønsker ikke at bare udlede mindre, Vi ønsker, hvis bilen kører og det bliver testet. 

Så der er et par andre ingredienser, folk har en hypotese softwaren gør, fordi fraværende selve kildekoden, du kan kun slags udlede af den fysiske virkninger af bilen, hvad der måske foregår under hætten i software. Så hvis bilen kører, og måske, sige, baghjul ikke bevæger sig, kan dette være vejledende af en slags test? Hvad skal jeg hentyder til her? Ja, måske, det er på den ene af disse rullelejer ting, hvor ens hjulene vender i den forreste eller i ryggen, alt efter om det er forhjul eller baghjulstræk, så halvdelen af ​​hjulene er i bevægelse, men den andre to er ikke, som er en underlig situation i den virkelige verden. Hvis du kører på vej, skal der ikke ske. Men hvis du er i et lager på en slags rullesystem, der kan faktisk ske. 

Jeg tror folk også foreslået, at måske, hvis bilen kører og styring hjulet ikke bevæger sig, at også kan være et signal, fordi det er rimeligt for som en straks på en vej. Men selv da, mennesket er sandsynligvis flytte det lidt eller helt sikkert over et par sekunder. Eller i løbet af et minut, odds er det ikke vil blive fikseret i nøjagtig samme position. 

Så med andre ord, vi kan tage subtraktion, er du bliver testet, og nedbryde denne funktionalitet ind i disse komponent ingredienser. Og det er virkelig, hvad Volkswagens ingeniører eller anden måde gjorde. De skrev software bevidst til opdage, hvis bilen bliver testet, Derfor udleder mindre, ellers udsender på den sædvanlige måde. 

Og problemet også her er, at software ikke er noget, du virkelig kan se, medmindre du har den såkaldte kildekode. Så der er to forskellige typer af code-- mindst to forskellige typer kode i verden. Der er noget, der hedder kilde kode, som ikke er ulig hvad Vi har været at skrive, kildekode. 

Dette er kildekode skrevet i et sprog kaldet pseudokode, som er lige noget engelsk-lignende. Der er ingen formel definition af det. Men C og Java, C ++, der er alle formelle sprog,, når du skriver i dem, hvad du har er en tekstfil, der indeholder kildekode. 

Men der er også noget i verden kaldet maskinkode. Og maskinkode, desværre, er kun 0'er og 1'er. Så maskinkode er hvad maskiner forstå, selvfølgelig. Kildekoden er, hvad mennesker forstår. 

Og generelt, men ikke altid, er der et program at en programmør bruger der tager kilde kode og forvandler det til maskinkode. Og at programmet er generelt kaldes en compiler. Så dit input er kildekode, dit output er maskinkode, og compileren er et stykke software, der gør denne proces. Så dette faktisk kort pænt til vores input, algoritmer, output. 

Men det er en meget specifik inkarnation af det, hvilket vil sige, at, selv hvis du ejer en af ​​Volkswagens biler, der er skyldige i denne, det er ikke ligesom du kan bare åbne hætte eller åbne manualen eller se på kildekoden, fordi på det tidspunkt det når din bil i din indkørsel, Det er allerede blevet omdannet til 0'er og 1'er. Og det er meget svært, ikke umuligt, men meget svært at indsamle meget af noget fra bare at kigge på den underliggende 0'er og 1'er. Så du kan finde ud af det i sidste ende, hvis du forstår, hvordan en maskine operates-- Intel inside-- hvis du forstår Intel-arkitektur, men det er meget tidskrævende. Og selv der, måske du ikke være i stand til at se alt at koden rent faktisk kan gøre. 

Eventuelle spørgsmål vedrørende denne eller dette slags proces mere generelt? Og faktisk kan vi binde denne diskussion til gårsdagens diskussion af Apple. Dette er også er grunden til, at FBI kan ikke bare gå og kigge i den mistænktes telefon og finde de linjer kode, for eksempel, at aktivere adgangskoden eller aktivere, at 80-millisekund forsinkelse. Fordi på det tidspunkt, det er på stipendiaten iPhone, Det er allerede blevet konverteret til 0 og 1'er. 

Nå, lad os holde pause her for vores se på beregningsmæssige tænkning. Hvorfor vi ikke tage en 15 minutters pause. Og når vi vender tilbage, vil vi tage et kig på programmering selv og begynde at kortlægge nogle af disse højt niveau begreber til en faktisk, hvis legende, programmeringssprog.