|
|
 | Hvor vigtig er matematik
Fra : Submind |
Dato : 22-01-01 19:59 |
|
Hej Jeg er en 16 årig gymnasie elev ( 1.g ) som har fået fortalt at
matematik er altafgørende i c++ programering og ville gerne vide om dette er
sandt, og hvor langt jeg kan nå på det niveau jeg er på nu ( rente
matematisk 9
| |
 Christian Worm Morte~ (22-01-2001)
| Kommentar
Fra : Christian Worm Morte~ |
Dato : 22-01-01 20:22 |
|
Hej,
> Hej Jeg er en 16 årig gymnasie elev ( 1.g ) som har fået fortalt at
> matematik er altafgørende i c++ programering og ville gerne vide om dette
er
> sandt, og hvor langt jeg kan nå på det niveau jeg er på nu ( rente
> matematisk 9
Du har lært alt den matematik du skal bruge for at komme langt med C++
programmering. Men hvis du lærer mere matematik og især matematisk tankegang
vil du kunne komme endnu længere..
Venlig Hilsen
Christian Worm
| |
Jonas Meyer Rasmusse~ (22-01-2001)
| Kommentar
Fra : Jonas Meyer Rasmusse~ |
Dato : 22-01-01 20:51 |
|
"Submind" <some45@worldonline.dk> wrote in message
news:Ik%a6.10390$l57.288284@news000.worldonline.dk...
> Hej Jeg er en 16 årig gymnasie elev ( 1.g ) som har fået fortalt at
> matematik er altafgørende i c++ programering og ville gerne vide om dette
er
> sandt, og hvor langt jeg kan nå på det niveau jeg er på nu ( rente
> matematisk 9
Det passer ikke.
Du kan nå en hel masse, næsten alt.
Når du skal igang med de mere teoretiske ting, så er matematisk indsigt en
fordel men ikke et krav.
men hvis du bare er igang med at starte med c++ så er det _lang_ vej indtil
at det punkt vil komme.
| |
Bertel Lund Hansen (22-01-2001)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 22-01-01 23:19 |
|
Jonas Meyer Rasmussen skrev:
>> Hej Jeg er en 16 årig gymnasie elev ( 1.g ) som har fået fortalt at
>> matematik er altafgørende i c++ programering
>Det passer ikke.
Jo det gør. Du forplumrer begreberne. Programmering er en
matematisk disciplin. At programmere er at lære matematik.
[Om 9. klasses niveau:]
>Du kan nå en hel masse, næsten alt.
Det er sådan lidt flot at slynge ud. Nogen vil aldrig lære det,
og andre skal kæmpe enormt for det som endnu andre lærer med
hænderne i lommerne. Men hvis viljen [1] er til stede, kan man da
nå et stykke vej.
>Når du skal igang med de mere teoretiske ting, så er matematisk indsigt en
>fordel men ikke et krav.
Jo, det er et krav. Mon ikke du mener at man ikke behøver
erhverve denne indsigt via et formelt kursus?
>men hvis du bare er igang med at starte med c++ så er det _lang_ vej indtil
>at det punkt vil komme.
Jeg tror vi er enige om at man da bare skal kaste sig ud i det
hvis man har lyst til at lære at programmere.
[1] "Vilje" betyder her at man gerne vil ofre blod sved og tårer
- samt tid!
--
Bertel http://lundhansen.dk/bertel/
FIDUSO: http://fiduso.dk/
| |
 Thomas Schulz (23-01-2001)
| Kommentar
Fra : Thomas Schulz |
Dato : 23-01-01 20:37 |
|
> Jo det gør. Du forplumrer begreberne. Programmering er en
> matematisk disciplin. At programmere er at lære matematik.
Når du siger det på den måde, vil jeg grave mig over i den anden grøft, og
postulere at programmering er en sproglig diciplin..
Thomas
| |
Bertel Lund Hansen (23-01-2001)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 23-01-01 21:44 |
|
Thomas Schulz skrev:
>Når du siger det på den måde, vil jeg grave mig over i den anden grøft, og
>postulere at programmering er en sproglig diciplin.
Alene det at der er så få sproglige studenter blandt programmører
burde gøre dig mistænksom over for din egen hypotese.
Kan vi enes om at logiske tests er helt centrale for
programmering - og matematik?
En designproces af en tekst- eller grafikskærm er en geometrisk
øvelse med en del talberegning og opmåling involveret. Det er
ikke just *typiske* sproglige emner.
Det er banalt at fremhæve den enorme mængde af rå talbehandling
der også hører til at programmere, både den del der danner
baggrunden for et korrekt program, og den del der skal kunne
udføres af programmet.
Sortering, tilfældige tal, søgning, ...
Listen over matematiske discipliner er uendelig.
--
Bertel http://lundhansen.dk/bertel/
FIDUSO: http://fiduso.dk/
| |
Christian Worm Morte~ (23-01-2001)
| Kommentar
Fra : Christian Worm Morte~ |
Dato : 23-01-01 21:50 |
|
Hej,
> Når du siger det på den måde, vil jeg grave mig over i den anden grøft, og
> postulere at programmering er en sproglig diciplin..
Er matematik så også en sprog diciplin?
Venlig Hilsen
Christian Worm
| |
Jens Axel Søgaard (24-01-2001)
| Kommentar
Fra : Jens Axel Søgaard |
Dato : 24-01-01 03:31 |
|
"Christian Worm Mortensen" <worm@dkik.dk> writes:
>> Når du siger det på den måde, vil jeg grave mig over i den anden
>> grøft, og postulere at programmering er en sproglig diciplin..
>
> Er matematik så også en sprog diciplin?
Ja - men srog er også en matematisk disciplin  Tænk bare på jeres
tyske grammatikbog. En stor samling af regler. Skriver man en sætning
gælder det om at analysere den, og være i stand til at følge bogens
regler for at kunne bøje verber med mere rigtigt. En grammatikbog er
altså bare en anden type program, end man er vant til.
En person, der er god til sprog, er bare en person, der har en god
intuitiv fornemmelse af reglerne.
Bemærk, at det er vist lykkedes mig i dette indlæg at være i begge
grøfter op én gang.
--
Jens Axel Søgaard -- http://www.jasoegaard.dk
A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös
| |
Rasmus Christian Kaa~ (24-01-2001)
| Kommentar
Fra : Rasmus Christian Kaa~ |
Dato : 24-01-01 08:24 |
|
> > Er matematik så også en sprog diciplin?
>
> Ja - men srog er også en matematisk disciplin Tænk bare på jeres
> tyske grammatikbog. En stor samling af regler. Skriver man en sætning
> gælder det om at analysere den, og være i stand til at følge bogens
> regler for at kunne bøje verber med mere rigtigt. En grammatikbog er
> altså bare en anden type program, end man er vant til.
[snip]
hvis du spurgte mig, så er du lagt ude.
det eneste jeg har fundet "sproglig" i min matematik uddannelse, er latinske
betegnelser for bogstaver.
-----
Rasmus Christian Kaae
www.daimi.au.dk/~kaae
| |
Christian Worm Morte~ (24-01-2001)
| Kommentar
Fra : Christian Worm Morte~ |
Dato : 24-01-01 13:14 |
|
Hej,
> hvis du spurgte mig, så er du lagt ude.
> det eneste jeg har fundet "sproglig" i min matematik uddannelse, er
latinske
> betegnelser for bogstaver.
For mig at se består matematik af to dele. Den ene del er at bevise og
definere ting meget formelt og præcist. Den anden del handler om at have en
intuitiv forståelse af hvad det er der sker. At have den intuitive
forståelse er ganske nødvendigt hvis man skal bruge matematikken til noget
fornuftigt eller hvis man skal udvikle ny matematik og ikke blot acceptere
at det andre har lavet ser rigtigt ud.
Derfor vil jeg heller ikke mene der er den store forskel mellem at udvikle
matematik og udvikle programmer. Begge dele består dels i nogle meget
formelt og dels af noget intuitivt der fortæller en hvilken overordnet
strategi man skal følge under sit arbejde.
Men jeg kan også godt acceptere at man kan mene at sprog er en matematisk
diciplin. For en del af sproget handler om at der er nogle præcise regler.
En anden del af sproget handler om at man skal have en intuitiv forståelse
for hvad det betyder.
Venlig Hilsen
Christian Worm
| |
Bertel Lund Hansen (24-01-2001)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 24-01-01 15:41 |
|
Christian Worm Mortensen skrev:
>For mig at se består matematik af to dele.
Hvor snævert.
>Den ene del er at bevise og definere ting meget formelt og præcist.
>Den anden del handler om at have en intuitiv forståelse af hvad det er der sker.
Mange mennesker forveksler åbenbart "matematik" med "matematik som det
forstås i universitetssammenhæng".
Når skolebørn tæller s'er eller deler en kage, så bruger de matematisk
tænkning til at løse nogle problemer.
>Men jeg kan også godt acceptere at man kan mene at sprog er en matematisk
>diciplin.
Det kan jeg ikke.
>For en del af sproget handler om at der er nogle præcise regler.
Nej. Sproget handler ikke om noget. Sproget er. Sproget kan bruges til
at beskrive noget.
Hvis man beskriver et maleri, bliver sproget ikke til maling.
Hvis man beskriver noget matematik, bliver sproget ikke til matematik.
Hvis man beskriver noget grammatik, bliver sproget ikke til grammatik
- og grammatik er ikke sprog.
XFut dk.kultur.sprog
--
Bertel http://lundhansen.dk/bertel/
FIDUSO: http://fiduso.dk/
| |
Bertel Lund Hansen (24-01-2001)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 24-01-01 08:09 |
|
Jens Axel Søgaard skrev:
>Ja - men srog er også en matematisk disciplin
Nej.
>Tænk bare på jeres tyske grammatikbog.
Javel. Tysk grammatik er en matematisk disciplin. Det er vi enige
om.
>En person, der er god til sprog, er bare en person, der har en god
>intuitiv fornemmelse af reglerne.
Nej. Hvis du følger reglerne, får du tysktalende til at holde sig
på maven af grin. Du er nødt til at kende et hav af undtagelser
og specielle forhold hvis du vil lyde normal.
Prøv at skrive et program der analyserer en vilkårlig sætning. Så
får du nok en fornemmelse af at sprog er et meget komplekst
fænomen.
Hvilken matematisk regel bruger du til at afgøre hvad følgende
betyder?
Han slog sig på flasken.
--
Bertel http://lundhansen.dk/bertel/
FIDUSO: http://fiduso.dk/
| |
Thorbjørn Ravn Ander~ (24-01-2001)
| Kommentar
Fra : Thorbjørn Ravn Ander~ |
Dato : 24-01-01 10:55 |
|
Bertel Lund Hansen wrote:
> Hvilken matematisk regel bruger du til at afgøre hvad følgende
> betyder?
>
> Han slog sig på flasken.
Blev nostalgisk.
I gamle dage kunne man spille Infocom adventurespil, hvor parseren var
imponerende avanceret. Der er ikke set meget siden der har slået det
(og så kunne det køre på stort set ingenting).
Man kunne på et tidspunkt hente Zork I+II+III fra Activision (som købte
Infocom), men det er gemt for godt til jeg kan hitte det. Et andet sted
er http://www.thediscworld.co.uk/zork.htm - gå kun efter de gamle Zork
spil.
--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear
| |
Soren 'Disky' Reinke (24-01-2001)
| Kommentar
Fra : Soren 'Disky' Reinke |
Dato : 24-01-01 11:46 |
|
"Thorbjørn Ravn Andersen" <thunderbear@bigfoot.com> wrote in message
news:3A6EA66D.C664DD83@bigfoot.com...
> Bertel Lund Hansen wrote:
>
> > Hvilken matematisk regel bruger du til at afgøre hvad følgende
> > betyder?
> >
> > Han slog sig på flasken.
>
> Blev nostalgisk.
>
> I gamle dage kunne man spille Infocom adventurespil, hvor parseren var
> imponerende avanceret. Der er ikke set meget siden der har slået det
> (og så kunne det køre på stort set ingenting).
>
> Man kunne på et tidspunkt hente Zork I+II+III fra Activision (som købte
> Infocom), men det er gemt for godt til jeg kan hitte det. Et andet sted
> er http://www.thediscworld.co.uk/zork.htm - gå kun efter de gamle Zork
Yep deres parser var bare for gennemført. Selv på en C64 kørte det godt.
Men MANGE MANGE tak for linken, jeg glæder mig allerede til at spille det
igen.
--
With many Thanks
Soren ' Disky ' Reinke ICQ #1413069 remove 'ihsyd' when email replying
Please visit my Freshwater Aquaria Webpage
http://www.disky-design.dk/fish
| |
Thorbjørn Ravn Ander~ (24-01-2001)
| Kommentar
Fra : Thorbjørn Ravn Ander~ |
Dato : 24-01-01 12:26 |
|
Soren 'Disky' Reinke wrote:
> Men MANGE MANGE tak for linken, jeg glæder mig allerede til at spille det
> igen.
Tjah, det krævede ikke meget andet end at skrive "zork download" til
Google, og benytte lidt kritisk sans.
Er man til Infocomspil, havde Activision en "Treasures of Infocom"-CD.
Alle undtagen Hitchhikers.
--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear
| |
Jens Axel Søgaard (24-01-2001)
| Kommentar
Fra : Jens Axel Søgaard |
Dato : 24-01-01 14:13 |
|
Bertel Lund Hansen <nospamto@lundhansen.dk> writes:
> Jens Axel Søgaard skrev:
>
> >Ja - men srog er også en matematisk disciplin
>
> Nej.
>
> >Tænk bare på jeres tyske grammatikbog.
>
> Javel. Tysk grammatik er en matematisk disciplin. Det er vi enige
> om.
- og grammatik er en del af sprog.
> >En person, der er god til sprog, er bare en person, der har en god
> >intuitiv fornemmelse af reglerne.
>
> Nej. Hvis du følger reglerne, får du tysktalende til at holde sig på
> maven af grin. Du er nødt til at kende et hav af undtagelser og
> specielle forhold hvis du vil lyde normal.
Jo - men jeg mente det heller ikke bogstaveligt. Med undtagelser og
specielle for er vel bare ekstra regler?
Jeg mener, at mange af de tankeprocesser, der benyttes i henholdsvis
matematik og sporg er sammenlignelige.
Et matematisk bevis skal for eksempel være krystalklart. Der må ikke
være plads til tvivl, når andre læser beviset. Det medfører, at en
matematiker altid dobbeltchecker om de (sproglige såvel som
matematiske) sætninger, han skriver kan misforstås/misfortolkes. Man
får udviklet en evne til med det samme at kunne se om, en sætning er
tvetydig. Det derfor en arbejdsskade hos martematikere (og mange
dataloger), når de går meget op i sprog (se bare på antallet af
dataloger i dk.kultur.sprog). Resumé: For at kunne beskrive matematik
nøjagtigt skal man i besiddelse af en god sprogsans.
Omvendt: En sprogmand går meget op i ordenes betydning og
anvendelse. Hvilket svarer til matematikeren, der samler sig et
"ordforråd" af anvendelige (matematiske) sætninger. En sprogmand
sætter ord sammen på nye måder og danner nye sætninger. Tilsvarende
leger en matematiker med de sætninger han kender, og sætter dem sammen
til nye.
Derudover er den gren af sprog, som beskæftiger sig med grammatik. Der
er mere struktur i for eksempel det danske sprog, end man umiddelbart
tror. Jeg tænker her på det berømte skema (som jeg selvfølgelig ikke
kan huske, hvad hedder <smiley>). Endelig er en matematiker god til at
fremlægge stof i en rækkefølge som hænger logisk sammen. En evne
(alle) har brug for, når de skal forklare komplicerede
emneområder. Resumé: Det er ingen skade til at have matematisk
forståelse, når man skal fremlægge noget.
> Prøv at skrive et program der analyserer en vilkårlig sætning. Så
> får du nok en fornemmelse af at sprog er et meget komplekst fænomen.
Jo - man kan altid finde en sætning, hvis betydning afhænger af
konteksten.
> Hvilken matematisk regel bruger du til at afgøre hvad følgende
> betyder?
>
> Han slog sig på flasken.
Glimrende eksempel. Her to engelse avisoverskrifter:
Disabled fly to se Carter
Wildcat strikes spread
NB: Hvis jeg vidste, hvordan man futtede, var dette indlæg røget over
i dk.kultur.sprog
--
Jens Axel Søgaard -- http://www.jasoegaard.dk
A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös
| |
Bertel Lund Hansen (24-01-2001)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 24-01-01 15:41 |
|
Jens Axel Søgaard skrev:
>Jo - men jeg mente det heller ikke bogstaveligt. Med undtagelser og
>specielle for er vel bare ekstra regler?
Jamen så er alt matematik for det kan beskrives med et sæt regler
suppleret med diverse undtagelser.
>Jeg mener, at mange af de tankeprocesser, der benyttes i henholdsvis
>matematik og sporg er sammenlignelige.
Jeg er helt uenig.
>Et matematisk bevis skal for eksempel være krystalklart.
Et fjernsyn skal også være krystalklart. Ergo er et fjernsyn også
sprog. Osv.
Kreativ tænkning er vigtig for både en matematiker og en sprogforsker.
Det gør ikke sprog til matematik eller matematik til sprog.
>Det derfor en arbejdsskade hos martematikere (og mange
>dataloger), når de går meget op i sprog (se bare på antallet af
>dataloger i dk.kultur.sprog).
Matematik kræver intelligens. Sprog kræver intelligens. På den
baggrund kan det næppe undre at der er et vist sammenfald mellem
matematisk og sproglig interesse. Det samme gælder i øvrigt musik
(bortset fra at det er ren matematik).
>Derudover er den gren af sprog, som beskæftiger sig med grammatik. Der
>er mere struktur i for eksempel det danske sprog, end man umiddelbart
>tror. Jeg tænker her på det berømte skema (som jeg selvfølgelig ikke
>kan huske, hvad hedder <smiley>).
Dyr kan også beskrives i et skema. Det gør ikke dyrene til matematik.
>Jo - man kan altid finde en sætning, hvis betydning afhænger af
>konteksten.
Må matematik gerne afhænge af konteksten?
>NB: Hvis jeg vidste, hvordan man futtede, var dette indlæg røget over
>i dk.kultur.sprog
Forklaring:
FUT = FollowUp-To:
Åbn de skjulte headers mens du redigerer et indlæg. Find den der
hedder FollowUp-To: og skriv den ønskede gruppe deri.
XFUT = krydspost samt FUT.
Gør som før, men skriv samtidig et komma og den nye gruppes navn i den
boks der hedder "Newsgroups" (el. lign.)
Ved begge metoder lander svarene kun i den nye gruppe.
XFut dk.kultur.sprog
--
Bertel http://lundhansen.dk/bertel/
| |
Ulrik Magnusson (24-01-2001)
| Kommentar
Fra : Ulrik Magnusson |
Dato : 24-01-01 10:32 |
|
> > Er matematik så også en sprog diciplin?
"Philosophy is written in this grand book of the universe, which stands
continually open to our gaze. But the
book cannot be understood unless one first learns to comprehend the
language and to read the alphabet in which it is
composed. It is written in the language of mathematics, and its
characters are triangles, circles and other geometric
figures, without which it is humanly impossible to understand a single
word of it; without these, one wanders in a
dark labyrinth. "
- Galileo Galilei "The Assayer", 1623.
Se også: http://www.math.montana.edu/~umsfwest/lm1.html
Ulrik Magnusson
| |
Sune (22-02-2001)
| Kommentar
Fra : Sune |
Dato : 22-02-01 09:30 |
|
Det er et fortolkningsspørgsmål om han virkelig mente sprog i sproglig
forstand.
Matematik er naturens "sprog", og det har sgu ette meget med menneskesprog
at gøre.
"Ulrik Magnusson" <ulrikm@yahoo.com> wrote in message
news:3A6F1C7E.38097FA5@yahoo.com...
> > > Er matematik så også en sprog diciplin?
>
> "Philosophy is written in this grand book of the universe, which stands
> continually open to our gaze. But the
> book cannot be understood unless one first learns to comprehend the
> language and to read the alphabet in which it is
> composed. It is written in the language of mathematics, and its
> characters are triangles, circles and other geometric
> figures, without which it is humanly impossible to understand a single
> word of it; without these, one wanders in a
> dark labyrinth. "
> - Galileo Galilei "The Assayer", 1623.
>
> Se også: http://www.math.montana.edu/~umsfwest/lm1.html
>
> Ulrik Magnusson
>
| |
Ulrik Magnusson (22-02-2001)
| Kommentar
Fra : Ulrik Magnusson |
Dato : 22-02-01 13:35 |
|
> Det er et fortolkningsspørgsmål om han virkelig mente sprog i sproglig
> forstand. Matematik er naturens "sprog", og det har sgu ette meget med
> menneskesprog
> at gøre.
Jeg vil ikke til at forklare min humor, men jeg synes bare
det var sjovt at fortolke "sprog" som ordet "sprog".
Ulrik Magnusson
--
"I'm a big tough man with a big tough plan
gonna spend my day in a big tough way"
Adam & the Ants - "5 Guns West", Prince Charming 1981
Visit my home page: http://www.geocities.com/ulrikm
| |
Rasmus Bøg Hansen (22-01-2001)
| Kommentar
Fra : Rasmus Bøg Hansen |
Dato : 22-01-01 21:02 |
|
On Mon, 22 Jan 2001, Submind wrote:
> Hej Jeg er en 16 årig gymnasie elev ( 1.g ) som har fået fortalt at
> matematik er altafgørende i c++ programering og ville gerne vide om dette er
> sandt, og hvor langt jeg kan nå på det niveau jeg er på nu ( rente
> matematisk 9
Det mener jeg ikke, man kan give et entydigt svar på. Det kommer an på
hvilke typer programmer, du har tænkt dig at udvikle.
Skal du lave beregnings-, grafik-, lyd- og videoprogrammer, er det en
klar fordel; somme tider en nødvendighed.
Sigter du derimod mere mod programmer, der manipulerer strukturelle data
såsom tekst, databaser o.l. er det mindre væsentligt.
Lidt logisk sans er dog aldrig helt af vejen.
Rasmus Bøg Hansen
| |
Peter Jespersen (22-01-2001)
| Kommentar
Fra : Peter Jespersen |
Dato : 22-01-01 23:48 |
|
On Mon, 22 Jan 2001 19:59:03 +0100, Submind wrote:
>Hej Jeg er en 16 årig gymnasie elev ( 1.g ) som har fået fortalt at
>matematik er altafgørende i c++ programering og ville gerne vide om dette er
>sandt, og hvor langt jeg kan nå på det niveau jeg er på nu ( rente
>matematisk 9
Man kan nå meget langt med lidt indsigt i diskret matematik
(Logik, relations og Mængdelære er her hovedbestanddelen).....
Der er selvfølgelig områder som 3D-fuskeri der kræver noget lidt
langhåret...
Det vigtiste er at man har en nogenlunde matematisk (logisk)
sans, når man begynder....
Det sværeste er dog ofte at holde sig til ilden, især da
nutidens oversættere ikke altid over de samme logiske love som
resten af verden...men det kommer med erfaringen....
Live long and prosper...
_________________________________________________________________
Peter Jespersen, Team OS/2 Denmark
flywheel@worldonline.dk
http://www.worldonline.dk/~flywheel/
You can tell a real programmer by the keyboard dents in his forehead.
| |
Rasmus Christian Kaa~ (23-01-2001)
| Kommentar
Fra : Rasmus Christian Kaa~ |
Dato : 23-01-01 07:55 |
|
"Submind" <some45@worldonline.dk> skrev i en meddelelse
news:Ik%a6.10390$l57.288284@news000.worldonline.dk...
> Hej Jeg er en 16 årig gymnasie elev ( 1.g ) som har fået fortalt at
> matematik er altafgørende i c++ programering og ville gerne vide om dette
er
> sandt, og hvor langt jeg kan nå på det niveau jeg er på nu ( rente
> matematisk 9
matematik er ikke vigtigt for at kunne programmere. men hvis du ønsker at
kunne sætte dig ind i en given algoritme så er matematisk-tankegang ofte en
forudsætning. selv havde jeg matematik på a-niveau og følger
matematik-kurser på universitetet.
-----
Rasmus Christian Kaae
www.daimi.au.dk/~kaae
| |
Michael Nielsen (23-01-2001)
| Kommentar
Fra : Michael Nielsen |
Dato : 23-01-01 11:54 |
|
Rasmus Christian Kaae wrote:
>
> "Submind" <some45@worldonline.dk> skrev i en meddelelse
> news:Ik%a6.10390$l57.288284@news000.worldonline.dk...
> > Hej Jeg er en 16 årig gymnasie elev ( 1.g ) som har fået fortalt at
> > matematik er altafgørende i c++ programering og ville gerne vide om dette
> er
> > sandt, og hvor langt jeg kan nå på det niveau jeg er på nu ( rente
> > matematisk 9
>
> matematik er ikke vigtigt for at kunne programmere. men hvis du ønsker at
> kunne sætte dig ind i en given algoritme så er matematisk-tankegang ofte en
> forudsætning. selv havde jeg matematik på a-niveau og følger
> matematik-kurser på universitetet.
Helt rigtig!
For at kunne blive en "god" programmør kræver det en større indsigt
ind i matematik, feks, når det kommer til at forstå hvorfor nogen kode
former er mere effektive end andre. For at kunne arbjede med
forskellige
standarder, bliver matematikken pludsligt meget vigtig, feks G.729 som
benyttes til "Voice over IP".
Der er meget matematik i programmering man kan fuske sig til. Skal
man være god til at skrive effektiv kode, skal man kunne forstå og bruge
principperne i Matematik. Dog er maskinerne så hurtige nu om dage at
man ikke har så meget behov for at beregne "cost of execution", og
derfor kan store mængder af "dårlig kode" begå sig i verden, dette er
også derfor at den største del af kommerciel programmering nu om dage
er hvad jeg kalder for "dårlig kode" (læs ineffektiv kode), spilder
mange program cycler som kunne spares ved en meget lille optimering.
Man behøver ikke at være en Matematik specialist, hvis man ikke arbjeder
med
matematiske programmer, krypterings algorithmer, o.lign.
Vil man bare arbjede med GUI'er, eller lave simple webmastering, så er
matematikken af meget lav værdi. Skal man analysere og behandle
data, især større mængder kan matematikken være dig en hjælp.
så det korte svar er, matematik kan være meget vigtig!.
mvh
mike.
--
#include <stddisclaimer.h>
-----------------------------------------------------------------------
(Ingeniør) Michael Nielsen BE(Hons)
ICQ: 53913906 telf: +45 9828
3431
Private email : mike@anarki.dk Company Email : mni@lasat.com
-----------------------------------------------------------------------
At arbejede er godt, så længe man husker at leve!
(To work is good as long as we remember to live!)
| |
Thorbjørn Ravn Ander~ (23-01-2001)
| Kommentar
Fra : Thorbjørn Ravn Ander~ |
Dato : 23-01-01 12:18 |
|
Michael Nielsen wrote:
> Der er meget matematik i programmering man kan fuske sig til. Skal
> man være god til at skrive effektiv kode, skal man kunne forstå og bruge
> principperne i Matematik. Dog er maskinerne så hurtige nu om dage at
> man ikke har så meget behov for at beregne "cost of execution", og
> derfor kan store mængder af "dårlig kode" begå sig i verden, dette er
> også derfor at den største del af kommerciel programmering nu om dage
> er hvad jeg kalder for "dårlig kode" (læs ineffektiv kode), spilder
> mange program cycler som kunne spares ved en meget lille optimering.
Det er rigtigt at computere er hurtige i dag, men det ændrer ikke på at
det er vigtigt at vide hvordan algoritmens køretid skalerer, eller sagt
på en anden måde, hvorfor quicksort/mergesort er bedre end bubblesort
som igen er bedre end "kast kortene op i luften og saml dem sammen.
Gentag indtil de er i rækkefølge".
Mange af de ting kan man sagtens få fortalt, men for at forstå hvorfor
er det rart at kunne matematik.
--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear
| |
Soren 'Disky' Reinke (23-01-2001)
| Kommentar
Fra : Soren 'Disky' Reinke |
Dato : 23-01-01 12:28 |
|
"> det er vigtigt at vide hvordan algoritmens køretid skalerer, eller sagt
> på en anden måde, hvorfor quicksort/mergesort er bedre end bubblesort
> som igen er bedre end "kast kortene op i luften og saml dem sammen.
> Gentag indtil de er i rækkefølge".
Ja og så kan man også forstå hvor quicksort i værste tilfælde (hvis data er
sorteret i omvendt rækkefølge) er ligeså langsom som bubble sort, nemlig
O(n^2)
Den sidste sorterings algoritme lyder spændende hvad er O(x) ??
--
With many Thanks
Soren ' Disky ' Reinke ICQ #1413069 remove 'ihsyd' when email replying
Please visit my Freshwater Aquaria Webpage
http://www.disky-design.dk/fish
| |
Thorbjørn Ravn Ander~ (23-01-2001)
| Kommentar
Fra : Thorbjørn Ravn Ander~ |
Dato : 23-01-01 12:52 |
|
Soren 'Disky' Reinke wrote:
>
> "> det er vigtigt at vide hvordan algoritmens køretid skalerer, eller sagt
> > på en anden måde, hvorfor quicksort/mergesort er bedre end bubblesort
> > som igen er bedre end "kast kortene op i luften og saml dem sammen.
> > Gentag indtil de er i rækkefølge".
>
> Ja og så kan man også forstå hvor quicksort i værste tilfælde (hvis data er
> sorteret i omvendt rækkefølge) er ligeså langsom som bubble sort, nemlig
> O(n^2)
>
> Den sidste sorterings algoritme lyder spændende hvad er O(x) ??
Det må en mere vidende person end mig udtale sig om.
Chancen for at få den rigtig er 1/(n!) pr gang, hvor n=52 for et spil
kort. Det er ikke ret møj. 52! er 8.06581751709439e+067.
Er der en med et program som kan regne med meget, meget stor præcision
som gider løse 0.5 = (1-1/(52!))^n for n?
--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear
| |
Jens Kristian Søgaar~ (24-01-2001)
| Kommentar
Fra : Jens Kristian Søgaar~ |
Dato : 24-01-01 00:11 |
|
Thorbjørn Ravn Andersen <thunderbear@bigfoot.com> writes:
> Er der en med et program som kan regne med meget, meget stor præcision
> som gider løse 0.5 = (1-1/(52!))^n for n?
Hvis vi nu regner med et "lille" spil kort, kan mit program godt finde
ud af det. Det giver dog helt op, når vi når over 40 kort.
Ved 40 kort, er n = 5.65549E47. En del.
--
Jens Kristian Søgaard,
jk@soegaard.net -- http://www.jksoegaard.dk/
Søger du noget? -- http://www.google.com/
echo|perl -ple'$_+=4E-6*!int rand()**2+rand()**2while$i++-1E6'
| |
Soeren Sandmann (23-01-2001)
| Kommentar
Fra : Soeren Sandmann |
Dato : 23-01-01 13:05 |
|
"Soren 'Disky' Reinke" <disky@disky-design.ihsyd.dk> writes:
> Ja og så kan man også forstå hvor quicksort i værste tilfælde (hvis data er
> sorteret i omvendt rækkefølge) er ligeså langsom som bubble sort, nemlig
> O(n^2)
Hvis data er sorteret i omvendt rækkefølge og man altid vælger det
midterste element at dele efter, får man ganske rigtigt O(n^2)
udførelsestid fra quicksort, men hvis man vælger deleelementet
tilfældigt, har quicksort forventet udførelsestid O(n log n) uanset
input.
| |
Soeren Sandmann (23-01-2001)
| Kommentar
Fra : Soeren Sandmann |
Dato : 23-01-01 13:09 |
|
Soeren Sandmann <sandmann@daimi.au.dk> writes:
> Hvis data er sorteret i omvendt rækkefølge og man altid vælger det
> midterste element at dele efter, får man ganske rigtigt O(n^2)
^^^^^^^^^
Nej, hvis man altid vælger det *første* (eller sidste) element.
| |
Thorbjørn Ravn Ander~ (23-01-2001)
| Kommentar
Fra : Thorbjørn Ravn Ander~ |
Dato : 23-01-01 14:21 |
|
Soeren Sandmann wrote:
> Hvis data er sorteret i omvendt rækkefølge og man altid vælger det
> midterste element at dele efter, får man ganske rigtigt O(n^2)
> udførelsestid fra quicksort, men hvis man vælger deleelementet
> tilfældigt, har quicksort forventet udførelsestid O(n log n) uanset
> input.
Derfor er mergesort tit mere interessant.
--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear
| |
Regnar Bang Lyngso (23-01-2001)
| Kommentar
Fra : Regnar Bang Lyngso |
Dato : 23-01-01 15:50 |
|
In article <3A6D854B.493439E@bigfoot.com>, Thorbjørn Ravn Andersen <thunderbear@bigfoot.com> writes:
>> Hvis data er sorteret i omvendt rækkefølge og man altid vælger
>> det midterste element at dele efter, får man ganske rigtigt
>> O(n^2) udførelsestid fra quicksort, men hvis man vælger
>> deleelementet tilfældigt, har quicksort forventet udførelsestid
>> O(n log n) uanset input.
TRA> Derfor er mergesort tit mere interessant.
Vel kun, hvis man har strenge tidskrav (og her mener jeg at man ønsker
at kunne forudse en maksimal køretid i fx et realtidssystem)?
Så vidt jeg husker har mergesort et større pladsforbrug (alt afhængig
af datastruktur) og typisk en større konstant, hvorfor quicksort
generelt giver en hurtigere eksekvering.
(jeg vil ikke afvise at jeg husker forkert)
Knus
Regnar
| |
Igor V. Rafienko (23-01-2001)
| Kommentar
Fra : Igor V. Rafienko |
Dato : 23-01-01 13:34 |
|
* Soren Reinke
[snip]
> Ja og så kan man også forstå hvor quicksort i værste tilfælde (hvis
> data er sorteret i omvendt rækkefølge) er ligeså langsom som bubble
> sort, nemlig O(n^2)
Det må da være en _særs_ dårlig partisjoneringsstrategi (la meg
gjette, boken til Cormen, Leiserson og Rivest?): en plain-vanilla
media-of-3 vil gjøre det _langt_ bedre på sorterte vektorer. Men dette
er vel off-topic...
Og apropos viktighet av matematikk (som UiO ikke ser til å sette en
stor pris på):
[quote]
Unfortunately, the computer science departments in many universities
apparently believe that fluency in C++ is more important than a sound
education in elementary mathematics.
-Leslie Lamport, Specifying Concurrent Systems with TLA+
[/quote]
ivr
--
Much of this software was user-friendly, meaning that it was intended
for users who did not know anything about computers, and furthermore
had absolutely no intention whatsoever of learning.
-- A. S. Tanenbaum, "Modern Operating Systems, ch 1.2.4"
| |
Thomas Jespersen (23-01-2001)
| Kommentar
Fra : Thomas Jespersen |
Dato : 23-01-01 18:32 |
|
"Soren 'Disky' Reinke" <disky@disky-design.ihsyd.dk> writes:
>
> Den sidste sorterings algoritme lyder spændende hvad er O(x) ??
Hvis man altid rammer rigtig er den O(1) :)
Den variant vil jeg vælge at kalde "Lucky Sort"
| |
Christian Worm Morte~ (23-01-2001)
| Kommentar
Fra : Christian Worm Morte~ |
Dato : 23-01-01 19:52 |
|
Hej,
> > Den sidste sorterings algoritme lyder spændende hvad er O(x) ??
>
> Hvis man altid rammer rigtig er den O(1) :)
Nej - både at kaste og tjekke om de nu har den rigtige orden tager O(n) tid.
Venlig Hilsen
Christian Worm
| |
Adam Sjøgren (23-01-2001)
| Kommentar
Fra : Adam Sjøgren |
Dato : 23-01-01 19:55 |
|
On Tue, 23 Jan 2001 18:51:44 GMT, Christian Worm Mortensen wrote:
>> Hvis man altid rammer rigtig er den O(1) :)
> Nej - både at kaste
Man kaster alle kort op i luften på en gang - man kaster dem ikke et
af gangen!
> og tjekke om de nu har den rigtige orden tager O(n) tid.
Men hvis man altid rammer rigtigt (hvilket var forudsætningen) er der
ingen grund til at checke noget.
,
--
"I wanna get with you - only you, girl Adam Sjøgren
And you sister, I think her name is Debra" asjo@koldfront.dk
| |
Christian Worm Morte~ (23-01-2001)
| Kommentar
Fra : Christian Worm Morte~ |
Dato : 23-01-01 20:19 |
|
Hej,
> >> Hvis man altid rammer rigtig er den O(1) :)
>
> > Nej - både at kaste
>
> Man kaster alle kort op i luften på en gang - man kaster dem ikke et
> af gangen!
Har du et C++ program jeg må se der kan det?  Det må vel være det mindste
man kan forlange givet gruppens navn og det oprindelige spørgsmål som tråden
udsprang fra.
> > og tjekke om de nu har den rigtige orden tager O(n) tid.
>
> Men hvis man altid rammer rigtigt (hvilket var forudsætningen) er der
> ingen grund til at checke noget.
Hmm.. Hmm... Jeg vil give mig så langt som at du med en simpel ændring af
den oprindelige algoritme vil kunne undgå dette tjek. Men så er der jo tale
om en helt 3. algoritme.
Venlig Hilsen
Christian Worm
| |
Lars Dam (24-01-2001)
| Kommentar
Fra : Lars Dam |
Dato : 24-01-01 10:45 |
|
On 23 Jan 2001 19:55:12 +0100, asjo@koldfront.dk (Adam Sjøgren) wrote:
>On Tue, 23 Jan 2001 18:51:44 GMT, Christian Worm Mortensen wrote:
>
>>> Hvis man altid rammer rigtig er den O(1) :)
>
>> Nej - både at kaste
>
>Man kaster alle kort op i luften på en gang - man kaster dem ikke et
>af gangen!
>
>> og tjekke om de nu har den rigtige orden tager O(n) tid.
Det med at checke er nok en af årsagerne til at matematik kan være
vigtigt i programmering - hvis man matematisk kan bevise at eens
algoritme fungerer, behøver man ikke lave kontrol check.
Hvis man f.eks. laver software til flyvemaskiner og rumraketter, så
tror jeg at man i mange tilfælde vil forlange matematiske beviser for
de algoritmer man nu vælger at bruge.
Det vil nu nok ikke være den store nødvendighed, i kontor
applikationer at bevise at de virker (bare tænk på microsoft
produkter).
Så i det store hele, så er matematik nødvendig alt efter den type
programmer man ønsker at lave.
Dog vil jeg nu personligt mene at det skader ikke at blice lidt
klogere på matematik.
vh. ld
--
"Time is the fire in which we burn"
| |
Adam Sjøgren (24-01-2001)
| Kommentar
Fra : Adam Sjøgren |
Dato : 24-01-01 16:09 |
|
On Wed, 24 Jan 2001 10:44:35 +0100, Lars Dam wrote:
> Det vil nu nok ikke være den store nødvendighed, i kontor
> applikationer at bevise at de virker
Det er umuligt at bevise korrekthed for programmer der er større en
tobak for en skilling. Spørg bare nogle der har prøvet...
,
--
"kalasbyxor, ettagluttare, blängsylta, lånbytas Adam Sjøgren
sockiplast, tjejlöss, killbaciller, gosedjur..." asjo@koldfront.dk
| |
Thorbjørn Ravn Ander~ (24-01-2001)
| Kommentar
Fra : Thorbjørn Ravn Ander~ |
Dato : 24-01-01 16:28 |
|
"Adam Sjøgren" wrote:
>
> On Wed, 24 Jan 2001 10:44:35 +0100, Lars Dam wrote:
>
> > Det vil nu nok ikke være den store nødvendighed, i kontor
> > applikationer at bevise at de virker
>
> Det er umuligt at bevise korrekthed for programmer der er større en
> tobak for en skilling. Spørg bare nogle der har prøvet...
Ikke med mindre du bruger nogen ordentlige værktøjer.
Efter sigende er det hvad det her går ud på. Skriv dine beviser og
kompilér det til kode.
http://www.ifad.dk/Products/vdmtools.htm
--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear
| |
Per Abrahamsen (25-01-2001)
| Kommentar
Fra : Per Abrahamsen |
Dato : 25-01-01 17:16 |
|
Thorbjørn Ravn Andersen <thunderbear@bigfoot.com> writes:
> Efter sigende er det hvad det her går ud på. Skriv dine beviser og
> kompilér det til kode.
Det virkelige problem er at der oftest er flere fejl i
specifikationerne, end i implementeringerne.
| |
Thomas Jespersen (23-01-2001)
| Kommentar
Fra : Thomas Jespersen |
Dato : 23-01-01 21:02 |
|
"Christian Worm Mortensen" <worm@dkik.dk> writes:
> Hej,
>
> > > Den sidste sorterings algoritme lyder spændende hvad er O(x) ??
> >
> > Hvis man altid rammer rigtig er den O(1) :)
>
> Nej - både at kaste og tjekke om de nu har den rigtige orden tager O(n) tid.
Ja, det kom jeg også i tanke om. Men hvis forudsætningen er held,
behøver man ikke "kaste kortene i vejret" :) (og det var det jeg
mente)
| |
Bertel Lund Hansen (23-01-2001)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 23-01-01 21:32 |
|
Soren 'Disky' Reinke skrev:
>Ja og så kan man også forstå hvor quicksort i værste tilfælde (hvis data er
>sorteret i omvendt rækkefølge) er ligeså langsom som bubble sort, nemlig
>O(n^2)
Det forstår jeg ikke. Jeg har i mit demoprogram lige kørt en test
hvor jeg præsorterede med faldende værdi. Det får QS til at køre
lidt hurtigere end ved tilfældig rækkefølge.
Men Igor har vist givet forklaringen.
--
Bertel http://lundhansen.dk/bertel/
FIDUSO: http://fiduso.dk/
| |
Thorbjørn Ravn Ander~ (24-01-2001)
| Kommentar
Fra : Thorbjørn Ravn Ander~ |
Dato : 24-01-01 10:59 |
|
Bertel Lund Hansen wrote:
>
> Soren 'Disky' Reinke skrev:
>
> >Ja og så kan man også forstå hvor quicksort i værste tilfælde (hvis data er
> >sorteret i omvendt rækkefølge) er ligeså langsom som bubble sort, nemlig
> >O(n^2)
>
> Det forstår jeg ikke. Jeg har i mit demoprogram lige kørt en test
> hvor jeg præsorterede med faldende værdi. Det får QS til at køre
> lidt hurtigere end ved tilfældig rækkefølge.
Det kritiske punkt med quicksort, er hvordan du vælger dit
sorteringspunkt.
Må vi se kildeteksten til den quicksort du bruger?
--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear
| |
Bertel Lund Hansen (24-01-2001)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 24-01-01 15:41 |
|
Thorbjørn Ravn Andersen skrev:
>Det kritiske punkt med quicksort, er hvordan du vælger dit
>sorteringspunkt.
>Må vi se kildeteksten til den quicksort du bruger?
Ja da. Jeg har ikke patent på QS, og derudover deler jeg gerne ud af
min viden. Denne her rutine er en anelse mere kompliceret end
nødvendigt fordi jeg arbejder direkte på en tekstskærm som både har en
tegnbyte og en attributbyte:
Procedure quick_sort (left,right: Word);
Var l, r : Word;
Begin
l:=left; r:=right; adr:=l+r; If adr Mod 2=1 Then Inc(adr);
pivot:=Mem[screen_start:adr];
Repeat
While Mem[screen_start:l*2]<pivot Do Inc(l);
While pivot<Mem[screen_start:r*2] Do Dec(r);
If l<=r Then Begin
temp:=Mem[screen_start:r*2];
Mem[screen_start:r*2]:=Mem[screen_start:l*2];
Mem[screen_start:l*2]:=temp;
Inc(l); Dec(r);
End;
Until l>r;
If left<r Then quick_sort(left,r);
If l<right Then quick_sort(l,right);
End;
--
Bertel http://lundhansen.dk/bertel/
FIDUSO: http://fiduso.dk/
| |
Thorbjørn Ravn Ander~ (24-01-2001)
| Kommentar
Fra : Thorbjørn Ravn Ander~ |
Dato : 24-01-01 16:03 |
|
Bertel Lund Hansen wrote:
> >Det kritiske punkt med quicksort, er hvordan du vælger dit
> >sorteringspunkt.
>
> >Må vi se kildeteksten til den quicksort du bruger?
>
> Ja da. Jeg har ikke patent på QS, og derudover deler jeg gerne ud af
> min viden. Denne her rutine er en anelse mere kompliceret end
> nødvendigt fordi jeg arbejder direkte på en tekstskærm som både har en
> tegnbyte og en attributbyte:
Det går nok.
Det der gør quicksort kritisk er lige præcis den her:
> pivot:=Mem[screen_start:adr];
som gør at din rutine bliver n^2 hvis værdien er lige præcis sådan at
den delsekvens som bliver puttet på stakken til senere sortering er lig
med alle de andre elementer der skal sorteres.
Dette er sædvanligvis enten en stigende sekvens eller en faldende
sekvens. Her _tror_ jeg det er en stigende, da du foretager
venstresiderekursionen først.
Den normale kur er at tage den miderste af tre værdier i stedet for bare
ukritisk den første. Her er første, sidste og midterste element de
traditionelle.
Bemærk iøvrigt at for små størrelser af n, er forskellen mellem n^2 og n
log n ikke så drastisk som den er når vi snakker fx n=100000.
--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear
| |
Soeren Sandmann (24-01-2001)
| Kommentar
Fra : Soeren Sandmann |
Dato : 24-01-01 16:15 |
|
Bertel Lund Hansen <nospamto@lundhansen.dk> writes:
> Procedure quick_sort (left,right: Word);
> Var l, r : Word;
> Begin
> l:=left; r:=right; adr:=l+r; If adr Mod 2=1 Then Inc(adr);
> pivot:=Mem[screen_start:adr];
Hvis du skifter denne linje ud med
pivot := Mem[screen_start:l];
og kører proceduren på en sorteret skærm, vil
> Repeat
> While Mem[screen_start:l*2]<pivot Do Inc(l);
denne linje aldrig blive udført, så l vil ikke ændre sig, og
> While pivot<Mem[screen_start:r*2] Do Dec(r);
denne linje vil blive udført O(n) gange. Herefter har
> If l<=r Then Begin
> temp:=Mem[screen_start:r*2];
> Mem[screen_start:r*2]:=Mem[screen_start:l*2];
> Mem[screen_start:l*2]:=temp;
> Inc(l); Dec(r);
> End;
ikke anden effekt end at tælle l én op, og r én ned, således at
> Until l>r;
bliver sand.
> If left<r Then quick_sort(left,r);
Denne linje bliver ikke udført.
> If l<right Then quick_sort(l,right);
Og så kaldes quicksort igen på en skærm som er én kortere. Der bliver
alt i alt udført ca.
n + (n-1) + ... + 1 = n(n+1)/2 = O(n^2)
operationer, hvor en ikke-degenereret quicksort udfører
T(n) = 2*T(n/2) + O(n)
operationer, fordi de to rekursive kald opererer på input af halv
størrelse. Hvis man forestiller sig rekursionstræet, ser man at det
giver anledning til summen
n + 2*n/2 + 4*n/4 + 8*n/8 + ...
Der er O(log_2(n)) led i summen, for man kan ikke halvere et datalogisk
tal mere end log_2(n) gange, så algoritmen udfører O(n log(n))
operationer.
Og så kan diskussionen vist ikke længere forsvares i en gruppe om
C-programmering, så
FUT: dk.edb.programmering.
| |
Rasmus Christian Kaa~ (24-01-2001)
| Kommentar
Fra : Rasmus Christian Kaa~ |
Dato : 24-01-01 16:30 |
|
> >Det kritiske punkt med quicksort, er hvordan du vælger dit
> >sorteringspunkt.
>
> >Må vi se kildeteksten til den quicksort du bruger?
>
> Ja da. Jeg har ikke patent på QS, og derudover deler jeg gerne ud af
> min viden. Denne her rutine er en anelse mere kompliceret end
> nødvendigt fordi jeg arbejder direkte på en tekstskærm som både har en
> tegnbyte og en attributbyte:
>
[noget grimt]
nu hvor dette er en C-gruppe, ser du det så ikke som OFF-TOPIC at poste
pascal kode her?
-----
Rasmus Christian Kaae
www.daimi.au.dk/~kaae
| |
Jens Axel Søgaard (24-01-2001)
| Kommentar
Fra : Jens Axel Søgaard |
Dato : 24-01-01 16:39 |
|
"Rasmus Christian Kaae" <rasmus@skallebank.com> writes:
> > >Det kritiske punkt med quicksort, er hvordan du vælger dit
> > >sorteringspunkt.
> >
> > >Må vi se kildeteksten til den quicksort du bruger?
> >
> > Ja da. Jeg har ikke patent på QS, og derudover deler jeg gerne ud af
> > min viden. Denne her rutine er en anelse mere kompliceret end
> > nødvendigt fordi jeg arbejder direkte på en tekstskærm som både har en
> > tegnbyte og en attributbyte:
> >
> [noget grimt]
> nu hvor dette er en C-gruppe, ser du det så ikke som OFF-TOPIC at poste
> pascal kode her?
Troll.
--
Jens Axel Søgaard -- http://www.jasoegaard.dk
A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös
| |
N/A (24-01-2001)
| Kommentar
Fra : N/A |
Dato : 24-01-01 17:38 |
|
| |
Thorbjørn Ravn Ander~ (24-01-2001)
| Kommentar
Fra : Thorbjørn Ravn Ander~ |
Dato : 24-01-01 17:38 |
|
Bertel Lund Hansen wrote:
> PS. Det var ikke Pascalkode. Med den rette brug af #define kan
> det kompileres som den smukkeste C-kode. Den del havde jeg bare
> klippet væk.
Tillad mig kraftigt at antyde at dét er en uvane.
En ting er diverse værktøjer som formoder at man egentlig programmerer i
C, og ikke i Pascal, kan blive særdeles forvirrede (og det er ret
trættende).
En anden, og meget værre, er at menneskelige læsere bliver forvirrede.
Du gør ikke den der kommer efter dig en tjeneste ved at lave kode på den
måde.
Det er selvfølgelig en sjov øvelse at få cpp til at spise et
Pascalprogram, men ikke når det bliver alvor.
--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear
| |
Bertel Lund Hansen (24-01-2001)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 24-01-01 23:47 |
|
Thorbjørn Ravn Andersen skrev:
>> PS. Det var ikke Pascalkode. Med den rette brug af #define ...
>Tillad mig kraftigt at antyde at dét er en uvane.
Det var en ren joke. Indlægget lå højst 10 sekunder inden jeg
slettede det fordi det skulle være sendt i mail, og jeg er helt
enig med dig. Jeg skriver så ren kode som muligt.
--
Bertel http://lundhansen.dk/bertel/
FIDUSO: http://fiduso.dk/
| |
Asger K. Alstrup Nie~ (13-02-2001)
| Kommentar
Fra : Asger K. Alstrup Nie~ |
Dato : 13-02-01 00:13 |
|
=?iso-8859-1?Q?Thorbj=F8rn?= Ravn Andersen <thunderbear@bigfoot.com> writes:
>Det kritiske punkt med quicksort, er hvordan du vælger dit
>sorteringspunkt.
Nemlig.
I den forbindelse er det interessant at vide at problemet er løst:
Man kender nu den optimale strategi for at vælge pivot'en:
"Optimal Sampling Strategies in Quicksort and Quickselect"
af Conrado Martinex, Salvador Roura.
Du kan læse den på
http://citeseer.nj.nec.com/martinez98optimal.html
Det kræver en god portion matematisk viden at forstå den artikel.
Der er udviklet algoritmer til sortering i O(n log log n) af Mikkel
Thorup...
http://citeseer.nj.nec.com/thorup96ram.html
....hvilket er et *kolosalt* gennembrud i den teoretiske datalogi[1],
men desværre er hastighedsgevinsten i virkeligheden stadigt tvivlsom,
fordi moderne processorers caches ikke egner sig til den form
for hukommelsestilgang, der optræder i algoritmen, og desuden er
ord-størrelsen i nutidens processorer for lille til at den ord-parallelisme
der udnyttes i algoritmen, rigtigt batter.
Se "An experimental study of word-level parallelism in some sorting
algorithms"
http://citeseer.nj.nec.com/rahman98experimental.html
for mere information om sortering i dag og i fremtiden.
Konklusionen er at i øjeblikket er der stadigt intet der slår gode gamle
Quicksort som generel sorteringsalgoritme, men selvom den har fået endnu
en håndsrækning med førstnævnte optimale løsning af pivot-problemet må
vi nok indse at dens dage som Kongen af sortering trods alt er talte.
Mvh
Asger Alstrup
[1] Se også M. Thorup "Faster deterministic sorting and priority
queues in linear space", Proceedings of the Ninth Annual ACMSIAM
symposium on Discrete Algorithms, pages 550-555, 1998.
| |
Thorbjørn Ravn Ander~ (13-02-2001)
| Kommentar
Fra : Thorbjørn Ravn Ander~ |
Dato : 13-02-01 10:05 |
|
"Asger K. Alstrup Nielsen" wrote:
> I den forbindelse er det interessant at vide at problemet er løst:
> Man kender nu den optimale strategi for at vælge pivot'en:
Tak for henvisningerne - lidt teori var lige hvad jeg trængte til
--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear
| |
Rasmus Christian Kaa~ (23-01-2001)
| Kommentar
Fra : Rasmus Christian Kaa~ |
Dato : 23-01-01 22:22 |
|
> Ja og så kan man også forstå hvor quicksort i værste tilfælde (hvis data
er
> sorteret i omvendt rækkefølge) er ligeså langsom som bubble sort, nemlig
> O(n^2)
>
> Den sidste sorterings algoritme lyder spændende hvad er O(x) ??
du kan lave spande sortering hurtigere end quicksort. den er vist noget der
minder om O(ln(n)*n) men jeg er ikke helt sikker. søg på radix sort.
-----
Rasmus Christian Kaae
www.daimi.au.dk/~kaae
| |
Soren 'Disky' Reinke (24-01-2001)
| Kommentar
Fra : Soren 'Disky' Reinke |
Dato : 24-01-01 09:56 |
|
"Rasmus Christian Kaae" <rasmus@skallebank.com> wrote in message
news:94ksff$bsu$1@news.cybercity.dk...
> > Ja og så kan man også forstå hvor quicksort i værste tilfælde (hvis data
> er
> > sorteret i omvendt rækkefølge) er ligeså langsom som bubble sort, nemlig
> > O(n^2)
> >
> > Den sidste sorterings algoritme lyder spændende hvad er O(x) ??
>
>
> du kan lave spande sortering hurtigere end quicksort. den er vist noget
der
> minder om O(ln(n)*n) men jeg er ikke helt sikker. søg på radix sort.
mener du ikke O(n*log(n)) ?? (som er quicksorts hastighed under 'normale'
omstændigheder)
Ja bucket sort er uhyggelig hurtig nemlig O(n)
problemmet er at du skal have ligeså mange spande som der er mulige værdier.
Kan alstå ikke bruges til at sortere navne og lignende med.
--
With many Thanks
Soren ' Disky ' Reinke ICQ #1413069 remove 'ihsyd' when email replying
Please visit my Freshwater Aquaria Webpage
http://www.disky-design.dk/fish
| |
Rasmus Christian Kaa~ (24-01-2001)
| Kommentar
Fra : Rasmus Christian Kaa~ |
Dato : 24-01-01 14:05 |
|
> > du kan lave spande sortering hurtigere end quicksort. den er vist noget
> der
> > minder om O(ln(n)*n) men jeg er ikke helt sikker. søg på radix sort.
>
> mener du ikke O(n*log(n)) ?? (som er quicksorts hastighed under 'normale'
> omstændigheder)
jeg er ikke fan a quicksort.
> Ja bucket sort er uhyggelig hurtig nemlig O(n)
> problemmet er at du skal have ligeså mange spande som der er mulige
værdier.
> Kan alstå ikke bruges til at sortere navne og lignende med.
næh, men jeg har også kun brugt den til at sortere fixed-point tal med (til
3d-polygoner). der kan man vælge en passende radix-inddeling. og så er
sorteringen turbo hurtig.
-----
Rasmus Christian Kaae
www.daimi.au.dk/~kaae
| |
Soren 'Disky' Reinke (25-01-2001)
| Kommentar
Fra : Soren 'Disky' Reinke |
Dato : 25-01-01 09:14 |
|
>
> jeg er ikke fan a quicksort.
>
> > Ja bucket sort er uhyggelig hurtig nemlig O(n)
> > problemmet er at du skal have ligeså mange spande som der er mulige
> værdier.
> > Kan alstå ikke bruges til at sortere navne og lignende med.
>
> næh, men jeg har også kun brugt den til at sortere fixed-point tal med
(til
> 3d-polygoner). der kan man vælge en passende radix-inddeling. og så er
> sorteringen turbo hurtig.
Der er den nok uden tvivl den hurtigste.
--
With many Thanks
Soren ' Disky ' Reinke ICQ #1413069 remove 'ihsyd' when email replying
Please visit my Freshwater Aquaria Webpage
http://www.disky-design.dk/fish
| |
Regnar Bang Lyngsø (24-01-2001)
| Kommentar
Fra : Regnar Bang Lyngsø |
Dato : 24-01-01 15:23 |
|
Soren 'Disky' Reinke wrote:
> Ja bucket sort er uhyggelig hurtig nemlig O(n)
> problemmet er at du skal have ligeså mange spande som der er mulige værdier.
Vel O(m+n)? Du har n input med m mulige forskellige værdier.
Ved hovedet-under-armen implementation:
Initialisering af spande: O(m)
Opfyldning af spande: O(n)
Tømning af spande: O(m)
Knus
Regnar
--
Regnar Bang Lyngsø (regnar@writeme.com, regnar@beer.com)
<URL: http://www.daimi.au.dk/%7Erblyngso/>
| |
Soren 'Disky' Reinke (25-01-2001)
| Kommentar
Fra : Soren 'Disky' Reinke |
Dato : 25-01-01 09:17 |
|
"Regnar Bang Lyngsø" <regnar@writeme.com> wrote in message
news:3A6EE53A.F0EF9787@writeme.com...
> Soren 'Disky' Reinke wrote:
>
> > Ja bucket sort er uhyggelig hurtig nemlig O(n)
> > problemmet er at du skal have ligeså mange spande som der er mulige
værdier.
>
> Vel O(m+n)? Du har n input med m mulige forskellige værdier.
>
> Ved hovedet-under-armen implementation:
>
> Initialisering af spande: O(m)
> Opfyldning af spande: O(n)
> Tømning af spande: O(m)
Ja men O(n) angiver jo at afviklingstiden stiger linært med antal elementer.
altså en fordobling af antal elementer giver en fordobling af
sorteringstiden.
I forhold til andre metoder betyder initialisering ikke noget, da det er
sorteringstiden vi snakker om.
Hvorimod f.eks. bubble sort tager 4 gange så lang tid for en fordobling af
elementer. pga O(n^2)
> Knus
Nej tak
> Regnar
--
With many Thanks
Soren ' Disky ' Reinke ICQ #1413069 remove 'ihsyd' when email replying
Please visit my Freshwater Aquaria Webpage
http://www.disky-design.dk/fish
| |
Regnar Bang Lyngsø (26-01-2001)
| Kommentar
Fra : Regnar Bang Lyngsø |
Dato : 26-01-01 00:31 |
|
Soren 'Disky' Reinke wrote:
> > Vel O(m+n)? Du har n input med m mulige forskellige værdier.
> >
> > Ved hovedet-under-armen implementation:
> >
> > Initialisering af spande: O(m)
> > Opfyldning af spande: O(n)
> > Tømning af spande: O(m)
>
> Ja men O(n) angiver jo at afviklingstiden stiger linært med antal elementer.
> altså en fordobling af antal elementer giver en fordobling af
> sorteringstiden.
> I forhold til andre metoder betyder initialisering ikke noget, da det er
> sorteringstiden vi snakker om.
Det kan godt være vi er enige og i givet fald er det bare mig, der er
lidt træt.
Jeg mener klart at det er nødvendigt at se på initialiseringen. Selv,
hvis vi vælger at se bort fra den, slipper du ikke for at tømme dine
spande.
> Hvorimod f.eks. bubble sort tager 4 gange så lang tid for en fordobling af
> elementer. pga O(n^2)
Min pointe er at man skal huske at se sig for.
Lad os antage at vi sorterer 25 heltal. Lad os yderligere antage at
disse heltal er mellem 0 og 1 million. Så bliver du nødt til at have en
1 million spande. Disse skal tjekkes for at du kan udskrive en sorteret
liste. En fordobling af antallet af elementer giver _ikke_ en fordobling
af køretiden.
Mit bud er at i den tænkte situation er selv en bubble-sort hurtigere.
Jeg mener det er en fejl at se bort fra antallet af spande.
Knus
Regnar
--
Regnar Bang Lyngsø (regnar@writeme.com, regnar@beer.com)
<URL: http://www.daimi.au.dk/%7Erblyngso/>
| |
Soren 'Disky' Reinke (26-01-2001)
| Kommentar
Fra : Soren 'Disky' Reinke |
Dato : 26-01-01 09:03 |
|
"Regnar Bang Lyngsø" <regnar@writeme.com> wrote in message
news:3A70B731.5D0FC470@writeme.com...
> Soren 'Disky' Reinke wrote:
>
> > > Vel O(m+n)? Du har n input med m mulige forskellige værdier.
> > >
> > > Ved hovedet-under-armen implementation:
> > >
> > > Initialisering af spande: O(m)
> > > Opfyldning af spande: O(n)
> > > Tømning af spande: O(m)
> >
> > Ja men O(n) angiver jo at afviklingstiden stiger linært med antal
elementer.
> > altså en fordobling af antal elementer giver en fordobling af
> > sorteringstiden.
> > I forhold til andre metoder betyder initialisering ikke noget, da det er
> > sorteringstiden vi snakker om.
>
> Det kan godt være vi er enige og i givet fald er det bare mig, der er
> lidt træt.
>
> Jeg mener klart at det er nødvendigt at se på initialiseringen. Selv,
> hvis vi vælger at se bort fra den, slipper du ikke for at tømme dine
> spande.
>
> > Hvorimod f.eks. bubble sort tager 4 gange så lang tid for en fordobling
af
> > elementer. pga O(n^2)
>
> Min pointe er at man skal huske at se sig for.
>
> Lad os antage at vi sorterer 25 heltal. Lad os yderligere antage at
> disse heltal er mellem 0 og 1 million. Så bliver du nødt til at have en
> 1 million spande. Disse skal tjekkes for at du kan udskrive en sorteret
> liste. En fordobling af antallet af elementer giver _ikke_ en fordobling
> af køretiden.
>
> Mit bud er at i den tænkte situation er selv en bubble-sort hurtigere.
> Jeg mener det er en fejl at se bort fra antallet af spande.
Det har du ret i.
Jeg ville så aldrig bruge bucket sort, hvis jeg havde 25 elementer som kunne
være imellem 0-1000000
Ligesom en anden skrev skal 'n' være pænt stort for at der er en forskel på
f.eks. O(n^2) og O(n*log_2(n))
--
With many Thanks
Soren ' Disky ' Reinke ICQ #1413069 remove 'ihsyd' when email replying
Please visit my Freshwater Aquaria Webpage
http://www.disky-design.dk/fish
| |
Thorbjørn Ravn Ander~ (26-01-2001)
| Kommentar
Fra : Thorbjørn Ravn Ander~ |
Dato : 26-01-01 09:28 |
|
Soren 'Disky' Reinke wrote:
> Ligesom en anden skrev skal 'n' være pænt stort for at der er en forskel på
> f.eks. O(n^2) og O(n*log_2(n))
Logaritmens grundtal er ligegyldigt, da det går i O's konstant. Samme
bliver iøvrigt interessant når man sammenligner forskellige algoritmer,
istedet for at kigge på hvordan det skalerer.
--
Thorbjørn Ravn Andersen "...sound of...Tubular Bells!"
http://bigfoot.com/~thunderbear
| |
Christian Worm Morte~ (26-01-2001)
| Kommentar
Fra : Christian Worm Morte~ |
Dato : 26-01-01 11:27 |
|
Hej,
> Jeg mener klart at det er nødvendigt at se på initialiseringen.
Man kan godt initialisere en tabel i konstant tid.
> Selv,
> hvis vi vælger at se bort fra den, slipper du ikke for at tømme dine
> spande.
Nej, det er nemlig problemet.
Venlig Hilsen
Christian Worm
| |
Byrial Jensen (27-01-2001)
| Kommentar
Fra : Byrial Jensen |
Dato : 27-01-01 10:59 |
| | |
Regnar Bang Lyngsø (27-01-2001)
| Kommentar
Fra : Regnar Bang Lyngsø |
Dato : 27-01-01 11:53 |
|
Byrial Jensen wrote:
> >Man kan godt initialisere en tabel i konstant tid.
>
> Hvordan?
Du antager at du kan allokere uinitialiseret lager i konstant tid.
Du allokerer så:
1 heltalsvariabel v (=vidnetæller) initialiseret til 0.
3 lister (en værdiliste, en vidneliste og en påstandsliste).
Ved indsættelse på i'te plads i tabel:
======================================
1. Indsæt værdien på i'te plads i værdilisten.
Værdien er sat i listen.
2. Skriv i på den v'te plads i vidnelisten.
Vi har nu et vidne, der kan verificere at den i'te indgang i værdilisten
er en vi selv har skrevet. Vi ved også at alle de v første indgange i
vidnelisten har vi selv skrevet. Vi kan altså stole på de første v
indgange i vidnelisten.
3. Skriv v på den i'te plads i påstandslisten.
Dette gøres for at effektivisere opslag.
4. Tæl v en op.
Ved aflæsning af den i'te plads i tabel:
========================================
1. Slå den i'te plads i påstandslisten op (kaldes herefter p).
Vi ved ikke om denne værdi er en vi selv har sat eller om den tilfældigt
har denne værdi på grund af at lageret er uinitialiseret. Vi må tjekke
om det påståede vidne p kan sige god for påstanden.
2. Hvis p er større end v returneres "ikke i listen".
Vi ved at vi har v vidner. Det påståede vidne har et højere nummer end
antallet af vidner. Altså er der ikke et vidne for den i'te plads.
3. Hvis p er skarpt mindre end v slåes den p'te indgang op i vidnelisten
(vidnet, v').
4. Hvis ikke v' er lig i returneres "ikke i listen".
Den i'te plads i påstandslisten påstod, at den p'te indgang i
vidnelisten ville sige god for den. Men den p'te indgang i vidnelisten
siger god for en anden. Ergo er påstanden forkert og værdien kan ikke
være i listen.
5. Hvis v' er lig i returneres den i'te indgang i værdilisten.
Vidnet v' siger god for påstanden. Vi ved derfor at der er en værdi på
den i'te plads. Denne slås op i værdilisten.
==
Voila. Oprettelse, indsættelse og opslag i O(1).
--
Regnar Bang Lyngsø (regnar@writeme.com, regnar@beer.com)
<URL: http://www.daimi.au.dk/%7Erblyngso/>
| |
Richard Flamsholt (27-01-2001)
| Kommentar
Fra : Richard Flamsholt |
Dato : 27-01-01 18:29 |
|
Regnar Bang Lyngsø <regnar@writeme.com> skrev:
>Ved indsættelse på i'te plads i tabel:
>1. Indsæt værdien på i'te plads i værdilisten.
>2. Skriv i på den v'te plads i vidnelisten.
>3. Skriv v på den i'te plads i påstandslisten.
>4. Tæl v en op.
Fint. Det skal du så gøre N gange for at indsætte N elementer.
>Voila. Oprettelse, indsættelse og opslag i O(1).
Ja, O(k) for ét element. Men hvad med de resterende N-1 elementer?
Jeg er ikke helt sikker på, om din algoritme er ment som en joke. Den
kan afgøre hvorvidt et givet element vitterligt er initialiseret eller
ej, javist, men det mindsker jo ikke kompleksiteten af initialiseringen
af hele tabellen.
--
Richard Flamsholt
richard@flamsholt.dk - www.richard.flamsholt.dk
| |
Jens Axel Søgaard (27-01-2001)
| Kommentar
Fra : Jens Axel Søgaard |
Dato : 27-01-01 18:46 |
|
Richard Flamsholt <richard@flamsholt.dk> writes:
> Regnar Bang Lyngsø <regnar@writeme.com> skrev:
> >Ved indsættelse på i'te plads i tabel:
> >1. Indsæt værdien på i'te plads i værdilisten.
> >2. Skriv i på den v'te plads i vidnelisten.
> >3. Skriv v på den i'te plads i påstandslisten.
> >4. Tæl v en op.
>
> Fint. Det skal du så gøre N gange for at indsætte N elementer.
Nej.
> >Voila. Oprettelse, indsættelse og opslag i O(1).
>
> Ja, O(k) for ét element. Men hvad med de resterende N-1 elementer?
>
> Jeg er ikke helt sikker på, om din algoritme er ment som en
> joke.
Han er skam alvorlig.
> Den kan afgøre hvorvidt et givet element vitterligt er initialiseret
> eller ej, javist, men det mindsker jo ikke kompleksiteten af
> initialiseringen af hele tabellen.
Ah - du har jo selv forklaringen. Når man aflæser en indgang
undersøger man først, om indgangen er initialiseret eller ej. Hvis den
ikke er initialiseret, jamen så siger vi bare, at vi læste et 0. Hvis
indgangen er initialiseret, jammen så slår vi dens værdi op.
Bemærk, at vi skal ikke benytte algoritmen for indsættelse af et
element, til at initialisere datastrukturen. Husk også, at
forudsætningen er, at alle indgangene bliver initialiseret til den
samme værdi.
--
Jens Axel Søgaard -- http://www.jasoegaard.dk
A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös
| |
Jens Axel Søgaard (27-01-2001)
| Kommentar
Fra : Jens Axel Søgaard |
Dato : 27-01-01 18:56 |
|
Hov forresten. Tak til Regnar for at poste algoritmen. Jeg havde
glemt, alt om den.
Det er åbenbart for længe siden, jeg havde algoritmik.
Er der nogen, der ved, hvad algoritmen hedder ?
--
Jens Axel Søgaard -- http://www.jasoegaard.dk
A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös
| |
Richard Flamsholt (27-01-2001)
| Kommentar
Fra : Richard Flamsholt |
Dato : 27-01-01 20:49 |
|
jensaxel@soegaard.net (Jens Axel Søgaard) skrev:
>Han er skam alvorlig.
Men misvisende, for han nævner ikke sine forudsætninger.
Man kan ikke generelt initialisere en tabel på konstant tid. Men man kan
med lazy-evaluation udskyde beregninger, hvilket kan være en fordel hvis
de beregninger ikke alle er nødvendige.
Det kan fx være en fordelagtig måde at håndtere en stor tabel på, hvor
kun få af tabellens værdier afviger fra en given default-værdi.
Jeg opfattede Christians "Man kan godt initialisere en tabel i konstant
tid" som en generelt påstand, dvs at han mente, man ved anvendelsen af
en smart metode kunne initalisere en given tabel i konstant tid. Det kan
man jo ikke, som du også siger:
>Hvis den ikke er initialiseret, jamen så siger vi bare, at vi læste et 0.
[snip]
>forudsætningen er, at alle indgangene bliver initialiseret til den
>samme værdi.
Det er ret væsentlige forudsætninger.
--
Richard Flamsholt
richard@flamsholt.dk - www.richard.flamsholt.dk
| |
Christian Worm Morte~ (27-01-2001)
| Kommentar
Fra : Christian Worm Morte~ |
Dato : 27-01-01 21:28 |
|
Hej,
> Man kan ikke generelt initialisere en tabel på konstant tid.
Hvis man er meget præcis kan man definere hvilken maskinmodel man arbejder
under. Og så kan man dernæst definere hvad en tabel er og så kan man udtale
sig om hvilke operationer man kan understøtte på denne tabel i hvilken tid i
den valgte maskinmodel.
Men hvis man antager en almindelige RAM maskin-model, som det vist hedder,
og hvis man definerer en tabel som værende en datastruktur der vedligeholder
en funktion defineret på heltallene i et interval [0;n[ og hvor man
understøtter operationerne at slå op hvad f(i) er for et i, at sætte f(i)
til en bestemt værdi for et i, eller at sætte f(i) til en bestemt værdi for
alle i, ja så kan man understøtte alle disse operationer i tid O(1) og plads
O(n).
Men man kan selvfølgelig ikke dermed til sin maskin model tilføje en
operation der hedder at sætte alle cellerne i lageret til en bestemt værdi i
konstant tid.
Venlig Hilsen
Christian Worm
| |
Richard Flamsholt (27-01-2001)
| Kommentar
Fra : Richard Flamsholt |
Dato : 27-01-01 21:42 |
|
"Christian Worm Mortensen" <worm@dkik.dk> skrev:
>ja så kan man understøtte alle disse operationer i tid O(1)
Her er vi helt enige.
>Men man kan selvfølgelig ikke dermed til sin maskin model tilføje en
>operation der hedder at sætte alle cellerne i lageret til en bestemt værdi i
>konstant tid.
Netop. Og eftersom det er det, man naturligt tænker på, når der tales om
at "initialisere en tabel", måtte jeg lige høre hvad meningen var.
Den algoritme, Regnar beskrev, gik snarere ud på at undgå at initalisere
(hele) tabellen, og det kan skam også være meget brugbart.
--
Richard Flamsholt
richard@flamsholt.dk - www.richard.flamsholt.dk
| |
Christian Worm Morte~ (27-01-2001)
| Kommentar
Fra : Christian Worm Morte~ |
Dato : 27-01-01 21:46 |
|
Hej,
> >Men man kan selvfølgelig ikke dermed til sin maskin model tilføje en
> >operation der hedder at sætte alle cellerne i lageret til en bestemt
værdi i
> >konstant tid.
>
> Netop. Og eftersom det er det, man naturligt tænker på, når der tales om
> at "initialisere en tabel", måtte jeg lige høre hvad meningen var.
Men pointen er at hvis du har brug for i en algoritme at kunne initialiseret
et stykke lager (=en tabel) i konstant tid - så kan du også gøre det.
> Den algoritme, Regnar beskrev, gik snarere ud på at undgå at initalisere
> (hele) tabellen, og det kan skam også være meget brugbart.
Hverken i den algoritme jeg eller Regnar skrev skulle der initialiseres
andet end en enkelt tæller der skulle sættes til 0.
Venlig Hilsen
Christian Worm
| |
Ulrik Magnusson (27-01-2001)
| Kommentar
Fra : Ulrik Magnusson |
Dato : 27-01-01 22:01 |
|
> Men pointen er at hvis du har brug for i en algoritme at kunne initialiseret
> et stykke lager (=en tabel) i konstant tid - så kan du også gøre det.
ok, hvordan?
void initializeInConstantTime( int* start, int length, int value )
{
??????
}
Ulrik Magnusson
| |
Christian Worm Morte~ (27-01-2001)
| Kommentar
Fra : Christian Worm Morte~ |
Dato : 27-01-01 22:06 |
|
Hej,
> ok, hvordan?
Jeg har allerde postet et C program der muligvis endda fungerer. A, B og C i
dette program behøver ikke initialiseres.
> void initializeInConstantTime( int* start, int length, int value )
> {
> ??????
> }
Men du bliver nødt til at tilgå tabellen via de funktioner jeg stiller
tilrådighed - som alle kører i konstant tid.
Venlig Hilsen
Christian Worm
| |
Ulrik Magnusson (27-01-2001)
| Kommentar
Fra : Ulrik Magnusson |
Dato : 27-01-01 22:25 |
|
> Men du bliver nødt til at tilgå tabellen via de funktioner jeg stiller
> tilrådighed - som alle kører i konstant tid.
Altså kan man ikke initialisere et stykke lager i konstant tid. Men man kan lade
som om.
Der er altså rimelig meget forskel, hvis en initialisering fx betyder en _reel_
(ikke-Kohl) sletning
et bestemt lagerområde (eller at farve det)
Ulrik Magnusson
| |
Christian Worm Morte~ (27-01-2001)
| Kommentar
Fra : Christian Worm Morte~ |
Dato : 27-01-01 22:39 |
|
Hej,
> > Men du bliver nødt til at tilgå tabellen via de funktioner jeg stiller
> > tilrådighed - som alle kører i konstant tid.
>
> Altså kan man ikke initialisere et stykke lager i konstant tid.
Om man kan gøre det er et rent hardware spørgsmål og er for så vidt
forholdsvis uinteresseant. På min maskine derhjemme kan jeg godt
initialisere lager i konstant tid - jeg kan bare tage strømmen og sætte den
til igen.
Hvad jeg har vist er, at givet en maskinemodel hvor man ikke kan
initialisere lager med vilkårlig størrelse i konstant tid, så kan jeg, ved
at bruge en konstant faktor mere plads og en konstant faktor mere tid
simulere en maskine hvor man kan initialisere lager med vilkårlig størrelse
i konstant tid.
Og det betyder, at når man analyserer i O notation så kan man tillade sig at
antage at man kan initialisere lager i konstant tid. Den antagelse ændrer
nemlig ikke på de konklusioner man får i O notationen.
Venlig Hilsen
Christian Worm
| |
Ulrik Magnusson (27-01-2001)
| Kommentar
Fra : Ulrik Magnusson |
Dato : 27-01-01 22:51 |
|
> Om man kan gøre det er et rent hardware spørgsmål og er for så vidt
> forholdsvis uinteresseant.
Ja til det første - måske nej til til det sidste. Det er selvfølgeligt et
hardwarespørgsmål når jeg
skriver at man ikke kan gøre det reelt (i.e. fysisk).
> På min maskine derhjemme kan jeg godt
> initialisere lager i konstant tid - jeg kan bare tage strømmen og sætte den
> til igen.
Det tror jeg nu ikke - dit operativsystem lader vel også bare som om det er
gjort.
> Hvad jeg har vist er, at givet en maskinemodel hvor man ikke kan
> initialisere lager med vilkårlig størrelse i konstant tid, så kan jeg, ved
> at bruge en konstant faktor mere plads og en konstant faktor mere tid
> simulere en maskine hvor man kan initialisere lager med vilkårlig størrelse
> i konstant tid.
"Simulere" er vist det vigtige ord her.
> Og det betyder, at når man analyserer i O notation så kan man tillade sig at
> antage at man kan initialisere lager i konstant tid. Den antagelse ændrer
> nemlig ikke på de konklusioner man får i O notationen.
Ok - dér har du en pointe (man laver jo bare algoritmen så den tilgår lageret på
Kohl-måden).
Takker
Ulrik Magnusson
| |
Richard Flamsholt (27-01-2001)
| Kommentar
Fra : Richard Flamsholt |
Dato : 27-01-01 23:35 |
|
"Christian Worm Mortensen" <worm@dkik.dk> skrev:
>På min maskine derhjemme kan jeg godt
>initialisere lager i konstant tid - jeg kan bare tage strømmen og sætte den
>til igen.
Det mener du vel ikke seriøst?
Hvis du gør, så overvej følgende:
1: Enten er dit lager fyldt med tilfældigt garbage når du tænder.
I så tilfælde er det ikke initialiseret.
2: Eller også initialiseres det til fx 0, men det må enten ske
a) vha en sekventiel initialisering af hver lagerenhed.
b) hardwaremæssigt, men så taler vi jo parallel processing (SIMD,
single-instruction-multiple-data), hvor man parallelt kan tildele
alle en værdi til alle lagerenheder samtidigt.
I begge tilfælde giver det ikke mening at tale om konstant tid.
Men, for nu at komme lidt videre - jeg tror vi godt ved, hvad modparten
egentlig mener. Matematisk set kan dine omskrivninger være en fordel når
du laver O-analyser og de kan afsløre, at hvis et lager slet ikke bruges
kan man slippe for at initialisere det. Men deraf følger jo ikke, at et
lager generelt kan initialiseres i konstant tid.
--
Richard Flamsholt
richard@flamsholt.dk - www.richard.flamsholt.dk
| |
Ulrik Magnusson (28-01-2001)
| Kommentar
Fra : Ulrik Magnusson |
Dato : 28-01-01 00:00 |
|
[snip om at initialisere i konstant tid]
> b) hardwaremæssigt, men så taler vi jo parallel processing (SIMD,
> single-instruction-multiple-data), hvor man parallelt kan tildele
> alle en værdi til alle lagerenheder samtidigt.
Så kan man vel gøre alt i konstant tid, eller hvad?
Giver "konstant tid" (og omicron, omega og theta) ikke kun
mening, hvis vi snakker om sådan en RAM (Random Access Machine)
ting, der er beskrevet i "Introduction to Algorithms":
"In the RAM model, instructions are executed one after another,
with no concurrent operations"
eller gælder det også i andre tilfælde??
(og ja, jeg skal have 2A nu, og har derfor lige læst kapitel 1 )
Ulrik Magnusson
| |
Christian Worm Morte~ (28-01-2001)
| Kommentar
Fra : Christian Worm Morte~ |
Dato : 28-01-01 04:58 |
|
Hej,
> >På min maskine derhjemme kan jeg godt
> >initialisere lager i konstant tid - jeg kan bare tage strømmen og sætte
den
> >til igen.
>
> Det mener du vel ikke seriøst?
Min pointe er blot at hvis du antager at det altid tager konstant tid at
skrive i en lagercelle, så tager det selvfølgelig mere end konstant tid at
skrive i mere end et konstant antal lagerceller.
Og min anden pointe er at det vi er interesserede i er ikke at skrive til
lagerceller. Vi er interesserede i at arbejde i en struktur der virker lige
som et lager.
Venlig Hilsen
Christian Worm
| |
Richard Flamsholt (27-01-2001)
| Kommentar
Fra : Richard Flamsholt |
Dato : 27-01-01 23:06 |
|
"Christian Worm Mortensen" <worm@dkik.dk> skrev:
>Men pointen er at hvis du har brug for i en algoritme at kunne initialiseret
>et stykke lager (=en tabel) i konstant tid - så kan du også gøre det.
Nej, man kan ej. Hold nu op. Man kan *udskyde* beregningen af en værdi
indtil der er brug for den, eller man kan benytte en defaultværdi for
ikke-explicit-initialiserede elementer, som din algoritme fx gør:
if(!updated[i]) {
return 0; // Den værdi vi initialiserer med
Man kan ikke generelt "initialisere et stykke lager i konstant tid", som
du siger, men man kan sommetider fjerne behovet for at initialisere hele
lageret på forhånd og dermed opnå O(k).
--
Richard Flamsholt
richard@flamsholt.dk - www.richard.flamsholt.dk
| |
Christian Worm Morte~ (28-01-2001)
| Kommentar
Fra : Christian Worm Morte~ |
Dato : 28-01-01 04:12 |
|
Hej,
> >Men pointen er at hvis du har brug for i en algoritme at kunne
initialiseret
> >et stykke lager (=en tabel) i konstant tid - så kan du også gøre det.
>
> Man kan ikke generelt "initialisere et stykke lager i konstant tid", som
> du siger, men man kan sommetider fjerne behovet for at initialisere hele
> lageret på forhånd og dermed opnå O(k).
Hvad forstår du ved et lager?
Venlig Hilsen
Christian Worm
| |
Richard Flamsholt (28-01-2001)
| Kommentar
Fra : Richard Flamsholt |
Dato : 28-01-01 17:08 |
|
"Christian Worm Mortensen" <worm@dkik.dk> skrev:
>Hvad forstår du ved et lager?
Det samme som du. (Dvs en datastruktur med et antal elementer, der som
udgangspunkt har ukendte værdier og som kan tildeles værdier og tilgås
på én eller anden måde. Array, liste, kø, hob, osv)
Det interessante er derimod ordet initialisering. Med "initialisering af
et lager" forstår jeg "arbejdet forbundet med tildeling af værdier til
elementerne i lageret". Du mener "arbejdet forbundet med at initialisere
selve lager-containeren, dvs ikke indbefattet arbejdet forbundet med at
tildele værdier til elementerne".
Jeg gik med andre ord ud fra, at initialiseringen gjaldt selve indholdet
i containeren, ikke blot containeren. Der findes jo masser af container-
datatyper, som kan skabes og initialiseres som tomme på konstant tid.
Selvom jeg godt kan se din pointe synes jeg stadig, det er lidt farlig
at sige "lageret er initialiseret", fordi mange vil naturligt forstå
"lager" som "indholdet af lageret" og ikke som "lager-containeren".
--
Richard Flamsholt
richard@flamsholt.dk - www.richard.flamsholt.dk
| |
Christian Worm Morte~ (28-01-2001)
| Kommentar
Fra : Christian Worm Morte~ |
Dato : 28-01-01 18:23 |
|
Hej,
> > Hvad forstår du ved et lager?
> Det samme som du. (Dvs en datastruktur med et antal elementer, der som
> udgangspunkt har ukendte værdier og som kan tildeles værdier og tilgås
> på én eller anden måde. Array, liste, kø, hob, osv)
> Det interessante er derimod ordet initialisering. Med "initialisering af
> et lager" forstår jeg "arbejdet forbundet med tildeling af værdier til
> elementerne i lageret".
Jammen dette arbejde består i den valgte repræsentation af tabellen i at
sætte en tæller til 0.
Venlig Hilsen
Christian Worm
| |
Jens Axel Søgaard (28-01-2001)
| Kommentar
Fra : Jens Axel Søgaard |
Dato : 28-01-01 00:30 |
|
Richard Flamsholt <richard@flamsholt.dk> writes:
> jensaxel@soegaard.net (Jens Axel Søgaard) skrev:
> >Han er skam alvorlig.
>
> Men misvisende, for han nævner ikke sine forudsætninger.
De er ikke misvisende i sammenhængen.
Hvis man læser tråden fra start af, kan man se, at den handler om
kompleksiteten af en bestemt søgealgoritme (spand-sortering). Analysen
af denne denne skal naturligvis foregå på et teoretisk grundlag -
dermed skal ordet "tabel" ikke opfattes som det, der kaldes tabel i C,
men som en abstrakt data-struktur (som nogle gør andetsteds i
tråden).
Det, der oprindeligt blev sået tvivl om, var tidskopleksiteten af
initialiseringen af spandene. Da alle spandene skal initialiseres til
det samme, foreslog Regnar en brugbar algoritme.
Er der nogen, der ved hvad den hedder? - eller er det bare en af dens
slags resultater, man kender fordi man engang har fået den som opgave?
--
Jens Axel Søgaard -- http://www.jasoegaard.dk
A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös
| |
Richard Flamsholt (28-01-2001)
| Kommentar
Fra : Richard Flamsholt |
Dato : 28-01-01 03:21 |
|
jensaxel@soegaard.net (Jens Axel Søgaard) skrev:
>De er ikke misvisende i sammenhængen.
Mit problem var, at "man kan godt initialisere en tabel i konstant tid"
fremstod som en generel sandhed om initialisering i al almindelighed og
det er det jo slet ikke.
Havde sætningen lydt "en sådan tabel..." havde jeg ikke reageret, men
jeg antog det for at være en generel påstand. Jeg kan nu godt se, at den
selvfølgelig kun var møntet på behovet i sorteringsalgoritmen.
>Er der nogen, der ved hvad den hedder? - eller er det bare en af dens
>slags resultater, man kender fordi man engang har fået den som opgave?
Jeg kendte den ikke, men har tidligere selv brugt noget der ligner ideen
bag værdiliste og vidneliste. Påstandslisten havde jeg ikke tænkt over,
men den er en ret smart optimering.
--
Richard Flamsholt
richard@flamsholt.dk - www.richard.flamsholt.dk
| |
Byrial Jensen (28-01-2001)
| Kommentar
Fra : Byrial Jensen |
Dato : 28-01-01 11:09 |
|
Jens Axel Søgaard <jensaxel@soegaard.net> skrev:
>De er ikke misvisende i sammenhængen.
Jeg er helt enig. Det var mig spurgte om hvordan man kan initialisere
i konstant tid, og jeg er fuldt ud tilfreds med de svar som jeg fik.
Tak til svarerne!
--
Byrial
http://home.worldonline.dk/~byrial/
| |
Soeren Sandmann (28-01-2001)
| Kommentar
Fra : Soeren Sandmann |
Dato : 28-01-01 15:47 |
|
jensaxel@soegaard.net (Jens Axel Søgaard) writes:
> Er der nogen, der ved hvad den hedder? - eller er det bare en af dens
> slags resultater, man kender fordi man engang har fået den som opgave?
Min algoritmikinstruktor hævdede at der engang var en eller anden der
forsøgte at få en artikel om den optaget på en konference. Den blev
afvist med henvisning til at den havde været stillet som
eksamensopgave på første år på Aarhus Universitet, så jeg tror ikke
den har noget navn.
| |
Jens Axel Søgaard (28-01-2001)
| Kommentar
Fra : Jens Axel Søgaard |
Dato : 28-01-01 16:22 |
|
Soeren Sandmann <sandmann@daimi.au.dk> writes:
> jensaxel@soegaard.net (Jens Axel Søgaard) writes:
>
>> Er der nogen, der ved hvad den hedder? - eller er det bare en af
>> dens slags resultater, man kender fordi man engang har fået den som
>> opgave?
>
> Min algoritmikinstruktor hævdede at der engang var en eller anden
> der forsøgte at få en artikel om den optaget på en konference. Den
> blev afvist med henvisning til at den havde været stillet som
> eksamensopgave på første år på Aarhus Universitet, den har noget
> navn.
På Daimi ? - så kan det være det ikke er almindelig kendt, men kun os
som er blevet udsat for opgaven i algoritmik, der kender den.
Vi kan jo opkalde den efter ham, som stillede den. Hvis det var en
ekamen på første år, kan det måske være Erik Meiniche Schimdt, som
har været opfindsom.
Jeg kiggede lidt i Knuth, for at se om, opgaven var hugget derfra, men
jeg kunne ikke umiddelbart finde noget, der lignede.
--
Jens Axel Søgaard -- http://www.jasoegaard.dk
A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös
| |
Rasmus Christian Kaa~ (28-01-2001)
| Kommentar
Fra : Rasmus Christian Kaa~ |
Dato : 28-01-01 18:14 |
|
> Vi kan jo opkalde den efter ham, som stillede den. Hvis det var en
> ekamen på første år, kan det måske være Erik Meiniche Schimdt, som
> har været opfindsom.
>
> Jeg kiggede lidt i Knuth, for at se om, opgaven var hugget derfra, men
> jeg kunne ikke umiddelbart finde noget, der lignede.
EMS bruger ikke Knuth som lærebog mere, i 2000 semesteret brugte han
"Datastructures and Algorithms in Java" af Goodrich og Tamassia, og så vidt
jeg ved blev den 1) ikke stillet til juni-eksamen 2000 og 2) ikke nævnt i
forelæsningerne / pensum.
-----
Bustur til MekkaSymposium: www.demo-scene.dk/bus
| |
Jens Axel Søgaard (28-01-2001)
| Kommentar
Fra : Jens Axel Søgaard |
Dato : 28-01-01 18:34 |
|
"Rasmus Christian Kaae" <rasmus@skallebank.com> writes:
> > Vi kan jo opkalde den efter ham, som stillede den. Hvis det var en
> > ekamen på første år, kan det måske være Erik Meiniche Schimdt, som
> > har været opfindsom.
> >
> > Jeg kiggede lidt i Knuth, for at se om, opgaven var hugget derfra, men
> > jeg kunne ikke umiddelbart finde noget, der lignede.
>
> EMS bruger ikke Knuth som lærebog mere, i 2000 semesteret brugte han
> "Datastructures and Algorithms in Java" af Goodrich og Tamassia, og
> så vidt jeg ved blev den 1) ikke stillet til juni-eksamen 2000 og 2)
> ikke nævnt i forelæsningerne / pensum.
Jeg tror ikke han har brugt Knuth som lærebog. Hvis man har brug for
en algoritme til et eller andet, er Knuth bare stedet _man_
starter. Der er også god mulighed for at hente inspiration til
eksamensopgaver.
Vi (mindst Regnar, Søren og jeg) havde den som opgave i algoritmik
engang tilbage i (ca.) 1996. Derfor troede jeg i første omgang, at det
var til algoritmik-eksamen, den var stillet første gang.
Ligger de gamle eksamensopgaver op nettet et eller andet sted?
Da vi havde EMS og Schwartzbach på første år, brugte de deres egen bog
om hedengangne Trine.
--
Jens Axel Søgaard -- http://www.jasoegaard.dk
A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös
| |
Regnar Bang Lyngsø (28-01-2001)
| Kommentar
Fra : Regnar Bang Lyngsø |
Dato : 28-01-01 19:10 |
|
"Jens Axel Søgaard" wrote:
> Vi (mindst Regnar, Søren og jeg) havde den som opgave i algoritmik
> engang tilbage i (ca.) 1996. Derfor troede jeg i første omgang, at det
> var til algoritmik-eksamen, den var stillet første gang.
>
> Ligger de gamle eksamensopgaver op nettet et eller andet sted?
Som jeg husker det var vi anden årgang, der havde skriftlig eksamen i
algoritmik, så jeg mener ikke at den har været stillet som
eksamensopgave. Til gengæld har den været fast gæst ved øvelserne i
flere år.
Derudover mener jeg også at det ville være bisset. Opgaveteksten var
(har lige fundet den i mappen):
"Opgave 2 (den er tricky!)
Vi er interesserede i følgende operationer
* Init(n): Initialiser datastruktur af størrelse n
* set(i,j): Sæt værdien af element i til j (0<i<=n)
* get(i): Returnerer den sidste værdi, som element i er sat til. Hvis
element i /ikke/ er sat til nogen værdi, returneres udefineret.
Konstruer en datastruktur, der implementerer operationerne i tid O(1).
Bemærk at n elementer i lageret ikke kan nulstilles i konstant tid!!!"
Personligt tog det mig omkring 2 timer og 3 Fuglsang Golden Bird at
knække den. Det er ikke svært når man har ideen; det der tager tid er at
få ideen. Eksamensopgaverne var væsentligt lettere.
Knus
Regnar
--
Regnar Bang Lyngsø (regnar@writeme.com, regnar@beer.com)
<URL: http://www.daimi.au.dk/%7Erblyngso/>
| |
Jens Axel Søgaard (28-01-2001)
| Kommentar
Fra : Jens Axel Søgaard |
Dato : 28-01-01 21:01 |
|
Regnar Bang =?iso-8859-1?Q?Lyngs=F8?= <regnar@writeme.com> writes:
> Som jeg husker det var vi anden årgang, der havde skriftlig eksamen
> i algoritmik, så jeg mener ikke at den har været stillet som
> eksamensopgave. Til gengæld har den været fast gæst ved øvelserne i
> flere år.
> Derudover mener jeg også at det ville være bisset. Opgaveteksten var
> (har lige fundet den i mappen):
>
> "Opgave 2 (den er tricky!)
[snip]
> Personligt tog det mig omkring 2 timer og 3 Fuglsang Golden Bird at
> knække den.
Fuglsang Golden Bird? Er det en øl?
> Det er ikke svært når man har ideen; det der tager tid er at få
> ideen.
Men alligevel er det altid det, man undervurderer.
> Eksamensopgaverne var væsentligt lettere.
Ja - der er jo aldrig god tid til at få gode idéer til eksamen.
--
Jens Axel Søgaard -- http://www.jasoegaard.dk
A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös
| |
Regnar Bang Lyngsø (29-01-2001)
| Kommentar
Fra : Regnar Bang Lyngsø |
Dato : 29-01-01 10:56 |
|
"Jens Axel Søgaard" wrote:
> Fuglsang Golden Bird? Er det en øl?
Hmmm.... nu er vi vist så langt fra C-programmering com man kan komme
Fuglsang Golden Bird er ganske rigtigt en øl (som jeg havde et
ganske godt forhold til i foråret 97).
Knus
Regnar
--
Regnar Bang Lyngsø (regnar@writeme.com, regnar@beer.com)
<URL: http://www.daimi.au.dk/%7Erblyngso/>
| |
Jens Axel Søgaard (29-01-2001)
| Kommentar
Fra : Jens Axel Søgaard |
Dato : 29-01-01 15:01 |
|
Regnar Bang =?iso-8859-1?Q?Lyngs=F8?= <regnar@writeme.com> writes:
> "Jens Axel Søgaard" wrote:
>
> > Fuglsang Golden Bird? Er det en øl?
>
> Hmmm.... nu er vi vist så langt fra C-programmering com man kan
> komme
Sorry
Kram,
--
Jens Axel Søgaard -- http://www.jasoegaard.dk
A Mathematician is a machine for turning coffee into theorems.
- Paul Erdös
| |
Rasmus Christian Kaa~ (28-01-2001)
| Kommentar
Fra : Rasmus Christian Kaa~ |
Dato : 28-01-01 19:44 |
|
> Jeg tror ikke han har brugt Knuth som lærebog. Hvis man har brug for
> en algoritme til et eller andet, er Knuth bare stedet _man_
> starter. Der er også god mulighed for at hente inspiration til
> eksamensopgaver.
ok.
> Ligger de gamle eksamensopgaver op nettet et eller andet sted?
jeg har ikke kunnet finde år-2000 eksamen på nettet, men du kan finde de
andre opgaver her :
< http://www.daimi.au.dk/dADS/eksamen.html>
> Da vi havde EMS og Schwartzbach på første år, brugte de deres egen bog
> om hedengangne Trine.
...og som i nok ved så er der ikke mere Trine og Rasmus på daimi
-----
Bustur til MekkaSymposium: www.demo-scene.dk/bus
| |
Ulrik Magnusson (27-01-2001)
| Kommentar
Fra : Ulrik Magnusson |
Dato : 27-01-01 21:04 |
|
> Husk også, at
> forudsætningen er, at alle indgangene bliver initialiseret til den samme
> værdi.
som man ikke kan gøre i mindre end lineær tid, med mindre jeg er helt
forskruet i hovedet..
Altså, man kan _ikke_ initialisere en tabel i konstant tid.
Tak for det - jeg troede lige, jeg var blevet tossig..
Ulrik Magnusson
| |
Soeren Sandmann (27-01-2001)
| Kommentar
Fra : Soeren Sandmann |
Dato : 27-01-01 19:07 |
|
Richard Flamsholt <richard@flamsholt.dk> writes:
> >Voila. Oprettelse, indsættelse og opslag i O(1).
>
> Ja, O(k) for ét element. Men hvad med de resterende N-1 elementer?
Initialisering af n elementer tager tid O(1). Indsættelse og opslag af
ét element tager tid O(1). Man kommer ikke uden om at indsættelse af n
elementer tager tid \Omega(n).
> Jeg er ikke helt sikker på, om din algoritme er ment som en joke. Den
> kan afgøre hvorvidt et givet element vitterligt er initialiseret eller
> ej, javist, men det mindsker jo ikke kompleksiteten af initialiseringen
> af hele tabellen.
Pointen er at der ikke er nogen grund til at initialisere hele
tabellen. Funktionen der slår op, kan i konstant tid give et af
svarene
- ja, der står noget meningsfyldt; der står 'i'.
- nej, der står ikke noget meningsfyldt.
Når opslagsfunktionen kan svare på den måde, er der ikke nogen grund
til at initialisere (hvor initialisere betyder at skrive fx NULL i
alle felterne).
| |
Christian Worm Morte~ (27-01-2001)
| Kommentar
Fra : Christian Worm Morte~ |
Dato : 27-01-01 19:42 |
|
Hej,
> >Man kan godt initialisere en tabel i konstant tid.
>
> Hvordan?
const int N=42;
// Antal elementer i tabellen
int A[N];
// Tabel der afbilleder hver position til hvad brugeren
// har gemt på den pågældende position.
int B[N];
// Tabel der afbilleder hver position til den position i C
// der bekræfter at den pågældende position er opdateret.
int C[N];
// Liste over opdaterede positioner.
int n=0;
// Antallet af elementer i C.
// Hjælpefunktion der afgør om en givet position i tabellen er opdateret.
bool updated(int i) {
if(B[i]>=0 && B[i]<n) {
// B peger til et initialseret sted i C
return C[B[i]]==i;
}
return false;
}
// Sæt position i til val:
void insert(int i, int val) {
A[i]=val;
if(!updated(i)) {
B[i]=n;
C[n++]=i;
}
}
// Læs position i.
int lookup(int i) {
if(!updated[i]) {
return 0; // Den værdi vi initialiserer med
} else {
return A[i];
}
}
Venlig Hilsen
Christian Worm
| |
Bertel Lund Hansen (24-01-2001)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 24-01-01 16:11 |
| | |
Rasmus Christian Kaa~ (24-01-2001)
| Kommentar
Fra : Rasmus Christian Kaa~ |
Dato : 24-01-01 19:19 |
|
> >Ja bucket sort er uhyggelig hurtig nemlig O(n)
>
> Hvordan ser algoritmen ud?
søg efter bucketsort på google.com
-----
Rasmus Christian Kaae
www.daimi.au.dk/~kaae
| |
Regnar Bang Lyngsø (24-01-2001)
| Kommentar
Fra : Regnar Bang Lyngsø |
Dato : 24-01-01 19:40 |
|
Bertel Lund Hansen wrote:
> >Ja bucket sort er uhyggelig hurtig nemlig O(n)
>
> Hvordan ser algoritmen ud?
Forudsætning:
=============
1. Du har n værdier du ønsker at sortere (værdiliste).
2. Du ved at de n værdier er i et endeligt domæne af størrelse m.
3. Du ved at m er mindre end den mængde fysisk arbejdslager du har til
rådighed.
Ide:
====
1. Du ønsker at udnytte at du kender de m forskellige værdier en værdi i
din værdiliste kan have.
2. Du laver en tælleliste af længde m (hver værdi i tællelisten er
initialiseret til nul).
3. Du løber værdilisten igennem og tæller det tilsvarende heltal i
tællelisten op.
4. Endeligt finder du din sorterede liste ved at løbe tællelisten
igennem og indsætter den tilsvarende værdi det antal gange som heltallet
i tællelisten angiver.
Pseudokode:
===========
Hvis vi ønsker at sortere n heltal i intervallet [0; m):
var value_list : Array[n] of Int(0..m)
var count_list : Array[m] of Int(0..n) init 0
var sort_list : Array[n] of Int(0..m)
for i := 0 to n do
value_list[i] := get_value()
endfor
for i := 0 to n do
Inc(count_list[value_list[i]])
endfor
sort_idx := 0
for i := 0 to m do
for j := 0 to count_list[i] do
sort_list[sort_idx] := i
Inc(sort_idx)
endfor
endfor
Analyse:
========
Initialiseringen af count_list er O(n)
Hver af de to første for-løkker er O(n)
Den sidste for-løkke er O(m + n). Det er relativt simpelt at se at den
ydre for-løkke løber m gange og at den inderste for-krop alt i alt
gennemløes n gange (antallet af forskellige værdier). Dette kan også ses
ved at aflæse sort_idx efter gennemløb.
Variation
=========
Over spandesorteringen kendes varianten radixsort. Jeg vil ikke gå i
dybden med den, men blot vise ideen.
Lad os se på mængden af positive heltal mindre end 1000.
En tilfældig liste af værdier herfra kan være:
522, 124, 234, 987, 656, 497, 204, 108, 740, 127
Vi laver nu kun 10 spande nummereret fra 0 til 9. Vi bruger disse spande
3 gange - en gang for hvert ciffer i tallet.
Første gennemløb (bageste tal):
0 740
1
2 522
3
4 124, 234, 204
5
6 656
7 497, 987, 127
8 108
9
Sorteret efter første gennemløb:
740, 522, 124, 234, 204, 656, 497, 987, 108
Andet gennemløb (midterste tal):
0 204, 108
1
2 522, 124, 127
3 234
4 740
5 656
6
7
8 987
9 497
Sorteret efter andet gennemløb (bageste to cifre)
204, 108, 522, 124, 234, 740, 656, 987, 497
Tredie gennemløb:
0
1 108, 124, 127
2 204. 234
3
4 497
5 522
6 656
7 740
8
9 987
Sorteret efter tredie gennemløb:
108, 124, 127, 204, 234, 497, 522, 656, 740, 987
I den virkelige verden ville man sikkert bruge en 2-potenser i stedet
for 10-potenser når man valgte antallet af spande.
Knus
Regnar
--
Regnar Bang Lyngsø (regnar@writeme.com, regnar@beer.com)
<URL: http://www.daimi.au.dk/%7Erblyngso/>
| |
Bertel Lund Hansen (23-01-2001)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 23-01-01 21:32 |
|
Michael Nielsen skrev:
>Vil man bare arbjede med GUI'er, eller lave simple webmastering, så er
>matematikken af meget lav værdi.
Den er uundværlig, men den er ikke kompliceret.
--
Bertel http://lundhansen.dk/bertel/
FIDUSO: http://fiduso.dk/
| |
Per Abrahamsen (23-01-2001)
| Kommentar
Fra : Per Abrahamsen |
Dato : 23-01-01 11:51 |
|
"Submind" <some45@worldonline.dk> writes:
> Hej Jeg er en 16 årig gymnasie elev ( 1.g ) som har fået fortalt at
> matematik er altafgørende i c++ programering og ville gerne vide om dette er
> sandt, og hvor langt jeg kan nå på det niveau jeg er på nu ( rente
> matematisk 9
En matematisk tankegang vil hjælpe dig som programmør, men at
programmere vil også hjælpe dig i matematik, så bare gå i gang.
| |
Mazzachre (23-01-2001)
| Kommentar
Fra : Mazzachre |
Dato : 23-01-01 19:48 |
|
On Mon, 22 Jan 2001 19:59:03 +0100, "Submind" <some45@worldonline.dk>
wrote:
>Hej Jeg er en 16 årig gymnasie elev ( 1.g ) som har fået fortalt at
>matematik er altafgørende i c++ programering og ville gerne vide om dette er
>sandt, og hvor langt jeg kan nå på det niveau jeg er på nu ( rente
>matematisk 9
Det kommer an på hvad du vil programmere...
For at komme igang med programmering af forskellige små programmer har
du lært alt hvad du skal bruge fra folkeskolen... Hvis du vil
programmere lowlevel 3D rutiner skal du lige have vektor matematik og
fysik til at sidde fast og skal du lave neurale netværk skal du have
en masse mere matematik for at forstå hvad det er der sker..
Men mit råd er at komme igang med at programmere, så finder du selv ud
af når du mangler noget matematik fopr at forstå nogle algoritmer...
så er det bare at lære det, det bliver nemmere at lære når man
pludselig kan se en mening med det (Som fx. med 3D vektorer!)
- Mazzachre
| |
Sune (12-02-2001)
| Kommentar
Fra : Sune |
Dato : 12-02-01 12:01 |
|
Jeg er helt enig (endelig en der var fornuftig).
Jeg har læst matematik i 4 år på KU og hobby programmeret i 7 år i
C++/Fortran/Java....., så jeg tror jeg har en udemærket fornemmelse for
kravene, og matematik er ikke en af dem.
Nu er matematik for mig også noget med at bevise sætninger, det andet kalder
jeg for ingenørregning og det dyrkes ikke så meget på matematikstudiet.
Selve tankegangen der deles kan vist forklares meget kort, nemlig at
funktioner kan tage argumenter og retunere værdier, præcis som i
"matematik". Det er klart at vektorer, matricer, bitoperationer og den slags
kræver en vis matematisk forståelse men det kan læres på en eftermiddag.
Hvis du ønsker at lave GUI og små windows utillities eller den slags har du
overhovedet ikke brug for matematik (selv en sproglig ville rule:).
Men programmering er jo et stort emne og hvis du vil simulere kollisioner af
sorte huller (f.eks.) så skal der dælme "matematik" på bordet.
Selv har jeg faktisk haft mest brug for algebra til programmering, det er
utrolig som de grupper popper op over alt.
"Mazzachre" <muhmuhmuhmuhmuh@hotmail.com> wrote in message
news:99kr6t483prl5mh1b6dda2hdib6bak10ij@4ax.com...>
> Det kommer an på hvad du vil programmere...
>
> For at komme igang med programmering af forskellige små programmer har
> du lært alt hvad du skal bruge fra folkeskolen... Hvis du vil
> programmere lowlevel 3D rutiner skal du lige have vektor matematik og
> fysik til at sidde fast og skal du lave neurale netværk skal du have
> en masse mere matematik for at forstå hvad det er der sker..
>
> Men mit råd er at komme igang med at programmere, så finder du selv ud
> af når du mangler noget matematik fopr at forstå nogle algoritmer...
> så er det bare at lære det, det bliver nemmere at lære når man
> pludselig kan se en mening med det (Som fx. med 3D vektorer!)
>
> - Mazzachre
| |
|
|