Programació 2

Esteu aquí

Crèdits
7.5
Tipus
Obligatòries
Requisits
Aquesta assignatura no té requisits

Departament
CS
En aquesta assignatura s'introdueix el disseny modular i el disseny basat en objectes, fent servir el llenguatge de programació C++; s'estudien noves estructures de dades lineals (piles, cues, llistes) i arborescents (arbres binaris, n-aris, generals); s'aprofondeix en el disseny iteratiu i recursiu, tant en el raonament sobre la correcció dels dissenys com en la detecció i millora de solucions ineficients; i es presenten implementacions d'estructures de dades lineals i arborescents usant tipus recursius de dades.

Professors

Responsable

  • Juan Luis Esteban ángeles ( )
  • Maria Josefina Sierra Santibañez ( )

Altres

  • Borja Valles Fuente ( )
  • Jordi Petit Silvestre ( )
  • M. Luisa Bonet Carbonell ( )
  • Pilar Nivela Alos ( )
  • Ramon Ferrer Cancho ( )
  • René Alquezar Mancho ( )
  • Xavier Messeguer Peypoch ( )

Hores setmanals

Teoria
2
Problemes
0
Laboratori
3
Aprenentatge dirigit
0.5
Aprenentatge autònom
6.8

Competències

Competències Transversals

Treball en equip

  • G5 - 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. 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.
    Related competences: CT8.6, CT5.4, CT1.1B, CT1.1A,
  2. 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.
    Related competences: CT5.3, CT5.4, CT1.1B, CT1.1A,
  3. 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.
    Related competences: CT5.3, CT4.1, CT4.2, CT5.2, CT5.4,
  4. Donada una implementació per a una classe de dades senzilla, introduir millores a la seva representació i a les seves operacions.
    Related competences: CT5.1, CT5.3, CT5.2, CT5.4, CT1.2B,
  5. Explicar les fases del disseny modular.
    Related competences: CT5.1, CT5.3, CT5.4, CT1.1B, CT1.1A,
  6. 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.
    Related competences: CT5.1, CT5.3, CT5.2, CT5.4,
  7. 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.
    Related competences: CT5.3, CT3.6, CT4.1, CT4.2, CT5.2, CT5.4, CT1.2B, CT1.1A,
  8. 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.
    Related competences: CT8.6, CT5.3, CT3.6, CT5.4,
  9. 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.
    Related competences: CT1.1B, CT1.1A,
  10. 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ó.
    Related competences: CT8.6, CT5.3, G5.1, CT3.6,
  11. 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).
    Related competences: CT4.1, CT4.2, CT5.2, CT1.1A,
  12. 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.
    Related competences: CT4.1, CT4.2, CT5.2, CT1.1A,
  13. Descriure els passos principals del disseny d'algoritmes iteratius. Justificar la correctesa d'algoritmes iteratius relativament senzills.
    Related competences: CT5.3, CT3.6, CT4.2, CT1.1A,
  14. Descriure els passos principals del disseny d'algoritmes recursius. Justificar la correctesa d'algoritmes recursius relativament senzills.
    Related competences: CT5.3, CT3.6, CT4.2, CT1.1A,
  15. 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.
    Related competences: CT5.3, CT4.2, CT1.1A,
  16. Donat un algoritme recursiu senzill, determinar si existeix una manera simple d'obtenir un algoritme iteratiu equivalent, i si és així, escriure'l.
    Related competences: CT5.3, CT4.2, CT1.1A,
  17. 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).
    Related competences: CT4.1, CT4.2, CT5.2, CT1.1A,
  18. 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.
    Related competences: CT4.1, CT4.2, CT5.2, CT1.1A,
  19. 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.
    Related competences: CT4.1, CT4.2, CT5.2, CT1.1A,
  20. 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).
    Related competences: CT4.1, CT4.2, CT5.2, CT5.4, CT1.1A,
  21. Dissenyar algoritmes iteratius i recursius per resoldre problemes de cerca i recorregut en estructures de dades enllaçades utilitzant directament la seva representació.
    Related competences: CT4.1, CT4.2, CT5.2, CT5.4, CT1.1A,

