## 30214 - Computer Science Theory

### Syllabus Information

2019/20
Subject:
30214 - Computer Science Theory
Faculty / School:
110 - Escuela de Ingeniería y Arquitectura
326 - Escuela Universitaria Politécnica de Teruel
Degree:
439 - Bachelor's Degree in Informatics Engineering
443 - Bachelor's Degree in Informatics Engineering
ECTS:
6.0
Year:
2
Semester:
First semester
Subject Type:
Basic Education
Module:
---

### 4.1. Methodological overview

The learning process that is designed for this course is based on:

• The presentation of the contents of the subject in lectures in the classroom
• Solving problems in class.
• Personal study of the subject by students.
• The development of lab assignments by students, guided by teachers in the laboratory
• Solving simple problems of increasing difficulty proposed by the teachers.

Keep in mind that the subject has both theoretical and practical orientation. Therefore, the learning process emphasizes both student attendance at lectures, as in the practical work in the laboratory, in solving simple problems of increasing difficulty, and individualized study.

The course includes the following learning tasks:

• In classes taught in the classroom, the program of the course will be presented.
• In classes of case studies, problems will be solved using the concepts and techniques presented in the course syllabus.
• Practical work sessions will be held in a computer lab.

### 4.3. Syllabus

The course will address the following topics. The course topics are organized around three pillars:

(1) Theory of formal languages, with an emphasis on regular languages and  context-free languages;

(2) Fundamentals of Computability, to narrow what problems can be solved algorithmically;

(3) Fundamentals of Algorithmic Complexity, to define what is the efficiency of an algorithmic solution and the number of resources an algorithm needs.

• Topic 0: Preliminaries
Mathematical Preliminaries: sets, functions, relations, induction.
Definition of alphabet and language.

• Topic 1: Regular Languages
Regular expressions and regular languages.
Deterministic finite automata (DFA) and nondeterministic finite automata (nDFA)
Equivalence between DFA and nDFA.
Properties of regular languages. Pumping Lemma

• Topic 2: Context-Free Languages
Grammars and context-free languages.
Pushdown automata.
Simplification of grammars.
Properties of context-free languages. Pumping Lemma

• Topic 3: Computability
Turing machines.
Languages and Turing machines. Church-Turing thesis.
Decidability. Non-decidable problems.

• Topic 4: Complexity
The classes of languages P and EXP.
The classes of languages NP and NP-complete.

The concepts, methods and tools of the above paragraphs are illustrated through examples, as realistic as possible, within the areas of computer security, cryptography, natural language processing and compression of information.

### 4.4. Course planning and calendar

Scheduling of sessions and presentation of works

The schedule of the course will be defined by the School in the academic calendar of the corresponding academic year.

Student Work

The dedication of the student to achieve the learning outcomes in this course is estimated at 150 hours distributed as follows:

In the School of Engineering and Architecture of Zaragoza:

•     56 hours, approximately, of classroom activities (lectures, problems and laboratory)
•     40 hours of teamwork
•     51 hours of personal study (study booktexts and lecture notes, problem solving, preparing lessons and lab assignments)
•     3 hours deoted to the written final exam

At the Polytechnic University School of Teruel:

60 hours of classroom activities (lectures, problems and laboratory)

30 hours of teamwork

55 hours of personal study (study booktexts and lecture notes, problem solving, preparing lessons and lab assignments)

5 hours of evaluation activities

## 30214 - Teoría de la computación

### Información del Plan Docente

2019/20
Asignatura:
30214 - Teoría de la computación
110 - Escuela de Ingeniería y Arquitectura
326 - Escuela Universitaria Politécnica de Teruel
Titulación:
Créditos:
6.0
Curso:
2
Periodo de impartición:
Primer semestre
Clase de asignatura:
Formación básica
Materia:

### 1.1. Objetivos de la asignatura

#### La asignatura y sus resultados previstos responden a los siguientes planteamientos y objetivos:

Los objetivos de la asignatura son fundamentalmente de cuatro tipos:

1. Capacitar al estudiante para que pueda abstraer problemas a resolver mediante un computador.
2. Conocer los modelos de cálculo básicos en los que se basan los computadores actuales e identificar el más adaptado a cada problema.
3. Asimilar paradigmas de problemas bien estudiados en el contexto de la informática para que pueda reducirlos o adaptarlos a los problemas que se le planteen.
4. Conocer las capacidades y limitaciones de la resolución automática de problemas y evaluar los recursos necesarios para ello.

### 1.2. Contexto y sentido de la asignatura en la titulación

La Teoría de la Computación es una asignatura de Formación Básica impartida en el segundo curso de la titulación. Esta particular ubicación temporal permite que los estudiantes puedan aplicar en todas las asignaturas de la titulación los conocimientos adquiridos en esta asignatura: decidibilidad, teoría de lenguajes y complejidad. Estas herramientas formarán parte del conjunto de habilidades y métodos fundamentales que el ingeniero informático aplicará en su trabajo.

