Return to home

12/04/15

1112023 Matemáticas Discretas
Maestría en Ciencias de la Computación 

GRUPO  CMC01
TRIMESTRE 15O

 

Comentarios y sugerencias

cbarron@correo.azc.uam.mx

cbarron99@hotmail.com

NOTAS:

Clases: Lunes, miércoles y viernes de  11:30 - 13:00. Salón: E313.

Calificaciones  alumnos.

PDF UEA MATEMATICAS DISCRETAS PARA LA COMPUTACION

No hay examen final. Revisen el PDF de la UEA.

 

Fechas de examen:

(Pueden traer una hoja carta con un resumen de sus notas como acordeón a mis exámenes)

1er. examen parcial: viernes, 9 de octubre de 2015.

2do. examen parcial:  viernes, 6 de noviembre de 2015.

3er. examen parcial: miércoles, 2 de diciembre  de 2015.

 

Tareas

  1. Fotocopias de las clase 1 y 2. Se entrega el miércoles, 23 de septiembre de 2015 a la hora de entrada de la clase.

  2. En la pág. 2 del libro: Feynman Lectures on Computation (Richard P. Feynman, Addison-Wesley, 1996), Feynman comenta mirar la universalidad de otra forma. En particular concluye: there is no "best" language or alphabet - each is logically universal, and each can model any other.  Aplicando lo visto en clase, su formación y sentido común, desarrolle un ensayo de no mas de dos cuartillas sobre este punto de los lenguajes y los alfabetos tomando como base los párrafos dentro el cuadro de la imagen de la pág. 2. Argumente a favor o en contra con conocimientos (puede consultar cualesquiera publicaciones o con personas) y de ser posible con argumentos cuantitativos, no solo cualitativos. Se entrega el lunes, 28 de septiembre de 2015 a la hora de entrada de la clase.

  3. Primer examen. Se entrega el examen, de portada con sus datos, junto con las hojas de las respuestas engrapadas en mi oficina H116 a mas tardar a las 17:00 el viernes 9 de octubre de 2015.

  4. Leer la lista de ejercicios de conjuntos. Se revisa y resuelve en la clase del viernes, 23 de octubre de 2015.

  5. Ejemplos de ejercicios para el segundo parcial. Vea también los ejercicios del libro Matemáticas Discretas. T. Veerarajan, MC Graw Hill, 2008. Consultar en la biblioteca de la UAM-A.

  6. Lista de ejercicios para el tercer parcial. Contestar 10 ejercicios. Se entregan el lunes, 30 de noviembre de 2015 a la hora de entrada de la clase.

 

 

