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

  • Maria Jose Serna Iglesias ( )

Altres

  • Conrado Martínez Parra ( )

Hores setmanals

Teoria
2
Problemes
1
Laboratori
0
Aprenentatge dirigit
0.179
Aprenentatge autònom
7.8

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

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
28h
Problemes
11h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
55h

Tasca de laboratori.



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

Control 1


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

Control 2


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

Control 3.


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

Examen final.


Objectius: 1 2
Setmana: 18
Tipus: examen final
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
20h

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 una hora 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% (C1 + C2 + C3) / 3 + 40% LW + 30% FT

C1, C2, C3 = Controls de problemes. Cadascú qualificat entre 0 i 10.

LW = Treball de laboratori (entre 0 i 10) en què cada participant ha de presentar un programa que implementi un algoritme aleatori per resoldre un problema extret d'un treball de recerca o d'una secció d'un llibre (prèviament assignat pel professor). La presentació consta de:
3-5 minuts de fons sobre el tema de la ponència, una motivació.
Visió general d'1 minut de les idees clau de la solució algorítmica.
Presentació de 10 minuts amb detalls més importants.
Demostració de 5 minuts d'un programa que implementa les idees introduïdes al document.


FT = Prova final qualificada de (0 a 10) incloent tots els continguts de RA.

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/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.