Algorísmia i Programació III

Crèdits
6
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
Departament
CS
En aquesta assignatura s'estudien els principals esquemes algorísmics per a la resolució de problemes computacionals complexos. De forma paral·lela s'introdueixen les eines necessàries per a poder implementar aquests algorismes en un llenguatge de programació modern.

Professorat

Responsable

  • Enric Rodriguez Carbonell (erodri@cs.upc.edu)

Altres

  • Öznur Yasar (oznur.yasar@upc.edu)

Hores setmanals

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

Competències

Competències Tècniques

Competències tècniques

  • CE2 - Ser capaç de programar solucions a problemes d'enginyeria: Dissenyar solucions algorítmiques eficients a un problema computacional donat, implementar-les en forma de programari robust, estructurat i mantenible, i comprovar la validesa de la solució.
  • CE7 - Demostrar coneixement i capacitat d'aplicació de les eines necessàries per a l'emmagatzematge, el processament i l'accés a les dades.

    • 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.
  • CT5 - Ús solvent dels recursos d'informació. Gestionar l'adquisició, l'estructuració, l'anàlisi i la visualització de dades i informació en l'àmbit de l'especialitat i valorar de forma crítica els resultats d'aquesta gestió.
  • CT6 - 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.
  • CT7 - Tercera llengua. Conèixer una tercera llengua, preferentment l'anglès, amb un nivell adequat oral i escrit i d'acord amb les necessitats que tindran els titulats i titulades.

    • Bàsiques

  • CB5 - Que els estudiants hagin desenvolupat aquelles habilitats d'aprenentatge necessàries per emprendre estudis posteriors amb un alt grau d'autonomia

    • Competències Tècniques Generals

    Genèriques

  • CG1 - Concebre sistemes computacionals que integren dades de procedències i formes molt diverses, construeixen amb ells models matemàtics, raonen sobre aquests models i actuen en conseqüència, aprenent de l'experiència.
  • CG2 - Elegir i aplicar els mètodes i tècniques més adequats a un problema definit per dades que representin un repte pel seu volum, velocitat, varietat o heterogeneïtat, inclosos mètodes informàtics, matemàtics, estadístics i de processament del senyal.
  • CG5 - Poder recórrer a coneixements fonamentals i metodologies de treball sòlides adquirits durant els estudis per adaptar-se als nous escenaris tecnològics del futur.

    • Objectius

    1. Prendre consciència dels límits de la computació: comprendre les implicacions de la pregunta "P=NP?", entendre l'enunciat del Teorema de Cook-Levin, reconèixer i identificar diversos problemes NP-complets clàssics.
      Competències relacionades: CG5,
    2. Conèixer, explicar, dissenyar, analitzar, comparar i implementar algorismes de cerca exhaustiva fent servir la tècnica de backtracking.
      Competències relacionades: CE2, CB5,
    3. Conèixer l'esquema de programació dinàmica, identificar quan es pot aplicar i com, i familiaritzar-se amb alguns algorismes de programació dinàmica fonamentals.
      Competències relacionades: CE2,
    4. Conèixer l'esquema dels algorismes golafres, identificar quan es pot aplicar i com, conèixer les tècniques més habituals per a demostrar la seva correctesa i familiaritzar-se amb alguns algorismes golafres fonamentals.
      Competències relacionades: CE2,
    5. Completar i modificar implementacions, en el llenguatge de programació Python, de diversos algorismes per resoldre problemes de dificultat mitjana.
      Competències relacionades: CE2, CT6,
    6. Identificar i proposar solucions a possibles problemes d'eficiència en programes escrits en el llenguatge de programació Python.
      Competències relacionades: CE2, CT6,
    7. Desenvolupar projectes de mida mitjana com a membre d'un equip, aprenent així a dividir un projecte en parts petites, distribuir-les entre els seus membres i actuar amb responsabilitat de manera coordinada per a la correcta finalització de les tasques assignades.
      Competències relacionades: CE2, CT4, CT5, CT6, CT7, CG1, CG2,
    8. Conèixer algorismes basats en cerca local per a resoldre eficientment problemes intractables. Conèixer una varietat de metaheurístiques de diferent natura i ser capaç d'identificar quan i com es poden aplicar en problemes concrets computacionalment durs.
      Competències relacionades: CE2,
    9. Conèixer els fonaments d'autòmats finits i expressions regulars per tal de poder-los usar a la pràctica (cerca de patrons en textos, etc.).
      Competències relacionades: CE7,

    Continguts

    1. Tractabilitat: classes de problemes P i NP
      Classes P i NP, Teorema de Cook-Levin, reduccions, NP-completesa.
    2. Cerca exhaustiva
      Principis teòrics: espai de solucions, solucions parcials, poda. Exemples: subconjunts, permutacions, viatjant de comerç, suma de subconjunts.
    3. Programació dinàmica
      Esquema top-down (memoització). Esquema bottom-up (tabulació). Exemples: Fibonacci, nombres binomials, motxilla, multiplicació de seqüències de matrius.
    4. Algorismes golafres
      Principis teòrics: esquema general dels algorismos voraços. Exemples: planificació de tasques, etc.
    5. Metaheurístiques
      Cerca local. Simulated Annealing, Tabu Search, GRASP, algorismes genètics.
    6. Autòmats finits i expressions regulars
      Alfabets, mots, llenguatges. Autòmats finits deterministes, autòmats finits indeterministes, autòmats finits amb lambda-transicions, equivalència entre models d'autòmats, minimització d'autòmats. Expressions regulars, equivalència amb autòmats. Operacions.

    Activitats

    Activitat Acte avaluatiu


    Tractabilitat


    Objectius: 1
    Continguts:
    Teoria
    6h
    Problemes
    4h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Cerca Exhaustiva


    Objectius: 2 5 6
    Continguts:
    Teoria
    4h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Programació Dinàmica


    Objectius: 3 5 6
    Continguts:
    Teoria
    4h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Algorismes Golafres


    Objectius: 4 5 6
    Continguts:
    Teoria
    4h
    Problemes
    2h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Metaheurístiques


    Objectius: 8 5
    Continguts:
    Teoria
    4h
    Problemes
    0h
    Laboratori
    6h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Autòmats finits i expressions regulars


    Objectius: 9
    Continguts:
    Teoria
    4h
    Problemes
    4h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Consolidació


    Objectius: 2 1 3 4 9 8
    Continguts:
    Teoria
    4h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Examen parcial


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

    Projecte - Cerca Exhaustiva


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

    Projecte - Algorismes Golafres


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

    Examen de laboratori


    Objectius: 2 3 4 9 8 5 6
    Setmana: 13
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Projecte - Metaheurístiques


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

    Examen final


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

    Metodologia docent

    El temari s'exposa de forma molt pràctica, a través de la presentació de molts exemples.

    Les classes de teoria introdueixen tots els conceptes i tècniques necessaris, els quals es posen en pràctica en les classes de problemes i de laboratori mitjançant una col·lecció de problemes i exercicis en un jutge automàtic.

    Les dues hores de classes de teoria es fan setmanalment. Les dues hores de classes de laboratori es fan quinzenalment. Les dues hores de classes de problemes es fan quinzenalment.

    El projecte integra els coneixements i les competències de tot el curs.

    Mètode d'avaluació

    NPar = nota examen parcial
    NFT = nota examen final de teoria
    NFL = nota examen final de laboratori
    NPro = nota projecte

    NOTA FINAL = max( 30%Npar + 30%NFT + 20%NFL + 20% NPro, 60%NFT + 20%NFL + 20% NPro)

    La nota de l'examen de reavaluació, si n'hi ha i és més alta, substitueix la nota de l'examen final de teoria (NFT). Les notes de parcial, projecte i laboratori (NPar, NPro, NFL) es conserven.

    Si durant la correcció d'una activitat o pràctica el professorat té dubtes fonamentats sobre la
    informació o l'autoria del treball proporcionat per l'estudiant (com ara problemes incomplets,
    resultats no justificats de manera lògica o asimetries extremes de nivell), es retindrà la
    publicació de la nota provisional i es convocarà l'estudiant a una sessió de verificació oral
    abans d'emetre la qualificació definitiva.

    Bibliografia

    Bàsic

    Complementari

    Web links

    Capacitats prèvies

    - Familiaritat amb les tècniques bàsiques de programació: iteracions, alternatives, funcions recursives, pas de paràmetres, classes, objectes, mètodes, ...

    - Coneixement de conceptes algorísmics bàsics: eficiència d'algorismes, notació asimptòtica, grafs, recorregut de grafs, estructures de dades (llistes, arbres de cerca, hash, heaps, ...)

    - Coneixements bàsics de matemàtica discreta, àlgebra lineal i càlcul

    - Coneixements bàsics de teoria de probabilitat i estadística