Domini de les tècniques de programació treballades a Metodologia i Tecnologia de la Programació (anàlisi descendent, modularitat, pas de paràmetres i estructures de dades bàsiques).
Conèixer bé el llenguatge que s´utilitzarà per realitzar els exercicis (Pseudocodi/C/Java).
Capacitat per seguir i proposar raonaments matemàtics.
Resultats d´aprenentatge
- Ús d´un entorn real de programació
- Treball en equip en l´análisis, disseny i implementació de software
- Definició de l´estructura modular i de dades per dur a terme les aplicacions informátiques
En acabar el curs, l´alumne ha de ser capaç de:
- Avaluar l´eficiència d´un algorisme a través del càlcul del cost.
- Dissenyar un algorisme recursiu.
- Transformar un algorisme recursiu a iteratiu.
- Justificar la necessitat de l´especificació formal dels algorismes.
- Explicar els principals mecanismes de derivació formal i demostració formal d´algorismes recursius simples i de dur-ho a la pràctica en problemes.
- Fer l´especificació d´una funció en termes de pre i post-condicions.
- Implementar un algorisme sense ambigüetats a partir de l´especificació del mateix.
- Escollir els mètodes de resolució de problemes combinatoris més adients en cada situació.
- Implementar els mètodes de Backtracking, Branch & Bound i Greedy adaptats a cada problema en concret i buscant-ne la màxima eficiencia i eficacia.
- Especificar formalment qualsevol Tipus Abstracte de Dades usant especificació algebraica.
- Implementar un Tipus Abstracte de Dades a partir de la seva especificació algebraica.
- Dissenyar i implementar l´estructura de dades més adequada per una determinada aplicació, donats uns requisits d´eficiència temporal i espaial.
- Implementar els arbres binaris, n-aris, avl, 2-3, B i heaps. Implementar també els diversos recorreguts possibles.
- Implementar les taules vistes a l´assignatura.
- Implementar les variants dels diferents grafs. Implementar la cerca del camí mínim.
Semestre 1 - Exemples i problemes en Pseudocodi/C
1. Especificació d´algorismes
1.1. Introducció
1.2. Com especificar algorismes
1.3. Precondicions i postcondicions: sintaxi i semàntica
2. Eficiència dels algorismes
2.1. Introducció
2.2. Mesures asimptòtiques. Taxa de creixement
2.3. Càlcul del temps d´execució i del cost
3. Disseny recursiu
3.1. Introducció
3.2. Etapes i disseny de programes recursius
3.3. Tècnica d´immersió
3.4. Tècnica de `plegat´ i `desplegat´
3.5. Transformació de recursiu simple a iteratiu
3.6. Recursivitat múltiple. Divide & Conquer
3.7. Ordenació amb Divide & Conquer: Mergesort i Quicksort
3.8. Verificació d´algorismes recursius simples
4. Tècnica del Backtracking
4.1. Terminologia i caracterització dels problemes
4.2. Esquemes recursiu i iteratiu
4.3. Metodologia de resolució
4.4. Exemples
4.5. Backtracking per trobar la millor de les solucions
4.6. Millora en l´eficiència
5. Branch & Bound
5.1. Introducció al mètode
5.2. Esquema algorísmic
5.3. Exemples
6. Greedy
6.1. Introducció al mètode
6.2. Esquema algorísmic
6.3. Exemples
Semestre 2 - Exemples i problemes en Pseudocodi/Java
7. Tipus abstractes de dades
7.1. Introducció. Concepte de tipus abstractes de dades
7.2. Especificació algebraica de tipus abstractes de dades
7.3. Exemples
8. Arbres
8.1. Introducció
8.2. Arbres n-aris i arbres binaris
8.3. Recorreguts
8.4. Arbres de cerca
8.5. Arbres AVL
8.6. Arbres B
8.7. Heaps
9. Taules
9.1. Introducció
9.2. Especificació
9.3. Disseny de taules
9.4. Taules de hash
9.5. Implementació de taules usant arbres equilibrats
10. Grafs
10.1. Introducció
10.2. Especificació
10.3. Representació
10.4. Recorregut de grafs
10.5. Algorismes de camins mínims
10.6. Arbres d´expansió minimals: Prim
11. Patrons de disseny GRASP i GOF [tema transversal del 2n semestre]
Les activitats formatives bàsiques per cada resultat d´aprenentatge són:
Per a l´ `Ús d´un entorn real de programació´
- Treball al laboratori
- Dedicació personal a les pràctiques de laboratori
- Activitats d´avaluació
Pel `Treball en equip en l´análisis, disseny i implementació de software´
- Presentació a l´aula dels conceptes i procediments associats al mòdul, utilitzant el mètode de la lliçó
- Treball al laboratori
- Dedicació personal a les pràctiques de laboratori
- Estudi i treball personals de l´alumne
- Activitats d´avaluació
Per a la `Definició de l´estructura modular i de dades per dur a terme les aplicacions informàtiques´
- Presentació a l´aula dels conceptes i procediments associats al mòdul, utilitzant el mètode de la lliçó
- Estudi i treball personals de l´alumne
- Activitats d´avaluació
Més concretament, la metodologia és un híbrid de la classe magistral amb els exercicis fets a classe i a casa i amb sessions practiques sobre exercicis petits o sobre les mateixes practiques a lliurar. Es va combinant de manera que l´alumne pugui anar assimilant els continguts fermament. Es procurar un ritme d´exposició de nos coneixements conjuntament amb l´exercitació d´aquestos per tal de facilitar aquest ritme que garanteixi l´assumpció dels coneixements a curt, mitjà i llarg termini.
Les eines d´avaluació emprades per cada resultat d´aprenentatge són :
Per a l´ `Ús d´un entorn real de programació´
- Informes o exercicis al laboratori
- Desenvolupament i presentació de pràctiques personals o en grup
Pel `Treball en equip en l´análisis, disseny i implementació de software´
- Exàmens
- Exercicis a classe
- Informes o exercicis al laboratori
- Desenvolupament i presentació de pràctiques personals o en grup
Per a la `Definició de l´estructura modular i de dades per dur a terme les aplicacions informàtiques´
- Exàmens
- Exercicis a classe
- Informes o exercicis al laboratori
- Desenvolupament i presentació de pràctiques personals o en grup
Per a calcular la nota final és imprescindible que la teoria i les pràctiques estiguin totes aprovades amb un mínim de 5.
Nota Final = 60% Nota Teoria + 40% Nota Pràctiques
La teoria consta d´una part majoritària d´exàmens semestrals i una part d´avaluació continuada on es destaca el punt de control realitzat a meitat de semestre aixií com altres exercicis realitzats i recollits a classe o exercicis curts pràctics implementats i totalment funcionals. Per a tenir en compte la nota d´avaluació continuada, la nota d´examen ha de ser igual o superior a 3.5.
Els semestres alliberen matèria fins a la convocatòria extraordinària sempre i quan tinguin una nota mínima de cinc (5).
La nota semestral de l´alumne es calcula com:
Nota Semestre = MAX (70% Nota Examen + 30% Nota AC, 100% Nota Examen)
A juny existeix la possibilitat de recuperar el 1r Semestre.
A juliol (convocatòria extraordinària) hi ha la possibilitat de recuperar el 1r Semestre i el 2n Semestre.
La nota de teoria de l´assignatura, sempre que els dos semestres tinguin una nota igual o superior a cinc (5), es calcula com:
Nota Teoria = 50% Nota 1r Semestre + 50% Nota 2n Semestre
A cada semestre hi ha una pràctica i un exercici pràctic a lliurar. Cada pràctica i cada exercici hauran de superar-se amb un mínim de 5 per a calcular-se la nota de pràctiques,
Nota Pràctiques Semestre = 75% NotaPracSemestre + 25% NotaExerciciPracSemestre
Nota Pràctiques = 50% NotaPracSem1 + 50% NotaPracSem2
Els exàmens finals del primer i segon semestre, l´examen del punt de control del segon semestre i les pràctiques del primer i segon semestre s´avaluaran mitjançant rúbriques adhoc.
Disponible a la intranet.
Disponible a la intranet.