Enginyeria en Informàtica (3371)
Programació II (12407)
Descripció
Aquesta assignatura és una continuació de Programació I, centrant-se en aspectes més avançats d'algorísmica, com recurrència, complexitat algorísmica, algorismes de cerca i classificació, i estructuració del codi d'un programa.
Objectius
Aquesta assignatura té principalment dos objectius. El primer és que l'alumne sigui capaç de fer
servir tècniques utilitzades amb freqüència durant el desenvolupament d'un programa. Això inclou,
per exemple, la recurrència, l'analisi de la complexitat de la solució que s'està desenvolupant, i
també algorismes ben coneguts que resolen problemes que aparèixen amb molt freqüència, com per
exemple el de cerca i d'ordenació.
El segon objectiu és que l'alumne comprengui quines són les bones pràctiques de programació,
de forma que pugui desenvolupar programes clars i ben estructurats. Aquesta part inclou una
introducció als esquemes algorísmics i al disseny descendent, i té un caire eminentment pràctic,
basat en estudiar numerosos exemples de programació estructurada d'algorismes.
Temari
Tema 1: Recurrència
Conceptes d'algorismes recursius.
Transformació d'algorismes recursius a iteratius.
Problemes recursius.
Tema 2: Tècniques d’anàlisi d’algorismes
Eficiència dels algorismes.
Notació asimptòtica.
Anàlisi de la recurrència.
Tema 3: Mètodes de cerca i de classificació
Cerca lineal.
Cerca binària.
Algorismes de cerca en cadenes.
Esquemes simples de classificació: bombolla, inserció, i selecció.
Classificació per intercalació: merge sort.
Classificació ràpida: quicksort.
Tema 4: Disseny descendent
Motivació
Principis del disseny descendent
Esquemes algorísmics: recorregut, cerca, esquemes mixtos, composició d'esquemes.
Exemples de disseny descendent
Tema 5: Tècniques de disseny d’algorismes
Backtracking
Dividir per vèncer
Pràctiques
La part pràctica de l'assignatura es fa en el llenguatge de programació C. Caldrà entregar dues pràctiques concretes de totes les que es plantejaran durant aquesta assignatura, una d´elles a meitat de trimestre i l´altre al final. La primera tindrà un pes del 20% sobre la nota de pràctiques i la segona del 80%.
Mètode d'avaluació
L'assignatura consta de dues parts, pràctica i teoria, cada una contant el 50% de la nota final, tot i que cal aprovar les dues parts per superar l'assignatura. La part teòrica s'avalua amb un examen "tradicional", és a dir, que no serà tipus test.
Bibliografia
Bibliografia bàsica
AHO, A.V. i d’altres: Estructuras de datos y algoritmos. Addison Wesley, 1988. ISBN:
968-444-345-5.
WIRTH, N: Algoritmos + estructuras de datos = programas. Ediciones del Castillo, 1980. ISBN:
84-219-0172-9.
WIRTH, N: Algoritmos y estructuras de datos. Prentice Hall, 1987. ISBN: 968-880-113-5.
BOTELLA, P.; i altres. Fonaments de programació. EDIUOC, 2001.
BRASSARD, G.; BRATLEY, P: Fundamentos de Algoritmia. Prentice Hall, 1997. ISBN: 84-89660-00-X.
SCHOLL P.C, PEYRIN J.P. Esquemas algorítmicos fundamentales. Secuencias e iteración. Masson, 1991. ISBN: 84-311-0550-X
ANTONAKOS, J. L.; MANSFIELD JR., K. C: Programación estructurada en C. Prentice Hall, 1997. ISBN: 84-89660-23-9.
CEBALLOS, F. J.: Curso de programación C/C++. Ra-Ma, 1995. ISBN:8478972005.
DEITEL, H. M.; DEITEL, P. J: Cómo programar en C/C++. 2a. edició. Prentice Hall, 1995. ISBN: 968-880-471-1.
GOTTFRIED, B. S: Programación en C. McGraw-Hill, Schaum, 1997. ISBN: 8448110684.
KNUTH, D.E: El arte de programar ordenadores. Editorial Reverté. 3 volums. ISBN: 84-291-2661-9.
MOLDES TEO, FJ: Lenguaje C. Anaya Multimedia, 1997. Guías Prácticas. ISBN: 84-7614-631-0.
PRATT, T.W.; ZELKOWITZ, M.V: Lenguajes de programación. Diseño e implementación. 3a. edició. Prentice Hall, 1997. ISBN: 970-17-0046-5.
SCHILDT, H. C: Manual de referencia. McGraw-Hill. ISBN: 8448103351.
KERNIGHAN, B. W.; RITCHIE, D.M: El lenguaje de programación C. 2a. edició. Prentice Hall, 1991. ISBN: 968-880-205-0.