T002: Conceptos básicos de programación

publicado a la‎(s)‎ 17 sept. 2012 15:28 por Hernan Nina Hanco   [ actualizado el 17 sept. 2012 20:01 ]
Algoritmo

"Es una secuencia finita de instrucciones, cada una de  las cuales tiene un significado preciso y puede ejecutarse con una cantidad finita de esfuerzo en un tiempo finito". 
(Según el Libro de "Estructuras de datos y algoritmos" de Alfred V. Aho, John E. Hopcroft, Jefrey D. Ullman.)

"Un Algoritmo es un método para resolver un problema". 
(Según el Libro de "Programación en C, metodología, algoritmos y estructuras de datos de Luis Joyanes Aguilar y Ignacio Zahonero Martinez")

Características de los algoritmos

Las características fundamentales que debe cumplir todo algoritmo son:
  • 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
  • Un algoritmo debe ser finito. Si se sigue un algoritmo, se debe terminar en algún momento; o sea, debe tener un numero fínito de pasos.
La definición de un algoritmo debe describir tres partes: Entrada, Proceso y Salida. En el algoritmo de receta de cocina se tendrá:
Entrada: ingredientes y utensilios empleados.
Proceso: elaboración de la receta en la cocina.
Salida: terminación del plato (por ejemplo, cordero).

Programa

Las operaciones que debe realizar el Hardware son especificadas por una lista de instrucciones, llamadas programas, o Software. Un programa se escribe en un lenguaje de programación en base a un algoritmo suministrado. Expresar un algoritmo en forma de programa se llama programación. 

Lenguaje de programación

Programas que sirven para escribir programas que permiten la comunicación usuario/máquina. Unos programas especiales llamados traductores (Compiladores o intérpretes) convierten las instrucciones escritas en lenguajes de programación en instrucciones escritas en lenguaje máquina (0 y 1, bits) que ésta pueda entender.

Conceptos básicos de algoritmo y programa

Ejemplo de algoritmo

Ejemplo 1.1
Un cliente ejecuta un pedido a una fábrica. La fábrica examina en su banco de datos la ficha del cliente, si el cliente es solvente entonces la empresa acepta el pedido; en caso contrario, rechazará el pedido.

Redactar el algoritmo correspondiente.

Los pasos del algoritmo son:

1. Inicio.
2. Leer el pedido.
3. Examinar la ficha del cliente.
4. Si el cliente es solvente, aceptar pedido; en caso contrario, rechazar pedido.
5. Fin.

Ejemplo 1.2

Se desea diseñar un algoritmo para saber si un número es primo o no. Un número es primo si sólo puede dividirse por sí mismo y por la unidad (es decir, no tiene más divisores que él mismo y la unidad). Por ejemplo, 9,8,6,4,12,16,20, etc., no son primos, ya que son divisibles por números distintos a ellos mismos y a la unidad. Así, 9 es divisible por 3, 8 lo es por 2, etc.
El algoritmo de resolución del problema pasa por dividir sucesivamente el número por 2, 3,4 ..., etc.

1. Inicio.
2. Poner X igual a 2 (X = 2, X variable que representa a los divisores del número que se busca N).
3. Dividir N por X (N/X).
4. Si el resultado de N/X es entero, entonces N no es un número primo y bifurcar al punto 7; en caso contrario, continuar el proceso.
5. Suma 1 a X (X X + 1).
6. Si X es igual a N, entonces N es un número primo; en caso contrario, bifurcar al punto
7. Fin.

Por ejemplo, si N es 131, los pasos anteriores serían:

1. Inicio.
2. X = 2.
3. 131/X. Como el resultado no es entero, se continúa el proceso.
5. X 2 + 1, luego X = 3.
6. Como X no es 131, se bifurca al punto 3.
3. 131/X resultado no es entero.
5. X3 + 1, X = 4.
6. Como X no es 131 bifurca al punto 3.
3. 131/X ..., etc.
7. Fin.

Ejemplo 1.3. Algoritmo para leer las páginas de un libro:

1. Inicio.
2. Abrir el libro en la 1ª página.
3. Leer la página.
4. ¿Es la última que deseo leer?
    Sí: Ve al paso 7.
    No: Ve al paso 5
5. Pasar a la siguiente página.
6. Ve al paso 3.
7. Cerrar el libro.
8. Fin.

Fases en la resolución de problemas

El proceso de resolución de un problema con una computadora conduce a la escritura de un programa y a su ejecución en la misma. Aunque el proceso de diseñar programas es esencialmente un proceso creativo, se puede considerar una serie de fases o pasos comunes, que generalmente deben seguir todos los programadores.

Las fases de resolución de un problema con computadora son:
  • Análisis del problema.
  • Diseño del algoritmo.
  • Codificación.
  • Compilación y ejecución.
  • Verificación.
  • Depuración.
  • Mantenimiento.
  • Documentación.
