[Musik Spela] [MUSIK - Rossini "Ranz DES Vaches "från William Tell] [MUSIK - DEN ENGELSKA BEAT, "MARS AV vridbara huvuden "] [Applåder och jublar] DAVID MALAN: Så detta är CS50. Mitt namn är David Malan. Och 73% av er har någon tidigare erfarenhet med datavetenskap, i motsats till vad du kanske tror. Så idag har vi trodde vi skulle nagga på att bristande kunskaper, men också ger dig en känsla av, för de av er med mer komfort, vilka riktningar du kan gå den här terminen. Så låt oss börja med det här. Jag har verkligen ingen aning om vad som finns inuti en dator, även om, som du, jag använder den varje dag. Men det är någon form av låda, och det finns inte många ingångar i den. Minimalt, det finns, vad? Förmodligen en strömkabel. Och faktiskt med denna ingrediens, el, tycks vi vara i stånd att gör ganska lite i dessa dagar. Men i slutet av dagen, vi måste representera saker att vi bryr oss om. Vi måste representera information i någon form. Och du förmodligen åtminstone vagt förtrogen med idén genom binär eller bitar eller annat sätt, datorer reduceras till ettor och nollor. Men kan vi omfamna det och minst sätta lite ljus på det? Så jag har dessa små skrivbordslampor här. Jag har ett eluttag här. Och jag kommer att föreslå att insidan min dator är åtminstone en av dessa saker, något som kan av slås på eller av. I detta fall är det verkligen en skrivbordslampa, men på lägre nivå, är det något kallas en transistor. Men i vår värld, det är en skrivbordslampa, så Jag ska gå vidare och koppla detta i min el här. Och jag hävdar att med hjälp av denna enkla, enkel anordning, denna enkla omkopplare, jag kan representera information. Till exempel, just nu är jag representerar någonting, rätt? Jag representerar vad jag ska kalla 0 eller falskt, motsatsen till något faktiskt är närvarande. Men om jag bara vända denna switch, Nu har jag representerade en 1. Så med hjälp av denna mycket enkel bit av minne, om du vill, kan jag företräder information. Nu tyvärr, min dator kan inte göra så mycket. Den kan endast representera två värden i hela världen - 0 eller 1. Men vad är en självklar lösning, nu, om vi vill utöka vår dator minne och utgör mer än bara 0 och 1? Nåväl, låt oss ta en annan sådan bit. Låt oss ta en annan switch, en annan transistor, men du vill tänka på det. Låt mig gå vidare och koppla detta in i min dator också. Och jag kommer att hävda, nu, att genom med lite mer el och vända mer av dessa växlar på och off, kan jag representera fler sådana information. Så just nu är det 1. Om jag vill nu representera 2, kan jag göra det här. Men typiskt, konvent, som vi kommer småningom se, kommer att få mig att göra det här. Så det här är 0, är ​​detta 1. Detta skulle vara 2. Och inte helt oväntat, skulle detta vara 3. Så på detta sätt, fortfarande kan Vi räknar upp ytterligare? Om jag får en tredje bit, en tredje omkopplare, vad är det högsta antalet jag kan nu räkna upp till från 0? Så 7 om jag börjar på 0, eller hur? För om jag slår detta ljus på och faktiskt plugga denna tredje och sista ljus i mitt eluttag här, då jag har förmågan att representera någon av två värden här, två värden här, två värden här - och så jag kan representera 2 gånger 2 gånger 2, eller åtta möjliga värden. Och om jag börjar redovisning till 0, så det är 0, 1, 2, 3, 4, 5, 6, 7. Så här binära. Det är verkligen så enkelt är det. Och jag skulle hävda att detta är faktiskt ganska bekant för de flesta alla i det här rummet. Låt mig gå vidare och öppna en liten textredigerare här. Och ni kanske minns från grundskolan att vi hade saker som de hundratals plats, det tiotals plats, och de som plats. Och minns att om du hade någon decimal nummer, som något slumpmässigt som 123, skulle du huvudsakligen skriva ut det i form av dessa tre kolumner. Och varför är 1, 2, 3 vad vi känner som 123? Tja, i kolumnen längst till vänster, har vi en 100 plus två 10s, så det är 120, plus tre 1s, så det är 123. Nu är denna värld som vi bara upplyst är exakt samma som du har varit bekant med i flera år, utom nu, våra kolumner är inte befogenheter 10. De är bara befogenheter 2. Så medan det är ettor plats, detta kommer att bli den tvåor plats, är detta kommer att bli fyra plats. Och eftersom jag bara använder den enklaste av mekanismer för att vända saker av och på - el flödar eller el inte flyter - Jag förstår inte riktigt har samma uttrycksfulla intervall som 0 till nio. Vi kommer att hålla det super enkelt i denna värld av datorer. Jag har bara 0 eller 1 - av eller på, falska eller sanna. Och så vad jag företräder just nu är 1, 1, 1, eftersom var och en av dessa lamporna lyser. Tja, ger det mig en 4 plus en 2, så det är 6, plus en 1, och det är 7. Och ergo gör denna sekvens av tre bitar representerar numret 7. Så all denna tid, insidan av din dator, har ett antal transistorer, varje antal bitar. Men i slutet av dagen, vi kan representera information så enkelt är det. Nu tyvärr har vi bara räknas upp till 7 i CS50 hittills, men förhoppningsvis kan vi göra en lite bättre än så. Och faktiskt vi kan. Antag att vi som människor bara godtyckligt bestämt att vi ska att associera siffror som 1 och 2, 3, 4, 5, 6, 7, med specifika bokstäver i alfabetet. Och av historiska skäl, kommer jag att starta något godtyckligt, men jag är kommer att säga, människor, kommer vi att besluta som standard, globalt, att 65 representerar antalet bokstaven A. 66 kommer att representera B. Dot, prick, prick. 90 kommer att representera bokstaven Z. Och låt oss anta, om vi verkligen sätta några trodde in i det, kan vi komma upp med siffror för utropstecken och gemener, och faktiskt, andra människor har gjort det för oss. Så nu hade vi bitar som vi kan representera siffror, siffror som Vi kan representera bokstäver, och med bokstäver kan vi nu börja komponera e-post och karaktärer utskrift på skärmen. Så låt mig bjuda, om jag kunde, åtta modiga frivilliga - som inte har något emot visas inte bara på kameran men på internet - att komma upp hit och representerar åtta sådana bitar, snarare än dessa tre. Så vad sägs om en, två? Vad sägs om tre? Vad sägs om fyra i ljuset blått, fem på slutet? Om någon hit? Sex i fronten, sju framme, och åtta framme, liksom. Så jag bara så råkade komma förberedd med en hel massa papperslappar. Och på dessa lappar är siffror som representerar vad kolumner ni kommer att representera. Så du kommer att vara - vad är ditt namn? STUDENT: Anna Leah. DAVID MALAN: Anna Leah, du kommer att vara den 128S kolonnen. Du är? STUDENT: Chris. DAVID MALAN: Chris kommer vara den 64s kolonnen. Du är? STUDENT: Dan. DAVID MALAN: Dan kommer vara den 32s kolonnen. STUDENT: Pramit. DAVID MALAN: Pramit kommer vara den 16s kolumnen. STUDENT: Lillian. DAVID MALAN: Lillian blir 8s. STUDENT: Jill. DAVID MALAN: Jill kommer vara den 4s kolonnen. STUDENT: Mary. DAVID MALAN: Mary blir 2s, och? STUDENT: David. DAVID MALAN: David kommer vara den 1s kolonnen. Så om ni kunde steg lite framåt så att alla kan se. Vad ni inte ser är att på baksidan av dessa papperslappar är en liten fusklapp som handlar om att instruera dessa åtta bitar till endera räcka upp handen eller inte räcka upp handen. Om handen går upp, de är som representerar en 1. Om deras hand stannar nere, de är representerar en 0. Under tiden vi publiken bör vara kunna räkna ut, baserat på denna kartläggning, vad tre bokstäver ord dessa folk är på väg att precisera. Så på bara ett ögonblick, du kommer att läs den första raden på baksidan av din lathund, och du är antingen kommer att höja eller inte höja handen. Om du är en 1, höjer du, om du är en 0, står du där tafatt, precis sådär. Go. Vilket nummer, först och främst, är dessa killar som företräder? 66. 66, eller hur? Vi har en 1 i 64s kolumnen en en i 2s kolumnen. Det ger mig 66, så som visas att representera B. Så ni har stavat - OK, det räcker. B. Så nu ska vi gå vidare vår andra brev. Go. Vem är snabbast på matte här? Så 79. Återigen, om vi lägger upp alla kolumner där det finns en 1, för närvarande, bara som vi gjorde tidigare med den enklaste exempel på 7, nu har vi få nummer 79. Som enligt våra mappning är den bokstaven O. Så vi är nästan där. B, O. Och slutligen, går. Vad de representerar nu? Mindre konsensus. Det är bara en absolut blåsljud. Ja, det är i själva verket 87. Bra. Så om vi nu kartlägga den tillbaka upp till - låt oss börja ringa vår ASCII kartlägger, American Standard Code för Information Interchange. Det ger oss brevet - inte "bo" men "båge." Och det är en perfekt cue för er att ta en båge och huvud på baksidan. Tack så mycket. [Applåder] DAVID MALAN: Du kan behålla dem. Fast egentligen, skulle någon som en skrivbordslampa, också? [DYFT av publiken] DAVID MALAN: Skrivbordslampa? [SKRATT] DAVID MALAN: Verkligen? Bordslampor för alla? Okej. Så börja med det allra enklaste av principer, har vi nu inte bara räknade upp från 0 ända upp till 7, har vi antas att bara genom att kasta mer bitar eller mer ljus eller fler transistorer på detta problem, kan vi representerar större och större siffror, och ergo, större och större serier av alfabet, som engelska. Och låt oss ta på tro för dag som på liknande sätt kan vi börja representera grafik och video samt eventuella antal andra medier med vilka vi är bekant idag. Så detta är CS50, och i denna klass vid sidan av er är, återigen, väldigt många klasskamrater som har så lite upplevelse som du. Och jag nämner detta bara för att helt ofta, bland annat så sent som en av förstaårselev rådgivning händelser och vid vårens sophomore rådgivning händelse, hör vi ofta studenter friskriver när man kommer upp till CS bordet, väl, Jag har funderat på att ta detta intro klass, men jag är inte riktigt en dator person. Eller, men alla säkert vet mer än mig. Och jag sätta detta i största teckensnittet möjligt, för att förmedla detta budskap som det är faktiskt inte fallet. Och om du undrar, bör Jag, faktiskt, vara här? Inse att det inte bara är den här kursen är Titel Introduction to Computer Vetenskap är det Introduktion till dator Science I. Så det finns faktiskt en andra sådan introduktion. Så du är inte, i själva verket, på fel ställe. Och bland de mål jag har för idag är att mildra sådana problem du kan ha, men även att måla en bild av vad som väntar för eleverna mindre och mer bekväm likadana i denna kurs. Men först ett ord på en av åhörarkopior du har idag, bland vilka finns ett antal frågor. Det har varit en vision av vår för en tid nu att införa ett nytt betygssystem Alternativet till denna kurs - nämligen, SAT / UNSAT. Filosofiskt för mig, är det mycket mycket, mycket viktigt att elever i denna klass ingrepp med material, ifrågasättas av material, och oroa dig långt, långt mindre om mekaniken i verkliga poängen och bokstavsbetyg vid terminens slut, men verkligen omfamna kursen och dess material. Och verkligen detta känns, mer allmänt, för vad som är intressant för dem, att känner sig utmanade och belönas, men utan rädsla för att misslyckas. Och faktiskt, är detta också en återkommande Temat i denna och andra inledande kurser inom andra områden, som du har denna bävan när det kommer till sätta sina tår i okänt vatten. Jag själv, redan 1995, var en freshman. Jag var väldigt fokuserad på att vara en Gov koncentrator här. Och ändå skulle jag alltid växt upp med en bit av ett intresse för datavetenskap. Jag var alltid nyfiken. Men då, även hade jag denna rädsla för ens sätta foten i CS50, så mycket så att jag inte ens handla det första år. Och den enda anledningen till att jag sätter en fot i Dörren andraårsstuderandeår var eftersom jag fick ta den godkänd / underkänd. Men även godkänt / underkänt krävs att jag får upp modet att boka tid med professor Kernehan på tiden, föra detta stora pappersark, och be honom för hans namnteckning och tillåtelse att utforska dessa obekanta vatten. Och det har inte hjälpt de senaste åren att när du gör detta i CS50, när vi brukade vara godkänt / underkänt, på liknande sätt skulle tiotals eller hundratals dina klasskamrater måste komma upp, Gud förbjude, vid framför Sanders med denna form, som i vissa sinnen representerar en oförmåga, Jag vågar påstå, att utföra är dina kamrater nivå. Vilket är löjligt, men jag tror finns det där mentalitet. Och det har aldrig varit i denna kultur av SAT / UNSAT eller godkänd / underkänd mer allmänhet, i denna kurs, eller egentligen på detta campus. Så i år har vi ändrat det. Jag skulle vara överlycklig hälften av denna klass eller fler avslutade upp att ta CS50 SAT / UNSAT. Under ett års tid, skulle det vara underbart om nästan alla är. Därefter kanske vi ska arbeta på bokstavsbetyg vid Harvard College mer generellt. Men för nu, vi gör detta inom vårt egen sfär, och jag vill varmt uppmanar dig att granska dessa frågor och ställa frågor som du tycker passar, så att Förhoppningsvis har du, till skillnad från mig, kommer inte riktigt har samma rädsla faktor när utforska vad som är nog en obekant plats. Så vad är CS50? Det är en introduktion till intellektuella företag av dator vetenskap och konsten att programmeringen. Men vad betyder det egentligen? Tja, hittills, vi pratade mycket kortfattat om motsvarande information. Men anta att vi faktiskt vill att göra något med det. Vi måste införa begreppet vad vi kallar en algoritm. En algoritm är ett förfarande, en process, en uppsättning instruktioner för göra något. Och en algoritm kan vara något super enkelt. Till exempel kan ett exempel med vilka vissa av er kanske känner är här sak här. Så denna bok här är allt daterat, men en gång i tiden, det innehöll en hel del namn och telefonnummer. Och faktiskt, om jag ville hitta någon i denna telefonbok - säga, någon som heter Mike Smith - Jag kunde hitta Mike Smith i valfritt antal av ganska enkla sätt. Jag kunde börja från början och gå vidare till sida 1, inte där. Sidan 2, inte där. Page 3. Är det algoritm, är att processen, korrekt? Så det är rätt, eller hur? Jag är typ av en idiot för att göra det i detta sätt, men så småningom kommer jag hitta efternamnet S, och förhoppningsvis Mike är i detta avsnitt, och jag kommer att bli gjort med min algoritm. Men säkert är det inte intuitivt. Mest varje rimlig människa i detta rum skulle inte ha gjort det. Vad skulle du ha gjort? Du skulle ha gått rakt till mitten, höger? Ungefär i mitten. Och du inser, åh, dessa är Ms Så Mike Smith, efternamn som Smith, är inte helt klart, sedan i vänstra halvan av boken. Han måste ligga mot S finns i höger. Och på denna punkt, även om de flesta av oss gör inte detta i verkligheten, kan vi bokstavligen riva detta problem i hälften. [Jublar och applåder] DAVID MALAN: Tack. [Jublar och applåder] DAVID MALAN: Du kan bokstavligen riva denna problem i hälften, lämnar mig med, bokstavligen, ett problem hälften så stor. Så om detta telefonbok var - och det förmodligen var - ungefär 1.000 sidor, nu det är bara 500. Om jag gör det igen, och jag inser, åh, fan, jag gick för långt, jag är i Ts avsnitt, kan jag på samma sätt - bildligt eller bokstavligt - rippa telefonboken - det var faktiskt mycket lättare då. Jag kan bokstavligen slita telefonboken på mitten, lämnar mig nu med inte 1000, inte 500 - 250 sidor. Och jag kan gå 125, och hälften av detta, och hälften av det, och hälften av denna, tills jag slutligen ska lämnas med bara en enda sida. [SKRATT] DAVID MALAN: Det är del jag misslyckas på. En enda sida där Mike är förhoppningsvis. Nu dessa olika algoritmer kan vara sorts bedömda eller utvärderade i olika sätt. Den första var väldigt linjär, rätt? Vänd sida, leta efter Mike. Vänd sida, leta efter Mike. Det är väldigt linjärt. Om det finns ytterligare en sida i telefonen bok, det kommer nog att ta mig en sekund till, en enhet av tid, men vi beräknar tiden. Så jag kan dra så här denna linje här, varigenom som storleken på den problemet ökar från vänster till höger - telefonboken blir mindre till större - och tiden kommer att öka på den vertikala axeln, desto större telefonboken är. Så n är bara en allmän variabel som datavetare använder för att representera visst värde, vissa nummer. Så n kommer att öka linjärt. Fördubbla storleken på telefonboken, är det kommer att ta mig dubbelt så mycket tid, mest troligt, att hitta Mike. Nu kunde jag ha varit smarta om det här, eller hur? Jag började bli uttråkad snabbt. Kunde ha gjort detta genom tvåor. Så två sidor, sedan fyra, sedan sex, sedan åtta. Och jag kunde börja flyga igenom det en lite snabbare, om än med mindre risk för överskridande Mike, men denna kurva är inte kommer att bli så annorlunda. Det kommer fortfarande att vara en rak linje, men något snabbare. Men vad gjorde jag? Jag gjorde faktiskt något fundamentalt bättre. Jag uppnådde vad vi kallar logaritmisk tid, log n, varvid denna gröna linje har en mycket, mycket, mycket mindre rak kant till den. Och snarare antyder det, eftersom det sorterar av närmar sig oändligheten någonsin så småningom, att jag faktiskt kunde ta en 1.000-sida telefonbok, fördubbla sin storlek nästa år - eftersom antar en hel fler människor flyttar in till stan. Så nu har jag 2.000 sidor, men hur många fler steg är att smartare algoritm kommer att ta? Bara en. Jag menar, det är en mäktig sak. Om vi ​​går till 4.000 sidor nästa år, som kommer att ta mig bara två steg. Så du kan kasta större och större problem på mig, inte olikt banan är kasta allt större problem varje dag på Googles och Facebooks av världen, och det är inte en så stor sak. Eftersom jag lägga mer tanke och omsorg i min algoritm som att lösa problemen snabbt och effektivt. Och faktiskt, kommer att bli en av målen för denna kurs. Du kommer, längs vägen, lära sig att programmera. Du får lära dig att programmera in valfritt antal språk. Men i slutet av dagen, är kursen om att lösa problem och att få bättre på att lösa problem - och, som i fall som detta, lösa problem mer effektivt. Nu så här långt, har vi gjort det här ganska intuitivt. Låt oss införa något rättvist generiskt kallas pseudokod. Så vi ska så småningom komma, i denna kurs, till olika programmeringsspråk. Men idag ska vi göra det på engelska-liknande syntax, där du bara typ av säg vad du menar, men du är aldrig så koncis och du inte oroa grammatik och fullständiga meningar. Du uttrycker precis själv som kortfattat som möjligt. Så pseudokod är engelska-liknande syntax som representerar ett programmeringsspråk. Och mot detta syfte, låt mig föreslå att Vi modellerar nu den process vi just beskrivs att räkna något lite annorlunda, den här gången med en titta på detta producerade fem-minuters video av våra vänner på TED som definierar vad pseudokod är, definierar vad algoritmisk tänkande är, och även Även om exemplet du ska se är, i sig själv, super enkelt, det är kommer att börja ge oss den mentala modell, vokabulären, som att göra mycket, mycket mer komplex algoritmer ganska snabbt. [BEGIN VIDEOAVSPELNING] [Musik Spela] Berättare: Vad är en algoritm? I datavetenskap är en algoritm en uppsättning instruktioner för att lösa vissa problem steg för steg. Typiskt är algoritmer exekveras av datorer, men vi människor har algoritmer, liksom. Till exempel, hur skulle du gå om att räkna antalet av personer i ett rum? Tja, om du är som jag, skulle du förmodligen punkt vid varje person, en vid en gång, och räknar upp från 0. 1, 2, 3, 4, och så vidare. Tja, det är en algoritm. I själva verket, låt oss försöka uttrycka det en lite mer formellt i pseudokod - Engelsk-liknande syntax som liknar ett programmeringsspråk. Låt N är lika med 0. För varje person i rummet, ställ N till N plus ett. Hur man ska tolka denna pseudokod? Tja, linje ett förklarar, så att säga, en variabel som heter N och initierar dess värde till 0. Det betyder bara att i början av vår algoritm, den saken som rknar har ett värde av 0. Efter allt, innan vi börjar räkna, Vi har inte räknat något ännu. Kalla denna variabel N är bara en konvention. Jag kunde ha kallat det mesta någonting. Nu line två avgränsar början på en loop, en sekvens av steg som upprepa några antal gånger. Så i vårt exempel, det steg vi tar räknar människor i rummet. Under ledning två är linje tre, som beskriver exakt hur vi ska gå om att räkna. Fördjupningen innebär att det är Rad tre som kommer att upprepa. Så vad pseudokoden säger är att efter början på 0, för varje person i rummet, vi öka N med 1. Nu är den här algoritmen korrekt? Nåväl, låt oss bang på det lite. Fungerar det om det finns två personer i rummet? Låt oss se. I linje ett, initiera vi N till 0. För var och en av dessa två personer, vi öka då N med 1. Så på den första resan genom loop, uppdaterar vi N från 0 till 1. Den andra resan genom samma loop, uppdaterar vi N från 1 till 2. Och så genom denna algoritm slut, n är 2, som passar faktiskt antalet personer i rummet. Så långt är allt väl. Vad sägs om ett hörn fall, men? Antag att det finns 0 personer i rummet - förutom mig, vem som gör rösträkningen. I linje ett, initiera vi N till 0. Men den här gången, inte linje tre inte exekvera alls eftersom det inte finns en personen i rummet. Och så N är 0, vilket motsvarar Antalet personer i rummet. Ganska enkelt, eller hur? Men räknar människor en i taget är ganska ineffektivt, också, nej? Visst vi kan göra bättre. Varför inte räkna två personer på en gång? Istället för att räkna 1, 2, 3, 4, 5, 6, 7, 8, och så vidare, varför inte räkna, 2, 4, 6, 8, och så vidare? Det låter ännu snabbare, och det är säkert. Låt oss uttrycka denna optimering i pseudokod. Låt N är lika med 0. För varje par av människor i rummet, ställa N lika med N plus 2. Ganska enkel förändring, eller hur? Snarare än räkna människor en vid en tidpunkt, räknar vi istället dem två åt gången. Denna algoritm är alltså dubbelt lika snabbt som den sista. Men är det korrekt? Låt oss se. Fungerar det om det finns två personer i rummet? I linje ett, initiera vi N till 0. För att ett par personer, vi öka då N med två. Och så genom denna algoritm slut, är N 2, som passar faktiskt antalet personer i rummet. Antag därefter att det finns 0 personer i rummet. I linje ett, initiera vi N till 0. Som tidigare, inte köra linje tre inte alls, eftersom det inte finns några par av människor i rummet. Och så N är 0, vilket faktiskt stämmer med antalet personer i rummet. Men tänk om det finns tre människor i rummet? Hur fungerar denna algoritm biljettpriset? Låt oss se. I linje ett, initiera vi N till 0. För ett par av dessa människor, vi öka då N med 2. Men sen då? Det finns inte en annan fullständig par människor i rummet, så att linje två nej längre gäller. Och så av denna algoritm slut, N är fortfarande 2, vilket inte är korrekt. I själva verket är denna algoritm sägs vara buggy, eftersom det har ett misstag. Låter upprättelse med några nya pseudokod. Låt n är lika med 0 för varje par människor i rummet. Ställ N till N plus 2. Om en person fortfarande oparade, ställa N lika med N plus ett. För att lösa detta problem, har vi infördes, i linje fyra, en tillstånd, annars känd som en filial som körs bara om det finns en person som vi inte kunde par med en annan. Och så nu, om det är en eller tre eller varje udda antal människor i rummet, denna algoritm kommer nu att räkna dem. Kan vi göra ännu bättre? Tja, kunde vi räkna in 3s eller 4s eller ens 5s och 10s, men utöver det, är det kommer att få en liten bit svårt att peka. Vid slutet av dagen, oavsett om det av datorer eller människor, algoritmer är bara en uppsättning av instruktioner med som att lösa problem. Dessa var bara tre. Vilka problem skulle du lösa med en algoritm? [END VIDEOAVSPELNING] DAVID MALAN: Det är den enda gången Jag kommer att visas i tecknad bildar. Men var den historien tar slut, nu, hur kan vi göra bättre? Treor och fyror, vi hävdar, att vi kan räkna människor mycket snabbare, men det kan vi gör grunden bättre än så? Och jag satsar vi kan. Om vi ​​inför lite av vår egen pseudokod här, kommer jag att föreslå att vi kan åstadkomma en rad som denna. Vi kommer inte att räkna människor ett, två, tre, fyra. Vi kommer inte att gå två, fyra, sex, åtta. Vi kommer att göra fundamentalt bättre genom att ändra på problemet, och i detta fall utnyttja en annars underutnyttjad resurs. På bara ett ögonblick, jag hoppas att du ska förlåta och humor oss genom att stå upp i plats, då vi kommer att ber var och en av er att ta på i din sinnen numret 1. Du sedan gå till allt olyckligt, eftersom tiden går, hitta någon annan som står, kombinera dina siffror tillsammans genom att lägga upp dem. En av er sedan kommer att tävla för att sitta ner först, och den andra personen kommer att upprepa. Så med andra ord, genom ympning alla du med nummer 1, och därefter kombinera dem 1s i 2s och dessa 2s till 4s, med alla allt sitter ned, bör vi, vid slutet av denna algoritm, har bara ett lån själ som inte sitta ner tillräckligt snabbt men som har hela publik räkna i hans eller hennes sinne. Så om ni vill, låt oss gå vidare och - steg ett - stå upp på plats. Och köra. [Publiken sorlande] DAVID MALAN: Vet du där Lauren är? 729? [Publiken sorlande] DAVID MALAN: Okej? [Publiken sorlande] DAVID MALAN: Okej, ska vi vara närmar sig slutet. Vi ser en karl står här fortfarande. Vem behöver annat att paras ihop? Om ni vill para sig. Någon där uppe. Varför inte jag låna ut en hand här. För de mycket få människor som fortfarande stående, vilka nummer gör du har i ditt sinne? STUDENT: 78. DAVID MALAN: 78 plus - vem står här nere? STUDENTEN 39. DAVID MALAN: Plus 39. Plus vem står fortfarande? 81? OK, vem annars? En annan 81? Wow. Och vad är i ryggen? STUDENT: 49. DAVID MALAN: 49, plus? STUDENT: 98. DAVID MALAN: 98 plus? Är det någon annan? 12? Bra jobbat. [SKRATT] DAVID MALAN: Åh, 112 - oh. Bra jobbat! [SKRATT] [Applåder] DAVID MALAN: Någon annan kvar? Förlåt? STUDENT: 99. DAVID MALAN: 99. Någon annan står stilla? Och det totala antalet studenter här är faktiskt, enligt - har du ett nummer? Åh, det faktiska antalet personer i rum, enligt det konto som undervisningen kamrater gjorde på allas sätt, var 729. Så ur ett rum fullt av Harvard studenter som räknade sig själva, Svaret är 637. [SKRATT] DAVID MALAN: Så nära. Men ändå. OK, är så att en undervisning ögonblick, eller hur? Detta är nu vad vi beskriver som en bugg. Någonstans på vägen, gjorde vi några aritmetiska fel, eller någon satt sig ned, eller vänster, eller något gick fel. Men det är bra. Eftersom även fortfarande, vi fick ganska nära. Och jag skulle hävda att vi fick fel svarar mycket snabbare än jag skulle ha använda min mer linjära metoden. Så låt oss anta att vi fick faktiskt komma att korrigera, men tänk nu på vad hände varje gång, jämfört med min egen naiva pekar algoritm. Ett, två, tre. Om det finns faktiskt 729 eller 637 personer Här skulle det ha tagit mig bokstavligen 637 eller 729 Pointings hos fingret och uppräkning min totala räkningen. Och jag kunde göra lite bättre genom kommer två, fyra, sex, åtta, och dubbla den hastigheten, kanske till och med tredubbla eller fyrdubbla, beroende på hur väl jag kan gör att räkna i huvudet. Men detta synsätt som ni tog var fundamentalt annorlunda. Eftersom i början, ni alla stod upp. Så alla 729. Och sedan bokstavligen halva av er satt. Och efter det, en annan hälften av er satte sig ner. Och efter det, en annan hälften av er satte sig ner. Och det totala antalet gånger som du killar kunde ha satt ner är ungefär åtta eller nio eller tio totalt tider, beroende på vad vår totala antal är. Och vi kan sortera om göra detta på annat sätt. Om vi ​​hade 1024 personer i rummet, det totala antalet gånger du kan halvera 1.024 personer är 10. Nu tänker på det i den andra riktningen. Antag, löjligt, att vi hade, säger fyra miljarder människor i det här rummet, eller ett något större rum. Hur många gånger skulle vi ha gått genom denna algoritm, så att halv av den klassen sätter sig? Det kommer bara att ta 32 sådana verksamhet, även i en klass av storlek fyra miljarder. Varför? Eftersom fyra miljarder går till två miljarder, går till en miljon, går till 500 miljoner går till 250 miljoner, pricka, pricka, pricka. Jag kan bara göra denna delning del 32 gånger, vid vilken punkt, alla utom en person skulle stå kvar. Och det är också en slags kraftfull tanken att allt vi ska försöka inflytande i den här kursen, och i programmering och datalogi mer allmänhet, dessa bakterier av en idé med som vi sedan kan lösa problem mycket, mycket mer kraftfullt. Så vi började ganska enkelt med den pseudokod och en kille i ett rum, men nu med ett helt rum fullt av människor har vi gjort fundamentalt bättre. Nåväl, låt oss nu övergången från pseudokod till några faktiska koden. Detta språk du ska se hända att kallas JavaScript, och Vi ska återkomma till detta mot terminens slut. Det är ett programmeringsspråk som du använder för att göra hemsidor och andra sådana programvara dessa dagar. Och vi har använt det, tack vare en vän av vårt på Stanford, för att koda någon dold information här. Detta är konsten att steganografi, så att säga, där man kan gömma informationen i vad som annars tycks vara brus eller en helt annan bild helt och hållet. Men inbäddad i viss bild är verkligen ett hemligt meddelande av slag. Så låt mig gå vidare och dra upp samma bild här, detta tid i en webbläsare. Och jag kommer att vinka min hand på några av detaljerna för i dag, särskilt för er som det ser ut inte bara JavaScript utan grekiska, som en helt obekant språk. Men detta är ett exempel på ett programmeringsspråk. Och för nu, ta på tron ​​att denna första kodrad - och genom kod, menar jag bara text. Text som jag bokstavligen kunde ha skrivit i Microsoft Word, om jag hade rätt programvara för att sedan göra något med det. Programmering källkod, programmering kod, är egentligen bara text, och det ser annorlunda baserat på vilket språk du använder, inte olikt engelska och Spanska och ryska alla ser olika ut när du skriver dem på tangentbordet. Så denna första raden, för nu tar på tro, bara öppnar en bild från internet, att bullriga grafiskt vi såg bara. Denna nästa linje är här ett exempel på en loop, och vi såg faktiskt samma jargong i TED-video. En slinga är något som händer igen och igen, och även om detta absolut ser kryptisk, med nyckelordet för, och några parenteser, och vissa semikolon. Vi ska återkomma till detta inom kort, men att slinga det i huvudsak är träffande programmet, iterera över alla av dessa bullriga prickar, från vänster till höger, uppifrån och ned. Eftersom vid slutet av dagen, en bild gillar det här - och du kan faktiskt typ av se det på denna projektor - är egentligen bara ett rutnät av punkter. Så vi kan identifiera var och en av dessa punkter av en koordinat, x, y, och med denna program, kan vi nu börja göra något för dessa punkter. Så vad jag ska gå vidare här och vet är jag ska göra några ändringar. Först kommer jag att gå vidare och bli av allt detta grönaktigt och blåaktig buller, och jag kommer att gå vidare och skriv in följande visserligen kryptisk syntax. im för bilden. set blå på plats x, kommatecken, läge y, till 0. Med andra ord, jag vill bara stänga av alla de blå prickar i den bilden. Jag ska gå vidare nu och klicka detta Run / Spara-knappen, och du kommer märke på höger sida, den resulterande bilden visas. Nu är det super grönt, men det är inte överraskande, eftersom jag bokstavligen vände rabatt, genom att göra en 1 a 0, alla den blå i den bilden. Nåväl, nu ska vi göra det lite mer. im för image, dot setGreen, x, y. Och det betyder bara iterate från vänster till höger och sedan uppifrån och ned. Stäng av det där med ett värde av 0, liksom. Spara. Och på projektorn, kan du inte faktiskt verkligen se någonting alls. På min laptop skärm, om jag kisar i just på rätt sätt, kan jag se en bit av en bild, eftersom de fortfarande är lite rött i det. Om du någonsin har hört förkortningen RGB - röd, grön, blå - det hänvisar till denna komposition av en bild med hjälp bara de tre färgerna. Och just nu har vi kastat bort allt grönt, alla blå, men det finns inte mycket rött. Så låt mig skruva upp det röda. Hur kan jag göra det? Tja, först, jag ska be detta program en fråga. Jag ska gå vidare och låt oss kalla det en variabel, precis som i algebra. Du kan ha x eller y eller z. Jag kommer att deklarera en variabel och säga, sätta in denna variabel, temporärt, värdet av den bilder getRed värde på x, y. Och igen, ska vi komma tillbaka till alla av denna detalj i framtiden. Men för nu, bara ta på tron ​​att denna linje frågar programmet, vad är det röda värdet på x, y? På just den punkten? Sedan kommer jag att göra något för det. Sedan kommer jag att göra bilden dot set röd på x, y, y, men den här gången kommer jag att öka den genom att göra röda tider, låt oss säga, 10. Så öka det med en faktor på 10. Låt mig zooma ut nu och Klicka kunde springa / Spara. Och voila, det var det hela tid, även om våra mänskliga ögon kunde inte riktigt se det. Så återigen, detta är nu riktiga koden, en exempel på ett språk som vi kommer tillbaka innan lång. Men inse, särskilt de av er utan sådan erfarenhet, är det ganska snart att vi själva kommer att vara skriva kod sånt där. I själva verket, ett verktyg med vilket du kan uppleva alla något bekant, kanske, är CS50: s egen kurs-shopping-verktyg, vilket var faktiskt startas denna sommar med några av CS50 egna tidigare studenter, nu vända TF. Så det här råkar vara en hemsida byggd på ett språk som kallas PHP. Den använder en databas som kallas MySQL, saker med vilken vi får våra händer smutsiga senare under terminen. Men tro det eller ej, även något Gillar du slutligen minskar till enklaste av loopar och villkor och grenar, som de vi såg bara en nyss i TED-video. Vad jag trodde jag skulle göra nu är aktien inte bara något vi personalen har gjort för campus, utan snarare något en före detta student - tre studenter, faktiskt - gjort det senaste året, Sierra, Daniel, och Sam, den sista av dem hade ingen tidigare programmering erfarenhet när han tog CS50. Och för deras sista projekt, de uppvisade vid CS50 Fair, en program som heter wrdly, vilket är en webbaserat program som de gjorde denna video som jag tänkte jag skulle dela med ger dig en känsla av vad är möjligt genom termins slut. [Musik Spela] DAVID MALAN: Det är från vecka Zero till vecka 12 förra året. [Applåder] DAVID MALAN: Som en teaser också, verkligen att fundera är att vad som är möjligt, kanske du har sett redan, eller kan snart se, market.cs50.net, en nya verktyg att kursen team har arbetat med, denna gång i samarbete med Harvard Student Byråer, så att från och med år och fortsätter förhoppningsvis i detta kommande sommaren har du en standard möjlighet på campus för att köpa och sälja saker av intresse för dig. Och med partnerskap genom HSA, kommer du också kunna släppa objekt utanför i en av HSA: s fysiska butiker på några gång i framtiden, så att proxy saker, särskilt när du examen och inte nödvändigtvis vill kasta saker, men faktiskt betalar det vidarebefordra till folk som kan följa dig här på campus. Så mer om detta framöver. Men lite mer konkret, ett verktyg som har kommit ut av CS50 i senaste år, som några av er kanske vara bekanta och andra om du kan vara googla nu, på CS50.net/2x, kommer du hitta en länk till en Chrome förlängning vilket är demonstrativ av hur du kan använder JavaScript, samma språk vi används med Eiffeltornet för en stund sedan, att genomföra 2x uppspelningshastighet för alla Harvard iSites videos. Detta är något som är byggd in CS50 egen videospelare. Men även detta, att om du börjar gräva i källkoden, som vi kommer gärna göra tillgänglig, ser du hur Du kan även lösa problem som detta, accelererande widgets på webbplatser med som du redan är väl bekant. Så ett ord nu på kursen och förväntningar och vad som väntar. I allmänhet kommer vi samlas faktiskt här på måndagar och onsdagar - men denna fredag, ska vi samlas för att av Shopping Week - 1:00 till 2:00, men ibland till 2:30. Med tanke på att du därför kanske vill eller måste ta lite klass kl 2:00 framåt, eller ännu tidigare, inser de Kursen är stödjande av vad som kallas samtidig inskrivning, där vi ska stödja en petition till Ad styrelsen och din bofast dekaner för din räkning om du har en konflikt någonstans i detta 1:00 till 02:30 intervall. Chef till denna URL online ytterligare detaljer. Men när det gäller stödkonstruktionen som kännetecknar CS50, för studenter mer och mindre bekväm likadana, vi erbjuda tydliga spår av sektioner. Och detta är ett par veckor off, men Snart kommer du att bli ombedd att din komfort nivå. Är du bland dem som mindre bekväm, bekvämare, eller någonstans mittemellan? Och vi ska ha tre distinkta spår som tillgodoser just de målgrupper. Så vid någon punkt på sikt bör du även känna att du tävlar mot någon student med mera eller mindre bakgrund än du. I själva verket är det naturligtvis tänkt att vara mycket mer kollaborativ och mycket mer öppet än så. När det gäller problemet uppsättningar, kommer du hitta också att förutom den standardversionen av varje veckas problem ställa, det finns ofta en "hacker edition "som är tänkt att vara riktade vid 5% till 10% eller så av demografiska som är faktiskt bland dem mer bekväm och vill ha mer av en utmaning än standard utgåva av denna pset förväntar. Mer information om de som ska finns i kursplanen. Men även i det kan finnas detaljer på kurserna sena dagar. Typiskt problem sätter beror på torsdagar. Däremot kan du förlänga många av er tidsfrister denna nedgång från torsdagar till Fredagar helt enkelt genom att möta oss halvvägs, så att säga, svara på några warm-up frågor i några av veckans problem uppsättningar, som kommer att automatiskt sedan ge dig en extra 24 timmar. Vi kommer också att släppa din lägsta poäng, enligt kursplanen. För att ge dig en känsla av vad problemet apparater är - för det är faktiskt kursens problemet sätter att slutligen definiera nästan alla studerandes erfarenheter, mer så än föreläsningar, mer så än sektioner, fler så än de flesta andra aspekt av kursen. Förra året, till exempel, började vi, som Vi kommer att börja i år, med Scratch. Särskilt denna fredag, kommer vi att använda för bara en dag tid, ett grafiskt programmeringsspråk, med vilket vi kommer börja programmera genom att dra och släppa pusselbitar som endast montera fysiskt om det är vettigt att göra detta logiskt. Nästa vecka ska vi snabbt övergången till C, ett ganska gamla men mycket små och enkelt språk som ger oss möjlighet att verkligen gå 0-60 under loppet på bara några veckor, och sedan parlay samma kunskaper och färdigheter för grundläggande programmering konstruktioner i högre nivå språk som PHP, JavaScript och ytterligare andra fortfarande. Förra året, den tredje pset under var det av kryptografi, en domän-specifik applikation där vi utmanade studenter att genomföra någon antal chiffer, program som att förvränga eller avkoda informationen, att kryptera den. För hacker upplagan, däremot, Vi gav hacker studenterna en fil från en vanlig Unix-dator som innehåller användarnamn och lösenord, den senare som var krypterat, och vi utmanade dem hacker studenter till dekryptera, så gott de kunde, dessa lösenord, fortfarande på att samma domän. Scramble, ett spel som en del av er är kanske bekant. En kriminalteknisk pjäs, där vi frågar eleverna att återskapa data som hade varit annars utgår från min egen digitala kamerans compact flash-kort, genom faktiskt skriva programvara för att räkna ut, där var nollor och ettor i att digital kamera som tidigare sammansatt en JPEG bild? En utmaning av slag förra året involverar skriver den snabbaste stavningskontroll möjligt, konkurrerande mot vänner och klasskompisar om de vill. Implementera Huff 'n Puff, ett komprimeringsprogram. Och sedan avsluta terminen med CS50 Finans, en webbaserad applikation med som du skapar en eTrade-liknande hemsida att köpa och sälja aktier, så att tala, genom att faktiskt dra nästan realtid citationstecken Yahoo! Finans. Vad vi inte gjorde förra året var ett problem uppsättning som förblir ändå en favorit. Om du aldrig har gått till shuttle.cs50.net, ser du en användare gränssnittet lite såhär. Men två år sedan, klassen genomförs med hjälp av Google Maps och Google Earth Plug-in och lite av kunniga med att köra runt campus, så att syftet med detta spel var, som ni kan se några av de ansikten, är att köra runt campus söker personal, kamrater undervisning och CA, och När du gör, sätta dem på din buss. Ingen av dem verkar faktiskt vara här, så vi kommer att ange en fuska kod. [SKRATT] DAVID MALAN: Det gå vi. Okej. Och här är nu personalen spetsad genom hela campus. Och som ni kan se, på den högra sida av skärmen, flygbussen har tomma platser. Och målet var att skriva kod med vilken att simulera detta körning och plocka upp och släppa bort av passagerarna. Att man också använda ett språk kallas JavaScript. Så inse att program som det kommer vara på vår samma bana här år, liksom. I termer, nu, av ytterligare stöd, Vi har kontorstid. Som du kanske har sett i ditt eget hus matsalen eller i Annenberg, vi ska vara i huset matsal hallar fyra kvällar i veckan - Leverett, Pfoho, Eliot och Annenberg detta år, från 20:00 till 23:00. Och vad vi trodde vi skulle göra det här året är något lite annorlunda. Om du hört Mullret förra året som Det var lite för stressigt, detta Årets kontorstid, när vi ska beskriva nästa vecka, kommer att vara mer organisk, varigenom vid ankomst, kommer du att sänds till en viss tabell där flera anställda väntar, och vi ska göra saker mycket mer organiskt. Inget mer kö, inget mer iPad, men hellre ha mer intim samtal runt ett bord med bara åtta eller så att eleverna, så att vi ungefärliga känslan av vad som annars skulle vara en mycket mindre klass. Vi erbjuder, liksom, dessa saker vi kallas genomgångar, videor filmade i förväg genom en av kursens undervisning stipendiaterna, Zamyla, där hon vägleder dig genom veckans problem set, som erbjuder tips och tricks för den utmaningar som ligger framför oss. Och omvänt, efter problemsamlingar är tack, det här året kommer vi släpper också små klipp kallar post-mortems som faktiskt gå igenom representativa lösningar, både bra och dålig, via vilken du kan sluta hur du kan ha eller borde ha genomfört en egen lösning. Och vad vi ska erbjuda för första gången även i år, särskilt för de studenter som använder sig av kursens andra resurser men ändå kämpar allt för mycket, kursen själv kommer att para ihop de elever, som resurserna tillåter, med handledare så att du har en mycket mer intim möjlighet än hus matsalar möjliggöra för en-mot-en hjälp. Nu en sista glimt på några av avancerade spel i sikte. Du kanske är bekant med den CS50 Hackathon. Nåväl, kom i december, från 08:00 PM till 7:00 AM i början av Läsa period kommer att vara en möjlighet att samlas med klasskamrater - detta skulle vara runt 9:00 PM - under vilken du dyka in i ditt slutgiltiga projektets genomförande tillsammans klasskamrater, vänner och mat. Detta skulle vara runt 01:00, när den första omgången av livsmedel kom. Och det är ungefär 4:00 att visst år på CS50 Hackathon. Men den verkliga höjdpunkten för kursen är betytt för CS50 Fair, ett campus-omfattande utställning av dina egna slutliga projekt, till vilken familj och vänner är alla inbjudna, eftersom våra rekryterare och våra vänner från industrin. Detta, till exempel, är en glimt av 2.000-plus människor som har deltagit senaste åren. Uttryck som denna är inte ovanligt, och på samma sätt gör din klasskamrater glädje i saker du har åstadkommit. Och faktiskt, mot detta syfte har vi en start-av-sikt händelsen, liksom. Om saker som detta tilltalar dig, eller du är minst nyfiken på vad detta, vet att en ny tradition av Kursen heter CS50 Puzzle Day. Och detta instiftades ett par år tillbaka för att verkligen signalera till campus att datavetenskap är inte om programmering, och det är verkligen inte om att omfamna endast de elever som har tidigare erfarenhet. Det handlar verkligen om problemlösning mer allmänt. Och så Puzzle dag, under de senaste år nu, har utvecklats till en fin partnerskap med våra vänner på Facebook, varigenom det kommer att vara fantastiskt priser och pizza över floden vid i-lab denna kommande lördag. Bege dig till den adressen med två eller tre vänner om du vill delta i denna nya tradition. Så jag skulle vilja be er att hålla en sak i åtanke, och vi har bara en två minuters klipp som att stänga idag. 73% är numret att minnas. Cake, också, väntar dig utanför detta transept som vi avbryta på bara en par ögonblick, är som en tradition av kursen, liksom. Men detta är nyckeln citat från kursens kursplan att hålla i minnet. Vad slutligen viktigt i denna kurs är inte så mycket när du hamnar förhållande till dina klasskamrater men där du, i vecka 12, hamna i förhållande till själv i vecka 0. Men glimt som vi kommer att lämna dig med här i dag är det sista här genom vår samma Daniel, gjorde vem wrdly video nyss. Jag lämnar er med denna glimt om vad som väntar. Och eftersom vi gör detta, om vi kunde ha CS50 personal från framsidan av rummet att komma vidare upp på scenen för att måla alla det mer av en visuell bild som till vad som väntar dig i år - bli besvärlig. Vi avslutar med detta här på skärmen. [Musik Spela] DAVID MALAN: Detta är CS50. [MUSIK - MATT & KIM, "det är okej"] Högtalare 1: Jag älskar CS50 mer än katter. TALARE 2: Whoaaaa! [SKRATT] DAVID MALAN: Detta är alltså CS50. Vi kommer att se dig på fredag. [Applåder och jublar] Berättare: Vid nästa CS50, en scen demo går inte som planerat. DAVID MALAN: Vi vill hitta Mike Smith i denna telefonbok. Tja, vad är dina instinkter? Jag kanske hoppar ungefär till mitten av telefonboken, blick ner, se till att Jag är på M, och jag vet nu att Mike Smith är inte åt vänster. Han måste vara till höger. Och så på denna punkt, vi kan bokstavligen riva - vid denna punkt kan vi riva bokstavligen - Vid denna punkt, kan vi bildligt riva telefonboken i hälften. [UKULELE strumming]