Algoritmos Aleatorios

Créditos
6
Tipos
Obligatoria de especialidad (Computación Avanzada)
Requisitos
Esta asignatura no tiene requisitos
Departamento
CS
El objetivo de este curso es presentar el poder y la variedad de algoritmos aleatorios y profundizar en el análisis probabilístico de algoritmos.

Un algoritmo aleatorizado es un algoritmo que toma decisiones aleatorias como parte de su lógica. El análisis probabilístico de algoritmos estima la complejidad computacional de algoritmos o problemas asumiendo alguna distribución probabilística del conjunto de todas las entradas posibles.

El curso tiene dos temas principales. El primer tema presenta las herramientas y técnicas básicas de la teoría de la probabilidad y el análisis probabilístico que son recurrentes en las aplicaciones algorítmicas. El segundo tema trata sobre áreas específicas de aplicación. Las herramientas y las técnicas se intercalarán con aplicaciones que las ilustrarán en entornos concretos.

Profesores

Responsable

  • Maria Jose Serna Iglesias ( )

Otros

  • Jordi Petit Silvestre ( )
  • Josep Diaz Cort ( )

Horas semanales

Teoría
2
Problemas
1
Laboratorio
0
Aprendizaje dirigido
0.179
Aprendizaje autónomo
7.8

Competencias

Competencias Técnicas de cada especialidad

Advanced computing

  • CEE3.1 - Capacidad para identificar barreras computacionales y analizar la complejidad de problemas computacionales en diversos ámbitos de la ciencia y la tecnología; así como para representar problemas de alta complejidad en estructuras matemáticas que puedan ser tratadas eficientemente con esquemas algorítmicos.
  • CEE3.2 - Capacidad para utilizar un espectro amplio y variado de recursos algorítmicos para resolver problemas de alta dificultad algorítmica.

Competencias Técnicas Genéricas

Genéricas

  • CG1 - Capacidad para aplicar el método científico en el estudio y análisis de fenómenos y sistemas en cualquier ámbito de la Informática, así como en la concepción, diseño e implantación de soluciones informáticas innovadoras y originales.
  • CG3 - Capacidad para el modelado matemático, cálculo y diseño experimental en centros tecnológicos y de ingeniería de empresa, particularmente en tareas de investigación e innovación en todos los ámbitos de la Informática.
  • CG5 - Capacidad para aplicar soluciones innovadoras y realizar avances en el conocimiento que exploten los nuevos paradigmas de la Informática, particularmente en entornos distribuidos.

Competencias Transversales

Razonamiento

  • CTR6 - Capacidad de razonamiento crítico, lógico y matemático. Capacidad para resolver problemas dentro de su área de estudio. Capacidad de abstracción: capacidad de crear y utilizar modelos que reflejen situaciones reales. Capacidad de diseñar y realizar experimentos sencillos, y analizar e interpretar sus resultados. Capacidad de análisis, síntesis y evaluación.

Básicas

  • CB6 - Que los estudiantes sepan aplicar los conocimientos adquiridos y su capacidad de resolución de problemas en entornos nuevos o poco conocidos dentro de contextos más amplios (o multidisciplinares) relacionados con su área de estudio.

Objetivos

  1. Conocer las principales técnicas y problemas de la aleatorización.
    Competencias relacionadas: CG1, CEE3.1, CEE3.2, CTR6,
  2. Examinar las condiciones bajo las cuales se pueden usar algoritmos aleatorios. Realizar un análisis y extraer las propiedades fundamentales, de diferentes dominios, para evaluar la idoneidad y aplicabilidad de los métodos aleatorios.
    Competencias relacionadas: CG3, CB6, CTR6, CG5,

Contenidos

  1. Introducción
    Ejemplos motivadores; algoritmos aleatorios; análisis probabilístico; Algoritmos de Monte Carlo, algoritmos de Las Vegas.
  2. Herramientas y técnicas probabilísticas
    Eventos y probabilidades; variables aleatorias y esperanzas; momentos y desviaciones; desigualdades de cola; bolas y contenedores; grafos aleatorios; Cadenas de Markov y paseos aleatorios.
  3. Ordenación y búsqueda
    Randomized quick sort; randomized quick select; randomized selection by sampling.
  4. Estructuras de datos
    Hashing; universal hashing, cuckoo hashing, bloom filters.
  5. Algoritmos de grafos
    Cortes mínimos, caminos más cortos, árboles de expansión.
  6. Técnicas algebraicas
    Fingerprinting; database consistency; pattern matching; primality testing.
  7. Optimización, aproximación, muestreo y contaje

