[Musikk spilles] [MUSIC - Rossini, "Ranz DES Vaches "fra WILLIAM TELL] [MUSIC - PÅ NORSK BEAT, "MARS Av svivelen Heads "] [Applaus og jublende] DAVID MALAN: Så dette er CS50. Mitt navn er David Malan. Og 73% av dere ikke har erfaring med informatikk, i motsetning til hva du kanskje tror. Så i dag tenkte vi at vi ville chip bort ved at mangel på kjennskap, men også gi deg en følelse av, for de av dere med mer komfort, hvilke retninger du kan gå dette semesteret. Så la oss starte med dette. Jeg har virkelig ingen anelse om hva som er inni en datamaskin, selv om, som deg, jeg bruker den hver dag. Men det er en slags boks, og det er ikke mange innganger inn i den. Minimalt, det er, hva? Sannsynligvis en strømledning. Og faktisk med en denne ingrediensen, elektrisitet, synes vi å være i stand til gjør ganske mye i disse dager. Men ved slutten av dagen, vi må representere de tingene at vi bryr oss om. Vi må representere informasjon i noen form. Og du er sannsynligvis minst vagt kjent med ideen av binære eller biter en eller annen måte, datamaskiner redusert til nuller og enere. Men kan vi omfavne det og minst sette litt lys på det? Så jeg har disse små bordlamper her. Jeg har strømkontakt her. Og jeg kommer til å foreslå at det inne av datamaskinen er minst ett av disse tingene, noe som kan for å bli slått på eller av. I dette tilfellet er det faktisk en bordlampe, men på lavere nivå, er det noe kalt en transistor. Men i vår verden, det er en bordlampe, så Jeg kommer til å gå videre og koble dette inn i min strøm her. Og jeg hevder at bruk denne enkle, enkel enhet, denne enkle bryteren, jeg kan representere informasjon. For eksempel akkurat nå, er jeg representerer ingenting, ikke sant? Jeg representerer det jeg vil kalle 0 eller usant, det motsatte av noe faktisk er til stede. Men hvis jeg bare slå denne bryteren, nå har jeg representert en en. Så bruker dette veldig enkelt stykke minnet, hvis du vil, kan jeg representerer informasjon. Nå dessverre, min datamaskin kan ikke gjøre så mye. Det kan bare representere to verdier i hele verden - 0 eller 1.. Men hva er en åpenbar løsning, nå, hvis vi ønsker å utvide vår datamaskinen minne og representerer mer enn 0 og 1? Vel, la oss ta en annen slik bit. La oss ta en annen bryter, en annen transistor, men du vil tenker på det. La meg gå videre og koble dette inn i min datamaskin også. Og jeg kommer til å kreve, nå, at ved bruker litt mer strøm og snu flere av disse bryterne på og off, jeg kan representere flere slike informasjon. Så akkurat nå, er dette en. Hvis jeg ønsker å nå representere 2, jeg kunne gjøre dette. Men vanligvis, konferansesenter, som vi vil til slutt se, vil ha meg til å gjøre dette. Så dette er 0, er dette en. Dette ville være to. Og ikke overraskende, vil dette være tre. Så på denne måten, likevel, kan vi telle opp enda lenger? Hvis jeg får en tredje bit, en tredje bytte, hva er det høyeste tallet jeg kan nå teller opp til fra 0? Så 7 hvis jeg starter på 0, ikke sant? Fordi hvis jeg slår dette lyset på og faktisk koble denne tredje og siste lys inn i min stikkontakten her, da har jeg muligheten til å representere noen av de to verdiene her, to verdier her, to verdier her - og så jeg kan representere to ganger to ganger 2, eller åtte mulige verdier. Og hvis jeg begynner regnskap på 0, så det er 0, 1, 2, 3, 4, 5, 6, 7. Så dette binært. Det er virkelig så enkelt som det. Og jeg vil påstå at dette er faktisk ganske kjent for de fleste alle i dette rommet. La meg gå videre og åpne en litt tekst editor her. Og du kanskje husker fra grunnskolen at vi hadde ting som de hundrevis sted, tiendeplassen, og de sted. Og huske på at hvis du hadde noen desimal nummer, som noe tilfeldig som 123, ville du i hovedsak skrive det ut i form av disse tre kolonner. Og hvorfor er 1, 2, 3 hva vi kjenner som 123? Vel, i kolonnen lengst til venstre, har vi en 100 pluss to 10s, så det er 120, pluss tre 1s, så det er 123. Nå er denne verden som vi bare opplyst er nøyaktig den samme som du har blitt kjent med i mange år, bortsett fra nå, våre kolonner ikke makter 10. De er bare makter to. Så mens det er de sted, dette kommer til å være den toere sted, er dette kommer til å være firere sted. Og fordi jeg bare bruker den enkleste mekanismer for å snu ting på og av - det går strøm eller elektrisitet ikke flyter - Jeg vet ikke helt har samme ekspressive utvalg som 0 til ni. Vi kommer til å holde det super enkelt i denne verden av datamaskiner. Jeg har bare 0 eller 1 - av eller på, falsk eller ekte. Og så hva jeg representerer akkurat nå er 1, 1, 1, fordi hver av disse lysene lyser. Og det gir meg en fire pluss ett to, så det er seks, pluss en 1, og det er syv. Og ergo gjør denne sekvensen av tre bits representerer nummer 7. Så all denne tiden, innsiden av datamaskin, har vært en rekke transistorer, noe antall bits. Men ved slutten av dagen, vi kan representere informasjon så enkelt som det. Nå dessverre, vi har bare telles opptil 7 i CS50 så langt, men forhåpentligvis kan vi gjøre litt bedre enn det. Og ja vi kan. Anta at vi som mennesker bare vilkårlig bestemt at vi skal å assosiere tall som 1 og 2, 3, 4, 5, 6, 7, med spesifikke bokstavene alfabetet. Og for historiske årsaker, kommer jeg til å starte noe tilfeldig, men jeg er kommer til å si, mennesker, skal vi bestemmer som en standard over hele verden som 65 representerer antall bokstaven A. 66 skal representere B. Dot, prikk, prikk. 90 skal representere bokstaven Z. Og la oss anta, hvis vi virkelig sette noen tenkte på det, kan vi komme opp med tall for utropstegn og små bokstaver, og faktisk, andre har gjort det for oss. Så nå hadde vi biter som vi kan representerer tall, tall som vi kan representere bokstaver, og med bokstaver kan vi nå begynne å komponere e-post og utskrift tegn på skjermen. Så la meg invitere, hvis jeg kunne, åtte modige frivillige - som ikke tankene dukker ikke bare på kamera, men på internett - å komme opp her og representerer åtte slike biter, snarere enn disse tre. Så hva med en, to? Hva med tre? Hva med fire i lys blå, fem på enden? Om noen over her? Seks i front, sju i front, og åtte foran, så vel. Så jeg bare så skjedde å komme forberedt med en hel haug med papirlapper. Og på disse bitene av papir er tall som representerer det kolonner dere kommer til å representere. Så du vil være - hva heter du? STUDENT: Anna Leah. DAVID MALAN: Anna Leah, du vil være den 128s kolonnen. Du er? STUDENT: Chris. DAVID MALAN: Chris vil være 64s kolonnen. Du er? STUDENT: Dan. DAVID MALAN: Dan vil være 32s kolonnen. STUDENT: Pramit. DAVID MALAN: Pramit vil være 16S kolonne. STUDENT: Lillian. DAVID MALAN: Lillian vil være 8s. STUDENT: Jill. DAVID MALAN: Jill vil være 4s kolonnen. STUDENT: Mary. DAVID MALAN: Mary vil være 2s, og? STUDENT: David. DAVID MALAN: David vil være 1s kolonnen. Så hvis dere kunne gå litt fremover slik at alle kan se. Hva dere ikke ser er at på baksiden av disse papirlapper er en liten jukselapp som er i ferd med å instruere disse åtte bits til enten heve sin hånd eller ikke heve sin hånd. Hvis deres hånd går opp, er de representerer en en. Hvis deres hånd holder seg nede, de er representerer en 0. I mellomtiden har vi publikum bør være i stand til å finne ut, basert på denne kartlegging, hva tre bokstaver ord disse folk er i ferd med å stave. Så i løpet av et øyeblikk, du kommer til les første linjen på baksiden av din jukselapp, og du er enten kommer til å heve eller ikke heve hånden. Hvis du er en 1, heve deg, hvis du er en 0, står du der forkjært, akkurat sånn. Go. Hvilket nummer, først og fremst, er disse gutta representerer? 66. 66, ikke sant? Vi har en i 64s kolonnen, en 1 i 2s kolonnen. Det gir meg 66, så det ser ut å representere B. Så dere har stavet - OK, det er nok. B. Så nå skal vi flytte inn vår andre brev. Go. Hvem er raskest i matte her? Så 79. Igjen, hvis vi legger opp alle kolonnene der det er en 1, for tiden, bare som vi gjorde før med den enkleste eksempler på 7, nå er vi får nummer 79. Som ifølge kartleggingen vår er bokstaven O. Så vi er nesten der. B, O. Og til slutt, gå. Hva er det de representerer nå? Mindre konsensus. Det er bare en absolutt bilyd. Ja, det er faktisk 87. Bra. Så hvis vi nå kartlegge det tilbake opp til - la oss begynne å ringe vår ASCII diagram, American Standard kode for Informasjon Interchange. Det gir oss brevet - ikke "bo" men "bue". Og det er et perfekt cue for dere å ta en bue og hodet på ryggen. Tusen takk. [APPLAUSE] DAVID MALAN: Du kan beholde dem. Selv om faktisk, ville noen som en bordlampe, også? [HOOT FRA PUBLIKUM] DAVID MALAN: Desk lampe? [Latter] DAVID MALAN: Really? Bordlamper for alle? OK. Så starter med meget enkleste prinsipper, har vi nå ikke bare telles opp fra 0 og helt opp til syv, har vi antatt at bare ved å kaste mer bits eller mer lys eller flere transistorer på dette problemet, kan vi representerer større og større tall, og ergo, større og større områder av alfabeter, som engelsk. Og bare la oss ta på tro for i dag at tilsvarende kunne vi begynne å representerer grafikk og video, og noen rekke andre medier som vi er kjent i dag. Så dette er CS50, og i denne klassen sammen av dere er, igjen, veldig mange klassekamerater som har så lite opplever som deg. Og jeg nevner dette bare fordi ganske ofte, blant annet som nylig som en av freshman rådgivning hendelser og ved siste vårens sophomore rådgivning hendelse, hører vi ofte fraskriver studenter når man kommer opp til CS tabellen, vel, Jeg har tenkt på å ta denne intro klasse, men jeg er egentlig ikke en datamaskin person. Eller, men alle sikkert vet mer enn meg. Og jeg sette dette i den største skriften mulig, for å formidle dette budskapet som det er faktisk ikke tilfelle. Og hvis du lurer på, bør Jeg, faktisk, være her? Innse at ikke bare er dette kursets Tittelen Introduksjon til Computer Vitenskap, er det Introduksjon til Computer Science I. Så det er faktisk et sekund slik innføring. Så du er ikke, faktisk, på feil sted. Og blant de målene jeg har for i dag er å lindre slike klager du kan ha, men også å male et bilde av hva som er i butikken for elevene mindre og mer behagelig både i dette kurset. Men først et ord på en av brosjyrer du har i dag, blant annet er en rekke spørsmål. Det har vært en visjon av oss for en stund nå å innføre en ny sensur alternativ til dette kurset - nemlig SAT / unsat. Filosofisk for meg, det er mye, mye, mye viktigere at elevene i denne klassen engasjere seg med materiale, bli utfordret av materiale, og bekymre deg langt, langt mindre om mekanikken i faktiske score og bokstavkarakterer ved semesterets slutten, men virkelig omfavne kurs og dens materiale. Og egentlig dette føles mer generelt, for hva som er interessant for dem, for å føler utfordret og belønnet, men uten frykt for å mislykkes. Og ja, dette er for et tilbakevendende tema i denne og andre innledende kurs i andre felt, som du har dette beven når det gjelder sette ens tær i ukjente farvann. Jeg selv, tilbake i 1995, var en førsteårsstudent. Jeg ble veldig mye fokusert på å være en Gov prosessanlegg her. Og likevel vil jeg alltid vokst opp med en bit av interesse for informatikk. Jeg var alltid nysgjerrig. Men tilbake da, selv hadde jeg denne frykten for selv stepping foten i CS50, så mye slik at jeg ikke engang handle det freshman year. Og den eneste grunnen til at jeg satte en fot i dør sophomore året var fordi jeg fikk lov til å ta det bestått / ikke bestått. Men selv bestått / ikke bestått nødvendig at jeg får opp nerve å gjøre en avtale med professor Kernehan på den tiden, bringe denne store ark, og be ham for hans signatur og hans tillatelse til å utforske disse ukjente farvann. Og det har ikke hjulpet de siste årene at når du gjør dette i CS50, når vi pleide å være bestått / ikke bestått, på samme måte ville dusinvis eller hundrevis av klassekameratene dine måtte komme opp, Gud forby, på foran Sanders med dette skjemaet, som i noen sinn representerer en manglende evne, Jeg tør si, til å utføre er dine jevnaldrende nivå. Som er latterlig, men jeg tror det er den mentaliteten. Og det har aldri vært i denne kulturen av SAT / unsat, eller bestått / ikke bestått mer generelt, i dette kurset, eller egentlig på denne campus. Så dette året vi endret det. Jeg ville være ekstatisk halvparten av denne klassen eller flere endte opp med å ta CS50 SAT / unsat. I et års tid, ville det være fantastisk hvis nesten alle er. Deretter kanskje vi skal jobbe på bokstavkarakterer ved Harvard College mer generelt. Men for nå, vil vi gjøre dette innenfor vår egen sfære, og jeg ville hjertelig oppfordrer deg til å gjennomgå de spørsmål og stille spørsmål som du ønsker, slik at forhåpentligvis du, i motsetning til meg, vil ikke helt har den samme frykten faktor når utforske hva som er nok et ukjent sted. Så hva er CS50? Det er en introduksjon til intellektuelle foretak av datamaskin vitenskap og kunst av programmering. Men hva betyr det egentlig? Vel, så langt, snakket vi veldig kort å representere informasjon. Men anta at vi faktisk ønsker å gjøre noe med det. Vi trenger å innføre begrepet hva vi vil kalle en algoritme. En algoritme er en fremgangsmåte, en prosess, et sett av instruksjoner for gjøre noe. Og en algoritme kan være noe super enkelt. For eksempel, et eksempel med hvilke noen av dere kan bli kjent er dette ting her. Så denne boken her er stadig datert, men en gang i tiden, det inneholdt en hel masse navn og telefonnumre. Og ja, hvis jeg ønsket å finne noen i denne telefonboken - si, noen som heter Mike Smith - Jeg kunne finne Mike Smith i en rekke av ganske enkle måter. Jeg kunne starte på begynnelsen og gå videre til side 1, ikke der. Side 2, ikke er der. Side 3. Er at algoritmen, er at prosess, riktig? Så det er riktig, ikke sant? Jeg er litt som en idiot for å gjøre det i den måten, men til slutt vil jeg finne etternavnet S, og forhåpentligvis Mike er i denne delen, og jeg vil bli ferdig med algoritmen min. Men sikkert er det ikke intuitivt. Mest Ethvert fornuftig menneske i dette rommet ville ikke ha gjort det. Hva ville du ha gjort? Du ville ha gått rett til midten, ikke sant? Omtrent til midten. Og du skjønner, oh, disse er Ms Så Mike Smith, etternavn være Smith, er ikke klart, deretter i venstre halvdel av boken. Han må være mot S er i riktig. Og på dette punktet, selv om de fleste av oss ikke gjør dette i virkeligheten, kan vi bokstavelig talt rive dette problemet i to. [Heier og applauderer] DAVID MALAN: Takk. [Heier og applauderer] DAVID MALAN: Du kan bokstavelig talt rive dette problem i to, forlater meg med, bokstavelig, et problem halvparten så stor. Så hvis denne telefonen boken var - og det sannsynligvis var - ca 1000 sider, nå det er bare 500 dollar. Hvis jeg gjør dette igjen og jeg skjønner, oh, faen, jeg gikk for langt, jeg er i Ts delen, kan jeg like - figurativt eller bokstavelig talt - rippe telefonboken - det var faktisk mye lettere at tiden. Jeg kan bokstavelig talt rive telefonboken i halvparten, forlater meg nå med ikke 1000, ikke 500 - 250 sider. Og jeg kan gå 125, og halvparten av det, og halvparten av det, og halvparten av det, til slutt vil jeg sitte igjen med bare en enkelt side. [Latter] DAVID MALAN: Det er del jeg mislykkes på. En enkelt side som Mike er forhåpentligvis. Nå er de forskjellige algoritmer kan være slags vurdert eller evaluert i forskjellige måter. Den første var veldig lineær, ikke sant? Slå side, se etter Mike. Slå side, se etter Mike. Det er veldig lineær. Hvis det er flere sider i telefonen bok, er det sannsynligvis kommer til å ta meg ett sekund, en mer tidsenhet, men vi beregne tiden. Så jeg kan tegne som dette denne linjen her, hvorved etter hvert som størrelsen av den problemet øker fra venstre til høyre - telefonboken blir mindre til større - og tid kommer til å øke på den vertikale aksen, jo større telefonboken er. Så n er bare en generell variabel som IT-forskere bruker til å representere noen verdi, noen nummer. Så n kommer til å øke lineært. Doble størrelsen på telefonlisten, er det kommer til å ta meg dobbelt så mye tid, mest sannsynlig, for å finne Mike. Nå kunne jeg ha vært smart om dette, ikke sant? Jeg begynte å bli lei fort. Kunne ha gjort dette ved toere. Så to sider, deretter fire, deretter seks, deretter åtte. Og jeg kunne begynne å fly gjennom det en litt raskere, om enn på mindre risiko for overshooting Mike, men at kurven er ikke kommer til å være så forskjellig. Det er fortsatt kommer til å være en rett linje, men litt raskere. Men hva gjorde jeg? Jeg faktisk gjorde noe fundamentalt bedre. Jeg oppnådde det vi kaller logaritmisk tid, logg av n, hvorved denne grønne linje har en mye, mye, mye mindre straight edge til det. Og heller, tyder det, som det liksom mot uendelig aldri så gradvis, at jeg faktisk kunne ta en 1000-siders telefonboken, doble sin størrelse neste år - fordi anta mye flere mennesker flytter inn til byen. Så nå har jeg fått 2000 sider, men hvordan mange flere skritt er at smartere algoritme kommer til å ta? Bare en. Jeg mener, det er en mektig ting. Hvis vi går til 4000 sider neste år, som kommer til å ta meg bare to trinn. Så du kan kaste større og større problemer på meg, ikke ulikt nettet er kaste større og større problemer hver dag på Googles og Facebooks av verden, og det er ikke en så big deal. Fordi jeg legge mer omtanke og omsorg i min algoritme som å løse problemene effektivt. Og ja, vil det være en av målene for dette kurset. Du vil, langs veien, lære å programmere. Du vil lære å programmere i en rekke språk. Men ved slutten av dagen, er det selvsagt om å løse problemer og komme flinkere til å løse problemer - og som i tilfeller som dette, løse problemer mer effektivt. Nå så langt, har vi gjort dette ganske intuitivt. La oss introdusere noe ganske generisk kalt pseudokode. Så får vi til slutt får, i dette kurset, til ulike programmeringsspråk. Men i dag vil vi gjøre det på engelsk-lignende syntaks, hvor du bare slags si hva du mener, men du er aldri så konsis og du trenger ikke bekymre deg grammatikk og fullstendige setninger. Du bare uttrykke deg som konsist som mulig. Så pseudokode er engelsk-lignende syntaks som representerer et programmeringsspråk. Og mot dette målet, la meg foreslå at vi nå modellere prosessen vi bare beskrevet for å telle noe litt annerledes, denne gangen tar et se på dette fem-minutters video produsert av våre venner på TED at definerer hva pseudokode er, definerer hva algoritmisk tenkning er, og selv men eksempelet du er i ferd med å se er, i seg selv, super enkel, det er kommer til å begynne å gi oss den mentale modell, vokabular, som å gjøre mye, mye mer kompleks algoritmer ganske raskt. [BEGIN VIDEOAVSPILLING] [Musikk spilles] FORTELLER: Hva er en algoritme? I informatikk, er en algoritme en sett med instruksjoner for å løse noen problemet steg for steg. Vanligvis blir algoritmer utført av datamaskiner, men vi mennesker har algoritmer, så vel. For eksempel, hvordan ville du gå om å telle antall av personer i et rom? Vel, hvis du er som meg, ville du sannsynligvis punkt på hver enkelt person, en på gangen, og telle opp fra 0. 1, 2, 3, 4, og så videre. Vel, det er en algoritme. Faktisk, la oss prøve å uttrykke det en litt mer formelt i pseudokode - Norsk-lignende syntaks som ligner et programmeringsspråk. La N lik 0. For hver person i rommet, satt N lik N pluss en. Hvordan tolke dette pseudokode? Vel, linjen man erklærer, så å si, en variabel kalt N og initialiserer verdien til 0. Det betyr bare at det i begynnelsen av vår algoritme, den tingen som vi teller har en verdi på 0. Tross alt, før vi begynner å telle, Vi har ikke regnet noe ennå. Kalle denne variabelen N er bare en konvensjon. Jeg kunne ha kalt det mest noe. Nå linje to demarks starten på en loop, en sekvens av trinn som vil gjentas et antall ganger. Så i vårt eksempel, steg vi tar teller mennesker i rommet. Under linje to er linje tre, som beskriver nøyaktig hvordan vi vil gå om å telle. Innrykk innebærer at det er linje tre som vil gjenta. Så hva pseudokode sier er som etter start på 0, for hvert person i rommet, vil vi øke N etter en. Nå er denne algoritmen riktig? Vel, la oss banke på det litt. Fungerer det hvis det er to personer i rommet? La oss se. I tråd ett, initialisere vi N til 0. For hver av disse to personer, vi da øke N etter en. Så på den første turen gjennom loop, oppdaterer vi N 0-1. På den andre tur gjennom den samme loop, oppdaterer vi N 1-2. Og så ved denne algoritmen er slutt, er n 2, som overensstemmer faktisk antallet personer i rommet. Så langt, så bra. Hva med et hjørne sak, skjønt? Anta at det er 0 personer i rommet - foruten meg, hvem som gjør tellingen. I tråd ett, initialisere vi N til 0. Denne gangen, skjønt, gjør linje tre ikke kjøre i det hele tatt siden det ikke er en person i rommet. Og så N fortsatt 0, som overensstemmer med antall personer i rommet. Ganske enkelt, ikke sant? Men telle folk en om gangen er ganske ineffektiv, også, nei? Sikkert vi kan gjøre bedre. Hvorfor ikke telle to personer på en gang? I stedet for å telle 1, 2, 3, 4, 5, 6, 7, 8, og så videre, hvorfor ikke telle, 2, 4, 6, 8, og så videre? Det høres enda raskere, og det er helt sikkert. La oss uttrykke denne optimaliseringen i pseudokode. La N lik 0. For hvert par av personer i rommet, satt N lik N pluss to. Ganske enkel endring, ikke sant? Snarere enn count folk en om gangen, i stedet vi telle dem to om gangen. Denne algoritmen er altså to ganger så fort som sist. Men er det riktig? La oss se. Fungerer det hvis det er to personer i rommet? I tråd ett, initialisere vi N til 0. For at ett par av mennesker, vi da øke N med to. Og så ved denne algoritmen er slutt, er N 2, som overensstemmer faktisk antallet personer i rommet. Anta at det er neste 0 personer i rommet. I tråd ett, initialisere vi N til 0. Som før, betyr linje tre ikke utføre i det hele tatt, siden det ikke er noen parene av mennesker i rommet. Og så N fortsatt 0, som faktisk stemmer overens med antallet personer i rommet. Men hva hvis det er tre personer i rommet? Hvordan fungerer denne algoritmen fare? La oss se. I tråd ett, initialisere vi N til 0. For et par av dem, vi da øke N ved to. Men hva så? Det er ikke en annen full par av mennesker i rommet, slik at linje to no lenger gjelder. Og så ved denne algoritmen er slutt, N er fremdeles 2, som ikke er riktig. Faktisk er denne algoritmen sies å være buggy, fordi den har en feil. Lar oppreisning med noen nye pseudokode. La n lik 0 for hvert par av mennesker i rommet. Sett N lik N pluss to. Hvis en person er fortsatt uparet, satt N lik N pluss en. For å løse dette problemet, har vi innført, på linje fire, en tilstand, også kjent som en gren som utfører bare hvis det er en person som vi ikke kunne sammenkobling med en annen. Og så nå, uansett om det er ett eller tre eller et odde antall mennesker i rommet, denne algoritmen vil nå telle dem. Kan vi gjøre det enda bedre? Vel, vi kunne telle i 3s eller 4s eller 5s og 10s, men utover det, er det kommer til å få en liten bit vanskelig å peke. På slutten av dagen, enten utført av datamaskiner eller mennesker, algoritmer er bare et sett av instruksjoner med for å løse problemer. Dette var bare tre. Hvilket problem vil du løse med en algoritme? [END VIDEOAVSPILLING] DAVID MALAN: Det er den eneste gangen Jeg vil vises i tegneserie form. Men hvor den historien bladene av, nå, hvordan kan vi gjøre bedre? Treere og firere, vi hevder, vi kan telle folk mye raskere, men vi kan gjøre fundamentalt bedre enn det? Og jeg satse vi kan. Hvis vi innfører en bit av vår egen pseudokode her, kommer jeg til å foreslå at vi kan oppnå en linje som dette. Vi kommer ikke til å telle folk en, to, tre, fire. Vi kommer ikke til å gå to, fire, seks, åtte. Vi kommer til å gjøre fundamentalt bedre ved å revurdere problemet, og i dette tilfelle, utnytte en ellers underutnyttet ressurs. På bare et øyeblikk, jeg håper du tilgir og humor oss ved å stå opp i sted, og da vi kommer til å spør hver av dere å ta på i din sinn nummer 1. Du deretter kommer til å stadig forkjært, som tiden går, finne noen andre som står, kombiner tallene dine sammen ved å legge dem opp. En av dere er da gå å rase til å sitte ned først, og den andre personen kommer til å gjenta. Så med andre ord, ved såing alle du med nummer 1, og deretter kombinere de 1s inn 2s og de 2s i 4-ere, med alle i økende grad sitte ned, bør vi, på slutten av denne algoritmen, har bare ett lån sjel som ikke sitte ned raskt nok, men som har hele publikum teller i hans eller hennes sinn. Så hvis du vil, la oss gå videre og - trinn en - stå opp på plass. Og kjøre. [CROWD knurring] DAVID MALAN: Vet du hvor Lauren er? 729? [CROWD knurring] DAVID MALAN: All right? [CROWD knurring] DAVID MALAN: Greit, skal vi være nærmer seg slutten. Vi ser en kar står her fortsatt. Hvem trenger andre å være sammen? Hvis dere ønsker å koble av. Noen opp toppen. Hvorfor kan jeg ikke låne en hånd her. For de svært få mennesker som fortsatt stående, hva tallene gjør du ha i tankene dine? STUDENT: 78. DAVID MALAN: 78 plus - som står her nede? STUDENT: 39. DAVID MALAN: Plus 39. Pluss hvem andre står fortsatt? 81? OK, hvem andre? En annen 81? Wow. Og hva er i ryggen? STUDENT: 49. DAVID MALAN: 49, pluss? STUDENT: 98. DAVID MALAN: 98 pluss? Er det noen andre? 12? God jobb. [Latter] DAVID MALAN: Oh, 112 - oh. Godt jobbet! [Latter] [APPLAUSE] DAVID MALAN: Alle andre fortsatt står? Sorry? STUDENT: 99. DAVID MALAN: 99. Alle andre som fortsatt står? Og det totale antallet studenter her faktisk, i henhold til - har du et nummer? Oh, det faktiske antall personer i rom, i henhold til kontoen som undervisning stipendiater gjorde på alles vei inn, var 729. Så ut av et rom fullt av Harvard studenter som telles seg selv, Svaret er 637. [Latter] DAVID MALAN: Så nær. Men likevel. OK, slik at en undervisning øyeblikk, ikke sant? Dette er nå det vi beskriver som en feil. Et sted på veien, vi gjorde noen aritmetisk feil, eller noen satte seg ned, eller venstre, eller noe gikk galt. Men det er fint. Fordi selv likevel, vi fikk ganske nær. Og jeg vil påstå at vi kom til feil svare på et mye raskere enn jeg ville ha bruke min mer lineær tilnærming. Så la oss anta at vi faktisk får det korrigere, men tenker nå på hva skjedde hver gang, kontra min egen naive peker algoritme. En, to, tre. Hvis det er faktisk 729 eller 637 personer her, ville det ha tatt meg bokstavelig talt 637 eller 729 pointings av fingeren og inkrementering min totalsum. Og jeg kunne gjøre det litt bedre etter kommer to, fire, seks, åtte, og doble denne hastigheten, kanskje trippel eller firemannsrom, avhengig av hvor godt jeg kan gjøre det telle i hodet mitt. Men denne tilnærmingen at dere tok var fundamentalt forskjellig. Fordi i begynnelsen, alle dere sto opp. Så 729 alt. Og så bokstavelig halvparten av dere satte seg. Og etter det, en annen halvparten av dere satte seg. Og etter det, en annen halvparten av dere satte seg. Og det totale antall ganger du Gutta kunne ha satt ned er omtrent åtte eller ni eller ti totalt ganger, avhengig av hva vår totale antallet er. Og vi kan liksom gjøre denne den andre veien. Hvis vi hadde 1024 mennesker i rommet, Totalt antall ganger du kunne halvere 1024 mennesker er 10. Nå tenker over det i den andre retningen. Anta, latterlig, som vi hadde, sier fire milliarder mennesker i dette rommet, eller en litt større rom. Hvor mange ganger vi ville ha gått gjennom denne algoritmen, slik at halvparten av klassen setter seg ned? Det er bare kommer til å ta 32 slike operasjoner, selv i en klasse av størrelsen fire milliarder. Hvorfor? Fordi fire milliarder går til to milliarder kroner, går til en million, går til 500 millioner kroner, går til 250 millioner, prikk, prikk, prikk. Jeg kan bare gjøre det divisjon noen 32 ganger, og da, alle unntatt en person ville bli stående igjen. Og det, også, er liksom en kraftig Ideen om at stadig skal vi prøve å innflytelse i dette kurset, og i programmering og informatikk mer generelt, disse bakteriene av en idé med som vi deretter kan løse problemene mye, mye mer kraftfullt. Så vi begynte ganske enkelt med at pseudokode og en fyr i et rom, men nå med et helt rom fullt av mennesker har vi gjort fundamentalt bedre. Vel, la oss nå overgang fra pseudokode til noen faktiske koden. Dette språket du er i ferd med å se skje å bli kalt JavaScript, og vi vil komme tilbake til dette mot semesters slutt. Det er et programmeringsspråk som du bruke for å lage nettsteder og andre slike programvare i disse dager. Og vi har brukt det, takket være en venn av våre på Stanford, å kode noen skjult informasjon her. Dette er kunsten steganography, så å si, der du kan skjule informasjon i det som ellers ser ut til å være støy eller et helt annet image helt. Men innebygd i dette spesielle bildet er faktisk en hemmelig melding slags. Så la meg gå videre og trekke opp det samme bildet her, dette tid i en nettleser. Og jeg kommer til å vinke min hånd på noen av detaljene for i dag, spesielt for de av dere som dette ser ut som ikke bare JavaScript men gresk, som en helt ukjent språk. Men dette er et eksempel på et programmeringsspråk. Og for nå, ta på tro at denne første linjen med kode - og etter koden, jeg mener bare tekst. Tekst at jeg kunne ha bokstavelig talt skrevet inn i Microsoft Word, hvis jeg hadde riktig programvare for å deretter gjøre noe med det. Programmering kildekode, programmering koden, er egentlig bare tekst, og det ser annerledes basert på hvilket språk du bruker, ikke ulikt engelsk og Spansk og russisk alt ser annerledes ut når du skriver dem på tastaturet. Så denne første linjen, for nå ta på tro, åpner bare en grafikk fra internett, så bråkete grafisk vi nettopp så. Denne neste linjen er her et eksempel på en loop, og vi faktisk så at samme sjargong i TED video. En løkke er noe som skjer igjen og igjen, og selv om denne absolutt ser kryptisk, med Stikkordet for, og noen parenteser, og noen semikolon. Vi vil komme tilbake til det før lenge, men at sløyfen er det egentlig forteller programmet, iterere over alle av de bråkete prikker, fra venstre til høyre, topp til bunn. Fordi på slutten av dagen, et bilde liker dette - og du kan faktisk slags se det på denne projektoren - er egentlig bare et rutenett av punkter. Så vi kan identifisere hver av disse prikkene ved en koordinat, x, y, og med denne program, kan vi nå begynne å gjøre noe til disse prikkene. Så hva jeg kommer til å gå videre her og vet er at jeg kommer til å gjøre noen endringer. Først skal jeg gå videre og bli kvitt av alt dette grønnaktig og blålig støy, og jeg kommer til å gå videre og skriv inn følgende riktignok kryptiske syntaks. im for bildet. satt blått plassering x, komma, plassering y, til 0. Med andre ord, jeg vil bare slå av alle de blå prikker i det bildet. Jeg kommer til å gå videre nå og klikk Dette Run / Lagre-knappen, og du vil merke på høyre side, det resulterende bildet vises. Nå er det super green, men det er ikke overraskende, fordi jeg bokstavelig talt slått av, ved å lage en en en 0, som alle den blå i det bildet. Vel, nå la oss gjøre det litt mer. im for bilde, dot setGreen, x, y. Og det betyr bare iterere fra venstre til høyre og deretter fra topp til bunn. Slå den av med en verdi 0 av, i tillegg. Lagre. Og på projektoren, kan du faktisk ikke virkelig se noe i det hele tatt. På min laptop skjermen, hvis jeg kikker på bare den rette måten, kan jeg se litt av en bilde, fordi de er fortsatt noe rødt i det. Hvis du noen gang har hørt forkortelsen RGB - rød, grønn, blå - det er å henvise til denne komposisjonen av et bilde ved hjelp bare disse tre fargene. Og akkurat nå har vi kastet bort alle grønne, blå, men det er ikke mye rødt. Så la meg skru opp den røde. Hvordan kan jeg gjøre det? Vel, først, kommer jeg til å spørre dette programmet et spørsmål. Jeg kommer til å gå videre og la oss kalle det en variabel, akkurat som i algebra. Du kan ha x eller y eller z. Jeg kommer til å erklære en variabel og si, satt i denne variabelen, midlertidig, verdien av bilder getRed verdi på x, y. Og igjen, vil vi komme tilbake til alle av denne detaljen i fremtiden. Men for nå, bare ta på tro at denne linjen ber programmet, hva er den røde verdi ved x, y? På det aktuelle prikk? Så jeg kommer til å gjøre noe til det. Så jeg kommer til å gjøre bildet dot sett rød ved x, y, y, men denne gangen kommer jeg til å øke det ved å gjøre røde ganger, la oss si, 10 år. Så øker det med en faktor på ti. La meg zoome ut nå, og klikk kunne kjøre / Lagre. Og voila, det var det hele tid, selv om våre menneskelige øyne kunne ikke helt se det. Så igjen, dette er nå fast kode, en eksempel på et språk som vi vil komme tilbake til før lenge. Men skjønner, spesielt de av dere uten slik erfaring, er det ganske snart som vi selv vil være skrive kode som det der. Faktisk, et verktøy som du er alle noe kjent, kanskje, er CS50 er egen kurs-shopping verktøy, som var faktisk restartet i sommer av noen av CS50 egne tidligere studenter, nå slå TFS. Så dette skjer for å være et nettsted bygget på et språk som heter PHP. Den bruker en database som heter MySQL, ting som vi får våre hender skitne senere i semesteret. Men tro det eller ei, selv noe som dette reduseres til slutt til den enkleste av loops og betingelser og greiner, som de så vi bare en øyeblikk siden i TED video. Det jeg tenkte jeg skulle gjøre nå er aksjen ikke bare noe vi de ansatte har gjort for campus, men snarere noe en tidligere student - tre studenter, faktisk - gjort det siste året, Sierra, Daniel, og Sam, den siste av dem hadde ingen forutgående programmering erfaring da han tok CS50. Og for deres endelige prosjektet, de utstilt ved CS50 Fair, en applikasjon kalt wrdly, som er en web-basert program som de gjorde denne videoen som jeg tenkte jeg skulle dele til gi deg en følelse av akkurat hva som er mulig ved sikt ende. [Musikk spilles] DAVID MALAN: Det er fra uke Zero til uke 12 det siste året. [APPLAUSE] DAVID MALAN: Som en teaser, også, egentlig å skjerpe appetitten er til hva som er mulig, kan du ha sett allerede, eller kan snart se, market.cs50.net, en nytt verktøy som kursets teamet har jobbet med, denne gangen i samarbeid med Harvard Student Etater, slik at start i år og fortsetter forhåpentligvis inn i dette kommende sommeren vil du ha en standard mulighet på campus for å kjøpe og selge ting av interesse for deg. Og med partnerskap gjennom HSA, vil du også være i stand til å slippe elementer off i en av HSA er fysiske butikker på noen punkt i fremtiden, slik som å proxy ting, spesielt som du oppgradere og ikke nødvendigvis ønsker å forkaste ting, men faktisk betaler det videresende til folk som kan følge deg her på campus. Så mer på det som kommer. Men litt mer konkret, et verktøy som har kommet ut av CS50 i nyere år, som noen av dere kanskje være kjent og andre av dere kan være googling nå, i CS50.net/2x, vil du finne en link til en Chrome utvidelse som er demonstrative av hvordan du kan bruke JavaScript, det samme språket vi brukes med Eiffeltårnet et øyeblikk siden, å gjennomføre 2x avspillingshastighet for alle Harvard iSites videoer. Dette er noe som er bygget inn CS50 egen videospiller. Men også dette til hvis du begynner å grave inn i kildekoden, som vi vil gjerne gjøre tilgjengelig, vil du se hvordan du kan også løse problemer som det, akselererende widgets på nettsteder med som du allerede er godt kjent. Så et ord nå på kurset og forventninger og hva som ligger foran oss. Generelt, vil vi faktisk samles her på mandager og onsdager - selv denne fredagen, vil vi samle fordi of Shopping Week - 01:00-02:00, men noen ganger til 2:30. Gitt at du kanskje derfor ønsker eller nødt til å ta noen klasse på 02:00 videre, eller enda før, innser Kurset er støttende av det som kalles samtidig påmelding, hvor vi vil støtte en begjæring til Ad styret og din bosatt dekaner på dine vegne hvis du har en konflikt eller annet sted i dette 01:00-02:30 rekkevidde. Hodet til at URL nettet for ytterligere detaljer. Men i forhold til understøttelseskonstruksjonen som karakteriserer CS50, for studenter mer og mindre komfortable like, vi tilbyr distinkte spor av seksjoner. Og dette er et par uker fri, men før lenge, vil du bli bedt om din komfort nivå. Er du blant dem mindre komfortable, mer komfortabel, eller et sted i mellom? Og vi vil ha tre distinkte låter som faller i nettopp de målgrupper. Så ikke på noe punkt i begrepet bør du selv føler at du konkurrerer mot enhver student med mer eller mindre bakgrunn enn deg. Faktisk er det naturligvis ment å være mye mer samarbeidende og mye mer åpen enn. I form av oppgavesett, vil du finner også at i tillegg til den standard utgave av hver ukes problem satt, det er ofte en "hacker edition "som er ment å være målrettet ved 5% til 10% eller så av den demografisk som er faktisk blant dem mer komfortabel og ønsker mer av en utfordring enn standard utgave av det PSett forventer. Flere detaljer om dem som skal funnet i pensum. Men også der kan finnes detaljer på kursene sene dager. Typisk problem setter forfaller på torsdager. Du kan imidlertid utvide mange av dine tidsfrister i høst fra torsdag til Fredager bare ved å møte oss halvveis, så å si, svarer noen warm-up spørsmål i noen av ukens problem settene, som automatisk deretter gi deg en ekstra 24 timer. Vi vil også slippe laveste poengsum, som per pensum. For å gi deg en følelse av hva problemet sett er - fordi det er faktisk kursets problem sett som slutt definere nesten hver studentens erfaring, mer enn forelesninger, mer enn seksjoner, flere enn de fleste andre aspektet av kurset. I fjor, for eksempel, begynte vi, som vi vil starte i år, med Scratch. Spesielt dette fredag, vil vi bruke, for bare en dags tid, en grafisk programmeringsspråk, som vi vil starter programmeringen ved å dra og slippe brikkene som bare montere fysisk om det er fornuftig å gjøre det logisk. Neste uke vil vi raskt overgangen til C, en ganske gammel, men svært liten og enkelt språk som vil tillate oss å virkelig går 0-60 løpet på bare noen få uker, og deretter parlay de samme ferdigheter og kunnskap om grunnleggende programmering konstruerer inn høyere nivå språk som PHP, JavaScript og atter andre fortsatt. I fjor, den tredje PSett i løpet var at av kryptografi, en domenespesifikke program der vi utfordret elevene til å gjennomføre noen antall koder, programmer som å rykke eller dekryptere informasjon, å kryptere den. For hacker utgaven, derimot, vi ga hacker studentene en fil fra en standard Unix datamaskin som inneholder brukernavn og passord, sistnevnte som var kryptert, og vi utfordret de hacker studenter å dekryptere, som best de kunne, disse passordene, fortsatt på at samme domene. Scramble, et spill som noen av dere er kanskje kjent. En etterforskning stykke, der vi ber elevene å gjenopprette data som hadde vært ellers slettet fra min egen digital kameraets compact flash-kort, etter faktisk skrive programvare for å finne ut, der var de nuller og enere i at digital kamera som tidligere komponert et JPEG-grafikk? En utfordring slags fjor involverer skrive den raskeste stavekontroll mulig, konkurrerer mot venner og klassekamerater hvis de ønsker. Implementering Huff 'n Puff, et pakkeprogram. Og så avslutter semesteret med CS50 Finans, en web-basert applikasjon med som du oppretter en eTrade-lignende nettside å kjøpe og selge aksjer, så å snakke, ved å faktisk trekke nesten real-time quotes Yahoo! Finansiere. Hva vi ikke gjorde i fjor var ett problem sett som gjenstår likevel en favoritt. Hvis du aldri har gått til shuttle.cs50.net, vil du se en bruker grensesnitt litt som dette. Men for to år siden, klassen implementert, ved hjelp av Google Maps og Google Earth plug-in og litt av kunnskapsrike med å kjøre rundt campus, slik at målet med dette spillet var, som du kan se noen av ansiktene, er å kjøre rundt campus leter etter ansatte, undervisning stipendiater og CAS, og når du gjør det, setter dem på din buss. Ingen av dem faktisk ser ut til å være her, så vi kommer til å skrive en cheat-kode. [Latter] DAVID MALAN: Det vi går. OK. Og her er nå de ansatte laced hele campus. Og som du kan se, på høyre hånd side av skjermen, skyttelbussen har tomme seter. Og målet var å skrive kode som brukes til å simulere dette kjøring og plukke opp og slippe ut av passasjerer. At man, også ved hjelp av et språk kalt JavaScript. Så innse at programmer som som vil være på vår samme bane dette år, i tillegg. I form nå, for ekstra støtte, vi har kontortid. Som du kanskje har sett i ditt eget hus spisesalen eller i Annenberg, vi vil være i huset servering haller fire kvelder i uken - Leverett, Pfoho, Eliot og Annenberg dette året, 08:00-23:00. Og hva vi trodde vi ville gjøre dette året er noe litt annerledes. Hvis du har hørt mumling i fjor at det var litt for stressende, dette Årets kontortid, som vi vil beskrive neste uke, vil være mer organisk, der ved ankomst, vil du bli sendt til en bestemt tabell der flere ansatte venter, og vi vil gjøre ting mye mer organisk. Ikke mer kø, ikke mer iPad, men heller ha mer intimt samtaler rundt et bord for bare åtte eller så elevene, slik at vi omtrentlig følelsen av hva som ellers ville være en mye mindre klasse. Vi tilbyr, i tillegg er disse tingene vi heter gjennomgang og videoer filmet i fremme ved en av kursets undervisning stipendiater, Zamyla, der hun leder deg gjennom ukes problem sett, som tilbyr tips og triks for utfordringene som lå foran. Og omvendt, etter oppgavesett er på grunn av dette året, vil vi også slippe små klipp kaller post-mortems som faktisk gå deg gjennom representative løsninger, både gode og dårlig, via hvor du kan antyde hvordan du kan ha eller bør ha implementert din egen løsning. Og hva vi vil tilby for første gang også i år, spesielt for de studentene som benytter seg av kursets andre ressurser, men likevel sliter alt for mye, emnet selv vil pare de studentene, som ressursene tillater, med lærere slik at har du en mye mer intim mulighet enn huset spisesaler tillate for en-til-en hjelp. Nå er en endelig glimt på noen av end spill i sikte. Du kan bli kjent med den CS50 Hackathon. Vel, kommer i desember, fra 08:00 PM til 07:00, i begynnelsen av Reading Periode, vil være en mulighet å samle med klassekamerater - dette ville være rundt 9:00 - der du dykke inn i den endelige prosjektets gjennomføring sammen klassekamerater, venner og mat. Dette vil være rundt 01:00, da den første batch av mat kom. Og dette er omtrent 4:00 at bestemt år på CS50 Hackathon. Men den virkelige klimaks med kurset er betydd for CS50 Fair, en campus-wide utstilling av dine egne endelige prosjekter, som familie og venner er alle invitert, som våre rekrutterere og våre venner fra industrien. Dette, for eksempel, er et glimt av den 2000-pluss folk som har deltatt siste årene. Uttrykk som dette er ikke uvanlig, og tilsvarende gjør din klassekamerater glede i ting du har oppnådd. Og faktisk, mot dette målet, har vi en start-av-term hendelse, så vel. Hvis ting som dette appellerer til deg, eller du er minst nysgjerrig på hva som dette, vet at en ny tradisjon av Kurset heter CS50 Puzzle Day. Og dette ble innstiftet et par år tilbake for å virkelig signalisere til campus at informatikk er ikke om programmering, og det er absolutt ikke om å omfavne bare de studentene som har tidligere erfaring. Det er virkelig om problemløsning mer generelt. Og så Puzzle Day, de siste par år nå, har utviklet seg til en fin samarbeid med våre venner på Facebook, hvor det vil være fabelaktig premier og pizza over elva ved i-lab førstkommende lørdag. Hodet til denne nettadressen med to eller tre venner hvis du ønsker å delta i denne nye tradisjonen. Så jeg vil gjerne be om at du holder en ting i tankene, og vi har bare en to minutters klipp som å lukke dag. 73% er nummer å huske. Kake, også venter deg utenfor dette transept som vi utsette på bare et par øyeblikk, som er en tradisjon av banen, så vel. Men dette er nøkkelen sitat fra Kursets pensum å huske på. Det som teller til slutt i dette kurset er ikke så mye hvor du ender opp i forhold til klassekameratene dine, men hvor du, i uke 12, ender opp i forhold til selv i uke 0. Men glimt at vi vil forlate deg med her i dag er denne siste her av våre samme Daniel, gjorde hvem wrdly video bare et øyeblikk siden. Jeg forlater dere med dette glimt av hva som ligger foran. Og når vi gjør dette, hvis vi kunne ha CS50 personale fra forsiden av rommet å komme fram til scenen for å male alle jo mer av et visuelt bilde som til hva som venter deg i år - får klosset. Vi vil konkludere med dette her på skjermen. [Musikk spilles] DAVID MALAN: Dette er CS50. [MUSIC - MATT & KIM, "Det er ok"] SPEAKER 1: Jeg elsker CS50 mer enn katter. SPEAKER 2: Whoaaaa! [Latter] DAVID MALAN: Dette er altså CS50. Vi vil se deg på fredag. [Applaus og jublende] FORTELLER: Ved neste CS50, en på scenen demo går ikke som planlagt. DAVID MALAN: Vi ønsker å finne Mike Smith i denne telefonboken. Vel, hva er dine instinkter? Jeg kan hoppe omtrent til midten av telefonboken, blikk ned, ser at Jeg er på M, og jeg vet nå at Mike Smith er ikke til venstre. Han må være til høyre. Og så på dette punktet, vi kan bokstavelig talt rive - på dette punktet, kan vi bokstavelig talt rive - på dette punktet, kan vi billedlig rive telefonboken i halvparten. [Ukelele klimpring]