Algoritmos Aleatorios

Créditos
6
Tipos
  • MIRI: Obligatoria de especialidad (Computación Avanzada)
  • MEI: Optativa
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
CS
Web
http://www.cs.upc.edu/~conrado/docencia/ra-miri.html
Mail
conrado@cs.upc.edu
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

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

    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
    0h
    Aprendizaje autónomo
    0h

    Presetaciones orales (II)



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

    Examen final


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

    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

    Nota = 0.7 E + 0.3 OP

    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)
    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ásico

    Complementario

    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