[Powered by Google Translate] [Semana 7] [David J. Malan - Harvard University] [Esta é CS50. - CS50.TV] Tudo bem. Bem-vindo de volta. Este é CS50, e este é o início da semana 7. Um par de pequenos anúncios: Pset5 está em andamento, ou em breve será, e deixe-me dizer, muito sinceramente, este tende a estar entre os mais desafiador de conjuntos do curso de problema, então deixe-me falar isso agora de modo que esta semana mais do que nunca que você não espere até que, digamos, na noite de quarta ou quinta à noite para mergulhar dentro Esta é definitivamente uma pset interessante. Nós pensamos que é divertido. Se você realmente obtê-lo totalmente correta e pode, então, desafiar o Conselho chamados grandes, você vai ter a oportunidade de combinar inteligência com alguns dos funcionários do curso e alguns de seus colegas de classe. O que o Big Board é, é uma vez que você tem o seu trabalho corretor ortográfico, você será capaz de ir para cs50.net após a execução de um comando, puramente optar, em seguida, a quantidade de tempo e a quantidade de RAM e mais que você usou em sua implementação serão expostos aqui na página do curso casa. Você vai perceber que um monte dessas pessoas aqui são listados como equipe desde o fim de semana, a equipe pensou que seria divertido tentar superar uns aos outros. Então percebe que o objetivo aqui não é superar o pessoal. Mesmo que eu só estou aqui, no número 13. Puramente optar, mas é uma oportunidade para ver o quão pouca memória RAM e como alguns segundos de CPU você pode usar vis-a-vis alguns de seus colegas de classe.
E eu vou admitir que Kevin Michael Schmid, actualmente na posição número 1 como um dos TFs, Esta é uma implementação que não chamam possível uma vez que ele está usando quase 0 RAM e quase 0 segundo para o carregamento. Então, vamos cuidar de Kevin desligada. [Risos] Há certas habilidades que Kevin está colocando à prova aqui. Uma das coisas que nós pensamos em fazer também é agora CS50x é uma semana em curso, e vocês são tanto uma parte desse experimento como esses estudantes são. Pedimo-lhes como parte de sua pset0, que foi igualmente a apresentar um projecto Scratch de interesse para eles - um jogo, uma peça interativa de arte, uma animação, ou similar - a 1 - vídeo de dois minutos, se eles gostariam, dizendo Olá para o mundo e que elas realmente são. Eu pensei que eu iria compartilhar com você apenas um par de vídeos que foram apresentados até agora porque para nós, na equipe, pelo menos, ele realmente foi emocionante e inspirador ver essas pessoas de todo o mundo - países de todo o mundo - em sintonia, de todas as coisas, para um curso de ciência da computação na Internet, se é porque eles querem continuar seus estudos, eles querem tomar suas carreiras em uma nova direção, eles querem preencher as lacunas em seu conhecimento, portanto, algumas das mesmas razões que vocês talvez tenham sido aqui.
Então, eu dar-lhe um tal estudante aqui. Você poderia aumentar o volume um pouco. Aqui está um dos nossos alunos de 1 minuto submissões. Olá, mundo. Eu sou um estudante de engenharia industrial aqui em Málaga, Espanha. Estou animado com este curso on-line, porque eu amo a ciência da computação, eu realmente fazer, e eu realmente aprecio que eu começar a explorá-lo. E o fato de que eu possa aprender o mesmo de todos vocês fazem mas, em vez de estar em Harvard estou em Málaga, como impressionante é isso? Bem, eu sou Fernando, e este é o CS50. Vejo vocês. [Risos] Outro clipe que gostamos muito, você vai achar que este cavalheiro Inglês não é tão forte. Parece que ele tinha uma tradução automática, assim que as traduções são um pouco imperfeito, mas este foi um dos nossos favoritos, até agora, também. [♪ ♪] Olá, mundo. [Falando em japonês] [Eu tenho que cumprimentar em japonês, porque o meu Inglês é muito confiável.] [Eu entreguei a mensagem para você da cidade de Gifu, no Japão]. [I pode ser um estudante, pela primeira vez em 20 anos, como pode ser visto.] [Eu sou muito grato a Universidade de Harvard, que me deu esta oportunidade e EDX.] [Golf é um violão e minha coisa favorita em execução.] [Risos] [♪ ♪] [Por que você acha que eu estava tentando assistir a uma cs50x.] [Universidade de Harvard, é o meu desejo.] [Especialmente se eu sou presença distante viveu no Japão]. [Eu queria tentar de imediato conhecimento da existência de tal quando EDX.] [Você não acha que você não relacionado com a idade do aprendizado I.] [CS50 é o meu desejo. Meu nome é Kazu, e este é o CS50.] [♪ ♪] [aplausos e aplausos] Outro favorito de nosso foi esta submissão aqui de alguém. [♪ ♪] [Malan] Google se você não estiver familiarizado com esse meme.
E então, finalmente, um par de outros que foi publicado que, talvez, ganhar o prêmio adorável. [Estudantes] Aww! >> [Malan] Nós vamos ter que ouvir. Esta é curto, para ouvir de perto. [Orador feminino] Qual é o seu nome? >> Louie. [Orador feminino] O que é isso? >> [Risos] CS50. [Risos] [Malan] Ele fez dois takes, no entanto. Aqui vamos nós, a última. Meu nome é Louie, e este é o CS50. [Risos] Isso, então, é CS50x. Obrigado a todos aqueles que ao seguir junto em casa que têm sido, até agora, que participa. Hoje, podemos concluir nossa discussão de estruturas de dados, pelo menos, alguns dos mais fundamental, e depois continuamos nossa conversa sobre HTML e programação web. Na verdade, passamos o passado cerca de sete semanas procurando nos fundamentos da programação - algoritmos, estruturas de dados, e outros semelhantes - e C, como você pode ter experimentado até agora, não é necessariamente o mais acessível de línguas com que a execução de algumas dessas idéias. E assim a partir desta semana e na próxima semana e então o seguinte, vamos finalmente ser capaz de transição a partir de C, a qual é geralmente conhecida como uma língua relativamente baixo nível, para coisas de mais alto nível, entre eles PHP, JavaScript, e similares, que veremos aproveitar as mesmas lições que aprendemos ao longo das últimas semanas, mas você vai descobrir que declarar as coisas como matrizes e tabelas hash e pesquisa e classificação tornar-se muito mais fácil, porque os idiomas próprios vamos começar a usar vai se tornar mais poderoso. Mas, primeiro, um pedido de árvores. É muito comum nos dias de hoje a necessidade de comprimir informações. Em que contexto você quer comprimir algum tipo de informação digital?
Sim. >> [Aluno] Quando você precisa enviá-lo através da Internet. Sim, quando você quer enviar alguma coisa pela web. Se você deseja fazer o download de um arquivo grande, é ideal se alguém do outro lado comprimiu o arquivo usando um formato zip ou algo parecido de modo que você está enviando menos bits do que poderia ser transmitidos. Assim como você comprimir informação? Tudo se resume a usar menos bits do que são exigidos por padrão. Mas este é um tipo de coisa curiosa, porque acha que volta para 0 e 1 semana quando falamos sobre ASCII e binário e nós conversamos sobre ASCII em particular como a utilização de 8 bits para representar as letras do alfabeto de modo que a letra A é representada por 65, minúsculas a é o número 97, e no entanto você representar o 65 ou 97, você está usando 7 ou 8 bits. Mas o problema é que há algumas letras no alfabeto Inglês que não são tão populares quanto os outros. Z não é tudo o que popular, Q não é tudo o que popular, mas A e E são super popular. E ainda para todas estas cartas, por padrão, o mundo usa o mesmo número de bits, de apenas 8. Portanto, não teria sido mais inteligente se, em vez de usar 8 bits para cada letra, mesmo o mais pouco usado como Q e Z, o que se usássemos menos bits para A e E e S e as letras mais populares e usados mais bits para as letras menos populares, a idéia é otimizar vamos para o caso comum, que é um tema em ciência da computação de tentar otimizar o que vai acontecer mais e passar um pouco mais de tempo, um pouco mais de espaço para as coisas que, sim, pode acontecer mas não necessariamente com tanta freqüência. Então, vamos dar um exemplo.
Suponha que queremos codificar a informação bastante eficiente. Você pode ter crescido sabendo um pouco sobre o código Morse, e as probabilidades são que você não sabia o código real, mas você deve se lembrar que ele é, pelo menos, esta série de pontos e traços. Esta é uma codificação bastante eficiente, e observe que a carta do mais popular - por exemplo, E - usa a mais curta de sinais sonoros. O código Morse é tudo sobre bip-bip-bip-bip-bip-bip e segurando tons ou por curtos períodos de tempo, ou períodos de tempo longos. E, tal como indicado pelo ponto, é um sinal de super curta, apenas bip, e isso representaria E. Em contraste, T seria um bip longo, como bip [prolonga som], e que representaria T. Mas isso ainda é muito curto, porque, por outro lado, se você olhar para Z, para expressar Z você iria beep, beep [mais som], beep, beep [som mais curta]. Então, é mais porque é menos comum. Mas a pegadinha aqui é que o código Morse é um pouco falho em que não é imediatamente decodable. Por exemplo, suponha que você ouve em algum fim do bip fio [curto], beep [longa]. Qual a mensagem que eu acabei de receber? Um ponto e um traço. O que isso representa? [Estudante] A. >> [Malan] Talvez. Também poderia ser E seguido por T. Em outras palavras, o código Morse, embora aproveita este princípio de optimizar o processo de canto, não se presta a Decodificação imediato. Isto é, o ser humano que está ouvindo ou receber esses pontos e traços tem de alguma forma descobrir onde os intervalos são entre as letras, porque se você não sabe onde as quebras são, você pode confundir um para ET ou vice-versa.
Então, o que você poderia fazer? Em código Morse que você poderia apenas fazer uma pausa entre cada uma das letras. Mas a pausa é uma espécie de contador para o ponto de acelerar as coisas. Então, o que se em vez disso, veio com um código onde não havia essa situação ruim em que E é um prefixo, por exemplo, de A - em outras palavras, se pudéssemos ter certeza de que os padrões são ainda curto para as letras populares tempo para as letras menos populares, mas não há confusão possível? Um homem com o nome de Huffman anos atrás inventou esse esquema chamado de código de Huffman que realmente aproveita uma das estruturas de dados que passamos um pouco de tempo falando sobre na semana passada, que de árvores, árvores binárias especificamente - um significado árvore binária que não tem mais do que duas crianças. Tem talvez um filho esquerdo, talvez uma criança direita, e é isso. Então suponho que apenas por uma questão de discussão que alguém queira enviar uma mensagem que se parece com isso. É um completo disparate, mas é composto de As, Bs, Cs, Ds e Es. E se você realmente contar-se todos os As, Bs, Cs, Ds e Es e depois dividir pelo número total de letras, este quadro pouco aqui diz que 45% das cartas são Es, 20% são como, 10% Bs, e assim por diante. Portanto, em outras palavras, assumir que a string lá é apenas uma mensagem que você quer enviar. Ele passa a ser um disparate só assim podemos usar como letras quanto possível, mas é verdade que permanece E o mais popular, e B e C são as menos populares, pelo menos, uma dessas 5 letras do alfabeto. Então, como podemos ir em chegar com uma codificação, uma codificação binária, um padrão de 0 e 1 para cada uma dessas cartas de tal modo que E é um padrão de curto e talvez B e C são padrões ligeiramente mais longos, novamente, a idéia de que nós queremos usar menos bits maior parte do tempo e mais bits só de vez em quando. De acordo com o código de Huffman, você pode criar uma floresta de árvores. Há uma espécie de uma história aqui que envolve árvores e também o processo de construção de-los. Vamos começar.
Proponho que você comece com essa floresta, por assim dizer, de 5 árvores, cada um dos quais é uma árvore muito estúpido. A árvore é composto por apenas um único nó, como representado aqui por um círculo. Assim, cada uma dessas coisas pode ser um struct C e dentro da estrutura C pode ser um float representando a contagem de freqüência e depois talvez um char que representa a letra. Então, acho que um desses nós como apenas struct C qualquer idade, mas, por agora, de nível superior. Esta é uma floresta de 5 árvores, cada um dos que só têm um único nó. O Huffman proposta é que começamos a combinar essas árvores que têm as menores contagens de freqüência um pouco maior em árvores ligando-os com um nó raiz nova. Assim, entre as letras aqui, observe que, por conveniência eu classificados los da esquerda para a direita, apesar de que não é estritamente necessário, e observe que os menores nós são actualmente 10% e 10%. Então Huffman propôs que mesclar essas duas menores nós em uma nova árvore pela introdução de um novo nó pai e depois dar esse pai de uma criança esquerdo e um direito da criança onde B é arbitrariamente a esquerda e C é arbitrariamente a direita. E então Huffman ainda proposto que vamos agora apenas de pensar no filho esquerdo em uma dessas árvores sempre como sendo representado por 0 e do direito da criança sempre como sendo representado pelo número 1.
Não importa se você lançá-los, desde que você é consistente. Portanto, agora temos quatro árvores na floresta. E eu digo quatro porque agora a árvore à esquerda - e não é tanto uma árvore no sentido de que ela cresce dessa forma, é mais como uma árvore de família onde agora o 0.2 é uma espécie de pai dos dois filhos - notar que, em que pai temos desenhado 0,2. Nós adicionamos a contagem de freqüência dos dois filhos e dado o novo nó a soma total. Então agora só repetir esse processo. Encontre as duas menores nós e depois uni-los em uma nova árvore e repita o processo ainda mais. Agora temos alguns candidatos, 20%, 15%, e outros 20%. Neste caso, temos que quebrar o empate. Nós podemos fazê-lo de forma arbitrária. Devemos fazê-lo apenas de forma consistente. Neste caso, eu vou arbitrariamente ir com o outro à esquerda, e eu agora fundir os 20% e os 15% para me dar um novo pai chamou 35%, cujo esquerda criança é 0, cujo direito é uma criança, e agora nós temos apenas três árvores na floresta. Você pode, talvez, ver onde isso vai dar. Se repetirmos esta mais algumas vezes, nós vamos ter apenas uma árvore maior, todos cujas bordas são rotulados com 0s e 1s. Vamos fazê-lo novamente. 35% é a raiz que árvore. 20% e 45%, por isso estamos indo para mesclar a 35% e 20%. Agora temos essa árvore aqui. Nós adicionamos os juntos, temos 55%. Agora só há duas árvores na floresta. Fazemos isso uma última vez, e espero que matematicamente todas as freqüências somam porque eles devem já que eles calculados a partir de a-go de somar 100%. E agora temos uma árvore. Portanto, esta é uma árvore de Huffman codificação. É o tipo de demorou um pouco para chegar lá verbalmente, mas a realidade é com um loop ou com uma função recursiva, você poderia construir esta coisa muito rápido. Portanto, agora temos um novo nó, e todos estes nós internos foram malloc'd, presumivelmente, ao longo do caminho. Então agora, na parte superior desta árvore temos 100%, mas agora notar que temos um caminho desta nova grande-grande-grande-avô para todas as grande-grande-grande-netos todo o caminho para o fundo, para todas as folhas.
O que vamos fazer agora é propor que, a fim de representar a letra E, nós simplesmente usar o número 1. Por quê? Porque se atravessar esta árvore a partir da raiz final até a folha conhecido como E, seguimos apenas a ponta, a borda da direita, e que é rotulado de curso superior em direito 1. Assim, a implicação aqui para Huffman foi que a codificação E em binário deve ser apenas uma. E isso é muito muito eficiente. Não pode realmente ficar menor do que isso. Em contrapartida, um vai ser representado, se você seguir a lógica, por que padrão de bits em vez? 01. Assim, para obter a A, começamos na raiz e vá para a esquerda e depois vá para a direita, o que significa que seguiu a 0 e, em seguida, um 1. Assim, devem representar a letra A com o padrão 0 e 1. E agora percebe que já temos uma propriedade de Decodificação imediata que nós não temos em código Morse. Mesmo que ambos os padrões são bastante curto - E é um pouco, um é de 2 bits - notar que eles não podem ser confundidas um ou o outro, porque se você ver um um que tem que ser um E, se você ver um 0, um 1 é, obviamente, tem que ser um A. Da mesma forma, o que há de D? 001. O que é C? 0001. E o que é B? 0000. E, novamente, porque todas as cartas que preocupam são as folhas e nenhum deles são uma espécie de intermediários no caminho da raiz até a folha, não há risco de confundir codificações duas letras 'diferentes porque todos esses padrões de bits são deterministas. 0000 será sempre B. Não há nó em algum lugar entre o que você pode confundir uma carta para o outro. Então, qual é a implicação aqui?
A carta mais popular - neste caso E - ficou mais curto de codificação, Um ficou a codificação mais baixo seguinte, e B e C, que já sabia do tipo get-go foram dos menos populares a freqüência de 10% cada um, eles têm obtido o maior codificação. E então o que isto significa que agora é que se você quiser enviar uma mensagem de que é comprimido através da Internet ou por e-mail ou semelhante, em vez de usar ASCII padrão, você pode enviar uma mensagem codificada Huffman através do qual se pretende enviar a letra E, você envia um único bit. Se você quiser enviar um A, você envia 2 bits, 01, em vez de enviar 8 bits seguidos de mais 8 bits seguidos por mais 8 bits e assim por diante. Mas há uma pegadinha aqui. Não é suficiente apenas para construir esta árvore e, em seguida, iniciar o envio de Alice para Bob o padrão mais curto pouco, string de ASCII, Alice também porque tem de informar Bob daquilo Bob se vai ser capaz de ler sua mensagem comprimido? [Resposta do aluno inaudível] >> O que é isso? [Resposta do aluno inaudível] >> De que a árvore é. Ou ainda mais especificamente, o que essas codificações são, especialmente porque durante esta história que fez um julgamento em um ponto. Lembre-se que tivemos de escolher arbitrariamente entre os dois diferentes nós de 20%? Portanto, não é o caso de que Bob, o destinatário, pode apenas reconstruir a árvore em sua própria porque talvez ele vai criar a árvore levemente diferente de Alice. Além disso, Bob ainda não sabe o que a mensagem original é porque a única coisa que Alice está enviando-lhe, é claro, é a mensagem de comprimido.
Assim, a captura com compressão como este é que, sim, Alice pode salvar um monte de bits enviando 1 para E e 01 para A e assim por diante, mas ela também tem de informar o que Bob é o mapeamento entre as letras e os bits porque não pode confiar em apenas claramente ASCII mais se nós não estamos usando ASCII. Então, ela pode enviar-lhe a árvore de alguma forma - anotá-la, guarde-a como dados binários, ou algo assim - ou apenas enviar-lhe uma folha de fraude pouco, um arquivo do Excel, que mostra os mapeamentos. Assim, a eficácia de compressão realmente assume que as mensagens que você está enviando são muito grandes, pelo menos, de médio porte, porque se você está enviando uma mensagem super curto, se você quiser apenas para enviar a mensagem BAD, que passa a ser uma palavra que pode significar aqui, B-A-D, você provavelmente vai usar menos bits, mas o problema é se você também tem que informar Bob o que a árvore é ou o que essas codificações são, você vai provavelmente superam todas as economias de ter as coisas comprimido para começar. Então ele pode realmente ser o caso de que se você tentar comprimir mesmo com algo como formatos zip ou arquivo que você pode estar familiarizado com - arquivos muito pequenos, até mesmo arquivos vazios - às vezes, esses arquivos podem ficar maior e não menor. Mas, realisticamente, o que acontece apenas para arquivos pequenos, por isso não vai fazer com que um arquivo gigabyte ser de 2 gigabytes; estamos realmente falando bytes ou apenas um par de kilobytes.
Alguns programas como o zip são inteligentes o suficiente para perceber que, "Você vai gastar mais bits comprimir isso." "Deixe-me não incomoda comprimi-lo para você em tudo." Portanto, esta é apenas uma forma de comprimir em seguida, formato de texto. Nós poderíamos implementar algo assim em C. Por exemplo, aqui é como podemos representar um nó na árvore onde temos um char para o símbolo, um valor flutuante para a freqüência, e, como vimos com os nossos estruturas de dados, outros dois ponteiros, 1 para o filho esquerdo, um para a direita, sendo que ambos podem ser NULL, mas se não, ele se refere a uma criança esquerdo e um direito da criança. Portanto, este é, então, Huffman, e é uma maneira que você pode ir sobre a comprimir informações, e é certamente um dos mais fáceis de implementar no contexto de, por exemplo, as estruturas de dados da última semana, embora mesmo algoritmos mais sofisticados existir que podem fazer mutações ainda mais sofisticadas de seus dados. Quaisquer perguntas, então em árvores, árvores binárias, ou compressão de texto? [Estudante] Existe alguma ambiguidade, como se dividir [inaudível] em 01, então 011 seria ambíguo, certo? [Inaudível] >> Boa pergunta. Ambigüidade. Deixe-me resumir referindo-se a este quadro aqui. Como os caracteres que você está comprimindo, as representações de, por definição deste algoritmo permanecer sempre as folhas, você nunca vai usar acidentalmente o mesmo padrão de bits para o prefixo de várias letras. Portanto, em outras palavras, você está preocupado, parece que, de uma ambigüidade decorrente em que 001 pode ser o início de B ou o início de C ou algo assim. Mas isso não pode ser o caso porque aviso de que todas as letras do alfabeto que está codificando são as folhas.
A ambiguidade só pode surgir, como no caso do código Morse, se, por exemplo, C estava em algum lugar ao longo do caminho da raiz até B. [Estudante] Direito. Assim, neste caso, por exemplo um tem 2 folhas. Diga >> A tem - Diga isso de novo. [Estudante] Diga A tem duas folhas, F e G, e então g - >> Certo. Mas não pode. A si não poderia ter folhas F e G, porque essas letras F e G elas próprias ser deixa lugar à esquerda ou à direita B de E. Assim, por definição, estes devem ser folhas. Caso contrário, você está absolutamente certo, nós não resolvemos o problema que enfrenta o código Morse. Boa pergunta. Outras perguntas? Tudo bem. Esta noção de bits, verifica-se que já tinha poder o tempo todo que não temos realmente usado quando se tratava de manipular esses 0s e 1s. Perguntamos sobre isso em um dos conjuntos mais antigos problemas: ou seja, como você vai fazer sobre a conversão de maiúsculas para minúsculas ou vice-versa? Ou, mais concretamente, um desses Série de Exercícios primeiro perguntou quantos bits você realmente tem que virar a fim de mudar Um para minúsculas uma ou vice-versa? Aqui está um lembrete rápido do que 65 e 97 parece em binário. E mesmo que essa pergunta tem a sorte de se desvaneceu em sua memória, você pode ver novamente aqui que quantos bits precisa ser invertida para mudar maiúsculo para minúsculas uma? Apenas um.
Eles só diferem em um único local, o terceiro bit a partir da esquerda. Considerando A tem um 010, um pouco tem um 011. Então, de alguma forma, precisamos apenas ser capaz de virar esse bocado, e então podemos capitalizar ou letras minúsculas. Nós fizemos isso no passado usando efetivamente, se as condições e verificar se a letra está entre capitais A e Z capital, em seguida, saídas como a - a + 26 ou algo assim. Você provavelmente fez uma mudança de aritmética para as letras do alfabeto. Mas o que se pudéssemos virar que um único bit? Como você poderia ir sobre a tomada de vale um byte de 8 bits, assim como pedaços 01000001 e 01100001? Se você tivesse os padrões de bits, como podemos ir sobre a mudança de apenas um deles? O que se apresentar em amarelo aqui esta outro padrão de bits? Se eu fizer toda a 0s cordas amarelas exceto para o pouco que eu quero mudar e então eu introduzir um novo operador conhecido como um operador bit a bit - bit a bit, no sentido de que opera em pedaços individuais, não sobre um byte inteiro ou quatro bytes de uma só vez. Esta barra vertical lá em amarelo sugere que o que se tomarmos a representação do capital de uma e bit a bit OR-lo com a seqüência de bits amarelo? Em outras palavras, acho que voltar à nossa discussão de expressões booleanas em Scratch e depois em C.
Fazendo um booleano ou significa que, para ser verdadeiro, ou a primeira coisa que tem que ser verdade ou a segunda coisa que tem que ser verdadeiro ou ambos têm de ser verdade, e, em seguida, o produto resultante é, em si verdadeira. Neste caso aqui, o que é que vamos chegar, se tomarmos 0 "ou" ed com 0? Falsa ou falsa? Ainda é falso, então a uma minúscula permanece como o esperado. E se em vez disso, fazer 1 ou 0? Este agora resta 1, mas perceber o que está para acontecer aqui. Se começarmos com A maiúsculo e continuamos a "ou" seus bits individuais como estamos fazendo aqui, 0 ou o amarelo nos dá o que aqui? Isto dá-nos uma. De fato, suponha que não sabia o que a versão em maiúsculas pouco um realmente era. Vamos fazer isso. Deixe-me passar esta de volta aqui. Vamos fazer isso de novo. 0 ou 0 dá-me 0. 1 ou 0 dá-me um. 0 ou 1 me dá 1. 0 ou 0 dá-me 0. O próximo é 0, a próxima é de 0, o próximo é 0. 1 ou 0 dá-me um. E por isso mesmo que nós não sabíamos de antemão o que era um minúsculas, simplesmente por "ou" ing A com este padrão de bits que temos aqui apresentados em amarelo, você pode minúsculas um capital Um virando o bit. Usamos esta expressão semanas atrás: apertar um pouco. Como você realmente fazer isso programaticamente? Você usa o que é geralmente chamado de máscara, uma seqüência de bits, que neste caso só acontece a olhar como este número aqui, e então você "ou" isso em conjunto, utilizando este operador C novo, não | |, você usa um único | e você realmente obter essa resposta aqui por que? Este é o lugar 1s, 2s lugar, 16s 4s, 8s, 32s. Assim, verifica-se que se você tirar uma letra maiúscula A e OR bit a bit com o 32 inteiro, porque o 32 inteiro, quando você olha para ele como bits, olha como este, isso significa que você pode virar o pouco que você realmente quer. E da mesma forma - e nós vamos olhar para o código em apenas um momento - suponha que queremos ir na outra direção.
Como você vai de capital de uma minúscula para A? Que pouco precisa mudar? É o mesmo. Queremos mudar isso a partir de um terceiro bit 1 a 0. E como podemos fazer sobre isso? Como podemos desligar um pouco? Com o padrão de bits podemos desligar um pouco? E se a gente meio que inverta a máscara? Considerando que, antes, fizemos os 0s máscara toda amarela exceto para o pouco que queríamos ligar, E se desta vez, nós fazemos o 1s máscara inteira, exceto para o pouco que nós queremos para desligar e, em seguida, usar o que operador? E se nós "e" as coisas? Vamos dar uma olhada. Se agora virar para isso, suponha que novamente eu criar uma máscara que é tudo 1s exceto para o pouco que eu quiser desligar e depois, em vez de "ou" os números brancos em cima com os números amarelos até aqui, e se eu, em vez "e" eles juntos? É chamado um bit a bit e. Logicamente, é a mesma coisa que um Boolean e. Isto dá-me 0 e 1 é 0. Tão falso e verdadeiro é falso. Verdadeira e verdadeira é verdadeiro. E aqui está a mágica: o verdadeiro eo falso é agora falso, por isso temos que desligado pouco. E agora o resto da história é um pouco simples. Uma vez que o resto da máscara está 1s, não importa qual os números estão em branco. Quando você "e" algo com verdade, você não vai mudar o seu valor. Se é verdade, ele permanecerá verdadeiro. Se era falsa, ele permanecerá falsa.
Mas a mágica acontece quando você toma algo que era verdade e então você "e" com falso. Isto tem o efeito de que o bit de desligar. Assim, uma enigmática pouco ali. Vamos realmente olhar para algum código, o que pode realmente olhar ainda mais enigmático, mas vamos dar uma olhada aqui tolower. Se eu olhar para tolower, passando de capital de um para letras minúsculas a, vamos ver como podemos implementar este programa. Aqui está o principal, e não está tomando quaisquer argumentos de linha de comando. Estou declarando um caractere c para a letra que o usuário vai digitar dentro Eu, então, usar um do laço familiar enquanto apenas para se certificar de que o usuário definitivamente me dá um A maiúsculo ou B ou C. .. Z, de modo que me dê algo entre A e Z. E agora o que eu estou fazendo aqui? Eu sou "ou" ing isso com 0x20, mas que na verdade é o mesmo que - e vamos voltar a isso em um momento - 32. Então, novamente, 32 é este padrão de bits aqui. Por que saber isso? Basta pensar de volta para semana 0. Este é o lugar 1s, 2s lugar, 4s, 8s, 16s, 32s lugar. Portanto, este número amarelo passa a ser 32. Posso, então, tomar uma carta como o char aqui, bit a bit "ou" isso literalmente com o número 32, eo que posso voltar? A versão minúscula que char. Há instantes, porém, eu expressei isso em uma notação de base diferente. O que isso representa? >> [Aluno] Hexadecimal. [Malan] Isso acontece para representar hexadecimal. Nós não falamos sobre hexadecimal tanto assim, mas é realmente conveniente em casos como este.
Mesmo que parece mais complexo e, embora parece que 20 e não 32, verifica-se que é na verdade a notação hexadecimal super conveniente porque em hexadecimal todos os dígitos após o 0x - e isso não significa nada; isso é apenas uma convenção humana que diz que aqui vem um número hexadecimal - cada um destes dígitos, a 2 e, em seguida, a 0, em si podem ser representados com exatamente 4 bits. Então, se fizermos isso, deixe-me abrir um editor de texto aqui - estranho autocomplete - se fizermos um editor de texto pouco aqui, o 0x20 número significa aqui é de 4 bits, aqui está mais 4 bits. Vamos fazer os 4 bits mais à direita em primeiro lugar. 0 quando representado com 4 bits é o que? Super fácil. Apenas 0s todos. Então 4 bits como 0s. Como você representar 2? Tem sido um tempo desde que fiz isso, mas é 0100. Portanto, este é o lugar 1s, este é o lugar 2s, e então não importa o que os outros lugares são. Em outras palavras, em hexadecimal você pode dizer 0x20, mas se você pensar então sobre o que é a 2 e como ele é representado em binário, qual é a 0 e como é representado em binário, as respostas a essas perguntas são este e este, respectivamente. Então 0x20 acontece para representar esse padrão de 8 bits, que é precisamente a máscara que nós queríamos. Portanto, este é o momento apenas um exercício intelectual, mas a realidade está no código é tipicamente mais comum para escrever constantes como esta em hexadecimal, em seguida, porque o programador pode de maneira relativamente fácil, mesmo que se exige um pouco de papel e lápis, descobrir o que o padrão de bits é porque você não pode simplesmente expressar 0s e 1s normalmente no código. Você não pode ir 00010 e assim por diante.
Você tem que escolher notações decimal ou hexadecimal ou octal ou outro. A maioria das pessoas tendem a escolher hexadecimal simplesmente para que cada dígito representa 4 bits e você pode fazer essa matemática rápida. E eu vou acenar a minha mão a toupper, que é quase o mesmo, parece quase idêntico. Toupper acontece de usar não o operador ou mas esse cara e df. O que representam df? df? Alguém? >> [Aluno] 255. 255? 255 não. Isso seria ss. Vamos deixar este como um pouco de exercício. Mas se você vai de 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 e então o que vem depois de 9? Nós somos o tipo de fora de dígitos decimais, mas em hexadecimal o que vem depois de 9? [Estudante] a. Então >> a, b, c, d. Você pode descobrir a partir daí o padrão de bits d realmente representa. E se fizermos as contas, veremos que a máscara que você acabar ficando para trás é idêntico a este. Trata-se de f, todos 1s, e este é d. Então df representa a máscara. Tudo bem. E, por último, para não fazer as coisas de som super, super técnico, Mas suponha que queria escrever um programa que faz isso. Deixe-me ir em frente e fazer binário, que é um programa em um arquivo chamado binary.c. E agora deixe-me correr binário e me dar um número inteiro não negativo. Vamos começar fácil e digite 0. Isto agora é um programa que imprime um inteiro em sua representação binária. Então, se eu jogar este jogo novamente e digite em apenas uma, eu deveria ter uma representação de 32 bits do 1. Se eu fizer isso de novo com dois, eu entendo isso. Se eu fizer 7, eu deveria ter um 1s poucos no final, e assim por diante. Acontece Digo isso porque, com operações bit a bit você pode realmente fazer uma outra coisa também. Você pode criar essas máscaras dinamicamente. Dê uma olhada neste exemplo uma final envolvendo operações bit a bit. Aqui está a primeira parte do código, solicitar ao usuário um número, e insiste em que você me dê um número inteiro não negativo. Então esse é tipo de coisa velha escola. Mas aqui é algo que é bem interessante.
Como faço para ir sobre a impressão de um número em binário? A primeira iteração de que para quê? O que é o tamanho de um int tipicamente, pelo menos, no interior do aparelho? >> [Aluno] 4. É 4. Então, 4 * 8 é de 32 - 1 é 31. Então, se eu estou começando a contar a partir de 31, que representa, ao que parece, apenas conceitualmente, o bit 31 ou pouco mais alta ordem, que é esse cara aqui, Considerando que este vai ser 0 bits. Portanto, esta é pouco 01 ... 31 bits. Então o que está fazendo esse código? Observe que este laço for, mesmo que pareça enigmático, é apenas a iteração de 31 a 0. É isso aí. Assim, a parte interessante agora deve estar nesses cinco linhas aqui. Observe que nessa linha que eu estou declarando uma máscara variável chamada para ser coerente com a nossa história desses números amarelos. E então o que é que esta fazendo? Este é um outro operador bit a bit não vimos antes, o mais provável. É o operador de deslocamento para a esquerda. Este operador faz isso. Aqui está o número 1, e se você fizer eu deixei mudança, desvio à esquerda, o que você acha que tem o efeito de fazer com que um indivíduo? Literalmente deslocando-o. Então, se o número 1 é o que você tem na esquerda e você começa por inicializar i a 31, o que é que vai fazer? Ele vai levar este número 1 e mude-31 lugares por aqui. E porque não há, obviamente, não os outros dígitos por trás dele, aqueles por padrão será substituído com 0s. Então você vai começar com o número 1, o que naturalmente se parece com isso - e deixe-me tirar isso aqui no centro. E então, como você muda as coisas para a esquerda, esse cara vai essencialmente dessa forma. Mas assim que você fizer isso, um 0 é preenchido dentro Se você transferi-lo uma segunda vez, ele vai para um lado e outro 0 é preenchido dentro
Você muda de novo e depois outro 0 é preenchido dentro Então, se você faz essa coisa de 1 << i 31 lugares, que acabam recebendo uma máscara que é de 32 caracteres, o que mais à esquerda do que é o 1, todo o resto dos quais são um 0. E não é que, como um aparte, mudando um número para a esquerda como esta também coincidentemente, e por vezes conveniente, tem o efeito de fazer o que para esse número? >> [Aluno] Dobrando-lo. Dobrar porque cada uma das colunas - o lugar 1s, 2s lugar, lugar 4s, Lugar 8s, 16s lugar - eles estão todos de duplicação que você vá para a esquerda. Ou melhor, quando você mudar a 1s você vai acabar dobrando o valor do número. Você pode acabar fazendo transformações interessantes de dígitos mudando tudo mais desta forma por potências de 2. Então, como isso funciona? Isso, então, dá-me uma máscara que é tudo 0s exceto por um 1 em lugar precisamente o que eu quero, e então esta expressão, que é roubado de toupper.c, está simplesmente dizendo ter o número n que o usuário digitou, "E" é com essa máscara, eo que é que você vai conseguir? Você está indo para obter um 1 se há um 1 em que a localização mascarado, ou você está indo para obter um 0 se não há. E assim todo o programa este que efetivamente é que tem um loop, e cria uma máscara com um 1 por aqui, então a 1 para cá, então a 1 para cá, e ele usa este bit a bit E truque para dizer é que há um bit 1 na entrada do usuário aqui?
Existe um bit 1 na entrada do usuário aqui? E se assim for, literalmente imprimir um, senão imprimir 0. Estamos fazendo isso com ints só porque é por isso que nós estamos fazendo 32 bits em vez de 8, mas o que nós introduzimos é este bit a bit E, este bit a bit OR, e este desvio para a esquerda do operador, o que muitas vezes não são muito úteis, mas acontece que eles podem ser. Na verdade, se você fosse a representar algo como um array de booleanos só para representar verdadeiro ou falso, suponha que você queira acompanhar ou não uma sala cheia de 300 alunos está presente, você pode declarar uma matriz de tamanho 300 do tipo bool para que você obtenha 300 bools, e você pode definir cada para true se alguém está aqui e falso caso contrário. Por que é que a representação em que a estrutura de dados ineficiente? O que é ruim sobre o projeto de que a estrutura de dados, um conjunto de 300 bools? O que é um bool, na verdade, por baixo do capuz? Isto, também, é algo que pode não estar familiarizado. Acontece que não há bool. Lembre-se que tipo de criada que com o arquivo cs50.h, que por sua vez inclui bool padrão. C é o tipo de muda, porém, quando se trata de bool. Ele usa 8 bits para representar todos os bool, que é completamente inútil porque, obviamente, quantos bits que você precisa para representar um bool? Apenas 1. Assim, verifica-se que se você agora tem a habilidade com os operadores bit a bit para manipular bits individuais, mesmo em um char, mesmo em um único byte, não é que você pode diminuir a memória necessária para representar algo estúpido assim a estrutura de dados denominada frequência por um factor de 8. Em vez de usar oito bits para representar verdadeiro ou falso, você poderia literalmente usar um usando um único byte para cada oito alunos da turma e alternar 0-1 bits individuais usando esses tipos de baixo nível truques. Isso realmente pôr fim à energia. Há dúvidas sobre as operações bit a bit?
Sim. >> [Aluno] Existe um operador exclusivo ou? Sim. Existe um operador exclusivo ou parecida com esta, ^, o símbolo de cenoura, o que significa que a única coisa que o primeiro ou o segundo aspecto pode ser um 1 para a saída para ser um 1. Há também um não, ~, o que lhe permitirá inverter a 0 para 1, ou vice-versa, bem. E há também um operador de deslocamento para a direita, >>, que é o oposto do que vimos. Tudo bem. Vamos levar as coisas agora para um nível superior. Começamos por falar de texto e, em seguida, comprimi-lo e representando o texto com um número menor de bits; nós conversamos um pouco sobre como nós podemos agora começar a manipular as coisas em um nível bit a bit. Vamos agora zoom até 10 mil pés de representação das coisas mais complexas, como gráficos. Aqui temos uma bandeira da Alemanha, aqui nós temos um da França. Estes podem ser representados em formatos de arquivo que você pode saber - GIFs, por exemplo. Se você já viu uma imagem na Web que termina em. Gif, este é um formato de intercâmbio de gráficos. Estas duas bandeiras aqui tipo de prestar-se a compressão para o que talvez seja óbvio motivo? >> [Resposta do aluno inaudível] Há um monte de repetição, certo? Para enviar bandeira da Alemanha, pense nisso como sendo uma imagem na tela trás em seus dias de Scratch. Você pode se lembrar que não há pixels individuais ou pontos que compõem uma imagem.
Há toda uma linha de pontos pretos e outra linha inteira de pontos pretos. Há um monte de linhas de pontos pretos que se possa ver se realmente o zoom, bem como quando nós zoom no rosto de Rob no Photoshop. Assim como nós temos mais, mais e mais fundo na imagem, você começou a ver a pixelização, todas as praças que compõem seu olho nesse caso. Mesma coisa aqui. Se o zoom um pouco, você veria pontos individuais. Bem, este é um tipo de desperdício de bits. Se um terço do pavilhão é preto e um terço do pavilhão é amarelo e assim por diante, por que não podemos de alguma forma comprimir esta bandeira? E mesmo a bandeira francesa pode ser comprimido, embora o padrão é um pouco diferente. Acontece que o formato de arquivo GIF é um formato de compressão sem perdas, o que significa que você pode ter uma imagem como a bandeira alemã aqui, você pode jogar fora um monte de seus bits sem sacrificar a qualidade. Isto está em contraste com algo como JPEG, com a qual a maioria de nós provavelmente está mais familiarizado. Facebook fotos e fotos do Flickr e afins quase sempre são salvos como JPEGs quando está carregado, mas JPEGs é uma perdas - formato em que você jogue fora bits - com perdas mas você também joga fora de qualidade. E por isso, se você compactar fotos com Photoshop ou enviá-los para o Facebook ou levá-los em um telefone realmente ruim, você sabe que o quadro começa a ficar muito manchado e pixelizada, e isso é porque ele está sendo comprimido pelo computador ou telefone por, literalmente, jogando informações de distância. Mas GIF é surpreendente na medida em que pode usar menos bits do que poderia por padrão sem perder nenhuma informação.
E é, essencialmente, fá-lo da seguinte maneira. Em vez de armazenar em um arquivo como um BMP seria um triplo RGB para preto, preto, preto, preto, preto, preto, preto, preto, preto, preto, preto, preto e assim por diante, em vez disso, o formato GIF é que vai dizer, "Black", e, em seguida, "Repita isso 100 vezes", ou algo assim. "Preto, repita este 100 vezes, preto, repita este 100 vezes ..." "Amarelo, repita este 100 vezes." E assim ele se lembra de, essencialmente, o pixel mais à esquerda e depois de alguma forma codifica a noção de repetir que o pixel de novo e de novo. Então GIFs pode comprimir-se sem perder nenhuma informação. Mas se você tivesse que adivinhar, se esse é o algoritmo que GIFs uso, qual destas bandeiras, mesmo que eles parecem idênticos em tamanho, vai ser menor quando salvos no disco como um GIF? >> [Aluno] Alemanha. Alemanha vai ser menor? Por quê? [Aluno] Porque você repetir isso muitas e muitas vezes na horizontal e então você repetir outra vez. >> Exatamente. Porque as pessoas que inventaram GIF apenas um tipo de arbitrariamente decidiu que a repetição será alavancado horizontalmente, e não lateralmente. Há uma repetição muito mais lateralmente aqui no pavilhão alemão do que na bandeira francesa. Então, se nós realmente abrir uma pasta no meu disco rígido que tem esses GIFs, você pode realmente ver que a bandeira alemã aqui é de 2 kilobytes e a francesa é de 4 kilobytes. Ele passa a ser uma coincidência que um é o dobro do outro, mas é, de facto, o caso em que a bandeira francesa é muito maior.
Mesmo que nós estamos falando aqui sobre os gráficos, as mesmas idéias podem ser aplicadas a não coisas como bandeiras, mas imagens que são um pouco mais complexo. Se você tirar uma foto de uma maçã, certamente há um monte de duplicação lá, para que pudéssemos de alguma forma, lembre-se que o padrão de fundo é azul e não, como a imagem da direita sugere, tem que lembrar a cor de cada pixel nesta foto. Assim, podemos jogar fora pedaços lá sem perda de informações. A maçã ainda parece a mesma coisa. Neste exemplo aqui, você pode ver o que acontece em um filme. Estes representam bobinas velha escola de cinema em que na imagem de cima há você tem uma condução RV passado uma casa e uma árvore. E, como que van drives passado da esquerda para a direita, o que, obviamente, não mudando? A casa não vai a lugar nenhum, e que a árvore não vai a lugar nenhum. A única coisa que está se movendo é a van neste caso. Assim como fundo inalteradas sugere, o que você pode fazer em filmes é igualmente apenas jogar fora a informação que não muda entre quadros. Isto é geralmente conhecida como a compressão interframe através do qual se este quadro é quase idêntica a esta, não vamos nos preocupar armazenado em disco qualquer informação idêntica sobre esses quadros intermediários, vamos usar apenas quadros principais de vez em quando que, na verdade, armazenar essas informações de forma redundante apenas como um pouco de sanidade verificar.
Por outro lado, uma outra abordagem para a compressão de vídeo é, neste segundo exemplo e inferior aqui, onde, em vez de armazenar 30 quadros, por que você não apenas armazenar 15 quadros por segundo em vez disso? Ao contrário do que o tipo de filme que flui lindamente, perfeitamente, ele pode olhar como está gagueira um pouco, uma pequena escola de idade, mas o efeito líquido será a de usar muito menos bits do que de outra forma seria necessária. Então onde é que isso, então isso nos deixa? Isso foi um pouco de um lado sobre onde mais você pode ir com a compressão. Para saber mais sobre isso, ter uma aula de como CS175 aqui. Aqui está outro exemplo dentro de vídeo. Se a abelha é a única coisa em movimento, você pode realmente jogar fora informações nesses quadros médios porque a flor e do céu e as folhas não estão mudando. Mas vamos agora considerar uma última coisa. Nos próximos cinco minutos que deixamos C para trás para sempre na aula? Sim. Não nos Série de Exercícios, no entanto. Última história sobre C e, então, chegar a coisas muito sexy envolvendo HTML e Web e woo-hoo. Tudo bem. Aqui vamos nós. Essa é a motivação. Acontece que todo esse tempo em que têm escrito programas que rodam Clang. E Clang, temos dito desde a primeira semana muito bonito, tem código fonte eo converte em código objeto. Leva C e converte-lo em 0s e 1s. Eu tipo de mentindo para você por algumas semanas, porque não é tão simples como isso.
Há muito mais acontecendo debaixo do capô quando você executar um programa como o Clang. Na verdade, o processo de compilação de um programa realmente pode ser resumido, como você pode se lembrar de vídeo de Rob sobre compiladores, para estes quatro passos: pré-processamento, compilação em si, montagem e ligação. Mas na sala de aula ea maioria das pessoas do mundo tipicamente resumir todas essas etapas apenas como "compilação". Mas se começarmos com o código fonte como este, recordo este é talvez o mais simples programa em C temos escrito até agora, lembro que quando compilado acaba desse jeito. Mas há, na verdade, um passo intermediário, e os passos são como se segue. Primeiro há essa coisa no topo deste e mais dos nossos programas, # Include O que o # include fazer por nós? Ele copia muito bonito e cola o conteúdo da stdio.h em meu arquivo de modo que por quê? Por que eu me preocupo com o conteúdo de stdio.h? O que há lá de interesse? Printf da declaração, o seu protótipo, de modo que o compilador, então, sabe o que quero dizer quando eu menciono essa função printf. Então, passo 1 na compilação é o pré-processamento, em que um programa como o Clang ou algum programa de ajuda que vem com Clang lê o código de topo para a base, esquerda para a direita, ea qualquer momento ele vê um símbolo # seguido de uma palavra-chave como include, ele executa essa operação, copiar e colar neste caso stdio.h em seu arquivo. Isso é o passo 1. Então você tem um arquivo muito maior C por causa da cópia enorme, cole trabalho que está apenas aconteceu.
2 passo agora é compilar. Mas acontece que a compilação tem código fonte que se parece com isso e transforma-lo em algo que se parece com isso, que para aqueles familiarizados é chamado? >> [Aluno] Assembléia. Língua >> Assembleia. Esta é realmente uma coisa se você tomar CS61 você vai mergulhar em mais detalhes. Este é apenas o mais próximo que você pode começar a escrever 0s e 1s-se mas escrever as coisas de tal forma que ainda faz, pelo menos, um pouco de sentido. Essas são instruções de máquina, e se desloque para a função principal aqui, perceber que existe esta instrução push, mover instrução, subtrair instrução, chamar a instrução, e assim por diante. Quando você ouve que o seu computador tem processador Intel dentro, você tem uma CPU Intel em seu Mac ou PC, o que significa isso? Uma CPU vem construído por empresas como a Intel compreender certas instruções. Eles não têm idéia do que funciona como swap são ou principal são, por si só, mas eles sabem o que muito instruções de baixo nível, como adicionar, subtrair, empurrar, mover, chamar, e assim por diante são. Então, quando você compilar o código C em linguagem de montagem, seu próprio código de usuário amigável para o futuro é convertido em algo que se parece com isso, que, literalmente, se move bytes ou 4 bytes em torno de tais pequenas unidades dentro e fora da CPU. Mas, finalmente, quando Clang está pronto para assumir essa representação de seu programa em 0s e 1s, em seguida, a etapa denominada montagem acontece, e isto tudo acontece de novo em um piscar de olhos ao executar Clang. Nós começamos aqui, ele gera um arquivo como este, e depois converte-lo para estes 0s e 1s. E se você quiser ir para trás em algum ponto e realmente ver isso em ação, se eu entrar em hello1.c-este é um dos programas primeiros que vimos - normalmente nós compilar este com hello1.c Clang e isso nos daria a.out. Se, pelo contrário você em vez dar o S-bandeira, o que você vai conseguir é hello1.s e você vai realmente ver a linguagem assembly.
Estou fazendo isso para um programa muito curto, mas se você voltar para Scramble ou recuperar ou qualquer outro programa que você escreveu e só por curiosidade quero ver o que ele realmente parece, o que está realmente a ser alimentado na CPU, você pode usar esse S-bandeira com Clang. Mas, então, por fim, ainda há uma pegadinha. Aqui estão os 0s e 1s que representam minha implementação do Olá mundo. Mas eu usei a função de alguém no meu programa. Assim, mesmo que o processo tenha sido eu tomar hello.c, ele é compilado em código de montagem, e depois ele fica montado em 0s e 1s, a única 0s e 1s que são emitidas neste momento no tempo são os que resultam do meu código. Mas a pessoa que escreveu printf, que compilou o código 20 anos atrás e agora ele é instalado em algum lugar do aparelho, para que de alguma forma tem que mesclar suas 0s e 1s com meu 0s e 1s, e que nos leva ao passo 4 e final de elaboração, conhecido como ligação. Assim, no lado esquerdo, temos o quadro exatamente como antes: hello.c torna-se código de montagem torna-se 0s e 1s. Mas lembre-se que eu usei a biblioteca de I / O padrão no meu código, e isso significa que em algum lugar no computador há um arquivo chamado stdio.c ou, pelo menos, a mesma versão compilada porque alguém há alguns anos compilado em código stdio.c montagem e depois um monte de 0s e 1s. Isso é o que é conhecido como estático ou uma biblioteca dinâmica. É algum arquivo sentado em algum lugar do aparelho.
Mas, finalmente, eu tenho que tomar minha 0s e 1s e dessa pessoa 0s e 1s e de algum modo vincular-los juntos, literalmente combinar os 0s e 1s em um único arquivo chamado a.out ou hello1 ou o que eu chamei meu programa de modo que o resultado final tem todos os 1s e 0s que devem compor o meu programa. Então todo esse tempo neste semestre, quando você estiver usando Clang e até mesmo, mais recentemente, de executar o make, a fim de executar Clang, todas essas etapas foram acontecendo tipo de instantaneamente, mas muito deliberadamente. E se você continuar em ciência da computação, ou seja, CS61, esta é a camada que você vai continuar a descascar lá fora falando sobre eficiência, implicações de segurança, e outros desses detalhes de nível inferior. Mas, com isso, que estamos prestes a deixar C para trás. Vamos em frente e tomar o nosso intervalo de 5 minutos, agora, e quando voltar: a Internet. Tudo bem. Estamos de volta. Agora vamos começar o nosso olhar não apenas em HTML, porque, como você vai ver, HTML em si é realmente muito simples mas realmente em programação web em geral, em rede de modo mais geral, e como todas essas tecnologias se reúnem para nos permitir criar programas muito mais sofisticados em cima da Internet do que até agora temos sido capazes de nos estas janelas preto e branco. Na verdade, neste momento, no semestre mesmo que vai passar um tempo relativamente menos em PHP, HTML, CSS, JavaScript, SQL e mais, a maioria dos estudantes do final para fazer projetos finais, que são baseados na web porque como você vai ver, o fundo que você tem agora em C é muito aplicável a estas linguagens de alto-nível.
E como você começar a pensar sobre o seu projeto final, que, assim como Conjunto de Problemas 0, onde foram encorajados de fazer mais qualquer coisa do seu interesse em Scratch, O projeto final é a sua oportunidade de ter o seu novo conhecimento e habilidade com C ou PHP ou JavaScript ou similar, para um giro e criar o seu próprio pedaço de software para o mundo ver. E a semente que com idéias, saiba que você pode dirigir aqui, projects.cs50.net. Todos os anos, solicitar idéias de professores e funcionários e grupos de estudantes no campus apenas para apresentar as suas ideias para coisas interessantes que poderiam ser resolvidos usando computadores, usando sites, usando o software. Então, se você está lutando para chegar a uma idéia de seu próprio país, por todos os meios percorrer as idéias lá a partir deste ano eo último. É perfeitamente bem para enfrentar um projecto que tem sido abordado antes. Temos visto muitos aplicativos para ver o status de roupa no campus, muitos aplicativos para navegar no menu sala de jantar, muitos aplicativos para navegar o catálogo de cursos e afins. E, de fato, em uma palestra futuro e em futuros seminários, vamos apresentá-lo a algumas APIs disponíveis ao público, ambos disponíveis no mercado , assim como aqui disponível CS50 no campus para que você tenha acesso a dados e pode, então, fazer coisas interessantes com ela. Então, mais em projetos finais em alguns dias, quando nós liberamos a especificação, mas por agora, sei que você pode trabalhar sozinho ou com um ou dois amigos em mais qualquer projeto de interesse para você. A Internet. Vá em frente e puxe o seu laptop, você vai para facebook.com pela primeira vez, não ter conectado recentemente, e pressione Enter. O que acontece exatamente?
Quando você pressione Enter em seu computador, monte um conjunto de passos começar espécie de passe de mágica acontecer. Então você aqui no servidor, web esquerda como o Facebook está aqui à direita, e de alguma forma você está usando esta linguagem chamada HTTP, Hypertext Transfer Protocol. HTTP não é uma linguagem de programação. É mais de um protocolo. É um conjunto de convenções que os navegadores e servidores Web usam quando intercomunicação. E o que isso significa é o seguinte. Assim como no mundo real, temos estas convenções onde se você encontrar algum ser humano pela primeira vez, se você não se importa brincando comigo aqui, Eu poderia vir até você, diga: "Oi, meu nome é David." >> Olá, David. Meu nome é Sammy. "Oi, David. Meu nome é Sammy." Então, agora temos apenas envolvidos neste tipo de protocolo humano bobo onde eu ter iniciado o protocolo, Sammy respondeu, temos aperto de mãos e a transação seja concluída. HTTP é muito semelhante em espírito. Quando seus pedidos navegador web www.facebook.com, que o seu navegador está realmente fazendo está estendendo sua mão, por assim dizer, para o servidor e ele está enviando-lhe uma mensagem. E essa mensagem é tipicamente algo como se - o que você quer chegar? - me a página inicial, que normalmente é indicado por uma única barra no final de uma URL. E só assim você sabe que língua eu estou falando, eu o navegador vou dizer a você que eu estou falando HTTP versão 1.1, E também para a boa medida, eu vou dizer a você que o host que eu quero a página inicial do é facebook.com. Normalmente, um navegador web, sem saber, o ser humano, envia esta mensagem através da Internet quando você simplesmente digita www.facebook.com,
Entrar, em seu navegador. E o que o Facebook responder com? Ele responde com alguns detalhes de aparência semelhante enigmáticas, mas também muito mais. Deixe-me ir à frente para a página do Facebook casa aqui. Esta é a tela que a maioria de nós provavelmente nunca ver se você ficar conectado o tempo todo, mas esta é de fato sua home page. Se fizermos isso no Chrome, perceber que você pode puxar para cima os menus de contexto pouco. Usando o Chrome, seja no Mac OS, Windows, Linux, ou similar, Se você controlar clique ou clique esquerdo, normalmente você pode puxar um menu que se parece com isso, onde algumas opções esperam, um dos quais é View Page Source. Você também pode normalmente obter a estas coisas, indo para o menu Exibir e bisbilhotando. Por exemplo, aqui em Exibir, desenvolvedor é a mesma coisa. Eu estou indo para ir em frente e olhar para View Page Source. O que você vai ver é o código HTML que Mark escreveu para representar facebook.com. É uma bagunça completa aqui, mas vamos ver que isso faz sentido um pouco mais antes de tempo. Mas existem alguns padrões aqui. Deixe-me rolar para coisas como esta. Isso é difícil para um ser humano para ler, mas percebe que não há esse padrão de colchetes angulares com palavras-chave como opção, palavras-chave como valor, algumas cordas citadas. Este é o lugar onde, quando você se inscreveu para a primeira vez, especificado o que o seu ano de nascimento é. Esse menu drop-down de anos de nascimento é de alguma forma codificada aqui nesta linguagem chamada HTML, HyperText Markup Language. Em outras palavras, quando o navegador solicita uma página web, fala esta convenção chamado HTTP. Mas o que é facebook.com responder a esse pedido com?
Ele responde com algumas dessas mensagens crípticas, como veremos em um momento. Mas a maior parte da sua resposta está na forma de HTML, linguagem de marcação de hipertexto. Essa é a linguagem real em que uma página é escrita. E o que é um navegador realmente é, então, após o recebimento de algo que se parece com isso, lê-lo de cima para baixo, da esquerda para a direita, e qualquer vez que vê um desses suportes angulares seguido por uma palavra-chave como opção, ele exibe que a linguagem de marcação de forma adequada. Neste caso, seria exibir um menu de lista pendente de anos. Mas, novamente, isso é uma bagunça completa para olhar. Isso não é porque os desenvolvedores do Facebook manifestam 0 para 5 de estilo, por exemplo. Isto é porque a maioria do código que escrever é, de fato, escreveu lindamente, bem comentado, bem recuado, e similares, mas de máquinas de curso, computadores, navegadores realmente não dou a mínima se seu código é bem estilo. E, na verdade, é completamente inútil para bater a tecla tab todas as vezes e para colocar comentários durante todo o seu código e escolher realmente descritivos nomes de variáveis porque se o navegador não se importa, tudo que você está fazendo no final do dia é desperdiçar bytes.
Assim, verifica-se que a maioria dos sites de fazer é mesmo que o código fonte para facebook.com, para cs50.net e todos esses outros sites na Internet são tipicamente bem escrita e bem comentado e bem recuado e semelhantes, normalmente antes do website é colocado na Internet, o código é minified, qual o código HTML e CSS - algo que vamos ver em breve - o código JavaScript que vamos ver em breve é comprimido, através do qual nomes de variáveis longos tornam-se X e Y e Z, e todos os que os espaços em branco que faz tudo parecer tão legível é tudo jogado fora, porque se você pensar sobre isso dessa maneira, Facebook recebe uma página de bilhões de acessos por dia - uma coisa louca como essa - de modo que se um programador apenas para ser anal bateu a barra de espaço uma vez extra apenas para travessão alguma linha de código sempre muito mais? Qual é a implicação se o Facebook que preserva os espaços em branco em todos os bytes que enviar de volta para as pessoas na internet? Bater a barra de espaço uma vez que lhe dá um byte extra em seu arquivo. E se um bilhão de pessoas, em seguida, proceder ao download da página inicial desse dia, quanto mais dados você transmitidos através da Internet? Um gigabyte por nenhuma boa razão. E concedido, por um monte de sites não é uma questão tão escalável, mas para o Facebook, para o Google, para alguns dos sites mais populares há grande incentivo financeiro para tornar seu código olhar como uma confusão de modo que você está usando como alguns bytes possível, além de, em seguida, comprimi-lo usando algo como zip, um algoritmo chamado gzip, que o navegador faz automaticamente para você. Mas isso é terrível. Nós nunca vamos aprender alguma coisa sobre sites de outras pessoas e como criar páginas web se temos de olhar para ele como este.
Então, felizmente, navegadores como o Chrome e IE e Firefox estes dias normalmente vêm com ferramentas embutidas desenvolvedor. Na verdade, se eu descer aqui para inspecionar Elemento ou se eu for para Ver, Developer e vá para Ferramentas de Desenvolvimento explicitamente, Nesta janela, na parte inferior da tela do meu agora aparece. É um pouco intimidante no início, porque há um monte de abas desconhecidas aqui, mas se eu clicar em Elementos todo o caminho na parte inferior esquerda, Chrome é, obviamente, muito inteligente. Ele sabe como interpretar todo este código. E assim o Chrome faz é que limpa tudo de HTML do Facebook. Mesmo que não há espaço em branco lá, não há recuo lá, Agora, observe que eu possa começar a navegar nesta página web ainda mais hierarquicamente. Acontece que cada página da web escrito em uma linguagem chamada HTML5 deve começar com isso, esta declaração DOCTYPE, por assim dizer: É uma espécie de luz e cinza lá, mas essa é a primeira linha de código neste arquivo, e que apenas diz o navegador, "Ei, aqui vem algum HTML5. Aí vem uma página web." O primeiro suporte aberto além do que vem a ser essa coisa, um suporte aberto tag HTML, e então se eu mergulhar no mais profundo - essas setas são completamente sem sentido; eles são apenas por causa da apresentação, eles não estão realmente no arquivo - perceberá que dentro de tag HTML do Facebook, qualquer coisa que começa com um suporte aberto e depois tem uma palavra é chamado de tag. Então, dentro da tag HTML é aparentemente uma marca de cabeça e uma marca de corpo. Dentro da marca de cabeça agora é uma bagunça toda para o Facebook porque eles têm um monte de metadados e outras coisas para o marketing e publicidade.
Mas se rolar para baixo, para baixo, para baixo, para baixo, vamos ver onde ele está. Aqui está. Este é pelo menos um pouco familiarizado. O título da página do Facebook de casa, se você olhar no guia em sua barra de título, é Bem-vindo ao Facebook - Log In, Registre-se ou Saber Mais. Isso é o que você vê na barra do Chrome título, e é assim que ele é representado no código. Se ignorar tudo na cabeça, a maior parte das entranhas de uma página web estão no corpo, e verifica-se que o código do Facebook vai olhar mais complexo que a maioria das coisas que vou escrever inicialmente apenas porque foi construído ao longo dos anos, mas há um monte de marcas de script, o código JavaScript, que torna o site muito interativo: ver atualizações de status instantaneamente usando linguagens como JavaScript. Há uma coisa chamada div, que é uma divisão de uma página. Mas, antes de chegar a esse detalhe, vamos tentar diminuir o zoom e olhar para uma versão mais simples do Facebook 1.0, por assim dizer. Aqui está o mundo, Olá de páginas web. Ele tem essa declaração DOCTYPE no topo que é um pouco diferente de tudo o resto. Nada mais que escrever em uma página web vai começar com para negrito. Mais uma vez, a história é a mesma: Olá, vírgula, começar a fazer isso em negrito, então mundo fica impresso em negrito, e isso significa parar de imprimir esta em negrito. Deixe-me ir em frente e salvar o meu arquivo, volte para o Chrome, eu vou aumentar o zoom apenas para que possamos vê-lo melhor, e recarregar, e você vai ver que o mundo está agora em negrito. A Web é tudo sobre hiperlinks, então vamos seguir em frente e fazer isso: o meu site favorito é, vamos dizer, youtube.com. Salvar, recarregar. Okay. Há alguns problemas agora além da hediondez do site. 1, eu tenho certeza que eu pressione Enter aqui. E eu fiz. Eu não apenas pressione Enter, eu também recuado, praticando o que estamos pregando sobre o estilo, mas a minha é bem próximo ao mundo. Então, por que é isso? Navegadores só fazer o que lhes dizem para fazer. Eu não disse o navegador, "linhas de quebrar aqui. Insira parágrafo quebrar aqui." Assim, o navegador, não importa se eu acertar retorno de 30 vezes, ela ainda vai colocar o meu ao lado mundo. O que eu realmente tenho que fazer aqui é dizer algo como
, insira uma quebra de linha.
E, na verdade, uma quebra de linha é um tipo de coisa estranha porque você não pode realmente começar a se mover para outra linha, em seguida, fazer alguma coisa, e, em seguida, parar de se mover para uma nova linha. É uma espécie de uma operação atômica. Você quer fazer isso ou não. Você tecle Enter ou não. Então br é um pouco de uma marca diferente, e por isso eu preciso para classificar tanto abrir e fechar de uma só vez. A sintaxe para que é isso. Tecnicamente, você poderia fazer algo assim em algumas versões do HTML, mas isso é uma estupidez, porque não há nenhuma razão para iniciar e parar algo se você pode fazê-lo, em vez de uma só vez. Perceba que o HTML5 não estritamente exigir essa barra, assim você vai ver livros didáticos e recursos on-line que não o possuem, mas para uma boa medida vamos praticar a simetria que temos visto até agora. Isto significa que a etiqueta é simultaneamente aberto e fechado. Então, agora deixe-me salvar o meu arquivo, volte aqui. Ok, isso está começando a parecer melhor, exceto a Web que eu sei é tipo de clicável, e ainda youtube aqui não parece levar a nada. Isso porque mesmo que ele se parece com um link, o navegador não sabe que, por si só, então eu tenho que dizer ao navegador que este é um link.
A maneira de fazer isso é usar uma marca de âncora: e deixe-me passar isso para uma nova linha apenas por isso é um pouco mais legível, e eu vou diminuir o tamanho da fonte. Estou feito ainda? Não. Não vai ser essa dicotomia. Essa marca, a marca de âncora, de fato, tomar um atributo, que modifica seu comportamento, eo valor desse atributo é aparentemente URL do YouTube. Mas note a dicotomia é que só porque essa é a URL que você está indo, isso não significa que tem de ser a palavra que você está destacando e fazendo um link. Em vez disso, que pode ser algo como isto. Então, eu tenho que dizer que parar de fazer essa palavra um hiperlink usando a tag âncora perto. Repare que eu não estou fazendo isso. 1, este seria apenas um desperdício de tempo de todos e que não é necessário.
Para fechar uma tag, você só mencionar o nome da marca novamente. Você não menciona qualquer um dos atributos. Então, vamos guardar esse, voltar. Ok, pronto, agora é azul e hiperlink. Se eu clicar nele, eu realmente ir ao YouTube. Assim, mesmo que a minha página da web não está na Internet, é, no mínimo, HTML, e se deixarmos a Internet pegar, nós realmente acabar aqui no youtube.com. E eu posso voltar e aqui está a minha página da web. Mas perceber isso. Se você já cheguei de spam ou de um ataque de phishing, agora você tem a capacidade depois de apenas cinco minutos para fazer o mesmo. Podemos ir aqui e fazer algo como www.badguy.com ou o que o site é esboçado, e então você pode dizer verificar a sua conta PayPal. [Risos] E agora isso está indo para ir para badguy.com, que eu não estou indo para clicar em porque eu não tenho idéia de onde que leva. [Risos]
Mas agora temos a capacidade de realmente acabar ali. Então, nós estamos realmente começando a arranhar a superfície. Nós não estamos a programação por si só, estamos escrevendo linguagem de marcação. Mas assim que completar nosso vocabulário em HTML, vamos introduzir PHP, uma linguagem de programação real que nos permitirá gerar HTML automaticamente, gerar CSS automaticamente, para que possamos começar na quarta-feira para implementar, por exemplo, o nosso próprio motor de busca e muito mais. Mas, mais do que em um par de dias. Vamos ver então.
[CS50.TV]