COURSE DESCRIPTION 2015-2016
1. Code: 11639
Name: Graphs, models and applications
--Lecture: 3,00 --Practice: 2. Credits: 4,50 Degree: 156-Bachelor's Degree in Computer Engineering
1,50
Type of Course: Elective
Module: 8-ELECTIVE SUBJECTS Subject: 38-COMPLEMENTARY TRAINING University Center: SCHOOL OF COMPUTER ENGINEERING 3. Coordinator: Jordan Lluch, Cristina Departament: APPLIED MATHEMATICS 4. References Applied and algorithmic graph theory Graph theory : An algorithmic apporach Aplicaciones de la Teoría de Grafos a la vida real (vídeos de los cursos en edX) Aplicaciones de la Teoría de Grafos a la vida real I (curso en edX) Aplicaciones de la Teoría de Grafos a la vida real II (curso en edX) Problemas resueltos de matemática discreta Matemáticas discreta y combinatoria : una introducción con aplicaciones Graph theory and its applications Matemáticas discretas Introducción a la teoría de grafos y sus algoritmos Estructuras matemáticas para la informática II (OCW) Matemática discreta y sus aplicaciones
Gary Chartrand Nicos Christofides Jordán Lluch, Cristina; Conejero Casares, José Alberto J. Alberto Conejero y Cristina Jordán J. Alberto Conejero y Cristina Jordán Félix García Merayo Ralph P. Grimaldi Jonathan L. Gross Richard Johnsonbaugh Cristina Jordán Lluch Cristina Jordán Lluch Kenneth H. Rosen
5. Course Outline La asignatura consta de 6 bloques. En cada uno de ellos se estudia: 1. CONOCIMIENTOS GENERALES DE LA TEORÍA DE GRAFOS 1.1. Revisión de conceptos básicos 1.2. Orientabilidad 1.3. Caminos más cortos 1.4. Árboles 2. EL PROBLEMA DE LA ASIGNACIÓN 2.1 Asignación óptima personas-tareas 2.2 Emparejamientos máx/mín coste 3. REDES 3.1 Flujo máximo cortadura mínima 3.2 Problema multifuente multisumidero 3.3 Problema de distribución 3.4 Problema de flujo máximo con restricción en los vértices 3.5 Problema de flujo máximo con capacidades mínimas 3.6. Problemas de redes espacio-temporales 4. RECORRIDOS ÓPTIMOS EN GRAFOS 4.1. Grafos eulerianos: Problema del cartero chino y sucesiones de De Bruijn 4.2. Grafos hamiltonianos: Problema del viajante de coste bajo 4.3. Código Gray 5. PROBLEMAS DE COLORACIÓN 5.1. Problema de almacenaje y horario 5.2. Coloración de vértices 6. PROBLEMAS DE LOCALIZACIÓN 6.1 Determinación de centros y anticentros 6.2 Determinación mediana y antimedianas
Pag.
1 / 4
Updated: 15/07/15
COURSE DESCRIPTION 2015-2016
6. Recommended Prior Knowledge (11547) Discrete Mathematics (11551) Data Structures and Algorithms (11593) Algorithmics (11650) Algorithm for Problem Solving 7. Student Outcomes
Sí
Control point No
Sí
No
Sí
No
Sí
No
Sí
No
it's worked
Control point No Si
Specific Student Outcomes CB1(G) Poseer y comprender conocimientos en su área de estudio que parten de la base de la educación secundaria general, y se suele encontrar a un nivel que, si bien se apoya en libros de texto avanzados, incluye también aspectos que implican conocimientos procedentes de la vanguardia de dicho campo de estudio. CB4(G) Students should be able to communicate information, ideas, problems and solutions to both a specialised and non-specialised audience. G06(G) Localizar información relevante desde diferentes fuentes e investigar las novedades tecnológicas en su ámbito de trabajo y en áreas afines. G04(G) Razonar de manera abstracta, analítica y crítica, sabiendo elaborar y defender argumentos en su área de estudio y campo profesional. CB5(G) Students must be able to developed those skills needed to undertake further studies with a high degree of autonomy. UPV-Generic Student Outcomes
(02) Application and practical thinking Si (03) Analyzing and solving problems Si - Activities carried out to achieve the student outcome Modelización de problemas reales - Detailed description of the activities Se plantean problemas en contexto real que, tras ser modelizados como un problema de grafos, deben ser resueltos aplicando teoría de grafos. - Assessment criteria Entrega periódicas de ejercicios, lectura y presentación de un artículo científico ya publicado, relativo a la resolución de problemas utilizando teoría de grafos (06) Teamwork and leadership Si No (08) Effective communication Si No (09) Critical thinking Si No (10) Awareness of contemporary problems issues Si Si - Activities carried out to achieve the student outcome Análisis de un artículo científico publicado en los últimos años - Detailed description of the activities Los alumnos deben analizar el trabajo y exponerlo ante sus compañeros y profesores - Assessment criteria Se evalúa el trabajo realizado a partir de la presentación. La nota se obtiene a partir de la opinión del profesor y de los compañeros (coevaluación) (11) Life-long learning Si No (13) Specific tools Si No 8. Syllabus
·
·
· ·
1. 1. CONOCIMIENTOS GENERALES DE LA TEORÍA DE GRAFOS 1.1. Revisión de conceptos básicos 1.2. Orientabilidad 1.3. Caminos más cortos 1.4. Árboles 2. 2. EL PROBLEMA DE LA ASIGNACIÓN 2.1 Asignación óptima personas-tareas 2.2 Emparejamientos máx/mín coste 3. 3. REDES 3.1 Flujo máximo cortadura mínima 3.2 Problema multifuente multisumidero 3.3 Problema de distribución
Pag.
2 / 4
Updated: 15/07/15
COURSE DESCRIPTION 2015-2016
8. Syllabus 3.4 Problema de flujo máximo con restricción en los vértices 3.5 Problema de flujo máximo con capacidades mínimas 3.6. Problemas de redes espacio-temporales 4. 4. RECORRIDOS ÓPTIMOS EN GRAFOS 4.1. Grafos eulerianos: Problema del cartero chino y sucesiones de De Bruijn 4.2. Grafos hamiltonianos: Problema del viajante de coste bajo 4.3. Código Gray 5. 5. PROBLEMAS DE COLORACIÓN 5.1. Problema de almacenaje y horario 5.2. Coloración de vértices 6. 6. PROBLEMAS DE LOCALIZACIÓN 6.1 Determinación de centros y anticentros 6.2 Determinación mediana y antimedianas 9. Teaching and Learning Methodologies UN
LE
SE
PS
LS
FW
CP
AA
CH
NCH
TOTAL HOURS
1
4,00
3,50
--
3,50
--
--
0,50
11,50
21,00
32,50
2
3,00
3,50
--
4,00
--
--
0,50
11,00
22,00
33,00
3
2,00
2,50
--
3,50
--
--
0,50
8,50
17,00
25,50
4
3,50
3,00
--
4,00
--
--
0,50
11,00
22,00
33,00
5
1,50
1,00
--
--
--
--
--
2,50
2,00
4,50
6
1,00
1,50
--
--
--
--
--
2,50
1,50
4,00
TOTAL HOURS
15,00
15,00
--
15,00
--
--
2,00
47,00
85,50
132,50
UN: Unit. LE: Lecture. SE: Seminar. PS: Practical session. LS: Lab sessions. FW: Field work. CP: Computer-mediated practice. AA: Assessment activities. CH: Contact hours. NCH: Non contact hours.
10. Course Assessment Outline (03) (05) (12) (11) (09)
Num. Acts Weight (%)
Achievement tests (multiple choice) Academic studies Coevaluación Observation Project
5 6 1 1 1
20 20 10 20 30
Se introducirán los modelos y las aplicaciones de los mismos. Correspondiente a esta parte habrá 6 trabajos académicos consistentes en la entrega de problemas relativos principalmente a la modelización de situaciones reales. Además se realizarán varias pruebas objetivas tipo test (con poliformat). Las notas correspondientes a las hojas de problemas junto a las notas de las pruebas tipo test constituirán el 40% de la nota final. La nota de observación 20% estará basada en las actividades desarrolladas en clase. Los alumnos desarrollarán individualmente o por parejas un proyecto relacionado con alguno de los modelos vistos durante el curso. Los artículos para el trabajo estarán disponibles para su elección por parte de los alumnos desde las primeras semanas de curso. La evaluación se realizará por el profesorado (30% de la nota) y por el resto de alumnos (10%). En caso de suspender la asignatura, se propondrá al alumno una colección de problemas que reflejen el contenido del curso que deberá devolver resueltos en el plazo de dos días. Los alumnos con dispensa de asistencia realizarán una única prueba de respuesta abierta que aportará el 60% de la nota final. El otro 40% corresponderá a la realización de un proyecto individual cuya evaluación será similar a la del resto de alumnos.
11. Absence threshold Activity
Pag.
3 / 4
Percentage Observations
Updated: 15/07/15
COURSE DESCRIPTION 2015-2016
11. Absence threshold Activity Lecture Theory Laboratory Practical
Pag.
4 / 4
Percentage Observations 40 40
Updated: 15/07/15
