[Speel van musiek] [Applous] David J. Malan Dit is CS50, Harvard Universiteit se bekendstelling die intellektuele ondernemings van rekenaarwetenskap en die kuns van die ontwikkeling. Nou as jy een van diegene wat elke jaar hier sit met 'n bietjie van die senuwees in jou gedagtes, soos dat jy dink nie jy hier hoort, jy dink dat die meeste iemand sit rondom jou weet baie meer as wat jy, is inderdaad meer gemaklik as jy op die rekenaar wetenskap of rekenaars meer in die algemeen, besef dat 78% van die studente wat nou neem CS50 het geen vorige ervaring. Trouens, daar is 100 punte daar op die skerm, 78 van wat soliede groen, wat beteken dat jy, As jy onder die demografiese, is in 'n baie goeie geselskap hier op uit. En as jy in plaas onder die 22% van die CS50 studente wat wel doen het vorige ondervinding, hetsy in hoërskool of 'n ander program, besef dat jy ook sal uitgedaag word in die kursus. Nie net het ons verskillende spore vir studente minder gemaklik en meer gemaklik gelyk in afdelings, ons ook sogenaamde hacker uitgawes van die meeste probleem sit dat sal studente daag met die bykomende ondervinding soortgelyke materiaal te verken maar van 'n meer gesofistikeerde perspektief. Maar wat is die rekenaar wetenskap? Wel, uiteindelik, wat gaan saak as jy verken hierdie gebied is nie soveel waar jy eindig relatief tot jou klasmaats, Maar waar jy jouself uiteindelik in week 12 versus waar jy hier begin in week nul. Nou rekenaar goed science--, laat noem dit die wetenskap van computation-- waar berekening is regtig net 'n fancy manier om te sê, die neem van 'n paar insette, vervaardiging van sommige uitvoer, en doen deur die loop van algoritmes, stelle van instruksies vir die oplossing 'n probleem op die insette ten einde 'n uitset te produseer of oplossing waarin jy belangstel. So het ons onlangs gehad geleentheid om te reis Kalifornië te ontmoet met 'n alumna. Haar naam is Susan Susan. En sy wil om te praat aan jou hier op video om te getuig net hoe toepassing selfs net 'n voorsmakie van die rekenaar wetenskap aan die inleidende vlak kan wees. Selfs as jy nie gaan nie op na te streef rekenaarwetenskap as 'n veld, of selfs ingenieurswese, of steel meer algemeen, jy sal sien, in werklikheid, hoe om 'n sekere Natuurlik haar lewe so beïnvloed. En sy net het dit toe sy was 'n senior hier by Harvard College. As ons die ligte vir Susan kon verdof. Susan Susan: Hello, world. Ek is Susan Susan. Ek is die hoof uitvoerende beampte van YouTube. En ek het CS50 toe ek 'n senior by Harvard in 1990. Ek was eintlik 'n geskiedenis en literatuur groot. En my junior somer, Ek het besef dat ek dalk wou iets om te leer oor rekenaars. En so, ek het terug gekom. Ek het CS50. Dit was moeilik, maar dit was die mees ongelooflike klas ek geneem het. Dit verander hoe ek dink oor alles. En wanneer ek gegradueer van Harvard in 1990, het ek na Silicon Valley. En ek het 'n werk. En ek het gewerk in tegnologie sedertdien. David J. Malan Nou wat Susan het nie in hierdie video praat, dat dit eintlik in haar garage dat Google self was gestig deur Larry en Sergey. Nou het ons ook bereik uit na ons vriende by code.org, 'n organisasie wat oor die afgelope jaar was om mense veral opgewonde oor rekenaarwetenskap en ontwikkeling, in die besonder. Maar dit is die moeite werd om daarop te let dat ontwikkeling is nie rekenaarwetenskap per se. Rekenaarwetenskap is nie programmering. Eerder ontwikkeling is net 'n tool-- waarmee almal van julle sal al te goed wees vertroud met semester se end-- sodanig dat jy nie kan aansoek doen net om toekomstige kursusse in CS maar alles velde waaruit jy kom, in die geesteswetenskappe, sosiale wetenskappe, natuurlike wetenskap, of die wil. Inderdaad, toelaat dat 'n paar ander alumni en hul kollegas te praat van die toepaslikheid van die veld wat wag. Bill Gates: Ek was 13 toe ek die eerste keer toegang tot 'n rekenaar. JACK DORSEY: My ouers gekoop het vir my 'n Macintosh in 1984 Toe ek agt jaar oud was. Mark Zuckerberg: Ek was in die sesde graad. Spreker 1: Ek het geleer om te kode in die kollege. Ruchi SANGHVI: eerste jaar, in die eerste semester, Inleiding tot Rekenaarwetenskap. Bill Gates: Ek het 'n program wat gespeel tic-tac-toe. DREW HOUSTON: Ek dink dit was mooi nederige begin. Ek dink die eerste program Ek het gevra dinge soos, Wat is jou gunsteling kleur? Of hoe oud is jy? ELENA SILENOK: Ek het eers geleer hoe om 'n groen sirkel te maak en 'n rooi vierkant op die skerm verskyn. GABE NEWELL: Die eerste tyd wat ek eintlik moes iets kom en sê hallo, wêreld. En ek het 'n rekenaar doen. Dit was net verstommend. Mark Zuckerberg: Leer hoe om program nie begin as wil leer al rekenaarwetenskap of probeer om dit te bemeester dissipline of iets soos dit. Dit het net begin af, want ek wou dit 'n eenvoudige ding om te doen. Ek wou iets te maak wat was groot pret vir myself en my susters. En ek het hierdie klein program. En dan basies net bygevoeg 'n bietjie om dit te. En dan wanneer ek nodig het iets nuuts om te leer, Ek kyk dit op, óf in 'n boek of op die internet, en toe 'n bietjie om dit te. DREW HOUSTON: Dit is regtig nie in teenstelling met 'n instrument speel of iets of speel 'n sport. David J. Malan Alle regte. So laat ons nou eintlik duik in 'n bietjie dieper. Wat is hierdie insette en uitsette dat ons hier praat? So hoe oor iets eenvoudig? Jy weet waarskynlik, selfs al het jy geen kennis van rekenaarwetenskap ookal, dat rekenaars of ander manier gebruik en verstaan ​​net nulle en ene. Maar hoe kan dit moontlik gegee word hoe veel vandag se desktops en skootrekenaars gelyk kan doen nie? Die DNA van die dag, die enigste alfabet dat hulle verstaan is 'n nul of 'n een. Wel, oorweeg dit. Ons, die mens, is geneig om die gebruik desimale stelsel. "Desember" beteken 10. En dit is 10, want ons het 10 syfers, 0 tot nege. Nou rekenaars, daarenteen, geneig binêre te gebruik. "Bi" beteken twee. So is hulle geneig om net nul en een gebruik. Maar dit blyk dat selfs net met nulle en ene, wat is 'n groot genoeg alfabet waarmee die meeste te verteenwoordig enige stuk data wat jy wil, of dit 'n nommer, of dit nou 'n brief, of dit nou 'n grafiese of video op die skerm. Oorweeg, byvoorbeeld, hoe ons mense tipies interpreteer hierdie getal hier. Dit is net drie syfers, een, twee, drie. Maar ons weet hierdie getal ingebore nou as 123. Maar hoekom is dit? Wel, as jy dink terug miskien graad skool, jy waarskynlik geleer om te dink aan hierdie getalle as in kolomme, waar die een is in die honderde plek, die twee is in die tien plek, en die drie is in dié plek. Hoekom is dit werklik nuttig? Wel, dink oor die super eenvoudige rekenkundige dat ons almal is doen vir die jaar. Effektief, as jy het ' 'n een in die honderde plek, jy die vinnige wiskunde 100 keer 1 plus 10 keer 2-- omdat twee is in die tien place-- plus 1 keer 3-- want drie is in dié plek. So, natuurlik, as ons eintlik hierdie vermenigvuldig, wat ons werklik verteenwoordig met hierdie pattern-- een twee three-- is 100 plus 20 plus 3, wat natuurlik, is 123. Nou binêre, en rekenaars regtig, fundamenteel dieselfde taal praat wat ons doen. Hulle het net 'n kleiner alfabet. So rekenaars net nulle en kinders tot hulle beskikking. So, terwyl ons mense in wese magte van 10 in elk van hierdie places-- 10 tot die nul, 10 aan die een, tien aan die twee, gee jou 110 en 100 onderskeidelik. Omdat rekenaars slegs twee waardes hulle kan verstaan, nul en een, hulle verskillende waardes te gebruik in hierdie kolomme, een, twee, vier. En as ons aan die gang gehou, agt, 16, 32, 64, en so meer. Maar die patroon en die mentaliteit is presies dieselfde. So deur hierdie logika, enigiemand, hoe sou Ek gaan verteenwoordig die aantal een in binêre? As jy nog nooit eens daaraan gedink dit voor, wat jou ingewande sê? Publiek: Een. David J. Malan Een. Presies. Ons moet net 'n een in die kinders plaasvind, omdat die nulle voldoende om ons te gee nie 'n vier of 'n twee. So een keer een is gelyk aan een. Nou dinge 'n bietjie interessant. As ek wil verteenwoordig in Binêre die aantal two-- maar weer, selfs as jy nog nooit hierdie taal voor gepraat, hoe kan ons verteenwoordig in binêre die waarde wat ons mense ken as twee? Zero 'n nul. Net die een in die kolom wat jy dit wil hê. Nou is dit redelik om maklik waarskynlik nou. So as ek wil three-- te verteenwoordig daar is geen drie se kolom. So, weer, ek kan nou hierdie waardes voeg saam deur 'n mens hier. So 2 keer 1 plus 1 keer 1 is, natuurlik, 3. Nou dinge 'n bietjie pret in dat die kinders raak nou nulle. En vier voor te stel, kry ek hierdie. En as ons inkrementeer stadig here-- dat vyf sou wees. Dit sou ses. Dit sou sewe. Maar nou lyk asof ek 'n hardloop in 'n probleem. Hoe kan ek gaan verteenwoordig eight-- sou die volgende waarde wees. Ja, so ons moet 'n nuwe stukkies. En, inderdaad, as jy het hoor hierdie frase voor, stukkies, dis net kort vir binêre syfer, nul of een. En so het ek gebeur te verteenwoordig slegs drie sulke stukkies hier. Maar as ek 'n manier van die stoor nie drie verskillende stukkies, maar vier, ja, ek kan verteenwoordig agt, en dan nege, en dan 10, en selfs hoër en hoër. Maar wat dan roep in die vraag hoe ons kan gaan oor hierdie verteenwoordig dinge in die eerste plek. Dit is een ding om te trek hulle hier op 'n skyfie, maar hoe hulle verteenwoordig jy nie as jy 'n meganiese toestel? Wat is 'n rekenaar te doen om verteenwoordig die insette en uitsette wat fundamenteel definieer berekening aan die einde van die dag? Wel, wat oor iets super eenvoudige soos hierdie? Dit is net 'n gloeilamp. En ek kan dit veroorsaak gloeilamp om te gaan op deur die draai sommige elektrisiteit op en om elektrone om deur te vloei, wat verander sy staat of sy waarde, om so te praat. Byvoorbeeld, dit is 'n ou skool lessenaar lamp hier met een so 'n gloeilamp binnekant van dit. En nou is dit nie regtig doen iets nuttig. Maar so gou as ek prop dit in 'n stopcontact en gebruik dan hierdie switch-- of ons kan selfs noem dit 'n transistor of dink dat dit as such-- Ek kan nou stel óf hierdie waarde, waar die gloeilamp se natuurlik af of die waarde. Hierdie waarde of hierdie waarde. Hierdie waarde en so meer. So binnekant van 'n rekenaar, vermoedelik, is veel kleiner stukke van die hardeware, maar dat aan die einde van die dag eenvoudig gebruik electricity-- miskien vang it-- en dan óf iets hou op of hou iets af. Natuurlik, dit is nie veral interessant om te doen met net 'n enkele gloeilamp. Trouens, hoe hoog kan ek tel in binêre met hierdie lessenaar lamp hier? Publiek: Een. David J. Malan Een, reg? Ek wil graag meer lessenaar lampe as ek eintlik wil hoër te tel. Maar ons kan beter as dit doen. Omdat die gloeilampe wat ons sit het in hierdie dinge is eintlik liefhebber gloeilampe as weleer sou toelaat. En hulle is eintlik netwerk gloeilampe. En trosse van maatskappye maak hierdie dinge deesdae. Maar dit blyk dat hierdie een in die besonder kom met 'n funksie waardeur jy die kleure kan verander. So byvoorbeeld, as jy versier jou koshuiskamer met 'n paar van hierdie lig bolle, afhangende van jou bui, afhangende van wat kom in, afhangende van die weer, afhangende van die tyd van die dag, kan jy eintlik verander die kleure van die gloeilampe in jou kamer. En dit is omdat hierdie lig gloeilampe en ander soos dit het, wat is genoem 'n API, 'n aansoek programming interface, wat is 'n onderwerp wat jy sal goed wees vertroud is met deur semester se einde. En dit is net 'n fancy, kriptiese manier om te sê, jy kan hierdie lig program bolle jou bied om te doen. Jy kan hulle boodskappe stuur net soos jy, 'n mens, kan 'n boodskap stuur na 'n web bediener sê, gee my vandag se nuus of gee my e-pos. Jy kan stuur vir meer arcane boodskappe op hierdie gloeilampe om te sê, draai op en af. Maar dit is nie al wat interessant. Jy kan sê, draai op die rooi, draai op die groen, draai op blou, almal met dieselfde gloeilamp. En jy kan selfs met 'n bietjie meer vaardig, sê, draai om jouself te blou wanneer dit is 'n somber dag buite, byvoorbeeld. Dit kan eintlik lap in 'n weer API en vind uit wat die weer is, of die tyd van die dag, of sodanige ander snellers. So, in die feit dat twee van CS50 se eie personeel, Dan Bradley en Ansel Duff hier, vriendelik verkry ons 'n hele klomp van die gloeilampe. En hulle CS50 se gebou eerste binêre bolle, waar ons verteenwoordig here-- met hierdie speels bietjie magnets-- die verskillende plekhouers ons verwys na net 'n bietjie gelede. So manier hier is die kinders plek, twee, vier. En ons het nie hoër as dié sien. Maar, natuurlik, hulle is magte van twee. Agt, 16, 32, 64, en 128. So as ek wil nou 'n bietjie liefhebber as die gebruik van hierdie ou skool skakel, Ek het hier op hierdie iPad 'n super eenvoudige koppelvlak dat Dan Bradley, 'n voormalige student en nou onderrig mede, geprogrammeerde behulp van 'n HTML en JavaScript, wat is opmaak en ontwikkeling tale onderskeidelik. En jy kan waarskynlik see-- selfs in die back-- daar is 'n groot plus en 'n groot minus, plus een knoppie vir elk van hierdie bolle. En wat dit gaan my toe te laat om doen is, byvoorbeeld, op die plus en nou verteenwoordig, van Natuurlik, watter getal? Een. En ek kan dit weer getref. Twee. Drie. Vier. Vyf. Ses. Sewe. En hier kry ons dat roll, maar ons het 'n vierde bietjie hierdie tyd, So nou het ons agt. So kan ons dit doen vir 'n geruime tyd. In werklikheid, as 'n eenkant, hoe hoog kan ons reken? Enigiemand? Publiek: 255. David J. Malan 255, reg? Moenie te veel bekommerd wees oor die wiskunde vir nou, maar dit is 'n mooi ordentlike nommer. Maar dit eintlik net gebind hoeveel stukkies inligting, soos 'n brief of 'n grafiese dat ons kan verteenwoordig. Maar maak nie saak vir nou. Ek gaan om voort te gaan en draai hulle almal af. En as ek kon, sou ek graag om te vra vir 'n vrywilliger, ons eerste volunteer-- O, hello-- op die verhoog. Die vangs is wat jy hoef te wees gemaklik verskyn, as jy duidelik is in die voorkant van al jou klasmaats, sowel as op die internet. En laat my kyk 'n bietjie verder as the-- hoe oor hier in die wit hemp? En oorhandig het. Kom op. Wat is jou naam? Publiek: Jackie. David J. Malan Jackie. Jackie, kom op. So, wat is daar ook op hierdie iPad is 'n knoppie genoem Game af. En dit spel af is gaan my toelaat om insette vooraf 'n bepaalde desimale nommer, die getalle wat ons mense is vertroud is met. En dan sal jy uitgedaag word hier om die knoppies te gebruik op die top-- een vir elk van hierdie bulbs-- om werklik uit te vind die patroon van die gloeilampe dat die aantal in die vraag. En ek is jammer, wat was jou naam nou weer? Publiek: Jackie. David J. Malan Jackie. Alle regte. Goed om jou te ontmoet. So laat my voor en program in te gaan vir die wêreld die nommer 15 te sien. Ons sal dit klein hou op die eerste hier. En ek gaan om te gaan in spel af. En ek gaan om te spesifiseer, gee ons die nommer 15. OK. En nou met almal watching-- indien jy wil miskien staan ​​hierdie manier, want dit sal in lyn up-- voort te gaan en wissel die agt knoppies langs die top die bolle om te draai of af soos jy goeddink. Publiek: OK. David J. Malan En geen bedrog deur slaan plus 15 keer. O, ons gaan om dit te doen. Publiek: O, wag. Ek is so jammer. David J. Malan Jy kan ook draai die gloeilampe op individueel met elkeen van hierdie knoppies op die top. Publiek: O, OK. So sal dit wees like-- David J. Malan OK. So nou het ons agt. So laat ons breek vir die gehoor hier betrokke te raak. Watter getal is Jackie tans verteenwoordig? 11. So ons is amper daar. En 'n uitstekende. So het ons ons eerste wenner. Baie geluk. En ons het gedink ons ​​wil ' n paar pragtige geskenke. As jy wil een so te wees koshuiskamer hier op kampus, kan jy jouself 'n finale projek gebruik nou hierdie API, te danke aan Jackie. So now-- [Applous] --if ons kon, een soos om van hierdie. O, nou almal wil 'n paar gloeilampe. Vir die sogenaamde hacker uitgawe, ons gaan om dit te oprit a-- o, ja, ontwykend. Ek dink jy kom nou as jou hand is om af te gaan. Wat is jou naam? Publiek: Alex. David J. Malan Alex, kom hier. So vir Alex, gaan ons program in 'n effens groter nommer. Miskien in orde is. Die nommer 50. Publiek: OK. David J. Malan Maar, soos Ek said-- en jy kan wil om hier te staan ​​sodat dat die knoppies line-up as jy wil expect-- maar ek het noem dit die hacker uitgawe. So-- baie geluk! [Gelag] Jy sal in staat wees om om te draai hulle af as you-- OK. Uitstekend. Wonderlik. Baie geluk. [Applous] Ek dink ek moet betaal. Baie geluk aan Alex sowel. OK. So die uiteindelike afhaal hier is hopelik, eerlik, die simplicity-- die eenvoud waarmee jy kan 'n paar mooi lig kry bolle, blykbaar in [onhoorbaar]. Maar hulle verteenwoordig, uiteindelik dieselfde idees waarmee ons mense is reeds al te bekend. So wat kan die volgende stap in die vordering probeer om iets te doen interessant met data en verteenwoordig insette wat nie net getalle nie, maar is dalk letters of meer? Wel, dit blyk dat die rekenaar wêreld, vir baie jare, bloot 'n arbitrêre, maar 'n aangenome konsekwent standaard wat kaarte nommers letters van die alfabet. Byvoorbeeld, hier is 'n uittreksel uit die kartering. Dit is bekend Ascii. A-S-C-ek-ek. En dit is net 'n tabel wat kaarte hoofletters letters-- in hierdie case-- na desimale getalle. Maar wat is die implikasie? Wel, as jy eintlik wil stel iets soos 'n e-pos of teks op 'n webblad, jy natuurlik wil om te wys die menslike letters van die alfabet, nie-nommers. So, afhangende van die konteks van die program dat 'n gebruiker is te gebruik, al is dit 'n webblaaier of e-pos kliënt, getalle kan seker wees geïnterpreteer as letters. Dit is om te sê, patrone van stukkies kan maklik vertolk word as letters. En ja, wat ons kan is die letter A wese verteenwoordig as 65, B verteenwoordig word as 66. So as ons 'n super kort woord, soos hi, wat 'n rekenaar sou uiteindelik winkel in desimale maar regtig in binêre, behulp van 'n reeks van stukkies, gebruik te maak 'n bietjie van elektrisiteit in een of ander manier, sou wees om die twee getalle 72 en 73. Maar die patroon van die stukkies wat verteenwoordig daardie waardes. So hierdie is dan hoe ons dit kan verteenwoordig ons insette en uitsette. En is dit voldoende om te sê, ons kan doen meer kompleks vertoë uiteindelik met dinge soos beelde, video's, musiek, en meer soos ons sal later hierdie kwartaal sien. Sodat net laat dan algoritmes, hierdie stelle instruksies waarmee ons die oplossing van werklike probleme. Ons is verby in insette te algoritmes. En die algoritmes is die vervaardiging van uitgange, hopelik korrek uitgange en hopelik ook doeltreffend versamel uitgange. Met ander woorde, dit is een ding iets om te korrek te implementeer. Dit is 'n ander ding om te implementeer iets goed of doeltreffend. Byvoorbeeld, een demonstrasie dat ons lief in die kursus is hierdie een. Maar hierdie dinge is om toenemend moeilik om te vind. Maar dit is inderdaad 'n ou skool telefoon boek, binnekant van wat is 1000 plus bladsye van name en telefoonnommers. En as ek wou om te kyk iemand in hierdie telefoon boek, Ek kon net nie 'n baie naïef algoritme. Ek kon oopmaak om die eerste bladsy, en Ek kan begin om te kyk vir, sê, iemand vernoem Mike Smith. En as hy nie op die eerste bladsy, ek vorder na die tweede, en dan na die derde, en dan die vierde, en so meer, totdat ek uiteindelik vind Mike Smith. Nou is dat algoritme korrek? Gehoor: Ja. David J. Malan Ja. As hy daar, ek sal uiteindelik vind hom. Maar dit is waarskynlik nie baie doeltreffende, beslis nie 'n vinnige, want my God, waarom word ek mors my tyd daarby deur al hierdie bladsye wanneer ek kon beslis nie hierdie fisies vinniger? Wel, 'n effense optimalisering, so te praat, dalk nie een bladsy op 'n tyd wees, maar twee, vier, ses, agt, 10. Nog korrek? GEHOOR: Nee David J. Malan So nie as ek vir byvoorbeeld spring oor Mike Smith. Maar so lank as wat ek terug trap een bladsy, as ek oorskiet hom miskien kan ons reg wat anders kan wees om 'n Gotcha. Maar is dit beter? Is dit vinniger? Ek bedoel, ja. Dit is letterlik twee keer so vinnig as ek dit doen twee bladsye op 'n slag. So as ek oorspronklik 1000 bladsye, nou is ek net 500 keer om te draai, nie ten volle 1000 bladsye te kry potensieel in die ergste geval aan die einde van die telefoon boek, waar iemand soos Mike Smith of iemand met 'n later naam dalk eintlik kan wees. Maar, natuurlik, ons mens beslis nie gaan word om dit te doen, beslis nie op hierdie stadium in ons lewens. Wat is 'n redelike menslike waarskynlik gaan om te doen? Publiek: Gaan reguit na the9 S se. David J. Malan Gaan reguit na die S se? Hoe gaan ek reguit na die S se? Publiek: rip dit in die helfte. David J. MALAN: Wel, daar is geen merk. So, ja, al was daar wel 'n etiket of 'n taai blad vir S, ons moet net daar spring. Maar dit is redelik onskadelike. So die beste wat ek kan doen, is ongeveer die S artikel of miskien rofweg in die middel. Maar die sleutel afhaal now-- en die aanvoeling dat jy vir geneem het verleen vir die jaar probably-- is dat dit wat nou te doen wat jy weet oor hierdie probleem? Publiek: [onhoorbaar] David J. Malan Mike Smith is sekerlik nie in hierdie helfte van die probleem omdat Smith kom nadat die middel wat ongeveer die M artikel, dit blyk te wees. So as jy dalk gesien het by Bezoeken, kan ons nou letterlik skeur hierdie probleem in die helfte. Publiek: Woo! David J. MALAN: Dit is om makliker en makliker. [Applous] Daar gaan jy. [Gelag] En nou het ek fundamenteel het dieselfde probleem, maar dit is letterlik die helfte so groot. Ek is nog steeds op soek na Mike Smith. En ek daresay, ek kan nog steeds kyk vir hom op dieselfde manier, verdeel die probleem in die helfte weer die probleem skeur weer in die helfte, wat nou laat my met 'n probleem 'n kwart van die grootte, dramaties gooi dat die helfte weg, en weer en weer herhaal hierdie proses en weer, skrams af by elke punt te sien As Mike Smith is op die betrokke bladsy. Maar as ek doen dit reg, uiteindelik gaan ek myself met net een bladsy waarop Mike Smith is as hy inderdaad in die telefoon boek. Natuurlik, ek kon nooit Mike weer bel. Maar die punt is hier dat as ons begin met 1000 bladsye, my eerste algoritme flip die bladsy, miskien 1000 times-- beslis minder, want dit is 'n naam en nie 'n Z naam nie, maar as soveel as 1000 bladsye potensieel. Tweede algoritme, hoe beter. 500 bladsye. Derde algoritme, al is, hoeveel stappe sal dit neem 'n 1000 bladsy te verdeel telefoon boek in die helfte soos wat? 10, gee of neem. So slegs deur daarby deur daardie telefoon boek, duik en 'n oorwinnaar so te sê, 10 keer, sal ek my pad af na slegs 'n enkele bladsy. En so kan ons hierdie intuïsie vang nou 'n bietjie grafies as jy net oorweeg hierdie super eenvoudige grafiek. Ons is op die x-as, of horisontale as, is die grootte van my probleem, die aantal bladsye in die telefoon boek. En rekenaar wetenskaplikes algemeen 'n beroep die grootte van 'n probleem N, waar N is net 'n paar veranderlike wat represents-- in hierdie case-- aantal bladsye. Die vertikale of y-as, hier is gaan die tyd op te los te wees, Miskien is die aantal bladsy draaie, Dalk is dit die aantal sekondes of minute, wat ookal jou eenheid van meet is. En so gaan dit rooi lyn die eerste algoritme want daar is 'n 1-1 verhouding tussen die getal bladsye en die bedrag van die tyd wat dit neem. As Verizon verdubbel die aantal bladsye in volgende jaar die telefoon boek, my loop time-- die tyd wat nodig is om uit te voer dat die eerste algorithm-- verdubbel in die ergste geval. Maar die tweede algoritme waar ek daarby deur twee, verg minder tyd vir 'n gegewe grootte probleem. So as ek dit baie bladsye here-- kennisgewing dat die geel lyn dui daarop minder tyd op te los. En inderdaad, dit verteenwoordig, ons sal sê, n oor twee. Maar wat is die vorm van die derde en finale kurwe gaan lyk? Ja, dit is inderdaad gaan ek te look-- Ek weet nie wat jy gaan om te sê. Maar laat ons sien wat jy gaan om te sê. Publiek: soos dit. David J. Malan Dit gaan lyk hierdie, 'n logaritmiese slope-- exactly-- waardeur jy hierdie nuuskierig helling. Dit is nie meer 'n reguit lyn. En wat is dwingende oor dit is dat selfs al is die grafiek word nou afgesny, jy kan ekstrapoleer in jou herinner ons dat die groen lyn is nie gaan toeneem in hoogte alles wat veel as jy verder gaan bepaal dat die horisontale as. Inderdaad, Verizon, vir Byvoorbeeld, kan verdubbel die aantal bladsye in die telefoon boek tussen hierdie jaar en volgende jaar vanaf 1000 tot 2000 bladsye, maar nie 'n groot deal. Met hierdie derde en finale, daar is 'n intuïtiewe algoritme verdeel en verower. Dit gaan my te neem hoeveel meer stappe volgende jaar om iemand te vind wil Mike Smith? Publiek: Een. David J. Malan Daar is net een. En hulle kan vier keer, dis gaan my net twee stappe te neem en so meer. En so is dit bewys van net hoe sommige versigtig ontwerp en sommige waardering vir wat u insette is selfs beter kan doen. Nou het ons verkul n bietjie in die sin dat ons gebruik te maak van 'n aanname. Wat is my aanname oor ons telefoon boek wat my toegelaat om te verdeel en oorwin in hierdie intuïtiewe en nog regte manier? Publiek: [onhoorbaar] David J. Malan Ja. So was dit bestel. Dit is analfabeet deur die telefoon boek maatskappy. As dit in enige volgorde, wat sou 'n hel van 'n telefoon boek wees, maar dit sou beslis nie leen tot die algoritme Ek gebruik nie, want jy sal nooit net gebeur oor Mike Smith As jy gehou verdeling in half in die pad deur die kans. So laat ons nou die formalisering Wat is duidelik intuïtief. So iets genoem pseudokode is waar ons sal begin om sommige van ons aanvanklike probleme. En dit is 'n generiese manier om te beskryf 'n algoritme of 'n rekenaar program, nie die gebruik van C of C ++, of Java, of enige spesifieke taal, maar net die gebruik van Engels, met wat enige mens vertroud kan wees. En ons kan die pseudokode skryf vir hierdie probleem soos volg. Stap een, haal die telefoon boek. Stap twee, oop te middel van die telefoon boek. Stap drie, kyk na die name. Stap vier, as Smith is een van names-- En nou is dit 'n interessante konstruk. Dit is 'n besluit punt. Dit is 'n vurk in die pad, as jy sal 'n tak, om so te praat. So ek gaan ingekeep net deur die konvensie step-- nie five-- wat tot sê, ek sal Mike bel. So hierdie inkeping, heeltemal arbitrêre menslike konvensie, maar dit is net bedoel semanties dra dat indien Smith is een van die name, dan moet ek Mike bel. Intussen is in stap ses, kennisgewing dat die inkeping weg. So anders is die ander vurk in die pad, die ander pad wat ek kan reis. So anders as Smith is vroeër in die boek, wat is my volgende stap waarskynlik gaan om hier te wees? Publiek: Jy gaan na die linkerkant. David J. Malan Ja, so gaan na die linker helfte van die telefoon boek. Gooi weg die regter helfte as Smith is vroeër in die boek. So oop tot in die middel van die linker helfte van die boek. En dan stap agt, gaan te reël drie. En dit is 'n snaakse lus ek is beïnvloeding, 'n rekursie so te praat. Maar meer oor dit in die toekoms. Ek gebruik my dieselfde algoritme my dieselfde pseudokode, weer dieselfde probleem op te los want die enigste ding wat verander is die omvang van die probleem, nie my doel, en nie die persoon Ek is op soek na. So ek kan die algoritme hergebruik dat ek reeds gedefinieer. Anders as Smith is later in book-- jy dalk guess-- oop tot in die middel van die regter helfte van die boek. En weer, gaan na reël drie. Else-- wat is die laaste lyn in hierdie program gaan wees? As hy nie onder die name op die bladsy is ek op, as hy nie vroeër in die boek, en hy is nie later in die boek, wat weet ek waar is oor Mike Smith nou? Publiek: Hy is nie in die boek. David J. Malan Hy is nie in die boek. Dus is die beste wat ek kan doen, is net gee en stop hierdie program. Alle regte. So op hierdie punt, laat ons 'n vinnige toer van sommige van wat wag. En in die feit, ek hier aangesluit deur 'n aantal van CS50 personeel. As hierdie mense kon al saam met my hier op die verhoog. [Applous] Mind u, dit is slegs 'n subset van CS50 personeel, aangesien elke jaar het ons byna 100 personeel lede in rolle natuurlik assistente, onderrig genote, en nog baie meer. Kom op. So sal hulle by ons aansluit hier ongemaklik vir 'n oomblik as ons gee 'n warrelwind toer van wat jy moet hier verwag in die kursus. So in die eerste plek, ons het Saterdag / UNS as die gradering opsie in die kursus. Dit is doelbewus bedoel 'n opsie waar te wees As jy 'n bietjie ongemaklik daarna om in die loop, en jy hoef nie te vrees failure-- selfs al eerlik mislukking beteken seer jou GPA, om 'n B en nie 'n A-- wat presies wat, seker vir 'n gateway kursus soos CS50 en ander inleidende kursusse hierdie gradering opsie is bedoel om voorsiening te maak. Ek stem heelhartig moedig students-- veral As daar op die fence-- die begin Natuurlik SAT / UNS, selfs bly SAT / UNS. Maar jy kan beslis oor te skakel na 'n brief graad deur die vyfde Maandag in die term. Om eerlik te wees, toe ek was 'n groentjie in 1995, Ek myself het nie eens CS50 want ek het nie die senuwee om werklik te voet stap in die klaskamer. Dit was 'n domein veels te onbekend aan my en eintlik net Vir diegene van my vriende, eerlik, wat al die programmering want hulle was van ses of miskien 10-jaar-oud. En dit was net omdat ek staat CS50 te neem in my dag in die ekwivalent weergawe van SAT / UNS-- slaag / druip terug in die day-- dat selfs ek het 50. En een of ander manier, ek is hier weer met jou vandag. Nou intussen wat jy nog moet in gedagte hou sowat 50 is gelyktydige registrasie. In teenstelling met gerugte dat jy dalk gehoor het, jy kan, in werklikheid, gelyktydig skryf in CS50 en 'n ander klas wat vergader op dieselfde of 'n oorvleueling tyd as CS50 se lesings hier. Sien die leerplan van die besonderhede van die implementering daarvan. Lesings, intussen, in teenstelling met Wat is amptelik in die katalogus, sal oor die algemeen net ontmoet vir net 'n uur. By geleentheid kan loop ons 'n bietjie lank. Maar hou in gedagte dat die doel in CS50 se lesings is om jou te voorsien met 'n konseptuele oorsig, hopelik 'n paar demonstrasies, miskien selfs 'n paar geskenke, van wat wag vir die week wat volg. En so in lesings, sal ons ondersoek daardie onderwerpe en voorbeelde saam bring studente op die verhoog, en personeel op die verhoog so dikwels as wat ons kan, vir net 'n paar uur elke week. Afdelings, intussen, sal wat aangebied word deur hierdie mense here-- baie van hulle onderrig genote, sommige van hulle natuurlik assistants-- wil weekliks gebeur. En wat is die sleutel te hou in gedagte is dat ons nie have-- nie anders as die eerste Nagte, die musiek class-- verskillende spore van artikels vir studente minder gemaklik, meer gemaklik, en iewers tussen in. En eerlik, jy weet as jy minder gemaklik. En jy waarskynlik weet of jy meer gemaklik. En as jy nie seker is, is jy per definisie iewers tussen in. So wanneer dit kom tyd om te deel in 'n week of so, volgens die leerplan, ons sal vra om die vraag. En jy kan self-kies op jou eie comfort vlak en met students-- wees met groen dots-- soortgelyke comfort vlak vir jou. Intussen het ons 'n probleem stel, wat sal uiteindelik jou ervaring in hierdie kursus te definieer. Hulle is tipies aangebied in verskeie uitgawes. 'N standaard uitgawe dat ons die meeste verwag elke student in die kursus aan te pak maar ook 'n sogenaamde hacker uitgawe wat bied geen vorm van ekstra krediet blatante maar regtig die bragging rights om te sê dat jy probeer en aangepak die kursus se hacker uitgawes wat die soortgelyke materiaal benader maar van 'n meer gesofistikeerde hoek. Wat ons bied vir die standaard uitgawe, vir, weer 'n super meerderheid van studente, is nie net loop-throughs, wat videos gelei deur personeel die kursus se wat werklik loop jy deur die Natuurlik se probleme en moontlike ontwerp implementering. En ons het ook na die Trouens, bied postmortems, waardeur as jy wonder hoe jy kan hê of moet opgelos het 'n paar probleem, die dosente sal loop jy deur diegene wat op video as well. Intussen, wat wag ook is vyf dae laat en die feit dat ons sal daal jou laagste probleem gestel telling. Ons het seker besef dat in ruil vir die werklading wat 50 word verwag van julle lewe in die pad soms, indien nie vyf keer. En so sal dit bied jy 'n bietjie van buigsaamheid, die uitbreiding van jou sperdatum van, sê, 'n Donderdag middag na 'n Vrydag middag. Sien die leerplan vir die implementering besonderhede daarvan. Nou wat nou wag? En dit is net voorkom vir my nou net hoe lank Ek het julle staan ​​hier op die verhoog. [Gelag] David J. Malan Maar ons sal kry om die klimaks afwerking voor lank. So, wat wag in terme van die probleem stelle? Wel, miskien 'n teaser van wat ons almal het verlede jaar met jou voorgangers. In die eerste probleem stel verlede jaar, het ons ' Nuuts af, 'n grafiese taal wat kan jy letterlik program sleep stukke van die legkaart, soos hierdie, wat herinner aan die konstrukte sal net een week sien Daarom, toe ons skakel na 'n meer tradisionele taal, bekend as C. Verlede jaar het ons voortgegaan om hierdie probleem stel, wat vir kriptografie, die skommeling van inligting om dit te hou van die regering of vriende se oë wat jy nie wil hê om dit te sien. Ingebou in hier is 'n boodskap wat vinnig jy sal in staat wees om te ontsyfer of de-geskarrel. Tempo was 'n probleem stel verlede jaar, waarin jy hierdie nuwe gevind ontwikkeling gebruik vaardighede om werklik te implementeer 'n spel wherein-- as jy kan onthou uit childhood-- Die doel was om die te bash stene wat bo-op die skerm hier, die opbou van 'n telling langs die pad, en implementering van jou eie algoritmes waarmee hierdie oplossing uiteindelik kan jy die spel speel. Intussen het later in die semester, sal ons gee jou 'n woordeboek van 143091 Engelse woorde. En jy sal uitgedaag word 'n program te skryf wat spel tjeks, dokumente, deur laai dat baie woorde in die geheue so doeltreffend as moontlik te maak. Die algemeen beit jy teen jou klasmaats as jy kies in 'n bietjie van 'n uitdaging in die leier raad om te sien wie kan die geringste sekondes hardloop tyd, en die minste aantal megagrepe geheue, en eintlik verfyn jou programme ongelooflik hulpbron doeltreffend nie net die tyd. Verlede jaar het ook gekyk na die einde van die semester op die web ontwikkeling. En inderdaad, sal ons weer doen wat jaar met verskeie probleem stelle, bekend te stel aan die tegnieke en die ingesteldheid waarmee jy kan aansoek doen hierdie programmeringsvaardighede te webtuistes, dinamiese webblaaie, webwerwe wat eintlik los probleme en anders optree en is nie net statiese webwerwe met statiese inligting. Die finale projek uiteindelik definieer, al is, die klimaks van die kursus vir studente, waarin jy sal uitgedaag word om te implementeer mees iets van belang aan jou, so lank as dit een of ander manier trek op die kursus se lesse. En as jy in die gesien video aan die begin, ons sal die semester met die gevolgtrekking CS50 Hackathon, wat as onbekende, begin om 07:00 een nag en eindig op 07:00 die volgende oggend. Rondom 09:00, sal ons Om in die eerste ete. Rondom 01:00, sal ons Om in die tweede ete. En as jy nog staan ​​op 05:00, ons sal shuttle bus jy te IHOP vir ontbyt. Die CS50 Fair, intussen, is 'n gebeurtenis waartoe 2000 plus fakulteit, studente, en personeel van regoor kampus sal kom jou prestasies te sien in die loop en die finale projekte en skeppings wat jy skep op jou skootrekenaars, desktops, of miskien selfs gloeilampe. Intussen kantoorure en die ondersteuning struktuur. En nou is dit sou gewees het 'n beter tyd om julle almal te bring. Kantoorure vier nagte plaasvind 'n week vir verskeie ure elke nag algemeen 20 tot 30 van die Natuurlik se personeel aan diens in 'n keer om jou te voorsien met 'n intieme een-tot-een-geleenthede vir ondersteuning met die kursus se probleem stelle. Tutoring te wees beskikbaar is nie, veral vir studente minder comfortable-- of waag om te sê die minste comfortable-- vir wie kantoorure is nie die die meeste koester omgewing en is beslis nie die meeste stres-vrye. Veral wanneer spertye te druk, ons sal proaktief paar jy onsself met 'n lid van die personeel te werk met op sommige gereelde skedule as jou behoeftes en hulle skedule dit toelaat. En personeel. Laat my toe om Davon, Rob te stel, en Gabriel, vanjaar se koppe. As jy wil graag elke say-- [Applous] --a woord. [Applous] Davon hier is die Natuurlik se bestuurder, wat beteken in sy voltydse rol Hy help met die uitvoering en logistiek van CS50. Davon: Ja, hi, ouens. Jy sal 'n baie te sien aan my by kantoorure. Ek sal onderrig word om dele. En as jy skiet die e-pos wat voorlê, Ek sal waarskynlik reageer word. So ek sal sien baie van julle almal semester. En welkom by CS50. David J. Malan En nou Gabriel, wat self was net 'n groentjie verlede jaar, maar vir die afgelope paar jaar het is wat sy eie weergawe van CS50 in Brasilië, waar hy afgelaai al van die kursus se content-- wat duidelik verfilm en geplaas online-- sodat hy dit kan vertaal na Portugees en dan leer meer as 100 van sy klasmaats oor die loop van 'n paar jaar, onderrig in sy moedertaal die kursus se kurrikulum. GABRIEL: Hello. [Applous] GABRIEL: Hi, ek is Gabriël. Ek is die hoof TF van die kursus. En ek hoop dat jy lief CS50. Dit is CS50. David J. Malan Nou vir Rob. O, jy wil inleiding? ROB: Nee, ek weet nie. [Gelag] David J. Malan en Rob Boden. [Gelag] ROB: Hi, ek is Rob. Dit is my vyfde jaar betrokke by die kursus. Elke jaar, is dit net 'n beter en beter klas sodat julle ouens is duidelik gaan awesome wees. Ek hoop julle almal het baie pret met dit. Ek gaan om pret te hê met dit. So sien jou rond. David J. Malan En tyd sal nie toelaat us-- [Applous] Tyd sal nie toelaat dat ons almal bekend te stel op die verhoog en al van hul kollegas wat inkopies klasse vandag. Maar laat my in te voer Belinda en CS50 legkaart Dag, wat wag om hierdie Eerskomende Saterdag, wat is die eerste van die Natuurlik se groot gebeurtenisse. Hierdie een in die besonder bedoel huis hamer die punt dat die rekenaar wetenskap is uiteindelik nie oor ontwikkeling nie, maar eerder oor die probleem oplos meer algemeen. En legkaart Day, soos u sal sien, sal jy bring en jou klasmaats saam op ons hoop dat hierdie Saterdag. BELINDA: OK. Hi, ouens. So dankie. So as ons roemryke kaptein gesê, my naam se Belinda. Ek is 'n stage by Quincy House. Ek, net soos julle, het CS50 verlede jaar, regtig mal daaroor. Ek het 'n sagte plekkie vir julle ouens in die derde ry. En ek is trots om te sê, ek is nou in 'n toegewyde verhouding met CS50 [onhoorbaar]. OK. Dit was my lam weergawe van 'n grap. In elk geval, so beweeg op, wou net te nooi julle al die i-laboratorium, of HBS korwe. Ons gaan word met Legkaart Day 12:00-03:00. En dit is 'n wonderlike geleentheid vir jou ouens jou mede CS vriende te ontmoet, los 'n paar nie-CS raaisels, soos Kaptein genoem, en eet ook 'n paar gratis kos, verdien 'n paar awesome pryse, soos geskenk kaarte, $ 75 per persoon, en also-- wat was dit? Wii U of iets? Wii U? Ja. Vir ons tombola. Awesome. So ek sal hou om na die klas. En as julle enige vrae, laat my weet. David J. Malan en jy sal sien, buite hierdie is daar is niks om te doen vandag. Die eerste probleem stel gaan uit Vrydag. Maar ons huis toe te bring vandag, wil ek graag stel jy spesifiek 'n meer lid van die personeel, Colton Ogden hier, wie se hande is nou bo jou beskerm met hierdie MIDI kontroleerder huis tot op die punt verder hamer dat die rekenaar wetenskap, ook het toepaslikheid ver buite ingenieurswese en die stam en rekenaarwetenskap self, selfs tot op domeine soos musiek. Colton het vriendelik offered-- Ek het gedink een van hulle is van plan om die fokus te los. Andrew, as ons kon ontbied fokus hier vir net 'n oomblik. Wat Colton gedoen vooruit is program hierdie toestel, hierdie pad van knoppies wat jy sien foto hier, as 'n MIDI kontroleerder, waardeur elk van die knoppies is bedraad om 'n bepaalde musikale noot of 'n gesonde, meer in die algemeen 'n opname, sodanig dat deur die speel van patrone van hierdie knoppies, baie soos patrone van stukkies, ander kan verteenwoordig hoër vlak konsepte. Sal hy in staat wees om uiteindelik ons huis toe te neem vandag hier? Sonder verdere uitstel het, indien ons die ligte kan verswak en draai op die skerm agter Colton. Publiek: Woo! David J. Malan Dit is CS50. [Speel van musiek] [Applous] Dit is dit vir CS50. Ons sal sien jy Vrydag. Sommige koek wag vir jou in die transept. [Speel van musiek]