Prograacion

Universidad Mayor de San Andr´s e Facultad de Ciencias Puras y Naturales Carrera de Inform´tica a

Fundamentos de la Programaci´n o
Jorge Humberto Ter´n Pomier a

La Paz - Bolivia, Diciembre 2006

ii

Prefacio
Motivaci´n o
Los conceptos presentados se estudian en muchas de las materias del pregrado de la carrera de inform´tica, con el rigor necesario. Sin embargo, a en mi experienciadocente he podido ver que hay muchos estudiantes que carecen de elementos pr´cticos con los que puedan aplicar directamente los a conceptos aprendidos y lo que se pretende es cubrir este vac´ ıo. El presente texto trata de introducir los conceptos de programaci´n, a o estudiantes de pregrado con un enfoque nuevo. Para una adecuada compresi´n de la tem´tica presentada en el libro, el o a lectordebr´ tener alguna experiencia en el desarrollo de programas. El libro a no pretende ense˜ar a codificar programas, sino a resolver problemas. n

Contenido
Se presentan en el cap´ ıtulo 1, los conceptos de algor´ ıtmica elemental con el prop´sito de introducir a los estudiantes, al concepto de la eficiencia de los o programas. El cap´ ıtulo dos introduce los conceptos de an´lisis de algoritmos conuna a serie de ejercicios aplicados. Se incluyen algunos laboratorios que tienen el prop´sito de que, los estudiantes asimilen estos conceptos en forma experio mental. El cap´ ıtulo tres introduce el concepto de la teor´ de n´meros, introduıa u ciendo las librer´ de Java. Se muestran ejemplos de n´meros grandes y ıas u aplicaciones en la criptograf´ ıa. El cap´ ıtulo 4 trata de la escritura deprogramas con miras a la prueba del c´digo. En este cap´ o ıtulo se introduce un concepto que es el dise˜o por conn iii

iv tratos y la forma de aplicar en Java. Aunque este concepto fue introducido inicialmente en el lenguaje Eifel, actualmente tiene mucho inter´s en el dee sarrollo de aplicaciones. El texto no trata de trabajar en conceptos de l´gica o formal en su totalidad, lo que propone esuna introducci´n a estos conceptos o para facilitar la prueba del c´digo en forma din´mica. o a El cap´ ıtulo 5 complementa el cap´ ıtulo 4 con conceptos de clasificaci´n y o b´squeda . Se introducen laboratorios y las bibliotecas Java para clasificar. u El cap´ ıtulo 6 est´ orientado a explicar como se encara la programaci´n a o de problemas de combinatoria b´sica. a El cap´ ıtulo 7 explica comoutilizar las librer´ del lenguaje Java y como ıas resolver problemas con pilas, listas enlazadas, conjuntos, ´rboles y colas de a prioridad. EL cap´ ıtulo 8 introduce al estudiante a los problemas de retroceso (bactracking) con problemas t´ ıpicos, como recorrido de grafos y permutaciones. El cap´ ıtulo 9 introduce a la geometr´ computacional. Muestra como consıa truir una librer´ de rutinas b´sicaspara desarrollar aplicaciones relacionadas ıa a a la geometr´ y muestra las librer´ Java as´ como las posibilidades que se ıa ıas ı tienen con las mismas. El lenguaje que se escogi´ fue el Java, primero porque la formaci´n o o est´ orientada a la programaci´n orientada a objetos. Segundo porque el a o lenguaje es de amplia utilizaci´n en las empresas y en la educaci´n. o o Los enunciadosorientados a la programaci´n fueron tomados de los cono cursos de programaci´n, fueron traducidos al espa˜ol manteniendo los datos o n de entrada y salida en ingl´s. Esto se hizo para permitir a los interesados e resolver los problemas y poder validar sus respuestas con el Juez en L´ ınea de Valladolid, en su p´gina web http://acm.uva.es. Estos ejercicios llevan a adelante el n´mero de problema del Juez enL´ u ınea de Valladolid.

Aplicaci´n en el aula o
Esta tem´tica puede aplicarse en el transcurso de un semestre en clases a te´ricas, pr´cticas y de laboratorio. o a Los laboratorios proponen ejercicios que tienen la finalidad de evaluar experimentalmente la ejecuci´n de los algoritmos. Esto permite que los estuo diantes obtengan una vivencia de los resultados te´ricos. o Se puede aplicar en...