Ampliació d'Algorísmia

Crèdits
6
Tipus
  • GRAU: Complementària d'especialitat (Computació)
  • GCED: Optativa
Requisits
  • Prerequisit: A
Departament
CS
Web
https://www.cs.upc.edu/~mjserna/docencia/grauAA/AA-GEI.html
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.

Professorat

Responsable

Hores setmanals

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

Competències

Competències Transversals

Aprenentatge autònom

  • G7 [Avaluable] - 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.
      Competències relacionades: 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.
      Competències relacionades: CCO1.1, G7.3,
    3. Conèixer alguns problemes Intractables clàssics i les classes que aquests identifiquen: NP, PSPACE, EXP i NEXP.

      Competències relacionades: 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.
      Competències relacionades: 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.
      Competències relacionades: 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.
      Competències relacionades: 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.
      Competències relacionades: 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.
      Competències relacionades: CCO1.1,

    Continguts

    1. 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.
    2. Algorismes Aleatoris
      Algorismes Monte Carlo. Algorismes Las Vegas. Generació de nombres aleatoris. Factorització (Heurístic Pollard Rho). Criptografia (RSA)
    3. 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.
    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: Graph Streams, Sampling, Sketches.

    Activitats

    Activitat Acte avaluatiu


    Examen Parcial 1


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

    Examen Parcial 2

    Examen Escrit
    Objectius: 5 7 6
    Setmana: 14 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Examen Final

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

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

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

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

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

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

    Aprenentatge del tema "Algorismes per 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
    4h
    Problemes
    4h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Metodologia docent

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

    A les classes de problemes es discutiran les solucions proposades pels estudiants d'exercicis plantejats pel professor amb antelació (enunciats més complexos, amb els quals l'estudiant ha pogut treballar durant una setmana, autònomament) o d'exercicis curts plantejats durant la mateixa classe per a ser treballats en equips de dos-quatre estudiants o individualment. Els estudiants podran ser requerits a exposar les seves solucions a la resta dels companys.

    Els estudiants hauran de fer diverses entregues/presentacions de la solució de problemes o d'algorismes assignats pel professor. 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.

    Mètode d'avaluació

    La nota final es calcula a partir de la nota de la resolució de problemes algorísmics en classe de problemes i la els lliuraments/presentacions (A); la de les proves escrites: parcial (P1 y P2) i l'examen final (F).

    La nota de l'avaluació contínua de l'assignatura es calcula a partir de la nota A, i les notes dels exàmens parcials P1 i P2 de la manera següent:

    Nota Contínua= 0.2 A + 0.4 P1 + 0.4 P2


    L'estudiant pot no presentar-se a l'examen final i, en aquest cas, la Nota Final = Nota Contínua.

    Si l'estudiant es presenta a l'examen final i obté una nota ExF, aleshores

    Nota Final = max { F, (NotaContínua + F)/2 }

    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 els temes assignats.

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

    Bibliografia

    Bàsic

    Complementari

    Capacitats prèvies

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

    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.