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

PARTE I: Diseño de Algoritmos y Estructuras de Datos

Clasificación de las técnicas de diseño de algoritmos y estructuras de datos fundamentales
by

Lidia López

on 20 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of PARTE I: Diseño de Algoritmos y Estructuras de Datos

Tipos de Problemas
Ordenamiento
Insertion Sort, Selection Sort, Bubble Sort, MergeSort, HeapSort, QuickSort, ...
Búsqueda
Lineal, Binaria, árboles de búsqueda, hashing, ...
Procesamiento de cadenas
String matching (semantic web applications)...
Exploración de grafos
En profundidad, por niveles, árboles de cubrimiento mínimo, flujo máximo, ...
Problemas Combinatorios
Combinaciones, permutaciones, conjuntos y subconjuntos, coloreados, ...
Geometría Computacional
Par de puntos más cercanos, convex hull, triangulación, ...
Algoritmos numéricos
Euclides, primalidad, aritmética modular, ...
Tipos importantes
" Indeed, I believe that every important aspect of programming arises somewhere in the context of sorting or searching" Knuth, D.E., The Art of Computer Programming, Volume 3, 1986
Estructuras de Datos
Listas
Pila
Conjuntos y Diccionarios
Cola
Grafos
Árboles
Lista enlazada simple
Lista enlazada doble
Arreglos
Cadenas
Cola de prioridad
Dirigido
No dirigido
Lista de
adyacencia
Representación
Matriz de adyacencia
Grafos etiquetados
o con peso
Caminos y Ciclos
Un árbol es un grafo acíclico conectado.
Un grafo que no tiene ciclos y no está necesariamente conectado es una foresta.
Un nodo arbitrario es considerado la raíz. Términos: Antecesor, Predecesor. Hermanos. Padre e hijo. Hoja. Subárbol.
Profundidad de un nodo. Altura del árbol
Árbol binario de búsqueda (lista enlazada)
"While control structures serve to tell the processor where it should be going, data structures, and the operations upon them, organize the data items in ways that enable it to do whatever it should do when it gets there." Harel, The Spirits of Computing. 2004
Diccionario: Estructura de datos para almacenar un conjunto sobre el cual se puede buscar, agregar, o eliminar un ítem de conjunto.
Su implementación debe ser eficiente y se realiza con hashing o árboles de búsqueda balanceados.
La representación de un conjunto de datos se puede hacer a partir de un arreglo o de listas enlazadas
Estructuras de Datos Avanzadas
Montículos - Particiones
Técnicas de
Diseño de Algoritmos

Fuerza Bruta
Divide-y-vencerás
-Divide antes de procesar
Merge Sort
Multiplicación de matrices de Strassen
Multiplicación de enteros grandes
Recorrido de árboles binarios
Par de puntos más cercanos

-Procesa antes de dividir
QuickSort
Convex Hull
Disminuye-y-vencerás
-Disminuye por una constante
Insertion Sort
Orden topológico
Algoritmos para generar objetos combinatorios
Transforma-y-vencerás
-Simplificación
Pre-ordenamiento
Eliminación de Gauss
Árboles AVL, 2-3
-Cambio de representación
Regla de Horner
Exponenciación binaria
-Reducción del problema
Cálculo del múltiplo común menor
Caminos en un grafo
Reducción de problemas de optimización
Programación lineal
Reducción a problemas de grafos
Técnicas generales
Técnicas de búsqueda local
-Método voraz
Problema del cambio
Algoritmo de kruskal y de Prim
Algoritmo de Dijsktra
Códigos y árboles de Huffman
Técnicas árboles espacio-estado
-Vuelta-atrás
Problema de las n-reinas
Circuito Hamiltoniano
Suma de Subconjuntos

