Ampliació d'Algorísmia

Esteu aquí

Inici » Estudis » Graus » Grau en Enginyeria Informàtica » Pla d'estudis » Assignatures » Ampliació d'Algorísmia
Crèdits
6
Tipus
Complementària d'especialitat (Computació)
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

  • Maria Jose Serna Iglesias ( )

Altres

  • Maria del Carme Alvarez Faura ( )

Hores setmanals

Teoria
3
Problemes
1
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: G7.3, CCO1.1,
  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: G7.3, CCO1.1, CCO2.5,
  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: G7.3, CCO1.1, CCO2.5, CCO2.6,
  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 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. 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.
  5. Algorismes d'Aproximació
    Problemes d'optimització i aproximabilitat.
    Mètodes algorísmics: Algorismes voraços, mètodes basats en Programació Lineal.

  6. 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ó. Programació dinàmica i treewidth
  7. 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.

Activitats

Activitat Acte avaluatiu


Entrega per escrit i/o presentació oral.

Una o dues vegades al llarg del curs els estudiants (en grups) hauran de resoldre problemes i/o estudiar algorismes relacionats amb temes presentats a classe. Els problemes s'hauran d'entregar per escrit i els algoritmes nous presentats a classe. Es considera un treball personal i autònom que s'haurà de completar a les seves hores d'estudi. Aquest és el treball en què s'avaluarà l'aprenentatge autònom.
Objectius: 1 2 3 4 5 7 6 8
Setmana: 10 (Fora d'horari lectiu)
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
11h

Examen Parcial 1


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

Examen Parcial 2

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

Examen Final

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

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

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

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

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 (A); la nota associada als lliuraments/presentacions (E); 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 les notes A, E i les notes dels exàmens parcials P1 i P2 de la manera següent:

Nota Contínua= 0.2 ( 0.3 A + 0.7 E) + 0.4 P1 + 0.4 P2


Si la Nota Contínua >= 5, l'estudiant pot no presentar-se a l'examen final i 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àsica:

Complementaria:

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.