document4
TRANSCRIPT
14-9-2013
FUNDAMENTOS
DE
ALGORITMOS
COMPUTACION PARA INGENIEROS
TAREA: 4
Leal Villavicencio Fernando Abel
Correo:
CONTENIDO:
5.1 La Computabilidad y Concepto de algoritmo: Máquina de Turing
5.2 Elementos de los algoritmos y tipos de datos
5.3 Representación de los algoritmos (diagrama de flujo y pseudocódigo)
5.4 Estructuras básicas (secuencia, condicional e iteración)
5.5 Resolución de problemas básicos de ingeniería
5.1 LA COMPUTABILIDAD Y CONCEPTO DE ALGORITMO: MÁQUINA DE TURING ¿Que es computabilidad? Consiste en ser capaz de encontrar la representación adecuada para la
descripción de un problema o fenómeno.
Para tal representación es necesario:
Un conjunto finito de símbolos. Hacer asociaciones entre conceptos y elementos del lenguaje (de
símbolos) Encontrar las combinaciones adecuadas de símbolos para evitar
ambigüedad. Definir una manera de confirmar tal descripción para que terceros
puedan reproducirla y llegar a los mismos resultados.
La Teoría de la Computabilidad consiste en encontrar maneras de representar descripciones de procesos, de tal manera que se pueda asegurar si existe o no una representación.
Se dice que un algoritmo es una manera formal y sistemática de representar la descripción de un proceso.
Un algoritmo es un conjunto prescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos sucesivos que no generen dudas a quien deba realizar dicha actividad. Dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución. Los algoritmos son el objeto de estudio de la algoritmia
Máquina de Turing. En 1937 el matemático ingles Alan Mathison Turing (1912-1953) publico otro artículo famoso (sobres los nueros calculables), que desarrollo el teorema de Gödel y que puede considerarse el origen oficial de la informática teórica. En este artículo introdujo la máquina de Turing, una entidad matemática abstracta que formaliza el concepto de algoritmo y resulto ser la precursora de las computadoras digitales. Con ayuda de su máquina, Turing pudo demostrar que existen problemas irresolubles, tales que ninguna máquina de Turing será capaz de obtener su solución, por lo que a Alan Turing se le considera el padre de la teoría de la computabilidad
La “máquina” no se debe confundir con un aparato físico. Se trata más bien de una construcción matemática. Una máquina de Turing puede considerarse como una cinta infinita dividida en casillas, cada una de las cuales contiene un símbolo. Sobre dicha cinta actúa un dispositivo que puede adoptar diversos estados y que, en cada instante, lee un símbolo de la casilla sobre la que está situado. En función del símbolo que ha leído y del estado en que se en cuenta, realiza las tres acciones siguientes: pasa a un nuevo estado, imprime un símbolo en lugar del que acaba de leer y se desplaza una posición hacia la izquierda, o hacia la derecha, o bien la maquina se para. El funcionamiento de una maquina Turing puede representarse mediante una tabla de doble entrada. Las filas están encabezadas por los estados, las columnas por los símbolos escritos en cinta. En cada posición de la tabla hay tres elementos: el estado siguiente, el símbolo que se escribe en la cinta y el movimiento de la cabeza (i,d,p). 5.2 ELEMENTOS DE LOS ALGORITMOS Y TIPOS DE DATOS
Elementos de un algoritmo ------- Variables, constantes y expresiones
Estructuras de control Secuencial Operación de asignación Operación de entrada Operación de salida
Condicional Repetitiva
Variables
• Como su nombre lo indica, representan un valor susceptible a modificaciones. Estas variables se pueden nombrar para identificarlas durante el proceso, este nombramiento se puede limitar en algunos compiladores de acuerdo al numero de caracteres utilizados, no se deben utilizar caracteres especiales como lo son /*-+@#,;<>?¿$!¡|\”%(), ni espacios en blanco, estos espacios se podrían simbolizar así _ Constantes
• Es una cantidad fija, donde el valor de esta no cambia durante la ejecución o ejecuciones del proceso. Suma: X (+) Y = Z Resta: X (-) Y = Z Estructura condicional
• Estas estructuras comparan una variable con otra variable o una constante, para que en base a estos resultados se efectúen las operaciones respectivas para cada caso. Existen 3 tipos básicos de estas estructuras: Las simples, Las dobles y Las Múltiples.
1. Simples
• Se conoce como toma de decisión y tiene la siguiente forma: Si <condición> Entonces Instrucción(es) Fin-Si Ejemplo:
INICIO
Leer X
Si (X >= 18) entonces
impr “ Persona es mayor de edad”
Fin-Si
FIN
2. Dobles
• Estas estructuras nos permiten elegir entre 2 opciones disponibles un “SI” y un “NO” y tienen la siguiente forma: Si <condición> Entonces Instrucción(es) Si no Instrucción(es)
Fin-Si Ejemplo:
INICIO
Leer X
Si (X >= 18) entonces
impr “ Persona es mayor de edad”
Si-no
impr ”persona es menor de edad”
Fin-Si
FIN
3. Múltiples
• Son tomas de decisión especializada que permiten comparar una variable contra distinta posibles soluciones ejecutando para cada caso una serie de instrucciones. Estas tienen la siguiente forma:
Ejemplo:
Tipos de datos Se denomina dato a cualquier objeto manipulable por la computadora. Un dato puede ser un carácter leído de un teclado, información almacenada en un disco, un número que se encuentra en memoria principal, etc.
Para que se pueda operar con los datos es necesario que existan unas operaciones internas en el conjunto de datos, que sean semejantes a las operaciones usuales en el conjunto de magnitudes. Dichas operaciones deben cumplir que la imagen de la transformación del resultado de una operación en el conjunto de magnitudes sea igual al resultado de las operaciones correspondientes en el conjunto de datos sobre las imágenes de los operandos. Para que los resultados obtenidos en el conjunto de datos puedan ser interpretados es necesario que exista una transformación de éstos al conjunto de magnitudes. Se denomina tipo de dato al conjunto de la transformación y de las operaciones y funciones internas y externas definidas sobre el conjunto de datos.
1. Datos de tipo entero El tipo entero es una representación del conjunto de los números enteros. La representación es posible para un subrango de magnitudes enteras centrado en el origen: números entre 2n-1 -1 y -2n-1. La razón de esta limitación está en la necesidad de utilizar un espacio finito, y fijo, para cada dato. El número de datos distintos de tipo entero que se pueden generar es 2n, donde n es el número de bits que se utiliza
en la representación. Por tanto, si se modifica el número de bits, se obtienen distintos tipos enteros. Cualquier operación con datos de tipo entero es exacta salvo que se produzcan desbordamientos. Ejemplos: x 21; y -34; z 0;
2. Datos de tipo real El tipo de datos real es una representación del conjunto de los números reales. Esta representación no suele permitir el almacenamiento de números muy grandes o muy pequeños, lo que conlleva que se produzcan desbordamientos (overflows) o agotamiento (underflows). La limitación del número de bits usados para representar la mantisa provoca una falta de precisión en la representación. Esto es debido a que la aplicación que define al tipo real no es unívoca. Es decir, cada dato de tipo real es la imagen de un conjunto infinito de números reales, concretamente representa a un intervalo de la recta real. En cada operación pueden producirse errores por falta de precisión en la representación (errores de redondeo), que se acumulan durante todo el proceso de cálculo. Ejemplos: y 4,56000987000001; x 23,236666666666666667;
3. Datos de tipo lógico Los datos de tipo lógico representan valores lógicos o booleanos. Pueden tomar uno de entre dos valores: verdadero o falso (abreviadamente V, F o 0,1) Sobre los valores lógicos pueden actuar los llamados operadores lógicos. Los operadores lógicos son: Y, O y NO (en inglés AND, OR y NOT). En algunos lenguajes de programación hay definidos sobre los datos de tipo lógico otros operadores booleanos, como son: NO-Y, NO-O y NO-exclusivo (en inglés NAN, NOR y XOR). Un caso particularmente importante de valor de tipo lógico es el obtenido como resultado de una operación de relación sobre datos de un tipo para el que existe una relación de orden. Una relación es una expresión formada por dos operandos pertenecientes a un mismo tipo ordenado y un operador de relación. El resultado de una operación de relación es el valor lógico verdadero si la relación expresada escierta, y falso en caso contrario.
4. Datos de tipo carácter
Los datos de tipo carácter representan elementos individuales de conjuntos finitos y ordenados de caracteres. El conjunto de caracteres representado depende de la computadora. Uno de los conjuntos más usuales es el ASCII. No hay ninguna operación interna sobre datos de tipo carácter (salvo la asignación). Normalmente existen funciones de conversión de tipo, como
por ejemplo la que asocia a cada dato de tipo carácter un valor entero, que indica su posición en el código. Ejemplos: x ‘a’; y ’4’;
5. Datos de tipo enumerado Los datos de tipo enumerado se definen explícitamente dando un conjunto finito de valores. Al contrario de los tipos vistos anteriormente, no es un tipo normalizado. Puede haber muchos tipos de datos enumerados distintos dentro de un programa en un lenguaje determinado. Los datos vistos en las secciones anteriores son usualmente tratados por la computadora a nivel hardware. Mientras que el tipo de datos enumerado y el tipo de datos subrango sólo son interpretados por el software. Internamente los datos de tipo enumerado se almacenan como valores enteros. A cada valor del tipo se le asocia un entero consecutivo, comenzando por cero. Ejemplo: x {azul (0), rojo (1), verde (2), amarillo (3)};
6. Datos de tipo subrango El tipo subrango se define a partir del tipo entero, carácter o de un tipo enumerado. Un dato de tipo subrango puede tomar determinados valores del tipo original, a partir del cual se ha definido el subrango, entre un mínimo y un máximo. Con datos de tipo subrango se pueden realizar las operaciones definidas para el tipo original. 5.3 REPRESENTACIÓN DE LOS ALGORITMOS (DIAGRAMA DE FLUJO Y PSEUDOCÓDIGO) Pseudocódigo No hay reglas fijas para la representación narrativa de algoritmos. No
obstante para describir algoritmos está muy extendido el uso de las
estructuras de control del lenguaje Pascal entre otros. En este caso, como
el objetivo no es escribir un programa para ser ejecutado por una
computadora, no hay reglas sintácticas escritas, el interés se centra en la
secuencia de instrucciones. Este tipo de descripción se denomina
pseudocódigo. La utilización de pseudocódigo presenta las ventajas de
ser más compacto que un organigrama, ser más fácil de escribir, y ser
más fácil de transcribir a un lenguaje de programación.
Ejemplo.
Diagrama de flujo
Es la representación gráfica de un algoritmo, también son utilizados en
campos como la economía, la programación, los procesos industriales.
Utilizan símbolos con significados definidos que representan la etapa del
algoritmo.
5.4 ESTRUCTURAS BÁSICAS (SECUENCIA, CONDICIONAL E
ITERACIÓN)
En la elaboración de algoritmos nos vamos a encontrar con estructuras
básicas o de control ya prediseñadas para el tratamiento de información,
estas estructuras básicas traducen acciones que se realizan de acuerdo
al requerimiento o al proceso necesario al cual deba someterse la
información. Estas estructuras son:
a) Secuenciales: cuando se requiere que una instrucción siga después de
otra.
b) Selección o decisión: se utiliza cuando se requiere tomar decisiones
lógicas, la ejecución de las instrucciones dependerá de que se cumplan o
no, una o varias condiciones.
c) Repetición o Iteración: se utiliza cuando un proceso debe repetirse un
número determinado o no de veces, una vez se haya establecido cierta
condición para finalizar el proceso de repetición.
Asimismo dentro de las estructuras básicas existen acciones o procesos
a los cuales son sometidos los datos, entre ellos, tenemos:
a. Asignación
b. Condicionado (a través de las expresiones lógicas)
c. Alternativas (estructura condicional)
d. Iterativas
e. De entrada y salida