Ampliación de Algorítmica

Usted está aquí

Inicio » Estudios » Grados » Grado en Ingeniería Informática » Plan de estudios » Asignaturas » Ampliación de Algorítmica
Créditos
6
Tipos
Complementaria de especialidad (Computación)
Requisitos
  • Prerrequisito: A
Departamento
CS
La algorítmica está presente en todas partes, más allá de la informática. Por ejemplo, las nociones básicas que utilizan los biólogos para expresar similitudes entre genes y genomas son definiciones algorítmicas. También cuando los economistas analizan la viabilidad de las subastas combinatorias. Estas subastas se pueden interpretar como problemas de búsqueda combinatoria. Algunos de estos problemas son intratables desde el punto de vista computacional, problemas que no se pueden resolver eficientemente. La noción de problema computacionalmente intratable y en particular la noción de problema NP-completo tienen un papel fundamental en el diseño de algoritmos. Muchos problemas en la práctica (de optimización, inteligencia artificial, combinatoria, lógica, ...) son de este tipo. Una vez identificado un problema como computacionalmente difícil deberíamos ser capaces de encontrar una solución satisfactoria. En este curso introducimos técnicas que nos permiten tratar problemas difíciles: algoritmos de aproximación (calculan eficientemente soluciones cercanas a la óptima en algunos problemas de optimización), algoritmos de parámetro fijo (identifican un parámetro del problema que al fijarlo el problema en cuestión pasa a ser tratable). En este curso ampliamos también el conjunto de técnicas aleatorias estudiadas hasta el momento en asignaturas previas.

Profesorado

Responsable

  • Maria del Carme Alvarez Faura ( )

Otros

  • Maria Jose Serna Iglesias ( )

Horas semanales

Teoría
3
Problemas
1
Laboratorio
0
Aprendizaje dirigido
0
Aprendizaje autónomo
6

Competencias

Competencias Transversales

Aprendizaje autónomo

  • G7 [Avaluable] - Detectar carencias en el propio conocimiento y superarlas mediante la reflexión crítica y la elección de la mejor actuación para ampliar este conocimiento. Capacidad para el aprendizaje de nuevos métodos y tecnologías y versatilidad para adaptarse a nueves situaciones.
    • G7.3 - Aprendizaje autónomo: Capacidad de planificación y organización del trabajo personal. Aplicar los conocimientos adquiridos a la realización de una tarea en función de la pertenencia y la importancia, decidiendo la manera de llevarla a cabo y el tiempo que hay que dedicarle y seleccionando las fuentes de información más adecuadas. Identificar la importancia de establecer y mantener contactos con los compañeros de estudios, con el profesorado y con profesionales (networking). Identificar fórums de información sobre ingeniería TIC, sus avances y su impacto en la sociedad (IEEE, asociaciones, etc.).

Competencias Técnicas de cada especialidad

Especialidad de computación

  • CCO1 - Tener un conocimiento profundo de los principios fundamentales y de los 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.
    • CCO1.1 - Evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución, y recomendar, desarrollar e implementar la que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.
  • CCO2 - Desarrollar de forma efectiva y eficiente los algoritmos y el software apropiados para resolver problemas complejos de computación.
    • CCO2.5 - Implementar software de búsqueda de información (information retrieval).
    • CCO2.6 - Diseñar e implementar aplicaciones gráficas, de realidad virtual, de realidad aumentada y videojuegos.

Objetivos

  1. Conocer los conceptos fundamentales de Problema Computacional y Algoritmo. Saber analizar los recursos computacionales, como Tiempo y Espacio de computación, que requereix un algorisme qualsevol.
    Competencias relacionadas: CCO1.1,
  2. Saber como clasificar la complejidad de un problema computacional. Saber distinguir entre problemas tratables y problemas intratables. Conocer las técnicas de reducibilidad y completitud para analizar rigurosamente la dificultad computacional de un problema.
    Competencias relacionadas: CCO1.1, G7.3,
  3. Conocer algunos problemas intratables clásicos y las clases que estos identifican: NP, PSPACE, EXP i NEXP.
    Competencias relacionadas: CCO1.1, G7.3,
  4. Conocer Algoritmos Aleatorios para resolver problemas intratables. En particular, conocer dos variedades de algoritmos aleatorios: Algoritmos Monte Carlo que computan en tiempo polinómico una solució que puede ser incorrecta con probabilidad muy baja y algoritmos Las Vegas que siempre computan una solución correcta y garantizan tiempo polinómica con alta probabilidad.
    Competencias relacionadas: CCO1.1, G7.3,
  5. Conocer Algoritmos de Aproximación que computan eficientemente soluciones aproximadas (cercanas a las óptimas) para problemas de optimizción. Conocer sus limitaciones o problema no aproximables en teimpo polinómico.
    Competencias relacionadas: CCO2.5, CCO1.1, G7.3,
  6. Conocer Algoritmos de Parámetro Fijo the nos permiten resolver en tiempo polnómico ciertas restricciones de problemas intratables. Saber identificar parámetros específicos de un problema, de manera que al ser fijados entonces el problema puede ser resuelto en tiempo polinómico.
    Competencias relacionadas: CCO2.5, G7.3,
  7. Conocer los algoritmos de flujos de datos para resolver de manera eficiente.
    problemas donde las entradas deben ser procesadas.
    haciendo una
    o una pequeña cantidad de pasadas sobre ellas, usando solo una cantidad limitada de memoria de trabajo.
    El modelo de flujo se aplica en problemas donde el tamaño de la entrada excede el tamaño
    de la memoria principal disponible.
    Competencias relacionadas: CCO2.5, CCO2.6, CCO1.1, G7.3,
  8. Conocer conceptos básicos de la Teoría de Juegos: Juegos, estrategias, beneficios, costes, jugadores egoistas. Nuevo concepto de solución: Equilibrio de Nash. Eficiencia de la soluciones: Precio de la Estabilidad y Precio de la Anarquía.
    Competencias relacionadas: CCO1.1,