Continguts

  1. 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.
  2. Estructures de dades lineals
    Piles, cues i llistes amb punt d'interés: especificació i ús (operacions de cerca i recorregut). Iteradors: definició i ús.
  3. Estructures de dades arborescents
    Arbres binaris, n-aris i generals: especificació. Ús d'arbres binaris: operacions de cerca i recorregut.
  4. Correctesa de programes iteratius
    Invariant d'un bucle. Justificació de la correctesa d'algoritmes iteratius.
  5. 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.
  6. 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.
  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

Introducció al disseny modular i al disseny basat en objectes.

Desenvolupament del tema corresponent de l'assignatura.
Teoria
4
Problemes
0
Laboratori
0
Aprenentatge dirigit
0
Aprenentatge autònom
4
  • Teoria: Sessions teoria setmanes 1 i 2.
Objectius: 1 2 3
Continguts:

Exercicis de repàs de C++.

Enllaç amb els continguts de PRO1.
Teoria
0
Problemes
0
Laboratori
3
Aprenentatge dirigit
0
Aprenentatge autònom
3
  • Laboratori: Sessió laboratori setmana 1
Objectius: 3 9
Continguts:

Especificació i ús de classes d'objectes en C++.

Exercicis del tema corresponent de l'assignatura.
Teoria
0
Problemes
0
Laboratori
6
Aprenentatge dirigit
0
Aprenentatge autònom
6
  • Laboratori: Sessions laboratori setmanes 2 i 3.
Objectius: 1 2 3
Continguts:

Implementació de classes d'objectes en C++.

Exercicis del tema corresponent de l'assignatura.
Teoria
0
Problemes
0
Laboratori
3
Aprenentatge dirigit
0
Aprenentatge autònom
3
  • Laboratori: Sessió laboratori setmana 4.
Objectius: 1 2 4
Continguts:

Exemple de disseny modular 1

Un exercici del tema corresponent de l'assignatura.
Teoria
0
Problemes
0
Laboratori
3
Aprenentatge dirigit
0
Aprenentatge autònom
3
  • Laboratori: Sessió laboratori setmana 5
Objectius: 1 2 5 6 7 8 9
Continguts:

Estructures de dades lineals.

Desenvolupament del tema corresponent de l'assignatura i exercicis de laboratori.
Teoria
2
Problemes
0
Laboratori
4
Aprenentatge dirigit
0
Aprenentatge autònom
6
  • Teoria: Sessió teoria setmana 3.
  • Laboratori: Sessió laboratori setmana 6 i primera hora de la sessió setmana 7
Objectius: 11
Continguts:

Estructures de dades arborescents.

Desenvolupament del tema corresponent de l'assignatura i exercicis de laboratori.
Teoria
2
Problemes
0
Laboratori
2
Aprenentatge dirigit
0
Aprenentatge autònom
4
  • Teoria: Sessió teoria setmana 4.
  • Laboratori: Dues hores últimes de la sessió de laboratori setmana 7.
Objectius: 12
Continguts:

Correctesa de programes iteratius

Desenvolupament del tema corresponent de l'assignatura.
Teoria
2
Problemes
0
Laboratori
0
Aprenentatge dirigit
0
Aprenentatge autònom
2
  • Teoria: Sessió teoria setmana 5
Objectius: 13
Continguts:

Exemple de disseny modular 2

Un exercici del tema corresponent de l'assignatura.
Teoria
0
Problemes
0
Laboratori
3
Aprenentatge dirigit
0
Aprenentatge autònom
3
  • Laboratori: Sessió laboratori setmana 8
Objectius: 1 2 5 6 7 8 9
Continguts:

Lliurament especificació pràctica

