Gestión Académica

Universidad de Oviedo

Uniovi.es | Inicio | Buscador | Mapa Web

| |

Grado en Ingeniería Informática en Tecnologías de la Información
GIITIN01-2-001
Algoritmia
Descripción General y Horario Guía Docente

Coordinador/es:

RAQUEL CORTINA PARAJON
raqueluniovi.es
Maria Teresa Gonzalez Aparicio
maytegauniovi.es

Profesorado:

Maria Teresa Gonzalez Aparicio
maytegauniovi.es
(English Group)
RAQUEL CORTINA PARAJON
raqueluniovi.es
JOSE RANILLA PASTOR
ranillauniovi.es
Nahuel Alejandro Costa Cortez
costanahueluniovi.es

Contextualización:

La asignatura de Algoritmia (ALG) forma parte de la materia de Programación (PR), del Módulo de Software de Aplicación (SA), junto con otras seis asignaturas: Fundamentos de Informática (FIN), Introducción a la Programación (INP), Metodología de la Programación (MTP), Estructuras de Datos (ESD), Tecnologías y Paradigmas de Programación (TPP) y Programación Concurrente y Paralela (PCP). Dentro de la materia PR, el principal contenido que cubre la asignatura ALG corresponde a Técnicas fundamentales para el diseño y verificación de algoritmos recursivos y Técnicas fundamentales para el diseño y análisis de algoritmos eficientes.

La algoritmia es uno de los pilares de la programación y su relevancia se muestra en el desarrollo de cualquier aplicación, más allá de la mera construcción de programas. El objetivo de la asignatura es proporcionar al alumno las técnicas básicas para el diseño e implementación de algoritmos, así como suministrar unas herramientas que le permitan determinar su efectividad y eficiencia.

Requisitos:

Para abordar esta asignatura es recomendable que el alumno haya cursado las asignaturas: Fundamentos de Informática, Introducción a la Programación y Metodología de la Programación.

Competencias y resultados de aprendizaje:

 

 

Competencias generales

GTR1.Capacidad para resolver problemas dentro de su área de estudio.

GTR2. Capacidad de abstracción: capacidad para crear y utilizar modelos que reflejen situaciones reales.

GTR3. Capacidad de actuar autónomamente.

GTR4. Capacidad de planificación y organización personal.

GTR6. Capacidad de comunicación efectiva (en expresión y comprensión) oral y escrita, con especial énfasis en la redacción de documentación técnica.

GTR7. Poseer las habilidades de aprendizaje necesarias para emprender estudios posteriores o mejorar su formación con un cierto grado de autonomía

GTR8. Tener motivación por la calidad y la mejora continua y actuar con rigor en el desarrollo profesional.

 

 

 

 

Competencias específicas

Resultados de aprendizaje

ECR6.1 Conocimiento y aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas

 

PR32 Comprender los esquemas algorítmicos clásicos (Divide y Vencerás, Ramifica y poda, etc.) y aplicarlos eficazmente ante un problema que lo requiera.

ECR6.2 Análisis de la idoneidad y complejidad de los algoritmos propuestos.

PR33 Calcular la eficiencia de un algoritmo a partir de la técnica del orden de complejidad (notación O).

PR34 Comprender el concepto de algoritmo recursivo.

PR35 Aplicar la técnica de diseño de algoritmos recursivos para resolver un problema.

PR36 Transformar un algoritmo recursivo en su versión iterativa equivalente.

PR37 Determinar la idoneidad del uso de un algoritmo recursivo frente al iterativo equivalente para resolver un problema

PR38 Seleccionar el esquema algoritmo idóneo para resolver un problema concreto.

 

Contenidos:

Unidad didáctica I: Conceptos fundamentales de algoritmia

Tema 1. Análisis de algoritmos

Introducción. Complejidad temporal y espacial. Notaciones asintóticas: O, omega y orden exacto. Órdenes de complejidad. Análisis por casos: mejor, peor y promedio. Análisis del coste de algoritmos iterativos y recursivos. Casos de estudio: búsqueda, ordenación, etc.

Tema 2. Diseño de Algoritmos Recursivos

Introducción. Principio de inducción. Diseño y verificación de una función recursiva. Técnicas de inmersión. Tipos de recursión. Transformación de algoritmos recursivos en su versión iterativa.

Unidad didáctica II: Esquemas Algorítmicos

Tema 3. Programación Dinámica

Introducción: características generales de programación dinámica. Problemas de optimización. Principio de optimalidad. Esquema general. Ejemplos: mochila, devolver el cambio, caminos mínimos, etc.

  Tema 4. Divide y Vencerás

  Introducción: características generales de divide y vencerás. Esquema general. Ejemplos:

  búsqueda binaria, ordenación por fusión, ordenación rápida, etc.

Tema 5. Vuelta atrás

Introducción: características generales de vuelta atrás. Árboles de exploración. Esquemas generales. Ejemplos: mochila, ocho reinas, etc.

Tema 6: Esquema Voraz

Introducción: características generales de los algoritmos voraces. Esquema general. Ejemplos: devolver el cambio, mochila, caminos mínimos (Dijkstra), árboles de expansión mínimos (Prim y Kruskal), planificación de tareas, etc.

Tema 7. Ramifica y poda

Introducción: características generales de ramifica y poda. Esquemas generales. Ejemplos: mochila, asignación de tareas, etc.

Metodología y plan de trabajo:

Las actividades presenciales del alumno consistirán en la asistencia a: clases expositivas, prácticas de aula, prácticas de laboratorio y tutorías grupales. En las clases expositivas el profesor alternará la exposición de los contenidos teóricos de la asignatura con la realización de ejemplos y ejercicios sobre los mismos. En las prácticas de aula se realizarán actividades de discusión teórica o preferentemente prácticas en las que se requerirá una elevada participación del alumnado. Las prácticas de laboratorio serán por el contrario individuales, para asegurar la adquisición de las habilidades prácticas básicas por cada alumno. Las tutorías grupales se dedicarán a la puesta en común por parte de los alumnos de las dudas y dificultades que se les hayan presentado durante el proceso de aprendizaje.

La tutoría académica se realizará en el horario establecido a tal fin por cada profesor, pudiéndose contactar por medio del correo electrónico del profesor.

Las actividades no presenciales consistirán en el estudio de la materia teórica y en la realización de los ejercicios y problemas que el profesor proponga o publique a través del Campus Virtual.

La asignatura requiere un total 150 horas entre trabajo presencial y no presencial del alumno.

El desglose estimado del trabajo por temas es el siguiente (dos horas de clase de teoría, media hora de práctica de aula y dos horas de práctica corresponden a una semana):

 

 

TRABAJO PRESENCIAL

TRABAJO NO

PRESENCIAL

Temas

Horas totales

Clase Expositiva

Prácticas de aula

Prácticas de laboratorio

Tutorías grupales

Sesiones de Evaluación

Total

Trabajo autónomo

Análisis de algoritmos

35

7

2

5

 

1

15

20

Diseño de Algoritmos recursivos

35

7

2

5

 

1

15

20

Programación Dinámica

44

7

1

5

1

 

14

30

Divide y Vencerás

7

2

 

2

 

 

4

3

Vuelta Atrás

12

2

1

2

 

 

5

7

Esquema Voraz

13

2

1

2

 

1

6

7

Ramifica y Poda

4

1

 

 

 

 

1

3

Total

150

28

7

21

1

3

60

90

El resumen por modalidades de trabajo se muestra seguidamente:

 

MODALIDADES

Horas

%

Totales

Presencial

Clases Expositivas

28

18,67

60 (40%)

Práctica de aula / Seminarios / Talleres

7

4,67

Prácticas de laboratorio / campo / aula de informática / aula de idiomas

21

14,00

Tutorías grupales

1

0,66

Sesiones de evaluación

3

2,00

No presencial

Trabajo Autónomo

90

60

90 (60%)

 

Total

150

 

 

 

De forma excepcional, si las condiciones sanitarias lo requieren, se podrán incluir actividades de docencia no presencial. En cuyo caso, se informará al estudiantado de los cambios efectuados.

Evaluación del aprendizaje de los estudiantes:

Convocatoria ordinaria

La evaluación del aprendizaje se realizará únicamente a través de un proceso de evaluación continua. La calificación final de la evaluación continua constará de tres partes, Teoría, Práctica y Trabajo Grupal, con los siguientes pesos:

  • Teoría 50%
  • Práctica 45%
  • Trabajo Grupal 5%

