UANL

Algoritmos computacionales

Este es el sitio web de la unidad de aprendizaje sobre algoritmos computacionales (Optativa II FBP) impartida por la Dra. Elisa Schaeffer en la FIME de la UANL en el verano de 2011 a M4-6 (09:30-12:00) con laboratorio a M1-2 (07:00-08:40), ambos en el salón 4200.

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 identificará 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

El siguiente listado indica la temática de cada sesión.

  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. Representación y manipulación de listas: algoritmos de búsqueda y ordenamiento (unidad 4a)
  9. Representación y manipulación de estructuras lineales dinámicas; tablas de dispersión (unidad 4b, ejemplo en ANSI C)
  10. Representación y manipulación de árboles: búsqueda y recorrido (unidad 5a, ejemplo en ANSI C)
  11. Grafos, parte 1: su representación
  12. Grafos, parte 2: su manipulación (caminos, expansión, cortes y flujos) (unidad 5b, ejemplo en ANSI C )
  13. Temas integradores
  14. Examen oral: 10 preguntas base y 10 por puntos extra.

Producto integrador

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.

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 de la clase se forma como la sumatoria de dos componentes:

Las tareas se evalúan en la siguiente escala:

El laboratorio se califica de la siguiente manera:

Los puntos se suman y se corta en 100. Es la responsabilidad del alumno de completar los 70 puntos requeridos para pasar el laboratorio en el transcurso de las tres semanas. No hay examen. No se otorga puntos por la mera presencia en el salón.

Tareas

Cada unidad temática tiene su propia tarea. Las tareas se entregan a través de un blog personal de cada participante. Siendo un curso de verano, es imposible otorgar prórrogas a la entrega de las tareas, ya que toda la unidad se debe cursar dentro de tres semanas.

  1. Algoritmos computacionales simples: reporte con gráficas para el primer viernes
  2. Fundamentos de la complejidad computacional: reporte con gráficas para el segundo miércoles
  3. Algoritmos recursivos: presentación en diapositivas incrustadas para el segundo viernes
  4. Arreglos, tablas y listas: presentación en video incrustado para el tercer martes
  5. Árboles y grafos: presentación en video con voz incrustado para el tercer jueves

Resultados

Clase

Participante Tareas Examen TotalExtraord.
1 2 3 4 5
Abraham 10 NP NP NP NP NP 10 -
Alejandro 16 11 NP NP NP NP 27 -
Cecilia 18 12 16 18 17 NP 81 -
Edwin 9 5 NP 14+6 NP NP(3+2) 34 54
Gaby 17 9 NP NP NP NP 26 -
Gemma 16 NP 17 NP NP NP 33 -
Isáias NP 13 14 NP+4 NP NP 31 -
Jesús 13 11 18 NP NP+18+10 5+5 80 -
Jorge 14+3 14+2+1 17 16+1 12 NP 80 -
Juan Esteban 15 NP NP NP NP NP 15 -
Heriberto 12+1 0 13+1+2 NP+1 NP+1+3
1+2
4+2 43 70
Humberto 12 10 17 7+2 10+2+3 6+4 73 -
Karla 13+3 12+4 15+2+3 16+3+2
2
16+2+2
1
NP 96 -
Leonardo 14+2 NP NP NP NP NP 16 -
Ludim 11 NP NP NP NP NP 11 -
Ramón Esteban 17 16 14 NP NP+4+4
3+16
NP 74 -
Roberto 18 17 18 18 17 NP 88 -
Uriel 12+1 7+4 16+2 NP+3+3
7+1+2
NP+10 3+5 76 -

Laboratorio

Participante Sesión Total
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Alberto 5+3 10 4+6+4 4+3+8 4+3 6+4+7
4
10+6 8+5 2+10 10+8 7+6 6 10 8 100+71
Alejandro 3 6+3 4+4 5+3 5+2 3+4 7 4 3+2 10 6 0 5 0 79
Alma 0 10+1+1 6+4 0 6 0 8 5+7+3
5
0 7+3+8
4
0 0 3+10 0 91
Carlos 0 3+4+2
3
3+2 2+3 2+4 2+5 4+2 2+2+3 2+5 4+4 0 3+4 0 0 70
Daniel 0 4+3+2
3
3+5+3
4
2+3+3
4
4+5+3 5+4 3+2+9
4
5+3 2+4 4+3+5 5+10 5 6+4 0 100+34
Fernanda 0 2+3 4 2+2 0 2+3+1
2
3+3+2 3+3+3 1+7 3+2+1 3 3+3 5+3 2 71
Karen v2 2 4+4 3+5 epic fail 7 0 0 10+4+4
5
10 8+4 7 6 0 0 83
Mauricio 3 0 5+1 4+4+2 3 3 4+10+3 4 0 8+3+4 4+10 0 8 5+4 92
Miguel 0 4+4+2
1
5 0 2+6+3 5 3+5+3 0 2+8 0 5+6 2+5 0 0 71
Salvador 3 8+1 10+7+1 0 0 8+3 3 7 6 5 4 10 0 1 77
Tulio 3+3+1 2+2 3+3+1
4+1+3
3+2 3+3 4 2+1+2
2+2+1
1
7 4 4 4 0 0 0 71

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, 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 18 de julio del 2011.
URL: http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/2011/