Algoritmo y complejidad

Vista previa del material en texto

Algoritmos y Estructuras de datos Página 1 de 6 
 
FACULTAD DE INGENIERÍA 
DEPARTAMENTO DE TECNOLOGÍAS DE INFORMACIÓN Y 
COMUNICACIONES 
 
 
Código-Materia: 09687 – Algoritmos y Estructuras de Datos 
Requisito: 09704 – Algoritmos y Programación II 
Programa – Semestre: Ingeniería de Sistemas – Ingeniería Telemática – 4to semestre 
Período académico: 202120 
Intensidad semanal: 5 horas 
Créditos: 3 
 
Programa: Ingeniería de Sistemas 
 Resultados de Aprendizaje 
relacionados con el Programa 
● A: Aplicación de las Ciencias y las Matemáticas (A) 
● C: Diseño de Software (T) 
● E: Solución de Problemas (T) 
● K: Herramientas de Ingeniería (A) 
 Fuente de Valoración NO 
Resultados de 
Aprendizaje 
 
Programa: Ingeniería Telemática 
 Resultados de Aprendizaje 
relacionados con el Programa 
● Aplicación de las Ciencias y las Matemáticas (A) 
● C: Diseño de Software (T) 
● E: Solución de Problemas (T) 
● K: Herramientas de Ingeniería (A) 
Fuente de Valoración NO 
Resultados de 
Aprendizaje 
 
 
 
En este curso los estudiantes se verán enfrentados a la solución de problemas utilizando estructuras de datos y 
análisis de algoritmos clásicos de la computación. El curso está orientado a generar en el estudiante la habilidad 
de analizar, diseñar e implementar estructuras de datos en memoria principal necesarias para resolver problemas 
concretos, teniendo en cuenta conjuntos de restricciones y criterios de calidad. Estas estructuras han de 
integrarse a proyectos que deben desarrollarse siguiendo un proceso sistemático, teniendo en cuenta el análisis, 
la planeación, el diseño de la aplicación, el uso de pruebas automáticas y la generación de documentación. 
 
Objetivos 
General 
Solucionar problemas a través del desarrollo de programas que utilizan algoritmos y estructuras de datos clásicos 
de la computación. 
 
Terminales 
Al final del curso, se espera que el estudiante esté en capacidad de: 
OT1. Evaluar algoritmos y estructuras de datos utilizados en la solución de problemas teniendo en cuenta criterios 
de eficiencia computacional. 
OT2. Desarrollar estructuras de datos desacopladas y reutilizables. 
OT3. Construir programas que utilicen las estructuras de datos clásicas fundamentales. 
 
Algoritmos y Estructuras de datos Página 2 de 6 
Objetivos Específicos: 
Unidad 1: Análisis de Algoritmos 
Al finalizar esta unidad, el estudiante estará en capacidad de: 
OE1.1. Calcular la complejidad temporal de algoritmos iterativos. 
OE1.2. Calcular la complejidad espacial de algoritmos iterativos. 
OE1.3. Caracterizar la entrada de un algoritmo iterativo con el fin de calcular la complejidad para el mejor y peor 
caso. 
OE1.4. Analizar algoritmos independientes de una implementación concreta (no dependiente del lenguaje de 
programación). 
OE1.5. Utilizar notación asintótica para describir la complejidad de algoritmos. 
OE1.6. Evaluar varios algoritmos que resuelven el mismo problema en términos de sus complejidades 
computacionales. 
OE1.7. Comprender la importancia del Modelo RAM en el proceso de análisis de algoritmos. 
OE1.8. Especificar formalmente un problema teniendo en cuenta sus precondiciones y postcondiciones. 
 
