Materia	Carrera	Plan	Año	Periodo
() GRAFOS Y COMBINATORIA I	LIC.CS.COMP.	32/12	2025	1° cuatrimestre

Docente	Función	Cargo	Dedicación
PASTINE, ADRIAN GABRIEL	Prof. Responsable	P.Tit. Exc	40 Hs

La teoría de grafos y la combinatoria son ramas fundamentales de la matemática discreta con profundas conexiones en la informática teórica y aplicada. Este curso propone un enfoque matemático riguroso para el estudio de estas áreas, centrándose en la formulación y demostración de resultados fundamentales, así
como en su aplicación al análisis y diseño de algoritmos.

Este curso está dirigido a estudiantes con conocimientos previos en algoritmos y complejidad, brindándoles una perspectiva más formal y abstracta de los problemas combinatorios y su resolución. El objetivo es fortalecer su capacidad de razonamiento matemático y su habilidad para modelar y analizar estructuras discretas con rigor y profundidad.

Este curso tiene como objetivo proporcionar a estudiantes de la Licenciatura en Computación un marco teórico sólido en grafos y combinatoria, complementado con aplicaciones prácticas en problemas computacionales. Se abordarán técnicas avanzadas de conteo, generación y búsqueda de estructuras combinatorias, teoría de grafos y sus aplicaciones en problemas computacionales. A lo largo del curso, los estudiantes explorarán métodos matemáticos para modelar problemas discretos y analizar su complejidad.

Unidad 1, Generación de objetos combinatorios elementales: Generación Combinatoria. Subconjuntos, orden lexicográfico y códigos de gray. Ordenes en k-subconjuntos. Permutaciones.


Unidad 2, Generación de objetos combinatorios avanzados: Particiones enteras. Particiones de conjuntos, números de Bell y de Stirling. Árboles etiquetados. Familias de Catalan.


Unidad 3, Algoritmos de backtracking: Generación de todas las cliques. Estimación de tamaño de árbol de backtrack. Cobertura exacta. Funciones acotadoras. Ramificación y acotación.


Unidad 4, Búsqueda heurística: Estrategias para algoritmos heurísticos, hill-climbing, recocido simulado, búsqueda tabú, algoritmos genéticos. Particiones uniformes de grafos. Sistemas de triples de Steiner. Problema de la mochila. Problema del Viajante de comercio.


Unidad 5, Grupos y Simetría: Grupos. Grupos de Permutaciones. Orbitas de subconjuntos. Representantes de cosets. Orbitas de k-uplas. Generación de objetos con automorfismos.


Unidad 6, Computación de isomorfismos: Invariantes. Certificados: árboles, grafos, podados con automorfismos. Isomorfismos de otras estructuras.

Se contarán con 6 trabajos prácticos, uno por cada unidad. Los mismos incluyen tanto ejercicios teóricos (demostración de propiedades, cálculo de complejidad) como prácticos (implementación de algoritmos, búsqueda, enumeración y generación de estructuras combinatorias dadas).

Para regularizar el curso el/la estudiante debe:
- entregar en tiempo y forma y aprobar los trabajos prácticos,
- aprobar un examen integrador o alguna de las 2 recuperaciones, con una nota no menor a seis puntos sobre un total de 10.
- haber asistido al menos al 60% de las clases

Para promocionar el curso el/la estudiante debe cumplir con:
- las condiciones de regularización,
- haber asistido al menos al 80% de las clases y
- aprobar los trabajos prácticos y el examen integrador con nivel superior o igual a siete puntos sobre un total de diez.

El seguimiento continuo de los/las estudiantes que cursan se realiza mediante la observación e interacción sistemática durante las clases prácticas , la evaluación de los prácticos y la evaluación final integradora.

La evaluación final integradora está basada en un esquema de coloquio, tomando como línea base de construcción del mismo el resultado de los trabajos prácticos de aula, junto con la demostración de resultados vistos en el transcurso de la materia.

Los estudiantes tienen una recuperación adicional en cada instancia de evaluación tal como lo regula la normativa vigente.

Exámenes libres según lo dispuesto por Art. 27 de la Ord. CS 13/03.

En el caso que un/a estudiante rinda libre, lo cual es admitido en el curso, debe presentar al equipo de cátedra los mismos prácticos de aula, de laboratorio y de campo que se exigen en la cursada normal, previamente al examen final integrador.

[1] Kreher, D. L., & Stinson, D. R. (1999). Combinatorial algorithms: generation, enumeration, and search. ACM SIGACT News, 30(1), 33-35.
[2] Kocay, W., & Kreher, D. L. (2016). Graphs, algorithms, and optimization. Chapman and Hall/CRC.

[1] Marcus, D. A. (2020). Graph theory (Vol. 53). American Mathematical Soc..
[2] Gross, J. L., Yellen, J., & Anderson, M. (2018). Graph theory and its applications. Chapman and Hall/CRC.
[3] Loehr, N. (2017). Combinatorics. Chapman and Hall/CRC.
[4] Charalambides, C. A. (2018). Enumerative combinatorics. Chapman and Hall/CRC.
[5] Gallian, J. (2021). Contemporary abstract algebra. Chapman and Hall/CRC.

Este curso tiene como objetivo proporcionar a estudiantes de la Licenciatura en Computación un marco teórico sólido en grafos y combinatoria, complementado con aplicaciones prácticas en problemas computacionales. Se abordarán técnicas avanzadas de conteo, generación y búsqueda de estructuras combinatorias, teoría de grafos y sus aplicaciones en problemas computacionales. A lo largo del curso, los estudiantes explorarán métodos matemáticos para modelar problemas discretos y analizar su complejidad.

Unidad 1, Generación de objetos combinatorios elementales.
Unidad 2, Generación de objetos combinatorios avanzados.
Unidad 3, Algoritmos de backtracking.
Unidad 4, Búsqueda heurística.
Unidad 5, Grupos y Simetría.
Unidad 6, Computación de isomorfismos.

Ante cualquier eventualidad comunicarse con el docente a agpastine@unsl.edu.ar