resumen unidad 1-2

Vista previa del material en texto

Unidad 3 Estructuras repetitivas
Bucle o lazo: sección de código o secuencia de instrucciones que se repite un número determinado de veces. 
Iteración: repetición de la ejecución o pasada a través del bucle
Bucles más típicos: 
· Mientras (while) 
· Hacer-mientras (do while) 
· Repetir-hasta que (repeat) 
· Desde/Hasta (for)
Las dos principales preguntas a realizarse en el diseño de un bucle son: 
· ¿qué contiene el bucle? 
· ¿cuántas veces se debe repetir?( Siempre habrá una CONDICIÓN para poder detener el bucle.)
Los casos generales de estructuras repetitivas dependen de la situación y modo de la condición. La condición se evalúa tan pronto se encuentra en el algoritmo y su resultado producirá los siguientes tipos de estructuras:
· While: La condición de salida del bucle se realiza al principio del bucle.
· Do-While: La condición de salida se origina al final del bucle; el bucle se ejecuta hasta que se verifica una cierta condición.
· For: La condición de salida se realiza con un contador que cuenta el número de iteraciones.
· Repeat: Condición al final.
WHILE
La estructura repetitiva mientras (en inglés while o do-while: hacer mientras) es aquella en que el cuerpo del bucle se repite mientras se cumple una determinada condición. Cuando se ejecuta la instrucción mientras, la primera cosa que sucede es que se evalúa la condición (una expresión booleana). Si se evalúa falsa, no se toma ninguna acción y el programa prosigue en la siguiente instrucción del bucle. Si la expresión booleana es verdadera, entonces se ejecuta el cuerpo del bucle, después de lo cual se evalúa de nuevo la expresión booleana. Este proceso se repite una y otra vez mientras la expresión booleana (condición) sea verdadera.
El bucle while al igual que el bucle for evalúan la expresión al comienzo del bucle de repetición; siempre se utilizan para crear bucle pre-test. Los bucles pre-test se denominan también bucles controlados por la entrada. En numerosas ocasiones se necesita que el conjunto de sentencias que componen el cuerpo del bucle se ejecuten al menos una vez sea cual sea el valor de la expresión o condición de evaluación. Estos bucles se denominan bucles post-test o bucles controlados por la salida. 
DO WHILE
El bucle do-while es análogo al bucle while y el cuerpo del bucle se ejecuta una y otra vez mientras la condición (expresión booleana) sea verdadera. Existe, sin embargo, una gran diferencia y es que el cuerpo del bucle está encerrado entre las palabras reservadas hacer y mientras, de modo que las sentencias de dicho cuerpo se ejecutan, al menos una vez, antes de que se evalúe la expresión booleana. En otras palabras, el cuerpo del bucle siempre se ejecuta, al menos una vez, incluso aunque la expresión booleana sea falsa.
Una sentencia do-while es similar a una sentencia while, excepto que el cuerpo del bucle se ejecuta siempre al menos una vez.
REPEAT
La estructura repetir (repeat) se ejecuta hasta que se cumpla una condición determinada que se comprueba al final del bucle. El bucle repetir-hasta_que se repite mientras el valor de la expresión booleana de la condición sea falsa, justo la opuesta de la sentencia mientras.
DIF ENTRE WHILE Y REPEAT
· La estructura mientras termina cuando la condición es falsa, mientras que repetir termina cuando la condición es verdadera.
· En la estructura repetir el cuerpo del bucle se ejecuta siempre al menos una vez; por el contrario, mientras es más general y permite la posibilidad de que el bucle pueda no ser ejecutado. Para usar la estructura repetir debe estar seguro de que el cuerpo del bucle —bajo cualquier circunstancia— se repetirá al menos una vez.
FOR
Cuando se conoce de antemano el número de veces que se desean ejecutar las acciones de un bucle se debe usar la estructura desde o para (for, en inglés).
 La estructura desde ejecuta las acciones del cuerpo del bucle un número especificado de veces y de modo automático controla el número de iteraciones o pasos a través del cuerpo del bucle
