Algorismes Aleatoris

Crèdits
6
Tipus
Obligatòria d'especialitat (Computació Avançada)
Requisits
Aquesta assignatura no té requisits
Departament
CS
Mail
L'objectiu d'aquest curs és presentar la potència i la varietat d'algorismes aleatoris i aprofundir en l'anàlisi probabilística d'algorismes.

Un algoritme aleatori és un algorisme que fa eleccions aleatòries com a part de la seva lògica. L'anàlisi probabilística dels algorismes calcula la complexitat computacional dels algoritmes o el problema assumint una certa distribució probabilística del conjunt de totes les entrades possibles.

El curs té dos temes principals. El primer tema presenta eines i tècniques bàsiques de la teoria de la probabilitat i de l'anàlisi probabilística recurrents en aplicacions algorítmiques. El segon tema tracta d'àrees específiques d'aplicació. Les eines i les tècniques es intercalaran amb aplicacions que il·lustren en entorns concrets.

Professors

Responsable

  • Conrado Martínez Parra ( )

Hores setmanals

Teoria
2
Problemes
2
Laboratori
0
Aprenentatge dirigit
0.409
Aprenentatge autònom
6

Competències

Competències Tècniques de cada especialitat

Computació avançada

  • CEE3.1 - Capacitat per a identificar barreres computacionals i analitzar la complexitat de problemes computacionals en diversos àmbits de la ciència i la tecnologia; així com per representar problemes d'alta complexitat en estructures matemàtiques que puguin ser tractades eficientment amb esquemes algorítmics.
  • CEE3.2 - Capacitat per utilitzar un espectre ampli i variat de recursos algorítmics per resoldre problemes d'alta dificultat algorísmica.

Competències Tècniques Generals

Genèriques

  • CG1 - Capacitat per aplicar el mètode científic en l'estudi i anàlisi de fenòmens i sistemes en qualsevol àmbit de la Informàtica, així com en la concepció, disseny i implantació de solucions informàtiques innovadores i originals.
  • CG3 - Capacitat per al modelatge matemàtic, càlcul i disseny experimental en centres tecnològics i d'enginyeria d'empresa, particularment en tasques de recerca i innovació en tots els àmbits de la Informàtica.
  • CG5 - Capacitat per aplicar solucions innovadores i realitzar avenços en el coneixement que explotin els nous paradigmes de la Informàtica, particularment en entorns distribuïts.

Competències Transversals

Raonament

  • CTR6 - Capacitat de raonament crític, lògic i matemàtic. Capacitat de resoldre problemes en la seva àrea d'estudi. Capacitat d'abstracció: capacitat de crear i utilitzar models que reflecteixin situacions reals. Capacitat de dissenyar i realitzar experiments senzills, i analitzar-ne i interpretar-ne els resultats. Capacitat d'anàlisi, de síntesi i d'avaluació.

Bàsiques

  • CB6 - Que els estudiants sàpiguen aplicar els coneixements adquirits y la seva capacitat de resolució de problemes en entorns nous o poc coneguts dins de contexts més amplis (o multidisciplinaris) relacionats amb la seva àrea d'estudi.

Objectius

  1. Conèixer les principals tècniques i problemes d'aleatorització
    Competències relacionades: CTR6, CEE3.1, CEE3.2, CG1,
  2. Examinar les condicions en què es poden utilitzar algoritmes aleatoris. Realitzar una anàlisi i extreure les propietats fonamentals, de diferents dominis, per avaluar la idoneïtat i l'aplicabilitat de mètodes aleatoris.
    Competències relacionades: CTR6, CG3, CG5, CB6,

Continguts

  1. Introducció
    Exemples motivadors; algorismes aleatoris; anàlisi probabilística; Algorismes de Monte Carlo, algorismes de Las Vegas.
  2. Eines i tècniques probabilístiques
    Esdeveniments i probabilitats; variables aleatòries i mitjanes; moments i desviacions; desigualtats de cua; boles i papereres; grafs aleatoris; Cadenes de Markov i passejos aleatoris.
  3. Ordenació i cerca
    Randomized quick sort; randomized quick select; randomized selection by sampling.
  4. Estructures de dades
    Hashing; universal hashing, cuckoo hashing, Bloom filters.
  5. Algorismes de grafs
    Talls mínims, camins més curts, arbres d'expansió.
  6. Tècniques algebraiques
    Fingerprinting; database consistency; pattern matching; primality testing.
  7. Optimització, aproximació,mostreig i comptatge

Activitats

Activitat Acte avaluatiu


Teoria
10h
Problemes
10h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
30h

Examen parcial


Objectius: 1 2
Setmana: 7
Tipus: examen de problemes
Teoria
0h
Problemes
1h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
12h

Desenvolupament dels temes del temari (II)



Teoria
12h
Problemes
10.5h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
30h

Tasca de laboratori

Disseny, implementació i documentació d'un treball pràctic sobre un dels temes desenvolupats a l'assignatura

Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
15h

Presentació de la tasca de laboratori.


Objectius: 1 2
Setmana: 14
Tipus: entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
1h
Aprenentatge autònom
6h

Presentacions orals (I)

Presentació oral d'un article o tema relacionat amb l'assignatura

Setmana: 15
Tipus: entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
2h
Aprenentatge autònom
4h

Presentacions orals (II)



Setmana: 16
Tipus: entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
2h
Aprenentatge autònom
4h

Metodologia docent

Hi haurà dos tipus de classes: sessions teòriques i sessions pràctiques. De mitjana, dues hores setmanals es dedica a la teoria i dus hores a la setmana a exercicis. El professor assignarà les hores d'acord amb el tema.

Les classes teòriques prenen la forma de conferències en què el professor exposa nous conceptes o tècniques i exemples que els il·lustren.

Les classes pràctiques s'utilitzen per realitzar exercicis en què els alumnes participen activament. Els professors van establir els exercicis amb antelació. Es demana als estudiants que presentin els exercicis i que tractin les diferents solucions / alternatives a la classe.

Mètode d'avaluació

Nota = 30% P + 40% LW + 30% T

P = Examen parcial (qualificat entre 0 i 10)

LW = Treball de laboratori (entre 0 i 10) en què cada estudiant presenta un o més exercicis de programació en el que s'implementen algorismes al.leatoritzats


T = Presentació oral d'un article o tema concret relacionat amb l'assignatura, junt amb un resum escrit i el material audiovisual de la presentació (qualificat entre 0 i 10); els articles i/o temes serà escollit per l'estudiant d'entre les propostes realitzades pel professor

Bibliografia

Bàsica:

Addenda

Continguts

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.

Metodologia docent

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ètode d'avaluació

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.

Pla de contingència

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.