Última revisión realizada: 20/05/2022

Presentación

En la asignatura de Informática Teórica se busca que el alumno se inicie en cuestiones como la definición y programación de una máquina de Turing, los lenguajes recursivos, lenguajes recursivamente numerables y no recursivamente enumerables, los problemas indecidibles y los problemas intratables.

Es una asignatura de marcado carácter teórico, pero fundamental en la formación de un ingeniero informático, ya que el estudio de fondo de las máquinas de Turing (que pueden resolver el mismo tipo de problemas que cualquier computador) tiene interés por sí solo, pero además esta disciplina tiene aplicaciones evidentes en el campo de los traductores de lenguaje, en los que resulta necesario saber si una cadena dada pertenece a un lenguaje determinado o no.

La cuestión de los problemas intratables también es esencial para un ingeniero informático, ya que tienen aplicaciones en campos como la logística, criptografía, gestión de redes, gestión de transporte, etc. También se estudian otros problemas de la Teoría de la Complejidad Computacional y se termina el curso con una introducción a las redes neuronales artificiales.

Competencias

A continuación se enumeran las competencias que adquirirás al cursar esta asignatura:

Competencias básicas

• CB1: Que los estudiantes hayan demostrado poseer y comprender conocimientos en un área de estudio que parte de la base de la educación secundaria general, y se suele encontrar a un nivel que, si bien se apoya en libros de texto avanzados, incluye también algunos aspectos que implican conocimientos procedentes de la vanguardia de su campo de estudio.
• CB2: Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio.
• CB3: Que los estudiantes tengan la capacidad de reunir e interpretar datos relevantes (normalmente dentro de su área de estudio) para emitir juicios que incluyan una reflexión sobre temas relevantes de índole social, científica o ética.
• CB4: Que los estudiantes puedan transmitir información, ideas, problemas y soluciones a un público tanto especializado como no especializado.
• CB5: Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía.

Competencias generales

• CG08: Conocimiento de las materias básicas y tecnologías, que capaciten para el aprendizaje y desarrollo de nuevos métodos y tecnologías, así como las que les doten de una gran versatilidad para adaptarse a nuevas situaciones.

Competencias específicas

• CC01: Capacidad para tener un conocimiento profundo de los principios fundamentales y modelos de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar, y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática.

Competencias transversales

• CT1: Capacidad de innovación y flexibilidad en entornos nuevos de aprendizaje como es la enseñanza on-line.
• CT2: Conocer, y utilizar con habilidad, los mecanismos básicos de uso de comunicación bidireccional entre profesores y alumnos, foros, chats, etc.
• CT3: Utilizar las herramientas para presentar, producir y comprender la información que les permita transformarla en conocimiento.

Contenidos

Tema 1. Conceptos matemáticos utilizados
Introducción a la lógica proposicional
Teoría de relaciones
Conjuntos numerables y no numerables

Tema 2. Lenguajes y gramáticas formales
Introducción
Lenguajes y gramáticas formales

Tema 3. Introducción a las máquinas de Turing
Problema de decisión
La máquina de Turing

Tema 4. Extensiones para las máquinas de Turing
Técnicas de programación para las máquinas de Turing
Extensiones para las máquinas de Turing

Tema 5. Máquinas de Turing restringidas. Computadoras
Máquinas de Turing restringidas
Máquinas de Turing y computadoras

Tema 6. Indecibilidad
Lenguaje no recursivamente enumerable
Un problema indecidible recursivamente enumerable

Tema 7. Otros problemas indecibles
Problemas indecidibles para las máquinas de Turing
Problema de correspondencia de Post (PCP)

Tema 8. Problemas intratables
Las clases P y NP
Un problema NP completo

Tema 9. Problemas intratables
Problema de la satisfacibilidad restringido
Otros problemas NP completos

Tema 10. Problemas co-NP y PS
Complementarios de los lenguajes de NP
Problemas resolubles en espacio polinómico
Problemas PS completos

Tema 11. Clases de lenguajes basados en la aleatorización
Modelo de la MT con aleatoriedad
Las clases RP y ZPP
Prueba de primalidad
Complejidad de la prueba de primalidad

