Primitivas algoritmicas y metodos de representación de algoritmos



Descargar 122,31 Kb.
Página1/2
Fecha de conversión08.06.2017
Tamaño122,31 Kb.
  1   2
TALLER 2

PRIMITIVAS ALGORITMICAS Y METODOS DE REPRESENTACIÓN DE ALGORITMOS

Que es un Algoritmo? : Es un conjunto preescrito 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. Tiempo secuencial. Un algoritmo funciona en tiempo discretizado –paso a paso–, definiendo así una secuencia de estados "computacionales" por cada entrada válida (la entrada son los datos que se le suministran al algoritmo antes de comenzar). Tiempo secuencial. Un algoritmo funciona en tiempo sincretizado –paso a paso–, definiendo así una secuencia de estados "computacionales" por cada entrada válida (la entrada son los datos que se le suministran al algoritmo antes de comenzar).

Estado abstracto. Cada estado computacional puede ser descrito formalmente utilizando una estructura de primer orden y cada algoritmo es independiente de su implementación (los algoritmos son objetos abstractos) de manera que en un algoritmo las estructuras de primer orden son invariantes bajo isomorfismo.

Exploración acotada. La transición de un estado al siguiente queda completamente determinada por una descripción fija y finita; es decir, entre cada estado y el siguiente solamente se puede tomar en cuenta una cantidad fija y limitada de términos del estado actual.


  1. Cuantas clases de algoritmos hay?:

Cuáles son?

Algoritmos numéricos

La solución obtenida es siempre aproximada pero su precisión esperada mejora aumentando el tiempo de ejecución. Normalmente, el error es inversamente proporcional a la raíz cuadrada del esfuerzo invertido en el cálculo.

Ejemplo: La aguja de Buffon

Teorema de Buffon: si se tira una aguja de longitud μ a un suelo hecho con tiras de madera de anchura w (w>=μ), la probabilidad de que la aguja toque más de una tira de madera es p=2μ/wp.

Aplicación:


  • Si μ=w/2, entonces p=1/p.

  • Si se tira la aguja un número de veces n suficientemente grande y se cuenta el número k de veces que la aguja toca más de una tira de madera, se puede estimar el valor de p: k ~ n/p → p ~ n/k

  • Es (probablemente) el primer algoritmo probabilista de la historia.

¿Es útil este método?

  • ¿Cómo de rápida es la convergencia? → ¿cuántas veces hay que tirar la aguja?

Muy lenta: n=1500000 para obtener un valor de p±0’01 con probabilidad 0’9.

Algoritmos de Montecarlo



Artículo principal: Método de Monte Carlo.

Hay problemas para los que no se conocen soluciones deterministas ni probabilistas que den siempre una solución correcta (ni siquiera una solución aproximada).



Algoritmo de Montecarlo:

  • A veces da una solución incorrecta.

  • Con una alta probabilidad encuentra una solución correcta sea cual sea la entrada.

Definición: Sea p un número real tal que 0.5
p–correcto
 si:

  • Devuelve una solución correcta con probabilidad mayor o igual que p, cualesquiera que sean los datos de entrada.

  • A veces, p dependerá del tamaño de la entrada, pero nunca de los datos de la entrada en sí.

Un ejemplo de algoritmo de Montecarlo (el más conocido): decidir si un número impar es primo o compuesto.

  • Ningún algoritmo determinista conocido puede responder en un tiempo “razonable” si el número tiene cientos de cifras.

  • La utilización de primos de cientos de cifras es fundamental en criptografía

Pierre Fermat postuló en 1640 el Pequeño teorema de Fermat: Sea n primo. Entonces, a^(n-1) mod n <> 1 para todo entero a tal que 1<=a<=n-1.

Ejemplo: n = 7, a = 5 → 5^6 mod 7 = 1.

Enunciado contra recíproco del mismo teorema: si a y n son enteros tales que 1<=a<=n-1, y si a^(n-1) mod n <> 1, entonces n no es primo.

Fermat formuló la hipótesis: " Fn = 2^ (2^n)+ 1 es primo para todo n"



  • Lo comprobó para: F0=3, F1=5, F2=17, F3=257, F4=65537.

  • Pero no pudo comprobar si F5=4294967297 lo era.

