UANL

Algoritmos computacionales

Este es el sitio web de la unidad de aprendizaje sobre algoritmos computacionales (Optativa II FBP) para los dos grupos de la Dra. Elisa Schaeffer en la FIME de la UANL en primavera de 2010 los martes 14:30-17:00 y los jueves 12:00-14:30 en el salón 4200 en el primer piso del edificio cuatro (el mapa de FIME ayuda a ubicar el edificio).

Requisitos

Es necesario haber cursado Matemáticas I.

Presentación

Esta unidad de aprendizaje aborda el tema del diseño de los algoritmos computacionales a necesidades especificas de los tipos de datos usándolos en base a su especificación (propiedades funcionales) y no a su implementación y estudio de los principales tipos, tanto elementales como no elementales, dividiendo éstos últimos en estructuras lineales (como listas, pilas y colas) y no lineales (como árboles y grafos), analizándolos desde el punto de vista teórico, sin perder de vista sus aplicaciones prácticas.

En la unidad se desarrollará el primer nivel de las competencias que ayudarán en la formación del perfil del egresado, debido a que esta unidad de aprendizaje contribuirá en el desarrollo del alumno haciéndolo competente en escribir pseudocódigo declarativo, formular métodos de solución para problemas, describir métodos de solución en términos computacionales, representar el estado de un sistema, manipular información eficientemente en forma de pilas, listas, árboles y grafos, analizar la complejidad de soluciones propuestas.

Saber hacer uso de las técnicas de diseño y los algoritmos computacionales suele ser vital en la formación de los alumnos que estudian una carrera afín a la computación debido a la trascendencia que el aprendizaje teórico-práctico de las mismas supondrá para la competencia general de la carrera.

Propósito

Esta unidad de aprendizaje se contribuye a la formación de egresados en que posean las habilidades y herramientas para el aprendizaje autónomo y pone en práctica una dinámica de superación constante. El alumno identificara las herramientas teóricas fundamentales para la representación y manipulación de información en la computadora, haciendo énfasis en el tipo de datos dinámicos, así como desarrollará su capacidad para aplicarlos a situaciones concretas y su forma de trabajar en equipo y desarrollar proyectos conjuntos.

Las competencias desarrolladas son las siguientes:

Unidades temáticas

  1. Algoritmos simples: Formular y desarrollar algoritmos simples utilizando para ello pseudocódigo declarativo o diagramas de flujo haciendo uso de herramientas computacionales graficas, que le permitan depurar errores de lógica, en problemas simples de ingeniería y manejo de información.
  2. Fundamentos de la complejidad computacional: Identificar las técnicas fundamentales de análisis y diseño de algoritmos que permitan comprender la naturaleza de los problemas tan independientemente como sea posible de los aspectos de implementación (tanto hardware como software) y resolverlos eficientemente.
  3. Algoritmos recursivos: Diseñar e implementar soluciones a problemas del entorno utilizando las estructuras de datos lineales, como lo son las pilas, colas y listas, mediante el diseño de algoritmos recursivos.
  4. Listas, ordenamiento, búsqueda y tablas de dispersión: Analizar, diseñar y programar soluciones de ordenamiento de datos, así como la búsqueda de la información ordenada, haciendo uso de las estructuras de datos lineales.
  5. Árboles y grafos: Analizar, diseñar y programar soluciones de problemas en el que se tengan que tomar decisiones que dependan del estado del sistema, haciendo uso de estructuras de datos no lineales.

Programa semanal

El siguiente listado indica la temática de cada sesión semanal. El tratamiento será introductorio, incluyendo elementos más avanzados según el nivel e interés demostrado por los participantes. Los elementos de la lista convertirán en ligas a diapositivas en formato PDF de lo que se ve en clase durante el semestre.

  1. Introducción a algoritmos: variables, condiciones y repeticiones; pseudocódigo (unidad 1a)
  2. Matemáticas de algoritmos; lógica computacional (unidad 1b)
  3. Modelos formales de computación: autómatas y máquinas (unidad 1c)
  4. Análisis asintótico de algoritmos (unidad 2a)
  5. Problemas de decisión y su complejidad computacional; problema de satisfacción (unidad 2b)
  6. Problemas de optimización y su complejidad computacional; problema de la mochila (unidad 2c)
  7. Recursión como herramienta en resolución de problemas computacionales (unidad 3)
  8. Examen de medio curso
  9. Representación y manipulación de listas: algoritmos de búsqueda y ordenamiento (unidad 4a)
  10. Representación y manipulación de estructuras lineales dinámicas; tablas de dispersión (unidad 4b)
  11. Representación y manipulación de árboles: búsqueda y recorrido (unidad 5a)
  12. Presentaciones del proyecto 4
  13. Representación y manipulación de grafos: caminos, expansión, cortes y flujos (unidad 5b)
  14. Estratégias clásicas de diseño algorítmico: algoritmo euclidiano y distancia de edición; manipulación de secuencias y textos: búsqueda de patrones y bioinformática; algoritmos de aproximación: problema del viajante y cobertura con vértices; algoritmos aleatorizados: probabilidad en computación; algoritmos heurísticos: búsqueda local y algoritmos evolutivos (temas integradores)
  15. Presentaciones del proyecto 5
  16. Examen ordinario