### 1.3. Recomendaciones para cursar la asignatura

Es conveniente que el alumno haya cursado las asignaturas de Programación I (1er Cuatrimestre) y Matemática Discreta (2º Cuatrimestre).

### 2.1. Competencias

#### Al superar la asignatura, el estudiante será más competente para...

Resolver problemas y tomar decisiones con iniciativa, creatividad y razonamiento crítico.

Comunicar y transmitir conocimientos, habilidades y destrezas en castellano.

Usar las técnicas, habilidades y herramientas de la Ingeniería necesarias para la práctica de la misma.

Aprender de forma continuada y desarrollar estrategias de aprendizaje autónomo.

Aplicar las tecnologías de la información y las comunicaciones en la Ingeniería.

Comprender y dominar los conceptos básicos de matemática discreta, lógica, algoritmia y complejidad computacional, y su aplicación para la resolución de problemas propios de la ingeniería.

Usar ordenadores, sistemas operativos, bases de datos y programas informáticos con aplicación en ingeniería.

#### El estudiante, para superar esta asignatura, deberá demostrar los siguientes resultados...

Conoce los modelos de cálculo básicos.

Encuentra el modelo de cálculo más simple para cada problema.

Aplica los formalismos de la teoría de lenguajes en la resolución de problemas.

Conoce las limitaciones de la resolución automática de problemas.

Identifica problemas irresolubles básicos como el problema de parada o el de detección de virus.

Analiza el coste en tiempo y memoria de un algoritmo.

Identifica problemas que requieren demasiados recursos de cálculo.

### 2.3. Importancia de los resultados de aprendizaje

El conjunto de los resultados de aprendizaje se puede resumir diciendo que el alumno será capaz de abstraer un problema a resolver mediante un computador identificando el modelo de cálculo más adecuado, reduciéndolo a problemas conocidos e identificando las limitaciones de dicha resolución y los recursos necesarios para ella. Haber aprendido a hacerlo bien y con eficiencia es de vital importancia en el contexto de unos estudios de Ingeniería Informática de los que uno de sus pilares es la resolución de problemas.

### 3.1. Tipo de pruebas y su valor sobre la nota final y criterios de evaluación para cada prueba

#### El estudiante deberá demostrar que ha alcanzado los resultados de aprendizaje previstos mediante las siguientes actividades de evaluacion

En la Escuela de Ingeniería y Arquitectura de Zaragoza:

Trabajo de laboratorio (30%). Por una parte, se evaluará el guión previo donde el estudiante deberá haber identificado las necesidades de información para resolver los problemas planteados y su utilización en la resolución. También se valorará la capacidad crítica a la hora de seleccionar alternativas y el grado de justificación de la solución alcanzada.
Se evaluará, por otra parte, la soltura en el manejo del computador para resolver problemas. También se evaluarán las soluciones implementadas para cada uno de los ejercicios planteados para las sesiones de prácticas, atendiendo a la calidad de los procedimientos y estrategias de resolución eficiente en el computador.

Prueba escrita (70%) en la que se plantearán cuestiones y/o problemas del ámbito de la Ingeniería Informática a resolver mediante un computador, de tipología y nivel de complejidad similar al utilizado durante el curso. Se valorará la calidad y claridad de la estrategia de resolución, así como su eficiencia.

Se requiere una nota mínima de 4 puntos sobre un total de 10 en la prueba escrita para aprobar la asignatura. Si se obtiene esta nota mínima, entonces la prueba escrita pondera un 70% en la nota de la asignatura y, si no se alcanza este mínimo, entonces la calificación en la asignatura es la de la prueba escrita.

En la Escuela Universitaria Politécnica de Teruel:

La nota final de la asignatura en la convocatoria ordinaria se divide de la siguiente forma:

Examen escrito. 70% de la nota final. Constará de una parte de teoría y otra de problemas. A mitad de asignatura habrá una prueba parcial que permitirá "adelantar" nota de cara al examen.

Trabajo teórico. 5% de la nota final. Consistirá en un trabajo de temática a definir durante el curso que tratará sobre alguno de los temas de la asignatura.

Prácticas. 25% de la nota final. Habrá varias prácticas entregables a lo largo del curso.

Se requiere una nota mínima de 4 puntos sobre un total de 10 en la prueba escrita para aprobar la asignatura. Si se obtiene esta nota mínima, entonces se realizará la ponderación antes indicada. Si no se alcanza este mínimo, entonces la calificación en la asignatura es la de la prueba escrita.

En cuanto a la convocatoria extraordinaria (septiembre), la nota final será la nota del examen extraordinario, teniendo en cuenta que ese examen tendrá una parte de teoría y problemas que valdrá el 75% de la nota total y una de prácticas que valdrá el 25%. No se mantendrán para septiembre las notas del parcial ni del trabajo.

