unidad_3
Post on 10-Jul-2016
4 Views
Preview:
TRANSCRIPT
Unidad III. Metodología de solución de problemas
3.1.- Definiciones y conceptos generales
3.1.1.- Problema
En ciencia computacional teórica, un problema abstracto o problema computacional es una relación entre un conjunto de instancias y un conjunto de soluciones. Un problema abstracto permite establecer formalmente la relación deseada entre la entrada de un algoritmo y su salida. Una solución algorítmica a un problema abstracto consiste de un algoritmo que por cada instancia del problema calcula al menos una solución correspondiente –en caso de haberla– o expide un certificado de que no existe solución alguna. Un problema abstracto se convierte en un problema concreto cuando las instancias y soluciones están codificadas en forma de lenguajes formales.
3.1.2.- Elementos y relaciones del problema
Los problemas abstractos suelen definirse en dos partes: en la primera se describe
al conjunto de instancias y en la segunda se describe la solución esperada para
cada instancia. Por ejemplo, el problema de ordenación de números enteros se
suele definir como sigue:
Instancia: Una sucesión finita de números enteros
Solución: Una permutación de la sucesión de entrada tal
que
Aquí tanto el conjunto de instancias y el de soluciones es el mismo, pues se trata
del conjunto de todas las sucesiones finitas de números enteros. La relación que
hay entre ellos asigna a cada sucesión la única
permutación tal que . Por
ejemplo, tiene como solución a . Una solución
algorítmica al problema de ordenamiento es el ordenamiento de burbuja porque
este algoritmo produce una solución como salida cada vez que se le suministra una
instancia como entrada.
3.1.3.- Herramientas computacionales para la solución de problemas
Las dos herramientas más utilizadas para diseñar algoritmos son: diagramas de
flujo y pseudocódigo. 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, por sus siglas en inglés). El
pseudocódigo es una herramienta de programación en 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 especificaciones de algoritmos.
3.1.4.- Hardware
El Hardware son todos los componentes y dispositivos físicos y tangibles que
forman una computadora como la CPU o la placa base, mientras que el Software
es el equipamiento lógico e intangible como los programas y datos que almacena
la computadora.
3.1.5.- Sistema Operativo
Un Sistema Operativo es el software encargado de ejercer el control y coordinar el
uso del hardware entre diferentes programas de aplicación y los diferentes
usuarios. Es un administrador de los recursos de hardware del sistema.
3.1.6.- Programas de Aplicación
Es un tipo de software diseñado para facilitar al usuario la concreción de un cierto
trabajo. Esta característica lo diferencia de otros tipos de programas, como los
sistemas operativos (que son los que hacen funcionar a la computadora), los
lenguajes de programación (que permiten crear los programas informáticos en
general) y las utilidades (que realizan tareas de mantenimiento o de uso general).
3.1.7.- Lenguajes de Programación
Es un lenguaje diseñado para describir el conjunto de acciones consecutivas que
un equipo debe ejecutar.
Generaciones De Los Lenguajes de Programación
Lenguaje de Primera Generación.
Lo constituyen los lenguajes máquina.
Estos se consideran como de bajo nivel porque no existe un programa de
codificación menos complicado que el que utiliza los símbolos binarios 1 y 0.
Utiliza ceros y unos para representar letras del alfabeto.
Como este es el lenguaje del CPU, los archivos de texto traducidos a los grupos
binarios ASCII pueden leerse por casi cualquier plataforma de sistemas de
computadoras.
Lenguaje de Segunda Generación
A estos se les denomino lenguaje ensamblador.
Los lenguajes ensambladores usan códigos como a para agregar o mvc para
mover, y así sucesivamente.
Los programas de software de sistemas tales como los sistemas operativos y los
programas de utilidad se escriben con frecuencia en un lenguaje ensamblador.
Lenguaje de Tercera Generación
Estos son más fáciles de aprender y usar que los lenguajes máquina y el lenguaje
ensamblador, pues su similitud con la comunicación y comprensión humana
cotidiana es mayor.
Enunciados, Print, Total Sales, Read normal Pay etc.
Aunque son más fáciles de programar, no son tan eficientes en términos de
rapidez operacional y memoria.
Son relativamente independientes del hardware de la computadora. Esto significa
que el mismo puede utilizarse en varias computadoras diferentes de distintos
fabricantes.
Lenguaje de Cuarta Generación
Son lenguajes que se relacionan menos con procedimientos y que son aún más
parecidos al inglés que los lenguajes de tercera generación.
Algunas características incluyen capacidades de consulta y base de datos, de
creación de códigos y capacidades gráficas.
Ejemplos Visual C++, Visual Basic, Power Builder, Delphi, Forte y muchos otros.
Lenguajes de consulta son utilizados para hacer preguntas a la computadora con
frases parecidas alas de un idioma, ejemplo el inglés.
Lenguaje de consulta estructurado. Lenguaje estándar que a menudo se usa para
realizar consultas y manipulaciones a la base de datos.
Lenguaje de Quinta Generación
Alrededor de la mitad 1998 surgieron grupos de herramientas de lenguajes de
quinta generación, los cuales combinan la creación de códigos basadas en reglas,
la administración de reutilización y otros avances.
Programación basada en conocimiento. Método para el desarrollo de programas
de computación en el que se le ordena a la computadora realizar un propósito en
vez de instruirla para hacerlo.
3.2.- Ciclo de desarrollo de programas
3.2.1.- Planteamiento del Problema
Es el enunciado del problema, el cual debe ser claro y completo. Es fundamental
conocer y delimitar por completo el problema, saber que es lo se desea realice la
computadora, mientras esto no se conozca del todo, no tiene caso continuar con el
siguiente paso.
3.2.2.- Análisis del problema
Consiste en establecer una serie de preguntas acerca de lo que establece el
problema, para poder determinar si se cuenta con los elementos suficientes para
llevar a cabo la solución del mismo.
3.2.3.- Elaboración de Algoritmos
Es el proceso que convierte los resultados del análisis en un diseño modular
(descendente) con refinamiento sucesivo (divide al problema en cada etapa y
expresa a cada paso en forma más detallada), que permitan una posterior
traducción a un lenguaje.
3.2.4.- Codificación, edición y compilación
Es el proceso que consiste en la traducción de las instrucciones del diagrama de
flujo o pseudocódigo al lenguaje de programación.
El proceso de compilación, acepta como entrada el programa fuente y checa la
sintaxis de las instrucciones del mismo, de no existir errores de sintaxis, se genera
el programa objeto escrito en el lenguaje de máquina, listo para su ejecución, en
caso contrario dicho programa no es generado hasta que quede exento de errores.
3.2.5.- Ejecución y depuración
Es el proceso en el cual se ejecuta el programa y la depuración es corregir los
errores encontrados en la etapa anterior, si hubiese algún error se tiene que
regresar hasta la etapa que sea necesaria para que la solución sea la que el
usuario requiere.
3.2.6 Documentación
La documentación de un problema consta de las descripciones de los pasos a dar
en el proceso de resolución de un problema. La documentación de un programa
puede ser interna y externa. La documentación interna es la contenida en líneas de
comentarios. La documentación externa incluye análisis, diagramas de flujo,
pseudocódigo, manuales de usuario con instrucciones para ejecutar el programa y
para interpretar los resultados. La documentación es vital cuando se desea corregir
posibles errores futuros o bien cambiar el programa. Tales cambios se denominan
mantenimiento del programa. Después de cada cambio la documentación debe ser
actualizada para facilitar cambios posteriores.
3.2.7 Mantenimiento
El mantenimiento preventivo es que hagamos lo posible por no caer en errores, la
actualización si el usuario tiene la necesidad de quitar o poner algo; téngase en
cuenta que cuando surge mantenimiento tenemos que volver a hacer todos los
pasos anteriores revisando que todas la condiciones sean favorables alrededor del
sistema.
3.3 Expresiones y Operadores
3.3.1 AsignaciónEl operador de asignación se representa por la secuencia de caracteres:=. Permite
asignar a una variable el valor de una expresión. Por ejemplo:
var x,y,z: real;
x:=12.5;
y:=-5.7;
z:=2*x+3*y;
3.3.1 Operadores aritméticos
Los operadores aritméticos operan sobre valores de tipo entero o real. Los
operadores aritméticos se resumen en la tabla 1. En el caso del operador unitario
de cambio de signo, el resultado es del mismo tipo que el del operando; en el caso
de los tres primeros operadores binarios (suma, resta y producto) si ambos
operando son enteros el resultado es entero, si alguno es real el resultado es real.
Tabla 1. Operadores aritméticos
3.3.2 Operadores relacionales
Los operadores de relación son operadores binarios en los que los operandos son
ordinales, reales o de cadena. Los dos primeros operadores sirven también para
operandos de tipo record y punteros. Todos ellos dan lugar a resultados de tipo
booleano. Los operadores de relación se resumen en la Tabla 2.
Tabla 2.- Operadores relacionales
3.3.3 Operadores lógicos
Los operadores lógicos o booleanos realizan operaciones con operandos de tipo
lógico o booleano y tiene como resultado un dato también del mismo tipo. Los
operadores booleanos definidos se resumen en la Tabla 3.
Tabla 3.- Operadores lógicos
3.3.4 Presencia de operadores y evolución de expresiones
Los niveles de prioridad entre operadores en una misma expresión se resumen en la Tabla 4.
Tabla 4.- Orden de prioridades entre operadores
Las secuencias de operadores de igual prioridad normalmente se evalúan de
izquierda a derecha dentro de una expresión, aunque, en algunos casos, el
compilador puede reordenar los operandos durante el proceso de compilación para
generar código objeto óptimo para su posterior ejecución. En muchas ocasiones se
recomienda el uso de los paréntesis para hacer que las expresiones sean más
claras y fáciles de entender. En la Tabla 5 se muestran algunos ejemplos de
expresiones y de los correspondientes resultados al ser evaluadas.
Tabla 5.- Expresiones y resultados correspondientes
Las reglas de evaluación de expresiones pueden resumirse en las siguientes:
a) Un operando situado entre dos operadores de diferente prioridad se liga al
operador de mayor prioridad.
b) Un operando situado entre dos operadores de igual prioridad se liga al operador
de la izquierda.
c) Las expresiones entre paréntesis se evalúan primeramente para ser tratadas
como operandos simples.
3.4 Técnicas de desarrollo de algoritmos
3.4.1 Diseño descendente
Conocida como de arriba-abajo (diseño descendente) y consiste en establecer una
serie de niveles de mayor a menor complejidad (arriba-abajo) que den solución al
problema. Consiste en efectuar una relación entre las etapas de la estructuración
de forma que una etapa jerárquica y su inmediato inferior se relacionen mediante
entradas y salidas de información.
Este diseño consiste en una serie de descomposiciones sucesivas del problema
inicial, que recibe el refinamiento progresivo del repertorio de instrucciones que van
a formar parte del programa.
La utilización de la técnica de diseño descendente tiene los siguientes objetivos
básicos: Simplificación del problema y de los subprogramas de cada
descomposición.
Las diferentes partes del problema pueden ser programadas de modo
independiente e incluso por diferentes personas.
El programa final queda estructurado en forma de bloque o módulos lo que hace
más sencilla su lectura y mantenimiento.
Tabla 6.- Diseño descendente
3.4.2 Refinación progresiva de solución
Es una técnica de análisis y diseño de algoritmos que se basa en la división del
problema principal en problemas más simples. Partiendo de los problemas más
simples, se logra dar solución más efectiva, ya que el número de variables y casos
asociados a un problema simple es más fácil de manejar que el problema
completo. Este tipo de procedimiento se le conoce con diseño descendente y
también aplicable a la optimización del desempeño y a la simplificación de un
algoritmo.
3.4.3 Seudocódigo y diagrama de flujo
Mezcla de lenguaje de programación y español (o inglés o cualquier otro idioma)
que se emplea, dentro de la programación estructurada, para realizar el diseño de
un programa. En esencial, el pseudocódigo se puede definir como un lenguaje de
especificaciones de algoritmos.
Es la representación narrativa de los pasos que debe seguir un algoritmo para dar
solución a un problema determinado. El pseudocódigo utiliza palabras que indican
el proceso a realizar.
El inicio de un algoritmo en pseudocódigo comienza con la palabra Inicio y termina
con la palabra fin.
Las líneas que están entre llaves ({ }) se denomina comentario.
Un ejemplo aclaratorio es el siguiente. Calcular el área de un cuadrado.
Inicio
Leer (lado)
A = lado * lado
Imprimir( A)
Fin
Un diagrama de flujo es la representación gráfica de un algoritmo. También se puede decir que es la representación detallada en forma gráfica de cómo deben realizarse los pasos en la computadora para producir resultados.
Esta representación gráfica se da cuando varios símbolos (que indican diferentes procesos en la computadora), se relacionan entre sí mediante líneas que indican el orden en que se deben ejecutar los procesos.
A continuación se muestra la simbología utilizada y su función correspondiente.
Ejemplo: Hacer un diagrama de flujo que permita leer 2 números diferentes y nos diga cuál es el mayor de los 2 números.
top related