• Author / Uploaded
• Kene Reyna Rojas

Citation preview

2017 Apuntes de fundamentos de Algoritmos y Programación

Docente KARR 01/01/2017

INDICE GENERAL 1.

Sistema de procesamiento de información ............................................................ 0

2.

Concepto de algoritmo ............................................................................................. 0 2.1.

Características de los algoritmos ...................................................................... 0

2.2.

Partes de un algoritmo...................................................................................... 0

3.

Resolución de problemas con computadoras y las herramientas de programación 1 3.1.

Análisis del problema: ....................................................................................... 1

3.2.

Diseño o desarrollo del algoritmo .................................................................... 1

3.3.

Resolución del algoritmo en la computadora .................................................. 1

4.

Representación de un algoritmo ............................................................................. 2 4.1.

Diagrama de flujo .............................................................................................. 2

4.2.

Pseudocódigo .................................................................................................... 3

5.

Datos y Tipos de datos ............................................................................................. 3 5.1.

Datos numéricos................................................................................................ 3

5.1.1.

Enteros: ...................................................................................................... 3

5.1.2.

Reales: ........................................................................................................ 3

5.2.

Datos Lógicos: .................................................................................................... 3

5.3.

Datos carácter: .................................................................................................. 3

6.

Constantes y Variables: ............................................................................................ 4

7.

Operadores ............................................................................................................... 4 7.1.

Relacionales o condicionales: ........................................................................... 4

7.2.

Aritméticos : ........................................................Error! Bookmark not defined.

7.3.

Alfanuméricos: .................................................................................................. 5

7.4.

Lógicos o Booleanos: ......................................................................................... 5

7.5.

Paréntesis: ......................................................................................................... 6

8.

Expresiones ............................................................................................................... 6

9.

Regla de Prioridad .................................................................................................... 6

10.

Operación de Asignación ...................................................................................... 7

11.

Ejercicios ................................................................................................................ 7

12.

Estructura General de un Programa ..................................................................... 8

12.1. 13.

Partes de un programa .................................................................................. 9

Instrucciones y tipos de instrucciones ................................................................. 9

13.1.

Instrucción ..................................................................................................... 9

13.2.

Tipos de instrucción ....................................................................................... 9

14.

Programación Estructurada ................................................................................ 11

14.1.

Estructuras Secuencial ................................................................................. 12

14.2.

Estructuras Selectivas .................................................................................. 16

14.2.1. Selectivas simples: ................................................................................... 20 14.2.2. Selectivas Dobles: .................................................................................... 21 14.2.3. Selectivas múltiples: ................................................................................ 21 14.2.4. Ejemplos ................................................................................................... 23 14.2.5. Ejercicios ................................................................................................... 27 14.3.

Estructuras Repetitivas ................................................................................ 36

14.3.1. Estructura repetitiva mientras (While o Do while): ............................... 45 14.3.2. Estructura repetitiva para (For): ............................................................. 45 14.3.3. Estructura repetitiva repetir:................................................................... 46 14.3.4. Ejemplos ................................................................................................... 47 14.3.5. Ejercicios ................................................................................................... 55 15.

Subprogramas ..................................................................................................... 66

15.1.

Procedimientos (Subprograma): ................................................................. 66

15.2.

Funciones ..................................................................................................... 66

15.3.

Algoritmos Recursivos ................................................................................. 68

16.

Estructuras de Datos ........................................................................................... 70

16.1.

Arreglos unidimensionales .......................................................................... 71

16.1.1. Ordenación ............................................................................................... 73 16.1.2. Búsqueda .................................................................................................. 85 16.2. 17.

Arreglos bidimensionales ............................................................................ 89

Estructuras lineal ................................................................................................ 96

17.1.

Pilas .............................................................................................................. 96

17.2.

Colas ............................................................................................................. 98

18.

Estructura no lineal ............................................................................................. 99

18.1.

Arboles ......................................................................................................... 99

18.2.

