---

Hej alle

Alle de algoritmer og datastrukturer i kan finde på er i da velkomne til
at fortælle mig om. Alle afarter heraf og gerne links til sider der
forklarer og evt. implementerer disse.

Her tænker jeg bl.a. på

hob (heap)
binomial-køer (kender jeg intet til)
prioritetskøer


træ-strukturer
rød-sorte træer
højde-balancerede træer (kender jeg intet til)
rodede træer (kender jeg intet til - hvert blad har barn-pointer til roden)
prioritetssøgetræer


forskellige anvendelser indenfor dynamisk programmering
grådige algoritmer
og sikkert meget mere som jeg ikke lige pt. husker.

Graf-algoritmer:
----------------
Dijkstra
Kruskal
Prim
Disjunkte mængder


Graf-typer:
----------------
H(2)-grafer
Sol-grafer
Diamant-grafer
Frem og tilbage grafer
Ensrettede grafer
Syd-Øst grafer
Bælte grafer


De ovennævnte graf-typer er kendte, men flere beskrivelser af ANDRE
graf-typer ville være kanon og gerne med forklaring til hvorledes de vil
kunne implementeres nemmest, og hvilke datatyper der skal anvendes.
Implementationerne skal gerne være så optimale som mulig.


Jeg skal til eksamen 2. januar og vil gerne have 100% styr på tingene og
være forberedt på de værste graf-typer - mærkelige datatyper som minder
om de nævnte emner. Træ-strukturer kommer der garanteret også noget med.

Forklaringer til Dijkstra's algoritme og evt. implementation er også savnet!

På forhånd MANGE MANGE tak.



Med venlig hilsen
Preben Holm


--
If your Dell laptop is unstable, try change the power supply - it works!
But the Dell will still stink! Nothing can change that!!!

---

Nogle gode implementationer og forklaring til specielt

Hash-tabeller og en rigtig god forklaring til hash-funktioner!

Rød-sorte træer (virkelig god forklaring kunne bruges)! Specielt en
implementation kunne være dejlig!


Mvh / Preben

---

Hob:

En hob-struktur:

hvordan kan man sige at hob-strukturen er opfyldt hvis et træ ser sådan ud:

root
/ \
l1 r1
/ \ \
l2 r2 r3
\ \
l3 r4


Mvh / Preben

--
If your Dell laptop is unstable, try change the power supply - it works!
But the Dell will still stink! Nothing can change that!!!

---

Preben <64bitATtheNet@mailme.dk> writes:

> Alle de algoritmer og datastrukturer i kan finde på er i da velkomne
> til at fortælle mig om. Alle afarter heraf og gerne links til sider
> der forklarer og evt. implementerer disse.
> [ ... ]
> Jeg skal til eksamen 2. januar og vil gerne have 100% styr på tingene
> og være forberedt på de værste graf-typer - mærkelige datatyper som
> minder om de nævnte emner. Træ-strukturer kommer der garanteret også
> noget med.

Har I ikke noget undervisningsmateriale der forklarer alle de ting I
skal til eksamen i? Det er vel det mest nærliggende sted at søge
informationen.

Hvis undervisningsmaterialet er på engelsk, så er det også fyldt med
gode søgeord til Google.

> Forklaringer til Dijkstra's algoritme og evt. implementation er også savnet!

Hvorfor er en implementation interessant? Er det ikke mere forståelsen
af algoritmen der er interessant? Min erfaring siger at den bedst
opnås ved at gå nogle gennemløb af algoritmen igennem i hånden og
efterfølgende evt. lave sin egen implementation frem for at køre en
implementation andre har lavet.

--
Jacob - www.bunk.cc
Put your trust in those who are worthy.

---

Hej

De nævnte graf-typer er ikke nævnt i litteraturen, men er fra tidligere
eksamensopgaver. Det er dog tydeligt at se, at nogle af algoritmerne
ikke er "opfundet" af dem selv, men faktisk virkelige - eller i hvert
fald noget der ligner. Derfor vil jeg gerne være specielt forberedt på
forskellige typer grafer hvorpå Dijkstra, kruskal, prim osv. ikke
længere er optimale til letteste udspændende træer og korteste veje
algoritmer. Derfor også gerne eksempler på METODER til implementation
(gode forklaringer er nok).


