- Presentación curso, objetivos y forma de
evaluación. Ejemplos de proyectos de computación y su relación
con los objetivos y temas de la UEA. Acuerdos (con base en las
modalidades de evaluación): 3 exámenes parciales por el 90% y 20% de
tareas. Escala: (0,6)-NA, [6,7.5)-S, [7.5-8.5)-B y [8.5,11]
MB. Clase 1.
-
Clase 2. Teoria de conjuntos y consecuencias.
- Clase 3. Álgebra de conjuntos para las
operaciones: unión, interseción, complemento. Leyes de Morgan,
Diagramas de Ven Euler, diferencia de conjuntos, diferencia simétrica
de conjuntos. Producto cruz y proyección. El modelo relacional de Cod,
como un ejemplo de la Teoría de Conjunto. Ejemplo de la Base
relacional Empleado, Departamento y Empleado_depto.
- Tarea 2, desarrollada en clase. Int. Lógica
Símbolica. Proposiciones por constantes o por notación funcional.
Operadores y ($\vee $) ,o ($\wedge$) , not ($\lnot$), tablas de
verdad, equivalencia ($\equiv $).
- Si-entonces. Equivalencia. Reflexión del ide la
inferecnia o de las deducciones cientificas de la ciencias, leyes.
- Entonces ($ \Rightarrow $). Ejercicios del A.B.C.
de la cibernética: la tripulación de una nave.
-
Inferencia. Ejemplos.
Versión Tex.
- Prolog.
SWI-Prolog.
Ejemplo 1,
ejemplo 2 y
ejemplo 3.
- Viernes 6, no hay clase.
- Scientific WorkPlace. Trabajos complemento del
primer parcial: 1) ejemplo de una base de datos
relacional, 2) Notas de Lógica y 3) ejemplos programas en Prolog.
- Miércoles 11 de febrero. Inducción Matemática.
Teoría y ejemplo.
- Principio de inclusión y exclusión. Tarea:
Demostración por el Principio de Inducción Matemática.
- Lunes 16 de febrero. Ejemplos de Inducción
Matemática y Principio de Inclusión y Exclusión.
-
|
- Demostración por Inducción Matemática del Principio de Inclusión y
Exclusión. Introducción a la combinaciones. El número de combinaciones
o subconjuntos de k elementos o eventos de un conjunto de eventos de n
elementos está dado por la fórmula: $ \left( \begin{array}{c} n \\ k \end{array}
\right) =\frac{n!}{\left( n-k\right) !k!}. $
- Permutaciones con repetición y sin repetición. $k! \left( \begin{array}{c} n \\ k \end{array}
\right)$ $ =$ $ P_{k}^n$. Permutación circular. Triángulo de Tartaglia.
$ \left( \begin{array}{c} n \\ k \end{array}
\right)$+ $ \left( \begin{array}{c} n \\ k+1 \end{array}
\right)$ $ =$ $ \left( \begin{array}{c} n+1 \\ k+1 \end{array}
\right)$. Número de aristas de un grafo completo.
- Ejercicios.
- Introducción a las Relaciones y Funciones como subconjuntos de
tuplas de un producto cruz.
- Función inyectiva (1-1), suprayectiva (sobre), biyectiva, inversa
de una relación y composición de relaciones. Ejemplos de
identificación de funciones, relaciones, construcción de la gráfica de
la función (tuplas (x,f(x)).
- Propiedades elementales de relaciones: Reflexiva,
simétrica, antisimetríca y transitiva. Relaciones complejas: igualdad,
relación de equivalencia (particiones) y relación de orden parcial y
total. Representación por digrafos de relaciones.
- Grafos y digrafos. Ciclo y camino Euleriano,
condiciones de Euler. Digrafos, clausura, conexidad, grado, matriz de
incidencia. Relación de orden parcial y total como digrafos, relación
de equivalencia como digrafo y organización de datos.
- Estudio de Grafos completos. Tabla de ciclos y
caminos Eulerianos, Hamiltoneanos. Prop. K$_n$ tiene (n-1)! ciclos
Hamiltoneanos, n! caminos Hamiltoneanos.
- Teorema del Hand-Shaking. Estudio de los grafos
regulares. Para grafos regulares de orden 2. Tabla de ciclos y caminos
Eulerianos, Hamiltoneanos. Prop. R$_{n,2}$ =(V,A) conexo tiene
|A|=|V|. ¿Los grafos R$_{6,3}$ conexos son isomorfos?.
- Grafos planos. Grafos bipartitos. Identificación
de grafos y propiedades. Teorema de Kuratowski para grafos planos.
- No hubo alumno. Llegó muy tarde.
|
- Árbol. Proposición. Un grafo es un grafo conexo sin ciclos.
Nomenclatura: raíz, nodos internos, nodos hojas, altura y tipo de
árbol. Pág. 415, Veerarajan.
- Proposición. Un árbol de n vertices tiene n-1 aristas. Prop. La
altura de un arbol de k-hijos lleno y balanceado de n vertices es la
parte entera de $log_{k}(n)$.
- Alumno, avisa que no puede asistir.
- Árbol binario completo. Prop. Un árbol binario completo tiene un
número impar de vértices, n, y el número de hojas es $(n+1)/2$.
- Desarrolla en casa. Árboles binarios ordenados y tipos de
recorridos.
- Presentación de grafos y árboles por parte del alumno.
- Deficiente presentación de árboles binarios ordenados.
- No hay clase lunes 30 de marzo. Estaré en sesión del Consejo
Divisional.
- Miércoles 1 de abril. Presentación del tema de la 3era parte del
curso. Se repetirá la presentación por deficiencias en la preparación.
- Miércoles 8 de abril. Presentación del tema de la 3era parte del
curso. Árbol binario ordenado. 3 tipos de recorridos. Prop. Todo
árbol binario completo tiene grad(r)=2 y el resto de sus vértices,
grad(v)=1 o 3. Prop. La complejidad de buscar un elemento en un árbol
binario ordenado completo balanceado de $n$ vértices es $ log_2(n) $.
Determinar la complejidad de obtener la lista ordenada de los
elementos de un árbol binario ordenado completo balanceado de $n$
vértices, o sea, la complejidad de un recorrido recursivo en-orden.
|