Grafos ........................................................................................................... 99

1.

Sistema de procesamiento de información Los temimos procesador de datos y sistema de procesamiento (tratamiento) de la información se utilizan con frecuencia, el uso diario de datos e información son esencialmente sinónimos sin embargo existe una diferencia, datos se refiere a la representación de algún hecho, concepto o entidad real (los datos pueden tomar diferentes formas, por ejemplo palabras escritas o habladas, números y dibujos), información implica datos procesados y organizados, un sistema en general se define como conjunto de componentes conectados e interactivos, que tienen un propósito y una unidad total. Sistema de procesamiento de información es un sistema que transforma datos brutos en información organizado, significativo y útil (Aguilar, 1988)

Entrada=Datos

Procesador

Salida=Información

Figura 1: representación de un sistema de procesamiento de información 2.

Algoritmo Definición: Es el conjunto de instrucciones que especifican la secuencia de operaciones a realizar en orden para resolver un sistema específico o clase de problema. Los algoritmos son independientes tanto del lenguaje de programación en que se expresa como de la computadora que los ejecuta. El diseño de la mayoría de los algoritmos requiere creatividad y conocimientos profundos de la técnica de la programación. En esencia. Todo problema se puede describir por medio de un algoritmo (Aguilar, 1988) 2.1. Características de los algoritmos  Un algoritmo debe ser preciso e indicar el orden de realización de cada paso  Un algoritmo debe estar definido. Si se sigue un algoritmo dos veces, se debe obtener el mismo resultado cada vez  Un algoritmo debe ser finito. Si se sigue un algoritmo, se debe terminar en algún momento ósea debe tener un numero finito de pasos 2.2. Partes de un algoritmo La definición de un algoritmo debe describir tres partes: Entrada, Proceso y Salida Entrada: son los datos que van iniciar el proceso

Proceso: Es la secuencia de paso que nos permite ejecutar alguna operación Salida: Es la información que se requiere al resolver el problema 2.3. Frfr 3. Fases de la resolución de problemas Esta se puede dividir en tres fases importantes (con computadoras y las herramientas de programación) 3.1. Análisis del problema: El problema debe estar bien definido si se desea llegar a una solución satisfactoria, para poder definir con precisión el problema se requiere que las especificaciones de entrada y salida sean descritas con detalle. Una buena definición del problema junto con una descripción detallada de las especificaciones de entrada y salida son los requisitos más importantes para llegar a una solución eficaz. El Análisis del problema exige una lectura previa del problema a fin de obtener una idea general de lo que se solicita la segunda lectura servirá para responder a las preguntas ¿Qué información debe proporcionar la resolución del problema? ¿Qué datos se necesitan para resolver el problema? 3.2. Diseño o desarrollo del algoritmo La descomposición del problema original en subproblemas más simples y a continuación dividir estos subproblemas en otros más simples que pueden ser implementados para la solución en la computadora se denomina diseño descendente (Top – Down Design.). Las ventajas más importantes del diseño descendente son.  El problema se comprende más fácilmente al dividirse en partes más simples denominados módulos.  Las modificaciones en los módulos son más fáciles  La comprobación del problema se puede verificar fácilmente Tras los pasos anteriores es preciso representar el algoritmo mediante determinadas herramientas de programación diagrama de flujo, pseudocódigo o diagrama N-S 3.3. Resolución del algoritmo en la computadora Una vez que el algoritmo está diseñado y representado gráficamente mediante una herramienta de programación (diagrama de flujo, pseudocódigo o diagrama N-S) se debe pasar a la fase de resolución práctica del problema con la computadora

