Conceptos y Motivación
- Hay casos en que no tenemos todo el tiempo del
mundo para llegar una respuesta (Consideraciones de tiempo real).
- El programa de pronóstico del tiempo no debe tomar
más allá del tiempo que estamos pronosticando.
- Ejemplo:
- ¿Cómo podría usted evaluar un
polinomio haciendo uso de sólo una variable y el mínimo
número de sumas y multiplicaciones?
- Algoritmo de ordenamiento:
- ¿Cuántas operaciones debemos hacer para
ordenar n números?
- ¿Podemos hacerlo usando un número de
operaciones proporcional a n?
- Ordenamiento
de Items
- ¿Cómo podemos buscar la mediana de entre un
conjunto de puntos? Aplicación en filtrado de imágenes.
- Hay problemas sin solución conocida en
tiempo polinomial.
- Problema del vendedor Viajero: Se tiene que visitar
ciudades todas interconectadas y se desea hacer un recorrido simple de
distancia mínima.
- Situaciones modeladas con Grafos (conjunto de vertices y
arcos entre ellos). Ejemplo:
- Ruteamiento de líneas en un PCB. Minimizar largo de
líneas, minimizar número de pasadas de una cara a la otra.
- Dada cierta capacidad de tráfico de las calles de
una ciudad, cuál es el flujo máximo de autos que pueden
circular de Valparaíso a Reñaca?
- Algoritmos distribuidos cálculo de ruta
"mínima" desde un origen a un destino en redes de computadores.
- 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.
- Veremos variadas estructuras de datos y
algoritmos, en ocasiones es no trivial 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 PSU?
- ¿Como sé a qué nota
corresponde el 50%?
- Quiero visitar cinco cuidades del sur,
¿Cuál es la mejor ruta para minimizar kilometraje?
- Recorrer los vértices de un sobre
abierto sin levantar el lápiz.
- Resulta ser un camino de Euler: sólo dos vertices
con grado impar y grafo es conexo.
- ¿Cómo hacer tres puntos que representen un
ángulo recto usando una huincha de medir y un lápiz?
- ¿Cómo hacer tres puntos que representen un
ángulo recto usando un compas y un hilo?
- Una cazador toma su arma, sale de casa y recorre 5 km
hacia el sur. Luego camina 5 km hacia el oeste. En ese punto da muerte a
un oso, camina 5 km al norte y llega a casa. ¿De qué
color era el oso?