Programació i Algorísmia Avançada

Crèdits
6
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
Departament
CS
Web
https://www.cs.upc.edu/~balqui/paa.html
S'estudien els fonaments de la computació i tècniques pel disseny eficient d'algoritmes. Es repassen les tècniques bàsiques algorítmiques i el seu l'anàlisis, i s'expliquen técniques addicionals de disseny d'algorismes. Seguidament, s'estudien els límits de la computació, com a conseqüència de l'estudi de models formals de càlcul,
i es fa una introducció a la complexitat computacional.

Professorat

Responsable

Altres

Hores setmanals

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

Competències

Competències Transversals

Transversals

  • CT4 [Avaluable] - Treball en equip. Ser capaç de treballar com a membre d'un equip interdisciplinari, ja sigui com un membre més o realitzant tasques de direcció, amb la finalitat de contribuir a desenvolupar projectes amb pragmatisme i sentit de la responsabilitat, assumint compromisos tenint en compte els recursos disponibles.
  • CT6 [Avaluable] - Aprenentatge autònom. Detectar deficiències en el propi coneixement i superar-les mitjançant la reflexió crítica i l'elecció de la millor actuació per ampliar aquest coneixement.

    • Bàsiques

  • CB1 - Que els estudiants hagin demostrat posseir i comprendre coneixements en una àrea d'estudi que parteix de la base de l'educació secundària general, i se sol trobar a un nivell que, si bé es recolza en llibres de text avançats, inclou també alguns aspectes que impliquen coneixements procedents de l'avantguarda del seu camp d'estudi.
  • CB2 - Que els estudiants sàpiguen aplicar els seus coneixements al seu treball o vocació d'una manera professional i posseeixin les competències que solen demostrar-se mitjançant l'elaboració i defensa d'arguments i la resolució de problemes dins la seva àrea d'estudi.

    • Competències Tècniques

    Específiques

  • CE02 - Dominar els conceptes bàsics de matemàtica discreta, lògica, algorísmica i complexitat computacional i la seva aplicació per al tractament automàtic de la informació per mitjà de sistemes computacionals i la seva aplicació per a la resolució de problemes.
  • CE03 - Identificar i aplicar els procediments algorítmics bàsics de les tecnologies informàtiques per dissenyar solucions a problemes, analitzant la idoneïtat i complexitat dels algoritmes proposats.
  • CE04 - Dissenyar i utilitzar de forma eficient els tipus i estructures de dades més adequats a la resolució d'un problema.
  • CE10 - Analitzar, dissenyar, construir i mantenir aplicacions de forma robusta, segura i eficient, triant el paradigma i els llenguatges de programació més adequats.
  • CE12 - Dominar els principis fonamentals i 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 intel·ligència artificial.
  • CE13 - Avaluar la complexitat computacional d'un problema, identificar estratègies algorítmiques que puguin conduir a la seva resolució i recomanar, desenvolupar i implementar aquella que garanteixi el millor rendiment d'acord amb els requisits establerts.

    • Competències Tècniques Generals

    Genèriques

  • CG2 - Utilitzar els coneixements fonamentals i metodologies de treball sòlides adquirits durant els estudis per adaptar-se als nous escenaris tecnològics de el futur.
  • CG4 - Raonar, analitzant la realitat i dissenyant algoritmes i formulacions que la modelin. Identificar problemes i construir solucions algorísmiques o matemàtiques vàlides, eventualment noves, integrant el coneixement multidisciplinari necessari, valorant diferents alternatives amb esperit crític, justificant les decisions preses, interpretant i sintetitzant els resultats en el context de l'domini d'aplicació i establint generalitzacions metodològiques a partir de aplicacions concretes.
  • CG8 - Observar un exercici ètic de la professió en totes les seves facetes, aplicant criteris ètics en el disseny de sistemes, algoritmes, experiments, utilització de dades, d'acord amb els sistemes ètics recomanats pels organismes nacionals i internacionals, amb especial èmfasi en seguretat, robustesa , privacitat, transparència, traçabilitat, prevenció de biaixos (de raça, gènere, religió, territori, etc.) i respecte als drets humans.

    • Objectius

    1. Aprendre a analitzar algorismes i conèixer les notacions asimptòtiques.
      Competències relacionades: CG2, CG4, CE02, CE03, CE12,
    2. Saber classificar els problemes segons la seva complexitat temporal i espaial.
      Competències relacionades: CG4, CG8, CT4, CT6, CB2, CE02, CE03, CE12, CE13,
    3. Conèixer esquemes algorítmics fonamentals com ara programació dinàmica, algoritmes voraços, tècniques combinatories i de formalització de restriccions lineals, identificar quan n'és idoni l'aplicació i plantejar i resoldre els programes adients.
      Competències relacionades: CG4, CT6, CB2, CE02, CE03, CE04, CE10, CE13,
    4. Conèixer els models teòrics de computació, així com els seus límits.
      Competències relacionades: CG4, CT4, CB1, CB2, CE02, CE13,

    Continguts

    1. Disseny d'algoritmes combinatoris
      Com son i com s'apliquen els algoritmes voraços, les restriccions lineals i la programació dinàmica.
    2. Models de computació
      Models de propòsit específic: autòmats finits, autòmats a pila. Models de propòsit general: màquines de Turing, sistemes acceptables de programació, funcions recursives parcials.
    3. Decidibilitat
      Problemes decidibles, indecidibles i semi-decidibles. La reduïbilitat com a eina per classificar problemes. Indecidibilitat de tota propietat no trivial sobre el comportament dels programes. Propietats de les funcions computables.
    4. Complexitat computacional
      Complexitat concreta i complexitat abstracta. Classes de complexitat. Relació amb esquemes de cerca combinatòria. NP-completesa a la IA i a altres dominis. Programació lineal i programació entera.

    Activitats

    Activitat Acte avaluatiu


    Conceptes bàsics d'algoritmes, anàlisi i complexitat

    Recapitulació d'algoritmes coneguts de PA2 / ABIA. Conceptes fonamentals de Problema Computacional Combinatòric i d'Algoritme Combinatòric. Ccomplexitat d'un problema computacional.
    Objectius: 1 3
    Continguts:
    Teoria
    2h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    4h

    Algoritmes voraços

    Concepte, exemples i característiques dels algoritmes voraços.
    • Teoria: Planificació de tasques. Algoritmes per camins mínims. Algoritmes de Kruskal y Prim per arbres d'expansió mínims. Particions (Union-find). Codis de Huffman.
    Objectius: 3
    Continguts:
    Teoria
    2h
    Problemes
    0h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Algoritmes de Programació Dinàmica

    Concepte, exemples i característiques dels algoritmes de programació dinàmica.
    • Teoria: Concepte, exemples i característiques dels algoritmes de programació dinàmica. Principi d'optimalitat. Memoització. Arbres binaris de cerca òptims. Algoritme de Floyd-Warshall per camins mínims. Problema de la motxilla. Altres exemples.
    Objectius: 3
    Continguts:
    Teoria
    2h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Llenguatges Formals

    Alfabets, llenguatges, gramàtiques. La jerarquia de Chomsky. Autòmats finits. Gramàtiques incontextuals i autòmats a pila. Ambigüitat.
    • Teoria: Alfabets, llenguatges, gramàtiques. La jerarquia de Chomsky. Autòmats finits. Gramàtiques incontextuals i autòmats a pila. Ambigüitat.
    Objectius: 4
    Continguts:
    Teoria
    2h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    6h

    Expressions regulars

    Concepte; equivalència amb autòmats i Lema d'Arden; operacions sobre expressions regulars. Expressions regulars esteses: exemples d'útilitat.
    Objectius: 4
    Continguts:
    Teoria
    2h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Parcial

    Parcial
    Objectius: 1 3 4
    Setmana: 8
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Funcions computables i decidibilitat

    Computabilitat: màquines de Turing, sistemes acceptables de programació. Propietats de les funcions computables. Problemes decidibles.
    Objectius: 4
    Continguts:
    Teoria
    2h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12h

    Propietats de les funcions computables. Indecidibilitat. Semidecidibilitat.

    Propietats de les funcions computables: s-m-n (avaluació parcial), recursió. Indecidibilitat del problema de parada. Reduïbilitat com a eina per argumentar indecidibilitat. Semidecidibilitat i propietats principals. Productivitat.
    Objectius: 4
    Continguts:
    Teoria
    5h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    10h

    Complexitat computacional

    Complexitat computacional. Complexitat abstracta i complexitat concreta. L'enfocament axiomàtic.Complexitat en temps i en espai. Les classes logarítmiques i polinòmiques: robustesa. Indeterminisme. Teorema de Savitch.
    Objectius: 2 4
    Continguts:
    Teoria
    5h
    Problemes
    0h
    Laboratori
    8h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    10h

    Algoritmes probabilistics.

    Métodes Monte-Carlo versus Las Vegas. Factorització i criptografia. Classes de complexitat probabilístiques. Desrandomització. Amplitud versus probabilitat: algoritme de Grover, introducció a la computació quàntica.
    Objectius: 2 4
    Continguts:
    Teoria
    6h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12h

    Metodologia docent

    Les classes es distribueixen en sessions de teoria i problemes. Les sessions de teoria s'exposaran els conceptes de l'assignatura fent ús del material de suport que els alumnes sempre tindran disponible, alguns conceptes s'exemplificaran sempre promovent la interacció dels alumnes per aclarir els possibles dubtes i discussió.

    Les sessions pràctiques es resoldran problemes proposats pel professor que permetran aprofundir en els conceptes, tècniques i mètodes exposats a teoria. En tot moment, s'animarà als estudiants a participar en la resolució dels problemes tant de manera individual com en petits grups per discutir les alternatives possibles.

    Els problemes podran ser tant amb paper i llàpis com sobre màquina, amb l'ajut de software adient disponible sense cost.

    Mètode d'avaluació

    Part de la secció d'Algorítmica (inicial del curs) requerirà per la seva avaluació una pràctica de dimensió modesta que es presentarà al començament del tema Programació Dinàmica i s'avaluarà a la seva entrega (nota P).

    Addicionalment hi haurà la nota del parcial (E) i la de l'examen final (nota F). La nota del curs s'obtindrà mitjançant el següent criteri:

    max(F*0.8, (E*0.3 + F*0.5)) + P*0.2

    Reavaluació
    Només es poden presentar a l'examen de reavaluació qui prèviament s'hagi presentat a l'examen final i l'hagi suspès. La nota màxima de reavaluació és un 7.

    Bibliografia

    Bàsic

    Complementari

    Web links

    Capacitats prèvies

    Programació i Algorítmica tal com s'adquireixen a les assignatures prèvies del Grau.