> Hvis undervisningsmaterialet er på engelsk, så er det også fyldt med
> gode søgeord til Google.

Jeg synes det er svært at finde noget relevant altid. Der er ganske
rigtigt meget store komplekse implementationer uden de store
forklaringer, som ikke rigtig giver det udbytte man kom efter. Det er
også nemt nok at finde illustrationer (java) som viser step-by-step
hvordan det virker.

Det er også gerne andre datatyper, algoritmer som blot minder om der
ville være lækre at vide en masse om.


>>Forklaringer til Dijkstra's algoritme og evt. implementation er også savnet!
>
>
> Hvorfor er en implementation interessant? Er det ikke mere forståelsen
> af algoritmen der er interessant? Min erfaring siger at den bedst
> opnås ved at gå nogle gennemløb af algoritmen igennem i hånden og
> efterfølgende evt. lave sin egen implementation frem for at køre en
> implementation andre har lavet.

Det er netop hvordan denne algoritme skal implementeres jeg har svært
ved at forstå. Eller måske det også kan være forståelse.. og helt ærlig
- så den lærebog (Cormen et. al - Introduction to Algorithms) er sq
ekstremt dårlig for at sige det mildt. Han går alt for meget i selvsving
nogen gange... Jeg vil sige sådan at bogen er meget god til
datastrukturer (i nogle tilfælde), men til forklaring af algoritmer -
der går det altså galt når vi bevæger os udover sortering.

Nå, men tilbage til Dijkstra. (jeg har ikke bogen liggende her -
desværre, men efter hukommelsen følger)

Man skal anvende en prioritetskø (hvis jeg ikke husker helt galt)
"sorteret" efter d-værdier (altså indtil videre korteste vej til given
knude. Men netop når man initialiserer Dijkstra følger det at d for
"roden" sættes lig nul og resten til "uendelig". Når man har besøgt
roden og dens dertil alle naboer og "relaxed" alle disse knuder. Så skal
værdien i prioritetskø'en jo opdateres - men den tilhørende værdi i
kø'en (lad os antage dette som værende en ens reference, således
relaxeringen har ændret d-værdi for hoben ligeledes) så kræver det jo en
opdatering af kø'en. Denne opdatering ser jeg værende meget dyr (og ikke
beskrevet i Cormen (kan selvfølgelig skyldes jeg er halvblind nogle
gange *gg*)) og jeg kan derfor ikke se hvordan køretiden kan overholdes?
Når man ændrer et "tilfældigt" element i en kø, så er det vel ikke
længere på nogen måde en prioritetskø, uden der sker ændringer i køen.
Hvor i relaxeringen ligger dette!


Mvh / Preben


--
If your Dell laptop is unstable, try change the power supply - it works!
But the Dell will still stink! Nothing can change that!!!

---

Preben <64bitATtheNet@mailme.dk> writes:

> [ ... ] helt ærlig - så den lærebog (Cormen et. al - Introduction to
> Algorithms) er sq ekstremt dårlig for at sige det mildt.

Jeg var nu vældig glad for den da jeg havde et kursus, hvor den blev
brugt. Jeg har også tit slået op i den efterfølgende.

Det er rigtigt at bogen er amerikansk, og man somme tider lige skal
filtrere alt fyldstoffet væk, men det er man vel vant til fra andre
amerikanske bøger.

> Nå, men tilbage til Dijkstra. (jeg har ikke bogen liggende her -
> desværre, men efter hukommelsen følger)

Jeg har bogen i 1. udgave. Jeg skal prøve at svare dig konsistent med
hvad der står i den.

> Man skal anvende en prioritetskø (hvis jeg ikke husker helt galt)
> "sorteret" efter d-værdier (altså indtil videre korteste vej til given
> knude. Men netop når man initialiserer Dijkstra følger det at d for
> "roden" sættes lig nul og resten til "uendelig".

Hvorfor siger du at køen skal være sorteret? Det er der ikke noget
krav om. Det er også derfor at EXTRACT-MIN() tager O(V) hvis køen er
implementeret som et array, men kan gøres hurtigere, hvis den er
implementeret som en heap. Måske er det her det går galt for dig? Skim
lige afsnittet om prioritetskøer igen.

> Når man har besøgt roden og dens dertil alle naboer og "relaxed"
> alle disse knuder. Så skal værdien i prioritetskø'en jo opdateres -
> men den tilhørende værdi i kø'en (lad os antage dette som værende en
> ens reference, således relaxeringen har ændret d-værdi for hoben
> ligeledes) så kræver det jo en opdatering af kø'en.

