[Musikk spilles] [APPLAUSE] DAVID J. MALAN: Dette er CS50, Harvard University innledning til den intellektuelle foretak av informatikk og kunsten programmering. Nå hvis du er blant dem som hvert år sitter her med litt nerver i tankene dine, slik at du ikke tror du hører hjemme her, du tror at de fleste noen sitter rundt deg vet langt mer enn deg, er faktisk mer komfortable enn deg ved datamaskinen vitenskap eller datamaskiner mer generelt, skjønner at 78% av studentene som nå ta CS50 har ingen tidligere erfaring. Faktisk er det 100 punkter der på displayet, 78 hvorav er solide grønt, som betyr at du, Hvis du er blant den demografiske, er i veldig godt selskap her på ut. Og hvis du er i stedet blant 22% av CS50 studenter som gjør faktisk har tidligere erfaring, enten i videregående skole eller et annet program, innser at du også vil bli utfordret i kurset. Ikke bare har vi forskjellige spor for studenter mindre komfortable og mer komfortabel både i seksjoner, vi også har såkalte hacker-utgaver av de fleste oppgavesett som vil utfordre de studentene med at ytterligere erfaring å utforske lignende materiale men fra en mer sofistikert perspektiv. Men hva er informatikk? Vel, til slutt, hva kommer til å Uansett når du utforsker dette feltet er ikke så mye hvor du ender opp forhold til klassekameratene dine, men hvor du selv ende opp i uke 12 versus hvor du begynne her i uke null. Nå datamaskin science-- vel, la oss kaller det vitenskapen om computation-- hvor beregningen er egentlig bare en fancy måte å si, tar noen innspill, produsere noen utgang, og gjøre det ved å kjøre algoritmer, sett med instruksjoner for å løse noen problem på disse innganger for å produsere en utgang eller løsning der du er interessert. Så vi har nylig hatt anledning til å reise ut til California for å møte med en alumna. Hennes navn er Susan Wojcicki. Og hun vil gjerne snakke til deg her på video å vitne til hvor aktuelt med bare en smak av datamaskin vitenskap ved innføringsnivå kan være. Selv om du ikke går på å forfølge informatikk som et felt, eller til og med engineering, STEM eller mer generelt, du vil se, faktisk, hvordan en bestemt Selvfølgelig så påvirket hennes liv. Og hun bare tok det når hun var en senior her ved Harvard College. Hvis vi kunne dempe lysene for Susan. SUSAN Wójcicki: Hei, verden. Jeg er Susan Wojcicki. Jeg er administrerende direktør i YouTube. Og jeg tok CS50 da jeg var senior på Harvard i 1990. Jeg var faktisk en historie og litteratur major. Og min junior sommer, Jeg innså at jeg kanskje ønsket å lære noe om datamaskiner. Og så kom jeg tilbake. Jeg tok CS50. Det var vanskelig, men det var mest fantastiske klassen jeg tok. Det forandret hvordan jeg tenker på alt. Og da jeg ble uteksaminert fra Harvard i 1990, gikk jeg til Silicon Valley. Og jeg fikk en jobb. Og jeg har jobbet i tech siden den gang. DAVID J. MALAN: Nå hva Susan ikke nevner i denne videoen, at det var faktisk i hennes garasje som Google selv var grunnlagt av Larry og Sergey. Nå også vi nådde ut til våre venner på code.org, en organisasjon som løpet av det siste året har vært å få folk spesielt begeistret informatikk og programmering, spesielt. Men det er verdt å merke seg at programmering er ikke informatikk per se. Informatikk er ikke programmering. Snarere programmering er bare en tool-- som dere alle vil være alt for godt kjent av semesters end-- slik at du kan bruke ikke bare til fremtidige kurs i CS men til uansett felt hvorfra du kommer, i humaniora, samfunnsfag, naturlig vitenskap, eller lignende. Faktisk, la noen andre alumni og deres kolleger å snakke med anvendbarhet av feltet som venter. Bill Gates: Jeg var 13 da jeg først fikk tilgang til en datamaskin. JACK DORSEY: Mine foreldre kjøpte meg en Macintosh i 1984 da jeg var åtte år gammel. Mark Zuckerberg: Jeg var i sjette klasse. SPEAKER 1: Jeg lærte å kode i college. Ruchi Sanghvi: Freshman år, først semester, Intro til Computer Science. Bill Gates: Jeg skrev et program som spilte tic-tac-toe. DREW HOUSTON: Jeg tror det var ganske beskjeden begynnelse. Jeg tror det første programmet Jeg skrev spurte ting som, hva er din favoritt farge? Eller hvor gammel er du? ELENA SILENOK: jeg først lærte hvordan å lage en grønn sirkel og en rød firkant på skjermen. Gabe NEWELL: Den første gang jeg faktisk hadde noe komme opp og si hei, verden. Og jeg gjorde en datamaskin gjør det. Det var bare utrolig. Mark Zuckerberg: Lære til programmet starter ikke som ønsker å lære alle informatikk eller prøver å mestre dette disiplin eller noe sånt. Det startet bare av fordi jeg ønsket å gjøre dette en enkel ting. Jeg ønsket å gjøre noe som var moro for meg selv og mine søstre. Og jeg skrev dette lille programmet. Og så i utgangspunktet bare lagt til litt til det. Og så når jeg trengte å lære noe nytt, Jeg kikket opp, enten i en bok eller på internett, og deretter lagt litt til det. DREW HOUSTON: Det er egentlig ikke ulikt spille et instrument eller noe eller spille en sport. DAVID J. MALAN: All right. Så la oss nå faktisk dykke i litt dypere. Hva er disse innganger og utganger at vi snakker om her? Så hva med noe enkelt? Du sikkert vet, selv om du har ingen kjennskap til informatikk overhodet, at datamaskiner eller annen måte bruke og forstår bare nuller og enere. Men hvordan kan det muligens bli gitt hvordan mye dagens stasjonære og bærbare datamaskiner alike kan gjøre? DNA av dagen, den eneste alfabetet at de forstår er en null eller en. Vel, tenk på dette. Vi, mennesker, har en tendens til å bruke desimalsystemet. "Desember" som betyr ti. Og det er 10 fordi vi har 10 sifre, 0 til ni. Nå datamaskiner, derimot, pleier å bruke binær. "Bi", som betyr to. Så de har en tendens til å bruke bare null og én. Men det viser seg at selv bare med nuller og enere, at er en tilstrekkelig stor alfabetet som å representere mest alt av data du vil, enten det er et tall, enten det er et brev, enten det er en grafisk eller video på skjermen. Tenk, for eksempel, hvordan vi mennesker vanligvis tolke dette nummeret her. Dette er bare tre sifre, en, to, tre. Men vi vet dette nummeret medfødt nå som 123. Men hvorfor er det? Vel, hvis du tenker tilbake å kanskje klasse på skolen, du sannsynligvis ble lært opp til å tenke på disse tallene som å være i kolonner, hvor den ene er i hundrevis sted, de to er i tiere sted, og tre er i seg sted. Hvorfor er det faktisk nyttig? Vel, tenk om super enkel aritmetikk at vi alle har vært gjort i mange år nå. Effektivt, hvis du har en en i hundrevis sted, du gjør den rask matematikk 100 ganger en pluss 10 ganger 2-- fordi to er i titalls sted-- pluss 1 ganger 3-- fordi tre er i seg sted. Så, selvfølgelig, hvis vi faktisk multiplisere dette ut, hva vi egentlig representerer med denne pattern-- ett to three-- er 100 pluss 20 pluss 3, noe som selvfølgelig er 123. Nå binære, og datamaskiner virkelig, fundamentalt snakker samme språk at vi gjør. De har bare en mindre alfabetet. Så datamaskiner har bare nuller og de på sin disposisjon. Så mens vi mennesker har i hovedsak potenser av 10 i hver av disse places-- 10 til null, 10 til en, ten til de to, noe som gir deg 110 og 100 respektivt. Fordi datamaskiner bare ha to verdier de kan forstå, null og én, de må bruke forskjellige verdier i disse kolonnene, en, to, fire. Og hvis vi holdt det gående, åtte, 16, 32, 64, og så videre. Men mønsteret og den mentalitet er nøyaktig den samme. Så ved denne logikken, noen, hvordan ville Jeg går om representerer tallet en i binær? Hvis du har aldri engang tenkt på dette før, hva er din gut si? PUBLIKUM: One. DAVID J. MALAN: One. Nettopp. Vi trenger bare en en i de plass fordi nuller nok til å gi oss verken en fire eller to. Så en ganger en lik en. Nå ting blir litt interessant. Hvis jeg ønsker å representere i binære antall to-- men, igjen, selv om du aldri har snakket dette språket før, hvordan gjør vi representerer i binær Verdien vi mennesker kjenner som to? Zero en null. Bare sette den i kolonne som du vil ha det. Nå blir det ganske lett nok nå. Så hvis jeg ønsker å representere three-- det ikke finnes noen tre-kolonne. Så, igjen, jeg kan nå legge disse verdiene sammen ved å sette en en her. Så 2 ganger 1 pluss 1 Tiden 1 er, selvfølgelig, 3. Nå ting blir litt moro i at de nå blitt nuller. Og for å representere fire, får jeg denne. Og hvis vi øke sakte her-- som ville være fem. Dette ville være seks. Dette ville være syv. Men nå synes jeg å ha kjører inn i et problem. Hvordan kan jeg gå om å representere eight-- ville være den neste verdien. Ja, så vi trenger en ny bit. Og, ja, hvis du har hørt dette uttrykket før, biter, det er bare en forkortelse for binære siffer, null eller én. Og så jeg tilfeldigvis skal representere bare tre slike biter her. Men hvis jeg hadde en måte å lagre ikke tre forskjellige biter, men fire, sikkert jeg kunne representere åtte, og deretter ni, og deretter 10, og enda høyere og høyere. Men det så kaller inn spørsmålet hvordan vi kan gå om å representere disse ting i første omgang. Det er én ting å trekke dem opp her på et lysbilde, men hvordan representerer du dem hvis du er en mekanisk innretning? Hva er en datamaskin gjør for å representerer de innganger og utganger som fundamentalt definere beregning på slutten av dagen? Vel, hva om noe super enkelt som dette? Det er bare en lyspære. Og jeg kan utløse dette lyspære å gå på ved å slå noen elektrisitet på og som gjør at elektroner å strømme gjennom, som endrer dens stat eller dens verdi, så å si. For eksempel er denne en gammel skole bordlampe her med et slikt lyspæren inne i den. Og akkurat nå er det ikke virkelig gjør noe nyttig. Men så snart jeg kobler den inn i en stikkontakt og deretter bruke denne switch-- eller Vi kan også kalle det en transistor eller tenke på det som such-- Jeg kan nå representere enten denne verdien, hvor lyspæren er åpenbart av, eller denne verdien. Denne verdien eller denne verdien. Denne verdi og så videre. Så innsiden av en datamaskin, formodentlig er mye mindre biter av maskinvare, men at på slutten av dagen rett og slett har å bruke electricity-- kanskje fange det-- og deretter enten holde noe på eller holde noe av. Selvfølgelig, dette er ikke spesielt interessant å gjøre med bare en enkelt lyspære. Faktisk, hvor høyt kan jeg telle på binær med denne bordlampe her? PUBLIKUM: One. DAVID J. MALAN: One, ikke sant? Jeg trenger mer skrivebord lamper hvis jeg faktisk ønsker å telle høyere. Men vi kan gjøre det bedre enn det. Fordi lyspærer som vi har satt i disse tingene er faktisk mer avansert lyspærer enn fjoråret ville tillate. Og de er faktisk nettverks lyspærer. Og bunter av selskaper gjøre disse tingene i disse dager. Men det viser seg at dette spesielt kommer med en funksjon der du kan endre sine farger. Så for eksempel, hvis du prydet din hybel med noen av disse lys pærer, avhengig av humøret, avhengig av hvem som kommer inn, avhengig av været, avhengig av tidspunktet av dagen, kan du faktisk endre fargene på pærene på rommet ditt. Og det er fordi disse lys pærer og andre liker det har hva som er kalt en API, et program programmeringsgrensesnitt, som er et tema som du vil være godt kjent med ved semester slutt. Og dette er bare en fancy, kryptiske måte å si: du kan programmere disse lys pærer å gjøre din budgivning. Du kan sende dem meldinger akkurat som deg, et menneske, kan sende en melding til en webserver sier, gi meg dagens nyheter eller gi meg e-posten min. Du kan sende mer uforståelige meldinger til disse lyspærene å si, slå på og slå av. Men det er ikke alle som interessant. Du kan si, slå på rødt, slå på grønt, slå på blå, alle med samme lyspære. Og du kan selv, med litt mer savvy, sier, slå deg til blå når det er en dyster dag utsiden, for eksempel. Det kan faktisk lappe inn en vær API og finne ut hva været er, eller den tiden av dagen, eller andre slike triggere. Så, faktisk, to av CS50 egne ansatte, Dan Bradley og Ansel Duff her, ber vi anskaffet oss en hel haug av disse lyspærene. Og de bygget CS50 er første gang binære pærer, hvor vi har representert her-- med disse leken liten magnets-- de ulike plassholdere vi hentydet til bare litt siden. Så måte over her er den de sted, to, fire. Og vi fikk ikke se høyere enn det. Men, selvfølgelig, de er krefter to. Åtte, 16, 32, 64, og 128. Så hvis jeg nå ønsker å være litt mer avansert enn å bruke denne gamle skolen bryter, Jeg har her på denne iPad en super enkelt grensesnitt at Dan Bradley, en tidligere student og underviser nå stipendiat, programmerte ved hjelp av noen HTML og Javascript, som er markup og programmering språk hhv. Og du kan sikkert see-- selv i back-- det er et stort pluss og et stort minus, pluss en knapp for hver av disse pærene. Og hva dette kommer til å tillate meg å gjør er, for eksempel, klikker du på pluss og nå representerer, av Selvfølgelig, hvilket nummer? One. Og jeg kan treffe den igjen. To. Tre. Fire. Five. Seks. Seven. Og her nå får vi at rollover, men vi har en fjerde bit denne periode så nå har vi åtte. Slik at vi kunne gjøre dette for en stund. Faktisk, som en side, hvor høyt kan vi telle? Anyone? PUBLIKUM: 255. DAVID J. MALAN: 255, ikke sant? Ikke bekymre deg for mye om matematikk for nå, men det er en ganske anstendig antall. Men det er faktisk ikke bundet bare hvor mange biter av informasjon, som et brev, eller en grafisk at vi kunne representere. Men uansett for nå. Jeg kommer til å gå videre og slå dem av. Og hvis jeg kunne, ville jeg gjerne be om en frivillig, vår første volunteer-- oh, hello-- på scenen. Fangsten er at du må være komfortabel vises, som du tydelig er foran alle dine klassekamerater, så vel som på internett. Og la meg se litt utover the-- hva med her i hvit skjorte? Og hånden opp. Kom opp. Hva er ditt navn? PUBLIKUM: Jackie. DAVID J. MALAN: Jackie. Jackie, kom opp. Så hva det er også på denne iPad er en knapp som heter Game Mode. Og denne spillmodus er kommer til å tillate meg å legge inn på forhånd en bestemt desimal tall, tallene vi mennesker er kjent med. Og da vil du bli utfordret her for å bruke knappene på en for top-- hver av disse bulbs-- å faktisk finne ut mønsteret av lyspærer som representerer tallet i spørsmålet. Og jeg beklager, hva var navnet ditt igjen? PUBLIKUM: Jackie. DAVID J. MALAN: Jackie. Greit. Godt å møte deg. Så la meg gå videre og programmet i for verden å se nummer 15. Vi vil holde det lite på først her. Og jeg kommer til å gå inn i spillmodus. Og jeg kommer til å spesifisere, gi oss nummer 15. OK. Og nå med alle watching-- hvis du vil kanskje stå på denne måten, fordi det vil stille opp-- gå videre og veksle de åtte knappene langs toppen å slå pærene på eller av som det passer deg. PUBLIKUM: OK. DAVID J. MALAN: Og ingen juks ved å trykke pluss 15 ganger. Oh, vi kommer til å gjøre det. PUBLIKUM: Å, vent. Jeg er så lei meg. DAVID J. MALAN: Du kan også slå lyspærer på individuelt med hver av disse knappene på toppen. PUBLIKUM: Å, OK. Så det ville være like-- DAVID J. MALAN: OK. Så nå har vi åtte. Så la oss stoppe for publikum til å engasjere seg her. Hvilket nummer er Jackie tiden representerer? 11. Så vi er nesten der. Og utmerket. Så vi har vår første vinner. Gratulerer. Og vi trodde vi ville ha noen fantastiske giveaways. Hvis du ønsker å være en slik dorm rom her på campus, du kan selv ha et avsluttende prosjekt bruker nå denne API, takket være Jackie. Så now-- [APPLAUSE] --Hvis vi kunne, ett mer for eksempel rundt av denne. Åh, nå alle ønsker noen lyspærer. For den såkalte hacker utgave, vi kommer til å trappe den opp en-- oh, yeah, uforpliktende. Jeg tror du kommer opp nå Hvis hånden din kommer ned. Hva er ditt navn? PUBLIKUM: Alex. DAVID J. MALAN: Alex, kom over her. Så for Alex, skal vi program i en litt større antall. Kanskje i orden. Tallet 50. PUBLIKUM: OK. DAVID J. MALAN: Men, som Jeg sa-- og du kan ønsker å stå her så at knappene linje opp som du forventer-- men jeg gjorde kaller dette hacker utgaven. So-- lykke til! [Latter] Du vil være i stand til å snu dem av hvis du-- OK. Utmerket. Fantastisk. Gratulerer. [APPLAUSE] Jeg antar at jeg skal betale opp. Gratulerer til Alex også. OK. Så den ultimate takeaway her er forhåpentligvis, ærlig, den simplicity-- den enkelhet som du kan få noen fine lys pærer, tilsynelatende i [uhørbart]. Men de representerer, slutt, den samme ideene som vi mennesker er allerede altfor kjent. Så hva kanskje neste steg være i progresjon for å prøve å gjøre noe interessant med data og som representerer innganger som ikke bare tallene, men er kanskje bokstaver eller mer? Vel, det viser seg at datamaskinen verden, i mange år, bare vedtatt en vilkårlig, men en konsekvent standard som kart tall til bokstavene i alfabetet. For eksempel er her en utdrag fra denne kartleggingen. Det kalles Ascii. A-S-C-I-I. Og det er rett og slett en tabell som kart store bokstaver letters-- i dette case-- til desimaltall. Men hva er implikasjonen? Vel, hvis du faktisk ønsker å representere noe sånt som en e-post eller noe tekst på en nettside, du åpenbart ønsker å vise de humane bokstavene i alfabetet, ikke tall. Så, avhengig sammenheng med program at en bruker ved hjelp av, hvis det er en nettleser eller e-postklient, tallene kan sikkert være tolkes som bokstaver. Det vil si, mønstre kan lett bli tolket som bokstaver. Og så hva vi kan ha er bokstaven A vesen representert som 65, B blir representert som 66. Så hvis vi har en super kort ord, som hi, hva en datamaskin ville til slutt butikk i desimal, men virkelig i binær, ved hjelp av noen sekvens av biter, utnytte en bit av strøm på noen måte, ville være de to tallene 72 og 73. Men mønsteret av biter som representerer disse verdiene. Så disse da er hvordan vi kan representere våre innganger og utganger. Og det er nok å si, vi kan gjøre mer komplekse representasjoner slutt med ting som grafikk, videoer, musikk og mer som vi skal se senere dette begrepet. Slik at bare forlater deretter algoritmer, disse settene av instruksjoner som vi løse aktuelle problemer. Vi passerer i innganger til algoritmer. Og disse algoritmene produserer utganger, forhåpentligvis korrekte utganger og forhåpentligvis også, effektivt samlet utganger. Med andre ord, det er en ting å gjennomføre noe riktig. Det er en annen ting å implementere noe godt eller effektivt. For eksempel, en demonstrasjon at vi er glad i på kurset er dette en. Men disse tingene blir stadig vanskeligere å finne. Men dette er faktisk en gammel skole telefonboken, innsiden av som er 1000 pluss sider navn og telefonnummer. Og hvis jeg ønsket å slå opp noen i denne telefonboken, Jeg kunne rett og slett gjøre en veldig naiv algoritme. Jeg kunne åpne opp for den første siden, og Jeg kunne begynne å se etter, si, noen heter Mike Smith. Og hvis han ikke er på den første side, I videre til den andre, og deretter til den tredje, og deretter til det fjerde, og så videre, før jeg endelig finne Mike Smith. Nå er at algoritmen riktig? PUBLIKUM: Ja. DAVID J. MALAN: Yeah. Hvis han er der, vil jeg slutt finne ham. Men det er kanskje ikke så veldig effektiv, absolutt ikke fort, fordi, min Gud, hvorfor er jeg kaste bort tiden min flipping gjennom alle disse sidene når jeg kunne absolutt gjøre dette fysisk raskere? Vel, en liten optimalisering, så å snakke, kanskje ikke en side om gangen, men to, fire, seks, åtte, ti. Fortsatt er riktig? PUBLIKUM: Nei DAVID J. MALAN: Så nei hvis jeg for eksempel hopp over Mike Smith. Men så lenge jeg tilbake pedal én side, hvis jeg skyter over ham, kanskje vi kunne rette opp det kan ellers være en fikser. Men er det bedre? Er det raskere? Jeg mener, ja. Det er bokstavelig talt dobbelt så fort hvis jeg gjør to sider om gangen. Så hvis jeg hadde opprinnelig 1.000 sider, nå er jeg bare nødt til å snu 500 ganger, ikke fullt 1000 sider for å få potensielt i verste fall til enden av telefonen bok, der noen som Mike Smith eller noen med et senere navn kan faktisk være. Men selvfølgelig, vi mennesker absolutt ikke kommer til å gjøre det, sikkert ikke på dette punkt i våre liv. Hva er en rimelig menneskelig sannsynlig kommer til å gjøre? PUBLIKUM: Gå rett til The9 S-er. DAVID J. MALAN: Gå rett til S-er? Hvordan går jeg rett til S-er? PUBLIKUM: Rip den i to. DAVID J. MALAN: Vel, det er ingen merking. Så, ja, hvis det var faktisk en etikett eller en klebrig fane for S, vi skal hoppe rett i det. Men det er ganske ufarlige. Så det beste jeg kan gjøre er grovt til S delen eller kanskje grovt inn i midten. Men nøkkelen takeaway now-- og intuisjon at du har tatt for gis for årene probably-- er at hva gjør du nå vet om dette problemet? PUBLIKUM: [uhørbart] DAVID J. MALAN: Mike Smith er sikkert ikke i dette halvparten av problemet fordi Smith kommer etter midten som er omtrent det M-delen, det synes å være. Så som du kanskje har sett på Visitas, kan vi nå bokstavelig talt rive dette problemet i to. PUBLIKUM: Woo! DAVID J. MALAN: Det er blir lettere og lettere. [APPLAUSE] Der du går. [Latter] Og nå er jeg fundamentalt har det samme problem, men det er bokstavelig talt halvparten så stor. Jeg er fortsatt ute etter Mike Smith. Og jeg påstår at jeg kan fortsatt let for ham på samme måte, splitte problem i halv igjen, rive problemet på nytt i to, som nå etterlater meg med et problem en fjerdedel av størrelsen dramatisk kaste at halvparten borte, og gjenta denne prosessen igjen og igjen og igjen, skotter ned ved hvert punkt til å vise hvis Mike Smith er på den aktuelle siden. Nå hvis jeg gjør dette riktig, til slutt vil jeg finne meg selv med bare én side på som Mike Smith er om han er faktisk i telefonboken. Selvfølgelig, jeg kunne aldri ringe Mike igjen. Men poenget her er at hvis vi begynte med 1000 sider, min første algoritmen, snu siden, kanskje 1000 times-- definitivt mindre fordi det er S navn og ikke en Z navn, men som mange som 1000 sider potensielt. Second algoritme, bedre. 500 sider. For det tredje algoritme, skjønt, hvor mange skritt ville det ta å dele opp en 1000 side telefonboken i halvparten sånn? 10, gi eller ta. Så bare ved å bla gjennom den telefonboken, dykking og erobre, så å si 10 ganger, vil jeg gjøre min vei ned til bare én enkelt side. Og slik at vi kan fange opp denne intuisjon nå litt grafisk hvis du bare vurdere denne super enkel graf. Vi er på x-aksen, eller horisontal aksen, er størrelsen på problemet, antall sider i telefonboken. Og dataforskere generelt liker å kalle på størrelse av et problem n, der n er bare noen variabel som represents-- i dette case-- antall sider. Den vertikale, eller y-aksen, her er kommer til å være den tid til å løse, kanskje antall side svinger, kanskje antall sekunder eller minutter, uansett målenhet er. Og så denne røde linjen representerer den første algoritme, fordi det er en 12:59 Forholdet mellom antall sider og hvor lang tid det tar. Hvis Verizon dobler antall sidene i telefonboken neste år, min kjører tid-- den tiden som kreves for å utføre at første algorithm-- dobler i verste fall. Men den andre algoritme, hvor jeg sitter og blar med to, krever mindre tid til en gitt størrelse problem. Så hvis jeg har dette mange sider her-- varsel at den gule linjen antyder mindre tid til å løse. Og ja, den representerer, vi vil si, n over to. Men hva er formen på den tredje og endelig kurven kommer til å se ut? Ja, det er faktisk kommer til å look-- jeg vet ikke hva du skulle si. Men la oss se hva du skulle si. PUBLIKUM: Sånn. DAVID J. MALAN: Det kommer til å se ut dette, en logaritmisk slope-- exactly-- der du har denne merkelige skråningen. Det er ikke lenger en rett linje. Og hva er overbevisende om det er at selv om grafen er nå avskåret, du kan ekstrapolere i din oppmerksom på at det grønne linjen er ikke kommer til å øke i høyde så mye som du går videre ned den horisontale aksen. Faktisk, Verizon, for eksempel, kunne doble antall sider i telefonen bok fra i år til neste år fra 1000 til 2000 sider, men ingen big deal. Med denne tredje og siste, det er en intuitiv algoritme dele og erobre. Det kommer til å ta meg hvor mange flere trinn neste år å finne noen liker Mike Smith? PUBLIKUM: One. DAVID J. MALAN: Det er bare ett. Og de kan firedoble det, det er kommer til å ta meg bare to flere trinn og så videre. Og så dette er testament til bare hvordan noen forsiktig design og noen forståelse for hva dataen er kan gjøre enda bedre. Nå er vi utro en litt i betydningen at vi utnytte en antagelse. Hva er min antakelse om vår telefonboken som tillot meg å splitt og hersk i denne intuitive og fortsatt riktig måte? PUBLIKUM: [uhørbart] DAVID J. MALAN: Yeah. Så det ble bestilt. Det ble ordnet alfabetisk etter telefonboken selskapet. Hvis det var i tilfeldig rekkefølge, som ville være et helvete av en telefonboken, men det absolutt ikke ville egner seg til algoritmen Jeg brukte, fordi du ville aldri bare skje på tvers av Mike Smith Hvis du holdt å dele inn halvparten på den måten ved en tilfeldighet. Så la oss nå formalisere hva er klart intuitivt. Så noe som kalles pseudokode er hvor vi vil begynner noen av våre innledende problemer. Og dette er en generisk måte å beskrive en algoritme eller et datamaskinprogram, ikke bruker C eller C ++, eller Java, eller noen bestemt språk, men bare bruker engelsk, med som noe menneske kan bli kjent. Og vi kan skrive pseudo for dette problem på følgende måte. Trinn en, plukke opp telefonboken. Trinn to, åpen for midten av telefonboken. Trinn tre, se på navnene. Trinn fire, hvis Smith er blant names-- Og nå er dette en interessant konstruksjon. Det er et beslutningspunkt. Det er et veiskille, hvis du vil, en gren, så å si. Så jeg kommer til å rykke inn bare ved konvensjonen step-- ikke five-- som er å si, jeg skal ringe Mike. Så dette innrykk, helt vilkårlig menneskelig konvensjonen, er men det bare ment å formidle semantisk at hvis Smith er blant navnene, da skal jeg ringe Mike. I mellomtiden i trinn seks, varsel at innrykk er borte. Så annet er den andre gaffel i veien, den andre veien jeg kan reise. Så annet hvis Smith er tidligere i boken, hva er Mitt neste steg trolig kommer til å være her? PUBLIKUM: Du går til venstre side. DAVID J. MALAN: Ja, så gå til den venstre halvdelen av telefonboken. Kast høyre halvdel hvis Smith er tidligere i boken. Så åpent til midten av den venstre halvdelen av boken. Og så steg åtte, gå til linje tre. Og dette er en nysgjerrig sløyfe jeg er induserende, en rekursjon så å si. Men mer om det i fremtiden. Jeg bruker min samme algoritme, min samme pseudokode, å løse det samme problem igjen fordi det eneste som har forandret seg er størrelsen av problemet, ikke målet mitt, og ikke personen Jeg ser etter. Så jeg kan bruke algoritmen at jeg allerede har definert. Else if Smith er senere i book-- du kanskje guess-- åpent til midten av høyre halvdel av boken. Og igjen, gå til linje tre. Else-- hva som er den siste linjen i dette programmet kommer til å bli? Hvis han er ikke blant de navn på den siden jeg på, hvis han ikke er tidligere i boken, og han er ikke senere i boken, hva vet jeg er sant om Mike Smith nå? PUBLIKUM: Han er ikke i boken. DAVID J. MALAN: Han er ikke i boken. Så det beste jeg kan gjøre er bare gi opp og stoppe dette programmet. Greit. Så på dette punktet, la oss ta en rask gjennomgang av noen av hva som venter. Og faktisk, jeg sluttet her av et antall ansatte CS50. Hvis disse folkene kunne alle bli med meg her oppe på scenen. [APPLAUSE] Mind du, dette er bare en undergruppe av CS50 personale siden hvert år vi har nesten 100 ansatte medlemmer i roller selvfølgelig assistenter, undervise stipendiater, og mer. Kom opp. Så de vil bli med oss ​​her klønete for bare et øyeblikk som vi gir en rask tur i hva du bør forvente her i kurset. Så først og fremst må vi SAT / UNS som gradering alternativet i kurset. Dette er ment bevisst å være et alternativ hvorved hvis du er litt urolig på å være i kurset, og du frykter failure-- selv om ærlig fiasko betyr sårer din GPA, å få en B og ikke en en-- som er nettopp det, i hvert fall for en gateway selvfølgelig liker CS50 og andre introduksjonskurs, denne gradering måte er ment å tillate. Jeg helhjertet oppmuntre students-- spesielt Hvis på fence-- å starte Kurset SAT / UNS, selv forbli SAT / UNS. Men du kan sikkert bytte til et brev karakteren med den femte mandag i begrepet. Oppriktig, tilbake når jeg var en førsteårsstudent i 1995, Jeg selv visste ikke engang ta CS50 fordi jeg ikke får opp nerve å faktisk gå foten i klasserommet. Det virket en domene altfor ukjent for meg og egentlig bare for de venner av meg, ærlig, som hadde vært programmering siden de var seks eller kanskje 10 år gammel. Og det var bare fordi jeg var stand til å ta CS50 i min tid i tilsvarende versjon av SAT / UNS-- bestått / ikke bestått tilbake i day-- at selv jeg tok 50. Og en eller annen måte, er jeg her igjen med deg i dag. Nå i mellomtiden hva annet du bør huske på om lag 50 er samtidig påmelding. I motsetning til ryktene om at du kanskje har hørt, du kan, faktisk, samtidig melde deg på CS50 og en annen klasse som møter ved samme eller noe overlapp tid som CS50 foredrag her. Se pensum for opplysningene for gjennomføring derav. Forelesninger, i mellomtiden, i motsetning til hva som er offisielt i katalogen, vil vanligvis bare møtes for bare en time. Av og til kan vi kjøre litt lang. Men husk at mål i CS50 foredrag er å gi deg en konseptuell oversikt, forhåpentligvis noen demonstrasjoner, kanskje også noen giveaways, av hva som venter for uken som følger. Og så i forelesninger, vil vi utforske disse emnene og eksempler sammen, bringe elevene opp på scenen, og bemanne opp på scenen så ofte som vi kan, for bare et par timer hver uke. Seksjoner, i mellomtiden, vil være tilbys av disse folkene her-- mange av dem undervise stipendiater, noen av dem selvfølgelig assistants-- vilje skje ukentlig. Og hva er nøkkelen til å holde i bakhodet er at vi trenger have-- ikke ulikt First Netter, musikken class-- ulike spor av seksjoner for studenter mindre komfortable, mer komfortable, og et sted i mellom. Og ærlig talt, vet du om du er mindre komfortabel. Og du sikkert vet om du er mer komfortabel. Og hvis du ikke er helt sikker, er du per definisjon et sted i mellom. Så når det gjelder tid til seksjon i en uke eller så, per pensum, vi vil be deg om det spørsmålet. Og du kan selv velge basert på din egen komfort nivå og være med students-- være med grønn dots-- lik i komfortnivå til deg. I mellomtiden har vi problem setter, som til slutt vil definere din erfaring i dette kurset. De blir tilbudt typisk i flere utgaver. En standard utgave som vi forventer mest hver elev i kurset for å takle men også en såkalt hacker utgave som tilbyr ingen form for ekstra kreditt outright Men egentlig skryte å si at du har prøvd og taklet kursets hacker utgaver som nærmer lignende materiale men fra en mer sofistikert vinkel. Hva vi tilbyr for standard utgave, for, igjen, en super flertall av studenter, er ikke bare walk-throughs, som er videoer ledet av kursets ansatte som virkelig gå deg gjennom kursets problemer og mulig utforming implementeringer. Og vi har også, etter Faktisk, tilbyr postmortems, der hvis du lurer på hvordan du kunne ha eller burde ha løst noen problem, lærerstaben vil lede deg gjennom de på video i tillegg. I mellomtiden, hva som venter også er fem dager sene og det faktum at vi vil slippe laveste problem satt poengsum. Vi absolutt setter pris på at i bytte for den belastning som 50 forventer av dere, blir livet i veien noen ganger, om ikke fem ganger. Og så dette vil tilby deg litt av fleksibilitet, forlenge fristen fra, sier en Torsdag midt på dagen til fredag ​​midt på dagen. Se pensum for gjennomføring detaljer om dette. Nå hva nå venter? Og det er bare fore for meg nå akkurat hvor lenge Jeg har dere stå her på scenen. [Latter] DAVID J. MALAN: Men vi får til klimaks ferdig før lenge. Så hva venter i form av oppgavesett? Vel, kanskje en teaser av hva vi alle gjorde i fjor med dine forgjengere. I det første problemet sett fjor introduserte vi Scratch, en grafisk programmeringsspråk som lar deg programmere bokstavelig talt av dra og slippe brikkene, som disse, som er minner om de konstruerer vil se bare én uke Derfor, når vi bytter til en mer tradisjonell språk, kjent som C. I fjor vi gikk videre på dette problemet sett, involverer for kryptografi, den scrambling av informasjonen å holde det fra statlig eller venner ' øyne som du ikke ønsker å se det. Kodet i her er en melding som snart du vil være i stand til å dekryptere eller de-krafse. Breakout var et problem satt i fjor, hvor du bruker disse nye funnet programmering ferdigheter til å faktisk gjennomføre et spill wherein-- som du kanskje husker fra childhood-- Målet var å bash klosser som er på toppen av skjermen her, samler en scorer underveis, og implementere dine egne algoritmer som denne løsningen til slutt lar deg spille spillet. I mellomtiden senere i semester, vil vi gi deg en ordbok med 143 091 engelske ord. Og du vil bli utfordret å skrive et program som stavekontroll, dokumenter, ved lasting at mange ord inn i minnet så effektivt som mulig. Vanligvis setter deg opp mot dine klassekamerater hvis du velger inn i en bit av en utfordring i ledertavlen for å se hvem som kan bruke færrest sekunder driftstid, og færrest av megabyte minne, og faktisk fin-tuning programmene dine å være utrolig ressurseffektiv ikke bare tid. I fjor også, så vi på slutten av semesteret på web-programmering. Og ja, vi vil gjøre det igjen dette år med flere oppgavesett, introdusere deg til teknikker og tankegangen som du kan bruke disse programmeringsferdigheter til nettsteder, dynamiske websider, nettsteder som faktisk løse problemer og oppføre seg annerledes og er ikke bare statisk nettsteder med statisk informasjon. Det siste prosjektet til slutt vil definere, skjønt, klimaks av kurset for studenter, der vil du bli utfordret til å gjennomføre de fleste noe av interesse til deg, så lenge det liksom trekker på kursets leksjoner. Og som du så i video i starten, vi vil avslutte semesteret med CS50 Hackathon, som hvis, ukjente, vil begynne kl 07:00 en natt og ende på 7:00 neste morgen. Rundt 09:00, vil vi For i første middag. Rundt 01:00, vil vi For i andre middag. Og hvis du fortsatt stående på 05:00, vi vil shuttle buss du til IHOP for frokost. Den CS50 Fair, i mellomtiden, er en hendelse som 2000 pluss lærere, studenter, og ansatte fra hele campus vil kommer til å se dine prestasjoner i kurset og den endelige prosjekter og kreasjoner som du lager på din bærbare PC, stasjonære, eller kanskje til og med lyspærer. I mellomtiden kontortid og støttestrukturen. Og nå ville det har vært en bedre tid til å bringe deg helt opp. Arbeidstid vil finne sted fire netter en uke for flere timer hver natt med generelt 20 til 30 av de Kursets ansatte på vakt på en gang å gi deg intime en-mot-én muligheter for støtte med kursets oppgavesett. Veiledning vil også være tilgjengelig, særlig for studenter mindre komfortabel-- eller tør si minst komfortabel-- for hvem kontortid er ikke den mest givende miljø og er absolutt ikke den mest stress-fri. Spesielt når tidsfrister pressing, vi vil proaktivt koble deg selv med et medlem av de ansatte til å jobbe med på noen regelmessig etter hvert som behovene og timeplanen deres tillater. Og ansatte. Tillat meg å presentere Davon, Rob, og Gabriel, årets hoder. Hvis du ønsker hver liker å si-- [APPLAUSE] voldtektsofre ord. [APPLAUSE] Davon over her er den Kursets manager, som betyr i sin fulltids rolle han hjelper med gjennomføringen og logistikk av CS50. Davon: Ja, hei, folkens. Du vil se mye til meg i kontortiden. Jeg skal være lærer seksjoner. Og hvis du skyter e-post i forkant, Jeg vil trolig være å svare. Så jeg får se mange av dere hele semesteret. Og velkommen til CS50. DAVID J. MALAN: Og nå Gabriel, som selv var bare en førsteårsstudent i fjor, men for de siste par årene har vært i drift sin egen versjon av CS50 i Brasil, hvor han lastet ned alle kursets content-- som er helt klart å være filmet og plassert online-- slik at han kunne oversette det til Portugisisk og deretter lære mer enn 100 av hans klassekamerater over løpet av et par år, undervisning i sitt morsmål kursets pensum. GABRIEL: Hei. [APPLAUSE] GABRIEL: Hei, jeg er Gabriel. Jeg er leder TF av kurset. Og jeg håper du vil elske CS50. Dette er CS50. DAVID J. MALAN: Nå for Rob. Åh, du vil innføring? ROB: Nei, jeg vet ikke. [Latter] DAVID J. MALAN: Og Rob Boden. [Latter] ROB: Hei, jeg er Rob. Dette er mitt femte år involvert med kurset. Hvert år, det er bare en bedre og bedre klasse så dere er klart kommer til å bli kjempebra. Jeg håper dere alle har det gøy med det. Jeg kommer til å ha det gøy med det. Så se deg rundt. DAVID J. MALAN: Og tid vil ikke tillate oss-- [APPLAUSE] Tiden vil ikke tillate oss å introdusere alle på scenen og alle deres kolleger som er shopping klasser i dag. Men la meg få presentere Belinda og CS50 Puzzle Dag, som venter dette kommer lørdag, som er den første av de kursets store arrangementer. Dette spesielt ment å hamre inn poenget at informatikk er slutt ikke om programmering, men heller om problemløsning mer generelt. Og Puzzle Day, som du vil se, vil bringe deg og dine klassekamerater together-- håper vi denne lørdagen. BELINDA: OK. Hei, folkens. Så takk. Så som vår strålende kaptein sa, jeg heter Belinda. Jeg er en sophomore på Quincy House. Jeg, akkurat som dere, tok CS50 fjor, virkelig elsket det. Jeg har en soft spot for dere i den tredje rad. Og jeg er stolt over å si, jeg er nå i et forpliktende samarbeid med CS50 [uhørbart]. OK. Det var min halt versjon av en vits. Uansett, så går videre, bare ønsket å invitere dere alle til I-lab, eller HBS elveblest. Vi kommer til å være å ha Puzzle Day 12:00-03:00. Og det er en flott mulighet for deg gutta å møte de andre CS venner, løse noen ikke-CS puslespill, som kaptein nevnt, og også spise litt gratis mat, tjene noen fantastiske premier, som gavekort, $ 75 per person, og also-- hva var det? Wii U eller noe? Wii U? Ja. For vår tombola. Awesome. Så jeg vil holde rundt etter klasse. Og hvis dere har noen spørsmål, gi meg beskjed. DAVID J. MALAN: Og du vil se, utover dette er det ingenting å gjøre i dag. Det første problemet satt vil gå ut fredag. Men for å bringe oss hjem i dag, vil jeg gjerne introdusere deg til spesielt én mer medlem av staben, Colton Ogden her, hvis hender er nå beskyttet over deg med dette MIDI controller å hamre inn poenget ytterligere som informatikk, også, har anvendelse langt utover ingeniør og STEM og informatikk selv, strekker seg selv til slike domener som musikk. Colton har vennlig offered-- jeg trodde en av dem skulle fikse fokus. Andrew, hvis vi kunne tilkalle fokus over her for bare et øyeblikk. Hva Colton har gjort på forhånd er program denne enheten, dette pad knapper som du ser avbildet her oppe, som en MIDI-kontroller, hvorved hver av disse knapper er kablet til en bestemt musikknote eller en lyd, mer generelt et opptak, slik at ved å spille mønstre av disse knapper, mye som punktmønstre, kan representere andre høyere nivå konsepter. Vil han være i stand til slutt å ta oss hjem her i dag? Uten videre, hvis vi kunne dempe lysene, og slå på skjermen bak Colton. PUBLIKUM: Woo! DAVID J. MALAN: Dette er CS50. [Musikk spilles] [APPLAUSE] Det er det for CS50. Vi vil se deg fredag. Noen kake venter på deg i tverrskipet. [Musikk spilles]