[MÚSICA DE JOGO] 

COLUNA 1: Tudo bem, essa é CS50, e este é o início da quarta semana e como você já deve ter ouvido ou ler, o mundo está acabando. Indo ao redor da internet tem sido de conhecimento e conscientização de um bug em um programa, um linguagem de programação chamada Bash. Este foi lindamente marca como Shellshock, ou a porta Bash, mas artigos como estes Não foram pouco frequentes. E, de fato, muitos deles trazem recordações de Heartbleed, que você pode ter notado na pressione novamente na primavera passada, que foi igualmente bastante dramática. Agora, aqueles de vocês aqui hoje, como muitos de vocês têm, mesmo se você não entende o que é tudo sobre, ouviu falar de Shellshock? Tudo bem, e como muitos de vocês têm computadores que são vulneráveis? OK, não deve ser muito, muito mais mãos até agora, por razões veremos. 

Vamos dar uma olhada no que está vem acontecendo nos meios de comunicação e, em seguida, explicar um pouco aqui para nós tecnicamente. 

COLUNA 2: Os especialistas em segurança têm alertou que uma falha grave poderia ser de cerca de centenas de afectar milhões de usuários da rede no mundo. Então, qual é exatamente o erro que tem sido apelidado Shellshock, eo que ele faz? Bem, Shellshock também é conhecido como o Bug Bash, o software que explora. Hackers usam vírus para escanear vulnerável sistemas rodando Linux e Unix sistemas operacionais e infectá-las. Bash é um shell de linha de comando. Isso permite aos usuários enviar comandos para lançar programas e funcionalidades no software digitando texto. É normalmente utilizado por programadores, e não deve ser aberto ao mundo exterior, embora Shellshock muda isso. 

Bem, worringly, alguns analistas advertem que poderia ser uma ameaça maior, Shellshock porque permite total controle de uma máquina infectada, Considerando Heartbleed só permitiu hackers para espionar computadores. É tão sério, é foi avaliado a 10 de 10 para a gravidade do National Vulnerability Database. 2/3 de todos os servidores web estão no risco, incluindo alguns computadores Mac. Bem, certifique-se de corrigir seus sistemas agora. Qualquer um que hospeda um site em funcionamento os sistemas operacionais afetados deve agir o mais rápido possível. Qualquer um que pode pagar deve olhar para seu aplicativo de monitoramento e web firewalls de olhar para qualquer ataque. Palestrante 3: A pior coisa que poderia acontecer é que alguém iria escrever um código que iria e verificar automaticamente a internet e afetaria todos esses computadores. E uma vez que eles fazem isso, bem, a pior coisa que poderia fazer é simplesmente apagar tudo, ou fechar os sites de baixo. Para que pudéssemos ver os danos a partir desse ponto de vista, onde teríamos pessoas mal-intencionadas que apenas decidir causar estragos reunindo sistemas para baixo ou a exclusão arquivos, e coisas assim. COLUNA 2: Alguns dizem que este é um dos mais difíceis de medir bugs em anos, e Pode levar semanas ou mesmo meses para determinar seu impacto final. 

COLUNA 1: Então, tudo isso é verdade, mas o engraçado é que, quase todos das imagens que você acabou de ver, exceto talvez o teclado, não tem nada a ver com o bug qualquer. Servidores e fios e assim por diante, É uma espécie de tangencialmente relacionado, mas no centro é realmente muito familiarizado o que está acontecendo aqui. Na verdade, deixe-me entrar nosso aparelho CS50. Deixe-me ir em frente e maximizar a janela de terminal aqui. E vocês têm vindo a utilizar este, ou a versão integrada do mesmo, no gedit para escrever programas, digitar comandos, e assim por diante, e esta é na verdade, e tem foi por semanas, Bash, B-A-S-H. Este é o Bourne-again Shell, que é apenas uma maneira elegante de dizer, este é um programa que tem um piscar rápido, eficaz, que fica lá esperando para a entrada para você. E é o comando interface de linha através da qual Vocês foram a execução de comandos e em última análise, compilação e, em seguida, executando programas. 

Mas Bash é também uma programação linguagem no seguinte sentido. Você sabe que existem comandos como cd e ls e também clang e outros, mas você pode definir seus próprios comandos por implementá-las em Bash. Agora nós não vamos entrar em grandes detalhes como para bater a linguagem de programação, mas sabe, por exemplo, que, no momento, não há nenhum comando chamado "Olá". Por isso, pode ser encontrada em um desses pacotes. Não está instalado no meu computador. Pergunte ao seu administrador. Mas se eu quero que haja um programa de chamado "Olá" em Bash, ou pelo meu aviso, Eu posso realmente usar uma sintaxe que é bem como C. Não é bem a mesma coisa, mas parece muito semelhante a um função, ainda faltam alguns detalhes. Nada parece acontecer, mas agora se eu digitar "Olá", você pode realmente escrever uma programa, não em C, não em Java, não noutro programação linguagem, mas em si Bash. 

Agora, a chave aqui é que eu escrevi o nome eu queria dar a este novo comando, e os parênteses são também simbólica de este ser uma função. Como um aparte, você também pode fazer o divertimento as coisas, e de fato, mesmo no Mac OS, este é um programa chamado Terminal. Ele vem embutido no de ninguém computador que tenha um Mac nesta sala, e você pode fazer coisas semelhantes em Mac OS, mas você pode ir mais além. E isso é um pouco tangencial, mas é o tipo de diversão. Lembrei-me hoje de manhã, quando se pensa sobre isso, de um pequeno jogo que eu costumava jogar com um dos ex-TFs do CS50 em que a qualquer momento ele iria a pé seu teclado com o seu ecrã desbloqueado, Gostaria de executar um comando como isso-- "dizer Olá". E agora qualquer momento ele voltou para sua teclado depois limpei a tela e ele iria sentar, tentar fazer algum trabalho, listar o conteúdo de sua directory-- 

[AUDIO REPRODUÇÃO] 

Alô. Olá. 

COLUNA 1: Então, para ser justo, não era, na verdade, "Olá". Geralmente era algo mais parecido com que-- [AUDIO REPRODUÇÃO] -Beep. COLUNA 1: --aquela I would-- assim que seu computador fosse Juro para ele a qualquer momento ele realmente sentou-se à do teclado. E muito rapidamente ele descobriu não deixar sua tela desbloqueado. Mas isso sugere o tipo de diversão estúpida que você pode ter algo como Bash. Mas é um pouco mais sério, com certeza, que isso. E, de fato, este é um dos A maioria dos bugs perigosos e duradouros que realmente atingiu o mundo globalmente. Este erro tem sido em torno para cerca de 20 anos, e você vai ser atingido em apenas um momento de sua relativa simplicidade. 

Portanto, este é um representante manda que se possuir um Mac, literalmente agora quando você tem a sua tampa aberta, você pode tentar digitar em que programa chamado Terminal. Terminal está sob Aplicações Utilities-- Pela primeira vez, os usuários do Windows não tem que preocupar com isso threat-- especial mas aqueles de vocês com Macs pode digitar isso em uma janela que eu vou fazer aqui, e se você digitar que para este programa chamado Terminal, como eu vou fazer agora, Se você ver a palavra "vulnerável" o computador é vulneráveis ​​à exploração. 

Agora, o que isso realmente significa? E este é reconhecidamente uma sintaxe muito louco, mas vamos ao menos tirar alguns dos aspectos interessantes. Portanto, há uma sintaxe que parece um pouco familiarizado, pelo menos, a partir do C e programação em geral. Vejo alguns parênteses, ponto e vírgula, chaves e tal, mas verifica-se que este coisa estúpida aqui em amarelo é essencialmente uma função que não faz nada. Os meios de cólon fazer nada, ea ponto e vírgula significa parar de fazer nada. Assim, dentro destas chaves, o fato de que eu tenho um igual assinar para a esquerda, este É, essencialmente, criar um comando ou de uma variável, chamado x, e atribuindo-lhe que pouco amarelo de código lá. Isso poderia ser algo como "echo Olá "ou" dizer bip "ou algo semelhante ao. Mas observe se os seus olhos vagar mais para a direita, não há mais a esta linha de apenas o fim desse ponto e vírgula. "Echo vulnerável", e em seguida, além disso há ainda mais. Outro ponto e vírgula, o bash-c :. 

Então, longa história curta, esta linha de código é suficiente para convincente um computador que é vulneráveis ​​a fazer algo que você quer que ele faça, porque há um bug no qual Bash embora Bash deveria parar linhas de leitura da direita comando lá depois do texto amarelo, por um ano de idade bug 20-plus, Bash foi realmente lendo além desse ponto e vírgula e bonita muito fazendo o que é dito. 

Então, qual é a implicação de que, em última análise? Eu apenas disse "echo Olá" ou "echo vulnerável" mas que se você fez algo realmente maliciosa, como rm-rf *, que você não pode já escreveu anteriormente, e, francamente, você provavelmente não deve muito em breve, porque você pode fazer uma muitos danos com ele. Por quê? rm faz o que, é claro? Remove. * Significa o quê? Tudo. Portanto, é um chamado wild card, então isso significa apagar tudo em o diretório atual. r acontece para significar recursiva, o que significa que se o que você está excluindo é um diretório, e lá dentro é outros arquivos e outros diretórios, recursivamente mergulhar lá e apagar tudo isso. E-f é o pior de todos eles. Alguém sabe o que significa f aqui? Force. Assim forçar os meios, inclusive Se esta é uma má idéia, fazê-lo sem me avisar para confirmação. Então, você sabe, nós rimos isso, mas, francamente, eu provavelmente digite isso várias vezes um dia, porque a realidade é que é o caminho mais rápido para excluir um monte de coisas. Mas, mesmo que eu tenha feito algum dano. 

Mas se você fosse para enganar um computador para definir alguma variável estúpido ou função chamada x, mas depois enganar o computador em execução para além dos limites dessa função, além disso ponto e vírgula, você poderia realmente enganar um computador para executar algo como rm-rf ou o comando de Email ou o comando Copiar. Qualquer coisa, literalmente, você pode fazer com o computador, seja apagando arquivos, a criação de arquivos, enviar spam para alguém, atacando algum servidor remotamente, se você pode expressá-lo com um comando, você pode enganar um computador para fazer isso. 

Agora, o que é um exemplo de como você pode fazer isso? Bem, há um monte de computadores no Bash internet funcionando. Todos os usuários nos Mac estão entre eles. Um monte de servidores Linux estão entre eles também, e servidores Unix. O Windows novamente fica relativamente fora do gancho a menos que você tenha instalado software especial. Agora um monte de servidores, por exemplo, servidores web são executados, e, de facto, é talvez o Linux mais popular sistema operacional para rodar em computadores na internet que estão servindo páginas da rede. Agora, como veremos mais tarde no semestre, quando você envia uma solicitação de seu browser-- Chrome, Internet Explorer, whatever-- para um servidor remoto, verifica-se que, apesar de você acabou de digitar www.example.com, seu navegador está enviando uma mensagem isso é um pouco mais misteriosa, como este. 

Mas note um pouco de algo estranho. As primeiras duas linhas Eu nunca tinha visto antes, mas eles não se parecem particularmente ameaçador. Mas note o que eu roubei para a terceira linha aqui. Se um bandido foram para enviar uma mensagem assim de seu computador a um Mac ou um vulnerável servidor Linux vulnerável, o engraçado é que Bash, que prompt de comando pouco simples, é onipresente e muitas vezes é Usado para executar essencialmente o conteúdo de um mensagem que recebe. E por essa lógica, você pode enganar um servidor web, por isso, enviando algo parecido User-Agent, que geralmente é suposto dizer o Nome do seu browser. User-Agent Chrome, User-Agent Internet Explorer, Firefox User-Agent, este é apenas seu navegador de maneira de identificar-se. Mas se um cara mau muito inteligentemente diz: mm-mm, eu sou não vou dizer a você o meu navegador é, Estou em vez de ir para enviar-lhe esta coisa enigmática-olhando com uma -rf rm * Nele, você pode literalmente enganar um servidor web vulnerável na internet para executar exatamente o que, em lá para apagar todos os arquivos. E, francamente, isso não é até mesmo o pior de tudo. Você pode fazer qualquer coisa. Você poderia começar a distribuição ataque de negação de serviço se você enviou esta mensagem a cachos inteiros de servidores web e depois tinha todos eles descem, para exemplo, em servidores Harvard.edu, e você pode classificar de Bang o inferno fora deles por um tráfego de rede que foi caso contrário, desencadeada por um cara ruim. 

Então, longa história curta, quase todos nesta sala que possui um Mac é vulnerável a isso. O consolo é que, a menos que você é executando um servidor web em seu laptop, e, a menos que você realmente configurado para permitir que algo como SSH para ele, você está realmente seguro. É vulnerável, mas não é um tentando entrar em seu laptop, assim você pode classificar de ter a certeza. No entanto, a Apple em breve estar atualizando uma correção para isso. O mundo do Linux já lançou uma série de correções para o Fedora e Ubuntu e outras versões do Linux, e de fato se você executar update 50 no aparelho, mesmo que também será atualizados e corrigidos. Mas isso também não tem sido realmente vulnerável, porque a menos que você tem consertou com o aparelho e fez o seu laptop publicamente acessível na internet, o que não é Por padrão, você tem na verdade, foi bom porque de firewall e outras técnicas. 

Mas é um exemplo extremo de um bug que vivemos para, literalmente, para 20 anos, e quem sabe se alguém todo este tempo soube sobre isso? E, de fato, este é um dos os desafios fundamentais que vamos ver mais tarde na semestre com a segurança, é que, assim como no mundo real, os mocinhos estão em desvantagem. Para manter os bandidos fora, temos que certifique-se de que cada porta está trancada, que cada janela é segura, que todos os pontos de entrada em uma casa é seguro para manter os bandidos fora. Mas o que o vilão tem que fazer para realmente comprometer a sua casa e roubá-lo? Ele ou ela só tem que encontrar um desbloqueado porta, uma janela quebrada, ou algo nesse sentido, e é o mesma coisa em segurança de computadores. Podemos escrever milhões de linhas de código de programação e gastar centenas ou milhares de horas a tentar obtê-lo correto, mas se você fizer apenas uma erro na correção, você pode colocar todo o sistema e na verdade, neste caso, toda a Internet e do mundo em risco. 

Então, se você quiser saber mais sobre isso, vá para esta URL aqui. Não há necessidade de uma ação hoje à noite, a menos que você é entre aqueles que mais confortável foram executando o seu próprio web servidor, no caso de você deve, que, Na verdade, atualizar seu software. 

E este também é o título de um discurso e, agora, um papel, que temos ligado na site do curso para hoje. Foi por um colega chamado Ken Thompson, que estava aceitando um famoso prêmio em ciência da computação, e ele deu a este discurso de alguns anos há, essencialmente, sobre o mesmo tema. Perguntar pessoas a pergunta, Se você realmente confiança, em última análise, o software que lhe foi dado? Por exemplo, todos nós temos escrevendo programas, e estamos compilando los com Tinido. E para o seu conhecimento, você escreveu qualquer programa de CS50 onde há uma porta traseira do tipo, há uma maneira que um cara mau, se executar o programa, poderia assumir o seu computador? Provavelmente não, certo? Mario e Greedy e Crédito. Estes são todos muito pequenos programas. Você teria que ser muito ruim se você realmente fez todo o seu computador vulnerável depois de escrever 10 ou 20 linhas de código, ou, pelo menos, alguns desconhecem das implicações de segurança. Agora eu digo isso de brincadeira, mas vamos ver hoje e esta semana é realmente muito, muito fácil ser mau e fazer ainda programas curtos vulneráveis. 

Mas, por enquanto, pelo menos, perceber que a questão que se coloca aqui é sobre Clang em um compilador. Por que temos sido confiando Clang nos últimos dois ou três semanas? Quem vai dizer que quem escreveu Clang não tinha um "se" condição lá que, essencialmente, injetado alguns zeros e aqueles em cada programa que compila que permitiria a ele ou ela o acesso seu computador quando você está dormindo e sua tampa do laptop é aberto e seu computador está funcionando? Certo? Temos este tipo de direito sistema de honra agora onde nós confio que Clang é legal. Você confia que o aparelho é legal. Você confia em que, literalmente, todos os programas no seu Mac ou PC é confiável. E como este bug simples sugere, mesmo se ele não é malicioso, isso não é absolutamente susceptível de ser o caso. 

Então você deve estar assustada como o inferno. Francamente, não há simples solução a esta outra do que um tipo de consciência social da crescente complexidade que estamos construindo em cima de nossos sistemas de computador, e como cada vez mais vulneráveis que poderia muito bem ser. 

Agora, com o que disse, Breakout. Então Breakout é problema definir três, e Breakout é um jogo de antigamente que você deve se lembrar, mas para nós no conjunto de problemas de três, que nos permite tomar as coisas de volta até um entalhe para que, quando estamos a escrever programas, mesmo em uma janela de terminal como este, podemos realmente executado, em última análise, programas gráficos não ao contrário daqueles que tivemos acesso a em risco. Portanto, este é o pessoal do implementação de Breakout, que é apenas isso de quebra de tijolos jogo, que você mover sua raquete para trás e para trás, e você bater na bola contra os tijolos coloridos em cima. Então, isso está nos trazendo espécie de volta para onde , foram capazes de ser muito rapidamente com o Scratch, e agora com C, implementação da nossa própria interfaces gráficas de usuário. 

Mas mais do que isso, este conjunto representa o primeiro problema em que nós estamos dando você um monte de código. E, na verdade, eu trago explícita atenção para isso, porque especialmente para aqueles menos confortável, este conjunto de problemas, pelo menos à primeira vista, vai sentir como demos-se um entalhe. Porque nós te dei, para algumas das buscas e classificar os problemas no pset, um monte de código que escreveu, e um par de comentários que dizem "fazer", onde você tem que preencher os espaços em branco. Então, não muito assustador, mas é a primeira vez estamos entregando-lhe um código que você precisa primeiro ler, entender, e em seguida, adicione a e concluí-lo. 

E então, com Breakout, vamos fazer o mesmo, dando-lhe uma dúzia de mais linhas de código que, francamente, dar-lhe uma grande parte do quadro de o jogo mas param de implementar os tijolos e a bola e na raquete, mas fazemos implementar algumas outras características. E, mesmo que à primeira vista, mais uma vez, especialmente se menos confortável, Pode parecer particularmente difícil e Você acha que há tantas novas funções você precisa envolver sua mente ao redor, e isso é verdade. Mas lembre-se, é bem como do risco. As probabilidades são que você não usar todos as peças do puzzle em zero. As probabilidades são que você não se importava para embrulhar sua mente em torno de todos eles porque tudo o que tinha era uma rápida olhada para compreender, oh, isso é o que eu posso fazer com essa peça do puzzle. E, de fato, no conjunto de problemas 3 spec, vamos apontá-lo na documentação que será apresentá-lo a novas funções, e, finalmente, a programação constrói você usa. Condições, laços, variáveis ​​e funções será idêntico ao o que temos visto até agora. 

Então, na verdade, o que nós vamos dar você é um código de exemplo que permite criar uma janela que não parece, ao contrário disso, e, finalmente, transformá-lo em algo parecido com isso. Então, aproveite CS50, discutir o horário de expediente e mais, e se consolar com o fato de que a quantidade de código que você tem que escrever na verdade não é tanto assim. O primeiro desafio é apenas para se aclimatar -se de algum código que você escreveu. 

Qualquer dúvida sobre pset3, Shellshock, ou de outra forma? 

AUDIÊNCIA: Parecia que passando com Breakout que o código é quase um estilo orientado a objetos, mas eu pensei que era um C programa orientado a objeto. COLUNA 1: Uma excelente pergunta. Assim, em olhando através da código de distribuição, o código nós escrevemos para pset3, para os que estão familiarizados, ele Parece que é um pouco orientada a objetos. A resposta curta é, é. É uma aproximação de como você pode fazer código orientado a objetos usando uma linguagem como C, mas é ainda, em última análise processual. Não existem métodos dentro de as variáveis, como você vai ver. Mas ele lembra-se disso. E nós vamos ver esse recurso novamente quando chegarmos ao PHP e JavaScript até o final do semestre. Mas, por agora, pense nisso como uma dica do que está por vir. Boa pergunta. Tudo certo. Então, merge sort era como nós coisas deixadas pela última vez. E merge sort foi legal no sentido de que era muito mais rápido, , pelo menos, com base nos ensaios superficiais fizemos na semana passada, que, digamos, bolha tipo, a seleção de classificação, ordenação por inserção. E o que era limpo também é apenas como forma sucinta e limpa você pode expressá-la. E o que podemos dizer que foi um superior obrigados, sob o tempo de execução da fusão classificar? Sim? 

AUDIÊNCIA: n log n? 

COLUNA 1: n log n, certo. n log n. E nós vamos voltar para o que isso realmente significa ou de onde vem isso, mas este foi melhor do que o tempo de execução que vimos para bolha seleção e inserção tipo? Então n ao quadrado. n ao quadrado é maior do que isso, e mesmo se não é óbvio, sei que log n é menor do que n, por isso, se você fizer n vezes algo menor do que n, vai ser menor do que n ao quadrado. É um pouco de intuição lá. Mas pagamos um preço por isso. Ele foi mais rápido, mas um tema que começou a surgir na semana passada foi essa compensação. Eu tenho um melhor desempenho tempo sábio, mas o que que eu tenho que passar por outro lado, a fim de conseguir isso? 