Els alumnes lliuraran un document amb l'especificació de la seva solució per a la pràctica.
Teoria
0
Problemes
0
Laboratori
3
Aprenentatge dirigit
0
Aprenentatge autònom
6
  • Laboratori: Sessió laboratori setmana 9.
Objectius: 1 2 5 6 7 8
Continguts:

Programació recursiva

Desenvolupament del tema corresponent de l'assignatura.
Teoria
3
Problemes
0
Laboratori
0
Aprenentatge dirigit
0
Aprenentatge autònom
3
  • Teoria: Sessió teoria setmana 6 i primera hora de la sessió setmana 7.
Objectius: 15 16 14
Continguts:

Exemple de disseny modular 3 + Revisió especificació pràctica

Un exercici del tema corresponent de l'assignatura.
Teoria
0
Problemes
0
Laboratori
3
Aprenentatge dirigit
0
Aprenentatge autònom
5
  • Laboratori: Sessió de laboratori setmana 10
Objectius: 1 2 5 6 7 8 9
Continguts:

Millores d'eficiència en programes recursius i iteratius.

Desenvolupament del tema corresponent de l'assignatura.
Teoria
3
Problemes
0
Laboratori
0
Aprenentatge dirigit
0
Aprenentatge autònom
3
  • Teoria: Segona hora de la sessió de teoria setmana 7 i sessió setmana 8.
Objectius: 13 15 16 17 18 14 19
Continguts:

Supervisió pràctica 1

Supervisió del disseny i implementació de la pràctica.
Teoria
0
Problemes
0
Laboratori
3
Aprenentatge dirigit
0
Aprenentatge autònom
9
  • Laboratori: Sessió laboratori setmana 11.
Objectius: 11 12 17 18 1 2 4 6 7 8 9
Continguts:

Supervisió pràctica 2

Supervisió del disseny i implementació de la pràctica.
Teoria
0
Problemes
0
Laboratori
3
Aprenentatge dirigit
0
Aprenentatge autònom
7
  • Laboratori: Sessió laboratori setmana 12.
Objectius: 11 12 17 18 1 2 4 6 7 8 9 10
Continguts:

Tipus recursius de dades.

Desenvolupament del tema corresponent de l'assignatura.
Teoria
10
Problemes
0
Laboratori
6
Aprenentatge dirigit
0
Aprenentatge autònom
16
  • Teoria: Sessions de teoria de les setmanes 9, 10, 11, 12 i 13
  • Laboratori: Sessions de laboratori de les setmanes 13 i 14
Objectius: 17 18 20 21 2 4 19
Continguts:

Repàs de teoria i problemes d'exàmens.

Els alumnes podran preguntar qüestions concretes sobre els temes donats a teoria.
Teoria
2
Problemes
0
Laboratori
0
Aprenentatge dirigit
0
Aprenentatge autònom
2
  • Teoria: Sessió teoria setmana 14.
  • Aprenentatge autònom: Resolució de problemes d'exàmens anteriors

Consolidació

Consolidació (setmana 15)
Teoria
2
Problemes
0
Laboratori
3
Aprenentatge dirigit
0
Aprenentatge autònom
6
  • Teoria: Sessió teoria setmana 15
  • Laboratori: Sessió laboratori setmana 15
  • Aprenentatge dirigit: Examen final
  • Aprenentatge autònom: Estudi examen final
Objectius: 11 12 13 15 16 17 18 20 21 14 19
Continguts:

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 els coneixements, tècniques i conceptes que es posen en pràctica en les classes de laboratori. També inclouen la presentación i discussió de les solucions d'un conjunt de problemes.

Les dues hores de classes de teoria es fan setmanalment. Les tres hores de classes de laboratori també es fan setmanalment.

La programació de la pràctica integra els coneixements i les competències de tot el curs, tret de l'últim contingut del temari (tipus de dades recursius) que s'avalua al segon examen parcial de teoria.

Mètode d'avaluació

