Anàlisi i Disseny d'Algorismes ( ADA )

Professors

Responsable:	Jordi Petit Silvestre (jpetitlsi.upc.edu).
Altres:	Alvar Vinacua Pla (alvarlsi.upc.edu) M. Teresa Abad Soriano (teresalsi.upc.edu) Salvador Roura Ferret (rouralsi.upc.edu).

Objectius Generals

Proveir l'alumne de les tècniques bàsiques d'algorísmia 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.

Objectius Específics

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, golafres, força bruta, 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 TADs.
3. Conèixer i saber utilitzar una varietat de tècniques d'implementació
   eficients d'estructures de dades.
4. Conèixer TADs 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 TADs 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.

Continguts

Hores estimades de:

Metodologia docent

Es pretén exposar el temari de forma molt pràtica, a través de la presentació de molts exemples.

Les classes es divideixen en dos tipus: sessions de teoria i sessions de
problemes. En mitjana, les classes de teoria es distrubueixen en tres hores setmanals i les de problemes en dues hores setmanals.

Les sessions de teoria són classes de tipus magistral, és a dir, classes en què
el professor aporta als alumnes nous conceptes o noves tècniques, així com
exemples seleccionats que els motivin o els il·lustrin.

Les classes de problemes tenen com a objectiu desenvolupar exercicis o casos
d'estudi. Els professors són els qui proposen els problemes que s'han de
resoldre. Pel que fa als exercicis, la finalitat és la presentació i discussió
de solucions a enunciats relativament simples que involucrin uns pocs
coneixements teòrics o tècniques. En general, es tracta d'exercicis triats per
tal d'il·lustrar conceptes que s'han introduït a les sessions de teoria més
recents. Pel que fa als casos d'estudi, els problemes proposats tenen una
major complexitat que la dels exercicis i, a més, involucren diferents
conceptes teòrics que cal combinar per obtenir una bona solució.

Mètode d'avaluació

La nota de l'alumne vindrà donada per dos examens: un de final (Fin) i un de parcial (Par). També es preveu també la possibilitat de realitzar treballs voluntaris que augmentin la nota dels examens entre 0 i 1 punt. La nota es calcula per la fórmula:

min{ max{Fin, (Par+Fin)/2} , 10 }

El temari del parcial inclou els temes <=5. El temari del final inclou tots els temes, però donarà més èmfasi als temes >=6. Els examens consistiran en resoldre problemes que permetin avaluar el grau d'assoliment dels objectius específics.

Bibliografía bàsica

• 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.

Bibliografía complementària

• 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.

Enllaços web

1. http://www.lsi.upc.edu/~jpetit/eda
   Pàgina de l'assignatura (en construcció)



2. http://it.lsi.upc.edu/concurs
   Concurs de Programació de la UPC

Capacitats prèvies

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.

TADs seqüencials (piles, cues, llistes amb punt d'interès, llistes amb iteradors). Ús i implementació interna.

TADs arboris (arbre binari, arbre n-ari, arbre general, recorreguts). Ús i implementació interna.

Coneixements matemàtics sobre grafs, sumatoris, límits. En general, quan més matemàtica discreta, millor. Capacitat per seguir raonaments matemàtics i formals.

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


PREREQUISITS: P2 i M3