PDF de programación - Algoritmo

Imágen de pdf Algoritmo

Algoritmográfica de visualizaciones

Publicado el 2 de Agosto del 2020
87 visualizaciones desde el 2 de Agosto del 2020
318,8 KB
42 paginas
Creado hace 14a (24/08/2006)
ALGORITMO:

“Un algoritmo es un conjunto finito de reglas que sin ambigüedad efectúan
algún calculo, el cual puede ser realizado en forma manual o por medio de una
maquina”



Algoritmos Deterministas: Para los mismos datos de entrada se producen los
mismos datos de salida.

Algoritmos no Deterministas: Para los mismos datos de entrada se pueden
producir diferentes salidas.

Existen problemas para los cuales no se conocen Algoritmos Prácticos,
porque el tiempo de finalización de los mismos puede ser de millones de años.

En estos casos, es necesario diseñar algoritmos que faciliten buenas soluciones
y en un tiempo razonable. (Se deben diseñar heurísticas).
Definición: De acuerdo con ANSI/IEEE Std 100-1984, la heurística trata de
métodos o algoritmos exploratorios durante la resolución de problemas en los
cuales las soluciones se descubren por la evaluación del progreso logrado en
la búsqueda de un resultado final. Se suele usar actualmente como adjetivo,
caracterizando técnicas por las cuales se mejora en promedio el resultado de
una tarea resolutiva de problemas (parecido al uso de "método óptimo").



1

ALGORITMIA

En algunas ocasiones se dispone de diferentes algoritmos que resuelven un
mismo problema, entonces, surge la pregunta: ¿Cual utilizar?

“La ALGORITMIA es la ciencia que estudia técnicas para diseñar algoritmos
eficientes y evaluar la eficacia de un algoritmo”

Para evaluar y diseñar algoritmos eficientes la Algoritmia utiliza criterios tales
como:

• La velocidad del computador
• La memoria requerida
• La claridad del código
• La facilidad de implementación
• La cantidad de instrucciones que se ejecutan, etc.


ANALISIS DE ALGORITMOS

“Determina los recursos que necesita la ejecución de un algoritmo”


Este análisis se realiza en función del tiempo de ejecución de un algoritmo
concreto.


Análisis de Algoritmos ≠ Análisis del Problema

Análisis de Algoritmos ≠ Complejidad Computacional



2

COMPLEJIDAD COMPUTACIONAL


“Se dedica al análisis de los problemas”.


El análisis del tiempo de ejecución de un algoritmo se hace mediante el conteo
de instrucciones o el análisis de ecuaciones de recurrencia.

Para el problema de la ordenación de un vector existen un gran número de
algoritmos que resuelven el problema, entre ellos podemos indicar: Inserción
y Mezcla.

Algoritmo Inserción( Var L: Vector[1..N] de <Tipo_Elemento>
Var i,j,n : Entero

Inicio



Fin

Algoritmo Mezcla( Var L: Vector[1..N] de <Tipo_Elemento>
Var L1, L2: Vector[1..N] de <Tipo_Elemento>
Inicio



Fin

x : <Tipo_Elemento>
Para i=2 to N Hacer
Inicio



Fin

x= L[i]; j= i-1;
Mientras (j>0) y (x<L[i]) Hacer
Inicio


Fin
L[j+1]=x

L[i+1]=L[j]
Dec(j)

Si Longitud(L) > 1 Entonces
Inicio



Fin

Partir(L, L1, L2)
Mezcla(L1)
Mezcla(L2)
Intercalar(L, L1, L2)



3

¿En Cual de ellos puedo calcular el tiempo de ejecución realizando un conteo
de instrucciones y en cual es necesario el análisis de ecuaciones de
recurrencia?

Se debe intentar buscar una expresión que modele el conteo de la cantidad de
operaciones elementales que se ejecutan en un algoritmo, en función del
mismo.

Dicho de otro modo, se debe buscar una función matemática (conocida) que
modele (o acote) la cantidad de instrucciones ejecutadas en ele algoritmo.

En esta función, lo importante es determinar como aumenta el tiempo de
ejecución en función del tamaño de la entrada de los datos.

Este crecimiento se representa mediante notación asintótica, y facilita la
comparación de funciones.

Notación Asintótica:


T (..) : Tiempo de ejecución del algoritmo
O (..) : Cota superior de complejidad
Ω (..) : Cota inferior de complejidad
Θ (..) : Orden exacto de complejidad



4

las

técnicas generales para

la

Solucion: <Tipo_Solucon>

DISEÑO DE ALGORITMOS

“El Diseño de Algoritmos engloba
construcción de algoritmos”

Podemos citar como ejemplo la técnica “Divide y Vencerás”, en la cual dado
un problema, se descompone en subproblemas de menor tamaño que el
primero, se resuelven los subproblemas y finalmente se combinan las
soluciones parciales.

Algoritmo D_V(p,q : Entero)
Var m: Entero

Inicio



Fin

Si Pequeño(p,q) Entonces

Sino Inicio


Fin
Devolver(Solucion)

m = Dividir(p,q);
Solucion= Combinar(D_V(p,m), D_V(m+1,q))

Solucion= Solucion_Directa(p,q)



5

DESARROLLO DE ALGORITMOS

Cualquier actividad que conlleve un desarrollo esta compuesto por una serie
de pasos que deben cumplirse con el propósito de garantizar objetivos sean
estos de tipo económico, tiempo, calidad, etc.

El proceso clásico para el diseño de algoritmos esta compuesto de:

• Especificación del problema
• Análisis del problema
• Diseño de la solución
• Implementación del diseño
• Pruebas


Además deben ser consideradas algunas normas que permitan la realización de
una buena programación:


• Planificar el diseño de un programa mediante refinamientos sucesivos.
• Encapsular: Extraer y Agrupar funciones relacionadas. Todas las
operaciones sobre un mismo TAD debe estar en el mismo modulo.
Modulo como mecanismo de encapsulación

• Ocultamiento de la implementación: Los aspectos de implementación
no son visibles fuera del modulo. El que usa el modulo solo debe saber
que hace, no como lo hace.

• Reutilizar programas existentes
• No resolver casos concretos, sino que el problema real.
• Repartir uniformemente la funcionalidad y la complejidad.



6

ANALISIS DE ALGORIMTOS

“Un algoritmo es un conjunto finito de reglas que sin ambigüedad efectúan
algún calculo, el cual puede ser realizado en forma manual o por medio de
una maquina”

Existen muchas definiciones, pero todas mantienen la esencia: un conjunto de
pasos (a veces se llaman reglas o acciones), finito, sin ambigüedades y que
conduce a algún resultado.

Antes del siglo XX se trataba de encontrar algoritmos aritméticos, esto
condiciono los esfuerzos en la construcción de maquinas que pudieran seguir
dichos algoritmos.
En la actualidad los algoritmos no solo responden cuestionen aritméticas, sino
que cosas tan dispares como reparar un vehículo o como lavarse los dientes.

RECURSOS QUE REQUIERE UN ALGORITMO
Sabemos que un mismo problema puede ser resuelto de diferentes formas, es
decir aplicando diferentes algoritmos. En este momento surge la pregunta:


¿Cual Utilizo?



7



Es evidente que un algoritmo es mucho mejor si consume menos recursos,
pero no debemos perder de vista el análisis de otros factores antes de
decidirnos por algún algoritmo, podemos mencionar:

a) La facilidad para programarlo
b) La facilidad para entenderlo
c) La robustez
d) El criterio empresarial de la eficiencia, es decir, la relación entre los

