[MÚSICA DE JOGO] [Aplausos] David J. MALAN: Este é CS50, Introdução da Universidade de Harvard ao intelectual empresas de informática ea arte da programação. Agora, se você está entre aqueles que a cada ano está sentado aqui com um pouco de nervosismo em sua mente, tais que você não acha que você é aqui, Você acha que a maioria alguém sentado ao seu redor sabe muito mais do que você, é de fato mais confortável do que no computador ciência ou computadores de modo mais geral, percebe que 78% dos alunos que agora tomar CS50 tem nenhuma experiência prévia. De fato, há 100 pontos lá no visor, 78 dos quais são verde contínuo, o que significa que, se você está entre esse grupo demográfico, estão em muito boa companhia daqui em diante. E se você estiver em vez entre os 22% dos estudantes que fazem de fato CS50 ter experiência anterior, seja em ensino médio ou algum outro programa, perceber que você, também, vai ser contestada no curso. Não só temos diferentes faixas para os alunos menos confortável e mais confortável iguais em seções, também chamado edições de hackers de mais conjuntos de problemas que vai desafiar os alunos com essa experiência adicional para explorar material semelhante mas a partir de um mais perspectiva sofisticado. Mas o que é ciência da computação? Bem, em última análise, o que vai importa como você explorar este campo não é tanto que você acaba em relação a seus colegas de classe, mas onde você mesmo acabar em semana 12 versus onde você começa aqui na semana zero. Agora computador science-- bem, vamos chamam a ciência da computation-- onde a computação é realmente apenas uma maneira elegante de dizer, tendo alguma entrada, produzir alguma saída, e fazê-lo por meio de algoritmos que executam, conjuntos de instruções para resolver algum problema nesses inputs de forma a produzir cerca de saída ou solução na qual você está interessado. Então, recentemente, tivemos oportunidade de viajar para fora para a Califórnia para se encontrar com uma aluna. O nome dela é Susan Wojcicki. E ela gostaria de falar para você aqui em vídeo para testemunhar o quão aplicável mesmo apenas uma amostra do computador ciência no nível introdutório pode ser. Mesmo se você não ir para prosseguir ciência da computação como um campo, ou até mesmo a engenharia, ou STEM mais geral, você vai ver, na verdade, como um certo Claro que tanto influenciou sua vida. E ela apenas tomou quando ela estava no último ano aqui na faculdade de Harvard. Se pudéssemos diminuir as luzes para Susan. SUSAN Wojcicki: Olá, mundo. Estou Susan Wojcicki. Eu sou o CEO do YouTube. E tomei CS50 quando eu era um sénior na Universidade de Harvard em 1990. Eu era realmente uma história e grande literatura. E o meu verão júnior, Eu percebi que talvez eu queria aprender algo sobre computadores. E assim, eu voltei. Tomei CS50. Foi difícil, mas foi o mais classe incrível que eu tomei. Ele mudou a forma como eu penso sobre tudo. E quando eu me formei em Harvard em 1990, fui para o Vale do Silício. E eu tenho um emprego. E eu tenho trabalhado em tecnologia desde então. DAVID J. MALAN: Agora que Susan não mencionou neste vídeo, que era, na verdade, em sua garagem que o próprio Google foi fundada por Larry e Sergey. Agora também estendeu a mão para os nossos amigos em code.org, uma organização que em relação ao ano passado foi levar as pessoas particularmente animado sobre ciência da computação e de programação, em particular. Mas é importante notar que a programação não é ciência da computação per se. A ciência da computação não está programando. Em vez de programação é apenas uma tool-- com que todos vocês será muito bem familiarizado com end-- semestre de tal forma que você pode não se aplicar apenas para os futuros cursos de CS mas para o que quer que os campos de onde você está vindo, em humanidades, ciências sociais, natural ciência, ou semelhantes. De fato, permitir que alguns outros ex-alunos e seus colegas para falar com a aplicabilidade do campo que o espera. BILL GATES: Eu tinha 13 anos quando eu primeiro tem acesso a um computador. Jack Dorsey: Meus pais me comprou um Macintosh em 1984 quando eu tinha oito anos de idade. Mark Zuckerberg: Eu estava na sexta série. COLUNA 1: Eu aprendi a programar na faculdade. Ruchi Sanghvi: primeiro ano, primeiro semestre, Introdução à Ciência da Computação. BILL GATES: Eu escrevi um programa que jogou tic-tac-toe. DREW HOUSTON: Eu acho que foi começos muito humildes. Acho que o primeiro programa Escrevi perguntou coisas como: qual é a sua cor favorita? Ou quantos anos você tem? ELENA SILENOK: Eu aprendi primeiro como fazer um círculo verde e um quadrado vermelho aparecerá na tela. Gabe Newell: O primeiro vez que eu realmente tinha algo chegar e dizer: Olá, mundo. E eu fiz um computador fazer isso. Foi simplesmente incrível. Mark Zuckerberg: Aprender para o programa não começou como querendo aprender tudo de ciência da computação ou tentando dominar essa disciplina ou qualquer coisa assim. Ele só começou porque eu queria fazer uma coisa simples. Eu queria fazer algo que Foi divertido para mim e para minhas irmãs. E eu escrevi este pequeno programa. E então, basicamente, apenas adicionado um pouco a ele. E então, quando eu precisava para aprender algo novo, Eu olhei para cima, seja em um livro ou na internet, e, em seguida, adicionado um pouco a ele. DREW HOUSTON: Realmente não é diferente de tocar um instrumento ou algo ou praticar um esporte. DAVID J. MALAN: Tudo bem. Então, nós vamos agora, na verdade, mergulhar um pouco mais fundo. Quais são essas entradas e saídas que estamos falando aqui? Então, que tal algo simples? Você provavelmente sabe, mesmo se você tiver nenhuma familiaridade com a informática que seja, de que os computadores de alguma forma usar e compreende apenas zeros e uns. Mas como é que isso pode, eventualmente, ser dada como desktops quanto laptops de hoje e da mesma forma pode fazer? O DNA do dia, a única alfabeto que eles compreendam é um zero ou um um. Bem, considere isso. Nós, os seres humanos, tendem a utilizar a sistema decimal. "Dezembro", que significa 10. E isso é 10 porque temos 10 dígitos, de 0 a nove. Agora, os computadores, por contraste, tendem a utilizar binário. "Bi" significa dois. Assim, eles tendem apenas zero e um para usar. Mas acontece que, mesmo apenas com zeros e uns, que é suficientemente grande alfabeto com a qual a representar mais qualquer pedaço de dados que você quer, se é um número, se é uma carta, se é um gráfico ou de vídeo na tela. Considere, por exemplo, como nós, seres humanos normalmente interpretar esse número aqui. Este é apenas três dígitos, um, dois, três. Mas sabemos que este número innately agora como 123. Mas por que isso? Bem, se você acha que volta talvez para a escola primária, você provavelmente foi ensinado a pensar em estes números como sendo, em colunas onde um é na ordem das centenas lugar, a dois está na casa das dezenas, e os três está na casa das unidades. Por que isso é realmente útil? Bem, pense sobre o aritmética super simples que todos nós temos sido fazendo há anos. Efetivamente, se você tem um na casa das centenas, Você faz a matemática rápida 100 vezes 1 mais 10 vezes 2-- porque dois é na casa das dezenas lugar-- mais 1 vezes 3-- porque três é na casa das unidades. Assim, é claro que, se realmente multiplicar isso, o que nós realmente estamos representando com este pattern-- dois três-- é de 100 mais 20 mais 3, o que, naturalmente, é de 123. Agora binário, e os computadores realmente, fundamentalmente falam a mesma língua o que fazemos. Eles só têm um alfabeto menor. Assim, os computadores só tem zeros e aqueles à sua disposição. Assim, enquanto nós seres humanos temos essencialmente potências de 10 em cada uma dessas places-- 10 para o zero, a 10 a um, dez para os dois, dando-lhe 110 e 100 respectivamente. Como os computadores só tem dois valores que eles possam compreender, zero e um, eles têm que usar valores diferentes nessas colunas, um, dois, quatro. E se continuou, oito, 16, 32, 64, e assim por diante. Mas o padrão e o mentalidade é exatamente o mesmo. Então, por esta lógica, qualquer um, como seria Eu vou sobre o que representa o número um binário em? Se você nunca sequer pensou em isso antes, o que é seu intestino dizer? AUDIÊNCIA: One. DAVID J. MALAN: One. Exatamente. Só precisamos de um um no queridos lugar porque os zeros suficiente para nos dar nem um, nem um de quatro dois. Então, um vezes um é igual a um. Agora as coisas ficam um pouco interessante. Se eu quiser representar em binário o número dois-- mas, novamente, mesmo que você nunca fala essa linguagem, antes, como é que vamos representar em binário O valor que os humanos sabem como dois? Zero um zero. Basta colocar um no coluna que você quer. Agora está ficando muito fácil provavelmente agora. Então, se eu quiser representar três-- há nenhuma coluna três. Então, novamente, eu agora pode adicionar esses valores juntos, colocando um aqui. Portanto, 2 vezes 1 mais 1 vezes 1 é, evidentemente, 3. Agora as coisas ficam um pouco de diversão aqueles que agora se tornou zero. E para representar quatro, eu entendo isso. E se aumentar lentamente aqui-- que seria cinco. Este seria seis. Este seria sete. Mas agora me parece ter deparar com um problema. Como eu poderia ir sobre a representação eight-- seria o próximo valor. Sim, por isso precisamos de uma nova bits. E, de fato, se você tiver ouviu esta frase antes, pedaços, isso é apenas a abreviação de dígito binário, zero ou um. E assim acontece que eu estar representando apenas três desses pedaços aqui. Mas se eu tivesse uma maneira de não armazenar três diferentes bits, mas quatro, com certeza eu poderia representar oito, nove e depois, e depois 10, e ainda mais e mais. Mas que chama então em causa como podemos ir sobre o que representa estes coisas em primeiro lugar. É uma coisa para desenhar los aqui em um slide, mas como você representá-los se você é um dispositivo mecânico? O que é um computador que faz a representam as entradas e saídas que fundamentalmente definir computação no fim do dia? Bem, o que dizer de algo super simples como este? É apenas uma lâmpada. E eu posso acionar essa lâmpada para ir em girando um pouco de eletricidade on e permitindo que os elétrons a fluir através de, que muda a sua estado ou o seu valor, por assim dizer. Por exemplo, esta é uma lâmpada de mesa velha escola aqui com um tal lâmpada dentro dele. E agora não é realmente fazendo algo útil. Mas assim que eu ligá-lo a uma tomada eléctrica e, em seguida, usar esse switch-- ou podemos até chamá-lo de um transistor ou pensar nele como such-- Agora eu posso representar tanto esse valor, caso a lâmpada do obviamente, fora, ou esse valor. Este valor ou esse valor. Este valor e assim por diante. Então, dentro de um computador, presumivelmente, são peças muito menores de hardware, mas que no final do dia simplesmente ter usar electricity-- talvez capturar ele-- e em seguida, manter algo ou manter algo fora. É claro, este não é particularmente interessante para fazer com apenas uma única lâmpada. Na verdade, o quão alto posso contar em binária com esta lâmpada de mesa aqui? AUDIÊNCIA: One. DAVID J. MALAN: um, certo? Preciso de mais lâmpadas de mesa se eu realmente quer contar superior. Mas podemos fazer melhor que isso. Porque as lâmpadas que nós colocamos nestas coisas são realmente extravagantes lâmpadas do que antigamente permitia. E eles são, na verdade, lâmpadas em rede. E grupos de empresas fazer essas coisas nos dias de hoje. Mas verifica-se que este em particular vem com um recurso através do qual você pode alterar suas cores. Assim, por exemplo, se adornada seu quarto do dormitório com alguns destes luz lâmpadas, dependendo do seu humor, dependendo de quem vem, , dependendo do tempo, dependendo o tempo do dia, você pode realmente mudar as cores as lâmpadas no seu quarto. E isso é porque estes luz lâmpadas e outros como ele tem o que é chamado de uma API, uma aplicação interface de programação, que é um tema com o qual você estará bem familiarizado com até o final do semestre. E esta é apenas uma fantasia, forma críptica de dizer: você pode programar estes luz lâmpadas para fazer o seu lance. Você pode enviar-lhes mensagens assim como você, um ser humano, pode enviar uma mensagem para um servidor web dizendo, dá-me a notícia de hoje ou dar-me o meu e-mail. Você pode enviar mais arcano mensagens para essas lâmpadas quer dizer, ligar e desligar. Mas isso não é tão interessante. Você pode dizer, ligue vermelho, ligar verde, ligue azul, todas com a mesma lâmpada. E você ainda pode, com um pouco mais savvy, dizem, vire-se para o azul quando é um dia sombrio fora, por exemplo. Ela pode realmente consertar em uma API tempo e descobrir que o tempo é, ou o tempo do dia, ou outros tais gatilhos. Assim, na verdade, dois Próprios membros da equipe do CS50, Dan Bradley e Ansel Duff aqui, por favor adquiridos nós um monte dessas lâmpadas. E eles construíram CS50 da primeiros bolbos já binários onde temos representado aqui-- com estes pequenos magnets-- brincalhão os vários espaços reservados nós aludido apenas um pouco atrás. Então até aqui é o queridos lugar, dois, quatro. E nós não vimos mais alto do que isso. Mas, é claro, eles são potências de dois. Oito, 16, 32, 64 e 128. Então, se eu agora quero ser um pouco amador que o uso dessa opção da velha escola, Eu tenho aqui neste iPad uma interface simples super que Dan Bradley, ex- estudante e agora ensinando companheiro, programado usando algum HTML e JavaScript, que são de marcação e programação idiomas respectivamente. E você pode provavelmente ver-- mesmo na traseira-- há uma grande vantagem e uma grande desvantagem, mais um botão para cada uma dessas lâmpadas. E o que isso vai me deixar não é, por exemplo, clique no sinal de mais e agora representam, de Naturalmente, o que número? Uma. E eu posso batê-lo novamente. Dois. Três. Quatro. Cinco. Six. Sete. E aqui agora temos que rollover, mas temos um quarto bit este tempo, então agora temos oito. Então, nós poderíamos fazer isso por algum tempo. De fato, como um aparte, quão alto poderíamos contar? Qualquer um? AUDIÊNCIA: 255. DAVID J. MALAN: 255, certo? Não se preocupe muito com a matemática para agora, mas que é um número bastante decente. Mas, na verdade, não vinculada apenas quantas peças de informação, como uma carta ou um gráfico que poderia representar. Mas não importa agora. Eu estou indo para ir em frente e transformá-los todos fora. E se eu pudesse, eu gostaria de pedir um voluntário, o nosso primeiro volunteer-- oh, hello-- no palco. O problema é que você tem que ser confortável aparecendo, como você claramente estão na frente de todos os seus colegas de classe, , assim como na internet. E deixe-me olhar um pouco além o-- E aqui na camisa branca? E entregar-se. Vamos lá para cima. Qual é o seu nome? AUDIÊNCIA: Jackie. DAVID J. MALAN: Jackie. Jackie, vamos lá para cima. Então, o que há é também neste iPad é um botão chamado Modo de Jogo. E este modo de jogo é vai me permitir a entrada antecipadamente um decimal especial número, os números que os seres humanos são familiarizado. E então você será desafiado aqui para usar os botões na para uma top-- cada um destes bulbs-- para realmente descobrir o padrão de lâmpadas que representa o número em questão. E eu sinto muito, o que era o seu nome? AUDIÊNCIA: Jackie. DAVID J. MALAN: Jackie. Tudo certo. Prazer em conhecê-lo. Então deixe-me ir em frente e no programa para que o mundo veja o número 15. Vamos mantê-lo pequeno a princípio aqui. E eu estou indo para entrar em Modo de Jogo. E eu vou especificar, dá-nos o número 15. Está bem. E agora, com todos watching-- se você quer se destacar, talvez desta maneira, porque ele vai alinhar up-- vá em frente e alternar entre os oito botões na parte superior para ligar as lâmpadas em ou fora como você vê o ajuste. AUDIÊNCIA: OK. DAVID J. MALAN: E sem batota por bater mais de 15 vezes. Oh, nós vamos fazer isso. AUDIÊNCIA: Oh, espere. Eu sinto muito. DAVID J. MALAN: Você também pode ativar as lâmpadas em individualmente com cada um desses botões na parte superior. AUDIÊNCIA: Oh, OK. Portanto, seria como-- DAVID J. MALAN: OK. Portanto, agora temos oito. Então, vamos fazer uma pausa para o público a participar aqui. O número é Jackie representando actualmente? 11. Então, nós estamos quase lá. E excelente. Portanto, temos o nosso primeiro vencedor. Parabéns. E nós pensamos que teríamos alguns brindes fabulosos. Se você gostaria de ser um desses dormitório quarto aqui no campus, pode-se ter um projeto final usando agora esta API, graças a Jackie. Então agora-- [Aplausos] --if pudéssemos, mais uma tal em torno deste. Oh, agora todo mundo quer algumas lâmpadas. Para a chamada edição hacker vamos rampa-lo a-- oh, sim, evasiva. Acho que está chegando agora se sua mão está indo para baixo. Qual é o seu nome? AUDIÊNCIA: Alex. DAVID J. MALAN: Alex, venha aqui. Assim, para Alex, vamos programa de um número ligeiramente maior. Talvez em ordem. O número 50. AUDIÊNCIA: OK. DAVID J. MALAN: Mas, como Eu disse-- e que você pode quero ficar aqui para que que os botões se alinham como seria expect-- mas eu fiz chamar esta edição hacker. Assim-- boa sorte! [Risos] Você vai ser capaz de transformar los se você-- OK. Excelente. Maravilhoso. Parabéns. [Aplausos] Acho que eu deveria pagar. Parabéns ao Alex também. Está bem. Assim, o takeaway final aqui está espero, sinceramente, o simplicity-- o simplicidade com que você pode obter alguma luz agradável lâmpadas, aparentemente em [inaudível]. Mas eles representam, em última análise, as mesmas idéias com o qual nós, seres humanos são já muito familiar. Então, o que pode próxima passo estar na progressão de tentar fazer alguma coisa interessante com dados e representando as entradas que não são apenas números, mas são talvez cartas ou mais? Bem, acontece que o mundo da informática, por muitos anos, simplesmente adoptou um arbitrário, mas um padrão consistente que mapeia números para as letras do alfabeto. Por exemplo, aqui está um trecho do mapeamento. É chamado Ascii. A-S-C-I-I. E isso é simplesmente uma tabela que mapeia letters-- maiúscula neste caso-- em números decimais. Mas qual é a implicação? Bem, se você realmente quer representar algo como um e-mail ou algum texto em uma página web, você obviamente quer mostrar as letras humanos da alfabeto, não números. Então, dependendo do contexto do programa que um usuário está usando, se é um navegador ou cliente de e-mail, números pode ser certamente interpretada como letras. Ou seja, os padrões de bits pode facilmente ser interpretada como letras. E então o que podemos ter é a letra A ser representada como 65, B sendo representado como 66. Então, se temos um super palavra curta, como oi, o que um computador faria em última instância loja em decimal, mas realmente em binário, usando uma sequência de bits, alavancando um pouco de eletricidade, de alguma forma, seriam os dois números 72 e 73. Mas o padrão de bits que representa os valores. Portanto, estas são, então, como podemos representam nossas entradas e saídas. E basta dizer, nós podemos fazer representações mais complexas em última análise, com coisas como gráficos, vídeos, música e muito mais como veremos no final deste prazo. Então, isso só deixa então algoritmos, esses conjuntos de instruções com o qual estamos resolvendo problemas reais. Estamos passando em insumos para algoritmos. E esses algoritmos estão produzindo saídas, saídas espero corretas e, esperamos, também, eficientemente reunidos saídas. Em outras palavras, é uma coisa implementar algo corretamente. É outra coisa para implementar algo bem ou eficiente. Por exemplo, uma demonstração que estamos Apaixonado por no curso é este. Mas essas coisas estão ficando cada vez mais difícil de encontrar. Mas esta é realmente uma velha escola livro de telefone, dentro do qual são 1.000 páginas, mais de nomes e números de telefone. E se eu quisesse olhar para cima alguém nesta lista telefónica, Eu poderia simplesmente fazer uma algoritmo muito ingênuo. Eu poderia abrir a primeira página, e Eu poderia começar a procurar, por exemplo, alguém chamado Mike Smith. E se ele não estiver na primeira página, que progride para o segundo, e, em seguida, para o terceiro, e depois para o quarto, e assim por diante, até que eu finalmente encontrar Mike Smith. Agora é que o algoritmo correto? AUDIÊNCIA: Sim. DAVID J. MALAN: Yeah. Se ele estiver lá, eu vou eventualmente encontrá-lo. Mas não é, sem dúvida, muito eficiente, certamente não é rápido, porque, meu Deus, por que eu sou desperdiçando meu tempo flipping através de todas essas páginas quando podia certamente fazer isso fisicamente mais rápido? Bem, uma pequena otimização, de modo a falar, pode não ser uma página de cada vez, mas dois, quatro, seis, oito, 10. Ainda correto? AUDIÊNCIA: Não DAVID J. MALAN: Portanto, não se eu para exemplo pular Mike Smith. Mas enquanto eu voltar pedal uma página, se eu ultrapassar ele, talvez pudéssemos corrigir o que poderiam ser uma pegadinha. Mas será que é melhor? É mais rápido? Quero dizer, sim. É, literalmente, duas vezes mais rápido se eu fazer duas páginas de cada vez. Então, se eu originalmente tinha 1.000 páginas, agora eu só tenho que virar 500 vezes, não é total de 1.000 páginas para obter potencialmente, no pior caso para o final do telefone livro, em que alguém como Mike Smith ou alguém com um nome mais tarde pode realmente ser. Mas, é claro, nós os seres humanos não são certamente vai estar fazendo isso, certamente não neste momento de nossas vidas. O que é um razoável humana provavelmente vai fazer? AUDIÊNCIA: Vá direto para The9 S de. DAVID J. MALAN: ir direto para o S do? Como faço para ir direto para o S do? AUDIÊNCIA: Rip-o ao meio. DAVID J. MALAN: Bem, não há nenhuma marcação. Então, sim, se houvesse de fato um rótulo ou uma guia pegajosa para S, devemos ir direto lá. Mas é bastante inócuo. Então, o melhor que posso fazer é mais ou menos para a seção S ou talvez mais ou menos para o meio. Mas o principal argumento agora-- ea intuição que você tomou para concedido por anos probably-- é que o que você faz agora sabe sobre este problema? AUDIÊNCIA: [inaudível] DAVID J. MALAN: Mike Smith é certamente não dessa metade do problema porque Smith vem depois do meio que é aproximadamente o ponto M, parece ser. Então, como você pode ter visto em Visitas, agora podemos literalmente rasgar este problema pela metade. AUDIÊNCIA: Woo! DAVID J. MALAN: É cada vez mais fácil. [Aplausos] Lá você vai. [Risos] E agora eu fundamentalmente têm o mesmo problema, mas é, literalmente, metade do tamanho. Eu ainda estou procurando por Mike Smith. E eu ouso dizer, eu ainda posso procurá-lo, da mesma forma, dividir o problema em metade novamente, rasgando o problema novamente ao meio, que agora deixa-me com um problema de um quarto do tamanho, jogar dramaticamente que meia de distância, e repita este processo uma e outra vez e de novo, olhando para baixo em cada ponto para ver se o Mike é em Smith a página em questão. Agora, se eu fizer isso direito, em última análise, eu vou encontrar-me com apenas uma página na qual Mike Smith é se ele está de fato no livro de telefone. Claro, eu poderia nunca chamar Mike novamente. Mas o ponto aqui é que se começou a com 1.000 páginas, meu primeiro algoritmo, virar a página, talvez 1.000 vezes-- definitivamente menos porque é um nome de S e não um nome de Z, mas como muitos como 1.000 páginas, potencialmente. Segundo algoritmo, melhor. 500 páginas. Terceiro algoritmo, no entanto, quantos passos seria ele levar a dividir uma página 1000 lista telefônica ao meio assim? 10, mais ou menos. Então, só por folhear que lista telefônica, mergulho e conquistando, por assim dizer, 10 vezes, farei meu caminho para baixo a apenas uma única página. E assim podemos capturar essa intuição agora um pouco graficamente se você considerar apenas Neste gráfico super simples. Estamos no eixo x, ou horizontal eixo, é o tamanho do meu problema, o número de páginas no livro de telefone. E cientistas da computação geralmente gostam de chamar o tamanho de um problema n, em que n é apenas uma variável que represents-- neste caso-- número de páginas. O eixo y vertical, ou, aqui está vai ser o tempo para resolver, talvez o número de viradas de página, talvez o número de segundos ou minutos, independentemente sua unidade de medida é. E assim esta linha vermelha representa o primeiro algoritmo, porque há um 1-1 relação entre o número de páginas e quantidade de tempo que leva. Se Verizon dobra o número de páginas da lista telefônica no ano que vem, minha corrida tempo-- o tempo necessário para executar aquele primeiro algorithm-- dobra na pior das hipóteses. Mas o segundo algoritmo, onde estou lançando a dois, requer menos tempo para um determinado problema de tamanho. Então, se eu tiver isso, muitos páginas aqui-- aviso que a linha amarela sugere menos tempo para resolver. E, de fato, representa, vamos dizer, n mais de dois. Mas o que é a forma da terceira e curva final, vai parecer? Sim, ele é, na verdade vai look-- I Não sei o que você ia dizer. Mas vamos ver o que você ia dizer. AUDIÊNCIA: Assim. DAVID J. MALAN: Vai parecer este, um exactly-- slope-- logarítmica em que você tem essa inclinação curiosa. Já não é uma linha reta. E o que é interessante sobre isso é que embora o gráfico está agora cortada, você pode extrapolar em sua importa que essa linha verde não é vai aumentar em altura tudo o que muito à medida que avançar ainda mais abaixo desse eixo horizontal. De fato, Verizon, por exemplo, pode dobrar o número de páginas no telefone livro entre este ano e no próximo ano a partir de 1000 a 2000 páginas, mas não é grande coisa. Com esta terceira e última, há um algoritmo intuitivo de dividir e conquistar. Vai me levar quantos mais as etapas no próximo ano para encontrar alguém como Mike Smith? AUDIÊNCIA: One. DAVID J. MALAN: Há apenas um. E eles podem quadruplicar isso, é vai me levar apenas mais dois passos e assim por diante. E por isso esta é uma prova apenas como algum projeto cuidadoso e alguns apreço por aquilo que suas entradas são pode fazer ainda melhor. Agora, estamos enganando a pouco no sentido que estamos alavancando uma suposição. Qual é a minha suposição sobre o nosso livro de telefone que me permitiu dividir e conquistar desta forma intuitiva e ainda correcta? AUDIÊNCIA: [inaudível] DAVID J. MALAN: Yeah. Por isso, foi encomendado. Foi classificada pelo a companhia telefônica. Se fosse em ordem aleatória, que seria um inferno de um catálogo telefônico, mas certamente não o faria prestar-se para o algoritmo Eu usei, porque você nunca faria só acontecerá através de Mike Smith se você manteve a divisão em metade dessa maneira por acaso. Então, vamos agora formalizar o que é claramente intuitiva. Então, uma coisa chamada pseudocódigo é onde vamos começar alguns de nossos problemas iniciais. E esta é uma forma genérica de descrever um algoritmo ou um programa de computador, não usar C ou C ++, ou Java, ou de alguma linguagem específica, mas apenas usando Inglês, com que qualquer ser humano pode ser familiar. E podemos escrever o pseudocódigo para este problema, como se segue. Passo um, pegar o livro de telefone. Passo dois, aberta a meio da lista telefônica. Passo três, olhar para os nomes. Passo Quatro, se Smith está entre names-- E agora esta é uma construto interessante. É um ponto de decisão. É uma bifurcação na estrada, se você vai, uma filial, por assim dizer. Então eu vou para recuar apenas por convenção step-- cinco-- que não é por exemplo, eu vou ligar para Mike. Portanto, este recuo, totalmente convenção humana arbitrária, mas é simplesmente a intenção de transmitir semanticamente que se Smith está entre nomes, então eu deveria chamar Mike. Enquanto isso, na etapa seis, aviso que o recuo foi embora. Então, outra coisa é outra bifurcação na estrada, o outro caminho que eu poderia viajar. Então else if Smith é no início do livro, o que é o meu próximo passo, provavelmente, vai estar aqui? AUDIÊNCIA: Você vai para o lado esquerdo. DAVID J. MALAN: Sim, então vá para a metade esquerda da lista telefônica. Jogue fora a metade direita se Smith está no início do livro. Então aberto até o meio da a metade da esquerda do livro. E depois passo oito, vá para a linha três. E este é um laço curioso eu sou indução, uma recursão por assim dizer. Mas mais sobre isso no futuro. Eu estou usando o meu mesmo algoritmo, minha mesmo pseudocódigo, para resolver o mesmo problema novamente porque a única coisa que mudou é o tamanho do problema, não meu objetivo, e não a pessoa Eu estou procurando. Para que eu possa reutilizar o algoritmo que eu já tenha definido. Else if Smith é mais tarde em book-- que você pode adivinhar aberta para o meio a metade direita do livro. E, novamente, vá para a linha três. Else-- qual é a linha final neste programa vai ser? Se ele não está entre os nomes na página Sou on, se ele não está no início o livro, e ele não é mais tarde no livro, o que eu sei é verdade sobre Mike Smith agora? AUDIÊNCIA: Ele não está no livro. DAVID J. MALAN: Ele não está no livro. Então, o melhor que posso fazer é apenas desistir e parar este programa. Tudo certo. Portanto, neste ponto, vamos dar uma rápido passeio um pouco do que espera. E, na verdade, eu estou juntou aqui por um número de funcionários CS50. Se essas pessoas poderiam tudo se juntar a mim aqui em cima no palco. [Aplausos] Lembre-se, este é apenas um subconjunto da equipe CS50, uma vez que cada ano temos cerca de 100 funcionários membros em função de auxiliar do curso, Teaching Fellows e muito mais. Vamos lá para cima. Então, eles vão se juntar a nós aqui desajeitadamente por um momento como dar um rápido tour do que você deve esperar aqui no curso. Então, em primeiro lugar, temos SAT / UNS como a opção de classificação no curso. Este destina-se deliberadamente para ser uma opção em que se você é um pouco desconfortável a estar em curso, e você temer failure-- mesmo francamente falha significa ferir o seu GPA, a obtenção de um B e não um A-- que é precisamente o que, certamente, para uma porta de entrada Claro que como CS50 e outros cursos introdutórios, esta opção de classificação destina-se a permitir. Eu sinceramente encorajar students-- especialmente se no fence-- para iniciar o Claro SAT / UNS, ainda permanecem SAT / UNS. Mas certamente você pode mudar para uma carta grau na quinta-feira no termo. Francamente, quando eu era um calouro em 1995, Eu mesmo nem sequer ter CS50 porque eu não tive coragem para realmente pisar na sala de aula. Parecia um domínio demasiado desconhecido para mim e realmente só para os meus amigos, francamente, que tinha sido programação uma vez que eles eram seis ou talvez 10 anos de idade. E foi só porque eu era capaz de tomar CS50 no meu dia na versão equivalente SAT / pass UNS-- / reprovação de volta na dia-- que mesmo eu levei 50. E de alguma forma ou de outra, eu sou aqui novamente com vocês hoje. Agora, entretanto, o que mais você deve ter em mente cerca de 50 é a inscrição simultânea. Contrariamente aos rumores que você pode ter ouvido, você pode, de fato, ao mesmo tempo inscrever no CS50 e outra classe que atende ao mesmo ou alguma sobreposição tempo, como palestras de CS50 aqui. Veja o currículo para as indicações da sua execução. Palestras, entretanto, ao contrário do o que está oficialmente no catálogo, geralmente só encontrar para apenas uma hora. Na ocasião, podemos correr um pouco longo. Mas tenha em mente que a objetivo em palestras de CS50 é fornecer-lhe com uma visão geral conceitual, espero que algumas manifestações, talvez até mesmo alguns brindes, do que aguarda para a semana que se segue. E assim, em palestras, vamos explorar esses tópicos e exemplos juntos, trazendo os alunos para o palco, e pessoal em cima do palco o mais rápido que pudermos, para apenas um par de horas por semana. Seções, entretanto, será oferecidos por essas pessoas aqui-- muitos deles ensinando companheiros, alguns deles curso assistants-- vontade acontecer semanalmente. E o que é fundamental para manter em mente é que nós Não ao contrário do primeiro have-- Nights, a música class-- diferentes faixas de seções para alunos menos confortáveis, mais confortável, e em algum lugar no meio. E, francamente, você sabe se você é menos confortável. E você provavelmente sabe se você está mais confortável. E se você não está realmente certo, você é por definição, algures no meio. Então, quando chega a hora de secção em uma semana ou assim, por o plano de estudos, vamos pedir-lhe essa pergunta. E você pode auto-seleção com base em seu próprio nível de conforto e estar com students-- estar com verde dots-- similar em nível de conforto para você. Entretanto, temos problema define, o que acabará definir a sua experiência neste curso. Eles são oferecidos normalmente em várias edições. A edição padrão que esperamos mais cada aluno no curso de enfrentar mas também o chamado edição hackers que não oferece nenhuma forma de crédito extra de imediato, mas realmente os direitos de se gabar quer dizer que você tentou e abordou edições de hackers do curso que aproximamos do material semelhante mas a partir de um ângulo de mais sofisticado. O que oferecemos para o Standard Edition, para, novamente, um super maioria dos estudantes, não são apenas walk-through, que são videos liderados pela equipe do curso que realmente levá-lo através do problemas do curso e possível desenho implementações. E também, após o fato, oferecer autópsias, em que se você está pensando como você poderia ter ou deveria ter resolvido alguns problema, o corpo docente o guiará através de aqueles em vídeo também. Enquanto isso, o que espera também são cinco dias de atraso eo fato que vamos soltar o seu menor conjunto de problemas de pontuação. Nós certamente apreciar que em troca para a carga de trabalho que espera 50 de você, a vida fica no caminho Às vezes, se não cinco vezes. E para que isso irá oferecer lhe um pouco de flexibilidade, estender o seu prazo de, digamos, um Quinta-feira ao meio-dia de sexta-feira ao meio-dia. Veja o currículo para o detalhes de implementação do mesmo. Agora, o que agora aguarda? E isso está ocorrendo apenas para mim agora quanto tempo Estou com vocês ficam aqui no palco. [Risos] DAVID J. MALAN: Mas nós vamos chegar a o acabamento clímax antes do tempo. Então, o que espera em termos dos conjuntos de problemas? Bem, talvez um teaser do que todos nós fez no ano passado com os seus antecessores. No primeiro conjunto de problemas no ano passado, introduzimos Zero, uma gráfica linguagem de programação que permite programar literalmente por arrastando e soltando peças do puzzle, como estes, que estão lembra as construções vai ver apenas uma semana Assim, quando trocamos de uma forma mais tradicional língua, conhecida como C. No ano passado, procedeu para este conjunto de problemas, envolvendo a criptografia, a codificação da informação para evitar que ela governamental ou amigos ' olhos que você não quer vê-lo. Codificado aqui é um mensagem de que em breve você será capaz de decifrar ou de-corrida. Breakout era um problema estabelecido no ano passado, no qual você usá-los nova programação encontrados habilidades para realmente implementar um jogo como wherein-- deve se lembrar de childhood-- o objetivo era bater o tijolos que estão no topo do ecrã aqui, acumulando marcar ao longo do caminho, e implementar seus próprios algoritmos com que esta solução, em última análise permite que você jogue o jogo. Entretanto, no final do semestre, vamos dar-lhe um dicionário de 143.091 palavras em inglês. E você será desafiado para escrever um programa que soletrar cheques, documentos, por carregamento que muitas palavras para a memória forma mais eficiente possível. Geralmente colocando você contra seus colegas de classe se você optar em um pouco de desafio no quadro de líderes para ver quem pode usar o menor número segundos de tempo de execução, e o número menor quantidade de megabytes de memória, e realmente afinar seus programas para ser incrivelmente eficiente de recursos não tempo apenas. No ano passado, também, olhamos para o final do semestre em programação web. E, de fato, nós vamos fazer isso de novo esta ano com vários conjuntos de problemas, introduzindo-lhe as técnicas e a mentalidade com a qual você pode aplicar essas habilidades de programação para sites, sites dinâmicos, sites que realmente resolver problemas e se comportam de forma diferente e simplesmente não são estáticos sites com informações estáticas. O projeto final, em última instância vai definir, porém, o clímax do curso para os alunos, que Você será desafiado a implementar mais qualquer coisa de interesse para você, desde que de alguma forma baseia-se em aulas do curso. E como você viu no vídeo no início, vamos concluir o semestre com o CS50 Hackathon, que se, não familiar, terá início às 07:00 uma noite e terminará às 07h00 do dia seguinte. Por volta de 09:00, vamos ordem no primeiro jantar. Por volta de 01h00, vamos ordem em segundo jantar. E se você ainda estiver situando-se em 5:00, nós vontade de traslado você para IHOP no café da manhã. O CS50 Fair, por sua vez, é um evento a que mais de 2.000 professores, alunos, e funcionários de todo campus vêm para ver as suas realizações no curso e na final projetos e criações que você cria em seus laptops, desktops, ou talvez até mesmo lâmpadas de luz. Enquanto isso, o horário de expediente e a estrutura de suporte. E agora ela já teria sido um melhor momento para trazer-lhe tudo. Horário de atendimento terá lugar quatro noites por semana durante várias horas por noite com geralmente 20 a 30 do Os funcionários do curso de serviço de uma só vez para fornecê-lo com íntimo one-on-one oportunidades de apoio com conjuntos de problemas do curso. Explicações também será disponíveis, em especial para os alunos menos comfortable-- ou ouso dizer menos comfortable-- para quem horário de expediente não o são mais ambiente acolhedor e, certamente, não são o mais livre de estresse. Especialmente quando os prazos estão pressionando, vamos proativamente emparelhar vocês mesmos com um membro do pessoal para trabalhar com em algum horário regular como suas necessidades e sua agenda permite. E a equipe. Permita-me apresentar Davon, Rob, e Gabriel, os chefes deste ano. Se você gosta de cada dizer-- [Aplausos] palavra --um. [Aplausos] Davon aqui é o gerente do curso, que significa em seu papel em tempo integral ele contribui com a execução e logística de CS50. Davon: Sim, oi, pessoal. Você vai ver um monte para mim no horário de expediente. Eu vou estar ensinando seções. E se você atirar-mails à frente, Eu provavelmente vou estar respondendo. Então, eu vou ver muitos de vocês durante todo o semestre. E bem-vindo ao CS50. DAVID J. MALAN: E agora Gabriel, que se era apenas um calouro do ano passado, mas para os últimos dois anos tem vindo a operar sua própria versão do CS50 no Brasil, em que ele baixou todos content-- do curso que está a ser claramente filmado e colocado online-- para que ele pudesse traduzi-lo para Português e, em seguida, ensinar mais de 100 de seus colegas sobre o curso de um par de anos, ensino em sua língua nativa currículo do curso. GABRIEL: Olá. [Aplausos] GABRIEL: Oi, eu sou Gabriel. Eu sou o TF cabeça do curso. E eu espero que você vai adorar CS50. Este é CS50. DAVID J. MALAN: Agora para Rob. Oh, você quer introdução? ROB: Não, eu não sei. [Risos] DAVID J. MALAN: E Rob Boden. [Risos] ROB: Oi, eu sou Rob. Este é o quinto ano envolvida com o curso. Todos os anos, é apenas um melhor e melhor classe, Então vocês são claramente Vai ser incrível. Espero que todos se divertir com ele. Eu estou indo para se divertir com ele. Então vê-lo ao redor. DAVID J. MALAN: E o tempo não vai permitir US-- [Aplausos] O tempo não permite-nos apresentar todos sobre o palco e todos os seus colegas que estão comprando aulas hoje. Mas permita-me apresentar Belinda e CS50 enigma Day, que aguarda esta próximo sábado, o que é a primeira da eventos de grande escala do curso. Este em particular significado para martelar a ponto que a informática é, em última análise não sobre a programação, mas sim sobre a resolução de problemas de forma mais geral. E Enigma do dia, como você vai ver, vai lhe trazer e seus colegas together-- esperamos que este sábado. BELINDA: OK. Oi, pessoal. Então, obrigado. Assim como o nosso ilustre capitão disse, Belinda do meu nome. Eu sou um estudante de segundo ano em Quincy House. Eu, assim como vocês, levou CS50 ano passado, realmente adorei. Eu tenho um fraquinho por vocês na terceira fila. E tenho orgulho de dizer, eu sou agora em um relacionamento sério com CS50 [inaudível]. Está bem. Essa foi a minha versão coxo de uma piada. De qualquer forma, assim que seguir em frente, só queria convidar vocês todos para o i-lab ou urticária HBS. Nós vamos ter Quebra-Day 12:00-03:00. E é uma grande oportunidade para você caras para conhecer seus colegas amigos CS, resolver alguns enigmas não-CS, como capitão mencionado, e também comer algum alimento livre, ganhar alguns prêmios incríveis, como cartões de presente, $ 75 por pessoa, e também-- o que era? Wii U ou algo assim? Wii U? Sim. Para o nosso sorteio. Incrível. Então, eu vou ficar por aqui depois da aula. E se vocês tem alguma perguntas, deixe-me saber. DAVID J. MALAN: E você vai ver, além isso não há nada para fazer hoje. O primeiro conjunto de problemas vai sair sexta-feira. Mas para nos trazer para casa hoje, eu gostaria de apresentar-lhe mais especificamente um membro da equipe, Colton Ogden aqui, cujas mãos estão agora protegido acima de você com este controlador MIDI para martelar o ponto mais que a informática, também, tem aplicabilidade muito além da engenharia e caule e ciência da computação em si, estendendo-se até mesmo a domínios como a música. Colton foi gentilmente offered-- Pensei um deles estava indo para fixar o foco. Andrew, se pudéssemos convocar foco aqui só por um momento. O Colton fez com antecedência é o programa este dispositivo, esta almofada de botões que você vê na foto aqui em cima, como um controlador MIDI, em que cada um desses botões é ligado a uma nota musical particular ou um som, mais geralmente uma gravação, de tal modo que ao jogar os padrões de estes botões, muito parecido com os padrões de bits, pode representar outro conceitos de nível superior. Será que ele vai ser capaz, em última instância para nos levar para casa hoje? Sem mais delongas, se poderíamos diminuir as luzes, e ligar a tela por trás Colton. AUDIÊNCIA: Woo! David J. MALAN: Este é CS50. [MÚSICA DE JOGO] [Aplausos] Isso é tudo para CS50. Vamos vê-lo sexta-feira. Alguns bolo espera por você no transepto. [MÚSICA DE JOGO]