Tema 12. Otras clases y gramáticas
Autómatas finitos probabilísticos
Autómatas celulares
Células de McCullogh y Pitts
Gramáticas de Lindenmayer

Tema 13. Sistemas avanzados de cómputo
Computación con membranas: sistemas P
Computación con ADN
Computación cuántica

Metodología

Las actividades formativas de la asignatura se han elaborado con el objetivo de adaptar el proceso de aprendizaje a las diferentes capacidades, necesidades e intereses de los alumnos.

Las actividades formativas de esta asignatura son las siguientes:

• Trabajos y Lecturas. Se trata de actividades de diferentes tipos: reflexión, análisis de casos, prácticas, etc. Además de análisis de textos relacionados con diferentes temas de la asignatura.
• Participación en eventos. Son eventos programados todas las semanas del cuatrimestre: sesiones presenciales virtuales, foros de debate, test.
• Laboratorios. Actividad práctica que se realiza en tiempo real e interactuando con otros alumnos. En el laboratorio los estudiantes tendrán que desarrollar los ejercicios propuestos en un entorno de simulación online. Los estudiantes contarán en todo momento con el apoyo de un tutor de laboratorio, que ayudará al
  alumno a desarrollar su actividad. El tutor de laboratorio podrá asignar grupos de alumnos para que, de forma
  colaborativa, alcancen los resultados solicitados. Este tipo de actividad posee un peso considerable en la
  evaluación continua del alumno, por lo que, a pesar de no ser obligatoria su realización, se recomienda firmemente la participación en los mismos.

En la programación semanal puedes consultar cuáles son las actividades concretas que tienes que realizar en esta asignatura.

Estas actividades formativas prácticas se completan, por supuesto, con estas otras:

• Estudio personal.
• Tutorías. Las tutorías se pueden articular a través de diversas herramientas y medios. Durante el desarrollo de la asignatura, el profesor programa tutorías en días concretos para la resolución de dudas de índole estrictamente académico a través de las denominadas “sesiones de consultas”. Como complemento de estas sesiones se dispone también del foro “Pregúntale al profesor de la asignatura” a través del cual se articulan algunas preguntas de alumnos y las correspondientes respuestas en el que se tratan aspectos generales de la asignatura. Por la propia naturaleza de los medios de comunicación empleados, no existen horarios a los que deba ajustarse el alumno.
• Examen final presencial u online

Las horas de dedicación a cada actividad se detallan en la siguiente tabla:

Bibliografía

Bibliografía básica

Los textos necesarios para el estudio de la asignatura han sido elaborados por UNIR y están disponibles en formato digital para consulta, descarga e impresión en el aula virtual.

En algunos temas deberás estudiar el siguiente manual de la asignatura:

• Hopcroft, J.E., Motwani, R. y Ullman, J.D. (2008). Introducción a la teoría de autómatas, lenguajes y computación (3ª ed.).
  España: Addison-Wesley.
  ISBN: 8478290567

Además, en varios temas deberás estudiar la siguiente bibliografía:

Temas 1, 2, 12 y 13

• Alfonseca, E., Alfonseca, M.y Moriyón, R. (2007). Teoría de autómatas y lenguajes formales (315-341 y 347 y 371).
  Madrid: Mc Graw Hill
  ISBN: 9788448156374

Bibliografía complementaria

Fernández-Ruiz, P. (2016). Desarrollo de una aplicación para simulación de máquinas de Turing. Cantabria: Universidad de Ciencias. Recuperado de https://repositorio.unican.es/xmlui/bitstream/handle/10902/9192/Fernandez%20Ruiz%20Pablo.pdf?sequence=1&isAllowed=y

Hofstadter, D. (2007). Gödel, Escher, Bach: un eterno y grácil bucle (pp. 238-248). Barcelona: Tusquets

Luque, F. M. (2017). El Lenguaje Natural como Lenguaje Formal. Recuperado de https://arxiv.org/abs/1703.04417

