ALGORITMOS AVANZADOS

INTRODUCCIN
En la presente investigacin se har
mencin de los diferentes tipos de
conceptos de los temas que tienen
relacin con la materia de algoritmos
avanzados, con el propsito de poder
tener una idea de la importancia de
los algoritmos y as poder saber cul
es la importancia y su funcin.
Definiciones de algoritmo
1.- Se define como una serie de
pasos organizados que describen el
proceso que se debe seguir, para dar
solucin a un problema especfico.
[1].
2.- Un Algoritmo, se puede definir
como una secuencia de instrucciones
que representan un modelo de
solucin para determinado tipo de
problemas. O bien como un conjunto
de instrucciones que realizadas en
orden conducen a obtener la solucin
de un problema. Por lo tanto
podemos decir que es un conjunto
ordenado y finito de pasos que nos
permite solucionar un problema. [2].

3.- Se denomina algoritmo a un grupo
finito de operaciones organizadas de
manera lgica y ordenada que
permite solucionar un determinado
problema. Se trata de una serie de
instrucciones o reglas establecidas
que, por medio de una sucesin de
pasos, permiten arribar a un resultado
o solucin [3].
I. Notacin asinttica
Ahora bien, la eficiencia de un
algoritmo se acostumbra a expresar
como una funcin del tamao de la
entrada: Si estamos en una
habitacin con 100 puertas y detrs
de cada una de ellas hay un nmero,
el algoritmo para encontrar el mnimo
de esos nmeros tardar 100
operaciones de abrir puerta y leer
nmero en finalizar. Si, por el
contrario, hubiese 100.000 puertas
tardara, como es obvio, 1.000 veces
ms que antes.
As, en general, podemos decir que el
algoritmo que consiste en abrir las
puertas una por una y leer el nmero
(memorizando siempre cual es el
mnimo de los ledos hasta ahora) es
un algoritmo que realiza un nmero
de operaciones directamente
proporcional al nmero de puertas.
Esto puede expresarse de manera
compacta diciendo que es un
algoritmo O(n) donde n es el nmero
de puertas y la O() implica
proporcionalidad directa.
II. Tiempo de ejecucin
Se denomina tiempo de ejecucin al
intervalo de tiempo en el que un
programa de computadora se ejecuta
en un sistema operativo. Este tiempo
se inicia con la puesta en memoria
principal del programa, por lo que el
sistema operativo comienza a
ejecutar sus instrucciones. El
intervalo finaliza en el momento en
que ste enva al sistema operativo la
seal de terminacin, sea sta una
terminacin normal, en que el
programa tuvo la posibilidad de
concluir sus instrucciones
satisfactoriamente, o una terminacin
ALGORITMOS AVANZADOS

anormal, en el que el programa
produjo algn error y el sistema debi
forzar su finalizacin [5].
III. Calculo de tiempo de ejecucion
Calcular el tiempo de ejecucin de un
algoritmo puede ser, o muy sencillo
una complicada tarea intelectual. En
muchos casos este tipo de anlisis es
un problema matemtico complejo.
En la practica aplicaremos unos
cuantos principios bsicos que
permitan una aproximacin a la
complejidad de una algoritmo dado.
Igualmente, y a efectos de
simplificacin, se considerar como
nico factor del que depende el
tiempo de ejecucin, el tamao de la
muestra de entrada: n.
1. El tiempo de ejecucin
de cada proposicin de
asignacin (lectura y
escritura) se considera
constante: O(1). Como
excepcin a este caso
estn las asignaciones
complejas a matrices o
aquellas en las que esta
implicada una llamada a
una funcin o
procedimiento.
2. Un algoritmo se analiza
de dentro hacia fuera.
Primero se determina el
tiempo o coste de las
proposiciones
individuales, que suele
estar acotado por una
constante, para
posteriormente combinar
estos tiempos de acuerdo
a las estructuras de
control que enlazan las
proposiciones.
3. Regla de composicin
secuencial:
El tiempo de ejecucin de
una secuencia de
proposiciones, la
determina la regala de la
suma, esto es: el tiempo
de ejecucin de una
secuencia es el mximo
del tiempo de ejecucin
de las proposiciones de la
secuencia.
4. El tiempo de ejecucin
de una proposicin
condicional es el costo de
las proposiciones que se
ejecutan
condicionalmente, ms el
tiempo de evaluar la
condicin (normalmente
O(1)).
5. El tiempo de ejecucin
de un ciclo for (para o
desde), es el coste de la
secuencia de
proposiciones por el
nmero de iteraciones. El
problema radica en
conocer el nmero de
iteraciones, aunque es
razonable pensar en el
peor caso y considerar el
mximo posible.
6. Si existe ciclos for anidados,
se realiza el anlisis de
adentro hacia fuera,
considerando el tiempo de
ejecucin de un ciclo interior
y la suma del resto de
proposiciones como el
ALGORITMOS AVANZADOS

