Teorias De Grafos En Informatica

2809 palabras 12 páginas
MATEMATICA APLICACIONES DE LA TEORIA DE GRAFOS EN LA INFORMÁTICA
CONTENIDO
Introducción
Proposito
Formulacion del problema y justificacion
Objetivos
Grafos
Historia
Definicion
Tipos de grafos
Modelos de los grafos
Aplicaciones
Arboles
Arbol Binario
Arbol de decision y aplicaciones
Software algoritmos voraces

INTRODUCCIÓN
La teoría de grafos también llamada teoría de las gráficas, es una disciplina que es importante tanto para las matemáticas como para la teoría de la computación. En esta última disciplina todo es manejado a través de los grafos que son estructuras discretas que constan de puntos y de líneas que se conectan entre sí. Es importante saber que existen diferentes tipos de grafos, que se distinguen entre sí
…ver más…
Cada sentencia se representa por un vértice, y hay una arista de un vértice a un segundo si la sentencia representada por el segundo vértice no puede ejecutarse hasta la sentencia representada por el primero se ha ejecutado.
Diseño de bases de datos
Empresa:
Vértices: Empleados, trabajos, departamentos y Empresa.
Enlaces: La comunicación.

APLICACIONES INFORMÁTICAS EN GRAFOS BIPARTITOS
Comparación de archivos de computador, utilizando el problema de la Longest Common Subsequence (LCS), en español Subsecuencia Común Más Larga.
Dadas dos palabras X e Y sobre un alfabeto finito cualquiera, pretende encontrar cuál es el largo máximo que puede tener una palabra que sea subsecuencia de X e Y simultáneamente.
El largo de una LCS se usa comúnmente como criterio de comparación de palabras, pues está relacionada con la cantidad de "pasos" necesarios para ir de una palabra a la otra mediante operaciones de inserción, eliminación y reemplazo de caracteres.
Todopar de palabras puede representarse convenientemente como un grafo bipartito donde los arcos unen a los caracteres coincidentes de ambas palabras.
Un matching en un grafo arbitrario (no necesariamente bipartito) es cualquier conjunto de arcos que no comparten extremos; un PM es un matching en donde los arcos no se cruzan ni comparten extremos. Así, calcular la LCS entre dos palabras no es más que calcular el matching planar de costo máximo del grafo bipartito

Documentos relacionados

  • Aplicación de la informática en la educación
    721 palabras | 3 páginas
  • Investigación de Operaciones en Informatica
    1089 palabras | 5 páginas
  • Aplicación de la informática en diferentes ciencias
    3548 palabras | 15 páginas
  • Aplicaciones de la informatica en la administracion
    932 palabras | 4 páginas
  • Estructuras Y Proyectos En El Contexto De La Informatica
    8794 palabras | 36 páginas
  • Tesis De T.S.U. En Informatica
    10181 palabras | 41 páginas
  • Monografia Teoria de Grafos
    3010 palabras | 13 páginas
  • Reticulados Ordenamiento De Los Elementos Teoría De Grafos
    2247 palabras | 10 páginas
  • Unidades De Medidas En Informaticas
    2686 palabras | 11 páginas
  • Importancia de las mátematicas en la informática
    1188 palabras | 5 páginas