Ampliació d'Algorísmia

Esteu aquí

Crèdits
6
Tipus
Complementària d'especialitat (Computació)
Requisits
  • Prerequisit: A
Departament
CS
L'algorísmia és present arreu, més enllà de la informàtica. Per exemple, les nocions bàsiques que utilitzen els biòlegs per expressar similituds entre gens i genomes són definicions algorísmiques. També quan els economistes analitzen la viabilitat de les subhastes combinatòries. Aquestes subhastes es poden interpretar com problemes de cerca combinatòria alguns d'ells intractables computacionalment, problemes que no es poden resoldre eficientment. La noció de problema computacionalment intractable i en particular de problema NP-complet té un paper fonamental en el disseny d'algorismes. Molts problemes a la pràctica (d'optimització, inteligència artificial, combinatòria, lògica, ... ) són d'aquest tipus. Un cop identificat un problema com a computacionalment difícil hauríem de ser capaços de trobar una solució prou satisfactòria. En aquest curs farem una petita introducció a tècniques que ens permeten tractar problemes difícils:
algorismes d'aproximació (calculen eficientment solucions properes a l'òptima en alguns problemes d'optimització), algorismes de paràmetre fix (identificar un paràmetre del problema que al fixar-lo el problema en questió esdevé tractable). També ampliarem el conjunt de tècniques aleatòries examinades fins al moment en assignatures prèvies.

Professors

Responsable

  • Maria del Carme Alvarez Faura ( )

Altres

  • Josep Diaz Cort ( )
  • Maria Jose Serna Iglesias ( )

Hores setmanals

Teoria
3
Problemes
1
Laboratori
0
Aprenentatge dirigit
0.4
Aprenentatge autònom
5.6

Competències

Competències Transversals

Aprenentatge autònom

  • G7 - Detectar carències en el coneixement propi i superar-les mitjançant la reflexió crítica i l'elecció de la millor actuació per ampliar aquest coneixement. Capacitat per a l'aprenentatge de nous mètodes i tecnologies, i versatilitat per a adaptar-se a noves situacions.
    • G7.3 - Aprenentatge autònom: capacitat de planificació i organització del treball personal. Aplicar els coneixements adquirits a la realització d'una tasca en funció de la pertinença i de la importància, decidir la manera de dur-la a terme i el temps que se li ha de dedicar, i seleccionar les fonts d'informació més adients. Identificar la importància d'establir i mantenir contactes amb els companys d'estudis, amb el professorat i amb els professionals (networking). Identificar fòrums d'informació sobre enginyeria TIC, els seus avenços i el seu impacte en la societat (IEEE, associacions, etc.).

Competències Tècniques de cada especialitat

Especialitat computació

  • CCO1 - Tenir un coneixement profund dels principis fonamentals i dels models de la computació i saber-los aplicar per a interpretar, seleccionar, valorar, modelar i crear nous conceptes, teories, usos i desenvolupaments tecnològics, relacionats amb la informàtica.
    • CCO1.1 - Avaluar la complexitat computacional d'un problema, conèixer estratègies algorísmiques que puguin dur a la seva resolució, i recomanar, desenvolupar i implementar la que garanteixi el millor rendiment d'acord amb els requisits establerts.
  • CCO2 - Desenvolupar de forma efectiva i eficient els algorismes i el software apropiats per a resoldre problemes complexos de computació.
    • CCO2.5 - Implementar software de cerca d'informació (information retrieval).
    • CCO2.6 - Dissenyar i implementar aplicacions gràfiques, de realitat virtual, de realitat augmentada i videojocs.

Objectius

  1. Conèixer els conceptes fonamentals de Problema Computacional i Algorisme. Saber analitzar els recursos computacionals, com Temps i Espai de computació, que requereix un algorisme qualsevol.
    Related competences: CCO1.1,
  2. Conèixer com classificar la complexitat d'un problema computacional. Saber distingir els problemes computacionals segons tractables o intractables. Conèixer les tècniques de reductibilitat i completesa per analitzar rigurosament la dificultat computacional d'un problema.
    Related competences: CCO1.1, G7.3,
  3. Conèixer alguns problemes Intractables clàssics i les classes que aquests identifiquen: NP, PSPACE, EXP i NEXP.

    Related competences: CCO1.1, G7.3,
  4. Conèixer Algorismes Aleatoris per a resoldre problemes Intractables. En particular, conèixer dues varietats d'algorismes aleatoris: Algorismes Monte Carlo que calculen en temps polinòmic una solució del problema que pot ser incorrecta amb molt baixa probabilitat i Algorismes Las Vegas que sempre calculen una solució correcta i garanteixen temps polinòmic amb alta probabilitat.
    Related competences: CCO1.1, G7.3,
  5. Conèixer Algorismes d'Aproximació que calculen eficientment solucions aproximades (properes a les òptimes) per a problemes d'optimització Intractables. Conèixer les seves limitacions o problemes no aproximables en temps polinòmic.
    Related competences: CCO2.5, CCO1.1, G7.3,
  6. Conèixer Algorismes de Paràmetre Fix que ens permeten resoldre en temps polinòmic certes restriccions de problemes Intractables. Saber identificar paràmetres específics d'un problema de manera que al ser fixats, aleshores el problema es pot resoldre efiientment.
    Related competences: CCO2.5, G7.3,
  7. Conèixer Algorismes de fluxos de dades per resoldre de forma eficient
    problemes les entrades dels quals s'han de processar
    fent una petita quantitat de passades sobre elles, utilitzant només una quantitat limitada de memòria de treball.
    El model de fluxes s'utilitza en problemes on la mida de l'entrada supera amb escreix la mida
    de la memòria principal disponible.
    Related competences: CCO2.5, CCO2.6, CCO1.1, G7.3,
  8. Conèixer conceptes bàsics de Teoria de Jocs: Jocs, estratègies, costos, beneficis, jugadors egoïstes. Nou concepte de solució: Equilibri de Nash. Eficiència de les solucions: Preu de l'Estabilitat i Preu de Anarquia. Introducció als Jocs de formació de Xarxes.
    Related competences: CCO1.1,

