CÁTEDRA: MATEMÁTICA DISCRETA

Asignaturas correlativas previas

Matemática Discreta II

OBJETIVOS

Lograr el manejo de la matemática necesaria para un estudiante de ciencias de computación: álgebra, lógica, combinatoria y tratamiento de gráficas.

Desarrollar la madurez matemática para la aplicación en el diseño lógico de circuitos.

Analizar y aplicar algoritmos, tiempo y eficacia de estos.

Manejar el cálculo iterativo y recursivo para sucesiones definidas por recursión.

Aplicar algoritmos para hallar árboles generadores mínimos.

Manejar relaciones y gráficas, sus aplicaciones y propiedades.

Manejar correctamente la combinatoria y sus aplicaciones.

CONTENIDOS

Conjuntos especiales: Unitario,,Universal. Conjunto, elemento, pertenencia, Definición por comprensión y por extensión. Subconjunto, inclusión, igualdad. Intervalos, abiertos y cerrados. Conjunto potencia o partes de un conjunto.

Operaciones entre conjuntos. Unión, Intersección, Complemento, Diferencia simétrica, Diagramas de Venn.

Propiedades de las operaciones entre conjuntos: asociativa, conmutativa, absorbente, distributivas, neutros, idempotencia, De Morgan, involutiva, acotación.

Pares ordenados, producto de conjuntos, n- adas ordenadas.

Sucesiones y cadenas

sistemas numéricos (binario)

2.1 Conjunto parcialmente ordenado. Relación de orden, propiedades reflexiva, antisimétrica y transitiva. Relación de orden parcial estricto propiedad arreflexiva. Diagrama de Hasse. Copo, elemento minimal, maximal. Subcopo, elemento máximo, mínimo, Cotas superior e inferior. Latis, principio de dualidad.

2.2 Ordenes especiales. Orden total, o lineal, cadena, cadena maximal, cadena bien ordenada, orden de archivero, usual y lexicográfico o de archivero.

2.3 Relación de equivalencia, propiedades reflexiva, simétrica y transitiva. Clase de equivalencia, Congruencia módulo-p.

2.4 Relaciones generales, binarias, funciones. Relación inversa. Composición.

2.5 Latis de particiones.

2.6 Sucesiones y notación o-grande. Sucesiones, términos. Polinomios.

2.7 Definiciones Recursivas. (B) Base, y ( R) fórmula recursiva o relación recursiva.

2.8 Relaciones recursivas.

2.9 Definiciones generales de Recursión.

3.1. Técnicas básicas de Conteo. Regla de la unión, Selección con y sin reemplazo. Permutaciones, Combinaciones, Principio de inclusión exclusión. Conteo de particiones ordenadas.

4.1 Notación para algoritmos

4.2 Algoritmos de Euclides

4.3 Algoritmos recursivos

4.4 Complejidad de los algoritmos

4.5 Sistema criptográfico con clave pública RSA

5.1 Gráficas.Vértices, aristas, lazos. Caminos y ciclos, simples. Gráficas conexa, inconexa, bipartita, completa, n-cubos, componentes.

5.2 Ciclos de Euler. Ciclos de Hamilton,

5.3 Subgráficas

5.4 Algoritmo para la ruta mas corta.

5.5 Representaciones de gráficas

5.6 Isomorfismo e invariantes, invalencia, exvalencia, valencia, anti-isomorfismo, autoisomorfismo, regular.

5.7 gráficas con peso. Peso de aristas, peso de camino, peso mínimo. Camino mínimo.

6.1. Propiedades de los árboles. Hojas, Árbol de expansión, árbol de expansión mínimo.

6.2. Árbol dirigido, Raíz, padre, hijos, descendientes, subárbol, árbol m-ario, Nivel, Altura, árbol m-ario pleno o completo, árbol isomorfo.

6.3. Algoritmo de búsqueda de primera profundidad, Definición recursiva de árbol enraizado, altura, Algoritmos preorder, postorder, inorder, treesort, topsort, tree, forest, tree+ y forest+.

6.4. Notación polaca, notación polaca o prefija, notación polaca inversa o postfija, notación algebraica usual o infija.

6.5. Árboles pesados, algoritmo de Huffman, árbol óptimo, código prefijo.

7.1. Introducción informal. Proposición. Verdadera y falsa. Refutar. Contraejemplo.

7.2. Cálculo proposicional. Implicación condicional. Tabla de verdad. Variables. Bicondicional. Tautología. Lógicamente equivalentes. Contrapositiva. Proposición compuesta.

7.3. Cuantificadores. Universal y existencial.

7.4. Cálculo de predicados. Variables lógicas. Proposición compuesta.

7.5. Inducción matemática. Primer y segundo principio de inducción matemática. Principio del buen orden.

7.6. Generalización de la inducción. Principio generalizado de la inducción.

7.7. Álgebra de Boole. Látises algebraicas. Látises distributivas y Booleanas.Redes lógicas. Funciones de Karnaugh.

ESTRATEGIAS METODOLÓGICAS

Clases teóricas: expositivas: se expondrán, aclararán y analizarán los conceptos , que serán ilustrados mediante el análisis y discusión de ejemplos. Trabajando con libro base de Matemáticas Discretas de Johnsonbaugh, y ampliando con otras bibliografías.

Clases prácticas: Resolución de ejercicios y problemas de aplicación: se dedicarán a iniciar al alumno en el planteo y resolución de problemas relacionados con el material estudiado en las clases teóricas. Y para ampliar, rever y aclarar los conceptos introducidos en teoría. Trabajos prácticos que serán discutidos y evaluados, con evaluaciones escritas individuales continuas.

BIBLIOGRAFÍA

MATEMÁTICA DISCRETA Y LÓGICA, Richard Johnsonbaugh.

MATEMÁTICAS DISCRETAS, Kenneth A. Ross y Charles R.B. Wright.

MATEMÁTICA DISCRETA Y LÓGICA, W.K. Grassmann

Otros.

REGULARIDAD

Promoción Directa

Se realizará una evaluación continua y la materia será promocional. La evaluación consistirá en la evaluación continua de los contenidos y trabajos prácticos de los mismos. Un parcial al finalizar el primer cuatrimestre y otro examen a mediados del segundo cuatrimestre de todos los contenidos dictados hasta esa fecha, y finalmente una evaluación global, que deberá aprobar con 60% o más. Las condiciones y nota para promocionar o regularizar la materia serán:

con el 80% de asistencia a clases teóricas y prácticas

concurrencia a los exámenes parciales y global.

La nota final de la materia se conformará de la siguiente manera:5% de asistencia a clases “A”, 15% el promedio de los parciales semanales y trabajos prácticos ”B” ; el 20% por cada parcial “C y D”y 40% el global “E”.

Es decir : 0.05xA + 0.15xB + 0,2(C + D) + 0.40xE, el alumno que de esta manera logre una nota de :

. entre 76% y 100% promociona la materia

. entre 45% y 75% regulariza la materia

. entre 0 y 44% quedará libre y deberá recursar la materia.

CRONOGRAMA