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

Herramientas y Técnicas de Diseño de Algoritmos

No description
by

maría del mar garcía

on 18 October 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Herramientas y Técnicas de Diseño de Algoritmos

HERRAMIENTAS
Y TÉCNICAS DE
DISEÑO DE
ALGORITMOS Se define como una serie
de pasos organizados Cuantitativos Cualitativos Herramientas
para el
Diseño Diagrama de flujo Diagrama N-S
(Nassi Schneiderman) A L G O R I T M O Que describe el proceso a seguir para solucionar un problema específico EJEMPLO CUALITATIVO:
Pasos para ver una película en cine. IR AL CINE HACER LA FILA PARA COMPRAR LA BOLETA ENTRAR AL CINE VER LA PELICULA SALIR DEL CINE EJEMPLO CUANTITATIVO: DESCRIBIR LOS PASOS PARA SUMAR DOS NUMEROS

DAR EL RESULTADO DE LA OPERACION ANTERIOR SOLICITAR LOS NUMEROS QUE SE VA A SUMAR TOMAR EL PRIMER NUMERO Y A ESTE SUMARLE EL SEGUNDO Pseudocódigo Técnicas de diseño ALGORITMOS ÁVIDOS Los algoritmos ávidos son algoritmos en los que tomamos decisiones locales para llegar a una cantidad óptima global. para resolver un problema mediante un algoritmo ávido, sólo tomamos la solución óptima del subproblema anterior y con esto calculamos la óptima actual Paso
sencillo Luego decisón más eficiente. DIVIDE Y VENCERÁS combina la descripción textual, propia del pseudocódigo, con la representación gráfica del diagrama de flujo Representa la solución a un algoritmo muy detalladamente y a su vez lo más parecida posible al lenguaje que se utilizara para la codificación del mismo. la representación grafica de las distintas operaciones que se tienen que realizar para resolver un problema Descompone el problema original en varios sub- problemas más sencillos. Se combinan los resultados de cada sub-problema para obtener la solución del problema original. PARALELO puede ser ejecutado por partes en el mismo instante de tiempo por varias unidades de procesamiento. es más rápido tratar grandes tareas de computación mediante la paralelización que mediante técnicas secuenciales Ejemplo una algoritmo que clacule todos los número primos entre 1 y 100. se podría dividir los números originales en subconjuntos y calcular los primos para cada uno de los subconjuntos de los números originales. PROBABILÍSTICO Deja al azar la toma de algunas decisiones Cuando la decisión óptima llevaría mucho tiempo.
Problemas con múltiples soluciones correctas Soluciones erróneas Algoritmos Numericos 1 2 3 4 5 Algoritmos de Montecarlo Algoritmo No dan respuesta incorrecta. respuesta concreta pero ésta no tiene por qué ser correcta para los que es imposible dar una respuesta exacta DETERMINÍSTICO es completamente predictivo si se conocen sus entradas el más práctico ya que puede ejecutarse en las máquinas eficientemente. Un modelo simple de algoritmo determinista es la función matemática NO DETERMINÍSTICO con la misma entrada ofrece muchos posibles resultados No se sabe cuál será el resultado METAHEURÍSTICA Algoritmos aproximados de optimización y búsqueda de propósito general mejoran la eficiencia de los algoritmos de búsqueda reduciendo el factor de ramificación un conjunto de reglas que evalúan la posibilidad de que una búsqueda va en la dirección correcta Ejemplo: Hombre en una colina se aplica a problemas que no tienen un algoritmo o heurística específica que dé una solución satisfactoria o bien cuando no es posible implementar ese método óptimo PROGRAMACIÓN DINÁMICA Ejemplo:
Camino más corto entre 2 vértices de un grafo. resuelve cada subproblema una sola vez y guarda su respuesta en una tabla, evitando así volver a calcular la respuesta Enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. RAMIFICACIÓN Y ACOTACIÓN se suele interpretar como un árbol de soluciones Para cada problema será necesario especificar cada uno de los componentes que caracterizan un problema de programación dinámica. Almacena los resultados en Tablas Como Divide y Vencerás Cada rama nos lleva a una posible solución posterior. se encarga de detectar en qué ramificación las soluciones dadas ya no están siendo óptimas. Luego poda esa rama del árbol y no continua malgastando recursos y procesos VUELTA ATRÁS Recorrer el espacio completo de las soluciones posibles al problema planteado Recorrido en profundidad dentro de un grafo dirigido Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido GRACIAS!!
Full transcript