- Clase de Presentación del Análisis y Diseño de
Algoritmos: caso de estudio el problema abierto de resolver un sistema
de ecuaciones lineales sobre los números reales $Ax=b$ donde $A$ es
una matriz $nxn$, $x,b$ vectores $nx1$. Los casos comentados van de
$n$ de 10 a 100,0000. Concluyendo que para dimensiones grandes los
métodos iterativos son más eficientes que los métodos directos
(triangulación).
- Presentación de los temas del curso. Definición de
complejidad para enmarcar los objetivos del análisis y diseño de
algoritmos. Tabulado de tamaño de la entrada vs tiempo. Crisis de la
virtualización de la memoria RAM. Modelo Cómputo Von Newman moderno
con buses inteligentes.
- Int. al diseño de algoritmos. Modelo de cómputo y
medición y formulación de la relación entre la entrada y el tiempo de
respuesta. Problema manejo de datos: Búsqueda y clasificación.
Fórmulas de series y fórmulas asintóticas.
====================================================
Regreso a clases
- Repaso. Entrega y resolución del examen
rápido.
- Repaso. Resolución del examen
rápido. Algoritmos de búsqueda en un árbol binario balanceado y
ordenado. Algoritmo de búsqueda binaria en un arreglo ordenado.
Complejidad, ventajas y desventajas.
- Algoritmo de ordenamiento. Quick Sort (algoritmo de
desordenamiento d datos, shufle) y Heap Sort. Complejidad, ventajas y
desventajas. Importancia del ordenamiento de datos.
- Introducción a grafos y al problema del agente viajero (Travel
salesman problem). Bases del nuevo algoritmo BB: Curva de Jordan,
2-Coloración, algoritmo de clasificación en coordenadas polares,
construcción por zonas circulares y espirales y eliminación de cruces
de diagonales. El artículo se les envió por correo electrónico.
- Grafos. Caminos y ciclos Eulerianos y Hamiltonenos. Prop. de Euler
sobre Caminos y ciclos Eulerianos (complejidad $n^2$. Complejidad
exhustiva para determinar en general Caminos y ciclos
Hamiltonenos (complejidad combinatoria $n!$). Propiedad de
verificación eficiente y traducción polinomial entre TSp y los NP, TSP
es NP. Grafos completos ($K_n$), bigrafos completos ($K_{nn}$), grafos
planares y Teorema de Kuratuwski. Aplicaciones relacionadas con
grafos.
- Miércoles 29 de mayo. No hay clase. Los alumnos tienen examen de
Teoría de la Computación.
- Viernes 31 de mayo de 2019. Solo Fernando asistió a clase. Se
suspendió la clase y se le manda carta al Coordinador de la MCC con
copia a los alumnos.
- Algoritmos y exploración. Algoritmos eficientes tienen complejidad
polinomial $t^n$ ($n$ pequeña, 3 o menor) o $log_2(t)$ o $t log_2(t)$
donde $t$ tamaño de datos. Complejidad combinatoria $t!$ (fuerza
bruta, exploración exhaustiva) o exponencial $2^t$, problemas
intratables. Algoritmos heurísticos (estrategias glotonas (gredy),
reducibilidad, metáforas (bioinspiradas, artísticas, etc.) Algoritmos
por propiedades matemáticas o computacionales. Tarea 2.
- Trabajo en equipo. Realizar el reporte de la simulación de la
corrida del Algoritmo Genético de Barbosa.
- Viernes 7 de junio. Presentar los resultados del trabajo de la
clase anterior.
|
- Entrega de calificaciones parciales. Transformación de grafos a
árboles. (Algoritmos que usan una estrategia glotona)
Algoritmo BFS.
Árboles de mínimo costo de un grafo.
Algoritmo Kruskal
por ordenamiento de los pesos de aristas,
Algoritmo de
Prim, privilegia vértices.
- Miércoles 12. Trabajo del proyecto de alumnos en clase.
- Viernes 14. Presentación proyecto y correcciones.
- Coloquio.
- Distancia. Descripción del proyecto distancia.
- Material del proyecto de distancia.
Heap sort.
Clusters.
-
Lunes 24 de junio. No hubo clase por asunto médico.
-
Proyecto distancia. Operaciones que no alteran las distancias:
Rotaciones, traslaciones y ordenamientos.
Matrices de rotaciones
(wikipedia).
|
- Lunes 1ro de julio. Flujos en redes. Ver bibliografía.
- Miércoles. Trabajo de alumnos del proyecto.
- Viernes 5 de julio. Trabajo de alumnos del proyecto. Tengo
una cita médica, no asisto al salón de clases.
- Lunes 8 de julio. Explicación de la distancia entre conjuntos pcb. Reporte de avances del proyecto.
Idea surgida de la discusión: Usar proyección 3d a 2D y matrices de
conteo de coincidencias. Uso de arreglos o listas apropiadas para
interpretar matriz de conteo (una entrada de la matriz de conteo solo
puede ser: 2 es un match de partículas de pcb1 y pcb2, 1 es solo una
partícula de pcb1 y pcb2, 0 sin información, 3 o mayor es un error,
partículas repetidas). La proyección usada para graficar por
computadora se obtiene de manuales en OpenGL, Matlab y la teoría en
libros de Geometría proyectiva. Si no se tiene cuidado en suar
arreglos o listas apropiadas, la complejidad de leer la matriz de
conteo es del producto de su resolución (800x800). Mientras que con
arreglos o listas se mantiene la Complejidad en K(n1+n2) donde K es
una constante, n1 y n2 son el número de partículas de los
archivos pcb1 y pcb2 respectivamente. Sugerencia incluir rotaciones y
traslaciones que permitan verificar la distancia resultante de su
algoritmo entre los clusters pcb1 y pcb2.
- Reporte de avances del proyecto.
- Miércoles 10 de julio. Trabajo de los alumnos en clase.
- Viernes 12 de julio. Reporte y preguntas de los avances del proyecto
individual de cada uno de los alumnos.
- Acuerdos: Se presenta y entrega el reporte el lunes 22 de julio,
en el horario de la clase. Asesorías en mi oficina o por correo
electrónico. Evaluación del Proyecto final: 20% resultados, 40%
reporte del proyecto en que consiste y como lo hicieron (2 hojas), 40%
Análisis, diseño del algoritmo y funcionamiento, se entrega la
implementación en Matlab, junto con el análisis de complejidad de sus
algoritmo, y se realizan ejecuciones que demuestren que funciona
correctamente.
|
