INICIACIÓ A LA PROGRAMACIÓ

TEMARI

I - Introducció. Concepte d'algorisme

II - Objectes. Constants, tipus i variables

III - Especificació

IV - Assignació

V - Composició seqüencial

VI - Composició alternativa

VII - Composició iterativa

VIII - Seqüencia, cerca i recorregut

IX - Taules

X - Parametrització de subprogrames

XI - Analisis descendent i triples

XII - Verificació

I - INTRODUCCIÓ. CONCEPTE D'ALGORISME I PRGRAMA

Autómat: és qualsevol mecanisme capaç de realitzar un treball de forma autónoma. Exemple d'autómats sencills: rellotge, rentadora.

Exemple d'autómats flexibles: l'ordinador.

Els primers tenen una cosa en comú que, una vegada conectats, poden realitzar la seva funció sense intervenció externa, el seu treball es sempre el mateix.

L'ordinador és una autómat de cálcul gobernat per un programa, de tal manera que diferents programes farien treballar l'ordinador de diferent manera.

Procés: execució d'acció o accions que pot realitzar l'autómat. El procés modifica l'estat de l'entorn.

Exemple: autómat--> rentadora.

proces -----> programa de rentat.

Algorisme: es pot definir com la descripció de les accions que duu a terme un procés. Suposem que l'estat de l'entorn / algorisme en cada moment es pot descriure donant els valors d'una quantitat finita de variables.

Programa: algorisme codificat o traduit a un llenguatge de programació i que per tant l'eneten un ordinador.

II - OBJECTES. CONSTANTS, TIPUS I VARIABLES

OBJECTE: lloc ones pot ammagatzemar informació. Hi ha dos tipus d'objectes:

Constants: el valor emmagatzemat no pot variar ni variarà.

Declaració:

const nom: tipus= valor fconst

nom= poden ser lletres en majúscules, dígits i subrallats.

tipus= defineix el rang de valors posibles i les operacions que es poden fer amb el valors. Els tipus podem ser: enters, reals, caracter o boolea.

El subrallat i el tipus són Paraules Reservades i no es poden utilitzar en el programa, només s'utilitza en el llenguatge algorismic.

Variables: seria una caixa on es pot guardar una dada, però de manera que pogui anar cambiant el seu contingut. El valor de la variable és el de l'ultima dada introduïda. Tota variable ha de tenir un nom per poder referir-nos a ella i s'ha de clasificar en tipos.

Declaració:

var nom: tipus fvar

nom= lletres minúscules, dígits o signes

tipus= els mateixos que en les constants

NOTA:

-> No podem utilitzar paraules reservades com a nom d'objeces.

-> No podem declarar varis objectes amb el mateix nom.

-> Si volem declarar variables del mateix tipus podem fer una sola declaració i separar-les utilitzant comes.

TIPUS: els tipus que hi han són simples, enumeratius i estructurats (taules, tuples). Els tipus simples i enumeratius només tindran un valor per constant o variable i, en canvi, els estructurats poden tenir més elements per només un identificador.

-Simples: són els de simbols predefinits per l'ordinador i poden ser:

·Naturals: (cardinals) són els nombres enters positius (0,.....,*). Els operadors que admet són: div, mod, +, * , imparell (x).

Div: és la divisió entera. Mod: dona el reste de la divisió.

Imparell (x): dona si x es imparell o parell, cert o fals. (odd (x))

·Enters: (-*,...., -1, 0 , 1,.....,*). Els operadors que admet són: +, *, div, mod, valor absolut (abs(x)), el signe menys( - unari) i l'imparell (x).

·Reals: son tots els nombres, decimals inclossos. Els operadors són: +, *, /, abs(x), - (unari)

·Caràcters: són els caràcters ASCII, lletres minúscules i majúscules, tots els dígits i simbols (subrallat...). Els caràcters estàn ordenats i per tant tindran un successor i un predecesor. Els caràcters van entre comes: `a', `1'. Els operadors són el succesor (suc(x))i el predecesor (pred(x)).

·Booleà: te dos elements (cert i fals) i tambè estan ordenats ja que fals es dona per més petit que cert. Els operadors que es poden fer servir són els de comparació. (>, <, <>, =>, =<, and, or)

·Subrangs: aquest s'han de posar sempre entre corxets i entre els corxets li direm el primer i l'últim element. Només es poden fer subrangs amb els tipus escalars, es a dir, que tenen un element predecesor i succesor, per tant es poden fer de naturals, enters, caràcter, booleans i d'enumeratius.

Declaració:

tipus nom = [1º element .. últim element* ftipus

-Enumeratius: aquest tipus pot ser definit per l'usuari. Són tipus ordenats i per tant es poden utilitzar com subrangs. Si després de l'enumeratiu es fa un subrang aquest buscarà el 1º element dels tipus d'enumeratius.

Declaració:

tipus nom = (1º element, 2º element.....element n) ftipus

Prioritats: 1º- els unaris y la negació

2º- *, divisió, logaritmes

3º- suma y resta

4º- <, >, =<, >=, <>, =

5º- "-> conjunció

6º- "-> disjunció

III- ESPECIFICACIÓ

Especificar és saber que fa l'algorisme. Es natural especificar un proces decribint la relació entre els estats incial i final del mateix. Formalitzarem aquesta relació, denominada especificació, amb l'ajut de predicats.

Un predicat o asserto és una relació entre objectes a la que sempre es possible assignar un dels valors del conjunt (fals o cert) en funció dels objectes involucrats.

El domini d'una de les variables serà el conjunt dels valors per la qual podem substituir en el predicat.

L'especificació d'un algorisme constarà de quatre elements:

1-Declaració de variables.

2-Precondició, condicions inicials (entre claus {P}).

3-Nom de l'algorisme o acció.

4-Postcondició, condicions finals (entre claus {Q}).

On la precondició i la postcondició són predicats sobre les variables. Aquests predicatsreflexen la situació inicial i final pretessa de les variables del nostre algorisme.

El punt 1 informa acerca de les variables que intervenen en el procés i el tipus de les mateixes. Els restants estableixen que, partint d'un estat inicial que satisfà la precondició (2), una vegada procesat l'algorisme (3) arribem a un estat final que verifica la postcondició (4).

En els predicats s'utilitzen les variables d'especificació que permet donar un valor inicial qualsevol a les variables. S'escriuen en majúscules. Aquestes variables no formaran part mai de l'algorisme i no són variables d'entorn. Ens donen una valor qualsevol inicial dintre dels permessos pel tipus.

REGLES DE CONSEQÜÈNCIA D'UNA ESPECIFCCIÓ

Direm que un algorisme S satisfa una certa especificació amb precondició P y postcondició Q, su una vegada procesat S sobre unes variables que cumpleixin P, aquestes pasin a cumplir Q. Les regles de la conseqüència són:

-Si {P} A {Q} y R=>P llavors {R} A {Q}.

-Si {P} A {Q} y R=>Q llavors {P} A {R}.

IV- ASSIGNACIÓ

La instrucció fundamental per escribir algorismes és l'assignació que consisteix en donar un valor a una variable. Tot algorisme pot contemplar-se com una combinació de variables mes o menys complexes.

La seva sintaxis és:

x:=E

que es llegeix: “x toma el valor que tingui E”. E haurà de ser una expressió vàlida del mateix tipus que x.

La seva especificació és: declaració de variables

{E compleix Q}

x:=E

{x compleix Q}

L'axioma de la assignació: Per tota variable x, tota expressió vàlida del mateix tipus E y tot aserto o predicat Q, l'especificació

x:tipus

{QxE}-------> substitució de x per E

x:=E

{Q}

és correcta.

A partir d'aquesta y amb l'ajut de la primera regla de conseqüència podem donar un procès per comprobar quan una assignació cumpleix una determinada especficació. Aquest resultat se denomina regla d'inferència de l'assignació. Per tal que sigui correcte l'algorisme:

x:tipus

{P}

x:=E

{Q}

s'ha de cumplir que P ens impliqui la substitució de x per E: P=>QxE. Si volem que x satisfagi Q després d'haver-li assignat el valor d'E es raonable demanar que el propi valor E cumpleixi Q.

V- COMPOSICIÓ SEQÜENCIAL

Es podem executar instruccions de manera consecutiva, això s'anomena composició seqüencial. Usem el simbol “;” per a conectar dues instruccions, indica que la funció s'ha acabat i que comença una altra. {P} A; B {Q}.

Per verificar l'algorisme s'ha de poder verificar a i b independenment, però la postcondició de tan sols A no és {Q} serà un aintermitja {R} que farà de postcondició de A i de precondició de B.

La regla d'inferencia: direm que l'especificació {P} S1;S2 {Q} és correcta si podem trobar un predicat R que cumpleixi {P}S1{R} y {R}S2{Q}.

D'aquesta afirmació es despren que el predicat R descriu els estats intermitjos possibles entre la execució de S1 y S2.

Podem extender aquest postulat a un cas general utilitzant tants predicats intermitjos com sigui necesari, gràcies a que la composició seqüencial és asociativa.

X, y :tipus Primer s'ha de comprobar

{P} l'última assignació de

x:=E1; P=>(R)xE1 l'algorisme i anant cap a

{R} P=>(QyE2)xE1 munt.

y:=E2 R=>(Q)yE2

{Q}

Si un algorisme té la postcondició i la precondició iguals, no fa res.

VI- COMPOSICIÓ CONDICIONAL O ALTERNATIVA

La composició condicional permet decidir quin subalgorisme executar depenent de l'estat inicial.

Sintaxis:

{P} si E1------->A1; €E2------->A2; €E3------->A3; . €En------->An fsi {Q}

on A1,...,An és un conjunt d'insruccions i E1,...,En és un conjunt d'expressions lógiques, es a dir, expressions que evaluen a un valor booleà. Una parella (Ei, Ai), es denomina instrucció protegida, ja que la instrucció Ai no s'executa si la condició E1 és falsa.

Si la primera condició es certa s'executarà A1 i si no, evalua la següent i si es certa s'executarà i així fins al final. En aquests cassos només s'executa una acció i es surt de la condició. Si hi ha més d'una expressió certa s'executarà la primera que sigui certa i sortirà. Entre si i fsi hi han d'apareixer totes les possibilitats.

Hi han dos tipus de conidcional la exclusiva i la general. La general es dona quan més d'una branca poden ser ertes, i en l'exclusiva només es farà certa una branca.

Regla d'inferencia de la composició alternativa: entenem que l'estructura alternativa està ben definida si es cumpleix que per l'estat inicial P al menys una de les proteccions Ei es certa. P=> E1"E2"....."En.

Per a cada algorisme posible s'ha de verificar la precondició, que es formada per {P} i la condició Ei, i la postcondició {Q}. La nova precondició formada es representa amb P*. En aquest cas es miren si els subprogrames de cadascuna de les branques són correctes. ("I: 1 <= i <= n: {P"Ei} Ai {Q}).

VII-COMPOSICIÓ ITERATIVA

Amb aquesta composició podem describir processos quina duració dependi de l'estat inicial. Per resoldre aquest problema tenim el mentre.

Sintaxis:

mentre B fer S fmentre

On B és una expresió lógica i S una instrucció. B: condició de continuació C: cos de la iteració, cos del bucle

L'algorisme S es realitza mentre B es fasi certa, i així fins que B es fasi fals.

Tota iteració planteja dos tipus de problemes:

1-Determinar l'efecte de la instrucció iterativa, per concretar-lo tindrem que buscar una relació I que es mantingui inalterada després de cada iteració. Aquesta relació és l'invariant.

2-Probar que la instrucció iterativa finalitza, per assegurar-nos això haurem d'associar a cada iteració una funció que dependi de les variables, de manera que la relació invariant (I) i condició de continuació (B) permita assegurar que la funció és positiva i decreix en cada proces de la instrucció iterativa. Aquesta funció és la funció de cota.

Expresant això amb més formalisme obtenim la regla d'inferència.

1ª fase (determinar que el mentre sigui correcte):

-Definir un invariant (condició que s'ha de cumplir sempre dintre del mentre).

-Mirar si la precondició P implica I. P=>I

-{I"B} S {I}.

-Que al surtir del bucle es cumpleix I"¬B=>Q.

2ª fase (mirar si el mentre acaba o no):

-Definir una funció fita.

-La fita ha de ser positiva i que forzossament decreix I"B=>f>0.

-Després d'executar l'algorisme f ha decrescut {I"B"f=F}S{f<F}.

Ajudes per trobar l'invariant:

-Si {Q} està estructurada en conjuncions i te la negació de B llavor I és {Q} però qitan la condició de continuació. Tenint en compte que normalment es compleix I"¬B=>Q quan estem verificant, podem tenir I agafant la postcondició Q i eliminant la conjunció ¬B.

-Substituir les variables d'especificació de la postcondició per variables de l'algorisme. Si la nova postcondició es cumpleix dintre del mentre, llavors aquesta condició és l'invariant.

La composició iterativa també es pot fer amb el per i repetir:

per i:=E1 fins E2 fer A fper	Executa A tantes vegades com la diferencia entre E1 i E2	repetir A finsque E frepetir	Es repeteix l'algo-risme fins que E es cumpla. A s'executa al menys una vegada.
i,j:enter i:=E1; j:=E2 mentre i=< j fer A; i:=i+1 fmentre		||| A; mentre ¬E fer A; fmentre

VIII-ACCES SEQÜÈNCIAL, CERCA I RECORREGUT

Una seqüéncia es defineix com un conjunt finit d'objectes, del mateix tipus, que tenen associades les operacionsprimer element i següent element que permiten, respectivament accedir al primer element i avançar a través d'ella, element tras element. La longitud de la seqüència és indeterminada. Per accedir a un element s'ha hagut de passar primer per tots els precessors.

L'actual(S) és l'element on es troba la seqüència. Els element tractats són part esquerra de la seqüència (p.e.s) i els que queden per tractar, inclós l'actual és la part dreta de la seqüència (p.d.s).

Notació angular: S=<,> on  representa la p.e.(S) i  la p.d.(S).

. reprsenta una concatenació de seqüències.

Longitud (S)=k es defineix la lomgitud de la seqüència.

Declaració:

S1,S2: seqüència de caràcters T: seqüència d'enters

OPERADORS

·Crear(S): crea seqüencies, comença a escriure a la seqüència.

·Escriure(S,e): escriu un element e a la seqüència.

En aquests dos primers la seqüència encara no existeix.

·Preparar(S): posa l'actual al primer element, comença a llegir la seqüència.

·Actual(S): agafar l'element que estem mirant.

·Avançar(S): ens posem a la següent posició, pasar al següent element.

·Fi?(S): ens diu si hem arribat al final de la seqüència. Cert->final

En aquests quatre últims la seqüència ja ha d'existir, sino donaria un error.

Especificacions dels operador primaris.

Crear(S):	{cert} crear(S) {S=<buida,buida>}		Escriure(S,e):	{S=<,buida>} escriure(S,e) {s=<.e,buida>}
Preparar(S):	{s=<,> preparar(S) {S=<buida,.>}		Actual(S):	{S=<,.e>} x:=actual(S) {S=<,e.> " x=e}
Avançar(S):	{S=<,e.>} avançar(S) {S=<.e,>}		Fi?(S):	{S=<,>} b:=fi?(S) {S=<,> " b=(=buida)}

D'aquests operadors primaris es poden deduir dos operadors més, els opradors derivats:

llegir_primer(S,x):

preparar(S) x:=actual(S)

llegir_següent(S,x):

avançar(S) x:=actual(S)

x és la variable on es guardaría el primer element de la seqüència.

ESQUEMES DE RECORREGUT I CERCA

Cerca: buscar el primer element que cumpleixi una determinada condició.

Recorregut: fer operacions amb cada element, per exemple sumar tots els elements d'una seqüència. Seria el tractament dels elements de la seqüència.

Mixtes: de tots els elements que cumpleixin una condició operar.

A més les seqüències poden estar marcades o no. Una marca és un element del mateix tipus que la seqüència que esta conctenat al final de la seqüència i que no es pot repetir al mig de la seqüència. En la seqüència marcada buida al menys hi ha d'apareixer la marca, i només amb aquestes seqüències es poden utilitzar els operadors derivats. Si la marca es troba al mig, la seq seria una seq sense marca, ja que la marca al mig no es considera com a tal.

ESQUEMA DE CERCA AMB MARCA

Donada una seqüència S acabada en un element F determineu si hi ha algún element e que sigui diferent de F i que tingui una propietat p(e)

Especificació: S: seqüència d'elements trobat: booleà {S=.F"F""¬p(F)} cerca {trobat=("e:e":p(e)}

Algorisme: var S: seq d'elements trobat: booleà e: element fvar llegir_primer(S,e); mentre ¬p(e)"(e"F) fer llegir_següent(S,e) fmentre trobat:= p(e)

I"{(p.e.(S)).(p.d.(S))= .F " F" " ¬p(F) " ("x: x"p.e.(S):¬p(x)) " e=actual(S)}

fita" longitud (p.d.(S)).

ESQUEMA DE RECORREGUT AMB MARCA

Donada una seq. S acabada en F, fer un tractament “tractar(e, variables)” amb tots els elements de la seq.

Especificació: S: seq d'elements (...altres variables...) {S=.F " F"} tractament {tractada(,variables)}

Algorisme: var S: seq d'elements (...altres variables...) e: element fvar inicilitzar variables; llegir_primer (S,e); mentre e"F fer tractar(e, variables) llegir_següent (S,e) fmentre tractament final

I"{(pe(S)).(pd(S))=.F"F" " ("x: x"pe(S): tractada (x,variables))"e=actual(S)}

fita= longitud (pd(S))

ESQUEMA DE RECORREGUT SENSE MARCA

Donada una seq. S, fer un tractament “tractar (e,variables)” amb tots els elements de la seq. Quan no hi ha marca no es poden utilitzar el llegir_primer ni el llegir_següent.

Especificació: S: seq d'elements (...altres variables...) {S=} recorregut sense marca {Tractar(,variables)}

Algorisme: var S: seq d'elements (...altres variables...) fvar inicialitzar variables; preparar (S) mentre ¬fi?(S) fer tractar (actual(S), variables) avançar (S) fmentre tractament final

I"{pe(S).pd(S)= " tractar (pe(S), variables)}

fita= longitud (pd(S))

ESQUEMA DE CERCA SENSE MARCA

Donada una seq. S, determinar si hi ha algún element que cumpleixi una propietat P(e)

Especificació: S: seq d'elements trobat: booleà {S=} cerca_sensemarca {trobat=("x: x": P(x) " trobat=> P(actual(S)}

Algorisme: var S: seq d'elements trobat: booleà fvar preparar (S) mentre ¬fi?(S) ¬trobat fer si P(actual(S))-> trobat:= cert ƒ¬P(actual(S))-> avançar (S) fsi fmentre

I"{S= " ("x: x"(pe(S)): ¬P(X)) " trobat=> P(actual(S)}.

fita" f=longitud (pd(S))+ boolenter(¬trobat).

No es pot posar només longitud(pd(S)) perque si es troba l'element no s'avança i per tant s'ha de posar una condició que digui no trobat. pd(S) queda igual al trobar l'elements desitjat i per tant la fita no disminueix i per tant, hi ha d'haver alguna cosa que disminueixi.

L'esquema mixte és una combinació de l'esquema de cerca i recorregut

IX-ACCÉS DIRECTE. TAULES

L'accés directe té l'avantatge de que anem directament a l'element desitgat sense d'haver de passar pels anteriors elements a ell. Només amb l'index ja se sap quin element es vol.

Propietats de la taula:

-L'accés a la taula es realitza a través d'un conjunt d'index totalment ordenats, finits i del mateix tipus. L'index és la quantitat de posicions on es poden tenir elements, va entre corxets. Dona el rang de la taula, es a dir, la dimensió de la taula. Aquest ser de qualsevol tipus que tingui ordenació (enter, natural, caràcter, subrang, enumeratiu i booleà.

-En canvi, el tipus_base que és el contingut pot pertànyer a qualsevol conjunt, són els elements que conté la taula.

-Si s'intenta a accedir a posicions inexistents d'una taula, el resultat no està definit.

Així doncs, les dades que pot admetre l'accés directe poseeixen estructura de taules amb index com entrades i valors com a sortides.

Els algorismes que traten taules han de contenir una declaració com:

Sintaxis:

nom: taula [index1,..,index n] de tipus_base

L'accés a la informació en una cel-la es fa mitjançant la següent expressió:

variable:= nom_taula[fila, columna]

Per esciure en la taula s'utilitza l'expressió següent:

nom_taula[fila,columna]:= E on E es una expressió

EXEMPLE

tipus

aules= (A201, A202, A203, )

assignatures= (IP, IC, F, AL)

ftipus

horari: taula[9..19, aules] de assignatures

a:= horari [9, A201] (llegir)

horari[10, A203]:= IC (escriure)

	9	...	19
A201	IP
A202		IC
A203			AL

S'ha d'utilitzar tants mentres o per com indexos hi hagi per a que es recorri tota la taula. I tal com es defineixen els index, es com s'han de llegir, encara que es llegeixi horitzontal o verticalment.

ESQUEMA DE RECORREGUT

Donada una taula t, fer un tractament amb tots els elements d'aquesta.

Especificació: t: taula[a..b] d'element (...altres varibales...) {t=T" a"b} recorregut-taula {("k: a"k"b: tractar(T[k],m))}

Algorisme: var t:taula [a..b d'element (...altres variables...) i:[a..b] fvar inicialitzar variables per i:=a fins b fer tractar (T[i] ,var) fper tractamen final

I"{t=T " a"b ("k: a"k<i: Tractar (T[k], var))}

fita= no te fita perque la composició iterativa es un per.

Si l'algorisme es fes amb el mentre ,la variable i cambiaria per i:=[a..b+1], la condició de continuació seria i"b+1, hi hauria un comptador al mentre i:=i+1. En aquest cas si hi hauria fita que seria (b+1)-i i a l'invariant seria:

I"{t=T " a"b "("k: a"k<i: Tractar (T[k], var)) " a"i"b+1}.

ESQUEMA DE CERCA

Donada una taula, determinar si conté algún element e amb una propietat P(e).

Especificació: t: taula [a..b] d'element trobat: booleà {t=T " a"b} cercar taula {trobat= ("i: a"i"b: P(T[i]))}

Algorisme: var t:taula [a..b] d'element trobat: booleà i: [a..b] fvar i:=a; mentre (i"b) " ¬P(t[i]) fer i:=i+1 fmentre trobat:= P(t[i])

I"{t=T " a"b " ("k: a"k<i: ¬P(T[k])) " a"i"b}

fita= b-i

Observem que si s'imposara com a condició del bucle la expressió:

i"b y ¬P(t[i])

l'algorisme seria incorrecte, ja que si ningún element satisfa P la variable i acabaria valent N+1 amb el que, tras l'ultima iteració, es produiria un error per accés a una posició no definida. Això no pasa en l'esquema proposat, ja que, si la cerca no ha tingut éxit, el bucle termina quan i=b i la postcondició es igualment satisfeta.

En la cerca hi han dos possibilitats per millorar la cerca:

· Cerca amb sentinella que millora el temps d'execució.

· Cerca dicotómica o binaria. La precondició es que la taula estigui ordenada. Es va a una posició aleatoria i es mira si el valor es mes gran o mes petit que el desitjat i així fins al final. S'utilitza quan s'han de fer moltes cerques.

CERCA AMB SENTINELLA

La sentinella seria una marca i sería l'element a buscar posat pel programador al final de l taula, es a dir, es posa una posició més a la taula. Aquest element a més ha de cumplir la propietat desitjada.

Especificació: t:taula [a..b+1] d'element trobat: booleà {t=T " a"b " P(sentinella)} cerca_sentinella {trobat=("r: a"r"b: P(T[r]))}

Algorisme: var t: taula [a..b+1] d'element trobat: booleà i:[a..b+1] fvar t[b+1]:= sentinella; i:= a; mentre ¬P(t[i]) fer i:=i+1; fmentre trobat:= (i"b+1)

I"{t=T " a"b+1 " ("x: a"x<i: ¬P(T[x]))}

fita= b+1-i

CERCA DICOTÓMICA O BINARIA

La taula ha d'estar ordenada, es tenen dos indexs: un inferior i unn superior. Agafem un altre index k a l'atzar, si l'element es més gran que el trobat s'agafa la part dreta i si es mes petit la part esquerra i així fins que es trobi o s'acabi la taula.

Especificació: T: Taula [1..n] d'enter x: enter i: [1..N] {t=T " x=X " N>1 " ordenat (T)} cerca_dicotómica {(x"T) " (T[i]=X)} Ordenat(T):("i: 1"i<N: T[i] " T[i+1])

Algorisme: var t:taula [1..N] d'enter x: enter i, j, k: [1..N] fvar i:=1; j:=n; mentre i<j fer k:=(i+j) div 2 si x"t[k]-> j:=k; ›x>t[k]-> i:=k+1; fsi fmentre

I"{t=T " x=X " N>1 " ordenat (T) " ((x"T) " (x"T[i..j]))}

fita=j-i

X-PARAMETRITZACIÓ DE SUBPROGRAMES

TUPLAS

Els elements de tipus complexes estaràn formats, per tipus més simples. Per definir els primers en funció dels segons s'utilitzen constructors de tipus. Comprobem que les estructures de taula i seqüència tenen en comú que els seus components son del mateix tipus. El constructor que introduïm es la tupla, que permitirà crear entitats complexes que les seves components, anomendes camps poden perteneixer a tipus diferents.

Declaració:

nom tupla= tupla camp1: tipus1 . . campn: tipusn ftupla

Cada un d'aquests camps està dotat d'un identificador. Per referenciar cada un d'ells individualment empleem el conector “.” Entre el nom de variable i els seus components.

Acabem de veure que el conector “.” Dota de significat a entitats, curtes o llargues, depenen de la complexitat de la tupla, el que pot resultat pesat escriure. Però existeixen blocs de instruccions on totes les components referenciades d'una tupla comparteixen els identificadors inicials i per tant es poden simplificar les expressions. No seria necessari estar repetint tot el temps la llista completa de camps i subcamps doncs no hi hauria posibilitat de confusió. Per permitir la supresió de lapart comú d'una colecció d'identificadors de camps introduïm la instrucció amb.

Declaració:

amb variable.part coincidnt fer referèncias sol a la part variable famb

L'accés a tuples de taules es fa de la següent manera:

nom variable [posició].camp

I per escirue en una tupla d'aquesta altra manera:

nom variable [posició].camp := expressió

ACCIONS I FUNCIONS

Al dissenay algorismes grans ens trobem a uns problemes com poden ser la dificultat en solucionar problemes de mitjana envergadura, errors de codi redundant i que són difícils d'entendre. Per solucionar aquest problemes s'utilitzen els subprogrames, els quals són de dos tipus: accions i funcions.

ACCIONS

Una acció es un algorisme disenyat de tal manera que es susceptible de ser cridat per altres algorismes que, a la seva vegada, poden ser accions. En aquest context, és usual referir-se a l'algorisme que efectua la crida com algorisme principal.

La crida a una acció es realitza escribint el nom de l'acció seguit de les expressions sobre les quals desitgem que treballi. Aquestes van tancadaes entre paréntesis i en ordre en que han sigut especificades en l'acció que es cridada.

Declaració:

nom_acció (parametres reals)

La especificació d'una acció te dos parts:

·Capcelera: es on consta l'identificador o nom de l'acció i la llista de parametres formals. En aquesta llista s'indica el tipus de paràmetres i la seva clase.

·Cos: compren la part de declaracions i instruccions que constitueixen l'acció.

Declaració:

acció nom_acció (parametres formals: tipus) declaració_variables_locals {P (paràmetres)} cos_de_l'acció {Q (paràmetres)} facció

Amb aquest protocol hem creat una via de comunicació entre la instrucció de crida i l'acció que es cridada que facilita l'intercanvi d'informació entre les dues. A partir d'ara denominarem paràmetres als objectes que intervenen en aquest protocol.

Els paràmetres que s'escriuen en la instruciió de crida son els paràmetres reals. En canvi, els que apareixen en l'acció que es cridada són els paràmetres formals. Al emparallar els paràmetres de les dues llistes de manera ordenada, han de coincidir en:

· el nombre de paràmetres

· el tipus dels paràmetres.

Pero no es necesari que coincideixin els identificadors dels paràmetres reals i formals. Es a dir, la conexió es fa mitjançant la posició i no el nom, per tant els paràmetres formal i reals han de tenir el mateix nombre d'objectes.

Els paràmetres es poden clasificar en:

-Entrada (ent): els objectes tenen un valor inicial i corresponen a aquells que surten a la precondició de l'algorisme.

-Sortida (sort): els objectes a on retornarem el resultat de l'acció, corresponen a les variables que surten a la postcondició.

-Entrada/Sortida (e/s): són aquells que inicialment tenen un valor inicial i amés es poden utilitzar per retornar el resultat de l'acció, apareixen a la pre i postcondicicó.

NOTA

-Han de coincidr el nombre de paràmetre real i formals.

-Han de coincidir els tipus dels paràmetres formal i reals per posició.

-Els paràmetres d'entrada no han de ser necesariament una variables, se li pot donar una expressió directament quan es fa la crida, i si es variable ha de tenir un valor inicial abans de fer la crida.

-Els paràmetres de sortida mai poden ser expressions i la variables noo h a de ser inicialitzada.

-Si es de ent/sort ha de ser una variable i ja inicialitzada.

FUNCIONS

Les funcions són les accions que els parametres son d'entrada excepte un, que es de sortida. Les funcions són un subconjunt de les accions i qualsevol funció es pot expresar com una acció.

Les funcions nomes tenen paràmetres de sortida i sempre retornen un element de sortida, donen el valor directament.

El fet de tenir un sol paràmetre de sortida fa que la funció calculi un valor i permeti asignar aquest a una variable.

En la crida a una funció el paràmetre de sortida no ha d'apareixer a la llista de paràmetres d'entrada i el valor calculat per la funció es referenciat per la crida misma.

Declaració:

variable := nom_funció

La declaració de funcions i la protecció de dades es similar al cas de les accions, excepte en:

-La llista de paràmetres formals només contenen paràmetres d'entrada.

-En la declaració de la funció s'indica el tipus del valor que retorna, afegint-lo al final de la capcelera despres de tancar els parèntesis i separats per dos punts.

-Per indicar el valor que retorna la funció utilitzarem la paraula retorna.

Declaració:

funció nom_funció (paràmetres formals) : tipus {P} només entrada element retornar cos de la funció {Q} retorna E ffunció

XI-ANALISIS I DISSENY DESCENDENT

El disseny descendent es basa en l'abstracció. La abstracció es basa en discernir els elements importants en un nivell donat i despreciar tots els altres elements que en un nivell no són importants.

El disseny descendent s'utilitza quan ja tenim algorismes dissenyats i verificats (reutilització) i quan la unitat lògica i l'elemental no coincideixen.

-Unitat elemental: tipus de dades mes baix, tipus mes baix eel problema.

-Unitat lógica: tipus que s'obté en el nivell més alt d'abstracció.

En el disseny descendent es poden distinguir tres fases:

1- Primer hem imaginat una unitat lògica de tractament i hem declarat una variables que la representa.

2- Aplicar el corespondent esquema sobre la unitat lògica.

3- Refinatment de les accions que han surgit, fins expresar-les en funció de les unitats elementals.

Quan es pasa d'un nivell superior d'abstracció a un nivell inferior es diu que s'ha fet una refinament.

Suposem que el conjunt de dades d'un problema pot dividir-se en unitats lógiques, progressivament més sencilles, fins a arribar a les elementals. Podem, llavors, resoldre el problema nivell per nivell, de manera que cada acció a refinar només involucri a la unitat que defineix el nivell i a la inmediatament inferior, mitjançant l'aplicació d'un esquema conegut o inclos de instruccions elementals. Així el nombre de nivells que apareixin en una descomposicó implicarà un temps major eb la resolució del problema però no una major dificultat conceptual ja que cada un d'aquests nivells es resoldrà d'una menra similar.

Avantages del disseny descendent:

-Legibilitat: el disseny descendent reflexa fielment el procés de construcció d'un algorisme, del mateix mode que informa sobre el seu funcionament.

-Reutilització: al fragmentar un algorisme en accions que resolen subproblemas associats mes sencills augmenta la probabilitat de que alguna de les accions es pugui aprofitar en altres situacions.

-Depurabilitat i modificabilitat: si el nostre algorisme conté algún error inadvertit o si despres de dissenyar-lo s'ha de modificar per satisfer algún canvi en la especificació, la seva estructura d'accions i funcions permet detectar ràpidament quals són els fragments qua s'han de canviar.

ORDENACIÓ DE TAULES

Utilitzarem els predicats següents:

-Ordenada (t, i, j)"("k: i"k<j: t[k] " t[k+1]).

