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
Conèixer les principals tècniques i problemes d'aleatorització
Competències relacionades:
CTR6,
CEE3.1,
CEE3.2,
CG1,
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
Introducció
Exemples motivadors; algorismes aleatoris; anàlisi probabilística; Algorismes de Monte Carlo, algorismes de Las Vegas.
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.
Ordenació i cerca
Randomized quick sort; randomized quick select; randomized selection by sampling.
Estructures de dades
Hashing; universal hashing, cuckoo hashing, Bloom filters.
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
- 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.