Algorísmia i Programació III

Esteu aquí

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.

Professors

Responsable

  • Enric Rodriguez Carbonell ( )

Altres

  • Albert Oliveras Llunell ( )

Hores setmanals

Teoria
2
Problemes
1
Laboratori
1
Aprenentatge dirigit
0.027
Aprenentatge autònom
5.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 - 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ó C++, 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ó C++.
    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

Teoria
4h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

Examen parcial


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

Projecte - Cerca Exhaustiva


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

Projecte - Algorismes Golafres


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

Examen de laboratori


Objectius: 2 3 4 9 8 5 6
Setmana: 13 (Fora d'horari lectiu)
Tipus: examen de laboratori
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
3h
Aprenentatge autònom
0h

Projecte - Metaheurístiques


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

Examen final


Objectius: 2 1 3 4 9 8
Setmana: 15 (Fora d'horari lectiu)
Tipus: examen final
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
3h
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.

El curs utilitza el llenguatge de programació C++.

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 s'escau, substitueix la nota de l'examen final de teoria (NFT). Les notes de parcial, projecte i laboratori (NPar, NFL, NPro) es conserven.

Bibliografia

Bàsica:

Complementaria:

Web links

Capacitats prèvies

- Familiaritat amb les tècniques bàsiques de programació i el llenguatge de programació C++: iteracions, alternatives, funcions recursives,
pas de paràmetres, punters, referències, memòria dinàmica, 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

Addenda

Continguts

No hi ha canvis respecte la informació publicada a la Guia Docent.

Metodologia docent

No hi ha canvis respecte la informació publicada a la Guia Docent.

Mètode d'avaluació

L'únic canvi previst és que l'examen de laboratori no es farà a la setmana 13, sinó en una data propera a l'examen final.

Pla de contingència

En cas que no es pugui dur a terme la docència de forma presencial, les classes (de teoria, problemes i laboratori) s'impartiran de forma remota mitjançant videoconferència; els continguts, la metodologia docent i el mètode d'avaluació continuaran igual.