recursos consumidos (o invertidos) y los productos conseguidos.

x: Entero);


Consideremos el siguiente algoritmo:

Algoritmo Recursos(Var a: vector[1..n] de <Tipo_Elemento>;
Var i: Entero;
Inicio



Fin

¿Cuántos recursos de tiempo y memoria consume el algoritmo?


i=0;
a[n+1]=x;
repetir

i=i+1;
hasta a[i]=x;
retornar(i);



8

Respuesta:
Depende, de lo que valgan n y x, de lo que contenga a, de los tipos de datos,
de la maquina.

Estos factores los podemos agrupar en dos categorías: Factores Internos y
Factores Externos.

FACTORES INTERNOS

• Tamaño de los datos de entrada
• Naturaleza de los datos de entrada

o Mejor caso: El contenido proporciona la ejecución más rápida.
o Peor caso: El contenido proporciona la ejecución más lenta.
o Caso promedio: Es la media de todos los posibles contenidos.

FACTORES EXTERNOS
El computador donde se ejecute (no es lo mismo un 286 que un Pentium

4 o una Cray)

El lenguaje de programación y el compilador utilizado.
Los factores externos no entregan información sobre el algoritmo.

OPERACIÓN ELEMENTAL
En el análisis de cualquier situación se necesitan medidas que nos permitan
cuantificar la situación, por ejemplo para saber la capacidad de una represa de
agua se utilizan los litros.
Para determinar la eficiencia de un algoritmo ¿Qué unidad podemos utilizar?
Debemos desechar el segundo: pues no es lo mismo un segundo en un
computador con microprocesador 8088 que en un Cray.



9

Como se entiende esto, ya que el tiempo es el mismo para todos: ¿Se ejecutan
el mismo número de operaciones durante un segundo en un computador con
un microprocesador 8088 que en un Cray? Esta es la clave.

La medida que buscamos debe ser independiente de factores externos que no
puedan ser controlados. De esta manera podremos comparar dos algoritmos en
cualquier parte del planeta, de una manera estándar y común a todos los
profesionales de la informática.

A esta nueva unidad que nos permitirá determinar la eficiencia de un
algoritmo la denominaremos OPERACIÓN ELEMENTAL.


La eficiencia de un algoritmo se mide mediante las operaciones elementales,
mas específicamente del numero de operaciones elementales que se deben

ejecutar.


Operación elemental: es aquella operación cuyo tiempo de ejecución se puede
acotar superiormente por una constante que solamente dependerá de la
implementación particular usada: de la maquina, del lenguaje, del compilador,
etc.

Ejemplo de estas operaciones son: suma, resta, multiplicación, asignación,
acceso a arreglos, etc. Aunque en rigor el tiempo de una multiplicación no es
el mismo que el tiempo de la suma, pero difieren en una constante
multiplicativa.



10

PRINCIPIO DE INVARIANZA
Si queremos medi
  • Links de descarga
http://lwp-l.com/pdf17994

Comentarios de: Algoritmo (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad