Programació II

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

Professorat

Responsable

• Borja Valles Fuente ( )
• Guillem Godoy Balil ( )
• Juan Luis Esteban Ángeles ( )

Altres

• Albert Calvo Ibañez ( )
• Alejandro Ivan Paz Ortiz ( )
• Alfonso Valverde Ruiz ( )
• Jorge Castro Rabal ( )
• Jose Carmona Vargas ( )
• M. Luisa Bonet Carbonell ( )
• Maria Josefina Sierra Santibañez ( )
• Pau Fernandez Duran ( )
• Santiago Marco Sola ( )
• Xavier Messeguer Peypoch ( )

Hores setmanals

Competències

Competències Transversals

Treball en equip

• G5 [Avaluable] - Ser capaç de treballar com a membre d'un equip, ja sigui com a un membre més, ja sigui realitzant tasques de direcció, amb la finalitat de contribuir a desenvolupar projectes d'una manera pragmàtica i amb sentit de la responsabilitat; assumir compromisos tenint en compte els recursos disponibles.
  • G5.1 - Capacitat de col·laborar en un entorn unidisciplinar. Identificar els objectius del grup i col·laborar en el disseny de l'estratègia a seguir i del pla de treball per a aconseguir-los. Identificar les responsabilitats de cada component del grup i assumir el compromís personal de la tasca assignada. Avaluar i presentar els resultats propis. Identificar el valor de la cooperació i intercanviar informació amb els altres components del grup. Intercanviar informació sobre el progrés del grup i proposar estratègies per millorar-ne el funcionament.

Competències Tècniques

Competències tècniques comunes

• CT1 - Demostrar coneixement i comprensió de fets essencials, conceptes, principis i teories relatives a la informàtica i a les seves disciplines de referència.
  • CT1.1A - Demostrar coneixement i comprensió dels conceptes fonamentals de la programació i de l'estructura bàsica d'un computador. CEFB4. Coneixement dels fonaments de l'ús i de la programació dels computadors, dels sistemes operatius, de les bases de dades i, en general, dels programes informàtics amb aplicació a l'enginyeria.
  • CT1.1B - Demostrar coneixement i comprensió dels conceptes fonamentals de la programació i de l'estructura bàsica d'un computador. CEFB5. Coneixement de l'estructura, funcionament i interconnexió dels sistemes informàtics, i dels fonaments de la seva programació.
  • CT1.2B - Interpretar, seleccionar i valorar conceptes, teories, usos i desenvolupaments tecnològics relacionats amb la informàtica i la seva aplicació a partir dels fonaments matemàtics, estadístics i físics necessaris. CEFB2. Capacitat per a comprendre i dominar els fonaments físics i tecnològics de la informàtica: electromagnetisme, ones, teoria de circuits, electrònica i fotònica i la seva aplicació per a la resolució de problemes propis de l'enginyeria.
