103131 - ESTRUCTURA DE DADES I ALGORISMES

Tipus d'assignatura: Obligatòria

Coordinador: Alfons Palacios Gonzàlez

Trimestre: Tercer trimestre

Crèdits: 4

Enunciats de pràctiques i/o exàmens poden ser en anglès.

Aquesta assignatura tanca el bloc de les assignatures de programació del primer curs. Està dividida en quatre: en la primera part s'estudia l'ús dels magatzems de dades volàtils (en memòria) més freqüents: cues i piles, llistes, conjunts, maps, ... tot continuant l'aproximació OO iniciada a les assignatures prèvies. La segona part és una breu introducció a les tècniques de programació recursiva. La tercera part mostra la utilització d'arxius com a eina d'emmagatzematge no volàtil. La darrera part és una introducció a la complexitat algorísmica. 

Si per motius relacionats amb la COVID-19 l'assignatura s'hagués d'impartir en modalitat no-presencial o en alguna  modalitat que representés una disminució sensible de la presencialitat la, metodologia de les sessions s'adaptarà a aquestes L'objectiu darrer d'aquesta adaptació serà el de preservar al màxim l'assoliment dels coneixements i de les competències especificades en aquest pla docent.
 

A nivell general, aquesta assignatura contribueix als següents resultats d'aprenentatge especificats per a la matèria a la qual pertany (Algorísmica i Programació)

• Demostrar coneixement i comprensió de fets essencials, conceptes, principis i teories relatives a la informàtica i a les seves disciplines de referència.
• Aplicar tècniques bàsiques de descomposició modular de problemes
• Dissenyar l'arquitectura dels programes utilitzant tècniques d'orientació a objectes, de modularització i d'especificació i implementació de tipus abstractes de dades.
• Construir algorismes correctes i eficients per a problemes de dificultat petita.
• Implementar algorismes senzills en un llenguatge de programació imperatiu de referència per al nivell inicial
• Identificar les solucions algorísmiques més escaients per a resoldre problemes de dificultat mitjana
• Raonar sobre la correcció i l'eficiència d'una solució algorísmica.
• 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 usant estructures de dades. 
• Usar les eines d'un entorn de desenvolupament de software per a crear i desenvolupar aplicacions

A un nivell més concret, en acabar l’assignatura l’estudiant o estudianta ha de ser capaç de:

• RA1: Aplicar tècniques recursives per a la resolució de problemes. Codificar programes de naturalesa recursiva.
• RA2: Conèixer l'especificació d'alt nivell de col·leccions de dades com les piles, les cues, les llistes, els conjunts i els diccionaris (col·leccions associatives). Fer ús d'aquestes col·leccions en programes, tot aplicant-hi algorismes escaients.
• RA3: Seleccionar les col·leccions de dades més escaients per a un problema donat
• RA4: Emmagatzemar i recuperar informació d'arxius.
• RA5: Mostrar coneixement sobre les diferents classes de complexitat computacional

Tots els conceptes teòrics de la matèria s'exposaran en classes de teoria (grups grans). En aquestes classes, i a discreció dels docents impartidors, també es resoldran exercicis i problemes de caire més pràctic. Així mateix, i sempre a discreció dels impartidors, es podrà demanar als estudiants que resolguin, de manera individual o en grup, problemes i/o exercicis breus. Aquestes activitats, breus i optatives, serviran a l'estudiant com a instrument d'autoavaluació del seu assoliment dels continguts de la matèria i podran ser utilitzades per part del docent per a prendre decisions sobre la qualificació final de l'estudiant bo i que mai en detriment de la qualificació numèrica calculada segons el sistema de qualificació especificat per l'assignatura.

Els estudiants haurien d'assistir a totes les classes amb un ordinador portàtil amb la capacitat d’executar el software escaient per a l’assignatura. Els docents impartidors informaran de quin és aquest software i com es pot obtenir.

Els conceptes de caire més pràctic i tot el que en essència es pugui considerar l'aplicació pràctica dels conceptes teòrics seran treballats de manera més intensiva en grups petits (de laboratori). En les sessions que es programin a aquest efecte es donaran les eines escaients per a resoldre les activitats programades bo i que s'espera que aquestes s'allarguin des del punt de vista temporal, més enllà de les hores de laboratori i que, en conseqüència, els estudiants les hagin de finalitzar durant el temps d'aprenentatge autònom.

Es posarà a disposició dels estudiants activitats de caire totalment opcional que els ajudin a preparar i a preparar-se per a les de caire obligatori.

