Pedro Reyes Columé   E.S. Ingeniería Informática Av. Reina Mercedes s/n (despacho B2.64) 41012 Sevilla   +34 95 455 4384 +34 95 455 7878 preyes@us.es   Doctor en Matemáticas por la Universidad de Sevilla y Profesor Titular de Escuela Universitaria, perteneciente al Departamento de Matemática Aplicada I de la Universidad de Sevilla.

(Página actualizada el día 15/02/2012)

 

DOCENCIA	INF. GENERAL	INVESTIGACIÓN
Matemática Discreta Fundamentos de la Geometría Computacional Tutorías		Tesis doctoral Enlaces de interés Curriculum Vitae

 

ESTALMAT                                          

Participo, como profesor invitado, en el proyecto Estalmat. En el presente curso académico imparto, conjuntamente con el profesor Alberto Márquez, una sesión conjunta para Veteranos de 1º y 2º sobre Geometría Computacional.

Puedes descargarte los archivos cdy correspondientes a los ejercicios propuestos.

 

DOCENCIA                                          

En la actualidad imparto docencia en la Escuela Superior de Ingeniería Informática. Concretamente de las asignaturas de  Matemática Discreta en el grupo 2 del curso segundo del grado de Ingeniería Informática-Tecnologías Informáticas, en la asignatura Herramientas de la Matemática Discreta para la Informática en el Master Universitario en Matemática Computacional y Fundamentos de la Geometría Computacional, asignatura optativa de tercer curso de la titulación de Ingeniería Técnica en Informática de Gestión (plan 97).

Tutorías

El horario de tutorías para el segundo cuatrimestre será el siguiente:

 

Volver al principio de la página

Matemática Discreta (MD-II-TI)

La asignatura Matemática Discreta es una asignatura obligatoria del grado en Ingeniería Informática-Tecnologías Informáticas de la Universidad de Sevilla y es impartida durante el primer cuatrimestre en el curso segundo. 

En el presente curso académico 2011-12 soy coordinador de la asignatura e imparto la teoría del grupo 2 y las prácticas de los  grupos 1 y 3 de dicha titulación.

Los alumnos de la asignatura disponen de la siguiente información:

También puedes consultar la página de la asignatura.    

Novedades y anuncios

• (04-Oct.2011): Se actualiza el horario de tutorías para este primer cuatrimestre..

En esta sección iré incluyendo aquellos anuncios que afectan a la docencia de la asignatura.

Volver al principio de la página

 

Desarrollo de las clases

En esta sección iré incluyendo una especie de diario de lo que vayamos haciendo en las clases del GRUPO 2. 

• Jueves, día 19-01-2012:
  • Segundo examen parcial.
• Martes, día 17-01-2012:
  • Examen de prácticas.
• Jueves, día 12-01-2012:
  • Tema 7: Flujos en redes:
    • Repaso de lo estudiado el jueves 22-12.
    • Algoritmo del máximo flujo-mínimo corte. Camino f-aumentante.
    • Ejercicios 128 y 122 del boletín.
• Martes, día 10-01-2012:
  • Práctica 5.
• Jueves, día 22-12-2011:
  • Tema 7: Flujos en redes:
    • Introducción.
    • Teorema del máximo flujo-mínimo corte. Camino f-aumentante.
• Martes, día 20-12-2011:
  • Subgrupo 2.1: Práctica 4.  
  • Subgrupo 2.2: Ejercicios del Tema 6:  Coloración de grafos.
    • Ejercicios 98, 99, 100, 103, 114, 109, 111, y 112 del boletín.
• Jueves, día 15-12-2011:
  • Tema 4: Planaridad.
    • Propiedades. Fórmula de Euler. Test de planaridad.
    • Teorema de Kuratowski.
    • Ejercicios 69, 73, 74, 75, 76 y 79  del boletín.
• Martes, día 13-12-2011:
  • Subgrupo 2.2: Práctica 4.  
  • Subgrupo 2.1: Ejercicios del Tema 6:  Coloración de grafos.
    • Ejercicios 98, 99, 100, 103, 114, 109, 111, y 112 del boletín.
• Jueves, día 1-12-2011:
  • Tema 6:  Coloración de grafos.
    • Coloración de aristas. Índice cromático. Teorema de Vizing.
    • Emparejamientos.
    • Ejercicios 104,  120, 122 y 124 del boletín.
• Martes, día 29-11-2011 (Sustituido por Clara Grima):
  • Tema 6:  Coloración de grafos.
    • Coloración de vértices. Número cromático. Acotación del número cromático.
    • Caracterización de grafos bipartitos.