Bitacora de Clases

  1. Presentación de la importancia de la Matemáticas Discretas. Temas del curso y forma de evaluación.  Acuerdos asesorias por cita. 2 evaluaciones parciales: examen 70% y tareas 40%. Una tercera evaluación: examen 60% y Proyecto con presentación 50%. Escala: NA: [0,6), S: [6,7.5), B: [7.5-8.5) y MB: [8.5,11] .
  2. Definición de Marco Teórico: temas o puntos de vista para el estudio de un tema, concepto, objeto, etc. Definición de Concepto: relación entre representación y significado. Lenguaje desde el punto de vista sintáctico (Computadores): Alfabeto ($ \Sigma $): Conjunto finito de símbolos. Palabra: concatenación finita de símbolos de $\Sigma$. Lenguaje: Conjunto de palabras. Distinción entre uso de una palabra y referencia a una palabra. Lenguaje: Como medio de comunicación de conceptos. Teoría: Definiciones (axiomas) y proposiciones (teoremas). Definición de sistema: Conjunto de elemento con uno o varios objetivos. Problemas de la Filosofía: creación de conceptos y comunicación entre personas.  Se recomienda leer 1, 3  y 4 de los materiales de lectura y referencia.
  3. Repaso introducción a la Lógica simbólica de las proposiciones y predicados. Def. de proposición sencilla. Conectivos: o, y , no, si-entonces. Cuantificadores: para todo, existe. Def. de proposición compuesta. Def. de predicado. Tabla de verdad. Def. de conectivo y ($\wedge$). Def. de conectivo o ($\vee$). Def. de conectivo no ($\rceil $). Ejemplos y notas de las pags. 1-2 del libro Veerarajan. Modelación y técnicas de resolución de problemas. Ejemplo del vuelo cosmico del material 3. A.B.C. de la cibernética, V. Kasatki. Def. de si-entonces ($\Rightarrow$) y discusión de su significado en la generación del conocimiento o de uso en la ciencia. Se deja la tarea 2.
  4. Consulta sobre la tarea 2. Prioridad de las operaciones lógicas. Álgebra de las proposiciones. Ley de dualidad. Equivalencia usando tabla de verdad. Ejemplos y notas de las págs. 2-3 del libro Veerarajan. Introducción a la deducción y al funcionamiento de Prolog.
  5. Discusión de la tarea. Desarrollo del estudio del mejor alfabeto como la representación de estados y bases $f(b)=b^{m/b}$ donde $m>0$ es el número de estados, cuya solución como problema continuo es $b=e$. Acuerdo: escribir un artículo con la discusión de lenguajes (donde no hay una definición de mejor, eficiente o eficaz que sirva universalmente para determinar el "mejor" lenguaje). El artículo amplia y corrige la nota de Feynman, rescata las notas de sus tareas y la explicación de mejor alfabeto. Lo unirán y presentaran un borrador en conjunto. Esta es la revista que sugiero: Revista Ciencias, temática y alcance y guía para autores.
  6. Introducción a la teoría de inferencia, págs. 27 del libro Veerarajan. Modelación en Prolog. Se suspendió la clase por la alarma sísmica. Se acordó  un calendario de 15 días para la primera propuesta.
  7. Estudio de ejemplos en Prolog: Ejemplos: universidades, librería, likes, conjunto, familia, dígrafo.
  8. Teoría axiomática de conjuntos. Lectura: Conjuntos de Paul Halmos. Axioma de extensión y axioma de especificacion. Propiedades, proposiciones, definiciones, aplicaciones, reflexiones y consecuencias. Prop. El conjunto vacío es único. Prop. El Universo de Von Newman genera los números naturales. Paradoja de Russell. Prop. No existe el conjunto universal.
  9. El álgebra de conjuntos como consecuencia de la Teoría axiomática de conjuntos. Ejemplos de demostraciones de las operaciones de conjuntos. Producto cartesiano, n-tuplas (o n-adas), propiedades y características: orden posicional e igualdad. Las cadenas son n-tupas sin los paréntesis y comas. La longitud de una cadena (|$s$|, número de símbolos) y el símbolo nulo ($\epsilon$, |$\epsilon$|=0). Alfabeto ($\Sigma$): conjunto finito de símbolos. Cerradura de Kleene ($\Sigma^\ast $ = $\sum_{i=1}^\infty$ $\Sigma^i$). Nota: $\Sigma^0$=$\{\epsilon\}$. $\Sigma=\{ 1 \} $, $\Sigma^\ast = \{ \epsilon, 1, 11, \ldots \} $.  Lenguajes como subconjuntos de $\Sigma^\ast$. Ejemplos de lenguajes usando el axioma de selección. El conjunto de los pares. 

 

  1. Revisión y entrega de los resultados del primer examen. Principio de inducción matemática. Axiomas de Peano. Principio del buen orden. Ejemplos. Demostraciones de $(3n+1) \leq n^2$ y $\Sigma_{k=0}^n k$ $=$ $ n(n+1)/2$.
  2. Demostraciones usando inducción matemática. Computabilidad de la función factorial.  Principio de inclusión y exclusión.
  3. Conjunto Potencia, relaciones, aplicaciones (bases de datos relacionales y organización de datos). Comentarios de métricas entre relaciones, pruebas estadísticas, minería de datos.
  4. Viernes 23 de octubre de2015. Enfermo de gripe, no hay clase.
  5. Presentación de la tarea 4 por parte de los alumnos. Encuesta del curso.
  6. Introducción a la combinatoria. Regla del producto. Permutaciones (modelos basados en tuplas) y combinaciones (modelos basados en conjuntos).  Fórmula que relaciona las permutaciones y las combinaciones. Triángulo de Tartaglía  (y de Pascal). Identidad de Pascal. En clase use equivocadamente el término función sobre, es solo función a secas. El número de funciones de $A_n$ en $A_n$ son $n^2$. Por tanto el número de relaciones de $A_n$ que no son función es $2^n-n^2.$ Referencia al tema de combinatoria: Capítulo 6 del libro Veerarajan.
  7. Relaciones y funciones. Reflexiva, simétrica, antisimétrica y transitiva. Equivalencia. Orden parcial total. Elemento minimal. Elemento maximal. Función, 1-1, sobre y biyectiva.
  8. Lunes, 2 de noviembre. No hay clase.
  9. Clase de repaso. Digrafos como relaciones. Matriz de adyacencia y representación de grafos, digrafos, relaciones por matrices.
  10. 2do examen parcial.
 

 

  1. Solución de 2do examen parcial, revisión, corrección y entrega de calificaciones.
  2. Int. Teoría de grafos. Grafos y digrafos. Nota los dígrafos los estudiamos como relaciones y sus propiedades. definición de grado. Teorema del hand-shaking y su demostración. Prop. El número de vertices de grado impar es par y su demostración.
  3. Lectura de mi carta de apoyo a la adecuación de la MCC. Definición de grafo conexo. Caminos y circuitos Eulerianos (CE, CRE) y Hamiltoneanos (CH, CRH). Criterios de Euler para caminos y circuitos Eulerianos (teoremas de existencia de complejidad $n^2$. La exploración de caminos y circuitos tiene complejidad $n!$. Ejemplos. Notas acerca de la complejidad y la reducción de la complejidad. Definición y ejemplos de de conjunto dominante como invitación a la plática: Variaciones de la teoría de dominación en gráficas, del martes 17 de noviembre de 2015 a las 13:15 e el salón del edif. HP planta baja.
  4. Lunes 15 de noviembre. Se suspende la clase.
  5. Tipos de grafos y propiedades. Grafos isomorfos. Tipos de grafos y propiedades. Grafo regular, grafo completo, grafo planar. Grafo bipartito. Teorema de Kuratuwski. Aplicaciones y ejemplos.
  6. Lunes, 23 de noviembre de 2015. No hay clase. Los alumnos asisten a la entrega de distinciones académicas.
  7. Conexidad de digrafos. Conexidad fuerte, unilateral y débil. Componentes. Tipos de Árboles. Estructura de datos recursiva de árbol. Árbol binario, balanceado, completo, ordenado. Recorridos de árbol: en-orden, pre-orden y pos-orden. Ejemplos y aplicaciones. Descomposición de imagenes por quad-tree y árboles de sintaxis.
  8. Clase de exposición de los alumnos, repaso y dudas para el 3er. examen parcial.
  9. Presentaciones alumnos. Fin del curso.
  10. Reunión para el proyecto.
  11. Ya tienen su calificación de los exámenes. Falta su proyecto final.

Materiales de lectura y referencias

  1. Teoría intuitiva de los conjuntos. Paul R. Halmos, Ed. CECSA, 1973. Consultar en la biblioteca de la UAM-A.
  2. Matemáticas Discretas. T. Veerarajan, MC Graw Hill, 2008. Consultar en la biblioteca de la UAM-A.
  3. Lectura: La computacion como el quinto pilar
  4. A.B.C. de la cibernética, V. Kasatki.
  5. Liga para conocer y descargar SWI-Prolog.
  6. Prolog, A Tutorial Introduction, James Lu, Jerud J. Mead, Computer Science Department, Bucknell University, Lewisburg, PA 17387.
  7. Tutorial básico de programación en Prolog, "Curso Intermedio de programación en Prolog", Angel Fernández Pineda.

 

 

Cursos

home

This site was last updated 12/04/15