Algorismes Aleatoris

Crèdits
6
Tipus
  • MIRI: Obligatòria d'especialitat (Computació Avançada)
  • MEI: Optativa
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
conrado@cs.upc.edu
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 (conrado@cs.upc.edu)

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

    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
    0h
    Aprenentatge autònom
    0h

    Presentacions orals (II)



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

    Examen final


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

    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ó

    Nota = 0.7 E + 0.3 OP

    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)
    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àsic

    Complementari

    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.