Observaciones y advertencias:
Estas transparencias pueden cambiar un poco antes o después de la clase correspondiente a cada tema.
Las presentaciones NO INCLUYEN las demostraciones que TAMBIEN forman parte del curso y que son dadas en clase. En la mayoría de los casos se incluyen sólo los enunciados de los teoremas. (o sea esto NO es un apunte de la materia!!).
También puede haber algún ejemplo o resultado que se de en clase y no esté las transparencias.
.
1. ALGORITMOS:
Definición de algoritmo. Modelos de computación: modelo RAM, Máquina de Turing. Complejidad, definición, complejidad en el peor caso, en el caso promedio. Algoritmos de tiempo polinomial y no polinomial. Límite inferior. Ejemplo: análisis de algoritmos de ordenamiento. Algoritmos recursivos. Análisis de la complejidad de algoritmos recursivos.
Técnicas de diseño de algoritmos: dividir y conquistar, backtracking, algoritmos golosos, programación dinámica.
Algoritmos probabilísticos. Algoritmos aproximados Algoritmos heurísticos: ejemplos. Metaheurísticas. Nociones de evaluación de heurísticas.
2. GRAFOS:
Definiciones básicas. Adyacencia, grado de un nodo, isomorfismos, caminos, conexión, etc. Grafos eulerianos y hamiltonianos. Grafos bipartitos. Arboles: caracterización, árboles orientados, árbol generador. Enumeración. Planaridad. Coloreo. Número cromático. Matching, conjunto independiente, recubrimiento. Recubrimiento de aristas y vértices.
3. ALGORITMOS EN GRAFOS Y APLICACIONES:
Representación de un grafo en la computadora: matrices de incidencia y adyacencia, listas.
Algoritmos de búsqueda en grafos: BFS, DFS, A*. Mínimo árbol generador, algoritmos de Prim y Kruskal. Arboles ordenados: códigos unívocamente descifrables. Algoritmos para detección de circuitos. Algoritmos para encontrar el camino mínimo en un grafo: Dijkstra, Ford, Floyd, Dantzig. Planificación de procesos: PERT/CPM.
. Heurísticas para el problema del viajante de comercio. Algoritmos para determinar si un grafo es planar. Algoritmos para coloreo de grafos.
Algoritmos para encontrar el flujo máximo en una red: Ford y Fulkerson. Matching: algoritmos para correspondencias máximas en grafos bipartitos. Otras aplicaciones.
4. PROBLEMAS NP-COMPLETOS:
Problemas tratables e intratables. Problemas de decisión. P y NP. Maquinas de Turing no determinísticas. Problemas NP-completos. Relación entre P y NP. Problemas de grafos NP-completos: coloreo de grafos, grafos hamiltonianos, recubrimiento mínimo de las aristas, corte máximo, etc.
BIBLIOGRAFÍA BÁSICA :
Brassard,G., Bratley,P."Fundamental of Algorithmics", Prentice Hall,1996.
Cormen, T.,Leiserson, C.,Rivest,R.,Stein, C.,"Introduction to Algorithms", The MIT Press, McGraw-Hill,2001.
Garey M.R. and Johnson D.S.: "Computers and intractability: a guide to the theory of NP- Completeness", W. Freeman and Co., 1979.
Gross,J., and Yellen, J. ,"Graph theory and its applications", CRC, 1999
Harary F., "Graph theory", Addison-Wesley, 1969.
BIBLIOGRAFÍA DE CONSULTA : ver en la página WEB de la materia y en el el archivo de las prácticas.
ALGORITMOS
Qué es un algoritmo ?
Qué es un buen algoritmo?
Dados dos algoritmos para resolver un mismo problema, cuál es mejor?
Cuándo un problema está bien resuelto?
Cómo se hace para inventar un nuevo algoritmo?
Qué es un algoritmo?
Noción "informal":
Un algoritmo es una sucesión finita de instrucciones "bien definidas" tal que:
i) No hay ambigüedad en las instrucciones.
ii) Después de ejecutar una instrucción no hay ambigüedad respecto de cual es la instrucción que debe ejecutarse a continuación.
iii) Después de un número finito de instrucciones ejecutadas se llega siempre a la instrucción STOP ("Un algoritmo siempre para").
PROBLEMA
instancia de un problema
datos de entrada de una instancia (E)
solución (S)
ALGORITMO:
técnica para la resolución de un problema
función f tal que f (E) = S
Problema de Collatz
Paso 1: z número entero positivo
Paso 2: mientras z ? 1 hacer
Paso 3: Si z es par poner z = : z / 2
En caso contrario poner z =: 3 z +1
Paso 4: parar
=====================================
es esto un algoritmo?
Cuánto tarda un algoritmo en resolver un problema?
Cuándo un algoritmo que resuelve un problema es mejor que otro que resuelve el mismo problema?
Complejidad Computacional
Complejidad
La complejidad de un algoritmo es una función que calcula el tiempo de ejecución en función del tamaño de la entrada de un problema.
Complejidad en el peor caso (es siempre significativo el peor caso?)
Complejidad en el caso promedio (porqué no usamos este enfoque siempre?)
Cómo medir el tiempo de ejecución en función del tamaño de la entrada de los datos del problema?
MODELOS DE COMPUTACION
RAM
MAQUINA DE TURING
Maquina RAM (RANDOM ACCESS MACHINE)
Es el modelo que usamos implícitamente en la práctica para evaluar la complejidad de un algoritmo.
==================================================
unidad de memoria
unidad de entrada
procesador (programa)
unidad de salida
conjunto de instrucciones
====================================================
Un programa RAM es una secuencia finita de estas instrucciones
Página siguiente  |