Mac2166 Introducao A Computacao 1a5v5d
This document was ed by and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this report form. Report r6l17
Overview 4q3b3c
& View Mac2166 Introducao A Computacao as PDF for free.
More details 26j3b
- Words: 1,313
- Pages: 5
1/3/2014
MAC2166 Introducao a Computacao
Departamento de Ciência da Computação - IME - USP
MAC2166 Introdução à Computação Escola Politécnica - Primeiro Semestre de 2014 Primeiro Exercício Programa
Entrega: até 15 de março de 2014 às 23h55m
O código de Vigenère "If you reveal your secrets to the wind, you should not blame the wind for revealing them to the trees." Kahlil Gibran
Objetivos O objetivo deste primeiro exercício-programa é familiarizar os alunos com o ambiente de programação do Python e com o processo de entrega de exercícios-programa. O foco desse primeiro EP é utilizar operações com números inteiros. Os EPs são uma forma de treinamento na resolução de problemas computacionais. Para aferirmos esse treinamento é importante que as únicas construções --comandos, funções, etc-- da linguagem Python que você use em seu programa sejam as constantes dos enunciados e as dadas em aula. Sempre que um aluno PRECISAR MUITO usar um comando não dado em aula, dá para perceber que a disciplina não conseguiu ensinar direito alguma coisa para ele. Forçar a usar só comandos dados em aula é bom para ter essa avaliação do processo de aprendizado.
Introdução Um efeito curioso da invenção da escrita foi a necessidade de se inventar formas de esconder a informação armazenada nos textos. A Criptografia é um ramo da matemática que estuda técnicas para transformar informação para uma forma "ilegível". Nessa forma, só o destinatário próprio é capaz de recuperar a informação por meio de uma "chave secreta" que torna possível decifrar o código. Uma informação não-cifrada enviada de uma pessoa (ou organização) para outra é chamada de "texto claro" (plaintext). Cifragem é o processo de conversão de um texto claro para um http://www.ime.usp.br/~mac2166/ep1/
1/5
1/3/2014
MAC2166 Introducao a Computacao
código cifrado e decifragem é o processo contrário, de recuperar o texto original a partir de um texto cifrado. Na verdade, o estudo da criptografia cobre bem mais do que apenas cifragem e decifragem. É um ramo especializado da teoria da informação com muitas contribuições de outros campos da matemática e do conhecimento. A criptografia moderna é basicamente formada pelo estudo dos algoritmos criptográficos que podem ser implementados em computadores. [Texto adaptado da Wikipedia] Uma das técnicas mais simples de criptografia é o código de César, também conhecido como cifra de César ou troca de César. Por esse método, cada letra de um texto a ser criptografado é substituido por uma outra letra, transformada por meio de uma chave definida por apenas uma letra. Para esse EP, vamos considerar que cada palavra é na verdade um número inteiro decimal, e portanto uma "letra" corresponde a um dígito entre 0 e 9 e a chave é composta por um número entre 0 e 9. Um número cifrado tem cada dígito transformado pela seguinte fórmula:
onde é o i-ésimo dígito do código cifrado, é o correspondente i-ésimo dígito no número, K é a chave e o operador % corresponde ao resto da divisão inteira. Por exemplo: O resultado de 32 % 10 é 2. O resultado de 3 % 5 é 3. O resultado de 12 % 6 é 0.
Assim, o número N = 3478 cifrado usando a chave K = 5 seria codificado como o número C = 8923. Para decifrar o código, cada dígito do código cifrado é transformado pela fórmula:
onde corresponde ao i-ésimo dígito do código decifrado. Observe que o número codificado C = 8923 é decifrado corretamente como D = 3478 usando K = 5. A simplicidade do método de César permite que as cifras geradas sejam decifradas facilmente por um intruso (sejam quebradas) pois cada dígito (ou letra) sempre sofre a mesma transformação. Para tornar o código mais difícil de decrifrar, Giovan Batista Belaso descreveu em seu livro datado de 1553 um método que se utiliza de uma chave mais complexa que, no caso desse EP, será constituída de um inteiro composto por vários dígitos. Esse método no entanto é erroneamente atribuído a Blaise de Vigenère, que foi o autor de uma cifra ainda mais robusta [veja mais detalhes na Wikipedia]. A idéia do método é usar os dígitos da chave mais complexa de forma circular para codificar os dígitos do número a ser cifrado. Como os dígitos da chave variam, a unicidade da transformação entre um dígito e sua cifra deixa de existir. Além disso, o uso dos dígitos da chave de forma circular permite a codificação de números de tamanho arbitrário. EXEMPLO: Para usar a chave mais complexa, a chave deve ser alinhada com o número e repetida quantas http://www.ime.usp.br/~mac2166/ep1/
2/5
1/3/2014
MAC2166 Introducao a Computacao
vezes forem necessárias para codificar todos os dígitos do número. Assim, para N = 23456 e K = 79 o número cifrado seria C = 10325 pois: O dígito 9 de K é usado para cifrar o dígito 6, gerando a cifra 5. O dígito 7 de K é usado para cifrar o dígito 5, gerando a cifra 2. Como não há mais dígitos de K, a forma circular implica que a chave deve ser repetida para que o dígito 9 seja usado para cifrar o dígito 4, gerando a cifra 3. O dígito 7 é usado para cifrar o dígito 3, gerando a cifra 0. A chave é repetida novamente e o dígito 9 é usado para cifrar o dígito 2, gerando a cifra 1. Uma outra forma de entender o processo de repetição é considerar que o número N = 23456 é cifrado pela chave K' = 97979 (ou seja, a chave K' usada no cálculo tem o mesmo número de dígitos de N e é formada por repetições de K).
Tarefa Neste exercício-programa, a sua tarefa será escrever um programa em Python que apenas cifra um número inteiro. O seu programa deve: 1. receber um número inteiro N > 0. 2. receber um número inteiro K > 0. 3. calcular e imprimir C, onde C é a cifra de N usando o método de Vigenère com a chave K. 4. O seu programa deverá finalizar depois de executar uma e somente uma vez os os de 1 a 3. Não devem ser feitas mais cifragens nem outras supostas melhorias no programa. É esperado que o usuário digite um inteiro correspondente a N e K e não entre com valores indevidos (como um texto, um número real ou inteiro negativo). Para corrigir o seu EP, vamos assumir que o seu programa obedece exatamente o que está especificado no enunciado do EP. Tudo que fugir da especificação prejudicará a avaliação de seu trabalho. As únicas construções --comandos, funções, etc-- da linguagem Python que você poderá usar em seu programa são as constantes deste enunciado e as dadas em aula.
Exemplos de execução Nos exemplos, considere que tudo que aparece em vermelho foi digitado pelo usuário.
Exemplo 1 Teste simples, como no método de César: O código de Vigenère Digite um número ......: 4579 http://www.ime.usp.br/~mac2166/ep1/
3/5
1/3/2014
MAC2166 Introducao a Computacao
Digite o valor da chave: 3 O valor cifrado é : 7802
Exemplo 2 Teste de chave maior que número: O código de Vigenère Digite um número ......: 784312 Digite o valor da chave: 84312134 O valor cifrado é : 96446
Exemplo 3 Teste qualquer: O código de Vigenère Digite um número ......: 81751425134465672234567 Digite o valor da chave: 638165 O valor cifrado é : 19816053299093737862622
Exemplo 4 Codificação com perda de informação (quando a crifra tem zeros à esquerda) O código de Vigenère Digite um número ......: 23123 Digite o valor da chave: 987 O valor cifrado é : 0
Observações Antes de começar assista ao vídeo com o o-a-o da edição e submissão do EP1 aqui. Certifique-se de que o seu programa foi realmente depositado no site verificando se você recebeu um e-mail com a confirmação da entrega. Leia as INFORMAÇÕES SOBRE ENTREGA DE EPs antes de entregar o seu EP.
http://www.ime.usp.br/~mac2166/ep1/
4/5
1/3/2014
http://www.ime.usp.br/~mac2166/ep1/
MAC2166 Introducao a Computacao
5/5
MAC2166 Introducao a Computacao
Departamento de Ciência da Computação - IME - USP
MAC2166 Introdução à Computação Escola Politécnica - Primeiro Semestre de 2014 Primeiro Exercício Programa
Entrega: até 15 de março de 2014 às 23h55m
O código de Vigenère "If you reveal your secrets to the wind, you should not blame the wind for revealing them to the trees." Kahlil Gibran
Objetivos O objetivo deste primeiro exercício-programa é familiarizar os alunos com o ambiente de programação do Python e com o processo de entrega de exercícios-programa. O foco desse primeiro EP é utilizar operações com números inteiros. Os EPs são uma forma de treinamento na resolução de problemas computacionais. Para aferirmos esse treinamento é importante que as únicas construções --comandos, funções, etc-- da linguagem Python que você use em seu programa sejam as constantes dos enunciados e as dadas em aula. Sempre que um aluno PRECISAR MUITO usar um comando não dado em aula, dá para perceber que a disciplina não conseguiu ensinar direito alguma coisa para ele. Forçar a usar só comandos dados em aula é bom para ter essa avaliação do processo de aprendizado.
Introdução Um efeito curioso da invenção da escrita foi a necessidade de se inventar formas de esconder a informação armazenada nos textos. A Criptografia é um ramo da matemática que estuda técnicas para transformar informação para uma forma "ilegível". Nessa forma, só o destinatário próprio é capaz de recuperar a informação por meio de uma "chave secreta" que torna possível decifrar o código. Uma informação não-cifrada enviada de uma pessoa (ou organização) para outra é chamada de "texto claro" (plaintext). Cifragem é o processo de conversão de um texto claro para um http://www.ime.usp.br/~mac2166/ep1/
1/5
1/3/2014
MAC2166 Introducao a Computacao
código cifrado e decifragem é o processo contrário, de recuperar o texto original a partir de um texto cifrado. Na verdade, o estudo da criptografia cobre bem mais do que apenas cifragem e decifragem. É um ramo especializado da teoria da informação com muitas contribuições de outros campos da matemática e do conhecimento. A criptografia moderna é basicamente formada pelo estudo dos algoritmos criptográficos que podem ser implementados em computadores. [Texto adaptado da Wikipedia] Uma das técnicas mais simples de criptografia é o código de César, também conhecido como cifra de César ou troca de César. Por esse método, cada letra de um texto a ser criptografado é substituido por uma outra letra, transformada por meio de uma chave definida por apenas uma letra. Para esse EP, vamos considerar que cada palavra é na verdade um número inteiro decimal, e portanto uma "letra" corresponde a um dígito entre 0 e 9 e a chave é composta por um número entre 0 e 9. Um número cifrado tem cada dígito transformado pela seguinte fórmula:
onde é o i-ésimo dígito do código cifrado, é o correspondente i-ésimo dígito no número, K é a chave e o operador % corresponde ao resto da divisão inteira. Por exemplo: O resultado de 32 % 10 é 2. O resultado de 3 % 5 é 3. O resultado de 12 % 6 é 0.
Assim, o número N = 3478 cifrado usando a chave K = 5 seria codificado como o número C = 8923. Para decifrar o código, cada dígito do código cifrado é transformado pela fórmula:
onde corresponde ao i-ésimo dígito do código decifrado. Observe que o número codificado C = 8923 é decifrado corretamente como D = 3478 usando K = 5. A simplicidade do método de César permite que as cifras geradas sejam decifradas facilmente por um intruso (sejam quebradas) pois cada dígito (ou letra) sempre sofre a mesma transformação. Para tornar o código mais difícil de decrifrar, Giovan Batista Belaso descreveu em seu livro datado de 1553 um método que se utiliza de uma chave mais complexa que, no caso desse EP, será constituída de um inteiro composto por vários dígitos. Esse método no entanto é erroneamente atribuído a Blaise de Vigenère, que foi o autor de uma cifra ainda mais robusta [veja mais detalhes na Wikipedia]. A idéia do método é usar os dígitos da chave mais complexa de forma circular para codificar os dígitos do número a ser cifrado. Como os dígitos da chave variam, a unicidade da transformação entre um dígito e sua cifra deixa de existir. Além disso, o uso dos dígitos da chave de forma circular permite a codificação de números de tamanho arbitrário. EXEMPLO: Para usar a chave mais complexa, a chave deve ser alinhada com o número e repetida quantas http://www.ime.usp.br/~mac2166/ep1/
2/5
1/3/2014
MAC2166 Introducao a Computacao
vezes forem necessárias para codificar todos os dígitos do número. Assim, para N = 23456 e K = 79 o número cifrado seria C = 10325 pois: O dígito 9 de K é usado para cifrar o dígito 6, gerando a cifra 5. O dígito 7 de K é usado para cifrar o dígito 5, gerando a cifra 2. Como não há mais dígitos de K, a forma circular implica que a chave deve ser repetida para que o dígito 9 seja usado para cifrar o dígito 4, gerando a cifra 3. O dígito 7 é usado para cifrar o dígito 3, gerando a cifra 0. A chave é repetida novamente e o dígito 9 é usado para cifrar o dígito 2, gerando a cifra 1. Uma outra forma de entender o processo de repetição é considerar que o número N = 23456 é cifrado pela chave K' = 97979 (ou seja, a chave K' usada no cálculo tem o mesmo número de dígitos de N e é formada por repetições de K).
Tarefa Neste exercício-programa, a sua tarefa será escrever um programa em Python que apenas cifra um número inteiro. O seu programa deve: 1. receber um número inteiro N > 0. 2. receber um número inteiro K > 0. 3. calcular e imprimir C, onde C é a cifra de N usando o método de Vigenère com a chave K. 4. O seu programa deverá finalizar depois de executar uma e somente uma vez os os de 1 a 3. Não devem ser feitas mais cifragens nem outras supostas melhorias no programa. É esperado que o usuário digite um inteiro correspondente a N e K e não entre com valores indevidos (como um texto, um número real ou inteiro negativo). Para corrigir o seu EP, vamos assumir que o seu programa obedece exatamente o que está especificado no enunciado do EP. Tudo que fugir da especificação prejudicará a avaliação de seu trabalho. As únicas construções --comandos, funções, etc-- da linguagem Python que você poderá usar em seu programa são as constantes deste enunciado e as dadas em aula.
Exemplos de execução Nos exemplos, considere que tudo que aparece em vermelho foi digitado pelo usuário.
Exemplo 1 Teste simples, como no método de César: O código de Vigenère Digite um número ......: 4579 http://www.ime.usp.br/~mac2166/ep1/
3/5
1/3/2014
MAC2166 Introducao a Computacao
Digite o valor da chave: 3 O valor cifrado é : 7802
Exemplo 2 Teste de chave maior que número: O código de Vigenère Digite um número ......: 784312 Digite o valor da chave: 84312134 O valor cifrado é : 96446
Exemplo 3 Teste qualquer: O código de Vigenère Digite um número ......: 81751425134465672234567 Digite o valor da chave: 638165 O valor cifrado é : 19816053299093737862622
Exemplo 4 Codificação com perda de informação (quando a crifra tem zeros à esquerda) O código de Vigenère Digite um número ......: 23123 Digite o valor da chave: 987 O valor cifrado é : 0
Observações Antes de começar assista ao vídeo com o o-a-o da edição e submissão do EP1 aqui. Certifique-se de que o seu programa foi realmente depositado no site verificando se você recebeu um e-mail com a confirmação da entrega. Leia as INFORMAÇÕES SOBRE ENTREGA DE EPs antes de entregar o seu EP.
http://www.ime.usp.br/~mac2166/ep1/
4/5
1/3/2014
http://www.ime.usp.br/~mac2166/ep1/
MAC2166 Introducao a Computacao
5/5
Related Documents 171j1w
Mac2166 Introducao A Computacao 1a5v5d
November 2019 37
Introducao A Sabedoria Hiperborea 6p5g10
October 2019 100
Introducao A Geometria Analitica 525e4p
November 2019 50
Introducao A Informatica 6i703n
September 2022 0
Introducao A Suma Teologica 115g5t
December 2020 0