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