[Muziek] [Applaus] DAVID J. MALAN: Dit is CS50, Introductie Harvard University's de intellectuele bedrijven van de informatica en de kunst van het programmeren. Nu als u onder degenen die Elk jaar worden hier zitten met een beetje van de zenuwen in je hoofd, zoals dat je niet denkt dat je hier deel van uitmaken, je denkt dat de meeste iedereen zit om je heen weet veel meer dan jij, is inderdaad comfortabeler dan je op de computer wetenschap of computers meer algemeen, realiseren dat 78% van de studenten die nu neem CS50 nog geen ervaring. Inderdaad, er is 100 punten er op het display 78 waarvan stevige groen, wat betekent dat u, als je onder dat demografische, zijn in zeer goed gezelschap hier op uit. En als je in plaats van de 22% van de CS50 studenten die inderdaad doen hebben eerdere ervaring, zowel in middelbare school of een ander programma, beseffen dat je, ook, zal worden aangevochten in de cursus. Niet alleen hebben we verschillende tracks voor studenten minder comfortabel en meer comfortabel zowel in secties, we Ook zijn zogenaamde hacker edities meeste probleem bepaalt dat zullen die leerlingen uitdagen met dat aanvullende ervaring soortgelijke materiaal staand maar vanuit een meer verfijnde perspectief. Maar wat is de informatica? Nou ja, uiteindelijk, wat er gaat materie als je dit gebied te verkennen is niet zoveel waar je terecht komt ten opzichte van je klasgenoten, maar waar je jezelf uiteindelijk in week 12 ten opzichte van waar je hier beginnen in week nul. Nu computer goed science--, laten we noem het de wetenschap van computation-- waar berekening is eigenlijk gewoon een mooie manier om te zeggen, het nemen van een aantal input, produceren van enkele uitgang, en hiertoe door draaien algoritmen, sets van instructies voor het oplossen van een probleem op die inputs om enige output of oplossing waarin u geïnteresseerd bent. Dus we onlangs hadden gelegenheid om te reizen naar Californië voor een ontmoeting met een alumna. Haar naam is Susan Wojcicki. En ze zou graag willen spreken u hier op video om te getuigen van hoe toepasselijke zelfs alleen maar een voorproefje van de computer wetenschappen aan de inleidende niveau zijn. Zelfs als u niet gaan om te streven informatica als een veld, of zelfs engineering, of STEM meer in het algemeen, je ziet, in feite, hoe een bepaalde natuurlijk zo beïnvloed haar leven. En ze nog maar net gepakt toen ze was een senior hier aan Harvard College. Als we de lichten voor Susan kon dimmen. SUSAN Wójcicki: Hallo, wereld. Ik ben Susan Wojcicki. Ik ben de CEO van YouTube. En ik nam CS50 toen ik een senior aan Harvard in 1990. Ik was eigenlijk een geschiedenis en literatuur belangrijk. En mijn junior zomer, Ik realiseerde me dat ik misschien wilde om iets te leren over computers. En zo kwam ik terug. Ik nam CS50. Het was moeilijk, maar het was de meest verbazingwekkende klasse I nam. Het veranderde hoe ik denk over alles. En toen ik afgestudeerd aan Harvard in 1990, ging ik naar Silicon Valley. En ik heb een baan. En ik heb gewerkt in tech sindsdien. DAVID J. MALAN: Nu, wat Susan niet in deze video noemen, dat het eigenlijk in haar garage die Google zelf was opgericht door Larry en Sergey. Nu hebben we ook bereikt om onze vrienden bij code.org, een organisatie die in het afgelopen jaar is geweest om mensen in het bijzonder enthousiast over de informatica en programmering, in het bijzonder. Maar het is vermeldenswaard dat de programmering is geen informatica per se. Informatica is niet programmeren. Plaats programmering is slechts een tool-- waarmee jullie allemaal zal maar al te goed te zijn vertrouwd door end-- semester zodanig dat je niet kunt toepassen alleen maar om de toekomst cursussen in CS maar wat velden waaruit je komt, in de geesteswetenschappen, sociale wetenschappen, natuurlijke wetenschap, of dergelijke. Inderdaad laat enkele andere alumni en hun collega's om de toepasbaarheid te spreken van het veld dat te wachten staat. Bill Gates: Ik was 13 toen ik eerst kreeg toegang tot een computer. JACK DORSEY: Mijn ouders kocht me een Macintosh in 1984 toen ik acht jaar oud. Mark Zuckerberg: ik was in het zesde leerjaar. SPEAKER 1: Ik heb geleerd om te coderen op de universiteit. RUCHI Sanghvi: Freshman jaar, eerst semester, Inleiding tot de informatica. Bill Gates: Ik schreef een programma dat tic-tac-teen gespeeld. DREW HOUSTON: Ik denk dat het vrij bescheiden begin. Ik denk dat het eerste programma Ik schreef vroeg dingen als: wat is je favoriete kleur? Of hoe oud ben je? ELENA SILENOK: ik voor het eerst leerde hoe je een groene cirkel te maken en een rood vierkant op het scherm verschijnen. GABE NEWELL: De eerste keer dat ik eigenlijk had iets komen en zeggen: hallo, wereld. En ik maakte een computer dat doet. Het was gewoon verbazingwekkend. Mark Zuckerberg: Leren om het programma niet te beginnen zo willen leren alle van de informatica of proberen om dit onder de knie discipline of iets dergelijks. Het begon net buiten omdat ik wilde dit een simpel ding te doen. Ik wilde iets maken dat was leuk voor mezelf en mijn zussen. En ik schreef dit kleine programma. En dan eigenlijk gewoon toegevoegd een beetje aan. En toen moest ik om iets nieuws te leren, Ik heb het opgezocht, hetzij in een boek of op het internet, en dan nog een beetje aan. DREW HOUSTON: Het is echt niet anders dan het spelen van een instrument of iets of het spelen van een sport. DAVID J. MALAN: Oke. Dus laten we nu eigenlijk duiken in een beetje dieper. Wat zijn deze inputs en outputs dat we het hier over? Dus wat dacht je van iets simpels? Je weet waarschijnlijk wel, ook al heb je geen vertrouwdheid met informatica dan ook, dat de computers of andere manier gebruiken en begrijpt alleen nullen en enen. Maar hoe kan dat eventueel worden gegeven hoe desktops en laptops alike's veel vandaag kunnen doen? Het DNA van de dag, de enige alfabet dat ze begrijpen is nul of een. Nou ja, overweeg dan dit. Wij, mensen, hebben de neiging om het te gebruiken decimale stelsel. "December", wat betekent 10. En dat is 10, want we hebben 10 cijfers, 0 tot en met negen. Nu computers, daarentegen, meestal binary. "Bi" betekent twee. Zodat ze de neiging om alleen nul en een te gebruiken. Maar het blijkt, dat zelfs alleen met nullen en enen, dat een voldoende groot alfabet waarmee meeste vertegenwoordigen een stuk van de gegevens die u wilt, of het nu een nummer, of het nu een brief, of het nu een afbeelding of video op het scherm. Denk bijvoorbeeld, hoe wij mensen meestal interpreteren hier dit nummer. Dit is slechts drie cijfers, een, twee, drie. Maar we weten dat dit aantal aangeboren nu als 123. Maar waarom is dat? Nou, als je terugdenkt tot misschien de lagere school, je waarschijnlijk geleerd om te denken van deze aantallen als in kolommen, wanneer het is in de honderden plaats de twee in de tientallen plaats, en de drie is degene plaats. Waarom is dat eigenlijk nuttig? Nou, na te denken over de super eenvoudige rekenkundige dat we allemaal zijn geweest doet al jaren. Effectief, als je hebt een een op de honderd plaats, u de snelle wiskunde 100 maal 1 plus 10 keer 2-- omdat twee in de tientallen plek-- plus 1 keer 3-- omdat drie is degene plaats. Dus, natuurlijk, als we eigenlijk vermenigvuldig dit uit, wat we echt wat neerkomt deze pattern-- een twee three-- is 100 plus 20 plus 3, die natuurlijk is 123. Nu binair, en computers echt, fundamenteel dezelfde taal spreken dat we doen. Ze hebben gewoon een kleinere alfabet. Dus computers hebben alleen nullen en degenen die tot hun beschikking. Dus terwijl wij mensen in wezen machten van 10 in elk van deze places-- 10 de nul 10 aan die tien om de twee, waardoor u 110 en 100 respectievelijk. Omdat computers hebben slechts twee waarden ze kunnen begrijpen, nul en een, ze hebben verschillende waarden in deze kolommen, een, twee, vier. En als we bleven gaan, acht, 16, 32, 64, enzovoort. Maar het patroon en de mentaliteit is precies hetzelfde. Dus door deze logica, iedereen, hoe zou Ik ga over die het aantal een binair? Als je nog nooit hebt gedacht over dit al eerder, wat je darmen zeggen? PUBLIEK: One. DAVID J. MALAN: One. Precies. We hoeven alleen maar een een op de die plaats omdat de nullen voldoende zijn om ons noch een vier of twee. Dus een keer een is een. Nu wordt het allemaal een beetje interessant. Als ik wil hebben te vertegenwoordigen in binaire het getal twee-- maar, weer, zelfs als je nog nooit hebt gesproken deze taal vóór, hoe doen wij vertegenwoordigen in binaire de waarde die wij mensen kennen als twee? Nul een nul. Gewoon de ene in de kolom die u het wilt. Nu wordt het vrij makkelijk waarschijnlijk nu. Dus als ik wil three-- te vertegenwoordigen er is geen column drieën. Dus, nogmaals, ik kan nu deze waarden toe te voegen samen door een hier. Dus 2 maal 1 plus 1 tijd 1 is natuurlijk 3. Nu wordt het allemaal een beetje plezier in dat degenen die nu worden nullen. En vier vertegenwoordigen, krijg ik dit. En als we langzaam verhogen hier-- dat zou vijf. Dit zou zes. Dit zou zeven. Maar nu ik lijken te hebben een probleem tegenkomt. Hoe zou ik over die eight-- zou de volgende waarde. Ja, dus we hebben een nieuwe bits. En, inderdaad, als je hebt eerder gehoord deze zin, beetjes, dat is gewoon een afkorting van binair getal, nul of een. En dus ik toevallig te vertegenwoordigen slechts drie van dergelijke stukjes here. Maar als ik een manier van het opslaan niet drie verschillende stukjes, maar vier, toch kon ik vertegenwoordig acht, en dan negen, en dan 10 en zelfs hoger en hoger. Maar dat roept dan in vraag hoe we kunnen gaan over organisaties van deze dingen in de eerste plaats. Het is een ding om te tekenen ze hier op een dia op, maar hoe krijg je ze vertegenwoordigen als je een mechanisch apparaat bent? Wat is een computer doet om vertegenwoordigen de ingangen en uitgangen die fundamenteel berekening definiëren aan het eind van de dag? Nou, wat over iets super simpel als dit? Het is gewoon een gloeilamp. En ik kan dit leiden tot gloeilamp te gaan door het draaien van een aantal elektriciteit on en waardoor elektronen doorstromen, dat verandert staat of de waarde ervan, bij wijze van spreken. Zo is dit een oude school bureaulamp hier met een dergelijke gloeilamp erin. En nu is het niet echt iets nuttigs doen. Maar zodra ik de stekker er in een stopcontact en gebruik dan deze switch-- of kunnen we zelfs spreken van een transistor of denk aan het als such-- Ik kan nu vertegenwoordigen ofwel deze waarde, waar de lamp is uiteraard af, of deze waarde. Deze waarde en deze waarde. Deze waarde enzovoort. Dus binnenkant van een computer vermoedelijk zijn veel kleiner stukken hardware, maar dat eind van de dag gewoon naar electricity-- gebruiken het-- misschien vangen en dan of er iets te houden op of houden iets af. Natuurlijk is dit niet bijzonder interessant te doen met slechts een enkele gloeilamp. In feite, hoe hoog kan ik rekenen in binaire met deze bureaulamp hier? PUBLIEK: One. DAVID J. MALAN: One, toch? Ik heb meer bureaulampen als ik eigenlijk willen hogere tellen. Maar we kunnen beter doen dan dat. Omdat de lampen die we in deze dingen heb gezet zijn eigenlijk liefhebber gloeilampen dan weleer zou toestaan. En ze zijn eigenlijk genetwerkte gloeilampen. En trossen van bedrijven maken deze dingen tegenwoordig. Maar het blijkt dat vooral deze wordt geleverd met een functie waarbij U kunt de kleuren veranderen. Dus bijvoorbeeld als u versierd uw dorm room met een paar van deze licht lampen, afhankelijk van je stemming, afhankelijk van wie binnenkomt, afhankelijk van het weer, afhankelijk van de tijd van de dag, kun je eigenlijk veranderen de kleuren van de lampen in uw kamer. En dat komt omdat deze licht bollen en anderen als het wat is riep een API, een toepassing programmeerinterface die is een topic met waar je goed vertrouwd met eind semester. En dit is gewoon een mooie, cryptische manier om te zeggen, U kunt deze lichte programmeren bollen te doen wat jij wilt. U kunt ze berichten sturen net als u, een mens, kunt een bericht sturen naar een webserver zeggen, geef mij het nieuws van vandaag of geef me mijn e-mail. U kunt meer arcane sturen berichten naar deze lampen te zeggen, aan en uit te schakelen. Maar dat is niet zo interessant. Je kunt zeggen, zet op rood, draaien op groen, zet blauw, allemaal met dezelfde lamp. En je kunt zelfs met een beetje meer savvy, zeggen, draai zelf naar blauw als het een sombere dag buiten, bijvoorbeeld. Het kan eigenlijk patchen in een weer-API en ontdek wat het weer is, of de tijd dag of andere dergelijke triggers. Dus, in feite, twee Eigen medewerkers CS50's, Dan Bradley en Ansel Duff hier, vriendelijk aangeschaft ons een hele hoop van deze lampen. En ze CS50's gebouwd eerste binaire bollen, waar we hier-- hebben vertegenwoordigd met deze speelse kleine magnets-- de verschillende placeholders we gezinspeeld gewoon een beetje geleden. Dus weg hier is de die plaats, twee, vier. En we zagen niet meer dan dat. Maar, natuurlijk, ze zijn machten van twee. Acht, 16, 32, 64, en 128. Dus als ik wil nu een beetje liefhebber zijn dan het gebruik van deze oude school schakelaar, Ik heb hier op deze iPad een super eenvoudige interface dat Dan Bradley, een oud- student en nu les collega, geprogrammeerd met behulp van enkele HTML en JavaScript, dat zijn markup en programmering respectievelijk talen. En je kan waarschijnlijk see-- zelfs in de Terug-- er is een groot pluspunt en een groot minpunt, plus een knop voor elk van deze bollen. En wat dit gaat me te laten doen is, bijvoorbeeld, klikt u op het plus en nu vertegenwoordigen, van Natuurlijk, welk nummer? Een. En ik kan het nog eens raken. Twee. Drie. Four. Vijf. Zes. Zeven. En hier nu krijgen we dat rollover, maar we een vierde bit ditmaal, dus nu hebben we acht. Dus konden we dit al geruime tijd doen. In feite, als een terzijde, hoe hoog konden we rekenen? Anyone? Publiek: 255. DAVID J. MALAN: 255, toch? Niet te veel zorgen te maken over de wiskunde voor nu, maar dat is een heel behoorlijk aantal. Maar het doet eigenlijk gebonden net hoeveel stukjes informatie, als een brief, of een grafische dat we konden vertegenwoordigen. Maar het maakt niet uit voor nu. Ik ga om te gaan en zet ze allemaal uit. En als ik kon, zou ik willen vragen voor een vrijwilliger, onze eerste volunteer-- oh, hello-- op het podium. De vangst is dat je moet zijn comfortabele verschijnen, zoals je duidelijk zijn in de voorkant van al je klasgenoten, en op het internet. En laat me een beetje verder kijken dan de-- wat dacht je hier in het witte shirt? En hand omhoog. Kom maar naar boven. Wat is je naam? PUBLIEK: Jackie. DAVID J. MALAN: Jackie. Jackie, kom op. Dus wat er ook op deze iPad is een knop genaamd Game Mode. En deze Game Mode is zal me toelaten om input op voorhand een bepaalde decimaal nummer, de nummers wij mensen vertrouwd zijn. En dan zul je worden uitgedaagd hier om de knoppen te gebruiken de top-- een voor elk van deze bulbs-- om daadwerkelijk te achterhalen het patroon van gloeilampen dat staat voor het aantal in kwestie. En het spijt me, wat was je naam ook alweer? PUBLIEK: Jackie. DAVID J. MALAN: Jackie. Oke. Leuk je te ontmoeten. Dus laat me gaan en het programma in voor de wereld om het nummer 15 te zien. We zullen het klein te houden eerst hier bij. En ik ga naar Game Mode te gaan. En ik ga om aan te geven, geef ons het nummer 15. OK. En nu met iedereen watching-- als wilt u misschien staan ​​op deze manier, want het zal lijn up-- doorgaan en schakelen de acht knoppen aan de bovenkant om de bollen op te zetten of uit te schakelen als u dat nodig achten. PUBLIEK: OK. DAVID J. MALAN: En nee vreemdgaan door het raken van plus 15 keer. Oh, gaan we dat doen. PUBLIEK: Oh, wacht. Het spijt me zo. DAVID J. MALAN: U kunt ook draaien de lampen op individueel met elk van deze knoppen op de bovenkant. PUBLIEK: Oh, OK. Dus het zou like-- zijn DAVID J. MALAN: OK. Dus nu hebben we acht. Dus laten we pauzeren voor de publiek hier gaan. Welk nummer is Jackie momenteel vertegenwoordigen? 11. Dus we zijn er bijna. En uitstekend. Dus hebben we onze eerste winnaar. Gefeliciteerd. En we dachten dat we zouden moeten een aantal fantastische giveaways. Indien u graag een van dien aard zijn dorm kamer hier op de campus, je kunt jezelf een afstudeerproject gebruik nu deze API, dankzij Jackie. Dus nu-- [Applaus] --als we konden, nog een zoals rond deze. Oh, nu wil iedereen een aantal lampen. Voor de zogenaamde hakker editie, we gaan het opvoeren a-- oh, ja, vrijblijvend. Ik denk dat je komt tot nu als je hand gaat naar beneden. Wat is je naam? PUBLIEK: Alex. DAVID J. MALAN: Alex, kom eens hier. Dus voor Alex, gaan we programma in een iets groter aantal. Misschien wel in orde. Het getal 50. PUBLIEK: OK. DAVID J. MALAN: Maar, als Ik zei-- en je misschien wil hier zo staan dat de knoppen lijn als je zou expect-- maar ik deed noemen dit de hacker editie. Dus-- good luck! [Lachen] Bent u in staat om te zetten zal zijn ze indien je-- OK. Excellent. Prachtig. Gefeliciteerd. [Applaus] Ik denk dat ik zou moeten betalen. Proficiat aan Alex ook. OK. Dus de ultieme afhaalrestaurant hier is hopelijk, eerlijk gezegd, de simplicity-- de eenvoud waarmee kunt u een aantal leuke licht te krijgen bollen, blijkbaar in [onverstaanbaar]. Maar zij vertegenwoordigen, uiteindelijk, dezelfde ideeën waarmee wij mensen reeds al te bekend. Dus wat zou de volgende stap in de progressie van te proberen om iets te doen interessant met data en het vertegenwoordigen van inputs die niet alleen cijfers, maar zijn misschien letters of meer? Nou, het blijkt dat de computer wereld, voor vele jaren, gewoon aangenomen een willekeurige, maar een consistente standaard die aantallen kaarten om letters van het alfabet. Bijvoorbeeld, hier is een fragment uit dat in kaart brengen. Het heet Ascii. A-S-C-I-I. En dat is gewoon een tabel die hoofdletters letters-- kaarten in deze geval-- naar decimale getallen. Maar wat is de implicatie? Nou, als je echt wilt vertegenwoordigen iets als een e-mail of een tekst op een webpagina, u natuurlijk willen laten zien het menselijke letters van de alfabet, geen nummers. Dus afhankelijk van de context van het programma dat een gebruiker gebruikt, als het een webbrowser of een e-mail client, nummers kunnen zeker geïnterpreteerd als brieven. Dat wil zeggen, bitpatronen kan gemakkelijk worden geïnterpreteerd als brieven. En dus wat we kunnen hebben is de letter A wezen weergegeven als 65, B wordt weergegeven als 66. Dus als we een super kort woord, zoals hi, wat een computer zou uiteindelijk winkel in decimale maar echt in binaire, met behulp van enkele opeenvolging van bits, gebruik te maken van wat elektriciteit of andere manier, zouden de twee getallen 72 en 73. Maar het patroon van bits die vertegenwoordigt die waarden. Dus deze dan zijn hoe we kunnen vertegenwoordigen onze in-en uitgangen. En volstaat het om te zeggen, we kunnen doen meer complexe representaties uiteindelijk met dingen als afbeeldingen, video's, muziek en meer zoals we later deze term zullen zien. Zodat alleen verlaat dan algoritmen, deze sets van instructies waarmee we zijn het oplossen van concrete problemen. We passeren in inputs om algoritmen. En die algoritmes produceren uitgangen, hopelijk de juiste uitgangssignalen en hopelijk, ook, efficiënt vergaderd uitgangen. Met andere woorden, het is een ding te kunnen iets uit te voeren. Het is een ander ding om te implementeren iets goed of efficiënt. Bijvoorbeeld, een demonstratie dat we zijn dol op in de loop is deze. Maar deze dingen worden steeds steeds moeilijk te vinden. Maar dit is inderdaad een oude school telefoonboek, binnenste gedeelte zijn 1.000 plus pagina's van namen en telefoonnummers. En als ik wilde opzoeken iemand in dit telefoonboek, Ik kon gewoon doen een zeer naïef algoritme. Ik kon openen voor de eerste pagina en Ik zou op zoek gaan naar, zeg, iemand genaamd Mike Smith. En als hij niet op de eerste pagina, vooruitgang ik naar de tweede, en vervolgens naar het derde, en de vierde, enzovoort, totdat ik eindelijk Mike Smith. Nu is dat algoritme juist? PUBLIEK: Ja. DAVID J. MALAN: Ja. Als hij daar is, zal ik hem uiteindelijk vinden. Maar het is waarschijnlijk niet erg efficiënt, zeker niet snel, want, mijn god, waarom ben ik het verspillen van mijn tijd flipping door al deze pagina's als ik kon zeker dit fysiek sneller doen? Welnu, een lichte optimalisatie, zo te spreken, kan niet een pagina tegelijk behoren, maar twee, vier, zes, acht, 10. Nog juist? PUBLIEK: Nee DAVID J. MALAN: Dus als ik voor Zo overslaan Mike Smith. Maar zo lang als ik een back-pedaal een pagina, als ik hem voorbij schieten, misschien kunnen we corrigeren wat misschien een gotcha anders. Maar is het beter? Is het sneller? Ik bedoel, ja. Het is letterlijk twee keer zo snel als ik twee pagina's tegelijk. Dus als ik had oorspronkelijk 1.000 pagina's, nu heb ik alleen maar 500 keer omdraaien, niet volledig 1000 bladzijden krijgen potentieel in het ergste geval aan het einde van de telefoon boek, waar iemand zoals Mike Smith of iemand met een later naam zou eigenlijk. Maar, natuurlijk, we mensen zeker niet gaat dat te doen, zeker niet op dit punt in ons leven. Wat is een redelijke mens waarschijnlijk gaan doen? PUBLIEK: Ga direct naar de The9 S's. DAVID J. MALAN: Ga direct naar de S? Hoe ga ik meteen naar de S? PUBLIEK: Scheur het in tweeën. DAVID J. MALAN: Nou, er is geen markering. Dus ja, als er inderdaad een etiket of een kleverige tabblad voor S, we moeten springen daar. Maar het is vrij onschuldig. Dus het beste wat ik kan doen is ruwweg het gedeelte S of misschien ruwweg in het midden. Maar de sleutel mee te nemen nu-- en de intuïtie dat je hebt genomen voor verleend voor de jaren probably-- is dat wat doet u nu weet over dit probleem? PUBLIEK: [onverstaanbaar] DAVID J. MALAN: Mike Smith is zeker niet in deze helft van het probleem want Smith komt na het midden die ongeveer het deel M, het lijkt. Dus zoals je misschien hebt gezien op Visitas, kunnen we nu letterlijk scheuren dit probleem in de helft. PUBLIEK: Woo! DAVID J. MALAN: Het is steeds eenvoudiger. [Applaus] Daar ga je. [Lachen] En nu fundamenteel I heb het zelfde probleem, maar het is letterlijk half zo groot. Ik ben nog steeds op zoek naar Mike Smith. En ik durf te zeggen, ik kan het nog steeds hem zoeken op dezelfde manier splitsen het probleem helft nogmaals, scheuren het probleem weer in de helft, die nu laat me met Een probleem een ​​kwart van de grootte, drastisch te gooien dat de helft weg, en steeds weer herhalen van dit proces en weer en keek naar beneden op elk punt te zien Als Mike Smith op de pagina in kwestie. Nu als ik dit recht, uiteindelijk zal ik mezelf vinden met slechts een pagina waarop Mike Smith is als hij inderdaad in het telefoonboek. Natuurlijk, ik kon nooit Mike weer bellen. Maar het punt hier is dat als we begonnen met 1.000 pagina's, mijn eerste algoritme, flip de pagina, misschien 1.000 times-- zeker minder, want het is een S naam en niet een Z naam, maar als liefst 1.000 pagina's mogelijk. Tweede algoritme, beter. 500 pagina's. Ten derde algoritme, hoewel, hoeveel stappen zou het naar een 1000 pagina verdelen telefoonboek doormidden als dat? 10, te geven of te nemen. Dus alleen door flipping via dat telefoonboek, duiken en te veroveren, zo te zeggen, 10 keer, zal ik mijn weg naar beneden tot slechts een enkele pagina. En dus kunnen we deze intuïtie vastleggen nu een beetje grafisch als je gewoon overwegen deze super eenvoudige grafiek. We zijn op de x-as, of horizontale as is de grootte van mijn probleem, het aantal pagina's in het telefoonboek. En informatici algemeen willen noemen de grootte van een probleem n, waarbij n is slechts enkele variabele die represents-- in deze geval-- aantal pagina's. De verticale of y-as, is hier naar de tijd te lossen, misschien is het aantal pagina bochten, misschien is het aantal seconden of minuten, wat dan ook maateenheid is. En dus is deze rode lijn is het eerste algoritme, want er is een een op een verhouding tussen het aantal van de pagina's en de hoeveelheid tijd die het kost. Als Verizon verdubbelt het aantal pagina's in het telefoonboek van volgend jaar, mijn running tijd-- de tijd die dit in beslag die eerste algorithm-- verdubbelt in het ergste geval. Maar het tweede algoritme, waar ik flippen door twee, vereist minder tijd voor een bepaalde grootte probleem. Dus als ik dit veel pagina's hier-- bericht dat de gele lijn stelt minder tijd op te lossen. En inderdaad, vertegenwoordigt, we zullen zeggen, n meer dan twee. Maar wat is de vorm van de derde en laatste bocht uit gaat zien? Ja, het is inderdaad gaat look-- I weet niet wat je gaat zeggen. Maar laten we eens kijken wat je zou gaan zeggen. PUBLIEK: Net als dat. DAVID J. MALAN: Het gaat om te kijken als dit is een logaritmische slope-- exactly-- waarbij je deze merkwaardige helling. Het is niet langer een rechte lijn. En wat is overtuigend over, dat is dat hoewel de grafiek nu afgesneden, u kunt extrapoleren in uw erg dat die groene lijn is niet zal toenemen in hoogte dat alles veel als je verder te gaan bepaald dat de horizontale as. Inderdaad, Verizon, voor Zo zou verdubbelen het aantal pagina's in de telefoon boek tussen dit jaar en volgend jaar van 1000 tot 2000 pagina's, maar geen big deal. Met deze derde en laatste, er is een intuïtieve algoritme verdelen en veroveren. Het gaat om me hoeveel meer stappen volgend jaar om iemand te vinden Like Mike Smith? PUBLIEK: One. DAVID J. MALAN: Er is slechts een. En ze kunnen het verviervoudigen, is het kost me slechts twee stappen enzovoort. En dus dit is een bewijs van gewoon hoe sommige zorgvuldig ontwerp en enkele waardering voor wat uw ingangen zijn kunnen nog beter doen. Nu zijn we vals spelen een beetje in de zin dat we gebruik te maken van een veronderstelling. Wat is mijn veronderstelling over onze telefoonboek dat stond me toe om te verdelen en te veroveren in deze intuïtieve en toch correcte manier? PUBLIEK: [onverstaanbaar] DAVID J. MALAN: Ja. Dus het werd besteld. Het werd in alfabetische volgorde het telefoonboek bedrijf. Als het in willekeurige volgorde, dat zou een hel van een telefoonboek te zijn, maar het zou zeker niet lenen zich tot het algoritme Ik gebruikte, want je zou nooit toevallig over Mike Smith als je hield te delen in helft zo toevallig. Dus laten we nu formaliseren wat is duidelijk intuïtief. Dus iets genaamd pseudocode is waar we zullen beginnen met een aantal van onze aanvankelijke problemen. En dit is een generieke manier van het beschrijven Een algoritme of een computerprogramma, niet met C of C ++ of Java, of een specifieke taal, maar alleen met behulp van het Engels, met die een mens zou kunnen zijn vertrouwd. En we kunnen de pseudocode schrijven Dit probleem als volgt. Stap een, pak de telefoon boek. Stap twee, open voor midden van het telefoonboek. Stap drie, kijken naar de namen. Stap vier Als Smith is onder names-- En nu is dit een interessante constructie. Het is een beslissing punt. Het is een splitsing in de weg, als je zal, een tak, zo te zeggen. Dus ik ga laten inspringen alleen volgens afspraak step-- niet five-- dat is te zeg, ik zal Mike bellen. Dus dit inspringen, totaal arbitraire menselijke conventie, maar het is gewoon bedoeld om semantisch te brengen dat als Smith is onder namen, dan moet ik Mike bellen. Ondertussen in stap zes, kennisgeving dat de inkeping is gegaan. Zo anders is de andere vork in de weg, de andere weg die ik zou kunnen reizen. Dus anders als Smith eerder in het boek, wat is mijn volgende stap waarschijnlijk gaan om hier te zijn? PUBLIEK: Je gaat naar de linkerkant. DAVID J. MALAN: Ja, dus ga naar de linker helft van het telefoonboek. Gooi de rechter helft als Smith eerder in het boek is. Dus open midden de linkerhelft van het boek. En dan stap acht, ga naar drie lijn. En dit is een merkwaardige lus ik ben inducerende, een recursie zo te zeggen. Maar meer daarover in de toekomst. Ik gebruik mijn hetzelfde algoritme, mijn zelfde pseudocode, om hetzelfde probleem weer op te lossen want het enige wat er veranderd is is de omvang van het probleem, niet mijn doel, en niet de persoon Ik ben op zoek naar. Dus ik kan het algoritme hergebruiken dat ik al hebt gedefinieerd. Anders als Smith is later in book-- je misschien guess-- open voor het midden van de rechter helft van het boek. En nogmaals, ga naar drie lijn. Anders-- wat is de laatste regel In dit programma gaat het worden? Als hij niet onder de namen op de pagina Ik ben op, als hij niet eerder in het boek, en hij is niet later in het boek, wat weet ik is waar over Mike Smith nu? PUBLIEK: Hij is niet in het boek. DAVID J. MALAN: Hij is niet in het boek. Dus het beste wat ik kan doen is gewoon opgeven en stoppen met dit programma. Oke. Dus op dit punt, laten we eens een snelle rondleiding door een deel van wat te wachten staat. En in feite, ik ben hier lid geworden van door een aantal CS50 personeel. Als deze mensen konden alle join me hier op het podium. [Applaus] Let wel, dit is alleen een subset van CS50 personeel want elk jaar hebben we bijna 100 medewerkers leden in rollen van natuurlijk assistenten, Teaching Fellows, en nog veel meer. Kom maar naar boven. Dus ze zullen ons hier mee onhandig voor slechts een moment zo geven we een wervelwind tour van wat moet je hier verwachten in de loop. Dus eerst en vooral, we hebben SAT / UNS als de sortering optie in de cursus. Dit is bewust bedoeld om een ​​optie waarbij zijn als je een beetje ongemakkelijk bij het zijn in de loop, en je hoeft bang failure-- zelfs als eerlijk gezegd niet betekent kwetsen van uw GPA, om een ​​B's geen A-- die precies wat zeker een gateway Natuurlijk zoals CS50 en andere inleidende cursussen, deze indeling optie is bedoeld om. Ik steun van harte aanmoedigen students-- vooral indien op de fence-- aan de start Natuurlijk SAT / UNS, zelfs blijven SAT / UNS. Maar je kan zeker overstappen naar een brief leerjaar van de vijfde maandag in de term. Eerlijk gezegd, toen ik was een eerstejaars in 1995, Ikzelf wist niet eens nemen CS50 want ik heb niet de moed om daadwerkelijk voet stap in de klas. Het leek een domeinnaam veel te onbekend voor mij en eigenlijk alleen voor die vrienden van mij, eerlijk gezegd, die had het programmeren omdat ze waren zes of misschien wel 10 jaar oud. En het was alleen omdat ik was kunnen CS50 nemen in mijn tijd in het equivalente versie SAT / UNS-- pass / fail terug in de dag-- dat zelfs ik nam 50. En een of andere manier ben ik hier weer met u vandaag. Nu ondertussen wat je nog meer moet in gedachten te houden over 50 is gelijktijdige inschrijving. In tegenstelling tot geruchten dat je zou kunnen hebben gehoord, u kan in feite gelijktijdig inschrijven in CS50 en een andere klasse die voldoet aan dezelfde of een overlappende tijd als lezingen CS50's hier. Zie de syllabus voor de gegevens van de uitvoering daarvan. Lezingen, ondertussen, in tegenstelling tot wat is officieel in de catalogus, zal in het algemeen alleen ontmoeten voor slechts een uur. Bij gelegenheid kunnen we lopen een beetje lang. Maar houd in gedachten dat de doel in lezingen CS50's is om u te voorzien van een conceptueel overzicht, hopelijk een aantal demonstraties, misschien zelfs wat giveaways, van wat er te wachten staat voor de week die volgt. En zo in lezingen, zullen we verkennen die onderwerpen en voorbeelden bij elkaar, brengen studenten op het podium, en personeel op het podium zo vaak als we kunnen, voor slechts een paar uur per week. Secties, ondertussen, zal die door deze mensen hier-- vele van hen te leren kerels, sommige van hen natuurlijk assistants-- wil worden wekelijks gebeurt. En wat is belangrijk om te blijven in het achterhoofd is dat we denk have-- niet in tegenstelling tot de eerste Avonden, de muziek class-- verschillende tracks van secties voor studenten minder comfortabel, meer comfortabel, en ergens tussenin. En eerlijk gezegd, weet je als je bent minder comfortabel. En weet je waarschijnlijk als je bent meer comfortabel. En als je niet echt zeker, je bent per definitie ergens tussenin. Dus als het tijd is om deel in een week of zo, per de syllabus, zullen we u vragen die vraag. En u kunt zelf selecteren op basis op uw eigen comfort niveau en met students-- met groene dots-- vergelijkbaar comfort voor u. Ondertussen hebben we probleem sets, die uiteindelijk zal definieer uw ervaring in deze cursus. Ze zijn meestal aangeboden in meerdere edities. Een standaard editie die we het meest verwachten elke student in de cursus aan te pakken maar ook een zogenaamde hakker editie dat biedt geen enkele vorm van extra krediet regelrechte maar echt het opscheppen om te zeggen dat je geprobeerd en aangepakt hacker edities van de cursus die benaderen soortgelijk materiaal maar vanuit een meer verfijnde hoek. Wat wij bieden voor de standaard editie, voor, Weer een super meerderheid van studenten, zijn niet alleen walk-throughs, die zijn video's onder leiding van medewerkers van de cursus dat je echt lopen door de problemen cursus en mogelijke vormgeving implementaties. En wij ook, na de feite bieden nabespreking, waarbij als je je afvraagt hoe je zou kunnen hebben of had moeten opgelost sommige probleem, het onderwijzend personeel zal u door die op video ook. Ondertussen wachten welke ook zijn laat vijf dagen en het feit dat we zullen dalen uw laagste probleem set score. We waarderen het zeker dat in ruil voor de werklast die 50 verwacht van u, het leven in de weg staat Soms, zo niet vijf keer. En dus dit zal bieden je een beetje van flexibiliteit, uitbreiding van uw deadline van, zeg, een Donderdag 's middags naar een vrijdag' s middags. Zie de syllabus voor de implementatie details daarvan. Nu, wat wacht nu? En het wordt alleen optredende me nu hoe lang Ik heb jullie staan ​​hier op het podium. [Lachen] DAVID J. MALAN: Maar we krijgen de climax afwerking duurde niet lang. Dus wat te wachten staat op het gebied van het probleem sets? Nou ja, misschien een teaser van wat we allemaal vorig jaar deden met uw voorgangers. In de eerste Probleemverzameling Vorig jaar introduceerden we Scratch, een grafische programmeertaal die laat je letterlijk programmeren door slepen en neerzetten van puzzelstukjes, soort, die denken aan de constructen zal slechts een week te zien Vandaar dat, wanneer we overschakelen een meer traditionele taal, bekend als C. Vorig jaar gingen we dit probleem set, waarbij voor cryptografie, het decoderen van informatie om te voorkomen dat de overheid of vrienden ' ogen die je niet wilt zien. Gecodeerde hier is een bericht dat u binnenkort kunnen decoderen of de-scramble. Breakout was een probleem set van vorig jaar, waarin je deze nieuwe gevonden programmering gebruiken vaardigheden om daadwerkelijk te implementeren een spel wherein-- als je kan herinneren van childhood-- het doel was om de bash stenen die bovenop het scherm hier, de opslag een scoren langs de weg, en de uitvoering van uw eigen algoritmes waarbij deze oplossing uiteindelijk laat je het spel speelt. Ondertussen, later in de semester, zullen wij u geven een woordenboek van 143.091 woorden Engels. En je wordt uitgedaagd om een ​​programma te schrijven dat spell cheques, documenten, door laden dat veel woorden in het geheugen zo efficiënt mogelijk. Algemeen pitting u tegen je klasgenoten Als u zich aanmeldt voor een beetje een uitdaging in het klassement om te zien wie het minst kan gebruiken seconden van de looptijd, en het minste aantal megabytes aan geheugen, en eigenlijk fine-tuning van uw programma's te zijn ongelooflijk resources efficiënt niet gewoon tijd. Vorig jaar, ook, hebben we gekeken naar het einde van het semester aan web programmeren. En inderdaad, we zullen dat opnieuw doen jaar met meerdere sets probleem, introductie tot de technieken en de mentaliteit waarmee u kunt toepassen deze programmering vaardigheden om websites, dynamische websites, websites die daadwerkelijk op te lossen problemen en gedragen zich anders en zijn niet alleen statisch sites met statische informatie. Het laatste project uiteindelijk definieert echter, de climax van de cursus voor studenten, waarin u zult worden uitgedaagd om te implementeren bijna alles van belang aan u, zo lang als het een of andere manier baseert zich op de lessen van de cursus. En zoals je zag in de video bij de start, zullen we het semester met de conclusie CS50 Hackathon, dat indien, onbekende, zal beginnen om 07:00 een nacht en eindigen om 7:00 uur de volgende ochtend. Rond 09:00 gaan we Om in eerste diner. Rond 01:00 gaan we Om in tweede diner. En als je nog steeds staan ​​op 05:00, we zal pendelbus u naar IHOP voor het ontbijt. De CS50 Fair, ondertussen, is een evenement waaraan 2.000 plus docenten, studenten, en medewerkers uit de hele campus zal komen om je prestaties te zien in de loop en de uiteindelijke projecten en creaties die u op uw laptop, desktops, of misschien zelfs gloeilampen. Ondertussen kantooruren en de steunconstructie. En nu zou het geweest een betere tijd om u allen brengen. Spreekuur vindt plaats vier nachten een week voor meerdere uren elke nacht algemeen 20 tot 30 van de personeel cursus van dienst in een keer om u te voorzien van intieme een-op-een mogelijkheden voor ondersteuning met de cursus probleem sets. Tutoring ook zal zijn beschikbaar, met name voor studenten minder comfortable-- of durven zeggen minstens comfortable-- voor wie openingstijden zijn niet de stimulerendste milieu en zeker niet het meest stress-vrij. Vooral wanneer deadlines te drukken, we zullen proactief koppelen u ons met een lid van het personeel om te werken met op sommige reguliere schema zoals uw behoeften en hun schema het toelaat. En personeel. Sta mij toe om Davon, Rob introduceren, en Gabriel, de hoofden van dit jaar. Wilt u elke willen zeggen-- [Applaus] --een woord. [Applaus] Davon hier is de manager opleiding, die betekent in zijn voltijds rol Hij helpt bij de uitvoering en de logistiek van de CS50. DAVON: Ja, hallo, jongens. Je zult een hoop te zien om me op het kantoor uren. Zal ik onderwijzen secties. En als je e-mails vooruit te schieten, Ik zal waarschijnlijk te reageren. Dus ik zie heel veel van jullie het hele semester. En welkom bij CS50. DAVID J. MALAN: En nu Gabriel, die zelf was gewoon een eerstejaars vorig jaar, maar voor de afgelopen paar jaar heeft de exploitatie van zijn eigen versie van CS50 in Brazilië, waardoor hij gedownload alle content-- de cursus hetgeen duidelijk wordt gefilmd en geplaatst online-- zodat hij kon vertalen naar Portugese en vervolgens te leren meer dan 100 van zijn klasgenoten over de loop van een paar jaar, onderwijs in zijn moedertaal curriculum van de cursus. GABRIEL: Hello. [Applaus] GABRIEL: Hoi, ik ben Gabriel. Ik ben het hoofd TF van de cursus. En ik hoop dat u zult genieten van CS50. Dit is CS50. DAVID J. MALAN: nu voor Rob. Oh, je inleiding wil? ROB: Nee, ik weet het niet. [Lachen] DAVID J. MALAN: En Rob Boden. [Lachen] ROB: Hoi, ik ben Rob. Dit is mijn vijfde jaar betrokken bij de cursus. Elk jaar, het is gewoon een beter en betere klasse, dus jullie zijn duidelijk zal geweldig zijn. Ik hoop dat jullie allemaal plezier mee te hebben. Ik ga om plezier te hebben met het. Zo zie je rond. DAVID J. MALAN: En de tijd zal niet toestaan ​​ons-- [Applaus] De tijd zal het ons niet toe iedereen introduceren op het podium en al hun collega die winkelen klassen vandaag. Maar staat u mij toe om te introduceren Belinda en CS50 Puzzle Dag, die deze wacht komende zaterdag, waarin is de eerste van de grootschalige evenementen cursus. Deze in het bijzonder bedoeld te hameren op het punt dat informatica is uiteindelijk niet over programmeren, maar over het oplossen van problemen in het algemeen. En Puzzle Day, zoals u zult zien, brengt u en je klasgenoten together-- we hopen dat dit zaterdag. BELINDA: OK. Hoi, jongens. Dus bedankt. Dus als onze illustere kapitein zei, mijn naam is Belinda. Ik ben een tweedejaars op Quincy House. Ik, net als jullie, nam CS50 vorig jaar, vonden het geweldig. Ik heb een zwak voor jullie in de derde rij. En ik ben trots om te zeggen, ik ben nu in een vaste relatie met CS50 [onverstaanbaar]. OK. Dat was mijn kreupele versie van een grap. Hoe dan ook, dus bewegen op, wilde alleen maar uit te nodigen jullie allemaal op de i-lab, of HBS netelroos. We gaan te hebben Puzzel Dag 12:00-03:00. En het is een geweldige kans voor u jongens om je collega CS vrienden te ontmoeten, oplossen van een aantal niet-CS puzzels, zoals Captain genoemd, en ook eten wat gratis eten, verdient een aantal geweldige prijzen, zoals cadeaubonnen, $ 75 per persoon, en also-- wat was het? Wii U of zo? Wii U? Ja. Voor onze tombola. Awesome. Dus ik zal blijven hangen na de les. En als jullie nog vragen, laat het me weten. DAVID J. MALAN: En je zult zien, dan dit is er niets te doen vandaag. Het eerste probleem vastgesteld gaat uit vrijdag. Maar om ons naar huis te brengen vandaag, wil ik graag u kennismaken met name een meer lid van het personeel, Colton Ogden hier, wier handen zijn nu boven je beschermd met Deze MIDI-controller naar het huis van de punt verder hamer dat informatica, ook, heeft toepasbaarheid veel verder dan techniek en STEM en informatica zelf, zelfs uit te breiden tot dergelijke domeinen als muziek. Colton heeft vriendelijk offered-- ik dacht een van hen was van plan om de scherpstelling vast. Andrew, als we konden opbrengen aandacht hier voor slechts een moment. Wat Colton heeft gedaan vooraf is het programma dit apparaat, dit pad van de knoppen dat je hier ziet afgebeeld up, als een MIDI-controller, waarbij elk van deze knoppen is aangesloten op een bepaalde muzieknoot of een geluid algemeen een opname, zodanig dat door het spelen van patronen van deze knopen, net als bitpatronen, kunnen andere vormen hogere concepten. Zal hij in staat zijn uiteindelijk hier aan ons huis te nemen vandaag? Zonder verdere omhaal, indien we konden de lichten dimmen, en zet het scherm achter Colton. PUBLIEK: Woo! DAVID J. MALAN: Dit is CS50. [Muziek] [Applaus] Dat is het voor CS50. We zullen je zien vrijdag. Sommige taart wacht op u in het transept. [Muziek]