Unid31 Estruct Dat - Algoritmos PDF

Preview

Summary

Estructuras de datos y Algoritmos....

Description

Universidad Nacional de Salta Facultad de Ingeniería

Introducción a Programación Estructurada usando SLE (pSeudo Lenguaje en Español) Estructuras de Datos y Control simples + Algoritmos = Resolución de Problemas. APUNTES DE CÁTEDRA 3.1 (versión 1ºcuat.2015)

INFORMÁTICA INFORMÁTICA 2°cuat.1°año de las Ing’s del Ciclo Común de Articulación

1° año Ingenierías de Univ.Nac.del Noroeste ACTIVIDAD DE CLASE

TEÓRICO / PRÁCTICO

Prof.Adj. (a cargo): Lic. José Ignacio Tuero JTP’s: Lic. Néstor Javier Hurtado Lic. Leopoldo Eugenio Lugones

Colaboraron versiones originales: Lic. Pablo Wolmy Lic. Patricia Aballay Sr. Fabián Montelongo

Univ.Nac.de Salta – Fac. de Ingeniería – INFORMÁTICA (C.C.A.)

Apuntes de Cátedra

Tabla de Contenidos TABLA DE CONTENIDOS............................................................................................................................................... 2 1 – ESTRUCTURAS DE DATOS...............................................................................................................................................3 1.1 - INTRODUCCIÓN: QUÉ Y POR QUÉ SON IMPORTANTES LAS ESTRUCTURAS DE DATOS.....................................................................3 1.1.1 - Cómo trabajaba una computadora:.................................................................................................................3 1.1.2 - Resolución de problemas usando una PC:........................................................................................................3 1.1.3 - Los datos ingresan, se procesan y salen:..........................................................................................................3 1.1.4 - Uniendo estos conceptos:................................................................................................................................3 1.1.5 - ESTRUCTURAS DE DATOS - 1ª DEFINICIÓN:......................................................................................................3 1.2 - ESTRUCTURAS DE DATOS: CARACTERÍSTICAS PRINCIPALES Y ANALOGÍAS...................................................................................4 1.3 - VARIABLES Y CONSTANTES (IDENTIFICADORES RESPECTIVOS).................................................................................................4 1.4 - INTRODUCCIÓN AL USO DE OPERADORES:....................................................................................................................... 5 1.4.1 - Precedencia entre Operadores aritméticos......................................................................................................5 1.4.2 - Operadores de comparación y lógicos.............................................................................................................6 2 – ALGORITMOS.................................................................................................................................................................7 2.1 - ETAPAS EN LA SOLUCIÓN DE PROBLEMAS Y PROGRAMACIÓN.................................................................................................7 2.2 - CONCEPTO DE ALGORITMO......................................................................................................................................... 7 A. - Secuencialidad.......................................................................................................................................................7 B. - Ausencia de ambigüedad......................................................................................................................................7 C. - Generalidad...........................................................................................................................................................7 D. - Limitación.............................................................................................................................................................8 2.2.1 - Dominio y Generalidad perseguida..................................................................................................................8 2.2.2 - Errores en la construcción de un algoritmo......................................................................................................8 2.2.3 - Criterios de elección de algoritmos:.................................................................................................................8 2.3 - PLANTEANDO UN ALGORITMO BÁSICO EN LENGUAJE NATURAL.............................................................................................. 8 2.3.1 - Ejemplos de algoritmos de la vida cotidiana...................................................................................................9 2.4 - PSEUDOCÓDIGO: ENTRE EL LENGUAJE NATURAL Y EL LENGUAJE DE PROGRAMACIÓN:.................................................................10 2.5 – ESTRUCTURAS DE CONTROL:..................................................................................................................................... 11 2.5.1 - Teorema de la Programación Estructurada....................................................................................................11 2.5.1 - Secuencia:.......................................................................................................................................................12 2.5.2 – Selección o Condición:...................................................................................................................................12

Unidad 3: Estructura de datos

2/14

Univ.Nac.de Salta – Fac. de Ingeniería – INFORMÁTICA (C.C.A.)

Apuntes de Cátedra

1 – Estructuras de Datos 1.1 - Introducción: qué y por qué son importantes las Estructuras de Datos 1.1.1 - Cómo trabajaba una computadora: Al estudiar los elementos básicos del hardware de una computadora veíamos sus funciones principales:

2 ingresar información

Memoria RAM

GABINETE

Disco Rígido