Ja, men RELAX(u, v, w) kører jo i konstant tid så længe d er et array,
hvor man kan tilgå elementerne i konstant tid.

> Denne opdatering ser jeg værende meget dyr (og ikke beskrevet i
> Cormen (kan selvfølgelig skyldes jeg er halvblind nogle gange *gg*))
> og jeg kan derfor ikke se hvordan køretiden kan overholdes?

Hvorfor ser du den opdatering som dyr? Der er tale om at man i et
array, d, holder en enkelt værdi for hver node i grafen. Den værdi kan
ændres i konstant tid. Det gør man så for alle kanter (v \in Adj[u])
fra u.

Hele opdateringen er da beskrevet.

> Når man ændrer et "tilfældigt" element i en kø, så er det vel ikke
> længere på nogen måde en prioritetskø, uden der sker ændringer i
> køen.

Jo.

> Hvor i relaxeringen ligger dette!

Det sker ikke.

--
Jacob - www.bunk.cc
Life is both difficult and time-consuming.

---

Scripsit Jacob Bunk Nielsen <spam@bunk.cc>
> Preben <64bitATtheNet@mailme.dk> writes:

> > Man skal anvende en prioritetskø (hvis jeg ikke husker helt galt)
> > "sorteret" efter d-værdier (altså indtil videre korteste vej til given
> > knude. Men netop når man initialiserer Dijkstra følger det at d for
> > "roden" sættes lig nul og resten til "uendelig".

> Hvorfor siger du at køen skal være sorteret?

Han mener at afstanden er den vægt der bruges til at vælge det
"minimale" element i den dertil beregnede prioritetskø-operation.

> Det er også derfor at EXTRACT-MIN() tager O(V) hvis køen er
> implementeret som et array, men kan gøres hurtigere, hvis den er
> implementeret som en heap.

Og derfor er det en dum ide at bruge en array uden yderligere invarianter.

> > Denne opdatering ser jeg værende meget dyr (og ikke beskrevet i
> > Cormen (kan selvfølgelig skyldes jeg er halvblind nogle gange *gg*))
> > og jeg kan derfor ikke se hvordan køretiden kan overholdes?

> Hvorfor ser du den opdatering som dyr?

Det koster tid at vedligeholde de invarianter implementeringen af
prioritetskøen afhænger af, når vægtene ændres.

Hvis priorietskøen er implementeret som et hobordnet træ [1], kræver
en ændring af vægten at man lader elementet boble opad eller nedad i
strukturen for at bevare invarianten. Det tager i almindelighed
O(logn) tid, og det kan nok godt betegnes som dyrt, hvis man havde
håbet på en samlet løsning der kører i O(e+v*log(v)) i stedet for
O(e*log(v)).

Det er muligt at man kan amortisere nogen af disse ekstraomkostninger
væk, når alle ændringer går *nedad*, men det kan jeg ikke lige ryste
ud af ærmet.


[1] Træet kan igen være repræsenteret implicit som en array, men det
er en anden sag.

--
Henning Makholm "`Update' isn't a bad word; in the right setting it is
useful. In the wrong setting, though, it is destructive..."

---

Jacob Bunk Nielsen wrote:

> Preben <64bitATtheNet@mailme.dk> writes:
>
>
>>[ ... ] helt ærlig - så den lærebog (Cormen et. al - Introduction to
>>Algorithms) er sq ekstremt dårlig for at sige det mildt.
>
>
> Jeg var nu vældig glad for den da jeg havde et kursus, hvor den blev
> brugt. Jeg har også tit slået op i den efterfølgende.
>
> Det er rigtigt at bogen er amerikansk, og man somme tider lige skal
> filtrere alt fyldstoffet væk, men det er man vel vant til fra andre
> amerikanske bøger.
>
>
>>Nå, men tilbage til Dijkstra. (jeg har ikke bogen liggende her -
>>desværre, men efter hukommelsen følger)
>
>
> Jeg har bogen i 1. udgave. Jeg skal prøve at svare dig konsistent med
> hvad der står i den.

Det kunne være en fordel - de er mange gange ikke fyldt med unødvendigt
bras.


>>Man skal anvende en prioritetskø (hvis jeg ikke husker helt galt)
>>"sorteret" efter d-værdier (altså indtil videre korteste vej til given
>>knude. Men netop når man initialiserer Dijkstra følger det at d for
>>"roden" sættes lig nul og resten til "uendelig".
>
>
> Hvorfor siger du at køen skal være sorteret? Det er der ikke noget
> krav om. Det er også derfor at EXTRACT-MIN() tager O(V) hvis køen er
> implementeret som et array, men kan gøres hurtigere, hvis den er
> implementeret som en heap. Måske er det her det går galt for dig? Skim
> lige afsnittet om prioritetskøer igen.

Ahh, ok - der var lige lidt jeg manglede... For vi har kun gennemgået
prioritetskøer opbygget som hob'er, og det gør jo en hvis forskel - kan
man roligt sige!

Når vi skal nå gennem (jeg mener alle beskrevne) sorteringsalgoritmer,
forskellige beviser, dyn. programmering, grådige algoritmer,
graf-algoritmer, træ-strukturer indtil rød-sorte træer på kun ½ år, så
går det altså hurtigt... Det er et lidt andet tempo end man lige var
vandt til - selv i forhold til de to første semestre. Og når det skal gå
så stærkt at man til forelæsningerne ikke har tid til at gennemgå
rød-sorte træer og hash-tabeller ordentligt og man selv når at lave så
mange fejl at ingen af de viste eksempler med rotationer passer, så er
det ikke ligefrem noget man bliver mere vel-orienteret om.
(Aggressionerne skulle lige ud *gg*)



>>Når man har besøgt roden og dens dertil alle naboer og "relaxed"
>>alle disse knuder. Så skal værdien i prioritetskø'en jo opdateres -
>>men den tilhørende værdi i kø'en (lad os antage dette som værende en
>>ens reference, således relaxeringen har ændret d-værdi for hoben
>>ligeledes) så kræver det jo en opdatering af kø'en.
>
>
> Ja, men RELAX(u, v, w) kører jo i konstant tid så længe d er et array,
> hvor man kan tilgå elementerne i konstant tid.

Ja, sålænge det er et array :)



