Programació i Algorísmia Avançada

Esteu aquí

Inici » Estudis » Graus » Grau en Intel·ligència Artificial » Pla d'estudis » Assignatures » 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

  • Jose Luis Balcázar Navarro ( )

Altres

  • Jordi Delgado Pin ( )

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
Tipus: examen de teoria
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
12h

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.

Bibliografia

Bàsica:

Complementaria:

Web links

Capacitats prèvies

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