Física (plan 2002) 2023-2

Optativas, Temas Selectos de Física Computacional I

El curso será impartido de 7:30 a 9:00 los días lunes y martes, en el Aula 1 de Cómputo del Departamento de Física de la FC.

Análisis de Algoritmos.

Grupo del curso (Telegram), donde nos pondremos de acuerdo de los horarios y demás detalles: https://t.me/+ZhfJKZ2MfxEyMWJj

El curso busca que los estudiantes entiendan la importancia de las implementaciones computacionales de los algoritmos que componen muchas de las soluciones de software de hoy en día, tanto en el campo científico como en la industria. El curso será mayormente teórico con énfasis en complejidad algorítmica, así como argumentos y demostraciones de exactitud y convergencia. La parte práctica del curso tiene como meta solidificar el conocimiento adquirido en la teórica, por medio de contar con programas interactivos que muestran el resultado de cada tema.

Temario

• Complejidad algorítmica y notación asintótica
• Primer vista: Algoritmos de ordenamiento (inserción, burbuja)
• Divide y Vencerás
• Recursión y teorema maestro
• Segunda vista: Algoritmos de ordenamiento (Merge Sort)
• Programación Dinámica
• Estructuras de datos (Arreglos, Listas, Filas, Árboles, Heaps)
• Árboles de búsqueda binaria
• Tercera vista: Algoritmos de ordenamiento (Heap Sort)
• Límite teórico de los ordenamientos
• Redes no dirigidas
• Búsquedas (BFS, DFS)
• Ordenamiento topológico
• Redes dirigidas
• Ciclos, Componentes y Flujos
• Ford-Fulkerson, cortes mínimos y flujos máximos
• Árboles de expansión
• Algoritmo de Prim
• Algoritmo de Kruskal
• Camino más corto
• Algoritmo de Bellman-Ford
• Algoritmo de Dijkstra
• Análisis Probabilístico
• Hashes y diccionarios
• Quick Sort: la despedida

Para que el temario no se haga tan largo, quitamos de ahí todos los ejemplos de casos prácticos y aplicaciones, los cuales se discutirán en el curso.

Las aplicaciones a los temas del curso son bastas, pero como ejemplos puntuales, se tiene la siguiente lista

• Problemas de control de flujo de tráfico
• Problemas que requieran ordenamientos
• Simulación de N-Cuerpos
• Dinámica Molecular
• Secuenciación y compresión de cadenas (ADN, por ejemplo)
• Diseño y análisis de circuitos
• Búsqueda de cadenas en grandes datos
• Comunicaciones y redes
• Problemas de optimización
• Videojuegos
• Cualquier aplicación informática, pues.

Todos los ejemplos de la clase y códigos que se les lleguen a proporcionar se harán con Rust, y en general es el lenguaje de programación recomendado para el curso. Sin embargo, los estudiantes podrán hacer sus ejercicios y tareas en Python, C++, C, y Javascript/Typescript. El curso no es de programación, por lo que se espera que en el lenguaje que el estudiante prefiera, se cuente ya con cierta experiencia.

La calificación se determinará con una única evaluación al final del curso. El objetivo del examen es determinar que los estudiantes salen del curso con conocimientos básicos sólidos, y con las herramientas necesarias para reconstruir el conocimiento cuando se requiera por medio de un razonamiento lógico, o una buena búsqueda en el lugar indicado.

Habrán ejercicios y tareas opcionales, que podrán otorgar hasta 1.5 puntos directo sobre el promedio final, pero estos puntos sólo serán tomados en cuenta si la calificación de la evaluación final es aprobatoria.