Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
INSTITUTO POLITÉCNICO NACIONAL SECRETARÍA ACADÉMICA DIRECCIÓN DE ESTUDIOS PROFESIONALES EN INGENIERÍA Y CIENCIAS FÍSICO MATEMÁTICAS PROGRAMA SINTÉTICO CARRERA: Ingeniería en Computación ASIGNATURA: Análisis de Algoritmos SEMESTRE: Quinto OBJETIVO GENERAL: El alumno resolverá problemas de procesamiento, diseñando algoritmos, aplicando técnicos de programación y estructuras de datos. CONTENIDO SINTÉTICO: I. Introducción. II. Teoría de la Computación. III. Tipos de datos Abstractos y Estructuras de Datos. IV. Técnicas, Diseño y Análisis de los Algoritmos, Algoritmos Geométricos. METODOLOGÍA: Preparación y discusión de los temas por parte de los alumnos así como la resolución de problemas bajo la supervisión del profesor. Trabajo en equipo. A su vez el uso de material didáctico y presentaciones en Power Point para un mejor y mayor avance en las unidades propuestas. EVALUACIÓN Y ACREDITACIÓN: Participación en actividades de clase, presentación y calidad de trabajos extra clase, aplicación de tres exámenes parciales o departamentales durante el semestre, cubrir y entregar la totalidad de las practicas de laboratorio. La calificación final será el promedio de las evaluaciones anteriores, siempre y cuando el alumno cumpla con lo estipulado en la reglamentación institucional. BIBLIOGRAFÍA: 1. Abellanas M. Lodares D., Análisis de Algoritmos y Teoría de Grafos, Macrobit Editores, México, 1998. p 1-256. 2. Aho, Alfred, Hopcroft, John and Ullman, Jeffrey. Data Structures and Algorithms. Ed. Addison-Wesley Pub. Co.1998. pp1-13, 29-50, 105-133, 205-218,253-257. 3. Drozdek Adam, Data Structures and Algorithms in C++, 2a. ed. Brooks Cole,USA, 2004. pp52-76, 215-300, 599- 644, 728. 4. Martin John C., Lenguajes formales y teoría de la Computación, 3ª. Ed., Mc Graw Hil, México, 2003. p86-110, 229-316. ESCUELA: Escuela Superior de Ingeniería Mecánica y Eléctrica. ASIGNATURA: Análisis de Algoritmos SEMESTRE: Quinto INSTITUTO POLITÉCNICO NACIONAL SECRETARÍA ACADÉMICA DIRECCIÓN DE ESTUDIOS PROFESIONALES EN INGENIERÍA Y CIENCIAS FÍSICO MATEMÁTICAS CARRERA: Ingeniería en Computación OPCIÓN: COORDINACIÓN: Academia de Computación DEPARTAMENTO: Ingeniería en Computación CLAVE: CLA027 CRÉDITOS: 7.5 VIGENTE: Agosto 2005 TIPO DE ASIGNATURA: Teórico-Practica MODALIDAD: Escolarizada TIEMPOS ASIGNADOS HORAS/SEMANA/TEORÍA: 3.0 HORAS/SEMANA/PRÁCTICA: 1.5 HORAS/SEMESTRE/TEORÍA: 54.0 HORAS/SEMESTRE/PRÁCTICA: 27.0 HORAS/TOTALES: 81.0 PROGRAMA ELABORADO O ACTUALIZADO POR: Academia de Computación de ESIME Culhuacan REVISADO POR: Subdirección Académica de ESIME Culhuacan APROBADO POR: Consejo Técnico Consultivo Escolar de ESIME Culhuacan. Ing. Ernesto Mercado Escutia AUTORIZADO POR: Comisión de Planes y Programas del Consejo General Consultivo del IPN INSTITUTO POLITÉCNICO NACIONAL SECRETARÍA ACADÉMICA DIRECCIÓN DE ESTUDIOS PROFESIONALES EN INGENIERÍA Y CIENCIAS FÍSICO MATEMÁTICAS ASIGNATURA: Análisis de Algoritmos CLAVE CLA027 HOJA: 2 DE 8 FUNDAMENTACIÓN DE LA ASIGNATURA El alumno resolverá problemas de procesamiento, diseñando algoritmos, aplicando técnicos de programación y estructuras de datos. Con la evolución de los lenguajes de programación, las computadoras y sus aplicaciones funcionan de acuerdo a la forma en que son programadas, por lo que, la asignatura de Análisis de Algoritmos que trata paso a paso y matemáticamente la eficiencia de los procesos de trabajo y la administración de los recursos y datos, se vuelve esencial en el área de la computación. Así que desde sus inicios su objetivo siempre ha consistido en el ahorro de espacio y tiempo para la ejecución de cálculos y ha dado origen a nuevas formas de resolver problemas de mayor dificultad. Además en todas las asignaturas consecuentes que tengan relación sobre el uso de las computadoras deberá existir el antecedente que permita resolver de una forma ordenada y metodológica la programación u organización, lo cual, se lleva a cabo mediante el Análisis de Algoritmos. Por consiguiente los ejemplos y técnicas comprendidas en el programa propuesto podrán ser aplicables a los materiales colaterales, y a las materias ulteriores como Sistemas Operativos, Sistemas Distribuidos y Programación Lógica entre otras. Las Matemáticas discretas, la Teoría de Autómatas y los Compiladores son antecedentes de esta asignatura. OBJETIVO DE LA ASIGNATURA El alumno resolverá algoritmos, aplicando técnicas de programación y estructuras de datos. Diseñando algoritmos resolverá problemas de procesamiento. INSTITUTO POLITÉCNICO NACIONAL SECRETARÍA ACADÉMICA DIRECCIÓN DE ESTUDIOS PROFESIONALES EN INGENIERÍA Y CIENCIAS FÍSICO MATEMÁTICAS ASIGNATURA: Análisis de Algoritmos CLAVE CLA027 HOJA: 3 DE 8 No. UNIDAD I NOMBRE: Introducción OBJETIVOS PARTICULARES DE LA UNIDAD El alumno modelará algoritmos. HORAS No. TEMA T E M A S T P EC CLAVE BIBLIOGRÁFICA 1.1 1.1.1 1.1.2 1.1.3 1.2 1.2.1 1.2.2 1.2.3 1.2.4 1.3 1.3.1 1.3.2 1.3.3 1.3.4 Algoritmos. Algoritmos, noción y conceptos. Origen y desarrollo de los algoritmos. Clasificación de los algoritmos. Importancia y uso de los algoritmos. Sintaxis y semántica del lenguaje (GLC). Secuenciación, selección e iteración Recursión. Tipo de datos, tipo de datos abstractos y estructura de datos. Solución de problemas. Conceptos. Clasificación de problemas. Técnicas para la solución de problemas. Problemas, algoritmos y programas Subtotal 1.5 4.5 6.0 12.0 3.0 3.0 1.5 4.5 6.0 1B, 3C, 5C ESTRATEGIA DIDÁCTICA Preparación de los temas por parte del alumno antes de la clase. Desarrollo de trabajos extra clase. Participación grupal para la solución de problemas en prácticas de laboratorio. Investigación de las definiciones formales. PROCEDIMIENTO DE EVALUACIÓN La evaluación será diagnóstica, formativa de aprendizaje constructivo y sumativa. - Evaluación de los conocimientos teóricos y aplicación de estos, mediante un examen departamental (40%). - Prácticas y problemas resueltos de acuerdo a la metodología en laboratorio (20%) - Investigación y trabajo extra clase (30%) - Participaciones (10%) INSTITUTO POLITÉCNICO NACIONAL SECRETARÍA ACADÉMICA DIRECCIÓN DE ESTUDIOS PROFESIONALES EN INGENIERÍA Y CIENCIAS FÍSICO MATEMÁTICAS ASIGNATURA: Análisis de Algoritmos CLAVE CLA027 HOJA: 4 DE 8 No. UNIDAD II NOMBRE: Teoría de la Computación OBJETIVOS PARTICULARES DE LA UNIDAD El alumno resolverá problemas de programación seleccionando el algoritmo adecuado, de acuerdo a las técnicas estudiadas y desarrolladas. HORAS No. TEMA T E M A S T P EC CLAVE BIBLIOGRÁFICA 2.1 2.1.1 2.1.2 2.1.3 2.1.4 2.1.5 2.2 2.2.1 2.2.2 2.2.3 2.3 2.3.1 2.3.2 2.3.2.1 2.3.2.2 2.3.2.3 2.3.3 2.3.4 2.3.5 2.3.6 Teoría de la computación. Tesis Church-Turing. Máquinas de Turing. Teorema de la recursión. Problemas. Complejidad de algoritmos. Introducción al análisis de algoritmos. Análisis de algoritmos. Importancia del análisis de algoritmos. Fundamentosmatemáticos. Análisis asintótico. Eficacia y eficiencia. Notación de la complejidad. Introducción a la complejidad de algoritmos. Notación O. Otras notaciones. Análisis de estructuras de control, secuencias, ciclos y llamadas. Análisis de estructuras de control, secuencias, ciclos y llamadas recursivas. Técnicas de análisis. Relaciones de recurrencia. Subtotal 3.0 3.0 9.0 12.0 3.0 3.0 3.0 9.0 9.0 1B, 2C, 3C ESTRATEGIA DIDÁCTICA Preparación de los temas por parte del alumno antes de la clase con la guía del profesor. Elaboración grupal de presentaciones en power point con la explicación de las técnicas estudiadas. Investigación de las definiciones formales actuales. PROCEDIMIENTO DE EVALUACIÓN La evaluación será diagnóstica, formativa de aprendizaje constructivo y sumativa. - Evaluación de los conocimientos teóricos y aplicación de estos, mediante un examen departamental (40%). - Prácticas y problemas resueltos de acuerdo a la metodología en laboratorio (30%) - Investigación y trabajo extra clase (10%) - Trabajo en grupo (20%) ASIGNATURA: Análisis de Algoritmos CLAVE CLA027 HOJA: 5 DE 8 INSTITUTO POLITÉCNICO NACIONAL SECRETARÍA ACADÉMICA DIRECCIÓN DE ESTUDIOS PROFESIONALES EN INGENIERÍA Y CIENCIAS FÍSICO MATEMÁTICAS No. UNIDAD III NOMBRE: Tipos de Datos Abstractos y Estructuras de Datos OBJETIVOS PARTICULARES DE LA UNIDAD El alumno seleccionando la estructura de los datos abstractos, solucionará problemas en la programación de algoritmos. HORAS No. TEMA T E M A S T P EC CLAVE BIBLIOGRÁFICA 3.1 3.1.1 3.1.2 3.1.3 3.1.4 3.2 3.2.1 3.2.2 3.2.3 3.2.4 3.3 3.3.1 3.3.2 3.3.3 3.3.3.1 3.3.3.2 3.3.3.3 3.3.3.4 Estructuras de datos y diseño de algoritmos. Estructura de datos lineales. Estructura de datos no-lineales. Procedimientos recursivos. Estructura de datos recursivos. Tipo de datos abstractos. Registros, arreglos, conjuntos. Pilas, colas y listas. Diccionarios. Árboles. Operaciones con las estructuras de datos Inserción y eliminación. Búsquedas. Ordenación e intercalamiento. Método del mínimo. Método de la burbuja. Método del Quicksort. Método de mezclas. 6.0 6.0 3.0 15.0 3.0 3.0 1.5 7.5 3.0 2C, 3C, 6C ESTRATEGIA DIDÁCTICA Preparación de los temas por parte del alumno antes de la clase bajo la guía del profesor. Desarrollo de trabajos extra clase y prácticas de laboratorio sobre los métodos estudiados. Elaboración grupal de presentaciones en power point con la explicación por parte de alumnos de los métodos estudiados. PROCEDIMIENTO DE EVALUACIÓN La evaluación será diagnóstica, formativa de aprendizaje constructivo y sumativa. - Evaluación de los conocimientos teóricos y aplicación de estos, mediante un examen departamental (40%). - Prácticas y problemas resueltos de acuerdo a la metodología en laboratorio (30%) - Trabajo extra clase (10%) - Trabajo en grupo (20%) ASIGNATURA: Análisis de Algoritmos CLAVE CLA027 HOJA: 6 DE 8 No. UNIDAD IV NOMBRE: Técnicas, Diseño y Análisis de los Algoritmos, Algoritmos Geométricos. OBJETIVOS PARTICULARES DE LA UNIDAD INSTITUTO POLITÉCNICO NACIONAL SECRETARÍA ACADÉMICA DIRECCIÓN DE ESTUDIOS PROFESIONALES EN INGENIERÍA Y CIENCIAS FÍSICO MATEMÁTICAS El alumno resolverá problemas sobre algoritmos donde la solución es más adecuada, eficiente y óptima. HORAS No. TEMA T E M A S T P EC CLAVE BIBLIOGRÁFICA 4.1 4.1.1 4.1.2 4.1.3 4.1.4 4.1.5 4.2 4.2.1 4.2.2 4.2.3 4.3 4.3.1 4.3.2 4.3.3 4.3.4 4.3.5 4.3.6 4.3.7 4.4 4.4.1 4.4.2 4.4.3 4.4.4 Técnicas del diseño y análisis para la optimización de los algoritmos. Relaciones de recurrencia. Programación dinámica. Backtracking. Divide y vencerás. El problema de la mochila. Algoritmos geométricos. Búsqueda geométrica. Inclusión de polígonos. Problemas de intersecciones. Algoritmos de grafos. Definición y clasificación de los grafos. Representación en la computadora de los grafos. Algoritmo de Dijkstra. Algoritmo de Euler. Algoritmo de camino mas corto. Grafos conexos. Graficas en computadora. Análisis asintótico de las funciones. Complejidad de los algoritmos. Acotación de problemas. Transformación de problemas. Cotas superiores e inferiores. Subtotal 3.0 3.0 3.0 3.0 3.0 15.0 1.5 1.5 1.5 1.5 6.0 3.0 3.0 1B, 2C, 4B, 5C ESTRATEGIA DIDÁCTICA Preparación de los temas por parte del alumno antes de la clase. Desarrollo de trabajos extra clase y prácticas de laboratorio sobre los algoritmos estudiados. Elaboración grupal sobre alguna aplicación real de alguna solución aprendida. PROCEDIMIENTO DE EVALUACIÓN La evaluación será formativa de aprendizaje constructivo y sumativa de los siguientes aspectos: - Participación grupal en la solución de un problema real de acuerdo a eficiencia y optimización (30 %) - Evaluación de los conocimientos teóricos y aplicaciones mediante un examen departamental (40%). - Desarrollo de trabajos extra clase y prácticas de laboratorio. (30%) INSTITUTO POLITÉCNICO NACIONAL SECRETARÍA ACADÉMICA DIRECCIÓN DE ESTUDIOS PROFESIONALES EN INGENIERÍA Y CIENCIAS FÍSICO MATEMÁTICAS ASIGNATURA: Análisis de Algoritmos CLAVE: CLA027 HOJA: 7 DE 8 RELACIÓN DE PRÁCTICAS PRACT. No. NOMBRE DE LA PRÁCTICA UNIDAD DURACIÓN LUGAR DE REALIZACIÓN 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Grafo dirigido Grafo TAD Flujo Dijkstra Algoritmo Ford-Fulkerson Problema de la suma y cifrado de Merckle-Hellman Cifrado de Merckle-Hellman Grafos con incidencias Algoritmo de exploración Algoritmo BFS Algoritmo DFS Combinaciones Recorridos Multiplicación de números grandes Multiplicación de Karatsuba Comparaciones de rendimiento Algoritmos N(p) completos I I I I II II II III III III III III IV IV IV IV Total 3.0 1.5 1.5 1.5 3.0 3.0 3.0 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 27 Todas las prácticas se llevaran a cabo en el Laboratorio de Cómputo. INSTITUTO POLITÉCNICO NACIONAL SECRETARÍA ACADÉMICA DIRECCIÓN DE ESTUDIOS PROFESIONALES EN INGENIERÍA Y CIENCIAS FÍSICO MATEMÁTICAS ASIGNATURA: ANÁLISIS DE ALGORITMOS CLAVE CLA027 HOJA: 8 DE 8 PERÍODO UNIDAD PROCEDIMIENTO DE EVALUACIÓN 1 2 3 4 I II III IV Evaluación de los conocimientos teóricos y aplicación de estos, mediante un examen departamental (40%). Prácticas y problemas resueltos de acuerdo a la metodología en laboratorio (20%) Investigación y trabajo extraclase (30%) Participaciones (10%) Evaluación de los conocimientos teóricos y aplicación de estos, mediante un examen departamental (40%). Prácticas y problemas resueltos de acuerdo a la metodología en laboratorio (30%) Investigación y trabajo extra clase (10%) Trabajo en grupo (20%) Evaluación de los conocimientos teóricos y aplicación de estos, mediante un examen departamental (40%). Prácticas y problemas resueltos de acuerdo a la metodología en laboratorio (30%) Trabajo extra clase (10%) Trabajo en grupo (20%) Participación grupal en la solución de un problema real de acuerdo a eficiencia y optimización (30 %) Evaluación de los conocimientos teóricos y aplicaciones mediante un examen departamental (40%). Desarrollo de trabajos extra clase y prácticas de laboratorio. (30%) CLAVE B C BIBLIOGRAFÍA 1 2 3 4 5 6 X X X X X X Abellanas M. , Lodares D., Análisis de Algoritmos y teoría de grafos, Macrobit Editores, México, 1998. p1-256. Aho, Alfred, Hopcroft, John and Ullman, Jeffrey. Data structures and Algorithms. Ed. Addison-Wesley Pub. Co. 1998.pp1-13, 29-50, 105-133, 205-218,253-257. Brassard Giles, Bratley P, Fundamentos de Algoritmia, Prentice Hall, 1997 pp42-64, 103-248 Drozdek Adam, Data Structures and Algorithms in C++, 2a. ed. Brooks Cole,USA, 2004. pp52-76, 215-300, 599-644, 728. Knuth Donald E., The Stanford Graphbase : A Platform for Combinatorial Computing, Addison-Wesley, 1993. pp94-112, 148-167. Martin John C., Lenguajes formales y teoría de la Computación, 3ª. Ed., Mc Graw Hil, México, 2003. pp86-110, 229-316. INSTITUTO POLITÉCNICO NACIONAL SECRETARÍA ACADÉMICA DIRECCIÓN DE ESTUDIOS PROFESIONALES EN INGENIERÍA Y CIENCIAS FÍSICO MATEMÁTICAS PERFIL DOCENTE POR ASIGNATURA 1. DATOS GENERALES ESCUELA: Escuela Superior de Ingeniería Mecánica y Eléctrica Unidad Culhuacan. CARRERA: Ingeniería en Computación SEMESTRE : Quinto ÁREA: BÁSICAS C. INGENIERÍA D. INGENIERÍA C. SOC. y HUM. ACADEMIA: Computación ASIGNATURA: Análisis de Algoritmos ESPECIALIDAD Y NIVEL ACADÉMICO REQUERIDO: Licenciatura en Ingeniería o Ciencias Físico Matemáticas 2. OBJETIVOS DE LA ASIGNATURA: El alumno resolverá problemas de procesamiento, diseñando algoritmos, aplicando técnicos de programación y estructuras de datos. 3. PERFIL DOCENTE: CONOCIMIENTOS EXPERIENCIA PROFESIONAL HABILIDADES ACTITUDES Experiencia en programación de alto y bajo nivel, conocimientos teóricos de Teoría de Autómatas, Análisis de Algoritmos y Estructuras de Datos. Haber impartido clases, o Formación pedagógica. Administración de redes. Programación en algún lenguaje de computación. Dominio de la asignatura. Manejo de grupos. Comunicación (Transmisión del conocimiento). Capacidades de análisis y síntesis. Motivación al alumno. Tener vocación por la docencia. Honestidad. Ejercicio de la critica fundamentada. Respeto (buena relación maestro-alumno). Tolerancia. Ética. Responsabilidad científica. Espíritu de colaboración. Superación docente y profesional. Compromiso social ELABORÓ REVISÓ AUTORIZÓ ______________________ ______________________ ____________________ Ing. Jorge F. Veloz Ortiz M. en C. Alberto Paz Gutiérrez Ing. Ernesto Mercado Escutia PRESIDENTE DE LA ACADEMIA DE SUBDIRECTOR ACADÉMICO. DIRECTOR COMPUTACIÓN FECHA: Agosto de 2005
Compartir