• Jueves, día 24-11-2011:
  • Tema 5:  Transversalidad en grafos.
    • Definiciones de camino y ciclo hamiltoniano. Grafos Hamiltonianos..
    • Condiciones necesarias de grafos hamiltonianos. Condición suficiente de grafo hamiltoniano: Teorema de Dirac.
    • Condiciones necesarias de grafos que admiten un camino hamiltoniano. Condición suficiente de existencia de tal camino.
    • Ejercicios 83, 84, 85, 89 y 90 del boletín.
• Martes, día 22-11-2011:
  • Primer examen parcial.
• Jueves, día 17-11-2011:
  • No hay clase por Asamblea de alumnos.
• Martes, día 15-11-2011:
  • Práctica 3.
• Jueves, día 10-11-2011:
  • Tema 3:  Árboles.
    • Ejercicios 34, 51, 36, 58 y 50 del boletín.
  • Tema 5:  Transversalidad en grafos.
    • Definiciones de recorrido y circuito eulerianos. Grafos Eulerianos. Teorema de Euler.
    • Multigrafos, pseudografos y digrafos eulerianos.
• Martes, día 8-11-2011 (Sustituido por Víctor Álvarez):
  • Ejercicios del Tema 3:  Árboles.
    • Ejercicios 64, 37, 40, 55 y 61-a del boletín.
• Jueves, día 3-11-2011:
  • Tema 3:  Árboles.
    • Algoritmo de Tarjan para las componentes fuertemente conexas de un digrafo.
    • Árbol recubridor de peso mínimo. Algoritmo de Kruskal.
    • Camino mínimo: Algoritmo de Djkstra.
    • Ejercicios 63 del boletín.
• Lunes, día 31-10-2011:
  • Tema 3:  Árboles.
    • Árboles m-arios
    • Árboles de decisión.
    • Árboles recubridores. Algoritmos DFS y BFS.
    • Ejercicios 42, 44, 48, 53, 54 y 56 del boletín.
• Jueves, día 27-10-2011:
  • No hay clase por Asamblea de alumnos.
• Martes, día 25-10-2011:
  • Tema 3:  Árboles.
    • Introducción.
    • Caracterización.
    • Árboles enraízados.
    • Ejercicio 35 del boletín.
• Jueves, día 20-10-2011:
  • Tema 2:  Conectividad en grafos.
    • Ejercicios 20-a, 21, 23, 25,  29 y 31 del boletín.
• Martes, día 18-10-2011:
  • Práctica 2.
• Jueves, día 13-10-2011:
  • Tema 2:  Conectividad en grafos.
    • Conexión en digrafos. Distintos tipos de conexión. Componentes fuertemente conexas.
    • k-conexión por vértices. Vértices de corte.
    • k-conexión por aristas. Aristas puente.
    • Teoremas de Menger y Whitney.
    • Ejercicios 24, 26 y 28 del boletín.
• Martes, día 11-10-2011:
  • Subgrupo 2.1: Práctica 1.
  • Subgrupo 2.2: Ejercicios del Tema 1:  Introducción a la teoría de grafos.
    • Ejercicios 1, 3, 4, 5, 6 7, 8, 12 y 14-a,b,c,d del boletín.
• Jueves, día 06-10-2011: ,
  • Tema 1:  Introducción a la teoría de grafos.
    • Ejercicios 14-e,f y 18 del boletín.
  • Tema 2:  Conectividad en grafos.
    • Motivación.
    • Definiciones previas: Camino, ciclo, etc.
    • Concepto de conexión. Grafos conexos. Componentes conexas.
• Martes, día 04-10-2011:
  • Subgrupo 2.2: Práctica 1.  
  • Subgrupo 2.1: Ejercicios del Tema 1:  Introducción a la teoría de grafos.
    • Ejercicios 1, 3, 4, 5, 6 7, 8, 12 y 14-a,b,c,d del boletín.
• Jueves, día 29-09-2011: ,
  • Tema 1:  Introducción a la teoría de grafos.
    • Formas de representar un grafo.
    • Operaciones con grafos.
    • Isomorfismo de grafos. Havel-Hakimi.
• Martes, día 27-09-2011:
  • Presentación de la asignatura.
  • Introducción de la asignatura. Breve reseña histórica de la teoría de grafos. Aplicaciones de la teoría de grafos.
  • Tema 1: Introducción a la teoría de grafos.
    • Conceptos básicos. Distintos tipos de grafos.
    • Valencia. Grafos notables.

Volver al principio de la página

Material didáctico     

Aquí colocaré enlaces a distinto material útil para los alumnos.

 

Volver al principio de la página

 

Guía docente

La guía docente de la asignatura contiene toda la información necesaria sobre metodología, contenido, evaluación, etc de la misma. 