Continguts

  1. Problemes i Algorismes
    Problemes computacionals.
    Complexitat d'Algorismes: Temps i Espai.
    Complexitat de problemes.
    Problemes tractables: Accessibilitat, Camins curts.
    Problemes intractables: Viatjant, Motxilla.
  2. Problemes Intractables
    Reductibilitat i Completesa.
    Problemes NP-complets: Satisfactibilitat, Subgrafs, Colorabilitat, Recorreguts, Particions, Scheduling.
    Problemes PSPACE, EXP i NEXP: Fórmules quantificades, Jocs de tauler, Enrajolar, Equivalència d'expressions regulars.

  3. Algorismes Aleatoris
    Algorismes Monte Carlo. Algorismes Las Vegas. Generació de nombres aleatoris. Factorització (Heurístic Pollard Rho). Criptografia (RSA)
  4. Algorismes d'Aproximació
    Problemes d'optimització i aproximabilitat.
    Mètodes algorísmics: Algorismes voraços, mètodes basats en Programació Lineal.

  5. Algorismes de Paràmetre Fix
    Problemes parametritzats: Recobriment de vèrtexs, Max Sat, Motxilla.
    Mètodes algorísmics: Arbres de cerca amb profunditat fitada, Kernelització.
  6. Algorismes de Fluxos de Dades
    Alguns problemes bàsics.
    Models computacionals per a fluxos de dades.
    Mètodes algorísmics: Sampling, Sketches, tècniques per a fluxos de grafs.
  7. Algorísmia i Teoria de Jocs: Modelitzant Internet.
    Definicions bàsiques: Joc, estratègia, costos i beneficis, jugadors egoïstes.
    Equilibri de Nash, Cost Social, Preu de l'Estabilitat i Preu de l'Anarquia.
    Introducció de Jocs de formació de Xarxes. Comprensió del funcionament d'Internet: Equilibri d'un joc.

Activitats

Activitat Acte avaluatiu


Entrega de problemes: Intractabilitat.


Objectius: 1 2 3
Setmana: 5
Tipus: entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
4h

Entrega de problemes: Solucions per a problemes Intractables (I)


Objectius: 1 2 4 5
Setmana: 10
Tipus: entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
3h

Entrega de problemes: Solucions per a problemes Intractables (II)


Objectius: 1 2 3 4 5 7 6 8
Setmana: 14
Tipus: entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
3h

Examen Final