1.- Col·leccions de dades

• Col·leccions seqüencials (piles, cues, llistes)
• Conjunts
• Col·leccions associatives (maps o diccionaris)

2.- Recursivitat

• Algorismes recursius vs. algorismes iteratius
• Tractament recursiu de seqüències. Estratègies

3.- Magatzems permanents: arxius

• E/S vers i des d'arxius. Canals
• Arxius de text
• Arxius de dades (binaris)

4.- Introducció a la complexitat algorísmica

Es posa a disposició dels estudiants tot un seguit d'activitats de caire eminentment pràctic (exercicis curts, problemes...) que són la base de les activitats d'aprenentatge de l'assignatura. Aquestes activitats els estudiants/es les hauran de resoldre, sovint de manera no presencial, seguint les indicacions dels docents i també seran treballades a classe, ja sia com a exemples en les sessions de teoria, ja sia en les sessions de laboratori. Si bé aquestes activitats tindran caràcter optatiu (els docents no en verificaran de manera individualitzada la realització per part dels estudiants), seran imprescindibles per assolir els coneixements teorico-pràctics de l'assignatura.

Amb l’objectiu de recollir evidència de l’assoliment dels  resultats d’aprenentatge esperats es realitzaran les següents activitats de caràcter avaluatiu:

Dues proves escrites (utilitzant, quan s’escaigui, una eina IDE)

• La primera prova versarà sobre el primer contingut (col·leccions de dades) i donarà evidència dels resultats d’aprenentatge RA2 i RA3.  Aquesta prova demana als estudiants el desenvolupament correcte de software a partir d’una base preestablerta. Això té a veure amb les següents competències comunes i específiques (entre parèntesis els aspectes més rellevants de cada competència als quals l’assignatura contribueix)
  • CIN1(desenvolupar programari),
  • CIN5(mantenir programari),
  • CIN6(aplicar procediments algorísmics),
  • CIN7(usar estructures de dades),
  • CIN8(construir i mantenir aplicacions),
  • EFB3(comprendre i dominar els conceptes de l’algorísmica)  i
  • EFB4(ús de programes informàtics)

• La segona prova inclourà tots els continguts i donarà evidència de tots els resultats d’aprenentatge previstos. Aquesta prova demana als estudiants el desenvolupament correcte de software a partir d’una base preestablerta i inclou l’ús de la recursivitat i dels arxius. A nivell de competències comunes i específiques seran rellevants totes les esmentades per a la primera prova afegint-hi:
  • CIN13(coneixement i aplicació de les eines necessàries per a l’emmagatzematge)

Es realitzaran també quatre pràctiques:

• En les dues primeres pràctiques, els estudiants hauran de codificar, provar, depurar i documentar programes que facin ús de col·leccions de dades. Amb això es podrà recollir evidència dels resultats d’aprenentatge RA2 i RA3.
• En la tercera pràctica es treballarà, sobretot, la codificació, prova, depuració i documentació de programes de naturalesa recursiva. Amb això es podrà recollir evidència del resultat d’aprenentatge RA1.
• En la quarta pràctica es treballarà, sobretot, la codificació, prova, depuració i documentació de programes que facin ús de col·leccions de dades i d’arxius, recollint així evidència dels resultats d’aprenentatge RA2, RA3 i RA4.  

A nivell competencial les quatre pràctiques, que majoritàriament s’hauran de desenvolupar en temps no presencial, cobreixen totes les competències comunes i específiques de l’assignatura:

• CIN1(desenvolupar programari),
• CIN3(hàbits de treball efectius en els entorns de desenvolupament de software)
• CIN5(mantenir programari),
• CIN6(aplicar procediments algorísmics),
• CIN7(usar estructures de dades),
• CIN8(construir i mantenir aplicacions),
• CIN13(coneixement i aplicació de les eines necessàries per a l’emmagatzematge)
• EFB3(comprendre i dominar els conceptes de l’algorísmica)  i
• EFB4(ús de programes informàtics)

Per tal de superar (aprovar) les activitats avaluatives, els estudiants hauran de demostrar

• Que han adquirit els coneixements teòrics relatius als continguts de l’assignatura i que la seva comprensió els permet de portar-los a la pràctica [MECES-2 punt a, punt c]
• Que poden desenvolupar solucions a problemes que, si bé són semblants a d’altres vistos anteriorment, presenten aspectes que són nous [MECES-2 punt f]

En relació a les competències bàsiques assignades a l’assignatura, aquestes queden cobertes especialment pel que fa als aspectes que s’expliciten:

• CB2: resolució de problemes dins de la seva àrea d’estudi.
• CB5: desenvolupament d’habilitats d’aprenentatge necessàries per a estudis posteriors (accés autònom a documentació, hàbits de treball efectius)

Finalment, i pel que fa a la competència transversal associada a l’assignatura (CT1: coneixement tercera llengua) aquesta es treballa a partir de les fonts documentals que els estudiants han de consultar, atès que totes elles es troben en anglès. En algunes ocasions també es subministren en anglès (només) els enunciats d’algunes de les pràctiques de l’assignatura.

Per a cada activitat, els docents n'informaran de les normes i condicions particulars que les regeixin.

Les activitats unipersonals pressuposen el compromís de l'estudiant de realitzar-les de manera individual i sense cap mena de col·laboració amb d’altres persones. Es consideraran suspeses (qualificació 0) totes aquelles activitats en què l'estudiant no s'ajusti a aquest compromís d’individualitat,  independentment del seu paper (emissor o receptor) i sense que això exclogui la possible aplicació d’altres sancions d’acord amb el Règim Disciplinari vigent.

Igualment, les activitats que s'hagin de realitzar en grup pressuposen el compromís per part dels estudiants que l'integren de realitzar-les en el si del grup i sense cap mena de col·laboració amb d’altres grups o persones que en siguin alienes (individualitat grupal). Es consideraran suspeses (qualificació 0) totes aquelles activitats en què el grup no hagi respectat aquest compromís amb independència del seu paper (emissor o receptor) i sense que això exclogui la possible aplicació d’altres sancions d’acord amb el Règim Disciplinari vigent.

En el cas particular de les pràctiques, quan en alguna d’elles no es respecti el compromís d’individualitat i/o s’utilitzin mitjans fraudulents en la seva realització, la qualificació de pràctiques (Pr) serà, per a tots els membres del grup, de 0 punts (Pr=0) amb independència de la qualificació de les altres pràctiques i sense que això exclogui la possible aplicació d’altres sancions d’acord amb el Règim Disciplinari vigent.

Qualsevol activitat no lliurada es considerarà puntuada amb zero punts

És potestatiu dels docents acceptar o no lliuraments fora dels terminis que s'indiquin. En el cas que aquests lliuraments fora de termini s'acceptin, és potestatiu del docent decidir si aplica alguna penalització i la quantia d'aquesta.

La qualificació final de l’assignatura (QF) es calcularà segons es detalla a continuació

Pe1: qualificació de la primera prova escrita

Pe2: qualificació de la segona prova escrita

Teo: qualificació de teoria

Pr_i: qualificació de la i-èssima pràctica

Pr: qualificació de pràctiques

QPT: qualificació ponderada teoria + pràctiques

QF: qualificació final de l’assignatura

Teo = max( (Pe1+Pe2)/2, Pe2)

Pr = mitjana(Pr_i)

QPT = Pr·0.35 + Teo·0.65

QF = Teo si Teo < 4

QF = QPT si Teo ≥ 4

Es responsabilitat de l'alumne evitar el plagi en totes les seves formes. En el cas de detectar un plagi, independentment del seu abast, en alguna activitat, correspondrà a tenir una nota de 0. A més, el professor comunicarà a la Cap d'Estudis la situació per a que en prengui mesures  aplicables en matèria de règim sancionador. En el context d'aquesta assignatura, plagi també significa utilitzar i/o adaptar codi que no s'hagi desenvolupat de manera totalment individual (o en el si del grup en el cas d'activitats grupals). Facilitar el codi que dóna lloc al plagi és també una forma de plagi i serà tractat de la mateixa manera. De manera resumida podem dir que les activitats avaluatives s'han de resoldre de manera estrictament no col·laborativa (en el cas d'activitats en grup la col·laboració no pot transcendir el si del grup). 

Recuperació

La part de pràctiques de l’assignatura (qualificació Pr) NO és recuperable.

Per als estudiants que assisteixin a l’examen de recuperació la seva qualificació Teo serà la obtinguda en aquesta prova i la seva qualificació final es calcularà amb les fórmules anteriorment detallades i en cap cas no serà superior a 5.

Sesa i Nogueras. EDA: notes de classe, exemples i exercicis. Publicació interna del TCM.

Tutorial Oracle Java Collections  https://docs.oracle.com/javase/tutorial/collections/

Java 8 API Documentation. https://docs.oracle.com/javase/8/docs/api/