Volver al principio de la página

INVESTIGACIÓN

En estas líneas podréis descubrir las líneas de mi actividad investigadora.

Tesis Doctoral

El trabajo elaborado para optar al título de Doctor en Matemáticas, titulado "Problemas de etiquetado: Complejidad Computacional", fue dirigido por los doctores Dña. M.Angeles Garrido Vizuete  y D. Alberto Márquez Pérez. La defensa del mismo la llevé a cabo el día 29 de noviembre de 2002.

Con la ortogonalidad como ingrediente básico y motivados por su evidente aplicación, en este trabajo nos sumergimos en el camino del etiquetado de mapas (map labeling). Dada la necesidad que surge en el diseño de redes de metro nos centramos en la manera de asociar etiquetas rectangulares a puntos (estaciones) situados sobre una recta (línea de metro). Siguiendo distintos modelos de etiquetado se han resuelto casos de manera eficiente aplicando algoritmos polinomiales, pero también han surgido otros de naturaleza NP-dura. 

Ante esta situación surge la necesidad de obtener aproximaciones de la solución óptima, por lo que hemos aplicado distintas técnicas de aproximación a problemas de conexiones ortogonales y de etiquetado, cuya característica común es la ortogonalidad pero con la diferencia en el "tipo" de NP-completitud que presentan. Entre los métodos aplicados podemos destacar los buenos resultados que ofrecen los algoritmos genéticos.

Volver al principio de la página

Enlaces de interés

A continuación ofrezco algunos enlaces y alguna información que pueden ayudar a profundizar en los temas fundamentales de mi línea de investigación.

• Etiquetado

 

• Geometría Computacional

• Matemática Discreta

• Representación de grafos

• Teoría de la Computación

 

Volver al principio de la página

Curriculum Vitae

• Capítulos de libros

  • Cover Contact Graphs. Lecture Notes in Computer Science, Springer-Verlag, v. 4875, pp 171-182, 2008. (Con M.N. Atienza, N. de Castro, C. Cortés, M.A. Garrido, C.I. Grima, G. Hernández, A. Márquez, M.A. Moreno, M. Nollenburg; J.R. Portillo, J. Valenzuela y A. Wolff).
  • Labeling Subway Lines. Lecture Notes in Computer Science, Springer-Verlag, v. 2223, pp 649-659, 2001. (con M.A. Garrido, C. Iturriaga, A. Márquez, J.R. Portillo y A.Wolff). 
  • Taller de Matemágica. Suma. Federación Española de Profesores de Matemáticas, v. 10, pp 62-67, 1992. (Con I. Escudero, M.L. Martín, C. Rodriguez y A. Sanz)

 

