## 39829 - Computer science theory

### Teaching Plan Information

2023/24
Subject:
39829 - Computer science theory
Faculty / School:
326 - Escuela Universitaria Politécnica de Teruel
Degree:
ECTS:
6.0
Year:
3
Semester:
First semester
Subject type:
Basic Education
Module:
---

### 1. General information

The objectives of the subject are basically of four types:

1. -To enable the student to abstract problems to be solved by means of a computer.

2. -To know the basic computational models on which current computers are based and to identify the most suitable one for each problem.

3. -Assimilate well-studied problem paradigms in the context of computer science so that they can reduce or adapt them to the problems that arise.

4. -Know the capabilities and limitations of automatic problem solving and evaluate the resources required for it.

Sustainable Development Goals, SDGs, of the 2030 Agenda ( https://www.un.org/sustainabledevelopment/es/): Goal 1, target 1.4. Goal 8, target 8.2. Goal 16, target 16.5.

### 2. Learning results

The student, in order to pass this subject, must demonstrate the following results...

1. Know the basic calculation models.

2. Find the simplest computational model for each problem.

3. Discard incorrect solutions as being too simple for given problems.

4. Adequately describe the calculation processes.

5. Apply the formalisms of language theory in problem solving.

6. Transform informal statements into formal statements and vice versa.

7. Know the limitations of automatic troubleshooting.

8. Identify basic unsolvable problems such as the shutdown problem or the virus detection problem.

9.  Analyze the cost in time and memory of an algorithm.

10.  Identify problems that require too many computational resources.

### 3. Syllabus

The program is organized around three basic pillars: (1) Theory of formal languages, with emphasis on regular and context-independent languages ; (2) Fundamentals of Computability, to narrow down what problems can be solved algorithmically; (3) Fundamentals of Algorithmic Complexity, to define what is the efficiency of an algorithm and what resources itneeds.

• Unit 0: Preliminaries
• Unit 1: Regular Languages
• Unit 2: Context Independent Languages
• Unit 3: Computability
• Unit 4: Complexity

The concepts, methods and tools of the topics will be illustrated with realistic examples within the areas of: security computer science, cryptography, natural language processing and information compression.

ACTIVITIES

• Classroom classes: development of the syllabus.
• Problem classes: application of concepts and methods of the program to practical cases.
• Practical classes: work in a computer laboratory.

The calendar of the subject will be defined in the academic calendar of the Center.

STUDENT WORK

• 60 hours of classroom activities
• 30 hours of teamwork
• 55 hours of effective self-study
• 5 hours of assessment activities

### 5. Assessment system

The final grade of the subject in the ordinary exam is divided into:

• Written exam. 70% of the final grade. It will consist of a theory part and a problem part. In the middle of the term there will be a partial test that will allow to "advance" the grade for the exam.
• Theoretical work. 5% of the final grade. It will consist of a paper on a topic to be defined during the term that will deal with any of the topics of the subject.
• Practical sessions. 25% of the final grade. There will be several practical deliverables throughout the ter,.

A minimum grade of 4 out of 10 on the written test is required to pass the subject. If this minimum grade is obtained, then the weighting indicated above will be applied. If this minimum is not reached, then the grade in the subject is the written test.

As forthe extraordinary exam, the final grade will be the grade of the extraordinary exam, taking into account that this exam will have a part of theory and problems that will be worth 75% of the total grade and a part of practices that will be worth 25%. The grades of the midterm and the paper will not be kept for the extraordinary examat.

Assessment weighting

The student will pass the subject by carrying out the above activities, with the indicated weightings. The global assessment will consist of two parts corresponding to these activities and its date will be specified in advance by the center. Those who have passed the deliverable activities during the course may also apply for a higher grade in the global assessment.

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

### Información del Plan Docente

2023/24
Asignatura:
39829 - Teoría de la computación
326 - Escuela Universitaria Politécnica de Teruel
Titulación:
634 - Programa conjunto en Ingeniería Informática-Administración y Dirección de Empresas
Créditos:
6.0
Curso:
3
Periodo de impartición:
Primer semestre
Clase de asignatura:
Formación básica
Materia:
Informática

### 1. Información básica de la asignatura

Los objetivos de la asignatura son fundamentalmente de cuatro tipos:

Capacitar al estudiante para que pueda abstraer problemas a resolver mediante un computador.

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.

Conocer las capacidades y limitaciones de la resolución automática de problemas y evaluar los recursos necesarios para ello.
Objetivos de Desarrollo Sostenible, ODS, de la Agenda 2030 (https://www.un.org/sustainabledevelopment/es/): Objetivo 1 - Meta 1.4. Objetivo 8 - Meta 8.2. Objetivo 16 - Meta 16.5.

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.

### 3. Programa de la asignatura

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

1. Conoce los modelos de cálculo básicos.
2. Encuentra el modelo de cálculo más simple para cada problema.
5. Aplica los formalismos de la teoría de lenguajes en la resolución de problemas.
7. Conoce las limitaciones de la resolución automática de problemas.
8. Identifica problemas irresolubles básicos como el problema de parada o el de detección de virus.
9. Analiza el coste en tiempo y memoria de un algoritmo.
10. Identifica problemas que requieren demasiados recursos de cálculo.

1. Clases en aula: desarrollo del programa de la asignatura.
2. Clases de problemas: aplicación de conceptos y métodos del programa a casos prácticos.
3. Clases prácticas: trabajo en laboratorio informático.
El calendario de la asignatura estará definido en el calendario académico del Centro.

TRABAJO DEL ESTUDIANTE

1. 60 horas de actividades presenciales
2. 30 horas de trabajo en equipo
3. 55 horas de estudio personal efectivo
4. 5 horas de actividades de evaluación

### 5. Sistema de evaluación

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

⦁ 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 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, 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 la convocatoria extraordinaria las notas del parcial ni del trabajo.

Organización de la evaluación

El alumno superará la asignatura realizando las actividades anteriores, con las ponderaciones señaladas. La evaluación global constará de dos partes correspondientes a dichas actividades y su fecha de realización se especificará con antelación por el centro. Quienes hubieran superado las actividades entregables durante el curso también podrán presentarse a subir nota en la evaluación global.