Algoritmos y Complejidad

Contenidos

1- Análisis de la eficiencia de los algoritmos.
Presentación: Repaso de herramientas matemáticas. Problemas e instancias de un problema. Eficiencia. Análisis del caso peor y medio. Algunos ejemplos concretos. Repaso estructuras de datos.
Notación asintótica: “Orden de”. Otras notaciones: Omega, Theta. Operaciones son notaciones asintóticas. Notaciones asintóticas condicionales. Ecuanciones recurrentes asintóticas. La técnica de inducción constructiva.
Resolución de recurrencias por el método de la ecuación característica: Recurrencias homogéneas y no homogéneas. Cambio de variable.

2- Estrategias para la resolución de problemas
Algoritmos voraces (geerdy, ávidos): Introducción. Algoritmos voraces en grafos: árboles de expansión mínimos. Caminos mínimos. Heurísticas voraces.
Divide y vencerás: Introducción. Determinación del umbral. Búsqueda y Ordenamiento. Selección y búsqueda de la mediana. Aritmética de los enteros grandes. Otros problemas.
Programación dinámica: Introducción. Características generales. Problema del camino más corto. Optimización

3- Exploración de grafos
Introducción. Recorrido de árboles. Recorrido en profundidad. Recorrido en anchura. Camino hamiltoneano. Flujo máximo. Circuitos de Euler.

4- Algoritmos probabilistas
Introducción. Algoritmos probabilistas numéricos. Algoritmos de Sherwood. Algoritmos de Las Vegas. Algoritmos de Monte Carlo.

5- Análisis Amortizado
Introducción. Colas binomiales. Montículos sesgados.

6- Complejidad Computacional
Clases de complejidad. Problemas de decisión y lenguaje. Complejidad del tiempo y espacio. Clase P: propiedades, reducibilidad en tiempo polinomial. Clase NP: Lenguaje NP Completos. Teorema de Cook. La conjetura P ? NP.

Profesor: pablo bohoslavsky: pbohosl@uncoma.edu.ar
Ayudante: marcela leiva: marceleiva@hotmail.com

Buenos Aires 1400 - (8300) Neuquén
Tel. +54-299-4490312 al 316 - Fax +54-299-4490313