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