1
|
|
2
|
- Forutsetninger for og essensen i faget
- Metodekall, rekursjon, permutasjoner
- Analyse av algoritmer
- Introduksjon til ADT’er
- Den første ADT: trær
- Binære trær, binære søketrær
- Hashing, hash-tabeller
- B-TrærB+ trær. ADTer og stakker. Rød-svarte
trær
|
3
|
- Oppsummering av dagens forelesning:
- Disjunkte sett
- Relasjoner
- Ekvivalensrelasjoner
- Disjunkte sett ADT og operasjoner
- Problemer og løsninger
- Fun-time analyse
|
4
|
|
5
|
|
6
|
- Ekvivalensrelasjoner
- En ekvivalensrelasjon =
på
en mengde S er en relasjon =
span>med
- følgende egenskaper:
- 1. a ~ a for alle elementer a i S (refleksivitet)
- 2. Hvis a ~ b, så er b ~ a (symmetri)
- 3. Dersom a ~ b og b ~ c, så har vi også a ~ c (transiti=
vitet)
- Eksempel:
- En velkjent ekvivalensrelasjon er =/://3/3D relasjonen på tall.
|
7
|
- Flere eksempler:
- bilveirelasjonen:
- La S være mengden av tettsteder i Norge, og la a og b væ=
re
to tilfeldige
- tettsteder. Da er a b =
hvis
og bare hvis det finnes en måte å komme fra a til b
- ved å kjøre bil uten å bruke ferge.
- Under forutsetning av at ingen veier er enveiskjørte,
- er dette en ekvivalensrelasjon.
- går i samme klasse som definert over elevene ved en skole
- er en ekvivalensrelasjon.
|
8
|
- Ekvivalensklasser
- En ekvivalensrelasjon =
~ på
en mengde S deler elementene i S inn i
- ekvivalensklasser slik at alle elementene i en ekvivalensklasse Ei
- er relaterte til hverandre, men ikke med noen elementer i andre
- ekvivalensklasser i S.
- Vi sier at ekvivalensklassene utgjør disjunkte delmengder av =
S.
|
9
|
- Eksempel:
- Ekvivalensklasser som kan tenkes indusert av bilveirelasjonen define=
rt
- over mengden av tettsteder i Norge:
- E1 =/://3/3D {Longyearbyen}
- E2 =/://3/3D {Svolvær, Kabelvåg, Stamsund, Leknes, =
Reine,
Sørvågen}
- E3 =/://3/3D {alle tettstedene på fastlandet}
|
10
|
- Det dynamiske ekvivalensproblemet
- Ekvivalensproblemet består i å avgjøre om to
elementer a og b i S
- står i relasjon til hverandre, dvs. om a ~ b for en gitt
ekvivalensrelasjon .
- Hvis alle relasjonene mellom elementene er gitt eksplisitt ved en
- 2-dimensjonal boolsk matrise, behøver vi bare et enkelt oppsl=
ag i
- matrisen for å avgjøre om a ~ b.
|
11
|
- Grunnen til det er at antall relasjonsforhold vokser kvadratisk (n
2)
i
- forhold til antall elementer i mengden.
- I stedet er det vanlig å få oppgitt noen relasjonsforhol=
d,
f.eks. at a ~ b,
- c ~ d, e ~ a og d ~ b.
- Så må vi raskt kunne svare på om det fra de tre
ekvivalensegenskapene
- følger at a ~ d.
- Viktig observasjon:
- For å bestemme om a ~ d, er det nok å sjekke om de er i
samme ekvivalensklasse!
|
12
|
|
13
|
- Disjunkte mengder ADT
- Weiss kap. 8.1–8.5
- Løser ekvivalensproblemet
- Lett og rask implementasjon
- Vanskelig tidsforbrukanalyse
|
14
|
- Operasjonene til disjunkte mengder
- Disjunkt mengde ADT tilbyr to operasjoner:
- Find(a) returnerer en representant for ekvivalensklassen til element=
a.
- Representanten er altid den samme, uavhengig av hvilken a i
- ekvivalensklassen man angir.
- Union(a, b) legger inn opplysningen om at a ~ b.
- Operasjonen heter Union fordi effekten av å legge inn at a ~ b=
er
at
- ekvivalensklassene til a og b blir slått sammen (fordi de n&ar=
ing;
må tilhøre
- samme ekvivalensklasse).
|
15
|
- Vi kan løse ekvivalensproblemet på en mengde S ved
følgende algoritme:
- Ved starten av algorit=
men er
hvert element i sin egen ekvivalensklasse.
- Når vi får=
vite
at a ~ b, bruker vi operasjonen Union(a, b).
- Når vi skal
avgjøre om c ~ d, sjekker vi om Find(c) =/://3/3D=/://3/3D Find(d).
|
16
|
- Legg merke til at algoritmen er dynamisk på den måten at=
- ekvivalensklassene vil forandre seg etter hvert som vi utføre=
r
- union-operasjonene.
- Observasjon 1:
- Vi sammenligner ikke navnene (verdiene) til elementene direkte. Alt<=
/li>
- vi er interessert i er hvilken (ekvivalens) klasse de er i.
- Dermed kan vi for enkelhets skyld anta at at vi jobber med elementer=
- fra 1 til N og at Ei =/://3/3D {i} når algoritmen starter=
.
|
17
|
- Observasjon 2:
- Vi bryr oss egentlig ikke så mye om navnet på klassen so=
m Find
returnerer.
- Det som er viktig er at Find(a)=/://3/3D=/://3/3DFind(b) hvis og bare hvis a ~ b=
- (dvs. at a og b er i samme klasse).
- Observasjon 3:
- Man kan velge to strategier når man implementerer disjunkt sett
ADT:
- Find kan være rask, O (1), men da blir Union relativt treg, O =
(log
n)
- Union kan være rask, O (1), men da blir Find relativt treg, O =
(log
n).
- Det er bevist at man ikke kan få både Find og Union O (1)
samtidig.
|
18
|
- Implementasjon som gir rask finn
- Hvis vi ønsker O (1) tid for Find, kan vi bruke et array der =
vi
for hvert
- element lagrer navnet på ekvivalensklassen:
- Da blir Find bare et enkelt oppslag i tabellen.
- Men Union er kostbar fordi vi må gå gjennom hele arrayet=
og
bytte
- klassenavnet til alle elementer i klassene som skal slås samme=
n.
Det
- tar O (n) tid.
|
19
|
- Ved å ta vare på størrelsen til hver ekvivalenskl=
asse
og alltid la klassen
- med færrest elementer bytte navn til klassen med flest element=
er,
kan
- man garantere at N - 1 unioner (som er det meste man kan ha fø=
;r
alle N
- elementene er i samme klasse) ikke tar mer enn O (N log N) tid.
- Det kommer av at et el=
ement a
bare kan skifte klassetilhørighet log N
- ganger fordi antall elementer i klassen til a vil bli minst fordoble=
t
- ved hver eneste union.
|
20
|
- Implementasjon som gir hurtig union
- Vi implementerer operasjonene til disjunkte sett ved hjelp av en sko=
g,
- dvs. en mengde trær.
- Ideen er å plassere alle elementer i en
- ekvivalensklasse i samme tre, og la roten i treet identifisere
- ekvivalensklassen.
- Trærne er ikke binære, men allikevel veldig enkle fordi =
vi
bare behøver å
- lagre forelderpekeren for å finne roten, altså ingen
barnepekere.
|
21
|
- Legg merke til at trærne kan representeres ved et enkelt array=
S
- fra 1 til N:
- - S[i] =/://3/3D=/://3/3D y betyr at node nr. i har y som forelder.
- - S[i] =/://3/3D=/://3/3D -1 betyr at noden er en rotnode.
|
22
|
- Union gjøres ved å sette den ene rotpekeren til å
peke på den andre
- roten. Det tar konstant tid hvis vi allerede kjenner røttene =
til
klassene
- som skal slås sammen.
- Find(a) tilsvarer å traversere forelderpekeren opp til roten.<=
/li>
- Tidsforbruket er proporsjonalt med dybden til node a, og den er i ve=
rste
- fall O (N) (hvis alle nodene er i samme ekvivalensklasse).
- Gjennomsnittsanalysen til operasjonene er veldig vanskelig.
|
23
|
|
24
|
|
25
|
- Union-by-size
- Vi kan redusere tidsforbruket til finn-operasjonen ved å bruke=
en
- smartere union-strategi:
- Vi lar alltid det minste treet (færrest elementer) bli et subt=
re i
det største
- (flest elementer).
- Med denne strategien, kalt union-by-size, blir dybden til et tre
- maks log N.
- Det kommer av at når dybden til en gitt node a øker (med
1), så skjer det
- ved at treet det er med i blir slått sammen med et tre som er
større
- enn seg selv.
|
26
|
- Dermed fordobles (minst) antall noder i treet hver gang dybden til a=
- øker med 1.
- Det kan bare skje log N ganger.
- Finn-operasjonen blir altså O (log n).
- Vi må lagre størrelsen til hvert tre. Det kan typisk
gjøres ved å lagre den
- negative størrelsen i tabellcellen til roten.
|
27
|
|
28
|
- Union-by-height
- En annen union-strategi er å lagre høyden til hvert tre
(den lengste
- veien fra roten til en bladnode), og alltid la treet med minst
høyde bli
- subtre av treet med størst høyde.
- Høyden til det nye treet vil bare øke (med 1) når
trærne som slås
- sammen har samme høyde!
- Også denne strategien gir O (log n) tidsforbruk worst case.
|
29
|
- Stikomprimering
- Det er sannsynligvis ikke mulig å gjøre union på =
en
smartere måte, så
- vi kan i stedet prøve en lurere finn-strategi:
- Når vi skal svare på Find(a), kan vi minske dybden til
nodene i den
- grenen som a ligger i ved å forandre på forelderpekerne =
slik
at de peker
- direkte på roten.
|
30
|
- Anta at a har b som forelder. Da kan denne strategien enkelt
- implementeres rekursivt ved å sette S[a] =/://3/3D Find(b), dvs.
returverdien av
- det rekursive kallet til forelderen.
- Denne strategien kalles stikomprimering.
- Man kan vise at dersom man kombinerer stikomprimering med
- union-by-size eller union-by-height, så vil tidsforbruket til =
M
- union/finn-operasjoner bli nesten
- O (M).
|
31
|
- Neste gang:
- Prioritetskøer
- MAW, kap. 6
|