1. Identificación del curso 1.1 Escuela / Departamento: Ciencias Naturales e Ingeniería 1.3 Programa: Facultad de Ingeniería de Sistemas 1.5 Carrera: Ingeniería de Sistemas 1.7 Nivel: Pregrado
1.8 Curso: Estructura de Datos 1.9 Código: MATE00108 1.10 Área de Formación: 1.11 Línea de Conocimiento: Estudios Profesionales – EP Matemáticas – MATE 1.12 Clase: 1.13 Modalidad: Segundo Semestre Presencial 1.14 Periodo Académico: Segundo Periodo 2010 1.15 Intensidad Horaria Semanal: 5 1.16 Créditos: 3 1.17 Horas Presenciales: 5 1.18 Horas de Estudio Independiente:180 1.19 Profesor: Juan Carlos García Ojeda, MSc., Ing.
1.20 ID: 100000064
2. Justificación La Teoría de la Computación es el pilar fundamental que subyace a la máquina: la Computadora. Por lo tanto ésta centra su interés en los modelos matemáticos que formalizan el concepto de hacer un cómputo (cálculo) y la clasificación de problemas de acuerdo a su grado de dificultad.
3. Articulación en el Plan de Estudios 3.1 Pre-requisitos: Matemática Discretas 3.3 Co-requisitos: Lógica y Argumentación
3.2 Código: MATE00107 3.4 Código: FILO00109
3.5 Descripción de Conocimientos y Habilidades requeridos para el curso • El estudiante está en la capacidad de entender los conceptos y técnicas de la Teoría de la Computación y explota el desarrollo de habilidades de lectura y escritura de pruebas matemáticas formales
3.6 Relación con el Núcleo Integrador Como parte del núcleo integrador, el estudiante está en la capacidad de desarrollar soluciones en computador para los temas originados en el núcleo integrador.
4. Competencias 4.1 Competencia Institucional: Ser Ciudadano 4.2 Específicas 4.3 Indicadores de Competencia Competencia “Ser Disciplinado”: El Estudiante: •
•
•
•
•
Madura en el desarrollo del pensamiento algorítmico del estudiante para aplicarlo a la resolución de problemas utilizando dispositivos computacionales como herramienta. Adquiera capacidades mentales (funciones cognitivas y operaciones mentales) que permitan alcanzar niveles de abstracción, complejidad, sistematización y divergencia. Desarrolla el pensamiento matemático que permite interpretaciones lógicas y sistémicas de la realidad. Desarrolla el pensamiento flexible e innovador para el ejercicio de actividades de modelamiento. Adquiera la capacidad de traducir modelos a soluciones de computadores.
Competencia “Ser Ciudadano”: •
Refuerza la responsabilidad por el propio aprendizaje y a las actitudes del estudiante hacia si mismo como una persona en la búsqueda de su propio desarrollo como profesional.
•
Comprende los conceptos de computación
•
Comprende y aplica pruebas formales: Deductiva, Inductiva y por Contradicción.
•
Comprende y aplica el concepto de Autómata Finito: Determinista, No Determinista.
•
Comprende y aplica el concepto de Lenguajes y Expresiones Regulares.
•
Comprende las propiedades de los Lenguajes Regulares
•
Comprende y aplica el concepto de Lenguajes y Gramáticas Libres de Contexto
•
Comprende y aplica el concepto de Autómatas de Pila
•
Comprende las propiedades de los Lenguajes Libres de Contexto
•
Comprende y aplica el concepto de Maquinas de Turing.
•
Reconoce cuando un problema no es decidible e intractable.
5. Contenidos (Unidades y Temas) Unidad Tema • Horarios • Laboratorios • Trabajos del Curso 1 . Introducción • Texto del Curso • Lecturas Recomendadas • Página Web del Curso • Conjuntos 2 . Teoría de • Operaciones sobre Conjuntos Conjuntos e • Pruebas Deductivas Inducción • Pruebas Inductivas Matemática • Pruebas por Contradicción • Autómata Determinístico 3. Autómata • Autómata No Determinístico Finito • Autómata Finito con ε- Transiciones 4. Expresiones • Expresiones Regulares • Expresiones Regulares y Autómatas Finitos Regulares 5. Gramáticas • Gramáticas Libres de Contexto Libres de • Árboles Contexto • Definición de Autómatas de Pilas • Lenguajes de un Autómata de Pila 6.Automatas de • Equivalencia de un Autómata de Pila y una Pila Gramática Libre de Contexto • Autómata de Pila Determinístico • Problemas que el Computador no puede resolver 7. Máquinas de • La Maquina de Turing Turing • Técnicas de Programación de Maquinas de Turing • Maquinas de Turing y Computadoras 8. Decibilidad y Tractabilidad
6. Actividades: 6.1 Del Docente:
•
Lenguajes que no es Recursible Enumerable (RE)
•
Lenguajes que es RE
•
Problemas P y NP
Situar al estudiante en la práctica de la profesión. • Introducir los conceptos y ejemplos que permitan la formalización de los conceptos relacionados a relacionados a la teoría de la computación • Analizar, diseñar e implementar soluciones a los ejemplos introducidos. • Elaborar ejercicios tal que los estudiantes apliquen los conceptos aprendidos en situaciones de la vida real. • Analizar, diseñar e implementar la solución a los ejercicios propuestos de forma tal que estos propicien el trabajo independiente del estudiante logrando en este el desarrollo del auto aprendizaje. • Atender las inquietudes de los estudiantes 6.2 De los Estudiantes: • Estudio del material correspondiente a: o Teoría de la Computación. o Lenguaje de Programación Java. o Ejemplos Propuestos o Ejemplos Resueltos o Ejercicios Propuestos. o Ejercicios Resueltos o Implementación en computador de los ejemplos y ejercicios propuestos. 6.3 Del Equipo Docente: • Promover el desarrollo de actividades de desarrollo de la lógica y habilidades matemáticas abstractas que convoquen a los estudiantes y les estimulen al desarrollo de estas. •
7. Estrategias de evaluación La verificación de desempeños se hará a través de: • • • •
Las soluciones propuestas deben demostrar ser efectivas Se valora tanto la calidad lógica de la solución como la aplicación de prácticas sanas de programación. Se valora el cumplimiento de las tareas propuestas en el término estipulado. Se valora la claridad en la escritura de programas.
8. Instrumentos de Registro • Dos Exámenes Ponderados de 0.0 a 5.0 • Desarrollo de Tareas (Cada dos semanas) 9. Recursos 9.1 Bibliografía Básica • Hopcroft, John E.Introducción a la teoría de autómatas, lenguajes y computación006.3 / H791t 2002 9.2 Bibliografía Complementaria
• Brookshear, J. GlennTeoría de la computación006.3 / B873tc 1993 • Hopcroft, John E.Introduction to automata theory, languages, and computation006.3 / H791ic 1979 • García, PedroTeoría de autómatas y lenguajes formales511.3 / T3142001 • Hopcroft, John E.Introduction to automata theory, languages, and computation006.3 / H791int 2001 • Hopcroft, John E.Introducción a la teoría de autómatas, lenguajes y computación006.3 / H791in 1998B 9.3 Audiovisuales • Video-Beam 9.4. Enlaces en Internet • http://fis.unab.edu.co/docentes/jgarciao/Index.html 9.5. Software • Java Versión 1.5.0 ó superior. Sun microsystems • Internet Explorer 7.0 ó Superior • Sistema Operativo Windows XP ó Superior.