Baixe Matemática Discreta e outras Notas de estudo em PDF para Informática, somente na Docsity! AVALIAÇÃO FORMATIVA NOTA Página 1 de 8 ORIENTAÇÕES PARA A RESOLUÇÃO - A presente avaliação formativa poderá ser realizada individualmente ou em duplas de acadêmicos, devendo ser entregue no dia 24 de junho de 2010, quinta-feira, durante a aula da disciplina (das 07h30min às 09h10min). - Esta avaliação vale 10,0 (dez) pontos, sendo uma das 03 (três) componentes que formarão a média final da disciplina, juntamente com outras DUAS avaliações (escritas, individuais e sem consulta). A média final será calculada pela média aritmética das TRÊS supraditas avaliações; - É permitida a entrega com atraso, com penalização de 1,0 (um ponto) por dia em relação à nota obtida. - A avaliação está dividida em duas partes: (I) com questões discursivas e (II) elaboração de programas de computador numa das seguintes linguagens de programação: Java, C, C++, Haskell, Visual Basic ou Delphi. - A avaliação deverá ser entregue na mídia CD-ROM ou DVD-ROM (não será aceito pendrive ou qualquer outro dispositivo de armazenamento), devidamente identificada por etiqueta adesiva com as seguintes informações: MATEMÁTICA DISCRETA Avaliação Formativa 2010/1 <nome do(a) acadêmico(a)> <nome do(a) acadêmico(a)> - Não será aceito CD-ROM/DVD-ROM sem identificação ou identificação incompleta. - A parte (I), com questões discursivas, deverá ser elaborada em editor de textos e entregue em documento eletrônico nos formatos .DOC (Microsoft Word 97-2003) ou .ODT (BrOffice 2.x ou Open Office 2.x). O nome do arquivo deverá ser DISCURSIVAS.DOC ou DISCURSIVAS.ODT. - A parte (II), com os programas de computador, exigirá que cada programa seja nomeado como QUESTAO05, QUESTAO06, QUESTAO07, ..., QUESTAO15, com a extensão relativa à linguagem empregada (.JAVA, .C, .CPP, .HS, .BAS ou .PAS). - As questões de 01 a 04 valem, cada uma, 0,5 ponto (meio ponto). As questões de 05 a 15 valem, cada uma, 0,8 ponto (oito décimos de ponto). Você deverá responder apenas 10 (dez) delas, ou seja, pode optar por não responder UMA DELAS. - O conteúdo exigido para resolução desta avaliação compreende os seguintes capítulos apresentados no Plano de Ensino da disciplina: (V) Recursão e (VI) Teoria dos Números. PARTE I – Questões Discursivas 01. Para os pares de números inteiros a e b, a seguir, determine o valor de q e r, também inteiros, de modo que a = b.q + r, com 0 ≤ r < b. a) a = 100 e b = 3 b) a = –100 e b = 3 c) a = 99 e b = 3 d) a = 0 e b = 3 02. Calcule, no contexto de Ζ10, o seguinte: a) 3 3 b) 7 3 c) 12 4 d) 4 4 Curso Bacharelado em Ciência da Computação Campus Jataí Disciplina Matemática Discreta Nome do(a) acadêmico(a) Assinatura Nº de matrícula Turma 1º Período “A” Data da Avaliação 01/06/2010 Professor(a) Wanderley de Souza Alencar ATENÇÃO: Somente serão passíveis de REVISÃO avaliações resolvidas a TINTA. AVALIAÇÃO FORMATIVA NOTA Página 2 de 8 e) 7 3 f) 12 5 g) 5 8 h) 8 5 i) 7 1 3 j) 8 7 k) 5 9 l) 6 2 03. Resolva as equações seguintes em relação a x Ζn no indicado: a) Ζ11: 3 4 b) Ζ11: 4 8 9 c) Ζ10:3 8 1 d) Ζ1003:432 448 73 04. Resolva, para todos os inteiros x, as seguinte equações: a) 3x ≡ 17 (mod 20) b) 2x + 5 ≡ 7 (mod 15) c) 10 – 3x ≡ 2 (mod 23) d) 100x ≡ 74 (mod 127) e) x ≡ 34 (mod 100) e x ≡ -1 (mod 51) f) 3x ≡ 8 (mod 10) e 2x + 4 ≡ 9 (mod 11) PARTE II – Elaboração de Programas de Computador 05. No jogo denominado Mega Sena o apostador pode escolher 6, 7, 8, 9 ou 10 dezenas para apostar dentre as 60 possíveis existentes na “cartela” (numerada de 1 a 60). É considerado GANHADOR DA MEGA SENA aquele de acerta as seis dezenas sorteadas. Um apostador gosta de apenas preencher cartelas de seis dezenas e, por isso, mesmo escolhendo mais números (7, 8, 9 ou 10) ele faz “combinações” destes números e preenche cada combinação numa cartela de seis dezenas. Atualmente ele faz isto manualmente. Sabendo que você cursa Ciência da Computação na Universidade Federal de Goiás, solicitou-lhe que escreva um programa de computador capaz de: a) Receber o número n (n = 6, 7, 8, 9 ou 10) indicando quantas dezenas o apostador quer marcar; b) Receber as dezenas desejadas para aposta; c) Gerar, e apresentar no dispositivo de saída, todas as “cartelas de seis dezenas” possíveis com aquelas dezenas escolhidas. Por exemplo: Suponha que ele escolheu marcar n = 7 e forneceu as dezenas 08, 16, 32, 34, 40, 46 e 54. O programa deverá gerar as seguintes “cartelas” e apresentá-las: 08, 16, 32, 34, 40, 46 08, 16, 32, 34, 40, 54 08, 16, 32, 34, 46, 54 08, 16, 32, 40, 46, 54 08, 16, 34, 40, 46, 54 08, 32, 34, 40, 46, 54 16, 32, 34, 40, 46, 54 06. O conjunto de todas as permutações possíveis sobre um conjunto de n elementos é indicado por Sn, também chamado de grupo simétrico de n elementos. AVALIAÇÃO FORMATIVA NOTA Página 5 de 8 . . . π(n) = ??? 12. Um dos mais conhecidos algoritmos para calcular o máximo divisor comum (mdc) entre dois números naturais a e b foi o elaborado pelo matemático grego Euclides: Entrada: Números naturais a e b, sendo a > b. Saída: mdc(a, b) Algoritmo: 1º Passo: Calcule c = a mod b 2º Passo: Se c = 0, retornamos como resposta b e finalizamos. Do contrário, se- guimos para o 3º passo. 3º Passo: Calcula-se o mdc(b,c) e o consideramos como resposta. Escreva um programa de computador que, utilizando uma função recursiva, calcule o máximo divisor comum de dois números naturais fornecidos. 13. Frank Gray, pesquisador dos Laboratórios Bell, em 1953 deu entrada num processo de registro de patente do que denominou Reflected Binary Code, que era um sistema binário de codificação em que cada elemento diferia do seu anterior somente por um único bit, como por exemplo: 00, 01, 11 e 10. No formulário de patente destacou que o código “ainda não tinha um nome reconhecido” e que seu nome “derivava do fato de que ele podia ser obtido a partir do sistema de codificação binária convencional por meio de processo de reflexão”. Outros pesquisadores passaram a utilizar o nome Gray Code que acabou por se tornar conhecido. As aplicações do código incluem: matemática (criação de quebra-cabeças, solução do problema da Torre de Hanoi), telegrafia/telecomunicações (correção de erros de comunicação), computação (algoritmos genéticos, mapas de Karnaugh), dentre outras. Há um algoritmo para construir um n-Gray Code, ou seja, um Gray Code de n bits de comprimento: Entrada: n, número natural Saída: n-Gray Code Algoritmo: 1º Passo: Inicie a lista com os seguintes elementos: 0 1 2º Passo: Se uma lista de valores binários de comprimento n foi construída, para construir a lista de valores binários de comprimento (n + 1) basta, nesta ordem, tomar cada um dos valores da lista de comprimento n e precedê-los por um: a) 0 (zero); b) 1 (um). Há também um algoritmo interativo para a geração do Gray Code por meio da utilização do código binário padrão: AVALIAÇÃO FORMATIVA NOTA Página 6 de 8 Entrada: n, número natural Saída: n-Gray Code Algoritmo: 1º Passo: A partir do código binário padrão, faça: a) inicie o código com 0(zero); b) inverta cada um dos bits cujo próximo bit de ordem mais elevada seja 1 (um); c) avance para o próximo código binário e repita o processo (b). Elabore um programa de computador que seja capaz de receber o valor de n, comprimento em bits do Gray Code, e gerar a sequência de valores binários em Gray Code empregando o algoritmo: a) recursivo b) iterativo 14. A divisão de polinômios é uma importante operação matemática. A seguir apresenta-se um pequeno resumo sobre este assunto. DIVISÃO DE POLINÔMIOS Um polinômio p(x), de única variável x, é expresso por: p(x) = a0.x 0 + a1.x 1 + a2.x 2 + ... + a(n-1).x (n-1) + an.xn com n ∈ Ν e a0, a1, a2, ..., an ∈ ℜ. O grau de um polinômio p(x) é o expoente da maior potência de sua variável x. Por exemplo: o polinômio p(x) = x10 + 5x2 + 6 tem grau 10, já o polinômio p(x) = 3x – 7 tem grau 1. Na situação em que o polinômio p(x) é representado apenas por um número, ou seja, uma constante que não possui variável associada, diz-se que o seu grau é zero. Por exemplo: p(x) = 8 tem grau 0 (zero), pois equivale a escrever p(x) = 8.x0. Há, entretanto, uma exceção, quando p(x) = 0, diz-e que seu grau é -1. O grau de um polinômio p(x) é representado por gr(p). Suponhamos dois polinômios p(x) e q(x) cujos coeficientes são números racionais definidos de forma que p(x) ≠ q(x). Escreva um programa de computador capaz de receber os polinômios p(x) e q(x) e, ao final apresentar a divisão de: a) p(x) por q(x) b) q(x) por p(x) Observação: O usuário informará os coeficientes dos termos de cada polinômio, seguindo ordem estritamente crescente do grau do polinômio. Assim informará: a0, a1, a2, ..., a(n-1) e an AVALIAÇÃO FORMATIVA NOTA Página 7 de 8 de cada polinômio, ou seja, p(x) e q(x). 15. Há um quebra-cabeças denominado Torre de Hanoi. Ele foi inventado pelo matemático francês Edouard Lucas em 1883. Há uma lenda sobre uma imagem num templo vietnamita que apresenta uma grande sala com três hastes verticais presas ao chão. Numa delas há 64 discos de ouro e a tarefa consistia em transferi-las para qualquer uma das duas outras hastes. Os sacerdotes de Hanoi (importante cidade na época), agindo sobre a determinação de uma antiga profecia, moviam os discos de acordo certas regras desde o início dos tempos (criação do universo). As regras eram as seguintes: R1: Apenas um disco pode ser movido por vez; R2: Nunca um disco de maior diâmetro pode ficar sobre um disco de menor diâmetro. Modelo de Torre de Hanoi com 8 discos. De acordo com a lenda quando a movimentação for completada será o fim dos tempos, ou seja, destruição do universo. Pesquise e elabore um programa de computador que empregue uma função recursiva capaz de resolver o problema da Torre de Hanoi para n discos, sendo n fornecido pelo usuário. Observação: Esta lenda possui muitas variações. “A principal enfermidade do homem é a curiosidade inquieta do que não pode conhecer.” Blaise Pascal (1623 – 1662) Matemático e filósofo francês “Não há livro tão ruim que não se possa aprender nele algo de bom.” Plínio, o Jovem (62-114) Escritor Romano