Algorismes Aleatoris

Crèdits
6
Tipus
Obligatòria d'especialitat (Computació Avançada)
Requisits
Aquesta assignatura no té requisits
Departament
CS
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

  • Jordi Petit Silvestre ( )

Altres

  • Josep Diaz Cort ( )

Hores setmanals

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

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.

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 expectatives; moments i desviacions; cua de desigualtats; boles, papereres i gràfics 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, skip-lists
  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ó i comptatge

Activitats

Activitat Acte avaluatiu


Desenvolupament dels temes del temari.



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

Exposicions dels estudiants.



Teoria
0h
Problemes
1h
Laboratori
0h
Aprenentatge dirigit
7.5h
Aprenentatge autònom
7.5h

Tasca de laboratori.



Setmana: 8
Tipus: examen de laboratori
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

Tasca 1.



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

Tasca 2



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

Tasca 3.



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

Examen final.



Setmana: 18
Tipus: examen de teoria
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
30h

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 = 40% FW + 30% FT + 30% SP

FW = Treball final (qualificat de 0 a 10) en el qual cada participant ha de presentar un document d'investigació o secció d'un llibre (prèviament assignat pel professor). La presentació consta de:
3-5 minuts de tornada sobre el tema del document, una motivació.
Visió general d'1 minut sobre les idees claus del document.
Presentació de 15 minuts amb detalls més importants.
Demo 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.

SP = Resums i participació (qualificats de 0 a 10) en els quals cada participant ha de lliurar un resum (extensió de 1 pàgina) de la presentació d'anothers i participar a classe (amb preguntes, comentaris i resolució de problemes a la pissarra).

Bibliografia

Bàsica: