Inicio arrow Programa

Programa de la asignatura

Image1. Algoritmos
Definición. Características. Complejidad de algoritmos. Notación O grande. Técnicas de análisis de algoritmos. Técnicas para el diseño de algoritmos: recursión, divide & conquer, balanceamiento, programación dinámica, técnica greedy. Rendimiento de un programa. Complejidad de espacio. Complejidad de tiempo. Complejidad de un problema. Introducción a Clases de problemas P y NP, y problemas NP completos.

2. Tipos abstractos de datos básicos
Introducción a las especificaciones formales. Especificación algebraica. El tipo abstracto de datos Pila. El tipo abstracto de datos Fila. El tipo abstracto de datos Lista y Lista Circular. Aplicaciones. Implementación de los tipos de datos básicos con arreglos y con listas enlazadas. Comparación entre implementaciones con variables estáticas y dinámicas. Limitaciones y ventajas

3. Tipos de datos no lineales
Arboles. El tipo abstracto de datos árbol. El tipo abstracto de datos árbol binario. Distintas representaciones. Aplicaciones. Grafos. Definiciones. Grafos no dirigidos y dígrafos. El tipo abstracto de datos grafo. Representación con matriz de adyacencia y con listas de adyacencia. Ciclo euleriano y ciclo hamiltoniano. Recorrido en un grafo: en profundidad y en amplitud. Árbol de recubrimiento mínimo. Algoritmo de Prim. Camino en un grafo, el problema de los caminos mínimos. Algoritmos de Dijkstra, Floyd y Warshall.

4. Ordenamiento
El problema de clasificación. Tiempo de ejecución. Memoria necesaria. Estabilidad. Sensibilidad. Métodos simples: Ordenación por selección, por inserción directa, por intercambio directo. Complejidad de los algoritmos simples. Limitaciones. Métodos mejorados: Ordenación por el método de incrementos decrecientes, Ordenación por el método rápido, Ordenación por mezcla. El tipo abstracto de datos Cola de Prioridad. Montículo. Ordenación por el método del montículo. Método de ordenación por residuos. Análisis de la complejidad de cada método. Comparación de los distintos métodos. Métodos lineales de clasificación para claves particulares. Ordenación externa. Métodos de mezcla.

5. Búsqueda
El tipo abstracto de datos tabla. Técnicas básicas de búsqueda: Búsqueda secuencial, Búsqueda binaria. Búsqueda en árboles binarios: en árboles binarios de búsqueda, en árboles binarios de búsqueda balanceados. Análisis de la altura de cada tipo de árbol y costo de las operaciones. Búsqueda en árboles generales: árboles multivías, árboles B. Algoritmos y complejidad. Dispersión. Funciones de dispersión. Colisión, soluciones.

 
  stilbruch-projekt.de