Algorismes Aleatoris

Esteu aquí

Inici » Estudis » Màsters » Màster en Innovació i Recerca en Informàtica » Pla d'estudis » Assignatures » Algorismes Aleatoris
Crèdits
6
Tipus
Obligatòria d'especialitat (Computació Avançada)
Requisits
Aquesta assignatura no té requisits, però té capacitats prèvies
Departament
CS
Web
http://www.cs.upc.edu/~conrado/docencia/ra-miri.html
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.

Professorat

Responsable

  • Conrado Martínez Parra ( )

Hores setmanals

Teoria
2
Problemes
2
Laboratori
0
Aprenentatge dirigit
0.32
Aprenentatge autònom
9.325

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. Tècniques algebraiques
    Fingerprinting; database consistency; pattern matching; primality testing.
  6. Optimització, aproximació,mostreig i comptatge

Activitats

Activitat Acte avaluatiu


Desenvolupament dels temes del temari (I)

Desenvolupament del temari i resolució d'exercicis
Objectius: 1 2
Continguts:
Teoria
10h
Problemes
10h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
25h

Examen parcial


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

Desenvolupament dels temes del temari (II)



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

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

Presentacions orals (I)

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

Setmana: 14 (Fora d'horari lectiu)
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
2h
Aprenentatge autònom
4h

Presentacions orals (II)



Setmana: 15 (Fora d'horari lectiu)
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
2h
Aprenentatge autònom
4h

Examen final


Objectius: 1 2
Setmana: 16
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
12h

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 dues hores a la setmana a exercicis. El professorat 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. El professorat proposarà 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ó

Si E >= 3.5 llavors
Nota = 0.5 E + 0.3 LW + 0.2 OP
Altrament
Nota = E

P = Examen parcial (qualificat entre 0 i 10)
F = Examen final (qualificat entre 0 i 10)
E = max(0.4 P + 0.6 F, F)
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
OP = 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:

Complementaria:

Capacitats prèvies

- Coneixements bàsics d'algorismes i estructures de dades: algorismes d'ordenació, algorismes sobre grafs, arbres binaris de cerca, taules de hash, cost d'algorismes, nocions de complexitat, esquemes algorítmics, ...

- Coneixements de, si més no, un llenguatge de programació, preferentment C++ o Python.