material oficial 2014

7/26/2019 Material Oficial 2014

1/112

Algoritmos y Estructura de Datos DISI UTN.BA Pgina 1

Algoritmos y estructura

de datosAsignatura anual, cdigo 082021

Departamento de Ingeniera en Sistemas de InformacinUniversidad Tecnolgica Nacional FRBA

Dr. Oscar Ricardo Bruno,Ing. Pablo Augusto Sznajdleder.Ing. Jose Maria Sola


2/112


Tabla de contenidoConceptos bsicos ............................................................................................................................. 10

Introduccin: ................................................................................................................................. 10

Informtica .................................................................................................................................... 10

Programacin ................................................................................................................................ 10

Partes de un programa .................................................................................................................. 11

Dato ............................................................................................................................................... 11

Abstraccin .................................................................................................................................... 12

Modelizacion ................................................................................................................................. 12

Precondicin .................................................................................................................................. 12

Poscondicin ................................................................................................................................. 12

Especificacin ................................................................................................................................ 12

Lenguaje de programacin ............................................................................................................ 12

Del problema real a su solucin por computadoras ..................................................................... 12

Caractersticas de un algoritmo .................................................................................................... 15

Propiedades de los algoritmos ...................................................................................................... 16

Eficiencia de un algoritmo ............................................................................................................. 16

Complejidades ms comunes ........................................................................................................ 16

Lxico y algoritmo ......................................................................................................................... 17

Estructura de un algoritmo ........................................................................................................... 17

Proceso Computacional ................................................................................................................ 17

Acciones y funciones ......................................................................................................................... 20

Introduccin .................................................................................................................................. 20

Modularizacion .............................................................................................................................. 20

Mdulos ........................................................................................................................................ 21

Alcance de los datos ...................................................................................................................... 21

Datos locales y globales ................................................................................................................ 21

Ocultamiento y proteccin de datos ............................................................................................. 21

Parmetros .................................................................................................................................... 21

Integridad de los datos .................................................................................................................. 22

Proteccin de datos ...................................................................................................................... 22

Uso de parmetros para retornar valores .................................................................................... 22


3/112


Utilidad del uso de parmetros ..................................................................................................... 22

Reusabilidad .................................................................................................................................. 22

Acciones ........................................................................................................................................ 22

Utilizacin de acciones .................................................................................................................. 22

Acciones con parmetros .............................................................................................................. 23

Abstraccin y acciones .................................................................................................................. 23

Tipos de Parmetros ..................................................................................................................... 24

Ejemplo en C++.............................................................................................................................. 24

Beneficios del uso de acciones ...................................................................................................... 25

Funciones ...................................................................................................................................... 26

Concepto de recursividad: ............................................................................................................ 27

Arreglos y registros ........................................................................................................................... 30Tipos de Datos ............................................................................................................................... 30

Registros y vectores ...................................................................................................................... 32

Declaracin .................................................................................................................................... 34

Acciones y funciones para vectores .............................................................................................. 36

BusqSecEnVector....................................................................................................................... 36

BusqMaxEnVector ..................................................................................................................... 36

BusqMinDistCeroEnVector ........................................................................................................ 37

BusqMaxySiguienteEnVector .................................................................................................... 37

CargaSinRepetirEnVectorV1 ...................................................................................................... 38

BusquedaBinariaEnVectorV2 .................................................................................................... 40

CargaSinRepetirEnVectorV2 ...................................................................................................... 40

OrdenarVectorBurbuja .............................................................................................................. 41

OrdenarVectorBurbujaMejorado .............................................................................................. 42

OrdenarVectorInserion ............................................................................................................. 42

OrdenarVectorShell ................................................................................................................... 43CorteDeControlEnVector........................................................................................................... 44

ApareoDeVectores .................................................................................................................... 44

CargaNMejoresEnVector ........................................................................................................... 45

Archivos ............................................................................................................................................. 47

Estructura tipo registro: ................................................................................................................ 47


4/112


Estructura tipo Archivo ................................................................................................................. 48

Archivos y flujos ............................................................................................................................ 48

Archivos de texto: ..................................................................................................................... 48

Operaciones simples ................................................................................................................. 49

Patrones algortmicos con archivos de texto ........................................................................... 50

Archivos binarios: ...................................................................................................................... 51

Definiciones y declaraciones: .................................................................................................... 53

Operaciones simples ................................................................................................................. 53

ConvertirBinario_Texto ............................................................................................................. 55

ConvertirTexto_Binario ............................................................................................................. 55

AgregarRegistrosABinarioNuevo ............................................................................................... 56

AgregarRegistrosABinarioExistente .......................................................................................... 56RecorrerBinarioV1 ..................................................................................................................... 57

RecorrerBinarioV2 ..................................................................................................................... 57

RecorrerBinarioV3 ..................................................................................................................... 57

CorteControlBinario .................................................................................................................. 58

ApareoBinarioV1 ....................................................................................................................... 58

ApareoBinarioV2 ....................................................................................................................... 59

ApareoBinarioPorDosClaves...................................................................................................... 60

BusquedaDirectaArchivo ........................................................................................................... 61

BusquedaBinariaArchivo ........................................................................................................... 61

BusquedaBinariaArchivoV2 ....................................................................................................... 62

El archivo como estructura auxiliar ........................................................................................... 63

GenerarBinarioOrdenadoPUP ................................................................................................... 63

GenerarIndicePUP ..................................................................................................................... 65

Implementaciones C C++ ................................................................................................................... 67

Operaciones sobre arrays ............................................................................................................. 67Antes de comenzar .................................................................................................................... 67

Agregar un elemento al final de un array ................................................................................. 67

Recorrer y mostrar el contenido de un array ............................................................................ 67

Determinar si un array contiene o no un determinado valor ................................................... 67

Eliminar el valor que se ubica en una determinada posicin del array .................................... 68


5/112


Insertar un valor en una determinada posicin del array ......................................................... 68

Insertar un valor respetando el orden del array ....................................................................... 68

Insetar un valor respetando el orden del array, slo si an no lo contiene ............................. 68

Templates ...................................................................................................................................... 69

Generalizacin de las funciones agregar y mostrar .................................................................. 69

Ordenamiento ........................................................................................................................... 69

Punteros a funciones ..................................................................................................................... 70

Ordenar arrays de diferentes tipos de datos con diferentes criterios de ordenamiento ......... 70

Arrays de estructuras .................................................................................................................... 71

Mostrar arrays de estructuras ................................................................................................... 72

Ordenar arrays de estructuras por diferentes criterios ............................................................ 72

Resumen de plantillas ................................................................................................................... 73Operaciones sobre archivos .......................................................................................................... 77

Antes de comenzar .................................................................................................................... 77

Introduccin .............................................................................................................................. 77

Comenzando a operar con archivos .............................................................................................. 77

Grabar un archivo de caracteres ............................................................................................... 77

Leer un archivo caracter a caracter ........................................................................................... 77

Archivos de registros ................................................................................................................. 78

Grabar un archivo de registros .................................................................................................. 78

Leer un archivo de registros ...................................................................................................... 79

Acceso directo a los registros de un archivo ............................................................................. 79

Cantidad de registros de un archivo ......................................................................................... 80

Templates ...................................................................................................................................... 80

Operaciones sobre estructuras dinmicas .................................................................................... 83

Antes de comenzar .................................................................................................................... 83

Punteros y direcciones de memoria.......................................................................................... 83Asignar y liberar memoria dinmicamente ............................................................................... 83

Nodo .......................................................................................................................................... 83

Punteros a estructuras: operador "flecha" ............................................................................... 83

Listas enlazadas ............................................................................................................................. 84

Agregar un nodo al final de una lista enlazada ......................................................................... 84


6/112


Mostrar el contenido de una lista enlazada .............................................................................. 84

Liberar la memoria que ocupan los nodos de una lista enlazada ............................................. 84

Probar las funciones anteriores ................................................................................................ 84

Determinar si una lista enlazada contiene o no un valor especificado ..................................... 85

Eliminar de la lista al nodo que contiene un determinado valor .............................................. 85

Eliminar el primer nodo de una lista ......................................................................................... 85

Insertar un nodo manteniendo el orden de la lista .................................................................. 86

Ordenar una lista enlazada ....................................................................................................... 86

Insertar en una lista enlazada un valor sin repeticin .............................................................. 86