La nota de les competències tècniques (NCTEC) es calcula de la manera següent:

NCTEC = 0.10*C + 0.25* EX_PAR1_TP + 0.15*EX_PRAC +
0.25*PRAC + 0.25*EX_PAR2_TP

on

* C és la nota del control de laboratori; per poder-se presentar en aquest control caldrà haver resolt satisfactòriament una sèrie d'exercicis de les sessions de laboratori de les tres primeres setmanes.

* EX_PAR1_TP i EX_PAR2_TP són les notes del primer i segon exàmens parcials de teoria

* EX_PRAC és la nota de l'examen de la pràctica

* PRAC és la nota de la pràctica

No obstant, NCTEC serà NP si el pes dels actes avaluatoris amb nota NP és igual o superior al 70%.


L'avaluació de la competència transversal Treball en Equip es realitzarà de la manera següent. Durant la realització de la pràctica es formaran equips d'estudiants, cadascun dels quals haurà de generar i lliurar un cert nombre de jocs de proves pel codi C++ de la pràctica. L'avaluació de la competència Treball en Equip per cada estudiant d'un equip es realitzarà utilitzant un document lliurat per l'equip on es descriuran les jocs de proves generats i la participació de cada membre de l'equip en la seva elaboració.



REAVALUACIÓ DE PRO2.

Hi haurà reavaluació d'aquesta assignatura. Consisteix en un curs intensiu de 12 hores presencials amb la corresponent avaluació, que es fan un cop finalitzats els exàmens finals i abans de l'inici del quadrimestre següent. Es calcula que la reavaluació requereix unes 50 hores de dedicació per part de l'estudiant entre classes presencials, hores d'estudi personal i avaluació. Només hi poden optar els estudiants que compleixen determinats requisits. Les places són limitades i s'assignaran per ordre decreixent de nota. Cada estudiant podrà fer com a molt la reavaluació d'una de les assignatures de fase inicial que s'ofereixen.

Requisits mínims per optar a la reavaluació.
Per a optar a la reavaluació és requisit indispensable estar matriculat de l'assignatura i haver obtingut una nota final entre 3.5 i 4.9. A més, cal haver obtingut un mínim de 4 sobre 10 de la nota global ponderada corresponent a la pràctica amb la ponderació establerta (2/3 de la nota PRAC, desenvolupament de la pràctica, i 1/3 de la nota EX_PRAC, l'examen de la pràctica).
Requisits per a ser avaluat del curs intensiu.
Per tal de ser avaluat del curs intensiu és obligatori:
- Assistir a totes les classes presencials.
- Fer els exercicis o activitats que demani el professorat del curs.

Preinscripció i admissió.
El procés d'inscripció es publicarà al racó. L'admissió i no assistència al curs pot comportar no ser admès en pròximes edicions.

Avaluació.
El resultat de l'avaluació del curs intensiu serà Apte o No apte. La nota definitiva de l'assignatura serà:
Nota definitiva = 5, si la nota de l' intensiu és Apte;
Nota definitiva = Nota assignatura, si la nota de l' intensiu és No apte;

on Nota assignatura és la nota sobre 10 obtinguda el quadrimestre.

Bibliografia

Bàsica:

Complementaria:

Web links

Capacitats prèvies

Tenir formació sobre les tècniques de programació imperativa basada en:
- instruccions bàsiques: assignació, alternativa, iteració
- accions i funcions; pas de paràmetres; recursivitat
- vectors i tuples; seqüències
- esquemes de recorregut i cerca
- algorismes fonamentals: cerca binària, ordenació de vectors, aritmètica de matrius

Conèixer bé almenys un llenguatge imperatiu, preferentment C++. Experiència en la posada en marxa de programes C++ en l'entorn Linux.

Capacitat per assimilar informació a partir d'un enunciat. Capacitat per argumentar sobre la correctesa d'un algorisme i per comparar solucions algorísmiques.