---

Nu er jeg efterhånden stødt ind i ordet algoritme mange steder, og jeg kunne
godt tænke mig at vide mere om hvad det egentlig er. Jeg er helt nybegynder
på det område, men har altså matematik i 2g. Hvis nogen kender nogle gode
sider på nettet eller bøger hvor man kan finde oplysninger??? Men altså ikke
alt for indviklet.

- Rikke =)

---

> Nu er jeg efterhånden stødt ind i ordet algoritme mange steder, og jeg
kunne
> godt tænke mig at vide mere om hvad det egentlig er. Jeg er helt
nybegynder
> på det område, men har altså matematik i 2g. Hvis nogen kender nogle gode
> sider på nettet eller bøger hvor man kan finde oplysninger??? Men altså
ikke
> alt for indviklet.
En algoritme er en metode til at løse et bestemt "problem".
Det bruges hyppigt i computerverdenen hvor programmører arbejder med
algoritmer.
Et eksempel er en algoritme der tager en tekstfil og søger efter en given
streng etc.
Hvis du har matematik på gym, med de sædvanelige bøger af Carstensen og
Frandsen, kan du slå op under Newton-Raphsons metode, der er en algoritme,
kan til iteration mener jeg ;)

mvh
Peter

---

Hej.

> Nu er jeg efterhånden stødt ind i ordet algoritme mange steder, og jeg
kunne
> godt tænke mig at vide mere om hvad det egentlig er. Jeg er helt
nybegynder
> på det område, men har altså matematik i 2g. Hvis nogen kender nogle gode
> sider på nettet eller bøger hvor man kan finde oplysninger??? Men altså
ikke
> alt for indviklet.

En algoritme er blot en række trin (beregninger) der kan udføres på endelig
tid, der er ikke noget dybere i det.
Men begrebet er bestemt centralt, især nu efter der er kommet computere på
banen.

Som et eksempel du kender kan nævnes, divisionsalgoritmen.
Altså den fremgangsmåde du følger, når du skal dividere to tal med hinanden
på papir.

-mb

--
Martin Bundgaard (mb@imf.au.dk)
Department of Mathematical Sciences
University of Aarhus, Denmark

---

Martin Bundgaard <mb@imf.au.dk> wrote:
> En algoritme er blot en række trin (beregninger) der kan udføres på endelig
> tid, der er ikke noget dybere i det.

En "algoritme" der ikke udføres på endelig tid, er vel stadig en
algoritme.
Sådan som jeg har set definitionen så er en algoritme korrekt, hvis:
- Den "løser" problemet.
- Den terminere, dvs. det kan udføres i endelig tid.
Sådan som jeg ser det, er det stadig en algoritme, selv om den ikke
udføres i endelig tid. Den kan blot ikke være korrekt.