4. Representación de un algoritmo Para representar los algoritmos debemos utilizar métodos gráficos o numéricos, que sea independiente de un lenguaje de programación, de tal manera que nos permita visualizar el algoritmo que queramos representar, existen varios métodos, los más usados a nivel internacional son el diagrama de flujo y el pseudocódigo. 4.1. Diagrama de flujo Es un diagrama que utiliza los símbolos (cajas) estándar mostrados y que tiene los pasos del algoritmo escritos en esas cajas unidas por flechas, denominadas líneas de flujo, que indican la secuencia en que se deben ejecutar. Un diagrama de flujo (flowchart) es una de las técnicas de representación de algoritmos más antigua y a la vez más utilizada, aunque su empleo ha disminuido, estos símbolos están normalizados por ANSI y entre las cajas más importantes tenemos: (Aguilar, 1988) Símbolo

Función Terminal: representa el comienzo, inicio, final y fin de un programa. Puede representar también una parada o interrupción programada

Si

No

Entrada / Salida: cualquier tipo de introducción de datos en la memoria desde los periféricos o registro dela información procesada en un periférico Proceso: Cualquier tipo de información que pueda originar cambio de valor, formato, posición de la información almacenada en memoria, operaciones aritméticas, de transferencia, etc. Decisión: indican operaciones lógicas o de comparación entre datos, normalmente dos y en función del resultado de la misma determina cuál de los distintos caminos alternativos del programa se debe seguir normalmente tiene dos salidas respuesta sí o no, pero puede tener tres o más según los casos Indicador de Dirección o Línea de Flujo: indica el sentido de ejecución de las operaciones

4.2. Pseudocódigo Es un lenguaje especificado de algoritmos. El uso de tal lenguaje hace el paso de codificación final relativamente fácil. La ventaja de un pseudocódigo es que en su uso la planificación de un programa, el programador se puede concentrar en la lógica y en las estructuras de control y preocuparse de las reglas de un lenguaje de programación. Es también fácil modificar el pseudocódigo si se descubren errores o anomalías en la lógica del programa (Aguilar, 1988) El pseudocódigo es un lenguaje algorítmico, de alto lenguaje utilizado para escribir con mucha más abstracción instrucciones de un lenguaje de programación. 5. Datos y Tipos de datos 5.1. Datos numéricos El tipo numérico es el conjunto de los valores numéricos, estos pueden representarse de dos formas distintas. 5.1.1. Enteros: Es un subconjunto finito de los números enteros. Los enteros son números completos, no tienen componentes fraccionarios o decimales y pueden ser negativos o positivos (Aguilar, 1988) , En java se representan con int, long, short Por ejemplo Int X 5.1.2. Reales: El tipo real consiste en un subconjunto de los números reales, Los números reales siempre tienen su punto decimal y pueden ser positivos o negativos En java se representan con float, doublé 5.2. Datos Lógicos: Tipo lógico también denominado booleano, es aquel dato que solo puede tener uno o dos valores cierto o verdadero (True) y falso (False), este tipo de dato se utiliza para representar alternativas (si/no) a determinadas conclusiones. 5.3. Datos carácter: Es el conjunto finito y ordenado de caracteres que la computadora reconoce. Un dato tipo carácter contiene un solo carácter (Char) (Aguilar, 1988)

Una cadena de caracteres (String) es una sucesión de caracteres que se encuentran delimitados por una comilla (apostrofo) o dobles comillas según el tipo de lenguaje de programación. La longitud de una cadena de caracteres es el número de ellos comprendidos entre los separadores o delimitadores Por ejemplo, podemos representar los acidos nucleicos por T(Timina), A(Adenina), G(Guanina) y C(Citosina). 6. Constantes y Variables: El programa de computadora contiene ciertos valores que no deben cambiar durante la ejecución del programa tales valores se llaman constantes de igual forma existen otros valores que cambiaran durante la ejecución del programa a estos valores se les llama variables. 7. Operadores Todos los símbolos que representan enlaces entre cada uno de los argumentos que intervienen en una operación se llaman operadores y se utilizan para construir expresiones. (Rodriguez Almeida, 1991) Los operadores pueden ser: 7.1. Relacionales o condicionales: Se utilizan para formar expresiones booleanas, es decir, expresiones que al ser evaluadas producen un valor booleano: verdadero o falso. Tal como se muestra en la figura (Rodriguez Almeida, 1991)

