Algoritmos 

Tipos abstractos de datos

Una vez que se ha elegido el algoritmo, la implementación puede hacerse usando las estructuras más simples, comunes en casi todos los lenguajes de programación: escalares, arreglos y matrices. Sin embargo algunos problemas se pueden plantear en forma más simple o eficiente en términos de estructuras informáticas más complejas, como listas, pilas, colas, árboles, grafos, conjuntos. Por ejemplo, el TSP se plantea naturalmente en términos de un grafo donde los vértices son las ciudades y las aristas los caminos que van de una ciudad a otra. Estas estructuras están incorporadas en muchos lenguajes de programación o bien pueden obtenerse de librerías. El uso de estas estructuras tiene una serie de ventajas :

- Se ahorra tiempo de programación ya que no es necesario codificar. 

- Estas implementaciones suelen ser eficientes y robustas. 

- Se separan dos capas de código bien diferentes, por una parte el algoritmo que escribe el programador, y por otro las rutinas de acceso a las diferentes estructuras. 

- Existen estimaciones bastante uniformes de los tiempos de ejecución de las diferentes operaciones.

- Las funciones asociadas a cada estructura son relativamente independientes del lenguaje o la implementación en particular. Así, una vez que se plantea un algoritmo en términos de operaciones sobre una tal estructura es fácil implementarlo en una variedad de lenguajes con una performance similar.

              Estructura de Datos              

Introducción básica a grafos

El problema se puede plantear usando una estructura matemática conocida como “grafo”. La base del grafo es un conjunto finito V de puntos llamados “vértices”. La estructura del grafo está dada por las conexiones entre los vértices. Si dos vértices están conectados se dibuja una línea que va desde un vértice al otro. Estas conexiones se llaman “aristas” (“edges”) del grafo. Los vértices pueden identificarse con un número de 0 a nv − 1 donde nv es el número total de vértices. También es usual representarlos gráficamente con un letra a, b, c, ... encerrada en un círculo o usar cualquier etiqueta única relativa al problema. Desde el punto de vista de la teoría de conjuntos un grafo es un subconjunto del conjunto G de pares de vértices. Un par de vértices está en el grafo si existe una arista que los conecta. También puede representarse como una matriz A simétrica de tamaño nv×nv con 0’s y 1’s. Si hay una arista entre el vértice i y el j entonces el elemento Aij es uno, y sino es cero. Además, si existe una arista entre dos vértices i y j entonces decimos que i es “adyacente” a j. 

ESTRUCTURA DE DATOS

Diseño y análisis de algoritmos 

 Conceptos básicos de algoritmos 

No existe una regla precisa para escribir un programa que resuelva un dado problema práctico. Al menos por ahora escribir programas es en gran medida un arte. Sin embargo con el tiempo se han desarrollado un variedad de conceptos que ayudan a desarrollar estrategias para resolver problemas y comparar a priori la eficiencia de las mismas.

Vídeo 1