Penrose, J. (1989). ¿Cuántos números reales hay? En La mente nueva del emperador (pp. 81-84). México: Fondo de Cultura Económica.

Evaluación y calificación

El sistema de calificación se basa en la siguiente escala numérica:

La calificación se compone de dos partes principales:

El examen se realiza al final del cuatrimestre y es de carácter PRESENCIAL U ONLINE y OBLIGATORIO. Supone el 60% de la calificación final y para que la nota obtenida en este examen se sume a la nota final, es obligatorio APROBARLO.

La evaluación continua supone el 40% de la calificación final. Este 40% de la nota final se compone de las calificaciones obtenidas en las diferentes actividades formativas llevadas a cabo durante el cuatrimestre.

Ten en cuenta que la suma de las puntuaciones de las actividades de la evaluación continua permite que realices las que prefieras hasta conseguir el máximo puntuable mencionado en la programación semanal. En ella se detalla la calificación máxima de cada actividad o evento concreto puntuables.

Para aprobar la asignatura será necesario aprobar cada una de las partes.

El sistema de evaluación de la asignatura es el siguiente:

Profesorado

Jordi Canela Sánchez

Formación: Licenciado en Matemáticas por la Universidad de Barcelona, Máster en Matemática Avanzada y Profesional por la Universidad de Barcelona. Doctorado en Matemáticas por la Universidad de Barcelona.

Experiencia: Profesor en la Escuela Superior de Ingeniería y Tecnología en la UNIR. Anteriormente: Investigador postdoctoral en Université Paul Sabatier (Toulouse, 2 años), profesor invitado en el IMPAN (Varsovia, 4 meses), investigador predoctoral dentro del proyecto europeo CODY (Kiel, Alemania, 1 año).

Líneas de investigación: Sistemas dinámicos en dimensión baja, sistemas dinámicos en variable compleja y análisis de métodos numéricos

Orientaciones para el estudio

Obviamente, al tratarse de formación on-line puedes organizar tu tiempo de estudio como desees, siempre y cuando vayas cumpliendo las fechas de entrega de actividades, trabajos y exámenes. Nosotros, para ayudarte, te proponemos los siguientes pasos:

1. Desde el Campus virtual podrás acceder al aula virtual de cada asignatura en la que estés matriculado y, además, al aula virtual de Lo que necesitas saber antes de empezar. Aquí podrás consultar la documentación disponible sobre cómo se utilizan las herramientas del aula virtual y sobre cómo se organiza una asignatura en la UNIR y también podrás organizar tu plan de trabajo personal con tu profesor-tutor.
2. Observa la programación semanal. Allí te indicamos qué parte del temario debes trabajar cada semana.
3. Ya sabes qué trabajo tienes que hacer durante la semana. Accede ahora a la sección Temas del aula virtual. Allí encontrarás el material teórico y práctico del tema correspondiente a esa semana.
4. Comienza con la lectura de las Ideas clave del tema. Este resumen te ayudará a hacerte una idea del contenido más importante del tema y de cuáles son los aspectos fundamentales en los que te tendrás que fijar al estudiar el material básico. Lee siempre el primer apartado, ¿Cómo estudiar este tema?, porque allí te especificamos qué material tienes que estudiar. Consulta, además, las secciones del tema que contienen material complementario (Lo + recomendado y + Información).
5. Dedica tiempo al trabajo práctico (sección Actividades y Test). En la programación semanal te detallamos cuáles son las actividades correspondientes a cada semana y qué calificación máxima puedes obtener con cada una de ellas.
6. Te recomendamos que participes en los eventos del curso (sesiones presenciales virtuales, foros de debate…). Para conocer la fecha concreta de celebración de los eventos debes consultar las herramientas de comunicación del aula vitual. Tu profesor y tu profesor-tutor te informarán de las novedades de la asignatura.

Recuerda que en el aula virtual de Lo que necesitas saber antes de empezar puedes consultar el funcionamiento de las distintas herramientas del aula virtual: Correo, Foro, Sesiones presenciales virtuales, Envío de actividades, etc.