|
Programa CI-7521: Matemáticas para Computación
Objetivo del curso: adquirir destrezas en la manipulación de fórmulas
matemáticas, utilizando una serie de técnicas para resolver problemas.
Las destrezas adquiridas son particularmente útiles en análisis de
algoritmos.
El libro principal de este curso es "Graham, Knuth, Patashnik. Concrete
Mathematics: a foundation
for computer science.", y cito textualmente lo que fundamentalmente
pretende este libro:
" The emphasis is on manipulative technique rather than on existence
theorems or combinatorial reasoning; the goal
is for each reader to become as familiar with discrete operations (like
the greatest-integer function and finite summation) as a student of
calculus is familiar with continuous operations (like the
absolute-value function and infinite integration)"
Objetivos específicos:
- Estudiar las propiedades fundamentales de los
principales coeficientes elementales de conteo que pueden surgir al
considerar conjuntos finitos de configuraciones (objetos
combinatorios), como son: coeficiente binomial, números de stirling,
números de fibonacci, conteo de funciones, etc.
- Técnicas para la manipulación,
el cálculo y la inversión de sumas.
- Técnicas usadas en la manipulación de
ecuaciones de recurrencia (generalmente surgen en análisis de
algoritmos recursivos).
- Elementos matemáticos básicos para el estudio
de la complejidad de algoritmos.
Programa:
- Conjuntos, Relaciones (equivalencia, buen orden, conjunto bien
fundado) 1.
- Funciones, Cardinalidad1.
- Principio de Inducción. Inducción Estructural2 .
- Inducción Noetheriana2. Inducción constructiva 6.
- Teoría de números: Teorema Fundamental de la aritmética 3.
- Funciones piso y techo3.
- Sumas: notación, sumas y recurrencias, manipulación, sumas múltiples,
métodos generales3.
- Sumas y diferencias. Sumas infinitas3,4. Ejemplos de sumas
con piso y techo.
- Coeficientes elementales de conteo. Principios básicos de conteo
4,5.
- Coeficientes binomiales y funciones generatrices3,4.
- Números de Stirling. Números Armónicos3 .
- Números de Fibonacci3.
- Teoría de Inversión5, sección (4.9) de 3.
- Recurrencias. Solución de recurrencias4,6.
- Funciones Generatrices3,4.
- Comportamiento asintótico3,4.
Bibliografía:
(1) Vicente Yriarte. Elementos de teoría axiomática de
conjuntos. Guías de curso U.S.B. 2001.
(2) N.H. Xuong. Mathemátiques discrètes et informatique .
Masson. 1991.
(3) Graham, Knuth, Patashnik. Concrete Mathematics: a foundation
for computer science. Addison Wesley. 1992.
(4) Vicente Yriarte. Elementos de teoría combinatoria. Guías
de curso U.S.B. 1996
(5) Claude Berge. Principles of Combinatorics. Academic Press.
1971.
(6) Gilles Brassard, Paul Bratley. Fundamentals of Algorithms.
Prentice Hall. 1996.
(7) Thomas Cormen, Charles Leiserson, Ronald Rivest. Introduction
to Algorithms . McGraw Hill. 1997.
Material:
-
Libro sobre Conjuntos y Relaciones (Vicente Yriarte)
-
Elementos de Teoría Combinatoria (Vicente Yriarte)
- Inducción Estructural
y Noetheriana (N.H. Xuong) en francés
- Teoría de
Inversión (Claude Berge)
- Coeficientes Elementales de
Conteo (Claude Berge)
- Otros
Libros
Actividades en los trimestres:
|
