Ampliación de Algorítmica

Créditos
6
Tipos
  • GEI: Complementaria de especialidad (Computación)
  • GCED: Optativa
Requisitos
  • Prerrequisito: A
Departamento
CS
Web
https://www.cs.upc.edu/~mjserna/docencia/grauAA/AA-GEI.html
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 Jose Serna Iglesias (mjserna@cs.upc.edu)

Horas semanales

Teoría
2
Problemas
2
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: G7.3, CCO1.1,
    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: G7.3, CCO1.1, CCO2.5,
    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: G7.3, CCO1.1, CCO2.5, CCO2.6,
    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 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.
    2. Algoritmos Aleatorios
      Algoritmos Monte Carlo. Algoritmos Las Vegas. Generación de números aleatorios. Factoritzación (Heurístico Pollard Rho). Criptografía (RSA)
    3. 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.
    4. Algoritmos de Aproximación
      Problemas de optimitzación y aproximabilidad.
      Métodos algorítmicos: Algoritmos voraces, métodos basados en Programación Lineal.
    5. 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.
    6. Algoritmos de Flujos de Datos
      Algunos problemas básicos.
      Modelos computacionales para flujos de datos.
      Métodos algorítmicos: Graph streams, Sampling, Sketches.

    Actividades

    Actividad Acto evaluativo


    Examen Parcial 1


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

    Examen Parcial 2

    Examen escrito
    Objetivos: 5 7 6
    Semana: 14 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Examen Final

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

    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
    6h
    Problemas
    6h
    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
    6h
    Problemas
    6h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    12h

    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
    2h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    6h

    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
    6h
    Problemas
    6h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    12h

    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
    3h
    Problemas
    4h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Aprendizaje del tema "Algoritmos para 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
    4h
    Problemas
    4h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Metodología docente

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

    En las clases de problemas se discutirán las soluciones propuestas por los estudiantes de ejercicios planteados por el profesor con antelación (enunciados más complejos, con los que el estudiante ha podido trabajar durante una semana, autónomamente) o ejercicios cortos planteados durante la misma clase para ser trabajados en equipos de dos-cuatro estudiantes o individualmente. Los estudiantes podrán ser requeridos a exponer sus soluciones al resto de sus compañeros.

    Los estudiantes tendrán que hacer varias entregas/presentaciones de la solución de problemas o de algoritmos asignados por el profesor. En algunos casos para encontrar la solución habrá que utilizar métodos que complementen los vistos en clase de teoría y requerirá realizar una pequeña investigación bibliográfica. En estos casos se pedirá que se presenten públicamente las soluciones.

    Método de evaluación

    La nota final se calcula a partir de la nota de la resolución de problemas algorítmicos en clase de problemas y la asociada a las entregas/presentaciones (A); la de las pruebas escritas: parcial (P1 y P2) y el examen final (ExF).

    La nota de la evaluación continua de la asignatura se calcula a partir de las nota A, y las notas de los exámenes parciales P1 y P2 de la siguiente forma:

    Nota Continua = 0.2 A + 0.4 P1 + 0.4 P2

    El estudiante puede no presentarse en el examen final y, en ese caso, la Nota Final = Nota Continua.

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

    Nota Final = max { ExF, (NotaContinua + ExF)/2 }

    La evaluación de la competencia G7.3 la realiza el profesor individualmente para cada alumno en base a las presentaciones públicas y también por escrito de los temas asignados.

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

    Bibliografía

    Básico

    Complementario

    Capacidades previas

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

    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.