Producto integrador

Proyectos individuales y en grupo de desarrollo, representación y análisis de métodos de solución en términos computacionales.

Al finalizar la unidad de aprendizaje el estudiante entregará su portafolio en forma de blog para su evaluación, el cual contendrá todos los reportes, registros de conclusiones e investigaciones generados en clase y en los proyectos desarrollados.

Blogs de los participantes

Bibliografía básica

Se hará uso amplio materiales de enseñanza en línea. No es necesario comprar un único libro de texto, sino cualquier libro de parecido sirve como material de apoyo.

Vean tambien materiales sobre programación. Para diagramas de flujo, pueden usar Raptor.

Evaluación

La calificación final se forma a través de las siguientes ponderaciones:

Para calcular la calificación final, se compara la suma acumulado de reportes al máximo posible (5 x 4 = 20) y acumula esa proporción de los 35 puntos a la calificación final. Luego se hace lo mismo con presentaciones (3 x 4 = 12). Los puntos de participación (5), examen parcial (10) y examen final (20) se suman directamente con estos dos para obtener la calificación final a escala de cero a cien con redondeo estándar (de 0.5 hacia arriba).

Por ejemplo, con un total de 16 puntos de los reportes, 9 de las presentaciones, 3 de participación y 6 + 17 de los exámenes, la calificación final sería

(16/20) x 35 + (9/12) x 30 + 3 + 6 + 17 = 28 + 22.5 + 26 = 76.5
que redondea a 77 como calificación de la unidad.

Los reportes, presentaciones, las respuestas a las preguntas de los exámenes (multiplicados por cinco - son 5 preguntas de 20 puntos cada uno en los dos exámenes) y la participación se evalúan en la siguiente escala:

A los proyectos más ambiciosos con temas avanzados se evaluará de manera menos estricta, mientras de los proyectos muy básicos se exige más. Los estudiantes tendrán posibilidad de definir el tema exacto y el nivel de su proyecto cuando está asignado.

Proyectos

Cada unidad temática tiene su propio proyecto que se evalua a través de reportes escritos, presentaciones orales y/o participación:

  1. Algoritmos computacionales simples - Reporte en pares - Fecha límite: el viernes 19 de febrero, 23:59 horas (medianoche)
  2. Fundamentos de la complejidad computacional - Reporte individual - Fecha límite: el viernes 5 de marzo, 11:59 horas (mediodía)
  3. Algoritmos recursivos - Reporte y presentación en grupos de 3-4 alumnos - Fecha límite: el domingo 14 de marzo, 23:59 horas (medianoche)
  4. Listas, ordenamiento, búsqueda y tablas de dispersión - Reporte y presentación en grupos de 3-4 alumnos - Fecha límite: el domingo 25 de abril, 23:59 horas
  5. Árboles y grafos - Reporte, presentación y participación individual

Resultados

Las ligas en la tabla apuntan a los criterios de calificación usadas en evaluación entre pares. La calificación final toma en cuenta los puntos acumulados por área (reportes / presentaciones / participación) ponderados por los porcentajes correspondientes a cada una en la tabla de evaluación. Los resultados de los exámenes han sido ya redondeados a los puntos finales: 10 máximo para el de medio curso y 20 para el ordinario. Las ligas a los exámenes contienen la hoja de preguntas y los resultados detallados.

En el extraordinario, el alumno define si quiere retomar el examen de medio curso o el ordinario o ambos. En la tabla de resultados, n/a significa "no aplica" en los casos que el alumno no tomó dicha parte como extraordinario. Los que no presentaron segundas no tienen ninguna calificación en las últimas tres columnas de la tabla de resultados. Al retomar uno o dos exámenes, sus calificaciones anteriores ya no estarán tomados en cuenta en determinar la calificación de segunda oportunidad.

