p. 1

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

[close]

p. 2

ii

[close]

p. 3

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 experiencia docente 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´ io 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 lector debr´ 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´ itulo 1 los conceptos de algor´ itmica elemental con el prop´sito de introducir a los estudiantes al concepto de la eficiencia de los o programas el cap´ itulo dos introduce los conceptos de an´lisis de algoritmos con una 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´ itulo tres introduce el concepto de la teor´ de n´meros introduia u ciendo las librer´ de java se muestran ejemplos de n´meros grandes y ias u aplicaciones en la criptograf´ ia el cap´ itulo 4 trata de la escritura de programas con miras a la prueba del c´digo en este cap´ o itulo se introduce un concepto que es el dise~o por conn iii

[close]

p. 4

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 es una introducci´n a estos conceptos o para facilitar la prueba del c´digo en forma din´mica o a el cap´ itulo 5 complementa el cap´ itulo 4 con conceptos de clasificaci´n y o b´squeda se introducen laboratorios y las bibliotecas java para clasificar u el cap´ itulo 6 est´ orientado a explicar como se encara la programaci´n a o de problemas de combinatoria b´sica a el cap´ itulo 7 explica como utilizar las librer´ del lenguaje java y como ias resolver problemas con pilas listas enlazadas conjuntos ´rboles y colas de a prioridad el cap´ itulo 8 introduce al estudiante a los problemas de retroceso bactracking con problemas t´ ipicos como recorrido de grafos y permutaciones el cap´ itulo 9 introduce a la geometr´ computacional muestra como consia truir una librer´ de rutinas b´sicas para desarrollar aplicaciones relacionadas ia a a la geometr´ y muestra las librer´ java as´ como las posibilidades que se ia ias i 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 enunciados orientados 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´ inea de valladolid en su p´gina web http acm.uva.es estos ejercicios llevan a adelante el n´mero de problema del juez en l´ u inea 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 una clase de teor´ de dos per´ ia iodos y una segunda clase que ser´ de ejercicios o laboratorio ia

[close]

p. 5

v contenido del cd el cd adjunto contiene los programas presentados en el texto hay que aclarar que todos han sido codificados utilizando el compilador java 1.5 de sun microsystems el cap´ itulo 4 relacionado a jml fue codificado con la versi´n 1.4 dado que a la fecha de la redacci´n de la obra no estaba disponible o o una versi´n de jml que funcionara con la versi´n 1.5 o o agradecimientos quiero agradecer a mi esposa a mis hijos por los aportes realizados y finalmente al dr miguel angel revilla por dejarme reproducir ejercicios del juez en l´ inea lic jorge ter´n pomier m.sc a

[close]

p. 6

vi

[close]

p. 7

´ indice general prefacio 1 algor´ itmica elemental 1.1 introducci´n o 1.2 algoritmo 1.3 problemas e instancias 1.4 eficiencia 1.5 qu´ considerar y qu´ contar e e 1.5.1 operaciones elementales 1.5.2 an´lisis del mejor caso caso a 1.5.3 ejercicios 1.5.4 laboratorio iii medio y peor caso 1 1 1 2 2 4 6 6 7 7 11 11 11 12 13 13 13 14 14 14 15 15 16 17 18 2 an´lisis de algoritmos a 2.1 introducci´n o 2.2 notaci´n orden de o 2.2.1 propiedades de o grande de n 2.3 notaci´n asint´tica condicional o o 2.4 notaci´n omega o 2.5 notaci´n teta o 2.6 an´lisis de las estructuras de control a 2.6.1 secuenciales 2.6.2 ciclos for 2.6.3 llamadas recursivas 2.6.4 ciclos while y repeat 2.6.5 an´lisis del caso medio a 2.6.6 an´lisis amortizado a 2.7 soluci´n de recurrencias o vii .

[close]

p. 8

viii ´ indice general 18 19 20 20 22 22 23 27 32 34 35 35 35 37 38 41 43 43 44 45 45 45 47 47 49 51 51 52 52 53 54 57 57 58 59 59 60 2.7.1 m´todo por substituci´n e o 2.7.2 cambio de variables 2.7.3 ejercicios 2.7.4 m´todo iterativo e 2.7.5 ejercicios 2.7.6 teorema master 2.7.7 soluci´n general de recurrencias lineales o 2.8 ejercicios resueltos 2.9 ejercicios 2.10 nota sobre el c´lculo integral a 3 teor´ de n´ meros ia u 3.1 introducci´n o 3.2 variables del lenguaje java 3.3 c´lculo del m´ximo com´n divisor a a u 3.3.1 divisibilidad 3.3.2 algoritmos extendido de euclides 3.4 m´ inimo com´n m´ltiplo u u 3.5 aritm´tica modular e 3.5.1 propiedades 3.5.2 congruencias 3.5.3 inverso multiplicativo 3.5.4 soluci´n de ecuaciones o 3.6 n´meros primos u 3.6.1 generaci´n de primos o 3.6.2 factorizaci´n o 3.6.3 prueba de la primalidad 3.6.4 teorema de fermat 3.6.5 prueba de miller rabin 3.6.6 otras pruebas de primalidad 3.7 bibliotecas de java 3.7.1 ejemplo 3.8 ejercicios 3.8.1 problema 136 n´meros feos u 3.8.2 problema 10042 n´meros de smith u 3.8.3 problema 10104 el problema de euclides 3.8.4 problema 10139 factovisors 3.8.5 problema 106 fermat vs pit´goras a .

[close]

p. 9

´ indice general 4 codificaci´n con miras a la prueba o 4.1 introducci´n o 4.2 algunos errores de programaci´n o 4.3 especificaci´n de programas o 4.3.1 ¿por qu´ especificar e 4.3.2 ¿qu´ especificar e 4.3.3 ¿c´mo especificar o 4.3.4 invariantes 4.3.5 ejercicios propuestos 4.4 aplicaciones de las invariantes 4.4.1 principio de correctitud 4.5 dise~o por contratos n 4.5.1 especificaci´n de contratos o 4.5.2 invariantes 4.6 prueba est´tica a 4.7 prueba din´mica a 4.7.1 afirmaciones 4.8 programaci´n bajo contratos con jml o 4.8.1 especificaci´n de invariantes o 4.8.2 cuantificadores 4.8.3 ejercicios ix 61 61 62 66 68 69 70 71 74 75 84 85 88 90 91 92 92 95 97 98 99 101 101 101 105 107 111 113 117 127 127 127 131 131 132 134 135 5 aplicaciones de b´ squeda y clasificaci´n u o 5.1 introducci´n o 5.2 algoritmos de b´squeda u 5.2.1 prueba exhaustiva 5.2.2 representaci´n gr´fica de la b´squeda o a u 5.3 clasificaci´n o 5.3.1 clasificaci´n en java o 5.3.2 algoritmos de clasificaci´n o 5.3.3 laboratorio 5.3.4 ejercicios 5.3.5 ejemplo de aplicaci´n o 5.4 ejercicios 5.4.1 problema 10107 hallar la mediana 5.4.2 problema 10295 c´lculo de salario a 5.4.3 problema 331 contando los intercambios 5.4.4 problema 499 hallar la frecuencia .

[close]

p. 10

x ´ indice general 137 137 137 139 141 141 142 143 146 146 149 149 150 151 152 153 153 153 157 160 162 164 166 168 6 combinatoria b´sica a 6.1 introducci´n o 6.2 t´cnicas b´sicas para contar e a 6.3 coeficientes binomiales 6.4 algunas secuencias conocidas 6.4.1 n´meros de fibonacci u 6.4.2 n´meros catalanes u 6.4.3 n´mero eulerianos u 6.4.4 n´meros de stirling u 6.4.5 particiones enteras 6.5 ejercicios 6.5.1 problema 357 formas de combinar monedas 6.5.2 problema 369 combinaciones 6.5.3 problema 10338 mal educados 6.5.4 problema 10183 secuencia de fibonacci 7 estructuras de datos elementales 7.1 introducci´n o 7.2 pilas 7.3 listas enlazadas 7.4 conjuntos 7.5 clases map 7.6 clases para ´rboles a 7.7 clases para colas de prioridad 7.8 ejercicios para laboratorio 8 backtracking 8.1 introducci´n o 8.2 recorrido de grafos 8.3 constuir todos los subconjuntos 8.4 construir todas las permutaciones 8.5 ejercicios 8.5.1 prolema 195 anagramas 8.5.2 prolema 574 sum it up 8.5.3 problema 524 anillos de primos 8.5.4 problema 216 hacer la l´ inea 171 171 171 175 179 182 182 183 185 186

[close]

p. 11

´ indice general 9 geometr´ computacional ia 9.1 introducci´n o 9.2 geometr´ ia 9.3 librer´ de java ias 9.4 cercos convexos 9.5 clase java para pol´ igonos 9.6 c´lculo del per´ a imetro y ´rea del pol´ a igo-no 9.7 ejercicios 9.7.1 problema 378 l´ ineas que intersectan 9.7.2 problema 273 juego de palos 9.7.3 problema 218 erradicaci´n de moscas o 9.7.4 problema 476 puntos en rect´ngulos a a fundamentos matem´ticos a a.1 recordatorio de logaritmos a.2 recordatorio de series a.2.1 series simples a.2.2 serie aritm´tica e a.2.3 serie geom´trica e a.2.4 propiedades de la sumatorias a.2.5 series importantes a.3 combinatoria b´sica a a.3.1 f´rmulas importantes o a.4 probabilidad elemental a.5 t´cnicas de demostraci´n e o a.5.1 demostraci´n por contradicci´n o o a.5.2 demostraci´n por inducci´n o o xi 189 189 190 196 198 205 207 211 211 212 214 216 219 219 220 220 220 220 221 221 222 222 223 224 224 224 .

[close]

p. 12

xii ´ indice general

[close]

p. 13

cap´ itulo 1 algor´ itmica elemental 1.1 introducci´n o en este cap´ itulo empezamos el estudio de los algoritmos empezaremos definiendo algunos t´rminos tales como algoritmo problema instancia efie ciencia e investigaremos m´todos para probar la eficiencia de los mismos e existen m´todos formales para realizar pruebas rigurosas sobre la correce ci´n de los programas ´sta tem´tica est´ fuera del alcance del texto pero oeaa ser´ mencionada m´s adelante solo como referencia a a 1.2 algoritmo definimos como algoritmo a un conjunto de pasos necesarios para resolver un problema ya sea manualmente o por m´todos mecanizados que e son los m´s usuales en la actualidad el concepto de algoritmos fue definido a inicialmente por el matem´tico persa al-khow^rizm en el siglo diecinueve a a i la ejecuci´n de un algoritmo no debe incluir procedimientos intuitivos o o que requieran creatividad por ejemplo una receta de cocina puede denominarse un algoritmo si contiene las instrucciones precisas para preparar algo siempre y cuando no tenga detalles tales como sal al gusto o cocinar hasta que est´ suave que son apreciaciones subjetivas del que prepara la receta e debemos indicar que los algoritmos deben cumplir un requisito fundamental y es que todo algoritmo debe terminar en un n´mero finito de pasos u si consideramos el sistema operativo veremos que no es un algoritmo porque no termina nunca dado que est´ en un ciclo infinito a 1

[close]

p. 14

