Matemática discreta (MATD)

El objetivo general de la asignatura es poner al alcance del estudiante un conjunto de conceptos y técnicas propios de la matemática discreta y del álgebra que, por su ubicuidad en el mundo de las nuevas tecnologías, son parte de la formación básica de todo ingeniero en informática.

Conocimientos

1. Conocer los principios básicos de enumeración: principio de identidad, del producto, del palomar y de inclusión-exclusión. Conocer el álgebra de las funciones generadoras. Saber expresar recurrencias en términos de funciones generadoras.
2. Conocer la estructura de grafo y dígrafo como modelo matemático y las diferentes formas de dar un grafo.
   Conocer las caracterizaciones de los árboles y la obtención de árboles generadores de coste mínimo.
3. Conocer las caracterizaciones del grafo euleriano y saber obtener un circuito euleriano cuando lo hay. Conocer el problema de los ciclos hamiltonianos y las dificultades asociadas.
4. Conocer los conceptos de flujo, conectividad y aparejamiento y los teoremas esenciales: teorema del flujo máximo/corte mínimo, teoremas de Menger y teorema de Hall.
5. Conocer la estructura de cuerpo de Z_p (los enteros módulo un primero p) y la de anillo de polinomios con coeficientes en Z_p. Saber qué es un polinomio irreducible y conocer el teorema de factorización única. Saber construir cuerpos finitos y conocer la existencia y unicidad.

Habilidades

1. Saber aplicar los principios básicos de enumeración. Saber operar con funciones generadoras. Saber plantear problemas de enumeración en términos de recurrencias. Saber resolver recurrencias empleando funciones generadoras.
2. Saber modelar problemas en términos de grafos y dígrafos. Saber emplear las relaciones que atan los parámetros de un grafo planar para deducir valores de unos parámetros en función de los valores de los otros.Saber calcular el número de árboles generadores de un grafo conexo. Saber aplicar los algoritmos de búsqueda en profundidad y en anchura para obtener árboles generadores. Saber aplicar los algoritmos de Prim y de Kruskal para obtener árboles generadores de coste mínimo.
3. Saber aplicar los algoritmos para obtener un circuito euleriano y un recorrido euleriano. Saber aplicar a ejemplos sencillos algunas condiciones suficientes de hamiltoneidad. Saber operar con ciclos.
4. Saber aplicar el algoritmo de Ford y Fulkerson para obtener un flujo máximo.Saber aplicar los teoremas de Menger y de Hall en situaciones simples.
5. Saber operar en Z_p con p primo, en particular saber calcular inversas.Saber operar con polinomios con coeficientes en Z_p. Saber construir cuerpos finitos.
   
   Saber operar en cuerpos finitos empleando la forma polinómica de sus elementos y empleando logaritmos discretos. Saber operar con polinomios con coeficientes en un cuerpo finito.

Competencias

1. Capacidad para el razonamiento crítico y lógico-matemático
2. Capacidad para aplicar las técnicas para construir demostraciones lógico-matemáticas.
3. Capacidad para transformar enunciados informales a enunciados formales, y al revés.
4. Capacidad para aplicar los conocimientos de matemáticas y lógica a la resolución de problemas.
5. Capacidad de abstracción. Capacidad para enfrentarse a problemas nuevos recorriendo conscientemente a estrategias que han sido tiles en problemas resueltos anteriormente.

Las clases de teoría responden al esquema clásico de clase magistral, eventualmente ayudada por el uso de retroproyector o demostración computacional.Las clases de problemas son participativas, con explicación por parte de los estudiantes de problemas encargados previamente y de discusión colectiva de otros problemas previamente marcados.

La evaluación és preferentemente continua y se basa en las pruebas siguientes

P1: examen de la parte inicial del temario,
P2: examen de la parte intermedia del temario,
P3: examen de la parte final del temario.

La nota final se calcula como sigue: N= 0.2*P1+0.4*P2+0.4*P3 (P1,P2,P3 són notes sobre 10)

Quien no siga la evaluación continua o quiera renunciar a ella tendrá que realizar un examen del temario comleto de la materia. La nota correspondienta a este examen será la nota de ls asignatura. En este caso, el estudiante tendrá que comunicarle al coordinador que renuncia a la evaluación continua, como muy tarde, el último dia de clases del cuatrimestr y por los canales que se publicaran en el Racó.

• Francesc Comelles, Josep Fàbrega, Anna Sànchez, Oriol Serra. Matemàtica Discreta, Edicions UPC, 1994.
• Norman L. Biggs Matemàtica Discreta, Vicens-Vives, 1994.
• Ralph P. Grimaldi Matemáticas Discreta y Combinatoria, Addison Wesley Iberoamericana, 1997.

• Josep M. Brunat Combinatòria i teoria de grafs, Edicions UPC, 1997.
• Joan Trias Matemàtica Discreta. Problemes resolts., Edicions UPC, 2001.
• Jiri Matousek, Jaroslav Nesetril Invitation to Discrete Mathematics, Clarendon Press, Oxford., 1998.
• Kenneth H. Rosen Matemática discreta y sus aplicaciones, McGraw Hill, 2004.

Conocer las operaciones y relaciones con conjuntos: reunión, intersección, diferencia, producto cartesiano, inclusión.Conocer los diferentes tipos de aplicaciones.

Saber contar combinaciones y permutaciones con y sin repetición.

Conocer las propiedades elementales de los números binomiales y saber calcularlos.

Saber calcular el mcd de números enteros y los coeficientes de la identidad de Bezout mediante el algoritmo de Euclides.

Saber calcular productos de matrices y saber calcular determinantes.

La asignatura AL debería ser prerrequisito.