• CT3 - Demostrar coneixement i comprensió del context organitzatiu, econòmic i legal en el qual es desenvolupa la seva feina (coneixement adequat del concepte d'empresa, del marc institucional i jurídic de l'empresa, d'organització i gestió de les empreses).
  • CT3.6 - Demostrar coneixement de la dimensió ètica a l'empresa: la responsabilitat social i corporativa en general i, en particular, les responsabilitats civils i professionals de l'enginyer en informàtica.
• CT4 - Demostrar coneixement i capacitat d'aplicació dels procediments algorísmics bàsics de les tecnologies informàtiques per a dissenyar solucions a problemes, analitzant la idoneïtat i la complexitat dels algorismes
  • CT4.1 - Identificar les solucions algorísmiques més adequades per a resoldre problemes de dificultat mitjana.
  • CT4.2 - Raonar sobre la correcció i l'eficiència d'una solució algorísmica.
• CT5 - Analitzar, dissenyar, construir i mantenir aplicacions de forma robusta, segura i eficient, triant el paradigma i els llenguatges de programació més adequats.
  • CT5.1 - Triar, combinar i explotar diferents paradigmes de programació, en el moment de construir software, tenint en compte criteris com la facilitat de desenvolupament, l'eficiència, la portabilitat i la mantenibilitat.
  • CT5.2 - Conèixer, dissenyar i utilitzar de forma eficient els tipus i les estructures de dades més adients per a la resolució d'un problema.
  • CT5.3 - Dissenyar, escriure, provar, depurar, documentar i mantenir codi en un llenguatge d'alt nivell per a resoldre problemes de programació aplicant esquemes algorísmics i utilitzant estructures de dades.
  • CT5.4 - Dissenyar l'arquitectura dels programes utilitzant tècniques d'orientació a objectes, de modularització i d'especificació i implementació de tipus abstractes de dades.
• CT8 - Planificar, concebre, desplegar i dirigir projectes, serveis i sistemes informàtics en tots els àmbits, liderar-ne la posada en marxa, la millora contínua i valorar-ne l'impacte econòmic i social.
  • CT8.6 - Demostrar comprensió de la importància de la negociació, dels hàbits de treball efectius, del lideratge i de les habilitats de comunicació en tots els entorns de desenvolupament de software.

Objectius

1. Dissenyar una classe de dades amb una clara independència entre la seva especificació i la seva implementació. Justificar que l'única forma de crear, consultar o modificar un objecte d'una clase de dades sigui a través de les operacions de l'especificació de la mateixa.
   Competències relacionades: CT5.4, CT5.3, CT1.1B, CT1.1A,
2. Resoldre en C++ qualsevol exercici basat en l'aplicació d'un esquema algorísmic senzill sobre un vector format per objectes d'una classe de dades.
   Competències relacionades: CT4.1, CT4.2, CT5.2, CT5.4, CT5.3,
3. Donada una implementació per a una classe de dades senzilla, introduir millores a la seva representació i a les seves operacions.
   Competències relacionades: CT5.2, CT5.4, CT5.1, CT5.3, CT1.2B,
4. Explicar les fases del disseny modular.
   Competències relacionades: CT5.4, CT5.1, CT5.3, CT1.1B, CT1.1A,
5. Identificar en un enunciat textual d'un problema les abstraccions de dades susceptibles de donar lloc a classes que permetin resoldre el problema. Comprovar si alguna de les abstraccions identificades ja han estat detectades en situacions anteriors per tal de reutilitzar la classe corresponent.
   Competències relacionades: CT5.2, CT5.4, CT5.1, CT5.3,
6. Disenyar de forma individual un programa modular en C++ a partir de les abstraccions de dades extretes del enunciat d'un problema. Afegir o modificar alguna funcionalitat d'un programa modular en C++ donat.
   Competències relacionades: CT3.6, CT4.1, CT4.2, CT5.2, CT5.4, CT5.3, CT1.2B, CT1.1A,
7. Codificar un programa modular en C++ amb bon estil i de forma que d'altres programadors siguin capaços d'entendre què fa i treballar sobre ell. Produir la documentació associada a un programa modular en C++ de manera que s'afavoreixi el seu ús per qualsevol altre programador.
   Competències relacionades: CT8.6, CT3.6, CT5.4, CT5.3,
8. Preparar un programa en C++ que faci servir tipus simples i classes de dades, algunes d'elles predefinides i d'altres definides pel propi alumne, per poder ser executat. Això s'ha de poder fer de dues maneres: 1) a base de compilar i muntar manualment amb el comandament g++; i 2) amb un makefile.
   Competències relacionades: CT1.1B, CT1.1A,
9. Disenyar entre un grup d'estudiants un programa modular en C++ i/o un conjunt de jocs de proves que tractin totes les funcionalitats del mateix. Depurar sistemàticament aquest programa, de forma que s'hi puguin eliminar en un temps raonable petits errors d'implementació.
   Competències relacionades: CT8.6, G5.1, CT3.6, CT5.3,
10. Conèixer els tipus de dades utilitzats habitualment per representar i manegar estructures de dades lineals i la seva especificació. Dissenyar algoritmes iteratius i recursius per resoldre problemes de cerca i recorregut en piles, cues i llistes, usant les operacions del tipus de dades corresponent i iteradors (quan sigui recomanable).
    Competències relacionades: CT4.1, CT4.2, CT5.2, CT1.1A,
11. Conèixer tipus de dades utilitzats per representar i manegar estructures de dades arborescents i la seva especificació. Dissenyar algoritmes recursius per resoldre problemes de cerca i recorregut en arbres binaris, n-aris i generals usant les operacions del tipus de dades corresponent.
    Competències relacionades: CT4.1, CT4.2, CT5.2, CT1.1A,
12. Descriure els passos principals del disseny d'algoritmes iteratius. Justificar la correctesa d'algoritmes iteratius relativament senzills.
    Competències relacionades: CT3.6, CT4.2, CT5.3, CT1.1A,
13. Descriure els passos principals del disseny d'algoritmes recursius. Justificar la correctesa d'algoritmes recursius relativament senzills.
    Competències relacionades: CT3.6, CT4.2, CT5.3, CT1.1A,
14. Conèixer el concepte d'immersió d'una funció, i explicar la diferència entre immersions d'especificació i immersions d'eficiència. Conèixer els diferents tipus d'immersions d'especificació i els diferents tipus d'immersions d'eficiencia.
    Competències relacionades: CT4.2, CT5.3, CT1.1A,
15. Donat un algoritme recursiu senzill, determinar si existeix una manera simple d'obtenir un algoritme iteratiu equivalent, i si és així, escriure'l.
    Competències relacionades: CT4.2, CT5.3, CT1.1A,
16. Determinar si el cost d'un algoritme iteratiu o recursiu senzill donat que treballi sobre vectors, piles, cues, llistes o arbres és lineal o si és quadràtic (suposant que el cost sigui d'un d'aquests dos tipus).
    Competències relacionades: CT4.1, CT4.2, CT5.2, CT1.1A,
17. Determinar si es pot millorar l'eficiència d'un algoritme recursiu senzill donat i, en cas de que sigui possible, dissenyar un algoritme recursiu alternatiu més eficient usant immersions d'eficiència.
    Competències relacionades: CT4.1, CT4.2, CT5.2, CT1.1A,
18. Determinar si es pot millorar l'eficiència d'un algoritme iteratiu senzill donat i, en cas de que sigui possible, dissenyar un algoritme iteratiu alternatiu més eficient.
    Competències relacionades: CT4.1, CT4.2, CT5.2, CT1.1A,
19. Implementar una estructura de dades amb requeriments específics sobre les seves operacions i/o l'eficiència de les mateixes usant tipus de dades recursius (o estructures de dades enllaçades).
    Competències relacionades: CT4.1, CT4.2, CT5.2, CT5.4, CT1.1A,
20. Dissenyar algoritmes iteratius i recursius per resoldre problemes de cerca i recorregut en estructures de dades enllaçades utilitzant directament la seva representació.
    Competències relacionades: CT4.1, CT4.2, CT5.2, CT5.4, CT1.1A,
21. Diferenciar els rols d'usuari, especificador i implementador de classes de dades. Conèixer els elements de l'especificació d'una classe de dades. Conèixer els elements de la implementació d'una classe de dades.
    Competències relacionades: CT8.6, CT5.4, CT1.1B, CT1.1A,

Continguts

1. Estructures de dades lineals
   Piles, cues, llistes, maps i sets: especificació i ús (operacions de cerca i recorregut). Iteradors: definició i ús.
2. Estructures de dades arborescents
   Arbres binaris.
3. Correctesa de programes iteratius
   Invariant d'un bucle. Justificació de la correctesa d'algoritmes iteratius.
4. Programació recursiva i correctesa d'algoritmes recursius
   Disseny inductiu d'algoritmes recursius. Justificació de la correctesa d'algoritmes recursius. Immersió (o generalització) d'una funció. Immersions d'especificació: per afebliment de la postcondició i per reforçament de la precondició. Relació entre algoritmes recursius lineals finals i algoritmes iteratius.
5. Millores d'eficiència en programes recursius i iteratius
   Detecció de la repetició de càlculs en programes recursius i iteratius. Immersions d'eficiència: nous dades (paràmetres d'entrada) i/o resultats (valors retornats o paràmetres de sortida) en operacions recursives per millorar l'eficiència. Noves variables locals que usen el seus valors en anteriors iteracions per millorar l'eficiència d' operacions iteratives.