Men okay, det er blot et spørgsmål om definitioner og har ikke nogen
konkret betydning. En algoritme der ikke terminere er ikke særlig
brugbar (det kunne selvfølgelig være microsoft kunne bruge det til
noget, jeg synes deres programmer terminere ustandseligt

Martin

---

"Martin Ehmsen" <ehmsen@imada.sdu.dk> skrev i en meddelelse
news:a8imnm$b10$1@sunsite.dk...

> En algoritme der ikke terminere er ikke særlig brugbar

Hvad med et operativsystem for en computer, som
aldrig slukkes?

--
Jens Axel Søgaard

---

Jens Axel Søgaard skrev:

>Hvad med et operativsystem for en computer, som
>aldrig slukkes?

Et operativsystem er ikke en algoritme.

--
Bertel
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

"Bertel Lund Hansen" <nospam@lundhansen.dk> skrev i en meddelelse
news:sobqau4k03dnsgok7v13fr3tu1400b041p@sunsite.auc.dk...
> Jens Axel Søgaard skrev:
>
> >Hvad med et operativsystem for en computer, som
> >aldrig slukkes?
>
> Et operativsystem er ikke en algoritme.

Nej - men operativsystemet følger en algoritme.
Her er en til et singletask OS:

loop
Indlæs program
Kør program
endloop

--
Jens Axel Søgaard

---

"Jens Axel Søgaard" <usenet@soegaard.net> wrote:
>> En algoritme der ikke terminere er ikke særlig brugbar
> Hvad med et operativsystem for en computer, som
> aldrig slukkes?

Sådan som jeg ser en algoritme, så er det en "foreskrift" som til noget
input, giver noget output, på en eller anden måde.
Et operativsystem giver ikke noget output!

Men som du også kan se af mit indlæg, så kan et operativsystem godt
siges at være en algoritme, men blot ikke en korrekt en.

Martin
--
"Science is like sex: sometimes something useful comes out, but that is
not the reason we are doing it"
   Richard Feyman

---

"Martin Ehmsen" <ehmsen@imada.sdu.dk> skrev i en meddelelse
news:a8jvd7$i0j$1@sunsite.dk...
> "Jens Axel Søgaard" <usenet@soegaard.net> wrote:
> >> En algoritme der ikke terminere er ikke særlig brugbar
> > Hvad med et operativsystem for en computer, som
> > aldrig slukkes?
>
> Sådan som jeg ser en algoritme, så er det en "foreskrift" som til noget
> input, giver noget output, på en eller anden måde.
> Et operativsystem giver ikke noget output!

Du sidder med en sort skærm?

Outputtet er outputtet af det første program, OS'et kører
fulgt af outputtet af det andet, ...

Men du har ret i, at det selvfølgelig hænger på, om man
opfatter algoritmer, som noget der skal terminere, eller ej.

--
Jens Axel Søgaard

---

Martin Ehmsen skrev:

>Sådan som jeg ser det, er det stadig en algoritme, selv om den ikke
>udføres i endelig tid. Den kan blot ikke være korrekt.

Så er divisionsalgoritmen ukorrekt. 10/3 terminerer aldrig.

--
Bertel
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

"Bertel Lund Hansen" <nospam@lundhansen.dk> wrote in message
news:p5drau0bid2jqd5o8igkbd78pe5ssqg4a2@sunsite.auc.dk...
> Martin Ehmsen skrev:
>
> >Sådan som jeg ser det, er det stadig en algoritme, selv om den ikke
> >udføres i endelig tid. Den kan blot ikke være korrekt.
>
> Så er divisionsalgoritmen ukorrekt. 10/3 terminerer aldrig.

Det afhænger af hvordan man definerer en divisionsalgoritme. Jeg har aldrig
set en divisionalgoritme der ikke terminerer (uanset hvilket input den
modtager)

---

"Thomas Krog" <rick@kampsax.dtu.dk> skrev i en meddelelse
news:a8kf6u$itb$1@eising.k-net.dk...
> "Bertel Lund Hansen" <nospam@lundhansen.dk> wrote in message
> news:p5drau0bid2jqd5o8igkbd78pe5ssqg4a2@sunsite.auc.dk...
> > Martin Ehmsen skrev:
> >
> > >Sådan som jeg ser det, er det stadig en algoritme, selv om den ikke
> > >udføres i endelig tid. Den kan blot ikke være korrekt.
> >
> > Så er divisionsalgoritmen ukorrekt. 10/3 terminerer aldrig.
>
> Det afhænger af hvordan man definerer en divisionsalgoritme. Jeg har
aldrig
> set en divisionalgoritme der ikke terminerer (uanset hvilket input den
> modtager)

Det kommer an på om man tænker i heltalsdivision,
for så bliver svaret 3, eller om tænker i reele tal, for så er svaret
3,333333.....

--
Jens Axel Søgaard

---

> Det kommer an på om man tænker i heltalsdivision,
> for så bliver svaret 3, eller om tænker i reele tal, for så er svaret
> 3,333333.....

tvivler dog på der er nogen (computere eller mennesker) der har fulgt en
sådan algoritme i praksis :)

---

"Thomas Krog" <rick@kampsax.dtu.dk> wrote in message
news:a8lknd$b0f$1@eising.k-net.dk...
> > Det kommer an på om man tænker i heltalsdivision,
> > for så bliver svaret 3, eller om tænker i reele tal, for så er svaret
> > 3,333333.....
>
> tvivler dog på der er nogen (computere eller mennesker) der har fulgt en
> sådan algoritme i praksis :)

man kunne også lave algoritmen sådan så den terminerer hvis den "havner i
samme situation 2 gange" så kan den endda fortælle hvilken sekvens af tal
der fortsætter i det uendelige:

fx 10/7 = 1,4285714...
Når den møder 4 tallet for 2. gang ved den at sekvensen 428571 vil fortsætte
i det uendelige og kan derfor terminere uden tab af præcision