El procesador central (CPU) realizaba todas sus operaciones aritméticas y lógicas (a través de su ALU) en la Memoria RAM. Comparábamos ésta con el “escritorio de trabajo” de la CPU. Todos los cálculos, el ingreso de valores / variables realizados por el usuario, se almacena en RAM (dispositivo de almacenamiento transitorio de la información). 1.1.2 - Resolución de problemas usando una PC: Para que una computadora pueda ejecutar y resolver problemas es necesario que se desarrollen programas. Éstos no son otra cosa que un conjunto de instrucciones secuenciales, interpretables por la computadora, que un programador codifica para que la misma sepa cómo resolver un problema. Para el programador, solucionar un problema implica, desarrollar algoritmos (secuencia de pasos y operaciones para resolver el problema 1) traduciéndolo a instrucciones interpretables por la PC. 1.1.3 - Los datos ingresan, se procesan y salen: Generalmente un problema tiene un conjunto de datos de entrada que, luego de su procesamiento (aplicar un algoritmo), se transforma en un conjunto de datos de salida.

1

ar e n 1carg R AM

PERIFÉRICOS

ia del 1 Buscar una cop co programa en el Dis Rígido

"lugar" de trabajo de la CPU

3 guarar la inform. procesada

CPU "cerebro" de la PC

2 procesar

1 ma Ejecutar un progra

"grabar" permanentemente la información

1.1.4 - Uniendo estos conceptos: La información debe ser ingresada (a través de los dispositivos de Entrada/Salida periféricos a la PC) y almacenada en memoria RAM, para que allí pueda ser manipulada por la CPU. De manera análoga, la información transformada, luego de la ejecución de las instrucciones programadas e interpretadas por el procesador, debe almacenarse en espacios de la memoria RAM destinados a tal fin y mostrados por dispositivos de Salida (o almacenada de manera permanente en medios magnéticos destinados con ese propósito). 1.1.5 - ESTRUCTURAS DE DATOS - 1ª DEFINICIÓN: Las Estructuras de Datos, no son otra cosa que reservas de espacio digital de Memoria RAM para almacenar datos o información que va a ser procesada (o que ya fue procesada). Esta reserva de espacio puede ser permanente (en el disco rígido o dispositivos símiles) o transitoria (en la memoria RAM).

Más adelante se define con mayor precisión ALGORITMOS

Unidad 3: Estructuras de Datos y Algoritmos

3/14

Univ.Nac.de Salta – Fac. de Ingeniería – INFORMÁTICA (C.C.A.)

Apuntes de Cátedra

1.2 - Estructuras de Datos: características principales y analogías Cuando se “reserva” un espacio de almacenamiento para guardar datos de entrada (o salida), equivale a: “preparar cajas para el archivo de documentación”. Cuando un administrativo de una oficina realiza esta actividad tiene presente las siguientes características: 

Rotula o identifica la caja dispuesta para el archivo de documentación, generalmente con un rótulo (o nombre) genérico que hace alusión al significado (o sentido) que tiene esa documentación (información).



La caja preparada para almacenar información documental es dispuesta de acuerdo al tipo de documentación que se almacenará (respetando las dimensiones de la papelería, será lo suficientemente robusta para soportar el peso de la cantidad de documentación que se almacenará, por ejemplo).



La caja archivo de documentación, preparada con las previsiones descriptas, puede recibir cualquier documentación (del tipo y propósito previstos), por lo cual es un “contenedor” variable dispuesto a tal fin.

Rótulo de la “variable“ (espacio RAM reservado)

Tipo de información o dato que se puede almacenar

De acuerdo a lo descrito, análogamente toda reserva de espacio de almacenamiento de información a ser procesada en Memoria RAM, deberá: 

Estar rotulada, tener un nombre o identificador 2; (mejor serán rótulos o nombres más descriptivos, haciendo alusión al sentido o finalidad que tendrá esa información,).

 

Especificarse el tipo de datos3 (o información) que se puede almacenar en ese espacio reservado. Este almacenamiento reservado, con un rótulo y tipo de datos que puede almacenar, actuará como variable, en el sentido que podrá almacenar cualquier dato que cumpla las características del tipo definido.

1.3 - Variables y Constantes (identificadores respectivos) Como se introdujo, una variable se puede usar para almacenar diferentes valores que correspondan a un determinado “tipo de dato”. Por otra parte, como su nombre indica, una constante es un valor que nunca cambia. Los “identificadores” (rótulos) por medio de los cuales distinguimos a los números en la mayoría de los lenguajes de programación son los mismos símbolos que los representan. 1; 3.1416 (son dos ejemplos de invocación, por medio de sus “identificadores” de dos números: uno entero, el 1 y otro real, el 3.1416).

