| Tema |
Subtema |
I - Especificació i correctesa. Asserts, quantificadors, precondicions i postcondicions. Lleis: composició, assignació, alternativa, crida a funció. Càlcul de programes senzills. Els tipus abstractes de dades com a ampliació del repertori de raonaments. Modularitat e independència de la representació. Deducció equacional. Alguns exemples de tipus abstractes comuns: piles, cues, arbres binaris, vectors, conjunts, taules, fitxers seqüencials.
II - Algorismes recursius. El principi d’inducció i la seva validesa. Breu introducció a les equacions recurrents i al seu ús per avaluar l’eficiència dels programes recursius. Anàlisi i construcció de programes recursius. Construcció de programes per immersió: transformació d’especificacions i transformació de programes.
III - Algorismes iteratius. Transformació de programes recursius lineals amb postcondició constant. Identificació del concepte d’invariant com a conseqüència d’aquesta transformació. Obtenció d’invariants: analogies amb el disseny recursiu. Construcció de programes per derivació d’iteracions. Transformació de programes recursius lineals generals.
IV - Recursivitat múltiple: concepte i aplicació. La recursivitat múltiple com a recorregut d’arbres. Càlcul dels recorreguts iteratius. Aplicació a la construcció de programes per transformació de recursivitat múltiple: quicksort.
VI - Introducció als algorismes àvids. L’esquema de divideix i venceràs. L’esquema de fer i desfer (backtracking): variants i aplicacions. Versions iteratives.
|
|
| |
|
Altres comentaris i segona convocatòria |
|
Examen final de tota l'assignatura. |
| Bàsica |
|
Apunts de l'assignatura. |
| Complementària |
|
|
(*)La Guia docent és el document on es visualitza la proposta acadèmica de la URV. Aquest document és públic i no es pot modificar, llevat de casos excepcionals revisats per l'òrgan competent/ o degudament revisats d'acord amb la normativa vigent |
|