Algoritmos Aleatorios

Créditos
6
Tipos
Obligatoria de especialidad (Computación Avanzada)
Requisitos
Esta asignatura no tiene requisitos
Departamento
CS
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.

Profesores

Responsable

  • Conrado Martínez Parra ( )

Horas semanales

Teoría
2
Problemas
2
Laboratorio
0
Aprendizaje dirigido
0.409
Aprendizaje autónomo
6

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: CTR6, CEE3.1, CEE3.2, CG1,
  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: CTR6, CG3, CG5, CB6,

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

Examen parcial


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

Desarrollo de los temas del temario (II)



Teoría
12h
Problemas
10.5h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
30h

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
15h

Presentación de la tarea de laboratorio.


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

Presentaciones orales (I)

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

Semana: 15
Tipo: entrega
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
2h
Aprendizaje autónomo
4h

Presetaciones orales (II)



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

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 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% P + 40% LW + 30% T

P = Examen parcial (calificado entre 0 y 10)

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


T = 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:

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 other suitable means. 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 altres medis apropiats. 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 otras medios apropiados.