I Algoritmos y Estructuras de Datos I I - glyc.dc.uba.ar

1 Algoritmos y Estructuras de Datos IDepartamento de Computaci on, FCEyN, UBA2 cuatrimestre de 20081 ContenidoEspecificaci onIclase 1, p. 3 Iclase 2, p. 28 Iclase 3, p. 48 Iclase 4, p. 78 programaci on funcionalIclase 1: p. 94 Iclase 2: p. 114 Iclase 3: p. 131 Iclase 4: p. 154 Iclase 5: p. 181 programaci on imperativaIclase 1: p. 205 Iclase 2: p. 225 Iclase 3: p. 247 Iclase 4: p. 260 Iclase 5: p. 2722 Especificaci onClase 1 Introducci on a la especificaci on de problemas3 CursadaIclases te oricasIPaula Zabala y Santiago FigueiraIclases pr acticasICarlos L opez Pombo, Pablo Turjanski y Mart n UrtasunIsitio web de la materia: egimen de aprobaci onIparcialesI3 parcialesI3 recuperatorios (al final de la cursada)Itrabajos pr acticosI3 entregasI3 recuperatorios (cada uno a continuaci on)Igrupos de 4 alumnosIexamen final (si lo dan en diciembre 2008 o febrero/marzo2009, cuenta la nota de la cursada)4 Objetivos y contenidosIObjetivos.

2 Iespecificar problemasIdescribirlos de forma no ambiguaIescribir programas sencillosItratamiento de secuenciasIrazonar acerca de estos programasIdemostrar matem aticamente que un programa es correctoIvision abstracta del proceso de computaci onImanejo simb olico y herramientas para demostrarIContenidos:Iespecificaci onIdescribir problemas en un lenguaje formal (preciso, claro,abstracto)Iprogramaci on funcional (Haskell)Iparecido al lenguaje matem aticoIescribir de manera simple Algoritmos y Estructuras de datosIprogramaci on imperativa (C++)Iparadigma m as difundidoIm as eficienteIse necesita para seguir la carrera5 Especificaci on, algoritmo, programa1. especificaci on = descripci on del problemaI qu e problema tenemos?Ien lenguaje formalIdescribe propiedades de la soluci onIDijkstra, Hoare (a nos 70)2.

3 Algoritmo = descripci on de la soluci on (escrito para humanos)I c omo resolvemos el problema?3. programa = descripci on de la soluci on (escrito para lacomputadora)Itambi en, c omo resolvemos el problema?Iusando un lenguaje de programaci on6 Problemas y soluci onSi voy a escribir un programa, es porque hay un problema aresolverIa veces, la descripci on es vaga o ambiguaIno siempre es claro que haya soluci onIno siempre involucra uno o m as programas de computaci onEjemplos de problemas:Icerr e el auto con las llaves adentroIseguramente tiene soluci on, sin programasIquiero calcular la edad de una personaItal vez podamos crear un programaInecesitamos que la empresa reduzca sus gastos en un 10 %Ipuede o no tener soluci on, que puede o no requerir programasnuevos o existentesIsoy muy petisoIquiz as no tenga soluci on7 Problema vs.

4 Soluci onParece una diferencia trivialIen los ejemplos, es claraIpero es f acil confundirlosEjemplo:Iconfundir el problema con la soluci on:A: tengo un problema: necesito un alambre B: no tengo Ien realidad, ese no era el problema:A: tengo un problema: cerr e el auto con las llaves adentro B: tom a la copia de la llave que me pediste que te guardaracuando compraste el auto Iconfundir el problema con la soluci on trae nuevos problemasIes muy com un en computaci onIlos programas de computadora casi nunca son la soluci oncompletaIa veces forman parte de la soluci onI y a veces ni siquiera se necesitan!8 Etapas en el desarrollo de programas1. especificaci on: definici on precisa del problema 2. dise no: elegir una soluci on y dividir el problema en partes 3. programaci on: escribir Algoritmos e implementarlos en alg unlenguaje 4.

5 Validaci on: ver si el programa cumple con lo especificado 5. mantenimiento: corregir errores y adaptarlo a nuevosrequerimientosEDPVM 91. Especificaci onIel planteo inicial del problema es vago y ambiguoIespecificaci on = descripci on clara y precisaI optimo: lenguaje formal, por ejemplo, el lenguaje de la l ogica matem aticaPor ejemplo, el problema de calcular de edad de una persona parece bienplanteado, pero:I c omo recibo los Datos ? manualmente, archivo en disco, sensorI cu ales son los Datos ? fecha de nacimiento, tama no de la persona,deterioro celularI c omo devuelvo el resultado? pantalla, papel, voz alta, emailI qu e forma van a tener? d as, a nos enteros, fracci on de a nosUna buena especificaci on responde algunas:INecesito una funci on que, dadas dos fechas en formato dd/mm/aaaa, medevuelva la cantidad de d as que hay entre a faltan los requerimientos no funcionalesIforma de entrada de par ametros y de salida de resultados, tipo decomputadora, tiempo con el que se cuenta para programarlo, son parte de la especificaci on funcional y quedan para otras materias102.

6 Dise noEtapa en la que se respondeI varios programas o uno muy complejo?I c omo dividirlo en partes, qu e porci on del problema resuelvecada una?I distintas partes en distintas m aquinas?Iestudio de las partes que lo componenI(mini) especificaci on de cada parteIun programador recibe una sola (o una por vez)I programas ya hechos con los que interactuar?Ilo van a ver enAlgoritmos y Estructuras de Datos IIy enIngenier a del Software I113. programaci on - AlgoritmosPensar en la soluci on al problema. Escribir un algoritmo:Ipasos precisos para llegar al resultado buscado de manera efectivaIprimero tienen que estar definidos los pasos primitivosEjemplo de algoritmo para la especificaci onNecesito una funci on que, dadas dos fechas a y b en formatodd/mm/aaaa, me devuelva la cantidad de d as que hay entre restar el a no debal a no dea2.

7 Multiplicar el resultado por 3653. sumarle la cantidad de d as desde el 1 de enero del a no debhasta el d ab4. restarle la cantidad de d as desde el 1 de enero del a no deahasta el d aa5. sumarle la cantidad de 29 de febrero que hubo en el per odo6. devolver ese resultado, acompa nado de la palabra d as Son todos primitivos? (3, 4, 5)Isi no, hay que dar Algoritmos para realizarlos12 Pasos primitivosIproblema: sumar dos n umeros naturalesIalgoritmos:Ivoy sumando uno al primero y restando uno al segundo, hastaque llegue a ceroIsumo las unidades del primero a las del segundo, despu es lasdecenas y as ( llev andome uno cuando hace falta)Iescribo el primero en una calculadora, aprieto +, escribo elsegundo, aprieto =Ilos tres son v alidosIdepende de qu e operaciones primitivas tengaIsumar / restar unoIsumar d gitos (y concatenar resultados)Iapretar una tecla de una calculadora133.

8 programaci on - ProgramasItraducir el algoritmo (escrito o idea) para que unacomputadora lo entiendaIlenguaje de programaci onIvamos a empezar usando uno: HaskellIdespu es, C++Ihay muchos otrosIpueden ser m as adecuados para ciertas tareasIdepende del algoritmo, de la interfaz, tiempo de ejecuci on, tipode m aquina, interoperabilidad, entrenamiento de losprogramadores, licencias, on de los datosIya vimos que era importante en el ejemplo de calcular la edadde una persona (d as, meses, a nos, fracciones de a no)Iotro ejemplo:Icontar la cantidad de alumnos de cada sexoIyo puedo darme cuenta a simple vista (a veces)Ila computadora probablemente no. Que dato conviene tener?IfotoIfoto del documentoIADNI valor de la propiedadsexopara cada alumnoIestructuras de datosInecesarias para especificarIpuede ser que haya que cambiarlas al programarIlas van a estudiar a fondo enAlgoritmos y Estructuras deDatos II154.

9 Validaci onAsegurarse de que un programa cumple con la especificaci onItestingIprobar el programa con muchos Datos y ver si hace lo que tieneque hacerIen general, para estar seguro de que anda bien, uno tendr aque probarlo para infinitos Datos de entradaIsi hay un error, con algo de suerte uno puede encontrarloIno es infalible (puede pasar el testing pero haber errores)IenIngenier a del Software Ivan a ver t ecnicas para hacertestingIverificaci on formalIdemostrar matem aticamente que un programa cumple con unaespecificaci onIes m as dif cil que hacer testingIuna demostraci on cubre infinitos valores de entrada a la vez(abstracci on)Ies infalible (si est a demostrado, el programa no tiene errores)Ien esta materia van a estudiar c omo demostrar que programassimples son correctos para una especificaci on165.

10 MantenimientoItiempo despu es, encontramos erroresIel programa no cumpl a la especificaci onIla especificaci on no describ a correctamente el problemaIo cambian los requerimientosIpuede hacerlo el mismo equipo u otroIjustifica las etapas anterioresIsi se hicieron bien la especificaci on, dise no, programaci on yvalidaci on, las modificaciones van a ser m as sencillas y menosfrecuentes17 Especificaci onIobjetivos:Iantes de programar: entender el problemaIdespu es de programar: determinar si el programa es correctoItestingIverificaci on formalIderivaci on (construyo el programa a partir de la especificaci on)Iestrategia:Ievitar pensar (todav a) una soluci on para el problemaIlimitarse a describir cu al es el problema a resolverIqu e propiedades tiene que cumplir una soluci on para resolverel problemaIbuscamos el qu e y no el c omo18 Instancias de un problemaIejemplo de problema: arreglar una cafeteraIpara solucionarlo, necesitamos m as datosI qu e clase de cafetera es?