6. Disseny modular i disseny basat en objectes
   Abstracció i la seva necessitat. Descomposició funcional i per dades. Mòduls. Ocultació de la informació.
   Encapsulat. Fases del disseny modular: distinció entre especificació i implementació. Tipus de mòduls i el seu ús. Biblioteques.
   
   Principis bàsics de disseny basat en objectes: classes i objectes; camps i mètodes.
   
   Implementació de dissenys modulars en C++. Compilació separada i muntatge. Depuració, prova i documentació de programes modulars.
7. Tipus recursius de dades
   Introducció a l'ús de tipus recursius de dades. El constructor de tipus punter i la gestió de memòria
   dinàmica. Implementació d'estructures de dades enllaçades mitjançant tipus recursius de dades. Algoritmes iteratius i recursius per resoldre problemes de cerca i recorregut en estructures de dades enllaçades accedint directament a la representació basada en nodes y punters a nodes.

Activitats

Activitat Acte avaluatiu

Metodologia docent

Mètode d'avaluació

Bibliografia

Bàsica:

• Apunts de teoria de PRO2 - Alquezar, René; Valles, Borja; [et al.],
  http://www.lsi.upc.es/~pro2/index.php?id=material-docent
• Sessions de Laboratori de PRO2 - Valles, Borja; [et al.],
  http://www.lsi.upc.es/~pro2/index.php?id=material-docent
• Iniciació a la Programació (notes de curs) - Cortadella, Jordi; Rubio, Albert; Valentin, Luis, 2001.
  http://www.lsi.upc.es/~pro2/index.php?id=material-docent
• Data structures and problem solving using C++ - Weiss, M.A, Pearson Education International, 2003. ISBN: 0321205006
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002579369706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• STL tutorial and reference guide: C++ programming with the standard template library - Musser, D.R.; Derge, G.J.; Saini, A, Addison-Wesley publishing company, 2000. ISBN: 0201379236
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003780719706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Complementaria:

• Curs de programació - Castro, J. [et al.], McGraw-Hill , 1992. ISBN: 844810031X
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000672229706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Programación metódica - Balcazar, J.L, McGraw-Hill , 1993. ISBN: 8448119576
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000866429706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Problem solving with C++ - Savitch, Walter J; Mock, Kenrick, Pearson , [2018]. ISBN: 9780134448282
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004158189706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Web links

• Manual de referència sobre els containers de la llibreria STL de C++. http://www.cplusplus.com/reference/stl/
• Curs de C++. Ideal com a manual de referència. http://c.conclase.net/curso/index.php
• Pàgina web dels professors de l'assignatura. Conté tota la documentació rellevant: apunts, col·leccions d'exercicis, enunciat de la pràctica. http://www.cs.upc.edu/~pro2

Capacitats prèvies