TAREA DE ALGORITMOS GUILLERMO MARTINEZ 5190-11-12377

¿QUE ES UN ALGRITMO?

En matemáticas, ciencias de la computación y disciplinas relacionadas, 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.

TIPOS DE ALGORITMOS:

Cualitativos:
Son aquellos en los que se describen los pasos utilizando palabras.

Cuantitativos
Son aquellos en los que se utilizan cálculos numéricos para definir los pasos del proceso.

¿EN QUE OTRAS CIENCIAS SE APOYA LA ALGORITMIA?

Ciencias de la computación.

Matemáticas.

Ciencias políticas.

Ciencias sociales.

¿COMO PODEMOS DETERMINAR LA COMPLEJIDAD DE UN ALGORITMO?

Es posible realizar el estudio de la complejidad de un algoritmo solo en base a  un conjunto reducido de sentencias, aquellas caracterizan que el algoritmo sea lento o rápido en el sentido que nos interesa. También es posible distinguir entre los tiempos de ejecución de las diferentes operaciones elementales.

REGLAS PARA EL CÁLCULO DE LA COMPLEJIDAD

DE UN ALGORITMO

1.    El tiempo de ejecución de cada sentencia simple puede tomarse como complejidad de T(1)

2.    Para las sentencias de bifurcación (if, case) el resultante de la complejidad será T(1)

3.    La complejidad para los bucles (for, repeat, while) independientes será T(n)

4.    La complejidad para los bucles anidados será: T(n^m) donde m nos representa el numero de bucles anidados

Ejemplo 1:
El algoritmo a1 tarda n segundos en resolver un problema para una determinada cantidad
de datos mientras que el algoritmo n2 + 400n tarda también un determinado
tiempo en resolver el mismo problema.
Determine cual de los dos algoritmos es más eficiente en base a los datos de entrada

a1		a2
5n2	>=	n2+400n
4n2	>=	400n
n2	>=	100n
n	>=	100
n	<	100	a1 es mejor
n	>=	100	a2 es mejor

Ejemplo 2:
Dado el siguiente algoritmo determine su complejidad

INICIO			T(1)
	Leer a,b,c,sum		T(1)
	if a>3 then b=c*a		T(1)
	desde a=1 hasta b		T(n)
		sum=sum+a	T(1)
	Fin		T(1)
FINAL			T(1)

La complejidad del algoritmo es T(n)