Utilización del pequeño teorema de Fermat para comprobar la primalidad: en el caso de F5, a Fermat le hubiera bastado con ver que existe un 'a' tal que 1<=a<=F5-1 tal que a ^(F5 - 1) mod F5 <> 1) (a=3). Con estas premisas, se puede desarrollar el siguiente algoritmo:

Función. (n:.) . Booleano

Variable a:

Principio

a:=._.(.,n-.);



Si an-. Mod n=.

Entonces devuelve.

Sino devuelve.

Fsi

Fin

Estudio del algoritmo basado en el pequeño teorema de punto:



  • Si devuelve el valor ., es seguro que . (por el teorema de punto).

Algoritmos de Las Vegas

Un algoritmo de Las Vegas nunca da una solución falsa.



  • Toma decisiones al azar para encontrar una solución antes que un algoritmo determinista.

  • Si no encuentra solución lo admite.

Hay dos tipos de algoritmos de Las Vegas, según la posibilidad de no encontrar una solución:

  • Los que siempre encuentran una solución correcta, aunque las decisiones al azar no sean afortunadas y la eficiencia disminuya.

  • Los que a veces, debido a decisiones desafortunadas, no encuentran una solución.

Tipo a: Algoritmos de Sherwood

Existe una solución determinista que es mucho más rápida en media que en el peor caso.

Ejemplo: quicksort.

Coste peor Ω(n^2) y coste promedio O (nlog n).



  • Coste promedio: se calcula bajo la hipótesis de equiprobabilidad de la entrada.

  • En aplicaciones concretas, la equiprobabilidad es falsa: entradas catastróficas pueden ser muy frecuentes.

  • Degradación del rendimiento en la práctica.

Los algoritmos de Sherwood pueden reducir o eliminar la diferencia de eficiencia para distintos datos de entrada:

  • Uniformización del tiempo de ejecución para todas las entradas de igual tamaño.

  • En promedio (tomado sobre todos los ejemplares de igual tamaño) no se mejora el coste.

  • Con alta probabilidad, ejemplares que eran muy costosos (con algoritmo determinista) ahora se resuelven mucho más rápido.

  • Otros ejemplares para los que el algoritmo determinista era muy eficiente, se resuelven ahora con más coste.

Tipo b: Algoritmos que, a veces, no dan respuesta.

  • Son aceptables si fallan con probabilidad baja.

  • Si fallan, se vuelven a ejecutar con la misma entrada.

  • Resuelven problemas para los que no se conocen algoritmos deterministas eficientes(ejemplo: la factorización de enteros grandes).

  • El tiempo de ejecución no está acotado pero sí es razonable con la probabilidad deseada para toda entrada.

Consideraciones sobre el coste:

  • Sea LV un algoritmo de Las Vegas que puede fallar y sea p(x) la probabilidad de éxito si la entrada es x.

Algoritmo LV (ent x: tpx; sal s: tpsolución;

Sal éxito: booleano)

{Éxito devuelve. si LV encuentra la solución

y en ese caso s devuelve la solución encontrada}


  • Se exige que p(x)>0 para todo x.

  • Es mejor aún si existe d>0: p(x)>=d para todo x (así, la probabilidad de éxito no tiende a 0 con el tamaño de la entrada).

Ahora repetimos el algoritmo anterior para ganar en eficacia:

Función repe_LV(x:tpx) devuelve tpsolución

Variables s:tpsolución; éxito: booleano

Principio

Repetir

LV(x,s,éxito)



Hasta Que éxito;

De vuelve s

Fin

  • El número de ejecuciones del bucle es ./p(x).

  • Sea v(x) el tiempo esperado de ejecución de LV si éxito=. y f(x) el tiempo esperado si éxito=.

  • el tiempo esperado de repe _L V () = v(x) + ((. - p(x))/ p(x)) f(x).

Ejemplo: El problema de todos los. En el tablero de go.

  • Algoritmo determinista: Nº de nodos visitados: de los . nodos del árbol)

  • Algoritmo de Las Vegas voraz: colocar cada aleatoriamente en uno de los escapes posibles de la siguiente fila. El algoritmo solo puede terminar con éxito (pues siempre hay forma de colocar el siguiente.).Nº de nodos visitados para éxito: v=., Probabilidad de éxito: p=. (más de . vez de cada .)

  • Número esperado de nodos visitados repitiendo hasta obtener un éxito: t=v+f(.-p)/p=., menos de .

Enlaces externos

Que es una variable? En programación, las variables son espacios reservados en la memoria que, como su nombre indica, pueden cambiar de contenido a lo largo de la ejecución de un programa. Una variable corresponde a un área reservada en la memoria principal del ordenador pudiendo ser de longitud:

Que es una constante? Una constante es un valor que no puede ser alterado durante la ejecución de un programa.

Una constante corresponde a una longitud fija de un área reservada en la memoria principal del ordenador, donde el programa almacena valores fijos.

Por ejemplo:


  • El valor de pi = 3.1416

Como se crean nombres de variables y constante

Primitivas algorítmicas: Una primitiva algorítmica capturar los datos que el usuario quiere asignar a las variable ¿Cómo? Hace que se interrumpa la ejecución del algoritmo y hace q el usuario digite un valor de cualquier tipo que será asignado a la variable X. la captura se acompaña de una mensaje que indica al usuario el objetivo de la captura. Las primitivas se clasifican en:

Estructuras Secuenciales

- asignación - entrada o lectura – salida

Estructuras condicionales

-simples -compuestas –anidadas

Estructuras repetitivas

-hacer para –hacer mientras –repetir hasta

Enúncielas y clasifíquelas:

Tipos de datos.

Expresiones.

Operadores y operados.

Identificadores como localidades de memoria.

Tipos De Datos

