Conceptos y Motivación
- ¿Qué es un Algortimo?
- ¿Qué es una Estructura de datos?
- Impacto en el tiempo de ejecución de un algoritmo: Crecimiento
de funciones O(n), O(n2). Comparar 30 minutos versus 30 ln (30)
minutos (= 1 hora 42 minutos) versus 302 minutos (= 15 horas)
La situación es más crítica aún cuando aumenta
el tamaño del problema.
- Consideraciones de tiempo real. Evaluación de polinomios.
- Algoritmo de ordenamiento
- Algoritmo de ordenamiento en tiempo lineal.
- Algoritmo de orden polinomial
Ordenamiento
de Items
- Problemas P: Son aquellos que poseen solución polinomial.
- Problemas NP: Aquellos cuya solución puede ser verificada en
tiempo Polinomial. Ejemplo: Existe un Ciclo Hamiltoneano para un Grafo? (Aquel
que recorre todos los nodos en un camino simple -sin dobles visitas)
- ¿P=NP? Nadie sabe. Se piensa que no.
- Problemas NP-Completos: Son aquellos cuyo estatus es desconocido. Se
piensa que poseen solución no polinomial. No se ha encontrado solución
polinomial a ninguno de ellos.
- Grafos. Ruteamiento de líneas en un PCB. Minimizar largo de
líneas, minimizar número de pasadas de una cara a la otra.
- Algoritmos distribuidos calculo de ruta "minima" en redes de computadores.
- ¿Cómo podemos buscar la mediana de entre un
conjunto de puntos? Aplicación en filtrado de imágenes.
- En sistemas operativos es importante detectar ciclos de espera.
Si los hay se produce una espera indefinida (deadlock). Se pueden usar grafos
para reconocer ciclos.
- Cuando hay un número de solicitudes de algún recurso
(por ejemplo una sala de clases), cuál es un buen algoritmo para
asignar el recurso y satisfacer el mayor numero de usuarios?
- Veremos variadas estructuras de datos y algoritmos, en ocasiones
no trivial es darse cuenta qué algoritmo resuelve nuestro problema.
Problema: Como reconocemos si una secuencia de paréntesis está
balanceada? Ej.: (())() (()()) Puedo usar un contador simplemente?
Que pasa si hay más tipos de paréntesis ({[]{}})?
- Problemas:
- ¿Cuál es una forma eficiente de ordenar objetos ordenables?
¿Hay algún límite teórico sobre qué tan
rápido puedo hacerlo? ¿Cuál es ese límite?
- ¿Cómo puedo saber qué porcentaje de alumnos
obtuvieron un puntaje mayor que yo en la PAA?
- ¿Como sé a qué nota le corresponde el 50%?
- Quiero visitrar cinco cuidades del sur, ¿Cuál es la
mejor ruta para minimizar kilometraje?
- Problema del vendedor Viajero: Se tiene que visitar ciudades todas
interconectadas y se sea hacer un recorrido simple de distancia mínima.
- Recorrer los vértices de un sobre: Camino de Euler: sólo
dos vertices con grado impar y grafo es conexo.
- ¿Grafo planar? Tarjeta de circuito impresos.