Modelos de la teoría de grafos aplicados a problemas de competiciones de programación

Abstract

[EN] The subject of Algorithms for Problem Solving of the degree of Computer Science Bachelor’s Degree of the ETSINF is geared towards the solution of programming challenges that are usually taken from programming competitions, such as the Southwestern Europe Regional Contest (SWERC), where students from the ETSINF have been regularly participating for the last years. The solution of such a problem is obtained by building a suitable mode for it, finding the optimal solution via this model, and being able of programming it without bugs in a short period of time. The skill on the solution of these problems is very much taken into account in recruiting processes of big technological companies such as Google, Apple, Yahoo, Microsoft or Facebook. We show a collaboration between two subjects of this degree: Algorithms for Problem Solving (CP) and Graphs, models, and applications (GMA). This collaboration was proposed by students who had taken both subjects simultaneously. The goals consist on redirect part of the contents of GMA to the analysis of models that usually appear in this type of problems, and to facilitate that students can face this challenges. The methodology consists on raising several problems from the point of view of both subjects. The first impressions concerning the innovation are positive

[ES] La asignatura Competicion de Programacion del Grado de Ingeniera Informatica esta orientada a la resolucion de desafos de programacion quese suelen proponer en competiciones como la Southwestern Europe RegionalContest (SWERC), en la que alumnos de la ETSINF llevan participandoasiduamente durante los ultimos a~nos. Para obtener la solucion deun problema de este tipo se necesita hacer una modelizacion adecuada delmismo, as como hallar una solucion optima por medio del modelo y sercapaz de programarla sin errores en un corto espacio de tiempo. La habilidaden la resolucion de dichos problemas se tiene muy en cuenta en losprocesos de seleccion de personal de grandes compa~nas tecnologicas comoGoogle, Apple, Yahoo, Microsoft o Facebook.Mostramos una colaboracion entre dos optativas de este grado: Competicion de Programacion (CP) y Grafos, Modelos y Aplicaciones (GMA).Esta colaboracion fue propuesta por alumnos que cursaban ambas asignaturassimultaneamente. Los objetivos consisten en reorientar parte de loscontenidos de GMA al analisis de modelos que suelen aparecer con frecuenciaen problemas de competiciones de programacion, facilitando aslos estudiantes para estos afrontar estos desafos. La metodologa consisteen plantear varios problemas desde la optica de ambas asignaturas. Lasprimeras valoraciones de la innovacion son positivas.