---

Thomas Krog skrev:

>Når den møder 4 tallet for 2. gang ved den at sekvensen 428571 vil fortsætte
>i det uendelige og kan derfor terminere uden tab af præcision

Ja, hvis den har gemt alle resterne fra divisionerne. Ikke blot
cifret, men også resten skal være den samme.

--
Bertel
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen <nospam@lundhansen.dk> wrote:
> Martin Ehmsen skrev:

>>Sådan som jeg ser det, er det stadig en algoritme, selv om den ikke
>>udføres i endelig tid. Den kan blot ikke være korrekt.

> Så er divisionsalgoritmen ukorrekt. 10/3 terminerer aldrig.

Det er som de andre indlæg også siger, an på hvordan du definere din
divisionsalgoritme.

Men jeg må altså stå fast på mit synspunkt om at en algoritme skal
terminere. Jeg citere følgende fra noterne til et algoritmekursus:

"En algoritme er _korrekt_, hvis
1. algoritmen terminere, og
2. algoritmen er partielt korrekt.

En algoritme er partielt korrekt, hvis der for enhver udførelse, for
hvilken præbetingelsen er opfyldt, gælder, at hvis postbetingelsen nås,
så er den også opfyldt."

Martin
--
"Science is like sex: sometimes something useful comes out, but that is
not the reason we are doing it"
   Richard Feyman

---

On Thu, 4 Apr 2002 23:35:06 +0200, "Martin Bundgaard" <mb@imf.au.dk>
wrote:

>En algoritme er blot en række trin (beregninger) der kan udføres på endelig
>tid, der er ikke noget dybere i det.
>Men begrebet er bestemt centralt, især nu efter der er kommet computere på
>banen.

Man kan teoretisk set tillade sig at sige, at en algoritme lige netop
er et program, som kan afvikles på en universiel Turing maskine. Dette
er Church's tese. Vedr. at programmet kan "udføres på endelig tid" så
mener jeg ikke, at det er et krav til en algoritme. Det ville i hvert
give et stort praktisk problem, da det så ville være umuligt generelt
at afgøre om man står med en algortime eller ej, da det jvf. halting
problemet er uafgørligt om en vilkårlig algoritme rent faktisk
terminerer.

Her er lidt saks fra et (næsten) tilfældigt website fundet vha Google:

http://www.cse.msu.edu/~torng/360Book/TM/

The Turing machine model : A formal model for representing algorithms.

Church's Thesis: This thesis states that any algorithm can be
represented as a Turing machine.

Universal Turing machines: A Turing machine which acts like a modern
general purpose computer in that it can "run" other Turing machines
and thus solve any problem which can be solved by Turing machines.

Undecidability: A formal proof that natural, important problems such
as the halting problem are "undecidable" or unsolvable.

Med venlig hilsen Sven.

When I gave a lecture in Japan,
I was asked not to mention the possible recollapse of the Universe,
because it might affect the stock market.
(Stephen Hawking)

---

> Man kan teoretisk set tillade sig at sige, at en algoritme lige netop
> er et program, som kan afvikles på en universiel Turing maskine. Dette
> er Church's tese. Vedr. at programmet kan "udføres på endelig tid" så
> mener jeg ikke, at det er et krav til en algoritme. Det ville i hvert
> give et stort praktisk problem, da det så ville være umuligt generelt
> at afgøre om man står med en algortime eller ej, da det jvf. halting
> problemet er uafgørligt om en vilkårlig algoritme rent faktisk
> terminerer.

Nej, men man skal lige huske hvem det er der spørger.

-mb

---

Rikke Bendlin wrote:

> Nu er jeg efterhånden stødt ind i ordet algoritme mange steder, og jeg
> kunne godt tænke mig at vide mere om hvad det egentlig er. Jeg er helt
> nybegynder på det område, men har altså matematik i 2g. Hvis nogen kender
> nogle gode sider på nettet eller bøger hvor man kan finde oplysninger???
> Men altså ikke alt for indviklet.

En algoritme er en opskrift. Som regel bruges udtrykket i forbindelse
med computere og i så fald er algoritmen oftest formuleret i et program-
meringssprog, men der findes også mange "menneske-algoritmer". F.eks
kan den fremgangsmåde du benytter dig af, når du dividerer kaldes en
algoritme.

Et andet eksempel - Algoritme for ordbogsopslag:

1. Tag fat om alle siderne i bogen
2. Del de sider du holder om op i to dele og kig på den miderste side
3. Hvis det ord du leder efter kommer før den side du kigger på, så
tag fat om siderne til venstre og hop til punkt 2.
4. Hvis det ord du leder eftre kommer efter den side du kigger på,
så tag fat om siderne til højre og hop til punkt 2.
5. Ellers findes ordet på den side, du kigger på.

Jeg har kigget lidt på google og kan desværre ikke umiddelbart finde
nogen introduktion til algoritmer.

Hvis du har lyst til at læse en bog om emnet, vil jeg anbefale bogen
"Algorithmics" af David Harel. Den er beregnet for folk, der ikke kender
til programmering i forvejen, men den forklarer emnet godt. Du kan sikkert
bestille den hjem på dit lokale bibliotek (jeg tror, du får svært ved at
finde den i en boghandel).

-Claus

---

Claus Rasmussen wrote:
>
> Rikke Bendlin wrote:
>
> > Nu er jeg efterhånden stødt ind i ordet algoritme mange steder, og jeg
> > kunne godt tænke mig at vide mere om hvad det egentlig er. Jeg er helt
> > nybegynder på det område, men har altså matematik i 2g. Hvis nogen kender
> > nogle gode sider på nettet eller bøger hvor man kan finde oplysninger???
> > Men altså ikke alt for indviklet.
>
> En algoritme er en opskrift.

Lige netop, opskrift er et godt ord. Her er den additionsalgoritme man
lærer otteårige børn der skal kunne lægge naturlige tal sammen.

a. Stil tallene op under hinanden således at enere står under enere,
tiere under tiere, etc.
b. Start fra højre! Læg cifrene længst til højre sammen. Hvis resultatet
bliver under 10, skrives dette resultat blot under stregen, stadig
yderst til højre. Hvis tallet bliver 10 eller større, skrives det
sidste af cifrene i resultatet under stregen, mens det første ciffer
(der kaldes menten) skrives øverst over det øverste tals næstsidste
ciffer.
c. Nu lægges cifrene næstlængst til højre sammen, idet man husker at
regne en evt. mente fra før med. Resultatet skrives nederst (lige
til venstre for resultatet fra før), og hvis det er tocifret, opfatter
man det første ciffer som en mente der overføres til kolonnen lige
til venstre for den kolonne man nu regner i.
d. Man fortsætter med at arbejde sig mod venstre på denne måde.
e. Hvis cifrene i det ene af tallene slipper op, opfatter man det som
om der stod nuller foran (til venstre for) dette tal.
f. Når cifrene i begge tallene er sluppet op, og når der heller ikke er
flere menter, er man færdig. Facit står så at læse nederst.

Ordet algoritme stammer fra navnet på matematikeren Algorismus (der på
sit eget sprog hed al-Khwarizmi). Han angav nogle opskrifter på regning
med »arabertal« (altså ikke romertal), og dén jeg skitserede herover, var
sikkert én af dem.

Kort sagt, en algoritme er en fremgangsmåde eller »kogebogsopskrift«
på hvordan man løser problemer af en bestemt type.

Når man programmerer en computer, så er de instruktioner man skriver
til den, en algoritme. For dataloger er viden om algoritmer derfor
utrolig vigtig (måske er datalogi faktisk det samme som forskning i
algoritmer?).

Indimellem illustrerer man algoritmer med et »rutediagram«, det kender
Rikke måske?

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen wrote:
>
> Når man programmerer en computer, så er de instruktioner man skriver
> til den, en algoritme. For dataloger er viden om algoritmer derfor
> utrolig vigtig (måske er datalogi faktisk det samme som forskning i
> algoritmer?).

Ahr, det er vist at stramme den. Algoritmik er et stort delområde af
datalogien - men der findes andre grene, der dårligt kan karakteriseres
som "forskning i algoritmer", fx formel semantik. Men man kan sige at
langt de fleste discipliner i datalogi på en eller anden måde har noget
at gøre med algoritmer.
--
mvh. Karsten Strandgaard Jørgensen - http://www.hammerich.cjb.net
"I call upon our Staffordshire delegate to explain this weird behaviour"

---