Puntos extra

Los puntos extra corresponden o a trabajos en el blog (en cual caso los puntos otorgados aparecen como un comentario de la profesora de la entrada en cuestón en el blog), en cual caso la calificación fue decidida de manera democrática o en las asesorías o en la lista de correos de los grupos 2010 (algcomp@googlegroups.com), o a problemas resueltos en el examen final, calificados por la profesora con las cantidades de puntos máximos indicados en la hoja del exámen. Si el alumno decidióo repitir un examen y luego sacóo un peor puntaje al repetir, queda vigente de todos modos la calificación más reciente.

Matrícula Proyectos realizados Exámenes Extra CF 1era Extra-
ordinario
CF 2da
Reportes en blog Presentac. Part.
 1 2 3 4 5  3 4 5  5 Medio
curso
Final Medio
curso
Final
1330260 2012- 33-- 07-31    
1346125 301-- 243- 615-51    
1366674 1012- 33-- 0--22    
1377870 3022- 44-- 24-38 4137
1382239 43243 3412 243456 4n/a92
1384138 40-23 3321 15-43    
1387357 03333 3434 3133+566 6n/a77
1410319 34344 3423 312173    
1412573 44343 2321 351558 4n/a74
1421041 20-3- -4-- 03-22 3224
1422117 1034- 332- 25-41    
1427841 002-- 34-- 12-24 2124
1437712 34334 3423 572+18+469 n/a1296
1441100 34-13 -4-- 14-34 2031
1441212 003-- 2--- 1--11    
1441477 22-3- -3-- 07-27 --20
1442475 44232 3321 453+9+4+259 n/a1180
1442709 44344 3443 69180    
1443417 43243 3433 561067 n/a879
1443502 43343 3443 213277    
1445018 42143 132- 29253 4450
1445053 40-43 131- 23138 3339
1445706 04134 3412 311259    
1446239 44334 3435 2102+278    
1446426 44444 3444 6171+4+9100+    
1449230 44244 3435 29275    
1449279 20243 2433 110258 5254
1450138 44344 3445 316287    
1450658 40--- 2--- 1--13    
1452344 20243 3321 27251 3247
1453644 12233 3341 382+8+458 7975
1453829 44333 3331 482+10+667 5n/a86
1454820 32243 3444 1102+1369 n/a1183
1455473 40-01 131- 15-27 3n/a29
1455593 20242 -441 142+446 0652
1455887 30233 3331 3519+5+151 2n/a75
1456126 20233 342- 127+6+243 7n/a64
1456340 0023- 23-- 1--22    
1456992 41--1 332- 02233 2035
1457717 34243 3435 113-72    
1458143 33242 2433 162+6+7+365 5679
1458774 00-32 332- 15-35 2637
1459025 34232 3311 369+352 41170
1459556 1--13 -4-- -3-22 2324
1461380 11-32 3321 37-43    
1462180 24233 4432 323+5+359 51181
1463098 44244 3442 1102+478    
1463439 34344 3335 2143+280    
1464007 ----- ---- 1--1    
1464182 44344 3335 592+178    
1464397 23234 2321 09852 3n/a63
1464402 21-2- -3-- 24123 3121
1535265 30344 4435 510375    
1535346 30322 44-1 28349 5350
1535393 12324 3433 4103+4+366 n/a1376

Ligas útiles

En esta sección se acumularán durante el semestre ligas a recursos que vemos en clase o que recomiendan los participantes.

Alumnos interesados en participar en proyectos de desarrollo, traducción y lanzamiento de herramientas interactivas para temas sobre programación, algoritmos y estructuras de datos desde el verano 2010 en adelante, repórtense con la profesora.

Utilización de documentos de formato PDF

Para acceder las diapositivas, ejercicios y otros materiales en formato PDF, se necesita Acrobat Reader (descarga gratuita) u otra herramienta similar (en sistemas linux/unix, use el comando acroread o xpdf). Para crear documentos en formato PDF, en Windows se puede instalar una impresora virtual como Primo PDF y en linux imprimir a un archivo en PostScript y utilizar el comando ps2pdf para la conversión.


Actualizado por última vez el 7 de junio del 2010.
URL: http://it.ciidit.uanl.mx/teaching/comp/alg/