COMPARACION DE BUCLES
While.
· Bucle controlado por la entrada. Condición al principio. Pretest. 
· Se ejecuta siempre que la condición sea verdadera. 
· El cuerpo del bucle puede no ser ejecutado. 
· Se debe utilizar cuando se desea saltar el bucle si la condición es falsa. 
· Bucle de condición variable.
Do-While. 
· Bucle controlado por la salida. Condición al final. Posttest.
· Es adecuada cuando se debe asegurar que al menos se ejecuta el bucle una vez. 
For. 
· Bucle controlado por la entrada. Condición al principio. Pretest.
· Bucle de conteo cuando el número de repeticiones se conoce por anticipado y puede ser controlado por un contador. Conteo fijo. 
Repeat. 
· Bucle controlado por la salida. Condición al final. 
· Se ejecuta siempre que la condición sea falsa. 
· Al menos el bucle se ejecuta una vez.
DISEÑO DE BUCLES
El diseño de un bucle requiere tres partes: 
1. El cuerpo del bucle. 
2. Las sentencias de inicialización. 
3. Las condiciones para la terminación del bucle.
La inicialización de variables se realiza antes de ejecutar el bucle y no necesariamente es cero.
FIN DE UN BUCLE
Existen cuatro métodos utilizados normalmente para terminar un bucle de entrada: 
1. Lista encabezada por tamaño: Si su programa puede determinar el tamaño de una lista de entrada por anticipado, bien preguntando al usuario o por algún otro método, se puede utilizar un bucle “repetir n veces” para leer la entrada exactamente n veces, en donde n es el tamaño de la lista. 
2. Preguntar antes de la iteración: preguntar, simplemente, al usuario, después de cada iteración del bucle, si el bucle debe ser o no iterado de nuevo. Este método es muy tedioso para listas grandes de números. Cuando se lea una lista larga es preferible incluir una única señal de parada, como se incluye en el método siguiente.
3. Lista terminada con un valor centinela: Un valor centinela es aquél que es totalmente distinto de todos los valores posibles de la lista que se está leyendo y de este modo sirve para indicar el final de la lista.
4. Agotamiento de la entrada: comprobar simplemente si todas las entradas del archivo se han leído y se alcanza el final del bucle cuando no hay más entradas a leer.
ESTRUCTURAS REPETITIVAS ANIDADAS
La estructura interna debe estar incluida totalmente dentro de la externa y no puede existir solapamiento.
SALIDAS INTERNAS DE LOS BUCLES
En ocasiones es necesario disponer de una estructura repetitiva que permita la salida en un punto intermedio del bucle cuando se cumpla una condición. Las salidas de bucles suelen ser válidas en estructuras mientras, repetir y desde
SENTENCIA DE SALTO
Las sentencias de salto se utilizan para influir en el flujo de ejecución de un bucle
· SENTENCIA INTERRUMPIR (BREAK): Se utiliza para terminar un bucle en un lugar determinado del cuerpo del bucle en vez de esperar que el bucle termine de modo natural por su entrada o por su salida.
· SENTENCIA CONTINUAR(CONTINUE): Hace que el flujo de ejecución salte el resto de un cuerpo del bucle para continuar con el siguiente bucle o iteración. Esta característica suele ser útil en algunas circunstancias.
INVARIANTES: Un ciclo invariante es una condición que siempre es verdadera en un punto específico de un algoritmo
UNIDAD 4 PROGRMACION MODULAR -- SUB PROBLEMAS
Un método ya citado para solucionar un problema complejo es dividirlo en subproblemas
Este método de diseñar la solución de un problema principal obteniendo las soluciones de sus subproblemas se conoce como diseño descendente (top-down design). 
Se denomina descendente, ya que se inicia en la parte superior con un problema general y el diseño específico de las soluciones de los subproblemas. 
Normalmente las partes en que se divide un programa deben poder desarrollarse independientemente entre sí.
Las soluciones de un diseño descendente pueden implementarse fácilmente en lenguajes de programación de alto nivel. Estas partes independientes se denominan subprogramas o subalgoritmos si se emplean desde el concepto algorítmico.
SUBPROGRAMAS
Lasolución de estos subproblemas se realiza con subalgoritmos. El uso de subalgoritmos permite al programador desarrollar programas de problemas complejos utilizando el método descendente.
Los subalgoritmos (subprogramas) pueden ser de dos tipos:
· Procedimientos o subrutinas. 
· Funciones.
El problema principal se soluciona por el correspondiente programa o algoritmo principal —también denominado controlador o conductor (driver)— y la solución de los subproblemas mediante subprogramas, conocidos como procedimientos (subrutinas) o funciones. Los subprogramas, cuando se tratan en lenguaje algorítmico, se denominan también subalgoritmos. 
Un subprograma puede realizar las mismas acciones que un programa: 
1) aceptar datos, 
2) realizar algunos cálculos 
3) devolver resultados
Un subprograma, sin embargo, se utiliza por el programa para un propósito específico. El subprograma recibe datos desde el programa y le devuelve resultados.
FUNCIONES
Una función es una operación que toma uno o más valores llamados argumentos y produce un valor denominado resultado
Cuando las funciones estándares o internas no permiten realizar el tipo de cálculo deseado es necesario recurrir a las funciones externas que pueden ser definidas por el usuario mediante una declaración de función. 
A una función no se le llama explícitamente, sino que se le invoca o referencia mediante un nombre y una lista de parámetros actuales. El algoritmo o programa llama o invoca a la función con el nombre de esta última en una expresión seguida de una lista de argumentos que deben coincidir en cantidad, tipo y orden con los de la función que fue definida. La función devuelve un único valor.
DECLARACION DE FUNCIONES
· LISTA DE PARAMENTROS: formales o argumentos, con uno o más argumentos de la siguiente forma: ({E|S|E/S} tipo_de_datoA: parámetro 1[, parámetro 2]...;
· NOMBRE DE LA FUNCION: nombre asociado con la func. identificador valido
· ACCIONES: instrucciones que constituyen la definición de la función y que debe contener una única instrucción: devolver (<expresion>); expresión sólo existe si la función se ha declarado con valor de retorno y expresión es el valor devuelto por la función.
· TIPO DE RESULTADO: resultado que devuelve la funcion
· SENTENCIA DEVOLVER (RETURN): se utiliza para volver a la función., termina inmediatamente la función en la cual se ejecuta
INVOCACION A FUNCIONES
Para que las acciones descritas en un subprograma función sean ejecutadas, se necesita que éste sea invocado desde un programa principal o desde otros subprogramas a fin de proporcionarle los argumentos de entrada necesarios para realizar esas acciones. 
Los argumentos de la declaración de la función se denominan parámetros formales, ficticios o mudos (“dummy”); son nombres de variables, de otras funciones o procedimientos y que sólo se utilizan dentro del cuerpo de la función.
Los argumentos utilizados en llamada a la función se denominan parámetros actuales, que a su vez pueden ser constantes, variables, expresiones, valores de funciones o nombres de funciones o procedimientos.
· nombre_función: función que llama
· lista de parámetros: actuales constantes, variables, expresiones, valores de funciones. Nombres de funciones o procedimientos 
Cada vez que se llama a una función desde el algoritmo principal se establece automáticamente una correspondencia entre los parámetros formales y los parámetros actuales. Debe haber exactamente el mismo número de parámetros actuales que de parámetros formales en la declaración de la función y se presupone una correspondencia uno a uno de izquierda a derecha entre los parámetros formales y los actuales. 
Una llamada a la función implica los siguientes pasos: 
1. A cada parámetro formal se le asigna el valor real de su correspondiente parámetro actual. 
2. Se ejecuta el cuerpo de acciones de la función.
3. Se devuelve el valor de la función y se retorna al punto de llamada
PROCEDIMIENTOS
Un procedimiento o subrutina es un subprograma que ejecuta un proceso específico. Ningún valor está asociado con el nombre del procedimiento; por consiguiente, no puede ocurrir en una expresión.
Un procedimiento se llama escribiendo su nombre, por ejemplo, SORT, para indicar que un procedimiento denominado SORT (ORDENAR) se va a usar. 
Cuando se invoca el procedimiento, los pasos que lo definen se ejecutan y a continuación se devuelve el control al programa que le llamó.
AMBITO DE VARIABLES
Las variables utilizadas en los programas principales y subprogramas se clasifican en dos tipos:
VARIABLE LOCAL: es aquella que está declarada y definida dentro de un subprograma, Y es distinta de las variables con el mismo nombre declaradas en cualquier parte del programa principal. El significado de una variable se confina al procedimiento en el que está declarada. Cuando otro subprograma utiliza el mismo nombre se refiere a una posición diferente en memoria. Se dice que tales variables son locales al subprograma en el que están declaradas. 
VARIABLE GLOBAL: es aquella que está declarada para el programa o algoritmo principal, del que dependen todos los subprogramas.
La parte del programa/algoritmo en que una variable se define se conoce como ámbito o alcance (scope, en inglés). 
El uso de variables locales tiene muchas ventajas. En particular, hace a los subprogramas independientes, con la comunicación entre el programa principal y los subprogramas manipulados estructuralmente a través de la lista de parámetros. Para utilizar un procedimiento sólo necesitamos conocer lo que hace y no tenemos que estar preocupados por su diseño, es decir, cómo están programados. 
Esta característica hace posible dividir grandes proyectos en piezas más pequeñas independientes. Cuando diferentes programadores están implicados, ellos pueden trabajar independientemente. 
Una variable local a un subprograma no tiene ningún significado en otros subprogramas. Si un subprograma asigna un valor a una de sus variables locales, este valor no es accesible a otros programas, es decir, no pueden utilizar este valor. A veces, también es necesario que una variable tenga el mismo nombre en diferentes subprogramas. 
Por el contrario, las variables globales tienen la ventaja de compartir información de diferentes subprogramas sin una correspondiente entrada en la lista de parámetros.
El ámbito de un identificador (variables, constantes, procedimientos) es la parte del programa donde se conoce el identificador. Si un procedimiento está definido localmente a otro procedimiento, tendrá significado sólo dentro del ámbito de ese procedimiento. A las variables les sucede lo mismo; si están definidas localmente dentro de un procedimiento, su significado o uso se confina a cualquier función o procedimiento que pertenezca a esa definición.
PASO DE PARAMETROS
Cuando un programa llama a un subprograma, la información se comunica a través de la lista de parámetros y se establece una correspondencia automática entre los parámetros formales y actuales. Los parámetros actuales son “sustituidos” o “utilizados” en lugar de los parámetros formales.
Existen diferentes métodos para la transmisión o el paso de parámetros a subprogramas. 
Los parámetros pueden ser clasificados como:
· ENTRADAS: las entradas proporcionan valores desde el programa que llama y que se utilizan dentro de un procedimiento. En los subprogramas función, las entradas son los argumentos en el sentido tradicional;
· SALIDAS: las salidas producen los resultados del subprograma; de nuevo si se utiliza el caso de una función, éste devuelve un valor calculado por dicha función, mientras que con procedimientos pueden calcularse cero, una o varias salidas; 
· ENTRADA/SALIDA: un solo parámetro se utiliza para mandar argumentos a un programa y para devolver resultados.
Los métodos más empleados para realizar el paso de parámetros son: 
· PASO POR VALOR (también conocido por parámetro valor): Los parámetros se tratan como variables locales y los valores iniciales se proporcionan copiando los valores de los correspondientesargumentos. 
Si el valor de la variable que se pasa como parámetro sufre algún cambio en su valor dentro de la función, éste cambio no afectará al valor original de la variable. Todos los parámetros son sólo de entrada.
· PASO POR REFERENCIA O VALOR(también conocido por parámetro variable): En numerosas ocasiones se requiere que ciertos parámetros sirvan como parámetros de salida, es decir, se devuelvan los resultados a la unidad o programas que llama.
Una variable pasada como parámetro real es compartida, es decir, se puede modificar directamente por el subprograma. En este método los parámetros son de entrada/salida y los parámetros se denominan parámetros variables. Los parámetros valor y parámetros variable se suelen definir en la cabecera del subprograma.
RECURSIVIDAD
Una función o procedimiento que se puede llamar a sí mismo se llama recursivo. La recursión puede ser utilizada como una alternativa a la repetición o estructura repetitiva. La escritura de un procedimiento o función recursiva es similar a sus homónimos no recursivos; sin embargo, para evitar que la recursión continúe indefinidamente es preciso incluir una condición de terminación.
UNIDAD 5 – ESTRUCTURAS ESTATICAS
Una estructura de datos es una colección de datos que pueden ser caracterizados por su organización y las operaciones que se definen en ella. 
Las estructuras de datos son muy importantes en los sistemas de computadora. Los tipos de datos más frecuentes:
Los tipos de datos simples pueden ser organizados en dif estructuras de datos: estáticas y dinámicas. 
Las estructuras de datos estáticas son aquellas en las que el tamaño ocupado en memoria se define antes de que el programa se ejecute y no puede modificarse dicho tamaño durante la ejecución del programa. Estas estructuras están implementadas en casi todos los lenguajes: array (vectores/tablasmatrices), registros, ficheros o archivos.
ARRAYS (ARREGLOS) UNIDIMENSIONALES: LOS VECTORES
Un array o arreglo (matriz o vector) es un conjunto finito y ordenado de elementos homogéneos. La propiedad “ordenado” significa que el elemento primero, segundo, tercero, ..., enésimo de un array puede ser identificado. 
Los elementos de un array son homogéneos, es decir, del mismo tipo de datos.
Un array puede estar compuesto de todos sus elementos de tipo cadena, otro puede tener todos sus elementos de tipo entero, etc. 
El tipo más simple de array es el array unidimensional o vector (matriz de una dimensión). Un vector de una dimensión denominado NOTAS que consta de n elementos
El subíndice o índice de un elemento (1, 2, ..., i, n) designa su posición en la ordenación del vector.
El número de elementos de un vector se denomina rango del vector. El rango del vector A(L:U) es U-L+1. El rango del vector B(1:n) es n.
Los vectores se almacenan en la memoria central de la computadora en un orden adyacente. Así, un vector de cincuenta números denominado NUMEROS se representa gráficamente por cincuenta posiciones de memoria sucesivas.
Cada elemento de un vector se puede procesar como si fuese una variable simple al ocupar una posición de memoria. 
NUMEROS[25] ← 72 almacena el valor entero o real 72 en la posición 25.ª del vector 
NUMEROS escribir (NUMEROS[25]) visualiza el valor almacenado en la posición 25.ª, en este caso 72.
Los subíndices de un vector pueden ser enteros, variables o expresiones enteras.
OPERACIÓNES CON VECTORES
· ASIGNACION: A[29] ← 5 asigna el valor 5 al elemento 29 del vector A Si se desea asignar valores a todos los elementos de un vector, se debe recurrir a estructuras repetitivas e incluso selectivas
· LECTURA/ESCRITURA: La lectura/escritura de datos en arrays u operaciones de entrada/salida normalmente se realizan con estructuras repetitivas, aunque puede también hacerse con estructuras selectivas
· ACCESO SECUENCIAL(RECORRIDO): Se puede acceder a los elementos de un vector para introducir datos (escribir) en él o bien para visualizar su contenido (leer).
A la operación de efectuar una acción general sobre todos los elementos de un vector se la denomina recorrido del vector. Estas operaciones se realizan utilizando estructuras repetitivas.
· ACTUALIZACION: Actualizar un vector puede constar a su vez de tres operaciones elementales:
Añadir elementos: Se denomina añadir datos a un vector la operación de añadir un nuevo elemento al final del vector. La única condición necesaria para esta operación consistirá en la comprobación de espacio de memoria suficiente para el nuevo vector
Insertar elementos: La operación de insertar un elemento consiste en introducir dicho elemento en el interior del vector. En este caso se necesita un desplazamiento previo hacia abajo para colocar el elemento nuevo en su posición relativa
Borrar elementos: se utilizara una variable auxiliar que contendrá el valor del elemento a borrar
ARRAYS DE VARIAS DIMENSIONES
Los vectores examinados hasta ahora se denominan arrays unidimensionales y en ellos cada elemento se define o referencia por un índice o subíndice. 
Estos vectores son elementos de datos escritos en una secuencia.
El array bidimensional se puede considerar como un vector de vectores. Es un conjunto de elementos, todos del mismo tipo, en el cual el orden de los componentes es significativo y en el que se necesita especificar dos subíndices para poder identificar cada elemento del array
Los elementos de un array bidimensional se referencian con dos subíndices: el primer subíndice se refiere a la fila y el segundo subíndice se refiere a la columna. Ej. M[2, 3]
ALMACENAMIENTO DE ARRAYS EN MEMORIA.
El almacenamiento en la computadora está dispuesto fundamentalmente en secuencia contigua, de modo que cada acceso a una matriz o tabla la máquina debe realizar la tarea de convertir la posición dentro del array en una posición perteneciente a una línea.
METODOS DE ORDENAMIENTO
La ordenación o clasificación es el proceso de organizar datos en algún orden o secuencia específica, tal como creciente o decreciente para datos numéricos o alfabéticamente para datos de caracteres. La ordenación de arrays se denomina también ordenación interna, ya que se almacena en la memoria interna de la computadora de gran velocidad y acceso aleatorio.
· Método de intercambio o de burbuja 
· Ordenación por inserción 
· Ordenación por selección 
· Método de Shell 
· Método de ordenación rápida (quicksort)
BUSQUEDA
La búsqueda (searching) de información está relacionada con las tablas para consultas (lookup). Estas tablas contienen una cantidad de información que se almacena en forma de listas de parejas de datos. Por ejemplo, un diccionario
Existen diferentes algoritmos de búsqueda. El algoritmo elegido depende de la forma en que se encuentren organizados los datos.
Los métodos más usuales de búsqueda son: 
· Búsqueda secuencial o lineal. 
· Búsqueda binaria. 
· Búsqueda por transformación de claves (hash). 
· Búsqueda de Recorrido