En algoritme er en samling instruktioner der trin for trin beskriver hvilke
operationer, der skal udføres for at løse en opgave. Man anvender oftest
begrebet inden for matematik og datalogi, men fx en madopskrift er
principielt også en algoritme.
For eksempler på (mere avancerede) algoritmer og referencer til bøger på
engelsk om emnet kan du kigge på http://mathworld.wolfram.com/Algorithm.html
..

Anders

"Rikke Bendlin" <Rikke_Bendlin@mail.dk> skrev i en meddelelse
news:3cacc3ad$0$5281$edfadb0f@dspool01.news.tele.dk...
> Nu er jeg efterhånden stødt ind i ordet algoritme mange steder, og jeg
kunne
> godt tænke mig at vide mere om hvad det egentlig er. Jeg er helt
nybegynder
> på det område, men har altså matematik i 2g. Hvis nogen kender nogle gode
> sider på nettet eller bøger hvor man kan finde oplysninger??? Men altså
ikke
> alt for indviklet.
>
> - Rikke =)
>
>

---

Rikke Bendlin <Rikke_Bendlin@mail.dk> skrev:
> Nu er jeg efterhånden stødt ind i ordet algoritme mange steder, og jeg
> kunne
> godt tænke mig at vide mere om hvad det egentlig er. Jeg er helt
> nybegynder
> på det område, men har altså matematik i 2g. Hvis nogen kender nogle
> gode
> sider på nettet eller bøger hvor man kan finde oplysninger??? Men
> altså ikke
> alt for indviklet.
>
> - Rikke =)
>
> Ordet algoritme stammer fra arabisk og betyder slet og ret regneregler, når du støder på ordet algoritmer kan du bare oversætte det tildet danske ord regneregler. Når man stadig bruger det arabiske ord skyldes det nok,at mennesker som i åeevis har studeret fremmede sprog i mellemtiden tit har glemt hvad tingene hedder på dansk.
venlig hilsen Agner

---

Agner Høj Nielsen <agner@post8.tele.dk> writes:


> Ordet algoritme stammer fra arabisk og betyder slet og ret
> regneregler, når du støder på ordet algoritmer kan du bare oversætte
> det tildet danske ord regneregler. Når man stadig bruger det
> arabiske ord skyldes det nok,at mennesker som i åeevis har studeret
> fremmede sprog i mellemtiden tit har glemt hvad tingene hedder på
> dansk.

Vrøvl. "algoritme" kommer godt nok fra arabisk, men det er afledt af
navnet på en person, Abu Abd-Allah Muhammad ibn Musa al'Khwarizmi,
hvor "al'Khwarismi" hetyder til at han stammer fra Khwarizm. Du
tænker måke på "algebra", som kommer fra titlen på en af hans værker
"Hisab al-jabr w'al-muqabala". Den fjerde reference herunder siger at
"al-jabr" betyder "reduktion", så det er ikke præcis "regneregler".

Se f.eks.:

http://members.aol.com/bbyars1/algebra.html
http://users.erols.com/zenithco/khawariz.html
http://members.tripod.com/~wzzz/KHAWARIZ.html
http://prairial.free.fr/alkhwarizimi.html
http://www.superluminal.com/cookbook/gallery_alkhwarizmi_kitab.html

   Torben Mogensen (torbenm@diku.dk)

---

"Torben Ægidius Mogensen" wrote:
>
> tænker måke på "algebra", som kommer fra titlen på en af hans værker
> "Hisab al-jabr w'al-muqabala". Den fjerde reference herunder siger at
> "al-jabr" betyder "reduktion", så det er ikke præcis "regneregler".

Ja. Det optræder i hans bog »Hisab al-jabr w'al-muqabala« og er
navnet på én af de to operationer han brugte til at løse andengrads-
ligninger. MacTutor:

[...] the two operations of al-jabr and al-muqabala. Here "al-jabr"
means "completion" and is the process of removing negative terms
from an equation. For example, using one of al-Khwarizmi's own
examples, "al-jabr" transforms x2 = 40 x - 4 x2 into 5 x2 = 40 x.
The term "al-muqabala" means "balancing" and is the process of
reducing positive terms of the same power when they occur on both
sides of an equation. For example, two applications of "al-muqabala"
reduces 50 + 3 x + x2 = 29 + 10 x to 21 + x2 = 7 x (one application
to deal with the numbers and a second to deal with the roots).

Kilde:
http://www-history.mcs.st-andrews.ac.uk/history/Mathematicians/Al-Khwarizmi.html

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)