-t[i..j] = T [i..j] Si i>j la taula es buida: ("k: i"k"j: t[k]=T[k]).

-No es poden afegir ni treure elements, s'agafa un element de a y es posa una sola vegada a b.

Pem (a, b, i, j)= ("k: i"k"j: (#r: i"r"j: a[r]=a[k])=(#r: i"r"j: b[r]=b[k])).

INSERCIÓ

Es tenen dos blocs, un ordenat y l'altre desordenat. S'agafen elements del desordenat y s'inserta entre els valors de l'ordenat.

Aquí ordenar una posició més es tradueix en averiguar la posició que li correspondria a l'element i-essim en la part ordenada i insertar-lo en aquesta.

Inv"{ ordenada (t,i,r-1) " t[1..i-1]=T[1..i-1]"t[j+1..N]=T[j+1..N]" perm (t,T,i,j)}.

Var

r: [1..N]

fvar

per r=i+1 fins j fer

Inv'"{ordenada(t,i,s) " ordenada (t,s+1,r) " s"i " t[s+1]=T[r] " x=T[r]}

s:=r-1; x:=t[r]

mentre (t[s] > t[s+1]) " (s>i) fer

t[s+1]:= t[s];

t[s]:= x;

s:= s+1;

fmentre

si t[s] > t[s+1]----->t[s+1]:= t[s]; t[s]:=x;

˜t[s] " t[s+1]---->

fsi

fper

SELECCIÓ

També es tenen dos blocs, es busca l'element menor del bloc desordenat i es posa en l'ordenat i això es repeteix fins que s'acaben els elements.

Una segona aproximació parteix de suposar que, a més d'estar ordenat, els i-1 primers elements de la taula son els menors, es a dir, tot altre elements de la taula es major o igual que t[i-1]. Consisteix en seleccionar el mínim valor d'entre els encara no ordenats i intercambiar-lo amb el i-essim.

Acció ordenar (ent/sort t:taula [1..N] d'enter; ent i, j:1..N)

P"{1"i"j"N " t=T}

Q"{ordenada (t,i,j) " t[1..i-1]=T[1..i-1] " t[j+1..N]=T[j+1..N] " perm(t,T,i,j)}

I"{ ordenada (t,i,r-1) " t[1..i-1]=T[1..i-1] " t[j+1..N]=T[j+1..N] " perm (t,T,i,j) " " l,m: i"l<r"m"j: t[l]"t[m]}

var

r:1..N

fvar

r:=i;

mentre r"j fer

min:= localizar_minimo (t,r,j)

{Inv " r"j " r"min"j " "m: r"m"j: t[min]"t[m]}

intercanviar (t[min], t[r]);

r:=r+1;

fmentre

funció localizar_minimo (ent t:taula [1..N] d'enter; r, j: 1..N)

var min, l: 1..N fvar

min:= r;

per l:=r+1 fins j fer

si t[l]< t[min]----->min:= l;

›t[l]" t[min]---->;

fsi

fper

retorna (min)

ffunció

10