Templates ...................................................................................................................................... 88

Pilas ............................................................................................................................................... 92

Funcin: push (poner) ............................................................................................................... 92Funcin: pop (sacar) .................................................................................................................. 92

Ejemplo de cmo usar una pila ................................................................................................. 92

Colas .............................................................................................................................................. 92

Funcin: agregar ........................................................................................................................ 92

Funcin: suprimir ...................................................................................................................... 93

Biblioteca de templates .................................................................................................................... 94

Operaciones sobre arrays ............................................................................................................. 94

Funcin: agregar ................................................................................................................... 94

Funcin: buscar ...................................................................................................................... 94

Funcin: eliminar ................................................................................................................. 94

Funcin: insertar ................................................................................................................. 94

Funcin: insertarOrdenado....................................................................................................... 94

Funcin: buscaEInsertaOrdenado............................................................................................. 94

Funcin: ordenar ................................................................................................................... 94

Funcin: busquedaBinaria ........................................................................................................ 94

Operaciones sobre estructuras dinmicas con punteros .............................................................. 95

El Nodo ...................................................................................................................................... 95

Operaciones s/Listas ..................................................................................................................... 95

Funcin: agregarAlFinal ............................................................................................................ 95

Funcin: liberar ................................................................................................................... 95


7/112


Funcin: buscar ...................................................................................................................... 95

Funcin: eliminar ................................................................................................................. 96

Funcin: eliminarPrimerNodo .................................................................................................. 96

Funcin: insertarOrdenado....................................................................................................... 96

Funcin: ordenar ................................................................................................................... 96

Funcin: buscaEInsertaOrdenado............................................................................................. 96

Operaciones sobre pilas ................................................................................................................ 96

Funcin: push (poner) ............................................................................................................ 96

