Matemáticas computacionales y teoría de la computación

DATOS GENERALES

Código ICCD224
Pensum 2020
Horas semanales 12
Tipo Obligatoria
Asignaturas pre-requisitos Programación I ICCD144
Asignaturas co-requisitos Ninguna
Unidad de organización curricular Básica

RESULTADOS DE APRENDIZAJE

De conocimiento
Conocer los conceptos y estructuras de matemáticas discretas, utilizados en sistemas computacionales. Conceptualizar los fundamentos teóricos de la ciencia de la computación.
De destrezas Aplicar el razonamiento lógico y matemático en la solución de problemas prácticos. Usar las estructuras discretas para el diseño de soluciones a problemas computacionales. 
De valores y actitudes Fomentar la solidaridad, la responsabilidad y la ética profesional.

CONTENIDO

Capítulo 1 Conjuntos y Lógica
  1. Sistema de numeración y aritmética binaria;
  2. Conjuntos;
  3. Proposiciones;
  4. Reglas de inferencia, y
  5. Cuantificadores.
Capítulo 2 Funciones, Secuencias y Relaciones
  1. Funciones;
  2. Strings y Secuencias; y
  3. Relaciones.
Capítulo 3 Métodos de Conteo
  1. Principios básicos de conteo;
  2. Permutaciones;
  3. Combinaciones;
  4. Permutaciones y Combinaciones generalizadas;
  5. Coeficientes binomiales y el principio del palomar, y
  6. Principio de la inducción matemática.
Capítulo 4 Grafos y Árboles
  1. Conceptos básicos sobre grafos;
  2. Ciclos de Hamilton y el problema del vendedor;
  3. Tipos de grafos;
  4. El camino más corto de un grafo;
  5. Conceptos básicos sobre árboles binarios y de expansión, y
  6. Isomorfismo de grafos y árboles.
Capítulo 5 Autómatas finitos
  1. Lenguajes formales;
  2. Autómatas finitos determinísticos;
  3. Autómatas finitos no determinísticos;
  4. Conversión NFA-DFA;
  5. Intersección de autómatas finitos;
  6. Autómatas finitos probabilísticos, y
  7. Cadenas de Markov.
Capítulo 6 Lenguajes regulares
  1. Lenguajes Regulares;
  2. Gramáticas regulares;
  3. Expresiones regulares formales, y
  4. Expresiones regulares en lenguaje de programación (PCRE).
Capítulo 7 Lenguajes libres de contexto
  1. Lenguajes libres de contexto;
  2. Autómatas de pila;
  3. Gramáticas libres de contexto, y
  4. Lenguajes ambiguos.
Capítulo 8 Máquinas de Turing
  1. Introducción a las Máquinas de Turing;
  2. Máquinas de Turing como reconoceres de lenguajes;
  3. Máquinas de Turing como transductores;
  4. Complejidad de tiempo, complejidad de espacio e intractabilidad;
  5. Introducción a la decibilidad, y
  6. Introducción a la reducibilidad.

Back to top