Unidad 2: Diseño y Construcción de Estructuras de Datos 
Al finalizar esta unidad, el estudiante estará en capacidad de: 
OE2.1. Aplicar apropiadamente una metodología de diseño de estructuras de datos abstractas. 
OE2.2. Utilizar correctamente tipos de datos genéricos en el diseño de nuevas estructuras de datos. 
OE2.3. Evaluar la complejidad computacional de las operaciones implementadas como parte de nuevas 
estructuras de datos. 
OE2.4. Implementar estructuras de datos extensibles y desacopladas utilizando interfaces y herencia. 
OE2.5. Implementar estructuras de datos genéricas utilizando apropiadamente los tipos de datos parametrizables 
del lenguaje de programación. 
OE2.6. Especificar apropiadamente el invariante de una clase. 
OE2.7. Implementar los métodos necesarios para verificar el invariante de una clase utilizando los elementos 
apropiados del lenguaje. 
OE2.8. Desarrollar estructuras de datos lineales FIFO. 
OE2.9. Desarrollar estructuras de datos lineales LIFO. 
OE2.10. Desarrollar estructuras de datos de acceso directo por llave (diccionarios de datos). 
OE2.11. Utilizar estructuras de datos de acceso directo por llave (diccionarios de datos) en la solución de 
problemas que lo requieran. 
OE2.12. Utilizar estructuras de datos FIFO en la solución de problemas que lo requieran. 
OE2.13. Utilizar estructuras de datos LIFO en la solución de problemas que lo requieran. 
OE2.14. Comparar las estructuras de datos propias del API del lenguaje con las estructuras implementadas en el 
curso. 
OE2.15. Desarrollar las pruebas unitarias para cada una de las estructuras de datos lineales implementadas. 
 
Unidad 3: Algoritmos y Estructuras Recursivas 
Al finalizar esta unidad, el estudiante estará en capacidad de: 
OE3.1. Calcular la complejidad temporal de algoritmos recursivos. 
OE3.2. Calcular la complejidad espacial de algoritmos recursivos. 
OE3.3. Resolver ecuaciones de recurrencia que sean resultado del análisis de complejidad temporal de algoritmos 
recursivos. 
OE3.4. Identificar los elementos propios de la técnica de diseño de algoritmos Dividir y Conquistar en algoritmos 
Algoritmos y Estructuras de datos Página 3 de 6 
clásicos de ordenamiento y búsqueda. 
OE3.5. Aplicar la técnica de diseño de algoritmos Dividir y Conquistar en la solución de problemas. 
OE3.6. Utilizar estructuras recursivas de datos para representar la información del modelo de datos cuando sea 
conveniente. 
OE3.7. Evaluar la utilidad del concepto de orden en un árbol binario de búsqueda para la solución de problemas. 
OE3.8. Evaluar la utilidad del concepto de balanceo en un árbol binario de búsqueda para la solución de 
problemas. 
OE3.9. Desarrollar estructuras de datos recursivas ABB. 
OE3.10. Desarrollar estructuras de datos recursivas R&N. 
OE3.11. Desarrollar estructuras de datos recursivas AVL. 
OE3.12. Desarrollar estructuras de datos recursivas Montículo Binario. 
OE3.13. Utilizar estructuras de datos Montículo Binario en la solución de problemas que lo requieran. 
OE3.14. Desarrollar las pruebas unitarias de cada una de las estructuras de datos recursivas implementadas. 
Unidad 4: Grafos 
Al finalizar esta unidad, el estudiante estará en capacidad de: 
OE4.1. Explicar los conceptos básicos sobre la teoría de grafos. 
OE4.2. Modelar la información de un problema utilizando un grafo como estructura de datos. 
OE4.3. Desarrollar una estructura de datos Grafo utilizando listas de adyacencia. 
OE4.4. Desarrollar una estructura de datos Grafo utilizando matrices de adyacencia. 
OE4.5. Aplicar el recorrido en profundidad de un grafos en el contexto de un problema dado. 
OE4.6. Aplicar el recorrido en amplitud de un grafo en el contexto de un problema dado. 
OE4.7. Desarrollar un grafo representado por matrices de adyacencia. 
OE4.8. Desarrollar un grafo representado por listas de adyacencia. 
OE4.9. Implementar el algoritmo de recorrido en amplitud -BFS- sobre un grafo. 
OE4.10. Implementar el algoritmo de recorrido en profundidad -DFS- sobre un grafo. 
OE4.11. Implementar el algoritmo de Dijkstra sobre un grafo. 
OE4.12. Implementar el algoritmo de Floyd-Warshall sobre un grafo. 
OE4.13. Implementar el algoritmo de Prim sobre un grafo. 
OE4.14. Implementar el algoritmo de Kruskal sobre un grafo. 
OE4.15. Utilizar el algoritmo de recorrido en amplitud -BFS- en la solución de problemas que lo requieran. 
OE4.16. Utilizar el algoritmo de recorrido en profundidad -DFS- en la solución de problemas que lo requieran. 
OE4.17. Utilizar el algoritmo de Dijkstra en la solución de problemas que lo requieran. 
OE4.18. Utilizar el algoritmo de Floyd-Warshall en la solución de problemas que lo requieran. 
OE4.19. Utilizar el algoritmo de Prim en la solución de problemas que lo requieran.OE4.20. Utilizar el algoritmo de Kruskal en la solución de problemas que lo requieran. 
OE4.21. Desarrollar las pruebas unitarias de cada una de las estructuras de datos Grafo implementadas. 
 
