Introducción
Este apartado es el estudio de los algoritmos y la programación, temas centrales de las ciencias de la computación y de cualquier carrera de informática. Desde el nacimiento de la informática, el hombre ha buscado y desarrollado métodos y herramientas para facilitar, agilizar y mejorar el trabajo de analistas y programadores, ofreciendo nuevas vías o caminos para la búsqueda de soluciones a determinados problemas mediante el diseño de algoritmos.
Aquí se presenta y se analiza las estructuras de datos y los algoritmos fundamentales desarrollados en las últimas décadas, especialmente los relacionados técnicas de diseño de algoritmos, a las estructuras de control: secuenciales, alternativas o condicional y repetitivas, a funciones y procedimientos, a vectores y matrices, a búsqueda, realizando en cada caso una evaluación del desempeño de estos algoritmos y estructuras de datos desde la perspectiva de su aplicación a problemas representativos.
Los fundamentos de programación son la base para empezar a programar, antes incluso de elegir un lenguaje. Cualquier persona que quiera aprender a programar y tenga un nivel de matemáticas igual o superior al de bachillerato.
La principal razón para que las personas aprendan lenguajes de programación es utilizar un computador como una herramienta para la resolución de problemas. Tres fases pueden ser identificadas en el proceso de resolución:
- Fase de Identificación (qué nos plantean)
- Fase de resolución del problema
- Fase de implementación (realización) en un lenguaje de programación
Diseño del algoritmo
Un algoritmo puede ser definido como la secuencia ordenada de pasos, sin ambigüedades, que conducen a la resolución de un problema dado y expresado en lenguaje natural, por ejemplo el castellano, Todo algoritmo debe ser:
- Preciso: Indicando el orden de realización de cada uno de los pasos.
- Definido: Si se sigue el algoritmo varias veces proporcionándole
(Consistente ) los mismos datos, se deben obtener siempre los mismos resultados.
- Finito: Al seguir el algoritmo, este debe terminar en algún momento, es decir tener un número finito de pasos.
Este método de diseño de algoritmos en etapas, yendo de los conceptos generales a los de detalle, se conoce como método descendente (top-down).
Como ejemplo supongamos que desea desarrollar un algoritmo que calcule la superficie de un rectángulo proporcionándole su base y altura. Lo primero que debemos hacer es plantearnos las siguientes preguntas:
Especificaciones de entrada
¿Qué datos son de entrada?
¿Cuántos datos se introducirán?
¿Cuántos son datos de entrada válidos?
Especificaciones de salida
¿Cuáles son los datos de salida?
¿Cuántos datos de salida se producirán?
¿Qué formato y precisión tendrán los resultados?
El algoritmo que podemos utilizar es el siguiente:
Paso 1. Entrada desde el teclado, de los datos de base y altura.
Paso 2. Cálculo de la superficie, multiplicando la base por la altura.
Paso 3. Salida por pantalla de base, altura y superficie calculada.
Construcción de programas
La programación es la disciplina de la computación que trata el desarrollo de programas. Es una tarea compleja, que requiere de métodos rigurosos, para alcanzar el objetivo de todo programa que es obtener resultados válidos y confiables.
En general, la actividad de programación se realiza por etapas, contemplando al menos las siguientes:
ü Análisis del problema
ü Diseño de la solución
ü Desarrollo del programa
ü Prueba del programa
Noción de algoritmo
Un algoritmo es conjunto ordenado y finito de operaciones que permite hallar la solución de un problema, es decir, son una serie de pasos que permiten obtener la solución a un problema.
El lenguaje algorítmico es aquel que implementa una solución teórica a un problema indicando las operaciones a realizar y el orden en el que se deben efectuarse.
Características que deben de cumplir los algoritmos:
· Un algoritmo debe resolver el problema para el que fue formulado. Lógicamente no sirve un algoritmo que no resuelve ese problema. En el caso de los programadores, a veces crean algoritmos que resuelven problemas diferentes al planteado.
· Los algoritmos son independientes del ordenador. Los algoritmos se escriben para poder ser utilizados en cualquier máquina.
· Los algoritmos deben de ser precisos. Los resultados de los cálculos deben de ser exactos, de manera rigurosa. No es válido un algoritmo que sólo aproxime la solución.
· Los algoritmos deben de ser finitos. Deben de finalizar en algún momento. No es un algoritmo válido aquel que produce situaciones en las que el algoritmo no termina.
· Validez. Un algoritmo es válido si carece de errores. Un algoritmo puede resolver el problema para el que se planteó y sin embargo no ser válido debido a que posee errores
· Eficiencia. Un algoritmo es eficiente si obtiene la solución al problema en poco tiempo. No lo es si es lento en obtener el resultado.
· Óptimo. Un algoritmo es óptimo si es el más eficiente posible y no contiene errores. La búsqueda de este algoritmo es el objetivo prioritario del programador.
No siempre podemos garantizar que el algoritmo hallado es el óptimo, a veces sí.
Elementos que conforman un algoritmo
· Entrada. Los datos iníciales que posee el algoritmo antes de ejecutarse.
· Proceso. Acciones que lleva a cabo el algoritmo.
· Salida. Datos que obtiene finalmente el algoritmo.
Fases en la creación de algoritmos
Hay tres fases en la elaboración de un algoritmo:
· Análisis. En esta se determina cuál es exactamente el problema a resolver. Qué datos forman la entrada del algoritmo y cuáles deberán obtenerse como salida.
· Diseño. Elaboración del algoritmo.
· Prueba. Comprobación del resultado. Se observa si el algoritmo obtiene la salida esperada para todas las entradas.
Ejemplo: Consideremos el algoritmo que responde a la pregunta ¿Qué hacer para ver una película?
Este ejemplo puede ser descrito en forma de algoritmo:
ü ir al cine
ü comprar una entrada (billete o ticket)
ü ver la película
ü regresar a casa
El algoritmo consta de cuatro acciones básicas, cada una de las cuales debe ser ejecutada antes de realizar la siguiente.
Como hemos dicho anteriormente, el algoritmo general se descompondrá en pasos más simples mediante refinamiento sucesivo. Cada acción puede descomponerse a su vez en otras acciones simples. Así, por ejemplo, un primer refinamiento del algoritmo (módulo o sub-algoritmo) ir al cine se puede describir de la forma siguiente:
1. Inicio
2. Ver la cartelera de cines en el periódico
3. Si no proyectan «Comiquitas» entonces
3.1. Decidir otra actividad
3.2. Finalizar
Si no
3.3. Ir al cine
fin_si
4. Si hay cola entonces
4.1. Ponerse en ella
4.2. Mientras haya personas delante hacer
4.2.1. Avanzar en la cola
fin_mientras
fin_si
5. Si hay localidades entonces
5.1. Comprar una entrada
5.2. Pasar a la sala
5.3. Localizar la(s) butaca(s)
5.4. Mientras proyectan la película hacer
5.4.1. Ver la película
fin_mientras
5.5. Abandonar el cine
Si no
5.6. Refunfuñar
fin_si
6. Volver a casa
7. Fin
Un programa es un conjunto unitario de instrucciones que permite a un computador realizar funciones diversas, como el tratamiento de textos, el diseño de gráficos, la resolución de problemas matemáticos, el manejo de bancos de datos, etc.
Existen diferentes métodos que permiten representar los algoritmos en sus correspondientes codificaciones, en una forma que todas las personas puedan entenderlo. Veamos dos de ellos:
El pseudocódigo
En lo fundamental, el Pseudocódigo es la forma narrativa de los pasos que debe seguir un algoritmo para dar solución a un problema determinado. En el pseudocódigo se describen los algoritmos utilizando una mezcla de lenguaje común, con instrucciones de programación, palabras claves, entre otros. El objetivo es que el programador se centre en la solución lógica del algoritmo y no en la implementación en un lenguaje de programación concreto (con las posibles complicaciones en las reglas sintácticas), o en otras palabras, sólo ayudan a repasar un programa antes de escribirlo en un lenguaje de programación formal.
Ejemplo: Realizar el pseudocódigo de un programa que permita calcular el área de un rectángulo.
Algoritmo área
Var: BASE, ALTURA, AREA; Tipo: enteros
Inicio
Escribir “introduzca la base y la altura”
Leer BASE, ALTURA
AREA = BASE * ALTURA
Escribir “El área del rectángulo es “
Fin
Diagramas de flujo
Es el esquema más viejo de la informática. Se trata de una notación que pretende facilitar la escritura o la comprensión de algoritmos. Gracias a ella se esquematiza el flujo del algoritmo. Fue muy útil al principio y todavía se usa como apoyo para explicar ciertos algoritmos. Si los algoritmos son complejos, este tipo de esquemas no son adecuados.
No obstante cuando el problema se complica, resulta muy complejo de realizar y de entender. De ahí que actualmente, sólo se use con fines educativos y no en la práctica.
Pero sigue siendo interesante en el aprendizaje de la creación de algoritmos.
Los diagramas utilizan símbolos especiales que ya están normalizados por organismos de estandarización como ANSI e ISO. Los principales símbolos usados en los diagramas de flujo se muestran a continuación:
| Inicio |
| Pare |
b) Flecha de dirección del flujo
| Operación |
Este símbolo de proceso y nos indica la asignación de un valor en la memoria y/o la ejecución de una operación aritmética.
e) Lectura de datos (símbolo de la lectora de tarjetas perforadas)
f) Impresión (símbolo de la impresora de papel)
h) Caja de decisiones (rombo)
SI
NO
Tendrán 2 salidas posibles, indicadas una por SI y la otra por NO.
i) Conectores de salida y conectadores de entrada al flujo
| Conector de Salida Conector de entrada entrada |
Ejemplo: Diagrama de flujo que escribe el mayor de dos números leídos
Escritura en pseudocódigo
Las instrucciones que resuelven el algoritmo en pseudocódigo deben de estar encabezadas por la palabra inicio (en inglés begin) y cerradas por la palabra fin (en inglés end). Entre medias de estas palabras se sitúan el resto de instrucciones.
Opcionalmente se puede poner delante del inicio la palabra programa seguida del nombre que queramos dar al algoritmo.
En definitiva la estructura de un algoritmo en pseudocódigo es:
Programa nombreDelPrograma
Inicio
Instrucciones
....
Fin
Variables
Una variable es un espacio de la memoria del ordenador a la que asignamos un contenido que puede ser un valor numérico (sólo números, con su valor de cálculo) o alfanumérico (sólo texto o texto con números). Dos o más variables pueden tener el mismo contenido, pero no el mismo nombre. El contenido de una variable puede ser numérico o alfanumérico.
Ejemplos:
A = 5 + 2
B = 32
Suma = A+ B
Variables Booleanas
Con el fin de facilitar la escritura y razonamientos de programas se admite el uso de variables bipolares o que sólo admiten dos valores: verdadero (true) o falso (false).
La asignación de contenido se hace tomando la variable igual a uno de los dos valores.
Ejemplos:
Debilidad = Verdadero
Mejorado = Falso
El tipo de datos de la variable puede ser especificado de muchas formas, pero tiene que ser un tipo compatible con los que utilizan los lenguajes informáticos. Se suelen utilizar los siguientes tipos:
· Entero. Permite almacenar valores enteros (sin decimales).
· Real. Permite almacenar valores decimales.
· Carácter. Almacenan un carácter alfanumérico.
· Lógico (o booleano). Sólo permiten almacenar los valores verdadero o falso.
· Texto. A veces indicando su tamaño (texto(20) indicaría un texto de hasta 20 caracteres) permite almacenar texto. Normalmente en cualquier lenguaje de programación se considera un tipo compuesto.
Constantes
Hay un tipo especial de variable llamada constante. Se utiliza para valores que no van a variar en ningún momento. Si el algoritmo utiliza valores constantes, éstos se declaran mediante una sección (que se coloca delante de la sección var) llamada const (de constante).
Operadores Lógicos
= Igual que A = B
> Mayor que A > B
< Menor que A < B
>= Mayor o igual que A >= B
<= Menor o igual que A <= B
<> Distinto que A <> B
Prioridad entre operadores
La prioridad entre operadores puede variar en función del lenguaje informático que utilicemos. Consideraremos estas prioridades: Operadores matemáticos > Operadores de comparación > Operadores de negación, conjunción o disyunción.
Declaración de variables
Es aconsejable al escribir pseudocódigo indicar las variables que se van a utilizar (e incluso con un comentario indicar para qué se van a usar). En el caso de los otros esquemas (diagramas de flujo y tablas de decisión) no se utilizan (lo que fomenta malos hábitos).
Esto se hace mediante la sección del pseudocódigo llamada var, en esta sección se colocan las variables que se van a utilizar. Esta sección se coloca antes del inicio del algoritmo. Y se utiliza de esta forma:
Programa nombreDePrograma
var
identificador1: tipoDeDatos
identificador2: tipoDeDatos
....
Inicio
Instrucciones
Fin
El tipo de datos de la variable puede ser especificado de muchas formas, pero tiene que ser un tipo compatible con los que utilizan los lenguajes informáticos. Se suelen utilizar los siguientes tipos:
· Entero. Permite almacenar valores enteros (sin decimales).
· Real. Permite almacenar valores decimales.
· Carácter. Almacenan un carácter alfanumérico.
· Lógico (o booleano). Sólo permiten almacenar los valores verdadero o falso.
· Texto. A veces indicando su tamaño (texto (20) indicaría un texto de hasta 20 caracteres) permite almacenar texto. Normalmente en cualquier lenguaje de programación se considera un tipo compuesto.
También se pueden utilizar datos más complejos, pero su utilización queda fuera de este tema.
Estructuras de Control
Las estructuras de control son las acciones que tienen por objeto marcar el orden de realización de los distintos pasos de un algoritmo o programa.
Cualquier programa puede ser realizado con una combinación de las siguientes estructuras de sentencias que definimos a continuación:
- Estructuras Secuencial
- Estructuras Selectiva (Alternativas o condicional (sentencias if, then))
- Estructuras Repetitiva
Estructura de control secuencial
En esta estructura cada acción se ejecuta en el orden preestablecido por como son enumeradas a lo largo del programa. Se ejecutan de forma secuencial (una detrás de otra) y no puede verse alterado el orden de ejecución. Es decir una acción sigue a otra en secuencia.
Gráficamente:
Estructuras de control selectivas
En ciertos programas la evolución natural del mismo durante su ejecución, puede necesitar unas variaciones de acuerdo con el cumplimiento o no de alguna-as condiciones. Mediante las estructuras selectivas podemos tomar decisiones, en las cuales se evalúa una condición y en función del resultado se ejecutará o no una acción o acciones.
Las distintas estructuras de las que disponemos son:
· Selección Alternativa Simple
La estructura selección alternativa simple si-entonces ejecuta una determinada acción cuando se cumple una determinada condición. La selección sí-entonces evalúa la condición y -si la condición es verdadera, entonces ejecuta la acción (o acciones) y si la condición es falsa, entonces no hacer nada y el programa continua con la siguiente instrucción.
La representación gráfica de la estructura condicional simple se muestra en la siguiente figura:
Si (condición) entonces < acción1 >
La alternativa simple se crea con la instrucción si (en inglés if). Esta instrucción evalúa una determinada expresión lógica y dependiendo de si esa expresión es verdadera o no se ejecutan las instrucciones siguientes.
Si expresión_lógica entonces
Instrucciones
fin si
Esto es equivalente al siguiente diagrama de flujo:
Las instrucciones sólo se ejecutarán si la expresión evaluada es verdadera.
· Selección Alternativa doble
Se emplea cuando queremos matizar qué acción (a partir de ahora en el lugar donde se cite acción se sobreentiende que también puede ser acciones) se realizará cuando sí se cumple la condición y cual se hará cuando no se cumpla. Se trata de una variante de la alternativa en la que se ejecutan unas instrucciones si la expresión evaluada es verdadera y otras si es falsa. Su pseudocódigo es el siguiente:
si (condición) entonces
accion1;
sino accion2;
fin_si
Sólo se ejecuta unas instrucciones dependiendo de si la expresión es verdadera. El diagrama de flujo equivalente es:
Hay que tener en cuenta que se puede meter una instrucción si dentro de otro sí. A eso se le llama alternativas anidadas.
Ejemplo:
si a≥5 entonces
escribe(“apto”)
si a≥5 y a<7 entonces
escribe(“nota:aprobado”)
fin_si
si a≥7 y a<9 entonces
escribe(“notable”)
si_no
escribe(“sobresaliente”)
fin_si
si_no
escribe(“suspenso”)
· Selección Alternativa Multiples
A veces es necesario que existan más de dos elecciones posibles Este problema se podría resolver por estructuras selectivas simples o completas que estuvieran anidadas o en cascada; sin embargo por este método si el número de alternativas es grande puede plantear serios problemas de escritura del algoritmo y naturalmente de legibilidad.
La estructura de decisión múltiple evaluará una expresión que podrá tomar n valores distintos (siempre un valor enumerado). Según que elija uno de estos valores en la condición, se realizará una de las n acciones.
La representación gráfica de la estructura de decisión múltiple es:
En pseudocódigo:
según_sea expresión hacer
valor1:
instrucciones del valor1
valor2:
instrucciones del valor2
...
si-no
instrucciones del si_no
fin_según
En muchas ocasiones se requieren condiciones que poseen más de una alternativa. En ese caso existe una instrucción evalúa una expresión y según los diferentes valores que tome se ejecutan unas u otras instrucciones.
Ejemplo
programa pruebaSelMultiple
var
x: entero
inicio
escribe(“Escribe un número del 1 al 4 y te diré si es par o impar”)
lee(x)
según_sea x hacer
1:
escribe(“impar”)
2:
escribe(“par”)
3:
escribe(“impar”)
4:
escribe(“par”)
si_no
escribe(“error eso no es un número de 1 a 4”)
fin_según
fin
Estructuras de control repetitivas
Algunas veces nos podremos encontrar ciertas tareas dentro de un programa que deben repetirse un número determinado o indeterminado de veces. Este es un tipo muy importante de estructura, ya que, por un lado nos permite ahorrar muchas líneas de programa y en otros casos no sería posible resolverlo.
Las estructuras que repiten una secuencia de instrucciones un número determinado de veces se denominan bucles y se denomina iteración al hecho de repetir la ejecución de una secuencia de acciones.
Por ejemplo: supongamos que se desea sumar una lista de 25 números escritos desde teclado -por ejemplo, calificaciones de los alumnos de una clase. Hasta ahora lo que haríamos es leer los números en una variable y añadir sus valores a una variable SUMA que contenga las sucesivas sumas parciales. La variable SUMA se hace igual a cero ya continuación se incrementa en el valor del número cada vez que uno de ellos se lea. En
pseudocódigo:
Inicio
entero numero,suma;
suma=0;
Leer (numero);
suma=suma+numero;
Leer (numero);
suma=suma+numero;
....
....
y así sucesivamente para cada número de la lista (los 25 alumnos!!!) . En otras palabras, el algoritmo repite muchas veces las acciones.
Cuando se utiliza un bucle para sumar una lista de números, se necesita saber cuántos números se han de sumar. Para ello necesitaremos conocer algún medio para finalizar el bucle. En el ejemplo anterior se repetiría desde 1 hasta 25 la acción de pedir la nota.
Otra variante del bucle la podemos pensar con el siguiente ejercicio; Un profesor quiere meter las notas pero debe tener la posibilidad de parar de meterlas cuando el quiera, por ejemplo cuando escriba él –1.
Necesitaríamos ‘algo’ que permitiera repetir el leer datos hasta que escribiera él –1, o bien que mientras lo que leemos sea distinto de –1, leamos notas. Pues esas son las estructuras de repetición.
Estructura mientras
Es aquella en la que la acción o grupo de acciones se repetirá mientras se cumpla la condición y en el momento en que no se cumpla se saldrá del bucle. Es una estructura iterativa con control antes de ejecutar el bloque de instrucciones, es decir, el bloque de instrucciones se ejecuta mientras la evaluación de la expresión sea verdadera, lo que implica que es posible que no se ejecute dicho bloque.
Gráficamente:
En pseudocódigo:
Mientras
.
.
Fin_mientras
Estructura repetir
Es una estructura de control que permite ejecutar un bloque de instrucciones varias veces hasta que la expresión que controla dicha estructura sea verdadera. Debido a que la evaluación de la expresión de control se realiza al final del bloque de instrucciones, este conjunto de instrucciones se ejecuta al menos una vez.
Gráficamente:
En pseudocódigo:
repetir
< acciones >
hasta (condición)
Con una estructura repetir, el cuerpo del bucle se ejecuta siempre al menos una vez. Cuando una instrucción repetir se ejecuta, la primera cosa que sucede es la ejecución del bucle ya continuación se evalúa la expresión booleana resultante de la condición. Si se evalúa como falsa, el cuerpo del bucle se repite y la expresión booleana se evalúa una vez. Después de cada iteración del cuerpo del bucle, la expresión booleana se evalúa; si es verdadera, el bucle termina y el programa sigue en la siguiente instrucción a hasta.
Ejemplo: Dado un conjunto de 100 números enteros, determinar el menor, el mayor y el promedio de ellos.
Acción Principal
Entero Menor, Mayor, N, Suma, cont;
Real promedio;
Leer(N);
Mayor ¬ N;
Menor ¬ N;
Suma ¬ N;
Cont ¬ 1;
Repetir
Leer(N)
Si N > Mayor entonces
Mayor ¬ N;
fsi
Si N < Menor entonces
Menor ¬ N;
fsi
Suma ¬ Suma + N;
cont ¬ cont+1;
Hasta (cont=100)
Promedio ¬ Suma/100;
Escribir (Mayor);
Diferencias de las estructuras mientras y repetir
- 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 mientras se debe estar seguro de que se cumplirá la condición de entrada.
Estructura Para...hasta
Una variable contendrá los valores el número de veces que queramos realizar una secuencia de código, por lo tanto debemos conocer obligatoriamente el número de veces (iteraciones) que se realizaran. Es una estructura iterativa que es controlada por una variable, la cual es modificada desde una cantidad inicial en incrementos dados hasta que alcanza un valor final.
Gráficamente:
En pseudocódigo:
La sintaxis que vamos a utilizar es la siguiente:
Para
Fin_para
No hay comentarios:
Publicar un comentario