Aspectos Teóricos da Computação I

 

Ementa

Teoria dos conjuntos. Relações. Funções. Indução. Estruturas algébricas. Reticulados. Álgebra Booleana. Noções de grafos.

 

Objetivos

Conhecer os principais conceitos matemáticos e computacionais envolvidos no desenvolvimento de um raciocínio lógico para a resolução de problemas. Ser capaz de aplicar o raciocínio lógico através dos conceitos estudados.


Conteúdo Programático

Parte I – Teoria dos conjuntos. (aulas: 01|08)

  • Introdução e conceitos básicos de Teoria dos Conjuntos:

    • Conjuntos / Pertinência;

    • Alguns conjuntos importantes;

    • Conjuntos finitos e infinitos;

    • Alfabetos, palavras e linguagens;

    • Subconjunto e igualdade de conjuntos;

    • Conjuntos nas Linguagens de Programação.

  • Diagramas de Venn;

  • Paradoxo de Russell;

  • Operações não-reversíveis: união, intersecção;

  • Operações reversíveis: complemento, conjunto das partes; produto cartesiano, união disjunta;

  • Relação entre lógica e álgebra de conjuntos;

  • Álgebra de conjuntos nas Linguagens de Programação;

  • Álgebra de conjuntos e Teoria da Computação.

Parte II – Álgebra Booleana. (aulas: 04|05|06|07)

  • Operações Booleanas;

  • Conjunção / Disjunção / Negação;

  • ou Exclusivo;

  • Implicação / Igualdade;

  • Expressões Booleanas;

  • Transformações.

Parte III – Relações (aulas: 09e10|16).

  • Relação;

  • Endorrelação como Grafo;

  • Relação como Matriz;

  • Relação dual e composição de relações;

  • Tipos de relações: funcional e injetora, total e sobrejetora, monomorfismo e epimorfismo, isomorfismo.

Parte IV – Funções (aulas: 17|18).

  • Funções parciais;

  • Composição de funções parciais;

  • Autômato finito como função parcial;

  • Função total / Função dual;

  • Composição de funções;

  • Construções matemáticas como funções.

    Parte V – Indução.

  • Cardinalidade de Conjuntos:

    • Cardinalidade finita e infinita;

    • Conjunto contável e não-contável;

    • Cardinal do conjunto de todos os problemas solucionáveis.

  • Principio da indução matemática;

  • Prova indutiva;

  • Segundo principio da indução matemática.

    Parte VI – Estruturas algébricas.

  • Operações binárias;

  • Propriedades das operações binárias;

  • Grupóides, semigrupos, monóides, grupos;

  • Homomorfismos;

  • Categorias.

    Parte VII – Reticulados.

  • Limitantes de conjuntos parcialmente ordenados;

  • Reticulados:

    • como relação de ordem;

    • como álgebra.

  • Tipos especiais de reticulados:

    • Reticulado distributivo;

    • Reticulado limitado;

    • Reticulado complementado.

Parte VIII – Noções de grafos.
  • Introdução à Teoria dos Grafos;

  • Tipos de Grafos:

    • Grafo orientado e sem orientação;

    • Grafo conexo e desconexo;

    • Grafo cíclico e acíclico.

  • Alguns problemas em Grafos.

 

Bibliografia Básica

MENEZES, Paulo Blauth. “Matemática Discreta Para Computação e Informática.” Bookman. 3 ed. 2010;

HALMOS, Paul R. “Teoria Ingênua dos Conjuntos.” Ciência Moderna. 1 ed. 2001;

NETO, Paulo Oswaldo Boaventura. “Grafos: Teoria, Modelos e Algoritmos.” Edgard Blucher Ltda. 4 ed. 2009.

 

Bibliografia Complementar

DOMINGUES, Hygino; IEZZI, Gelson. “Álgebra Moderna.” Atual. 4 ed. 2003;

KNUTH, Donald E. “The Art of Computer Programming, Volume 1: Fundamental Algorithms.” Addison-Wesley. 3rd ed. 1997.

 

Listas de Exercício

Lista 01 - Raciocínio lógico;

Lista 02 - Teoria dos Conjuntos e Lógica;

Lista 03 - Avaliação complementar (Extra);

Lista 04 - Teoria de Grafos;

Lista 05 - Capítulos 04 ao 08.

 

Critérios de Avaliação da Aprendizagem

Avaliações

  • A1 – Avaliação teórica.

    • Data - 28 de Setembro;

    • Pontuação: 0 a 10 pontos;

  • A2 – Avaliação teórica.

    • Data - 31 de Outubro;
    • Pontuação: 0 a 5 pontos;

  • A3 – Avaliação teórica.

    • Data - 07 de Dezembro;
    • Pontuação: 0 a 10 pontos;

  •   T1 – Trabalho sobre Grafos.

    • Data - 04 de Novembro;
    • Pontuação: 0 a 5 pontos;

  • LE – Listas de exercícios.

    • Realizadas ao fim de cada tópico de estudo;

    • Pontuação: 0 a 10 pontos.

A nota final (NF) será calculada da seguinte forma:

  • NF = (A1 + A2 + A3 + T1) * 0,3 + (LE) * 0,1

Página principal


CEUNES - Centro Universitário Norte do Espírito Santo
Rodovia BR 101 Norte, Km. 60, Bairro Litorâneo, CEP 29932-540, São Mateus – ES, Tel.: +55 (27) 3312-1511
http://www.ceunes.ufes.br