Transversales 
Durante el desarrollo de todo el curso, el estudiante desarrollará la capacidad de: 
OET1. Utilizar convenciones de codificación como un elemento de calidad en la implementación de programas. 
OET2. Reconocer la importancia de la medición de su proceso personal de desarrollo de software. 
OET3. Medir sistemáticamente los tiempos utilizados en cada una de las etapas de desarrollo de software. 
OET4. Medir sistemáticamente el tamaño de los entregables producidos. 
OET5. Mantener un registro ordenado del proceso de medición llevado a cabo en cada uno de los proyectos de 
Algoritmos y Estructuras de datos Página 4 de 6 
desarrollo de software. 
OET6. Valorar y corregir las inconsistencias que se pueden presentar entre cada uno de los elementos de diseño 
propuestos en el diagrama de clases y su implementación en el lenguaje de programación. 
OET7. Utilizar un sistema de control de versiones para la gestión de los archivos producidos durante el proceso 
de desarrollo de software. 
 
Metodología 
Para los estudiantes: 
La herramienta de Icesi Virtual (INTU) es el medio que contiene la información oficial del curso y es 
responsabilidad del estudiante consultar en ella todo lo referente al curso, especialmente las actualizaciones 
del material y actividades. 
 
De acuerdo a la metodología de aprendizaje activo de la universidad Icesi, los estudiantes deben preparar, antes 
de la clase, los temas asignados en la programación del curso. Esto es: 
● Leer y estudiar el material asignado para la sección de clase. Si no se ha asignado material, entonces 
investigar sobre los temas acordados en la planeación. 
● Utilizar estrategias de estudio (mapas conceptuales, mapas mentales, resúmenes, etc.) que sean efectivas 
y que sirvan como refuerzo después del proceso de lectura. 
● Intentar contestar las preguntas que contiene el material, así como las preguntas adicionales que el 
profesor entregue. 
● Resolver los ejercicios propuestos en el material, así como los ejercicios adicionales que se le entreguen. 
● Formular preguntas para ser resueltas durante la clase. 
Durante la clase, el estudiante deberá: 
● Plantear las dudas que le quedaron durante el proceso de estudio del tema a tratar. 
● Participar en las actividades de revisión y consolidación de conceptos que proponga el profesor. 
● Trabajar en la solución de los problemas de aplicación que se propongan. 
Después de la clase: 
● Establecer las relaciones entre los temas tratados en la clase y el conocimiento previamente adquirido. 
● Intentar resolver los ejercicios de aplicación del tema, en especial aquellos con un nivel de complejidad 
mayor al de los ejercicios que resolvió previamente. 
 
Para el desarrollo del curso: 
Este curso cuenta semanalmente con dos tipos espacios que son utilizados de la siguiente forma: 
● Sesiones teórico/prácticas: los estudiantes y el profesor se encontrarán en este espacio, en dos sesiones 
de una hora y media (una hora, 30 minutos) en las cuales se llevará a cabo la discusión de los diferentes temas 
y la realización de ejercicios que permitan ponerlos en práctica. 
● Sesiones principalmente prácticas: los estudiantes, el profesor y el monitor del curso comparten un 
espacio en el cual se llevan a cabo la solución de problemas propuestos y su implementación en el lenguaje 
Java. Para este componente se han destinado dos (2) horas por semana. 
 
Este curso utilizará Java como lenguaje de programación y Eclipse como entorno de desarrollo. No obstante, los 
objetivos de aprendizaje son independientes del lenguaje y el entorno de programación seleccionado. 
 
