Usuario:Ltaravilse/Programación competitiva

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
Campeonato abierto de programación Yandex.Algorithm,22 de agosto, 2013.

La programación competitiva es un deporte mental en el que normalmente se compite por Internet o una red local, y consiste de participantes intentando escribir un programa de computadora según especificaciones pedidas por un enunciado. La programación competitiva es reconocida y apoyada por muchas de las compañías de software más importantes del mundo, como Google, y Facebook. Hay muchas organizaciones que organizan competencias de programación regularmente.

Una competencia de programación implica generalmente un organizador escribiendo un conjunto de problemas algorítmicoslógicos o matemáticos para que los participantes (quiénes pueden variar en número de decenas a varios miles) escriban un código de computadora capaz de solucionar cada uno de los problema, que suelen ser presentados mediante la descripción de una situación de la vida real. La forma de evaluar a los competidores consiste generalmente en ejecutar los programas que estos envían al jurado durante la competencia, y comparar su solución en distintos casos de prueba (armados por el jurado) con la solución que desarrolla el jurado de la competencia previo a la misma. Existen distintas formas de puntuar estos códigos, que pueden o no considerar muchos factores como la dificultad del problema, el tiempo que el participante tarda en escribir una solución correcta (ya sea desde que empieza la competencia o desde que empieza a leer el enunciado del problema) o la cantidad de casos de prueba que son resueltos de manera correcta en los casos de competencia con puntajes parciales, aunque en la mayoría de las ocasiones, el puntaje es otorgado únicamente cuando el problema es resuelto correctamente para todos los casos de prueba.

Historia[editar]

Una de las competencias de programación más antiguas y prestigiosases la ACM-ICPC [1]​, la cuál comenzó en la década de 1970, y ha crecido hasta llegar a 88 países en su edición 2011 [2]​. El interés por la programación competitiva ha crecido extensamente desde el 2000, lo cual está fuertemente conectado con el crecimiento de la Internet, medio por el cuál se desarrollan la mayoría de estas competencias.

Descripción[editar]

El objetivo de la programación competitiva es escribir un código fuente de computadora capaz de solucionar un problema dado. Una mayoría vasta de los problemas que aparecen en estas competencias son matemáticos o lógicos en naturaleza. Generalmente pertenecen a alguna de las siguientes categorías: combinatoria, teoría de números, teoría de grafos, geometría, análisis de cadenas y estructuras de datos. Existen también competencias donde los problemas pertenecen al ámbito de la inteligencia artificial.

Más allá de la categoría del problema, generalmente el proceso de resolver un problema está dividido en dos etapas: construir un algoritmo eficiente, e implementar dicho algoritmo eficientemente en un lenguaje de programación, el cuál puede variar según la competencia (la mayoría de las competencias permiten más de un lenguaje de programación). Estas son las dos habilidades que más se evalúan en este tipo de competencias.

En la mayoría de las competencias, el juzgado es automático y por computadoras, a las que se conoce generlmente como jueces. Cada solución entregada por un participante es corrida en una máquina juez contra un conjunto de casos de prueba (generalmente no disponibles para los participantes durante la competencia). Estas computadoras (jueces) suelen ser supervisadas por un jurado integrado por una o más personas, que es quien se encarga de elaborar los enunciados, las soluciones oficiales, y los casos de prueba para los problemas de la competencia. Algunas competencias sólo requieren que el participante entregue la salida que produce su programa al ser ejecutado con datos de entrada provistos por el jurado.

Competencias notables[editar]

Hay dos tipos de formatos de competición: competencias cortas y competencias largas. Cada ronda de una competencia corta dura comunmente entre 1 y 5 horas. Las competencias largas pueden durar entre unos cuantos días a unos cuantos meses.

Competencias cortas[editar]

  • ACM-ICPC - Una de las competencias más viejas, para estudiantes universitarios que compiten en equipos de 3 personas representando a una universidad.
  • Google Code Jam: competencia organizada por Google desde 2003.
  • Facebook Hacker Cup: competencia organizada por Facebook desde 2011.
  • HackerRank: Sitio web mediante el cual se organizan muchas competencias cortas (y también competencias largas).
  • CodeChef Cook-Off: competencia similar a las de ACM-ICPC que tienen lugar el segundo domingo de cada mes.
  • IOI - Un de las competiciones más viejas, para alumnos de escuelas secundarias y preuniversitarias.
  • TopCoder Open: Competencia organizada por TopCoder desde 2004. Esta empresa también organiza competiciones regulares denominadas Single Round Match (competencia de una ronda, SRM por sus siglas en inglés).
  • Yandex Algorithm: Competencia organizada desde 2013 por Yandex.
  • Rondas de CodeForces: Competencias organizadas regularmente por la plataforma rusa CodeForces.

La mayoría de las competencias mencionadas consisten de varias rondas debido al alto número de participantes. Generalmente requieren de una inscripción previa a través de internet, salvo por las rondas finales que suelen ser presenciales. En la ACM-ICPC y la IOI los mejores competidores reciben medallas de oro, plata y bronce, mientras que en otras competencias los premios suelen ser económicos. Además, un buen resultado en este tipo de competencias suele ser muy atractivo para los reclutadores de compañías de software e internet.

Competencias largas[editar]

  • Competencia de programación Al Zimmermann: Competencia de tres meses organizada dos veces al año
  • Competencias largas de CodeChef
  • Google AI Challenge: competencia para estudiantes de dos años que tuvo lugar entre 2009 y 2011
  • HackerRank Week of Code: Competencia de 7 días organizada por HackerRank
  • Competencias Marathon Match de TopCoder: Competencias que suelen durar entre 2 y 4 semanas y en las que el objetivo es aproximar la solución de un problema lo mejor posible al óptimo.

Competencias en línea y recursos de entrenamiento[editar]

La comunidad de programación competitiva ha creado y mantenido a lo largo de los años diversos recursos destinados a programación competitiva en internet. Estos varían desde páginas que organizan competencias hasta páginas con tutoriales, foros, o cursos de entrenamiento en línea:

Ranking Similarweb Nombre Descripción Sitio web
6047 HackerRank Sitio innovador de programación competitiva. Comenzó en 2012, y ofrece problemas de competencias en distintos dominios de la Ciencia de la Computación. Ayuda a conectar programadores con empresas del Silicon Valley. hackerrank.com
GeeksforGeeks Un sitio web de programación con artículos y plataforma de práctica. El sitio está principalmente destinado a la preparación de entrevistas para trabajos de programación. Comenzó en 2009 y agregó una plataforma de práctica para programación competitiva en 2015 geeksforgeeks.org
14366 Codeforces Sitio ruso, mantenido por la Universidad Estatal de Saratov, el cual mayoritariamente proporciona competencias cortas frecuentes (hasta dos por semana). Características especiales: capacidad de comprobar correctitud de soluciones de otros participantes durante las competencias, participación virtual, etc. codeforces.com
23477 HackerEarth Compañía basada en Bangalore, India que provee competencias online como recurso para reclutadores de compañías de tecnología. www.hackerearth.com
26450 CodeChef Mantenido por Directi, organiza competencias largas de 10 días y alguans competencias cortas por mes (normalmente una con estilo IOI y otra con estilo ACM-ICPC), y proporciona una plataforma para organizar competencias gratuitamente para instituciones educativas. Los primeros dos competidores de la competencia larga ganan premios en efectivo mientras que los primeros 10 obtienen una remera. www.codechef.com
43360 TopCoder Compañía estadounidense que organiza competiciones y provee problemas de tipo industrial como trabajo independiente. Organiza varias competiciones cortas y algunas competencias largas cada año. En sus competencias cortas, ofrece la posibilidad de desafiar soluciones de otros participantes para testear su correctitud evaluándolas en casos de prueba provistos por el participante que envía el desafío www.topcoder.com
48672 Project Euler Colección de problemas de matemática computacional (no directamente relacionados a programación pero que a menudo requieren habilidades de programación para ser resueltos). projecteuler.net
50338 AtCoder AtCoder Es una plataforma de concurso creada por un equipo de altamente-valorado programadores competitivos japoneses. atcoder.jp/
67605 SPOJ Sistema de juez on-line polaco qué proporciona muchos problemas para entrenar, y proporciona una plataforma para otros organizadores a anfitriones sus concursos de programación. www.spoj.com
147369 POJ Pekín el juez Universitario on-line para ACM/ICPC creado por Ying Fuchen, Xu Pengcheng y Xie Di. Contiene 3,055 problemas. www.poj.org
172157 Coderbyte Contiene programar retos puedes

Campamentos de programación[editar]

En muchos países del mundo los participantes organizan campamentos de programación. Muchos de los más importantes son organizado por competidores rusos. Existen muchos campamentos en castellano, entre ellos, destacan el Campamento Caribeño de Programación, organizado por profesores de la Universidad de las Ciencias Informáticas de Cuba, auspiciado por el gobierno cubano y dictado generalmente por profesores invitados de distintos lugares del mundo, y el Training Camp Argentina, campamento organizado por competidores y ex competidores argentinos, que ha contado a lo largo de sus ediciones con muchos auspiciantes (entre los que destacan Google, Facebook, Microsoft, Medallia y la Fundación Sadosky y al que han asistido participantes de Argentina, Bolivia, Chile, Colombia, Paraguay, Perú, Venezuela y Uruguay. Estos dos campamentos se han organizado todos los años desde 2010 a la fecha y fueron los primeros en latinoamérica. En las primeras ediciones de estos campamentos existían muy pocos campamentos de programación en el mundo, lo que hizo que ganen mucho prestigio muy rápidamente.

References[editar]

  1. https://icpc.baylor.edu/ sitio oficial de la ACM-ICPC
  2. http://codeforces.com/blog/entry/49340 lista de equipos participantes por país en la final mundial 2017 de la ACM ICPC, en inglés

Traducción del artículo en inglés disponible en https://en.wikipedia.org/wiki/Competitive_programming. Faltan agregar muchas referencias. Muchas de las referencias pueden ser extraídas de la versión en inglés, por favor en lugar de borrar el artículo por falta de referencia agregar las mismas (no lo hice yo porque no sé cómo agregarlas), una vez que vea algunas referencias agregadas podré agregar las faltantes siguiendo el mismo formato