Programació i Algorísmia II

• Professorat
• Hores setmanals
• Competències
• Objectius
• Continguts
• Activitats
• Metodologia docent
• Mètode d'avaluació
• Bibliografia
• Web links
• Capacitats prèvies

Professorat

Responsable

• Jordi Delgado Pin ( )
• Jose Luis Balcázar Navarro ( )

Altres

• Caroline König ( )

Hores setmanals

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.

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. Conèixer estructures de dades noves: Piles, Cues, Llistes, Arbres i Grafs i els algorismes associats a les operacions necessàries sobre aquestes estructures.
   Competències relacionades: CG2, CG4, CT6, CE03, CE04, CE12,
2. Conèixer diferentes implementacions d'estructures de dades: Implementacions fent servir estructures de dades més simples proporcionades pel llenguatge de programació, i implementacions dinàmiques.
   Competències relacionades: CG2, CG4, CE02, CE03, CE04, CE12,
3. Conèixer els principis bàsics de l'orientació a objectes: Conceptes de classe, instància, mètode, herència (simple i múltiple), etc.
   Competències relacionades: CG2, CG4, CT6, CE03, CE04, CE10,
4. Ampliació de Complexitat Computacional: Big O, Big Omega, Master Theorems
   Competències relacionades: CG2, CG4, CT6, CE02, CE12, CE13,
5. Resoldre en grup un problema de mida petita-mitjana aplicant allò aprés sobre orientació a objectes
   Competències relacionades: CG2, CG4, CG8, CT4, CE03, CE04, CE10,

Continguts

1. Arbres i Grafs
   Començarem el curs utilitzant les estructures de dades que el llenguatge de programació ens proporciona per implementar els Arbres i els Grafs. Veurem algorismes de recorregut per a les dues estructures, i d'altres algorismes importants relacionats amb aquestes, com per exemple l'algorisme de Dijkstra.
2. Objectes i Classes
   S'introdueixen els conceptes fonamentals d'orientació a objectes: Classe, objecte, instància, delegació, herència, etc i altres particularitats de la implementació de l'orientació a objectes pròpies del llenguatge de programació amb que treballem.
3. Estructures dinàmiques de dades
   S'estudia com implementar estructures de dades conegudes utilitzant el concepte de referència a un objecte. Es re-implementaran d'aquesta manera estrucures de dades que el llenguatge de programació proporciona per defecte, i estructures de dades noves que ja hem vist implementades de manera més senzilla.
4. Conjunts i Diccionaris: Implementació
   Veurem diferentes maneres d'implementar conjunts i diccionaris: Taules Hash i arbres binaris de cerca (BSTs). S'estudiaran les propietats d'aquestes estructures, els avantatges i inconvenients.
5. Ampliació de Complexitat Algorísmica
   A PA1 es va començar a veure el concepte de complexitat d'un programa, un algorisme i un problema, i vam introduir la notació asimptòtica, concretament la definició de Theta(f). Aquest tema vol ser una continuació, on veurem la Big O, la Big Omega, etc, i els Master Theorems.

Activitats

Activitat Acte avaluatiu

Metodologia docent

Mètode d'avaluació

Bibliografia

Bàsica:

• Composing programs - DeNero, John,
  
• Structure and interpretation of computer programs - Abelson, Harold; Sussman, Gerald Jay; Sussman, Julie, MIT Press [etc.], 1996. ISBN: 9780262011532
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002456139706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Data structures and algorithms with Python - Lee, Kent D; Hubbard, Steve, Springer, 2014. ISBN: 9783319130712
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004152009706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Complementaria:

• Python pocket reference - Lutz, Mark, O'Reilly Media , 2014. ISBN: 9781449356941
  

Web links

• Aquest és el text PRINCIPAL de l'assignatura, la font d'informació primària per a tot allò que expliquem a classe. Tot i això, a PA2 hi ha temes que no apareixen en aquest text. http://composingprograms.com/
• La principal referència del llenguatge de programació que fem servir: Python. No és un lloc on aprendre a programar, és un lloc on consultar detalls de les construccions i llibreries del llenguatge https://docs.python.org/3/reference/index.html

Capacitats prèvies