Ementa

Objetivos

A primeira parte da disciplina tem por objetivo ajudar o estudante em sua transição de uma matemática do ensino médio, que consiste em resolver problemas em contextos concretos e por meio de métodos bem definidos, para uma matemática mais madura, na qual ele será capaz de escrever demonstrações e fornecer contraexemplos. O objetivo da segunda parte é apresentar os conceitos de conjuntos, relações, combinatória, teoria dos números e grupos, que são pedras fundamentais da Ciência da Computação. Noções de criptografia concluem a disciplina com o intuito de mostrar aos estudantes a íntima relação entre matemática superior e aplicações computacionais.

Ementa

Provas. Conjuntos. Relações. Combinatória. Teoria dos números. Grupos.

Conteúdo Programático

• 1. Provas:

     1. 1. definição, teorema e prova;

        2. contraexemplo;

        3. redução ao absurdo (reductio ad absurdum);

        4. princípio da indução finita.

  2. Conjuntos:

• • • 1. noções primitivas e definições:

         1. igualdade de conjuntos;

         2. subconjuntos;

      2. quantificadores: existe, para todo;

      3. operações com conjuntos:

         2. 1. união, interseção e diferença;

            2. complementar e conjunto potência.

• 3. Relações:

• • • 1. propriedades;

      2. relações de equivalência e partições;

      3. produto cartesiano;

      4. relação inversa e composição de relações;

• • 1. funções.

1. Combinatória:

   1. permutações e combinações:

      1. permutações simples;

      2. combinações simples;

      3. permutações circulares;

      4. permutações com elementos nem todos distintos;

      5. permutações completas;

      6. permutações caóticas;

   2. princípio da inclusão-exclusão;

   3. principio das gavetas de Dirichlet (ou da casa dos pombos);

   4. números binomiais:

• • 1. números binomiais;

    2. triângulo de Pascal;

    3. binômio de Newton.

1. 5. Teoria dos números:

      2. 1. divisão;

         2. primos;

         3. máximo divisor comum;

         4. aritmética modular;

         5. pequeno teorema de Fermat;

         6. teorema do resto chinês;

         7. fatoração.

   6. Grupos:

• • • 1. grupos e isomorfismos de grupos;

      2. subgrupos;

      3. homomorfismo, isomorfismo e automorfismo.

1. 7. Aplicação:

• • • 1. criptografia de chave pública.

Bibliografia Básica

• 1. SCHEINERMAN, Edward R. Matemática Discreta – Uma Introdução. Trad. Alfredo Alves de Farias. 2 ed. São Paulo: Cengage, 2010.

  2. CARVALHO, Paulo C. P.; MORGADO, Augusto C. O.; PITOMBEIRA, João B.; FERNANDEZ, Pedro. Análise Combinatória e Probabilidade. 6 ed. Coleção do Professor de Matemática. Rio de Janeiro: SBM, 1997.

Bibliografia Complementar

1. KURTZ, David C. Foundations of Abstract Mathematics. New York: McGraw-Hill, 1992.

2. LOVÀSZ, L.; PELIKÁN, J.; VESZTERGOMBI, K. Matemática Discreta. Trad. Ruy de Queiroz. Coleção Textos Universitários. Rio de Janeiro: SBM, 2005.