Fuente: Libro de metodología de la programación de Rodríguez Almeida.

7.2. Aritméticos: Para tratar los números se utilizan los operadores aritméticos, que junto con las variables numéricas forman expresiones aritméticas (Rodriguez Almeida, 1991)

Fuente: Libro de metodología de la programación de Rodríguez Almeida Nota: Los operadores mod y div son de menor prioridad 7.3. Alfanuméricos: Se utiliza para unir datos alfanuméricos (Rodriguez Almeida, 1991)

Fuente: Libro de metodología de la programación de Rodríguez Almeida Concatenación, unir expresiones alfanuméricas como si fueran eslabones de una cadena. 7.4. Lógicos o Booleanos: Combinan sus operandos de acuerdo con las reglas del algebra de Boole con el fin de producir un nuevo valor que se convierta en el valor de la expresión

Fuente: Libro de metodología de la programación de Rodríguez Almeida

OR u O: Es un operador binario, afecta a dos operadores. La expresión forma es cierta cuando al menos alguno de los operandos es cierto. Es el operador lógico de disyunción. AND o Y: es un operador binario. La expresión formada es cierta cuando ambos operandos son ciertos al mismo tiempo. Es el operador lógico de Conjunción. NOT o no: es un operador unario. Afecta a la expresión cambiando su estado lógico, si era verdad lo transforma en falso o viceversa. 7.5. Paréntesis: Los paréntesis se utilizan para anidar expresiones,

Fuente: Libro de metodología de la programación de Rodríguez Almeida 7.6. ded 8. Expresiones Las expresiones son combinaciones de constantes, variables, símbolos de operación, paréntesis, y nombres de funciones especiales. Las mismas ideas son utilizadas en notación matemática tradicional Cada expresión toma un valor que se determina tomando los valores de las variables y constantes implicadas y la ejecución de las operaciones indicadas Una expresión consta de operando y operadores según el tipo de objetos que se manipulan, se clasifican las operaciones en:  Aritméticas  Relacionales  Lógicas  Carácter 9. Regla de Prioridad Según Rodríguez (Rodriguez Almeida, 1991), la prioridad a la hora de evaluar los operadores en cualquier expresión es  Paréntesis  Potencias  Productos y divisiones  Sumas y restas  Concatenación  Relacionales  Lógicos

Según Joyanes(Aguilar, 1988)Las expresiones que tienen dos o más operadores requieren usar reglas matemáticas que permitan determinar el orden de las operaciones, se denominan reglas de prioridad o precedencia y son: a) Las operaciones que están encerradas entre paréntesis se evalúan primero. Si existen diferentes paréntesis anidados (interiores unos a otros), las expresiones más internas se evalúan primero. b) Las expresiones aritméticas dentro de una expresión suelen seguir el siguiente orden de prioridad:  Operador exponencial (^)  Operadores de multiplicación y división  Operadores de suma y resta  Operadores lógicos or y and 10. Operación de Asignación La operación de asignación es el modo de darle valores a una variable. La operación de asignación se representa con el símbolo u operador (  ). LA operación de asignación se conoce como instrucción o sentencia de asignación cuando se refiere a un lenguaje de programación El formato general de una operación de asignación es Nombre de la variable  Expresión

Expresión Expresión, expresión, variable o constante Ejemplo A  10 Significa que la variable A se le ha asignado el valor entero de 10. 11. Ejercicios  Encontrar el valor de la variable valor después de la ejecución de las siguientes operaciones a. Valor  4.0*5 b. X  3.0 Y  2.0 Valor  X^Y – Y c. Valor  5 X3 Valor  valor* X  Deducir el resultado que se puede producir con las siguientes instrucciones Variables x, y = enteros X1 Y5

