[MUSIC Playing] [MUSIC - Rossini, "Ranz DES Vaches "fra William Tell] [MUSIC - DEN ENGELSKE BEAT, "MARTS AF svinghoveder "] [Applaus og råber] DAVID MALAN: Så dette er CS50. Mit navn er David Malan. Og 73% af du ikke har nogen forudgående erfaring med datalogi, i modsætning til hvad du måske tror. Så i dag vi troede, vi ville chip væk på det manglende kendskab, men også giver dig en fornemmelse af, for dem af jer med mere komfort, hvilke retninger du kan gå i dette semester. Så lad os starte med dette. Jeg har virkelig ingen idé om, hvad der er inde i en computer, selvom ligesom dig, jeg bruger det hver dag. Men det er en slags kasse, og der er ikke mange input til det. Minimalt, der er, hvad? Sandsynligvis en netledning. Og faktisk med denne ene ingrediens, elektricitet, vi synes at være i stand til gør lidt i disse dage. Men i slutningen af ​​dagen, vi nødt til at repræsentere de ting at vi holder af. Vi er nødt til at repræsentere information i en eller anden form. Og du er sikkert mindst vagt fortrolig med tanken ved binære eller bits eller anden måde, computere reduceret til nuller og ettaller. Men kan vi omfavne det, og i det mindste sætte en smule lys på det? Så jeg har disse små bordlamper her. Jeg har en stikkontakt her. Og jeg har tænkt mig at foreslå, at inde af min computer er mindst én af disse ting, noget der kan for at blive tændt eller slukket. I dette tilfælde er det faktisk en bordlampe, men på lavere niveau, er det noget kaldes en transistor. Men i vores verden, er det en bordlampe, så Jeg har tænkt mig at gå videre og tilslutte denne ind i min el her. Og jeg hævder, at bruge denne simple, simpel anordning, denne enkle switch, jeg kan repræsentere information. For eksempel, lige nu er jeg repræsenterer noget, right? Jeg repræsenterer, hvad jeg vil kalde 0 eller falsk, det modsatte af noget faktisk er til stede. Men hvis jeg bare vende denne switch, nu har jeg repræsenterede en 1. Så bruger denne meget simpelt stykke hukommelse, hvis du vil, kan jeg repræsenterer oplysninger. Nu desværre min computer kan ikke gøre så meget. Det kan kun repræsentere to værdier i hele verden - 0 eller 1. Men hvad er en oplagt løsning, nu hvis vi ønsker at udvide vores computers hukommelse og udgør mere end blot 0 og 1? Nå, lad os få fat i en anden sådan bit. Lad os tage en anden switch, en anden transistor, men du gerne vil tænke over det. Lad mig gå videre og tilslutte denne ind i min computer så godt. Og jeg har tænkt mig at hævde, nu, at ved ved hjælp af en smule mere el og drejning flere af disse parametre, og slukket, kan jeg repræsenterer flere af sådanne oplysninger. Så lige nu er, det er 1. Hvis jeg ønsker at udgør nu 2. Jeg kunne gøre dette. Men typisk, konvention, som vi vil i sidste ende se, vil have mig til at gøre dette. Så dette er 0, det er 1. Dette ville være 2. Og ikke overraskende, ville dette være 3.. Så på den måde stadig, kan vi tæller op endnu mere? Hvis jeg får en tredje bit, en tredje switch, hvad er det højeste antal jeg kan nu tælle op til fra 0? Så 7, hvis jeg starter på 0, right? Fordi hvis jeg tænder dette lys, og faktisk tilslutte denne tredje og sidste lys ind i min stikkontakt her så jeg har evnen til at repræsentere nogen af ​​to værdier her, to værdier her to værdier her - og så jeg kan repræsentere 2 gange 2 gange 2, eller otte mulige værdier. Og hvis jeg starter regnskab på 0, så der er 0, 1, 2, 3, 4, 5, 6, 7. Så denne binære. Det er virkelig så simpelt er det. Og jeg ville argumentere for, at dette faktisk er ganske velkendt for de fleste alle i dette rum. Lad mig gå videre og åbne en lidt tekst editor her. Og du måske husker fra folkeskolen at vi havde ting som de hundredvis sted, TEN sted, og dem sted. Og huske, at hvis du havde nogle decimal nummer, som noget tilfældigt Ligesom 123, ville du hovedsageligt skriver, at i formularen af disse tre kolonner. Og hvorfor er 1, 2, 3, hvad vi kender som 123? Tja, i kolonnen til venstre, har vi én 100 plus to 10'ere, så det er 120, plus tre 1s, så det er 123. Nu er denne verden, at vi bare belyst er nøjagtig den samme som du har været bekendt med i årevis, undtagen nu, kolonner vores ikke beføjelser 10.. De er bare beføjelser 2.. Så mens det er dem sted, dette kommer til at være det toere sted, er det vil være det Fours plads. Og fordi jeg kun bruger den enkleste af mekanismer til at vende tingene tændes og slukkes - elektricitet flyder eller elektricitet ikke flyder - Jeg forstår ikke helt den samme ekspressive område som 0 til ni. Vi kommer til at holde det super enkel i denne verden af ​​computere. Jeg har kun 0 eller 1 - fra eller til, falske eller ægte. Og så hvad jeg repræsenterer lige nu er 1, 1, 1, fordi hver af disse lys lyser. Nå, det giver mig en 4 plus en 2, så der er 6, plus en 1, og det er 7.. Og ergo gør denne sekvens af tre bit repræsenterer nummer 7.. Så al den tid, indersiden af ​​dit computer, har været en række transistorer, helst antal bit. Men i slutningen af ​​dagen, vi kan repræsentere information så enkelt som det. Nu desværre har vi kun talt op til 7 i CS50 hidtil, men forhåbentlig kan vi gøre en smule bedre end det. Og faktisk vi kan. Antag, at vi som mennesker bare vilkårligt besluttet, at vi vil at knytte numre som 1 og 2, 3, 4, 5, 6, 7, med specifikke bogstaver i alfabetet. Og af historiske grunde vil jeg starte noget vilkårligt, men jeg er kommer til at sige, mennesker, vi vil beslutte som en standard, globalt, at 65 repræsenterer antallet af bogstavet A. 66 vil repræsentere B. Dot, prik, prik. 90 vil repræsentere bogstavet Z. Og lad os antage, hvis vi virkelig sætte nogle tænkte ind i det, kunne vi komme op med tal for udråbstegn og små bogstaver, og ja, andre mennesker har gjort det for os. Så nu havde vi bits, som vi kan repræsentere tal, tal med hvilke vi kan repræsentere bogstaver, og med breve kan vi nu begynde at komponere emails og trykning tegn på skærmen. Så lad mig opfordre hvis jeg kunne, otte modige frivillige - der ikke har noget imod vises ikke blot på kamera, men på internettet - til at komme herop og repræsenterer otte sådanne bits, snarere end disse tre. Så hvordan omkring en, to? Hvordan omkring tre? Hvordan omkring fire i lyset blå, fem på enden? Om nogen herovre? Seks foran, syv i front, og otte i front, så godt. Så jeg bare så sket til at komme forberedt med en hel bunke af sedler. Og på disse stykker papir er tal der repræsenterer, hvad kolonner du fyre kommer til at repræsentere. Så du vil være - hvad er dit navn? STUDENT: Anna Leah. DAVID MALAN: Anna Leah, du vil være 128S kolonne. Du er? STUDENT: Chris. DAVID MALAN: Chris vil være den 64s kolonne. Du er? STUDENT: Dan. DAVID MALAN: Dan vil være den 32s kolonne. STUDENT: Pramit. DAVID MALAN: Pramit vil være 16s kolonnen. STUDENT: Lillian. DAVID MALAN: Lillian bliver 8s. STUDENT: Jill. DAVID MALAN: Jill vil være 4s kolonne. STUDENT: Mary. DAVID MALAN: Mary vil være 2s, og? STUDENT: David. DAVID MALAN: David være 1s kolonne. Så hvis du fyrene kunne træde lidt frem, så alle kan se. Hvad du fyre ikke ser, er, at det på bagsiden af ​​disse sedler er en lille bedrager ark, der er ved at instruere disse otte bit til enten hæve deres hånd eller ikke hæve deres hånd. Hvis deres hånd går op, de er repræsenterer en 1. Hvis deres hånd bliver nede, de er repræsenterer et 0. I mellemtiden har vi publikum bør være i stand til at regne ud, baseret på denne kortlægning, hvad tre bogstaver ord disse folk er ved at stave. Så i bare et øjeblik, du kommer til at læse den første linie fra bagsiden af din bedrager ark, og du er enten kommer til at hæve eller ikke hæve din hånd. Hvis du er en 1, du raiser, hvis du er en 0, du står der akavet, ligesom det. Go. Hvilket nummer, først og fremmest, er disse fyre repræsenterer? 66.. 66, right? Vi har en 1 i 64s kolonne en 1 i 2s kolonnen. Det giver mig 66, så der vises at repræsentere B. Så du fyre har stavet - OK, det er nok. B. Så lad os nu gå videre vores andet brev. Go. Hvem er hurtigst til matematik her? Så 79. Igen, hvis vi tilføje op alle de kolonner hvor der er et 1 i øjeblikket, bare som vi gjorde før med den enkleste eksempler på 7, vi nu få nummer 79. Som efter vor mapping er den bogstavet O. Så vi er der næsten. B, O. Og endelig gå. Hvad er de repræsenterer nu? Mindre enighed. Det er bare en absolut mumlen. Ja, det er i virkeligheden 87. Godt. Så hvis vi nu kortlægge det tilbage til - lad os begynde at kalde vores ASCII diagram, American Standard Code for Information Interchange. Det giver os det brev - ikke "bo", men "bue". Og det er en perfekt cue for jer at tage en bue og hoved på ryggen. Mange tak. [Applaus] DAVID MALAN: Du kan beholde dem. Selvom faktisk, ville nogen ligesom en bordlampe,? også [Hoot FROM AUDIENCE] DAVID MALAN: Desk lamp? [Latter] DAVID MALAN: Really? Bordlamper for alle? Ok. Så startende med meget simpleste af principper, vi har nu ikke kun tælles op fra 0 hele vejen op til 7, vi har antages, at blot ved at kaste mere bits eller mere lys eller mere transistorer på dette problem, kan vi repræsentere større og større tal, og Ergo, større og større intervaller af alfabeter, som engelsk. Og bare lad os tage på tro i dag der på samme måde kunne vi begynde at repræsentere grafik og video og enhver Antallet af andre medier, som vi er velkendt i dag. Så dette er CS50, og i denne klasse siden af ​​jer er, igen, rigtig mange klassekammerater, der har så lidt oplever som dig. Og jeg nævner dette kun fordi ganske ofte, bl.a. så sent som en af freshman rådgive begivenheder og forårets sophomore rådgive begivenhed, vi ofte hører eleverne fralægger når de kommer op til CS bordet, ja, Jeg har været tanker om at tage dette intro klasse, men jeg er ikke rigtig en computer person. Eller, men alle sikkert ved mere end mig. Og jeg sætter dette i den største skrifttype muligt at formidle dette budskab, det er faktisk ikke tilfældet. Og hvis du undrer dig, bør I, i virkeligheden, være her? Indse, at ikke alene er dette kursus er title Introduktion til Computer Videnskab er det Introduktion til Computer Science I. Så der er faktisk en anden sådanne introduktion. Så du er ikke i virkeligheden, på det forkerte sted. Og blandt de mål, jeg har for i dag, er at dæmpe sådanne bekymringer, du kan have, men også at male en billede af, hvad der er i vente for studerende mindre og mere komfortabel ens i dette kursus. Men først et par ord på en af ​​uddelingskopier du har i dag, blandt hvilke er en række ofte stillede spørgsmål. Det har været en vision om vores for nogen tid nu at indføre en ny klassificering option i dette kursus - nemlig SAT / unsat. Filosofisk for mig, det er meget, meget, meget mere vigtigt, at elever i denne klasse engagere sig med materiale, blive udfordret af de materiale, og bekymre langt, langt mindre om mekanik faktiske scoringer og brev kvaliteter ved semesters ende, men virkelig omfavne kursus og dets materiale. Og virkelig det føles mere generelt for, hvad der er interessant for dem, at føler udfordret og belønnes, men uden frygt for fiasko. Og ja, også dette er et tilbagevendende tema i denne og andre indledende kurser i andre områder, som du har denne bæven når det kommer til sætte ens tæer ukendte farvande. Jeg selv, tilbage i 1995, var en freshman. Jeg var meget fokuseret på at være a Gov koncentrator her. Og alligevel ville jeg altid vokset op med en smule af en interesse i datalogi. Jeg var altid nysgerrig. Men dengang, selv havde jeg denne frygt for selv at træde fod i CS50, så meget så jeg ikke engang handle det første år. Og den eneste grund til jeg sætter en fod i dør sophomore år var fordi jeg fik lov til at tage det bestået / ikke bestået. Men selv bestået / ikke bestået kræves, at jeg får op den frækhed at lave en aftale med professor Kernehan dengang, bringe denne store ark papir, og spørg ham for hans underskrift og hans tilladelse til at udforske disse uvante farvande. Og det har ikke hjulpet i de seneste år at når du gør dette i CS50, når vi bruges til at være bestået / ikke bestået, ligeledes ville snesevis eller hundredvis af dine klassekammerater nødt til at komme op, Gud forbyde det, ved forsiden af ​​Sanders med denne form, i nogle sind repræsenterer en manglende evne, Jeg tør sige, at udføre er dine kammerater 'niveau. Hvilket er latterligt, men jeg tror Der er denne mentalitet. Og der har aldrig været i denne kultur af SAT / unsat eller bestået / ikke bestået mere generelt i dette kursus, eller virkelig på denne campus. Så dette år vi ændrede det. Jeg ville være ekstatisk halvdel af denne klasse eller mere sluttede at tage CS50 SAT / unsat. I et års tid, ville det være vidunderligt om næsten alle er. Derefter måske vi vil arbejde på brev kvaliteter ved Harvard College mere generelt. Men for nu, vil vi gøre dette inden for vores egen sfære, og jeg vil varmt opfordre dig til at gennemgå disse ofte stillede spørgsmål og stille spørgsmål, som du ønsker, så forhåbentlig du, i modsætning til mig, vil ikke helt har den samme frygt faktor, når udforske, hvad er nok et ukendt sted. Så hvad er CS50? Det er en introduktion til den intellektuelle virksomheder af computer videnskaben og kunsten for programmering. Men hvad betyder det egentlig? Nå, hidtil, vi talte meget kort om repræsentation af information. Men formoder, at vi faktisk ønsker at gøre noget med det. Vi er nødt til at introducere begrebet hvad vi vil kalde en algoritme. En algoritme er en procedure, en proces, et sæt af instruktioner til gør noget. Og en algoritme kan være noget super enkel. For eksempel eksempel en som en række af jer kan være bekendt er det ting her. Så denne bog her er i stigende grad dateret, men engang det indeholdt en hel masse navne og telefonnumre. Og ja, hvis jeg ønskede at finde nogen i denne telefonbog - sige, nogen ved navn Mike Smith - Jeg kunne finde Mike Smith i et vilkårligt antal af forholdsvis ukomplicerede måder. Jeg kunne starte ved begyndelsen og gå videre til side 1, der ikke. Side 2, der ikke. Page 3. Er denne algoritme er at proces, korrekt? Så det er korrekt, right? Jeg er lidt en idiot for at gøre det i denne måde, men til sidst vil jeg finde efternavnet S, og forhåbentlig Mike er i denne sektion, og jeg bliver gjort med min algoritme. Men sikkert er det ikke intuitivt. De fleste enhver rimelig menneske i denne plads ikke ville have gjort. Hvad ville du have gjort? Du ville være gået direkte til midten, right? Nogenlunde til midten. Og du indser, åh, det er disse Ms Så Mike Smith, efternavn bliver Smith, er ikke klart, derefter i venstre halvdel af bogen. Han skal være mod S er i den rigtige. Og på dette punkt, selvom de fleste af os ikke gør dette i virkeligheden, kan vi bogstaveligt rive dette problem i halve. [Jubler og klapper] DAVID MALAN: Tak. [Jubler og klapper] DAVID MALAN: Du kan bogstaveligt talt rive dette problem i halve, forlader mig med, bogstaveligt, et problem, halvt så stort. Så hvis dette telefonbog var - og det formentlig var - omkring 1.000 sider, nu det er kun 500. Hvis jeg gør det igen, og jeg er klar over, åh, damn, jeg gik for langt, jeg er i Ts sektionen, kan jeg ligeledes - billedligt eller bogstaveligt - rippe telefonbogen - det var faktisk meget nemmere at tid. Jeg kan bogstaveligt talt rippe telefonbogen i halve, forlader mig nu med ikke 1.000, ikke 500 - 250 sider. Og jeg kan gå 125 og halvdelen af ​​det, og halvdelen af ​​det, og halvdelen af ​​denne, indtil jeg til sidst vil stå tilbage med blot en enkelt side. [Latter] DAVID MALAN: Det er del I mislykkes på. En enkelt side, hvor Mike forhåbentlig er. Nu er de forskellige algoritmer kan være slags bedømt eller vurderet i forskellige måder. Den første var meget lineær, right? Vend siden, kigge efter Mike. Vend siden, kigge efter Mike. Det er meget lineær. Hvis der er én side mere i telefonen bog, er det sandsynligvis kommer til at tage mig en mere sekund, en mere enhed af tid, Men vi computing tid. Så jeg kunne tegne som dette denne linje her, hvorved som størrelsen af ​​den problemet stiger fra venstre til højre - telefonbog bliver mindre til større - og tid kommer til at stige på den lodrette akse, jo større telefonbogen er. Så n er blot en generel variabel, dataloger bruger til at repræsentere vis værdi, nogle tal. Så n vil øges lineært. Fordoble størrelsen af ​​telefonbogen, er det kommer til at tage mig dobbelt så meget tid, mest sandsynligt, at finde Mike. Nu kunne jeg have været smarte om dette, right? Jeg fik kede hurtigt. Kunne have gjort dette ved toere. Så to sider, derefter fire, derefter seks, derefter otte. Og jeg kunne begynde at flyve igennem det en lidt hurtigere, omend på mindre risiko for overskridelse Mike, men at kurven ikke er kommer til at være så forskellig. Det er stadig kommer til at være en lige linje, men lidt hurtigere. Men hvad gjorde jeg? Jeg rent faktisk gjorde noget fundamentalt bedre. Jeg opnåede, hvad vi vil kalde logaritmisk tid, log n, hvorved denne grønne line har en meget, meget, meget mindre lige kant til det. Og i stedet, det antyder, som det sortere i mod uendelig nogensinde så gradvist, at jeg faktisk kunne tage en 1.000-siders telefonbog, fordoble sin størrelse næste år - fordi formoder, at en masse flere mennesker flytter ind til byen. Så nu har jeg fået 2.000 sider, men hvor mange flere trin er, at smartere algoritme kommer til at tage? Blot én. Jeg mener, det er en kraftfuld ting. Hvis vi går til 4.000 sider næste år, der kommer til at tage mig kun to trin. Så du kan smide større og større problemer på mig, ikke ulig nettet er smide større og større problemer hver dag på Googles og Facebooks af i verden, og det er ikke sådan en big deal. Fordi jeg lægge mere tanke og pleje i min algoritme med at løse problemer effektivt. Og ja, vil det være en af målene for dette kursus. Du vil undervejs, lære at programmere. Du vil lære hvordan man programmerer i vilkårligt antal sprog. Men i slutningen af ​​dagen, er kurset om at løse problemer og få bedre til at løse problemer - og som i tilfælde som dette, løse problemer mere effektivt. Nu hidtil har vi gjort dette forholdsvis intuitivt. Lad os indføre noget forholdsvis generisk kaldet pseudokode. Så vi vil i sidste ende får, i dette kursus, at forskellige programmeringssprog. Men i dag vil vi gøre det på engelsk-lignende syntaks, hvor du bare slags siger hvad du mener, men du er nogensinde så kortfattet og du behøver ikke bekymre dig om grammatik og hele sætninger. Du skal bare udtrykke dig selv som kortfattet som muligt. Så pseudokode er engelsk-lignende syntaks, der repræsenterer et programmeringssprog. Og mod denne ende, lad mig foreslå, at vi nu modellere proces vi bare beskrevet for at tælle noget lidt anderledes, denne gang tager en se på dette fem-minutters produceret video af vores venner på TED, at definerer, hvad pseudokode er definerer, hvad algoritmisk tankegang er, og endda selvom det eksempel, du er ved at se er, i sig selv, super enkel, det er vil begynde at give os den mentale model, ordforråd, med til at gøre meget, meget mere kompleks algoritmer ganske hurtigt. [BEGIN VIDEOAFSPILNING] [MUSIC Playing] Fortæller: Hvad er en algoritme? I datalogi, er en algoritme en sæt af instruktioner til at løse nogle problem trin for trin. Typisk algoritmer udføres af computere, men vi mennesker har algoritmer, så godt. For eksempel, hvordan ville du gå om at tælle antallet mennesker i et rum? Tja, hvis du ligesom mig, du ville nok punkt på hver person, én ad en tid, og tælle op fra 0. 1, 2, 3, 4, og så videre. Nå, det er en algoritme. Faktisk, lad os prøve at udtrykke det en lidt mere formelt i pseudokode - Engelsk-lignende syntaks der ligner et programmeringssprog. Lad N være lig med 0.. For hver person i rummet, der N lig med N plus 1. Hvordan man skal fortolke dette pseudokode? Nå, line man erklærer, så at sige, en variabel kaldet N og initialiserer dens værdi til 0. Det betyder bare, at i begyndelsen af vores algoritme, de ting, som Vi regner har en værdi af 0. Efter alt, vi før begynde at tælle, Vi har ikke talt noget endnu. Opkald denne variabel N er blot en konvention. Jeg kunne have kaldt det mest noget. Nu line to demarks starten på en løkke, en sekvens af trin, som vil gentage nogle antal gange. Så i vores eksempel, det skridt vi tager regner mennesker i lokalet. Under linie to er linie tre, der beskriver præcis hvordan vi vil gå om at tælle. Indrykningen indebærer, at det er line tre, der vil gentage. Så hvad pseudokode siger, er der efter start på 0, for hver person i rummet, vi vil øge N med 1. Nu er denne algoritme korrekt? Nå, lad os bang på det en smule. Virker det, hvis der er to personer i rummet? Lad os se. På linje et, initialisere vi N til 0. For hver af disse to personer, vi derefter tilvækst N med 1. Så på den første tur gennem loop, vi opdaterer N fra 0 til 1. På anden tur gennem den samme loop, vi opdaterer N 1 til 2. Og så ved denne algoritme udgang, er n 2, som faktisk svarer til det antal personer i rummet. Så langt, så godt. Hvordan omkring et hjørne tilfælde? Selv Antag at der er 0 personer i rummet - ud over mig, hvem der gør optællingen. På linje et, initialisere vi N til 0. Denne gang dog linje tre ikke udføre på alle, da der ikke er en person i rummet. Og så N forbliver 0, hvilket svarer til Antallet af personer i lokalet. Ret simpelt, ikke? Men tælle folk én ad gangen er temmelig ineffektiv, også, ikke? Sikkert vi kan gøre bedre. Hvorfor ikke tæller to personer ad gangen? I stedet for at tælle 1, 2, 3, 4, 5, 6, 7, 8, og så videre, hvorfor ikke tælle, 2, 4, 6, 8, og så videre? Det lyder endda hurtigere, og det er helt sikkert. Lad os udtrykke denne optimering i pseudokode. Lad N være lig med 0.. For hvert par af mennesker i rummet, indstille N lig N plus 2. Temmelig simpel ændring, right? Snarere end tæller folk én på en gang, i stedet vi tæller dem to ad gangen. Denne algoritme er således to gange så hurtigt som det sidste. Men er det korrekt? Lad os se. Virker det, hvis der er to personer i rummet? På linje et, initialisere vi N til 0. For at et par mennesker, vi derefter tilvækst N med to. Og så ved denne algoritme udgang, er N2, som faktisk svarer til det antal personer i rummet. Antag næste, at der er 0 personer i rummet. På linje et, initialisere vi N til 0. Som før, er linie tre ikke eksekvere på alle, der siden er ikke nogen par mennesker i lokalet. Og så N forbliver 0, hvilket faktisk svarer til det antal personer i rummet. Men hvad nu, hvis der er tre personer i rummet? Hvordan denne algoritme billetpris? Lad os se. På linje et, initialisere vi N til 0. For et par af de mennesker, vi derefter tilvækst N med 2. Men hvad så? Der er ikke en anden fuld par af mennesker i rummet, så linie to nej længere gælder. Og så ved denne algoritme udgang, N er stadig 2, hvilket ikke er korrekt. Faktisk er denne algoritme siges at være buggy, fordi det har en fejl. Lader oprejsning med nogle nye pseudokode. Lad n lige 0 for hvert par mennesker i lokalet. Indstil N lig med N plus 2. Hvis en person er fortsat uparrede, indstille N lig N plus 1. For at løse dette særlige problem, vi har indsat i overensstemmelse fire, en betingelse, ellers kendt som en filial at kun henretter hvis der er en person, som vi ikke kunne par med en anden. Og så nu, om der er én eller tre eller enhver ulige antal personer i rummet, denne algoritme vil nu tælle dem. Kan vi gøre det endnu bedre? Nå, kunne vi tælle i 3s eller 4s eller endda 5s og 10s, men ud over det, er det kommer til at få en lille smule svært at pege. Ved slutningen af ​​dagen, udføres om af computere eller mennesker, algoritmer er blot et sæt af instruktioner med at løse problemer. Det var blot tre. Hvilket problem vil du løse med en algoritme? [END VIDEOAFSPILNING] DAVID MALAN: Det er den eneste gang Jeg vil blive vist i tegneserie formular. Men hvor denne historie blade off, nu er, hvordan kan vi gøre bedre? Treere og firere, vi påstår, at vi kan regne folk meget hurtigere, men kan vi gøre fundamentalt bedre end det? Og jeg vædde vi kan. Hvis vi indfører en smule af vores egne pseudokode her, vil jeg foreslå at vi kan nå en linje som denne. Vi kommer ikke til at tælle folk én, to, tre, fire. Vi kommer ikke til at gå to, fire, seks, otte. Vi kommer til at gøre fundamentalt bedre ved nytænkning af problemet, og i dette tilfælde, gearing en ellers underudnyttede ressource. På bare et øjeblik, jeg håber du vil tilgive og humor os ved at stå op i sted, på hvilket punkt vi kommer til at bede hver af jer til at tage på i din sind nummer 1. Du derefter gå til stigende kejtet, som tiden går, finder en anden, der står, kombinere dine tal sammen ved at tilføje dem op. En af jer bliver derefter gå til kapløbet om at sidde ned først, og den anden person kommer til at gentage. Så med andre ord, ved podning alle dig med nummer 1 og derefter kombinerer disse 1s i 2s og de 2s i 4s, i stigende grad med alle sidder ned, bør vi i slutningen af denne algoritme, har kun én lån sjæl, som ikke sidde ned hurtigt nok, men der har hele publikum tæller i hans eller hendes sind. Så hvis du gerne, så lad os gå videre og - Step One - stå op på plads. Og udføre. [CROWD mumlende] DAVID MALAN: Kender du hvor Lauren er? 729? [CROWD mumlende] DAVID MALAN: Okay? [CROWD mumlende] DAVID MALAN: Okay, vi skal være nærmer sig slutningen. Vi ser en fyr stå her stadig. Hvem ellers skal parres? Hvis du fyre vil parre sig. Nogen op øverst. Hvorfor kan jeg ikke give en hånd her. For de meget få mennesker, der stadig stående, hvilke numre gør du har i dit sind? STUDENT: 78.. DAVID MALAN: 78 plus - hvem der står hernede? STUDENT: 39.. DAVID MALAN: Plus 39. Plus hvem der ellers stadig stående? 81? OK, hvem ellers? En anden 81? Wow. Og så hvad der er i tilbage? STUDENT: 49.. DAVID MALAN: 49 plus? STUDENT: 98. DAVID MALAN: 98 plus? Er det en anden? 12? Godt arbejde. [Latter] DAVID MALAN: Åh, 112 - oh. Godt arbejde! [Latter] [Applaus] DAVID MALAN: Alle andre stadig stående? Undskyld? STUDENT: 99. DAVID MALAN: 99. Alle andre stadig stående? Og det samlede antal studerende her er faktisk, ifølge - har du et nummer? Åh, det faktiske antal personer i rum, ifølge den konto, de pædagogiske fellows lavede på alles måde, var 729. Så ud af en stuen fuld af Harvard studerende der tælles selv, Svaret er 637. [Latter] DAVID MALAN: Så tæt. Men stadig. OK, så det er en undervisning øjeblik, right? Det er nu, hvad vi beskriver som en fejl. Et eller andet sted på vejen, vi gjorde nogle aritmetiske forkert, eller nogen satte sig ned, eller venstre, eller noget gik galt. Men det er fint. Fordi selv stadig, vi fik temmelig tæt på. Og jeg ville argumentere for, at vi kom til den forkerte besvare en masse hurtigere, end jeg ville have bruger min mere lineær tilgang. Så lad os antage, at vi rent faktisk få det rette, men synes nu over, hvad skete hver gang, kontra min egen naive peger algoritme. En, to, tre. Hvis der er faktisk 729 eller 637 personer her, ville der have taget mig bogstaveligt 637 eller 729 pointings af fingeren og forøgelse min samlede optælling. Og jeg kunne gøre lidt bedre ved går to, fire, seks, otte, og det dobbelte hastighed, måske endda tredobbelt eller firdoble, afhængig af hvor godt jeg kan gør, at tælle i mit hoved. Men denne tilgang, at du fyre tog var fundamentalt anderledes. Fordi i begyndelsen, alle jer stod op. Så alt 729. Og så bogstaveligt halvdelen af du sad. Og efter det, en anden halvdelen af ​​du sad. Og efter det, en anden halvdelen af ​​du sad. Og det samlede antal gange, som du fyre kunne have siddet ned er nogenlunde otte eller ni eller ti i alt tider, afhængigt af, hvad vores samlede optælling er. Og vi kan sortere i gøre dette den anden vej. Hvis vi havde 1.024 personer i rummet, samlede antal gange, du kan halvere 1.024 mennesker er 10. Nu tænker over det i den anden retning. Antag, latterligt, at vi havde, siger fire milliarder mennesker i dette rum, eller et lidt større rum. Hvor mange gange ville vi være gået gennem denne algoritme, således at halvdelen af denne klasse sidder ned? Det er kun kommer til at tage 32 sådanne drift, selv i en klasse af størrelse fire milliarder. Hvorfor? Fordi fire milliarder går til to mia går til en million, går til 500 millioner går til 250 million, prik, prik, prik. Jeg kan kun gøre denne deling nogle 32 tidspunkter, på hvilket tidspunkt, alle undtagen én person ville blive efterladt stående. Og det også er en slags magtfuld idé, at vi i stigende grad vil prøve at gearing i dette kursus, og programmering og datalogi mere Generelt er disse bakterier i en idé med som vi derefter kan løse problemer meget, meget mere kraftfuldt. Så vi startede ganske enkel med det pseudokode og en fyr i et rum, men nu med et helt rum fuld af mennesker har vi gjort fundamentalt bedre. Nå, lad os nu overgang fra pseudokode til nogle konkrete kode. Dette sprog du er ved at se ske at blive kaldt JavaScript og vi vil vende tilbage til dette i retning af semesters afslutning. Det er et programmeringssprog, som du bruger til at lave hjemmesider og andre sådanne software i disse dage. Og vi har brugt det, takket være en ven af vores på Stanford, indkode til nogle skjulte oplysninger her. Dette er kunsten steganografi, så at sige, hvor du kan skjule oplysninger i hvad der ellers synes at være støj eller en helt anden billede helt. Men indlejret i denne bestemt billede er faktisk en hemmelig besked slags. Så lad mig gå videre og trække op det samme billede her, dette tid i en webbrowser. Og jeg har tænkt mig at vinke min hånd på nogle af detaljerne for i dag, især for dem af jer der det ligner ikke kun JavaScript, men græsk, som en helt uvant sprog. Men dette er et eksempel på et programmeringssprog. Og for nu, tage på tro på, at denne første linje kode - og kode, jeg bare betyde tekst. Tekst, jeg kunne have bogstaveligt indtastet til Microsoft Word, I, hvis havde rigtige software til at så gøre noget med det. Kildekode, programmering kode, er egentlig bare tekst, og det ser anderledes baseret på, hvad sprog du bruger, ikke ulig engelsk og Spansk og russisk alle ser anderledes når du skriver dem på tastaturet. Så dette første linje, tager for nu tro, blot åbner en grafik fra internettet, at støjende grafik vi lige så. Denne næste linie her er et eksempel på en loop, og vi faktisk så, at samme jargon i TED video. En løkke er noget, der sker igen og igen, og selvom dette absolut ser kryptisk, med nøgleordet for, og nogle parenteser, og nogle semikolon. Vi vil vende tilbage til dette inden længe, men at sløjfe der hovedsagelig er fortæller programmet, gentage over alle af disse støjende prikker, venstre fra til højre, top til bund. Fordi i slutningen af ​​dagen, et billede gerne dette - og du kan faktisk slags se det på denne projektor - er egentlig bare et gitter af prikker. Så vi kan identificere hver enkelt af disse punkter ved et koordinatsystem, x, y, med og dette program, kan vi nu begynde at gøre noget for disse prikker. Så hvad jeg har tænkt mig at gå videre her og gør, er jeg har tænkt mig at foretage nogle ændringer. Først vil jeg tænkt mig at gå videre og slippe af alt dette grønlig og blålig støj, og jeg har tænkt mig at gå videre og skriv følgende ganske kryptisk syntaks. im for billedet. sæt blåt ved placeringen x, komma, Placeringen y, til 0. Med andre ord, vil jeg bare slukke for alle de blå prikker i det billede. Jeg har tænkt mig at gå videre nu, og klik på denne Run / Save-knappen, og du vil mærke på højre side, det resulterende billede vises. Nu er det super grøn, men det er ikke overraskende, fordi jeg bogstaveligt talt vendt slukket, ved at lave en 1 en 0, af alle det blå i dette billede. Nå, nu lad os gøre det lidt mere. im til billedet, dot setGreen, x, y. Og det betyder bare gentage fra venstre mod højre og derefter fra top til bund. Slå funktionen fra med en værdi af 0, så godt. Gem. Og på projektoren, kan du faktisk ikke rigtig se noget overhovedet. På min laptop skærm, I, hvis peer i blot den rigtige måde, kan jeg se lidt af en billede, fordi de er stadig nogle røde derinde. Hvis du nogensinde har hørt akronymet RGB - rød, grøn, blå - det er med henvisning til denne sammensætning af et billede ved hjælp af netop disse tre farver. Og lige nu har vi smidt væk alle grønne, alt blåt, men der er ikke meget rødt. Så lad mig skrue op for rødt. Hvordan kan jeg gøre det? Nå, først vil jeg bede dette program et spørgsmål. Jeg har tænkt mig at gå videre og lad os kalde det en variabel, ligesom i algebra. Du kan have x eller y eller z. Jeg har tænkt mig at erklære en variabel og sige, sat i denne variabel, midlertidigt, værdien af billeder getRed værdi på x, y. Og igen, vi vil komme tilbage til alle af denne detalje i fremtiden. Men for nu, blot tage på tro, at denne linje beder programmet, hvad er den røde værdi ved x, y? På det pågældende prik? Så jeg har tænkt mig at gøre noget for det. Så jeg har tænkt mig at gøre billedet dot sæt rød ved x, y, y, men denne gang jeg har tænkt mig at øge det ved at gøre røde tider, lad os sige, 10. Så øge det ved en faktor 10. Lad mig zoome ud nu, og klik kunne løbe / Gem. Og voila, der var der hele tid, selv om vores menneskelige øjne kunne ikke helt se det. Så igen, denne nu er reel kode, en eksempel på et sprog, som vi vil komme tilbage til inden længe. Men indse, især dem af jer uden en sådan erfaring, er det helt snart at vi selv vil være skrive kode som den der. I virkeligheden som et værktøj, du er alle noget fortrolig, måske, er CS50 s eget kursus-shopping værktøj, som var faktisk genstartet denne sommer af nogle af CS50 egne tidligere elever, nu vende TFs. Så det sker for at være en indbygget hjemmeside på et sprog, der kaldes PHP. Det bruger en database kaldet MySQL, tingene som vi får vores hænder beskidt senere i semesteret. Men tro det eller ej, selv noget ligesom dette i sidste ende reducerer de enkleste af loops og betingelser, og grene, som dem, vi oplevede bare en øjeblik siden i TED video. Hvad jeg troede, jeg ville gøre nu, er aktien ikke bare noget, vi har personale gjort for campus, men snarere noget en tidligere elev - tre studerende, i virkeligheden - gjort det seneste år, Sierra, Daniel og Sam, den sidste af dem havde ingen forudgående programmering erfaring da han tog CS50. Og for deres afsluttende projekt, de udstillet på CS50 Fair, en program kaldet wrdly, hvilket er en web-baseret program, som de gjorde denne video, som jeg troede, jeg ville dele med give dig en fornemmelse af, hvad der er muligt ved udtrykket udgang. [MUSIC Playing] DAVID MALAN: Det er fra uge Zero til uge 12 det seneste år. [Applaus] DAVID MALAN: Som en teaser, også, virkelig at hvæsse din appetit er, hvad der er muligt, kan du allerede har set, eller måske snart se, market.cs50.net, en nyt værktøj, som kursets hold har arbejdet på, denne gang i samarbejde med Harvard Student Organer, såsom at der starter i år og fortsætter forhåbentlig i dette kommende sommer har du en standard lejlighed på campus for at købe og sælge ting af interesse for dig. Og med partnerskabet via HSA, vil du også være i stand til at slippe elementer fra i en af ​​HSA fysiske butikker ved nogle i fremtiden, således at proxy ting, især som du graduate og ikke nødvendigvis ønsker at kassere ting, men faktisk betaler det videresende til folk, der kan følge dig her på campus. Så mere om det at komme. Men lidt mere konkret, et værktøj der er kommet ud af CS50 i de seneste år som nogle af jer måske velkendte, og andre af jer måske googling nu, CS50.net/2x, du finde et link til en Chrome forlængelse hvilket er demonstrative, hvordan du kan bruge JavaScript, det samme sprog, vi bruges med Eiffeltårnet et øjeblik siden, at gennemføre 2x afspilningshastighed for alle Harvard iSites videoer. Det er noget, der er bygget i CS50 egen videoafspiller. Men også dette til, hvis du begynder at grave i kildekoden, som vi vil lykkeligt til rådighed, vil du se, hvordan du kan endda løse problemer som disse, accelererende widgets i hjemmesider med som du allerede godt bekendt. Så et ord nu er på kurset og forventninger og hvad der ligger forude. Generelt vil vi faktisk samles her på mandage og onsdage - selvom denne fredag, vil vi samles, fordi af Shopping Week - 1:00 til 2:00, skønt undertiden indtil 02:30. I betragtning af at du derfor måske ønsker eller nødt til at tage nogle klasse på 02:00 fremefter, eller endda før, indser de Kurset er støtter, hvad der kaldes samtidige tilmelding, hvorved vi får understøtte et andragende til Ad bestyrelsen og din bopæl dekaner på dine vegne, hvis du har en konflikt sted i dette 1:00 til 02:30 rækkevidde. Head til denne URL online for yderligere oplysninger. Men i form af støttestrukturen der kendetegner CS50, for studerende mere og mindre behagelig ens, vi tilbyde forskellige spor af sektioner. Og det er et par uger væk, men inden længe vil du blive bedt om at din komfort niveau. Er du blandt dem mindre behagelig, mere komfortabel, eller et sted i mellem? Og vi har tre særskilte spor, der appellerer til netop de målgrupper. Så på intet tidspunkt i udtrykket skulle du engang har lyst til du konkurrerer mod enhver studerende med mere eller mindre baggrund end dig. Faktisk er det naturligvis menes at være langt mere samarbejdsorienteret og meget mere åben end det. Med hensyn til problemet sæt, vil du finde også, at ud over de Standardudgaven af ​​hver uge problem indstillet, er der ofte en "hacker edition ", der er beregnet til at være målrettet ved 5% til 10% eller deromkring af demografiske der er faktisk blandt dem mere komfortabel og gerne mere af en udfordring end standard udgave af denne Pset forventer. Flere detaljer om dem, der skal findes i pensum. Men også i der kan findes oplysninger på kurserne sene dage. Typisk problem sætter skyldes om torsdagen. Men du kan udvide mange af dine deadlines dette efterår fra torsdag til Fredage blot at møde os halvvejs, så at sige, besvare et par warm-up spørgsmål i nogle af ugens problemet sæt, der vil automatisk derefter give dig en ekstra 24 timer. Vi vil også slippe dine laveste score, som pr pensum. For at give dig en fornemmelse af, hvad problemet sæt er - fordi det er faktisk kursets problemet sæt, at sidste ende definerer næsten alle studerendes erfaringer, mere end foredrag i højere grad end sektioner flere grad end de fleste andre aspekt af kurset. Sidste år, for eksempel, begyndte vi som Vi begynder i år, med Scratch. Især denne fredag, vil vi bruge, for kun én dags tid, en grafisk programmeringssprog, som vi vil starte programmeringen ved at trække og droppe puslespilsbrikker der kun samle fysisk, hvis det giver mening at gøre det logisk. I næste uge, vi vil hurtigt overgang til C, en temmelig gamle, men meget lille og enkelt sprog, som vil give os mulighed for at virkelig gå 0-60 løbet af blot et par uger, og derefter parlay de samme færdigheder og viden om grundlæggende programmering konstruktioner i højere niveau sprog som PHP, JavaScript og endnu andre stille. Sidste år, den tredje Pset i løbet var, at kryptografi, en domain-specifik anvendelse, hvorved vi udfordret eleverne til at gennemføre nogen antal ciphers, programmer, som at forvrænge eller dekryptere information, at kryptere det. For hackeren edition, derimod Vi gav hacker eleverne en fil fra en standard UNIX computer indeholdende brugernavne og adgangskoder, sidstnævnte som var krypteret, og vi udfordrede dem hacker studerende til at dekryptere, som de bedst kunne, disse passwords, stadig på, at samme domæne. Scramble, et spil med, hvor nogle af jer er måske bekendt. En retsvidenskab stykke hvor vi spørge eleverne at gendanne data, der havde været ellers slettet fra min egen digitale kameraets compact flash-kort, som faktisk skriver software til at regne ud, hvor var nuller og ettaller i at digitale kamera, der tidligere komponeret en JPEG grafik? En udfordring af sorterer sidste år involverer skriver den hurtigste stavekontrol er muligt, konkurrerende mod venner og klassekammerater, hvis de gerne vil. Implementering Huff 'n Puff, en kompression program. Og så slutter semesteret med CS50 Finance, et web-baseret program med som du opretter en eTrade-lignende website at købe og sælge aktier, så at tale, ved faktisk at trække næsten real-time citater Yahoo! Finansiering. Hvad vi ikke gjorde sidste år, var ét problem sæt, der forbliver ikke desto mindre en favorit. Hvis du aldrig har gået til shuttle.cs50.net, vil du se en brugers interface en lidt ligesom dette. Men for to år siden, klassen implementeres ved hjælp af Google Maps og Google Earth plug-in og en lille smule af kyndige med at køre rundt campus, så målet i dette spil var, som du kan se nogle af de ansigter, er at køre rundt campus søger personale, undervisning stipendiater og CA, og når du gør, sætte dem på din shuttle bus. Ingen af ​​dem synes faktisk at være her, så vi kommer til at indtaste en snyde kode. [Latter] DAVID MALAN: Der går vi. Ok. Og her nu er personalet snøret hele campus. Og som du kan se, på højre hånd side af skærmen, shuttle bus har tomme pladser. Og målet var at skrive kode med at simulere dette kørsel og optagning og slippe off af passagerer. At man, også ved hjælp af et sprog hedder JavaScript. Så indse, at programmer som der vil være på vores samme bane dette år, så godt. Med hensyn nu, for supplerende støtte, Vi har kontortid. Som du måske har set i dit eget hus spisesal eller i Annenberg, vi vil være i huset spisning haller fire nætter om ugen - Leverett, Pfoho, Eliot og Annenberg dette år, fra 20:00 til 11:00. Og hvad vi troede, vi ville gøre dette år er noget lidt anderledes. Hvis du har hørt rygter sidste år, at det var lidt for stressende, dette års kontortid, som vi vil beskrive i næste uge, vil være mere organisk, hvorved ved ankomsten, vil du være sendes til en bestemt tabel hvor flere medarbejdere venter, og vi vil gøre tingene meget mere økologisk. Ikke mere kø, ikke mere iPad, men hellere have mere intim samtaler omkring et bord for bare otte eller så studerende så vi omtrentlige fornemmelsen af ​​hvad der ellers ville være en meget mindre klasse. Vi tilbyder, så godt, disse ting vi kaldet walkthroughs, filmet videoer forhånd af en af ​​kursets undervisning stipendiater, Zamyla, hvor hun fører dig gennem ugen problem sæt, der tilbyder tips og tricks til udfordringer, der lå forude. Og omvendt, når problemet sæt er skyldes dette år, vil vi også frigive små klip kalder obduktioner, at faktisk gå dig igennem repræsentative løsninger, både gode og dårlig, via hvilket du kan udlede, hvordan du kunne have eller burde have implementeret din egen løsning. Og hvad vi vil tilbyde for første gang dette år så godt, især for de studerende, der benytter sig af kurset øvrige ressourcer, men ikke desto mindre kæmper alt for meget, kurset selv vil parre de studerende, som ressourcerne tillader, med undervisere, så De har en meget mere intim mulighed end hus spisesale give mulighed for en-til-én assistance. Nu er en endelig glimt på nogle de endelige spil i syne. Du vil måske være bekendt med Den CS50 hackathon. Nå, der kommer i december, 8:00 PM til 7:00, ved begyndelsen af Læsning Periode, vil være en anledning at samles med klassekammerater - dette ville være omkring 21:00 - hvor du dykker ned i din endelige projektets gennemførelse sammen klassekammerater, venner og mad. Dette ville være omkring 01:00, når det første parti af fødevarer ankom. Og det er omkring 4:00, at bestemt år på CS50 hackathon. Men den sande klimaks af kurset er betydet for CS50 Fair, en campus-dækkende udstilling af dine egne afgangsprojekter, hvortil familie og venner er alle inviterede, som vores personalekonsulenter og vores venner fra industrien. Dette, for eksempel, er et glimt af 2.000-plus mennesker, der har deltaget i seneste år. Udtryk som dette er ikke ualmindeligt, og ligeledes gør dit klassekammerater glæde i tingene du har opnået. Og faktisk mod dette formål har vi en start-of-sigt begivenhed, samt. Hvis ting som dette appellerer til dig, eller du er mindst spændt på, hvad dette ved, at en ny tradition for Kurset hedder CS50 Puzzle Day. Og dette blev indført for et par år tilbage til virkelig at signalere til campus at datalogi ikke handler om programmering, og det er bestemt ikke omkring omfavne kun de studerende der har forudgående erfaring. Det handler i virkeligheden om problemløsning mere generelt. Og så puslespil Day, i løbet af de sidste par år nu, har udviklet sig til en hyggelig partnerskab med vores venner på Facebook, hvor der vil være fantastisk præmier og pizza over floden på i-lab denne kommende lørdag. Head til denne webadresse med to eller tre venner, hvis du gerne vil deltage i denne nye tradition. Så jeg vil gerne bede om, at du holder en ting i tankerne, og vi har fået bare en to minutter klip på hvilke at lukke dag. 73% er antallet at huske. Kage, vil også venter dig uden for dette tværskib som vi udsætte på bare et par øjeblikke, hvilket er en tradition af kurset. samt Men det er nøglen citat fra kursets pensum at huske på. Der i sidste ende betyder noget i dette kursus er ikke så meget, hvor du ender i forhold til dine klassekammerater, men hvor dig, i uge 12, ender i forhold til dig selv i uge 0. Men glimt, at vi vil forlade dig med her i dag, er det sidste her af vores samme Daniel gjorde hvem wrdly video bare for et øjeblik siden. Jeg forlader dig med denne glimt af, hvad der ligger forude. Og når vi gør det, hvis vi kunne få CS50 personale fra den forreste del af rummet at komme videre op på scenen for at male alle jo mere af et visuelt billede af, hvad der venter dig i år - få akavet. Vi slutte med dette her på skærmen. [MUSIC Playing] DAVID MALAN: Dette er CS50. [MUSIC - MATT & KIM, "Det er i orden"] SPEAKER 1: Jeg elsker CS50 mere end katte. SPEAKER 2: Whoaaaa! [Latter] DAVID MALAN: Denne er altså CS50. Vi vil se dig på fredag. [Applaus og råber] Fortæller: På det næste CS50, på scenen en demo ikke går som planlagt. DAVID MALAN: Vi ønsker at finde Mike Smith i denne telefonbog. Nå, hvad er dine instinkter? Jeg kunne springe nogenlunde til midten af telefonbogen, blik ned, se, at Jeg er på M, og jeg ved nu, at Mike Smith er ikke til venstre. Han må være til højre. Og så på dette punkt, vi kan bogstaveligt talt rive - på dette punkt, kan vi bogstaveligt rive - på dette punkt, kan vi billedligt rive telefonbogen i halve. [Ukelele strumming]