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
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 ( )

Otros

  • Maria del Carme Alvarez Faura ( )

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. Programación dinámica y treewidth
  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 escrita y/o presentación oral.

Una o dos veces a lo largo del curso los estudiantes (en grupos) tendrán que resolver problemas y/o estudiar algoritmos relacionados con temas presentados en clase. Los problemas tendrán que entregarse por escrito y los algoritmos nuevos presentados en clase. Se considera un trabajo personal y autónomo que deberá completarse en sus horas de estudio. Éste es el trabajo en el que se evaluará el aprendizaje autónomo.
Objetivos: 1 2 3 4 5 7 6 8
Semana: 10 (Fuera de horario lectivo)
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
11h

Examen Parcial 1


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

Examen Parcial 2

Examen escrito
Objetivos: 5 7 6
Semana: 14 (Fuera de horario lectivo)
Teoría
0h
Problemas
2h
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
2h
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
15h

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

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
3h
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
10h

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

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 (A); la nota asociada a las entregas/presentaciones (E); la de las pruebas escritas: parcial (P1 y P2) y el examen final (F).

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

Nota Continua = 0.2 ( 0.3 A + 0.7 E) + 0.4 P1 + 0.4 P2


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

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

Nota Final = max { F, (NotaContinua + F)/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ásica:

Complementaria:

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.