Todos los datos tienen un tipo asociado con ellos. Un dato puede ser un Simple carácter, tal como `b', un valor entero tal como 35. El tipo de dato Determina la naturaleza del conjunto de valores que puede tomar una variable.

Numéricos, Simples Lógicos, Alfanuméricos (string), Tipos de, datos Arreglos (Vectores, Matrices) Estructurados Registros (Def. por el Archivo su usuario) Apuntadores

Tipos de Datos Simples

Datos Numéricos: Permiten representar valores escalares de forma numérica, esto incluye a los números enteros y los reales. Este tipo de datos permiten realizar operaciones aritméticas comunes.

Datos Lógicos: Son aquellos que solo pueden tener dos valores (cierto o falso) ya que representan el resultado de una comparación entre otros datos (numéricos o alfanuméricos).Datos Alfanuméricos (String): Es una secuencia de caracteres alfanuméricos que permiten representar valores identificables de forma descriptiva, esto incluye nombres de personas, direcciones, etc. Es posible representar números como alfanuméricos, pero estos pierden su propiedad matemática, es decir no es posible hacer operaciones con ellos. Este tipo de datos se representan encerrados entre comillas. Ejemplo: “Instituto Tecnológico de Tuxtepec”“1997” Expresiones Las expresiones son combinaciones de constantes, variables, símbolos de operación, paréntesis y nombres de funciones especiales. Por ejemplo: a+ (b + 3)/c 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 operadores y operandos. Según sea el tipo de datos que manipulan, se clasifican las expresiones en: Aritméticas, Relaciónales, Lógicas, Operadores y Operandos Operadores: Son elementos que relacionan de forma diferente, los valores de una o más variables y/o constantes. Es decir, los operadores nos permiten manipular valores. Aritméticos, Tipos de Operadores Relaciónales, Lógicos, Operadores Aritméticos: Los operadores aritméticos permiten la realización de operaciones matemáticas con los valores (variables y constantes).Los operadores aritméticos pueden ser utilizados con tipos de datos enteros o reales. Si ambos son enteros, el resultado es entero; si alguno de ellos es real, el resultado es real.



Identifique y explique la estructura de las primitivas algorítmicas secuenciales y condicionales

Estructuras Secuenciales

La estructura secuencial es aquella en la que una acción (instrucción) sigue a otra en secuencia. Las tareas se suceden de tal modo que la salida de una es la entrada de la siguiente y así sucesivamente hasta el fin del proceso.



- Asignación: La asignación consiste, en el paso de valores o resultados a una zona de la memoria. Dicha zona será reconocida con el nombre de la variable que recibe el valor. La asignación se puede clasificar de la siguiente forma:

· Simples: Consiste en pasar un valor constate a una variable (a=15)

· Contador: Consiste en usarla como un verificador del numero de veces que se realiza un proceso (a=a+1)

· Acumulador: Consiste en usarla como un sumador en un proceso

(a=a+b)

· De trabajo: Donde puede recibir el resultado de una operación matemática que involucre muchas variables (a=c+b*2/4).



-Lectura o salida: La lectura consiste en recibir desde un dispositivo de entrada (p.ej. el teclado) un valor. Esta operación se representa en un pseudocódigo como sigue:

Lea (a);

Lea (b);

Donde “a” y “b” son las variables que recibirán los valores

-Escritura o salida: Consiste en mandar por un dispositivo de salida (p.ej. monitor o impresora) un resultado o mensaje. Este proceso se representa en un pseudocódigo como sigue:

Escriba (‘El resultado es:’);

Escriba(R);

Escriba (‘El resultado es:’ R);

Donde “El resultado es:” es un mensaje que se desea aparezca y R es una variable que contiene un valor.

Estructura condicionales

Las primitivas condicionales comparan una variable contra otro(s) valor(es), para que en base al resultado de esta comparación, se siga un curso de acción dentro del programa. Cabe mencionar que la comparación se puede hacer contra otra variable o contra una constante, según se necesite. Existen dos tipos básicos, las simples y las múltiples.



  1. Simples.

Consisten en pasar un valor constante a una variable (a 15)

  1. Compuestas

Son aquellos que utilizan las dos acciones (verdadera y falsa)

  1. ANIDADAS

Son aquellas que utilizan varias condicionales simples o compuestas

En ocasiones cuando hay más de dos caminos posibles es necesario implementar estructuras condicionales anidadas, es decir por la rama del verdadero o falso (else:) disponemos otras estructuras condicionales.

Debemos tener cuidado con la identificación del código para evitar errores.

Veamos un ejemplo que requiere utilizar estructuras condicionales anidadas. Generaremos tres números aleatorios y luego imprimiremos el mayor de los tres:

import random
X1=random. randint (1,100)

X2=random. randint (1,100)

X3=random .randint(1,100)

print x1


print '-'

print x2


print '-'

print x3


print '
'

print 'El mayor es:'

if x1>x2:

if x1>x3:

print x1

else:


print x3

else:


if x2>x3:

print x2


else:

print x3


  1. MULTIPLES

Las estructuras de comparación múltiples, son tomas de decisión especializada que permiten comparar una variable contra distinta posibles resultados, ejecutando para cada caso una serie de instrucciones específicas.

.

Explique los siguientes métodos de representación algorítmicas e identifique las convenciones símbolos o estructuras que utiliza cada una:

Pseudocódigo 

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. 

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 realiza.

Las acciones sucesivas se puedes escribir en cajas sucesiva y como en los diagramas de flujo, se puede escribir diferentes acciones de una caja. Un algoritmo se representa en la siguiente forma

Ejemplo:

Inicio


Leer

Nombre,hrs,Precio

Calcular

Salario = Hrs * Precio

Calcular

Imp = Salario* 0.15

Calcular

Neto = Salario +Imp

Escribir

Nombre, Imp, SNeto

Fin.

Diagrama de Flujo

Concepto

Los diagramas de flujo (o flujo gramas) son diagramas que emplean símbolos gráficos parare presentar los pasos o etapas de un proceso. También permiten describir la secuencia de los distintos pasos o etapas y su interacción.

Las personas que no están directamente involucradas en los procesos de realización del producto o servicio, tienen imágenes idealizadas de los mismos, que pocas veces coinciden con la realidad. 
Los símbolos en un diagrama de flujo tienen significados específicos y se conectan por medio de flechas que indican el flujo entre los distintos pasos o etapas.

Los símbolos más comunes son:


Símbolos


Comienzo o inicio y fin

Proceso General



Toma de decisiones



Comentarios

Entrada de datos por teclado

Salida de datos por pantalla





Salidas de datos por impresora

Almacenamiento en disco magnético

Conector fuera de pagina

Línea de conexión y dirección de flujo

Ejempló de un diagrama de flujo




  1   2


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal