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(n²). Comparar 30 minutos versus 30 ln (30) minutos (= 1 hora 42 minutos) versus 30² 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.