EST
CPBD
A
p
u
N
T
s
000
000
000
DIPLOMATURA D'ESTADÍSTICA
COMPLEMENTS DE
PROGRAMACIÓ I
BASES DE DADES
LLENGUATGE ALGORÍSMIC I
ESTRUCTURES DE DADES LINEALS
(PART 1)
Ma a F anquesa Niubó
Llo en� Roselló Sau í
' ,
UPC FACULTAT DE MATEMATIQUES I ESTADISTICA
UNIVERSITAT P0LITECNICA DE CATALUNYA
Biblio eca
111111111111111111111111111111111111111111111111111111111111
1400249382
......
COMPLEMENTS DE PROGRAMACIÓ
I BASES DE DADES
Llengua ge Algo ísmic
Es uc u es de Dades Lineals (I)
Apun s
Ma a F anquesa Niubó
Llo en� Roselló Sau í
Depa amen de Llengua ges i Sis emes In o ma.�ics
7 d'oc ub e de 1996
1 In oducció
Aques apun s o men pa d 'una se ie de documen s que ani án so in al lla g del cu s. Aques a
p ime a pa cons a de :
•Un b eu esum de la no ació algo ísmica que cal u ili za pe esold e els p oblemes. J
un
a.mb el llengua ge algo ísmic es p esen a la a.ducció llengua ge PASCAL.
•La pa de Modula i zació la qual s 'ha adui al Tu boPASCAL (no al PASCAL s anda d)
u ili zan com a eina la uni .
•Un apa a dedica a }'es uc u a de dades lineal CUA.
2 Llengua ge A)go ísmic
En a.ques capí ol es p esen a. un esum de la. no a.ció del llengua ge a.lgo ísmic i la. se a aducció
al llengua. ge PASCAL. No es p e én e una exposició exhaus i a dels llengua. ges sino un b eu
esum dels ma eixos.
algo i me N omAlgo isme
usos
de inicio de cons an s
de inicio de ipus
decla acio de a iables
sen encies
algo i me
modul NomModul
especi icació
usos
de/inició de con an s
de inició de ipus
cap ale es de subp og ames
especi icació
implemen ació
implemen ació de subp og ames
implemen ació de subp og ames p i a s
implemen ació
modul
1
p og am NomAlgo isme
usos
de inició de cons an s
de inició de ipus
decla ació de a iables
begin
sen encies
end. accions_ uncions
uni NomModul
in e ace
usos
de/inició de cons an s
de/inició de ipus
cap9le es de subp og ames
implemen a ion
implemen ació de subp og ames
implemen ació de subp og ames p i a s
begin
end.

usos::=
usa
noms moduls
usa
de/inició de cons an s::=
cons
N omCons an : N omTipus = Exp essioCons an
cons
de inició de i pus::=
ipus
NouTipus
ipus
NouTipus:=
NomNouTipus = Tipus_elemen al
NomNouTipus = (nl, n2, .. .)
uses ( noms moduls )¡
( és una llis a sepa ada pe comes)
cons
NomCons an = Exp essióCons an
ype
NouTipus
NomNouTipus = aula {1 .. n1,1 .. n2, ... J de NomTipus
N omN ouTipus = upla
NomCampl, ... : NomTipus
upla
Tipus_elemen al:= en e , eal, ca ac e , boolea
Implemen ació en PASCAL:
NomNouTipus = Tipus_elemen al
NomNouTipus= (n1, n2, ... )
NomNouTipus=a ay[1. .n1,1. .n2, .... ] o NomTipus
NomNou Tipus= eco d
NomCamp1,NomCamp2, ... : NomTipus¡
end;
Tipus_elemen al:=in ege , eal, cha , boolean
2
a
decla ació de a iables::=
a Nom Va l, Nom Va 2, ... : NomTipus;
NomVa l,N omVa 2, ... : NomTipus
a
cap9ale es de subp og ames::=
accio NomAcció( Pa ame esFo malsAcció)
p ocedu e NomAccio(Pa ame esFo malsAcció)
uncio NomFunció( Pa ame esFo malsFunció ) e o na NomTipus
unc ion N omFunció(Pa ame esFo malsFunció): Nom Ti pus
cap9ale a de Subp og ames p i a s::=
accio p i ada NomAcció( Pa ame esFo malsAcció)
uncio p i ada NomFunció( Pa ame esFo malsFunció) e o na NomTipus
� Pascal
� Pascal
(PASCAL: els subp og ames p i a s es de ineixen dins de la pa d'implemen ació de les uni a s
sense indica la se a p i aci a )
Pa ame esFo malsAccio:: =
en Nom Va : NomTipus
en /so Nom Va : NomTipus
so Nom Va : NomTipus
Pa ame esFo malsFuncio:: =
en Nom Va : NomTipus
Sen encies::=
assignació
al e na i a o condicional
i e a i a_M en e
i e a i a_Fe
c ida a subp og ama
assignació : : =
Nom Va := exp essió
3
Nom Va : Nom ipus
a Nom Va : Nom ipus
a Nom Va : Nom ipus
En llengua ge algo ísmic es conside en co ee
es assignacions en e aules o uples semp e
que hi hagi conco dancia de ipus.
e

uncio Esbuidcua(en c: cua) e o na booleaes
Esbuidacua := (c.cmp = O)
uncio
uncio Esplenacua( en c: cua) e o na boolea. es
Explenacua. := ( cmp = max)
uncio
implemen acio
modul
4 Es ació de ens Ma sens
El cap de man enimen de l' es ació de e oca il de Ma sens ens enca ega que li dissenyem un algo isme
que alidi les maniob es que p e eu pe al de o ma els ens que li calen.
Pe po a a e me les maniob es l 'es ació de Ma sens només disposa d 'una ia de maniob es que
pe un ex em acaba en un ope i pe 1 'al e es a conec ada a una ia d 'en ada i a una al a de so ida.
Una maniob a es de ineix com una seqüencia de codis de mo imen al com {EESEESSS} que s'aplica a
un conjun dona d'iden i icado s o dena s de agó al com {idl, id2, id3, id4}. Els possibles mo imen s E
i S signi iquen espec i amen en a i eu e un agó de la ía de maniob es de mane a que, la seqüencia
indicada, quan s'aplica al conjun de agons dona , p odueix el nou conjun {id2, id4, id3, idl }.
U na seqüencia de mo imen s és admisible si con é an s codis E com S, o s els mo imen s indica s poden
po a -se a e me i el en o ma con é o s els agons dona s. Cada seqüencia de mo imen s s'acaba
amb un símbol especial. La in o mació associada a un agó cons a d'un nomb e na u al (iden i icado )
i d'un codi del conjun {PP, PS, CA, CO} que indica el ipus de ca ega del agó. Cada seqüencia de
agons s'acaba amb un símbol especial.
Es deman que:
•lmplemen is un modul pe a ges iona una cua de agons:CUAVAGO
•lmplemen is un modul pe a ges iona una pila de agons:PILAVAGO
•Usan les es uc u es de dades implemen ades, dissenya l'algo isme de ini com segueix:
unció Maniob a_ alida e o na boolea és
{ e o na CERT si la maniob a és alida i FALS en cas con a i }
7
Q<éld J ..lCS�
1