Mvh / Preben

--
If your Dell laptop is unstable, try change the power supply - it works!
But the Dell will still stink! Nothing can change that!!!

---

Henning Makholm <henning@makholm.net> writes:
> Scripsit Jacob Bunk Nielsen <spam@bunk.cc>
>
>> Hvorfor siger du at køen skal være sorteret?
>
> Han mener at afstanden er den vægt der bruges til at vælge det
> "minimale" element i den dertil beregnede prioritetskø-operation.

Jo, det er jeg med på, men hvis man læser bogen - jeg prøver at svare
ud fra hvad der står i den bog Preben tilsyneladende har som
undervisningsmateriale - er køretiden forklaret ud fra at man bruger
O(V) på at køre EXTRACT-MIN() fordi køen er implementeret som et
array.

>> Det er også derfor at EXTRACT-MIN() tager O(V) hvis køen er
>> implementeret som et array, men kan gøres hurtigere, hvis den er
>> implementeret som en heap.
>
> Og derfor er det en dum ide at bruge en array uden yderligere invarianter.

Ja - det forklarer bogen også senere. Den beskriver også i hvilke
situationer det er særlig interessant.

Det er dog IMHO ikke så væsentligt for at forstå køretiden. Vælger man
en anden løsning, så vil EXTRACT-MIN() også kunne køre meget hurtigere
end O(V), og så kan man stadig sagtens få Dijkstras algoritme til at
køre i O(V²) som forklaret i bogen.

>> > Denne opdatering ser jeg værende meget dyr (og ikke beskrevet i
>> > Cormen (kan selvfølgelig skyldes jeg er halvblind nogle gange *gg*))
>> > og jeg kan derfor ikke se hvordan køretiden kan overholdes?
>
>> Hvorfor ser du den opdatering som dyr?
>
> Det koster tid at vedligeholde de invarianter implementeringen af
> prioritetskøen afhænger af, når vægtene ændres.

Ja, det er klart - men i den variant der er beskrevet i omtalte bog er
der ikke nogle dyre invarianter at vedligeholde. Der kan det gøres i
konstant tid fordi der blot benyttes et array, og EXTRACT-MIN() så
kører i O(V).

Kort fortalt, så kan man vinde på EXTRACT-MIN() ved at betale lidt
ekstra for RELAX(). Man skal ikke "betale" dyrt begge steder.

--
Jacob - www.bunk.cc
It is easier to get forgiveness than permission.

---

Scripsit Jacob Bunk Nielsen <spam@bunk.cc>
> Henning Makholm <henning@makholm.net> writes:

> > Og derfor er det en dum ide at bruge en array uden yderligere invarianter.

> Ja - det forklarer bogen også senere.

Ved nøjere eftertanke tror jeg nu nok alligevel jeg trækker det
tilbage. Hvis grafen er tæt, vil en lineær søgning efter den mindste
knude ikke tage længere tid end det tager at behandle alle de udgående
kanter, og så kan det jo være ligemeget alligevel.

> Vælger man en anden løsning, så vil EXTRACT-MIN() også kunne køre
> meget hurtigere end O(V), og så kan man stadig sagtens få Dijkstras
> algoritme til at køre i O(V²) som forklaret i bogen.

Der må være noget amortisering på spil, så.

--
Henning Makholm "It's kind of scary. Win a revolution and
a bunch of lawyers pop out of the woodwork."

---

Preben wrote:
> Alle de algoritmer og datastrukturer i kan finde på er i da velkomne til
> at fortælle mig om. Alle afarter heraf og gerne links til sider der
> forklarer og evt. implementerer disse.

I stedet for at jeg skal skrive en bog af og sende den som et indlæg,
foreslår jeg at du tager et kig på den selv. Den hedder "Algorithm
Design" og er skrevet af Michael T. Goodrich og Roberto Tamassia.

En glimrende bog som handler om alt det som du spørger til.

Lur mig om ikke at jeg - ved et rent tilfælde, selvfølgelig - havde
skrevet nøjagtigt det samme som der står i bogen, hvis jeg havde ladet
mig overtale til at beskrive alle de mange ting som du spørger efter.

Den kan fåes i bogladen på RUC (med mindre at de har udsolgt).

God læselyst.

Michael.

---

On Sun, 28 Dec 2003 21:21:34 +0100, Preben wrote:

> Alle de algoritmer og datastrukturer i kan finde på er i da velkomne til
> at fortælle mig om. Alle afarter heraf og gerne links til sider der
> forklarer og evt. implementerer disse.

Mht. implementationer (C++) af væsentlige datastrukturer og operationer
på disse:

http://boost.org/libs/graph/doc/table_of_contents.html

--
Greetings from Troels Arvin, Copenhagen, Denmark

---

Jeg skrev tidligere til Preben:

> Mht. implementationer (C++) af væsentlige datastrukturer og operationer
> på disse:
>
> http://boost.org/libs/graph/doc/table_of_contents.html

Ved nærmere eftertanke, så er Boost's graph-bibliotek nok ikke det mest
stedet for de mest illustrative implementationer.

Tidligere nævnte du Java, og jeg går ud fra, at du ønsker
implementations-eksempler i det sprog. I så fald ville jeg i dit sted
hente sovsen til Java:
http://wwws.sun.com/software/communitysource/j2se/java2/download.html Dér
kan du fx. se, hvordan java.util.Hashtable er kodet. Ulempen er dog lidt
ligesom ved boost: Fordi der er tale om "produktionskode", indeholder den
forskellige optimeringer og hjælpemetoder, der kan sløre kernen af
algoritmerne/strukturerne.

Det lyder desuden som om, at du har behov for et hurtigt supplement til
din algoritmikbog - med fokus på implementation.

Når man hurtigt skal have en bog, kan en online-udgave være på sin
plads, og i sådanne situationer har jeg flere gange haft gavn af Safari,
hvor man kan købe sig adgang til en pæn sjat bøger i online-udgaver. Se
fx.
http://safari.oreilly.com/?x=1&mode=books&sortKey=title&sortOrder=asc&view=&xmlid=&open=true&g=&catid=itbooks.csci.algrthms&s=1&b=1&f=1&t=1&c=1&u=1&r=&o=1&srchText=
og
http://safari.oreilly.com/?x=1&mode=section&sortKey=title&sortOrder=asc&view=&xmlid=0-201-36120-5&open=true&g=&catid=itbooks.prog.java&s=1&b=1&f=1&t=1&c=1&u=1&r=&o=1&page=0