Actividades

Actividad Acto evaluativo


Teoría
28h
Problemas
11h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
55h

Tarea de laboratorio.



Semana: 8
Tipo: entrega
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
16h

Control 1.


Objetivos: 1 2
Semana: 5
Tipo: examen de problemas
Teoría
0h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Control 2.


Objetivos: 1 2
Semana: 10
Tipo: examen de problemas
Teoría
0h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Control 3.


Objetivos: 1 2
Semana: 15
Tipo: examen de problemas
Teoría
0h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Examen final.


Objetivos: 1 2
Semana: 18
Tipo: examen final
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
20h

Metodología docente

Habrá dos tipos de clases: sesiones teóricas y sesiones prácticas. En promedio, dos horas a la semana se dedica a la teoría y una hora a la semana a los ejercicios. El maestro asignará las horas de acuerdo con el tema.

Las clases de teoría toman la forma de conferencias en las cuales el maestro establece nuevos conceptos o técnicas y ejemplos que los ilustran.

Las clases prácticas se utilizan para llevar a cabo ejercicios en los que los estudiantes toman parte activa. Los maestros establecen los ejercicios por adelantado. Los estudiantes deben presentar los ejercicios y luego discutir las diversas soluciones / alternativas en clase.

Método de evaluación

Nota = 30% (C1 + C2 + C3) / 3 +40% LW + 30% FT +

C1, C2, C3 = Controles de problema. Cada uno se califica de 0 a 10.

LW = Trabajo de laboratorio (calificado de 0 a 10) en el que cada participante debe presentar un programa que implemente un algoritmo aleatorio para resolver un problema, tomado de un trabajo de investigación o una sección de un libro (previamente asignado por el profesor). La presentación consta de:
3-5 minutos de antecedentes sobre el tema del trabajo y su motivación.
Descripción general de 1 minuto de las ideas clave de la solución algorítmica.
Presentación de 10 minutos con los detalles más importantes.
Demostración de 5 minutos de un programa que implemente las ideas introducidas en el documento.

FT = Prueba final calificada de (0 a 10) incluyendo todos los contenidos de RA.40% FW + 30% FT + 30% SP

Bibliografía

Básica:

Adenda

Contenidos

There are no modifications to the contents of the teaching guide. No hi ha modificacions respecte als continguts de la guia docent. No hay modificaciones respecto a los contenidos de la guía docente.

Metodología docente

There are no modifications to the methodology given in the teaching guide. The on-line classes will be complemented with voluntary activities that encourage participation in these classes and the assimilation of the topics of the course. No hi ha modificacions respecte a la metodologia de la guia docent. Les classes de teoria no presencial es complementaran amb activitats voluntàries que fomentin la participació en aquestes classes i l'assimilació dels continguts de l'assignatura. No hay modificaciones respecto a la metodología de la guía docente. Las clases no presenciales se complementarán con actividades voluntarias que fomenten la participación en estas clases y la asimilación de los contenidos de la asignatura.

Método de evaluación

There are no modifications to the evaluation method. No hi ha modificacions al mètode d'avaluació. No hay modificaciones al método de evaluación.

Plan de contingencia

In case of cancellation of the face-to-face teaching, the classes will continue on-line, in the same schedule, and they will be reinforced with communication tools that allow to maintain contact between students and between students and teachers in an agile way. The exams will be held in person, with delivery through the Racó and/or Atenea En cas de cancel·lació de tota activitat lectiva presencial les classes es continuaran de forma no presencial en el mateix horari i és reforçaran amb eines de comunicació que permetin mantenir el contacte entre els estudiants i entre estudiants i professors de forma àgil. Els exàmens i controls es realitzaran de forma no presencial, amb entrega a través del Racó i/o d'Atenea. En caso de cancelación de toda actividad lectiva presencial las clases continuarán de forma no presencial en el mismo horario y se reforzarán con herramientas de comunicación que permitan mantener el contacto entre los estudiantes y entre estudiantes y profesores de forma ágil. Los exámenes se realizarán de forma no presencial, con entrega a través del Racó y/o de Atenea.