Evaluación continua de Teoría.-

Durante el curso se realizarán tres controles para evaluar el trabajo del alumno en la parte Teórica de la asignatura. Los dos primeros controles se realizarán en las clases presenciales teóricas y el tercero tendrá lugar en la fecha oficial fijada para la convocatoria. El peso de los controles en la calificación final de la parte teórica será: 25% el primer control, 25% el segundo y 50% el tercero. Dicho peso es proporcional a la carga docente de la parte evaluada. No hay examen final de recuperación.

Evaluación continua de Práctica.-

Para la parte Práctica, se evaluarán de forma continua los trabajos individuales realizados por los alumnos en el aula de prácticas. La materia estará dividida en los mismos tres bloques que en la parte de Teoría y con los mismos pesos en la nota final de prácticas. No hay examen final de recuperación.

Evaluación de Trabajo Grupal.-

Se realizará un trabajo en grupo que será planteado y supervisado en las prácticas de aula de la asignatura, por lo que cada grupo debe estar formado por alumnos del mismo grupo de prácticas de aula.

 

Las actividades evaluables no realizadas por el alumno se valorarán con un cero. No obstante, si el peso total de estas actividades supone más del 50% de la nota total, la calificación final del alumno será “No presentado”.

Si no se alcanza al menos un 40% de la calificación en la parte Teórica, o en la parte Práctica, la calificación final de la asignatura será “Suspenso”, con un máximo de 4,5 puntos. Para superar la convocatoria ordinaria la calificación final de la asignatura debe ser de al menos 5 puntos (sobre 10).

Convocatoria extraordinaria

La evaluación constará de un examen teórico y uno práctico, con los siguientes porcentajes sobre la nota final:

  • Examen extraordinario de Teoría: 50%
  • Examen extraordinario de Prácticas: 50%

Para aprobar la asignatura se requiere alcanzar al menos el 50% de la calificación en el examen de Teoría y el 50% de la calificación en el examen de Prácticas.

Los alumnos que hayan obtenido como mínimo el 50% de la calificación de la parte de Teoría o el 50% de la calificación de la parte de Práctica en la Convocatoria Ordinaria, no tendrán obligación de examinarse de la parte superada en las convocatorias extraordinarias del presente curso académico. Para aprobar la asignatura, deben obtener el 50% en la calificación final de la asignatura.

Evaluación diferenciada

La evaluación será la misma en todas las convocatorias y constará de un examen teórico y uno práctico, con los siguientes porcentajes sobre la nota final:

  • Examen de Teoría 50%
  • Examen de Prácticas 50%

Para aprobar la asignatura se requiere alcanzar al menos el 50% de la calificación en el examen de Teoría y el 50% de la calificación en el examen de Prácticas.

De forma excepcional, si las condiciones sanitarias lo requieren, se podrán incluir métodos de evaluación no presencial. En cuyo caso, se informará al estudiantado de los cambios efectuados.

 

Recursos, bibliografía y documentación:

Bibliografía básica

  • Brassard, G., Bratley, P., Fundamentos de Algoritmia, Prentice-Hall, 1997.
  • Cormen,T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.,  Introduction to Algorithms, The MIT Press, 2009.
  • Peña, R., Diseño de Programas. Formalismo y Abstracción, Prentice-Hall, 2005.

 Bibliografía complementaria

  • Aho, A. V., Hopcroft, J. E., Ullman, J. D., Data Structures and Algorithms, Addison Wesley, 1987.
  • Baase, S., Computer Algorithms, Introduction to Design and Analysis, Addisson Wesley, 1988.
  • Horowitz, E., Sahni, S., Fundamentals of Computer Algorithms, Pitman, 1978.
  • Scholl, P. C., Algorítmica y Representación de Datos, Recursividad y Árboles, Masson, 1986.
  • Torres, C., Diseño y Análisis de algoritmos, Paraninfo, 1992.

 Documentación complementaria

 Además de esta guía docente, el equipo docente proporcionará material adicional a través del entorno de enseñanza virtual de la asignatura:

 

https://www.innova.uniovi.es/innova/campusvirtual/campusvirtual.php