Pi

3,141 6

“Tipo de Dato” definido para el ejemplo: REAL. Al cargar una “Variable” con un valor fijo  la convertimos en una “Constante”.

Referencia: Puede comparar una constante con un DVD de música pre-grabado (de solo escritura) comprado en un comercio oficial; la música almacenada en el disco compacto nunca podrá ser cambiada por usted.

En un programa, se puede ver muchos ejemplos en los que hay constantes y variables en la misma instrucción. Considere, por ejemplo, la siguiente: int indice;

2 3

indice: numerico; //declaración de variable en C++ y SLE respectiv.

Identificadores: más adelante se profundiza sobre este tópico. Tipos de Datos: también posteriormente se profundiza en la descripción de los tipos de datos clásicos y elementales que utilizaremos, incluso los que soporta el lenguaje de programación C que utilizaremos.

Unidad 3: Estructuras de Datos y Algoritmos

4/14

Univ.Nac.de Salta – Fac. de Ingeniería – INFORMÁTICA (C.C.A.)

Apuntes de Cátedra

in d

ic e rece (rótu ptácu lo/no mb dato lo que re s de cibirá re del “tipo” : ENT cualquier ERO ).

indice = 1;

“Tipo de Dato” definido para el ejemplo: ENTEROS

//asignación de un valor constante a la variable declarada

en donde el símbolo: 1 es una constante ya que siempre tiene el mismo valor (1), mientras que el “símbolo”: indice es la variable que tenía este rótulo y se le asignó la constante 1, convirtiéndola en una constante (hasta que el programador no decida cambiarle su valor).

Expresiones

En otras palabras, indice contiene el valor 1 después de ejecutar la instrucción. Luego, si hay otra instrucción:

es una expresión que primero suma 2 y 3, y después multiplica el resultado de la suma por 10. (El resultado final de la expresión es, 50; pero en esta expresión no se almacena en ninguna variable).

indice = 10;

Una expresión es una combinación de constantes, variables y operadores para realizar cálculos. Por ejemplo, lo siguiente:

(2 + 3) * 10

En forma similar, la expresión

después de que se ejecute, indice quedará con el valor 10. Esto sería debido a que indice puede contener diferentes valores, por eso se le llama variable.

índice = 10 * (4 + 5); produce 90 como resultado y lo almacena en la variable indice.

1.4 - Introducción al uso de Operadores: Una expresión puede contener símbolos como: +, -, * y /. En lenguaje de programación de alto nivel, estos símbolos se denominan operadores aritméticos. Se interpretan de idéntica manera que en lenguaje natural. Estos operadores, necesitan operandos (variables y/o constantes) que se consignan a izquierda y derecha de los mismos. El resultado de la operación se asigna a la variable cuyo rótulo figure a la izquierda del símbolo = Se presenta una lista de todos los principales (y más elementales) operadores aritméticos y su significado que utiliza el lenguaje de programación SLE, C y C++ . Símbolo u Operador

Significado

+ * / %

Suma

Resulta “natural” estar familiarizado con los operadores aritméticos tal como los interpreta el computador desde el lenguaje de programación de alto nivel. Quizás la excepción sea el operador: resto, residuo o módulo (%) de una división entera.

Resta Multiplicación División Residuo, Resto (o módulo)

Este operador se usa para obtener el residuo/resto de la división del primer operando /dividio el segundo. Ej.: 6 % 4 produce un valor de 2 debido a que 4 cabe una vez en 6 con un resto o residuo de 2.

1.4.1 - Precedencia entre Operadores aritméticos Entre los operadores aritméticos, los operadores de multiplicación, división y residuo, tienen una precedencia más alta que los operadores de suma y resta (igual que lo aprendido en AMI y ALGA). Por ejemplo, la expresión: 2 + 3 * 10 da como resultado 32 = 2+(3*10); no 50 = (2+3)*10; debido a que el operador de multiplicación tiene mayor precedencia que el de suma. Primero se calcula 3 * 10 y después se suma 2 al resultado de la multiplicación.

Unidad 3: Estructuras de Datos y Algoritmos

5/14

Univ.Nac.de Salta – Fac. de Ingeniería – INFORMÁTICA (C.C.A.)

Apuntes de Cátedra

