Doble Grau en International Computer Engineering and Management of Business and Technology

Programació avançada i estructura de dades

Descripció
L´assignatura divideix els seus continguts en dues parts clarament diferenciades: - En la primera part es treballa l´anàlisi d´algorismes (costos, casos, notació asimptòtica, resolució de recurrències simples), l´especificació i la verificació formal d´algorismes recursius simples. S´introdueix l´anàlisi de l´eficiència dels programes com un criteri més de qualitat. S´estudia també el disseny d´algorismes recursius simples i múltiples, i varies tècniques de resolució de problemes combinatoris. - En la segona part, s´introdueix el concepte i especificació de tipus abstractes de dades com estructures de dades lineals, arbres, taules i grafs. Les tècniques bàsiques esmentades inclouen coneixements teòrics i pràctics, habilitats, experiències i sentit crític, totes elles fonamentades en teories i tècniques sòlides, comprovades i ben establertes.
Tipus assignatura
Tercer - Obligatoria
Semestre
Anual
Curs
2
Crèdits
8.00
Coneixements previs

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.

Objectius

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.

Continguts

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]

Metodologia

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.

Avaluació

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

Criteris avaluació

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.

Bibliografia bàsica

Disponible a la intranet.

Material complementari

Disponible a la intranet.