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

optimizacion de codigos

matematicas discretas II
by

alejandra cruz

on 11 June 2010

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of optimizacion de codigos

NOMBRE:
ALEJANDRA CRUZ SÁNCHEZ.
MATERIA:
MATEMATICAS DISCRETAS.
TEMA:
OPTIMIZACIÓN DE CODIGROS (GRAFOS YO) GRAFOS. Conjunto de nodos unidos por un conjunto de líneas o flechas. NODOS. Son estructuras que contienen algun tipo de información y las líneaso flechas son conexiones entre estas estructuras. GRAFOS DIRIGIDOS. Son cuando las flechas se utilizan para conectar loas nodos, y en caso contrario es un GRAFO NO DIRIGIDO, ambos casos con aristas -FUNCIÓN ARISTA. Ellas tienen algun tipo de información asociada cuyo en cuyo caso estamos en presencia de un grafo pesado, las secuencia de aristas forman ciclos. -CICLO. Es un camino que termina en el mismo nodo donde comenzo (a todo nodo del grafo se llama TOUR. -LONGITUD CAMINO. Es el numero de aristas. -GRAFO DE CONEXO. Es el que se puede llegar desde cualquier nodo hasta cualquier otro mediante un camino lo contrario puede dividirse en componentes conexas (son subconjuntos de nodos y ariatas del grafo original qque son conexos sin ciclo es llamado un arbol. REPRESENTACIÓN EN EL COMPUTADOR. Los grafos pueden representarse estructuras de datos distintas. Los algoritmos que se aplican sobre ellos adoptan tiempos distintos dependiendo de la forma de representación elegida . En particular, los tiempos de ejecución variarán en función del número de vértices y el de aristas, por lo que la utilización de una representación u otra dependerá en gran medida de si el grafo es denso (muchas aristas) o disperso (muy pocas aristas). -REPRESENTACION POR MATRIZ ADYACENTE. La matriz de adyacencia es la forma más común de representación y la más directa.
Consiste en una tabla de tamaño nxn, en que la que aij tendrá como valor 1 si existe una
arista del vértice i al vértice j. En caso contrario, el valor será 0. Si el grafo es no
dirigido hay que asegurarse de que se marca con un 1 tanto la entrada aij como la
entrada aji, puesto que se puede recorrer en ambos sentidos.
Como se puede apreciar, la matriz de adyacencia siempre ocupa un espacio de n2. PROBLEMAS DE PROCESAMIENTO DE UN GRAFO. Obviamente, si el grafo es no dirigido, en la lista enlazada de j aparecerá la correspondiente referencia al vértice i.Una lista de adyacencia consiste de una lista de los vértices del grafo y para cada vértice de una lista de sus vértices vecinos. En el caso de tener varias soluciones y tener que mostrarlas siguiendo un determinado orden. Ante una situación así podría ser conveniente modificar la forma de meter los nodos en la lista de manera que el algoritmo mismo diera las soluciones ya ordenadas. - FACÍLES. - TRATABLES. Es el que se resuelve utilizando un programa eficiente y elegante. su tiempo de ejecución es lineal en el peor caso, o limitado por un polinomio de bajo grado en el número de nodos o el número de aristas. -INTRATABLES. Aquel para el que se conoce un algoritmo que garantiza que sus requerimientos en tiempo y espacio están limitados por una función polinomial en el tamaño del grafo (número de nodos + número de aristas). Aquel para el que no se conoce algoritmo que garantice obtener un solución del problema en una cantidad razonable de tiempo. Esta clase de problemas es extensa y muchos expertos piensan que no existen algoritmos eficientes para solucionar estos problemas. El término NP-hard describe los problemas de esta clase, el cual representa un altísimo nivel dedificultad. Algunos de los problemas más conocidos de procesamiento de grafos son:. -Conectividad Simple: Consiste en estudiasi el grafo es conexo, si existe al menos un camino entre cada par de vértices. -Detección de Ciclos. Consiste en estudiar la existencia de al menos un ciclo en el grafo. - CAMINO SIMPLE. Consiste en estudiar la existencia de un camino entre dos vértices cualquiera. -Camino de Euler: Consiste en estudiar la existencia de un camino que conecte dos vértices dados usando cada arista del grafo exactamente una sola vez. Si el camino tiene como inicio y final el mismo vértice, entonces se desea encontrar un tour de Euler. -Camino de Hamilton: Consiste en estudiar la existencia de un camino que conecte dos vértices dados que visite cada nodo del grafo exactamente una vez. -Conectividad Fuerte en Dígrafos: Consiste en estudiar si hay un camino dirigido conectando cada par de vértices del dígrafo. Inclusive se puede estudiar si existe un camino dirigido entre cada par de vértices, en ambas direcciones. -Clausura Transitiva: Consiste en tratar de encontrar un conjunto de vértices que
pueda ser alcanzado siguiendo aristas dirigidas desde cada vértice del dígrafo. -Árbol de Expansión Mínima: Consiste en encontrar, en un grafo pesado, el conjunto de aristas de peso mínimo que conecta a todos los vértices. -Caminos cortos a partir de un mismo origen: Consiste en encontrar cuales son los caminos más cortos conectando a un vértice v cualquier con cada uno de los
otros vértices de un dígrafo pesado.
-Pareamiento (Matching): Encontrar cual es el subconjunto más largo de sus aristas con las propiedad de que no haya dos conectados al mismo vértice. -Ciclos Pares en Dígrafos: Consiste en encontrar en un dígrafo un camino de
longitud par. -Asignación: Consiste en encontrar un pareamiento perfecto de peso mínimo en un grafo bipartito. -Un grafo bipartito: Es aquel cuyosvértices se pueden separar en dos conjuntos, de tal manera que todas las aristas conecten a un vértice en un conjunto con otro vértice en el otro conjunto. -Conectividad General: Consiste en encontrar el número mínimo de aristas que al ser removidas separarán el grafo en dos partes disjuntas (conectividad de
aristas). -Colorabilidad: Consiste en estudiar si existe alguna manera de asignar k colores
a cada uno de los vértices de un grafo, de tal forma de que ninguna arista
conecte dos vértices del mismo color.
-Conjunto Independiente: Consiste en encontrar el tamaño del mayor subconjunto de nodos de un grafo con la propiedad de que no haya ningún par conectado por una arista.
-Clique: Consiste en encontrar el tamaño del clique (subgrafo completo) más
grande en un grafo dado. -Isomorfismo de grafos: Consiste en estudiar la posibilidad de hacer dos grafos
idénticos con solo renombrar sus nodos. RECORRIDOS DE UN GRAFO.
Consiste básicamente en visitar un nodo del grafo y luego ir visitando los nodos conectados a este. A diferencia un algoritmo de recorrido de otro es, una vez ubicado en un nodoen particular, la forma en que se visitan los nodos conectados a este. Por supuesto, estos algoritmos pueden ser aplicados en grafos dirigidos o no dirigidos. Los dos algoritmos “clásicos” de recorrido de grafos son: El recorrido en profundidad y en anchura. Precisamente por ser “clásicos” se les conoce su orden de complejidad en tiempo y todos los beneficios de aplicarlos.
Recorrido en profundidad. Trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar mas despues se vuelven atras en busca de caminos alternativos y no estudiaron previamente.Una bondad de este algoritmo es que los nodos solo se vistan una vez. implica que se salvan en alguna estructura las aristas que se van recorriendo se obtiene un conjunto de aristas de cubrimiento mínimo del grafo, lo cual se utiliza frecuentemente para reducir la complejidad del grafo cuando la perdida de información de algunas aristas no es importante. Este resultado se conoce como árbol DFS (DFS Tree). RECORRIDO EN ANCHURA. Recorre grafo apartir de un nodo dadoen niveles primero lo que estan a una distanciade un arco sde destancia y así sucesivamente hasta alcanzar todos los nodos que se pudiesen llegar desde el nodod de salida . Una diferencia notable entre el DFS y el BFS es que este ultimo necesita de una estructura auxiliar, que por lo general es una cola, para el almacenamiento de las aristas que se van a visitar durante el recorrido.El siguiente ejemplo ilustra el funcionamiento del algoritmo BFS sobre un grafo de ejemplo. La secuencia de ilustraciones va de izquierda a derecha y de arriba hacia abajo.
Al igual que en el DFS, usando el BFS se puede obtener un conjunto de aristas de
cubrimiento mínimo del grafo, conocido como el árbol (BFS Tree). También puede modificarse fácilmente y utilizarse para resolver problemas
sencillos como los de conectividad simple, detección de ciclos y camino simple.
El BFS es el algoritmo clásico para encontrar el camino más corto entre dos nodos
específicos en un grafo, mientras que DFS nos ofrece muy poca ayuda para esta tarea
debido a que el orden en el que se visitan los nodos no tiene absolutamente ninguna
relación con la longitud de los caminos.
Full transcript