Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Complejidad Computacional

No description
by

edgar hernandez

on 9 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Complejidad Computacional

Complejidad Computacional

Si un problema está en la clase P, se dice que es polinomial y
significa que existe un algoritmo de tiempo polinomial para su solución.

ESPACIO COMPUTACIONAL
La complejidad de espacio de un algoritmo indica la cantidad de
almacenamiento temporal requerido para correr un algoritmo, esto es, el
acceso directo a la memoria de la computadora requerido para representar los
datos necesarios para llevar a cabo el procedimiento.
Formas de almacenamiento
Arrays. Es la estructura más simple, con un número fijo de datos
almacenados en forma ordenada y se accesan por un índice.

COMPLEJIDAD DE LOS PROBLEMAS
La clasificación de la complejidad de los problemas es en cuatro clases
La complejidad computacional estudia la eficiencia de los algoritmos
estableciendo su efectividad de acuerdo al tiempo de corrida y al espacio
requerido en la computadora o almacenamiento de datos, ayudando a evaluar
la viabilidad de la implementación práctica en tiempo y costo.

DEFINICIÓN DE ALGORITMO
Un algoritmo es un procedimiento computacional bien definido, el cual
considera un valor o conjunto de valores como valores de entrada y a través de
una secuencia de instrucciones organizadas produce un valor o conjunto de
valores de salida, en un tiempo determinado con la finalidad de dar solución a
un problema específico.

Las características principales de un algoritmo son:
Preciso y Definido. Cada paso debe ser definido en forma precisa e indicar el
orden de realización.

Problemas Indecidibles.
Son problemas para los cuales no se puede escribir
un algoritmo para su solución, por lo tanto son los problemas de
complejidad más alta.

Problemas Intratables
Son los problemas para los cuales no se puede
desarrollar un algoritmo de tiempo polinomial, únicamente algoritmos
exponenciales.

Problemas NP (Polinomial no determinístico).
Son los problemas para los
cuales la factibilidad del problema utilizando el correspondiente problema de
decisión, puede ser verificada en tiempo polinomial, .
Listas ligadas sencillas
El conjunto de datos está organizado
secuencialmente y para el acceso se requiere información adicional. Los
datos se encuentran en celdas con dos campos: el dato o elemento del
conjunto y la liga.
Listas ligadas dobles.
La diferencia con las listas sencillas es que cada celda
tiene dos ligas, una a la celda predecesora y la otra a la sucesora. Debido a
su estructura permite realizar operaciones en ambas direcciones.
Stacks (pila).
Es una lista ordenada de datos o elementos, la característica
es que los datos se insertan y se eliminan en la parte superior.
Colas
Este tipo de lista tiene la característica de que los datos se insertan
en un extremo y se eliminan en el otro.

Es la estructura más reciente y permite realizar las
operaciones más eficientemente que en d-heaps. Utiliza las propiedades de
los números Fibonacci.

d-heaps.
Este tipo de estructura permite almacenar y manipular un conjunto
de elementos eficientemente y cada elemento tiene asociado un número
real
GRACIAS
Based on Jim Harvey's speech structures
Datos de entrada (input). El algoritmo recibe datos iniciales antes de su
ejecución.
Datos de salida (output). El algoritmo tiene una o más salidas, es decir,
datos que tienen una relación específica respecto a los datos de entrada.
Generalidad. Independientemente de las veces que se siga un algoritmo, se
debe obtener el mismo resultado.
Finito. Un algoritmo debe terminar siempre después de un número finito de
pasos.

PROBLEMAS DE DECISIÓN
Los problemas de decisión son utilizados para la clasificación de la complejidad
de los problemas, y se refieren a una subclase de problemas donde la solución
es un conjunto S = { sí, no } únicamente.


Cada problema de optimización tiene un problema de decisión correspondiente,
por ejemplo para el problema de la ruta más corta,
Problemas P
Los esquemas de almacenamiento y manipulación de datos dentro de la
memoria son indispensables para el desempeño de los algoritmos, haciendo en
ocasiones la diferencia en la elección entre varios algoritmos.

La forma del almacenamiento de datos se relaciona con el tipo de operaciones
que se pueden realizar, porque dependiendo de la manera en que se
almacenen los datos se podrán efectuar cierto tipo de operaciones
Fibonacci heaps.
Edgar Ivan Hernandez Ferruza 179718
Felipe Medina Carrillo
Omar Jimenez Bucio
Michael Giovanni Solís Ramírez 159993
Full transcript