2 1 algor´ itmica elemental podemos citar algunos ejemplos de algoritmos conocidos el m´todo de e multiplicar que aprendimos en la escuela el algoritmo para verificar si un n´mero es primo y muchos otros u 1.3 problemas e instancias si pensamos los procedimientos para multiplicar n´meros que conocemos u veremos que hay varias formas de resolver el problema de multiplicaci´n o tenemos los m´todos que aprendimos en la escuela m´todos por divisi´n yeeo multiplicaci´n por 2 denominado multiplicaci´n a la rusa y otros ¿cu´l de o o a ´stas posibles soluciones hay que implementar esta decisi´n corresponde a e o un ´rea muy desarrollada en el campo de la inform´tica denominada an´lisis a a a de algoritmos una instancia particular ser´ por ejemplo multiplicar el n´mero 123 por ia u el 4567 pero un algoritmo debe ser capaz de funcionar correctamente no solo en una instancia del m´todo sino m´s bien en todas las instancias posibles e a para demostrar que un algoritmo es incorrecto es suficiente demostrar que es incorrecto para una instancia as´ como es dif´ probar que un i icil teorema es correcto tambi´n es dif´ probar que un algoritmo es correcto e icil existen limitaciones propias de las computadoras que ponen restricciones a los algoritmos estas pueden ser debido al tama~o de los n´meros n u espacio de memoria o almacenamiento en el an´lisis de los algoritmos se a trata de analizarlos en forma abstracta inicialmente pero en el transcurso del texto tambi´n tocaremos aspectos espec´ e ificos sobre la implementaci´n y o la eficiencia de los mismos 1.4 eficiencia cuando tenemos que resolver un problema pueden existir muchos algoritmos disponibles obviamente quisi´ramos escoger el mejor de aqu´ nos e i viene la pregunta ¿cu´l es mejor a si tenemos un problema sencillo con algunas pocas instancias escogemos lo m´s f´cil y nos despreocupados de la eficiencia a a para analizar ´sto tenemos dos m´todos el m´todo emp´rico tambi´n eeeie llamado a posteriori consiste en programar todos los m´todos y probarlos e con diferentes instancias y con la ayuda de la computadora analizamos y

[close]

p. 15

1.4 eficiencia 3 escogemos alguno el segundo llamado m´todo apriori es el an´lisis te´rico del algoritmo e a o que con la ayuda de las matem´ticas podemos determinar la cantidad de los a recursos requeridos por cada algoritmo en base del tama~o de las instancias n consideradas el tama~o de una instancia normalmente est´ definida por el n´mero de n a u bits en el caso de un grafo por el n´mero de nodos y v´rtices o en otros u e por el n´mero de elementos a procesar la ventaja del m´todo te´rico es que u e o no depende de la computadora lenguaje de programaci´n o implementaci´n o o particular en el tratamiento del tema utilizaremos en algunos casos un m´todo e h´ ibrido donde se determinar´ la eficiencia en forma te´rica y se hallar´n los a o a valores num´ricos en forma experimental e retornando a la pregunta debemos indicar que la eficiencia se mide en tiempo para esto diremos que un programa toma un tiempo del orden tn para una instancia de tama~o n m´s adelante trataremos un t´rmino m´s naea riguroso que es la notaci´n asint´tica o o si tratamos el tiempo en segundos uno podr´ pensar si tengo una m´quiia a na m´s r´pida el tiempo ser´ menor ¿c´mo es que este m´todo te´rico llega aaaoeoa ser efectivo consideremos que el algoritmo toma un tiempo en segundos t1 n para una m´quina en particular y t2 n para otra para un n´mero n suficientea u mente grande podemos hallar unas constantes a y b tales que atn btn esto nos dice que cualquier ejecuci´n del algoritmo est´ acotado por una o a funci´n tn y existen unas constantes positivas de proporcionalidad que nos o dan el tiempo esto indica que si cambiamos de equipo podemos ejecutar el algoritmo 10 o 100 veces m´s r´pido y que este incremento est´ dado solo a a a por una constante de proporcionalidad la notaci´n asint´tica dice que un algoritmo toma un tiempo del orden o o de en funci´n del tama~o de la instancia existen algoritmos que ocurren o n muy frecuentemente y ameritan tener un nombre que a su vez se denominan tasas de crecimiento se denominan algoritmos constantes los que cuyo tiempo de proceso no depende del tama~o de n la instancia lineales a los que toman tiempos proporcionales a n.

[close]