Cursos

Home

1112033 Matemáticas Discretas 

GRUPO  CCB81

TRIMESTRE 13O

Comentarios y sugerencias

cbarron@correo.azc.uam.mx

cbarron99@hotmail.com

1. Presentación curso, objetivos y forma de evaluación. Acuerdos: Tarea 1. 3 exámenes parciales por el 80% y 20% de tareas, proyectos, reportes y participación. $ P_p=(P_1+P_2+P_3)/3 $, $ T=(C_1+C_2+...+C_m)/m $, Antes global: $ C_P=P_p*80% + T*30% $. Ex.Global (corto y largo, si reprobaste parciales). Calificación Final = $ (C_p+E_g)/2 $. Escala: (0,6)-NA, [6,7.5)-S, [7.5-8.5)-B y [8.5,11] MB.

2.  Introducción a la Lógica. Teoría intuitiva de conjuntos (Lectura: Conjuntos de Paul Halmos). Objetivo dar los elementos para realizar la Tarea 2. Resumen clase.

3. Operaciones de Lógica, silogismo clásico. Axioma de extensión y axioma de especificación. Pertenencia $ \in $, subconjunto de $ \subset$, Igualdad de conjuntos $A=B$ si y solo si $A \subset B$ y $ B \subset A$.  Universo de Von Newman, Paradoja de Russell. Reglas de Morgan: $ \rceil (P \vee  Q) \equiv \rceil P \wedge \rceil Q $, $ \rceil (P \wedge  Q) \equiv \rceil P \vee \rceil Q $, verificación por tabla de verdad.

4. Operador de equivalencia ($ \equiv$). Teoría de Conjuntos. Axiomas de extensión, axioma de especificación y Lógica (Cálculo de enunciados). Reglas de Morgan para Conjuntos: $ ( A\cup B) ^{c}=A^{c}\cap B^{c}$, $ ( A\cap B) ^{c}=A^{c}\cup B^{c}$. Verificación de $ ( A\cup B ) ^{c}=A^{c}\cap B^{c}$ por igualdad de conjuntos, es decir probando i)  $\left( A\cup B\right) ^{c}\subset A^{c}\cap B^{c}$, ii) $A^{c}\cap B^{c}\subset \left( A\cup B\right) ^{c}$. Producto cruz $A\times B=\left\{ \left( a,b\right) | a\in A, b\in B\right\} $, pares ordenados, tuplas, $A\times A\times A=A^{3}$.

5. Ejemplos de Teoría de Conjuntos y Lógica. Lista de ejercicios. No entregaron los reportes en clase. Los reportes que me dejaron por debajo de mi puerta no corresponden con el nivel de calidad y conocimiento de la estudiantes de la UAM. Ejemplo de un reporte de tarea (Ejercicios de la clase 5).

6. Resolución de los ejercicios de la tarea.

7. Repaso: Formulación simbólica de enunciados (ejemplo en Prolog libreria.pl) , esquemas de deducción (demostración, deducción). Principio de Inducción Matemática (PIM).

8. Ejemplos de aplicación del Principio de Inducción Matemática. Repetir ejemplo 0+1+...+m = m(m+1)/2. Universo de Von Newman y los números naturales. Demostración de la cardinalidad de la unión de conjuntos (Principio de inclusión y exclusión).

9. Ejemplos de aplicación del Principio de Inducción Matemática. Principio del buen orden. Ejercicios de PIM.

10. Huelga.

11. Examen.

1. Revisión de la 1era etapa del curso.
2. Principios fundamentales del conteo. Principio de la producto. Fórmula de permutaciones (corresponden a k-tuplas) sin repetición de n objetos de tamaño k: $P_k^{n} = \frac{n!}{(n-k)!}.$ Fórmula de combinaciones (corresponden a conjuntos de cardinalidad k) de n objetos de tamaño k: $ \left(\begin{array}{c} n \\ k \\ \end{array}\right)= \frac{n!}{(n-k)!k!}.$ Relación entre combinaciones permutaciones sin repetición de n objetos de tamaño k:  $ \left(\begin{array}{c} n \\ k \\ \end{array}\right)=P_k^{n} / k!. $ Relación entre combinaciones: $ \left(\begin{array}{c} n+1 \\ k \\ \end{array}\right) = \left(\begin{array}{c} n \\ k-1 \\ \end{array}\right) +\left(\begin{array}{c} n \\ k \\ \end{array}\right).$ Identificación entre los coeficientes del binomio de Newton y la fórmula de las combinaciones.
3. Principio de la Pichonera. Permutaciones circulares. Ejemplos.
4. Relaciones. Funciones y relaciones. Ejemplo del problema del número de no funciones, numero de funciones inyectivas, y el número de funciones entre  conjuntos de tres elementos. Resultado generalizado para conjuntos de $n$ elementos: $ 2^{n*n} > n^n $ ¿porqué?.
5. Propiedades de las relaciones. 1) Reflexiva, 2) simétrica, 3) transitiva. Relación de equivalencia (cumple ser reflexiva, simétrica, transitiva). Familias de clases de conjuntos.
6. Para cualquier conjunto $A$, toda relación de equivalencia de $A$ induce una familia de clases de $A$ y recíprocamente. (Organizar datos es importante, ¿porqué?)
7. Relación de orden no estricto: reflexiva, antisimétrica y transitiva (como $ \leq $), de orden estricto: irreflexiva, asimétrica y transitiva (como $ < $), parcial y total. Digrafo como relaciones, diagrama de un digrafo. Diagrama Hassa. Elemento minimal, elemento maximal de un orden. La inclusión $ \subset $ como relación de orden no estricto total.
8. Ejemplos de relaciones de orden, relaciones de equivalencia y de familias de clases de conjuntos.
9. Composición de relaciones. Ejercicios del 2do parcial.
10. 2do examen parcial.
11. (Viernes 18, octubre) Solución 2do parcial.
     

1. (Lunes 21 de octubre) Recursión. Funciones recursivas primitivas (FRP).
2. (Miércoles 23 de octubre) No hay clase.
3. Función Total, Función parcial. Ejercicios. (FRP). Conceptos: Robustez, eficiencia y computabilidad.
4. FRP, Computabilidad y Solubilidad. Ejemplos sencillos para la determinación de problemas no computables y no solubles. $ 1 + \frac{1}{2}+\frac{1}{3}+\cdots $ (serie divergente) y $ e=\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots $ (serie convergente a $e$ base de los logaritmos naturales). Árbol como estructura recursiva, recorridos (en pseudo código): pre_orden, post_orden y en_orden. ¿porque el recorrdio de un árbol binario ordenado es ineficiente? ¿Explicar porqué la búsqueda en de un árbol binario ordenado y balanceado es eficiente?
5. Introducción y resultados básicos de Teoría de Gráficas. (relacionandolo con eficiencia y solubilidad) Digrafo, Grafo, Grafo asociado a un digrafo, conexidad (fuerte, débil para digrafos), camino, camino simple, circuito simple, T. Handshaking (demostración por inducción), grado de un vértice, camino y circuitos Eulerianos y Hamiltoneanos, Criterio de Euler para Circuito Euleriano, Criterio de Euler para Camino Euleriano. Tipos de grafos: regulares y planares. Ejercicios.
6. Grafos regulares, planares, Teorema de Kurawtowski, grafos completos, grafos bipartitas, representación matricial e isomorfismos entre grafos y digrafos. Ejercicios.
7. Ejercicios y dudas.
8. 3er examen parcial. Viernes 8 de noviembre.
9. 11 de noviembre, resolución y entrega de exámenes.