1.4.2 - Operadores de comparación y lógicos Los operadores de condición o comparación se utilizan para comprobar las condiciones de las sentencias o instrucciones de control de flujo o estructuras de control4. Los operadores son: Cuando se evalúa una condición el resultado que se obtiene es 0 si no se cumple y un número distinto de 0 si se cumple, normalmente devuelven un 1.

Símbolo

== != > < >= 5) y (6==6). Los operadores lógicos son: AND (&&), OR (||), NOT(!) y devuelven estas expresiones de verdad resultante: 

&& (AND, en castellano Y): devuelve un 1 si son verdaderas ambas condiciones. (10==10) && (5>2 ) devuelve verdadero



|| (OR, en castellano O): devuelve un 1 si se cumple una de las dos condiciones. (10==10) || (5>2 ) devuelve verdadero (10==10) || (5>8 ) devuelve verdadero (10!=10) || (5 !, ~, ++, -*, /, % +, = ==, != & ^ | && || ? =, +=, -=, *=, /= ,

Estructuras de Control: se introducen más adelante.

Unidad 3: Estructuras de Datos y Algoritmos

6/14

Univ.Nac.de Salta – Fac. de Ingeniería – INFORMÁTICA (C.C.A.)

Apuntes de Cátedra

2 – Algoritmos 2.1 - Etapas en la solución de problemas y programación Se puede describir la programación como aquella tarea o actividad que permite transformar un problema dado, mediante algún método apropiado, de manera que la solución del mismo quede expresada como un conjunto de instrucciones (comandos o sentencias) que puedan ser ejecutadas por una computadora. El proceso de programación es la tarea de programar, este proceso involucra una secuencia de etapas a cumplir en el tiempo. Estas etapas pueden describirse en términos de los siguientes pasos: 1. 2. 3. 4.

Descripción del problema. Elección de un algoritmo para resolver el problema. Diseño del algoritmo. Codificación en algún lenguaje que la computadora reconozca (por ejemplo: C, C++, Pascal, Fortran, Visual Basic, Java, y muchos otros). 5. Ingreso del código y ejecución del programa en una computadora. 6. Corrección, pruebas y optimización del programa. 7. Documentación y mantenimiento del programa.

2.2 - Concepto de Algoritmo Reseña: La palabra algoritmo se usa en homenaje al matemático Uzbeco Al-Kuaritzmi quien en el año 880 escribió un libro, en el que por primera vez se expresaban métodos precisos para efectuar las cuatro operaciones básicas, que hoy en día se siguen utilizando.

A nivel de programación, lo primordial en la solución de un problema con una computadora, es el diseño del algoritmo y de la estructuración fundamental de datos involucrados en dicho procesamiento. Basados en el entendimiento de la estructuración de la información a ser procesada, iremos aprehendiendo (internalizando) los principios de la programación (la algoritmia) de una manera amigable e imperceptible.

Definición: Un algoritmo es un conjunto finito de instrucciones que especifican una secuencia de operaciones a realizar en orden para resolver un problema específico. En otras palabras, un algoritmo es un método para la solución del problema. Podemos distinguir cuatro propiedades de un algoritmo que son fundamentales: A. Secuencialidad. B. Ausencia de ambigüedad. C. Generalidad. D. Limitación. A. - Secuencialidad Sin lugar a dudas se debe especificar la secuencia en la que se deben llevar a cabo los pasos del algoritmo. Por cada “paso”, un algoritmo debe tener una instrucción única y cada instrucción debe tener otra sucesora única. Las instrucciones son llevadas a cabo e interpretadas de arriba hacia abajo. Las entradas son las partidas de datos presentadas al algoritmo. Un algoritmo puede tener o no entradas. Si las hay, deben ser del tipo para el cual fue diseñado el algoritmo. Las salidas son datos procesados como resultado de la ejecución de un programa basado en el algoritmo. Un algoritmo debe producir al menos una salida. B. - Ausencia de ambigüedad Un algoritmo debe ser definido de manera: clara, precisa y sin ambigüedad. La representación de cada paso de un algoritmo debe dar lugar a una sola interpretación posible. Esta condición significa que cada vez que se presente para su ejecución un algoritmo con los mismos datos de entrada, se obtendrán los mismos resultados. Unidad 3: Estructuras de Datos y Algoritmos

Las instrucciones de un algoritmo deben ordenar a la computadora que solo lleve a cabo tareas que sea capaz de hacer. Una computadora no puede efectuar una instrucción si tiene información insuficiente o si el comando no está definido. C. - Generalidad Un algoritmo se debe ...