Ampliación de Algorítmica

Usted está aquí

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.

Profesores

Responsable

  • Maria del Carme Alvarez Faura ( )

Otros

  • Maria Jose Serna Iglesias ( )

Horas semanales

Teoría
3
Problemas
1
Laboratorio
0
Aprendizaje dirigido
0.4
Aprendizaje autónomo
5.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. 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: Sampling, Sketches, técnicas para flujos de grafos.
  7. 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.

Actividades

Actividad Acto evaluativo


Entrega de problemas: Intratabilidad


Objetivos: 1 2 3
Semana: 5
Tipo: entrega
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
4h

Entrega de problemas: Soluciones para problemes Intratables (I)


Objetivos: 1 2 4 5
Semana: 10
Tipo: entrega
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
3h

Entrega de problemas: Soluciones para problemas Intratables (II)


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

Examen Final

Prueba por escrito.
Objetivos: 1 2 3 4 5 7 6 8
Semana: 15 (Fuera de horario lectivo)
Tipo: examen final
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
3h
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
3h
Problemas
1h
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
9h
Problemas
3h
Laboratorio
0h
Aprendizaje dirigido
1h
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
6h
Problemas
2h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
10h

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

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
6h
Problemas
2h
Laboratorio
0h
Aprendizaje dirigido
0.5h
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. Dependiendo de la dificultad de los problemas, las soluciones se podran presentar en grupos de 2 o 3 personas. En algunos casos para encontrar una solucó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.

Presentaciones:
Se assignará a cada grupo o individualment secciones de artículos o libros que tendrán que presentar en clase en un tiempo limitado de máximo 20 minutos. El material asignado ha de permitir demostrar algunos de los resultados o propiedades anunciados en classe de teoria.

La nota de las presentaciones Lec, es la media de la nota de todas les presentaciones.

Examen:
También habrá un examen final en el que se evaluará si el estudiante ha adquirido los conocimientos más generales introducidos durante todo el curso.

La nota final de la asignatura se calcula a partir de Pro, Lec, and ExF (la nota del examen) de la manera siguiente:

Nota Final = 0.3 Pro + 0.2 Lec + 0.5 ExF

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.

Adenda

Contenidos

No hi ha canvis.

Metodología docente

La modificació important és que les classes de Teoria seran no presencials, síncrones i es faran via Meet. L'assignatura està organitzada en 2 hores/setmana de teoria, 1 hora/setmana teòrica pràctica i 1 hora/setmana de problemes. L'horari assignat a AA consta d'una franja de 2 hores de teoria (no presencial) i una franja presencial de 2 hores una de les quals és teòrica-pràctica (preparació i exposició de presentacions) i l'altra de problemes (preparació i exposició de problemes).

Método de evaluación

No hi ha canvis.

Plan de contingencia

Si per emergència COVID haguéssim de fer la classe de problemes i la teòrica-pràctica també de manera no presencial, aleshores ho faríem semblant a la classe presencial, canviant la pissarra o projeccions per una presentació via Meet. Les solucions als problemes assignats s'hauran d'entregar via Pràctiques del Racó i durant la classe els estudiants les hauran de presentar i defensar via Meet (presentació del pdf entregat al Racó), explicant oralment les línies principals del seu argument. El professor farà els comentaris i correccions pertinents i prendrà nota de la valoració de cada presentació. Els exàmens es realitzaran de forma no presencial, amb entrega a través de Pràctiques del Racó.