[Muziciranja] [Pljesak] DAVID J. Malan: Ovo je CS50, Sveučilištu Harvard uvod za intelektualno poduzeća informatike i umijeće programiranja. Sada, ako ste među onima koji svake godine se sjedi ovdje s malo živaca u vašem umu, kao što da ne mislite da pripadam ovdje, mislite da je većina tko sjedi oko vas zna daleko više od tebe, uistinu udobnije od vas na računalu znanost ili računala općenitije, shvatite da je 78% učenika koji su sada potrajati CS50 nemaju prethodnog iskustva. Doista, postoji 100 točaka postoji na zaslonu, od kojih je 78 su svijetli zeleno, što ti znači, Ako ste među tom demografske, su u vrlo dobrom društvu ovdje na van. A ako ste umjesto među 22% CS50 studenata koji to uistinu imaju prethodno iskustvo, bilo u visoka škola ili neki drugi program, shvatite da vas, također, će biti izazvan u tijeku. Ne samo da imamo različite pjesme za studente manje ugodno i više ugodno podjednako u sekcijama, mi također su tzv hakerski izdanja većine problema postavlja da će izazov one studente s tim dodatnim iskustvom istražiti sličan materijal ali s više sofisticiran perspektive. No, ono što je informatika? Pa, na kraju krajeva, što će se obzira na to što ste istražiti ovo područje nije toliko toga gdje ćete završiti u odnosu na svoje kolege iz razreda, ali gdje ste sami završiti u 12 tjedna u odnosu na kojoj se početi ovdje U tjednu nula. Sada računalo science-- dobro, neka je nazvati ga znanost computation-- gdje računanja je zapravo samo fancy način govoreći, uzimanje nekih ulaz, proizvoditi neki izlaz, a Pritom pokretanjem algoritama, seta uputa za rješavanje neki problem na tim ulazima kako bi se proizvesti neki izlaz ili Rješenje u kojem ste zainteresirani. Tako smo nedavno imali Povod za putovanje izvan u Kaliforniju u susret s alumna. Njezino ime je Susan Wojcicki. A ona bih razgovarati da ste ovdje na videu da svjedoče koliko je primjenjivo čak i samo okus računala znanosti na Uvodni razini može biti. Čak i ako ne ide na potjeru računalnih znanosti kao polje, ili čak i inženjering, ili matičnih općenitije, vidjet ćete, u stvari, kako je određena Naravno, tako utjecalo na njezin život. A ona je samo samo ga je uzeo kad je bio viši ovdje na Harvard College. Ako smo mogli prigušiti svjetla za Susan. SUSAN Wójcicki: Zdravo, svijete. Ja sam Susan Wojcicki. Ja sam predsjednik Uprave YouTube. I ja sam uzeo CS50 kada sam bio viši na Harvardu 1990. Bio sam zapravo povijest i književnost veliki. I moj mlađi ljeta, Shvatio sam da je možda sam htjela naučiti nešto o računalima. I tako, sam se vratio. Uzeo sam CS50. Bilo je teško, ali to je bio Najviše nevjerojatna klasa sam uzeo. To je promijenilo kako sam razmišljati o svemu. I kad sam diplomirala na Harvardu 1990, otišao sam u Silicijskoj dolini. I ja sam dobio posao. I ja sam radio u tech otkad. DAVID J. Malan: Što sad Susan nije spomenuo u ovom videu, da je zapravo u njoj garaža da Google je sama osnovali Larry i Sergey. Sada smo i posegnuo za našim prijateljima na code.org, organizacije koja u proteklih godinu dana nije bilo uzimajući narod osobito uzbuđen o računalnoj znanosti i programiranje, posebno. Ali, to je vrijedno napomenuti da je programiranje Nije informatike po sebi. Računarstvo nije programiranje. Umjesto programiranje je samo tool-- s kojim sve vas će biti predobro poznato po semestru je end-- tako da možete primijeniti ne Samo budućim tečajevima u CS ali što god poljima odakle ideš, u humanističkim znanostima, društvene znanosti, prirodne znanosti, ili slično. Doista, dopustiti neke druge bivših i njihovi kolege govoriti o primjenjivosti polja koja čeka. Bill Gates: Bio sam 13 kad sam Prvi je dobio pristup računalu. JACK Dorsey: Moji roditelji Kupio mi Macintosh 1984 kad sam bio osam godina star. Mark Zuckerberg: Ja sam bio u šestom razredu. Zvučnik 1: Naučio sam da kod na faksu. RUCHI SANGHVI: prve godine, prvi semestar, Uvod u računalne znanosti. Bill Gates: Napisao sam program da je igrao Tic-Tac-nožni prst. DREW HOUSTON: Mislim da je to bio prilično skromnih početaka. Mislim da je prvi program Napisao sam pitao stvari poput, koja je tvoja najdraža boja? Ili koliko ti je godina? ELENA SILENOK: Prvi put sam saznao kako napraviti zeleni krug i Crveni trg se pojaviti na zaslonu. Gabe NEWELL: Prvi Vrijeme i zapravo je nešto smisliti i reći zdravo, svijete. I sam je napravio računalo učiniti. To je bio samo zapanjujuće. Mark Zuckerberg: Učenje kako na programu nije Krenuti kao žele naučiti sve informatike ili pokušavaju svladati to disciplina ili bilo što slično. To samo započela jer sam želio učiniti jednu jednostavnu stvar. Htjela sam napraviti nešto što Bilo je zabavno za mene i moje sestre. I sam je napisao ovaj mali program. I onda zapravo samo dodao malo na njega. I onda kad mi je trebalo naučiti nešto novo, Ga pogledao sam prema gore, bilo u Knjiga ili na internetu, a zatim je dodao malo na njega. DREW HOUSTON: To je stvarno ne razlikuje sviranje instrumenta ili nešto ili igrati sport. DAVID J. Malan: U redu. Tako nam neka sada zapravo zaroniti u malo dublje. Što su ti ulazi i izlazi da mi ovdje govorimo o? Pa kako o nečemu jednostavnom? Vi vjerojatno znate, čak i ako imate Ne poznavanje informatike god, da računala na neki način koristiti i razumije samo nula i jedinica. No, kako se to može eventualno biti s obzirom kako Mnogo je današnja stolna i prijenosna računala podjednako mogu učiniti? DNK dana, samo Abeceda da oni razumiju je nula ili jedan. Pa, razmislite o ovom. Mi, ljudi, imaju tendenciju da koriste decimalni sustav. "Prosinca", što znači 10. I to je 10, jer imamo 10 znamenaka, 0 do devet. Sada računala, s druge strane, imaju tendenciju da koriste binarni. "Bi", što znači dva. Dakle, oni imaju tendenciju da se koristiti samo nula i jedan. No, ispostavilo se, da je čak i Upravo s nula i jedinica, odnosno je dovoljno velika abeceda s kojim se predstavljaju većinu bilo podatak želite, da li je broj, da li je to pismo, da li je grafički ili video na zaslonu. Razmotrite, na primjer, kako smo ljude obično tumače taj broj ovdje. Ovo je samo tri znamenki, jedan, dva, tri. Ali mi znamo taj broj urođeno sada kao 123. Ali zašto je to tako? Pa, ako mislite vratiti da možda osnovnoj školi, si vjerojatno naučio razmišljati o ti brojevi kao da su u kolonama, gdje je netko u stotinama mjesto, dva je na desetke mjesta, a tri je onih mjestu. Zašto je to zapravo korisni? Pa, razmislite o super jednostavna aritmetika da smo svi bili radi već godinama. Efektivno, ako imaš jedan u stotinama mjestu, što učiniti brzo matematiku 100 puta 1 plus 10 puta 2-- jer dva je u nekoliko desetaka mjesto-- plus 1 puta 3-- jer je u tri onih mjestu. Dakle, naravno, ako smo zapravo množite ovo, ono što mi predstavlja s ovim pattern-- jednom dva three-- je 100 plus 20 plus 3, koji je, naravno, 123. Sada binarno, i računala zapravo, temeljno govore istim jezikom što nam je činiti. Oni samo imaju manji abecedu. Tako računala samo nula i one na raspolaganju. Dakle, dok mi ljudi imaju bitno Ovlasti 10 u svakoj od tih places-- 10 do 10 za nulu, jedan, deset do dva, dajući vam 110 i 100 respektivno. Jer samo računala imaju dvije vrijednosti oni mogu razumjeti, nula i jedan, oni moraju koristiti različite vrijednosti u ovim stupcima, jedan, dva, četiri. A ako mi čuva ide, osam, 16, 32, 64, i tako dalje. No, uzorak i mentalitet je isti. Dakle, po toj logici, tko, kako bi Idem oko predstavlja broj jedan u binarnom? Ako ste nikada nije ni razmišljao o tome to prije, što se vaše crijevo reći? PUBLIKA: Jedan. DAVID J. Malan: Jedan. Točno. Potrebna je samo jedan u Ones mjesto, jer je nula dovoljan da nam se dati ni četiri niti dva. Dakle, jedan puta jedan jednako jedan. Sada se stvari malo zanimljiva. Ako želim predstavljati u Binary broj two--, ali, opet, čak i ako ste nikada govori taj jezik i prije, kako ćemo predstavljati u binarnom vrijednosti koju ljudi znaju kao dva? Nula jedan nula. Samo stavite jedan u Kolona da ga želite. Sada postaje prilično lako vjerojatno sada. Dakle, ako želim predstavljati three-- Nema tri stup. Dakle, opet, ja mogu sada dodati ove vrijednosti zajedno stavljanjem jedan ovdje. Dakle 2 puta 1 plus 1 1 puta je, naravno, 3. Sada se stvari malo zabave u da su one sada postaju nule. I da predstavljaju četiri, ja ovo. A ako mi se polako povećavati ovdje-- da će biti pet. To će biti šest. To će biti sedam. Ali sada sam čini se da su naiđete na problem. Kako bih mogao ići oko zastupanje eight-- će biti sljedeći vrijednost. Da, tako da nam je potrebna nova bitova. I, doista, ako ste čuli ovu rečenicu prije, bita, to je samo kratko za binarna znamenka, nula ili jedan. I tako sam se dogoditi da se predstavlja samo tri takva bita ovdje. Ali, ako sam imao način pohranjivanja ne tri različite bita, ali četiri, Ja sigurno mogu predstavljati osam, a zatim devet, a potom 10, pa čak i veći i veći. Ali to onda zove u pitanje kako možemo ići oko njih predstavlja stvari na prvom mjestu. To je jedna stvar za crtanje ih ovdje na slajdu, ali kako ćete ih predstavljaju ako si mehanički uređaj? Što je računalo radi na predstavlja ulaza i izlaza koji fundamentalno definirati računanje Na kraju krajeva? Pa, što o nečemu super jednostavna ovako? To je samo žarulja. I ja mogu biti okidač žarulja ići na okretanjem neke struje na i omogućuju elektroni teći kroz koji mijenja svoj država ili njezina vrijednost, da se tako izrazim. Na primjer, to stara škola stolna svjetiljka ovdje jedan takav žarulja unutar nje. I sada to nije stvarno rade ništa korisno. No, čim sam ga priključite u električnu utičnicu a zatim koristite ovu switch-- ili možemo čak nazvati ga tranzistor ili mislite o njemu kao such-- Ja sada mogu predstavljati bilo Ova vrijednost, gdje je žarulja je Očito off, ili ta vrijednost. Ova vrijednost ili ta vrijednost. Ova vrijednost i tako dalje. Dakle, unutar računala, vjerojatno, puno su manji komadi hardvera, a da na kraju dana jednostavno imati koristiti electricity-- Možda it-- snimiti a zatim ih zadržati nešto ili bi nešto off. Naravno, to nije Posebno je zanimljivo to učiniti sa samo jednim žarulja. Zapravo, koliko visoko mogu računati u binarni s ovim stolnu lampu ovdje? PUBLIKA: Jedan. DAVID J. Malan: Jedan, zar ne? Trebam još stolnih svjetiljki, ako sam zapravo žele brojati više. Ali možemo napraviti bolje od toga. Budući da su žarulje koje smo stavili u tim stvarima su zapravo ljubitelj žarulje nego prošla godina bi omogućilo. I oni su zapravo umreženih žarulje. A trsovi tvrtki napraviti ove stvari ovih dana. No, ispada da ovo posebno dolazi s značajka pri čemu možete promijeniti svoje boje. Tako, primjerice, ako krase svoj spavaonica s nekoliko tih svjetlosti žarulje, ovisno o raspoloženju, ovisno o tome tko dolazi u, ovisno o vremenskim uvjetima, ovisno o vremenu dana, možete zapravo promjenu boje lukovice u svoju sobu. A to je zato što ta svjetla žarulje i drugi poput njega imaju ono što je pozvao API, primjena sučelje za programiranje, koji je tema s kojom ćete biti dobro poznaje do kraja semestra je. A to je samo fantazija, zagonetan način govoreći, možete programirati ove svjetlo Žarulje učiniti vaš ponudu. Možete im poslati poruke baš kao i vi, ljudi, Možete poslati poruku na web poslužitelju govoreći, daj mi današnje vijesti ili mi dati svoj e-mail. Možete poslati više kompliciranih Poruke na ta žarulja Naime, uključivanje i isključivanje. No, to nije sve što je zanimljivo. Možete reći, uključite crvena, uključite zeleni, uključite plava, sve s istim žarulje. A možete i, s malo više pamet, kažu, uključite se u plavu kad je tmurno dan izvana, na primjer. To zapravo može zakrpati u Vrijeme API i saznajte ono vrijeme, ili vrijeme dana, ili druge takve okidače. Dakle, u stvari, dva Vlastitih djelatnika CS50-a, Dan Bradley i Ansel Duff je ovdje, ljubazno nabavljati nas cijela hrpa tih žarulja. I oni su izgradili CS50-a Prva ikada binarni žarulje, gdje smo zastupljeni ovdje-- s tim razigranim malo magnets-- razni rezerviranih mi aludirala samo malo prije. Dakle način ovdje je Ones mjesto, dva, četiri. I nismo vidjeli više od toga. Ali, naravno, oni su ovlasti dva. Osam, 16, 32, 64 i 128. Dakle, ako ja sada želim biti malo ljubitelj nego koristeći ovaj stari školski prekidač, Imam ovdje na ovom iPad Super jednostavno sučelje da je Dan Bradley, bivši Student a sada podučava kolega, programirana koristeći neki HTML i JavaScript, koja su označavanje i programiranje jezici respektivno. I vjerojatno možete vidjeti-- čak iu back-- Tu je veliki plus i veliki minus, plus jedan gumb za svaki od tih žarulja. A što je ovo će mi omogućiti da to je, primjerice, kliknite plus a sada predstavljaju, od Naravno, ono broj? Jedan. I ja mogu ga opet udariti. Dva. Tri. Četiri. Pet. Šest. Sedam. I evo sada smo dobili da rollover, ali imamo i četvrtu malo tog vremena, tako da sada imamo osam. Tako bismo mogli to učiniti za neko vrijeme. U stvari, kao što je na stranu, koliko visoko možemo računati? Svatko? PUBLIKA: 255. DAVID J. Malan: 255, zar ne? Ne brinite previše o matematici za sada, ali to je prilično pristojan broj. No, to zapravo ne veže samo koliko komada informacija, kao pismo, ili grafički da bismo mogli predstavljati. No, bez obzira na to za sada. Ja ću ići naprijed i pretvoriti ih sve off. I kad bih mogao, ja bih pitati za volonter, naš prvi volunteer-- Oh, hello-- na pozornici. Kvaka je da morate biti udobno se pojavljuju, kao što je vama jasno su pred svim svojim kolegama, , kao i na internetu. I neka mi izgleda malo izvan do- o tome kako ovdje u bijelu košulju? A ruku. Dođi gore. Koje je tvoje ime? PUBLIKA: Jackie. DAVID J. Malan: Jackie. Jackie, dođi gore. Dakle, ono što postoji i na taj iPad je gumb pod nazivom Game način. A to je Igrači Mod će me pustiti da se ulaz unaprijed određeni decimalni broj, brojevi su mi ljudi poznaju. A onda će biti izazvan Ovdje se koristiti gumbe na top-- jedan za svaki od tih bulbs-- zapravo shvatiti uzorak žarulja koji predstavlja broj u pitanju. I žao mi je, što se zoveš? PUBLIKA: Jackie. DAVID J. Malan: Jackie. U redu. Drago mi je da sam te upoznao. Pa neka mi ići naprijed i program u za svijet da vidi broj 15. Mi ćemo ga zadržati male isprva ovdje. I ja ću ići u modu igre. A ja ću navesti, daju nam broj 15. U redu. I sada sa svima watching-- ako Želite li možda stati na ovaj način, jer će se postroje up-- ići naprijed i prebacivanje osam gumbiće duž vrha pretvoriti žarulje na ili isključiti kao što vidite stane. PUBLIKA: U redu. DAVID J. Malan: I nema varanja skom plus 15 puta. Oh, mi ćemo to učiniti. PUBLIKA: Oh, čekaj. Tako mi je žao. DAVID J. Malan: Također možete uključiti žarulje za pojedine sa svakom od tih gumba na vrhu. PUBLIKA: Oh, u redu. Dakle, to bi bilo volimo-članovima DAVID J. Malan: U redu. Tako sada imamo osam. Tako ćemo pauzu za Publika je da se uključe ovdje. Koji broj je Jackie trenutno predstavlja? 11. Tako smo stigli. I izvrsno. Dakle, mi imamo prvi pobjednik. Čestitamo. I mislili smo da ćemo imati neki mitski poklonima. Ako želite biti jedan takav sobi u studentskom domu ovdje na kampusu, možete i sami imati konačni projekt sada koriste taj API, zahvaljujući Jackie. Dakle now-- [Pljesak] --if smo mogli, još jedan kao oko toga. Oh, sada svatko želi neke žarulje. Za tzv hakerske izdanju, ćemo ga rampu A- Oh, Da, suzdržan. Mislim da ste došli do sada ako je tvoja ruka ide prema dolje. Koje je tvoje ime? PUBLIKA: Alex. DAVID J. Malan: Alex, dođi ovamo. Tako je za Alex, mi smo idući u Program u nešto većem broju. Možda bi. Broj 50. PUBLIKA: U redu. DAVID J. Malan: Ali, kao što je Ja said-- i možda Želite stajati ovdje, pa da su tipke postroje kao što bi expect--, ali jesam pozvati ovaj haker izdanje. So-- sretno! [Smijeh] Vi ćete biti u mogućnosti da se ih se, ako ti-- redu. Izvrsno. Wonderful. Čestitamo. [Pljesak] Pretpostavljam da bih trebao platiti. Čestitke Alex kao dobro. U redu. Dakle, krajnji takeaway evo nadam se, iskreno, simplicity-- jednostavnost možete dobiti neke lijepe svjetlo žarulje, očito u [nečujan]. Ali oni predstavljaju, u konačnici, iste ideje s kojima mi ljudi su već sve previše upoznat. Dakle, što bi iduće korak se u progresiji pokušava nešto napraviti Zanimljivo s podacima i predstavlja ulaza koji su ne samo brojevi, ali su možda i slova ili više? Pa, ispada da računalni svijet, već dugi niz godina, jednostavno usvojili proizvoljna, ali dosljedni standard koji mapira brojeve do slova abecede. Na primjer, ovdje je izvadak iz tog mapiranja. To se zove ASCII. -S-C-I-I. I to je jednostavno Tablica koja preslikava veliko letters-- u ovom case-- u decimalne brojeve. No, ono što je dublji smisao? Pa, ako stvarno želiš da predstavlja nešto poput e-mail ili neki tekst na web stranici, očito žele pokazati ljudska pisma abeceda, a ne brojevi. Dakle, ovisno o kontekst programa da korisnik koristi, ako je to web preglednik ili e-mail klijent, Brojevi svakako može biti tumačiti kao slova. To će reći, obrasci bitova može lako može protumačiti kao slova. I tako ono što može imati je pismo biće predstavljeni kao 65, B koji se predstavljao kao 66. Dakle, ako imamo super Ukratko riječ, kao i bok, ono što računalo bi u konačnici dućan u decimale, ali stvarno u binarnom, koristite neki slijed bitova, utjecati malo električne energije na neki način, će biti dva broja 72 i 73. Ali uzorak bitova koji predstavlja one vrijednosti. Dakle, to su onda kako možemo zastupati naše ulaze i izlaze. A dovoljno je reći, možemo učiniti više složenih reprezentacije u konačnici sa stvarima kao što su grafika, video, glazba, i još mnogo toga kao što ćemo vidjeti kasnije ovaj pojam. Tako da samo ostavlja onda algoritmi, ove garniture uputa kojom mi smo rješavanje stvarnih problema. Mi smo se u prolazu ulaza na algoritmima. A ti algoritmi se proizvoditi izlaza, nadamo se ispraviti izlaza i nadamo se, također, učinkovito okupili izlaza. Drugim riječima, to je jedna stvar pravilno provesti nešto. To je još jedna stvar za provedbu nešto dobro ili učinkovito. Na primjer, jedan dokaz da smo draga u tijeku je ovo jedan. Ali te stvari su uzimajući sve teže pronaći. No, to je doista stara škola telefonski imenik, od kojih je unutar su 1.000 plus stranice Imena i telefonski brojevi. A ako sam htio pogledati netko u tom telefonskom imeniku, Jednostavno sam mogao učiniti vrlo naivno algoritam. Ja mogu otvoriti na prvu stranicu, a Mogao bih početi tražiti, recimo, netko po imenu Mike Smith. A ako on nije na prvi stranica, sam napredak na drugo, i onda se treći, a zatim na četvrtom mjestu, i tako dalje, dok sam konačno naći Mike Smith. Sada je to algoritam točno? PUBLIKA: Da. DAVID J. Malan: Da. Ako je on tamo, ja ću na kraju su ga pronašli. No, to je vjerojatno nije jako učinkovit, pogotovo ne brzo, jer, Bože moj, zašto sam ja gubim vrijeme pečenje kroz sve ove stranice, kada sam mogao svakako to učinite fizički brže? Pa, blagi optimizacije, tako da se govore, možda ne za jednu stranicu u isto vrijeme, ali dvije, četiri, šest, osam, 10. Još uvijek u pravu? PUBLIKA: Ne DAVID J. Malan: Pa ne, ako sam za instanca preskočiti Mike Smith. Ali tako dugo dok sam natrag papučicu jednu stranicu, ako sam ga preletjeti, Možda bismo mogli ispraviti ono što bi u protivnom biti Jesam. No, je li bolje? Je li to brže? Mislim, da. To je doslovno dva puta brže ako sam napraviti dvije stranice u isto vrijeme. Dakle, ako sam izvorno imao 1.000 stranica, Sada imam samo za okretanje 500 puta, nije u potpunosti 1.000 stranica da bi dobili potencijalno u najgorem slučaju na kraj telefona Knjiga, u kojoj je netko kao što je Mike Smith ili netko s kasnije ime zapravo moglo biti. No, naravno, mi ljudi sigurno nisu će se taj događaj, zasigurno Ne u ovom trenutku u našim životima. Što je razumno Ljudsko vjerojatno će učiniti? PUBLIKA: Idite ravno do the9 S-ih. DAVID J. Malan: Idi ravno sa S-ih? Kako mogu ići ravno na S-ih? PUBLIKA: Rip ga na pola. DAVID J. Malan: Pa, nema tragova. Dakle, da, ako je bilo uistinu naljepnice ili ljepljive karticu za S, smo trebali skočiti tamo. No, to je prilično bezazleno. Dakle, najbolje što možete učiniti je grubo na S dijelu ili možda grubo u sredini. No, ključna takeaway now-- i intuicija da ste uzeti za odobren godinama probably-- je li to ono što ti se sada znate o ovom problemu? PUBLIKA: [nečujan] DAVID J. Malan: Mike Smith je zasigurno ne lopte problema jer Smith dolazi nakon sredine što je otprilike području M čini se da je. Dakle, kao što ste mogli vidjeti na Visitas, možemo sada doslovno suza taj problem na pola. PUBLIKA: Woo! DAVID J. Malan: To je sve lakše i lakše. [Pljesak] Postoji li ići. [Smijeh] I sada iz temelja imaju isti problem, ali to je doslovno upola velika. Ja sam još uvijek u potrazi za Mike Smith. I usuđujem se reći, još uvijek mogu tražiti za njega na isti način, cijepanje problem u polovici opet, suzenje problem opet na pola, što me sada ostavlja s Problem četvrtina veličine, dramatično baciti da je polovica daleko, a ponovite postupak i opet i opet, gledajući prema dolje u svakom trenutku vidjeti ako je Mike Smith je na Stranica je u pitanju. Sada, ako ja to pravo, konačnici ću se naći sa samo jedne stranice na kojoj je Mike Smith je li on doista u telefonskom imeniku. Naravno, nisam mogao nikada više nazvati Mike. No, poanta je da ako smo počeli sa 1.000 stranica, moj prvi algoritam, okrenuti stranicu, možda i 1.000 times-- definitivno manje jer je Naziv S a ne ime Z, ali kao čak 1.000 stranica potencijalno. Drugi algoritam, to bolje. 500 stranica. Treće algoritam, međutim, koliko koraka bilo bi se podijeliti na 1.000 stranica telefonski imenik na pola kao što je to? 10, dati ili uzeti. Dakle, samo flipping kroz koje telefonski imenik, ronjenje i osvajati, da se tako izrazim, 10 puta, učinit ću moj put prema dolje na samo jedan stranici. I tako bismo mogli snimiti ovaj intuiciju sad malo grafički ako samo razmislite Ovaj super jednostavan graf. Mi smo na x-osi, ili vodoravna osi, je veličina mog problema, broj stranica u telefonskom imeniku. I računalni znanstvenici općenito vole zvati veličina problema n, gdje je n je samo neka varijabla koja represents-- u to case-- broj stranica. Vertikalni ili y-os, ovdje je će biti vremena za rješavanje, Možda broj stranica okreta, Možda broj sekundi ili minuta, bez obzira na Vaša jedinica mjere je. I tako je ova crvena linija predstavlja prvi algoritam, jer postoji jedna do jedan Odnos između broja stranica i količinu vremena koje je potrebno. Ako Verizon udvostručuje broj Članci u telefonskom imeniku iduće godine, moj hod put-- Vrijeme potrebno za izvršavanje da je prvi algorithm-- parovima u najgorem slučaju. No, drugi algoritam, gdje sam preklapanje po dva, zahtijeva manje vremena za Navedeni problem veličina. Dakle, ako sam to mnogi stranica su ovdje-- obavijest da žute crte predlaže manje vremena za rješavanje. I doista, ona predstavlja, ćemo reći, n više od dva. No, ono što je oblik treće i konačna krivulja će izgledati? Da, to je doista ide na look-- I Ne znam što si htio reći. No, da vidimo što što si htio reći. PUBLIKA: Kao da je. DAVID J. Malan: Bit će to izgledati to, logaritamska slope-- exactly-- pri čemu imate ovu neobičnu padinu. To više nije ravna crta. A što je uvjerljiv o tome da je iako graf sada je odsječen, možete ekstrapolirati u vašem umu da je zelena linija nije će se povećati u Visina sve što je puno kao što nastavite dalje dolje da horizontalnoj osi. Doista, Verizon, za instanca, mogla udvostručiti broj stranica u telefonu Knjiga između ove godine i iduće godine od 1.000 do 2000 stranicama, ali nije velika stvar. Uz ovo treći i posljednji, postoji intuitivno algoritam dijeljenja i osvajanje. To će me odvesti koliko još korake od iduće godine kako bi pronašli nekoga Like Mike Smith? PUBLIKA: Jedan. DAVID J. Malan: Postoji samo jedan. I oni mogu učetverostručiti, to je ide mi se samo još dva koraka i tako dalje. I tako je to dokaz koliko su neki oprezni dizajn a neki zahvalnost za ono što Vaši ulazi su mogu učiniti još boljim. Sada smo varanje malo u smislu da smo utjecati pretpostavku. Ono što je moja pretpostavka o našem telefonskom imeniku koji mi je dopustio da podijeli pa vladaj u ovom intuitivan i dalje ispravan način? PUBLIKA: [nečujan] DAVID J. Malan: Da. Dakle, to je naredio. To je po abecedi po telefonskog imenika tvrtke. Ako je to bilo u slučajnim redoslijedom, da će biti pakao od telefonskog imenika, ali to sigurno ne bi sama posuditi algoritmu Koristio sam, jer nikada ne bi samo dogoditi preko Mike Smith ako je zadržao podjelu u pola na taj način slučajno. Tako ćemo sada formalizirati ono što je jasno intuitivno. Dakle, nešto što se zove pseudocode je gdje ćemo početak neke od naših početnih problema. A to je generički način opisivanja Algoritam ili računalni program, Ne koristeći C ili C ++, ili Java, ili bilo koji specifičan jezik, ali samo pomoću engleski, s koji je bilo koje ljudsko bi moglo biti poznato. A mogli bismo napisati pseudocode za ovaj problem na sljedeći način. Korak jedan, pokupiti telefonski imenik. Korak dva, otvoren do sredine telefonskom imeniku. Treći korak, pogledate imena. Četvrti korak, ako Smith je među names-- I sada je to Zanimljivo konstrukt. To je točka odluke. To je raskrižje, ako vas će, grana, da se tako izrazim. Dakle, ja ću uvući samo po konvenciji step-- Ne five-- što je recimo, ja ću nazvati Mike. Dakle, to udubljenje, potpuno proizvoljna ljudska konvencija, ali je jednostavno značilo prenijeti semantički da, ako Smith je među imenima, onda sam trebao zvati Mike. U međuvremenu u koraku šest, najave da udubljenje je otišao. Dakle, ostalo je druga vilica u ceste, druga cesta bih mogao putovati. Dakle, još ako je Smith ranije u knjizi, što je Moj sljedeći korak vjerojatno će biti ovdje? PUBLIKA: Možete ići na lijevoj strani. DAVID J. Malan: Da, pa ići na lijeva polovica telefonskom imeniku. Bacite desnu polovicu ako Smith je ranije u knjizi. Dakle otvoren do sredine lijeva polovica knjige. A onda korak osam, ide da se postroje tri. A to je znatiželjan petlje sam izazivanje, rekurzija da se tako izrazim. No, više o tome u budućnosti. Ja sam koristeći moj isti algoritam, moj isto pseudocode, ponovno riješiti isti problem jer jedino što se promijenilo je veličina problema, ne moj cilj, a ne osoba Tražim. Dakle, ja mogu ponovno koristiti algoritam da sam već definirana. Inače, ako je Smith kasnije u book-- možda ćete guess-- otvoren do sredine desna polovica knjige. I opet, idite na liniji tri. Else-- što je konačna linija U ovom programu će biti? Ako on nije među imena na stranici Ja sam na, ako nije ranije u Knjiga, a on je najkasnije u knjizi, ono što ja znam je istina o Mike Smith je sada? PUBLIKA: Nije u knjizi. DAVID J. Malan: Nije u knjizi. Dakle, najbolje što možete učiniti je jednostavno odustati i zaustaviti ovaj program. U redu. Dakle, u ovom trenutku, uzmimo Brzi obilazak nekih od onoga što čeka. A u stvari, ja sam se pridružio ovdje brojnim CS50 osoblja. Ako ti ljudi mogli sve pridružite mi se ovdje na pozornici. [Pljesak] Da se podsjetimo, to je samo podskup CS50 osoblja, jer svake godine imamo gotovo 100 zaposlenika Članovi u ulogama naravno asistenata, podučava novaka, i još mnogo toga. Dođi gore. Dakle, oni će nam se pridružiti ovdje nespretno samo na trenutak kao što smo dati kovitlac obilazak ono trebali očekivati ​​ovdje u tijeku. Dakle, prije svega, imamo SAT / UNS-a kao ocjenjivanja opciju u tijeku. To je značilo namjerno biti opcija kojom Ako ste malo nelagodno na što je u tijeku, a vi ne bojte se, čak i ako failure-- iskreno neuspjeh znači ranjavanje svoje GPA, uzimajući B, a ne A- koji je upravo ono što, svakako za pristupnika Naravno, kao i CS50 i drugi uvodni tečajevi, ovo ocjenjivanje opcija je značilo dopustiti. Iz sveg srca potaknuti students-- pogotovo Ako na fence-- za početak Naravno SAT / UNS-a, pa čak i dalje SAT / UNS-a. Ali sigurno možete prebaciti na slovo stupnja po peti u ponedjeljak u pojam. Iskreno, kad sam bio brucoš u 1995, Ja osobno nisam ni uzeti CS50 jer nisam mogao se živac zapravo korak noga u učionici. Činilo domenu previše upoznati sa mnom, a zapravo samo za one koji su mi prijatelji, Iskreno, koji je bio programiranje jer su bili šest- ili možda 10-godina-stari. I to je samo zato što sam bio mogućnosti da se CS50 u mom danu u protuvrijednosti verziji SAT / UNS-- pass / fail natrag u day-- da je čak i sam uzeo 50. I na neki način, ja sam opet ovdje s vama danas. Sada je u međuvremenu što još treba imati na umu o 50 istovremeni upis. Suprotno glasinama koje ste možda čuli, možete, u stvari, istodobno učlaniti u CS50 i druge klase koje Sastaje se ista ili preklapanja Vrijeme kao CS50 predavanja upravo ovdje. Pogledajte plan za pojedinosti na njihovu provedbu. Predavanja, u međuvremenu, suprotno što je i službeno u katalogu, će uglavnom samo susret za samo sat vremena. U povodu možemo pokrenuti malo dugo. No, imajte na umu da Cilj u CS50 predavanja je pružiti vam konceptualni pregled, nadamo se neke demonstracije, možda čak i neki pokloni, što čeka za tjedan koji slijedi. I tako na predavanjima, mi ćemo istražiti te teme i primjeri zajedno, vođenje učenika i studenata na pozornicu, a osoblja na pozornicu, što je češće možemo, za samo par sati svaki tjedan. Sekcije, u međuvremenu, bit će nude tih ljudi ovdje-- mnogim ih podučava novaka, neke od njih, naravno assistants-- volje se događa jednom tjedno. A ono što je ključno zadržati na umu je da smo Ne have-- ne za razliku od Prvog Noći, glazba class-- različitih pjesama odsjeka za studenti manje udobne, više udobna, a negdje između. I iskreno, znaš li da si manje ugodno. A što vjerojatno znate, ako ti si udobnije. A ako niste sasvim sigurni, vi ste po definiciji negdje između. Dakle, kada dođe vrijeme da sekciji u tjedan dana ili tako, po nastavnom planu, ćemo vam postaviti to pitanje. A možete samostalno odabrati Based na svoju razinu udobnosti i biti s students-- biti sa zelenim dots-- slični u razini komfora i na vas. U međuvremenu, mi imamo problema postavlja, što će u konačnici definirati svoje iskustvo u ovom tečaju. Oni su ponudili obično u više izdanja. Standardno izdanje koje smo najviše očekivali svaki student u tijeku kako bi se borila ali i tzv haker izdanje koji nudi nikakav oblik dodatnog kredita Konačni ali stvarno hvalisanje prava reći da ste pokušali i rješavati Tečaj je hakerski izdanja koje pristupiti sličan materijal ali s više sofisticirane kuta. Ono što mi nudimo za standardno izdanje, za, opet, super većina studenata, nisu samo hodaju materijale, koji su Video pod vodstvom osoblja Tečaj je da vas doista provesti kroz Problemi Naravno je i to moguće dizajn implementacije. I mi također, nakon što Činjenica, ponuditi postmortems, pri čemu ako se pitate Kako biste mogli imati ili su trebali riješiti neke Problem, nastavno osoblje će vas provesti kroz one koji su na videu, kao dobro. U međuvremenu, što se čeka su previše pet dana kasne i činjenica da ćemo Baci najniža je problem postaviti rezultat. Mi svakako cijenimo da je u zamjenu za radno opterećenje koje se očekuje da će 50 od vas, život dobiva na putu Ponekad, ako ne i pet puta. I tako će to ponuditi ti malo fleksibilnosti, širi svoj rok od, recimo, Četvrtak u podne do petka u podne. Pogledajte plan za njihovi detalji provedbe. Sada ono što sada čeka? I to je samo pojavljuje Sad mi samo koliko dugo Imam ti dečki ovdje stajati na pozornici. [Smijeh] DAVID J. Malan: Ali, mi ćemo doći do vrhunac završiti prije dugo. Pa što ga čeka u smislu od problematičnih seta? Pa, možda i teaser za ono što smo svi i prošle godine sa svojim prethodnicima. U prvom setu problema prošle godine smo uveli Scratch, grafički programski jezik koji omogućuje programirati doslovno strane povučete i ispustite slagalice, kao što je to, da su podsjeća na konstrukata će vidjeti samo jedan tjedan Dakle, kad smo se prebacili na više tradicionalnih jezik, poznat i kao C Prošle godine smo nastavili za ovaj problem skupa, uključujući za kriptografiju, remećenje informacija čuvati ga od vladine ili prijatelji ' Oči koje ne žele vidjeti. Kodirana je ovdje Poruka koja je prije vas moći će dešifrirati ili de-otimati. Bijeg je problem postavljen prošle godine, pri čemu koristite te novu pronašao programiranje vještine zapravo provesti Igra wherein-- kao ti može pozvati iz childhood-- Cilj je bio da se bash cigle koje su na vrhu zaslona Ovdje, gomilaju postići na putu, i provedbi vlastite algoritme s kojima je ovo rješenje u konačnici vam omogućuje da igraju igru. U međuvremenu, kasnije u semestar, mi ćemo vam dati rječnik od 143.091 engleskih riječi. A što će biti izazvan napisati program koji piše čekove, dokumente, po loading da mnoge riječi u memoriju što je učinkovitije moguće. Općenito ti rupičaste protiv svojih kolega Ako ste se odlučili na malo izazov vođa odbora da se vidi tko može koristiti najmanji sekundi vrijeme rada, i manjem broju od megabajta memorije, i zapravo fino ugađanje programa biti nevjerojatno štedljivih ne Samo vrijeme. Prošle godine, također, gledali smo na kraju od semestra na web programiranja. I doista, mi ćemo to učiniti i ove godine s više problematičnih setovima, vas uvodi u tehnike i razmišljanje s kojim se možete prijaviti ove vještine programiranja do web stranice, dinamičke web stranice, Web stranice koje zapravo riješiti Problemi i ponašaju drugačije i nisu samo statične mjesta s statičke informacije. Završni projekt u konačnici definirat će, ipak, Vrhunac tečaja za studente, u kojoj vi ćete biti izazvani da provede najviše bilo od interesa za vas, tako dugo dok to nekako oslanja lekcije tečaja je. I kao što ste vidjeli u Video na početku, ćemo zaključiti semestar s CS50 Hackathon, što ako, upoznati, počet će u 7:00 sati jedne noći i završiti u 7:00 ujutro sljedećeg jutra. Oko 21:00, mi ćemo Kako bi se u prvoj večeri. Oko 01:00, mi ćemo Kako bi se u drugoj večeri. A ako ste još uvijek stoji na 05:00, što će shuttle bus ti da IHOP za doručak. CS50 sajam, u međuvremenu, je događaj kojemu 2.000 plus fakulteta, studenti, i osoblje iz cijele kampusu će došao vidjeti svoje uspjehe u tijeku i konačni projekti i kreacije koji ste stvorili na svojim prijenosnim računalima, stolna računala, ili možda čak i žarulje. U međuvremenu, radno vrijeme i potporna struktura. I sada bi bilo bolja vremena za sve vas dovesti do. Radno vrijeme održat će se četiri noći tjedno za više sati svake noći s uglavnom od 20 do 30 Osoblje naravno o dužnosti odjednom pružiti vam intimni jedan-na-jedan prilike za podršku Uz naravno problem setovima. Poduke također će biti dostupni, posebno za studente manje comfortable-- ili Usudio bih se reći barem comfortable-- za koga Radno vrijeme nisu najviše njegovanje okoliša i sigurno nisu najčešće bez stresa. Pogotovo kada su rokovi pritiskom, Aktivno će vam upariti sebe s član osoblja za rad s na nekom redovitom rasporedu kao i svoje potrebe i njihov raspored dopušta. I osoblje. Dopustite mi da vas upoznam Davon, Rob, Gabriel, ovogodišnji glave. Ako bi svatko želio say-- [Pljesak] -A riječ. [Pljesak] Davon ovdje je Voditelj tečaja, a koje se znači u svom punom radnom vremenu ulozi on pomaže s izvršenjem i logistiku CS50. DAVON: Da, bok, dečki. Vidjet ćete mi puno u uredovno vrijeme. Ja ću biti nastave sekcije. A ako snimate e-mail naprijed, Vjerojatno ću se reagira. Tako ću vidjeti puno vas sve semestra. I dobrodošli u CS50. DAVID J. Malan: A sada Gabriel, koji je Sam je bio samo brucoš prošle godine, ali u posljednjih nekoliko godina ima posluje svoju verziju CS50 u Brazilu, gdje je skinuti sve content-- tečaja je što je jasno da snimio i stavio online-- tako da je mogao prevesti do Portugalci i onda naučiti više od 100 njegovih kolega više Naravno za par godina, nastava u njegovom materinjem jeziku Nastavni plan i program tečaja je. GABRIEL: Pozdrav. [Pljesak] GABRIEL: Bok, ja sam Gabriela. Ja sam šef TF tečaja. I nadam se da će vam se svidjeti CS50. Ovo je CS50. DAVID J. Malan: Sada za Rob. Ma, što želite uvod? ROB: Ne, ne znam. [Smijeh] DAVID J. Malan: A Rob Boden. [Smijeh] ROB: Bok, ja sam Rob. Ovo je moja peta godina uključen u tijeku. Svake godine, to je samo bolje i bolje klase, Dakle, vi ste očito će biti strašan. Nadam se da ćete se zabaviti s njom. Ja ću se zabaviti s njom. Dakle, vidjet ćemo se. DAVID J. Malan: I Vrijeme neće dopustiti us-- [Pljesak] Vrijeme nam neće dopustiti uvesti svima na pozornici i sve svoje kolege koji su u kupovinu nastavu danas. No, dopustite mi da vas upoznam Belinda i CS50 Puzzle Dan, koji čeka ovo dolazi u subotu, što je prvi od Naravno velikih razmjera događaja. To je jedan posebno namijenjen čekić Početna točka da je računalna znanost je u konačnici Ne radi se o programiranju, nego o rješavanju općenito problem. I Puzzle dan, kao što ćete vidi, će vas dovesti i tvoji kolege together-- nadamo se ove subote. Belinda: U redu. Bok, dečki. Dakle, hvala. Dakle, kao što je naš kapetan slavan , rekao je, moje ime je Belinda. Ja sam student na Quincy House. I, baš kao i ti dečki, uzeo CS50 prošle godine, jako je voljela. Imam soft spot za ti dečki u trećem redu. I ja sam ponosni reći, ja sam sada u počinio odnos s CS50 [nečujan]. U redu. To je bio moj jadan verzija šala. U svakom slučaju, pa se kreće na, Samo je htjela pozvati vi svi na I-laboratoriju ili HBS košnica. Mi ćemo imati Male dan od 12:00 do 03:00. I to je velika prilika za vas Dečki zadovoljiti svoje kolege CS prijatelje, riješiti neke ne-CS zagonetke, poput kapetana spomenuto, ali i jesti neke besplatna hrana, zaraditi neki strašan nagrade, kao što su poklon kartice, 75 dolara po osobi, i also-- što je to? Wii U ili nešto? Wii U? Da. Za našu tombolu. Strašan. Dakle, ja ću ostati ovdje nakon nastave. A ako vi imate bilo pitanja, javite mi. DAVID J. Malan: I vidjet ćete, s onu stranu to postoji ništa učiniti danas. Prvi problem postavljen će izaći petka. No, kako bi nas dovesti kući i danas, ja bih Vas upoznati s posebno još jedan član osoblja, Colton Ogden ovdje, čije ruke su sada zaštićeni iznad vas to MIDI kontroler čekić dom točka dalje da je računalna znanost, također, ima primjenjivost daleko izvan inženjering i matičnih i informatika sama po sebi, proteže čak i na takvim područjima glazbe. Colton je ljubazno offered-- sam mislio jedan od njih je bio idući popraviti fokus. Andrew, ako smo mogli pozvati fokusu ovamo na trenutak. Što Colton je učinio Unaprijed je Program Ovaj uređaj, to slabljenja gumba koju vidite na slici gore, kao MIDI kontroler, pri čemu svaka od ovih tipki je priključena na određenu glazbene note ili zvuk, općenito snimanje, tako da igrajući uzorke tih tipke, baš kao uzorke bitova, može predstavljati drugi viši pojmovi razini. Hoće li on biti u mogućnosti u konačnici kako bi nas odvesti kući danas ovdje? Bez dodatnih teškoća, ako bismo mogli prigušiti svjetla, i okrenuti na zaslonu iza Colton. PUBLIKA: Woo! DAVID J. Malan: Ovo je CS50. [Muziciranja] [Pljesak] To je to za CS50. Mi ćemo vas vidjeti u petak. Neki kolač vas čeka u transepta. [Muziciranja]