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à d'un examen parcial, un
examen davant d'ordinador, un examen final i un
treball pràctic voluntari.

L'examen parcial (P) és una prova escrita on entra
la matèria dels temes 1 a 4.

L'examen davant d'ordinador (M) és una prova
consistent a resoldre dos problemes sobre la
matèria dels temes 2, 4, 5 i 6 davant de
l'ordinador i utilizant el sistema del Jutge.

L'examen final (F) és una prova escrita on entra
tota la matèria de l'assignatura.

El treball pràctic voluntari (V) consisteix en la
implementació d'un jugador per a un joc.

La nota de l'assignatura es calcula així:

NOTA = min(10, max(25% P + 25% M + 50% F, 100% F) + 20% V )


La temporització és la següent:

L'examen parcial es fa a mitjans de curs, l'examen
davant d'ordinador cap a final de curs i l'examen
final un cop acabat el curs. El treball voluntari
s'ha de lliurar cap a final de curs.


El mecanisme de l'examen davant de màquina és el
següent:

Davant de l'ordinador, els estudiants reben dos
problemes. Un problema es defineix amb un
enunciat, un o més jocs de proves públics i,
potser, cert codi ja implementat. Quan un estudi
vulgui lliurar la seva solució per algun dels
problemes, l'envia a un jutge automàtic que, en
poc segons, li retornarà el veredicte sobre el
comportament del seu programa. L'estudiant pot
reenviar fins a 10 solucions per al mateix
problema. Els professors corregiran el darrer
enviament realitzat per cada problema.


El mecanisme del treball pràctic voluntari és el
següent:

Després del parcial, es lliurarà l'enunciat del
treball pràctic voluntari, que consistirà en la
descripció d'un joc. Els estudiants que vulguin
portar a terme el treball pràctic voluntari hauran
de programar un jugador per aquest joc (és a dir,
implementar una estratègia per intentar guanyar el
joc). Juntament amb l'enunciat, els professors
també lliuraran el codi d'un jugador molt senzill:
el "tonto".

A finals de curs, hi haurà un enfrontament públic
a través d'un sistema de rondes que inclourà tots
els jugadors lliurats pels estudiants i el tonto.
D'aquest enfrontament es deduirà una classificació
i es nomenarà un campió.

La nota del treball pràctic voluntari es calcula
automàticament a partir de la posició a la
classificació, de forma lineal i garantint que el
campió tingui un 10 i que tots els participants
que guanyin al tonto tinguin un nota mínima de 5.
Els jugadors que no guanyin al tonto tindran una
nota de 0.

El lliurament del treball pràctic voluntari
implica acceptar que, si es comprova que hi ha
hagut frau en la seva realització, es restaran els
seus punts (enlloc de sumar-los) als de
l'assignatura.

• R. Sedgewick Bundle of Algorithms in CPP, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition), Addison-Wesley, 2001.
• Mark Allen Weiss Data structures and algorithm analysis in C++, Pearson Education, 2006.
• Thomas H. Cormen ... [et al.] Introduction to algorithms, MIT Press, 2001.
• G. Brassard, T. Bratley Fundamentos de algoritmia, Prentice Hall,, 1996.

• Mark Allen Weiss Data structures and problem solving using C++, Pearson Education International, 2003.
• Ian Parberry Problems on algorithms, Prentice Hall, 1995.
• Narciso Martí Oliet, Yolanda Ortega Mallén, José Alberto Verdejo López. Estructuras de datos y métodos algorítmicos : ejercicios resueltos, Pearson Educación, 2001.

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.