[Musik spiller] [Applaus] David J. MALAN: Dette er CS50, Harvard University introduktion til den intellektuelle virksomheder af datalogi og kunsten at programmeringen. Nu, hvis du er blandt dem, der hvert år sidder her med en smule nerver i dit sind, sådan at du ikke tror, ​​du hører til her, du tror, ​​at de fleste nogen sidder omkring dig kender langt mere end dig, er faktisk mere komfortabel end dig på computeren videnskab eller computere mere generelt, indser at 78% af de studerende, der nu tage CS50 har nogen forudgående erfaring. Faktisk er der 100 punkter der på skærmen, hvoraf 78 er fast grønt, hvilket betyder, at du, Hvis du er blandt det demografiske, er i meget godt selskab her på ud. Og hvis du er i stedet blandt de 22% af CS50 studerende, der gør faktisk have forudgående erfaring, enten i gymnasiet eller et andet program, indser, at du også vil blive udfordret i løbet. Ikke alene har vi forskellige spor for studerende mindre komfortabel og mere komfortabel ens i sektioner, vi har også såkaldte hacker udgaver af de fleste problem indstiller, at vil udfordre de studerende med at yderligere erfaring at undersøge lignende materiale men ud fra et mere sofistikeret perspektiv. Men hvad er datalogi? Nå, i sidste ende, hvad der kommer til noget, som du udforske dette felt er ikke så meget, hvor du ender i forhold til dine klassekammerater, men hvor man selv ender i uge 12 versus hvor du begynder her i uge nul. Nu computer science-- godt, lad os kalder det videnskab computation-- hvor beregning er egentlig bare en fancy måde at sige, idet nogle input, producerer nogle output, og gør det ved at kører algoritmer, sæt af instruktioner for at løse nogle problem på disse input for at frembringe nogle output eller løsning, hvor du er interesseret. Så vi havde for nylig lejlighed til at rejse ud til Californien for at mødes med en alumna. Hendes navn er Susan Wojcicki. Og hun vil gerne tale til dig her på video at vidne til, hvor relevant bare en smag af computer videnskab på indledende niveau kan være. Selv hvis du ikke gå på at forfølge datalogi som et felt, eller endda teknik, eller STEM mere generelt, du vil se, i virkeligheden, hvordan en bestemt kursus så påvirket hendes liv. Og hun kun lige tog det, da hun var en højtstående her på Harvard College. Hvis vi kunne dæmpe lyset til Susan. SUSAN Wojcicki: Hej, verden. Jeg er Susan Wojcicki. Jeg er administrerende direktør for YouTube. Og jeg tog CS50, da jeg var en senior på Harvard i 1990. Jeg var faktisk en historie og litteratur større. Og min junior sommer, Jeg indså, at jeg måske ønskede at lære noget om computere. Og så kom jeg tilbage. Jeg tog CS50. Det var svært, men det var mest fantastiske klasse tog jeg. Det ændrede hvordan jeg tænker om alt. Og når jeg dimitterede fra Harvard i 1990, gik jeg til Silicon Valley. Og jeg fik et job. Og jeg har arbejdet i tech lige siden. David J. MALAN: Nu hvad Susan nævner ikke i denne video, at det faktisk var i hende garage, som Google selv var grundlagt af Larry og Sergey. Nu er vi også nået ud til vores venner ved code.org, en organisation, der i det forløbne år har været få folk især begejstrede datalogi og programmering, i særdeleshed. Men det er værd at bemærke, at programmeringen er ikke datalogi per se. Datalogi er ikke programmering. Snarere programmering er blot en tool-- som alle jer vil være alt for godt fortrolig med semesters end-- sådan at du kan anvende ikke bare til fremtidige kurser i CS men uanset felter fra hvorfra du kommer i humaniora, samfundsvidenskab, naturlig videnskab eller lignende. Faktisk tillade et par andre alumner og deres kolleger at tale med anvendeligheden af marken, der venter. Bill Gates: Jeg var 13, da jeg først fik adgang til en computer. JACK DORSEY: Mine forældre købte mig en Macintosh i 1984 da jeg var otte år gammel. Mark Zuckerberg: Jeg var i sjette klasse. SPEAKER 1: Jeg lærte at kode i college. RUCHI Sanghvi: Freshman år, først semester Introduktion til datalogi. Bill Gates: Jeg skrev et program der spillede tic-tac-toe. DREW HOUSTON: Jeg tror, ​​det var temmelig ydmyg begyndelse. Jeg tror, ​​det første program Jeg skrev spurgte ting som, Hvad er dit foretrukne farve? Eller hvor gammel er du? ELENA SILENOK: Jeg lærte først hvordan man laver en grøn cirkel og en rød firkant vises på skærmen. GABE NEWELL: Den første gang jeg havde faktisk noget kommer op og sige, hej, verden. Og jeg lavede en computer gøre det. Det var blot forbløffende. Mark Zuckerberg: lære til programmet ikke starter som ønsker at lære alle datalogi eller forsøger at beherske dette disciplin eller noget lignende. Det bare startede, fordi jeg ønskede at gøre dette én simpel ting. Jeg ønskede at gøre noget, var sjovt for mig og mine søstre. Og jeg skrev dette lille program. Og så dybest set bare tilsat en lille smule til den. Og da jeg havde brug for at lære noget nyt, Jeg slog det op, enten i en bog eller på internettet, og derefter tilsat en lille smule til den. DREW HOUSTON: Det er virkelig ikke ulig spille et instrument eller noget eller spille en sport. David J. MALAN: Okay. Så lad os nu faktisk dykke i en lidt dybere. Hvad er disse input og output at vi taler om her? Så hvordan omkring noget simpelt? Du kender sikkert, selvom du har ingen kendskab til datalogi overhovedet, at computere eller anden måde anvender og forstår kun nuller og ettaller. Men hvordan kan det muligvis blive givet hvordan meget nutidens stationære og bærbare computere både kan gøre? DNA'et af dagen, den eneste alfabet, at de forstår er nul eller én. Nå, overveje dette. Vi mennesker har en tendens til at bruge decimal system. "December", hvilket betyder 10. Og det er 10, fordi vi har 10 cifre, 0 til ni. Nu computere, derimod, tendens til at bruge binær. "Bi" betyder to. Så de har en tendens til kun nul og en til at bruge. Men det viser sig, at selv bare med nuller og ettaller, at er et tilstrækkeligt stort alfabet som at repræsentere de fleste et stykke data, du ønsker, uanset om det er et nummer, uanset om det er et brev, uanset om det er en grafisk eller video på skærmen. Overvej, for eksempel, hvordan vi mennesker fortolke typisk dette nummer her. Dette er blot tre cifre, en, to, tre. Men vi ved, at dette tal medfødt nu som 123. Men hvorfor er det? Tja, hvis du tænker tilbage til måske folkeskolen, du sandsynligvis blev oplært til at tænke på disse numre som værende i søjler, hvor den ene er i hundredvis sted, de to er i TEN sted, og tre er i dem sted. Hvorfor er det faktisk nyttigt? Nå, så tænk på super enkel aritmetiske at vi alle har været gjort i årevis nu. Effektivt, hvis du har fået en en i hundreder sted, du gør den hurtig math 100 gange 1 plus 10 gange 2-- fordi to er i snesevis place-- plus 1 gange 3-- fordi tre er i dem sted. Så selvfølgelig, hvis vi faktisk multipliceres ud, hvad vi egentlig repræsenterer med denne pattern-- en to three-- er 100 plus 20 plus 3, som naturligvis er 123. Nu er binær, og computere virkelig, fundamentalt taler samme sprog at vi gør. De har blot en mindre alfabet. Så computere har kun nuller og dem til deres rådighed. Så mens vi mennesker har i det væsentlige beføjelser 10 i hver af disse places-- 10 til nul, 10 til den ene, ti til de to, der giver dig 110 og 100 henholdsvis. Fordi computere har kun to værdier de kan forstå, nul og én, de skal bruge forskellige værdier i disse kolonner, en, to, fire. Og hvis vi holdt, otte, 16, 32, 64 og så videre. Men mønsteret og mentalitet er nøjagtig den samme. Så ved denne logik, nogen, hvordan ville Jeg går om der repræsenterer antallet et binært? Hvis du har aldrig selv tænkt på dette før, hvad er din tarm sige? Publikum: One. David J. MALAN: One. Præcis. Vi har bare brug for en en i dem sted fordi nuller tilstrækkelig til at give os hverken fire eller to. Så én gange én er lig én. Nu tingene bliver lidt interessant. Hvis jeg ønsker at repræsentere i binær antallet to-- men igen, selvom du har aldrig talt dette sprog før, hvordan gør vi repræsenterer i binær den værdi, vi mennesker kender som to? Nul et nul. Bare sætte den i kolonne, du ønsker det. Nu er det ved at blive ret let nok nu. Så hvis jeg ønsker at repræsentere three-- der er ingen tre kolonne. Så igen, jeg kan nu tilføje disse værdier sammen ved at sætte en en her. Så 2 gange 1 plus 1 gange 1 er naturligvis 3. Nu tingene bliver lidt sjov i at dem nu blevet nuller. Og til at repræsentere fire, får jeg dette. Og hvis vi tilvækst langsomt her-- der ville være fem. Dette ville være seks. Dette ville være syv. Men nu har jeg synes at have løber ind i et problem. Hvordan kan jeg gå om at repræsentere eight-- ville være den næste værdi. Ja, så har vi brug for en ny bits. Og, ja, hvis du har hørt denne sætning før, bits, det er bare en forkortelse for binært ciffer nul eller én. Og så jeg tilfældigvis at repræsentere kun tre sådanne bit her. Men hvis jeg havde en måde at lagre ikke tre forskellige bits, men fire, sikkert jeg kunne repræsentere otte, og derefter ni, og derefter 10, og endnu højere og højere. Men det kalder derefter i spørgsmålet om, hvordan vi kan gå om repræsenterer disse ting i første omgang. Det er én ting at tegne dem op her på et dias, men hvordan kan du repræsentere dem hvis du er en mekanisk enhed? Hvad er en computer gør for at repræsentere input og output, som fundamentalt definere beregning ved slutningen af ​​dagen? Jamen, hvad med noget super enkel som dette? Det er bare en pære. Og jeg kan udløse denne pære til at gå på ved at dreje nogle el på og tillader elektroner at strømme igennem, som ændrer sin stat eller dens værdi, så at sige. For eksempel er en gammel skole bordlampe her med et sådant pære inde i den. Og lige nu er det ikke virkelig gør noget nyttigt. Men så snart jeg sætter det i en stikkontakt og derefter bruge denne switch-- eller vi kan endda kalde det en transistor eller tænke på det som such-- Jeg kan nu repræsentere enten denne værdi, hvor lyset løgets naturligvis slukket, eller denne værdi. Denne værdi eller denne værdi. Denne værdi og så videre. Så inde i en computer, formentlig, er langt mindre stykker hardware, men at der ved udgangen af dagen simpelthen at bruge electricity-- måske fange det-- og derefter enten holde noget på eller holde noget væk. Selvfølgelig er dette ikke særligt interessant at gøre med blot en enkelt pære. I virkeligheden, hvor højt kan jeg tælle på binær med denne bordlampe her? Publikum: One. David J. MALAN: En, højre? Jeg har brug for mere skrivebord lamper, hvis jeg faktisk ønsker at tælle højere. Men vi kan gøre det bedre end det. Fordi pærer, vi har lagt i disse ting er faktisk mere avanceret pærer end Gårsdagens ville tillade. Og de er faktisk netværksbaserede pærer. Og klaser af virksomheder gøre disse ting i disse dage. Men det viser sig, at dette især kommer med en funktion, hvormed du kan ændre sine farver. Så for eksempel, hvis du smykket dit kollegieværelse med et par af disse lys løg, afhængigt af dit humør, afhængigt af hvem der kommer ind, afhængig af vejret, afhængigt af tidspunktet af dagen, kan du faktisk ændre farverne pærer i dit værelse. Og det er fordi disse lys pærer og andre som det har, hvad der er kaldet et API, en ansøgning programming interface, som er et emne, som du vil være godt bekendt med ved semesters slutning. Og dette er bare en fancy, kryptisk måde at sige, du kan programmere disse lys løg til at gøre dit bud. Du kan sende dem beskeder ligesom dig, et menneske, kan sende en besked til en webserver sige, giv mig dagens nyheder eller give mig min e-mail. Du kan sende mere mystisk beskeder til disse pærer at sige, at tænde og slukke. Men det er ikke alt, interessant. Man kan sige, tænd rød, tænde grøn, tænd blå, alle med samme pære. Og du kan endda, med en smule mere kyndige, siger, drej dig selv til blå når det er en dyster dag udenfor, for eksempel. Det kan faktisk lappe ind en vejr-API og finde ud hvordan vejret er, tidspunktet på dagen, eller andre sådanne udløsere. Så i virkeligheden to CS50 egne medarbejdere, Dan Bradley og Ansel Duff her, venligt indkøbt os en hel masse af disse pærer. Og de byggede CS50 s første nogensinde binære løg, hvor vi har repræsenteret her-- med disse legesyg lille magnets-- de forskellige pladsholdere vi hentydet til bare en smule siden. Så måde herovre er den dem sted, to, fire. Og vi kunne ikke se højere end det. Men selvfølgelig, de er potenser af to. Otte, 16, 32, 64, og 128. Så hvis jeg nu ønsker at være en smule mere avanceret end at bruge denne gamle skole switch, Jeg har her på denne iPad en super enkel brugerflade at Dan Bradley, en tidligere studerende og underviser nu fyr, programed bruge nogle HTML og JavaScript, som er markup og programmering sprog hhv. Og du kan sikkert see-- selv i tilbage-- der er et stort plus og et stort minus, plus en knap for hver af disse pærer. Og hvad dette vil tillade mig at gør, er for eksempel, skal du klikke på plus og udgør nu af Selvfølgelig hvad nummer? One. Og jeg kan ramme det igen. To. Tre. Fire. Five. Seks. Syv. Og her nu får vi at rollover men vi har en fjerde bit dette tidspunkt, så nu har vi otte. Så vi kunne gøre det i temmelig lang tid. I virkeligheden, som en side, hvor højt kunne vi tælle? Anyone? Publikum: 255. David J. MALAN: 255, ikke? Må ikke bekymre dig for meget om matematik for nu, men det er en smuk anstændigt nummer. Men det rent faktisk bundet bare hvor mange stykker information, som et brev eller en grafisk at vi kunne repræsentere. Men ligegyldigt for nu. Jeg har tænkt mig at gå videre og slukke for dem alle. Og hvis jeg kunne, ville jeg gerne bede om en frivillig, vores første volunteer-- åh, hello-- på scenen. Fangsten er du nødt til at være komfortabel vises, som du tydeligt er foran alle dine klassekammerater, samt på internettet. Og lad mig se lidt ud over det-- hvad med her i den hvide skjorte? Og hånden op. Kom op. Hvad er dit navn? Publikum: Jackie. David J. MALAN: Jackie. Jackie, kom op. Så hvad er der også på dette iPad er en knap kaldet Game Mode. Og denne Game Mode er vil tillade mig at indtaste på forhånd en bestemt decimal nummer, numrene er vi mennesker bekendt med. Og så vil du blive udfordret her for at bruge knapperne på top-- en for hver af disse bulbs-- til rent faktisk at finde ud af mønster af pærer der repræsenterer det pågældende nummer. Og jeg er ked af det, hvad var dit navn igen? Publikum: Jackie. David J. MALAN: Jackie. Okay. Godt at møde dig. Så lad mig gå videre og program for verden at se nummer 15. Vi vil holde det lille ved første her. Og jeg har tænkt mig at gå ind i game mode. Og jeg har tænkt mig at præcisere, give os nummer 15. OK. Og nu med alle watching-- hvis du vil måske stå på denne måde, fordi det vil linje up-- gå videre og skifte de otte knapper langs toppen at tænde pærerne på eller fra som du ønsker det. Publikum: OK. David J. MALAN: Og ingen snyd ved at ramme plus 15 gange. Åh, vil vi gøre det. PUBLIKUM: Åh, vent. Jeg er så ked af det. David J. MALAN: Du kan også slå pærer lys på individuelt med hver af disse knapper på toppen. PUBLIKUM: Åh, OK. Så det ville være like-- David J. MALAN: OK. Så nu har vi otte. Så lad os stoppe den publikum til at engagere sig her. Hvilket nummer er Jackie øjeblikket repræsenterer? 11. Så vi er der næsten. Og fremragende. Så vi har vores første vinder. Tillykke med det. Og vi troede, vi ville have nogle fantastiske foræring. Hvis du gerne vil være en sådan kollegieværelse her på campus, du kan selv have et afsluttende projekt bruger nu denne API, takket være Jackie. Så nu-- [Applaus] --if vi kunne, en mere sådan rundt på dette. Åh, nu alle ønsker nogle pærer. For den såkaldte hacker udgave, vi kommer til at rampe op en-- åh, yeah, uforpligtende. Jeg tror, ​​du kommer op nu Hvis din hånd kommer ned. Hvad er dit navn? Publikum: Alex. David J. MALAN: Alex, kom herover. Så for Alex, vil vi program i en lidt større antal. Måske i orden. Tallet 50. Publikum: OK. David J. MALAN: Men, som Jeg sagde-- og du måske ønsker at stå her, så at knapperne linje op som du ville expect-- men jeg gjorde kalde dette hacker udgave. Så-- held og lykke! [Latter] Du vil være i stand til at vende dem fra, hvis du-- OK. Fremragende. Wonderful. Tillykke med det. [Applaus] Jeg formoder, at jeg skulle betale op. Tillykke til Alex så godt. OK. Så den ultimative takeaway her er forhåbentlig helt ærligt, den simplicity-- den enkelhed, hvormed du kan få nogle nice lys løg, tilsyneladende i [uhørligt]. Men de repræsenterer, i sidste ende, det samme ideer som vi mennesker er allerede alt for velkendte. Så hvad kunne det næste trin være i progressionen for at forsøge at gøre noget interessant med data og som repræsenterer input, der ikke bare numre, men er måske bogstaver eller mere? Tja, det viser sig, at computeren verden i mange år, simpelthen vedtaget en vilkårlig, men en ensartet standard, der kortlægger tal til bogstaver i alfabetet. For eksempel her er en uddrag fra denne kortlægning. Det hedder ASCII. A-S-C-I-I. Og det er simpelthen en tabel, der kortlægger store bogstaver letters-- i denne case-- til decimal tal. Men hvad er konsekvenserne? Tja, hvis du rent faktisk ønsker at repræsentere noget som en e-mail eller noget tekst på en webside, du naturligvis ønsker at vise de menneskelige bogstaver i alfabet, ikke tal. Så afhængigt af forbindelse med programmet at en bruger ved hjælp af, hvis det er en webbrowser eller e-mail klient, numre kan sikkert være tolkes som bogstaver. Det vil sige, mønstre af bits kan let tolkes som bogstaver. Og så, hvad vi kan få er bogstavet A væsen repræsenteret 65, B repræsenteres som 66. Så hvis vi har en super korte ord, ligesom hej, hvad en computer ville i sidste ende butik i decimal, men virkelig i binær, bruge nogle sekvens af bits, der kan mobilisere en smule af elektricitet på en måde, ville være de to tal 72 og 73. Men det mønster af bit, repræsenterer disse værdier. Så disse så er, hvordan vi kan repræsentere vores input og output. Og det tilstrækkeligt at sige, at vi kan gøre mere komplekse repræsentationer i sidste ende med ting som grafik, videoer, musik og meget mere som vi skal se senere i denne valgperiode. Så bare forlader derefter algoritmer, disse sæt instruktioner, som vi løse reelle problemer. Vi passerer input til algoritmer. Og de algoritmer producerer udgange, forhåbentlig korrekte udgange og forhåbentlig også effektivt ufarligt udgange. Med andre ord, det er én ting at implementere noget rigtigt. Det er en anden ting at gennemføre noget godt eller effektivt. For eksempel, en demonstration at vi er glade for i løbet er denne ene. Men disse ting bliver i stigende grad svært at finde. Men dette er faktisk en gammel skole telefonbog, inden i hvilken er 1000 plus sider navne og telefonnumre. Og hvis jeg ønskede at se op nogen i denne telefonbog, Jeg kunne simpelthen gøre en meget naiv algoritme. Jeg kunne åbne op til den første side, og Jeg kunne begynde at kigge efter, siger, nogen opkaldt Mike Smith. Og hvis han ikke er på den første side, jeg videre til den anden, og derefter til den tredje, og derefter til den fjerde, og så videre, indtil jeg endelig finde Mike Smith. Nu er, at algoritmen korrekt? Publikum: Ja. David J. MALAN: Ja. Hvis han er derinde, vil jeg sidst finde ham. Men det er velsagtens ikke meget effektiv, bestemt ikke hurtigt, fordi, min Gud, hvorfor er jeg spilde min tid spejlvende gennem alle disse sider, når jeg kunne sikkert gøre det fysisk hurtigere? Nå, en lille optimering, så at tale, måske ikke én side ad gangen, men to, fire, seks, otte, ti. Stadig korrekt? Publikum: Nej David J. MALAN: Så nej, hvis jeg for eksempel springe over Mike Smith. Men så længe jeg sikkerhedskopiere pedal én side, hvis jeg skyde ham, måske vi kunne korrigere det ellers kunne være en gotcha. Men er det bedre? Er det hurtigere? Jeg mener, ja. Det er bogstaveligt talt dobbelt så hurtigt hvis jeg gør to sider ad gangen. Så hvis jeg oprindeligt havde 1.000 sider, nu har jeg kun nødt til at vende 500 gange, ikke helt 1.000 sider til at få potentielt i værste fald til slutningen af ​​telefonen bog, hvor nogen Ligesom Mike Smith eller en person med et senere navn kan faktisk være. Men selvfølgelig, vi mennesker er bestemt ikke vil gøre det, i hvert fald ikke på dette tidspunkt i vores liv. Hvad er en rimelig menneske sandsynligvis kommer til at gøre? Publikum: Gå direkte til the9 S '. David J. MALAN: Gå direkte til S '? Hvordan kan jeg gå direkte til S '? Publikum: Riv det i halve. David J. MALAN: Jamen, der er ingen mærkning. Så, ja, hvis der var faktisk en etiket eller en klæbrig fane for S, vi skal hoppe lige der. Men det er temmelig uskadelige. Så det bedste jeg kan gøre, er groft til S sektion eller måske groft i midten. Men nøglen takeaway nu-- og intuition at du har taget for ydes for år probably-- er, at hvad gør du nu kender om dette problem? Publikum: [uhørligt] David J. MALAN: Mike Smith er sikkert ikke i denne halvdel af problemet fordi Smith kommer efter midten hvilket er omtrent M sektion, det synes at være. Så som du måske har set på Visitas, kan vi nu bogstaveligt rive dette problem i halve. Publikum: Woo! David J. MALAN: Det er bliver lettere og lettere. [Applaus] Værsgo. [Latter] Og nu er jeg fundamentalt har det samme problem, men det er bogstaveligt talt halvt så stort. Jeg er stadig på udkig efter Mike Smith. Og jeg tør sige, jeg kan stadig efter ham på samme måde, opdele problemet i halve igen, tåreflåd problemet igen i halve, som nu efterlader mig med et problem en fjerdedel af størrelsen, dramatisk smide at halvdelen væk, og gentage denne proces igen og igen og igen, kigger ned på hvert punkt for at se hvis Mike Smith er på den pågældende side. Nu, hvis jeg gør det rigtigt, i sidste ende finder jeg mig selv med kun én side, hvor Mike Smith er, hvis han er faktisk i telefonbogen. Selvfølgelig kunne jeg aldrig kalde Mike igen. Men pointen her er, at hvis vi begyndte med 1.000 sider, min første algoritme, flip side, måske 1.000 gange-- absolut mindre, fordi det er et navn og ikke en Z navn, men som mange som 1.000 sider potentielt. Anden algoritme, bedre. 500 sider. Tredje algoritme, selvom, hvor mange skridt ville det tage for at opdele en 1.000 side telefonbog i halvdelen sådan? 10, give eller tage. Så kun ved at bladre gennem det telefonbog, dykning og erobre, så at sige, 10 gange, vil jeg gøre min vej ned til blot en enkelt side. Og så vi kan fange denne intuition nu lidt grafisk hvis du lige overveje denne super simpel graf. Vi er på x-aksen, eller horisontal akse, er på størrelse med mit problem, antallet af sider i telefonbogen. Og dataloger generelt gerne opfordre størrelsen af ​​et problem n, hvor n er blot nogle variabel, represents-- i denne case-- antal sider. Den lodrette eller y-aksen, her er vil være tid til at løse, måske det antal sider omdrejninger, måske det antal sekunder eller minutter, uanset din måleenhed er. Og så denne røde linje repræsenterer den første algoritme, fordi der er en for en forholdet mellem antal sider og mængden af ​​tid, det tager. Hvis Verizon fordobler antallet af sider i telefonbogen til næste år, min kører time-- den tid, der kræves til at udføre at første algorithm-- fordobler i værste fald. Men den anden algoritme, hvor jeg flippe med to, kræver mindre tid til en given størrelse problem. Så hvis jeg har denne mange sider her-- varsel at den gule linje foreslår mindre tid til at løse. Og ja, det repræsenterer, vi vil sige, n mere end to. Men hvad er formen af ​​den tredje og sidste kurve kommer til at se ud? Ja, det faktisk kommer til at look-- jeg ved ikke, hvad du ville sige. Men lad os se hvad du ville sige. Publikum: Sådan. David J. MALAN: Det kommer til at ligne dette, en logaritmisk slope-- exactly-- hvorved du har denne nysgerrig skråning. Det er ikke længere en lige linje. Og hvad er overbevisende ved det er, at selvom grafen er nu afbrudt, du kan ekstrapolere i din imod, at den grønne linje er ikke vil stige i højde alt, meget som du gå videre ned det vandrette akse. Faktisk Verizon, for Eksempelvis kunne fordoble antallet af sider i telefonens bog mellem dette år og næste år fra 1000 til 2000 sider, men nogen big deal. Med denne tredje og sidste der er en intuitiv algoritme opdele og erobre. Det kommer til at tage mig, hvor mange flere trin næste år at finde nogen lide Mike Smith? Publikum: One. David J. MALAN: Der er kun én. Og de kan firedoble det, er det kommer til at tage mig blot to flere trin og så videre. Og så dette er bevis på bare hvordan nogle omhyggelig design og nogle forståelse for, hvad Deres input er kan gøre det endnu bedre. Nu er vi snyder en lidt i den forstand at vi udnytte en antagelse. Hvad er min antagelse om vores telefonbog der tillod mig at dele og erobre i denne intuitive og stadig korrekt måde? Publikum: [uhørligt] David J. MALAN: Ja. Så det blev bestilt. Det blev ordnet alfabetisk ved telefonbogen selskab. Hvis det var i tilfældig rækkefølge, som ville være et helvede af en telefonbog, men det ville helt sikkert ikke egner sig til algoritmen Jeg brugte, fordi du ville aldrig bare ske på tværs af Mike Smith hvis du holdt dividere i halvdelen på denne måde tilfældigt. Så lad os nu formalisere hvad er klart intuitiv. Så noget, der hedder pseudokode, hvor vi vil begynde nogle af vores indledende problemer. Og dette er en generisk måde at beskrive en algoritme eller et edb-program, ikke ved hjælp af C eller C ++, eller Java, eller noget bestemt sprog, men blot ved hjælp af engelsk, med som ethvert menneske kan være bekendt. Og vi kunne skrive pseudokode til dette problem som følger. Trin et, afhente telefonbogen. Trin to, åben for midten af ​​telefonbogen. Trin tre, se på navnene. Trin fire, hvis Smith er blandt names-- Og nu er det en interessant konstruktion. Det er en beslutning punkt. Det er en gaffel i vejen, hvis du vil en gren, så at sige. Så jeg har tænkt mig at indrykke blot ved konvention step-- ikke five-- som er at sige, at jeg ringer til Mike. Så denne indrykning, helt vilkårlig menneskelig konvention, men det er betød blot at formidle semantisk at hvis Smith er blandt navnene, så skal jeg ringe til Mike. I mellemtiden i trin seks, varsel at indrykningen er væk. Så ellers er den anden gaffel i vej, den anden vej, jeg vil kunne rejse. Så ellers hvis Smith er tidligere i bogen, hvad er mit næste skridt sandsynligvis kommer til at være her? Publikum: Du går til venstre side. David J. MALAN: Ja, så gå til den venstre halvdel af telefonbogen. Smid den højre halvdel, hvis Smith er tidligere i bogen. Så åben til midten af den venstre halvdel af bogen. Og derefter trin otte, gå til linje tre. Og det er en nysgerrig løkke jeg overtalelse, en rekursion så at sige. Men mere om det i fremtiden. Jeg bruger min samme algoritme, min samme pseudokode, at løse det samme problem igen fordi det eneste, der er ændret er størrelsen af ​​problemet, ikke mit mål, og ikke den person Jeg leder efter. Så jeg kan genbruge den algoritme at jeg allerede har defineret. Ellers hvis Smith er senere i book-- du måske guess-- åben til midten af højre halvdel af bogen. Og igen, gå til linje tre. Else-- hvad er den sidste linje i dette program vil være? Hvis han ikke er blandt de navne på den side, jeg er på, hvis han ikke er tidligere i bogen, og han er ikke senere i bogen, hvad gør jeg ved er sandt om Mike Smith nu? Publikum: Han er ikke i bogen. David J. MALAN: Han er ikke i bogen. Så det bedste jeg kan gøre er bare give op og stoppe dette program. Okay. Så på dette punkt, så lad os tage et hurtig rundtur til nogle af, hvad der venter. Og i virkeligheden, jeg sluttede her af en række CS50 personale. Hvis disse folk kunne alle slutte mig op her på scenen. [Applaus] Mind dig, dette er kun en delmængde af CS50 personale, da vi hvert år har næsten 100 medarbejdere medlemmer i roller kursus assistenter, undervisning medmennesker, og meget mere. Kom op. Så de vil slutte sig til os her akavet for bare et øjeblik som vi giver en hurtig rundvisning i hvad bør du forvente her i løbet. Så først og fremmest har vi SAT / UNS som bedømmelsen mulighed i kurset. Dette menes bevidst at være en mulighed, hvorved hvis du er en smule urolig ved at være i kurset, og du behøver frygte failure-- selvom ærligt fiasko betyder såre din GPA, at få en B og ikke en A-- der er præcis, hvad, i hvert fald for en gateway kursus som CS50 og andre introduktionskurser, denne klassificering indstilling er beregnet til at tillade. Jeg helhjertet opfordre students-- især hvis den fence-- at starte kursus SAT / UNS, selv forblive SAT / UNS. Men du kan helt sikkert skifte til et brev klasse af den femte mandag i udtrykket. Helt ærligt, tilbage, når jeg var en freshman i 1995, Jeg selv ikke selv tage CS50 fordi jeg ikke komme op den frækhed til rent faktisk at sætte sine ben i klasseværelset. Det virkede et domæne alt for uvant for mig og virkelig kun for de af mine venner, helt ærligt, der havde været programmering da de var seks eller måske 10 år gammel. Og det var kun, fordi jeg var stand til at tage CS50 i min dag i den tilsvarende version af SAT / UNS-- bestået / ikke tilbage i day-- at selv jeg tog 50. Og en eller anden måde, er jeg her igen med jer i dag. Nu mellemtiden hvad du ellers skal huske på omkring 50 er samtidig tilmelding. I modsætning til rygter om, at du måske har hørt, De kan faktisk samtidig tilmelde dig i CS50 og en anden klasse, mødes på den samme eller en vis overlapning tid som CS50 forelæsninger lige her. Se pensum for oplysningerne af gennemførelsen heraf. Forelæsninger, i mellemtiden, i modsætning til hvad der er officielt i kataloget, vil generelt kun mødes til blot en time. Til tider kan vi køre lidt lang. Men husk på, at det mål i CS50 foredrag er at give dig en begrebsmæssig oversigt, forhåbentlig nogle demonstrationer, måske endda nogle foræring, af, hvad der venter for ugen efter. Og så i foredrag, vil vi udforske disse emner og eksempler sammen, bringe de studerende op på scenen, og personale op på scenen så ofte som vi kan, for blot et par timer hver uge. Sektioner, i mellemtiden, vil være tilbydes af disse folk her-- mange af dem undervise medmennesker, nogle af dem naturligvis assistants-- vilje ske ugentligt. Og hvad er nøglen til at holde i tankerne er, at vi behøver have-- ikke ulig First Nætter, musikken klasse-- forskellige spor af sektioner til studerende mindre behagelig, mere komfortabel, og et sted i mellem. Og helt ærligt, du vide, hvis du er mindre komfortabel. Og du sikkert vide, hvis du er mere komfortabel. Og hvis du ikke er helt sikker på, du er definition et sted i mellem. Så når det drejer sig tid til sektion i en uge eller deromkring, pr pensum, Vi vil bede dig om, at spørgsmål. Og du kan selv vælge Baseret på din egen komfort niveau og være med students-- være med grøn dots-- samme komfort niveau til dig. I mellemtiden har vi problem sæt, der vil i sidste ende definere din oplevelse i dette kursus. De er tilbudt typisk i flere udgaver. En standard udgave, som vi forventer de fleste hver elev i løbet at tackle men også en såkaldt hacker udgave der tilbyder ingen form for ekstra kredit direkte men virkelig håneret at sige, at du har forsøgt og tackles kursets hacker udgaver som nærmer lignende materiale men ud fra et mere sofistikeret vinkel. Hvad tilbyder vi for standard udgave, til, igen, en super flertal af de studerende, er ikke kun gå-through, som er videoer ledet af kursets personale der virkelig gå dig gennem kursets problemer og mulige design implementeringer. Og vi har også efter Faktisk tilbyder postmortems, hvorved hvis du spekulerer på hvordan du kunne have eller burde have løst nogle problem, lærergruppen vil lede dig gennem dem på video samt. I mellemtiden, hvad der venter også er fem sene dage og det faktum, at vi vil slippe din laveste problem sæt score. Vi bestemt værdsætter i bytte til arbejdsbyrden at 50 forventer af dig, får livet på den måde tider, hvis ikke fem gange. Og så dette vil give dig en smule fleksibilitet, strækker din deadline fra, siger, en Torsdag middag til en fredag ​​ved middagstid. Se pensum for detaljer gennemførelse. Nu, hvad der nu venter? Og det er kun forekommende for mig nu bare, hvor lang tid Jeg har jer stå her på scenen. [Latter] David J. MALAN: Men vi vil komme til de klimatiske færdig inden længe. Så hvad venter i form af problemet sæt? Tja, måske en teaser af hvad vi alle gjorde sidste år med dine forgængere. I det første problem sæt sidste år introducerede vi Scratch, en grafisk programmeringssprog, lader dig programmere bogstaveligt talt ved trække og slippe puslespilsbrikker, som disse, der er minder om konstruktionerne vil se blot en uge Derfor, når vi skifter til en mere traditionel sprog, der er kendt som C. Sidste år vi fortsatte på dette problem sæt, involverer for kryptografi, scrambling af oplysninger at holde det fra statslige eller venner ' øjne, som du ikke ønsker at se det. Kodet i her er der en besked, som snart du vil være i stand til at dekryptere eller de-kapløbet. Breakout var et problem sat sidste år, hvor du bruge disse nyfundne programmering færdigheder til rent faktisk at gennemføre et spil, wherein-- som du måske husker fra childhood-- målet var at bash klodser, der er på toppen af ​​skærmen her, akkumulering en score undervejs, og gennemføre dine egne algoritmer med denne løsning i sidste ende lader dig spille spillet. I mellemtiden, senere i semester, vil vi give dig en ordbog over 143.091 engelske ord. Og du vil blive udfordret til at skrive et program, der stave kontrol, dokumenter ved lastning, at mange ord i hukommelsen så effektivt som muligt. Generelt grubetæring dig mod dine klassekammerater hvis du vælger ind i lidt af en udfordring i pointtavlen for at se, hvem der kan bruge færrest sekunders køretid, og færrest af megabyte hukommelse, og faktisk finjustere dine programmer at være utrolig ressourceeffektiv ikke bare tid. Sidste år også, så vi i slutningen af semestret på web programmering. Og ja, vi vil gøre det igen denne år med flere problemet sæt, introducere dig til de teknikker og den tankegang, som du kan anvende disse programmeringssprog kvalifikationer til hjemmesider, dynamiske hjemmesider, hjemmesider, der faktisk løse problemer, og opfører sig anderledes og ikke blot er statiske websteder med statisk information. Det endelige projekt i sidste ende vil definere, selv om, klimaks af kurset for studerende, hvor vil du blive udfordret til at implementere mest noget af interesse til dig, så længe det på en måde trækker på kursets lektioner. Og som du så i video i starten, vil vi afslutte semestret med CS50 hackathon, som hvis uvant, vil begynde på 7:00 en nat og slutter kl 7:00 næste morgen. Omkring 09:00, vil vi orden i første middag. Omkring 01:00, vil vi orden i anden middag. Og hvis du stadig stående på 5:00 AM, vi vil shuttle bus du til IHOP til morgenmad. Den CS50 Fair, i mellemtiden, er en begivenhed hvortil 2.000 plus fakultet, studerende, og personale fra hele campus vil kommer til at se dine resultater i løbet, og den endelige projekter og kreationer som du opretter på din bærbare, desktops, eller måske endda pærer. I mellemtiden, kontortid og støttestrukturen. Og nu ville det har været en bedre tid til at bringe dig alle op. Kontortid vil finde sted fire nætter en uge til flere timer hver nat med generelt 20 til 30 i den kursus personale på told på én gang at give dig med intim en-til-én muligheder for støtte med kursets problemet sæt. Vejledning også vil være til rådighed, navnlig for studerende mindre comfortable-- eller tør sige mindst comfortable-- for hvem kontortid er ikke den mest nærende miljø og er bestemt ikke mest stress-fri. Især når deadlines presning, vil vi proaktivt parre dig selv med et medlem af personalet til at arbejde med på nogle normale skema som dine behov og deres tidsplan tillader. Og personale. Tillad mig at introducere Davon, Rob, og Gabriel, dette års hoveder. Hvis du vil hver gerne sige-- [Applaus] --a ord. [Applaus] Davon herovre er den kursus manager, som betyder i sin fuld tid rolle han hjælper med udførelsen og logistik i CS50. Davon: Ja, hej, gutter. Du vil se en masse til mig på kontortid. Jeg vil undervise sektioner. Og hvis du skyder emails forude, Jeg vil sandsynligvis reagerer. Så jeg vil se masser af jer alle semester. Og velkommen til CS50. David J. MALAN: Og nu Gabriel, som selv var bare en freshman sidste år, men i de seneste par år har været i drift sin egen version af CS50 i Brasilien, hvor han hentede alle kursets content-- hvilket er klart at være filmet og lagt online-- så han kunne oversætte det til Portugisisk og derefter undervise mere end 100 af sine klassekammerater over løbet af et par år, undervisning i sit modersmål kursets pensum. GABRIEL: Hej. [Applaus] GABRIEL: Hej, jeg er Gabriel. Jeg leder TF af kurset. Og jeg håber, du vil elske CS50. Dette er CS50. David J. MALAN: Nu til Rob. Åh, du ønsker introduktion? ROB: Nej, jeg ved det ikke. [Latter] David J. MALAN: Og Rob Boden. [Latter] ROB: Hej, jeg er Rob. Dette er mit femte år involveret med kurset. Hvert år, det er bare en bedre og bedre klasse, så du fyre er klart kommer til at være awesome. Jeg håber I alle har det sjovt med det. Jeg har tænkt mig at have det sjovt med det. Så se dig omkring. David J. MALAN: Og tid vil ikke tillade os-- [Applaus] Tiden vil ikke tillade os at indføre alle på scenen og alle deres kolleger der er shopping klasser i dag. Men tillad mig at introducere Belinda og CS50 Puzzle Dag, der venter det kommende Lørdag, som er den første af de kursets begivenheder i større målestok. Denne ene i særdeleshed betydet at hamre hjem det punkt at datalogi er i sidste ende ikke om programmering, men snarere om problemløsning mere generelt. Og puslespil Day, som du vil se, vil bringe dig og dine klassekammerater together-- Vi håber, at denne lørdag. BELINDA: OK. Hej, gutter. Så tak. Så som vores hæderkronede kaptajn sagde mit navn er Belinda. Jeg er en sophomore på Quincy House. Jeg, ligesom du fyre tog CS50 sidste år, virkelig elskede det. Jeg har en svaghed for du fyre i tredje række. Og jeg er stolt af at sige, jeg er nu i et fast forhold med CS50 [uhørligt]. OK. Det var min halt version af en vittighed. Anyway, så bevæger sig på, blot ønskede at invitere jer alle til i-lab, eller HBS bistader. Vi kommer til at have Puzzle Dag 12:00 til 03:00. Og det er en stor chance for dig fyrene til at opfylde dine kolleger CS venner, løse nogle ikke-CS puslespil, ligesom kaptajn nævnt, og også spise nogle gratis mad, tjene nogle awesome præmier, ligesom gavekort, $ 75 per person, og also-- hvad var det? Wii U eller noget? Wii U? Ja. For vores tombola. Awesome. Så jeg vil holde sig omkring efter klasse. Og hvis du fyre har nogen spørgsmål, så lad mig det vide. David J. MALAN: Og du vil se, ud dette er der ikke noget at gøre i dag. Det første problem sæt vil gå ud fredag. Men at bringe os hjem i dag, vil jeg gerne introducere dig til specielt det ene mere medlem af personalet, Colton Ogden her, hvis hænder er nu beskyttet over dig med denne MIDI controller at hamre hjem punktet yderligere at datalogi, også, har anvendelighed langt ud over teknik og STEM og datalogi selv, strækker sig endda til sådanne domæner som musik. Colton har venligt offered-- jeg troede en af ​​dem skulle indstille fokus. Andrew, hvis vi kunne tilkalde fokus herovre for bare et øjeblik. Hvad Colton har gjort i forvejen er program denne enhed, denne pude af knapper at du ser afbilledet op her, som en MIDI controller, hvorved hver af disse knapper er tilsluttet til en bestemt musikalsk tone eller en lyd, mere generelt en optagelse, sådan at ved at spille mønstre af disse knapper, meget gerne mønstre af bits, kan repræsentere andre højere koncepter plan. Vil han være i stand til i sidste ende at tage os hjemme her i dag? Uden videre, hvis vi kunne dæmpe lyset, og tænde for skærmen bag Colton. Publikum: Woo! David J. MALAN: Dette er CS50. [Musik spiller] [Applaus] Det er det for CS50. Vi vil se dig fredag. Nogle kage venter dig i tværskib. [Musik spiller]