Escribir x, y  Deducir el valor de las expresiones siguientes X  A +B +C XA+B*C XA+B/C X  A + B mod C X (A + B) / C X  A + (B / C) X A + (B * C) Siendo A =5, B =25, C= 10  Escribir las siguientes expresiones en forma de expresiones algorítmicas i. ii. iii. iv. v. vi.

𝐌 𝐍

+𝑷 𝑵

𝑴 + (𝑷−𝑸) (𝑴+𝑵) (𝑷−𝑸) 𝒏 𝒑 𝒓 (𝒒− ) 𝒔

(𝑴+ )

(𝒔𝒆𝒏𝒐(𝒙)+𝒄𝒐𝒔𝒆𝒏𝒐(𝒙)) 𝒕𝒂𝒏(𝒙) −𝒃±√𝒃𝟐 −𝟒𝒂𝒄 𝟐𝒂

 Como se intercambian los valores de las A, B y Aux Aux A AB B Aux 12. Programa informático Es un conjunto de instrucciones u órdenes dadas a la máquina, que producirán la ejecución de una determinada tarea. En esencia un programa es un medio para conseguir un fin. El proceso de la programación es por consiguiente, un proceso de solución de problemas, y el desarrollo de un programa requiere las siguientes fases  Definición y análisis del problema  Diseño de algoritmos o Diagrama de flujo o pseudocódigo  Codificación del programa  Depuración y verificación del programa  Documentación  Mantenimiento

12.1. Estructura General de un Programa

Entrada

Programa (algoritmo de resolución)

Salida

Entrada: Son los datos que se ingresan por medio de una variable. Programa: Son todas las instrucciones que representa un algoritmo (Diagrama de Flujo de Datos o Pseudocódigo) de un problema abstracto, que es codificado en un lenguaje de programación (Powerbuilder) o interprete (Perl, Java,) que este respeta una sintaxis. Salida: Son los datos resultantes del programa 12.2. Partes de un programa en perl print "ingrese un numero: "; $num=; print $num; 13. Instrucciones y tipos de instrucciones 13.1. Instrucción Son las acciones o instrucciones que se deben escribir y posteriormente almacenar en memoria en el mismo orden en que han de ejecutarse, es decir, en secuencia 13.2. Tipos de instrucción  Instrucciones de inicio y fin Son aquellas instrucciones que inicializan y finalizan la escritura y ejecución del programa por ejemplo en java public class { public static void main(String, args[]){ } }  Instrucciones de asignación Son aquellas instrucciones que permite asignar valores a una variable Ejemplo en perl $th=23;

 Instrucciones de lectura Esta instrucción lee datos de un dispositivo de entrada ejemplo leer edad, tiempo. Ejemplos en PERL. Ejemplo 1 Print " ingrese el nombre del empleado: "; $nombre=; Ejemplo 2 print"ingrese la cantidad de horas trabajadas: "; $th=; chop($th); o también puede usarse chomp($th); Otro ejemplo de lectura en matlab: a=input ('ingrese el valor de a:'); b=input ('ingrese el valor de b:');  Instrucciones de escritura Esta instrucción escribe en un dispositivo de salida ejemplo escribir A, B, C Ejemplos En PERL : print"empleado sueldo bruto descuento sueldo neto \n"; print"==============================================\n"; print " $sb $desc $sn $nombre"; En matlab : disp('la suma de dos números es :'); disp(s);  Instrucciones de bifurcación El desarrollo lineal de un programa se interrumpe cuando se ejecuta una bifurcación. Las bifurcaciones pueden ser según el punto del programa a donde se bifurca hacia adelante o hacia atrás. o Bifurcación incondicional: se realiza siempre que el flujo del programa pase por la instrucción sin necesidad del cumplimiento de ninguna condición

Acción 1

Acción 2

Acción 3

o Bifurcación Condicional: depende del cumplimiento de una determinada condición. Si se cumple la condición, el flujo sigue ejecutando la acción F2 si no cumple se ejecuta la acción F1

¿?

Acción F1

Acción F2

Ejemplo en Perl if($num