Evaluación 
En todas las evaluaciones de carácter escrito se tendrá en cuenta la GRAMÁTICA, ORTOGRAFÍA y PUNTUACIÓN 
con el objetivo de desarrollar y consolidar la competencia de escritura del estudiante. Las evaluaciones del curso, 
están programadas en el cronograma del curso disponible en INTU. 
Algoritmos y Estructuras de datos Página 5 de 6 
● Controles de lectura y quices: corresponde a todas las comprobaciones de lectura y de aprendizaje que 
se hagan durante el curso. Estas comprobaciones pueden realizarse con o sin previo aviso por parte del 
profesor. 
● Tareas Integradoras: durante el semestre se llevarán a cabo 3 Tareas Integradoras que los estudiantes 
deben entregar utilizando la plataforma de Icesi Virtual (INTU). La nota de cada tarea integradora se calcula 
así: primero, se revisa el trabajo entregado con base en la rúbrica de la tarea. Esa revisión deja una nota que 
será multiplicada por el factor de la sustentación. El factor, es un valor real entre 0 y 1 que se calcula así: se 
hacen, por ejemplo, 4 preguntas al estudiante, si responde a las 4 preguntas de forma correcta, entonces el 
valor será 1, si responde a 3 correctamente (1 la responde erróneamente) obtendrá 0.75 en el factor, si 
responde solo a 2 correctamente tendrá 0.5, y así. Entonces, si en la calificación obtuvo una calificación de 
5.0 y en el factor de sustentación es de 0.75, su nota de la tarea será de 5.0*0.75 = 3.75. Las tareas 
integradoras tendrán una evaluación formativa, es decir, si después de obtener esta nota, el estudiante desea 
mejorarla, puede hacerlo, y el trabajo será evaluado nuevamente, por una única vez adicional. Esto último, 
por cada tarea integradora 
● Seguimientos de Aprendizaje: al final de la semana se evaluarán los temas y competencias desarrollados 
a lo largo de la semana a través de una prueba breve que puede ser teórica, práctica o teórico/práctica. La 
prueba será calificada una vez cada dos semanas. 
Supletorios: Como no hay exámenes presenciales, tampoco existen supletorios. 
 
Nota definitiva: 
A continuación, se especifican los porcentajes de las evaluaciones: 
 
Evaluación Porcentaje 
Tarea Integradora 1 20% 
Tarea Integradora 2 20% 
Tarea Integradora 3 20% 
Seguimientos 30% 
Controles de Aprendizaje Previo y Participación 10% 
Total 100% 
 
TUTORÍAS GRUPALES 
El Departamento de TIC ofrece 2 sesiones de tutoría grupales a la semana, de 2 horas cada una, para el bloque 
de algoritmos y programación desde la semana 1 del semestre. También tendremos 3 sesiones de monitorias, de 
2 horas cada una. Las tutorías son atendidas por profesores de algoritmos, las monitorias son atendidas por 
estudiantes destacados de semestres superiores. En estos espacios los estudiantes cuentan con un profesor del 
área con el cual pueden resolver interrogantes que hayan quedado sobre temáticas del curso o ser asesorados 
en dudas puntuales que tengan respecto a la solución de problemas. El horario y los espacios de estas tutorías 
serán informados oportunamente en la primera semana del semestre académico. 
 
TUTORÍAS INDIVIDUALES 
El Departamento de TIC ofrece también tutorías individuales a aquellos estudiantes que hayan asistido a las 
tutorías grupales y consideren que requieren de tutorías adicionales para aclarar ciertos conceptos puntuales. 
Estas tutorías deben programarse con la asistente del programa previa remisión del profesor del curso del 
estudiante. 
 
 
Algoritmos y Estructuras de datos Página 6 de 6 
Bibliografía 
● Thomas Cormen. Charles Leiserson. Ronald Rivest. Clifford Stein. Introduction to Algorithms. Third Edition. 
The MIT Press. 2009. 
● Sally A. Goldman and Kenneth J. Goldman. A Practical Guide to Data Structures and Algorithms Using Java. 
Boca Raton: Chapman & Hall/CRC, 2009. http://goldman.cse.wustl.edu/. 
● Mark A. Weiss. Data Structures and Problem Solving Using Java, 4/E . Addison-Wesley. 2010. 
● Steven Skienna. The Algorithm Design Manual Springer. 1997 
● V. Anton Spraul. Think like a Programmer. No starch press. 2012. 
● Jorge Villalobos. Diseño y manejo de Estructuras de Datos en C. McGraw-Hill/ Interamericana Editores.2006.