-
Presentación de la UEA y del contenido sintético
con ejemplos: 1. Lenguaje y álgebra de conjuntos. 2. Principios
fundamentales del conteo. 3. El principio de inclusión y exclusión. 4.
Naturales, inducción matemática y recursión. 5. Funciones, relaciones
de orden, relaciones de equivalencia y particiones. 6. Introducción a
la teoría de gráficas.
7. Árboles. (Asistencia 6 de 7).
-
Acuerdos forma de evaluación: Tres parciales y un
examen global. Cada calificación parcial se obtiene del examen
parcial*80%+Tareas*30%+Participación*10%. La calificación de la UEA
corresponde al (promedio+Examen global)/2. Temas de clase: Lenguaje
formal es un conjunto de cadenas o palabras de un alfabeto de símbolos
finito. Concatenación de símbolos, longitud de cadenas, símbolo nulo.
Ejemplo lenguaje binario. Sistema lógico formal: axiomas y predicados.
Ejemplos: x=Mayra, P: _ es humano. P(x) es 1. P(gato) es 0.
-
Acuerdos: el horario de asesoría es el publicado y
se puede concertar cita avisando por correo electrónico. Temas de
clase: Axioma de extensión y Axioma de especificación. Operadores de
pertenencia ($\in$) y subconjunto ($\subset$). Cardinalidad de un
conjunto $|A|$ y el conjunto vacio ($\phi$).
-
Repaso de lógica proposiciones y operadores.
Usando el axioma de especificación se definieron las operaciones de
conjuntos: unión, intersección, complemento y diferencia. Se discutió
la paradoja de Russell: No hay el conjunto universo. Se demostraron la
conmutatividad de la unión y de la intersección de conjuntos, la no
conmutatividad de la diferencia de conjuntos y que el doble
complemento retorna al conjunto original $(A^c)^c$ $=$ $A$
-
Se presento la teoría de conjuntos y
demostraciones de las propiedades del Álgebra de Conjuntos con
las operaciones unión, intersección y complemento (similar al álgebra
de los números reales con $+$ y $\cdot$). Se presento y se dieron
ejemplos de Diagramas de Ven Euler. Se revisaron
los ejercicios de la
tarea 3 y se fijo la fecha de entrega.
-
Se presento la asociatividad de la unión y de la intersección de
conjuntos (que es parte de las propiedades del álgebra de conjuntos).
Producto cartesiano, su representación en el plano cartesiano,
generalización a productos de mas de 2 conjuntos, $A \times A
\cdots\times A$ = $A^n$. Prop. $|A \times B|$ = $|A$ $|B|$.
Conjunto potencia (conjunto que tiene como elemento a todos los
subconjuntos de un conjunto). Caso particular de los conjuntos del
universo de Von Newman y su relación con los números naturales: $|\phi|$
= 0, $| \{ \phi \ } |$=1,$| \{ \phi, \{ \phi \} \ }|$ = 2, $| \{ \phi,
\{ \phi \} , \{ \phi, \{ \phi \} \} \ }|$ = 3, .... Ejemplos de la
potencia de conjuntos de 1, 2, ..., n elementos, para establecer la
fórmula: $|P(\{1,2,...,n\})|$ = $2^n$, mediante el binomio de newton y
los factores del binomio de Newton$.
-
(Lunes 1 octubre). Revisión tarea. Los alumnos participan
presentando una interpretación de los ejemplos de acciones y de la
encuesta de alumnos de los ejercicios de la tarea 3.
Se presenta la operación de proyección y se revisa la notación de los
conjuntos del universo de Von Newman. La función projección
cartesiana y ejemplos de bases de datos relacionales (con base en los
ejercicios 16,17 y 18).
-
Exposición de los alumnos de los ejercicios de la tarea 3.
-
Principio de inducción matemática.
-
Lunes 8 octubre. Se suspende la clase.
-
Principio de inclusión y exclusión. Demostraciones
usando inducción matemática. Introducción a la combinatoria.
Permutaciones con repetición y sin repetición, combinaciones. $P_{k}^{n}$
y $(_{k}^{n})$.
-
Clase de repaso. Entrega de tareas calificadas y
resolución de ejercicios de la
Guía de
ejercicios para el 1er. Examen Parcial.
-
1er. examen
parcial. Se debe entregar de tarea (5) para la siguiente clase.
-
Solución del 1er.
examen parcial.
|
-
Combinatoria. Regla de la suma. Regla del producto. Prop. Las
combinaciones de tamaño $k$ de $n$ objetos están relacionadas con las
permutaciones sin repetición por la expresión: $P_{k}^{n}
/ k! = (_{k}^{n}).$ Ejemplo de probabilidad (de un subconjunto
de 2 de 3 colores) y frecuencia relativa experimental: $P(\{\{A,R\}\})=1/
(_{2}^{3})$ = $1/3$.
-
Exposición de alumnos del ejercicio 6.1 del libro
de Verarajan.Prop. Las posibles permutaciones circulares ($Pc(n)$) de
$n$ objetos están dadas por $Pc(n)=(n-1)!.$ Demostración por
inducción matemática. Tres demostraciones de la identidad de Pascal
$(_{k}^{n+1})=(_{k-1}^{n})+(_{k}^{n})$, por el triángulo de Tartaglia,
por las propiedades de las combinaciones y por álgebra.
-
Identidad de Vandermonde: $(_{k}^{n+m}) = \sum
_{i=0}^k (_{k-i}^{n}) (_{i}^{m}) + \sum _{i=0}^k (_{i}^{n})
(_{k-i}^{m})$. Principio generalizado de la pichonera: $n$ pichones y
$m$ nidos, con $m<n$ entonces al menos uno de los nidos tiene
$[(n-1)/m]+1$ donde $[\cdot]$ menor o igual entero. Demostración por
inducción matemática del principio de inclusión y exclusión.
Demostración por inducción matemática de la fórmula de las
permutaciones con repetición de tamaño $k$ de un conjunto $A$: $|A|^k$.
-
(Lunes 29 de octubre) . Clase de ejercicios
y participación. Los alumnos presentan las demostraciones por
combinatoria o por inducción matemática de la clase anterior o la
solución de alguno de los ejercicios de la tarea 6. Presentaron: Mayra
(ej. 8), Enrique (ej. 1), Gabriel (ej.1) y Francisco (ej.12
incompleto).
-
(Miercoles 31 de octubre) . Clase de ejercicios y
participación. Los alumnos que asistieron y participaron (2 puntos
c/u) fueron Mayra , Enrique y Francisco. Discutimos sobre que un
árbol de decisión sirve para contar los resultados de forma
equivalente a la regla del producto.
-
Definición de árbol y demostración de la
proposición combinatoria: Un árbol de decisión de $k$ alternativas por
cada etapa tiene $k^n$ resultados después de $n$ etapas. Nota: Se
destaco la similaridad con las permutaciones con repetición y que los
árboles de decisión pueden servir para analizar las acciones o
conductas cotidianas para elegir aquellas actitudes y decisiones que
mejoren el desempeño escolar. Asistieron: Mayra , Enrique,
Gabriel, Francisco y Valentino. Participaron: Gabriel (+1) y Valentino
(fallo en su exposición).
-
2do Examen parcial, miércoles 7 de noviembre de 2018.
Ver tarea 7.
-
9 noviembre. No hay clase.
-
Solución del 2do Parcial y participaciones: Mayra(1)
, Enrique (2), Gabriel(1), Francisco(1), Ricardo(1) y Valentino(2).
|
-
Funciones, relaciones, grafos y dígrafos.
Presentación como el estudio de los tipos de asociaciones entre puntos
de un producto cruz. Una función es una relación donde a un punto del
dominio ($D$), le corresponde un único punto del rango ($R$). Una
relación es cualquier subconjunto de $D\times R.$ Problema de los
puentes de Königsberg , o sea de pasar por todos los puentes una sola
vez, modelación y solución de Euler como un grafo. Ejemplos de
dígrafos. Observación: El conjunto de las aristas con dirección (pares
ordenados) de un dígrafo representa una relación. Ver
Tarea 8.
-
Sugerencias para ejercicios 1 y 5. Grafo y Digrafo.
Grado de un vertice. Proposición (Handshaking). Todo grafo $(V, A)$
cumple: $2|A|=\sum_{v\inV} gr(v)$. Proposición. El número de vértices
de grado impar es par. Tipos de grafos: completo ($K_n$),
n-regular, bipartito $(V_1,V_2,A)$.
-
Gráficas planares, propiedades y
aplicaciones. $K_5$ no es planar y así como los $K_n$ con $n \geq 5$.
$K_{3,3}$ no es planar y todo grafo que los contenga (Teorema de
Kuratuwski). Grafos como medio de entender y representar las
relaciones y sus propiedades. Relación reflexiva. Relación Simétrica.
Relación anti-simétrica. Relación Transitiva. Relaciones mas
complejas: Relación de orden parcial: reflexiva anti-simétirca y
transitiva. Relación de orden total: relación de orden parcial y
completa (i.e. sobre todas las parejas del conjunto de la relación).
-
Particiones y relación de
equivalencia: reflexiva, simétrica y transitiva. Prop. Toda partición
o familia de clases de un conjunto inducen una relación de
equivalencia (sobre la pertenencia) y recíprocamente. Representación
de grafos y digrafos e isomorfismo y su relación con álgebra lineal.
Ver tarea 9.
-
Sugerencias para tarea 9. Definiciones y ejemplos de
trayectorias (simples), ciclos (simples) y conectividad (o conexidad)
pags. 387 - 391. Libro Veerarajan. Prop. Si un grafo conexo o
disconexo tiene exactamente dos vértices de grado impar entonces hay
una trayectoria que une a estos vértices. Prop. La potencia $r$ de la
matriz da adyacencia de un grafo, indica en sus entradas el número de
trayectorias distintas de longitud $r$. Asistieron (3): Valentino,
Enrique y Mayra. Faltaron 3.
-
Asistencia completa, Ricardo y Mayra a tiempo. Los
demás llegaron tarde. Todos entregaron tarea. Se resolvieron dudas de
particiones y relación de equivalencia, pag. 74 del libro de texto.
Identificación de tipos de grafos. Camino Euleriano (CaE), circuito
Euleriano (CiE), camino Hamiltoneano (CaH) y circuito Hamiltoneano(CiH).
Notas: 1) Criterio de Euler para la existencia de un CaE. 2) Criterio
de Euler para la existencia de un CiE. Observación si se tiene un CiE
entonces se tiene un CaE, pero no al revés. No hay criterios
semejantes para CaH y CiH, pero los grafos completos tienen $n!$ CiH
que corresponden a las permutaciones sin repetición de sus vértices.
Ejemplos de aplicación: Problema del agente viajero y encontrar
caminos baratos. Problema de Flujo de redes. Esbozo del Algoritmo de
Dikstra y concepto de equilibrio (Nash) en lugar de optimizar.
-
Árboles. Pags. 415 a 421 del libro Veerarajan. Def. de
árbol (alternativa): 1) Existe un único nodo sin padre denominado
raíz. 2) Todos los nodos $\neq$ raíz tienen un nodo padre.
Propiedades. Un árbol no tiene ciclos. Un árbol es conexo. Todo grafo
conexo tiene un árbol de expansión. Un árbol de expansión se puede
construir por el algoritmo de BFS (The breadth-first search
algorithm). Con matriz de costos entre vértices, se tienen los
algoritmos de PRIM (por vertices) y algoritmo de Kruskal (por airistas)
para estimar un árbol de expansión mínimo (en los costos de las
aristas). Ejemplos de árboles y aplicaciones: Árbol de cuatro nodos (quadtree)
para desglose de imágenes en sus subcuadrantes, Árbol binario ordenado
y balanceado, diseño top-down, especificación de un algoritmo por
llaves $\{$ (Branch design). Árbol de notación prefija, etc. La
relación entre número de vértices ($n$) y la altura de un árbol
balanceado o de mínima altura es $\lfloor log_2(n)\rfloor$ donde $\lfloor
\cdot \rfloor$ es la función de truncación. Recorridos en un árbol
binario: inorden, preorden y postorden. Ejemplos de recorridos en
árboles ordenados y balanceados.
-
Clase de ejercicios. Revisión y entrega de la tarea 3
(orden parcial y total, particiones y relaciones de equivalencia) y
ejercicios de árboles. Asistieron todos. Una participación para
Francisco.
-
3er Examen parcial.
-
Resultados y solución del
3er examen parcial.
Se espera que los alumnos participen en la resolución del examen.
|
