Download programa de

Pontificia Universidad Católica Argentina
“SANTA MARÍA DE LOS BUENOS AIRES”
Facultad de Ciencias Fisicomatemáticas e Ingeniería
PROGRAMA DE MATEMATICA DISCRETA
324
INGENIERIA INFORMATICA -2008
1.- Números naturales y enteros
1.1 Números Naturales
Principios de inducción matemática y de buena ordenación.
1.2 Números Enteros
Dominios de integridad. Divisores de cero y ley de cancelación. Propiedades de orden.
Divisibilidad. Divisores enteros de 1. Enteros asociados. Algoritmo de división de
enteros o algoritmo de Euclides. Números primos. Función de Euler.
Máximo común divisor y mínimo común múltiplo. Teorema fundamental de la
aritmética. Análisis de la complejidad del algoritmo de Euclides.
1.3 Relaciones de recurrencia
Relaciones de recurrencia homogéneas y no homogéneas, lineales y no lineales de
primero y de segundo órdenes. Resolución: método de la función generadora
de Taylor. Ejemplos de algoritmos recursivos y análisis de su complejidad.
2.- Anillos y aritmética modular
Estructura de anillo: definición, ejemplos y propiedades. Homomorfismos e
isomorfismos de anillos. Enteros módulo n. Congruencias: definición, propiedades y
teoremas relativos. Clases residuales. Teorema de Fermat. Generalización de Euler.
Aplicación de la noción de congruencia a la recuperación de información.
3.- Funciones generadoras y representaciones asintóticas
3.1 Funciones Generadoras
Definición y propiedades. Operaciones: combinaciones lineales. Producto por potencias.
Producto de Cauchy. Derivación e integración.
Números armónicos: propiedades. Estimación y constante de Euler. Números y
polinomios de Bernoulli.
3.2 Representaciones asintóticas
Definición de orden. Propiedades y teoremas relativos.
4.- Algebras booleanas y funciones de conmutación
Estructura de un álgebra booleana, definiciones. Propiedades y teoremas relativos.
Funciones de conmutación: formas normales conjuntiva y disyuntiva. Compuertas
AND, OR, NOT. Expresiones booleanas. Circuitos combinatorios y síntesis.
Redes de compuertas: sumas minimales de productos y diagramas de Karnaugh.
5.- Teoría de grafos y Algoritmos en redes.
Definiciones: arcos, ramas o ejes, matriz de adyacencias o de incidencia nodoarco.
Caminos simples y compuestos, orientación. Cadenas. Redes.
Pontificia Universidad Católica Argentina
“SANTA MARÍA DE LOS BUENOS AIRES”
Facultad de Ciencias Fisicomatemáticas e Ingeniería
Definiciones, propiedades y ejemplos de árboles. Árboles con raíz. Matrices asociadas y
triangulación inferior. Teoremas relativos. Modelos matemáticos y algoritmos.
Aplicaciones algorítmicas: Algoritmos de Kruskal y Prim. Algoritmos para la
optimización de la programación en redes: máximo flujo-mínimo corte y de
descomposición (out-of-kilter).
6.- BIBLIOGRAFIA
[1] Discrete Mathematics with algorithms - Michael O.Albertson - Joan P.
Hutchinson - John Wiley & Sons - 1988
[2] Matemáticas discreta y combinatoria - Ralph P. Grimaldi - Addison Wesley
Iberoamericana - 1985
[3] The art of computer programming - Vol.I - Donald E. Knuth - Addison Wesley
Publishing Company – 1973
[4] Concrete Mathematics - A Foundation for Computer Science - GrahamKnuth - Patashnik - 1994
[5] Álgebra para informáticos - Telma Caputti - Universidad Austral - 1996
[6] Matemática Discreta - Telma Caputti - Universidad Austral - 1997