Operaciones sobre colas (implementacin con dos punteros ...................................................... 97

Funcin agregar ......................................................................................................................... 97

Funcin suprimir ....................................................................................................................... 97

Opeaciones sobre colas (implementacin: lista enlazada circular) .............................................. 97Funcin encolar ........................................................................................................................ 97

Funcin desencolar ................................................................................................................... 97

Operaciones sobre archivos .......................................................................................................... 97

Funcin read ........................................................................................................................... 97

Funcin write ......................................................................................................................... 97

Funcin seek ........................................................................................................................... 97

Funcin fileSize ......................................................................................................................... 97

Funcin filePos .......................................................................................................................... 97

Funcin busquedaBinaria ......................................................................................................... 97

Operaciones sobre estructuras dinmicas con TADS en struct .................................................... 97

El Nodo ...................................................................................................................................... 98

Operaciones s/Listas ..................................................................................................................... 98

Lista Implementada en struct ................................................................................................... 98

Funcin: agregarAlFinal ............................................................................................................ 98

Funcin: liberar ................................................................................................................... 98

Funciones para estructuras enlazadas .............................................................................................. 99

ANEXO 1 Biblioteca Standard C ....................................................................................................... 101

1.1. Definiciones Comunes ........................................................................................ 101

1.2. Manejo de Caracteres ......................................................................................... 101

1.3. Manejo de Cadenas ............................................................................................. 102


8/112


1.3.1. Concatenacin ............................................................................................................... 102

1.3.2. Copia .............................................................................................................................. 102

1.3.3. Bsqueda y Comparacin .............................................................................................. 102

1.3.4. Manejo de Memoria...................................................................................................... 102

1.4. Utilidades Generales ........................................................................................... 103

1.4.1. Tips y Macros ................................................................................................................. 103

1.4.2. Conversin ..................................................................................................................... 103

1.4.3. Administracin de Memoria ......................................................................................... 103

1.4.4. Nmeros Pseudo-Aleatorios ......................................................................................... 103

1.4.5. Comunicacin con el Entorno ....................................................................................... 104

1.4.6. Bsqueda y Ordenamiento ........................................................................................... 104

1.5. Entrada / Salida .................................................................................................... 1041.5.1. Tipos .............................................................................................................................. 104

1.5.2. Macros ........................................................................................................................... 105

1.5.3. Operaciones sobre Archivos .......................................................................................... 105

1.5.4. Acceso ........................................................................................................................... 105

1.5.5. Entrada / Salida Formateada ......................................................................................... 105

1.5.6. Entrada / Salida de a Caracteres ................................................................................... 106

1.5.7. Entrada / Salida de a Cadenas ....................................................................................... 106

1.5.8. Entrada / Salida de a Bloques........................................................................................ 106

1.5.9. Posicionamiento ............................................................................................................ 107

1.5.10. Manejo de Errores ....................................................................................................... 107

1.6. Otros ..................................................................................................................................... 107

1.6.1. Hora y Fecha .................................................................................................. 108

1.6.2. Matemtica ................................................................................................................... 108

ANEXO 2 Flujos de texto y binario C++ ........................................................................................... 109

C++ ifstream, ofstream y fstream ............................................................................................... 109Abrir los ficheros ..................................................................................................................... 109

Leer y escribir en el fichero ..................................................................................................... 110

Cerrar los ficheros ................................................................................................................... 110

Ejemplos Archivos de texto ..................................................................................................... 110

Ejemplo Archivo binario .......................................................................................................... 111


9/112


Acceso directo ......................................................................................................................... 111


10/112


Conceptos bsicos

1Objetivos de aprendizajeDominando los temas del presente capitulo Usted podr.

1. Conocer la terminologa propia de la disciplina.2. Definir y comprender claramente conceptos especficos muchas veces mal definidos3. Comprender el valor de la abstraccin.

4. Dar valor a la eficiencia en las soluciones5. Introducirse en la notacin algortmica y a la forma e encarar los problemas de

programacin

Introduccin:Se presenta el alcance del presente trabajo y se introducen conceptos fundamentales dealgoritmia y programacin, los que servirn de base para el desarrollo de los temas a tratar.

InformticaDisciplina del estudio sistematizado de los procesos algortmicos que describen y transformaninformacin, su teora, anlisis, diseo, eficiencia, implementacin y aplicacin.La informtica es una disciplina cientfica, matemtica y una ingeniera; tiene tres formas depensar propias: Teora, abstraccin y diseo.Las tres se complementan para la resolucin de la mayora de los problemas. Teora: Con el pensamiento terico se describen y prueban relaciones. Abstraccin: Recoleccin de datos y formulacin de un modelo, se eliminan los detalles

irrelevantes. Diseo: se tienen en cuenta requisitos, especificaciones y se disean o analizan

mecanismos para resolver problemas. Supone llevar a la prctica los resultados tericos.

ProgramacinLa programacin es una actividad transversal asociada a cualquier rea de la informtica, aunque

es la ingeniera del software el rea especfica que se ocupa de la creacin del software.En principio la programacin se vea como un arte, solo era cuestin de dominar un lenguaje deprogramacin y aplicar habilidades personales a la resolucin de problemas, casi en formaartesanal. El software era visto como algo desarrollado a travs de la intuicin sin la utilizacin demtodos de diseo con tcnicas para proceder en forma sistemtica y sin ningn control de sudesarrollo. Con el reconocimiento de la complejidad del desarrollo del software naci la ingenieradel software.


11/112


Se considero que al igual que cualquier otra disciplina la creacin de software deba ser reconocidacomo una actividad de ingeniera que requera la aplicacin de slidos principios cientficos.La ingeniera del software es la disciplina que se ocupa de la aplicacin del conocimiento cientficoal diseo y construccin de programas de computacin y a todas las actividades asociadas dedocumentacin, operacin y mantenimiento, lo que proporciona un enfoque sistemtico.La programacin es una actividad en la que la creatividad juega un rol primordialPrograma:Conjunto de instrucciones, ejecutables sobre una computadora, que permite cumplir una funcinespecifica. Se asocia al programa con una determinada funcin o requerimiento a satisfacer por laejecucin del conjunto de instrucciones que lo forman. En general alcanzan su objetivo en tiempofinito, aunque hay excepciones, por ejemplo los programas de control de un sistema de alarmaposeen requerimiento de tiempo infinito. Un programa sin errores que se ejecuta puede no sercorrecto si no cumple con los requerimientos.

DefinicinPrograma: conjunto de instrucciones no activas almacenadas en un computador, se vuelve tareaapartir de que se selecciona para su ejecucin y permite cumplir una funcin especfica. Un procesoes un programa en ejecucin.

En principio las tareas ms importantes a la que se enfrenta quien debe escribir programas encomputadoras son:

1. Definir el conjunto de instrucciones cuya ejecucin ordenada conduce a la solucin.2. Elegir la representacin adecuada de los datos del problema.

La funcin esencial del especialista informtico es explotar el potencial de las computadoras pararesolver situaciones del mundo real. Para esto debe analizar los problemas del mundo real, sercapaz de sintetizar sus aspectos principales y poder especificar la funcin objetivo que se desee.Posteriormente debe expresar la solucin en forma de programa, manejando los datos del mundoreal mediante una representacin valida para una computadora.

Partes de un programaLos componentes bsicos son las instrucciones y los datos. Las instrucciones o sentencias

representan las operaciones que se ejecutaran al interpretar el programa. Todos los lenguajes deprogramacin tienen un conjunto mnimo de operaciones que son las de asignacin, seleccin eiteracin. Un lenguaje con solo estas tres instrucciones permite escribir cualquier algoritmo.Los datos son valores de informacin de los que se necesita disponer, en ocasiones transformarpara ejecutar la funcin del programa.Los datos estn representados simblicamente por un nombre que se asocia con una direccinnica de memoria.El contenido de la direccin de memoria correspondiente a un dato constante se asigna solo unavez y solo puede ser modificado en una nueva compilacin. En cambio el contenido o valor de ladireccin de memoria correspondiente a un dato variable puede ser asignado o modificado entiempo de ejecucin.Un programa se corresponde con una transformacin de datos. A partir de un contextodeterminado por las precondiciones.El programa transforma la informacin debiendo llegar al resultado esperado produciendo elnuevo contexto caracterizado por las poscondiciones.

DatoRepresentacin de un objeto el mundo real mediante el cual se pueden modelizar aspectos de unproblema que se desea resolver con un programa en una computadora.

Definicin


12/112


Dato representacin de un objeto el mundo real mediante el cual se pueden modelizar aspectosde un problema que se desea resolver con un programa en una computadora. ->

Abstraccin

Proceso de anlisis del mundo real con el propsito de interpretar los aspectos esenciales de unproblema y expresarlo en trminos precisos.

ModelizacionAbstraer un problema del mundo real y simplificar su expresin, tratando de encontrar losaspectos principales que se pueden resolver, requerimientos, los datos que se han de procesar y elcontexto del problema.

PrecondicinInformacin conocida como verdadera antes de iniciar el programa.

PoscondicinInformacin que debiera ser verdadera al cumplir un programa, si se cumple adecuadamente elrequerimiento pedido.

EspecificacinProceso de analizar problemas del mundo real y determinar en forma clara y concreta el objetivoque se desea. Especificar un problema significa establecer en forma univoca el contexto, lasprecondiciones el resultado esperado, del cual se derivan las poscondiciones.

Lenguaje de programacinConjunto de instrucciones permitidas y definidas por sus reglas sintcticas y su valor semnticopara la expresin de soluciones de problemas.

Del problema real a su solucin por computadorasAnalizando un problema del mundo real se llega a la modelizacindel problema por medio de laabstraccin.A partir del modelo se debe elaborar el anlisis de la solucin como sistema, esto significa la

descomposicin en mdulos. Estos mdulos deben tener una funcin bien definida.La modularizacin es muy importante y no solo se refiere a los procesos a cumplir, sino tambin ala distribucin de los datos de entrada, salida y los datos intermedios necesarios para alcanzar lasolucin.Estudio de los datos del problema.Cada mdulo debe tener un proceso de refinamiento para expresar su solucin en formaordenada, lo que llevara a la construccin del algoritmo correspondiente.A partir de los algoritmos se pueden escribir y probar programas en un lenguaje determinado ycon un conjunto de datos significativos.Etapas de resolucin de problemas con computadoras.

1. Anlisis del problema: en su contexto del mundo real.2. Diseo de la solucin: Lo primero es la modularizacin del problema, es decir la

descomposicin en partes con funciones bien definidas y datos propios estableciendo lacomunicacin entre los mdulos.

3. Especificacin del algoritmo: La eleccin adecuada del algoritmo para la funcin de cadamodulo es vital para la eficiencia posterior.

4. Escritura del programa: Un algoritmo es una especificacin simblica que debe convertirseen un programa real sobre un lenguaje de programacin concreto.


13/112


5. Verificacin: una vez escrito el programa en un lenguaje real y depurado los erroressintcticos se debe verificar que su ejecucin conduzca al resultado deseado con datosrepresentativos del problema real.

Programacin modularprogramacin estructuradaSe dice modular porque permite la descomposicin del problema en mdulos y estructurada solopermite la utilizacin de tres estructuras: Asignacin, seleccin, repeticin.AlgoritmoEl termino algoritmo es en honor del matemtico rabe del siglo IX, Abu Jafar Mohamed ibn MusaAl Khowrizm. Refiere conjunto de reglas, ordenadas de forma lgica, finito y preciso para lasolucin de un problema, con utilizacin o no de un computador.En la actualidad al trmino se lo vincula fuertemente con la programacin, como paso previo a larealizacin de un programa de computacin aunque en realidad es una metodologa de resolucinpresente en muchas de las actividades que se desarrolla a lo largo de la vida.Desde los primeros aos de escuela se trabaja con algoritmos, en especial en el campo de lasmatemticas. Los mtodos utilizados para sumar, restar, multiplicar y dividir son algoritmos quecumplen perfectamente las caractersticas de precisin, finitud, definicin y eficiencia.Para que el algoritmo pueda ser fcilmente traducido a un lenguaje de programacin y luego ser

ejecutado la especificacin debe ser clara, precisa, que pueda ser interpretada con precisin ycorresponda a pocas acciones, si esto no ocurre ser necesario acudir a desarrollar un mayor nivelde refinamiento.La utilizacin de refinamientos sucesivos es lo que permite alcanzar la solucin modular que sepropone.Diseo modular, entonces, es la aplicacin del criterio de refinamientos sucesivos, partiendo de unplan de accin, determinando que hacer, por aplicacin de los conocimientos estratgicos deresolucin pasando luego al como hacerlo con los conocimientos tcticos para la realizacin delalgoritmo.La programacin de algoritmos representa un caso de resolucin de problemas que requiererepresentacin mental del mundo real, adaptacin para tener una solucin computable y criterio

para elegir una alternativa eficiente de implementacin.Cuando se analiza un problema, particularmente de programacin, y ste es difcil de describir, elplan de accin recomendable para alcanzar la solucin es comenzar trazando un esbozo de lasformas ms gruesas, para que sirvan de andamio a las dems; aunque algunas de ellas se debancambiar posteriormente. Despus, se agregan los detalles, (obtenindose el algoritmo refinado),para dotar a estos esqueletos de una estructura ms realista.Durante la tarea de integracin final, se descartan aquellas primeras ideas provisionales que ya noencajan en la solucin. Por lo que, hasta que no se haya visto el conjunto global es imposibleencontrarle sentido a ninguna de las partes por s solas.Siempre es mejor explicar un misterio en trminos de lo que se conoce, pero cuando esto resultadifcil de hacer, se debe elegir entre seguir tratando de aplicar las antiguas teoras, o dedescartarlas y probar con otras nuevas. Siguiendo este anlisis, se define como reduccionistas a

aquellas personas que prefieren trabajar sobre la base de ideas existentes, y como renovadores alos que les gusta impulsar nuevas hiptesis. En programacin debe encontrarse un equilibrio entreambas posturas.La programacin como toda actividad que requiere creatividad necesita que se produzca un saltomental que se puede sintetizar como seala David Perkins en:

1. Larga bsqueda, se requiere esfuerzo en analizar y buscar.2. Escaso avance aparente: el salto mental sobreviene tras un avance que parece escaso o no

muy evidente, pero sobreviene.


14/112


3. Acontecimiento desencadenante: El tpico proceso de hacer clic comienza con unacontecimiento que lo desencadena.

4. Chasquido cognitivo: De pronto aparece la solucin la que sobreviene con rapidez quehace que las piezas encajen con precisin, aun cuando sea necesario todava ajustaralgunos detalles. Pero la idea generadora apareci.

5. Transformacin. Este avance nos va modificando nuestro mundo mental.En sntesis, la practica del salto de pensamiento requiere en primer lugar de buscar analogas, ensegundo lugar juegan un papel importante las conexiones lgicas, formulacin de una preguntacrucial ocupa un papel decisivo. El repertorio de acciones tras el salto del pensamiento se expandepara incluir no solo la analoga sino una extrapolacin lgica y la formulacin de la preguntaadecuadaPara encontrar una solucin muchas veces se necesita desplazarse bastante por el entornoadecuado. Conforme a esto Thomas Edison declaro que la invencin significa 99% de transpiraciny 1% de inspiracin, en contraposicin con Platn que sostena que las soluciones aparecen porinspiracin divina.Muchos problemas son razonables, cabe razonarlos paso a paso para alcanzar la solucin. Otrosson irrazonables no se prestan a un a reflexin por etapas.

DefinicinAlgoritmoEspecificacin rigurosa (debe expresarse en forma univoca) de la secuencia de pasos,instrucciones, a realizar sobre un autmata para alcanzar un resultado deseado en un tiempofinito. Esto ltimo supone que el algoritmo empieza y termina, en el caso de los que no son detiempo finito (ej. Sistemas en tiempo real) deben ser de nmero finito de instrucciones.

En definitiva un algoritmo es una especificacin ordenada de la solucin a un problema de la vidareal. Son el fundamento de la programacin de computadores en el paradigma de programacinimperativo.Bajo este paradigma desarrollar un programa significa indicarle al computador, con precisin, sin

ambigedad y en un lenguaje que este pueda entender, todos y cada uno de los pasos que debeejecutar para lograr el objetivo propuesto.Previo a la traduccin en un lenguaje de programacin es necesario poder entender el problema,conocer las pre condiciones, establecer cual debe ser la pos condicin, o aquello que debe sercierto al finalizar la ejecucin del algoritmo, en definitiva entender claramente Quees lo que sedebe hacer para luego avanzar en Como hacerlo. Aqu debe utilizarse todas las herramientas alalcance de la mano para el desarrollo del algoritmo como paso previo a la solucin del problemapor el computador.Existen varias tcnicas para representar formalmente un algoritmo, una descriptiva llamadapseudo cdigo, y otras graficas como los diagrama de flujo, diagrama Nassi Sneiderman,Diagramas de Lindsay, diagramas de Jackson, entre otros, en este caso se presentara una notacinalgortmica similar a la presentada por Piere Scholl en el texto Esquemas algortmicosfundamentales: Secuencia e iteracin.

DefinicinAlgoritmo:Secuencia finita de instrucciones, reglas o pasos que describen en forma precisa las operacionesque una computadora debe realizar para llevar a cabo una tarea en tiempo finito [Knuth, 1968].


15/112


Descripcin de un esquema de comportamiento expresado mediante un repertorio finito deacciones y de informaciones elementales, identificadas, bien comprendidas y realizables a priori.Este repertorio se denomina lxico[Scholl, 1988].

Esta formado por reglas, pasos e instrucciones.Las reglas especifican operaciones.

La computadora es el agente ejecutor.La secuencia de reglas y la duracin de la ejecucin son finitas.

Caractersticas de un algoritmoUn algoritmo debe tener al menos las siguientes caractersticas:

1. Ser preciso: esto significa que las operaciones o pasos del algoritmo deben desarrollarseen un orden estricto, ya que el desarrollo de cada paso debe obedecer a un orden lgico.

2. Ser definido. Ya que en el rea de programacin, el algoritmo es el paso previofundamental para desarrollar un programa, es necesario tener en cuenta que elcomputador solo desarrollar las tareas programadas y con los datos suministrados; esdecir, no puede improvisar y tampoco inventar o adivinar el dato que necesite pararealizar un proceso. Por eso, el algoritmo debe estar plenamente definido; esto es, quecuantas veces se ejecute, el resultado depende estrictamente de los datos suministrados.Si se ejecuta con un mismo conjunto de datos de entrada, el resultado deber ser siempreel mismo.

3. Ser finito: esta caracterstica implica que el nmero de pasos de un algoritmo, por grandey complicado que sea el problema que soluciona, debe ser limitado. Todo algoritmo, sinimportar el nmero de pasos que incluya, debe llegar a un final. Para hacer evidente estacaracterstica, en la representacin de un algoritmo siempre se incluyen los pasos inicio yfin.

4. Presentacin formal: para que el algoritmo sea entendido por cualquier personainteresada es necesario que se exprese en alguna de las formas comnmente aceptadas;pues, si se describe de cualquier forma puede no ser muy til ya que solo lo entenderquien lo dise. Las formas de presentacin de algoritmos son: el pseudo cdigo,

diagrama de flujo y diagramas de Nassi/Schneiderman, entre otras. En esta publicacin sepropondr una notacin algortmica y se darn las equivalencias entre la propuesta y lasexistentes y tambin con las sentencias de los lenguajes de programacin, en particularPascal y C.

5. Correccin: el algoritmo debe ser correcto, es decir debe satisfacer la necesidad osolucionar el problema para el cual fue diseado. Para garantizar que el algoritmo logre elobjetivo, es necesario ponerlo a prueba; a esto se le llama verificacin o prueba deescritorio.

6. Eficiencia: hablar de eficiencia o complejidad de un algoritmo es evaluar los recursos decmputo que requiere para almacenar datos y para ejecutar operaciones frente albeneficio que ofrece. En cuanto menos recursos requiere ser ms eficiente el algoritmo.

La vida cotidiana est llena de soluciones algortmicas, algunas de ellas son tan comunes que no serequiere pensar en los pasos que incluye la solucin. La mayora de las actividades que se realizandiariamente estn compuestas por tareas ms simples que se ejecutan en un orden determinado,lo cual genera un algoritmo. Muchos de los procedimientos utilizados para desarrollar tareascotidianas son algortmicos, sin embargo, esto no significa que todo lo que se hace estdeterminado por un algoritmo.El primer paso en el diseo de un algoritmo es conocer la temtica a tratar, el segundo ser pensaren las actividades a realizar y el orden en que deben ejecutarse para lograr el objetivo, el tercero yno menos importante es la presentacin formal.


16/112


Propiedades de los algoritmos1. Especificacin precisa de la entrada: El algoritmo debe dejar claro el nmero y tipo de

datos de entrada y las condiciones iniciales que deben cumplir esos valores de entradapara conseguir que las operaciones tengan xito.

2. Especificacin precisa de cada instruccin: cada etapa del algoritmo debe estar definidacon precisin, no debe haber ambigedades sobre las acciones que se deben ejecutar encada momento.

3. Un algoritmo debe ser exacto y correcto: Un algoritmo se espera que resuelva unproblema y se debe poder demostrar que eso ocurre. Si las condiciones de entrada secumplen y se ejecutan todos los pasos el algoritmo entonces debe producir la salidadeseada.

4. Un algoritmo debe tener etapas bien definidas y concretas, un nmero finito de pasos,debe terminar y debe estar claro la tarea que el algoritmo debe ejecutar.

5. Debe ser fcil de entender, codificar y depurar.6. Debe hacer uso eficiente de los recursos de la computadora

Finitud: en longitud y duracin.Precisin: Determinar sin ambigedad las operaciones que se deben ejecutar.Efectividad: las reglas pueden ejecutarse sin el ordenador obtenindose el mismo resultado.Generalidad: Resolver una clase de problema y no un problema particular.Entradas y salidas: puede tener varias entradas pero una sola salida, el resultado que se debeobtener.

Eficiencia de un algoritmoSe pueden tener varias soluciones algortmicas para un mismo problema, sin embargo el uso derecursos y la complejidad para cada una de las soluciones puede ser muy diferente.La eficiencia puede definirse como una mtrica de calidad de los algoritmos asociada con lautilizacin optima de los recursos del sistema de cmputo donde se ejecutara el algoritmo, su

claridad y el menor grado de complejidad que se pueda alcanzar. Hacer todo tan simple como sepueda, no ms (Albert Einstein).La eficiencia como factor espacio temporal debe estar estrechamente relacionada con la buenacalidad, el funcionamiento y la facilidad del mantenimiento.Medidas de eficiencia para N = 10.0000

Eficiencia Iteraciones Tiempo estimadoLogartmica Log 2 N 14 Microsegundos

Lineal N 10.000 0.1 segundoLogartmica lineal N * Log 2 N 140.000 2 segundos

Cuadrtica N 2 10.000 2 15-20 minutos

Poli nmica N k 10.000 K Horas

Exponencial 2N

210.000

Inmedible

Complejidades ms comunes1. Complejidad constante: se expresa como O(1). Se encuentra en algoritmos sin ciclos, por

ejemplo en un intercambio de variables.2. Complejidad logartmica: Es una complejidad eficiente, la bsqueda binaria tiene esta

complejidad.3. Complejidad lineal: se encuentra en los ciclos simples.


17/112


4. Complejidad logartmica lineal: Los mejores algoritmos de ordenamiento tienen estacomplejidad.

5. Complejidad cuadrtica: Aparece en el manejo de matrices de dos dimensiones,generalmente con dos ciclos anidados.

6. Complejidad cbica: Aparece en el manejo de matrices de tres dimensiones, generalmentecon tres ciclos anidados.

7. Complejidad exponencial: es la complejidad de algoritmos recursivos.

Lxico y algoritmoPara escribir un algoritmo deben seguirse un conjunto de pasos bsicos

1. Comprender el problema2. Identificar los elementos a incluir en el lxico: constantes, tipos, variables y acciones.3. Encontrar la forma de secuenciar las acciones para obtener el resultado, esto es, alcanzar

las poscondiciones a partir de un estado inicial que cumple con la precondicin. Paraestablecer el orden de las acciones los lenguajes de programacin proporcionanmecanismos de composicin: Secuenciacin, anlisis de casos, iteracin y recursion.

4. Al organizar las acciones en el tercer paso puede ocurrir que se detecte que faltan

elementos en el lxico o que algn aspecto del problema no ha sido bien comprendido locual requerira volver a los pasos anteriores.

5. Nunca la solucin aparece en el primer intento, en general aparece en un proceso cclico,entonces se debe:

6. Escribir el lxico,a. escribir la primera versin,b. incluir en el lxico nuevos elementos que faltaban,c. escribir la nueva versin del algoritmo y as sucesivamente

Estructura de un algoritmo

LEXICO {Lxico Global del algoritmo}{Declaracin de tipos, constantes, variables y acciones}Accin 1

PRE {Precondicin de la accin 1}POS {Poscondicin de la accin 1}LEXICO {Lxico local, propio de la accin 1}

Declaraciones localesALGORITMO {Implementacin de la accin 1}

{Secuencia de instrucciones de la accin 1}FIN {Fin implementacin algoritmo de la accin 1}

ALGORITMOPRE {Precondicin del algoritmo principal}POS {Poscondicin del algoritmo principal}

{Secuencia de instrucciones del algoritmo principal}FIN {Fin del algoritmo principal}

Proceso ComputacionalSe refiere a un algoritmo en ejecucin. La ejecucin de las instrucciones origina una serie deacciones sobre elementos de memoria que representan informacin manejada por el algoritmo. Anivel algortmico se asigna un nombre a cada informacin de modo de manejar un par nombre-valor para cada informacin.


18/112


Una variable representa alguna entidad del mundo real, relevante para el problema que se quiereresolver. El efecto que producen las acciones del proceso sobre las variables produce cambio deestados o de sus valores.

DefinicionesPrograma: Algoritmo escrito en un lenguaje cuyas instrucciones son ejecutables por unacomputadora y que estn almacenados en un disco.Tarea: Un programa se vuelve tarea a partir del momento que se lo selecciona para su ejecucin yhasta que esta termina.Proceso:programa en ejecucin, se ha iniciado pero an no ha finalizado.Lenguajes de programacin: notacin que permite escribir programas a mayor nivel deabstraccin que los lenguajes de mquina. Sus instrucciones deben ser traducidas a lenguaje demquina.Lenguaje de mquina: Instrucciones que son ejecutables por el hardware de una computadora.Paradigmas de programacinParadigma: Coleccin de conceptos que guan el proceso de construccin de un programa. Estosconceptos controlan la forma en que se piensan y formulan los programas.

ImperativoProceduralObjetos.DeclarativoFuncionalLgico.Dato Informacin ConocimientoDato: sin interpretar.Informacin: aade significado al dato.Conocimiento: Aade propsito y capacidad a la informacin. Potencial para generar acciones.ProblemaEnunciado con una incgnita, la solucin es encontrar el valor de esa incgnita.Problema computacional o algortmico: tarea ejecutada por una computadora con unaespecificacin precisa de los datos de entrada y de los resultados requeridos en funcin de estos.Clase de problemas

No computables: No existe un algoritmo.ComputablesTratables: Existe un algoritmo eficiente.Intratable: No existe algoritmo eficiente.Expresiones Sentencias LxicoExpresiones: secuencia de operadores y operandos que se reduce a un solo valor.Sentencias: accin produce un efecto, puede ser primitiva o no primitiva.Lxico: Descripcin del conjunto de acciones e informaciones a partir de la cual se expresa elesquema de comportamiento del algoritmo.Pasos para resolver un algoritmoComprender el problema.Identificar informacin y acciones a incluir en el lxico (constantes, tipos, variables y acciones).Encontrar un camino de secuenciar las acciones para obtener el resultado, es decir para alcanzar laposcondicin a partir del estado inicial que cumple con la precondicin.Acciones primitivas y derivadasAcciones primitivas: Incorporadas por el lenguaje.Acciones derivadas: realizadas mediante la combinacin de acciones primitivas con el objeto dedesarrollar una tarea en particular. Son complementarias y pueden ser desarrolladas por elprogramador.


19/112


Estructura de un algoritmoLEXICO {Lxico Global del algoritmo}

{Declaracin de tipos, constantes, variables y acciones}Accin 1

PRE {Precondicin de la accin 1}POS {Poscondicin de la accin 1}LEXICO {Lxico local, propio de la accin 1}

Declaraciones localesALGORITMO {Implementacin de la accin 1}

{Secuencia de instrucciones de la accin 1}FIN {Fin implementacin algoritmo de la accin 1}

ALGORITMOPRE {Precondicin del algoritmo principal}POS {Poscondicin del algoritmo principal}

{Secuencia de instrucciones del algoritmo principal}FIN {Fin del algoritmo principal}

Resumen:En el presente capitulo se introdujeron trminos y frases de la disciplina en estudio.Se abordo el problema desde un punto de vista conceptual definiendo con precisin trminos yfrases para evitar ambigedades. Se puso especial nfasis en la necesidad de pensar las solucionesantes de escribir cdigo. Se establecieron cuales son los pasos que deben seguirse para unasolucin correcta de problemas y cuales son los problemas que pueden tratarse en formaalgortmica. Se defini cuales son las caractersticas deseables de los algoritmos y se introdujo elconcepto de eficiencia de modo de hacer, las cosas tan simple como se pueda.Se introdujo, adems una representacin semi formal para la descripcin de los algoritmos


20/112


Acciones y funciones

2Objetivos de aprendizajeDominando los temas del presente trabajo Usted podr.

1. Entender la descomposicin como forma de resolucin de problemas.2. Dar valor a la reusabilidad en bsqueda de la eficiencia en la escritura el cdigo.3. Establecer comunicacin entre mdulos.

4. Comprender las ventajas de la descomposicin5. Diferenciar acciones de funciones y los distintos tipos de parmetros y datos

IntroduccinEn este trabajo se analiza la descomposicin como forma de alcanzar la solucin de problemas.Una regla bsica de la programacin indica que si existe un programa de longitud L tal que L = L1 +L2, se dice que el esfuerzo de resolver L es mayor que la suma de los esfuerzos de resolucin de L1y L2, aun cuando haya que derivar esfuerzo para la integracin de los mdulos.

SI L = L 1 + L 2EntoncesEsfuerzo(L)> Esfuerzo(L1)+ Esfuerzo (L2)

Antes de analizar las particularidades de las acciones y funciones es necesaria la definicin de los

trminos que se utilizan.ModularizacionEn general los problemas a resolver son complejos y extensos, puede incluso presentarsesituaciones en que una parte del problema deba ser modificada para adaptarse a nuevosrequerimientos. Se hace necesario conocer algunas herramientas que permitan facilitar la solucinde estos problemas, la abstraccin y la descomposicin pueden ayudar a ello. La abstraccinpermitir encontrar y representar lo relevante del problema y la descomposicin se basa en elparadigma de dividir para vencer . La descomposicin tiene como objetivo dividir cadaproblema en subproblemas cada uno de los cuales ser de ms simple solucin.Es conveniente, e importante descomponer por varias razones:

Favorece la comprensin. Una persona entiende un problema de caractersticas complejas

partiendo la informacin, descomponiendolo. Por esto para comprender un problemacomplejo del mundo real es necesario dividirlo o modularizar.

Favorece el trabajo en equipo. Cada programador recibe las especificaciones la tarea arealizar y las restricciones con las que debe manejarse.

Favorece el mantenimiento. Las tareas involucradas en este mantenimiento, estnvinculadas con detectar corregir errores, modificar y/o ampliar codigo. Esto es mucho massencillo si se hace un anlisis y control de una porcin o modulo y luego se lo relaciona queatendiendo de una sola vez la totalidad del problema.


21/112


Permite la reusabilidad del cdigo. Siempre es deseable, de ser posible, hacer uso decdigo ya escrito.

Permite adems, como veremos, separar la lgica de la algoritmia con el tipo o estructurade dato involucrada. Alcanzando reusabilidad y diversidad de tipos tendiente a un criteriode programacin mas genrica centrada en la algoritmia.

MdulosUn problema debe ser descompuesto en subproblemas que se denominan mdulos en los quecada uno tendr una tarea especifica, bien definida y se comunicaran entre si adecuadamentepara conseguir un objetivo comn. Un modulo es un conjunto de instrucciones mas un conjuntode datos que realizan una tarea lgica.

Alcance de los datosEl desarrollo de un programa complejo con muchos mdulos en los que en cada uno de ellos sedeben definir los propios tipos de datos puede ocasionar algunos de los inconvenientes siguientes:

Demasiados identificadores.

Conflictos entre los nombres de los identificadores de cada modulo.

Integridad de los datos, lo que implica que puedan usarse datos que tengan igualidentificador pero que realicen tareas diferentes.

La solucin a estos problemas se logra con una combinacin entre ocultamiento de datos y uso deparmetros.

Datos locales y globalesUnos se declaran en la seccin de declaracin del programa principal, los otros en la seccin dedeclaracin de cada modulo. Otros pueden ser declarados en un bloque determinado, por lo quesolo tendr visibisilidad en el mismo.Local y global puede ser sido utilizado de manera absoluta pero los mdulos pueden anidarse lasreglas que gobiernan el alcance de los identificadores son:

El alcance de un identificador es el bloque del programa donde se lo declara.

Si un identificador declarado en un bloque es declarado nuevamente en un bloque internoal primero el segundo bloque es excluido del alcance de la primera seccin. Algunoslenguajes permiten la incorporacin de operadores de mbito.

Ocultamiento y proteccin de datosTodo lo relevante para un modulo debe ocultarse a los otros mdulos. De este modo se evita queen el programa principal se declaren datos que solo son relevantes para un modulo en particular yse protege la integridad de los datos.

ParmetrosSon variables cuya caracterstica principal es que se utilizan para transferir informacin entremdulos. En programas bien organizados toda informacin que viaja hacia o desde mdulos sehace a travs de parmetros.Hay dos tipos de parmetros, los pasados por valor y los pasados por referencia o direccin.Cuando existen datos compartidos entre mdulos una solucin es que un modulo pase una copiade esos datos al otro. En este caso el pasaje se denomina pasaje por valor. El modulo que recibeesta copia no puede efectuar ningn cambio sobre el dato original; el dato original se encuentrade este modo protegido de modificacin.


22/112


Los parmetros pasados por referencia o direccin no envan una copia del dato sino envan ladireccin de memoria donde el dato se encuentra por lo que tanto el proceso que lo llama como elproceso llamado pueden acceder a dicho dato para modificarlo.Razones por la que es conveniente la utilizacin de parmetros sobre las variables globales.

Integridad de los datosEs necesario conocer que datos utiliza con exclusividad cada modulo para declararlos como localesal modulo ocultndolo de los otros, si los datos pueden ser compartidos por ambos mdulosdebera conocerse cuales son, si el modulo los utiliza solo de lectura o puede modificarlos y es aqudonde se utilizan los parmetros.

Proteccin de datosSi una variable es local a un modulo se asegura que cualquier otro modulo fuera del alcance de lavariable no la pueda ver y por lo tanto no la pueda modificar. Dado que las variables globalespueden ser accedidas desde distintos mdulos, la solucin para evitar modificaciones no deseadases el pasaje como parmetros valor.

Uso de parmetros para retornar valoresSi bien el pasaje por valor es til para proteger a los datos, existen situaciones en las que serequiere hacer modificaciones sobre los datos y se necesitan conocer esas modificaciones. Paraesto se deben utilizar parmetros pasados por referencia. Los parmetros enviados por referenciason aptos adems para enviar datos en ambos sentidos.

Utilidad del uso de parmetrosEl uso de parmetros independiza a cadamodulo del nombre de los identificadores que utilizan losdems. En el caso de lenguajes fuertemente tipiados solo importa la correspondencia en cantidadtipo y orden entre los actuales del llamado y los formales de la implementacin con independenciadel nombre del identificador.

ReusabilidadEl uso de parmetros permite separar el nombre del dato, del dato en si mismo, lo que permiteque el mismo cdigo sea utilizado en distintas partes del programa simplemente cambiando la

lista de parmetros actuales.

AccionesEl lxico establece el nivel de abstraccin de un algoritmo. Es decir, introduce las variables, lasconstantes, los tipos de datos y las acciones con que se construye el algoritmo.El concepto de accin est muy ligado al concepto de abstraccin. Se analiza como abstraccin porparametrizacin y abstraccin por especificacin.Las acciones pueden desarrollar distintos clculos y retornar cero, uno o mas resultados alprograma que lo invoca. En general se los usa con una invocacin a si mismo, no retornan valor enel nombre (solo podra retornar uno), en cambio retornan valores en los parmetros (losparmetros variables o enviados por referencia.

Utilizacin de acciones

Una accines una secuencia de instrucciones que se identifica por un nombre y que puede serinvocada desde un algoritmo principal o desde otra accin. Cuando una accin es invocada desdealgn punto de un algoritmo, el flujo de ejecucin se traslada a la primera instruccin de la accin,entonces la accin se ejecuta hasta el final y cuando acaba, el flujo se traslada de nuevo a lainstruccin del algoritmo que sigue a aquella que origino la invocacin.Una accin debe tener un efecto bien definido, lo que significa que debe ser cohesiva. El nombrede la accin es conveniente que evoque la tarea que realiza. Hay que definir acciones que seanaplicables a cualquier posible conjunto de valores de entrada y no a un valor concreto.


23/112


Entre una accin y el algoritmo que la invoca se debe producir una comunicacin de valores: elalgoritmo debe proporcionar los valores de entrada y la accin puede retornar el resultado, opuede modificar el estado de alguno de ellos.Puede haber acciones en las que la comunicacin se realice mediante variables globales definidasen el mbito del algoritmo principal, que pueden ser manejadas por la accin. Pero esta no es laforma mas apropiada. Una accin, en principio, nunca debera acceder a variables globales.Losparmetrosson el mecanismo que posibilita escribir acciones generales, aplicables a cualquiervalor de la entrada, e independientes del lxico del algoritmo.

Acciones con parmetrosUn parmetroes un tipo especial de variable que permite la comunicacin entre una accin y elalgoritmo que la invoca, ya sea que este pase a la accin un valor de entrada o bien que la accindevuelva el resultado al algoritmo, o que pasen ambas cosas simultneamente.A los parmetros que proporcionan un valor de entrada se los llaman Parmetros dato, y a losque, adems de recoger un valor, retornan un resultado, se los llama dato-resultado. En ladeclaracin de una accin, la lista de los parmetros se indica despus del nombre de la accinentre parntesis y separados por coma.Nombre(dato tipo p1 ,dato-resultado tipo p2 )

Un parmetro tambin cuenta con una caracterstica: la direccin de memoria en la que se realizala transmisin de la informacin.Se denomina paso de parmetros al modo en que se establece la comunicacin entre losargumentos pasados a la accin desde el algoritmo y los parmetros de la accin; en la llamada sepasan los datos de entrada, y en el retorno se devuelven los resultados. Cada argumento se ligacon el parmetro que ocupa la misma posicin en la declaracin de la accin y ambos debencoincidir en tipo.En la invocacin a una accin, el algoritmo debe proporcionar un valor para cada parmetro dato,mientras que debe indicar para cada parmetro dato-resultado (&) qu variable de su lxicorecoger el valor.

Abstraccin y acciones

El trmino abstraccin se refiere al proceso de eliminar detalles innecesarios en el dominio delproblema y quedarse con aquello que es esencial para encontrar la solucin. Como resultado deaplicar la abstraccin, se obtiene un modelo que representa la realidad que nos ocupa. Estemodelo no es la realidad, es una simplificacin de esa realidad que establece un nivel deabstraccin mas apropiado para razonar sobre el problema y encontrar la solucin.La abstraccin tambin est relacionada con los lenguajes de programacin. Estos ofrecenmecanismos de abstraccin que determinan la forma de razonar de un programador.El concepto de accin conjuga dos tcnicas de abstraccin que son la parametrizacin y laespecificacin. La parametrizacin es un mecanismo por el cual se generaliza una declaracin paraque no sea aplicado a un nico caso, sino que sirva para cualquier valor que pueda tomar ciertoparmetro.La abstraccin por especificacin es la separacin entre la especificacin (el Qu) y laimplementacin (el cmo). En el caso de acciones, se refiere a distinguir entre la descripcin dequ hace la accin y el cmo se la implementa. Una vez que se define una nueva accin, se lasutiliza del mismo modo que si se tratase de una accin primitiva.Del mismo modo que el algoritmo, las acciones se especifican mediante una precondicin y unaposcondicin. La precondicin establece las restricciones que satisfacen los parmetros (datos deentrada) para que se pueda ejecutar la accin, y la postcondicin describe el resultado.


24/112


Cada accin debe ir siempre acompaada de una descripcin textual de su efecto y de suprecondicin y postcondicin. De esta forma, cualquier programador podra conocer qu hace ypodra utilizarla sin conocer cmo lo hace.El programador solo debe preocuparse por que se cumpla la precondicin al invocar la accin ytendr la certeza de que la accin cumplir su objetivo.

Tipos de ParmetrosUna accin se comunica con el algoritmo que lo invoca a travs de los parmetros. Es necesariauna comunicacin en dos sentidos. El algoritmo debe proporcionar los datos de entrada quemanipular durante su ejecucin y la accin debe retornar los resultados que obtiene.El tipo de parmetroindica cmo los valores de los argumentos son ligados a los parmetros.El tipo de parmetro datosolo permite que el parmetro pueda recibir el valor de un argumentomientras que el tipo de parmetro dato-resultadopermite que el parmetro pueda recibir un valory pueda retornar un resultado. En la declaracin de una accin hay que indicar el tipo de cadaparmetro. La declaracin de una accin se la denomina cabecera.Se denomina paso por valoral paso de parmetros que corresponda al tipo de parmetro dato ypaso por referenciaal que corresponda al tipo de parmetro dato-resultado.Parmetro dato(o parmetro de entrada)

El valor del argumento es asignado al parmetro en el momento de la llamada. El argumentopuede ser una expresin del mismo tipo de dato que el parmetro. Se trata de una comunicacinunidireccional: solamente se transmite informacin desde el punto del llamado hacia la accin.Una regla de buen estilo de programacin es no modificar el valor de parmetros tipo dato,aunque ello no tenga efecto fuera de la accin.Parmetro dato-resultado(o parmetro de entrada y salida)El valor del argumento es asignado al parmetro en el momento de la llamada y al final de laejecucin el valor del parmetro es asignado al argumento. Se trata de una comunicacinbidireccional. Si la ejecucin de la accin provoca un cambio en el valor del parmetro, en elmomento del retorno el argumento tendr el valor del parmetro al finalizar la ejecucin.Un argumento para un parmetro dato-resultado debe ser una variable del mismo tipo de dato

que el parmetro y no puede ser una expresin.Accin para el intercambio de dos variables: La accin recibe dos identificadores con dos valores ydebe retornar los identificadores con los valores cambiadosIntercambiar(dato-resultado a, b : Entero) : una accinPRE { a, b : Entero, a = A, b = B }POST { a = B, b = A }LXICO

t : EnteroALGORITMOt = a;a = b;b = t

FIN

Ejemplo en C++./* Funcion que no retorna valor en su nombre, el tipo de retorno void es lo que lo indica. Lafuncin tiene dos parmetros que son pasados por referencia o direccin, el & delante del

Estos son los parmetros, que como

deber ser modificados sus valores por

la accion se definen como Dato-

Resultado, son las variables que

intercambian informacion entre el

programa principal y el modulo. Son

Este identificador se

necesita como variable

auxiliar para poder hacer

el intercambio. Su valor no

lo necesita el programa

que invoca a la accion, solo

interesa su visibilidad en el

modulo por tanto no es


25/112


parmetro es el que lo indica. Al ser enviados por referencia el programa que lo invoca recibe losidentificadores con los valores intercambiados */void Intercambiar ( int &a, int &b){// comienzo del bloque de declaracin de la funcion

int t; //declaracin de una variable auxiliar tt = a; //asignacin a t del valor de a, para contenerloa = b; //asignacin a a del valor de b para intercambiarlob = t; //asignacin a b del valor que contena originalmente a.

} // fin del bloque de la funcion

Beneficios del uso de accionesEn la actualidad, las clases de los lenguajes orientados a objetos son los mecanismos msadecuados para estructurar los programas. No obstante, las acciones no desaparecen con estosnuevos mecanismos porque dentro de cada clase se encuentran acciones.Una accin tiene cuatro propiedades esenciales. Ellas son:

1. Generalidad2. Ocultamiento de informacin3. Localidad

4. Modularidad

De estas propiedades, se deducen una serie de beneficios muy importantes para el desarrollo dealgoritmos.

1. Dominar la complejidad2. Evitar repetir cdigo3. Mejorar la legibilidad4. Facilitar el mantenimiento5. Favorecer la correccin6. Favorecer la reutilizacin

La funcin desarrollada tiene la propiedad de la reusabilidad ya mencionada, es decir, puede ser

invocada en distintos puntos del programa con pares de identificadores de tipo entero y producirel intercambio. Sin embargo para que pueda producirse el intercambio utilizando esta accin elrequerimiento es que los parmetros sean de tipo int.Algoritmos de UTNFRBA utilizara para las implementaciones C++. Este lenguaje agrega unacaracterstica de reutilizacin de cdigo realmente poderosa que es el concepto de plantilla. Lasplantillas de funciones, que son las que utilizaremos son de gran utilidad para evitar escribir cdigocuando las acciones deben realizar operaciones idnticas pero con distintos tipos de datos.Las definiciones de las plantillas comienzan con la palabra template seguida de una lista deparmetros entre , a cada parmetro que representa un tipo se debe anteponer la palabra

typenameo class. Nosotros usaremos typename. Por ejemplo:template si solo involucra un tipo de datootemplate < typename R, typename T> si involucra dos tipos de dato diferentes

La funcin del ejemplo tiene un solo tipo de dato que es int, si quisiramos hacer el intercambioutilizando variables de otro tipo, por ejemplo doubl, tambin tendramos un nico tipo en toda laaccin. En lugar de colocar un tipo definido optaremos por un tipo gentico al que llamaremos T.

La funcin quedara://definicion de la plantilla de la funcin intercambiar


26/112


template < typename T>void Intercambiar ( T &a, T &b) //con dos parmetros de tipo generico{// comienzo del bloque de declaracin de la funcion

T t; //declaracin de una variable auxiliar tt = a; //asignacin a t del valor de a, para contenerloa = b; //asignacin a a del valor de b para intercambiarlob = t; //asignacin a b del valor que contena originalmente a.


El tipo genrico es T por lo cual en cada aparicin de int de la funcin original fue reemplado por eltipo genrico y ahora la misma accin es valida no solo para diferentes pares de valores(reusabilidad) sino adems para distintos tipos de datos (polimorfismo)

FuncionesSi el propsito es calcular un valor a partir de otros que se pasan con argumentos y se utilizanacciones, habr que definir un parmetro dato-resultado para que retorne el valor calculado. Lasacciones que retornan valor en los parmetros no pueden ser utilizadas en una expresin.

Para resolver este problema, los lenguajes de programacin incorporan el concepto de funcin.Las funciones devuelven un nico valor. La funcin supone extender el conjunto de operadoresprimitivos. Se invocan en una expresin.En cada declaracin se especifica el nombre de la funcin, la lista de los parmetros y finalmenteel tipo de valor que retorna la funcin.Nombre_funcion (par1: td1; ... ; parn: tdn) : tr : una funcinUna funcin no debe tener efectos laterales. Es decir, debe limitarse a calcular un valor y nomodificar ninguno de los que se describen en el momento de la invocacin.Las acciones se utilizan para extender el conjunto de acciones primitivas. Las funciones permitenextender el conjunto de funciones u operadores primitivos. Siempre deben utilizarse dentro deuna expresin.

Funcin que obtenga el mayor de tres nmeros

Max(a, b, c : Entero)Entero : una funcinALGORITMO

SI (a >= b) y (a >= c)ENTONCES

Max = aSINO SI (b >= a) y (b >= c)ENTONCES

Max = bSINO

Max = cFIN_SIFIN_SI

FIN.

//definicion de la plantilla de la funcin Maxtemplate < typename T>T Max ( T a, T b, T b) \* vea que la funcin retorna un valot de tipo T y los parmetros no

estn pasados por referencia*\

Las funciones siempre retornan un unico

valor. El identificador del nombre de la

funcion se puede utilizar en una expresin

como cualquier identificador del tipo que

retorna. Las funciones pueden retornar un

escalar un apuntadoro un registro


27/112


{// comienzo del bloque de declaracin de la funcionT t = a; //declaracin de una variable auxiliar t para contener el maximoif (b > t) t = b;if (c > t) t = c;return t; //retorna en t el valor del maximo.


Concepto de recursividad:Es un proceso que se basa en su propia definicin. Una funcin puede invocarse a s misma comoparte de los tratamientos de clculo que necesita para hacer su tareaParte de instancias complejas y las define en trminos de instancias ms simples del mismoproblema, llegando a un punto donde las instancias ms simples son definidas explcitamente.Define el problema en trminos de un problema ms simple de la misma naturaleza.Debe disminuir el espacio del problema en cada llamada recursivaHay una instancia particular que se conoce como caso base o caso degeneradoDivide el problema original en subproblemas ms pequeos. Cuando es lo suficientemente chicose resuelve directamente y se combinan soluciones del subproblema hasta que queda resuelto el

problema

Tiene: Una ecuacin de recurrencia, en funcin de trminos anteriores Tn= F(Tn-1, Tn-2, T0). Uno o varios trminos particulares que no dependen de los anteriores. Ti = G (i)(base)

Funcion Factorial Ecuacin de recurrencia : n! = n * (n-1)! Condiciones particulares: 0! = 1

Instancias que permanecen en memoria:

Funcion PotenciaNatural Ecuacin de recurrencia : an= a (n-1)* a si n > 1 Condiciones particulares: a0= 1

Funcion DivisionNaturalDados dos valores num y den, con den 0 se puede definir el clculo del cociente y el resto delsiguiente modo: Si num < denel cociente es = y el resto num. Si num


28/112


Meses Padres Hijos Nietos Cant Parejas0 I 1

1 M 1

2 M I 23 M M I 3

4 M M M I I 55 M M M M I M I I 8

Diseo y verificacin de algoritmos recursivosPotenciaNatural (a: Real; n : Entero)Real : una funcinEspecificacin Formal:Pre: {(n >=0) y (n = 0a 0}Pos: {PotenciaNatural (a,n) = an}Anlisis de casos:Caso trivial Solucion caso Trivial n = 0 an= 1

Caso no trivial Solucion caso no trivial N > 0 an = a (n-1)* aComposicinPotenciaNatural(a : Real; n : Entero)Real : una funcin;Pre: {(n >=0) y (n = 0a 0}Pos: {PotenciaNatural (a,n) = an}ALGORITMO

Segn nn = 0 : PotenciaNatural1;n > 0 : PotenciaNaturala * Potencianatural (a1)

FINVerificacin Formal: debe demostrarse que:

Para cualquier dato de entrada que satisfaga la precondicin se cumple la condicinbooleana del caso trivial o no trivial.Q(x) Bt(x) o Bnt(x)

Para cualquier dato de entrada que satisfaga la precondicin y la condicin del caso notrivial, los datos de entrada correspondientes a la llamada recursiva respetan laprecondicinQ(x) y Bnt (x) Q(S(x))

La solucin calculada en el caso trivial respeta la poscondicionQ(x) y Bt(x) R(x, triv(x))

Recursividad Indirecta:

Procedure B(); forward;

Procedure A();BeginEnd.

funcionA();

funcionb();main(){funcionA();

Eliminacin de la recursividadToda funcion recursiva puede ser transformada a la forma iterativa mediante una pila (LIFO).La recursin es una abstraccin, una construccin artificial que brindan los compiladores comoherramienta extra para resolver problemas, sobretodo aquellos que son de naturaleza recursiva.

A B


29/112


BBR (a; inferior, superior : Entero; clave: Info)central: EnteroSi (inferior > Superior ) BBR-1SI_NOCentral(inferior + suoerior)/2Si (a[central] 0 clave BBRcentralSI_NO

Si (-------

RecorrerEnOrdenArbol(Dato Arbol: TPNodo; Dato Valor: Tinfo) una accionALGORITMO

SI (Arbol NULO)ENTONCES

RecorrerEnOrdenArbol(Arbol^.izquierdo);Imprimir(Arbol*.info);

RecorrerEnOrdenArbol(Arbol^.Derecho);FIN_SI;

InsertarNodoArbol(Dato_Resultado Arbol: TPNodo; Dato Valor: Tinfo) una accionALGORITMO

SI (Arbol NULO)ENTONCES {Nuevo(Arbol); Arbol^;}SINO SI (ValorArbol^.info)

ENTONCES InsertarNodoArbol(Arbol^.izquierdo, Valor)SINO ERROR

FIN

Resumen:

En este trabajo se avanza sobre la necesidad de mayor abstraccin procedural introduciendoconceptos claves de programacin como acciones y funciones como la forma mas adecuada deestructurar problemas en el paradigma procedural. Es una introduccin a la abstraccinprocedural y de datos que servir de base para sustentar futuros conocimientos de estructuracinde programas en clases cuando se aborde, en otra instancia, la programacin orientada a objetos.Se dio valor a trminos como reusabilidad, ocultamiento de datos, polimorfismo y cohesin. Seintrodujeron conceptos como parmetros actuales, argumentos, parmetros formales, pasaje porvalor, pasaje por referencia. Si introdujo un concepto desde el punto de vista de la algoritmiaimportante como la programacin genrica que permite el lenguaje que estamos abordando.


30/112


Arreglos y registros

3Tipos de DatosIdentifica o determina un dominio de valores y el conjunto de operaciones aplicables sobre esosvalores.

1. Primitivos.2. Derivados.

3. Abstractos.

Los algoritmos operan sobre datos de distinta naturaleza, por lo tanto los programas queimplementan dichos algoritmos necesitan una forma de representarlos.Tipo de dato es una clase de objeto ligado a un conjunto de operaciones para crearlos ymanipularlos, un tipo de dato se caracteriza por

1. Un rango de valores posibles.2. Un conjunto de operaciones realizadas sobre ese tipo.3. Su representacin interna.

Al definir un tipo de dato se esta indicando los valores que pueden tomar sus elementos y las

operaciones que pueden hacerse sobre ellos.Al definir un identificador de un determinado tipo el nombre del identificador indica la localizacinen memoria, el tipo los valores y operaciones permitidas, y como cada tipo se representa de formadistinta en la computadora los lenguajes de alto nivel hacen abstraccin de la representacininterna e ignoran los detalles pero interpretan la representacin segn el tipo.

Como ya vimos, los tipos de datos pueden ser.1. Estticos:Ocupan una posicin de memoria en el momento de la definicin, no la liberan

durante el proceso solamente la liberan al finalizar la aplicacin.a. Simples: Son indivisibles en datos mas elementales, ocupan una nica posicin

para un nico dato de un nico tipo por vez.i. Ordinales: Un tipo de dato es ordinal o esta ordenado discretamente si

cada elemento que es parte del tipo tiene un nico elemento anterior(salvo el

material oficial 2014

Documents