Algoritmos Aleatorios

Usted está aquí

Inicio » Estudios » Másteres » Máster en Innovación e Investigación en Informática » Plan de estudios » Asignaturas » Algoritmos Aleatorios
Créditos
6
Tipos
Obligatoria de especialidad (Computación Avanzada)
Requisitos
Esta asignatura no tiene requisitos, pero tiene capacidades previas
Departamento
CS
Web
http://www.cs.upc.edu/~conrado/docencia/ra-miri.html
Mail
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.

Profesorado

Responsable

  • Conrado Martínez Parra ( )

Horas semanales

Teoría
2
Problemas
2
Laboratorio
0
Aprendizaje dirigido
0.32
Aprendizaje autónomo
9.325

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. Técnicas algebraicas
    Fingerprinting; database consistency; pattern matching; primality testing.
  6. Optimización, aproximación, muestreo y contaje

Actividades

Actividad Acto evaluativo


Desarrollo de los temas del temario (I)

Desarrollo del temario y resolución de ejercicios
Objetivos: 1 2
Contenidos:
Teoría
10h
Problemas
10h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
25h

Examen parcial


Objetivos: 1 2
Semana: 7
Teoría
0h
Problemas
2h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
12h

Desarrollo de los temas del temario (II)



Teoría
10h
Problemas
10h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
25h

Tarea de laboratori

Diseño, implementación y documentación de un trabajo práctic sobre un de los temas presentados en la asignatura

Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
20h

Presentaciones orales (I)

Presentación oral de un artículo o tema relacionado con la asignatura

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

Presetaciones orales (II)



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

Examen final


Objetivos: 1 2
Semana: 16
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
12h

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 dos horas a la semana a los ejercicios. El profesorado 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.El profesorado propondrá ejercicios con antelación. Los estudiantes deben presentar los ejercicios y luego discutir las diversas soluciones / alternativas en clase.

Método de evaluación

Si E >= 3.5 entonces
Nota = 0.5 E + 0.3 LW + 0.2 OP
Sino
Nota = E

P = Examen parcial (calificado entre 0 y 10)
F = Examen final (calificado entre 0 y 10)
E = max(0.4 P + 0.6 F, F)
LW = Trabajo de laboratorio (entre 0 y 10) en el que cada estudiante presenta uno o más ejercicios de programación en el que se implementan algoritmos aleatorizados
OP = Presentación oral de un artículo o tema concreto relacionado con la asignatura, junto con un resumen escrito y el material audiovisual de la presentación (calificado entre 0 y 10); los artículos y / o temas será escogido por el estudiante de entre las propuestas realizadas por el profesor

Bibliografía

Básica:

Complementaria:

Capacidades previas

- Conocimientos básicos de algoritmos y estructuras de datos: algoritmos de ordenación, algoritmos sobre grafos, árboles binarios de búsqueda, tablas de hash, coste de algoritmos, nociones de complejidad, esquemas algorítmicos, ...

- Conocimiento de, al menos, un lenguaje de programación, preferentemente C++ o Python