• Comunicaciones y ponencias en congresos internacionales

  • Cover Contact Graphs. The 15th International Symposium on Graph Drawing (GD 2007). Sydney (Australia) 2007. (Con M.N. Atienza, N. de Castro, C. Cortés, M.A. Garrido, C.I. Grima, G. Hernández, A. Márquez, M.A. Moreno, M. Nollenburg, J.R. Portillo, J. Valenzuela y A. Wolff).
  • Separating blue points with red segments. Kyoto International Conference on Computational Geometry and Graph Theory (KyotoCGGT 2007). Kyoto (Japón) 2007. (Con C. Cortés, D. Garijo, M.A. Garrido, C.I. Grima, A. Márquez, M.A. Moreno, J.R. Portillo, M.P. Revuelta, R. Robles, M.E. Suárez, J. Valenzuela y M.T. Villar).
  • Cover Contact Graphs. 22nd European Workshop on Computational Geometry (EWCG 06). Delfos (Grecia) 2006. (Con M. Abellanas, M.N. Atienza, N. de Castro, C. Cortés, M.A. Garrido, C.I. Grima, G. Hernández, A. Márquez, M.A. Moreno, J.R. Portillo, J. Valenzuela y M.T. Villar).
  • Orthogonal Bend Wiring with Prefixed Vertices. International Congress of Mathematicians (ICM 2002). Beijing (R.P.China) 2002. (Con M.A. Garrido, A. Márquez y J.R. Portillo).
  • Labeling Subway Lines. International Symposium on Algorithms and Computation (ISAAC'01), Christchurch, (New Zealand) 2001. (Con M.A. Garrido, C. Iturriaga, A. Márquez, J.R. Portillo y A.Wolff). 
  • Labeling points on a line. Euroconference on Discrete and Algorithmic Geometry. Anogia, Creta (Grecia) 2000.
    (Con M.A. Garrido, A. Márquez y J.R. Portillo).
  • Drawing Constrained Rectangles in the Plane without Intersections. Joint Meeting of the Third World Multiconference on Systemics, Cybernetics and Informatics (SCI'99) and the Fifth International Conference on Information Systems Analysis and Synthesis (ISAS'99), Orlando, (USA) 1999. (Con M.A. Garrido, A. Márquez y J.R. Portillo).
  • Orthogonal triangles in the plane. 15th European Workshop on Computational Geometry (15th EWCG). Juan-les-Pins (Francia) 1999. (Con M.A. Garrido, A. Márquez y J.R. Portillo).

 

• Comunicaciones y ponencias en congresos nacionales

  • Experiencia piloto en la implantación del ECTS en la Introducción al Cálculo Infinitesimal en I.T.I. Gestión.  XIII Congreso Universitario de Innovación Educativa en las Enseñanzas Técnicas. Gran Canaria, 2005 . (con V. Álvarez y M.D. Frau).
  • k-Factores en nubes bicromáticas. XII Encuentros de Geometría Computacional (EGC 07). Valladolid, 2007. (con M.N. Atienza, C. Cortés, D, Garijo. M.A. Garrido, C.I. Grima, A. Márquez, M.A. Moreno, J.R. Portillo, R. Robles, M.T. Villar, M.E. Suárez y J. Valenzuela).
  • NP-completitud fuerte y débil en problemas de etiquetado. III Jornadas de Matemática Discreta y Algorítmica (III JMDA). Sevilla, 2002. (con M.A. Garrido, A. Márquez y J.R. Portillo).
  • Conexiones ortogonales con vértices prefijados. III Jornadas de Matemática Discreta y Algorítmica (III JMDA). Sevilla, 2002. (con M.A. Garrido, A. Márquez y J.R. Portillo).
  • Complejidad computacional para problemas de etiquetado y conexiones ortogonales. II Encuentro Andaluz de Matemática Discreta (II EAMD). Castillo de Los Molares, Sevilla, 2001. (con M.A. Garrido, A. Márquez y J.R. Portillo).
  • Etiquetado de puntos alineados.. IX Encuentros de Geometría Computacional (EGC'01). Gerona, 2001. (con M.A. Garrido, C. Iturriaga, A. Márquez, J.R. Portillo y A. Wolff).
  • Etiquetado de puntos alineados.. II Jornadas de Matemática Discreta  y Algorítmica (II JMDA). Palma de Mallorca, 2000. (con M.A. Garrido, C. Iturriaga, A. Márquez y J.R. Portillo).
  • Trazados ortogonales en el plano. Resultados generales y aproximación por algoritmos genéticos. II Jornadas de Matemática Discreta y Algorítmica (II JMDA). Palma de Mallorca, 2000. (con M.A. Garrido, A. Márquez y J.R. Portillo).
  • Triángulos Ortogonales en el plano. VIII Encuentros de Geometría Computacional (EGC'99) . Castelló, 1999. (con M.A. Garrido, A. Márquez y J.R. Portillo).
  • Aplicación de algoritmos genéticos al problema Max-SBW. I Encuentro Andaluz de Matemática Discreta. La Rábida (Huelva), 1999. (Con M.A. Garrido, A. Márquez y J.R. Portillo).
  • Drawing Constrained Rectangles in the plane without intersections. I Encuentro Andaluz de Matemática Discreta. La Rábida (Huelva), 1999. (Con M.A. Garrido, A. Márquez y J.R. Portillo).
  • Recursos metodológicos en la enseñanza de las Matemáticas. I Jornadas para la REnovación Metodológica en EEMM. 1987. (Con A.J. Pérez).
  • Resolución de problemas (Ecuaciones y Sistemas). II Jornadas Andaluzas sobre Didáctica de las Mátemáticas (Un encuentro con Iberoamerica). 1987. (Con I. Álvarez, I. Escudero, A.J. Pérez, C. Rodríguez, A. Rubio y L. Vidal).
  • Geometría en primero de BUP (Ecuaciones y Sistemas). II Jornadas Andaluzas de Profesores de Matemáticas. 1986. (Con I. Álvarez, I. Escudero, A.J. Pérez, C. Rodríguez, A. Rubio y L. Vidal).
  • Probabilidad en segundo de BUP. II Jornadas Andaluzas de Profesores de Matemáticas. 1986. (Con I. Álvarez, I. Escudero, A.J. Pérez, C. Rodríguez, A. Rubio y L. Vidal).

 

• Grupos de investigación

En la actualidad pertenezco a los siguientes grupos de investigación:

• Optimización de Redes de Interconexión (BFM2001-2474)-ORI. Ministerio de Ciencia y Tecnología.
• Matemática Discreta: Teoría de Grafos y Geometría Computacional (FQM-164). Junta de Andalucía.

Volver al principio de la página