Constituyen el ciclo de vida del software y las fases o etapas usuales son:
Análisis. El problema se analiza teniendo presente la especificación de los requisitos dados por el cliente de la empresa o por la persona que encarga el programa.
Diseño. Una vez analizado el problema, se diseña una solución que conducirá a un algoritmo que resuelva el problema.
Codificación (implementación). La solución se escribe en la sintaxis del lenguaje de alto nivel (por ejemplo, C) y se obtiene un programa.
Ejecución, verificación y depuración. El programa se ejecuta, se comprueba rigurosamente y se eliminan todos los errores que puedan aparecer.
Mantenimiento. El programa se actualiza y modifica, cada vez que sea necesario, de modo que se cumplan todas las necesidades de cambio de sus usuarios.
Documentación. Escritura de las diferentes fases del ciclo de vida del software, esencialmente el análisis, diseño y codificación, unidos a manuales de usuario y de referencia, así como normas para el mantenimiento.

Las dos primeras fases conducen a un diseño detallado escrito en forma de algoritmo. Durante la tercera etapa (codificación) se implementa el algoritmo en un código escrito en un lenguaje de programación, reflejando las ideas desarrolladas en las fases de análisis y diseño. La fase de compilación y ejecución traduce y ejecuta el programa. En las fases de verificación y depuración el programador busca errores de las etapas anteriores y los elimina. Comprobará que mientras más tiempo se gaste en la fase de análisis y diseño, menos se gastará en la depuración del programa. Por último, se debe realizar la documentación del programa.

Ejemplos de Algoritmos

Algoritmo de la burbuja


Algoritmos para multiplicar dos números


Análisis del problema

La primera fase de la resolución de un problema con computadora es el análisis del problema. Esta fase requiere una clara definición, donde se contemple exactamente lo que debe hacer el programa y el resultado o solución deseada. Dado que se busca una solución por computadora, se precisan especificaciones detalladas de entrada y salida. 

Para poder definir bien un problema es conveniente responder a las siguientes preguntas:
  • ¿Qué entradas se requieren? (tipo y cantidad).
  • ¿Cuál es la salida deseada? (tipo y cantidad).
  • ¿Qué método produce la salida deseada?

Ejemplo: calcular el área de un rectángulo

Análisis del problema
El cálculo del área del rectángulo se puede dividir en:
  • Entrada de datos (altura, base)
  • Proceso: Cálculo del área (= base x altura)
  • Salida de datos (base, altura, área)

Diseño del algoritmo

En la etapa de análisis del proceso de programación se determina qué hace el programa. En la etapa de diseño se determina como hace el programa la tarea solicitada. Los métodos más eficaces para el proceso de diseño se basan en el conocido por divide y vencerás. Es decir, la resolución de un problema complejo se realiza dividiendo el problema en subproblemas y a continuación dividir estos subproblemas en otros de nivel más bajo, hasta que pueda ser implementada una solución en la computadora.

Este método se conoce técnicamente como diseño descendente (top-down) o modular. El proceso de romper el problema en cada etapa y expresar cada paso en forma más detallada se denomina refinamiento sucesivo.
Cada subprograma es resuelto mediante un módulo (subprograma) que tiene un solo punto de entrada y un solo punto de salida. Cualquier programa bien diseñado consta de un programa principal (el módulo de nivel más alto) que llama a subprogramas (módulos de nivel más bajo) que a su vez pueden llamar a otros subprogramas.
Los programas estructurados de esta forma se dice que tienen un diseño modular y el método de romper el programa en módulos más pequeños se llama programación modular. Los módulos pueden ser planeados, codificados, comprobados y depurados independientemente (incluso por diferentes programadores) y a continuación combinarlos entre sí. El proceso implica la ejecución de los siguientes pasos hasta que el programa se termina:

1. Programar un módulo.
2. Comprobar el módulo.
3. Si es necesario, depurar el módulo.
4. Combinar el módulo con los módulos anteriores.

El proceso que convierte los resultados del análisis del problema en un diseño modular con refinamientos sucesivos que permitan una posterior traducción a un lenguaje se denomina diseño del algoritmo. El diseño del algoritmo es independiente del lenguaje de programación en el que se vaya a codificar posteriormente.

Ejemplo de diseño para el problema del área del triangulo.


Herramientas de programación

Las dos herramientas más utilizadas comúnmente para diseñar algoritmos son: diagramas de flujo, y pseudocódigos.

Diagramas de flujo


Un diagrama de flujo (flowchart) es una representación gráfica de un algoritmo. Los símbolos utilizados han sido normalizados por el Instituto Norteamericano de Normalización (ANSI).

Pseudocódigo

El pseudocódigo es una herramienta de programación en la que las instrucciones se escriben en palabras similares al inglés o español, que facilitan tanto la escritura como la lectura de programas. En esencia, el pseudocódigo se puede definir como un lenguaje de especijicaciones de algoritmos.

Algunas palabras utilizadas en el pseudocódigo:
  • Inicio
  • Fin
  • Leer
  • Escribir
  • Asignar ()
Ejemplo de pseudocodigo para el problema del área del triangulo

Programa CalculoAreaRectangulo
Inicio
    leer(base, altura)
    area.base x altura
    escribir(base,altura,area)
Fin


Comments