pract1

INSTITUTO TECNOLOGICO SUPERIOR DE SAN MARTIN TEXMELUCAN

NOMBRE DEL ALUMNA:

LOURDES QUIROZ HERNANDEZ

NOMBRE DE LA PROFESORA:

YESENIA

NOMBRE DE LA MATERIA:

TEORIA DE LA COMPUTACION

NOMBRE DEL TEMA:

PRACTICA#1 COMPLEJIDAD COMPUTACIONAL

GARDO Y GRUPO:

4TO  “B”

ANALIZAR MEDIANTE UN LENGUAJE DE ALTO NIVEL, LA COMPLEJIDAD COMPUTACIONAL
	Observaciones

1.-OBJETIVO

Analizar la complejidad de algoritmos y realizar modificaciones que mejoren su desempeño.

2.- MARCO TEÓRICO

Cuando solucionamos un problema mediante la construcción de un algoritmo, normalmente podemos atacar el problema desde distintos puntos de vista, aplicando distintas estrategias, y por tanto, llegando a soluciones algorítmicas distintas.

Desde el punto de vista computacional, es necesario disponer de alguna forma de comparar una solución algorítmica con otra, para conocer cómo se comportarán cuando las implementemos, especialmente al atacar problemas "grandes".

La complejidad algorítmica es una métrica teórica que se aplica a los algoritmos en este sentido. Es un concepto que fundamental para todos los programadores, pero sin embargo, a menudo se desconoce por completo. En muchos cursos y libros se elude el tema porque a menudo se considera farragoso.

Pero eso no es necesariamente cierto. La complejidad de un algoritmo es un concepto complicado pero sólo desde un punto de vista estrictamente formal. La obtención y el estudio de la complejidad de un algoritmo requiere ciertamente de unas cuantas destrezas matemáticas que no todos tenemos y la aplicación de una serie de técnicas bastante particulares. Sin embargo, no es un concepto difícil de entender.

En éste artículo (algo más largo de lo habitual) intentamos ver qué es la complejidad de un algoritmo y cuáles son las situaciones más comunes.

4.- PROCEDIMIENTO

1.- Desarrolle un programa de computadora que maneje 4 tipos de funciones recursivas y que son mostradas en la sección de actividades, datos y resultados.

2.- Genera para cada una de estas funciones una sucesión de al menos 100 números continuos naturales.

3.- mande a imprimir en la pantalla los resultados generados al sustituir esta sucesión de números naturales. 

5.- APARATOS E INSTRUMENTOS

Una PC

Un Lenguaje de alto nivel

Sistema Operativo Windows o Linux

6. ACTIVIDADES, DATOS Y RESULTADOS

Dadas las siguientes expresiones:

1) F(n)= [0                             Si n=0                       

F (n−1)+1      Si n>0] Sumatoria

2) F (n)= [1                Si n=0

F (n−1) ∗n      Si n>0] Factorial

3) F (n)= [0                Si n=0

1                     Si n=1

F (n−1)+F (n−2)                   Si n>1] Fibonacci

4) F (n)= [1                Si n=0

1                     Si n=1

1+F (n−1) ∗F (n−2) Si n>1] “Factoracci (una serie inventada)”

Se pide:

a)    Implemente en el lenguaje de su elección un algoritmo para cada una de las expresiones anteriores, calcule la complejidad del algoritmo implementado, y realice varias corridas para verificar empíricamente la complejidad algorítmica previamente calculada.

Con los resultados de las corridas realice un gráfico que muestre la tasa de crecimiento de cada algoritmo.

b) Optimice cada uno de los algoritmos anteriores. Calcule la eficiencia de la optimización y compare con el gráfico de la versión no optimizada.

CUESTIONARIO

¿Qué diferencias de crecimiento notaste en cada una de las funciones recursivas?

En sus funciones como la suma y resta que nos da a solo un resultado en el último final y las demás van creciendo pero tiene un mismo a parentesco valor

¿Qué pasa cuando hay pocos datos y cuando hay muchos datos?

Cuando hay pocos se ejecuta rápido y nos manda el resultado

Y cuando hay muchos va paso por paso hasta obtener un mismo resultado pero va preguntando si se puede hacer o no

¿Se cumple en todos los casos que en cuanto los datos crecen, la complejidad también crece?

No en todos pero la mayoría si

¿Existe repetición entre los datos, o todos son diferentes para cada una de las sucesiones?

Algunos se repiten como el fibonaci y factorial.

Conclusión:

Mi conclusión es que con el paso de cada resultado nos da un mismo valor y va  comparando hasta que llegue si son iguales o no y se van eligiendo un valor absoluto que sea el correcto como ejemplo 5+1=6 ósea el valor nos va representando hasta que llegue la comparación con todos.

8.-BIBLIOGRAFÍA

Martin, John C.

Introduction to Languages and the Theory of Computation.

Ed. Prentice Hall.

2. Sipser, Michael.

Introduction to the Theory of Computation.

Ed. PWS Publishing Company.

3. Cohen, Daniel I.A.

Introduction to Computer Theory.

Ed. Wie Wiley.

4. Davis, Martín D., Weyuker, Elaine.

Computability, Complexity and Languages Fundamentales of Teorical

Computer Science.

Ed. Academic Press.

5. Denning, Peter J.

Machines, Langueges and Computation.

Ed. Prentice Hall.

6. Hopcroft, John, Ullman, Jeffrey.

Introduction to Automatas Theory, Languages and Computation.

Ed. Addison-Wesley.

7. Kelley, Dean.

Teoría de Automatas y Lenguajes Formales.

Ed. Prentice Hall.

8. Lewis, Larry., Papadimitrion, Chistos H.

Elements of the Theory of Computation.

Ed. Prentice Hall.

9. Rayward-Smith, V.S.

A First Course in a Formal Language Theory.

Ed. Mc Graw Hill.

10. Jeffey E.F. Friedl.

Mastering Regular Expressions.

Ed. O’reilly & Associates, Inc.

11. Brookshear.

Teoría de la Computación, Lenguajes Formales, Autómatas y Complejidad.

Ed. Addison Wesley.

12. Isasi, Martínez y Borrajo.

Lenguajes, Gramáticas y Autómatas.

Ed. Addison Wesley.