AUDIÊNCIA: Memória. COLUNA 1: Diga de novo? AUDIÊNCIA: Memória. COLUNA 1: Memória, ou espaço de forma mais geral. E não foi super óbvia com os seres humanos, mas lembrar que nossos voluntários foram avançando e pisando de volta como se houvesse uma matriz aqui, e como se houvesse um segundo conjunto que aqui eles poderiam usar, porque nós um lugar necessário para mesclar essas pessoas. Nós não poderíamos simplesmente trocá-los no lugar. Então, merge sort alavancagem há mais espaço, que nós não precisamos de os outros algoritmos, mas a vantagem é que é muito mais rápido. E, francamente, no espaço do mundo real estes RAM dias--, disco rígido espaço-- é relativamente barato, e por isso é não necessariamente uma coisa ruim. 

Então, vamos dar uma olhada rápida, um pouco mais metodicamente, pelo o que fizemos e por isso que disse que estava n log n. Então aqui estão os oito números ea oito voluntários que tivemos da última vez. E a primeira coisa que se fundem Ordenar nos disse para fazer o que era? AUDIÊNCIA: Divide em dois. COLUNA 1: Diga de novo? AUDIÊNCIA: Divide em dois. COLUNA 1: Divida em dois, certo. Isso lembra muito o livro de telefone, de dividir e conquistar mais geral. Então, olhamos para o lado esquerdo. E, em seguida, uma vez dissemos, tipo a metade da esquerda dos elementos, o que nós fizemos próxima dizer? Ordena a metade esquerda da esquerda metade, o que nos permitiu, depois de dividir em dois, concentrar em quatro e dois. 

Como você classificar uma lista agora, em amarelo, de tamanho dois, usando Merge Sort? Bem dividi-lo ao meio, e classificar a metade esquerda. E este era o lugar onde as coisas ficou um pouco brevemente estúpido. Como você classificar uma lista que é de tamanho um, como este número quatro aqui? É classificada. Você está feito. 

Mas então como você classificar uma lista de um tamanho quando é o número dois? Bem, a mesma coisa, mas agora o que era o terceiro eo passo fundamental na Merge Sort? Você tinha que se fundem à esquerda metade e metade direita. E uma vez que fizemos isso, nós olhamos em quatro, nós olhamos para dois. Decidimos tudo bem, obviamente dois vem em primeiro lugar, então colocamos dois em sua lugar, seguido por quatro. E agora você tem que tipo de retrocesso, e isso é uma espécie de característica de um algoritmo como Mesclar Ordenar, retroceder na memória. Qual foi a linha seguinte da história? O que eu deveria estar centrada na próxima? A metade direita da esquerda metade, que é de seis e oito anos. 

Então deixe-me passar por este sem belaboring o ponto muito. Seis e oito, em seguida, seis são classificadas, oito são classificados. Fundi-las assim, e agora o próximo grande passo É, claro, ordenar a metade direita da o primeiro passo deste algoritmo. Então, nos concentramos em um, três, sete, cinco. Nós, então, concentrar-se na metade esquerda. A metade esquerda do que a metade direita que, em seguida, fundir em um e três. Em seguida, a metade direita, depois à esquerda metade do mesmo, em seguida, a metade direita do mesmo. Mesclar-lo, e agora o que passo permanece? Mesclar o grande meia esquerda eo grande metade direita, de modo que um vai lá em baixo, depois dois, depois três, depois quatro, depois cinco, depois seis, depois sete, depois oito. 

Então agora porque é que isto acaba por revelar, especialmente se n mais e logaritmos geralmente bastante escapar de você, pelo menos na memória recente? Bem, observe a altura dessa coisa. Tivemos oito elementos, e nós dividido por dois, por dois, por dois. Então log base dois dos oito nos dá três. E confiar em mim que, se um pouco vago sobre isso. Mas log base dois dos oito é três, assim fizemos três camadas de fusão. E quando se fundiu elementos, quantos elementos se olharmos para a cada uma dessas linhas? Um total de n, certo? Porque se fundir a linha superior, mesmo que nós fizemos isso aos poucos, que em última análise, tocou em cada número uma vez. E na segunda linha, a mesclar essas listas de tamanho dois, tivemos que tocar cada elemento uma vez. E então aqui realmente claramente na última fila, tivemos que tocar cada um desses elementos uma vez, mas apenas uma vez, então aqui está, então, a nossa log n n. 

E agora só para tornar as coisas um pouco mais formal só por um momento, se você eram agora analisar esta a uma espécie de nível mais elevado e tentar decidir, bem como pode você ir sobre expressando o tempo de execução deste algoritmo só de olhar para ele e não usando um exemplo inventado? Bem, quanto tempo você diria que um passo como este em amarelo levaria, Se n <2 retorno? Isso é um grande O de quê? Então, eu estou vendo um, por isso uma única etapa, talvez duas etapas porque é se e depois voltar, mas é constante de tempo, certo? Então nós dissemos O (1), e que é como vou expressar isso. T, basta ter tempo de execução. n é o tamanho da entrada, então T (n), apenas uma maneira elegante de dizer que o funcionamento dado tempo de entrada de tamanho n vai ser na ordem constante de tempo, em O (1). 

Mas por outro lado, o que sobre isso? Como você se expressar a tempo desta linha amarela que funcionam? T de quê? Você pode tipo de fraude aqui e responder a minha pergunta ciclicamente. Assim, se o tempo de funcionamento em geral que acabamos de dizer é T (n). E agora você está tipo de punt aqui e dizendo, bem, apenas ordenar a metade esquerda, e, em seguida, classificar a metade direita. Como podemos representar simbolicamente o tempo de execução desta linha amarela? T de quê? Qual é o tamanho da entrada? n mais de dois. Por que eu não disse isso? E, em seguida, esta é outra T (n / 2) e, em seguida, novamente, se eu fundir duas metades ordenadas, quantos elementos é que eu vou ter que tocar todo? n. Para que eu possa expressar isto, apenas para ser uma espécie de fantasia, como o tempo de funcionamento em geral. T (n) é apenas o tempo de execução T (n / 2), além de T (n / 2), deixou metade e metade direita, além S (n), que é, provavelmente, n passos, mas talvez, se eu estou usando dois dedos, é o dobro passos, mas é linear. É uma série de passos isso é um fator de n, assim podemos expressar isso como este. E é aí que agora vamos chutar para o de trás do nosso livro de matemática do ensino médio estamos em última análise, que a recorrência termina-se igual a este, n vezes log n, se você realmente fazer a a matemática mais formal. 

Então, isso é apenas duas perspectivas. Uma numericamente com um codificado exemplo representativo usando oito números e um mais olhada geral como chegamos lá. Mas o que é realmente interessante aqui é, mais uma vez, essa noção de ciclismo. Eu não estou usando para loops. Eu sou o tipo de definição algo em termos de si mesmo, Não só com a presente função matemática, mas também em termos de este código pseudo. Este código pseudo é recursiva em que duas das suas linhas é, essencialmente, dizendo-lhe para ir utilizar-se para resolver um menor problema de menor tamanho, e, em seguida, uma e outra vez e de novo até que ele talhar até este chamado caso base. 

Então, vamos realmente tirar um mais atraente take-away de isso da seguinte forma. Deixe-me ir em gedit e dar uma olhar para alguns dos código-fonte de hoje, em particular, este exemplo aqui. Sigma 0, que, aparentemente aumenta os números de um a n. Então vamos ver o que é familiar e desconhecido aqui. Primeiro, temos um par de inclui, portanto, nada de novo nisso. Prototype. Eu sou um pouco vago sobre isso depois de alguns dias, mas o que dizemos um protótipo de uma função é? AUDIÊNCIA: [inaudível]. COLUNA 1: O que é isso? AUDIÊNCIA: Nós anunciá-lo. COLUNA 1: Nós anunciá-lo. Então, você está ensinando Clang, hey, não realmente implementar isso ainda, mas em algum lugar neste arquivo, presumivelmente, vai ser uma função chamada quê? Sigma. E esta é apenas uma promessa de que ele vai olhar como este. Vai demorar um inteiro como input-- e eu posso ser mais explícito e dizer int n --e é vai retornar um int, mas meio ponto e vírgula, mm, eu vou dar a volta para implementar esta um pouco mais tarde. Mais uma vez, Clang é burro. Ele só vai saber o que você diga a ele de cima para baixo, por isso precisamos de pelo menos dar uma dica do que está por vir. 

Agora vamos olhar para o principal aqui. Vamos rolar para baixo aqui e ver o principal está fazendo. Não é que a longo de uma função, e na verdade, a construção aqui é familiar. Eu declaro uma variável n, e depois Eu importunar o usuário novo e de novo para um número inteiro positivo utilizando getInt, e só sair fora deste circuito uma vez que o usuário tenha cumprido. Do While, que usamos para importunar o usuário dessa maneira. Agora isto é interessante. Declaro um int chamado de "resposta". Eu atribuí-lo o valor de retorno de uma função chamada "sigma". Eu não sei o que isso faz ainda, mas Lembro-me de declarar que um momento atrás. E então eu estou passando no valor que o usuário digitou, n, e então eu relatar a resposta. Bem, vamos rolar para trás por apenas um momento. Vamos em frente neste diretório, fazer sigma 0, e realmente executar este programa e ver o que acontece. Então, se eu ir em frente e correr Neste programa, ./sigma-0, e eu digitar um positivo inteiro como dois, Sigma, como o símbolo grego indica, é apenas vai somar todos os números de zerar em até dois. Assim 0 mais 1 mais 2. Portanto, este deve espero dar-me 3. Isso é tudo o que está fazendo. E da mesma forma, se eu executar isto novamente e eu dar-lhe o número de três, isso é 3 + 2, de modo que é 5, mais 1 deveria me dar 6. E então se eu ficar muito louco e começar a digitar em números maiores, deve dar-me somas cada vez maiores. Então, isso é tudo. 

Então, o que sigma parece? Bem, é bastante simples. É como poderíamos ter implementado isso para o último par de semanas. "Int" vai ser o tipo de retorno. Sigma é o nome, e é preciso m uma variável em vez de n. Eu vou mudar isso em cima. Então este é apenas um teste de sanidade. Vamos ver por que em um momento. Agora eu declarar outra variável, suma, inicialize-o a zero. Então eu tenho esse loop iteração, aparentemente, para maior clareza, a partir de i = 1 em cima de um m =, que é tudo o que o usuário digitou, e então eu incrementar a soma assim. E, em seguida, retornar a soma. 

Assim, um par de perguntas. Um, eu afirmo no meu comentário que esta evita risco de um loop infinito. Por que passar em um número negativo induzir, potencialmente, um loop infinito? 

AUDIÊNCIA: Você nunca vai chegar a m. 

COLUNA 1: Nunca chegar m. Mas m é passado, então vamos Considere um exemplo simples. Se m é passado pelo usuário como um negativo. Independentemente do principal. Principal nos protege de isso também, então eu sou apenas sendo muito anal com sigma também certificar-se que a entrada não pode ser negativa. Portanto, se m for negativo, algo como um negativo. O que vai acontecer? Bem, eu vai se inicializado com um, e então eu vai ser inferior ou igual a m? 

Estar por. Isso estava-- não vamos, vamos nix esta história. Eu não pedi a essa pergunta, porque o risco que estou aludindo não vai acontecer, porque eu é sempre vai ser maior OK than--, Eu retiro a essa pergunta. Está bem. Vamos focar apenas esta parte aqui. Por que eu declarar algum fora do loop? Aviso na linha 49 eu tenho declarado i interior do laço, mas em linha 48 eu tenho declarou alguns fora. Sim. AUDIÊNCIA: [inaudível]. COLUNA 1: Claro. Então, em primeiro lugar, eu certamente não quero declarar e inicializar soma a zero no interior da circuito em cada iteração, porque isso iria derrotar claramente a propósito de somar os números. Gostaria de ficar mudando o valor de volta para zero. E também, o que é um outro mais arcanos razão para essa mesma decisão design? Sim. 

AUDIÊNCIA: [inaudível]. COLUNA 1: Exatamente. Eu quero acessá-lo fora do laço também em que linha? Em 53. E com base em nossa regra de ouro a partir de um par de palestras atrás, variáveis ​​são escopo, realmente, para o chaves que eles abrangem. Então, se eu não declarar soma dentro dessas chaves externas, Eu não posso usá-lo na linha 53. Dito de outra forma, se eu declarei soma aqui, ou até mesmo dentro do Para loop, eu não podia acessá-lo em 53. A variável que efetivamente desaparecido. Assim, um par de razões lá. Mas agora vamos voltar e ver o que acontece. Então sigma é chamada. Acrescenta-se 1 mais 2 ou 1 mais 2 mais 3, e em seguida, retorna o valor, armazena em resposta, e printf aqui É por isso que eu estou vendo na tela. Então é isso que nós vamos chamar uma iterativo abordagem, onde apenas iteração significa usar um loop. Um loop, um loop While, um Do While loop, apenas fazendo algo de novo e de novo e de novo. 

Mas sigma é um tipo de função puro em que eu poderia implementá-lo de forma diferente. E sobre isso, o que apenas para ser bem legal, deixe-me realmente se livrar de uma grande quantidade de distracção porque esta função É realmente muito simples. Vamos talhar-lo apenas aos seus quatro linhas centrais e se livrar de toda a comentários e chaves. Esta é uma espécie de alucinante execução alternativa. Tudo bem, talvez não alucinante, mas é o tipo de mais sexy, tudo bem, de olhar para este muito mais sucinta. Com apenas quatro linhas de código, A primeira vez que tenho esse teste de sanidade. Se m é igual ou inferior a zero, sigma não faz sentido. É só deveria estar na Neste caso, para números positivos, então eu só vou retornar zero arbitrariamente para que, pelo menos, ter alguns chamados caso base. 

Mas aqui está a beleza. A totalidade dessa ideia, acrescentando que o os números entre 1 e n, ou m, neste caso, pode ser feito por meio de passar a bola. Bem, o que é a soma de 1 a m? Bem, você sabe o quê? É o mesmo que a soma de m mais a soma de 1 para menos 1 m. Bem, você sabe o quê? O que há de sigma de m menos 1? Bem, se você seguir este tipo de logicamente, é o mesmo que m menos 1 além de sigma de m menos 2. Assim, você pode tipo de apenas-- isso é assim, se você está apenas tentando irritar um amigo e eles lhe fazer uma pergunta, você meio que responder com uma pergunta, você pode tipo de manter passar a bola. Mas o que é importante é que se você continuar fazer a pergunta menor e menor e menor, você está não perguntar o que há de sigma de n, o que é sigma de n, o que é sigma de n? Você está fazendo o que é sigma de n, o que é sigma de n menos 1, o que é sigma de n menos 2? Eventualmente sua pergunta vai tornar-se o quê? O que é de uma ou sigma zero, um valor muito pequeno, e assim que conseguir isso, o seu amigo, você não vai perguntar a mesma pergunta novamente, você está indo só para dizer, ah, é zero. Nós somos feitos de jogar este tipo de jogo cíclico estúpido. 

Então recursividade é o ato em programação de uma função que se autodenomina. Este programa, quando compilado e executado, é vai se comportar exatamente da mesma maneira, mas o que é importante é que dentro de uma função chamada sigma, há uma linha de código, em que estamos chamando a nós mesmos, que, normalmente, seria ruim. Por exemplo, se eu primeiro compilou este, assim que sigma-- fazer sigma 1 ./sigma-1. Inteiro positivo, por favor, 50 1275. Então, qual a função parece ser, com base em um teste, correcta. Mas e se eu ficar um pouco perigoso e excluir o chamado caso base, e dizer, bem, eu só estou fazendo isso é mais complicado do que é. Vamos calcular o sigma tomando m e, em seguida, adicionando em sigma m de menos um? Bem, o que vai acontecer aqui? Vamos diminuir o zoom. Vamos recompilar o programa, salvá-lo, recompilar o programa, e então pronto ./sigma-1 ampliar, entrar inteiro positivo, por favor, 50. Quantos de vocês estão dispostos para confessar a ver isso? 

Está bem. Então isso pode acontecer por um certo número de razões, e, francamente, esta semana estamos prestes a dar-lhe mais um deles. Mas, neste caso, tente raciocinar para trás o que poderia ter acontecido aqui? Falha de segmentação, que disse na última tempo, refere-se a um segmento de memória. Algo ruim aconteceu. Mas o que era mecanicamente que não deu certo aqui por causa da minha remoção de que o chamado caso base, onde voltei um valor embutido? O que você acha que deu errado? Sim. 

AUDIÊNCIA: [inaudível]. COLUNA 1: Ah. Boa pergunta. Assim, o tamanho do número que eu estava resumindo ficou tão grande que excedeu o tamanho do espaço de memória. Boa idéia, mas não fundamentalmente vai causar um acidente. Isso pode causar estouro de inteiros, onde os bits simplesmente virar e, em seguida, nós confundimos realmente um grande número de como um número negativo, mas isso em si não vai causar um acidente. Porque, no final do dia um int ainda é de 32 bits. Você não vai acidentalmente roubar um pouco 33. Mas um bom pensamento. Sim. 

AUDIÊNCIA: [inaudível]. COLUNA 1: O método nunca pára de correr, e, de fato, chama a si mesmo novamente e de novo e de novo e de novo e mais uma vez, e nenhuma as funções de todos os tempos terminar, pois seu único linha de código chama a si mesmos uma e outra vez e novamente. E o que é realmente acontecendo aqui, e agora nós pode tipo de desenhar esse pictoricamente. Deixai-me passar para um imagem por apenas um momento. Esta é uma imagem, que acabará por detalhar com mais detalhes, do que está acontecendo dentro da memória do seu computador. E verifica-se que em a parte inferior da imagem é algo chamado de pilha. Este é um pedaço de memória, um pedaço de memória RAM, que é apenas usado a qualquer momento uma função é chamada. Toda vez que você, programador, chamar uma função, o sistema operativo, como Mac OS, Windows ou Linux, pega um monte de bytes, talvez um poucos kilobytes, talvez alguns megabytes de memória, os entrega para você, e então permite que você executar a sua função usando o que quer que as variáveis ​​que você precisa. E se, em seguida, chamar outro função e uma outra função, você começa uma outra fatia de memória e outra fatia de memória. 

E, de fato, se estas bandejas verdes de Annenberg representam a memória, aqui está o que acontece pela primeira vez que você chamar função sigma. É como colocar uma bandeja como esta sobre o que é inicialmente uma pilha vazia. Mas, então, se essa bandeja chama-se, por assim dizer, chamando outra instância de sigma, que é como perguntar o sistema operacional, ooh, precisa de um pouco mais de memória, me que dar. E então ele fica empilhado em na parte superior. Mas o que é importante aqui é que a primeira bandeja ainda está lá, porque ele invocou esta segunda bandeja. Agora, entretanto, chamar sigma sigma, Isso é como perguntar para mais memória. Fica empilhado em cima aqui. sigma chamar sigma, que é um outro bandeja que fica empilhado aqui. E se você continuar fazendo isso, eventualmente, tipo de mapear esse visual para esse gráfico, o que vai acontecer com a pilha de bandejas? Ele vai exceder o montante de memória do computador. E assim que esta bandeja verde excede a linha horizontal acima pilha e acima dessa palavra montão, que vamos voltar no futuro, que é uma coisa ruim. A pilha é um diferente segmento de memória, e se você deixar que estes bandejas de pilha e pilha em, você vai exceder seu próprio segmento de memória, e um programa é de fato vai falhar. 

Agora, como um aparte, esta idéia de recursividade, portanto, pode claramente levar a problemas, mas não é necessariamente uma coisa ruim. Porque considerar, depois tudo, e talvez how-- isso leva algum tempo para se acostumar • Como a elegante ou como simples que a implementação do sigma foi. E nós não vamos usar recursão muito nos CS50, mas em CS51, e realmente qualquer classe onde você manipular estruturas de dados como árvores ou árvores genealógicas, que têm alguma hierarquia, ele é super, super útil. Agora, como um aparte, para que você como aspirantes a cientistas da computação estão familiarizados com alguns dos Google piadas, se você vai para o Google e você olha para o que está a definição de, digamos, a recursão, digite. Uh-huh. Como um aparte, eu puxei um pouco. Isso foi como 10 minutos de procrastinação esta manhã. Se você também Google "torto", aviso inclinando a cabeça slightly-- e então este é, talvez, mais atroz de todos desde que alguém passou como seu dia de aplicação do presente alguns anos ago-- vamos. Oh, wait-- isso é um bug. 

Assim sendo executado em um dos maiores sites do mundo são esses ovos de Páscoa estúpidos. Eles provavelmente consumir uma número não trivial de linhas de código apenas para que possamos ter pequenas coisas divertidas como essa. Mas pelo menos agora você começa algumas dessas piadas. 

Agora vamos dar uma olhada em algumas das branco mentiras que temos vindo a dizer nos últimos tempos, e começar a descascar algumas camadas tecnicamente de modo que você realmente entender o que está acontecendo e você pode entender algumas das ameaças, como Shellshock, que já começou a se tornar na vanguarda de todo mundo atenção, pelo menos nos meios de comunicação. Então aqui está uma função muito simples que retorna nada, vazio. Seu nome é swap. Leva em duas variáveis e ele retorna nada. Leva em ae b. Então, uma rápida demonstração. Trouxemos estes acima. Podemos muito bem ter um pouco quebrar aqui por apenas um momento e ter um pouco de algo para beber. Se alguém não se importaria se juntar me até aqui só por um momento. E quanto a você com a camisa marrom? Vamos lá para cima. Apenas o de hoje. Obrigado, no entanto. Tudo bem, e temos chegando que aqui? Qual o seu nome? 

COLUNA 4: Laura. 

COLUNA 1: Laura. Vamos lá para cima. Então Laura, desafio muito simples hoje. Prazer em conhecê-yo. Tudo certo. Portanto, temos um pouco de leite até aqui e nós temos um pouco de suco de laranja aqui e alguns copos que nós emprestado de Annenberg hoje. 

COLUNA 4: emprestado. COLUNA 1: E indo para a frente e dar-lhe metade de um copo de presente. Tudo certo. E nós vamos dar-lhe metade um copo de leite. Ah, e só para que você possa lembre-se que este era como, Lembrei-me de trazer isso e hoje. Ok. Se você não se importa, vamos ver, nós pode colocá-los sobre seus próprios óculos se você quiser. Este vai ser o mundo de olhos de Laura. Tudo certo. Portanto, o seu objetivo, dado duas xícaras de líquido aqui, leite e suco de laranja, é trocar os dois conteúdos de modo que a suco de laranja vai para a xícara de leite e o leite passa para o copo de suco de laranja. 

COLUNA 4: Eu recebo um outro copo? COLUNA 1: Eu estou tão feliz que você perguntou, embora que teria sido muito melhor filmagem se você não tivesse pedido. Mas sim, nós podemos oferecer-lhe um terceiro copo que está vazio, é claro. Tudo certo. Então trocar o conteúdo lá. Muito bom. Muito bom. Você está fazendo isso extremamente cuidado. E o passo três. Tudo certo. Excelente. Um grande aplauso seria bom para Laura. Tudo certo. Temos um pequeno presente de despedida para você, mas deixe-me levá-los. Muito obrigado. Assim, um exemplo simples, no entanto, para demonstrar que, se você fizer quer trocar o conteúdo de dois recipientes, ou vamos chamá-los de variáveis, você precisa de algum armazenamento temporário encenar um dos conteúdos na que você pode realmente fazer a troca. Então, na verdade, este código fonte aqui em C é representativa de exatamente isso. Se o sumo de laranja era um eo leite era b, e queríamos trocar os dois, você poderia tentar algo criativo vertendo-se umas às outras, mas que provavelmente não acabar particularmente bem. E, assim, usar um copo terceira, chamada ele tmp, T-M-P, por convenção, e colocar o conteúdo do JO em que, em seguida, trocar um copo, em seguida, colocar o JO no copo originais, assim atingir, exatamente como Laura fez, o swap. 

Então, vamos fazer exatamente isso. Deixe-me ir em frente e abrir -se um exemplo de que é na verdade, chamado de "não Swap ", porque este não é como simplesmente feito como se poderia pensar. Então, neste programa, note que Estou usando stdio.h, nosso velho amigo. Eu tenho o protótipo para trocar lá em cima, o que significa a sua implementação de provavelmente abaixo, e vamos ver o que este principal programa vai fazer por mim. A primeira vez que declarar int x recebe um, e int y recebe dois. Então, acho que aqueles que JO e leite, respectivamente. E então eu só tenho um printf dizendo x é este e y é isso, só para que eu possa visualmente ver o que está acontecendo. Então eu printf reivindicando que eu estou trocando os dois, e então eu imprimir um afirmam que eles são trocados, e eu imprimir x e y novamente. Então, aqui em swap é exatamente o que Laura fez, e exatamente o que vimos em a tela de um momento atrás. 

Então, vamos em frente e uma grande desilusão. Não se troca, e não corre swap, zoom sobre a saída aqui. Digite x é 1, y é 2, trocando trocados. ainda x é 1, e y é ainda 2. Assim, mesmo que, francamente, isso parece exatamente como, ainda mais tecnicamente, Laura o que fez, não parece funcionar. Então, por que isso? Bem, acontece que quando nós escrevemos um programa como este que tem tanto principal, destacamos aqui, e, em seguida, uma outra função, como swap, Destacam-se aqui, que chama, o mundo parece um pouco algo como estas bandejas há pouco. Quando principal em primeiro lugar é chamado, Isso é como perguntar sistema operacional para um pouco de memória para qualquer local, variáveis ​​como x e y que a principal tem, e eles acabam por aí. Mas, se as chamadas principais trocar, e principal passa para trocar dois argumentos, a e b, suco de laranja e leite, não é como entregando o suco de laranja eo leite para Laura. O que um computador faz, é passa cópias do suco de laranja e cópias do leite para Laura, de modo que o que é, em última análise dentro desta bandeja é o valor de um e dois, ou JO e leite, mas cópias dos mesmos, de modo que, neste ponto na história, não é JO e leite em cada uma destas bandejas. Há um um e dois em cada uma destas bandejas, ea função de swap é de fato trabalhando. Está trocando-os por dentro de bandeja o segundo mais alto, mas que a troca não tem impacto. E com base em apenas algumas princípio básico nós temos falamos antes, e de fato a poucos minutos atrás, o que poderia explicar por que mudar a e b dentro de troca não tem efeito sobre x e y, embora Passei x e y para a função swap. Qual é a palavra chave aqui que pode simplista explicar? Acho que ouvi-lo aqui? AUDIÊNCIA: Return. COLUNA 1: Retorno? Não voltar. Vamos com um outro. O que é isso? 

AUDIÊNCIA: [inaudível]. 

COLUNA 1: OK, então return-- pudéssemos tornar o trabalho de retorno na história, mas há uma explicação ainda mais simples. AUDIÊNCIA: Scope. COLUNA 1: Âmbito. Vou levar escopo. Então alcance, lembre-se que a x e y declarada. Eles estão declaradas dentro de principal até aqui. a e b, entretanto, são efetivamente declarado dentro de swap, não exatamente as chaves, mas ainda na área geral de swap. E assim, de facto, a e b só existem dentro dessa bandeja de Annenberg, esta segunda parte do código. Então, nós estamos mudando a cópia, mas isso não é realmente tudo o que útil. 

Então, vamos dar uma olhada este nível um pouco inferior. Eu vou voltar para o diretório de origem, e eu estou indo para a primeira zoom aqui, e apenas para confirmar que estou nesta janela de terminal maior, o programa ainda está se comportando assim. Suponha agora que este não é intencional. É evidente que eu queria swap para trabalho, por isso se sente como um bug. Agora eu poderia começar a adicionar um Muitas printf do para o meu código, imprimir x aqui, y sobre aqui, um ali, b aqui. Mas, francamente, isso é provavelmente o que você tem feito por um par de semanas agora, no horário de expediente e em casa quando se trabalha em Série de Exercícios tentando encontrar alguns bugs. Mas você vai ver, se você não tiver, que conjunto de problemas apresenta três para um comando chamado GDB, onde GDB, depurador GNU, tem-se um monte de recursos que podem, na verdade, vamos entender situações como este, mas mais convincente, resolver problemas e encontrar bugs. Então, eu vou fazer isso. Em vez de ./noswap, estou vez vai correr GDB ./noswap. Em outras palavras, eu estou indo para executar o meu programa não em Bash, nosso novo amigo hoje. Eu estou indo para executar o meu programa noswap dentro deste outro programa chamado GDB, que é um depurador, que é um programa que foi projetado para ajudar Vocês, humanos, encontrar e remover bugs. Então, se eu bater correr aqui, há uma quantidade atroz de texto que você realmente nunca tem que ler. É essencialmente uma distração a partir da linha, que Eu vou bater Control-L para chegar no topo lá. Este é o prompt GDB. Se eu quiser executar este programa agora, como esta pequena folha de fraude em hoje slides sugere, Run é o primeiro ordena que pretendia introduzir. E eu estou indo só para digitar correr até aqui dentro de GDB, e na verdade ele correu meu programa. Agora há algum adicional saídas da tela como esta, mas isso é GDB apenas sendo anal e nos dizer o que está acontecendo. Você realmente não precisa se preocupar sobre esses detalhes agora mesmo. Mas o que é realmente legal sobre GDB, se eu fizer isso novamente-- Control-L limpa o screen-- deixe-me ir em frente e digite "quebrar principal", assim, quando eu pressione Enter, definindo o que é chamado um ponto de ruptura na noswap.c, linha 16, que é onde GDB descobri o meu programa, na verdade, é, a minha função é realmente. Isso nós vamos ignorar por agora mas esse é o endereço na memória especificamente desta função. Então agora quando eu digito correr, perceber o que é legal aqui. Meu programa quebra na linha I disse GDB para pausar a execução em. Então eu não tenho que mudar agora meu código, adicionar alguns printf de, recompilar, reprise ele, alterar, adicionar alguns printf do, salvá-lo, recompilar, executá-lo. Eu só posso andar através do meu programa passo a passo a passo na velocidade humana, não no tipo Intel dentro da velocidade. 

Então agora perceber essa linha aparece aqui, e se eu voltar ao meu programa no gedit, perceber que isso é verdade a primeira linha de código. Há linha 16 em gedit. Há linha 16 no GDB, e mesmo embora esta interface em preto e branco não é tão usuário amigável, isso significa que a linha 16 não foi executado ainda, mas que está prestes a ser. Então, na verdade, se eu digitar impressão x, não printf, apenas print x, Eu recebo algum valor falso lá de zero, porque x ainda não foi inicializado. Então eu vou escrever a seguir, ou, se você quer ser extravagante, apenas n para o próximo. Mas quando eu digito seguinte entra, agora notar que se move sobre a linha 17. Então, logicamente, se eu tiver executado linha 16 e agora estou a escrever print x, o que devo ver? Uma. 

E agora esse é reconhecidamente confuso. Dois dólares é apenas uma maneira elegante de, se você quero referir-se a esse valor mais tarde, você pode dizer "sinal de dólar dois." É como uma referência para trás. Mas, por enquanto, apenas ignorá-lo. O que é interessante é o que é à direita do sinal de igual. E agora se eu digitar seguinte novamente e imprimir y, eu deveria ver 2. Eu também já pode imprimir x novamente, e, francamente, se eu estou ficando um pouco confuso quanto ao onde eu estou, eu posso tipo de lista para lista e só ver algum contexto ao redor o ponto que eu estou realmente em. E agora eu posso escrever ao lado, e não é x 1. Agora eu digito seguinte. Oh, y é 2. E mais uma vez, é confuso, porque a produção do GDB está sendo misturados com a minha própria saída. Mas se você manter em mente, por olhando para trás e para a frente em seu código ou colocando-o para fora do lado a lado, talvez, você vai ver que realmente eu sou apenas percorrendo meu programa. 

Mas observe o que acontece em seguida, literalmente. Aqui está a linha 22. Deixe-me ir sobre ele, movendo-se, assim, em a 23, e se eu imprimir x agora, ainda um. E se eu imprimir y agora, ainda um. Portanto, este não é um exercício útil. Então, vamos refazer isso. Deixe-me voltar até o tiragem superior e tipo novamente. E ele está dizendo o programa que está sendo depurado já começou, iniciado a partir do início. Sim, vamos fazer isso de novo. E desta vez vamos fazer a seguir, next, next, next, next, mas agora as coisas começam a ficar interessantes. Agora eu quero entrar swap, então eu não digitar em seguida. Eu digito passo, e agora percebe que me saltou para a linha noswap.c 33. Se eu voltar para o gedit, o que é linha 33? Essa é a primeira real linha de código dentro de swap. O que é bom, porque agora eu posso tipo de fuçar e ficar curioso sobre o que está acontecendo realmente lá. Deixe-me imprimir tmp. Whoa. Por que ter algum tmp louco, valor de lixo falso? AUDIÊNCIA: Não foi inicializado. COLUNA 1: Não foi inicializado. E, de fato, quando você executar um programa, você está dado um monte de memória pelo sistema operacional, mas você não inicializou quaisquer valores, então o que você está bocados vendo aqui, mesmo que seja este grande negativo louco número, significa apenas que aqueles que são os restos de algum uso anterior de que a memória RAM, apesar de eu não ter eu precisava disso ainda. Então agora eu estou indo para ir em frente e tipo seguinte, e se eu agora digite impressão tmp, o que devo ver? Seja qual for o valor de a foi, um é o primeiro argumento, apenas como x foi o primeiro coisa que está sendo transmitido, assim um e x deve ser o mesmo, assim imprimir tmp deve imprimir-me um. 

Então, o que você verá no conjunto de problemas três é um tutorial das sortes no GDB, mas percebe que este é o começo de uma olhada em uma ferramenta que vai realmente ajudá-lo a resolver problemas forma muito mais eficaz. O que nós estamos, em última instância vai fazer na quarta-feira é começar a descascar algumas camadas e remover algumas rodinhas. Essa coisa chamada cadeia que temos utilizado durante algum tempo, vamos tomar lentamente que longe de você e começar a falar sobre algo mais esotericamente conhecido como char *, mas vamos fazer isso agradável e suavemente em primeiro lugar, embora os ponteiros, como são chamados, podem fazer alguma coisas muito ruins se vítimas de abuso, olhando um pouco de claymation nosso amigo Nick Parlante de Stanford Universidade, professor em computador ciência que montar esse pré-visualização do que está por vir nesta quarta-feira. 

[REPRODUÇÃO] Ei, Binky. Acorde. É hora de diversão ponteiro. 

-Qual Que é isso? Saiba mais sobre ponteiros? Ah, que bom! [FIM REPRODUÇÃO DE VÍDEO] COLUNA 1: Que espera por você na quarta-feira. Vamos vê-lo em seguida. [REPRODUÇÃO] -E Agora, pensamentos profundos, por Daven Farnham. 

Por quê estamos aprendendo C? Por que não A +? 

[Risos] 

[FIM REPRODUÇÃO DE VÍDEO]