(Jeg har ikke læst nogle af de nævnte bøger.)

--
Greetings from Troels Arvin, Copenhagen, Denmark

---

Troels Arvin wrote:

> On Sun, 28 Dec 2003 21:21:34 +0100, Preben wrote:
>
>
>>Alle de algoritmer og datastrukturer i kan finde på er i da velkomne til
>>at fortælle mig om. Alle afarter heraf og gerne links til sider der
>>forklarer og evt. implementerer disse.
>
>
> Mht. implementationer (C++) af væsentlige datastrukturer og operationer
> på disse:
>
> http://boost.org/libs/graph/doc/table_of_contents.html
>

Tak for linket... og også til de to bøger.. Der kan jo læses lidt
"introduction" til hver algoritme - og det er nogen gange nok jo!

Jeg har overvejet et SAFARI medlemskab nogen gange, men det er vel ikke
muligt at få bøgerne i PDF? Desuden skal man jo hele tiden betale for at
have adgang til bøgerne!


Mvh / Preben

--
If your Dell laptop is unstable, try change the power supply - it works!
But the Dell will still stink! Nothing can change that!!!

---

On Mon, 29 Dec 2003 06:23:36 +0100, Preben wrote:

> Jeg har overvejet et SAFARI medlemskab nogen gange, men det er vel ikke
> muligt at få bøgerne i PDF?

Du kan få kapitler som PDF, hvilket er en ret ny feature. Desværre skal
man betale ekstra for adgang til PDFer.

> Desuden skal man jo hele tiden betale for at
> have adgang til bøgerne!

Det er sandt.

--
Greetings from Troels Arvin, Copenhagen, Denmark

---

"Preben" <64bitATtheNet@mailme.dk> skrev i en meddelelse
news:3fef3b4f$0$95001$edfadb0f@dread11.news.tele.dk...
> Hej alle
>

> Jeg skal til eksamen 2. januar og vil gerne have 100% styr på tingene og
> være forberedt på de værste graf-typer - mærkelige datatyper som minder

> Med venlig hilsen
> Preben Holm


Hej Preben.

Har du nogensinde hørt om forberedelse i god tid?

Du har sikkert vidst i ca. et halvt års tid at du skulle til eksamen d. 2
januar 2004. Du har ligeledes også haft Juleferie fra sikkert d. 19 december
2003. Er det ikke lidt sent at du går i gang?
De indlæg du er kommet med er jo relevante helt sikkert for en eksamen, jeg
lavede en afhandling om dette i 1994. med implementeringer og beviser for de
forskellige prioritetskøer, algoritmer og datastrukturer.

Det eneste jeg kan råde dig til er hvis du skal bevise fordele/ulemper i de
enkelte algoritmer/strukturer skal du først og fremmest beskrive dit formål
(overfor dig selv). Og afprøve algoritmen på dine egne elementer og kode.
Herved får du "foræret" din implementringsmodel.

Som jeg læste et indlæg i denne tråd var der en der sagde meget fornuftigt
at man skulle skrive ned på et stykke papir først for at afprøve teorien, og
derefter lave en implementeringsmodel. Og jeg må sande min erfaring siger
mig. Selv inden for datalogi er man nødt til at "skynde sig langsomt".

Lad være med at holde nytår, og brug din tid fornuftigt i stedet for at gøre
det i sidste øjeblik.

Og husk det allervigtigste, der er ingen fuldstændig "facitliste" inden for
datalogi. Hvis du kan argumentere for en bestemt datastruktur/algoritme
uanset hvilke fordele/ulemper den måtte have, så er det jo egentlig dit
valg. Hvorfor crasher MS-Windows eller Linux er det p.g.a. kompleksitet
eller inkompleksitet? Er det p.g.a. dårligt implementrede
algoritmer/datatstrukturer? Hvis du kan forklare datastrukturen for at sætte
ting i køleskabet, og ud af dette skrive en algoritme, så har du nået dit
mål.

Hårde ord, men nogle skal holde en moralprædiken.

Mvh, Billyboy

Don't try harder, just try smarter.