- Presentación de la UEA y del contenido sintético
con ejemplos: Introducción al análisi de algoritmos. 2. Recursión. 3.
Algoritmos de exploración. 4. Árboles generadores mínimos. 5.
Distancia. 6 Flujo de redes. (Asistencia completa 2 de 2).
- Introducción al análisis y diseño de algoritmo. Modelo
computracional RAM (mod. Von Newman). Conceptos básicos: estado e
instrucción, bajo el modelo de verificación de programas: pre-condición;
instrucción (cambio o efecto) post-condición. Tipos de instrucciones:
entrada, salida, asignación, si-entonces, si-entonces-sino, control de
ciclos: para, mientras y repite; subprogramas. Primer ejemplo para
análisis: Algoritmo de ordenamiento por burbuja.
- Acuerdos: Forma de
evaluación: Exámenes * 70% y Tareas o proyectos * 40%. El horario de
asesoría es el publicado. Análisis de complejidad: cálculo asintótico
de los pasos de ejecución del algoritmo combinado con casos de datos:
mejor, promedio y peor. Para el algoritmo de burbuja el mejor es que
los datos estén ordenados: complejidad $n$, el peor caso es la lista
invertida: complejidad: $n^2$ (corresponde a $n(n+1)/2$). El caso
promedio tiene complejidad intermedia entre $n$ y $n^2$.
Programas Matlab del
algoritmo de burbuja.
- Complejidad notación $\Theta(g(n))$, $O(g(n))$, $\Omega(G(n)).$
Prop. $f(n)$= $\Theta(g(n))$ si y solo si $f(n))$ $=$ $O(g(n))$ y $f(n))$
$=$ $\Omega(G(n))$. Comprobación de que la complejidad del algoritmo
de burbuja es $\sum_{i=1}^n i$ $=$ $n(n+1)/2$ Por principio de
inducción matemática. Verificación que $n(n+1)/2$ $=$ $\Theta(n^2)$.
Algoritmo de búsqueda en un árbol ordenado y balanceado. La
complejidad en el peor caso, i.e, localizar las hojas, es la áltura
del árbol, por tanto es $log_2 (n)$. La complejidad de búsqueda de
datos en un arreglo desordenado o en un árbol degenerado es $n$.
Lograr complejidad $log_2(n)$ es usar estrategias para dividir un
problema en dos subproblemas de medio tamaño o cuando ya se tienen
datos estructurados apropiadamente. La complejidad $n$ es un ideal de
resolver un problema desconocido. Formato de tareas de investigación:
1) Introducción: descripción del problema e información relevante. 2)
Desarrollo: análisis del algoritmo, describir como se obtiene la
fórmula, ubicar su complejidad $\Theta$, $O$ o $\Omega$. 3)
Experimentación numérica: datos y resultados de los experimentos
(tablas y gráficos). 4) Conclusiones.
- Se realizo un ejercicio de diseño de algoritmos
para búsqueda en un arreglo de datos ordenados de menor a mayor. Se
aplicaron las estrategias de divide y vencerás, uso de recursión y
estructura complejas (árbol) versus estructura simple arreglo o vector
de datos. Los alumnos realizaron un algoritmo que descartaron por
ineficiente $\Theta(n)$. Diseñaron por similitud con el algoritmo de
búsqueda en un árbol balanceado y ordenado, el famoso algoritmo de
búsqueda binaria sobre un arreglo. Comprobaron que la complejidad es
$\Theta(log_2(n))$ y observaron que la eficiencia no está ceñida a una
estructura de datos particular. Se discutío que el gran o problema
marco que estamos analizando es el de ordenamiento y localización de
datos. Del cual la búsqueda de datos es un subproblema. La complejidad
de búsqueda es hasta esté momento $\Theta(log_2(n))$. Para
ordenamiento de datos se estudiara el quick sort con complejidad $\Theta(nlog_2(n))$
y se explorará la posibilidad de mejorar la eficiencia para casos de
datos adecuados basados en llaves o claves de acceso como la matrícula
de un alumno o de un auto.
- Se revisa la complejidad de la búsqueda binaria.
Se enlistan puntos relevantes del diseño de algoritmos. Se realiza una
comparación en consumo de memoria y costo de manejo de información
para arreglo ordenado y árbol ordenado y balanceado. El costo de
memoria de un árbol es $n \cdot K \cdot L$, donde $n$ número de datos,
$K$ tamaño del dato, $L$ es 2 tamaño de un apuntador entero de
memoria. Costo arreglo $n \cdot K$. Complejidad borrado o inserción de
$m$ datos en peor de los casos para un árbol $ m*6$, $\Theta(m)$.
Complejidad borrado o inserción de $m$ datos en peor de los casos en
un arreglo $n(n+1)/2-(n-m)(n-m+1)/2$, $\Theta(n^2)$. Propuesta de
proyecto curso: Plataforma de manejo y búsqueda de datos y objetos.
Programas Matlab de captura
de imágenes para proyecto del curso para usar de entrada de datos
para identificación de objetos en un ambiente restringido y
controlado.
- Diseño de algoritmos. Tema Recursión.
Revisar y explicar lo programas de
búsqueda en una arreglo,
búsqueda en un
árbol binario y ordenamiento de datos:
quick sort (viejo y nuevo).
El alumno debe explicar el uso de la recursión en el diseño y
análisis de la complejidad y los problemas que puede tener en la
ejecución. En particular debe estudiar los efecto de la modificación
qSort: viejo y
nuevo. Explicar el
efecto en el proceso de ordenamiento usando la rutina
revolver.
- Recursión, diseño y complejidad. Ejemplo de un programa de
ordenamiento: heap Sort,
robusto y eficiente (no falla como quick Sort con un pivote y datos
repetidos. No falla con lista invertida, con la rutina revolver se
resuelve este fallo de quick sort un pivote y dos pivotes.)
- Exploración. Ejemplos de algoritmos de complejidad $n$ , $nlog_2(n)$,
$n^2$, $n^3$. Complejidad polinomial, combinatoria y exponencial
(tratable e intratable).
- Lunes 8 octubre. Se suspende la clase.
- Modelación: identificación del espacio de estados
$\Omega$, construcción de las instancias de $\Omega$, construcción de
la función objetivo y criterios de aceptación de soluciones.
Programación dinámica, estrategias: fuerza bruta y glotona. Ejemplos:
Código de Huffman para resolver el problema de guardar información
mediante un código que minimiza el espacio de almacenamiento de texto,
donde se conoce la distribución estadística de un alfabeto,
factorización de matrices para disminuir el número de operaciones (o
de colocación de paréntesis). Cálculo del factor combinatorio por el
triángulo de Tartaglia.
- Exploración. Objetivos: Optimización (conflictos
en la visión de optimización), Equilibrio y planes de control.
Conceptos de Biomatemática, Teoría de Juegos y Teoría de Control.
Jugadores e interacción. Exploración por fuerza bruta, back and forht
(uso de pila) . Robotica. Principio de Bellman. Heuristicas y
Reductibilidad. Ejemplos de rutas de mínimo costo y reducción de un
grafo de costos por distancia Euclidiana (la complejidad cambia en el
ejemplo de $\Theta((n-1)!)$ a $\Theta(n).$
- Algoritmos de Dikstra y Warshal y su relación con
el Principio de Optimalidad de Bellman. Grafos y digrafos, (multigrafos)
representación y propiedades. Matriz de adyacencia (matriz de costos)
y matriz de incidencia de grafos y digrafos. Explicación de las
matrices del algoritmo de Warshall y complejidad $\Theta(n^3)$. Grafos
completos, grafo planar. $K_5$ no es planar. Caminos y ciclos.
Aplicaciones y problemas relacionados.
- Grafos Eulerianos y Hamiltoneanos. Problema
estimar la complejidad de determinar rutas Eulerianas. Fuerza bruta $\Theta(n!
2^n)$. Prop. Una grafo tiene un camino Euleriano si tiene exactamente
dos vertices de grado impar y los demás de grado par. Prop. Una grafo
tiene un ciclo Euleriano si todos vertices sus vertices son de grado
par. La complejidad de determinar la existencia ($kn$) y la
determinación de la ruta o camino ($kn$) conduce a que la complejidad
total es $\Theta(n)$. Por otro lado la complejidad de determinar un
ciclo o camino Hamiltoneano de un grafo arbitrario es $\Theta(n!)$.
Para grafos completos $K_n$ cualquier permutación de sus
vertices es un camino Hamiltoneano. Para matrices arbitrarias de
costo, la determinación de un costo mínimo o máximo de un camino
Hamiltoneano tiene complejidad $\Theta(n!)$ que corresponde a todas
las permutaciones de vertices.
- Metaforas de exploración. Recocido simulado,
metaforas evolutivas.
|
- Metáforas y optimización global. Complejidad de búsqueda uniforme
y búsqueda estocástica: $\Theta(10^n)$. Métodos de relleno y
deflación, Métodos de tunelización. Nota: la exploración de estos
métodos es $\Theta(kn)$ que no garantiza una exploración exhaustiva,
sino resultados locales. Algoritmos inspirados de la Biología.
Algoritmo genéticos: Fenotipos vs genomas. Paso 1) Crear población
inicial. paso 2) Operaciones genéticas, nueva población. Paso 3)
Operaciones de selección (Elitismo o mejor, peor, promedio o moda)
para determinar la recortar la nueva población tratando que sea
diversa y representativa. Repetir M veces o repetir hasta tener
estacionalidad por M' veces.
- Operaciones genéticas y un ejemplo. Presentación del
proyecto de tarea
4. Materiales del
proyecto. Se agrega referencia 4.
- Distancias. Subtemas Geometria Computacional (cap. 35. de libro de
texto). Diseño de un algoritmo para resolver el problema de encontrar
los puntos más cercanos de un par de conjuntos disjuntos y se parados.
( A priori por fuerza bruta la complejidad $\Theta(n^2)$ corresponde a
dos ciclos anidados). Del cálculo de los centros de masas y del
semicentro de los centros de masa, se tiene una complejidad
$\Theta(2n)$, del cálculo de las distancias al semicentro y de los
puntos de mínimos al semicentro (inclusión de una operación dentro de
los ciclos de cálculo de distancias) se tiene una complejidad total
$\Theta(4n)$. Nota si no se incluye la selección del mínimo, se
agrega una clasificación de costo $2nlog_2(n)$ que "sobra". A
posteriori, si los puntos tienen una estructura triangular y en
particular los puntos de su cáscara poliédrica, la complejidad
resultante es $\Theta(4m)$ donde $m \ll n$ puntos de la cáscara. Hay
un costo sombra del cálculo de la cáscara, pero que vale la pena para
resolver el problema a posteriori muy eficientemente. Orientación de
triángulos por el signo del determinante del producto cruz $x$ y la
base del algoritmo de z buffer para graficación.
- Representación de un
grafo por listas de vecinos.
Algoritmo
Breadth-first search (BFS) para construir un árbol de
recorridos, ejemplo.
Algoritmo de recorridos
de un árbol de complejidad lineal. Relación y usos de árboles de
expansión mínima. Nota: La coloración de los vértices de los
clusters bajo el potencial
de LJ, es una aplicación del alg. BFS donde la coloración es la
distancia a la raíz. Capítulo 23 Elementary graph algorithms (del
libro de texto).
- Revisión y presentación de la tarea 3. Presentación de aa
coloración de los vértices de los
clusters bajo el potencial
de LJ. Discusión de los puntos del reporte, énfasis en ir un paso
más allá el diseño recursivo, divide y venceras, etc. del libro de
texto. La medida de las pruebas computacionales del reporte es CP
time. Las referencias incluyen los libros de Knuth.
- Algoritmos para crear un árbol de expansión mínima a partir de un
grafo conexo y con pesos en sus aristas.
Algoritmo genérico.
Algoritmo de Kruskal
estrategia voraz por aristas ordendas de menor a mayor, más
operaciones de conjuntos.
Algoritmo de Prim estrategia por vertices, como un BFS para
seleccionar los pesos mínimos.
- Revisión de los objetivos y contenido del reporte de los
algoritmos de ordenamiento. Se les dieron correccciones y se agrego en
notas del curso:
Formato para
trabajos del curso.
- 9 noviembre. No hay clase.
|
- Flujo Máximo.
Problema libro de
Texto.
Ejemplo libro de texto.
Bazaraa, Programación
Lineal y flujo de redes.
Formulación como
problema de programación lineal.
- Presentación alumnos:
Método de Ford-Fulkerson.
Algoritmo de
Ford-Fulkerson. Revisión de avances de los proyectos. Dos ejemplos
resueltos con modelado y representación bajo estructuras de datos
apropiadas y
Método de Ford-Fulkerson.
- Reunión en mi oficina para revisión de los
proyectos. Concursos:
http://www.aniei.org.mx/ANIEI/eventos-aniei/congreso-nacional-e-internacional/concurso-de-programacion/
https://omegaup.com/ Libro:
Problemas y
Algoritmos, Luis E. Vargas Azcona Acordamos revisar los códigos de
los programas y los experimentos la próxima clase.
- 19 de noviembre 2018. Lunes. Los alumnos no se
presentaron para presentar un examen de inglés.
- Revisamos y sugerimos correcciones para el primer
reporte. Presté una revista y el libro texto.
- No se presentaron los alumnos a revisión.
- Revisión y correcciones, proyecto 1. Se les prestó
una computadora portátil Laptop Dell XPS.
- Viernes 30 de noviembre. Los alumnos no se
presentaron a revisión.
- Pasen por las sugerencias de la introducción y
antecedentes y conclusiones.
|
