Preparación para Competencias de Programación
De Pyrox
Como primera tarea, se debe definir un esquema de preparación para las competencias.
La idea es realizar reuniones periódicas, y en cada una se tratará un tema determinado.
Contenido |
[editar] Preparación
[editar] Complejidad Algorítmica
[editar] Importancia
El análisis de algoritmos juega un papel en las competencias de programación, ya que permite determinar cuál es el mejor algoritmo para una aplicación particular.
Las competencias de programación suelen probar las capacidades de los participantes en el planteamiento de algoritmos que son sometidos a enormes volúmenes de datos. La complejidad se puede medir tanto en el tiempo de ejecución del programa, como en la memoria utilizada por este, con respecto a la entrada.
[editar] Ejercicios Planteados
[editar] Referencias
- The Art of Computer Programming - Donald Knuth (Analysis of an Algorithm)
- http://en.wikipedia.org/wiki/Computational_complexity_theory
- http://en.wikipedia.org/wiki/Analysis_of_algorithms
[editar] Matemáticas para las competencias
[editar] Importancia
[editar] Referencias
- The Art of Computer Programming - (Donald Knuth) - Mathematical Preliminaries
- http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=math_for_topcoders
[editar] Enteros Grandes
Este topic es comúnmente conocido como BigNum, y se refiere a la representación y tratamiento de números enteros con precisión arbitraria, lo que se busca es poder hacer operaciones aritméticas entre enteros, donde dichos números puedan tener cualquier cantidad de dígitos. Es importante mencionar que la expresión "precisión arbitraria" desde el punto de vista computacional tiene una limitante que viene determinada por la cantidad de memoria de la que se dispone.
En algunos lenguajes de programación la precesión arbitraria en números enteros no está soportada; al menos nó sin incluir antes librerías diseñadas específicamente para este fin; como es el caso de C, donde se pueden usar tipos de datos para representar enteros como int, long int y long long int,pero todos estos tipos tienen determinada una cantidad de memoria específica lo que restringe a un intervalo los números que allí podríamos almacenar, por ejemplo el tipo int de C tiene disponibles 4 bytes(en la mayoría de los casos) para almacenar el número, lo que significa que solo se podría almacenar un número entero entre -2147483648 y 2147483647 ó si se usa un unsigned int se podría almacenar un número entre 0 y 4294967295.
Por otro lado, algunos lenguajes de programación tiene implementada la precisión arbitraria por defecto como Python.En este tipo de lenguajes el manejo y representación de enteros grandes es algo por lo que el programador no debe preocuparse.
Existe un error muy común en la manipulación de enteros grandes cuando se usan tipos de datos que no soportan precisión arbitraria y ocurre cuando se intenta almacenar un número entero que está por fuera del rango de almacenamiento de la variable que se usa, este error es conocido como overflow(desbordamiento), en la mayoría de los casos este error no detiene la ejecución normal del programa pero en lugar de guardar el número que deseabamos almacenar se guarda un valor indeterminado, lo que afectará de gran manera las operaciones posteriores que se hagan con ese valor.
En el contexto de las competencias de programación, el manejar precisión arbitraria o una precisión mayor a la provista normalmente por el lenguaje, es un tema de vital importancia, gran parte de los problemas exigen trabajar con números enteros grandes y el nó saber cómo, se traduce en muchos fracasos.Dado esto se tienen dos posibilidades para manejar los enteros grandes, se puede usar alguna librería diseñada para este propósito o se puede implementar un nuevo tipo de dato BigNum from the scratch.
Si decide optar por la primera posibilidad puede usar la librería GMP(GNU Multi-Precision Library) para C y C++ ó la clase BigInteger para Java en el paquete Java.math, si por el contrario opta por construir el tipo de dato BigNum en las referencias bibliográficas puede encontrar información muy útil acerca de cómo hacerlo.
Finalmente, es importante saber que no es bueno reinventar la rueda, es decir, si se dispone de una clase ó un tipo de dato ya definido para el manejo de enteros grandes ¿por qué no usarlo?, pero más importante aún es saber que algunos problemas nos exigen entender como se manipulan los enteros grandes, entoces es un excelente ejercicio el implementar un tipo de dato BigNum.
[editar] Bibliografía
- Programming Challenges-Steven Skiena & Miguel A. Revilla, capítulo 5.
- http://www.algorithmist.com/index.php/Bignum
- http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
- http://home.att.net/~jackklein/c/inttypes.html
[editar] Problemas sugeridos
Arithmetic Operations With Large Integers
[editar] Números de punto flotante
[editar] Importancia
Los números de reales tienen una complicación para su representación en una computadora. Requieren de una precisión infinta para su correcta representación, por tanto al realizar numerosas operaciones sobre números de punto flotante (la forma más común para representar enteros), se suele generar un error, y por tanto, son de especial cuidado al momento de resolver problemas.
[editar] Sobre los números de punto flotante
[editar] Problemas
[editar] Referencias
- Programming Challenges - Capítulo 5
- http://en.wikipedia.org/wiki/Floating_point
- http://docs.sun.com/source/806-3568/ncg_goldberg.html
