Anàlisi i Disseny d'Algorismes (ADA)

Proveir l'alumne de les tècniques algorísmiques bàsiques que permeten abordar el desenvolupament de programes correctes i eficients per a resoldre problemes no trivials. 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.

Coneixements

1. Anàlisi d'algorismes: Eficiència, costos, casos, notació asimptòtica, resolució de recurrències simples.
2. Estructures de dades: Cues de prioritat, diccionaris, grafs.
3. Esquemes algorísmics: Dividir i vèncer, voraços, cerca exaustiva, programació dinàmica.
4. Algorismes fonamentals: Ordenació, camins mínims, arbres d'expansió...

Habilitats

1. Prendre contacte amb algunes tècniques fonamentals de disseny i anàlisi
   d'algorismes i d'estructures de dades.
2. Adquirir una metodologia per a l'especificació, l'ús, el disseny i
   la implementació de TAD.
3. Conèixer i saber utilitzar una varietat de tècniques d'implementació
   eficients d'estructures de dades.
4. Conèixer TAD genèrics, saber utilitzar-los i saber adaptar-los per donar
   solucions a necessitat específiques.
5. Saber raonar sobre la correcció i l'eficiència tant de les
   implementacions de TAD com dels algorismes que els utilitzen.
6. Disposar de criteris que permetin, durant les etapes d'especificació,
   disseny i implementació escollir l'alternativa més adequada, i disposar
   d'elements per argumentar de forma raonada les eleccions realitzades.
7. Conèixer alguns algorismes clàssics per a problemes fonamentals.
8. Saber particularitzar esquemes algorísmics generals per a resoldre problemes.

Competències

1. Capacitat per al raonament crític i lògico-matemàtic
2. Capacitat de resoldre problemes aplicant els mètodes de la ciència i l'enginyeria
3. Capacitat per dissenyar sistemes, components o processos que s'ajustin a unes necessitats, utilitzant els mètodes, tècniques i eines més adients en cada cas.
4. (1) Capacitat d'abstracció. Capacitat d'enfrontar-se a problemes nous recorrent conscientment a estratègies que han estat útils en problemes resolts anteriorment.
5. Saber aplicar el cicle de resolució de problemes típic de la ciència i l'enginyeria: especificació, generació d'idees i alternatives, disseny d'una estratègia de solució, execució de l'estratègia, validació, interpretació i avaluació dels resultats. Capacitat d'analitzar el procés un cop acabat.
6. (1) Capacitat per estudiar de diverses fonts, identificant quan la informació rebuda a classe no és suficient i cercant informació complementària.
7. Capacitat per relacionar i estructurar informació de diverses fonts, per integrar idees i coneixements.

El temari s'exposa de forma molt pràtica, a través de la presentació de
molts exemples.

Les classes introdueixen la teoria i els exemples d'aplicació de manera més o menys paral·lela.

Les cinc hores setmanals en promig de l'assignatura es fan en dos blocs de 2 hores cada setmana i un bloc de 2 hores en setmanes alternes.

L'avaluació constarà de dos exàmens parcials (PAR1 i PAR2),
i un exàmen final (FINAL) aquest últim pels alumnes que hagin optat per no fer avaluació
continuada o que hagin tret una nota inferior a 4 en el primer parcial (PAR1). A l'exàmen FINAL entra tota la matèria de l'assignatura.

A més, al llarg del curs
l'alumne pot obtenir entre 0 i 1 punts corresponents a treballs voluntaris proposats pels professors (TV), consistents en la realització de petit exercicis de programació.

El primer exàmen parcial és alliberatori i entren típicament
els temes de l'1 al 4
del temari. Els alumnes que no volen fer avaluació continuada (i per tant no s'han presentat al primer parcial) o que
obtinguin una nota inferior a 4 en aquest
parcial hauràn d'anar a l'exàmen final.
Els que hagin obtingut una nota més gran o igual a 4 en el parcial PAR1 poden anar a l'exàmen final si ho volen, però llavors no se'ls conservarà la nota PAR1.

La nota de l'assignatura es calcula així:

[si PAR1 < 4 ó PAR1 = NP ] NF = min(FINAL + TV, 10)

Aquells que obtinguin una nota superior o igual a 4 en el primer parcial,
podran escollir entre fer el segon parcial o l'exàmen final.
Al segón parcial entren típicament els temes 5 a 7. La seva nota serà, segons que facin el segón parcial o el final:

[si PAR1 >= 4 i PAR2 != NP] NF = min((PAR1 + PAR2) / 2 + TV, 10)
[si PAR1 >= 4 i PAR2 = NP i FINAL != NP] NF = min(FINAL + TV, 10)

L'exàmen parcial PAR2 es fa el mateix dia i hora que l'exàmen FINAL, però és
més curt ja que sols cobreix un part del temari.

Els exàmens consistiran a resoldre problemes que permetin avaluar el grau
d'assoliment dels objectius específics. Com a mínim el 80% de la nota de totes les proves provindrà de problemes basats en els que apareixen a la col·lecció de problemes disponible per als estudiants. Cada quadrimestre hi haurà dues edicions de la col·lecció, una a començaments del quadrimestre (de cara a PAR1) i una altra
cap a la meitat del curs (de cara a PAR2 i FINAL). No hi haurà cap més modificació de la col·lecció al llarg del curs.

• R. Sedgewick Bundle of Algorithms in CPP, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition), Addison-Wesley, 2001.
• M.A. Weiss Data Structures and Algorithm Analysis in CPP (2nd Edition), Addison-Wesley, 1999.
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein Introduction to Algorithms, Second Edition, MIT Press, 2001.
• Brassard, Bratley Fundamentos de Algoritmia, Prentice Hall, 1997.

• M.A. Weiss Data Structures and Problem Solving Using CPP (Second Edition), Addison-Wesley,, 2000.
• Ian Parberry and William Gasarch Problems on Algorithms, 2a edició disponible online a http://hercule.csci.unt.edu/ian/books/poa.html, 2002.
• N. Martí, Y. Ortega, J.A. Verdejo Estructuras de datos y métodos algorítmicos - Ejercicios resueltos, Prentice Práctica, 2003.

Domini de les tècniques de programació imperativa basada en objectes:
- pas de paràmetres,
- classes,
- objectes,
- mètodes,
- punters,
- memòria dinàmica,
- genericitat,
- ús de classes estàndard.

Conèixer bé almenys un llenguatge imperatiu orientat a objectes, preferentment C++.

Recursivitat.

Concepte de TAD.

TAD seqüencials:
- piles,
- cues,
- llistes amb punt d'interès,
- llistes amb iteradors.

Ús i implementació interna dels TAD seqüencials.

TAD arboris:
- arbre binari,
- arbre n-ari,
- arbre general,
- recorreguts.

Ús i implementació interna dels TAD arboris.

Coneixements matemàtics sobre grafs, sumatoris, límits. Matemàtica discreta. Capacitat per seguir i proposar raonaments matemàtics.

Alguns coneixements rudimentaris d'estadística i probabilitats: espai de probabilitat, esdeveniments, funcions de distribució, variable aleatòria, esperança.