Contenidos

  1. Problemas y Algoritmos
    Problemas computacionales.
    Complejidad de algoritmos: Tiempo y Espacio.
    Problemas tratables: Accesibilidad, Caminos corto.
    Problemas intratables: Viajante, Mochila.
  2. Problemas Intratables
    Reducibilidad y Completitud.
    Problemas NP-completos: Satisfactibilidad, Subgrafos, Colorabilidad, Recorridos, Particiones, Scheduling.
    Problemas PSPACE, EXP y NEXP: Fórmulas cuantificadas, Juegos de tablero, Mosaico, Equivalencia de expresiones regulares.
  3. Algoritmos Aleatorios
    Algoritmos Monte Carlo. Algoritmos Las Vegas. Generación de números aleatorios. Factoritzación (Heurístico Pollard Rho). Criptografía (RSA)
  4. Algoritmia y Teoría de Juegos: Modelizando Internet.
    Definiciones básicas: Juego, estrategia, costes y beneficios, jugadores egoistss.
    Equilibrio de Nash, Coste Social, Precio de la Estabilitat i Precio de la Anarquía.
    Introducción de Juegos de formación de redes. Comprensión del funcionamento de Internet: Equilibrio de un juego.
  5. Algoritmos de Aproximación
    Problemas de optimitzación y aproximabilidad.
    Métodos algorítmicos: Algoritmos voraces, métodos basados en Programación Lineal.
  6. Algoritmos de Parámetro fijo.
    Problemas parametrizados: Recubrimento de vértices, Max Sat, Mochila.
    Métodes algorítmicos: Arboles de búsqueda de profundidad acotada, Kernelización.
  7. Algoritmos de Flujos de Datos
    Algunos problemas básicos.
    Modelos computacionales para flujos de datos.
    Métodos algorítmicos: Sampling, Sketches, técnicas para flujos de grafos.

Actividades

Actividad Acto evaluativo


Entrega de problemas: Intratabilidad


Objetivos: 1 2 3
Semana: 5 (Fuera de horario lectivo)
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
5h

Entrega de problemas: Soluciones para problemes Intratables (I)


Objetivos: 1 2 4 5
Semana: 8 (Fuera de horario lectivo)
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
5h

Entrega de problemas: Soluciones para problemas Intratables (II)


Objetivos: 1 2 3 4 5 7 6 8
Semana: 14 (Fuera de horario lectivo)
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
5h

Examen Parcial 1


Objetivos: 1 2 3 4 8
Semana: 8
Teoría
0h
Problemas
3h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Examen Parcial 2

Examen escrito
Objetivos: 5 7 6
Semana: 14
Teoría
0h
Problemas
3h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Examen Final

Prueba por escrito.
Objetivos: 1 2 3 4 5 7 6 8
Semana: 15 (Fuera de horario lectivo)
Teoría
3h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
8h

Aprendizaje del tema "Problemas y Algoritmos"

Los alumnos asisten a las classes de teoría, intentan comprender este tema y miran de resolver los problemas assignados, aprovechando las clases de problemas para pedir ayuda al professor. En clase de problemas también se puede pedir a los estudiantes que presenten en la pizarra alguno de los problemas asignados.
Objetivos: 1
Contenidos:
Teoría
4h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
4h

Aprendizaje del tema "Problemas Intratables"

Los alumnos asisten a las classes de teoría, intentan comprender este tema y miran de resolver los problemas assignados, aprovechando las clases de problemas para pedir ayuda al professor. En clase de problemas también se puede pedir a los estudiantes que presenten en la pizarra alguno de los problemas asignados.
Objetivos: 2 3
Contenidos:
Teoría
8h
Problemas
2h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
12h

Aprendizaje del tema "Algoritmos Aleatorios"

Los alumnos asisten a las classes de teoría, intentan comprender este tema y miran de resolver los problemas assignados, aprovechando las clases de problemas para pedir ayuda al professor. En clase de problemas también se puede pedir a los estudiantes que presenten en la pizarra alguno de los problemas asignados.
Objetivos: 4
Contenidos:
Teoría
5h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Aprendizaje del tema "Algorítmica y Teoría de Juegos: Modelizando Internet"

Los alumnos asisten a las classes de teoría, intentan comprender este tema y miran de resolver los problemas assignados, aprovechando las clases de problemas para pedir ayuda al professor. En clase de problemas también se puede pedir a los estudiantes que presenten en la pizarra alguno de los problemas asignados.
Objetivos: 8
Contenidos:
Teoría
5h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
5h

Aprendizaje del tema "Algoritmos de Aproximación"

Los alumnos asisten a las classes de teoría, intentan comprender este tema y miran de resolver los problemas assignados, aprovechando las clases de problemas para pedir ayuda al professor. En clase de problemas también se puede pedir a los estudiantes que presenten en la pizarra alguno de los problemas asignados.
Objetivos: 5
Contenidos:
Teoría
7h
Problemas
2h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
10h

Aprendizaje del tema "Algoritmos de Parámetro Fijo"

Los alumnos asisten a las classes de teoría, intentan comprender este tema y miran de resolver los problemas assignados, aprovechando las clases de problemas para pedir ayuda al professor. En clase de problemas también se puede pedir a los estudiantes que presenten en la pizarra alguno de los problemas asignados.
Objetivos: 6
Contenidos:
Teoría
7h
Problemas
2h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
9h

Aprendizaje del tema "Algoritmos de Flujos de Datos""

Los alumnos asisten a las classes de teoría, intentan comprender este tema y miran de resolver los problemas assignados, aprovechando las clases de problemas para pedir ayuda al professor. En clase de problemas también se puede pedir a los estudiantes que presenten en la pizarra alguno de los problemas asignados.
Objetivos: 7
Contenidos:
Teoría
6h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
9h

Metodología docente

Los contenidos teóricos de la asignatrua se imparten en las clases de teoría.

En las sesiones de problemas los esudiantes resolverán problemas con la ayuda del profesor y presentarán alguna de sus soluciones en la pizarra.

Los estudiantes tienen que entregar por escrito la soluciones de los problemas asignados. En algunos casos para encontrar una solución se deberan usar métodos que complementan a los que se han estudiado en clase. Ello requerirá realizar una pequeña búsqueda bibliográfica. En estos casos se pedirá a los estudantes que presenten sus soluciones públicamente en la pizarra en las clase de problemas.

Método de evaluación

Hay tres tipos de actos evaluadores: Entrega de Problemas y Examen Final.


Entrega de Problemas:
Esta parte consistirá en resolver unas listas de problemas que se asignaran a cada estudiant (o a cada grupo de trabajo) tal com se indica en la planificación. Los estudiantes podrán discutir en clase de problemas las dudas que van a ir presentándose, pero se considera que éste es un trabajo personal y autónomo (o per grups) que debe completarse en las horas de estudio. En general serán problemas cuyas soluciones requerirán aplicar los conocimientos adquiridos, seleccionar el método apropiado en cada caso y también de la ayuda de bibliografía específica. Deben entregar sus solucions por escrito y presentar en clase de problemes alguna d'elles, si se considera oportuno (cuando se amplíen los conocimientos introduidos en el tema actual y sobre todo cuando el trabajo és en grup). Para evaluar el aprendizaje autónomo se tendrá en cuenta la valoración de estas entregas.

La nota de entrega de problemas Pro es la media de la nota de todas las entregas.



Exámenes:

Hay dos exámenes parciales o controles de problemas y un examen final
en el que se evaluará si el estudiante ha adquirido los conocimientos generales del curso.

La nota de la evaluación continua se calcula a partir de la nota de problemas Pro y de las notas de los exámenes parciales P1 y P2 de la manera seguiente:

Nota Continua= 0.2 Pro + 0.4 P1 + 0.4 P2


Si la Nota Continua >= 5, el estudiante puede no presentarse al examen final y la Nota Final = Nota Continua.


Si el estudiante se presenta al examen final y obtiene una nota ExF, entonces

Nota Final = max { ExF, (NotaContínua+ExF)/2 }


La evaluación de la competencia G7.3 la realitza el profesor individualment para cada alumno basándose en les presentacions públicas y por escrito de les solucions de los problemas asignados.

La evaluación de las competencias no afecta a la evaluación de la asignatura.

Bibliografía

Básica:

Complementaria:

Capacidades previas

Conocimientos de algoritmia y conceptos relacionados: Eficiencia de algoritmos, notación asintótica,
algoritmos voraces, programación dinámica, ...

Conocimientos de la teoría de la computación básicos: autómatas, gramáticas, máquinas de Turing, decidibilidad, complejidad.

Capacidad crítica.

Madurez matemática.