[MUSIK SPELA] [Applåder] DAVID J. MALAN: Detta är CS50, Harvard University introduktion till den intellektuella företag av datavetenskap och konsten att programmeringen. Nu om du är bland dem som Varje år sitter här med lite nerver i ditt sinne, såsom att du inte tror att du hör hemma här, du tror att de flesta någon som sitter runt dig vet mycket mer än du, är verkligen bekvämare än du vid datorn vetenskap eller datorer mer allmänt, inser att 78% av de studenter som nu ta CS50 ha någon tidigare erfarenhet. I själva verket finns det 100 punkter där på displayen, 78 varav är fast grönt, vilket innebär att du, Om du är bland den demografiska, är i mycket gott sällskap här på ut. Och om du är i stället bland de 22% av CS50 studenter som gör faktiskt har tidigare erfarenhet, vare sig i gymnasiet eller något annat program, inse att du kommer också att utmanas i kursen. Inte nog med att vi har olika spår för studenter mindre bekväma och mer bekväm både i sektioner, vi också har så kallade hackers upplagor de flesta problem uppsättningar som kommer att utmana de elever med att ytterligare erfarenhet att undersöka liknande material men från en mer sofistikerad perspektiv. Men vad är datavetenskap? Tja, i slutändan, är det som kommer att materia som du utforska detta område inte är så mycket när du hamnar i förhållande till dina klasskamrater, men där du själv hamnar i vecka 12 kontra där du börjar här i vecka noll. Nu dator science-- ja, låt oss kalla det vetenskapen om computation-- där beräkningen är egentligen bara en fint sätt att säga, med lite input, producerar några utgång, och gör det genom att löpande algoritmer, uppsättningar av instruktioner för att lösa vissa problem på dessa insatsvaror i syfte att producera en utmatning eller lösning där du är intresserad. Så vi hade nyligen tillfälle att resa ut till Kalifornien för att träffa en alumn. Hon heter Susan Wojcicki. Och hon vill tala till dig här på video att vittna om hur tillämpliga och med bara en smak av dator vetenskap vid introduktionsnivå kan vara. Även om du inte går på att fullfölja datavetenskap som ett fält, eller till och med teknik, eller STEM mer allmänt, du ser, faktiskt, hur en viss Naturligtvis så påverkade hennes liv. Och hon bara tog det när hon var en senior här på Harvard College. Om vi ​​kunde dämpa belysningen för Susan. SUSAN Wojcicki: Hej, värld. Jag är Susan Wojcicki. Jag är VD för YouTube. Och jag tog CS50 när jag var en senior på Harvard 1990. Jag var faktiskt en historia och litteratur som huvudämne. Och min junior sommaren, Jag insåg att jag kanske ville lära sig något om datorer. Och så kom jag tillbaka. Jag tog CS50. Det var svårt, men det var det mest fantastiska klass jag tog. Det förändrade hur jag tänker på allt. Och när jag tog examen från Harvard 1990 åkte jag till Silicon Valley. Och jag har ett jobb. Och jag har jobbat i tech sedan dess. DAVID J. MALAN: Nu vad Susan nämnde inte i denna video, att det faktiskt var i hennes garage som Google själv var grundades av Larry och Sergey. Nu nådde vi också ut till våra vänner vid code.org, en organisation som under det senaste året har varit få människor i synnerhet entusiastiska över datavetenskap och programmering, i synnerhet. Men det är värt att notera att programmering inte datavetenskap i sig. Datavetenskap är inte programmering. Snarare programmering är bara en tool-- som ni alla kommer att vara allt för väl bekant med termins end-- så att du kan använda inte bara för att framtida kurser i CS men att oavsett fält från whence du kommer, inom humaniora, samhällsvetenskap, natur vetenskap, eller liknande. I själva verket tillåta några andra alumner och deras kollegor att tala om tillämplig av fältet som väntar. BILL GATES: Jag var 13 när jag först fick tillgång till en dator. Jack Dorsey: Mina föräldrar köpte mig en Macintosh 1984 när jag var åtta år gammal. Mark Zuckerberg: Jag var i sjätte klass. SPEAKER 1: Jag lärde mig att koda på college. Ruchi SANGHVI: Freshman år, först terminen, Introduktion till datalogi. BILL GATES: Jag skrev ett program som spelade tic-tac-toe. DREW HOUSTON: Jag tror det var ganska blygsam start. Jag tror det första programmet Jag skrev frågade saker som, vad är din favoritfärg? Eller hur gammal är du? ELENA SILENOK: jag först lärde mig hur man gör en grön cirkel och en röd fyrkant visas på skärmen. GABE NEWELL: Den första gången jag faktiskt haft något som kommit upp och säga, hej, värld. Och jag gjorde en dator göra det. Det var bara häpnadsväckande. Mark Zuckerberg: Att lära sig till programmet inte börja som vill lära alla datavetenskap eller försöker att behärska detta disciplin eller något liknande. Det började precis utanför för att jag ville göra det här en enkel sak. Jag ville göra något som var kul för mig och mina systrar. Och jag skrev den här lilla programmet. Och sedan i princip bara lagt lite för den. Och sedan när jag behövde att lära sig något nytt, Jag tittade upp, antingen i en bok eller på internet, och sedan lagt till lite till den. DREW HOUSTON: Det är verkligen inte i motsats till spela ett instrument eller något eller spela en sport. DAVID J. MALAN: Okej. Så låt oss nu faktiskt dyka i lite djupare. Vilka är dessa in-och utgångar att vi pratar om här? Så vad sägs om något enkelt? Du vet förmodligen, även om du har ingen kännedom datavetenskap helst, att datorer på något sätt använder och förstår bara nollor och ettor. Men hur kan det möjligen med tanke på hur mycket dagens stationära och bärbara datorer såväl kan göra? DNA av dagen, den enda alfabetet som de förstår är en nolla eller en etta. Tja, överväga detta. Vi, människor, tenderar att använda decimalsystemet. "December" som betyder 10. Och det är 10 eftersom vi har 10 siffror, 0 till nio. Nu datorer, däremot, tenderar att använda binär. "Bi" betyder två. Så de har en tendens att bara noll och ett använder. Men det visar sig, att även bara med ettor och nollor, som är ett tillräckligt stort alfabet som för att representera de flesta varje bit data du vill ha, oavsett om det är ett nummer, oavsett om det är en bokstav, oavsett om det är en bild eller en video på skärmen. Betänk till exempel, hur vi människor vanligtvis tolka detta nummer här. Detta är bara tre siffror, ett, två, tre. Men vi vet att det här numret medfött nu som 123. Men varför är det? Tja, om du tänker tillbaka till kanske skolan, du förmodligen fick lära sig att tänka på dessa siffror som att vara i kolumner, där man är i de hundratals plats, är de två i tiotalen, och de tre är i sådana rum. Varför är det faktiskt bra? Tja, tänk på super enkla aritmetiska att vi alla har varit gör i flera år nu. Effektivt, om du har en en i hundra rum, du gör den snabb matematik 100 gånger ett plus 10 gånger 2-- eftersom två är i tiotals plats-- plus 1 gånger 3-- eftersom tre är i sådana rum. Så, naturligtvis, om vi multiplicera faktiskt ut det här, vad vi verkligen representerar med denna pattern-- en två tre-- är 100 plus 20 plus 3, vilken, naturligtvis, är 123. Nu binärt, och datorer egentligen, i grunden talar samma språk att vi gör. De har bara en mindre alfabetet. Så datorer har bara nollor och kära till sitt förfogande. Så medan vi människor har i huvudsak befogenheter 10 i var och en av dessa places-- 10 till noll, 10 till en, tio till de två, vilket ger dig 110 och 100 respektive. Eftersom datorer har bara två värden de kan förstå, noll och ett, de måste använda olika värden i dessa kolumner, en, två, fyra. Och om vi höll på, åtta, 16, 32, 64, och så vidare. Men mönstret och mentala är exakt samma. Så genom denna logik, vem som helst, hur skulle Jag går omkring som representerar antalet en i binär? Om du har aldrig ens tänkt på det här förut, vad är din gut säger? PUBLIKEN: One. DAVID J. MALAN: One. Exakt. Vi behöver bara en en i ettor plats eftersom nollor räcker för att ge oss varken en fyra eller en två. Så ett gånger ett är lika med ett. Nu det blir lite intressant. Om jag vill representera i binära numret two-- men, igen, även om du har aldrig talat detta språk innan, hur gör vi representerar i binär värdet vi människor känner som två? Noll en nolla. Bara sätta den i kolumn som du vill ha det. Nu blir det ganska lätt nog nu. Så om jag vill representera tre-- det finns ingen tre spalt. Så, återigen, jag kan nu lägga till dessa värden tillsammans genom att sätta en man här. Så 2 gånger 1 plus 1 gånger 1 är, naturligtvis, 3. Nu det blir lite kul i att de som blir nu nollor. Och för att representera fyra, får jag det här. Och om vi öka långsamt här-- som skulle vara fem. Detta skulle vara sex. Detta skulle vara sju. Men nu verkar jag ha stöter på ett problem. Hur skulle jag gå om att representera eight-- skulle bli nästa värde. Ja, så vi behöver en ny bitar. Och, ja, om du har hört denna fras förut, bitar, det är bara en förkortning för binär siffra, noll eller ett. Och så jag råkar representera endast tre sådana bitar här. Men om jag hade ett sätt att lagra inte tre olika bitar, men fyra, säkert jag kan representera åtta, och sedan nio, och sedan 10, och till och med högre och högre. Men som sedan kallar ifrågasätta hur vi kan gå företräder dessa saker i första hand. Det är en sak att dra dem upp här på en bild, men hur ska du representera dem om du är en mekanisk anordning? Vad en dator gör att representerar de in-och utgångar som fundamentalt definierar beräkning i slutet av dagen? Nå, hur är det något super enkelt så här? Det är bara en glödlampa. Och jag kan utlösa detta glödlampa att gå på genom att vrida lite el på och tillåter elektroner att strömma genom, som ändrar sin stat eller dess värde, så att säga. Till exempel är denna en gammal skola skrivbordslampa här med en sådan glödlampa i den. Och just nu är det inte verkligen gör något användbart. Men så fort jag ansluter den till ett eluttag och sedan använda denna switch-- eller Vi kan till och med kalla det en transistor eller se det som such-- Jag kan nu representera antingen detta värde, där glödlampan är uppenbarligen av, eller detta värde. Detta värde eller detta värde. Detta värde och så vidare. Så insidan av en dator, förmodligen, är mycket mindre bitar av hårdvara, men att i slutet av dagen helt enkelt ha använda electricity-- kanske fånga den-- och sedan antingen behålla något eller hålla något av. Naturligtvis är detta inte särskilt intressant att göra med bara en enda glödlampa. Faktum är hur högt kan jag räkna in binärt med denna skrivbordslampa här? PUBLIKEN: One. DAVID J. MALAN: En, eller hur? Jag behöver mer skrivbordslampor om jag egentligen vill räkna högre. Men vi kan göra bättre än så. Eftersom glödlampor som Vi har lagt in dessa saker är faktiskt snyggare glödlampor än förr skulle tillåta. Och de är faktiskt nätverks glödlampor. Och klasar av företag göra dessa saker i dessa dagar. Men det visar sig att detta i synnerhet kommer med en funktion som innebär att Du kan ändra dess färger. Så till exempel, om du prydd ditt studentrum med några av dessa ljus lökar, beroende på ditt humör, beroende på vem som kommer in, beroende på vädret, beroende på tiden på dagen, kan du faktiskt ändra färg på lökarna i ditt rum. Och det beror på att dessa ljus glödlampor och andra gillar det har vad är kallas ett API, ett program programmeringsgränssnitt, som är ett ämne som du kommer att vara känner av terminen slut. Och detta är bara en fantasi, kryptiska sätt att säga, du kan programmera dessa ljus lökar att göra din budgivning. Du kan skicka meddelanden till dem precis som du, en människa, kan skicka ett meddelande till en webbserver säga, ge mig dagens nyheter eller ge mig min e-post. Du kan skicka mer svårbegripliga meddelanden till dessa lampor att säga, sätta på och stänga av. Men det är inte så intressant. Man kan säga, slå på rött, slå på green, slå på blå, alla med samma glödlampa. Och du kan till och med, med lite mer kunniga, säger, vända dig till blå när det är en dyster dag utanför, till exempel. Det kan faktiskt patcha in en väder API och reda hur vädret är, eller den tid på dagen, eller andra sådana triggers. Så i själva verket två av CS50 egna anställda, Dan Bradley och Ansel Duff här, vänligen upphandlas oss en hel massa av dessa lampor. Och de byggde CS50 s första någonsin binära lökar, där vi har representerade här-- med dessa lekfull liten magnets-- de olika platshållare vi anspelade på bara lite sen. Så vägen hit är det kära plats, två, fyra. Och vi såg inte högre än så. Men, naturligtvis, de är potenser av två. Åtta, 16, 32, 64 och 128. Så om jag nu vill vara lite snyggare än att använda din gamla switch, Jag har här på denna iPad en super enkelt gränssnitt att Dan Bradley, en före detta student och nu undervisar karl, programed använda en del HTML och JavaScript, vilket är uppmärkning och programmering språk respektive. Och du kan förmodligen se-- även i back-- det är ett stort plus och ett stort minus, plus en knapp för varje av dessa lampor. Och vad detta kommer att tillåta mig att gör är till exempel klicka på plus och nu representerar, om Naturligtvis vilket nummer? One. Och jag kan slå det igen. Två. Tre. Fyra. Fem. Sex. Sju. Och här nu får vi att rollover, men vi har en fjärde bit denna tid, så nu har vi åtta. Så vi kunde göra detta under ganska lång tid. I själva verket, som en sidoreplik, hur högt kan vi räkna? Någon? PUBLIKEN: 255. DAVID J. MALAN: 255, eller hur? Oroa dig inte för mycket om matematik för nu, men det är verkligen ingen dålig siffra. Men det faktiskt inte bunden bara hur många bitar av information, som ett brev, eller en grafisk att vi kan representera. Men oavsett för nu. Jag kommer att gå vidare och slå dem alla. Och om jag kunde skulle jag vilja be om volontär, vår första volunteer-- åh, hello-- på scenen. Fångsten är att du måste vara bekväm visas, eftersom du tydligt är framför allt dina klasskamrater, samt på internet. Och låt mig se lite längre än i-- vad sägs om här i vit skjorta? Och lämna dig. Kom upp. Vad heter du? PUBLIKEN: Jackie. DAVID J. MALAN: Jackie. Jackie, kom upp. Så vad finns det också på denna iPad är en knapp som heter Game Mode. Och detta spelläge är kommer att tillåta mig att mata på förhand en viss decimal nummer, siffrorna vi människor är bekant med. Och då kommer du att utmanas för att använda knapparna på top-- en för var och en av dessa bulbs-- att faktiskt räkna ut mönstret av glödlampor som representerar det aktuella numret. Och jag är ledsen, vad var ditt namn igen? PUBLIKEN: Jackie. DAVID J. MALAN: Jackie. Okej. Trevligt att träffas. Så låt mig gå vidare och program för världen att se hur många 15. Vi ska hålla det litet till en början här. Och jag kommer att gå in i Spelläge. Och jag kommer att specificera, ge oss numret 15. OK. Och nu med alla watching-- om du vill kanske stå på detta sätt, eftersom det kommer att radas up-- gå vidare och växla de åtta knapparna längs toppen att vända lamporna på eller av som du tycker passar. PUBLIKEN: OK. DAVID J. MALAN: Och inget fusk genom att slå plus 15 gånger. Åh, vi kommer att göra det. PUBLIK: Åh, vänta. Jag är så ledsen. DAVID J. MALAN: Du kan också aktivera glödlampor på individuellt med var och en av dessa knappar på toppen. PUBLIK: Åh, OK. Så det skulle vara like-- DAVID J. MALAN: OK. Så nu har vi åtta. Så låt oss göra en paus för publiken att engagera sig här. Vilket nummer är Jackie närvarande representerar? 11. Så vi är nästan där. Och utmärkt. Så vi har vår första vinnare. Gratulerar. Och vi trodde att vi skulle ha några fantastiska giveaways. Om du vill vara en sådan dorm rum här på campus, du kan själv ha en slutprojekt använder nu detta API, tack till Jackie. Så nu-- [Applåder] --Om vi ​​kunde, ytterligare en såsom runt denna. Åh, nu alla vill vissa glödlampor. För den så kallade hackare upplagan, vi kommer att rampa upp en-- oh, ja, intetsägande. Jag tror att du kommer upp nu Om din hand är på väg ner. Vad heter du? PUBLIKEN: Alex. DAVID J. MALAN: Alex, kom hit. Så för Alex, kommer vi att program i ett något större antal. Kanske för. Antalet 50. PUBLIKEN: OK. DAVID J. MALAN: Men, som Jag sa-- och du kanske vill stå här så att knapparna radas upp som du skulle expect-- men jag gjorde kalla detta hacker upplagan. Så-- lycka till! [LAUGHTER] Du kommer att kunna vända dem om du-- OK. Utmärkt. Underbart. Gratulerar. [Applåder] Jag antar att jag borde betala. Grattis till Alex också. OK. Så den ultimata takeaway här är förhoppningsvis, ärligt talat, den simplicity-- den enkelhet med vilken du kan få några trevliga ljus lökar, uppenbarligen i [ohörbart]. Men de representerar, slutligen, samma idéer med vilka vi människor är redan alltför välbekant. Så vad kanske nästa steg vara i progression för att försöka göra något intressant med uppgifter och representerar indata som inte bara siffror men är kanske bokstäver eller mer? Tja, det visar sig att den datorn världen, i många år, helt enkelt antagit ett godtyckligt men en konsekvent standard som mappar siffror till bokstäverna i alfabetet. Till exempel, här är en utdrag från denna kartläggning. Det kallas Ascii. A-S-C-I-I. Och det är helt enkelt en tabell som mappar versaler letters-- i detta case-- till decimaltal. Men vad är innebörden? Tja, om du verkligen vill representera något som e-post eller någon text på en webbsida, du uppenbarligen vill visa mänskliga bokstäverna i alfabet, inte siffror. Så beroende på ramen för programmet att en användare använder sig av, om det är en webbläsare eller e-postklient, nummer kan säkert vara tolkas som bokstäver. Det vill säga, mönster av bitar kan lätt tolkas som bokstäver. Och så vad vi kan få är bokstaven A varelse representeras som 65, B representeras som 66. Så om vi har en super korta ord, som hi, vad en dator skulle i slutändan butik i decimal men egentligen i binär, med användning av någon sekvens av bitar, utnyttja lite av el på något sätt, skulle vara de två siffrorna 72 och 73. Men mönstret av bitar som representerar dessa värden. Så dessa är då hur vi kan representerar våra in-och utgångar. Och det räcker att säga, vi kan göra mer komplexa representationer slutligen med saker som grafik, video, musik och mer som vi får se senare denna term. Så att bara lämnar sedan algoritmer, dessa uppsättningar av instruktioner som vi lösa faktiska problem. Vi passerar på insatsvaror till algoritmer. Och dessa algoritmer producerar utgångar, förhoppningsvis korrekta utgångar och förhoppningsvis också, effektivt samlat utgångar. Med andra ord, det är en sak att genomföra något fullständigt. Det är en annan sak att genomföra något bra eller effektivt. Till exempel, en demonstration att vi är förtjust i under loppet är detta en. Men dessa saker blir allt svårare att hitta. Men detta är verkligen en gammal skola telefonbok, inuti vilken är 1.000 plus sidor namn och telefonnummer. Och om jag ville söka upp någon i den här telefonboken, Jag kunde helt enkelt göra en mycket naiv algoritm. Jag skulle kunna öppna upp till den första sidan, och Jag skulle kunna börja leta efter, säg, någon vid namn Mike Smith. Och om han inte är den första sida, jag vidare till den andra, och sedan till den tredje, och sedan till den fjärde, och så vidare, tills jag hittar äntligen Mike Smith. Nu är att algoritmen korrekt? PUBLIKEN: Ja. DAVID J. MALAN: Ja. Om han är där, jag småningom hitta honom. Men det är utan tvekan inte mycket effektiva, absolut inte snabbt, eftersom, min Gud, varför är jag slösa min tid vändning igenom alla dessa sidor när jag kunde säkert göra det fysiskt snabbare? Tja, en liten optimering, så att tala, kanske inte en sida i taget, utom två, fyra, sex, åtta, 10. Fortfarande korrekt? PUBLIK: Nej DAVID J. MALAN: Så nej om jag för exempel hoppa över Mike Smith. Men så länge jag tillbaka pedalen en sida, om jag skjuta honom, Vi kanske skulle kunna rätta till det som kan annars vara en gotcha. Men är det bättre? Är det snabbare? Jag menar, ja. Det är bokstavligen dubbelt så snabbt om jag gör två sidor i taget. Så om jag hade ursprungligen 1.000 sidor, Nu har jag bara att vända 500 gånger, inte helt 1.000 sidor för att få potentiellt i värsta fall till änden av telefonen bok, där någon som Mike Smith eller någon med ett senare namn kan faktiskt vara. Men, naturligtvis, vi människor är verkligen inte kommer att göra det, absolut inte på denna punkt i våra liv. Vad är en rimlig människa sannolikt kommer att göra? PUBLIK: Gå direkt till the9 S. DAVID J. MALAN: Gå direkt till S? Hur går jag direkt till S? PUBLIK: Rip den på mitten. DAVID J. MALAN: Tja, det finns ingen märkning. Så, ja, om det verkligen var en etikett eller en klibbig flik för S, Vi ska hoppa där. Men det är ganska harmlöst. Så det bästa jag kan göra är ungefär till S sektionen eller kanske grovt i mitten. Men nyckeln takeaway nu-- och intuition att du har tagit för beviljats ​​för år probably-- är det vad gör ni nu vet om det här problemet? PUBLIK: [ohörbart] DAVID J. MALAN: Mike Smith är säkert inte i denna halv av problemet eftersom Smith kommer efter mitten vilket är ungefär M sektionen, det verkar vara. Så som ni kanske har sett på Visitas, kan vi nu bokstav riva detta problem i hälften. PUBLIK: Woo! DAVID J. MALAN: Det är blir lättare och lättare. [Applåder] Så där ja. [LAUGHTER] Och nu har jag i grunden har samma problem, men det är bokstavligen hälften så stor. Jag letar fortfarande efter Mike Smith. Och jag vågar påstå, jag kan fortfarande leta efter honom på samma sätt, att dela upp problemet i halv igen, riva problemet igen på mitten, som nu lämnar mig med ett problem en fjärdedel av storleken, dramatiskt kasta att hälften bort, och upprepa processen om och om igen och igen, en blick ner vid varje punkt för att se Om Mike Smith är på sidan i fråga. Nu om jag gör denna rätt, i slutändan jag hittar mig själv med bara en sida där Mike Smith är om han är verkligen i telefonboken. Naturligtvis kunde jag aldrig ringa Mike igen. Men poängen här är att om vi började med 1.000 sidor, min första algoritmen, vända sida, kanske 1.000 times-- definitivt mindre eftersom det är ett namn och inte ett Ö namn, utan som många som 1.000 sidor potentiellt. Andra algoritm, bättre. 500 sidor. Tredje algoritm, fast, hur många steg skulle det ta för att dela upp en 1.000 sida telefonbok i hälften så? 10, ge eller ta. Så bara genom att bläddra igenom det telefonbok, dykning och erövra, så att säga, 10 gånger, kommer jag att göra min väg ner till bara en enda sida. Och så att vi kan fånga denna intuition Nu lite grafiskt om du bara överväga denna super enkel graf. Vi är på x-axeln, eller horisontell axeln, är storleken på mitt problem, antalet sidor i telefonboken. Och datavetare allmänhet vill kalla storleken på ett problem n, där n är bara några variabel som represents-- i detta case-- antal sidor. Den vertikala, eller y-axeln, här är kommer att vara tid att lösa, Kanske antalet sidan varv, Kanske antalet sekunder eller minuter, oavsett din måttenhet är. Och så denna röda linjen representerar den första algoritmen, eftersom det finns en 1-1 förhållandet mellan antalet sidor och hur lång tid det tar. Om Verizon fördubblar antalet sidor i telefonboken nästa år, mitt spring time-- den tid som krävs för att exekvera att första algorithm-- fördubblas i värsta fall. Men den andra algoritmen, där jag vända med två, kräver mindre tid för en given storlek problem. Så om jag har den här många sidor här-- Grafiska att den gula linjen föreslår mindre tid att lösa. Och faktiskt, står det, vi ska säga, n över två. Men vad är formen på den tredje och sista kurvan kommer att se ut? Ja, det verkligen kommer att look-- I vet inte vad du skulle säga. Men låt oss se vad du skulle säga. PUBLIK: Gillar det. DAVID J. MALAN: Det kommer att se ut detta, en logaritmisk slope-- exactly-- där du har denna nyfikna lutning. Det är inte längre en rak linje. Och vad är övertygande om det är att även om diagrammet är nu avskurna, du kan extrapolera i ditt tänka att det gröna linjen inte är kommer att öka i höjden så mycket när du går vidare ner den horisontella axeln. Indeed, Verizon för Exempelvis kan fördubblas antalet sidor i telefonen bok mellan i år och nästa år från 1000 till 2000 sidor, men ingen big deal. Med denna tredje och sista, det finns en intuitiv algoritm att dela och erövra. Det kommer att ta mig hur många fler steg nästa år att hitta någon gillar Mike Smith? PUBLIKEN: One. DAVID J. MALAN: Det finns bara en. Och de kan fyrdubbla det, det är kommer att ta mig bara två steg och så vidare. Och så det här är ett bevis på hur några noggrann utformning och lite uppskattning för det som dina ingångar är kan göra ännu bättre. Nu är vi fuskar en liten bit i den meningen att vi utnyttja ett antagande. Vad är mitt antagande om vår telefonbok som får mig att söndra och härska i denna intuitivt och ändå rätt sätt? PUBLIK: [ohörbart] DAVID J. MALAN: Ja. Så det beställdes. Den var i alfabetisk ordning efter telefonboken företaget. Om det var i slumpvis ordning, att skulle vara ett helvete av en telefonbok, men det verkligen inte skulle lämpar sig för algoritmen Jag använde, eftersom du skulle aldrig bara hända över Mike Smith om du höll dela in halv på detta sätt av en slump. Så låt oss nu formalisera vad är klart intuitivt. Så något som kallas pseudokod är där vi ska börjar några av våra inledande problem. Och detta är ett generiskt sätt att beskriva en algoritm eller ett datorprogram, inte med C eller C ++ eller Java, eller något specifikt språk, men bara med hjälp av engelska, med som någon människa kan vara bekant. Och vi kanske skriva pseudokod för detta problem enligt följande. Steg ett, plocka upp telefonboken. Steg två, öppen för mitt i telefonboken. Steg tre, titta på namnen. Steg fyra om Smith är bland names-- Och nu detta är en intressant konstruktion. Det är en beslutspunkt. Det är ett vägskäl, om du kommer, en gren, så att säga. Så jag kommer att dra in bara genom konvention step-- inte five-- vilket är att säg, jag ringer Mike. Så detta indrag, helt godtycklig mänsklig konvention, är men det helt enkelt tänkt att förmedla semantiskt att om Smith är bland namn, då ska jag ringa Mike. Under tiden i steg sex, meddelande att fördjupningen är borta. Så annars är den andra gaffeln i väg, den andra vägen jag skulle resa. Så annars om Smith är tidigare i boken, vad är mitt nästa steg kommer förmodligen att vara här? PUBLIK: Du går till vänster sida. DAVID J. MALAN: Ja, så gå till den vänstra halvan av telefonboken. Kasta bort den högra halvan, om Smith är tidigare i boken. Så öppet till mitten av den vänstra halvan av boken. Och sedan steg åtta, gå till rad tre. Och detta är en nyfiken loop är jag förmå, en rekursion så att säga. Men mer om det i framtiden. Jag använder min samma algoritm, my samma pseudo, att lösa samma problem igen eftersom det enda som har förändrats är storleken på problemet, inte mitt mål, och inte personen Jag letar efter. Så jag kan återanvända algoritmen som jag redan har definierats. Annars om Smith är senare i book-- du kanske guess-- öppen till mitten av den högra halvan av boken. Och återigen, gå till rad tre. Else-- vad är den sista raden i detta program kommer att bli? Om han inte är bland de namn på sidan är jag på, om han inte tidigare i boken, och han är inte senare Jag vet i boken, vad gör är sant om Mike Smith nu? PUBLIK: Han är inte i boken. DAVID J. MALAN: Han är inte i boken. Så det bästa jag kan göra är att bara ge upp och stoppa detta program. Okej. Så på denna punkt, låt oss ta en guidad visning av några av vad som väntar. Och faktiskt, jag gick med här av ett antal CS50 personal. Om dessa människor kunde alla gå med mig här på scenen. [Applåder] Märk väl, detta är bara en delmängd av CS50 personal, eftersom varje år har vi nästan 100 anställda medlemmar i roller kursassistenter, undervisning medmänniskor, och mer. Kom upp. Så de kommer att ansluta oss här tafatt för bara ett ögonblick som vi ger en whirlwind rundtur i vad du kan förvänta dig här på kursen. Så först och främst har vi SAT / UNS som alternativet betygssättning i kursen. Detta menas avsiktligt vara ett alternativ som innebär att Om du är lite orolig på att ligga i kursen, och du fruktar failure-- även om frankly misslyckande innebär skada din GPA, få ett B och inte ett A-- som är exakt vad, säkert för en gateway kurs som CS50 och annat introduktionskurser, denna betygs alternativet är tänkt att låta. Jag helhjärtat uppmuntra students-- speciellt om å fence-- att starta Naturligtvis SAT / UNS, även förbli SAT / UNS. Men du kan säkert byta till ett brev klass den femte måndagen i termen. Uppriktigt sagt, tillbaka när jag var ny 1995, Jag själv tog inte ens CS50 eftersom jag inte få upp nerven att faktiskt steg fot i klassrummet. Det verkade en domän alltför obekant för mig och egentligen bara för de vänner till mig, ärligt talat, som hade varit programmering eftersom de var sex eller kanske 10 år gammal. Och det var bara för att jag var kunna ta CS50 i min dag i motsvarande version av SAT / UNS-- pass / fail tillbaka i day-- att till och med jag tog 50. Och på något sätt eller annat, är jag här igen med er i dag. Nu under tiden vad du bör tänka på om 50 är samtidig inskrivning. I motsats till rykten om att du kanske har hört, du kan, faktiskt, samtidigt skriva in sig i CS50 och en annan klass som sammanträder vid samma eller någon överlappning tid som CS50 föreläsningar här. Se kursplanen för de uppgifter av genomförandet av dessa. Lectures, under tiden, i motsats till vad är officiellt i katalogen, kommer i allmänhet endast träffas för bara en timme. Ibland kan vi köra lite längre. Men tänk på att det mål i CS50 föreläsningar är att ge dig en konceptuell översikt, förhoppningsvis några demonstrationer, kanske till och med några giveaways, om vad som väntar för veckan som följer. Och så på föreläsningar, kommer vi att undersöka dessa ämnen och exempel tillsammans, föra eleverna upp på scenen, och personal upp på scenen så ofta vi kan, för bara ett par timmar varje vecka. Sektioner, under tiden, kommer att vara erbjuds av dessa folks här-- många av dem undervisa stipendiater, en del av dem naturligtvis assistants-- vilja hända varje vecka. Och vad är nyckeln till att hålla i åtanke är att vi inte have-- inte olikt First Nätter, musiken class-- olika spår av sektioner för eleverna mindre bekväma, mer bekväma och någonstans däremellan. Och ärligt talat, vet du om du är mindre bekväm. Och du vet säkert om du är mer bekväm. Och om du inte är riktigt säker, är du definitions någonstans däremellan. Så när det blir dags att avsnitt i en vecka eller så, per kursplanen, Vi kommer att be dig den frågan. Och du kan själv välja Based på din egen komfort nivå och vara med students-- vara med grönt dots-- liknande komfort till dig. Under tiden har vi problem sätter, vilket kommer i slutändan definiera din upplevelse i denna kurs. De erbjuds vanligen i flera utgåvor. En standard edition som vi förväntar oss mest varje elev i kursen för att ta itu med men även en så kallad hacker utgåva som erbjuder någon form av extra kredit rakt av men egentligen skryta att säga att du försökt och åtgärdas kursens hacker utgåvor som närmar liknande material men från en mer sofistikerad vinkel. Vad vi erbjuder för Standard Edition, för, igen, en super majoritet av studenter, är inte Endast genomgångar, som är videoklipp ledda av kursens personal som verkligen gå igenom kursens problem och utformning implementeringar. Och vi också, efter Faktum erbjuder postmortems, vari om du undrar hur du kan ha eller borde ha löst en del problem, lärarna kommer att gå igenom de på video också. Under tiden vad som väntar för är fem sena dagar och det faktum att vi kommer att släppa din lägsta problemet satt poäng. Vi uppskattar verkligen att i utbyte för arbetsbördan att 50 förväntar av dig, blir livet i vägen Ibland, om inte fem gånger. Och så detta kommer att erbjuda du lite flexibilitet, utvidga din deadline från, säg, en Torsdag vid lunchtid på en fredag ​​vid lunchtid. Se kursplanen för genomförandet detaljer om detta. Nu vad nu väntar? Och det är bara inträffar för mig nu bara hur länge Jag har ni stå här på scenen. [LAUGHTER] DAVID J. MALAN: Men vi ska komma till den kulminerande slut snart. Så vad väntar i termer av problemsamlingar? Tja, kanske en teaser för vad vi alla gjorde förra året med era föregångare. I det första problemet set förra året introducerade vi Scratch, ett grafiskt programmeringsspråk som kan du programmera bokstavligen genom dra och släppa pusselbitar, som dessa, som är påminner om konstruktionerna ser bara en vecka alltså, när vi byter till en mer traditionell språk, som kallas C. Förra året fortsatte vi på detta problem uppsättning, involverar för kryptering, krypteringsinformations att hålla den från statliga eller vänner " ögon som du inte vill se det. Kodad in här är en meddelande som snart du kommer att kunna dekryptera eller de-scramble. Bryt var ett problem satt förra året, i vilken du använda dessa nyfunna programmering kompetens att faktiskt genomföra ett spel wherein-- som ni kanske minns från childhood-- målet var att bash tegelstenar som är ovanpå skärmen här, ackumulera en poäng på vägen, och genomföra egna algoritmer med vilka denna lösning ytterst kan du spela spelet. Under tiden, senare i termin, vi ger dig ett lexikon över 143.091 engelska ord. Och du kommer att utmanas att skriva ett program som spell kontroller, dokument, genom lastning att många ord i minnet så effektivt som möjligt. Generellt pitting du mot dina klasskamrater om du väljer in en bit av en utmaning i poängtavlan att se vem som kan använda det mest få sekunders gångtid, och minst antal av megabyte minne, och faktiskt finjustera dina program vara otroligt resurseffektiva inte bara tid. Förra året också, vi tittade på slutet av terminen på webbprogrammering. Och faktiskt, vi gör det igen år med flera problemsamlingar, introducera dig till de tekniker och tänkesätt som du kan använda dessa kunskaper i programmering till webbplatser, dynamiska webbplatser, webbplatser som faktiskt löser problem och beter sig annorlunda och inte bara statiska platser med statisk information. Den slutgiltiga projektet i slutändan kommer att definiera, men, kulmen av kursen för studenter, där du kommer att utmanas att genomföra de flesta något av intresse till dig, så länge som det på något sätt bygger på kursens lektioner. Och som du såg i video i början, Vi kommer att avsluta terminen med CS50 Hackathon, som om det, främmande, börjar klockan 07:00 en natt och slutar vid 7:00 nästa morgon. Omkring 09:00, vi ska För i första middag. Omkring 01:00, vi ska ordning i andra middag. Och om du fortfarande står vid 05:00, vi kommer buss du till IHOP för frukost. Den CS50 Fair, under tiden, är en händelse till vilken 2,000 plus lärare, studenter, och personal från hela campus kommer kommit för att se dina framgångar i kursen och den slutliga projekt och skapelser som du skapar på din bärbara datorer, stationära datorer, eller kanske till och med glödlampor. Samtidigt kontorstid och stödstrukturen. Och nu det har varit en bättre tid att ge dig allt. Öppettider kommer att äga rum fyra nätter en vecka för flera timmar varje natt med i allmänhet 20 till 30 av kursens personal i tjänst på en gång att förse dig med intima en-mot-en möjligheter för stöd med kursens problemsamlingar. Undervisningstid alltför kommer att vara tillgängliga, i synnerhet för studenter mindre comfortable-- eller vågar säga minst comfortable-- för vem kontorstid är inte mest vårdande miljö och är verkligen inte den mest stress. Speciellt när tidsfrister pressar, Vi kommer aktivt koppla ihop er själva med en medlem av personalen att arbeta med på någon regelbundet schema när behoven och deras schema tillåter. Och personal. Tillåt mig presentera Davon, Rob, och Gabriel, årets huvuden. Om du vill var och vilja säga-- [Applåder] --a ord. [Applåder] Davon här borta är den Naturligtvis chef, som betyder i sin heltidsroll Han hjälper till med utförandet och logistik av CS50. Davon: Ja, hej, grabbar. Du kommer att se en hel del till mig på kontorstid. Jag kommer att undervisa sektioner. Och om du skjuter e-post i förväg, Jag kommer förmodligen att svara. Så jag får se massor av er alla termin. Och välkommen till CS50. DAVID J. MALAN: Och nu Gabriel, som själv var bara en nybörjare i fjol, men för de senaste åren har varit verksamma sin egen version av CS50 i Brasilien, där han hämtat alla kursens content-- vilket är klart att filmas och placerades online-- så att han kunde översätta det till Portugisiska och sedan lära mer än 100 av hans klasskamrater över loppet av ett par år, undervisning på sitt modersmål kursens läroplan. GABRIEL: Hej. [Applåder] GABRIEL: Hej, jag är Gabriel. Jag är chef TF av kursen. Och jag hoppas att du kommer att älska CS50. Detta är CS50. DAVID J. MALAN: Nu till Rob. Åh, vill införa? ROB: Nej, jag vet inte. [LAUGHTER] DAVID J. MALAN: Och Rob Boden. [LAUGHTER] ROB: Hej, jag är Rob. Det här är mitt femte år involverad i kursen. Varje år är det bara en bättre och bättre klass, så ni är helt klart kommer att bli häftigt. Jag hoppas att ni alla har kul med det. Jag ska ha kul med det. Så se dig omkring. DAVID J. MALAN: Och tiden tillåter inte oss-- [Applåder] Tiden kommer inte att tillåta oss att införa alla på scenen och alla deras kolleger som är shopping klasser idag. Men låt mig presentera Belinda och CS50 pussel Dag som väntar här kommande lördag, vilket är den första av den kursens storskaliga evenemang. Här en särskilt avsedd att hamra hem poängen att datavetenskap är ytterst inte om programmering, utan snarare om problemlösning i allmänhet. Och Puzzle Day, som du kommer se, kommer att ge dig och dina klasskamrater together-- Vi hoppas nu på lördag. BELINDA: OK. Hej, grabbar. Så tack. Så som vår illustra kapten sa, jag heter Belinda. Jag är en sophomore på Quincy House. Jag, precis som ni, tog CS50 förra året, verkligen älskade det. Jag har en soft spot för er i den tredje raden. Och jag är stolt att säga, jag är nu i en engagerad relation med CS50 [ohörbart]. OK. Det var min lama version av ett skämt. Hur som helst, så vi går vidare, ville bara bjuda in ni alla till i-lab eller HBS nässelutslag. Vi kommer att ha Puzzle dag från 12:00 till 03:00. Och det är en stor möjlighet för dig killar att möta dina kolleger CS vänner, lösa några icke-CS pussel, som kapten nämnts, och även äta lite gratis mat, tjäna några enorma vinster, som presentkort, $ 75 per person, och also-- vad var det? Wii U eller något? Wii U? Ja. För vår lotteri. Toppen. Så jag ska stanna kvar efter lektionen. Och om ni har någon frågor, låt mig veta. DAVID J. MALAN: Och du kommer att se, bortom här finns det ingenting att göra idag. Det första problemet set kommer att gå ut fredag. Men för att ta oss hem i dag, skulle jag vilja presentera dig för specifikt ytterligare anställd, Colton Ogden här, vars händer är nu skyddade ovanför dig med denna MIDI-controller att hamra hem poängen ytterligare att datavetenskap, också, har tillämplighet långt utanför ingenjörs och STEM och datavetenskap i sig, sträcker sig även till sådana områden som musik. Colton har vänligt offered-- jag trodde en av dem var på väg att låsa fokus. Andrew, om vi kunde kalla fokus över för bara en stund här. Vad Colton har gjort i förväg är programmet denna enhet, denna pad knappar som du ser på bilden här uppe, som en MIDI-controller, varvid var och en av dessa knappar är kopplad till en viss musikalisk anteckna eller ett ljud, mer allmänt en inspelning, så att genom att spela mönster av dessa knappar, ungefär som mönster av bitar, kan representera andra koncept på högre nivå. Kommer han att kunna slutligen att ta oss hem här i dag? Utan vidare, om vi kunde dämpa belysningen, och slå på skärmen bakom Colton. PUBLIK: Woo! DAVID J. MALAN: Detta är CS50. [MUSIK SPELA] [Applåder] Det var allt för CS50. Vi kommer att se dig fredag. Någon kaka väntar dig i tvärskeppet. [MUSIK SPELA]