tiempo de ejecucin de una
iteracin del ciclo exterior.
7. El tiempo de ejecucin
de un condicional mltiple
(if-then-else, swicth,...) es
el tiempo necesario para
evaluar la condicin, ms
el mayor de los tiempos
de las secuencias a
ejecutar en cada valor
condicional.
8. El tiempo de ejecutar un
ciclo es la suma, sobre
todas las iteraciones del
ciclo, del tiempo de
ejecucin del cuerpo ms
el tiempo para evaluar la
condicin que cierra el
ciclo. En la mayor parte
de los casos este tiempo
es el producto del numero
de iteraciones del ciclo
por el tiempo de
ejecucin del ciclo. El
problema surge en el
hecho de que, a priori, es
difcil evaluar el numero
de iteraciones del ciclo.
Se han de recordar, aqu, algunas
reglas del manejo de la notacin
asinttica:
1. Regla de la suma:
Si T
1
(n) y T2(n) son las
funciones que expresan los
tiempos de ejecucin de dos
fragmentos de programa que
se acotan de forma que se
tiene T
1
(n)=O(f(n)) y
T
2
(n)=O(g(n)), se puede
decir que
T
1
(n) +
T
2
(n)=O(max(f(n),g(n))).
2. Regla del producto:
Si T
1
(n) y T
2
(n) son las
funciones que expresan los
tiempos de ejecucin de dos
fragmentos de programa, y
se acotan de forma que se
tiene T
1
(n)=O(f(n)) y
T
2
(n)=O(g(n)), se puede
decir que
T
1
(n)T
2
(n)=O(f(n),g(n)).
IV. recursividad

La recursividad es un
comportamiento presente en la
misma naturaleza de muchos
problemas para los que buscamos
soluciones informticas
La recursividad es una herramienta
de diseo de algoritmos aceptada en
la mayora de los lenguajes de
programacin. Esos lenguajes
permiten la creacin de un
procedimiento o funcin que hace
referencia a s mismo dentro de la
propia definicin. Eso supone que al
invocar a una funcin recursiva, sta
genera a su vez una o varias nuevas
llamadas a ella misma, cada una de
las cuales genera a su vez una o
varias llamadas a la misma funcin, y
as sucesivamente. Si la definicin
est bien hecha, y los parmetros de
entrada son adecuados, la cadena de
invocaciones termina felizmente en
alguna o varias llamadas que no
generan nuevas invocaciones. Esas
llamadas finales terminan su
ejecucin y devuelven el control a la
llamada anterior, que finaliza su
ejecucin y devuelve el control a la
llamada anterior, y as retornando el
camino de llamadas emprendido, se
ALGORITMOS AVANZADOS

llega a la llamada inicial y se termina
el proceso.

Conclusin.

Podemos concluir y comprender los
conceptos importantes que tienen
relacin con algoritmos, los
significados de cada concepto de la
unidad y cumpliendo con el objetivo
que es dar a entender la importancia
de llevar acabo algoritmos.

Bibliografa.

[1]http://www.virtual.unal.edu.co/curso
s/sedes/manizales/4060024/Leccione
s/Capitulo%20I/conceptos.htm
[2]http://informaticafrida.blogspot.mx/
2009/03/algoritmo.html
[3] Algoritmo y estructura de datos
With Niclaw; Persin Education

[4]http://blog.pseudolog.com/article/efi
ciencia-algoritmica-y-notacion-
asintotica
[5]http://es.wikipedia.org/wiki/Tiempo_
de_ejecuci%C3%B3n
[6]http://www.infor.uva.es/~jmrr/tad20
01/TAD2001020TEjecucion.htm