• Descripción

Enfoque conceptual y relación con el resto del plan de estudios

Esta asignatura fundamenta muchos de los procesos directamente implicados en la Ingeniería de Informática, tanto con respecto al software como al hardware, desde el estudio de las estructuras de la información hasta la construcción de circuitos y el uso más eficiente de estas estructuras; incluso puede proporcionar herramientas para conocer sus límites. De hecho, el origen y el desarrollo de esta nueva rama matemática ha ido siempre ligado a la evolución de la informática y, por eso, su mutua dependencia no es casual.

• Información previa a la matrícula

Es muy conveniente haber cursado de forma reciente los cursos de matemáticas correspondientes a Bachillerato o nivel equivalente. En caso de que no sea así, se aconseja cursar previamente el curso de Iniciación a las Matemáticas para Ingenierías que ofrece la UOC.

Se aconseja cursar Fundamentos de programación antes de esta signatura.

• Objetivos

Globalmente, los objetivos básicos que se pretenden alcanzar son los siguientes:

1.     Entender los siguientes principios básicos de la combinatoria: principio de la adición, principio de la multiplicación, principio de las cajas y principio de inclusión-exclusión. Saber aplicarlos correctamente.

2.     Reconocer cuando un tipo de muestra es ordenada y utilizar los recursos adecuados para hacer el recuento.

3.     Reconocer cuando un tipo de muestra no es ordenada y utilizar los recursos adecuados para hacer el recuento.

4.     Reconocer los problemas de distribuciones y particiones donde pueden utilizarse los números multinomiales y resolverlos con su ayuda.

5.     Identificar la función generatriz de un problema combinatorio y resolverlo con su ayuda.

6.     Saber reconocer los problemas que admiten una formulación recursiva y una resolución a través de las ecuaciones recurrentes.

7.     Entender el concepto de algoritmo para resolver un problema y saber calcular su complejidad.

8.      Entender el concepto de grafo y modelar ciertas situaciones con grafos.

9.      Identificar los grafos más habituales y describir sus características fundamentales.

10.  Saber aplicar los algoritmos de exploración de un grafo.

11.  Entender la noción de conectividad y aplicarla correctamente.

12.  Saber calcular las distancias dentro de un grafo con la ayuda de los algoritmos adecuados.

13. Saber caracterizar los árboles y, específicamente, los árboles con raíz. Saber aplicar los algoritmos de determinación de un árbol generador minimal.

14.  Identificar los grafos eulerianos y hamiltonianos y caracterizarlos.

15.  Entender el problema del viajante. Conocer y saber aplicar el algoritmo de resolución aproximada de este problema.

Los objetivos de cada módulo se encuentran en el material asociado a la asignatura.

• Contenidos

MÓDULOS	DESCRIPCIÓN
Módulo 1	Combinatoria. Muestras ordenadas.
Módulo 2	Combinatoria. Muestras no ordenadas.
Módulo 3	Números multinomiales. La técnica de las funciones generatrices.
Módulo 4	Ecuaciones recurrentes. Complejidad computacional.
Módulo 5	Fundamentos de grafos.
Módulo 6	Recorridos y conectividad.
Módulo 7	Árboles.
Módulo 8	Grafos eulerianos y grafos hamiltonianos.

• Lista de los materiales de los que dispone la asignatura

• Materiales