-Ramificación-y-poda
Problema de asignación
Problema de la mochila
Problema del viajante
Programación dinámica
Técnicas especiales
“First, the study of these techniques leads to an organized way to devise algorithms... Second, it helps us to categorize the algorithms we know and in that way to understand them better.” Horowitz Encyclopedia of Computer Science, 3rd edition, 1993
La búsqueda por fuerza bruta, búsqueda combinatoria, búsqueda exhaustiva o simplemente fuerza bruta, es una técnica trivial pero a menudo usada, que consiste en procesar sistemáticamente todos los posibles candidatos para la solución de un problema, con el fin de chequear si dicho candidato satisface la solución al mismo.
Selection Sort
Bubble Sort
Búsqueda Secuencial
Es considerado por algunos autores como un caso especial de divide-y-vencerás. La diferencia fundamental entre los dos radica en el número de subproblemas más pequeños que necesitan ser resueltos:
varios (por lo general, dos) en algoritmos divide-y-vencerás y sólo uno en los algoritmos de disminuye-y-vencerás.
Corresponde a la reducción recursiva del problema dado a una instancia más pequeña para luego extender la solución obtenida y así alcanzar la solución de la instancia original.
-Disminuye por un factor constante
Búsqueda binaria
Problema de la falsa moneda
Multiplicación rusa
Problema de Josephus
-Tamaño variable de disminución
Algoritmo de Euclides
Problema de selección y mediana
Búsqueda interpolada
Búsqueda e inserción en un árbol de búsqueda binario
Juego de Nim
3 variaciones
Se basa en la partición de un problema en varios subproblemas
más pequeños (por lo general de la misma clase e idealmente de aproximadamente el mismo tamaño). La solución se obtiene resolviendo cada uno de los subproblemas en forma recursiva, y luego combinando estas soluciones parciales independientes para obtener la solución al problema original.
Esta técnica agrupa métodos de diseño que se basan en la idea de transformación. Es decir, primero la instancia del problema es transformada de manera que facilite su tratamiento, y luego se resuelve.
instancia del problema

instancia más simple
u
otra representación
u
otra instancia de un problema diferente
solución
Agrupa las técnicas de diseño más utilizadas
El problema de la mochila y funciones de memoria.
Árboles de búsqueda binaria óptimos
Algoritmos de Floyd y de Warshall
Los algoritmos voraces son algoritmos que toman decisiones de corto alcance, basadas en información inmediatamente disponible, sin importar consecuencias futuras.
El método de mejora iterativa funciona a partir de encontrar una primera solución relativamente fácil. Esta solución se puede mejorar por una secuencia de cambios pequeños. Se termina cuando no se pueden hacer más mejoras.
Es un problema de optimización, busca minimizar o maximizar algún valor (costo / beneficio).
Se refiere al tratamiento de problemas de optimización. Se consideran dos métodos: el voraz que construye la solución pieza por pieza buscando alcanzar la solución y la mejora iterativa que comienza con una posible solución que va mejorando a través de aplicaciones repetidas de un paso simple.
-Mejora iterativa
Método Simplex
Problema del flujo máximo
Problema del matrimonio estable
Programación Dinámica (PD), al igual que DyV, resuelve problemas a través de combinar soluciones a subproblemas. La diferencia está en que DyV resuelve los subproblemas recursivamente en forma independiente, y luego combina sus soluciones por el contrario, PD se aplica cuando los subproblemas no son independientes entre sí, es decir los subproblemas tienen subsubproblemas en común.

En este contexto DyV resolvería varias veces el mismo subproblema. En PD se resuelve cada subproblema una vez y se guarda su resultado en una tabla, evitando el trabajo de calcularlo otra vez.
Los árboles estado-espacio se consideran las configuraciones o estados sucesivos de una instancia, con el objeto de encontrar un estado con una propiedad deseada.

Los problemas a menudo se modelan como un espacio de estados. El conjunto de estados forma un grafo donde dos estados están conectados si existe una operación que se puede realizar para transformar el primer estado en el segundo.
Agrupa las técnicas menos usadas
"Two ideas lie gleaming on the jeweler's velvet. The first is the calculus, the second, the algorithm. The calculus and the rich body of mathematical analysis to which it gave rise made modern science possible; but it has been the algorithm that has made possible the modern world." David Berlinski, The Advent of the Algorithm, 2000
Full transcript