[Powered by Google Translate] [Semana 6, continuação]
[David J. Malan] [Harvard University]
[Esta é CS50.] [CS50.TV]
Este é CS50 e este é o fim da semana 6.
Então CS50x, um dos primeiros cursos de Harvard envolvidos na iniciativa EDX
de fato estreou esta segunda-feira passada.
Se você gostaria de obter um vislumbre do que os outros na Internet
estão agora acompanhando com, você pode ir para x.cs50.net.
Que irá redirecioná-lo para o local apropriado no edx.org,
que foi onde este e outros cursos do MIT e Berkeley vivem agora.
Você vai ter que se inscrever para uma conta, você vai descobrir que o material é basicamente o mesmo
como você teve neste semestre, embora algumas semanas atrasadas, como temos tudo pronto.
Mas o que os alunos em CS50x vai ver agora é uma interface bastante como este.
Este, por exemplo, é Zamyla levando passo a passo para conjunto de problemas 0.
Ao fazer o login para edx.org, um estudante CS50x vê os tipos de coisas
que seria de esperar para ver em um curso: a palestra para a segunda-feira,
palestra para quarta-feira, shorts diversos, os conjuntos de problemas, as orientações, PDFs.
Além disso, como você vê aqui, traduções automáticas
transcrições de inglês para chinês, japonês, espanhol, italiano,
e um bando inteiro de outras línguas que certamente vai ser imperfeito
como nós rolamos-los programaticamente usando uma coisa chamada API,
ou interface de programação de aplicativo, do Google
que nos permite converter Inglês para essas outras línguas.
Mas, graças ao maravilhoso espírito de alguns voluntários mais de cem,
pessoas aleatórias na Internet que gentilmente oferecidos a se envolver
Neste projeto, nós vamos ser gradualmente melhorar a qualidade dessas traduções
por ter humanos corrigir os erros que nossos computadores fizeram.
>> Assim, verifica-se que havia alguns estudantes mais aparecer na segunda-feira do que o inicialmente esperado.
Na verdade, agora CS50x tem 100.000 pessoas que seguem junto em casa.
Então, percebe que são todos parte dessa aula inaugural de fazer este curso de ciência da computação
educação mais geralmente, de forma mais ampla, acessível.
E a realidade é agora, com alguns desses cursos massivos online,
todas elas começam com estes números muito elevados, como parece ter feito aqui.
Mas o objetivo, em última instância, para CS50x é realmente levar as pessoas como muitos a linha de chegada quanto possível.
Pelo projeto, CS50x vai ser oferecido a partir desta segunda-feira passada
todo o caminho até 15 de abril de 2013, para que as pessoas que têm compromissos escolares em outros lugares,
trabalho, a família, os conflitos outros e semelhantes, tem um pouco mais de flexibilidade
com o qual a mergulhar neste curso, que, basta dizer,
é bastante ambiciosa feito apenas ao longo de apenas três meses, durante um semestre de costume.
Mas esses alunos serão enfrentar os conjuntos mesmo problema, vendo o mesmo conteúdo,
ter acesso aos mesmos calções e semelhantes.
Então, percebemos que todos nós somos verdadeiramente juntos nessa.
E um dos objetivos finais de CS50x não é só para ter pessoas como muitos
para a linha de chegada e dar-lhes essa nova compreensão da ciência da computação
e programação, mas também para que eles têm essa experiência compartilhada.
Uma das características definidoras de 50 no campus, esperamos,
foi este tipo de experiência comum, para melhor ou para pior, às vezes,
mas ter essas pessoas a voltar-se para a esquerda e para a direita,
e as horas de expediente e Hackathon e da feira.
É um pouco mais difícil de fazer isso pessoalmente com pessoas on-line,
mas CS50x vai concluir em abril, com a primeira CS50 Expo,
que será uma adaptação online da nossa idéia da feira
onde estes milhares de estudantes todos serão convidados a apresentar uma 1 - a 2 minutos de vídeo,
ou um screencast de seu projeto final ou vídeo deles acenando Olá
e falar sobre seu projeto e demos-lo,
bem como os seus antecessores fizeram aqui no campus da feira,
de modo que até o final do semestre, a esperança é ter uma exposição global
de projetos dos alunos CS50x 'finais, bem como aquele que o espera em dezembro aqui no campus.
Assim, mais do que em próximos meses.
>> Com 100.000 estudantes, porém, vem a necessidade de uma CAs mais alguns.
Dado que vocês estão abrindo a trilha aqui e tendo CS50
várias semanas antes do lançamento deste material para as pessoas em EDX,
perceber que gostaríamos de envolver como muitos de nossos próprios alunos quanto possível a esta iniciativa,
tanto durante o semestre, assim como neste inverno e na próxima Primavera.
Então, se você gostaria de se envolver em CS50x,
juntando-se particularmente em CS50x discutir, a versão de EDX CS50 discutir,
que muitos de vocês estão usando no campus, no quadro de avisos online,
por favor, faça a cabeça para essa URL, deixe-nos saber quem você é,
porque nós adoraríamos para construir uma equipe de alunos e funcionários e professores iguais
no campus que estão simplesmente jogando bem e ajudando.
E quando vêem uma questão que é familiar a eles,
você ouve um estudante relatar algum bug em algum lugar lá fora, em algum país na Internet,
e que toca uma campainha porque você também teve que mesmo assunto
em seu d-hall, há algum tempo, espero, então você pode dialogar e partilhar a sua própria experiência.
Então por favor não participar se você gostaria.
>> Cursos de ciência da computação na Universidade de Harvard tem um pouco de uma tradição,
CS50 entre eles, de ter algum fato, algumas roupas, que você pode usar com orgulho
no final do semestre, dizendo com um certo orgulho que você terminou CS50
e tomou CS50 e afins, e nós tentamos sempre envolver os alunos
neste processo, tanto quanto possível, em que convidamos,
nessa época do semestre, os alunos a apresentarem projetos
usando o Photoshop, ou qualquer ferramenta de escolha que você gostaria de usar
se você é um designer, a submeter projetos para T-shirts e camisolas
e guarda-sóis e bandanas para cães pequenos que temos agora e similares.
E tudo é então - os vencedores de cada ano são, então, exibiu
no site do curso em store.cs50.net.
Tudo é vendido ao custo de lá, mas o site só funciona sozinho
e permite que as pessoas a escolher as cores e desenhos que eles gostam.
Então eu pensei que tinha acabado de partilhar alguns dos projetos do ano passado
que estavam no site além deste aqui, que é uma tradição anual.
"Todo dia eu estou Seg Faultn" era uma das propostas do ano passado,
que ainda está disponível lá para ex-alunos.
Tivemos um presente ", CS50, Fundação 1989."
Um dos nossos Bowdens, Rob, era muito popular no ano passado.
"Team Bowden" nasceu, este projeto foi submetido, entre os mais vendidos.
Como foi este aqui. Muitas pessoas tiveram "Fever Bowden" de acordo com os registros de vendas.
Perceba que que poderia agora ser seu projeto lá, em cima da Internet.
Mais detalhes sobre este problema na próxima define por vir.
>> Mais uma ferramenta: você teve alguma exposição e espero que agora
alguma experiência hands-on com o GDB,
que é, naturalmente, um depurador e permite que você manipule
o seu programa em um nível bastante baixo, fazendo o tipo de coisas?
O que o GDB deixar você fazer?
Sim? Dê-me alguma coisa. [Responder Estudante, ininteligível]
Bom. Etapa em função, para que você não só tem que digitar run
e ter o golpe programa através do seu conjunto, imprimir coisas para a saída padrão.
Em vez disso, você pode percorrê-lo linha por linha, digitando próxima
ir linha por linha por linha ou passo para mergulhar em uma função, normalmente aquele que você escreveu.
O que mais faz GDB deixar você fazer? Sim? [Responder Estudante, ininteligível]
Imprimir variáveis. Então, se você quer fazer um pouco de introspecção dentro de seu programa
sem ter que recorrer a escrever instruções printf em todo o lugar,
você pode apenas imprimir uma variável ou exibir uma variável.
O que mais você pode fazer com um depurador como o GDB?
[Responder Estudante, ininteligível]
Exatamente. Você pode definir pontos de interrupção, você pode dizer que a execução pausa
a função principal ou a função foo.
Você pode dizer que a execução pausa na linha 123.
E pontos de interrupção são uma técnica muito poderosa
porque se você tem uma sensação geral de que o seu problema
provavelmente é, você não precisa perder tempo percorrendo totalidade do programa.
Você pode pular essencialmente à direita e então começar a escrever -
percorrendo-a com passo ou próximo ou semelhante.
Mas o problema com algo parecido com o GDB é que ele ajuda você, o humano,
encontrar os seus problemas e encontrar seus bugs.
Isso não significa necessariamente encontrá-los muito por você.
>> Então, nós introduzimos o style50 outro dia, que é uma ferramenta de linha de comando curta
que tenta estilizar seu código um pouco mais limpa do que você, o humano, poderia ter feito.
Mas isso, também, é realmente apenas uma coisa estética.
Mas acontece que há essa outra ferramenta chamada Valgrind que é um pouco mais misterioso de usar.
Sua saída é atrozmente enigmática, à primeira vista.
Mas é maravilhosamente útil, especialmente agora que estamos na parte do termo
onde você está começando a usar malloc e alocação dinâmica de memória.
As coisas podem dar muito, muito errado rapidamente.
Porque se você esquecer de libertar a sua memória, ou você cancelar a referência de algum ponteiro NULL,
ou você cancelar a referência de algum ponteiro de lixo, que normalmente é o sintoma que resultados?
Seg culpa. E você começa este arquivo núcleo de algum número de kilobytes ou megabytes
que representa o estado da memória do seu programa quando ele caiu,
mas o seu programa, em última análise seg falhas, falha de segmentação,
o que significa que algo de ruim aconteceu quase sempre relacionados
a um erro relacionado com a memória que você fez em algum lugar.
Então Valgrind ajuda a encontrar coisas como esta.
É uma ferramenta que você execute, como GDB, depois de ter compilado seu programa,
mas em vez de executar o programa diretamente, você corre Valgrind
e você passar para ele o seu programa, assim como você faz com o GDB.
Agora, o uso, para obter o melhor tipo de saída,
é um pouco longo, por isso lá no topo da tela, você verá Valgrind-v.
"-V" quase universalmente significa verbose quando você está usando programas em um computador Linux.
Então isso significa cuspir mais dados do que você pode, por padrão.
"- Leak-check = total". Este é apenas dizer seleção para todos os possíveis vazamentos de memória,
erros que eu poderia ter feito. Isto, também, é um paradigma comum com programas Linux.
Geralmente, se você tem um argumento de linha de comando que é um "interruptor",
que deveria mudar o comportamento do programa, e é uma única letra,
é-v, mas se isso está ligado, apenas pelo design do programador,
é uma palavra completa ou série de palavras, o argumento de linha de comando começa com -.
Estes são apenas convenções humanas, mas você vai vê-los cada vez mais.
E, em seguida, finalmente, "a.out" é o nome arbitrário para o programa, neste exemplo particular.
E aqui vai uma saída representativa.
>> Antes de olharmos para o que isso significa, deixe-me ir para um trecho de código aqui.
E deixe-me passar esta fora do caminho, em breve,
e vamos dar uma olhada em memory.c, que é este pequeno exemplo aqui.
Portanto, neste programa, deixe-me zoom e as funções e perguntas.
Nós temos uma função principal que chama uma função, f,
e então o que se f continuar a fazer, em Inglês um pouco técnico?
O que faz f proceder para fazer?
Que tal eu vou começar com a linha 20, e localização da estrela não importa,
mas eu só vou ser coerente aqui com última palestra.
Qual é a linha 20 não para nós? No lado da mão esquerda. Vamos dividi-la ainda mais.
Int * x: o que é que faz?
Okay. É declarar um ponteiro, e agora vamos ser ainda mais técnico.
O que significa, muito concretamente, para declarar um ponteiro? Alguém mais?
Sim? [Responder Estudante, ininteligível] Muito longe.
Então você está lendo para o lado direito do sinal de igual.
Vamos nos concentrar apenas na esquerda, apenas em int * x.
Isso significa "declarar" um ponteiro, mas agora vamos mergulhar mais fundo para essa definição.
O que isso concretamente, tecnicamente significa? Sim?
[Responder Estudante, ininteligível]
Okay. Ele está se preparando para gravar um endereço na memória.
Bom. E vamos dar um passo adiante, que é declarar uma variável, x, que é de 32 bits.
E eu sei que é de 32 bits porque -?
Não é porque é um int, porque é um ponteiro neste caso.
Coincidência que é um eo mesmo com um int,
mas o fato de que não é a estrela que significa que este é um ponteiro
e no interior do aparelho, como acontece com muitos computadores, mas não todas, as indicações são de 32 bits.
Em mais hardware moderno, como os mais recentes Macs, os mais recentes PCs, você pode ter ponteiros de 64 bits,
mas no aparelho, essas coisas são de 32 bits.
Então, vamos padronizar isso. Mais concretamente, a história é a seguinte:
Nós "declarar" um ponteiro, o que é que isso significa?
Nós nos preparamos para armazenar um endereço de memória.
O que significa isso?
Nós criamos uma variável chamada x, que ocupa 32 bits
que em breve armazenar o endereço de um inteiro.
E isso é provavelmente tão preciso quanto podemos chegar.
É bom avançar para simplificar o mundo e dizer declarar um ponteiro chamado x.
Declare um ponteiro, mas perceber e entender o que está realmente acontecendo
mesmo em apenas alguns desses personagens.
>> Agora, este é quase um pouco mais fácil, mesmo que seja uma mais expressão.
Então o que é que esta fazendo, que é destaque agora: "malloc (10 * sizeof (int));" Sim?
[Responder Estudante, ininteligível]
Bom. E eu vou levá-lo lá. É atribuição de um bloco de memória para 10 inteiros.
E agora vamos mergulhar em um pouco mais profunda, que é alocar um bloco de memória para 10 inteiros.
O que é malloc depois retornar?
O endereço do bloco, ou, de forma mais concreta, o endereço do primeiro byte do referido pedaço.
Como, então, sou eu, o programador, para saber onde esse pedaço de fins de memória?
Eu sei que é contíguo. Malloc, por definição, lhe dará um pedaço contíguo de memória.
Nenhum lacunas. Você tem acesso a todos os bytes nesse pedaço,
de costas para trás, mas como eu sei que o fim deste pedaço de memória é?
Quando você usa malloc? [Responder Estudante, ininteligível] Boa.
Você não. Você tem que se lembrar.
Eu tenho que lembrar que eu usei o valor 10, e eu não parecem mesmo ter feito isso aqui.
Mas a responsabilidade é inteiramente em mim. Strlen, que nos tornamos um pouco dependente para cordas,
só funciona por causa dessa convenção de ter \ 0
ou este caráter especial nul, NUL, no final de uma string.
Isso não vale para apenas pedaços arbitrários de memória.
Cabe a você. Assim, a linha 20, então, aloca um bloco de memória
que pode armazenar 10 inteiros, e armazena o endereço do primeiro byte
desse pedaço de memória na variável x chamado.
Logo, o que é um ponteiro. Então, linha 21, infelizmente, foi um erro.
Mas, primeiro, o que ele está fazendo? É dizer loja no local 10, 0 indexados,
do bloco de memória chamado x o valor 0.
>> Então, observe algumas coisas estão acontecendo.
Mesmo que x é um ponteiro, lembrar de algumas semanas atrás
que você ainda pode usar a matriz estilo de notação de colchete.
Porque isso é realmente curto-mão notação para a aritmética de ponteiro mais crítico para o futuro.
onde iríamos fazer algo como isto: Pegue o endereço x, mover mais de 10 pontos,
em seguida, ir para lá a qualquer endereço é armazenado no local.
Mas, francamente, este é apenas atroz de ler e se sentir confortável com.
Assim, o mundo geralmente usa os colchetes só porque ele é muito mais humano-amigável para ler.
Mas isso é o que realmente está acontecendo debaixo do capô;
x é um endereço não, uma matriz, de per si.
Portanto, este é armazenar 0 na posição 10 em x.
Por que isso é ruim? Sim?
[Responder Estudante, ininteligível] Exatamente.
Nós só alocados 10 ints, mas contar de 0 ao programar em C,
para que você tenha acesso a 0 10 1 2 3 4 5 6 7 8 9, mas não.
Assim, ou o programa vai culpa seg ou não é.
Mas nós realmente não sabemos, este é um tipo de comportamento não determinístico.
Isso realmente depende se temos sorte.
Se se verificar que o sistema operacional não se importa se eu usar esse byte extra,
mesmo que não tenha dado para mim, o meu programa não pode falhar.
É cru, é buggy, mas você não pode ver esse sintoma,
ou você pode vê-lo só de vez em quando.
Mas a realidade é que o bug é, de fato, não há.
E é realmente problemático se você escreveu um programa que você quer ser correto,
que você vendeu o programa que as pessoas estão usando que de vez em quando cai
porque, é claro, este não é boa. De fato, se você tem um celular com Android ou um iPhone
e você baixar aplicativos nos dias de hoje, se você já teve um app abortar,
de repente ele desaparece, que é quase sempre o resultado de algum problema relacionado à memória,
qual o programador asneira e dereferenced um ponteiro
que ele ou ela não deve ter, eo resultado do iOS ou Android é apenas para matar o programa completo
em vez de comportamento indefinido risco ou algum tipo de comprometimento da segurança.
>> Há um outro bug no programa além deste.
O que mais eu estraguei tudo neste programa?
Eu não pratiquei o que eu tenho pregado. Sim?
[Responder Estudante, ininteligível] Boa.
Eu não libertou a memória. Portanto, a regra de ouro agora
tem que ser sempre que você chamar malloc, você deve chamar livre quando você é feito usando a memória.
Agora, quando eu iria querer libertar esta memória?
Provavelmente, assumindo que esta primeira linha foi correta, eu gostaria de fazê-lo aqui.
Porque eu não poderia, por exemplo, faça-o aqui. Por quê?
Apenas fora do escopo. Assim, mesmo que estamos falando de ponteiros,
esta é uma semana 2 ou 3 questão, em que x é apenas um alcance dentro das chavetas onde foi declarado.
Então você definitivamente não pode libertá-lo lá. Minha única chance de libertá-la é de aproximadamente após a linha 21.
Este é um programa bastante simples, era bastante fácil, uma vez que o tipo de enrolado sua mente
em torno do que o programa está fazendo, onde os erros foram.
E mesmo se você não vê-lo em primeiro lugar, espero que seja um pouco óbvio agora
que esses erros são muito facilmente resolvidos e facilidade.
Mas quando um programa é mais do que 12 linhas de tempo, é 50 linhas, 100 linhas,
andar através de seu código linha por linha, pensando por isso, logicamente,
é possível, mas não particularmente divertido de fazer, constantemente à procura de bugs,
e também é difícil de fazer, e é por isso que uma ferramenta como Valgrind existe.
Deixe-me ir em frente e fazer isso: deixe-me abrir a janela de terminal,
e deixe-me não apenas executar memória, porque a memória parece estar bem.
Eu estou tendo sorte. Indo para o byte adicional no fim da matriz
não parece ser muito problemático.
Mas deixe-me, no entanto, fazer uma verificação de sanidade mental, o que significa apenas para verificar
se este é ou não realmente correto.
>> Então vamos fazer valgrind-v - leak-check = completo,
e, em seguida, o nome do programa, neste caso, é a memória, e não a.out.
Então deixe-me ir em frente e fazer isso. Pressione Enter.
Querido Deus. Esta é a sua saída, e é isso que me referi anteriormente.
Mas, se você aprender a ler através de todos os disparates aqui,
mais isso é apenas a saída de diagnóstico que não é tão interessante.
O seu olho realmente quer estar procurando é qualquer menção de erro ou inválido.
Palavras que sugerem problemas.
E, de fato, vamos ver o que está acontecendo de errado aqui.
Eu tenho um resumo de algum tipo, "em uso na saída:. 40 bytes em blocos de 1"
Eu não tenho certeza do que um bloco é ainda, mas 40 bytes
realmente se sente como se eu pudesse descobrir de onde que vem.
40 bytes. Por que 40 bytes em uso na saída?
E, mais especificamente, se rolar aqui,
por que eu definitivamente perdeu 40 bytes? Sim?
[Responder Estudante, ininteligível] Perfeito. Sim, exatamente.
Havia dez números inteiros, e cada um destes é o tamanho de 4 ou 32 bits,
então eu perdi exatamente 40 bytes, porque, como você propôs, eu não chamei livre.
Isso é um erro, e agora vamos olhar para baixo um pouco mais e ver ao lado deste,
"Inválido escrever de tamanho 4". Agora, o que é isso?
Este endereço é expresso que a notação de base, aparentemente?
Este é hexadecimal, ea qualquer momento você vê um número começando com 0x,
isso significa hexadecimal, o que fizemos no caminho de volta, eu acho, seção pset 0 de perguntas,
que era apenas para fazer um exercício de aquecimento, a conversão de decimal para hexadecimal para binário e assim por diante.
Hexadecimal, apenas por convenção humana, é geralmente usado para representar ponteiros
ou, de modo mais geral, aborda. É apenas uma convenção,
porque é um pouco mais fácil de ler, é um pouco mais compacto do que algo como decimal,
e binário é inútil para a maioria dos seres humanos de usar.
Então agora o que isso significa? Bem, parece que há uma gravação inválido
de tamanho 4 na linha 21 de memory.c.
Então vamos voltar para a linha 21, e, de fato, é aqui que a gravação inválido.
Então Valgrind não vai completamente segura minha mão e me diga o que a correção é,
mas ele está detectando que eu estou fazendo uma gravação inválido.
Estou tocando 4 bytes que eu não deveria ser, e, aparentemente, isso porque,
como você apontou, eu estou fazendo [10] em vez de [9] maximamente
ou [0] ou algo entre os dois.
Com Valgrind, realizar qualquer momento que você está escrevendo um programa
que usa ponteiros e utiliza a memória, e mais especificamente malloc,
definitivamente o hábito de correr tanto tempo
mas muito facilmente copiado e colado comando do Valgrind
para ver se há alguns erros lá.
E vai ser esmagadora cada vez que você ver a saída,
mas apenas analisar visualmente através de toda a saída e veja se você ver menções de erros
ou avisos ou inválido ou perdido.
Quaisquer palavras que soam como você errou em algum lugar.
Então percebe que é uma nova ferramenta em seu toolkit.
>> Agora na segunda-feira, tivemos um monte de gente veio aqui
e representar a noção de uma lista ligada.
E introduzimos a lista ligada como uma solução para o problema?
Sim? [Responder Estudante, ininteligível] Boa.
Matrizes não podem ter memória adicionados a eles.
Se você alocar uma matriz de tamanho 10, que é tudo que você conseguir.
Você pode chamar uma função como realloc se inicialmente chamada malloc,
e que pode experimentar a crescer a matriz, se houver espaço para o fim de que
que ninguém mais está usando e, se não há, ela só vai encontrar um pedaço maior em outro lugar.
Mas então ele vai copiar todos os bytes para a nova matriz.
Isso soa como uma solução muito correta.
Por que isso é pouco atraente?
Quero dizer que funciona, os seres humanos têm resolvido este problema.
Por que temos que resolver isso na segunda-feira com listas ligadas? Sim?
[Responder Estudante, ininteligível] Pode levar um longo tempo.
Na verdade, a qualquer momento que você está chamando malloc calloc ou realloc ou, o que é ainda um outro,
qualquer momento que você, o programa, está falando com o sistema operacional,
você tende a tornar o programa lento.
E se você está fazendo esses tipos de coisas em loops, você está realmente abrandar as coisas.
Você não vai perceber isso por mais simples de "Hello World" programas do tipo,
mas em programas muito maiores, pedindo que o sistema operacional novo e de novo para a memória
ou dando-lhe de volta uma e outra vez tende a não ser uma coisa boa.
Além disso, é apenas uma espécie de intelectual - é um completo desperdício de tempo.
Por que alocar mais memória e mais risco, copiar tudo para a nova matriz,
se você tem uma alternativa que permite alocar memória apenas o quanto você realmente precisa?
Portanto, há prós e contras aqui.
Uma das vantagens é que agora temos dinamismo.
Não importa de onde os pedaços de memória são de que estão livres,
Eu só posso classificar de criar estas migalhas de pão através de ponteiros
amarrar minha lista inteira ligados.
Mas eu pagar pelo menos um preço.
>> O que eu tenho a dar-se na obtenção de listas ligadas?
Sim? [Responder Estudante, ininteligível] Boa.
Você precisa de mais memória. Agora eu preciso de espaço para estas indicações,
e no caso de esta lista super simples ligado
que está apenas a tentar armazenar números inteiros, que são 4 bytes, que continua dizendo
bem, um ponteiro é de 4 bytes, então agora eu tenho literalmente dobrou
a quantidade de memória que eu preciso apenas para armazenar esta lista.
Mas, novamente, esta é uma troca constante em ciência da computação
entre tempo e espaço e esforço de desenvolvimento, e outros recursos.
O que é outra desvantagem de usar uma lista ligada? Sim?
[Responder Estudante, ininteligível]
Bom. Não é tão fácil de acessar. Nós não podemos mais alavancagem
Semana 0 princípios como dividir e conquistar.
E, mais especificamente, a pesquisa binária. Porque mesmo que nós, seres humanos
pode ver mais ou menos onde a meio da lista é,
o computador só sabe que esta lista ligada começa no endereço chamado primeiro.
E isso é 0x123 ou algo parecido.
E a única maneira que o programa pode encontrar o elemento do meio
é realmente procurar a lista inteira.
E mesmo assim, ele literalmente tem que pesquisar a lista inteira porque
mesmo quando chegar o elemento do meio, seguindo os ponteiros,
você, o programa, não tem idéia de quanto tempo essa lista é, potencialmente,
até chegar ao final do mesmo, e como você sabe de programação
que está no final de uma lista ligada?
Há um ponteiro especial NULL, portanto, novamente, uma convenção.
Em vez de usar esse ponteiro, nós definitivamente não queremos que seja algum valor lixo
apontando para fora do palco em algum lugar, nós queremos que seja mão para baixo, NULL,
de modo que temos este terminal nesta estrutura de dados para sabermos onde ela termina.
>> O que se quer manipular isso?
Fizemos a maior parte deste visualmente, e com os seres humanos,
mas o que se quer fazer uma inserção?
Assim, a lista original era de 9, 17, 20, 22, 29, 34.
E se nós então queria espaço malloc para o número 55, um nó para ele,
e então nós queremos inserir 55 na lista, assim como fizemos na segunda-feira?
Como podemos fazer isso? Bem, Anita veio e ela caminhou essencialmente da lista.
Ela começou no primeiro elemento, então o próximo, o próximo, o outro, o próximo, o próximo.
Finalmente atingiu a mão esquerda todo o caminho
e percebi oh, isso é NULL. Então, o que a manipulação de ponteiros precisava ser feito?
A pessoa que estava no fim, número 34, precisava de sua mão esquerda levantada
para apontar para 55, 55 precisavam de seu braço esquerdo apontando para baixo para ser o novo terminador nulo. Concluído.
Muito fácil de inserir em uma lista de 55 classificados.
E como isso pode olhar?
>> Deixe-me ir em frente e abrir algum exemplo de código aqui.
Vou abrir o gedit, e deixe-me abrir dois arquivos primeiro.
Um é list1.h, e deixe-me lembrar que este foi o pedaço de código
que usamos para representar um nó.
Um nó tem tanto um int chamado n e um ponteiro chamado em seguida que apenas pontos para a próxima coisa na lista.
Que agora está em um arquivo h.. Por quê?
Há essa convenção, e não temos aproveitado este uma enorme quantidade de nós mesmos,
mas a pessoa que escreveu funções printf e outros
deu como um presente para o mundo todas essas funções por escrever um arquivo chamado stdio.h.
E depois há string.h, e então há map.h, e há todos esses arquivos h
que você pode ter visto ou usado durante o prazo escritos por outras pessoas.
Normalmente nos. Arquivos h são apenas coisas como typedefs
ou declarações de tipos personalizados ou declarações de constantes.
Você não colocar implementações funções 'em arquivos de cabeçalho.
Você coloca, em vez disso, apenas os seus protótipos.
Você coloca as coisas que você deseja compartilhar com o mundo o que eles precisam
para compilar o seu código. Então, só para chegar a este hábito,
decidimos fazer a mesma coisa. Não há muito em list1.h,
mas nós colocamos algo que pode ser do interesse de pessoas no mundo
que querem usar a nossa implementação lista encadeada.
Agora, em list1.c, eu não vou passar por essa coisa toda
porque é um pouco longo, este programa, mas vamos executá-lo real rapidamente no prompt.
Deixe-me compilar list1, deixe-me em seguida, executar list1, eo que você vai ver é
temos um programa de simulação simples pouco aqui
que vai me permite adicionar e remover números a uma lista.
Então deixe-me ir em frente e digite 3 para a 3 opção de menu.
Quero inserir o número - vamos fazer o primeiro número, que foi de 9,
e agora eu sou informado a lista é agora 9.
Deixe-me ir em frente e fazer outra inserção, então eu bati opção de menu 3.
Qual o número que eu quero inserir? 17.
Enter. E eu vou fazer só mais um.
Deixe-me inserir o número 22.
Portanto, temos o início da lista encadeada que tínhamos em forma de slides um momento atrás.
Como é que esta inserção realmente acontecendo?
De facto, 22 é agora no fim da lista.
Assim, a história que contou no palco na segunda-feira e só agora recapitulou
deve realmente estar acontecendo no código.
Vamos dar uma olhada. Deixe-me rolar neste arquivo.
Nós vamos passar por cima algumas das funções,
mas nós vamos descer para, digamos, a função de inserção.
>> Vamos ver como nós vamos sobre a inserção de um novo nó para esta lista ligada.
Onde está a lista declarada? Bem, vamos percorrer todo o caminho até ao topo,
e perceber que a minha lista ligada essencialmente declarado como um ponteiro único que é inicialmente NULL.
Então, eu estou usando uma variável global aqui, que em geral temos pregado contra
porque faz com que o seu código um pouco confuso para manter,
é uma espécie de preguiça, normalmente, mas não é preguiçoso e não é errado e não é ruim
se o propósito único de seu programa na vida é para simular uma lista ligada.
Que é exatamente o que estamos fazendo.
Então ao invés de declarar isso em principal e depois ter de passá-lo para cada função
temos escrito neste programa, em vez perceber oh, vamos torná-lo global
porque todo o propósito deste programa é demonstrar uma e apenas uma lista ligada.
Então, que se sente bem. Aqui estão os meus protótipos, e não vamos passar por tudo isso,
mas eu escrevi uma função de exclusão, uma função de encontrar, uma função de inserção, e uma função de travessia.
Mas vamos agora voltar-se para a função de inserção
e ver como este funciona aqui.
Inserção é on line - aqui vamos nós.
Inserir. Então, não é preciso nenhum argumento, porque nós vamos pedir
o interior usuário desta função para o número que deseja inserir.
Mas, primeiro, nos preparamos para dar-lhes um pouco de espaço.
Esta é uma espécie de copiar e colar do outro exemplo.
Nesse caso, fomos atribuição de um int, desta vez estamos alocando um nó.
Eu realmente não me lembro quantos bytes um nó é, mas isso é bom.
Sizeof pode descobrir isso para mim.
E por que estou verificando NULL na linha 120?
O que poderia dar errado na linha 119? Sim?
[Responder Estudante, ininteligível]
Bom. Só poderia ser o caso que eu pedi muita memória
ou algo está errado eo sistema operacional não tem bytes suficiente para me dar,
por isso sinaliza tanto por retornar nulo, e se eu não verificar que
e eu apenas cega continuar a usar o endereço retornado, pode ser NULL.
Poderia ser algum valor desconhecido, não é uma boa coisa a menos que eu -
na verdade, não será um valor desconhecido. Pode ser NULL, então eu não quero
a abusar dela e arriscar dereferencing-lo.
Se isso acontecer, eu só voltar e vamos fingir que eu não voltar qualquer memória de todos.
>> Caso contrário, eu digo o usuário me dar um número para inserir, eu chamo a nossa GetInt velho amigo,
e então esta foi a nova sintaxe que introduziu na segunda-feira.
'Newptr-> n' significa ter o endereço que lhe foi fornecido por malloc
que representa o primeiro byte de um objecto novo nó,
e depois ir para o campo chamado n.
Uma questão pouco trivial: Este é equivalente ao que linha mais enigmática do código?
Como poderia eu ter escrito isso? Quer dar uma facada?
[Responder Estudante, ininteligível]
Bom. Usando o n., Mas não é tão simples como isso.
O que eu primeiro preciso fazer? [Responder Estudante, ininteligível]
Bom. Eu preciso fazer newptr.n *.
Portanto, este novo ponteiro está dizendo é, obviamente, um endereço. Por quê?
Porque ele foi devolvido por malloc. O newptr * dizendo "vá lá",
e, em seguida, uma vez que você estiver lá, então você pode usar o mais familiar. n,
mas isso só parece um pouco feio, especialmente se nós, seres humanos vão
desenhar os ponteiros com as setas todo o tempo, o mundo tem padronizado nesta notação de seta,
que faz exatamente a mesma coisa.
Assim, você só usar o - notação> quando a coisa da esquerda é um ponteiro.
Caso contrário, se é uma estrutura real, use o n..
E depois este: Por que eu inicializar newptr-> ao lado nulo?
Nós não queremos uma mão pendurada esquerda fora da final da etapa.
Queremos que ele apontando diretamente para baixo, o que significa o fim desta lista
poderia ser neste nó, então é melhor ter certeza que é NULL.
E, em geral, inicializar suas variáveis ​​ou membros de dados e estruturas
a algo é apenas uma boa prática.
Apenas deixar lixo existem e continuarão a existir, geralmente você fica em apuros
se você se esquecer de fazer alguma coisa mais tarde.
>> Aqui está alguns casos. Isso, novamente, é a função de inserção,
ea primeira coisa que eu verificar é se a variável chamada primeiro,
essa variável global é NULL, que significa que não há lista ligada.
Nós não inseriu nenhum número, por isso é trivial para inserir este número atual
na lista, porque apenas pertence no início da lista.
Então, isso foi quando Anita estava em pé aqui sozinho, fingindo
não havia mais ninguém aqui no palco até alocamos um nó,
então ela poderia levantar a mão pela primeira vez,
se todo mundo tivesse vindo no palco depois de sua segunda-feira.
Agora, aqui, este é um cheque pequeno onde eu tenho que dizer se o valor do novo nó de n
é <o valor de n no nó atual primeiro,
isso significa que há uma lista encadeada que começou.
Há pelo menos um nó na lista, mas esse cara nova
pertence, antes disso, por isso temos de mudar as coisas ao redor.
Em outras palavras, se a lista começou com apenas, vamos dizer,
apenas o número 17, que é a - na verdade, o que podemos fazer isso mais claramente.
Se começarmos a nossa história com um ponteiro aqui chamado em primeiro lugar,
e, inicialmente, é nulo, e inserir o número 9,
o número 9 pertence claramente no início da lista.
Então vamos fingir que apenas malloced o endereço ou o número 9 e colocá-lo aqui.
Se o primeiro é de 9 por padrão, o primeiro cenário discutimos apenas significa ponto vamos esse cara aqui,
deixar isso como NULL, agora temos o número 9.
O próximo número que deseja inserir é 17.
17 pertence aqui, então nós vamos ter que fazer alguma revisão lógica por isso.
Então, vamos em vez disso, antes de fazer isso, vamos fingir que queria inserir o número 8.
>> Então, só por conveniência, eu vou desenhar aqui.
Mas lembre-se, malloc pode colocá-lo em qualquer lugar.
Mas, pelo amor de desenho, vou colocá-lo aqui.
Então, fingir que acabou atribuído um nó para o número 8, que é NULL por padrão.
O que tem que acontecer agora? Um par de coisas.
Fizemos esse erro no palco na segunda-feira, onde atualizamos um ponteiro como este,
em seguida, fez isso, e então alegou - nós órfãos todos os outros no palco.
Porque você não pode - a ordem das operações aqui é importante,
porque agora nós perdemos esta 9 nó que é exatamente o tipo de flutuar no espaço.
Portanto, este não era o caminho certo na segunda-feira.
Primeiro temos de fazer outra coisa.
O estado do mundo é assim. Inicialmente, 8 foi alocado.
Qual seria a melhor maneira de inserir 8?
Em vez de atualizar este primeiro ponteiro, apenas atualizar este aqui em seu lugar.
Então, precisamos de uma linha de código que vai virar personagem NULL
em um ponteiro real que está apontando para o nó 9,
e então podemos seguramente mudar primeiro a apontar para esse cara aqui.
Agora temos uma lista, uma lista ligada, de dois elementos.
E o que isso realmente parecido com aqui?
Se olharmos para o código, observe que eu fiz exatamente isso.
Eu já disse newptr, e nesta história, newptr estava apontando para esse cara.
>> Então deixe-me tirar mais uma coisa, e eu deveria ter deixado quarto um pouco mais por isso.
Então, perdoe o desenho pequeno.
Esse cara é chamado newptr.
Essa é a variável que declarou algumas linhas antes, em linha - só acima de 25.
E está apontando para 8. Portanto, quando digo newptr-> seguinte, o que significa ir para a estrutura
que está sendo apontado por newptr, então aqui estamos nós, vá lá.
Em seguida, a seta está dizendo obter o próximo campo, e então a = está dizendo colocar o valor lá?
O valor que estava em primeiro, qual o valor que estava em primeiro lugar?
Primeiro foi apontando para esse nó, o que significa que este deve agora apontar para este nó.
Em outras palavras, o que parece ainda uma bagunça ridículo com a minha letra,
o que é uma idéia simples de apenas mover essas setas ao redor
traduz em código com apenas forro este.
Armazenar o que está em primeiro no campo ao lado e então atualizar o primeiro realmente é.
Vamos em frente e avançar rapidamente um pouco disso,
e olhar apenas para essa inserção da cauda para agora.
Suponha que eu chegar ao ponto em que eu achar que o próximo campo de algum nó é NULL.
E neste ponto da história, um detalhe que eu estou passando por cima
é que eu introduzi outro ponteiro-se aqui na linha 142, ponteiro antecessor.
Essencialmente, neste ponto da história, uma vez que a lista é longa,
Eu meio que preciso andar com dois dedos, porque se eu for muito longe,
lembre-se em uma única lista de comprimento, você não pode ir para trás.
Então essa idéia de predptr é o meu dedo para a esquerda, e newptr - não newptr.
Outro indicador que está aqui é o meu outro dedo, e eu sou apenas um tipo de andar a lista.
É por isso que existe. Mas vamos considerar apenas um dos casos mais simples aqui.
Se o campo seguinte que ponteiro é NULL, o que é a implicação lógica?
Se você está atravessando esta lista e você bater um ponteiro NULL?
Você está no fim da lista, e assim o código para então acrescentar este elemento adicional
é uma espécie de intuitiva terá que nó cuja próxima ponteiro é NULL,
por isso este é atualmente NULL, e alterá-lo, embora, para ser o endereço do novo nó.
Então, estamos apenas desenhando no código da seta que traçamos no palco, levantando a mão esquerda de alguém.
>> E o caso que eu vou acenar as mãos menos por enquanto,
só porque eu acho que é fácil se perder quando o fazemos neste tipo de ambiente,
é a verificação de inserção no meio da lista.
Mas apenas de forma intuitiva, o que deve acontecer se você quiser descobrir
onde um número pertence no meio é que você tem que caminhar
com mais de um dedo, mais de um ponteiro,
descobrir onde ele pertence, a verificação é o elemento <o atual,
> O atual, e uma vez que você encontrar esse lugar,
então você tem que fazer esse tipo de jogo de conchas onde você move os ponteiros em torno de muito cuidado.
E essa resposta, se você gostaria de razão por este em casa no seu próprio país,
se resume apenas a essas duas linhas de código, mas a ordem das linhas é super importante.
Porque se você soltar a mão de alguém e levantar outra pessoa na ordem errada,
novamente, você pode acabar orfandade da lista.
Para resumir mais conceitualmente, a inserção na cauda é relativamente simples.
A inserção na cabeça também é relativamente simples,
mas você precisa atualizar um ponteiro adicional neste momento
para espremer o número 5 na lista aqui,
e, em seguida, a inserção no meio envolve um esforço ainda maior,
para inserir cuidadosamente o número 20 na sua posição correcta,
que é entre 17 e 22.
Então, você precisa fazer algo como ter o novo nó de ponto de 20 a 22,
e, em seguida, o ponteiro que nó precisa ser atualizado passado?
É 17, de realmente inseri-lo.
Então, novamente, eu vou adiar o código real para que a implementação particular.
>> À primeira vista, é um pouco assustador, mas é realmente apenas um ciclo infinito
que é looping, looping, looping, looping, e quebrando assim que bateu o ponteiro NULL,
em que ponto você pode fazer a inserção necessária.
Este, então, é o código de inserção representante lista ligada.
Que era uma espécie de um lote, e parece que nós resolvemos um problema,
mas nós introduzimos um totalmente diferente. Francamente, nós passamos todo esse tempo
em grande O e Ω e correndo o tempo, tentando resolver problemas mais rapidamente,
e aqui estamos dando um grande passo para trás, ele se sente.
E, no entanto, se o objetivo é armazenar dados,
parece que o Santo Graal, como dissemos na segunda-feira, seria realmente
para guardar coisas instantaneamente.
>> Na verdade, acho que fizemos colocar lista de lado ligado por um momento
e nós, em vez introduziu a noção de uma mesa.
E vamos pensar em uma mesa por um momento como uma matriz.
Esta matriz e neste caso aqui tem cerca de 26 elementos, de 0 a 25,
e suponha que você precisava de algum pedaço de armazenamento de nomes:
Alice e Bob e Charlie e similares.
E você precisa de alguma estrutura de dados para armazenar esses nomes.
Bem, você poderia usar algo como uma lista ligada
e você pode percorrer a lista de inserir Alice antes de Bob e Charlie depois de Bob e assim por diante.
E, de fato, se você quiser ver o código assim como um aparte,
sei que em list2.h, fazemos exatamente isso.
Nós não vai passar por esse código, mas esta é uma variante do primeiro exemplo
que introduz uma outra struct que já vimos antes estudante chamado,
e então o que realmente armazena na lista vinculada é um ponteiro para uma estrutura de estudante
em vez de inteiro um pouco simples, n.
Então, percebo que há código lá que envolve cordas reais,
Mas se o objetivo em mãos realmente agora é resolver o problema da eficiência,
Não seria bom se nós estamos dando um objeto chamado Alice,
queremos colocá-la no local certo, em uma estrutura de dados,
parece que seria muito bom para apenas colocar Alice,
cujo nome começa com A, no primeiro local.
E Bob, cujo nome começa com B, na segunda posição.
Com uma matriz, ou vamos começar chamando-o de uma tabela, uma tabela hash em que,
nós podemos fazer exatamente isso. Se nos é dado um nome como Alice,
uma seqüência como Alice, onde você põe A-l-i-c-e?
Precisamos de um hueristic. Precisamos de uma função para tirar alguma entrada como Alice
e retornar uma resposta, "Alice Coloque neste local."
E esta função, esta caixa preta, vai ser chamado de função hash.
>> Uma função hash é algo que tem uma entrada, como "Alice",
e volta para você, normalmente, a localização numérica em alguma estrutura de dados onde Alice pertence.
Neste caso, a função hash deve ser relativamente simples.
Nossa função hash deve dizer, se você está dado "Alice", que a personagem deveria me importar com?
O primeiro. Então eu olho para [0], e então eu digo se [0] o caráter é A, retornar o número 0.
Se for B, retornar 1. Se é C, o retorno 2, e assim por diante.
Todos índice 0, e que me permita inserir Alice e Bob e Charlie e assim por diante
para essa estrutura de dados. Mas há um problema.
O que se Anita vem de novo?
Onde colocamos Anita? Seu nome também começa com a letra A,
e parece que fizemos uma confusão ainda maior do problema.
Nós temos agora a inserção imediata, inserção constante de tempo, para uma estrutura de dados
em vez de pior caso linear,
mas o que podemos fazer com Anita neste caso?
Quais são as duas opções, realmente? Sim?
[Responder Estudante, ininteligível] Ok, então nós poderíamos ter outra dimensão.
Isso é bom. Assim, podemos construir coisas em 3D como falamos verbalmente na segunda-feira.
Poderíamos acrescentar um outro acesso aqui, mas acho que não, eu estou tentando manter isso simples.
O objetivo geral aqui é ter acesso constante de tempo imediato,
de modo que é a adição de muita complexidade.
Quais são as outras opções ao tentar inserir Anita para esta estrutura de dados? Sim?
[Responder Estudante, ininteligível] Boa. Então, nós poderíamos passar todo mundo para baixo,
como Charlie cutuca baixo Bob e Alice, e então colocamos Anita onde ela realmente quer ser.
>> É claro que, agora, há um efeito colateral dessa.
Esta estrutura de dados é provavelmente útil não porque queremos inserir as pessoas uma vez
mas porque queremos verificar se eles estão lá mais tarde
se queremos imprimir todos os nomes na estrutura de dados.
Nós vamos fazer alguma coisa com esses dados, eventualmente.
Então agora nós meio que parafusado sobre Alice, que não é mais onde ela deveria estar.
Nem é Bob, nem é Charlie.
Então talvez isso não é uma boa idéia.
Mas, na verdade, esta é uma opção. Nós poderíamos mudar todos para baixo,
ou diabos, Anita chegou atrasado para o jogo, por que não vamos apenas colocar Anita
aqui não, aqui não, aqui não, vamos colocá-la um pouco mais abaixo na lista.
Mas, então, este problema começa a devolver novamente.
Você pode ser capaz de encontrar Alice instantaneamente, com base em seu primeiro nome.
E Bob instantaneamente, e Charlie. Mas então você olha para Anita,
e você vê, hein, Alice está no caminho.
Bem, deixe-me ver abaixo Alice. Bob não é Anita.
Charlie não é Anita. Oh, há Anita.
E se você continuar nesse trem da lógica toda a maneira,
o que é o tempo de execução do pior caso de encontrar ou inserção de Anita para esta nova estrutura de dados?
É O (n), certo?
Porque, na pior das hipóteses, há Alice, Bob, Charlie. . .
todo o caminho para alguém chamado "Y", por isso há apenas um ponto à esquerda.
Felizmente, não temos um chamado de "Z", então colocamos Anita na parte inferior.
>> Nós realmente não resolveu o problema.
Então talvez nós precisamos introduzir esta terceira dimensão.
E não é que, se nós não introduzir esta terceira dimensão,
nós não podemos fazer isso perfeitamente, mas o Santo Graal vai estar recebendo
constante de tempo de inserção e dinâmicos de modo a que as inserções
não temos a hard-código uma matriz de tamanho 26.
Podemos inserir tantos nomes como queremos, mas vamos dar o nosso intervalo de 5 minutos aqui
e depois fazer isso corretamente.
Tudo bem. Eu defini a história até muito artificialmente há
escolhendo Alice e Bob e Charlie e Anita,
cujo nome foi, obviamente, vai colidir com Alice.
Mas a pergunta que terminou na segunda-feira com é apenas quão provável é
que você deseja obter esses tipos de colisões? Em outras palavras,
se começarmos a usar essa estrutura de tabela, que é realmente apenas uma matriz,
neste caso, de 26 posições,
E se nossos insumos são distribuídos uniformemente em vez?
Não é artificialmente Alice e Bob e Charlie e David e assim por diante em ordem alfabética,
é uniformemente distribuída ao longo de A a Z.
>> Talvez nós vamos ter sorte e nós não vamos ter dois Um ou dois de B
com probabilidade muito alta, mas como alguém apontou,
se este problema generalizado e não 0-25
mas, digamos, de 0 a 364 ou 65, muitas vezes, o número de dias em um ano típico,
e fez a pergunta: "Qual é a probabilidade de que dois de nós nesta sala tem a mesma data de aniversário?"
Dito de outra forma, qual é a probabilidade de que dois de nós tem um nome que começa com A?
O tipo de pergunta é a mesma, mas este espaço de endereços,
este espaço de busca, é maior no caso de aniversários,
porque temos tantos dias a mais no ano do que letras no alfabeto.
Qual é a probabilidade de uma colisão?
Bem, podemos pensar nisso por descobrir a matemática de forma oposta.
Qual é a probabilidade de colisões não?
Bem, essa expressão aqui diz que o que é a probabilidade
se há apenas uma pessoa neste quarto, que tem um aniversário?
É 100%. Porque se há apenas uma pessoa na sala,
seu aniversário pode ser qualquer um dos 365 dias fora do ano.
Logo, as opções 365/365 me dá um valor de 1.
Assim, a probabilidade em questão no momento é apenas 1.
Mas se há uma segunda pessoa no quarto,
qual é a probabilidade de que seu aniversário é diferente?
Há apenas 364 dias possíveis, anos bissextos, ignorando
para seu aniversário para não colidir com as outras pessoas.
Assim, 364/365. Se uma terceira pessoa entra, é 363/365, e assim por diante.
Assim, continuam se multiplicando junto destas frações, que estão ficando cada vez menores,
para descobrir qual é a probabilidade de que todos nós temos aniversários originais?
Mas, então, nós podemos, é claro, basta ter essa resposta e lançá-lo em torno de
e fazer 1 menos de tudo isso, uma expressão que vai finalmente chegar
se você se lembra a parte de trás de seus livros de matemática, que parece um pouco algo como isto,
que é muito mais facilmente interpretada graficamente.
E este gráfico aqui tem no eixo x o número de aniversários,
ou o número de pessoas com aniversários, e no eixo y é a probabilidade de uma partida.
E o que isso está dizendo é que se você tem, digamos, até mesmo,
vamos escolher algo como 22, 23.
Se há 22 ou 23 pessoas na sala,
a probabilidade de que duas dessas poucas pessoas vão ter o mesmo aniversário
é realmente super alta, combinatoriamente.
50% as probabilidades de que em uma classe de apenas 22 pessoas, de um seminário, praticamente,
2 de essas pessoas vão ter o mesmo aniversário.
Porque há muitas maneiras em que você pode ter o mesmo aniversário.
Pior ainda, se você olhar para o lado direito do gráfico,
no momento em que você tem uma classe com 58 alunos em que,
a probabilidade de duas pessoas que tenham um aniversário é alta, super super, cerca de 100%.
Agora, isso é uma espécie de fato divertido sobre a vida real.
>> Mas as implicações, agora, para estruturas de dados e armazenamento de informações
significa que apenas supondo que você tem um bom, distribuição, limpa e uniforme de dados
e você tem uma matriz grande o suficiente para caber um monte de coisas
não significa que você está indo para obter as pessoas em locais exclusivos.
Você vai ter colisões. Portanto, esta noção de hash, como é chamado,
tomando uma entrada como "Alice" e massageando-o de alguma forma
e depois voltar uma resposta como 0 ou 1 ou 2.
Voltando alguma saída dessa função é atormentado por essa probabilidade de colisão.
Então, como podemos lidar com essas colisões?
Bem, em um caso, podemos ter a idéia de que foi sugerido.
Nós podemos apenas mudar todos para baixo, ou talvez, um pouco mais simples,
em vez de todos os outros movimento, vamos mover Anita para o fundo do local disponível.
Então, se Alice está em 0, Bob está em 1, Charlie está em 2,
vamos colocar Anita na localização 3.
E esta é uma técnica em estruturas de dados chamado linear sondagem.
Linear porque você está apenas caminhando nessa linha, e você é uma espécie de sondagem
para os locais disponíveis na estrutura de dados.
Naturalmente, este transforma em O (n).
Se a estrutura de dados é realmente completo, há 25 pessoas que já,
e Anita vem, ela acaba com o que seria localização Z, e isso é bom.
Ela ainda se encaixa, e podemos encontrá-la mais tarde.
>> Mas isso era contrário ao objetivo de acelerar as coisas.
Então, o que se criou, essa terceira dimensão?
Essa técnica é geralmente chamado encadeamento separado, ou que possuam cadeias.
E o que uma tabela hash é agora, esta estrutura tabular,
sua tabela é apenas uma matriz de ponteiros.
Mas o que os ponteiros apontam para adivinhar o que é?
Uma lista ligada. Então, o que se tirar o melhor de ambos os mundos?
Usamos matrizes para os índices iniciais
na estrutura de dados, de modo que pode imediatamente ir para [0] [1], [30], ou assim por diante,
mas para que possamos ter alguma flexibilidade e podemos encaixar Anita e Alice e Adam
e qualquer nome de um outro,
nós mas deixar que o outro eixo crescer de forma arbitrária.
E finalmente, a partir de segunda-feira, tem essa capacidade expressiva com lista encadeada.
Podemos crescer uma estrutura de dados de forma arbitrária.
Alternativamente, podemos apenas fazer uma matriz de 2 dimensões enormes,
mas que vai ser uma situação terrível se uma das linhas de uma matriz de 2 dimensões
não é suficientemente grande para a pessoa cujo nome adicional acontece a começar com A.
Deus nos livre de ter que realocar uma estrutura 2-dimensional enorme
apenas porque há tantas pessoas denominados A,
especialmente quando há tão poucas pessoas nomeadas algo Z.
Ele só vai ser uma muito escassa estrutura de dados.
Portanto, não é perfeito, por qualquer meio, mas agora pelo menos temos a capacidade
Para encontrar onde Alice ou Anita pertence,
pelo menos em termos do eixo vertical,
e depois só temos de decidir onde colocar Anita ou Alice nesta lista ligada.
Se nós não nos importamos com classificando as coisas, com que rapidez podemos inserir Alice em uma estrutura como esta?
É tempo constante. Nós índice para [0], e se não houver ninguém,
Alice vai no início dessa lista ligada.
Mas isso não é um grande negócio. Porque se Anita então vem
um número de passos depois, onde é que Anita pertence?
Bem, [0]. POO. Alice já está na lista ligada.
>> Mas, se não se importam com a classificação desses nomes,
podemos apenas passar mais de Alice, inserção Anita, mas mesmo isso é tempo constante.
Mesmo se houver Alice e Adão e todos esses outros nomes A,
ele não está realmente mudando-los fisicamente. Por quê?
Porque nós fizemos aqui com lista encadeada, quem sabe se esses nós são afinal?
Tudo que você tem a fazer é mover as migalhas de pão.
Mova as setas ao redor, você não tem que mover fisicamente todos os dados ao redor.
Assim, podemos inserir Anita, nesse caso, instantaneamente. Tempo constante.
Portanto, temos de tempo constante de pesquisa e de tempo constante inserção de alguém como Anita.
Mas tipo de simplificar o mundo.
O que se mais tarde quiser encontrar Alice?
Quantos passos é que vai levar?
[Responder Estudante, ininteligível]
Exatamente. O número de pessoas antes de Alice na lista ligada.
Portanto, não é perfeita, porque a nossa estrutura de dados, mais uma vez, tem este acesso vertical
e então ele tem essas listas ligadas de suspensão - na verdade, não vamos desenhar uma matriz.
Tem essas listas ligadas pendurado fora dele que se parece um pouco algo como isto.
Mas o problema é se Alice e Adão e todos esses outros nomes A
acabar mais e mais para lá,
encontrar alguém pode acabar levando um monte de etapas,
bcause você tem que atravessar a lista ligada,
que é uma operação linear.
Então, realmente, em seguida, o tempo de inserção, em última análise é O (n), onde n é o número de elementos na lista.
Dividido por, vamos chamá-lo arbitrariamente m, onde m é o número de listas ligadas
que temos neste eixo vertical.
Em outras palavras, se realmente assumir uma distribuição uniforme de nomes,
totalmente irrealista. Há, obviamente, mais de algumas letras do que outros.
>> Mas se nós assumimos para o momento de uma distribuição uniforme,
e temos n total de pessoas, e m correntes totais
à nossa disposição, em seguida, o comprimento de cada uma destas cadeias
forma muito simples, vai ser o total, n, dividido pelo número de correntes.
Assim, n / m. Mas aqui é onde podemos ser tudo matematicamente inteligente.
m é uma constante, porque não há um número fixo de estes.
Você está indo para declarar a matriz no início,
e não estamos redimensionando o eixo vertical. Por definição, que permanece fixo.
É apenas o eixo horizontal, por assim dizer, isso está mudando.
Então, tecnicamente, é uma constante. Então, agora, o tempo de inserção
é muito bonito O (n).
De modo que não se sente tudo o que muito melhor.
Mas o que há de verdade nisso? Bem, todo esse tempo, por semanas,
estamos dizendo O (n ²). O (n), 2 x n ², - n, dividido por 2. . . ech.
É apenas ² n. Mas agora, nesta parte do semestre,
podemos começar a falar sobre o mundo real novamente.
E n / m é absolutamente mais rápido do que apenas n sozinha.
Se você tem mil nomes, e dividi-las em vários baldes
para que você tenha apenas 10 nomes em cada uma dessas cadeias,
absolutamente buscar 10 coisas vai ser mais rápido do que mil coisas.
E assim um dos conjuntos de problemas futuros vai desafiá-lo
para pensar sobre exatamente que, apesar de, sim,
assintoticamente e matematicamente, isso ainda é apenas linear,
que suga, em geral, ao tentar encontrar as coisas.
Na realidade, o que vai ser mais rápido do que
devido a este divisor.
E assim, lá está de novo vai ser este trade-off
e este conflito entre a teoria ea realidade,
e um dos botões vai começar a girar neste ponto no semestre
é mais a realidade como um tipo de preparar para o final de semster,
como vamos introduzir no mundo da programação web,
onde realmente, o desempenho vai contar porque seus usuários estão indo para
começar a sentir e apreciar as decisões de design pobre.
>> Então, como você vai fazer sobre a implementação de um ligado - uma tabela hash com 31 elementos?
E o exemplo anterior foi arbitrariamente sobre aniversários.
Se alguém tem um aniversário de 01 de janeiro ou 01 de fevereiro, vamos colocá-los neste balde.
Se é 02 de janeiro, 02 de fevereiro, 2 de março, nós vamos colocá-los neste balde.
É por isso que foi de 31. Como você declarar uma tabela hash?
Ele pode ser bastante simples, mesa * nó é o meu nome arbitrário para ele, [31].
Isso me dá 31 dicas para nós,
e que me permite ter 31 ponteiros para listas ligadas
mesmo que essas correntes são inicialmente NULL.
O que eu quero colocar, se eu quiser armazenar "Alice", "Bob", "Charlie"?
Bem, é preciso envolver essas coisas em uma estrutura
porque precisamos de Alice para apontar para Bob, para apontar para Charlie, e assim por diante.
Nós não podemos apenas ter os nomes só, então eu poderia criar uma nova estrutura chamada nó aqui.
>> O que é um nó real? O que é um nó nesta nova lista ligada?
O primeiro, chamado palavra, é para o nome da pessoa.
COMPRIMENTO, presumivelmente, refere-se ao comprimento máximo do nome de um ser humano,
seja o que for, 20, 30, 40 personagens em casos de canto louco,
e um é para o que? É apenas o caractere NULL extra, \ 0.
Portanto, este nó é embrulho "algo" dentro de si,
mas também declara um ponteiro chamado próxima
para que possamos cadeia de Alice para Bob para Charlie e assim por diante.
Pode ser NULL, mas não necessariamente tem que ser.
Qualquer dúvida sobre estas tabelas de hash? Sim?
[Estudante pedindo questão, ininteligível] Uma matriz - boa pergunta.
Porque é que esta palavra char em uma matriz em vez de apenas char *?
Neste exemplo um tanto arbitrária, eu não queria ter que recorrer
para malloc para cada um dos nomes originais.
Eu queria declarar uma quantidade máxima de memória para a cadeia
para que eu pudesse copiar para a estrutura de Alice \ 0 e não ter de lidar com malloc e free e similares.
Mas eu poderia fazer isso se eu queria ser mais consciente do uso do espaço. Boa pergunta.
Então, vamos tentar generalizar longe deste
e focar o restante de hoje em estruturas de dados mais geral
e outros problemas que podemos resolver usando os mesmos fundamentos
mesmo que as estruturas de dados elas mesmas podem diferir nos seus pormenores.
>> Assim, verifica-se em ciência da computação, as árvores são muito comuns.
E você pode pensar em uma espécie de árvore como uma árvore genealógica,
onde há algumas raízes, alguns matriarca ou patriarca,
avô ou avó ou mais cedo de volta,
sob o qual estão a mãe eo pai ou irmãos diversas ou similares.
Assim, uma estrutura de árvore tem nós e tem filhos,
geralmente 0 ou mais crianças para cada nó.
E alguns dos jargões que você vê nesta foto aqui
é qualquer uma das crianças pequenas ou netos nas bordas
que não têm setas que emanam a partir deles,
essas são as folhas chamados, e qualquer pessoa no interior
é um nó interno, você pode chamá-lo de qualquer coisa nesse sentido.
Mas essa estrutura é muito comum. Este aqui é um pouco arbitrária.
Nós temos um filho à esquerda, temos três filhos, à direita,
duas crianças no canto inferior esquerdo.
Assim podemos ter diferentes tamanhos de árvores, mas se começarmos a padronizar as coisas,
e você pode chamar este de vídeo Patrick em busca binária de um curta anterior
pesquisa, online binário não tem que ser implementado com uma matriz
ou pedaços de papel em um quadro negro.
Suponha que você queria para armazenar seus números em uma estrutura de dados mais sofisticados.
Você poderia criar uma árvore como esta.
Pode ter um nó declarado em C, e que o nó pode ter, pelo menos, dois elementos no interior do mesmo.
Um deles é o número que deseja armazenar, eo outro é - bem, nós precisamos de mais um.
A outra é seus filhos.
Então, aqui está uma outra estrutura de dados. Desta vez, o nó é definido como o armazenamento de um número n
e, em seguida, dois ponteiros, criança esquerdo e direito da criança.
E eles não são arbitrárias. O que é interessante sobre esta árvore?
>> Qual é o padrão na forma como temos colocado isso ou como Patrick colocou-o em seu vídeo?
É meio óbvio que há alguma ordenação acontecendo aqui,
mas o que é a regra simples? Sim?
[Responder Estudante, ininteligível]
Perfeito. Se você olhar para isso, você vê os números pequenos de esquerda,
grandes números do lado esquerdo, mas isso é verdade para cada nó.
Para cada nó, o seu filho esquerdo inferior, e a sua criança direita maior do que.
O que isto significa que agora é que se eu quiser procurar esta estrutura de dados para, por exemplo, o número 44,
Eu tenho que começar na raiz, porque, como com todas essas estruturas mais complexas de dados, agora,
temos apenas um ponteiro para uma coisa, o início.
E, neste caso, o início é a raiz. Não é o lado esquerdo,
é a raiz desta estrutura. Então eu vejo aqui é 55, e eu estou procurando 44.
Qual direção que eu quero ir?
Bem, eu quero ir para a esquerda, porque, obviamente, para a direita vai ser muito grande.
Então, observe aqui, você é uma espécie de conceitualmente cortar a árvore em meia
porque você nunca está indo para o lado direito.
Então agora eu ir do 55 ao 33. É muito pequeno de um número.
Estou à procura de 44, mas agora eu sei, se 44 é nesta árvore, eu posso ir, obviamente, para a direita.
Então, novamente, eu sou a poda da árvore no meio.
É praticamente idêntico conceitualmente para o livro de telefone.
É idêntico ao que fizemos com os papéis no quadro negro,
mas é uma estrutura mais sofisticada, que nos permite realmente fazer
este dividir e conquistar, pelo design do algoritmo,
e, de fato, atravessando uma estrutura como esta - gritos.
Atravessando uma estrutura como esta, onde é apenas "ir por este caminho ou ir por esse caminho",
significa todo o código que que dobrado sua mente em primeiro lugar quando implementá-lo na seção
ou andar com ele em casa, por busca binária, usando recursão ou iteração,
é uma dor no pescoço. Encontre o elemento do meio, em seguida, fazer o seu arredondamento para cima ou para baixo.
>> Há uma beleza a este, porque agora podemos usar recursão novamente,
mas muito mais limpa. Na verdade, se você está no número 55 e você quer encontrar 44,
você vá para a esquerda, neste caso, então o que você faz? Você corre o algoritmo exato.
Você verifica o valor do nó, então você vá para a esquerda ou direita.
Então você verificar o valor do nó, vá para a esquerda ou direita.
Isto é perfeitamente adequado para a recursividade.
Assim, mesmo que no passado fizemos alguns exemplos bastante arbitrárias que envolvem recursão
que não precisa ser recursiva, com stuctures de dados,
especialmente árvores, é uma perfeita aplicação desta idéia de levar um problema,
reduzindo-a, e em seguida a solução do mesmo tipo de, mas menor do programa.
>> Portanto, há uma outra estrutura de dados que podemos apresentar.
Este é projetada à primeira vista olhar enigmático, mas este é incrível.
Portanto, esta é uma estrutura de dados chamada trie, trie, que é herdado da recuperação de palavra,
que não é pronunciado re-try-val, mas é o que o mundo chama essas coisas. Tenta. T-r-i-e.
É uma estrutura de árvore de algum tipo, mas cada um de nós em um trie
parece ser o que? E isso é um pouco enganoso, porque é uma espécie de abreviado.
Mas parece que cada nó neste trie é na verdade uma matriz.
E mesmo que o autor deste diagrama não tem mostrado que,
neste caso, este trie é uma estrutura de dados cujo propósito na vida é armazenar palavras
como A-l-i-c-e ou B-o-b.
E a maneira pela qual os dados lojas Alice e Bob e Charlie e Anita e assim por diante
é que ele usa uma matriz para armazenar qual Alice em uma trie,
começamos no nó raiz que se parece com uma matriz,
e que ele foi escrito em notação abreviada.
O autor omitido abcdefg porque não havia nomes com isso.
Eles só mostrou M e P e T, mas neste caso,
vamos passar longe de Alice e Bob e Charlie para alguns nomes que estão aqui.
Maxwell é realmente neste diagrama.
Então, como o armazenamento de autor M-a-x-w-e-l-l?
Ele ou ela começou no nó raiz, e foi para [M], de modo mais ou menos 13, o local 13 na matriz.
Então, a partir daí, há um ponteiro.
Um ponteiro levando para outro array.
A partir daí o autor indexados em que a matriz na posição A, como mostrado lá em cima, à esquerda,
e depois que ele ou ela seguiu esse ponteiro para outra matriz,
e foi para o ponteiro no local X.
Em seguida, na próxima localização matriz W, E, L, L, e assim por diante,
e, finalmente, vamos realmente tentar colocar uma imagem para isso.
O que faz um nó como no código?
Um nó em uma trie contém uma matriz de ponteiros para nós mais.
Mas há também tem de haver algum tipo de valor booleano, pelo menos nesta implementação.
Acontece que eu chamá-lo is_word. Por quê?
Porque quando você está inserindo Maxwell, você não está inserindo
nada para esta estrutura de dados.
Você não está escrevendo M. Você não está escrevendo X.
Tudo o que você está fazendo é seguir ponteiros.
O ponteiro que representa M, então o ponteiro que representa A,
em seguida, o ponteiro que representa X, em seguida, W, E, L, L,
mas o que você precisa fazer no final é uma espécie de vão, verificar, cheguei a este local.
Havia uma palavra que termina aqui na estrutura de dados.
>> Então, o que uma trie é realmente cheio e com o autor escolheu para representar
estes terminuses com pequenos triângulos.
Isto apenas significa que o fato de esse triângulo está aqui, este valor booleano verdadeiro
significa que se você ir para trás na árvore,
significa que uma palavra é chamado Maxwell neste.
Mas a palavra foo, por exemplo,
não está na árvore, porque se eu começar no nó raiz aqui em cima,
Não há ponteiro f, nenhum ponteiro o, não o ponteiro. Foo não é um nome neste dicionário.
Mas por outro lado, turação, t-u-r-i-n-g. Mais uma vez, eu não armazenar t ou u ou r ou i ou n ou g.
Mas eu fiz na loja esta estrutura de dados um valor de verdadeiro caminho até aqui neste nó - na árvore
definindo esse valor booleano de is_word a verdade.
Assim, um trie é uma espécie de esta estrutura meta muito interessante,
onde você não está realmente armazenar as próprias palavras para este tipo de dicionário.
Para ser claro, você está apenas armazenando sim ou não, não é uma palavra que termina aqui.
>> Agora, qual é a implicação?
Se você tem 150 mil palavras em um dicionário que você está tentando armazenar na memória
usando algo como uma lista ligada,
você vai ter 150 mil nós em sua lista ligada.
E encontrar uma dessas palavras em ordem alfabética pode levar tempo O (n).
Tempo linear. Mas no caso aqui de uma trie,
o que é o tempo de execução de encontrar uma palavra?
Acontece que a beleza aqui é que mesmo se você tem 149.999 palavras já neste dicionário,
como implementado com esta estrutura de dados,
quanto tempo leva para encontrar ou inserir mais uma pessoa em que, como Alice, Alice?
Bem, é apenas 5, talvez 6 passos para o personagem de fuga.
Porque o presense de outros nomes na estrutura
não ficar no caminho de inserção de Alice.
Além disso, encontrar Alice uma vez que existem 150.000 palavras neste dicionário
não entrar em seu caminho de encontrar Alice em tudo,
porque Alice é. . . . . aqui, porque eu encontrei um valor booleano.
E se não houver booleano verdadeiro, então Alice não está na esta estrutura de dados de palavras.
Em outras palavras, o tempo de execução de encontrar as coisas e inserindo as coisas para este novo
estrutura de dados de trie é O de - não é n.
Porque o presense de 150.000 pessoas não tem efeito sobre Alice, que parece.
Então, vamos chamá-lo de k, onde k é o comprimento máximo de uma palavra em Inglês
que é, tipicamente, não mais do que 20 e poucos caracteres.
Assim, k é uma constante. Assim, o Santo Graal que parecem ter encontrado agora
é o de uma vez, trie constante para pastilhas, para pesquisas, por eliminações.
Como o número de coisas já na estrutura,
que não são nem mesmo fisicamente lá. Mais uma vez, eles estão apenas uma espécie de desmarcado, sim ou não,
não tem impacto no seu tempo futuro em execução.
>> Mas tem de ser um problema, caso contrário, não teria perdido tanto tempo
em todas essas estruturas de dados outros apenas para finalmente chegar ao um segredo que é incrível.
Então, qual o preço que estamos pagando para alcançar essa grandeza aqui? Espaço.
Essa coisa é enorme. E a razão que o autor
não apresentá-lo aqui, notar que todas essas coisas que se parecem com matrizes,
ele não desenhar o restante da árvore, o resto do trie,
porque eles são não apenas relevantes para a história.
Mas todos esses nós são super grande, e cada nó na árvore ocupa
26 ou, na verdade, poderia ser de 27 caracteres, porque neste caso eu estava incluindo espaço para o apóstrofo
para que pudéssemos ter palavras apostrofado.
Neste caso, trata-se matrizes de largura. Assim, mesmo que eles não estão picutured,
isso leva-se uma enorme quantidade de RAM.
O que pode ser bom, especilly em hardware moderno,
mas essa é a troca. Nós temos menos tempo, gastando mais espaço.
Então, onde é que isto tudo vai?
Bem, vamos fazer - vamos ver aqui.
Vamos fazer um salto para esse cara aqui.
>> Acredite ou não, divertido como C tem sido já há algum tempo,
estamos chegando ao ponto em que, no semestre é hora de transição para as coisas mais modernas.
Coisas em um nível superior. E mesmo que para o próximo par de semanas
vamos continuar a mergulhar no mundo de ponteiros e gerenciamento de memória
para obter esse conforto com a qual podemos então construir,
O jogo final é, finalmente, para introduzir, ironicamente, não esta linguagem.
Nós vamos gastar, como 10 minutos falando sobre HTML.
Todo o HTML é uma linguagem de marcação, e que é uma linguagem de marcação é
é esta série de suportes abertos e fechados suportes que dizem "fazer este bold '
"Tornar esta itálico" "fazer esta centrada."
Não é tudo o que intelectualmente interessante, mas é super útil.
E é certamente onipresente nos dias de hoje.
Mas o que é poderoso sobre o mundo do HTML e programação web em geral,
está construindo coisas dinâmicas; escrever código em linguagens como PHP ou Python ou Ruby ou Java ou C #.
Realmente, qualquer que seja o idioma de sua escolha, e gerar HTML dinamicamente.
Gerando uma coisa chamada CSS dinamicamente.
Folhas de estilo em cascata, o que é também sobre a estética.
E por isso mesmo que, hoje, se eu for para algum site como o Google.com familiar,
e vou ver, desenvolvedor, fonte de visão, que talvez você tenha feito antes,
mas vai ver o código fonte, este material provavelmente parece muito enigmática.
Mas este é o código subjacente que implementa Google.com.
Na extremidade dianteira. E, na verdade, tudo isso é coisa de estética fofo.
Este é CSS aqui. Se eu continuar a rolagem para baixo nós vamos pegar algumas coisas com código de cores.
Este é HTML. Código do Google parece uma bagunça, mas se eu realmente abrir uma janela diferente,
podemos ver alguma estrutura para isso.
Se eu abrir isto, observe aqui, é um pouco mais legível.
Nós vamos ver em pouco tempo essa marca, [palavra] é uma tag,
HTML, cabeça, corpo, div, roteiro, área de texto, extensão, centrado, div.
E esta é também classificar de aparência enigmática, à primeira vista,
mas toda esta confusão segue certos padrões, e padrões repetitivos,
de modo que uma vez que temos o básico para baixo, você vai ser capaz de escrever um código como este
e, então, manipular o código como esta usando outra linguagem, chamada de JavaScript.
E JavaScript é uma linguagem que roda dentro de um browser
hoje, que usamos em Harvard cursos, para a ferramenta de compras curso que usa mapas do Google
para dar-lhe um monte de dinamismo, o Facebook dá a você para mostrar atualizações de status instantâneas,
Twitter usa para mostrar o tweets instantaneamente.
Tudo isso, vamos começar a mergulhar dentro
Mas para chegar lá, precisamos entender um pouco sobre a Internet.
Este clip aqui é apenas um minuto de duração, e vamos assumir por agora este é, de fato,
como a Internet funciona como um teaser para o que está por vir. Eu dar-lhe "Guerreiros do líquido."
>> [♫ ♫ música lenta coro]
[Narrador Masculino] Ele veio com uma mensagem.
Com um protocolo de todo seu.
[♫ ♫ música Faster eletrônico]
Ele veio para um mundo de firewalls frias, insensíveis roteadores,
e perigos muito piores do que a morte.
Ele é rápido. Ele é forte. Ele é o TCP / IP, e ele tem o seu endereço.
Guerreiros da rede.
[Malan] Na próxima semana, então. A Internet. Programação web. Este é CS50.
[CS50.TV]