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.
Professorat
Responsable
M. Luisa Bonet Carbonell (
)
Pau Fernandez Duran (
)
Altres
Albert Calvo Ibañez (
)
Alejandro Ivan Paz Ortiz (
)
Alfonso Valverde Ruiz (
)
Borja Valles Fuente (
)
Guillem Godoy Balil (
)
Jorge Castro Rabal (
)
Jose Carmona Vargas (
)
Juan Luis Esteban Ángeles (
)
Maria Josefina Sierra Santibañez (
)
Santiago Marco Sola (
)
Xavier Messeguer Peypoch (
)
Hores setmanals
Teoria
2
Problemes
0
Laboratori
3
Aprenentatge dirigit
0.3
Aprenentatge autònom
7.2
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
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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
Estructures de dades lineals
Piles, cues, llistes, maps i sets: especificació i ús (operacions de cerca i recorregut). Iteradors: definició i ús.
Estructures de dades arborescents
Arbres binaris.
Correctesa de programes iteratius
Invariant d'un bucle. Justificació de la correctesa d'algoritmes iteratius.
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.
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.
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.
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.
Els alumnes podran preguntar qüestions concretes sobre els temes donats a teoria.
Teoria: Sessió teoria setmana 14.
Aprenentatge autònom: Resolució de problemes d'exàmens anteriors
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
2h
EX_SIMUL1
Examen de simulacre per al Parcial 1 Objectius:10111617192023567818 Setmana:
8 (Fora d'horari lectiu)
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
2h
Aprenentatge autònom
2h
EX_PAR1_TP
Primer examen parcial de teoria i problemes. Objectius:10111617192023567818 Setmana:
9 (Fora d'horari lectiu)
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
5h
CODI_DOC_PRAC
Lliurament del codi i la documentació de la pràctica. Objectius:101112141617211567891318 Setmana:
12 (Fora d'horari lectiu)
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h
EX_SIMUL2
Examen de simulacre per al Parcial 2 Objectius:10111617192023567818 Setmana:
13 (Fora d'horari lectiu)
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
2.5h
Aprenentatge autònom
2.5h
EX_PAR2_TP
Segon examen parcial de teoria i problemes Objectius:10111617192023567818 Setmana:
15 (Fora d'horari lectiu)
Teoria
2.5h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
6.5h
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, potser tret de l'últim contingut del temari (tipus de dades recursius), que s'avalua al segon examen de teoria.
Mètode d'avaluació
La nota de les competències tècniques (NCTEC) es calcula de la manera següent:
* EXAM1 I EXAM2 són les notes del primer i segon exàmens parcials de teoria
* PRAC és la nota de la pràctica; podrà tenir un component obtingut automàticament mitjançant l'execució amb jocs de proves, i un component obtingut per correcció manual
* DELIVERY és la nota obtinguda de les entregues de resolució d'exercicis portats a terme pels estudiants durant el curs.
* VERIF és la nota d'un petit control sobre correctesa d'algorismes iteratius i recursius fet a classe de teoria.
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à a partir de l'el·laboració, en equips d'estudiants, de jocs de proves complets per la pràctica.
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 d'entre 3.5 i 4.9. A més, cal que 0.25*PRAC + 0.10*DELIVERY >= 1.5.
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ó del curs de reavaluació
Es farà un examen de reavaluació (REVAL). El resultat de l'avaluació del curs intensiu serà Apte si 0.6*REVAL + 0.25*PRAC + 0.10*DELIVERY + 0.05*VERIF >=5, i NoApte en cas contrari. 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 NoApte;
on NOTA_ASSIGNATURA és la nota sobre 10 obtinguda al curs quadrimestral.
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
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.