### Organización de las actividades de evaluación

El alumno superará la asignatura mediante la realización de las actividades enumeradas en el apartado anterior y con las ponderaciones relativas allí señaladas. La evaluación global se desglosará en dos partes correspondientes a dichas actividades y su fecha de realización se especificará con suficiente antelación por el centro. Los alumnos que hubieran superado la actividad 1) durante el curso también podrán presentarse a subir nota en las fechas de la evaluación global.

### 4.1. Presentación metodológica general

#### El proceso de aprendizaje que se ha diseñado para esta asignatura se basa en lo siguiente:

1. La presentación de los contenidos de la asignatura en clases magistrales por parte de los profesores.
2. La resolución de problemas planteados en clase.
3. El estudio personal de la asignatura por parte de los alumnos.
4. El desarrollo de prácticas por parte de los alumnos, guiadas por los profesores, que desarrollan los conocimientos teóricos.
5. La resolución de problemas sencillos de dificultad creciente propuestos por los profesores.

Se debe tener en cuenta que la asignatura tiene una orientación tanto teórica como práctica. Por ello, el proceso de aprendizaje pone énfasis tanto en la asistencia del alumno a las clases magistrales, como en la realización de prácticas en laboratorio, en la resolución de problemas sencillos de dificultad creciente, y en el estudio individualizado.

#### El programa que se ofrece al estudiante para ayudarle a lograr los resultados previstos comprende las siguientes actividades...

En las clases impartidas en el aula se desarrollará el programa de la asignatura.

En las clases de problemas se resolverán problemas de aplicación de los conceptos y técnicas presentadas en el programa de la asignatura.

Las sesiones de prácticas de desarrollan en un laboratorio informático.

### 4.3. Programa

El programa de esta asignatura se organiza alrededor de tres pilares básicos: (1) Teoría de lenguajes formales , con énfasis en los lenguajes regulares y los independientes de contexto; (2) Fundamentos de Computabilidad, para acotar qué problemas pueden ser resueltos algorítmicamente; (3) Fundamentos de Complejidad Algorítmica, para definir qué es eficiencia de una solución algorítmica y los recursos que necesita un algoritmo.

Tema 0: Preliminares

Preliminares matemáticos: conjuntos, funciones, relaciones, inducción.

Definición de alfabeto y lenguaje.

Tema 1: Lenguajes Regulares

Expresiones regulares y lenguajes regulares.

Autómatas finitos deterministas (AFD) y no deterministas (AFnD)

Equivalencia entre AFD y AFnD.

Propiedades de los lenguajes regulares. Lema de bombeo

Tema 2: Lenguajes Independientes de Contexto

Gramáticas y lenguajes independientes del contexto.

Autómatas de pila.

Simplificación de gramáticas.

Propiedades de los lenguajes independientes del contexto. Lema de bombeo

Máquinas de Turing.

Lenguajes y Máquinas de Turing. Tesis de Church-Turing.

Clases de lenguajes P y EXP.

Clases de lenguajes NP y NP-completo.

Los conceptos, métodos y herramientas de los apartados anteriores se ilustrarán a través de ejemplos, lo más realistas posibles, dentro de los ámbitos de: seguridad informática, criptografía, procesamiento de lenguaje natural y compresión de la información.

### 4.4. Planificación de las actividades de aprendizaje y calendario de fechas clave

#### Calendario de sesiones presenciales y presentación de trabajos

El calendario de la asignatura estará definido por el centro en el calendario académico del curso correspondiente.

### Trabajo del estudiante

La dedicación del estudiante para alcanzar los resultados de aprendizaje en esta asignatura se estima en 150 horas distribuidas del siguiente modo:

En la Escuela de Ingeniería y Arquitectura de Zaragoza:

• 56 horas, aproximadamente, de actividades presenciales (clases teóricas, de problemas y prácticas en laboratorio)
• 40 horas de trabajo en equipo
• 51 horas de estudio personal efectivo (estudio de apuntes y textos, resolución de problemas, preparación clases y prácticas)
• 3 horas de examen final escrito

En la Escuela Universitaria Politécnica de Teruel:

• 60 horas de actividades presenciales (clases teóricas, de problemas y prácticas en laboratorio)
• 30 horas de trabajo en equipo
• 55 horas de estudio personal efectivo (estudio de apuntes y textos, resolución de problemas, preparación clases y prácticas)
• 5 horas de actividades de evaluación

El calendario de exámenes y las fechas de entrega de trabajos de evaluación se anunciarán con suficiente antelación.

En la Escuela de Ingeniería y Arquitectura del Campus Rio Ebro:
En la Escuela Universitaria Politécnica del Campus de Teruel