Prova per escrit.
Objectius: 1 2 3 4 5 7 6 8
Setmana: 15 (Fora d'horari lectiu)
Tipus: examen final
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
3h
Aprenentatge autònom
8h

Aprenentatge del tema "Problemes i Algorismes"

Els alumnes assiteixen a les classes de teoria, intenten comprendre aquest tema i miren de resoldre els problemes assignats aprofitant les classes de problemes per demanar ajut al professor. A les classes de problemes també se'ls pot demanar que facin una presentació a la pissarra d'algun dels problemes assignats.
Objectius: 1
Continguts:
Teoria
3h
Problemes
1h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
4h

Aprenentatge del tema "Problemes Intractables"

Els alumnes assiteixen a les classes de teoria, intenten comprendre aquest tema i miren de resoldre els problemes assignats aprofitant les classes de problemes per demanar ajut al professor. A les classes de problemes també se'ls pot demanar que facin una presentació a la pissarra d'algun dels problemes assignats.
Objectius: 2 3
Continguts:
Teoria
9h
Problemes
3h
Laboratori
0h
Aprenentatge dirigit
1h
Aprenentatge autònom
15h

Aprenentatge del tema "Algorismes Aleatoris"

Els alumnes assiteixen a les classes de teoria, intenten comprendre aquest tema i miren de resoldre els problemes assignats aprofitant les classes de problemes per demanar ajut al professor. A les classes de problemes també se'ls pot demanar que facin una presentació a la pissarra d'algun dels problemes assignats.
Objectius: 4
Continguts:
Teoria
6h
Problemes
2h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

Aprenentatge del tema "Algorismes d'Aproximació"

Els alumnes assiteixen a les classes de teoria, intenten comprendre aquest tema i miren de resoldre els problemes assignats aprofitant les classes de problemes per demanar ajut al professor. A les classes de problemes també se'ls pot demanar que facin una presentació a la pissarra d'algun dels problemes assignats.
Objectius: 5
Continguts:
Teoria
7h
Problemes
3h
Laboratori
0h
Aprenentatge dirigit
0.5h
Aprenentatge autònom
10h

Aprenentatge del tema "Algorismes de Paràmetre Fix"

Els alumnes assiteixen a les classes de teoria, intenten comprendre aquest tema i miren de resoldre els problemes assignats aprofitant les classes de problemes per demanar ajut al professor. A les classes de problemes també se'ls pot demanar que facin una presentació a la pissarra d'algun dels problemes assignats.
Objectius: 6
Continguts:
Teoria
7h
Problemes
2h
Laboratori
0h
Aprenentatge dirigit
0.5h
Aprenentatge autònom
9h

Aprenentatge del tema "Algorismes de Fluxos de Dades"

Els alumnes assiteixen a les classes de teoria, intenten comprendre aquest tema i miren de resoldre els problemes assignats aprofitant les classes de problemes per demanar ajut al professor. A les classes de problemes també se'ls pot demanar que facin una presentació a la pissarra d'algun dels problemes assignats.
Objectius: 7
Continguts:
Teoria
7h
Problemes
2h
Laboratori
0h
Aprenentatge dirigit
0.5h
Aprenentatge autònom
9h

Aprenentatge del tema "Algorísmia i Teoria de Jocs: Modelitzant Internet"

Els alumnes assiteixen a les classes de teoria, intenten comprendre aquest tema i miren de resoldre els problemes assignats aprofitant les classes de problemes per demanar ajut al professor. A les classes de problemes també se'ls pot demanar que facin una presentació a la pissarra d'algun dels problemes assignats.
Objectius: 8
Continguts:
Teoria
6h
Problemes
2h
Laboratori
0h
Aprenentatge dirigit
0.5h
Aprenentatge autònom
9h

Metodologia docent

Els continguts teòrics de l'assignatura s'imparteixen a les classes de teoria.

A les sessions de problemes els estudiants resoldran problemes amb l'ajut del professor i presentaran algunes de les seves solucions a la pissarra.

Els estudiants hauran de fer tres entregues presentant per escrit la solució de problemes assignats pel professor. Depenent de la dificultat dels problemes podran presentar les solucions en grups de 2 o 3 persones. En alguns casos per trobar la solució caldrà emprar mètodes que complementen els vistos a classe de teoria i requerirà fer una petita recerca bibliogràfica. En aquests casos
es demanarà que es presentin públicament les solucions a les sessions de problemes.

Mètode d'avaluació

Hi ha dos tipus d'actes avaluatius: Entrega de Problemes i Examen Final.


Entrega de Problemes:
Aquesta part consistirà a resoldre unes llistes de problemes que s'assignaran a cada estudiant (o a cada petit grup de treball) tal com s'indica en la planificació. Els estudiants podran discutir a classe de problemes els dubtes que se'ls hi poden anar presentant, però es considera un treball personal i autònom (o per grups) que s'haurà de completar a les seves hores d'estudi. En general seran problemes que la seva solució requerirà aplicar els coneixements adquirits, triar el mètode apropiat en cada cas i també l'ajut de bibliografia específica. Hauran d'entregar les seves solucions per escrit i presentar a classe de problemes alguna d'elles, si es considera oportú (quan s'amplien els coneixements introduits en el tema actual i sobre tot quan el treball és en grup). Aquest és el treball en que s'avaluarà l'aprenentage autònom.


La nota de l'entrega de problemes P és la mitja de la nota de totes les entregues.


Examen:
També hi haurà un examen final en el que s'avaluarà si l'estudiant ha assolit els coneixements més generals introduits durant tot el curs.

La nota final de l'assignatura es calcula a partir de la nota de problemes P i de la nota de l'examen final E de la manera següent:

Nota Final= 0.3 P + 0.7 E

L'avaluació de la competència G7.3 la realitza el professor individualment per a cada alumne basant-se en les presentacions públiques i també per escrit de les solucions dels problemes assignats.

L'avaluació de les competències no afecta a l'avaluació de l'assignatura.

Bibliografia

Bàsica:

Complementaria:

Capacitats prèvies

Coneixements d'algorísmia i conceptes relacionats: Eficiència d'algorismes, notació assimptòtica,
algorismes golafres, programació dinàmica, ...

Coneixements de la teoria de la computació bàsics: autòmats, gramàtiques, màquines de Turing, decidibilitat, complexitat.

Capacitat crítica.

Maduresa matemàtica.